boolean operations on meshes

Question

given a set of vertices and triangles for each mesh. Does anyone know of an algorithm, or a place to start looking( I tried google first but haven't found a good place to get started) to perform boolean operations on said meshes and get a set of vertices and triangle for the resulting mesh? Of particular interest are subtraction and union.

Example pictures: http://www.rhino3d.com/4/help/Commands/Booleans.htm

Answer 1

I think of this as Constructive-Solid-Geometry (CSG). Hopefully you can find some help here.

http://www.alsprogrammingresource.com/csg.html

http://createuniverses.blogspot.com/2009/09/qtcsg-constructive-solid-geometry.html

http://www.nigels.com/research/

Also search google for Constructive Solid Geometry as a start.

HTH

Answer 2

I think we can puzzle it out if we just think about it.

You would obviously want to create faces (triangles) where the two geometries intersect. Then you're left with three meshes: the intersection you just isolated, geometry 1, and geometry 2.

Then, just delete what you don't need!

• BooleanDifference: delete the isolated part and geometry 2.
• BooleanIntersection: delete geometry 1 and 2, leaving the isolated part
• BooleanUnion: merge geometries 1 and 2 and delete the isolated part (make sure to stitch together geometries 1 and 2 into a solid geometry)
• BooleanSplit: Separate out geometry 1, geometry 2, and duplicate the isolated part (attach one to geometry 1 and the other to geometry 2)

I think that covers it, eh? The tough part would obviously be creating the intersection faces. For that, iterate through each face of one and check if that face is part of the other; if it's totally inside, then copy the face as part of the intersection mesh. If it's partially inside, then you need to split the triangle along the intersection line; I think DirectX and OpenGL would both have helper functions for this, or it's just some 3D plane math (vectors). I learned that kind of thing in Calculus 3 (or was it 2?) but if you don't have a clue, perhaps ask at math.stackexchange.com. And then of course if the face is outside, do nothing. Once you iterate over all faces of both meshes you'll be left with the intersection mesh.

Answer 3

If you're dealing with polygonal models, you may well have to deal with non-manifold geometry, which means the question of what is "inside" and what is "outside" is not defined. It's tricky to perform a boolean operation if you don't know if you have a 0 or a 1.

You also have to deal with fringe cases such as co-planar polygons, polygons which intersect edges, vertices which lie on edges and/or faces, and things of that nature. None of which is impossible, you just need a very robust way of representing your mesh data, and a tight definition of what you expect to happen in those cases.

Answer 4

It's worth noting that most of your operations can be represented by negation and union, where negation of some geometry is just that geometry with its normals flipped. So if you can get union right, then the other operations should just follow:

• intersection(A,B) := !union(!A,!B)
• subtract(A and B) := !union(!A,B)

Sander has some fairly good blog posts that discuss CSG implementations: http://sandervanrossen.blogspot.com/search/label/CSG

Answer 5

This is a pretty tricky subject, at least if you want to do it robustly (floating point causes some serious difficulties).

I would point you to the computational geometry / computer graphics literature on the subject, particularly these recent papers:

http://homes.cs.washington.edu/~gilbo/repofiles/booleans2009.pdf

http://openflipper.org/uploads/media/campen_2010_eg_02.pdf