Triangular Crystal Growth

A small simulation which begins from a "seed" set of triangles, growing new ones from each available vertex while taking care than any newly-added triangles do not overlap any existing triangles.

Because the set of triangles grows exponentially, several optimizations were tested to keep the simulation running as close to real-time as possible. First, the triangles are grown one-by-one rather than growing all triangles from a whole iteration at once. This ensures that the actual rendering of new triangles is always done in constant-time and that the program never takes on a work load large enough to prevent a user from closing the application.

The next problem is collision detection. As can be seein in the image to the right, newer (smaller) triangles even after many iterations may still be in a position near the original seed triangles (the largest). This means we can't cull existing triangles from the set we need to compare against based on their age or size. Several spatial data structures were used before I finally settled on inserting each new triangle into an R-Tree and using it to manage the data for collisions. With the tree, performance remains acceptable up until well after new triangles are being created with a width of just 1 or 2 pixels. At this point, the overal shape does not change much, so there is little point in running the simulation further. A better optimization if it becomes necessary to run the simulation even longer would probably be to render every triangle to a bitmap, and then test new triangles against the pixels on a sub-region of the bitmap. With such an approach, the simulation could probably run indefinitely on a fixed-size bitmap (but it's not as much fun as using R-Trees!).

Play online here