   CSG Project
  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 cleanIt's not quite working in real-timeIt can only do binary operations (i.e. those with two meshes)Triangulation produces lots of 'sliver' shapesThere's some redundancy in the codeThe existing solution for non-closed meshes might not be very goodMaybe 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.   
  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;  One more thing. Slivers happen. To dealwith this, do a postprocessing pass and do"edge flips" to locally retriangulate forimproved triangle quality. Or mergevertices to kill sliver triangles.(Sorry for poor formatting. Typing mobilephone.)   ;  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.;  Michael, I'm impressed with what you've done there, on spiked3.com!   ;Speed / My ImplementationCurrently 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" EdgesI'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 meshesThis 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 operationsI 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 BB 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 CD is not present except where it is inside A and CThat's a somewhat more complicated operation, and I wonder if it could be streamlined anyway.   ;  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.