Introduction
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.
ZBuffer Constructive Solid Geometry (CSG) Rendering is a multipass,
viewspecific, technique for displaying the result of volumetric
boolean operations in realtime, 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 5axis 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 zbuffer 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.
Regards,
Nigel Stewart
Thesis
N. Stewart,
An ImageSpace Algorithm for HardwareBased Rendering of Constructive Solid Geometry, May 2008
PhD Thesis
Publications
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. 4753
Paper:
graphite03.pdf (452 Kb) MD5 checksum: 7d083721578a8562f2ca95f94ca3ec4e
Slides:
graphite03.pdf (412 Kb) MD5 checksum: d662f3077a03de433842321179a825ca
N. Stewart, G. Leach, S. John,
Lineartime CSG Rendering of Intersected Convex Objects,
The 10th International Conference in Central Europe on Computer Graphics,
Visualization and Computer Vision '2002  WSCG 2002, Volume II, pp. 437444
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. 165176
Paper:
Abstract
dmtcs2001.pdf (107 Kb) MD5 checksum: 03b7bcfcec07b638e9d4c0196fef92c2
N. Stewart, G. Leach, S. John,
A CSG Rendering Algorithm for Convex Objects,
The 8th International Conference in Central Europe on Computer Graphics,
Visualisation and Interactive Digital Media '2000  WSCG 2000,
Volume II, pp. 369372
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 ZBuffer CSG Rendering Algorithm,
1998 Eurographics/Siggraph Workshop on Graphics Hardware, pp. 2530
Paper:
egsggh98.pdf (345 Kb) MD5 checksum: 805f9ad8bada61268571da1c0f0fa390
Slides: Online,
egsggh98_4up.pdf (949 Kb) MD5 checksum: 06da99cc9c6b40529b54699a43076de8
Citations
F. Romeiro,
L. Velho,
L. H. Figueiredo,
Hardwareassisted Rendering of CSG Models,
XIX Brazilian Symposium on Computer Graphics and Image Processing (SIBGRAPI'06),
2006, pp. 139146
J. Hable,
J. Rossignac,
CST: Constructive Solid Trimming for Rendering BReps and CSG,
GVU Technical Report GITGVU0616,
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. 333335
J. Hable,
J. Rossignac,
Blister: GPUbased rendering of Boolean combinations of freeform triangulated shapes,
Proceedings of ACM SIGGRAPH 2005,
Vol. 24, No. 3, 2005, pp. 10241031
F. Kirsch,
J. DÃ¶llner,
Rendering Techniques for HardwareAccelerated ImageBased CSG,
Journal of WSCG 2004,
Vol. 12, No. 2, 2004, pp. 221228
K. Munagala,
S. Guha,
S. Krishnan,
S. Venkat,
The Power of a TwoSided 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 TwoSided 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. 8691
T. Theoharis,
G. Papaioannou,
E. Karabassi,
The Magic of the ZBuffer: A Survey,
The 9th International Conference in Central Europe on Computer Graphics,
Visualization and Computer Vision 2001 
WSCG 2001,
2001
R. Tobler,
G. Erhart,
General Purpose ZBuffer CSG Rendering with Consumer Level Hardware,
VRVis Technical Report 200003
2000
Bibliography
ImageSpace CSG Rendering (by author)
D. Epstein,
F. Jansen,
J. Rossignac,
ZBuffer 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 PixelPowers Graphics System,
Computer Graphics (Proc. Siggraph),
Vol. 20, No. 4, Aug 1986, pp. 107116
J. Goldfeather,
S. Molnar,
G. Turk,
H. Fuchs,
Near RealTime CSG Rendering Using Tree Normalization and Geometric Pruning,
IEEE CG&A,
Vol. 9, No. 3, May 1989, pp. 2028
J. O'Loughlin,
C. O'Sullivan,
RealTime Animation of Objects Modelled using Constructive Solid Geometry,
Proceedings of the Spring Conference in Computer Graphics '99,
1999, pp. 6773
A. Rappoport,
S. Spitz,
Interactive Boolean Operations for Conceptual Design of 3D Solids,
Siggraph 97,
pp. 269278
A. Requicha,
Representations for Rigid Solids: Theory, Methods, and Systems,
Computing Surveys,
Vol. 12, No. 4, Dec 1980, pp. 437464
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. 3044
J. Rossignac,
J. Wu,
Correct Shading of Regularised CSG Solids using a DepthInterval 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. 249261
Permutation Embedding Sequences (by date)
L. Adleman,
Short Permutation Strings,
Discrete Mathematics,
Vol. 10, 1974, pp. 197200
P.J. Koutas, T.C. Hu,
Shortest String Containing All Permutations,
Discrete Mathematics,
Vol. 11, 1975, pp. 125132
G. Galbiati, F.P. Preparata,
On PermutationEmbedding Sequences,
SIAM J. Appl. Math.,
Vol. 30, No. 3, May 1976, pp. 421423
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. 129136
M. Cai,
A New Bound on the Length of the Shortest String
Containing all rPermutations,
Discrete Mathematics,
Vol. 39, 1982, pp. 329330
C. Savage,
Short Strings Containing All kElement Permutations,
Discrete Mathematics,
Vol. 42, 1982, pp. 281285
A.A. Schaffer,
Shortest Prefix Strings Containing All Subset Permutations,
Discrete Mathematics,
Vol. 64, 1987, pp. 239252
Image Gallery
Sequenced Convex Subtraction (SCS) Algorithm
Illustrations of the SCS Algorithm
WSCG 2000 Paper Images
Download


Source Code
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.



Binaries (95/98/NT/2000/XP)
 CsgDemo csgdemo0.4.exe (3522 Kb)
MD5 checksum: d934b50873373c188b7c9bc87882a1d1 9th May 2009



csgdemo
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 16.



bubbles
Bubbles Convex Intersection Demonstration
Three animated spheres intersected in realtime.



convint
Cylinder Intersection Demonstration
Use + and  to adjust the number of intersected cylinders.



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
OpenGL ZEqual Diagnostic
The exact depth stored in the zbuffer 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
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

Links

