“Merging BSP trees yields polyhedral set operations” by Naylor, Amanatides and Thibault
Conference:
Type(s):
Title:
- Merging BSP trees yields polyhedral set operations
Session/Category Title: Object Space Methods
Presenter(s)/Author(s):
Moderator(s):
Abstract:
BSP trees have been shown to provide an effective representation of polyhedra through the use of spatial subdivision, and are an alternative to the topologically based b-reps. While bsp tree algorithms are known for a number of important operations, such as rendering, no previous work on bsp trees has provided the capability of performing boolean set operations between two objects represented by bsp trees, i.e. there has been no closed boolean algebra when using bsp trees. This paper presents the algorithms required to perform such operations. In doing so, a distinction is made between the semantics of polyhedra and the more fundamental mechanism of spatial partitioning. Given a partitioning of a space, a particular semantics is induced on the space by associating attributes required by the desired semantics with the cells of the partitioning. So, for example, polyhedra are obtained simply by associating a boolean attribute with each cell. Set operations on polyhedra are then constructed on top of the operation of merging spatial partitionings. We present then the algorithm for merging two bsp trees independent of any attributes/semantics, and then follow this by the additional algorithmic considerations needed to provide set operations on polyhedra. The result is a simple and numerically robust algorithm for set operations.
References:
1. Sandra H. Bloomberg,”A Representation of Solid Objects for Performing Boolean Operations”, U.N.C. Computer Science Technical Report 86-006 (1986).
2. N. Chin and S. Feiner,”Near Real-Time Shadow Generation Using BSP Trees”, Computer Graphics Vol. 23(3), pp. 99-106, (Aug. 1989).
3. H. Fuchs, Z. Kedem, and B. Naylor, “On Visible Surface Generation by a Priori Tree Structures,” Computer Graphtcs Vol. 14(3), pp, 124-133, (June 1980).
4. Donald Fussell and A.T. Campbell, “Adaptive Mesh Generation for Global Diffuse Illumination,” Computer Graphics Vol. 24(3), (Aug. 1990).
5. Christoph M. Hoffmann, Geometric and Solid Modeling, Morgan Kaufmann, 1989.
6. Michael Karasick, “On the Representation and Manipulation of Rigid Solids,” Ph.D. Thesis, ComeU University (March 1989).
7. Martti Mantyla, Solid Modeling, Computer Science Press, 1988.
8. Bruce F. Naylor, “A Priori Based Techniques for Determining Visibility Priority for 3-D Scenes,” Ph.D. Thesis, University of Texas at Dallas (May 1981),
9. Bruce F. Naylor, “SCULPT : An Interactive Solid Modeling Tool”, Proc. of Graphics Interface, (May 1990).
10. Bruce F. Naylor, “Binary Space Partitioning Trees as an Alternative Representation of Polytopes”, Computer Aided Design, Vol 22(4), (May 1990).
11. Bruce F. Naylor and William C. Thibauh, “Application of BSP Trees to Ray-Tracing and CSG Evaluation,” Technical Report GIT-ICS 86/03, School of Information and Computer Science, Georgia Institute of Technology, Atlanta, Georgia 30332 (February 1986).
12. M.S. Paterson and F.F. Yao, “Binary partitions with applications to hidden-surface removal and solid modeling”, Proceedings of Fifth Syrup. on Computational Geometry, pp. 23-32, (1989).
13. M.S. Paterson and F.F. Yao, “Optimal Binary Space Partitions for Orthogonal Objects”, Proceedings of Ist Syrup. on Discrete Algorithms, pp. 100-106, (Jan. 1990).
14. R. A. Schumacker, R. Brand, M. G illiland, and W. Sharp, “Study for Applying Computer-Generated Images to Visual Simulation,” AFHRL-TR-69-14, U.S. Air Force Human Resources Laboratory (1969).
15. I.E. Sutherland, R.F. Sproull and R. A. Schumacker, “A Characterization of Ten hidden Surface Algorithms,” ACM Computing Surveys Vol 6(1), (1974).
16. W. Thibault and B. Naylor, “Set Operations On Polyhedra Using Binary Space Partitioning Trees,” Computer Graphics Vol. 21(4), (July 1987).
17. William C. Thibault, “Application of Binary Space Partitioning Trees to Geometric Modeling and Ray- Tracing”, Ph.D. Dissertation, Georgia Institute of Technology, Atlanta, Georgia, (1987).
18. Enric Torres, “Optimization of the Binary Space Partition Algorithm (BSP) for the Visualization of Dynamic Scenes” Eurographics ’90 (Sept. 1990).
