Graphics Reference
In-Depth Information
// generate children nodes from a quadtree encoded
// in a 32
−
bit word
void
lt_children_2_15
(
in uint key
,
out uint children
[4])
{
key
=(++
key
&0
xF
)
|
((
key
&
∼
0
xF
)
<<
2
u
);
children
[0] =
key
;
children
[1] =
key
|
0
x10
;
children
[2] =
key
|
0
x20
;
children
[3] =
key
|
0
x30
;
}
// generate parent node from a quadtree encoded
// in a 32
−
bit word
uint lt_parent_2_15
(
in uint key
)
{
return
((
−−
key
&0
xF
)
|
((
key
>>
2
u
)&0
x3FFFFFF0
));
}
Listing 3.2.
Splitting and merging procedures in GLSL.
Note that compared to the node representation, the levels differ by 1 and the bit
codes are either 2-bit expansions or contractions. The GLSL code to generate
these representations is shown in Listing 3.2. It simply consists of an arithmetic
addition, a bitshift, and logical operations and is thus very cheap.
3.2.3 GPU Implementation
Managing a linear quadtree on the GPU requires two buffers and a geometry
shader. During initialization, we store the base hierarchy (we start with the root
node only) in one of the buffers. Whenever the nodes must be updated, the buffer
is iterated over by the geometry shader, set to write into the second buffer. If a
node needs to be split, it emits four new words, and the original code is deleted.
Conversely, when four nodes must merge, they are replaced by their parent's
code. In order to avoid generating four copies of the same node in memory, we
only emit the code once from the UL child, identified using the test provided
in Listing 3.3. For the nodes that do not require any intervention, their code is
simply emitted, unchanged.
// check if node is the upper left child
// in a 32
−
bit word
bool lt_is_upper_left_2_15
(
in
uint
key
)
{
return
((
key
&0
x30
)==0
x00
);
}
Listing 3.3.
Determining if the node represents the UL child of its parent representation.
Only the first 2-bit word of the Morton code has to be tested.
