Path: utzoo!attcan!uunet!tut.cis.ohio-state.edu!cs.utexas.edu!swrinde!emory!mephisto!mcnc!rti!stdc01!mjones
From: mjones@stdc01.UUCP (Michael Jones)
Newsgroups: comp.graphics
Subject: Re: BSP (Binary Space Partition) trees?
Summary: What they are/Who invented them/Who uses them
Keywords: BSP
Message-ID: <629@stdc01.UUCP>
Date: 2 Jul 90 14:25:10 GMT
References: <3880001@hpspkla.spk.hp.com> <$JH$|Q|@rpi.edu>
Reply-To: mjones@stdc01.UUCP (Michael Jones)
Organization: Star Technologies, Graphicon Products Division (RTP, N.C)
Lines: 64

*** 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 --