Graphics Reference
In-Depth Information
Line
Record
z
n
1
Pos
p
0
n
1
0
0
12
p
z
n
1
0
0
18
p
n
2
z
n
2
z
n
1
0
0
112
p
z
n
1
z
n
2
0
0
12
n
2
z
n
2
z
n
2
z
n
1
0
0
18
n
2
n
3
z
n
3
z
n
3
z
n
1
z
n
1
0
0
12
p
z
n
2
z
n
2
z
n
2
0
0
12
n
2
z
n
1
z
n
3
z
n
3
0
0
12
n
3
z
n
1
0
0
18
n
3
Figure 1.2.
Insertion of three fragments into the list of pixel
p
. Their respective depths
are
z
1
,
z
2
and
z
3
with
z
2
>z
3
>z
1
. The triangles on the left indicate the start of the
insertion of a new fragment. Each line is a snapshot of the variables and main buffer
state at each iteration of the
while
loop at lines 12 or 18 of Listing 1.3.
been properly re-inserted. Figure 1.2 illustrates the insertion of three fragments
associated with a single pixel
p
.
Compared to the approach of [Harris 01] based on a 32-bit atomic compare
and swap, our technique has the advantage of compactness and does not require
synchronization in the main loop. In particular the loop in Listing 1.3 can be
rewritten as follows:
while
((
old
=
atomicMax64
(
buffer
+
pos
,
record
))
>
0)
{
1
=
getNext
(
max
(
old
,
record
));
pos
2
record
=
min
(
old
,
record
);
3
}
4
Please refer to the accompanying source code for an implementation of both
approaches (file
implementations.fp
, functions
insert_prelin_max64
and
insert_prelin_cas32
).