Sign in to follow this  
Aken H Bosch

CSG Project

Recommended Posts

Aken H Bosch    348
I've been working on a Constructive Solid Geometry (but really just mesh Boolean operations) program/library written in C# in my free time during the past several weeks. Sample of what it does: I've managed to get it working, but it's not as awesome as I'd like. To name a few things:
  • Its API isn't very clean
  • It's not quite working in real-time
  • It can only do binary operations (i.e. those with two meshes)
  • Triangulation produces lots of 'sliver' shapes
  • There's some redundancy in the code
  • The existing solution for non-closed meshes might not be very good
  • Maybe some other stuff?
I'd appreciate whatever help I can get fixing these issues. Obviously there's more info I can add, but I'll wait until someone asks for details before I start spouting .cs files.

Share this post


Link to post
Share on other sites
grhodes_at_work    1385
Some quick comments:

- real time will be difficult, especially for non-binary
end results (see below)
-CSG operations are not well defined for open meshes.
It is well defined for manifold solids (closed watertight
meshes with no stray triangles attached). Open
meshes cannot define solids. They define surfaces but
the openness means they cannot bound a solid. Reason
being there is no clear inside and outside, or more
technically, the surface does not clearly mark the boundary
between two half spaces.

- But you can define Boolean operations such as open-
surface subtract a solid. The other direction is not
well-defined, e.g., what would solid subtract surface be?
There is no volume, only an infinitely thin thing. Volume
subtract surface-without-volume equals no change
to the original solid volume.

- The rules change if you deal with nonmanifold
topology. Your indexed mesh already can do
that, but the algorithmic logic to implement
general purpose nonmanifold Booleans is
nontrivial
- To deal with more than two objects, you have
to build and traverse a tree that operates on
two objects at a time, using results of one
operation to feed the next
- Addressing speed can be done to a point
using coarser meshes, using spatial partioning
to enable fast rejection of groups of triangles
that cannot possible intersect (e.g., build a
Kd-tree for each mesh and use that)
- If you are only needing image space, e.g.,
rendered result and can forego geometric
mesh result, there is an elegant image
space algorithm that exploits the stencil
buffer. It is robust and well documented.
It runs in real time for reasonably complex
models on reasonably modern graphics
hardware. But only works for manifold
solids.

- Another approach is to do the operations
on a volume grid then use marching
cubes to extract result mesh. But this is
challenging, and lossy in terms of
exact input shape

Share this post


Link to post
Share on other sites
grhodes_at_work    1385
One more thing. Slivers happen. To deal
with this, do a postprocessing pass and do
"edge flips" to locally retriangulate for
improved triangle quality. Or merge
vertices to kill sliver triangles.

(Sorry for poor formatting. Typing mobile
phone.)

Share this post


Link to post
Share on other sites
Spiked3    100
I have a BSP based CSG in c# thing I've been working on for a while.
It is able to do real time as long as the polycount stays relatively low, say under 800 or so, and obviously, csg ups the count quickly so at the moment I am trying to come up with a solution to eliminate the intermediate csg steps.

http://www.spiked3.com/ is my main site with a pic of the latest SlimDX version.

http://www.spiked3.com/CncGo3_7.swf.html is a capture of the pre slimDX version showing the CSG in action.

I would definitely be interested in trading ideas to improve performance. My source code can be made available, actually I have a smaller stub/test subset that might be helpful if you need.

I would be interested in your code as well. Although my needs are generally simpler - boxes and cylinders.

Share this post


Link to post
Share on other sites
Aken H Bosch    348
Speed / My Implementation

Currently I've got a decent culling system in place. It compares the AABBs of both operands, and will skip to the "removing stuff" step if they don't intersect. Otherwise, it constructs an octree inside the intersection AABB, and populates it with triangles from each of the operands (based on the triangles' AABBs, for now). Whichever pairs of triangles (from different operands) are in the same leaf-level nodes of the octree are those which will require intersect tests; any triangles which never occurred in the same leaf as a triangle from the other operand is 'safe' until the "removing stuff" step.

I then do intersect tests, triangulate the results, and find edge-neighbors. This part could probably be more efficient if I didn't throw away the edge-neighbor data from previous operations.

Then it's the "removing stuff" step; I divide the meshes into regions. Any triangles which are edge neighbors are in the same region, so long as the edge between them is not one of the edges formed by the intersection of the two meshes. I determine which regions are inside/outside, and based on that I determine whether to delete them, include them, or include them but flip their normal vectors and vertex windings.

Slivers and "Meaningless" Edges

I'm thinking now that if I don't triangulate the result that's going to be re-input into the CSG function, but instead keep a format with arbitrary planar polygons, and only triangulate it for rendering (and maybe physics), that will prevent some of those meaningless edges from creating unnecessary intersections.

Unclosed meshes

This notion came up because I was originally considering using this in a level editor, which would have had a tessellated sphere partitioned into 180 large triangular sectors. Rather than work with the entire sphere for every operation, I determined which of the nearby sectors might possibly be affected by it, shoved all of their triangles into a single operand, and did that CSG operation. I then re-divided the result into the original partitioning (approximately).

The problem was that I had to define 'inside' somehow. Ultimately I made a delegate function which would let the user define it however they chose, but provided a default function for it, as well as a couple utility functions which the default function used internally. I'm still not sure if this solution is

Non-binary operations

I don't know if this is actually something I need to concern myself with, after all. I was noticing that successive union operations in my level editing program were causing lots of slivers, and that if they were carried out simultaneously prior to triangulation, many of them would not be needed. That said, if I go with my arbitrary polygons idea, that wouldn't be an issue.

Still, some compound operations are more complicated than a bunch of unions... for example, blasting a hole into the hull of a spacecraft (non-realistic) might work like this:


There are four regions, A, B, C, and D. Region A is the hull. Region B is the blasted-out region (probably an inverted sphere). Region C is a tougher substructure underneath the hull which is less easily destroyed than the hull. Region D is the center of the blast (probably a smaller inverted sphere, concentric), around which even the substructure is destroyed.

A is not present except where it is outside B
B is not present except where it is inside A (but not inside C)
C is not present except where it is inside A and B, but not C
D is not present except where it is inside A and C


That's a somewhat more complicated operation, and I wonder if it could be streamlined anyway.

Share this post


Link to post
Share on other sites
LogicalError    293
Just to throw in my 2cts.

If you're fine with limiting yourself to convex polytopes and additive and subtractive brushes only, then it's possible to do CSG a lot faster.
(You can treat subtractive brushes as a special case where you handle touching polygons differently and reverse the polygons at the final step)

Here's an old video of mine which demonstrates it

And here's an even older one.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this