Z-Buffer CSG Rendering

Using OpenGL graphics hardware for solid modeling.

Image Gallery


These pages are related to my PhD research into CSG Rendering techniques using OpenGL. I was enrolled with the RMIT School of Aerospace, Mechanical and Manufacturing Engineering in Melbourne, Australia. Currently I work for Nvidia in Austin TX, USA.

Z-Buffer Constructive Solid Geometry (CSG) Rendering is a multi-pass, view-specific, technique for displaying the result of volumetric boolean operations in real-time, using the frame buffer of graphics hardware. The general idea of CSG rendering is to combine shapes by intersecting, subtracting or merging their volumes.

The origins of this research project is the specific problem of visualising the result of tool and cutter manufacturing. Published techniques such as the Trickle Algorithm and the Goldfeather Algorithm were applied to display the result of grinding tools on 5-axis CNC grinding machines.

Several issues and deficencies were identified, both with the graphics hardware used, and the existing CSG rendering algorithms. Subsequent work has been directed at developing better algorithms for doing CSG rendering on modern graphics hardware, using OpenGL.

The new CSG rendering algorithm that we call SCS (Sequenced Convex Subtraction) works on the basic principle of subtracting convex volumes from the z-buffer in an appropriate sequence. The optimal sequence is from front to back. Without sorting, efficient sequences can be utilised that work for any viewing direction.

Generating sequences for the SCS algorithm is quite an interesting subproblem. There are easy methods to generate good sequences, but finding better or optimal sequences, based on various forms of information, can be complicated. SCS uses sequences with a permutation embedding property, which involves combinatorial mathematics.

The purpose of this page is to make reasources available to the general academic and commercial community, related to CSG rendering and the SCS algorithm. Please feel welcome to email me with questions, suggestions, or feedback.


Nigel Stewart


N. Stewart, An Image-Space Algorithm for Hardware-Based Rendering of Constructive Solid Geometry, May 2008
PhD Thesis


N. Stewart, G. Leach, S. John, Improved CSG Rendering using Overlap Graph Subtraction Sequences, International Conference on Computer Graphics and Interactive Techniques in Australasia and South East Asia - GRAPHITE 2003, pp. 47-53
Paper: graphite03.pdf (452 Kb)
MD5 checksum: 7d083721578a8562f2ca95f94ca3ec4e
Slides: graphite03.pdf (412 Kb)
MD5 checksum: d662f3077a03de433842321179a825ca
N. Stewart, G. Leach, S. John, Linear-time CSG Rendering of Intersected Convex Objects, The 10-th International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision '2002 - WSCG 2002, Volume II, pp. 437-444
Paper: wscg2002.pdf (615 Kb)
MD5 checksum: f99557baa4d53d850b123fa4e7550d3f
Slides: Online, wscg2002_4up.pdf (2114 Kb)
MD5 checksum: 5a29fce94b8d6c96fe5d8c7659d2ae2e
R. Erra, N. Lygeros, N. Stewart, On Minimal Strings Containing the Elements of ${S}_{n}$ by Decimation, Discrete Mathematics & Theoretical Computer Science, Proceedings vol. AA (2001), pp. 165-176
Paper: Abstract dmtcs2001.pdf (107 Kb)
MD5 checksum: 03b7bcfcec07b638e9d4c0196fef92c2
N. Stewart, G. Leach, S. John, A CSG Rendering Algorithm for Convex Objects, The 8-th International Conference in Central Europe on Computer Graphics, Visualisation and Interactive Digital Media '2000 - WSCG 2000, Volume II, pp. 369-372
Paper: wscg2000.pdf (751 Kb)
MD5 checksum: 5dd2a526b938cc8a1901f14f3ef7455e
Slides: Online, wscg2000_4up.pdf (1012 Kb)
MD5 checksum: 5f58e09bad90c325ce3797f40b5b901b
N. Stewart, G. Leach, S. John, An Improved Z-Buffer CSG Rendering Algorithm, 1998 Eurographics/Siggraph Workshop on Graphics Hardware, pp. 25-30
Paper: egsggh98.pdf (345 Kb)
MD5 checksum: 805f9ad8bada61268571da1c0f0fa390
Slides: Online, egsggh98_4up.pdf (949 Kb)
MD5 checksum: 06da99cc9c6b40529b54699a43076de8


F. Romeiro, L. Velho, L. H. Figueiredo, Hardware-assisted Rendering of CSG Models, XIX Brazilian Symposium on Computer Graphics and Image Processing (SIBGRAPI'06), 2006, pp. 139-146

J. Hable, J. Rossignac, CST: Constructive Solid Trimming for Rendering BReps and CSG, GVU Technical Report GIT-GVU-06-16, 2006

G. Herres, Real time constructive solid geometry rendering using 3D texture mapping, Journal of Computing Sciences in Colleges, Vol. 19, No. 5, 2004, pp. 333-335

J. Hable, J. Rossignac, Blister: GPU-based rendering of Boolean combinations of free-form triangulated shapes, Proceedings of ACM SIGGRAPH 2005, Vol. 24, No. 3, 2005, pp. 1024-1031

F. Kirsch, J. Döllner, Rendering Techniques for Hardware-Accelerated Image-Based CSG, Journal of WSCG 2004, Vol. 12, No. 2, 2004, pp. 221-228

K. Munagala, S. Guha, S. Krishnan, S. Venkat, The Power of a Two-Sided Depth Test and its Application to CSG Rendering, Proceedings of ACM Siggraph Symposium on Interactive 3D Graphics, 2003

S. Guha, S. Krishnan, K. Munagala, S. Venkatasubramanian, Application of the Two-Sided Depth Test to CSG Rendering, SIGGRAPH Symposium on Interactive 3D Graphics, 2003

C. Raymaekers, F. Van Reeth, Algorithms for Haptic Rendering of CSG Trees, Proceedings of EuroHaptics 2002, 2002, pp. 86-91

T. Theoharis, G. Papaioannou, E. Karabassi, The Magic of the Z-Buffer: A Survey, The 9-th International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision 2001 - WSCG 2001, 2001

R. Tobler, G. Erhart, General Purpose Z-Buffer CSG Rendering with Consumer Level Hardware, VRVis Technical Report 2000-03 2000


Image-Space CSG Rendering (by author)
D. Epstein, F. Jansen, J. Rossignac, Z-Buffer Rendering from CSG: The Trickle Algorithm, IBM Research Report RC 15182, Nov 1989

J. Goldfeather, J. Hultquist, H. Fuchs, Fast Constructive Solid Geometry in the Pixel-Powers Graphics System, Computer Graphics (Proc. Siggraph), Vol. 20, No. 4, Aug 1986, pp. 107-116

J. Goldfeather, S. Molnar, G. Turk, H. Fuchs, Near Real-Time CSG Rendering Using Tree Normalization and Geometric Pruning, IEEE CG&A, Vol. 9, No. 3, May 1989, pp. 20-28

J. O'Loughlin, C. O'Sullivan, Real-Time Animation of Objects Modelled using Constructive Solid Geometry, Proceedings of the Spring Conference in Computer Graphics '99, 1999, pp. 67-73

A. Rappoport, S. Spitz, Interactive Boolean Operations for Conceptual Design of 3-D Solids, Siggraph 97, pp. 269-278

A. Requicha, Representations for Rigid Solids: Theory, Methods, and Systems, Computing Surveys, Vol. 12, No. 4, Dec 1980, pp. 437-464

A. Requicha, H. Voelcker, Boolean Operations in Solid Modelling: Boundary Evaluation and Merging Algorithms, Proc. of the IEEE, Vol. 73, No. 1, Jan 1985, pp. 30-44

J. Rossignac, J. Wu, Correct Shading of Regularised CSG Solids using a Depth-Interval Buffer, Proc. Fifth Eurographics Workshop on Graphics Hardware, 1990

T.F. Wiegand, Interactive Rendering of CSG Models, Computer Graphics Forum, Vol. 15, No. 4, Oct 1996, pp. 249-261
Permutation Embedding Sequences (by date)
L. Adleman, Short Permutation Strings, Discrete Mathematics, Vol. 10, 1974, pp. 197-200

P.J. Koutas, T.C. Hu, Shortest String Containing All Permutations, Discrete Mathematics, Vol. 11, 1975, pp. 125-132

G. Galbiati, F.P. Preparata, On Permutation-Embedding Sequences, SIAM J. Appl. Math., Vol. 30, No. 3, May 1976, pp. 421-423

D.J. Kleitman, D.J. Kwiatkowski, A Lower Bound on the Length of a Sequence Containing All Permutations as Subsequences, Journal of Combinatorial Theory (A), Vol. 21, 1976, pp. 129-136

M. Cai, A New Bound on the Length of the Shortest String Containing all r-Permutations, Discrete Mathematics, Vol. 39, 1982, pp. 329-330

C. Savage, Short Strings Containing All k-Element Permutations, Discrete Mathematics, Vol. 42, 1982, pp. 281-285

A.A. Schaffer, Shortest Prefix Strings Containing All Subset Permutations, Discrete Mathematics, Vol. 64, 1987, pp. 239-252

Image Gallery

Sequenced Convex Subtraction (SCS) Algorithm
Illustrations of the SCS Algorithm
WSCG 2000 Paper Images


Windows Linux Cygwin SGI Source Code
  • glt-csg-0.8-rc3.zip (201 Kb)
    MD5 checksum: dfa8d614b4e3b0a662d7afbb1c835d23
    9th September 2003
Depends on GLT C++ OpenGL Toolkit 0.8 or later
Project files for Microsoft Visual C++ 6.0
Makefiles for UNIX
Much older snapshot also available.

Windows Binaries (95/98/NT/2000/XP)
  • CsgDemo csgdemo-0.4.exe (3522 Kb)
    MD5 checksum: d934b50873373c188b7c9bc87882a1d1
    9th May 2009


OpenGL CSG Rendering Demonstration

The program includes several CSG rendering algorithms including SCS, Goldfeather, Improved Goldfeather and Improved Goldfeather II. Many example CSG models are included: those appearing in SCS related publications and other test cases. Overlap graph SCS sequence encoding is utilised for the SCS algorithm.

Use the left mouse button to access the menu system, right mouse to rotate, shift together with right mouse to pan and control together with right mouse to zoom.

Various information pages are available by holding shift and pressing a number key 1-6.
bubbles bubbles

Bubbles Convex Intersection Demonstration

Three animated spheres intersected in real-time.
convint convint

Cylinder Intersection Demonstration

Use + and - to adjust the number of intersected cylinders.
glzcopy glzcopy

OpenGL Depth Buffer Copying Diagnostic

The accuracy of copying depth buffer data can vary according to the stored depth. In this example typical of NVIDIA hardware, near depths do not copy correctly, further depths are copied correctly using glCopyPixels().
glzequal glzequal

OpenGL Z-Equal Diagnostic

The exact depth stored in the z-buffer can depend on the order in which vertecies are passed to OpenGL. In this example a red triangle is drawn with glDepthFunc(GL_ALWAYS), followed by the same blue triangle with glDepthFunc(GL_EQUAL). With the second triangle vertecies passed in the opposite order, most pixels match but some do not.
glcopysp glcopysp

OpenGL Buffer Copying Benchmark

This simple program measures the number of pixels that can be copied via glCopyPixels() per second, as either colour, stencil or depth. The results vary according to the system and graphics card.

GeForce4 MX: 300M Colour, 450M Stencil, 140k Depth pixel/sec


N. T. Stewart
RMIT Mech Eng Computer Science & IT CRC for IMST