[World] We have an intersection

[Daniel Phillips]

The attached image shows a solid tetrahedron subtracted from an open mesh. A 
lot of things are going right here, and though some finishing work remains, 
this is not far from being usable. I may have mentioned it before, but 
handling open meshes is a lot more complex than closed meshes because of the 
larger number of permutations of boundary edge, interior edge, and face 
adjacencies. Fortunately, this is as complex as it gets. Topologically 
speaking, besides boundary edges, interior edges, and faces there isn't 
anything else.

It is interesting how an intersection arc goes about cutting a mesh. Each arc 
segment splits an edge of one or the other of the intersecting surfaces, 
creating a new vertex.  Then a bundle of four new half edges is created to 
join each pair of neighbour vertices along the arc, two running in each 
direction. Why four? Because each surface will be split into two parts, 
needing two new boundary rings. And there are two surfaces. So four edges per 
arc segment. And each of the new vertices is shared by four half edges, at 
least for a while.

If this algorithm were implemented using the traditional half edge mesh 
approach, which uses two half edges instead of one to represent each boundary 
edge, this arc cut operation would generate eight new half edges per arc 
segment, which is getting a bit out of control. Some of those new edges would 
be freed later when recombining mesh sections to make solids, causing 
allocation churn. So this is an good example of how the AHEM approach saves 
nontrivial amounts of processing time and memory.

Of course it would be possible to optimize away some of those half edge 
allocations that will be deleted instead of becoming part of the final result, 
but at the cost of having an inconsistent intermediate mesh (a pain for 
debugging because the mesh might be invalid for drawing) and at the cost of 
considerable code complexity. So AHEM really spanks the standard approach for 
this rather important algorithm. To a much greater extent than I originally 
expected, to tell the truth.

Joining up the new mesh vertices does not in itself split the surfaces. We 
still need some tricky rearrangement of the half edge data to integrate the 
new boundary rings with faces of their respective surfaces. For the mesh/plane 
intersection algorithm which was the ancestor of this algorithm, I came up 
with an approach that uses five separate passes over the arc segments, and was 
devilishly hard to debug. For this new, much more complex problem, I found a 
three pass method, which is less than half the code, makes good use of 
existing primitives, is far easier to understand and debug, and is more 
efficient. The moral of this story is: just because something works, do not 
assume it is finished. It may be possible to do the same thing in a much better 
way. The technique I used here will eventually be ported back to the 
mesh/plane slicer, which otherwise is arguably unmaintainable.

After the surfaces are successfully split with boundary edges, they still 
share vertices along the cutting arc. This may be ok if part of each surface 
is going to be discarded immediately, which is not uncommon, but in other 
situations we may need to keep all the pieces and be able to move them around 
independently. So shared vertices need to be duplicated and the duplicates 
assigned to the appropriate edges, depending on how the mesh pieces will 
finally be recombined. That messy little detail is still in development.

Regards,

Daniel
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://phunq.net/pipermail/world/attachments/20120617/f9e0838b/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: solid15.png
Type: image/png
Size: 27513 bytes
Desc: not available
URL: <http://phunq.net/pipermail/world/attachments/20120617/f9e0838b/attachment-0001.png>