#### Archived

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

# polygonal CSG with concave volumes

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

## Recommended Posts

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.

##### Share on other sites
you could try bsp trees, it''s quite easy. build a bsp tree from one of the meshes and clip all polygons of the other one against the tree to see what''s inside and what''s outside.

##### Share on other sites
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?

##### Share on other sites
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.

##### Share on other sites
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).

1. 1
2. 2
Rutin
15
3. 3
4. 4
5. 5

• 13
• 26
• 10
• 11
• 9
• ### Forum Statistics

• Total Topics
633725
• Total Posts
3013559
×