Abstract

The \emph{Sequenced Convex Subtraction} (SCS) algorithm is a hardware based multi-pass image-space algorithm for \emph{Constructive Solid Geometry} (CSG) Rendering. Objects combined by volumetric intersection, difference and union are rendered in real-time without b-rep pre-processing. Graphics hardware stencil and depth testing is used at each pixel to solve the visible surface problem for CSG trees. Intersections between convex objects in CSG trees can be handled by a new $O(n)$ technique, we call SCS-Intersect. Incorporation of this algorithm into SCS results in $O(i+s^2)$ time, rather than $O(n^2)$, where $i$ is the number of intersections, $s$ is the number of subtractions, and $n$ is the total number of objects: $i+s$.

This paper outlines the SCS-Intersect algorithm for convex intersection, and integration into the SCS algorithm for general CSG rendering. OpenGL implementation and experimental results are also presented. SCS-Intersect requires stencil and depth buffers, convex objects and linear time.