Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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

share|improve this question

5 Answers 5

up vote 9 down vote accepted

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

share|improve this answer
    
+1 - I was going to post the same links, JustBoo - until I noticed that you beat me to it! :) –  jacmoe Aug 6 '10 at 19:24
    
thanks! The terminology Constructive-Solid-Geometry is exactly what I needed! –  lathomas64 Aug 6 '10 at 19:34
    
@jacmoe - The irony is amazing and complete now :-) You deserve credit for some of those. Thx. –  JustBoo Aug 6 '10 at 19:41
    
some of those? :P I believe I jotted them all down back there. :D Still, they're only basic CSG stuff. It gets pretty hairy from there - not even the major commercial modelling packages got it right. –  jacmoe Aug 7 '10 at 0:29

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

share|improve this answer

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

share|improve this answer
    
I was going to mention my own CSG stuff, but apparently someone else already did :O) –  Sander van Rossen Aug 9 '10 at 14:54

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.