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.
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.
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.
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:
Every 4th layer starting at Z=2 | |||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
…+y | … | … | … | … | … | … | … | … | … | … | … |
+4 | … | C | x | F | x | C | x | F | x | C | … |
+3 | … | x | x | x | x | x | x | x | x | x | … |
+2 | … | F | x | V | x | F | x | V | x | F | … |
+1 | … | x | x | x | x | x | x | x | x | x | … |
0 | … | C | x | F | x | C | x | F | x | C | … |
-1 | … | x | x | x | x | x | x | x | x | x | … |
-2 | … | F | x | V | x | F | x | V | x | F | … |
-3 | … | x | x | x | x | x | x | x | x | x | … |
-4 | … | C | x | F | x | C | x | F | x | C | … |
-y… | … | … | … | … | … | … | … | … | … | … | … |
^{y}⟋_{x} | …-x | -4 | -3 | -2 | -1 | 0 | +1 | +2 | +3 | +4 | +x… |
Every layer where Z is odd | |||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
…+y | … | … | … | … | … | … | … | … | … | … | … |
+4 | … | x | x | V | x | x | x | V | x | x | … |
+3 | … | x | F | x | F | x | F | x | F | x | … |
+2 | … | V | x | x | x | V | x | x | x | V | … |
+1 | … | x | F | x | F | x | F | x | F | x | … |
0 | … | x | x | V | x | x | x | V | x | x | … |
-1 | … | x | F | x | F | x | F | x | F | x | … |
-2 | … | V | x | x | x | V | x | x | x | V | … |
-3 | … | x | F | x | F | x | F | x | F | x | … |
-4 | … | x | x | V | x | x | x | V | x | x | … |
-y… | … | … | … | … | … | … | … | … | … | … | … |
^{y}⟋_{x} | …-x | -4 | -3 | -2 | -1 | 0 | +1 | +2 | +3 | +4 | +x… |
Every 4th layer starting at Z=0 | |||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
…+y | … | … | … | … | … | … | … | … | … | … | … |
+4 | … | V | x | F | x | V | x | F | x | V | … |
+3 | … | x | x | x | x | x | x | x | x | x | … |
+2 | … | F | x | C | x | F | x | C | x | F | … |
+1 | … | x | x | x | x | x | x | x | x | x | … |
0 | … | V | x | F | x | V | x | F | x | V | … |
-1 | … | x | x | x | x | x | x | x | x | x | … |
-2 | … | F | x | C | x | F | x | C | x | F | … |
-3 | … | x | x | x | x | x | x | x | x | x | … |
-4 | … | V | x | F | x | V | x | F | x | V | … |
-y… | … | … | … | … | … | … | … | … | … | … | … |
^{y}⟋_{x} | …-x | -4 | -3 | -2 | -1 | 0 | +1 | +2 | +3 | +4 | +x… |
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:
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:
"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.
shared face | neighbor cell | |||||
---|---|---|---|---|---|---|
face index | X_{F} | Y_{F} | Z_{F} | X_{C} | Y_{C} | Z_{C} |
0 | -1 | -1 | -1 | -2 | -2 | -2 |
1 | +1 | -1 | -1 | +2 | -2 | -2 |
2 | -1 | +1 | -1 | -2 | +2 | -2 |
3 | +1 | +1 | -1 | +2 | +2 | -2 |
4 | 0 | -2 | 0 | 0 | -4 | 0 |
5 | -2 | 0 | 0 | -4 | 0 | 0 |
6 | +2 | 0 | 0 | +4 | 0 | 0 |
7 | 0 | +2 | 0 | 0 | +4 | 0 |
8 | -1 | -1 | +1 | -2 | -2 | +2 |
9 | +1 | -1 | +1 | +2 | -2 | +2 |
10 | -1 | +1 | +1 | -2 | +2 | +2 |
11 | +1 | +1 | +1 | +2 | +2 | +2 |
acute vertex "L" | acute vertex "R" | obtuse vertex "B" | obtuse vertex "T" | |||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
face index | X_{V0} | Y_{V0} | Z_{V0} | X_{V1} | Y_{V1} | Z_{V1} | X_{V2} | Y_{V2} | Z_{V2} | X_{V3} | Y_{V3} | Z_{V3} |
0 | 0 | 0 | -2 | -2 | -2 | 0 | 0 | -2 | -1 | -2 | 0 | -1 |
1 | 0 | 0 | -2 | +2 | -2 | 0 | +2 | 0 | -1 | 0 | -2 | -1 |
2 | 0 | 0 | -2 | -2 | +2 | 0 | -2 | 0 | -1 | 0 | +2 | -1 |
3 | 0 | 0 | -2 | +2 | +2 | 0 | 0 | +2 | -1 | +2 | 0 | -1 |
4 | -2 | -2 | 0 | +2 | -2 | 0 | 0 | -2 | -1 | 0 | -2 | +1 |
5 | -2 | +2 | 0 | -2 | -2 | 0 | -2 | 0 | -1 | -2 | 0 | +1 |
6 | +2 | -2 | 0 | +2 | +2 | 0 | +2 | 0 | -1 | +2 | 0 | +1 |
7 | +2 | +2 | 0 | -2 | +2 | 0 | 0 | +2 | -1 | 0 | +2 | +1 |
8 | 0 | 0 | +2 | -2 | -2 | 0 | -2 | 0 | +1 | 0 | -2 | +1 |
9 | 0 | 0 | +2 | +2 | -2 | 0 | 0 | -2 | +1 | +2 | 0 | +1 |
10 | 0 | 0 | +2 | -2 | +2 | 0 | 0 | +2 | +1 | -2 | 0 | +1 |
11 | 0 | 0 | +2 | +2 | +2 | 0 | +2 | 0 | +1 | 0 | +2 | +1 |
Each face in a rhoxel has two triangles. This sequence will produce two triangles with a counter-clockwise winding order:
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: