I need a break from Delos, and so I’m back on one of my many other Hobby Horses; that being the subdivision of space. Not for pure mathematical curiosity, mind. Rather, as a mechanism to store and retrieve Assets from ye storage in a networked, virtual environment. It’s what got me back into blogging again, and it’s something I’ve had on the back burner for far longer, so it’s always nice to make some progress on this project.
Adaptive Mesh Refinement
In my mad info search on spatial indexing I did a couple of years back, I stumbled across a rather amazing paper (and Thesis, lol): A tetrahedral space-filling curve for non-conforming adaptive meshes

The figure above is from the paper, and boy is it one of the coolest things I’ve ever seen. One of the key insights I gleaned is that you don’t have to keep subdividing the tetrahedrons to get to the refinement level target. You can simply subdivide the cube to the desired refinement level, and then subdivide that cube into tetrahedrons. Just mind blowing for me.
They also have a nice presentation of the concepts of the paper, focusing on how they can map this tetrahedral subdivision of space to a space filling curve – the Morton “Z” curve, in particular.

Just wonderfully clever and quite the beautiful thing to behold.
Also, too, scales to the bejesus belt.
A Remarkable Subdivision
The Tetrahedron that this mesh refinement uses is known as the Sommerville Type 1 Tetrahedron

This is a remarkable tetrahedron and suits my needs for a modular, indexed storage mechanism that is tetrahedral. If you dig back to my earlier posts on these subjects, you’ll see that I have a dynamic point tracking grid that I intend to use for my event driven simulations. This grid system tetrahedralizes space in a Delaunay mesh of the tracked points.
One of the uses I have for this spatial index is to provide modular refinement of space to smoothly and efficiently manage the animation of my virtual spaces. A key piece of dynamic animation is being able to quickly and easily address one’s nearest neighbors. The Delaunay tetrahedralization – and its dual, the 3D Voronoi – provides a most efficient mechanism for these kinds of searches. Searches that one must do every simulation “tick” and so forms a foundational piece for my event driven simulation framework.
This framework gives me a way to modularly split and refine the domains of controllers that are tracking dynamically moving entities, and are responsible for their event driven simulation. Think of them as domain controllers for simulation entities. And given the swarming and clumping nature of these entities, it is useful to implement a splitting/combining strategy based on modular refinement.
Using tetrahedral modules means I can use these tetrahedrons for the “big tetrahedron” that the tracking grid uses as the boundary for the tracked points. These Type 1 tetrahedra stand in for the maximum tetrahedral extent, and can either be zipped together as the swarming of simulated entities thins out, or modularly split, shedding simulation load to a new controller.
Modular Storage
And then there’s one of the original goals I have, which is to provide a modular asset storage grid that is most suitable for streaming large scale simulations’ spatial assets. It’s pretty cool in that all the tetrahedra are similar, and if I further subdivide the Type 1 tetrahedra into 2 more, I get the totally congruent Type 2 tetrahedra as a fundamental storage geometry. Which is also easy to modularly tetrahedralize, of course – lol.
So that is all very cool and unexpected. And it’s gotten me back into my Luciferase code base, implementing this Tetrahedral spatial index. I’ll likely post more about that as that completes, but it is simply amazing and highly entertaining.
I also found an unexpected toy that is cleverly composed of Sommerville Type 2 tetrahedra using magnets

Two of these Type 2 Tetrahedra combine to form the Sommerville Type 1 Tetrahedra, so I’ve been having a blast with that. When I get my light box set up again, I’ll post some picks. I bought 6 of these puppies and going to buy another 2 so I can emulate a refinement level of 1 in actual physical reality.

You can see that I can make 2 Rhombic Dodecahedrons, and have 2 cubes left over. Quite gorgeous in a glowing fashion and gives me an endless source of pondering that isn’t an Orb.


Leave a Reply