Graphics Reference
In-Depth Information
atomic_uint firstFreeCell
=
gScreenSize
;
1
databuf
[
gBufferSize
];
Data
2
uint64_t buffer
[
gBufferSize
+
gScreenSize
];
3
4
5
uint64_t pack
(
uint32_t depth
,
uint32_t next
)
{
return
((
uint64_t
)
depth
<<
32)
|
next
;
6
}
7
8
9
void
insertFrontPack
(
x
,
y
,
uint32_t depth
,
data
)
{
const int
fresh
=
atomicCounterIncrement
(
firstFreeCell
);
10
databuf
[
fresh
−
gScreenSize
]=
data
;
11
buffer
[
fresh
]=
atomicExchange
(
buffer
+
x
+
y
gScreenW
,
12
pack
(
depth
,
fresh
));
13
}
14
Listing 1.2.
Insertion at the head of a linked list with packing.
1.2.2 Packing
depth
and
next
Together
In order to facilitate the understanding of later sections and render the exposition
more uniform with Section 1.3, this section introduces specific changes to the
buffer layout. We illustrate this new layout by describing an alternative way to
build unsorted linked-lists.
The following changes are done: First, all fragment data except
depth
are
segregated in a specific data buffer, that we call
databuf
. Second, the
depth
and
the
next
fields are packed in a single 64-bits word. Third, the main buffer is
enlarged with as many cells as pixels on screen. These additional cells at the
beginning of the buffer are used just like the
heads
array in Listing 1.1.
Listing 1.2 shows the new insertion procedure. Two observations should be
kept in mind:
We must follow the
next
index
n −
1 times to access the depth of the
n
th
fragment, and
n
times to access its other data.
Notice the new initial value of
firstFreeCell
and the offset needed when
accessing the fragment data.
We keep this buffer layout throughout the remainder of the chapter.
The following diagram illustrates the position of four fragments
f
i
,i
=1
,
2
,
3
,
4,
inserted in this order, with depth
z
fi
and data
d
i
, associated with a pixel with
coordinates (
x, y
). Observe how each cell of the main buffer packs the depth
z
i
of a fragment and the index
n
fi
of the next item in the list. Note that with this
layout the index
n
fi
of the fragment following
f
fi
never changes.
databuf (offset by gScreen Size):
· · ·
d
1
· · ·
d
2
· · ·
d
3
· · ·
d
4
x
+
y
× gScreen Width
n
1
n
2
n
3
n
4
z
4
n
4
z
1
n
1
z
2
n
2
z
3
n
3
0
buffer
· · ·
· · ·
· · ·
· · ·
used as heads
