If I construct a shape using constructive solid geometry techniques, how can I construct a wireframe mesh for rendering? I'm aware of algorithms for directly rendering CSG shapes, but I want to convert it into a wireframe mesh just once so that I can render it "normally"
To add a little more detail. Given a description of a shape such as "A cube here, intersection with a sphere here, subtract a cylinder here" I want to be able to calculate a polygon mesh.
There are two main approaches. If you have a set of polygonal shapes, it is possible to create a BSP tree for each shape, then the BSP trees can be merged. From Wikipedia,
1990 Naylor, Amanatides, and Thibault provide an algorithm for merging two bsp trees to form a new bsp tree from the two original trees. This provides many benefits including: combining moving objects represented by BSP trees with a static environment (also represented by a BSP tree), very efficient CSG operations on polyhedra, exact collisions detection in O(log n * log n), and proper ordering of transparent surfaces contained in two interpenetrating objects (has been used for an x-ray vision effect).
The paper is found here Merging BSP trees yields polyhedral set operations.
Alternatively, each shape can be represented as a function over space (for example signed distance to the surface). As long as the surface is defined as where the function is equal to zero, the functions can then be combined using (MIN == intersection), (MAX == union), and (NEGATION = not) operators to mimic the set operations. The resulting surface can then be extracted as the positions where the combined function is equal to zero using a technique like Marching Cubes. Better surface extraction methods like Dual Marching Cubes or Dual Contouring can also be used. This will, of course, result in a discrete approximation of the true CSG surface. I suggest using Dual Contouring, because it is able to reconstruct sharp features like the corners of cubes .
These libraries seems to do what you want:
www.solidgraphics.com/SolidKit/ carve-csg.com/ gts.sourceforge.net/
See also "Constructive Solid Geometry for Triangulated Polyhedra" (1990) Philip M. Hubbard doi:10.1.1.34.9374
Here are some Google Scholar links which may be of use.
From what I can tell of the abstracts, the basic idea is to generate a point cloud from the volumetric data available in the CSG model, and then use some more common algorithms to generate a mesh of faces in 3D to fit that point cloud.
Edit: Doing some further research, this kind of operation is called "conversion from CSG to B-Rep (boundary representation)". Searches on that string lead to a useful PDF:
http://www.scielo.br/pdf/jbsmse/v29n4/a01v29n4.pdf
And, for further information, the key algorithm is called the "Marching Cubes Algorithm". Essentially, the CSG model is used to create a volumetric model of the object with voxels, and then the Marching Cubes algorithm is used to create a 3D mesh out of the voxel data.
I've had some luck with the BRL-CAD application MGED where I can construct a convex polyhedron by intersecting planes using CSG then extract the boundary representation using the command-line g-stl command. Check http://brlcad.org/ Malcolm
You could try to triangulate (tetrahedralize) each primitive, then perform the boolean operations on the tetrahedral mesh, which is "easier" since you only need to worry about tetrahedron-tetrahedron operations. Then you can perform boundary extraction to get the B-rep. Since you know the shapes of your primitives analytically, you can construct custom tetrahedralizations of your primitives to suit your needs instead of relying on a mesh generation library.
For example, suppose your object was the union of a cube and a cylinder, and suppose you have a tetrahedralization of both objects. In order to compute the boundary representation of the resulting object, you first label all the boundary facets of the tetrahedra of each primitive object. Then, you perform the union operation: if two tetrahedra are disjoint, then nothing needs to be done; both tetrahedra must exist in the resulting polyhedron. If they intersect, then there are a number of cases (probably on the order of a dozen or so) that need to be handled. In each of these cases, the volume of the two tetrahedra needs to be re-triangulated in a way that respects the surface constraints. This is made somewhat easier by the fact that you only need to worry about tetrahedra, as opposed to more complicated shapes. The boundary facet labels need to be maintained in the process so that in the final collection of tetrahedra, the boundary facets can be extracted to form a triangle mesh of the surface.
If you can convert you input primitives to polyhedral meshes then you could use libigl's C++ mesh boolean routines. The following computes the union of a mesh (VA,FA) and another mesh (VB,FB):
igl::mesh_boolean(VA,FA,VB,FB,"union",VC,FC);
where VA is a #VA by 3 matrix of vertex positions and FA is a #FA by 3 matrix of triangle indices into VA, and so on. The technique used in libigl is different from those two mentioned in Joe's answer. All pairs of triangles are intersected against each other (using spatial acceleration) and then resulting sub-triangles are categorized as belonging to the output surface or not.
