Xylem experiments and improvements

We have been working on the system we used to create the Xylem line in preparation for making a new collection of 3D printed pieces, including jewelry, lighting and furniture. We are extending the functionality and improving the performance of the simulation to take the designs from 2D cut pieces to fully 3D ones. For a bit more of an explanation of some of the things I refer to in the post, see the original paper that this system is based on.

First and foremost is making the system work in 3D. The original system uses a Delaunay triangulation to determine source neighborhoods. This allows the creation of closed cells. Closed cells are not only desirable for us aesthetically, but necessary for improved structural stability when we are making 3D prints. Having a bunch of unconnected branches would be too weak for functional plastic pieces. Computing Delaunay triangulations becomes much harder in 3D, so we switched over to C++ in order to use CGAL, an open source library of computational geometry algorithms. The other major challenge is producing the 3D surface itself from the vein data. For our previous 3D printed line, we created a simple mesh skeleton and smoothed it using subdivision surfaces. This was possible because we had a very orderly surface. However, the venation patterns are much more chaotic and it is harder to determine how things are connected. Instead, we used an implicit surface technique. This means defining a function everywhere in space which essentially returns 1 inside the surface and -1 outside the surface. A common method for computing a surface for such a function is called marching cubes. However, CGAL has an implementation of a much more sophisticated algorithm which produces higher quality meshes. We also use a CGAL implementation of Axis-Aligned Bounding Box Trees to do quick intersections and projections to a boundary surface that we import to constrain the growth. CGAL kills many birds with one stone.

These are the basic elements for a 3D growth. By projecting onto the surface as the system grows, we can also create growth on a surface as seen in this test cuff we made.

That is just the beginning of the changes we’ve been working on. We were also dissatisfied with the character of the growth. Generally, the algorithm does not produce one of the main things we would expect from venation, a primary central vein with secondary veins perpendicular to it. Everything just tends to grow out at the same time, causing veins to be more parallel then we would like. This contrasts with the real theory of how veins form based on a positive feedback mechanism between flow and flow rate. The primary vein starts to form first, then secondary and tertiary veins. To attempt to inject some of that hierarchical logic into our system, we changed the growth rules. Instead of veins growing in the average direction of all the sources flowing to them, veins grow probabilistically, the more sources flowing to a vein the more likely that vein is to grow. This anticipates which veins become primary or secondary and grows them first.

One problem with probabilistic growth is it is inherently much slower. Each step of the simulation takes just as long, but instead of all the veins growing only a small percentage grow. This led to an idea to make the simulation much faster. The way we determine which veins a source flows to is we temporarily insert that source into a Delaunay triangulation of all the veins and look at the neighbors within that triangulation. This is a computationally costly step. The thing to note is that only new veins that we add in each step of the simulation can possibly be added to or change a sources neighborhood. This is because the veins and sources never move, so adding a new vein could never cause an old vein that was not previously a neighbor to become one. Instead of keeping track of a global triangulation that gets bigger and bigger with every step of the simulation, we only keep track of the local neighborhood for each source. Since the size of the neighborhood of each source stays small, the number of new veins added in each step stays small, and the number of sources is constantly decreasing, this means that as the simulation progresses it actually gets faster (in practice it slows down sharply until the number of veins added normalizes and then gradually speeds up). The key element is to keep track of the neighborhood of each source. The relative neighborhood of veins the source actually flows to is insufficient. That information cannot be used to figure out which new veins are neighbors. Instead we let each vein represent a half plane that points away from the source. Any vein that is within this half plane cannot be the sources neighbor. It is blocked by the vein that defines that half plane. We need to keep track of the minimal set of such veins. Essentially we are defining a convex shell around each source, outside of which nothing can be a neighbor of the source. Maintaining that data structure is a similar problem to linear programming, though because the problem is in a low dimension and we incrementally add each point, it is efficient to take a fairly brute force approach. Long story short, this turns out to be much more efficient. Allowing us to create probabilistic growths faster than we used to make deterministic ones.

Delaunay triangulations in 3D are even more computationally difficult than in 2D. Using CGAL, it takes us several hours to make one growth. So applying this new technique in 3D is even more powerful. It is more difficult to keep track of the convex shell around each source, but it is still much faster. We have not finished implementing this yet, but we have made a video of our preliminary results which looks pretty promising. The next step is to insert this into our framework that uses CGAL to create the 3D mesh.

Sorry the video quality is so poor. It does not seem to compress well.

Another aspect I would like to work on is growth on a surface. Right now, we apply the 3D algorithm with sources confined to a surface and we also project each vein onto the surface. This is fine for simple surface, but for surfaces on which there is a large difference between the distance along the surface and the distance through space this can cause a problem. I would like to use geodesic distances to compute neighbors instead of distance in 3-space. This presents a lot of challenges which we are still working on.

This entire exposition would be a lot clearer with a few nice diagrams, but that is a little more in depth than I can muster right now. Stay tuned for more results and new designs with this system.