mjones@stdc01.UUCP (Michael Jones) (07/02/90)
*** Robert R. Champagne writes: *** Could somebody please explain/define BSP (Binary Space *** Partition) trees. Binary Space Partitioning trees (BSP-Trees) are a hierarchial data structure used to encode spatial relationships. These trees are very useful in graphic applications where a fixed or semi-fixed database is view from a series of changing viewpoints. In this application, they allow traversal of the database in a fixed front-to-back or back-to-front order in _linear_ time. This is a significant advantage over the O(n log n) time required by general sorting methods. They have been used in high-performance flight simulation for many years, and represent the central theme of systems by Evans and Sutherland, General Electric COMPU-SCENE, and, of course, Star Technologies :-). Their only weakness is the semi-fixed database restriction, which can be a pain. This is why the ubiquitous "Graphics Workstation" uses Z-buffering, thereby avoiding the pre-processing step (BSP-Tree generation) and limits on database editing. However, they yield total throughput, update rate, and image quality in exchange for this flexibility -- BSP-Trees are still firmly rooted in the real-time out-the-window world of flight simulation. *** Wm. Randolph Franklin writes: *** You could contact Bruce Naylor, one of the inventors, at *** naylor@allegra.att.com Although Mr. Naylor's 1980 paper with H. Fuchs and Z.M. Kedem was good, and the further research for the Ph.D. was also good, he was not one of the BSP Tree inventors. I only mention this because there seems to be a belief that "the first appearance in SIGGRAPH denotes discovery" by posters in this news group. Not so! (That's like saying the National League vs. Americal League championship is the "World Series" (as if Portugal and China were invited.) Although I cannot say who was first with the BSP-Tree idea, any claim to priority must preceed Schumacker, Brand, Gilliland, and Sharp's "Study for Applying Computer-Generated Images to Visual Simulation," published by the U.S. Air Force Human Resources Laboratory as AFHRL-TR-69-14 in September 1969. In this paper, they describe both the separating plane (BSP-Tree) and cluster ideas quite explicitly. There was an earlier Schumacker work, "Modifications to Interim Visual Spaceflight Simulator," provided by GE to NASA as the final report of contract NAS 9-3916 in February 1968. This one also discusses the ideas, although perhaps less powerfully. Since these papers preceed Naylor by 11 years, he cannot be credited with the invention of BSP-Trees. NEW MATERIAL: There are other interesting priority encoding schemes, used by Star, Evans and Sutherland, GE Daytona Beach (COMPU-SCENE), and others. This is just not an area where all research has been published. What has been published is usually in the I/ITSC proceedings, not SIGGRAPH, which may be seen as less receptive to innovative graphics technology with military applications. Many papers have been published in the I/ITSC proceedings about BSP-Trees and other graphics research, including texture mapping, anti-aliasing, interpolation of motion, object intersection, and transparency simulation. Some current flight simulation visual systems provide _all_ of these feaures, at 60 Hz update rates for several thousand polygons, at prices competitive with graphics workstations. Need I say whose? -- -- Michael T. Jones Email: ...!{uunet,mcnc}!rti!stdc01!mjones -- -- The wise man will pursue Paper: 3101-H Aileen Drive, Raleigh NC 27606 -- -- excellence in all things Voice: W:(919)361-3800 and H:(919)851-7979 --
amana@andante.UUCP (John Amanatides) (07/31/90)
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.