thinman@netcom.COM (Lance Norskog) (05/24/91)
mikhaley@images.cs.und.ac.za writes: >I am writing a ray-tracer as an honours research project, which >renders tesselated shapes from >Mathemtica, and am also looking into >implementing CSG for some non-tesselated shapes to be input. I'm interested in a related problem: painting a changing 3D scene in real-time. Yes, the Virtual Reality problem. The situation is that there's a large database of polygons, probably nothing else, that can change per frame update. 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 full of bouncing soccer balls. There is one soccer ball specification. The balls bounce as if they were concrete cubes. No intersection or squishing, so the balls are static. Now we're getting somewhere. Treat the scene is a two-level database: sort the balls not as sets of polygons, but just as balls. Each ball is a "virtual copy" of a BSP'd soccer ball. Each frame needs a full sort of a small database, and a repetetive BSP walk of a static pre-sorted database. Another issue is shading. There's no time to shade moving, changing objects from first principles. But, there may be time to take the surface normals of each soccer ball face against the eyepoint and one or more light sources and look up a brightness for that polygon, giving a reasonable stab at flat shading. A much nicer job can be done on still objects like furniture. If we legislate that moving object cast no shadows, we can radiositize the static members of a scene, and voxel-walk them on each update. This allows nice shading and surface textures for environments, and really adds to the ambience of the virtual experience. What data structures should be used for this radiosity operation? What overall rendering method (scan-line v.s. object-first, etc.) should be used to repetitively walk a multi-data-structure object database? Lance Norskog -- Lance THES IZ BENITO AGEN. WEE AR STUK SUMWERE IN TEKSUS. WEE AR LOST. I OFURRED THE MAP TOO CAESAR THRE TIMES, END THRICE HEE REFUZED ITT. THERFORE, I REMANED NAVIGATER.
ads@canon.co.uk (Adam Billyard) (05/24/91)
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. Adam Billyard
uselton@nas.nasa.gov (Samuel P. Uselton) (05/25/91)
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
falk@peregrine.Sun.COM (Ed Falk) (05/30/91)
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.