“Blister: GPU-based rendering of Boolean combinations of free-form triangulated shapes” by Hable and Rossignac

By combining depth peeling with a linear formulation of a Boolean expression called Blist, the Blister algorithm renders an arbitrary CSG model of n primitives in at most k steps, where k is the number of depth-layers in the arrangement of the primitives. Each step starts by rendering each primitive to produce candidate surfels on the next depth-layer. Then, it renders the primitives again, one at a time, to classify the candidate surfels against the primitive and to evaluate the Boolean expression directly on the GPU. Since Blist does not expand the CSG expression into a disjunctive (sum-of-products) form, Blister has O(kn) time complexity. We explain the Blist formulation while providing algorithms for CSG-to-Blist conversion and Blist-based parallel surfel classification. We report real-time performance for nontrivial CSG models. On hardware with an 8-bit stencil buffer, we can render all possible CSG expressions with 3909 primitives.

1. Adams, B., and Dutré, P. 2003. Interactive Boolean operations on surfel-bounded solids, ACM Transactions on Graphics, 22, 3, 651–656. Google ScholarDigital Library
2. Banerjee, R., Goel, V., Mukherjee, A. 1993. Efficient parallel evaluation of CSG tree using fixed number of processors. ACM Symposium on Solid Modeling and Applications, 137–146. Google ScholarDigital Library
3. Barber C., Dobkin, D., Huhdanpaa, H., 1993. The Quickhull algorithm for convex hulls, ACM Transactions on Mathematical Software, 22, 4, 469–483. Google ScholarDigital Library
4. Cameron, S., Yap, C. 1992. Refinement methods for geometric bounds in constructive solid geometry, ACM Transactions on Graphics, 11, 1 12–39. Google ScholarDigital Library
5. Chen, H., and Fang, S. 1999. A volumetric approach to interactive CSG modeling and rendering. ACM Symposium on Solid Modeling and Applications, 318–319. Google ScholarDigital Library
6. Ellis J., Kedem G., Lyerly G. T., Thielman D., Marisa R., Menon J. 1991. The Ray Casting Engine and ray representations. ACM Symposium on Solid Modeling Foundations and Applications, 255–268. Google ScholarDigital Library
7. Epstein, D., Jansen, F., and Rossignac, J. 1989. Z-buffer rendering from CSG: The Trickle algorithm. Research Report RC 15182, IBM.Google Scholar
8. Erhart, G., and Tobler, R. 2000. General purpose z-buffer CSG rendering with consumer level hardware. Tech Rep. VRVis 003, VRVis Zentrum für Vurtual Reality und Visualisierung Forschungs-GmbH.Google Scholar
9. Everitt, C. 2002. Interactive order-independent transparency. Tech Report, nVidia Corporation. http://developer.nvidia.com.Google Scholar
10. Fang, S., and Liao, D. 2000. Fast CSG voxelization by frame buffer pixel mapping. IEEE Symposium on Volume Visualization, 43–48. Google ScholarDigital Library
11. Fuchs, H., and Poulton, J. 1981. Pixel-planes: a VLSI-oriented design for 3-D raster graphics. Canadian Man-Computer Communications Conference. 343–347.Google Scholar
12. Goldfeather, J., Hultquist, J. P. M., and Fuchs, H. 1986. Fast constructive solid geometry display in the pixel-powers graphics system. Annual Conference on Computer Graphics and Interactive Techniques. 107–116. Google ScholarDigital Library
13. Goldfeather, J., Molnar, S., Turk, G., and Fuchs, H. 1989. Near realtime CSG rendering using tree normalization and geometric pruning. IEEE Computer Graphics and Applications, 9, 3, 20–28. Google ScholarDigital Library
14. Goodrich, M. 1990. Applying parallel processing techniques to classification problems in constructive solid geometry. ACM-SIAM Symposium on Discrete Algorithms, 118–128. Google ScholarDigital Library
15. Goodrich, M. 1998. An improved ray shooting method for constructive solid geometry models via tree contraction. International Journal of Computational Geometry and Applications, 8, 1, 1–24.Google ScholarCross Ref
16. Guha, S., Krishnan, S., Munagala, K., Venkatasubramanian, S. 2003. Application of the two-sided depth test to CSG Rendering. Symposium on Interactive 3d graphics, 177–180. Google ScholarDigital Library
17. Hoffmann, C. 1989. Geometric and Solid Modeling: An Introduction, Morgan Kaufmann. Google ScholarDigital Library
18. Jansen, E. 1986. A Pixel-Parallel Hidden Surface Algorithm for Constructive Solid Geometry. Eurographics, 29–40.Google Scholar
19. Kelley, M., Gould, K., Pease, B., Winner, S., Yen, A. 1994. Hardware accelerated rendering of CSG and transparency. Conference on Computer Graphics and Interactive Techniques, 177–184. Google ScholarDigital Library
20. Keyser, J., Bulver, T., Foskey, M., Krishnan, S., Manocha, D. 2002. Esolid — A system for exact boundary evaluation. ACM Symposium on Solid Modeling and Applications, 23–34. Google ScholarDigital Library
21. Kohavi, Z. 1986. Switching and Finite Automata Theory, 2nd Edition. McGraw Hill College. R. Hamming and E. Feigenbaum. Google ScholarDigital Library
22. Liao, D., and Fang, S. 2002. Fast volumetric CSG modeling using standard graphics system. ACM Symposium on Solid Modeling and Applications, 204–211. Google ScholarDigital Library
23. Mamman, A. 1989. Transparency and antialiasing algorithms implemented with the virtual pixel maps technique. IEEE Computer Graphics and Applications, 9, 4, 43–55. Google ScholarDigital Library
24. Rappoport A. and Spitz, S. 1997. Interactive Boolean Operations for Conceptual Design of 3-D Solids. ACM SIGGRAPH Conference on Computer Graphics, 269–278. Google ScholarDigital Library
25. Requicha, A., and Voelcker, H. 1985. Boolean operations in solid modeling: Boundary evaluation and merging algorithms. Proceedings of the IEEE, 75, 1, 30–44.Google ScholarCross Ref
26. Rossignac, J., and Requicha, A. 1986. Depth-buffering display techniques for constructive solid geometry, IEEE Computer Graphics and Applications, 6, 9, 26–39.Google ScholarDigital Library
27. Rossignac, J., Voelcker, H. 1988. Active zones in CSG for accelerating boundary evaluation, redundancy elimination, interference detection, and shading algorithms, ACM Transactions on Graphics, 8, 1, 51–87. Google ScholarDigital Library
28. Rossignac, J., and Wu, J. 1992. Correct shading of regularized CSG solids using a depth-interval buffer, Advanced Computer Graphics Hardware V: Rendering, Ray Tracing and Visualization Systems, Eurographics Seminars, 117–138.Google Scholar
29. Rossignac, J., Megahed, A., Schneider. B. O. 1992. Interactive Inspection of Solids: Cross-Sections and Interferences, ACM Computer Graphics, Vol. 26, No. 2, pp. 353–360, July (Proc. SIGGRAPH). Google ScholarDigital Library
30. Rossignac, J. 1994. Through the cracks of the solid modeling milestone, From Object Modeling to Advanced Visual Communication, S. Coquillart, W. Strasser, P. Stucki, Ed., Springer-Verlag, 1–75.Google Scholar
31. Rossignac, J. 1996. CSG formulations for identifying and for trimming faces of CSG models. In CSG’96: Set-theoretic solid modeling techniques and applications, Information Geometers, Ed. John Woodwark. 1–14.Google Scholar
32. Rossignac, J. 1999. BLIST: A Boolean list formulation of CSG trees, Technical Report GIT-GVU-99-04 available from the GVU Center at Georgia Tech. http://www.cc.gatech.edu/gvu/reports/1999/Google Scholar
33. Stewart, N., Leach, G., and John, S. 1998. An improved z-buffer CSG rendering algorithm. Eurographics/SIGGRAPH Workshop on Graphics Hardware, ACM Press, New York. 25–30. Google ScholarDigital Library
34. Stewart, N., Leach, G., and John, S. 2000. A CSG rendering algorithm for convex objects. International Conference in Central Europe on Computer Graphics, Visualization and Interactive Digital Media — WSCG 2000, 2, 369–372.Google Scholar
35. Stewart, N., Leach, G., and John, S. 2002. Linear-time CSG rendering of intersected convex objects. International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision — WSCG 2002, 2, 437–444.Google Scholar
36. Stewart, N., Leach, G., and John, S. 2003. Improved CSG rendering using overlap graph subtraction sequences. International Conference on Computer Graphics and Interactive Techniques in Australasia and South East Asia, ACM Press, New York. 47–53. Google ScholarDigital Library
37. Tawfik, M. 1991. An efficient algorithm for CSG to Brep conversion. ACM Symposium on Solid Modeling Foundations and Applications, 99–108. Google ScholarDigital Library
38. Tilove, R. B. 1984. A Null-Object Detection Algorithm for Constructive Solid Geometry, Communications of the ACM, 27, 7, 684–694. Google ScholarDigital Library
39. Wiegand, T. F. 1996. Interactive rendering of CSG models, Computer Graphics Forum, 15, 4, 249–261.Google ScholarCross Ref