Cutting 3d objects

One thing I can think of is to build a BSP tree of the object, then take the splitting plane and construct a large polygon on it. Clip the polygon to the bsp tree so the polygon fragments exist only in leaves (inside)

when you do a boolean operation of two object no new geometry is created. It just gets subdivided.
Each of the Objects 1 and 2 has a part that lies inside the other (I) and a part that lies outside the other (O). eg I2 is the part of object 1 that''s inside 1.

Once you have calculated the intersecting line you can calculate the which is which.

After that all thats needed is taking the appropriate parts and welding them together

e.g 1-2 = O1 + I2

all that remains is flipping the normals of any I parts

---------------------------
I may be getting older, but I refuse to grow up

I think the easiest/best way of doing CSG is using BSP trees. Its the same process that Dreamforger has described, just using the BSPs to define the inside/outside of each mesh. Each object (brush) has a BSP tree made from it that defines the solid space that the mesh contains. You can clip each triangle of one object against the BSP of the other object to find the mesh that is inside the other.

Using Dreamforgers notation, these are the common CSG operations..

Boolean Union : O1 + O2
Intersection: I1 + I2
Subtraction (carving): O1 + I2

one thing I forgot:

I wrote a CSG module once - but in matlab which won''t be of much assistance.

Main problem of a CSG result is that it''s either trivial or a catastrophe. All that subdividing, cutting polygons, etc lead to a very complex mesh. For me that was ok since it was mainly a proof of concept but if you intend to use the generated mesh in a game or anything else that should run fast, better think twice about allowing CSGs.

Better extend the tools to bevel, face cutting, etc. Tools a intelligent leveldesigner can use to create the effects of most CSG (you''re probably aiming for ''cut'', mainly) without increasing the polygon and vertexcount so drastic

Dreamforger:

quote:

---

All that subdividing, cutting polygons, etc lead to a very complex mesh.

---

that is the problem i currently have maybe i can retriangulate it but that would be too complicated i think....

another problem: i have two cubes, and two approaches. the one is to insert all faces (from both cubes) into one BSP and then subdivide the tree. then (for union, as an example) i could discard all primitives inside the one object, etc. but this also discards some faces that are not really "inside".

the other approach is to put each object in its own BSP.

can someone give me some help here? from what i read (again for union) i need to push all polys of A through B´s tree, split if neccessary, and if a poly reaches a leaf, discard it if it is behind node´s split plane. is the node´s split plane the plane of the leaf´s node or the parent node of the leaf node? and should polys which are front of the split plane be added to object B??

And then do it again with B for A?? Original B and A or with discarded / added polys?

i hope my questions are not too messy....

thanks
Gammastrahler

the unreal editor used to work with CSG modelling. great, has you were always assured to have solid geometry with no gaps, unlike Quack.

If you cut a cube in half, it will be solid. The thing is, you have to thing of a cube as a solid, not as a colletion of faces. BSP is the only way.

K, Gammastrahler, heres how I do my BSP based CSG, I dunno how other ppl do it, I worked this out on my own and it seems fine

I start with constructing two solid-leaf bsp trees for two first brushes(objects). I keep a copy of object B. From the bsp of object B I delete all polygons, but leave all the nodes and leaf flags. Then for each leaf in object A, i push its polygons through the bsp tree of object B, deleting all of the faces that end up in leaves and putting the rest in the source leaf of A. This is the first step. In the second, I push all of copied object Bs polygons through the tree of A and remove all faces that end up in leaves.
This gives ya the union of A and B in the tree of A.
When considering a next brush to union, i use that brush as object B, reusing the tree of A from the previous pass.

There are a few more things worth mentioning:
In the 1st step if some poly is coplanar to the splitter plane, it should always be put to back. You must do it this way, otherwise ther would be holes in the model where brush faces were coplanar.
In the 2nd step if some polygon during splitting lies on the same plane as the splitter, it should be put to front if they have the same normals and should be put to back, if the normals are opposite.

One last thing: IMO the most important thing in CSG, portalization, or BSP in general is an accurate polygon splitter. In my experience 90% of the problems involved in these algorithms come from float inaccuracy and no error handling/prevention in the polygon::split function There are also more subtle problems when your levels get really huge(especially in portalization) and only VERY tight error handling can avoid/minimize them...

I hope this post makes any sense