Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!think.com!spool.mu.edu!agate!usenet.ins.cwru.edu!eagle!data.nas.nasa.gov!wk207!uselton
From: uselton@nas.nasa.gov (Samuel P. Uselton)
Newsgroups: comp.graphics
Subject: Re: Spatial data structures again
Keywords: Ray tracing Spatial subdivision Voxel
Message-ID: <1991May24.170453.22951@nas.nasa.gov>
Date: 24 May 91 17:04:53 GMT
Article-I.D.: nas.1991May24.170453.22951
References: <1991May14.070444.18261@images.cs.und.ac.za> <1991May24.040551.2811@netcom.COM> <1991May24.140240.27603@canon.co.uk>
Sender: Sam Uselton
Organization: NAS Program, NASA Ames Research Center, Moffett Field, CA
Lines: 48

In article <1991May24.140240.27603@canon.co.uk> ads@canon.co.uk writes:
>thinman@netcom.COM (Lance Norskog) writes:
>
>> BSP doesn't work well here by itself, because you have to re-BSP the
>> scene per change.  Re-sorting the list per update doesn't work either,
>> because it takes too long.  But, consider the following scene: a room
>
>I think I'd take issues with this idea that you have to recompute the
>BSP trees each time an object moves.  When the model is closed and
>convex, then any transform short of inversion with be fine since there
>is no crossing of planar boundaries from one half space to the other.
>
>I've been thinking that when BSP trees are built, they should include
>some sort of specification as to the space constraints imposed by the
>root on the immediate children; if the transform leaves the subtree
>still within this bounding volume (probably needs to be finer than a
>bbox) then BSP recomputation is unnecessary. 

The defining planes for the nodes from the root on the path to the current
node DO define this bounding volume!
>
>
>	Adam Billyard

Try looking at the original two stage spatial hierarchy as described in
several older texts (and the old Sutherland Sproull & Schumacher, "10
Hidden Line (or Surface?) Algorithms), usually called Schumacher et al's
Priority Based Algorithm.  They defined a static priority ordering for 
each rigid object (this could be done with a BSP-tree for the object),
and a separate priority ordering for objects in the scene.  As long as
objects don't interpenetrate (actually as long as convex hulls don't
interpenetrate, but objects DON'T need to be convex), only the tree for 
the object level needs redone with moving objects (and then really only 
if an object intersects a plane used in defining the previous tree).
  
Also, note that things don't change "too much" from frame to frame,
so an "edit" to a subtree may be all that is needed, rather than a 
total rebuild.  (Analogous to using a "sort" in the Painter's Algorithm
that makes linear passes of local interchanges, rather than using a
sort that runs in O(n log n) worst case.)


I've seen some pretty impressive performance from BSP-tree implementations
(thanks for the demos Bruce) and would suggest you look for faster rendering
(shading calculations) first (maybe hardware assist?).

Sam Uselton		uselton@nas.nasa.gov
employed by CSC		working for NASA (Ames)		speaking for myself