[World] Ready to slice and dice

[Daniel Phillips]

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.

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. 

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.

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.

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.

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.

Regards,

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