Graphics Reference
In-Depth Information
1
2
3
4
C
A
B
Figure 7.23
Using time stamping avoids having to intersect the ray against object
A
twice,
in both cells 1 and 2, as the ray is traced through the uniform grid. By storing the computed
intersection with object
B
into a
mailbox
, the intersection can be reused in cell 3 without
having to be recomputed.
between
A
and the ray,
A
is simply tagged with the time stamp of the ray and the
ray processing continues to the next cell. In cell 2, the ray is again tested against
A
,
but because it has already been time stamped with the current time object
A
can be
safely ignored.
However, consider what happens with object
B
. It is also tested against in cell 1.
There is an intersection between
B
and the ray, but the intersection point is in cell 3.
Because the intersection point is not in the current cell, it is possible that there could
be another intersection in the cells between (and in fact there is, with object
C
in
cell 3). Thus, the ray processing must continue to subsequent cells. Before continuing
to the next cell, the intersection with
B
must be compared to the best intersection
stored so far to see if it constitutes a closer intersection. Because
B
happens to be
the first object intersected, this is clearly the case and a pointer to
B
along with the
parametric time at which the ray strikes
B
are saved as the currently best intersection.
Before
B
is finally time stamped, it also makes sense to update the number of cells
being traversed by the ray query. Because it is now known that there is an intersection
in cell 3, there is no need to continue processing into cell 4. In cell 2, objects
A
and
B
have to be tested again, but both have been time stamped and are thus ignored,
with processing continued to cell 3. In cell 3,
B
is again tested and ignored because
of its time stamp. The ray is also tested against object
C
, which it intersects. As the
intersection with
C
is found to be closer than the stored intersection with object
B
, the best intersection is updated to correspond to this new intersection. At this
point, because there are no more objects to test in cell 3 and the ray processing
was earlier set to stop in this cell the query can now return with the intersection
with
C
as the result after having performed the intersection test with each object
once only.
One slight problem remains. Regardless of the size used for the time stamp
counter, eventually it will overflow. If enough bits have been assigned for the
counter — which could well approach 64 bits for certain applications — the problem
can safely be ignored as not happening during the uptime of the application. Assume
for now that to conserve memory only an 8-bit counter was used. Every 256 ticks, the
time stamp counter will now overflow and at that time all stored time stamps will
have to be reset. If they are not, an object that has not been time stamped in 256 ticks
