Constructive Solid Geometry

Eric Cramer

California Polytechnic State University: San Luis Obispo

CPE 473, Spring 2013

About Constructive Solid Geometry

Constructive Solid Geometry (CSG) is a modeling technique that allows the modeler to create complex geometry using set operations (such as union, intersection, and difference) on primitive objects (such as spheres, cones, and boxes) or other objects created from CSG.

Set Operation Examples

Merge

Intersection

Difference

CSG Trees

We can create even more complex geometry be performing set operations on other CSG objects and have a CSG tree:

Implementation within Ray Tracing

In the context of ray tracing, one must often return the closest intersection between a ray and an object. When we introduce CSG, we ought to now return all intersections of a ray and an object. In other words, we ought to return, for a given ray and object, a list of intervals when the ray is inside the object. We then perform set operations on the lists of intervals (yeah, you heard me right - "lists").

Algorithms for the Set Operations on Intervals

The following algorithms assume that v1 and v2 are non-empty lists of disjoint intervals in ascending order and that rtn is the list to be returned:

Difference

This is simply v1 intersected with the complement of v2.

Merge

Merge the two lists in ascending order of their lower endpoints. Call
the new list v.

run <- v[0]
for (i = 1; i < v.size; i++)
   if run.high < v[i].low
      rtn.append(run)
      run <- v[i]
   else
      run <- [run.low, max(run.high, v[i].high)]
rtn.append(run)

Intersection

i1 <- i2 <- 0

while i1 < v1.size and i2 < v2.size
   if v1[i1].high < v2[i2].low
      i1++
   else if v2[i2].high < v1[i1].low
      i2++
   else
      rtn.append([max(v1[i1].low, v2[i2].low), min(v1[i1].high, v2[i2].high)])
      if v1[i1].high < v2[i2].high
         i1++
      else if v1[i1].high = v2[i2].high
         i1++, i2++
      else
         i2++

Povray Support

The following website provides basic information on Povray support for CSG:

Povray support for CSG

Povray Support in my Program

I use all of the above specifications (even transforms and textures) with a few exceptions:

Cool results

Input file for the die

References