[World] Doing the right thing

[Daniel Phillips]

The tricky arc tracing step is now fully worked out for open meshes and seems 
to be doing the right thing in all cases, of which there are many. Like the 
simpler closed mesh problem, we know that if intersection arcs are extracted 
correctly, then using them to cut the mesh will always succeed. So this is a 
big step forward. The class of meshes that can now be handled is: all open and 
closed meshes. In other words, all meshes. And because all 3D objects can be 
represented by meshes, the class of objects that can be handled is all 
objects. It would be tough to do better than that.

I did not immediately realize that an open arc does not necessarily end on the 
same surface it started on. The simplest example of this is two interlocking 
triangles. In general, if an arc begins and ends on a boundary of the same 
surface then it cuts a piece out of that surface, and it if ends on a different 
surface then the two surfaces just interpenetrate and neither completely cuts 
the other. This observation is bound to be important when  automatiing the 
process of recombining the cut up mesh pieces to form new solids.

What do we mean by "different surface"? This question is more subtle than it 
seems. For one thing, an open or close mesh may intersect itself, and all the 
"different surface" logic just works correctly. That is because we do not 
actually rely on the idea of a face or edge belonging to any particular 
surface, but instead, only on the direction an edge penetrates a face, either 
in the same direction as the face normal ("positive" hit) or in the opposite 
direction ("negative" hit). Then we propagate that information along the 
intersection arc as we trace it out. In fact, we rely on knowing with "side" 
of the intersection we are on at each step in order to know where to look in 
the soup of edge/face intersections to find the next arc step, which must exist 
and must be unique (or we have a big problem, but that is another story).

To keep things interesting, the "side" flips for some types of edge/face 
intersection and not for others. The real determinant of whether or not an 
open arc cuts a surface completely is whether the "side" ends up the same as 
it started. One reward we get for dealing accurately with a local instead of 
global definition of sideness is, self intersections just work, whereas in all 
the published algorithms I have seen, self intersection has been a separate 
algorithm. Boolean combination of a surface with itself would then be done in 
two steps: 1) intersect the surface with itself 2) combine the resulting 
separate surfaces. We can do it in one step, simply because we do not actually 
rely on any notion of separate surface.

I am sure that this is far from the only benefit of adopting a local definition 
of sideness. What we are doing is extracting value from the concept of 
"oriented manifold", the topological entity defined by a half edge mesh, a deep 
and powerful notion.

Now it is time to add the ability to cut meshes with open arcs as opposed to 
closed arcs, which already work. After that there is only a modest amount of 
work remaining to press this new boolean modeling technique into service.

Regards,

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