Graphics Reference
In-Depth Information
Leaves:
t
0
t
1
t
2
t
0
t
1
t
7
t
8
t
1
t
4
t
5
t
7
...
Triangles:
v
0
v
2
v
3
v
0
v
4
v
5
v
1
v
2
v
4
...
Vertices: (x
0
,
y
0
,
z
0
)(x
1
,
y
1
,
z
1
)(x
2
,
y
2
,
z
2
)(x
3
,
y
3
,
z
3
)(x
4
,
y
4
,
z
4
)
...
Figure 13.6
A tree structure stored in a compact format, with a lot of indirection, starting
with indices from the leaves to the triangles contained in the leaves.
cache hit rate drastically and therefore also overall performance. Linearized data is
also easier to prefetch or preload (as described in Section 13.3.3).
To illustrate data structure linearization through software caching, consider a tree-
type data structure in which the leaf nodes contain a number of triangles. To reduce
space, the leaf triangles have been stored as 16-bit indices into an array of the actual
triangles. The triangles have in turn each been stored as three 16-bit indices into
an array of vertices. The data format is illustrated in Figure 13.6, and through the
following code.
// Array of all vertices, to avoid repeating vertices between triangles
Point vertex[NUM_VERTICES];
// Array of all triangles, to avoid repeating triangles between leaves
struct IndexedTriangle {
int16 i0, i1, i2;
} triangle[NUM_TRIANGLES];
// Variable-size leaf node structure, containing indices into triangle array
struct Leaf {
int16 numTris;
// number of triangles in leaf node
int16 tri[1];
// first element of variable-size array, with one or more triangles
};
