Mathematics for Computer Graphics
Greg Turk, August 1997
"What math should I learn in order to study computer graphics?" This is
perhaps the most common general question that students ask me about computer
graphics. The answer depends on how deeply you wish to go into the field.
If you wish to begin to use off-the-shelf graphics programs then the answer
is that you probably do not need to know very much math at all. If you wish
to take an introductory course in computer graphics, then you should read
the first two sections below for my recommendations (algebra, trigonometry
and linear algebra). If you want some day to be a researcher in graphics
then I believe that you should consider your mathematics education to be an
ongoing process throughout your career.
If you do not particularly care for mathematics, is there still a chance of
working in the field? Yes, a few areas within computer graphics are not
much concerned with mathematical ideas. You should not give up on graphics
just because you are not a math wizard. It is likely, however, that you will
have more freedom in choosing research topics if you have a willingness to
learn about new mathematical ideas.
There is no absolute answer to what mathematics is important in computer
graphics. Different areas within the field require different mathematical
techniques, and your own interests will likely lead you towards some topics
and may never touch others. Below are descriptions of a number of areas in
mathematics that I believe are useful in computer graphics. Do not feel
that you need to be an expert in each of these areas to become a graphics
researcher! I deliberately included many areas below to give a fairly broad
view of the mathematical ideas used in graphics. Many researchers, however,
will never find the need to look at some of the topics that I mention below.
Finally, although it should be clear from reading this, the opinions given
within this document are entirely my own. It is likely that you would get a
different list of topics or at least different emphases from other people
who work in computer graphics. Now on to the list of topics.
Algebra and Trigonometry
High-school level algebra and trigonometry are probably the most important
areas to know in order to begin to learn about computer graphics. Just
about every day I need to determine one or more unknowns from a simple set
of equations. Almost as often I need to perform simple trigonometry such as
finding the length of the edge of some geometric figure based on other
lengths and angles. Algebra and trigonometry are the subjects that will
solve such day-to-day tasks in computer graphics.
What about the geometry that we learn in high school? It may come as a
surprise, but our high school geometry is not very often needed for most
tasks in computer graphics. The reason for this is that geometry as it is
taught in many schools actually is a course in how to construct mathematical
proofs. While proof construction is definitely a valuable intellectual
tool, the actual theorems and proofs from your geometry class are not often
used in computer graphics. If you go to graduate school in a mathematics
related field (including computer graphics) then you may well find yourself
proving theorems, but this is not necessary in order to start out in
graphics.
If you have a good understanding of algebra and trigonometry then you are
quite prepared to begin reading an introductory book in computer graphics.
Most such books contain at least an abbreviated introduction to the next
important area of mathematics for computer graphics, namely linear algebra.
Book recommendation:
- Computer Graphics: Principles and Practice
- James Foley, Andries van Dam, Steven Feiner, John Hughes
- Addison-Wesley
- [a huge book, but still my favorite]
Linear Algebra
The ideas of linear algebra are used throughout computer graphics. In fact,
any area that concerns itself with numerical representations of geometry
often will collect together numbers such as x,y,z positions into
mathematical objects called vectors. Vectors and a related mathematical
object called a matrix are used all the time in graphics. The language of
vectors and matrices is an elegant way to describe (among other things) the
way in which an object may be rotated, shifted (translated), or made larger
or smaller (scaled). Linear algebra is usually offered either in an
advanced high school class or in college. Anyone who wishes to work in
computer graphics should eventually get a solid grounding in this subject.
As I mentioned before, however, many textbooks in graphics give a reasonable
introduction to this topic-- often enough to get you through a first course
in graphics.
Book recommendation:
- Linear Algebra and Its Applications
- Gilbert Strang
- Academic Press
Calculus
Knowledge of calculus is an important part of advanced computer graphics.
If you plan to do research in graphics, I strongly recommend getting a basic
grounding in calculus. This is true not just because it is a collection
of tools that are often used in the field, but also because many researchers
describe their problems and solutions in the language of calculus. In
addition, a number of important mathematical areas require calculus as a
prerequisite. This is the one area in mathematics in addition to basic
algebra that can open the most doors for you in computer graphics in terms
of your future mathematical understanding.
Calculus is the last of the topics that I will mention that is often
introduced in high school. The topics to follow are almost always found in
college courses.
Differential Geometry
This area of mathematics studies equations that govern the geometry of
smooth curves and surfaces. If you are trying to figure out what direction
is perpendicular to (points directly away from) a smooth surface (the
"normal vector") then you are using differential geometry. Making a vehicle
travel at a particular speed along a curved path is also differential
geometry. There is a common technique in graphics for making a smooth
surface appear rough known as "bump mapping", and this method draws on
differential geometry. If you plan to do work with curves and surfaces for
shape creation (called "modeling" in the graphics field) then you should
learn at least the basics of differential geometry. Multivariable calculus
is the prerequisite for this area.
Book recommendation:
- Elementary Differential Geometry
- Barrett O'Neill
- Academic Press
Numerical Methods
Almost every time we represent and manipulate numbers in the computer we use
approximate instead of exact values, and because of this there is always the
possibility for errors to creep in. Moreover, there are often many
different approaches to solving a given numerical problem, and some methods
will be faster, more accurate or require less memory than others. The study
of these issues goes by a number of names including "numerical methods" and
"scientific computing". This is a very broad area, and several of the other
areas of mathematics that I will mention can be considered sub-areas
underneath this umbrella. These sub-areas include sampling theory, matrix
equations, numerical solution of differential equations, and optimization.
Book recommendation:
- Numerical Recipes in C: The Art of Scientific Computing
- William Press, Saul Teukolsky, William Vetterling and Brian Flannery
- Cambridge University Press
- [this is a very valuable reference but is not normally used as a textbook]
Sampling Theory and Signal Processing
Over and over in computer graphics we represent some object such as an image
or a surface as a collection of numbers that are stored in a regular
two-dimensional array. Whenever we do this we are creating a "sampled"
representation of the object. A good understanding of sampling theory is
important if we are to use and to control the quality of such
representations. A common issue in sampling as it applies to graphics is
the jagged edges that can appear on the silhouette of an object when it is
drawn on a computer screen. The appearance of such jagged edges (one form
of a phenomenon known as "aliasing") is very distracting, and this can be
minimized by using well-understood techniques from sampling theory. At the
heart of sampling theory are concepts such as convolution, the Fourier
transform, and spatial and frequency representations of functions. These
ideas are also important in the fields of image and audio processing.
Book recommendation:
- The Fourier Transform and Its Applications
- Ronald N. Bracewell
- McGraw Hill
Matrix Equations
There are a wide variety of problems that come up in computer graphics
that require the numerical solution of matrix equations. Some problems
that need matrix techniques include: finding the best position and
orientation to match one object to another (one example of a "least
squares" problem), creating a surface that drapes over a given collection of
points with minimal creases (thin-plate splines), and simulation of
materials such as water or cloth. Matrix formulations of problems come up
often enough in graphics that I rank this area very high on my list of
topics to know.
Book recommendation:
- Matrix Computations
- Gene Golub and Charles Van Loan
- Johns Hopkins University Press
Physics
Physics is obviously a field of study in its own right and not a
sub-category of mathematics. Nevertheless, physics and mathematics are
closely tied to one another in several areas within computer graphics.
Examples of graphics problems that involve physics include how light
interacts with the surfaces of objects, how light bounces around in a
complex environment, the way people and animals move, and the motion of
water and wind. Knowledge of physics is important for simulating all of
these phenomena. This is closely tied to solving differential equations,
which I shall discuss next.
Numerical Solutions of Differential Equations
It is my belief that techniques for solving differential equations are
extremely important to computer graphics. As we just discussed, much of
computer graphics is devoted to simulating physical systems from the real
world. How waves form in water and how an animal walks across the ground
are two examples of physical simulation. Simulation of physical systems
very often leads to numerical solutions of differential equations. Note
that this is actually very different than symbolic solutions to differential
equations. Symbolic solutions are exact answers, and usually can be found
only for extremely simple sets of equations. Sometimes a college course
called "Differential Equations" will only examine symbolic solutions, and
this will not help much for most computer graphics problems.
In physical simulation, one breaks the world down into little pieces that
are represented as large vectors. Then the relations between the parts of
the world are captured in the entries in matrices. Solving the matrix
equations that arise is not usually done exactly, but is instead performed
by carrying out a long series of calculations that yields an approximate
solution as a list of numbers. This is what numerical solutions of
differential equations are about. Note that the solution of matrix
equations is an intimate part of numerical solutions to differential
equations.
Optimization
Quite often in computer graphics we are looking for a description of an
object or a collection of objects that satisfies some desired goal.
Examples include looking for the positions of lights that give a certain
"feeling" to how a room is lit, figuring out how an animated character can
move its limbs to carry out a particular action, and positioning shapes and
text on a page so that the result does not look cluttered. Each of these
examples can be stated as an optimization problem. Ten years ago there was
little in the graphics literature that made use of optimization techniques,
but the field is using optimization more and more in recent work. I think
that optimization will continue to play an increasingly important role in
computer graphics.
Probability and Statistics
There are a number of areas within computer graphics that make use of
probability and/or statistics. Certainly when researchers carry out studies
using human subject, they require statistical methods in order to perform
the analysis of the data. Graphics related areas that often make use of
human subjects include Virtual Reality and Human-Computer Interaction (HCI).
In addition, many computer descriptions of the real world involve using
various probabilities that a given action will occur. The probability that
a tree limb will branch during growth or that a synthetic animal will decide
to walk in a particular direction are two examples of this. Finally, some
techniques for solving difficult equations make use of random numbers to
estimate their solutions. An important example of this is a class of
techniques known as Monte Carlo methods that are often used to determine how
light propagates in an environment. These are just a few of the ways that
probability and statistics are used in computer graphics.
Computational Geometry
Computational geometry is the study of efficient ways to represent and
manipulate geometry within the computer. Typical problems include testing
whether two objects collide, deciding how to break up a polygon into
triangles, and finding the nearest point in a group to a given location.
This area is a blend of algorithms, data structures and mathematics.
Researchers in graphics who work on creating shapes (modeling) draw heavily
upon this area.
Book recommendations:
- Computational Geometry in C
- Joseph O'Rourke
- Cambridge University Press
- [undergraduate text]
- Computational Geometry: An Introduction
- Franco Preparata and Michael Shamos
- Springer-Verlag
- [the classic text, somewhat dated]
Concluding Words: Applied and Pure Mathematics
One common thread to many of the mathematical topics that are associate with
graphics is that they are from the applied side instead of the theoretical
side of mathematics. This should not come as a surprise. Many of the
problems in computer graphics are closely tied to problems that physicists
and engineers have studied, and the mathematical tools of the physicist and
of the engineer are overwhelmingly the tools that graphics researchers use.
Most of the topics that make up theoretical ("pure") mathematics are seldom
put to use in computer graphics. This should not be taken as an absolute
truth, however. We should pay attention to examples from other fields:
molecular biology is now drawing upon knot theory for the study of DNA
dynamics, and subatomic physics makes use of abstract group theory. Who can
tell when a "pure" mathematics topic will be put to use in computer
graphics?
There are a few areas of mathematics that seem as though they ought to be
important and yet never really play a large part in computer graphics.
Perhaps the most interesting of these areas is topology. The usual
one-sentence description of topology is the study of why a doughnut and a
coffee cup are the same. The answer is that they are both surfaces with one
hole. Here we are talking about ideas from topology. Aren't surfaces a big
part of computer graphics? Yes, but it turns out that most of the ideas in
topology that are useful to graphics can be learned in a first course in
differential geometry. Differential geometry studies the *shapes* of
surfaces, whereas topology studies things such as which parts of a surface
are next to which other parts. I have seen very little topology that is put
to use in graphics, and I believe that this is because much of topology is
concerned with rather abstract sets, and that much of topology is far removed
from the concepts in three dimensional Euclidean space that is so central to
most of graphics. There are times when the formalism of topology (the
symbolic notation) is a convenient way to express ideas in graphics, but the
actual tools from abstract topology so seldom play a role in graphics.
Study this beautiful subject for its own sake, but don't expect an immediate
payoff for graphics!
I have been asked a few times whether either abstract algebra (group theory,
rings, etc.) or number theory play a role in computer graphics. Not much
that I have seen. These subjects, like topology, are areas that are full of
beautiful ideas. Unfortunately these ideas seldom find their way into
computer graphics.