Graphics Reference
In-Depth Information
and is suddenly tested would incorrectly report that it has already been tested in the
current time slice!
The time stamping technique described here has been described in the context
of ray tracing as
mailboxes
[Amanatides87]. Another approach to eliminating mul-
tiple intersections and redundant calculations is the
residency masks
described in
[Cychosz92].
In most applications, resetting the time stamp values will go unnoticed. However,
for applications with a huge number of objects this operation could become expensive.
For those applications, the solution is then to not reset all time stamp values at once.
This solution is explored in the next section.
7.7.3
Amortized Time Stamp Clearing
The one-time overhead of resetting time stamp counters can be lessened using an
amortized clearing scheme. Instead of clearing the counters all at once when the
global counter overflows, the set of all time stamp counters can be divided into
smaller blocks with a single block being reset each frame.
The best illustration of this amortized method is through a small example (see
Table 7.2). Consider having some
n
objects, say 10, that are divided into three blocks
(of three, three, and four objects each). Let the time stamp counters also count up
to three. At start, all objects are initialized to have a time stamp of 0. On the first
frame, the global time stamp counter is incremented to 1. After all objects have been
updated, it is possible for each block to contain objects with time stamps of either 0
or 1. Before ending the first frame, block 0 is cleared to the
current
value of the global
time stamp counter.
The same procedure is now repeated on each successive frame, with the next
block of objects cleared, again to the current value of the global counter of that frame.
Referring to Table 7.2, note that at the end of frame 4 there can no longer exist an
object with a time stamp of value 1, which is the value the global counter will assume
on frame 5. Similarly, at the end of frame 5 there is no object with a time stamp value
of 2, and so on for all subsequent frames.
To further illustrate how the amortized clearing method works, the following code
is an example of what an implementation of the method could look like. First, some
required constant values are defined.
// Use 8 bits for the time stamp counter [0..255]
#define MAX_COUNTER_VALUE 255
// Divide up all time-stamped objects into as many blocks
#define NUM_BLOCKS MAX_COUNTER_VALUE
