
<!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 intersection arc tracing algorithm is not a hack any more. It actually turned into a pleasingly symmetric and efficient piece of code. The ugly duckling/beautiful swan thing. Now that the algorithm is known, it is easy to see that it is correct - at least I think it is, though there remains a lot of testing to do. Discovering the correct algorithm was another matter entirely.</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;">Now the next step is to use the cutting arc to slice up the original objects, then recombine the pieces to form solids that represent boolean combinations. </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;">This algorithm can also produce results that can't be described as boolean combinations. For example, it could well be useful to use one object to cut a hole in another and simply leave the hole open. The result is not a boolean solid, rather it is an open manifold. Therefore I claim that this new approach to boolean combinations is actually a superset of constructive solid geometry that includes all the classic boolean operations and adds additional operations that yield open manifolds. Supporting evidence that this is actually something new is, all these results are accomplished without relying on any notion of inside or outside, which is actually the central concept of classic CSG. Instead, these algorithms rely purely on manifold orientation. An important consequence is of that is, intersections between open manifolds can be handled consistently without needing heuristics to impose a an extended and possibly inconsistent interpretation of insideness on meshes with holes. I hope to demonstrate the practical effect of that in the not too distant future.</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;">Another nice thing that dropped out of this approach is: it can handle not only combinations of two surfaces, but of any number of surfaces in a single iteration. And those surfaces are allowed to intersect with themselves. So it is pretty general. The main restriction it imposes is, mesh faces are required to be triangles, which the arc tracing relies on as I have described in some detail. In time that restriction will be relaxed. It would actually be quite easy to extend to convex polygonal faces, and arbitrary polygonal faces can also be handled in theory, though I am not sure it is worth the extra complexity. Most probably, users will be pleased enough if just triangles and quads are handled directly without preprocessing.</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;">With nearly all major algorithm steps completed, I can now estimate the running efficiency, and it is looking good. I don't plan to optimize it extensively just yet, being more concerned with correctness for now, but I will have to do something about the N-squared behavior of edge/face intersection detection, otherwise this will be unusable on large meshes. It should be pretty easy to improve that to N*log(N) using a plane sweep algorithm, which was planned from the beginning. All other steps in the algorithm are linear in the number of faces and edges, and the constant overhead is quite low. So with luck this is going to turn out to be a really high performance algorithm, able to compute solid combinations on complex objects at interactive frame rates.</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;">Apologies for the slightly broken image. The subproject to add depth buffer support to antialiased lines has not made it to the top of the stack yet, and might not for some time. But at least I have figured out a reasonable way to do that.</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>