Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!cs.utexas.edu!sun-barr!newstop!jethro!exodus!peregrine!falk
From: falk@peregrine.Sun.COM (Ed Falk)
Newsgroups: comp.graphics
Subject: Re: Spatial data structures again
Keywords: Ray tracing Spatial subdivision Voxel
Message-ID: <14197@exodus.Eng.Sun.COM>
Date: 30 May 91 06:41:59 GMT
References: <1991May14.070444.18261@images.cs.und.ac.za> <1991May24.040551.2811@netcom.COM> <1991May24.140240.27603@canon.co.uk>
Sender: news@exodus.Eng.Sun.COM
Organization: Sun Microsystems, Mt. View, Ca.
Lines: 25

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.

A good example of this is a spacewars game I wrote once.  The space
ships are all rigid bodies and are well represented as BSP trees.  I
keep a sorted list (by distance) of all objects in the game.  Since
this is a small number of objects (<=20), sorting the list is not
expensive.  Also, since objects change relative distance infrequently,
a simple exchange sort usually runs in O(n) time.  It all works quite
well and the only real time-consuming operation is the actual
rendering.

		-ed falk, sun microsystems
		 sun!falk, falk@sun.com

In the future, somebody will quote Andy Warhol every 15 minutes.