On Constructing Binary Space Partitioning Trees Ravinder Krishnaswamy Ghascm S. Alijani Auto Trol Technology Shyh-Chang Su Research and Development Computer Science Department 12500 North Washington University of Wyoming Denver, CO 80233 Laramie, WY 82071 Abstract Binary Space Partitioning Trees have several applications in computer graphics. We prove that there exist n-polygon problem instances with an O(n2) lower bound on tree size. We also show that a greedy algorithm may result in constructing a tree with O(n2) nodes, while there exist a tree for the same n-polygon instance with only O(n) nodes. Finally, we formulate six different heuristics and test their performance. 1. Introduction The hidden line elimination problem is of fundamental importance in computer graphics [4,6,7]. The Binary Space Partitioning (BSP) tree is one approach to the problem [l], and has received recent attention in [2.3,8]. An attractive aspect of the BSP tree is that once the tree corresponding to a collection of objects is created, the scene represented by the tree can be displayed with hidden line elimination in time that is linear in the number of nodes of the tree. This efficiency inherent in BSP tree based hidden line elimination is cause for serious consideration of BSP trees to be used in parallel real-time scene generation [5]. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery. To copy other- wise, or to republish, requires a fee and/or specific permission. 0 1990 ACM 089791-348-5/90/0002/0230 $1.50 230 In general, the tree representing a set of polygons is not unique, in fact, the number of nodes in trees representing the same scene may vary substantially depending on heuristics used in constructing the tree. The focus of this research is to evaluate several heuristics used to construct BSP trees according to the following two criteria : (a) The size (number of nodes) of the tree. @J) The extent to which the tree is height-balanced. The order in which polygons in the left subtree of a node are processed is independent of the order in which polygons of the right subtree of the node are processed. This observation is the motivation for including (b) as a method of judging the potential for parallelism (balanced subdivision of labour) reflected in the tree structure 2. Definition and Notation Definition : A BSP tree is a binary tree constructed from a polygon list. The basic notion is that given a plane in a three dimensional scene and a viewing point, no polygon on the view point side of the plane can be obstructed by any polygon on the far side. The tree can be recursively constructed as follows :A polygon is selected from the list and placed at the root, Each remaining polygon is tested to see which side of the plane containing the root polygon it lies in, and is placed in the appropriate side list. A polygon that intersects the plane containing the root polygon is split, and each of the pieces is placed in the appropriate list depending on which halfspace it lies in. The left and right subtrees are recursively constructed using the descendent sublists generated. Figure 1 shows a 2-D example of the above proCdUre. Figure 1 Notation : Let BSP(I) denote a BSP tree corresponding to an instance I of n polygons and BSP(I)I denote the tree obtained from instance I through using heuristic j.We say that BSP(I)* is a ‘node-optimal’ tree if BSP(I)* contains the least number of nodes of all possible trees BSP(1). ‘Height-optimal’ is similarly defined. It is observed in [l] that a BSP tree may contain as much as O(n2) nodes, where n = I I I. We show that in fact the node-optimal tree BSP(l)* may contain as many nodes too. Bounds on Tree Size T&vent 1: There exists an instance I such that BSP(I)* contains O(n2) nodes. Proof : Let II denote the set of polygons PO, PI . . . . P(n/2 -1) obtained as follows. PO is a rectangle with coordinates ~(0, 0, l),(i, 0, l),(l, n/2+2,1),(0, n/2+2,1)>, and pi is obtained by translating pi-l unit distance along the positive z direction for II i c n/2. Let 12 denote the set of polygons Pt.,/2 s P,/2+1, . . . . Pn-I where P,/2 is a rectangle with coordinates <(2,1,0), (3.1.0). (3,l,n/2+1), (2.1, n/2+1)>, and pi is obtained by translating Pi-l unit along the y direction for n /2 5 i c n. (see Figure 2). Let I = I1 U 12. We claim that any tree constructed from I must contain exactly n(n+!) /4 nodes. Let 1 i, n/p+j represent the line of intersection of the planes containing the polygons Pi and Pn/2 +j where 0 I ij c n/2. Let BSP (I)* be a ‘node-optimal’ tree and let P be some node in the tree. Without loss of generality assume that P was obtained from Pi for some i < $2. We say the line li, n/2+j is properly contained in P if li, n/2+j intersects the interior of P. Let k lines be properly contained in P. This means that polygons Pn/2+jl , Pn/2+j2,.., Pn/2+jk were split by P when P was selected to be the root of some subtree. Since each line li, n/2+j is properly contained in some polygon of the tree, the number of such splits equal to the number of lines 1 id = (n/2)2* Therefore, the number of polygons in the tree is equal to (n/2)2+ n = n(n+4)/4. Y Figure 2 231Scvcral diffcrcnt heuristics have been formulated and applied in constructing the BSP tree [1,3]. Each of thcsc hcurislics pcrforrn near oplimal under a certain wclldcfmcd conditions. In Lhc following WC rcfcr to a greedy algorithm as the heuristic which at each step selects a polygon as the root that imcrsccls the least number of polygons. In the next thcorcm we in fact show that a greedy algorithm results in the worst case tree (BSP(I)g) for even a fairly straightforward problem instance. This further justifies the need lo formulate different heuristics and carefully examine their performance. Theorem 2 : There exists
View Full Document
Unlocking...