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.
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.
Regards,
Nigel Stewart
Thesis
N. Stewart,
An Image-Space Algorithm for Hardware-Based 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. 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
Citations
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
Bibliography
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
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 csgdemo-0.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 1-6.
|
 |
|
bubbles
Bubbles Convex Intersection Demonstration
Three animated spheres intersected in real-time.
|
 |
|
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 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
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
|
|
