A different kind of transform

Lordy. What a long strange path to get back to Tetrahedral coordinates. I started this particular leg of this long journey with the assumption that I really needed a Body Centered Cubic grid for my whacky spatial modularization/caching scheme. I have been pursuing this path most vigorously when I realized that what I really needed was a different transform.

Stepping back a bit, I pondered the problem I was originally trying to solve, rather than a problem of a particularly promising path which may or may not be relevant to the original problem. Previously, I had modeled my storage as a 3 dimensional matrix, where the spheres live in the cubic grid cells. As I discovered along the way, you only fill up half of the cells in the cubic grid in this construction You can actually get two grids of closest packed spheres stored this way in a cubic grid. Something, in retrospect, that should have clued me in almost immediately (but sometimes it takes me a while to catch on).

Inverting the Problem

The fundamental rat hole I had gotten caught in was thinking about the target grid coordinates in the wrong way. These coordinates were the index into a simple array based storage model for the spatial cache. In the model I have described, it’s storing spherical packing grids in cubic grids. What I need to do is the inverse. I need to store spherical packing grids in a three dimensional grid, where every integer address – 3D point – is the center of a cell in the grid.

Here’s an example. Say that my avatar in a simulation is in the cell with address:
{ 565, 56, 123 }
These numbers correspond to the traditional X, Y and Z values in a three dimensional point. However, rather than referring to the Cartesian X, Y and Z basis, our X, Y and Z numbers refer to non orthogonal basis vectors.

To make a long story short, I found that someone had posted a Python Gist describing a butt simple way to convert Cartesian grid coordinates to and from Tetrahedral coordinates. I had previously discounted Tetrahedral grid coordinates because I had not found a three dimensional basis scheme. I had alway seen the combinatorial four dimensional tetrahedral coordinate scheme. I really didn’t want a grid where I had to deal with relationships and duplication between the coordinates. I mean, it’s like Perl, for “Bob’s” sake. You really don’t need multiple coordinates to refer to the same cell.

So that was pretty amazing. I had also previously found another paper by the same folk who produced the BCC grid I referred to. This is a Face Centered Cubic grid using the Rhombic Dodecahedron as the cell.

They produced a Rhombic Dodecahedron FCC grid where each integer 3D point is the center of a cell. It’s quite cool, frankly, and before I really groked the 3D Tetrahedral coordinates, I had gone down quite the path using this coordinate scheme.

You can see my Zome model of such basis vectors above. One clever things about this basis is that the X and Y axes are orthogonal. The Z axis is bent off both with the result that each axis in the basis goes through the centers of the faces. Again, very cool that I can just represent this with nothing special in Zome.

The picture above is the same basis as the previous image, but I’ve added the Cartesian basis vectors in blue. These vectors are the original basis that are then warped into the resulting non orthogonal basis developed in the paper.

Anyways, cool paper if you’re into that kind of thing.

A Grid For All Headings

So I finally have a pretty workable grid abstraction for my wacky spatial caching scheme and it is compact. The video below shows the Tetrahedral coordinate system that I’m using to address each of the spheres in the spherical packing grid. As you can see, it’s a non orthogonal grid as well, but unlike the basis discussed previously, this basis has no orthogonal vectors – it’s Tetrahedral.

The video starts with just the three basis vectors of the Tetrahedral coordinate system I’m using. The image one should have is basically two tetrahedra joined at a vertex at the origin. The X, Y and Z vectors basically trace the edges of the two opposed tetrahedra – opposites, of course; mirror images. I also flip on the trad Cartesian basis vectors for comparison to the Tetrahedral coordinates.

To refresh our memory wrt sphere packing, the video above demonstrates how the cells pack. The center sphere is any particular cell in our shiny new grid. The 12 blue spheres are the nearest neighbors of the cell. The resulting polyhedron the blue spheres make is, of course, the Cuboctahedron. The Cuboctahedron is, of course, the dual of the Rhombic Dodecahedron.

In the video above, you can see the Rhombic Dodecahedron Grid in action, so to speak. This is a 3x3x3 grid where each integer point is a sphere. As with the previous video, the center sphere is at grid point {0, 0, 0} and is green (although you can barely see it – lol). The 12 neighboring spheres are blue as before and you can see the shape starting to take pace, which is basically a squashed cube: the Parallelepiped.

And like any self respecting grid, you can keep this pattern going. In a sphere packing, you just get more and more shells around your kernel – i.e. {0, 0, 0}. The video above shows a 21x21x21 grid. You can clearly see the Parallelepiped shape made by iterating over the cubical array of coordinate points. Very cool. You’ll also note that the Parallelepiped allows us to basically make use of every integer coordinate, rather than only half as what I had started out with previously.

The weird ass basis vector of the Parallelepiped can be used as Tetrahedral coordinates. Who would have guessed?

Well, probably everyone else but me of course. Still, now that I know about this, it really makes perfect sense to my twisted brain. Which is precisely what one would expect to be said by someone losing their mind to alternate geometries and projective spaces. precisely.

Scaling

So with all that in place, all that’s left is to really just use Rhombic Dodecahedrons instead of spheres. Which, believe me, is really a lot easier said than done – lol.

In this video, I’ve separated out the individual cells and expanded the grid, rather than keeping all the cells closest packed as befits a grid. I’m not that great with opacity and culling in JavaFX as of yet, so if I didn’t expand it, one would not be able to see inside the grid structure. This is in contrast, of course, with the spherical versions of this grid where there’s a decent amount of space and even clear-through lines throughout the grid.

And here’s the final product. While certainly not something I’m finished with yet, the RDG functional grid abstraction is quite serviceable for my needs. You can check out the viewer in my Luciferase project.

It was quite entertaining getting an algorithm to make all this stuff happen graphically. It’s a lot harder than it looks simply because the whole thing is operating in a different space than what we normally inhabit when we think of how we modularize and address the space we, ourselves, are embedded in. I mean, just scaling the Tetrahedral → Cartesian mapping, with a couple of square roots of 2 thrown in for good measure.

I’ll have to sit down sometime and figure out if I can simplify and eliminate some of those constants, but at this point I’m simply happy to have a compact effing Rhombic Dodecahedron grid I can start building upon.

The Next Target

So now that I have a serviceable FCC grid, that is also compact and utilizes every integer grid coordinate, I can start on the real work. The “storage” structure for our spatial cache is literally a three dimensional grid where each cell is a sphere and the spheres form a closest packing and shaped like a Parallelepiped rather than a Cube. Thus trivial and works like everyone else’s grid storage on the planet. The Voronoi domain of these spheres is the Rhombic Dodecahedron. And so this polyhedron becomes the way we divide up space.

And how we divide up the Rhombic Dodecahedron is what is next on the menu.