Creating Rhoxel Meshes From Integer Coordinates

What is a "rhoxel"?

It's word I made up. "Rhoxel" is a portmanteau of rhombic dodecahedral honeycomb element, with the obligatory spurious x in the middle so you know it has something to do with graphics. I'm not writing the phrase "rhombic dodecahedral honeycomb element" more than twice in this post.

Anyways. A singular rhoxel is a rhombic dodecahedron. They have 12 congruent sides, and each side is a rhombus. When you project them orthographically, there are 6 viewpoints where they look like squares, and 8 viewpoints where they look like hexagons. What is really neat about rhoxels, is you can calculate their center points, the centers of their faces, and all of their vertices relative to an integer coordinate system. Translating from the integer grid to real coordinates only requires multiplying a few constants.

The purpose of this page is to explain how to construct these in relatively plain language. There are probably plenty of formal definitions out there for the people who need them.

First, some examples

Quantization Example

In the animation above, a signed distance field model of a flower is quantized to rhoxels with gradually increasing density. As the density increases, the rhoxel face normals are gradually blended with the distance field gradient to give the model a smoother appearance.

Rotation Example

In the animation above, a signed distance field model of an abstract shape has been quantized to a fixed rhoxel density with flat shading, and is slowly rotating to emphasize how the cells look at different angles.

The Grid

Our goal is to construct a grid of spheres in a tightly packed face-centered cubic lattice. However, ignore the construction rules in that wikipedia article, because they're over complicated. Instead, we're going to try to construct something like this:

In the above image, the spheres are arranged in an ordinary square grid in each X/Y plane, and these planes are staggered. The offset for each layer is (radius, radius, radius * √2). If we were to multiply the radius of each sphere by √2 (without changing their spacing), the empty space in the lattice is eliminated.

If we were to further clip the expanded spheres with planes placed in the center of their overlaps with other spheres, the result is a set of rhombic dodecahedra (or, rhoxels if you will).

However, repeatedly bisecting convex hulls is a terrible way to construct triangle meshes ^{[citation needed]}. The problem here essentially boils down to floating point numbers being absolute dog shit for this sort of thing.

On the other hand, integers have never wronged anybody so maybe we can just construct a grid with just integers and worry about the square roots later? Well it turns out you can, and not only can you use this to enumerate the rhoxel centers, but you can also use this to enumerate the center points for each face and all of the vertices.

To do this we will use an integer grid where each unit corresponds to half a radius. In other words, the sphere centers are always 4 units apart on the X or Y axis in the integer grid.

The following three tables illustrate the repeating grid pattern with this key:

• C is the center of a cell
• F is the center of a face
• V is a vertex
• x contains nothing important

Easy peasy, yeah? Great.

To convert the integer grid coordinates into the desired floating point coordinates, multiply the integer coordinates with some constants like so:

• X_float = X_grid * radius * 0.5
• Y_float = Y_grid * radius * 0.5
• Z_float = Z_grid * radius * 0.5 * √2

Alright! Let's apply the above information.

Suppose you've picked out a rhoxel that you really like, and it has the integer grid coordinates (-4, 4, 2).

Let's also arbitrarily say your sphere lattice has a radius of 9.

Thus, you'd calculate the center position like so:

• X_float = X_grid * radius * 0.5 -4 * 9 * 0.5
• Y_float = Y_grid * radius * 0.5 4 * 9 * 0.5
• Z_float = Z_grid * radius * 0.5 * √2 2 * 9 * 0.5 * √2

"Ok but what about the coordinates of face centers and vertices?" excellent question, imagined reader! You use the exact same formula.

"Ok but how do I know which thing belongs to which other thing?" easy! You can use the following lookup table. Actually wait, let me drop a <h2> for the people who are just skimming.

Enumerating a Rhoxel's Neighbors

Enumerating a Rhoxel's Vertices

Generating Vertices

Each face in a rhoxel has two triangles. This sequence will produce two triangles with a counter-clockwise winding order:

1. emit XYZ_V0
2. emit XYZ_V2
3. emit XYZ_V3
4. emit XYZ_V3
5. emit XYZ_V2
6. emit XYZ_V1

Ideas

1. With some polish, you could use this as an alternative to Marching Cubes and similar meshing strategies.
2. The underlying lattice is one of the variations on the densest possible packing of equal spheres. I suspect this may be a useful property for discretizing signed distance fields, as it may minimize the number of evals needed vs another regular lattice. SDF evals take a point and produce a radius, so you can think of SDF evaluation as an act of producing many spheres. However, the spheres produced by SDF evals are not uniformly sized, so this might not be the right tool for the job.
3. An alternative lattice for voxel art that doesn't look like everyone else's voxel art (yet).
4. Cellular automata!

Help I Can Only Read Python!

I put together a little stand-alone demo that uses all this to generate a little fractal thing.

Here's the source code, the model it generates, and a rendering of the model: