Graphics Reference
In-Depth Information
// Increment the count field of that element
elem2[index].count++;
All
value
fields are now consecutive in memory instead of being interleaved by
the
count
field and all other fields that may be part of the original
S
structure. The
search to find the largest
value
field could therefore be sped up by a factor of 2 (or
more, if additional cold fields are present in addition to the
count
field).
Compilers and linkers can also use principles similar to hot/cold splitting for
reordering of code, so that functions and parts of functions that are not frequently
called are moved, reducing instruction cache thrashing due to reduced caller-callee
cache conflicts. One such optimization is based on the concept of
cache line coloring
and involves arranging code (or data) such that frequently accessed items map to dif-
ferent cache lines (each of a distinct hypothetical color) [Hashemi97]. Unfortunately,
very few compilers currently implement cache line coloring. Although the process
can be applied by hand, it is a laborious procedure that has to be redone when-
ever the code is changed. Cache-conscious placement of data is also discussed in
[Chilimbi99a]. Splitting and field reordering is discussed in [Chilimbi99b].
13.3.2
Quantized and Compressed Vertex Data
In addition to the data structures themselves, for collision detection code it is also
important to consider how vertices are represented because they constitute a large
part of the data. Although the
x
,
y
, and
z
values of vertices are frequently stored as
three floats, it is often possible to quantize them to, for example, three 16-bit integer
values. This quantization effectively snaps the vertices to a grid, so care must be taken
so as not to cause quads and other larger collision primitives to become nonplanar.
In some cases it might even be possible to quantize a vertex further. For example,
for smaller worlds a vertex could be encoded as a 32-bit integer with, say, 11 bits
reserved for each of
x
and
y
, and 10 bits for
z
(Figure 13.3).
By expressing vertices in terms of a displacement from a previous vertex, even
less space might be required to represent a vertex. One alternative is to compute the
AABB of the vertices, use its center as a fixed origin, and compute the displacement of
vertices from this point. At the cost of representing one extra point (the origin itself)
at full precision, the other vertices can be expressed in fewer bits, on average.
For example,
consider the five spatially coherent,
but otherwise random,
16-bit
integer
vertices
A
=
(30086, 15857, 9385),
B
=
(30189, 15969, 9285),
31
0
x
11 bits
y
11 bits
z
10 bits
Figure 13.3
Vertex quantized to a 32-bit integer with 11 bits of X and Y and 10 bits of Z.
