Graphics Reference
In-Depth Information
in which the
record
is successfully inserted (line 10). The
record
is tentatively
inserted in the buffer at line 7. If the insertion fails, the insertion proceeds in the
next cell along the probe sequence (lines 16 and 17). If it succeeds, the table
A
is updated and if another fragment
f
was evicted (
old != 0
), the pixel
q
covered
by
f
is computed from the age of
f
(line 11) and function
h
−
1
(line 12). The
insertion of
f
continues from the end of the list of fragments for pixel
q
,given
by
A
[
q
]+1.
The macro
OA_PACK
packs the age, depth and data of a fragment in a 64-
bits word. The age occupies the 8 most significant bits. The macro
OA_WRITE_AGE
updates the 8 most significant bits without touching the rest of the word. Finally,
the constant
OA_INC_AGE = ((uint64_t)1<<56)
is used to increment the age in the
packed
record
.
1.3.3 Building Sorted Lists with Insertion-Sort (
Pre-Open
)
In this section, we modify the construction algorithm above so as to keep the list
of fragments sorted by depth, by transforming it into an insertion-sort algorithm.
Let
f
p
be the fragment, associated with pixel
p
, that we are inserting in the
main buffer. When a collision occurs at age
i
with a stored fragment
f
p
associated
with the
same
pixel
p
, we know that both fragments currently have the same age.
Therefore, the
atomicMax
operation will compare the cell bits that are lower than
the bits used for storing the age. If the higher bits, among these lower bits,
encode the depth of the fragment then we ensure that the fragment with largest
depth is stored in the main buffer after the atomic operation:
age: 8 bits depth: 24 bits data: 32 bits
.
Further, it is possible to show that during the insertion of fragment
f
p
at age
i
,if
a collision occurs with a fragment
f
q
with
h
(
q,j
)=
h
(
p,i
), then
i
j
.Thus,the
insertion procedure will skip over all stored fragments that are not associated with
pixel
p
(since
i
≤
=
p
) and will correctly keep the fragments associated
with
p
sorted by decreasing depth along the probe sequence of
p
.Theinterested
reader will find more detail and a proof of correctness of the insertion-sort with
open addressing in our technical report [Lefebvre and Hornus 13].
Thus, we obtain an insertion-sort with open addressing simply by packing the
depth of the fragment right after its age and always starting the insertion of a
fragment at the beginning of the probe sequence. A sample implementation is
given in Listing 1.5.
=
j
⇒
q
1.4
Post-sort
and
Pre-sort
In this section we discuss details depending on the choice of scheduling for the
sort. We discuss the sort in local memory required for Post-Lin and Post-
Open, as well as how to perform early culling with Pre-Lin and Pre-Open.
