<!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 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.</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;">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.</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;">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.</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;">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.</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;">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.</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;">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.</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>