PDA

View Full Version : Boolean operations with 3D meshes

billy
03-27-2002, 06:47 AM
I know this is bit of topic, but does anyone know where I can find information about boolean operations, such as union, subtract and interesect?

Thanks,

Billy.

Eric
03-27-2002, 07:01 AM
Sorry, I don't have links but if you search for "Constructive Solid Geometry" (or CSG) on the web, you will probably find some links. If I remember correctly, resources are scarce on this topic....

Regards.

Eric

billy
03-27-2002, 07:22 AM
Thanks Eric, but I do not want to visualize a boolean operation, I want to compute the resulting mesh after a union, subtraction or instersection of 2 meshes.

Basically I want to compute the resulting closed volume after the union, subtraction or intersection of two closed meshes.

Devulon
03-27-2002, 07:51 AM
I know what you meant billy. It isn't easy. As far as I know its basically an edge into plane projection. But that is of course much to vague to be of any use. Its not easy with meshes (as compared to actual CSG models). There are significant problems with models that are open as well as degenerate triangles/surfaces. That problem is why 3ds max and maya and the like may do weird things with boolean. Anyway my best advice is just to look online. I know there are engines you can purchase that do LOD and bool operations and the like, but I get the impression that you would like to do it yourself.

I am also interested and will look and see what I can find and let you know if I see anything of any use. Keep me informed if you find anything too.

Thanks.
Happy Coding.

okapota
03-28-2002, 02:57 AM
two methods for doing that. one is using a bsp tree, the other i dont have time to explain now.
what you need to do is construct a bsp tree for each mesh in the boolean operation (lets say we have two meshes). than you should cut each mesh polygons with the polygons of the other meshes (while cutting dont touch the bsp trees). than when you have 2 bsp trees and 2 lists of cutted polygons, put each polygon of each mesh trough the other mesh's tree, and depends on the operation you want dicied if you need th polygon or not. you might be confused a bit, so here is an example.
we want to cut a window in a wall, a subtraction. we build two bsp trees, and two cuted polygons lists. we take each of the wall's polys from its list, and if it is inside of the window's mesh, we delete it. than we take each of the window's polys from its list, and if it is outside the walls mesh. we delete it. and then you have it, a wall with a holl. right?

Eric
03-28-2002, 03:22 AM
Originally posted by billy:
Thanks Eric, but I do not want to visualize a boolean operation, I want to compute the resulting mesh after a union, subtraction or instersection of 2 meshes.

Basically I want to compute the resulting closed volume after the union, subtraction or intersection of two closed meshes.

Sorry but that's exactly what CSG is about... CSG is about the maths equations needed for achieving what you want. It has nothing to do with visualization !

As I said, resources on the web are scarce about this topic and chances are you only found demos using the stencil buffer and claiming they were doing CSG.

Regards.

Eric

billy
03-28-2002, 05:28 AM
I am going to keep on searching the web. I thought that this link:
http://mathworld.wolfram.com/

would explain some of the mathematics behind CSG, but I still haven't found it.

Sorry Eric I thought you meant those CSG OpenGL demos.

okapota
03-28-2002, 11:44 PM
read my post, thats a good way for doing csg.

coredump
03-29-2002, 08:00 PM
okapota...your post sounds familiar...did you take the BSP course at game institute?

b

okapota
03-30-2002, 02:52 AM
no actually, me and my friend searched the web and found nothing but a few words that it is possibile to use bsp trees for csg. so we learned about bsp trees, and "reinvented" the wheel.

davepermen
03-30-2002, 03:16 AM
poor okapoka, i even found once a tutorial exactly describing your way on the web.. http://www.opengl.org/discussion_boards/ubb/smile.gif

okapota
03-31-2002, 04:43 AM
that probably means we were right. we also invented another way, that recurcively cuts a brush with another one's poly's planes, and that gives you a subtract boolean operation, which only works with convex volumes, less flexibile, much faster and much cleaner, produces no unneccesary polys.
we coded this method eventually, altho now i think using a bsp is a better approach. the reason is because is more flexibile, and it's maor cons - the poly count - isnt such a big problem, because these polys will be fairly small, and with today's per pixel engine's, it is better to have "a lot" of small polys instead of large ones, this is nothing new to you im sure, but its just a thought.

davepermen
03-31-2002, 04:57 AM
i never coded anything with csg, i just know the theory http://www.opengl.org/discussion_boards/ubb/smile.gif
but yes, bsp is imho the best approach.. there was another way i dunno remember, wich was more or less as flexible..
but as we all know bsp simply from rendering, why not reusing? http://www.opengl.org/discussion_boards/ubb/wink.gif

yeah, and go for small triangles. at least on nvidiaboards to get rid of the errors you get when you do perpixelstuff on theyr gpu's http://www.opengl.org/discussion_boards/ubb/wink.gif

okapota
03-31-2002, 09:14 AM
me and my friend just finished our editor project. we coded it for school. it features some editing tools like csg and such, u can create n sided cylynders and cones, put lights and assign different textures to brushes and colors to lights.
everything casts shadows (stencil) on everything, and all the lighting is perpixel. and everything is done real time, while editing, u can the shadows move as you move lights. it is quiet good looking.we might post a few screen shots soon.

[This message has been edited by okapota (edited 03-31-2002).]