Hello This question is directed to anyone who has implemented some Constructive Solid Geometry, or who knows about it. I am after some advice! I am in a situation where I need to implement some CSG algorithim within a short about of time. Basically I am dealing with convex brushes and polygons here, so thats nice and simple. I need to be able to have Subtractive and Additive brushes just like UnrealEd. Now some time ago sombody put me onto a MAP file tutorial which used the Laidlaw approach to CSG, and CSG Unions were used to cut brushes against other brushes. Basically for those of you who dont know the tute, each brush was cut against each other brush, and geometry within the brush the current brush was being cut against is removed.

while(more brushes)
{
   while(more brushes)
   {
        CutBrushes(X against Y)
        X++
   }
    y++
}

Unfortunately I have just realized that this is fine for a Quake style editor, but for Unreal (and my editor), its not going to work. Union is fine if you are dealing with all additives or all subtractive brushes, but not when you have both, overlapping, etc. Order also becomes important here: You Subtract a hollow space, add another brush over it to fill part of it up, and then subtract part of this again...the above algo wont cut things right...I wasted 2 days implementing the above until I realized what a mistake I had made. So I was thinking of a different algo, my original one that I thought about: keep track of the order of which each brush was added or subtracted in the editor. Begin by cutting brush 2 against brush 1, then store the result. Then cut brush 3 against the result to have a new resulting brush, then cut number 4 against that...etc. So a cumulative algorithim here. IS this a sound algo? Is it a good way to do things? I dont want to spend another 2 days implenting this to find that its not gonna work as expected...I got studying to do! Also, for anyone that knows, what is the diff between the Naylor and Laidlaw approach. I red about them both, but I aint understanding too well... I will appreciate any advice here, especially from people who are familiar with CSG!

Crap, I just realized that my algo will result in a non-convex cumulative brush...making CSG ops much more difficult...

Might just settle for simple CSG Union and dont allow for subtractive brushes to cut additive ones...

I am not sure about the CSG approach you are using but I compile my brushes into BSP solid trees prior to performing Union, Carve or intersection operations on them. It works perfectly all the time.

Also, in this instance it is just as easy to carve the hell out of the none convex results because the BSP tree, and its solid and empty space partitioning takes care of clipping away of the brush polygons. Hell, you can even do this dynamically.

It might be worth you looking into this approach as it seems this would do what you want to do.

Yeah thats the Naylor BSP approach I think, and it would do what I want. If I had have had more time, I may have gone down that path. My system is a variation on this that works only wth convex brushes and so you dont need BSP. Its not ideal, but its the method I have decided to go with to get this done by the deadline.

Later I will come back and do a more comprehensive system like yours.