boolean intersection/add/sub algorithms

I''ve never tried to do that before, but I thought up something that might help:

If your object consists purely of vertices/triangles, then you should be able to break your shape up into a set of 4-vertex pyramids. Once you have that set, you would only need to write one function to find CSG results for intersections, unions and subtractions.

I have no idea what the easiest way to compare two 4-point 3d pyramids is... someone else around here might help with that... or you can try to derive a formula by looking at 2d objects broken down into triangles.

I''d be curious to see the algorithm once it''s done, too.

If you want to do this in real time, there may be some difficulties. Before you take everything I say very seriously, I am primarily a math guy who has done modeling. If you want to do booleans of any kind, I think you need to know the intersection lines of faces. Specifically, you need to know the endpoints of the lines of intersection of various faces on the object. Once you get this array of intersection points at the object boundary, I think it should then be easy to incorporate them into the set of verticies that are not part of this bounded region to create your boolean addition or subraction. Try searching boolean operations on volumes or something to that effect in google.
Brendan

After talking with a friend, we decided that it's probably best to NOT break the object into 4-point pyramids... you can do all the same things after figuring out what lines intersect planes to get a list of new vertices and triangles (like Punty50 said), and figure out how to determine (based on surface normals probably) where the "inside" of each intersection is.

The tricky bits that I see: figuring out which new vertices are used with which new triangles, what triangles to remove, determining surface normals, texture coordinates... and even WHICH texture to use if it could go either way.

Of course... I'm still assuming the model is a vertex/triangle based one without any continuous surfaces (other than planes).

Oh BTW -- the speed of a single 3D line/triangle test is fairly decent, I'd expect you'd be able to do several thousands (maybe tens of thousands) of such tests a second no problem...

I might come up with some equations/algorithms if you don't find any in a google search...

[edited by - Nypyren on December 4, 2002 9:37:43 PM]

Well, in theory such a system is straightforward. Basically all you need is some parametric representation of 'in' and 'out' of your object. You then clip all intersecting faces, and split them until no triangle intersects any other anymore. Alot of triangle edges will now lie on the surface of other polygons, they will touch each other but not intersect. At this point, you classify each face as being inside or outside of each of your two objects (it will either be fully inside or fully outside, all intersecting faces were removed in the first step). The last step is to remove all faces that are inside of both object sets.

That's the theory. The practical implementation is in a whole different league, unfortunately. And that's because of one evil little detail: floating point accuracy. Such a geometric algorithm is extremely hard to get mathematically stable. Typically, it will work on some objects, and fail on others (strange results, degenerated objects, division by zero, vertices at infinity, etc). It's already pretty hard to get that working in 2D, but it's even harder in 3D. Ever tried the boolean function in 3DSMax on some complex arbitrary objects ? Often, you'll get pretty strange results, or it might even crash.

But there are ways around that. Do you need extreme precision ? If an approximate fusion is acceptable, then you can use an isosurface approach. Transform both objects into a 3D voxel potential field representation. The resolution of the voxelgrid will determine the precision of the boolean object. Then use an isosurface extraction algorithm, such as marching cubes, to construct the outer surface of the potential field. You can easily simulate all possible boolean operations with that system (union, intersection, subtraction, exclusive or).

/ Yann

[edited by - Yann L on December 4, 2002 10:55:30 PM]

Considering 3DS Max, it took them 3 versions (7 if you take 3DStudio into account) and at last a ''Boolean 2'' operator to finally get it to work reasonably.
I think that''s a good indication of the complexity of boolean operations.