Graphics Reference
In-Depth Information
Spatial structure
g
b
a
e
c
d
f
Logical structure alternatives
e
b
d
g
a
f
c
Underlying array
Underlying linked list
Figure 37.6: A set of points distributed in 2D and two logical data structures describing
them with list semantics. The list interface on the left relies on an underlying array. The
one on the right uses an underlying linked list. Note that the order of elements within the
list is arbitrary.
Now consider the implications of generalizing from a 1D key such as a grade
to a higher-dimensional key such as a 2D location. Figure 37.6 shows a sample
2D data set with seven points labeled
a
-
g
and two alternative list implementations
corresponding to those data.
Compared to a 1D list, there is no longer a total ordering on keys. For example,
there is no general definition of “greater” between (0, 1) and (1, 0) the way that
there is between 3 and 6. Note that this problem occurs because the
key
has two or
more dimensions. There are still many cases in computer graphics where one has
values
that describe 3D data and associates those with 1D keys like the depth of
each object in a scene from the camera. One-dimensional data structures remain
as useful in graphics as in any field of computer science or software development.
Given a set of
n
values each paired with a
k
d key (Figure 37.6), a list data
structure backed by a linked list or array implementation requires
O(
n
)
space. In
practice, both implementations require space for more than just the
n
elements if
the data structure is dynamic. In the linked list there is the overhead of the link
pointers. A dynamic array must allocate an underlying buffer that is larger by a
constant factor to amortize the cost of resizing.
Because we cannot order the values in an effective way for general queries,
a query such as ray or box intersection requires
n
individual tests (see Listings
37.10-11). It must consider each element, even after some results that satisfy the
query have been obtained. We could imagine imposing a specific ordering such as
sorting by distance from the origin or by the first dimension, but unless we know
that our queries will favor early termination under that sorting, this cannot even
promise a constant performance improvement.
