Constructive solid geometry mesh
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.
Answer
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 .