Graphics Reference
In-Depth Information
enough to recover
p
as
o
i
mod
H,
or, in
C
speak,
(hVal + gBufferSize - offsets[i]) % gBufferSize
.
p
=
h
(
p,i
)
−
Let us define
h
−
1
(
v,i
)=
v
o
i
mod
H
. The function
h
−
1
lets us recover the
pixel
p
, which is covered by a fragment of age
i
stored in cell
v
of the main
buffer:
p
=
h
−
1
(
v,i
). In order to compute this inverse given
v
, the age of a
fragment stored in the main buffer must be available. Hence, we reserve a few
bits (typically 8) to store that age in the buffer, together with the depth and data
of the fragment.
When inserting the fragments, we should strive to minimize the age of the
oldest fragment, i.e., the fragment with the largest age. This is particularly
important to ensure that when walking along lists of fragments for several pixels in
parallel, the slowest thread—accessing old fragments—does not penalize the other
threads too much. This maximal-age minimization is achieved during insertion:
old fragments are inserted with a higher priority, while young fragments must
continue the search of a cell in which to be written.
We define the
load-factor
of the main buffer as the ratio of the number of
fragments inserted to the total size of the main buffer.
−
Collisions.
A collision happens when a thread tries to insert a fragment in a cell
that already contains a fragment. Collisions can happen since the probe sequence
that we follow is essentially random. When the main buffer is almost empty (the
load-factor is low), collisions rarely happen. But as the load-factor increases, the
chance of collisions increases as well. The open addressing scheme that we have
just described works remarkably well even when the load-factor is as high as 0
.
95.
A collision happens when a thread tries to insert a fragment
f
p
covering pixel
p
at position
h
(
p,i
)forsome
i
, but the cell at that position already contains a
fragment
f
q
for some other pixel
q
.Wethenhave
h
(
p,i
)=
h
(
q,j
) and solve the
collision depending on the value of
i
and
j
:
•
If
j
=
i
,then
q
=
p
. The fragment
f
q
covers the same pixel
p
; we keep it
there and try to insert fragment
f
p
at the next position
h
(
p,i
+1). Alterna-
tively, as in Section 1.3.3, we might compare the depths of both fragments
to decide which one to keep at that position and which one to move.
•
If
j
=
i
, then pixels
p
and
q
are different pixels. In that case, we store
the fragment with the largest age in that cell and continue along the probe
sequence of the other fragment. More precisely, if
i>j
then the older
fragment
f
p
replaces
f
q
in the main buffer and the insertion of the younger
fragment
f
q
is restarted at age
j
+ 1, i.e., at position
h
(
q,j
+1)inthe
main buffer. Note that the value
q
is not known in advance and must be
computed as
q
=
h
−
1
(
h
(
p,i
)
,j
). If
i<j
, then fragment
f
q
does not move
