CSG - Functions - Theory

Check out www.povray.org It is a freeware open source ray-tracer that supports CSG.

The ray tracing approach (implemented in povray) is rather straightfoward. It is wonderful if all you want is an image of your CSG object. HOWEVER , if you need to create a mesh or mathematical representation of the resulting CSG solid you will have to go beyond ray tracing to get decent results. (Ray tracing generates a very high quality image, but if you want to use it to generate a mesh of the booleaned objects, you'll have to reduce the number of rays you shoot significantly---so you don't generate a mesh with way too many polygons---and shoot from several positions so that you cover the front, back, sides of the object. The result will be a very very poor quality mesh---for example, you will likely not shoot a ray that exactly touches the crease intersection between a sphere and a box and the resulting object will just not look right, it will lack the symmetry and consistencies that make a good mesh.)

The easiest way to compute a mesh representing a CSG object is to do boolean operations on closed polyhedra (i.e., represent each object as a closed mesh, then do the boolean on the meshes---the result being a new mesh that can be further booleaned with something else). There is a book called "Open Geometry" (by Georg Glaser I think) that may discuss some of the theory for doing this with 3D meshes, and includes a sample implementation---source code in German. There is a book called "Computational Geometry: Algorithms and Applications" by Mark De Berg (editor). I like this this much better than the other book. It discusses 2D booleans on arbitrary planar polygonal objects using two algorithms called "map overlay" and "plane sweep." These are two classical computational geometry algorithms. These algorithms may be part of some 3D polyhedra boolean algorithms. I think some folks have used BSP trees to do booleans on polyhedra, perhaps in combination with plane sweep.

You probably don't have the resources to go beyond booleans on polyhedra. If you want to representations of mathematically smooth objects, for example, you'll have to switch from CSG (which is merely a way of expressing a combination of objects at a high level) to either a winged-edge non-manifold representation or a manifold boundary representation (B-rep) (which are low-level ways of representing complex geometry). Both of these representations require computations that involve advanced calculus, gradient-based numerical optimization with multiple objectives and nonlinear constraints, iterative methods, manifold vs. non-manifold geometry, complex ugly ugly stuff. Stick with closed polyhedra and you'll have a decent chance of understanding the theory and implementing something that works.

Even if you don't really need it, there is another benefit of actually generating a mesh of the CSG object instead of using ray tracing. If you use ray-tracing only, you'll have to re-ray-trace the scene whenever the camera changes and that will be slow to render. If you generate a mesh, you can use a normal graphics API such as OpenGL or DirectX to render and interact with the mesh in real-time.

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.



Edited by - grhodes_at_work on November 24, 2001 12:07:24 AM