Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

chipmunk1886

boolean intersection/add/sub algorithms

This topic is 5734 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

this is a general question. Can anyone point me to a good place for information on this topic? I''m thinking about it in terms of fusing two reaonably complex objects together. I''ve done a google search but haven''t found what I''m looking for. I''ve thought about breaking it down to a two dimensional problem and constructing the final object by weaving together the silohuettes each object at different levels. I can think of several major problems with this. There must be a better way to do it.

Share this post


Link to post
Share on other sites
Advertisement
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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
If you only need to render the result of the boolean operation, you can do this by a multipass algorithm using the stencil buffer: http://www.sgi.com/software/opengl/advanced96/node33.html

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!