[World] On the way to constructive modeling

[Daniel Phillips]

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.

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.

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?

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.

The Blender folks are well aware of the problem in regards to the newly 
integrated Carve constructive solid geometry library:
	
http://wiki.blender.org/index.php/Dev:Ref/Release_Notes/2.62/Boolean_Modifier

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?

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.

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.

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).

We have seen these things before, see here:

	http://phunq.net/files/cut24.png

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:

	http://phunq.net/files/triangulate10.png

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.

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.)

A cutting arc can be closed (a ring) or open (a loop). See here for a few open 
arcs marked in red:

	http://phunq.net/files/contour23.png

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. 

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.

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.

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.

Regards,

Daniel
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://phunq.net/pipermail/world/attachments/20120606/88af9b2f/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: csg2.png
Type: image/png
Size: 125416 bytes
Desc: not available
URL: <http://phunq.net/pipermail/world/attachments/20120606/88af9b2f/attachment-0001.png>