Building Efficient BSP Trees for Hidden Surface Removal and Ray Tracing
Date
1998-12
Authors
Wang, Yuan
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
A Binary Space Partitioning (BSP) tree represents a recursive, hierarchical partitioning, or subdivision, of n- dimensional space into convex subspaces. The BSP tree is extremely versatile because of its powerful sorting and classification structure. The BSP trees have been used in hidden surface removal and ray tracing of computer graphics.
The choice of partition plane in building BSP trees depends on how the tree will be used and what sort of efficiency criteria will be used for the construction. For some purposes, it is appropriate to choose the partition plane from the input set of polygons. Other applications may benefit more from axes aligned to orthogonal partitions. In any case, it is necessary to evaluate how the choice will affect the results. One of the problems of constructing a BSP tree is splitting versus tree balance, which usually requires a trade off between a well-balanced tree and a large number of splits. However, no detailed criteria for a well-balanced tree have been given. The random selection of partition planes is the most commonly used approach so far in constructing BSP trees.
In this project, the criteria for building efficient BSP trees for hidden surface removal and ray tracing are analyzed. Several parameters are considered as the factors of BSP trees. They include the surface areas of polygons, the size of polygons, the number of polygons and the balance of the trees. Seven proposed methods for BSP tree generation are compared to each other by implementing applications and reporting timing results and intersected nodes per ray. The proposed methods are also compared using different sizes and different total number of polygons. The results show that a BSP tree with the fewest splits and final polygons is an optimal tree for hidden surface removal. The result also shows that a BSP tree with fewer splits and more "surface area balanced" is a more optimal tree for ray tracing.
Description
Keywords
image processing, computer programming, computer graphics
Citation
Wang, Y. (1998). Building efficient BSP trees for hidden surface removal and ray tracing (Unpublished thesis). Southwest Texas State University, San Marcos, Texas.