<!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;">I've been bothered for quite some time by a nagging problem: how to add boolean geometry operations to World Welder so we can stop feeling inadequate about not having them. After all, Blender has them, and so do Maya and 3D Max. Over the last few years, constructive geometry has become a basic requirement for any 3D modeler worthy of the name. Designers need to be able to add shapes together, to subtract them, cut holes in them and so on, just like they need to live, breath and reproduce. I exaggerate only slightly. There has never been a question of if World Welder will have this, just when and how.</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 I am happy to say that the when is now, or at least it is getting closer. And the how is, with a shiny new algorithm I have been kicking around for the better part of a year now, and which appears to be quite different from anything in the literature. Different enough that it really needs a new name and maybe constitutes a new branch of computational geometry. A strong claim indeed, but let me justify it.</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;">As far as I know, every current implementation of constructive solid geometry is based on the notion of inside and outside. A "solid" is defined as the set of all points inside a given boundary. But what happens if the boundary has a hole in it? No matter how small the hole, we now have a huge problem with the concept of inside and outside. Say we have a tire with a hole for the valve, and a bit of the tire is poking out through the valve hole. Is that bit of tire inside or outside?</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;">One can try to come up with rules that impose a new, extended definition of insideness in order to implement algorithms, like constructive solid geometry operations, that depend on the notion of inside and outside, but it is a losing battle.</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;">The Blender folks are well aware of the problem in regards to the newly integrated Carve constructive solid geometry library:</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;"> http://wiki.blender.org/index.php/Dev:Ref/Release_Notes/2.62/Boolean_Modifier</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;">Carve is a very respectable library. It is mature, stable, reasonably efficient, and capable of creating beautiful models. But for World Welder it has two fatal flaws. The first is the issue of insideness, which Carve has only hacked around and not solved. The second and more practical issue is, Carve uses its own native mesh format. Similar in many respects to World Welder's AHEM mesh format to be sure, but not the same. Instead of using tables, it uses pointers. It can share vertices just like AHEM, but oddly, not faces. It does not have a first class mesh boundary representation and relies on the traditional "empty face" convention. If we were to interface to the Carve library as Blender does, every operation would require converting all the meshes involved to Carve format and back again. As far as I can see, that is likely to cost more than the actual operation. And how do we figure out what Carve has done to our edges, what if we are treating some of them as handles, or have put text tags on some of them? What if Carve deletes those, how would we know?</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;">The whole proposition starts to sound like a massive, distasteful mess and an open invitation to endless bugs. Especially if a new version of Carve comes out that behaves differently and confuses all the hacks we did to interface to it. Rejected. I would rather suffer the pain of implementing my own constructive geometry library than suffer 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;">So to add some R&D content to this and make it more than just a slogging reimplementation effort, I decided to take a run at solving the insideness problem. In so doing I basically had to throw out the common wisdom about constructive solid geometry and start over. Because CSG depends on the notion of insideness, and we broke that notion. An unfortunate fact of the topological universe.</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;">So instead of recombining volumes and talking about inside and outside a volume, we will be recombining 2D surfaces and talking about 1D linear boundaries of surfaces. Those boundary rings again, and a new, related concept called edge loops, which are like boundary rings folded in half. I will get more into that later (much much more).</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;">We have seen these things before, see here:</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;"> http://phunq.net/files/cut24.png</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;">When I use boundary rings in this way I call them "cutting arcs", just to be clever and make the connection to World Welder. But the terminology makes a lot of sense. I originally developed this idea in the context of slicing a mesh into two parts with a plane. That worked out well, and here is a solid model to prove it:</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;"> http://phunq.net/files/triangulate10.png</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;">Note that the above model is only partly solid. The bottom part is an open mesh with a square boundary running around its base. Topologically speaking, that is no different from having a hole anywhere in the mesh. So we really have already solved the interesting problem of how to deal with meshes that don't have any real inside or outside: we just glue together bits of mesh to make solids were we can, and where we can't or don't care to, the mesh just stays open. What a gloriously simple idea! Surprisingly, this appears to be a new idea.</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;">And now all we want is, instead of slicing a mesh by a plane, we slice it by another mesh. How much harder could that be? (A lot harder as it turns out, but not impossible.)</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;">A cutting arc can be closed (a ring) or open (a loop). See here for a few open arcs marked in red:</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;"> http://phunq.net/files/contour23.png</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;">Incidentally, the contour map algorithm is really the same as the plane slicing algorithm, it just finds all the open and closed cutting arcs of a series of parallel. planes. </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 we want to find all the open and closed cutting arcs formed by the intersection of two arbitrary meshes. Maybe more than two, or even of one mesh with itself, or any combination. Now that we are liberated from the notion of inside and outside, all these things become possible.</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 what I am happy to say is, part of that algorithm is now implemented and working. As of now, we can find closed arcs lying entirely within one face, as in the attached image csg2.png. There are two tetrahedra, one penetrating the other, and we found the closed arc of intersection between the bounding surfaces, shown in white. I will get into the details of exactly how that is done but not now, because this post is getting a little long. Suffice to say that this algorithm extends nicely all the way to the general case and it looks like it is going to be exceptionally efficient. And it is also going to be a lot of work to implement, and I have limited time for implementing, so I thought I had better get started or it will never be done.</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;">Just one more thing to say: the algorithm under construction is not only a new algorithm, needing a new name, but the we may also need to name this branch of computational geometry, because as far as I can see, we are first in here. And there is plenty of goodness to be gotten. I hope to demonstrate 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;">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>