Graphics Reference
In-Depth Information
1.1.12
Chapter 13: Optimization
The last chapter of the topic talks about how to take the efficient data structures
and algorithms presented throughout the topic and make them even more efficient
by targeting and tuning them for a particular hardware platform. Large performance
gains can be had by optimizing code to take advantage of memory hierarchies (caches)
and of code and data parallelism. Chapter 13 presents detailed descriptions on how
to perform such optimizations.
1.2
About the Code
As part of the hands-on nature of this topic, many of the presented ideas are sup-
plemented by code examples. Whereas many topics rely exclusively on high-level
pseudocode to convey the broad ideas of an algorithm, here the majority of the code
is given in C++. There are two reasons for presenting code in this detail. First, it
provides the minutiae often vital to the understanding (and implementation) of an
algorithm. Second, understanding can now additionally be had from running the
code and inspecting variable values during execution. The latter is particularly impor-
tant for a reader who may not be fully versed in the mathematics required for a
particular algorithm implementation. Only in a few places in the topic is the given
code expressed in pseudocode, primarily where it would not be practical to provide
a full implementation.
Although C++ is used for the code in the topic, it should be stressed that the
focus of the topic is
not
on C++. C++ is only used as a means to present detailed
executable descriptions of the described concepts. Any computer language would
serve this purpose, but C++ was chosen for a few reasons, including its popularity
and its ability to abstract, in a succinct way, the low-level manipulation of geometrical
entities such as points and vectors using classes and (overloaded) infix operators. To
make the presented code accessible to as many programmers as possible (for example,
those only familiar with C or Java), certain features of C++ such as templates and STL
(Standard Template Library) were deliberately avoided where possible. C++ purists
may want to take a few deep breaths at the start of each chapter!
Similarly, this is
not
a topic on software engineering. To get the basic ideas to come
across as best as possible, the code is kept short and to the point. Concessions were
made so as not to clutter up the text with verbose C++ syntax. For example, class
definitions are deliberately minimalistic (or nonexistent), global variables sometimes
substitute for proper member variables, pointers are not declared
const
(or
restrict
),
and arrays are often declared of fixed size instead of being dynamically allocated of
an appropriate size. Variable names have also been limited in length to make code
lines better fit on a typeset page.
To turn the presented code into real production code, some additions may be
necessary. For example, tests for division by zero are not always performed to avoid
