Path: utzoo!utgpu!news-server.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!zaphod.mps.ohio-state.edu!wuarchive!mit-eddie!andante!amana From: amana@andante.UUCP (John Amanatides) Newsgroups: comp.graphics Subject: Re: BSP (Binary Space Partition) trees? Message-ID: <38864@andante.UUCP> Date: 31 Jul 90 04:37:22 GMT Organization: AT&T Bell Laboratories, Murray Hill Lines: 107 The following is from Bruce Naylor (he does not read netnews and thus asked me to forward this) ----------------------------------------------------------------- This is in response to some earlier comments on the origin of the binary space partitioning tree. The idea of using a binary tree of separating planes for determination of visibility priority first appears in Schumacker, Brand, Gilliland, and Sharp's "Study for Applying Computer- Generated Images to Visual Simulation,". Their method required placing the separating planes manually around polyhedral objects. These objects had the property that one could determine an "a priori visibility priority ordering" that required only the removal of back-facing polygons (convex polyhedra are a trivial example of this). No general method of finding this ordering was known at that time. While it is fairly clear as to how the bsp tree idea can be arrived at by trying to automate the tree of separating planes approach, as in fact it was, what is not well known, unless one has happened to read my thesis, is that developing a general method for solving their second technique of an a priori ordering led to the bsp tree as well. In "Predetermining Visibility Priority in 3-D Scene" by Fuchs, Kedem and Naylor, SIGGRAPH 79, the first steps toward automation of this second technique are described. This work first constructs the graph of visibility occlusion: A -> B iff there exists a viewing position such that A occludes B. If this graph is acyclic, then any total ordering of this graph will provide the view independent ordering. However, this is rarely the case due to cycles. So, one can first find the connected components; thus all cycles will be "inside" the components, and one can then totally order the components. This is all in the 79 paper. In my thesis, "A Priori Based Techniques For Determining Visibility Priority for 3-D Scenes" (UT Dallas, 1981), I present a general solution to this problem. Given the graph of a connected component and a given viewing position, one first removes all back-facing polygons from the graph. If an acyclic graph results, we are done. However, there can exist cycles and viewing positions for which all member polygons are front-facing. Therefore, as part of the pre-processing, each cycle in a connected component is examined to see if there exist such a viewing position. If not, we need do nothing. Otherwise, we choose the plane of any polygon P in the cycle and partition the cycle by this plane, i.e. split polygons by the plane. We then insert a "complement node" in the cycle that has the opposite orientation of the P, so that for every viewing position, either P or its complement is "back-facing". Thus removing back-facing polygons at display time guarantees an acyclic graph, and so a priority ordering. The problem with this approach is that there are too many cycles. So what if instead of breaking only one cycle with the plane of a polygon, we break alot of cycles at once. That is, we partition the entire subspace containing faces with the plane of some face, and then apply this recursively. This is the idea behind using bsp trees for visibility determination. So, pursuing the graph theoretic approach to determining visibility, suggested by one approach of Schumaker et al led to an extension of their second approach. However, while the idea of the bsp tree clearly came from trying to solve the visible surface problem, the bsp tree is not per se simply a structure for solving the visible surface problem! As defined in my thesis, it is a dimension independent recursive partitioning of space by hyperplanes without reference to any application. This is why I gave it the name that is has, rather than "visibility tree" for example, and its use for visibility is addressed in a separate chapter of my thesis. As I noted at that time, bsp trees generalize k-d trees, and are essentially the same as linear decision trees, which have been used to prove lower bounds on a number of problems such as the traveling salesman problem and the knapsack problem (decision trees typically do not treat the "on hyperplane" case separately because they are not interested in the boundary). It is also obviously related to quad- and oct- trees. The importance of defining it as a spatial partitioning structure is evident in its subsequent use as a representation of polytopes using only hyperplanes and { in, out } values at cells, i.e. with no faces. We are now using it in the representation of images and are exploring it use in data bases. Also, a paper appearing in this year's siggraph describes how to merge two bsp trees., and it uses only the semantics of spatial partitionings. Part of the reason that the above view of bsp trees is not wide spread is that these aspects were suppressed somewhat in the original 1980 paper because it was felt that the siggraph community was not generally receptive to formal treatments. So its application to visibility was made the prominent aspect. Also, the paper was a bit premature. It contains no references to k-d trees or linear decision trees, as does my thesis. It also does not contain the empirical results in my thesis that indicated that the size of tree was reasonable (for example, the space shuttle experienced only a 40% increase in the number of polygons, which was the first hard evidence that the approach was really practical. These results, however, were included in the siggraph presentation). As for moving objects, I have an interactive program, called Sculpt, that performs set operations between a convex "tool" and an arbitrary polyhedral work-piece at interactive rates. This is accomplished by inserting the tool into a bsp tree representing the workpiece for every "frame". Using visibility priority instead of z-buffer provides a 2x speedup on average using a Personal Iris, and there are none of the numerical problems of z-buffers. Not needing a z-buffer also makes it easy to use Sculpt with window systems on standard workstations that have no z-buffer. Sculpt is described in a paper that appeared in Graphics Interface 90. Also, the merging of bsp trees mentioned above provides a method for constructing one tree from a set of moving objects, each represented by individual trees.