[World] Boolean Surface Geometry

[Daniel Phillips]

The general case of sectioning meshes along arcs (step 4 of 5) now appears to 
work, including nontrivial combinations of open and closed surfaces and 
multiple intersections per surface. Solid16.png shows a tetrahedron subtracted 
from the middle of an open mesh.

In the process of doing the tricky arc cutting I discovered a wonderful new 
Euler operator (an operator that always takes a mesh from one valid state to 
another) called "pivot":

	pivot(a, b, c, d) {
		swap(next(a), next(c))
		swap(next(a), next(b))
		swap(next(a), next(d))
	}

where a, b, c, and d are half edges. Wow, how can that do anything 
interesting, it is just three swaps!? But in fact it does something very 
interesting: it reroutes two pairs of oppositely oriented edges (a ring edge 
and its twin or two paired half edges) where all edges are incident on the 
same vertex, so that each edge "turns left" at the vertex instead of going 
straight through. So to cut a mesh by an arc, I first create a ring going all 
around the (closed) arc, then twin it. This creates exactly the right 
conditions to apply the pivot operator at each vertex, leaving a cleanly split 
mesh with boundary rings at its edges. I used to do this in a far more complex 
way that was nigh on impossible to read let alone debug. This new way is tiny 
code that is blindingly fast. Look at it, just three swaps. One nanosecond per 
vertex or thereabouts.

Well, it is not quite so simple because pivot has an additional annoying 
property: if you provide the edge parameters in the wrong order, instead of 
splitting the mesh it tangles it. And trust me, it is way easier to tangle a 
mesh than split it. The right order to give the parameters depends on arcane 
details of the essentially random order in which edge intersections are 
detected. In the end, the correct logic was simple, efficient and easy to prove, 
but getting there required some serious head scratching.

How do you debug this stuff? With great difficulty. Soild17.png  shows how I did 
it this time, a schematic view augmented to show the mesh topology details so 
I don't have to go crazy staring at tables of halfedge link numbers. In this 
case, all the links point exactly where they should. Of course there were 
other situations along the way where the links appear as a big tangled 
hairball instead of the nice consistent counterclockwise faces we see here. 
This enhanced schematic allowed me to track down bugs about a hundred times 
faster than previously, no exaggeration.

Notice that one of the faces in the sectioned mesh has six sides. There is 
actually no limit to the complexity of the polygons of a mesh intersection. 
Though most non-triangular faces will be convex and therefore easy to 
triangulate, the general case requires the services of a full polygon 
triangulator.  Which fortunately we have, otherwise that would be a reason to 
stop right here and spend weeks getting one.

Intersected polygons do have some helpful properties: 1) they always lie in 
the plane and within the bounds of exactly one original face; 2) each result 
edge is a segment of some original edge; 3) edges never cross. The last point 
is important because my triangulator fails if edges cross (and something needs 
to be done about that). Anyway, I should probably add a new step to the full 
algorithm: retriangulate, which comes right after sectioning and before the 
last step, reassembly.

Solid18.png and solid19.png are exploded renderings I made to clarify how this 
all works. The first image shows a tetrahedron/surface intersection yielding 
five separate mesh parts. One result part is a small, zero volume ring that 
puzzled me for a while until I realized that it really belongs to the green 
tetrahedron. It is the small slit where the other surface penetrates the back 
face.

The other interesting thing about the green tetrahedron is the zero-area slit 
on the front. It is not immediately obvious what this might be useful for. 
Well, it provides an attachment point to which one or two of the other 
fragments can be glued exactly, if that is what we want. And if we do that, 
the result will all make sense and be a consistent mesh, but it is definitely 
not something you could do with traditional constructive solid geometry. As I 
may have mentioned earlier, this new algorithm includes all of traditional 
constructive solid geometry as a subset. So actually, this is pretty exciting, 
if you are the kind of person who gets excited by things like this.

I made a quick survey of the literature, and as far as I know, this new 
approach to boolean combination is unique, and nothing similar has been 
published. So on the assumption that I actually discovered it, I get to name 
it. Tentatively, this will be called "Boolean Surface Geometry" (BSG), a 
superset of constructive boolean geometry (CSG). In BSG, we dispense with any 
notion of inside and outside, and instead rely only on adjacency, boundaries 
and local orientation. For some constructions (any closed manifold) it is 
indeed possible to define inside and outside precisely in BSG, but the general 
case also has open manifolds as in these images, which do not have inside and 
outside, only front and back.

In CSG parlance, such volume-less structures are called "non-manifold" and can 
result from various CSG operations. They must be removed by some separate 
algorithm in a "clean up" step before further CSG operations can take place. 
So CSG is incomplete in the sense that the result of a CSG operation may not 
have a well defined inside. But "BSG" (boolean surface geometry) is complete, 
because the result of any boolean operation on a collection of open or closed 
manifolds is always a collection of open or closed manifolds. Or in other 
words, the group of boolean operations on open meshes form a mathematical 
"ring" while those of CSG do not. Or in other words, BSG is well defined for 
open manifolds while CSG is not. So this is not just a nice new algorithm, but 
a (seemingly obvious) extension of a significant part of computational 
geometry.

The last attached image is a simpler alignment that produces three result 
surfaces instead of five. But it is actually the most computationally complex 
example so far, because there are multiple edges of each original mesh part 
interpenetrating multiple faces of the other. This, and many other examples, 
are now working reliably. So pretty soon it will be on to the final step: re-
triangulate and recombine the segmented surfaces to create some shiny demo 
images. And shortly after that, I hope to use this new tool to model a nice 
solid catapult, which is after all, the whole point of this effort.

Regards,

Daniel
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://phunq.net/pipermail/world/attachments/20120621/56823e55/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: solid16.png
Type: image/png
Size: 28608 bytes
Desc: not available
URL: <http://phunq.net/pipermail/world/attachments/20120621/56823e55/attachment-0004.png>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: solid17.png
Type: image/png
Size: 26118 bytes
Desc: not available
URL: <http://phunq.net/pipermail/world/attachments/20120621/56823e55/attachment-0005.png>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: solid18.png
Type: image/png
Size: 41348 bytes
Desc: not available
URL: <http://phunq.net/pipermail/world/attachments/20120621/56823e55/attachment-0006.png>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: solid19.png
Type: image/png
Size: 34509 bytes
Desc: not available
URL: <http://phunq.net/pipermail/world/attachments/20120621/56823e55/attachment-0007.png>