<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0//EN" "http://www.w3.org/TR/REC-html40/strict.dtd">
<html><head><meta name="qrichtext" content="1" /><style type="text/css">
p, li { white-space: pre-wrap; }
</style></head><body style=" font-family:'Ubuntu'; font-size:11pt; font-weight:400; font-style:normal;">
<p style=" margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; -qt-user-state:0;">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.</p>
<p style="-qt-paragraph-type:empty; margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; "> </p>
<p style=" margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; -qt-user-state:0;">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":</p>
<p style="-qt-paragraph-type:empty; margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; "> </p>
<p style=" margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; -qt-user-state:0;"> pivot(a, b, c, d) {</p>
<p style=" margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; -qt-user-state:0;"> swap(next(a), next(c))</p>
<p style=" margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; -qt-user-state:0;"> swap(next(a), next(b))</p>
<p style=" margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; -qt-user-state:0;"> swap(next(a), next(d))</p>
<p style=" margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; -qt-user-state:0;"> }</p>
<p style="-qt-paragraph-type:empty; margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; "> </p>
<p style=" margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; -qt-user-state:0;">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.</p>
<p style="-qt-paragraph-type:empty; margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; "> </p>
<p style=" margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; -qt-user-state:0;">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.</p>
<p style="-qt-paragraph-type:empty; margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; "> </p>
<p style=" margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; -qt-user-state:0;">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.</p>
<p style="-qt-paragraph-type:empty; margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; "> </p>
<p style=" margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; -qt-user-state:0;">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.</p>
<p style="-qt-paragraph-type:empty; margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; "> </p>
<p style=" margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; -qt-user-state:0;">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.</p>
<p style="-qt-paragraph-type:empty; margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; "> </p>
<p style=" margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; -qt-user-state:0;">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.</p>
<p style="-qt-paragraph-type:empty; margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; "> </p>
<p style=" margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; -qt-user-state:0;">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.</p>
<p style="-qt-paragraph-type:empty; margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; "> </p>
<p style=" margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; -qt-user-state:0;">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.</p>
<p style="-qt-paragraph-type:empty; margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; "> </p>
<p style=" margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; -qt-user-state:0;">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.</p>
<p style="-qt-paragraph-type:empty; margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; "> </p>
<p style=" margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; -qt-user-state:0;">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.</p>
<p style="-qt-paragraph-type:empty; margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; "> </p>
<p style=" margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; -qt-user-state:0;">Regards,</p>
<p style="-qt-paragraph-type:empty; margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; "> </p>
<p style=" margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; -qt-user-state:0;">Daniel</p>
<p style="-qt-paragraph-type:empty; margin-top:0px; margin-bottom:0px; margin-left:0px; margin-right:0px; -qt-block-indent:0; text-indent:0px; "> </p></body></html>