Hi all. Im trying to do a CSG subject whereby the actual subtracting (clipping) volume is concave. I know one solution to this difficult problem is to spilt the clipping volume into a union of convex pieces however this would be too time consuming in my scenario due to the number of times it would have to be performed. Ideally what I need is a good clipping algorithm for dealing wityh concave volumes. The weiler atherton algortihm seems to be able to calculate the parts of the subject polygon that are inside the concave volume, but no good way of getting the pieces outside as well. And this is what I need, both the inside and outside pieces. I''ve been looking at UnrealEd recently and this seems to be able to exactly what I want. I can create a concave brush and use this to subtract any manner of concave shapes from addition brushes already in a level. I would love to know how they do this, and whether it is polygon based etc. Any information anyone has is greatly received. thanks.

yes ive read about it being done with BSP trees but as far as i know this will not work if the clipping volume is a concave volume will it?

quote:Original post by superpig
Correct, I don''t believe it will.

Perhaps you could use the weiler algorithm to get the inside pieces, and then perform a CSG subtraction with each piece on the rest of the world? You might still be left facing the original problem though, I guess.

Indeed, it will do just fine.
Build a BSP-tree from the first piece, and cut the second with it. Store the result. Build a BSP from the second piece, and cut the first one with it. Add the resulting polys with the ones stored after the first cut and you''ll get the final mesh.
(do not care much about balancing the BSP).
Algorithm is O(N^2.logN) = O(N.logN) for building the tree and O(N.logN) for cutting the piece with the tree in average case, and O(N^2) in the worst case. Then may be it is even O(N.logN).