Constructive Solid Geometry

Ken Hung
kehung@calpoly.edu
CPE 473

Constructive Solid Geometry (CSG) takes primitives such as Sphere, Box, Cone, Cylinder, Torus, etc... and applies Set operations on them to obtain more complex geometry or surfaces. My implementation includes the following:

Primitives

Sphere
Box

Set Operations

UNION
INTERSECTION
DIFFERENCE

Within the context of a raytracer, implementing CSG is straightforward. The same principle described above is applied at the ray level. Each ray intersection returns an interval that represents where the ray has entered and exited a primitive. Set Operations are then applied to these intervals according to a specified order in the file (.pov). The closest t is recorded per pixel after Set operations have been applied to the intervals and the pixel is colored accordingly.

The following are examples of each Set operation between a Box and a Sphere:

UNION

UNION example

INTERSECTION

INTERSECTION example

DIFFERENCE

DIFFERENCE example

Handling Multiple Primitives

In order to handle multiple primitives, a CSG Tree is used to maintain operation ordering among primitives. It is a binary tree with primitives in the leaf nodes and Set operations in the interior nodes.

CSG Tree

The following exemplify multiple Set operations on multiple primitives.

Iteration 1

Iteration 2

Complex

Other CSG Images

Box differenced with a Sphere differenced with a smalled Sphere

Sphere differenced by 4 boxes intersected by a larger box

Future Work

Multiple Spanning Intervals
- Keeping track of multiple intervals during CSG Tree traversal so that the appropriate t value is used to color a pixel. Also includes efficiently combining spans.
Shadows, Reflections, and Refractions
- Shadow, Reflect, and Refract rays must hit CSGed objects and not the original primitives.

References

http://groups.csail.mit.edu/graphics/classes/6.838/F01/lectures/SmoothSurfaces/0the_s040.html

http://www.cse.ohio-state.edu/~parent/classes/681/Lectures/19.RayTracingCSG.pdf

http://www.cs.mtu.edu/~shene/COURSES/cs3621/NOTES/model/csg.html

General Comparison of Runtimes for CUDA and Bounding Volume Hierarchy

CPU         bunny_jumbo_tris.pov   640x480   w/o Shadows  w/o Anti-Aliasing
--------------------------------------------------------------------------
real    18m34.650s
user    18m32.900s
sys     0m0.080s


CPU         bunny_jumbo_tris.pov   640x480   w/ Shadows  w/o Anti-Aliasing
--------------------------------------------------------------------------
real    > 1 hour
user    ??
sys     ??


CPU (BVH)   bunny_jumbo_tris.pov   640x480   w/ Shadows   w/o Anti-Aliasing
--------------------------------------------------------------------------
real    1m27.810s
user    1m25.415s
sys     0m1.243s


GPU (CUDA)  bunny_jumbo_tris.pov   640x480   w/o Shadows  w/o Anti-Aliasing
--------------------------------------------------------------------------
real    1m3.030s
user    0m56.188s
sys     0m6.592s

Image of bunny_jumbo_tris.pov 640x480 With Shadows, No Anti-Aliasing

Complex