Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!apple!netcomsv!thinman
From: thinman@netcom.COM (Lance Norskog)
Newsgroups: comp.graphics
Subject: Spatial data structures again
Keywords: Ray tracing Spatial subdivision Voxel
Message-ID: <1991May24.040551.2811@netcom.COM>
Date: 24 May 91 04:05:51 GMT
References: <1991May14.070444.18261@images.cs.und.ac.za>
Organization: Netcom - Online Communication Services  UNIX System {408 241-9760 guest}
Lines: 45

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.