==============================================================================

Hi Friends,

Last week we looked at the problem of how to schedule a ray-tracing
algorithm.  We shoot rays back from a viewpoint.  To do so, we divide
space into blocks, and in each block we processed all of the rays entering
the block and send the rays out in the correct direction, to a neighboring
block.  The ultimate objective is to schedule the problem to minimize the
number of memory transfers because this will optimize the computing time. 
Our main objective was to minimize the number of blocks that we have to
process in this algorithm, where the cost of processing block is one time
unit. 

Each ray that we shoot backwards forms a tree, where the nodes form the
names of the blocks.  Steve will begin the meeting by reminding us why
this problem is related to the shortest supersequence problem on a
collection of strings.  We will also consider both online and offline
versions of this scheduling problem.  (Unfortunately, Kevin Kreeger and
Ingmar Bitter will not be able to attend the reading group, because of a
last minute graphics conflict.  We will try not to solve all of the
problems in their absence.) 

It should be an excellent meeting!
See you tomorrow.
Michael

==============================================================================

  Scheduling for Memory Coherent Ray Tracing

  Naive ray tracing follows each ray to completion as
  it bounces around a computer simulated scene. Spatial
  decomposition of a scene into cells has been proposed to
  reorder the computations to perform spatially coherent
  processing. We are interested in determining a (hopefully)
  optimal schedule order for the individual cells to
  maximize memory coherency.