Dual Contouring with Sphere Packing

dcsp.txt

after a sleepness night of faces, edges and vertices rotating in my head I got
this idea this morning:

"Dual Contouring with Sphere Packing"

sample volume of implicit function on vertices and edges of the FCC lattice;  
we get a set of hermite points denoting planes crossing the FCC edges, and
spherical center points that are either "inside" or not.

create vertices in voronoi diagram of lattice: the rhombic dodecahedral honeycomb,
which is equivalent to the soap foam model of perfectly stacked spheres. We treat
each rhombic dodecahedron as one "sphere".

we construct the vertices and faces of the honeycomb on an offset FCC lattice
as well, too; 
each vertex marks the empty space between six touching "spheres" and is connected 
to intersection points of type 2, where four spheres meet. 
The six-sphere singularity is equivalent to the center of the octahedra of the FCC
lattice, while the four-sphere singularity is the center of the tetrahedra.

to decide whether to construct a face or not, we look at the differential of the
vertices of the octahedron that describes the centers of the neighboring spheres.
if one vertex is set, and one is missing, then a sphere meets open air: we 
construct a face pointing away from the set vertex. the end points of the face are
the intersection points computed from the hermite data using the QEF; this way
we ensure that all vertices lie on the surface of the implicit function. 

there's also the option to construct the honeycomb vertices and faces on a
cubic lattice, if using the tetrahedral centers rather than the octahedral
centers; in this case, translation is invariant, but the face coordinates are mirrored
in a checkerboard fashion. here we construct at most six faces, as opposed to the
twelve faces at the octahedral centers; or rather, as faces are shared with neighbors,
three faces tetrahedral instead of six octahedral.

by default, the faces are constructed by splitting up each rhombic face along
the short diagonal edge. but we could also split it up along the long diagonal
edge - how to decide? fortunately, because our honeycomb is the voronoi diagram
of the FCC lattice, we have a guaranteed sampled hermite point on the edge
that passes through the center of the face.

therefore we split up the face along the edge that is closer to the surface to
get an optimal result.

The work is neatly parallelizable on the GPU, but in comparison to my earlier 
approach, we don't store the vertices anymore, but the hermite data and the
"is inside" flag at the sphere centers. I'm not sure how that data can be useful
for editing that extends beyond basic CSG operations, but at least it does that
part well, and can be easily summed and subdivided.

There's also a chance for some reversal of the operation (and aren't symmetric
operations the best), where the faces can be easily sampled back into new 
hermite data.

------------------------------

Implementation notes:

when constructing from the tetrahedral centers, two cases are possible, case A
or case B, where the selector is (x^y^z)&1 == 0; the basis vectors of each 
rhombic face are, for example, for case A

(1, 1, 1) (1, -1, -1) (2, 0, 0) facing (1, -1, 1) (1, 1, -1)
(1, 1, 1) (-1, 1, -1) (0, 2, 0) facing (-1, 1, 1) (1, 1, -1)
(1, 1, 1) (-1, -1, 1) (0, 0, 2) facing (-1, 1, 1) (1, -1, 1)

and for case B

(1, -1, 1) (1, 1, -1) (2, 0, 0) facing (1, 1, 1) (1, -1, -1)
(-1, 1, 1) (1, 1, -1) (0, 2, 0) facing (1, 1, 1) (-1, 1, -1) 
(-1, 1, 1) (1, -1, 1) (0, 0, 2) facing (1, 1, 1) (-1, -1, 1)

you can see that the lattice points opposing each face are each others
complement.

the mapping coords into the FCC grid from memory index (i,j,k) are

x=i
y=j
z=2*k+(i%2)+(j%2)

the conversion from FCC grid coordinate to memory index is

i=x
j=y
k=(z-(x%2)-(y%2))/2

while the mapping coords into the dual cubic grid from (i,j,k) are

x=i+1/2
y=j+1/2
z=k+1/2

to reach the corner points using one of the the basis vectors v(i), one uses p + v(i)/2