de-mystifying the walkthrough visibility code

[Seth Teller <seth@graphics.lcs.mit.edu>]

here are some random facts that may help de-mystify the
visibility modules in the walkthrough code.

first, most heavyweight computations (portals, visibility)
are computed lazily, that is, only when they are needed.
there are some conventions in place to effect this:

   * if a pointer is null, its contents have not yet been computed

   * if an ordinarily non-negative integer is -1, its value
     has not yet been computed

some consequences of these are:

   * a pointer to a list data structure containing zero elements
     signifies that the list *has* been computed and found to be
     empty (examples:  list of portals out of a cell, list of cells
     visible to a cell).

   * if something changes, and a value must be invalidated, simply
     discard the allocated memory, and reset pointer to null, OR
     reset integer value to -1.

another obscure aspect of the code is its use of time stamps.  there
is a single, integer-valued global time stamp KD_TIME(), the value of
which increases monotonically.  each cell has its own time stamp
KD_TIME(kdcell) as well.  the convention is that a cached
value stored with a cell is valid only if the cell's timestamp is
equal to the global value.  this permits any algorithm to invalidate
every cached value simply by incrementing the global timestamp.
typically this happens once per displayed frame, but it might happen
two or three times for some multi-pass visibility algorithms.

why is this useful?  the kd tree data structure is huge, and only
partially memory resident.  so a conventional "clearing" strategy
(loop over every cell, clear its data items) would not only cost a
lot of CPU, but would cause a lot of disk activity, neither of which
would be desirable in an interactive setting.  moreover, the results
of the "last" visibility query are usually completely uninteresting,
so it's objectionable in principle to expend any unrequired effort on
them, even on discarding them.

seth.