Math for Computer Graphics
Greg Turk, August 2019
Twenty-two years ago, I wrote an essay about what math is important for
computer graphics. That document is now fairly dated, and I have decided that
it is time to re-visit this question. I am writing this essay in part for
college students who want to know what courses may be relevant to the study of
computer graphics. For this reason, I will remark on the departments that are
likely to offer courses in a given topic. Hopefully it is obvious that you do
not need to be a college student to read this essay!
Computer graphics draws upon many different areas of mathematics for tools that
help accomplish various computational tasks. For as long as you want to pursue
computer graphics, you should also plan to continue to learn more mathematical
techniques. There are very few corners of computer graphics that do not make
use of some form of mathematics.
The most important point that I want to convey in this essay is the following.
The mathematical topics that are often the most useful to graphics are
so-called Numerical Methods. These are the tools that take abstract
mathematical concepts (differentiation, integration, matrix inversion, etc.)
and turn them into concrete algorithms that we can use to find numerical
results to the problem at hand. When you first learn in calculus class how to
differentiate and integrate, you start by doing this symbolically. (For
example, the derivative of the sine function is cosine.) In graphics, we need
to be able to translate the symbolic answer to a given problem into a numerical
technique that can be implemented on the computer. For this reason, it is most
often the applied mathematics courses (not those in pure mathematics) that are the most
relevant to graphics.
The numerical methods that are useful for graphics are frequently the same
tools that various engineers use. This means that sometimes the most useful
courses for graphics may not be in the math department. They may instead be
found in other departments such as electrical engineering or mechanical
engineering.
In this essay I am going to refer the four core areas of computer graphics.
These areas are:
- Modeling - creating 3D shape descriptions of objects
- Animation - making objects move
- Image Synthesis, also called Rendering - making pictures from 3D shapes
- Image and Video Manipulation
I am going to visit the mathematics useful to graphics in an order that
(approximately) lines up with the order of the four topics listed above. Note
that modeling and animation often make use of similar mathematics. The same is
true of the other pair — image synthesis and image/video manipulation often use
similar math tools. Before I visit any of these topics, however, I am going to
start with the math needed for a first course in graphics.
Mathematical Basics: Linear Algebra and Trigonometry
The most important topics for starting out in graphics are Linear Algebra and
Trigonometry. We usually describe the location of a 3D graphics object
according to its x, y and z coordinates. We can then apply the following
operations on a 3D object: translate (move), scale (change size), and rotate.
Translation and scale are accomplished using addition and multiplication,
respectively. Rotation is done using sine and cosine, hence the need for
trigonometry. The x, y and z coordinates of an object can be conveniently
represented as a 3D vector, and the translate, scale and rotate operations can
be described as multiplication by a matrix (of size 3x3 or 4x4). This is one
of the reasons that a background in linear algebra is important for starting in
graphics. Several other concepts from linear algebra also are useful,
including matrix inversion, dot product, and cross product.
Multivariable Calculus
Many of the more advanced topics in computer graphics make use of the tools of
Multivariable Calculus. These topics are usually saved for a second or third
course in calculus. Many of the representations that are used in computer
graphics are functions of multiple variables, and thus require tools to reason
about derivatives and integrals of such functions. If you want to study
computer graphics beyond a first course in the area, I strongly recommend
taking the full sequence of calculus classes that your school offers.
Differential Geometry
Differential Geometry is the measurement of properties of curves and surfaces,
and these techniques are very important for modeling in graphics. Common
graphics-related tasks that fall under this domain include determining
tangents, measuring curvature, evaluating lengths and areas, and finding
shortest paths. Often differential geometry techniques are combined with
optimization methods (more on this below). Fortunately, many math departments
offer an undergraduate course in differential geometry.
Computational Geometry
Computational Geometry is the study of algorithms that efficiently and robustly
solve geometric problems. Some common problems in this area include find
convex hulls, finding nearest neighbors to a given query point, determining the
intersection between two surfaces, and triangulating a polygon. The tools of
computational geometry are frequently used in both modeling and animation (e.g
for collision detection). Strictly speaking, computational geometry is a
branch of computer science theory, not mathematics. You are more likely to
find a course in computational geometry in a computer science department rather
than in a math department.
Numerical Linear Algebra
The one topic in applied mathematics that is perhaps the most important across
a wide array of graphics problems is Numerical Linear Algebra. Usually the
study of numerical methods for linear algebra is typically not covered in a
first course in linear algebra. The linear algebra problems that arise from
computer graphics often require setting up and solving large linear systems of
equations, with very large matrices and thousands or tens of thousands of
unknowns. The simple methods that you learn for solving matrix equations in a
first linear algebra course do not work for such problems. Instead, you need
to learn to describe the linear systems in a sparse matrix form (much more
memory efficient) and learn about iterative techniques for solving such
systems. Some of these methods used include Jacobi, Gauss-Seidel, and the
conjugate gradient method. Occasionally you may run into other related
numerical problems such as finding eigenvectors and eigenvalues.
Optimization
Many problems in both modeling and animation describe a given task as an
Optimization problem. Say we wish to create a smooth object that passes
through a given set of points. First, the object in question is represented
numerically, such as a collection of triangles that describes the shape of the
surface. Next, we represent a desired quality of the object numerically,
such as the smoothness of the surface. The problem is now to find the
positions of the triangles’ vertices that maximizes the smoothness measure,
while still passing through the given set of points. Such a minimization
problem is described as a large linear system of equations, and iterative
numerical techniques are used to solve such a system.
Partial Differential Equations
Animation of materials such as water, rubber and snow require numerical methods
for Partial Differential Equations (PDE’s). The equations that arise from
these problems include diffusion equations, transport equations, Laplace
equations and Poisson equations. These are often solved by turning the problem
into a large linear system of equations, or formulating the problem as one of
constrained optimization. You are unlikely to learn much about these
techniques in a calculus class. The techniques for solving such problems are
more often studied in engineering courses and numerical methods courses. A
well-known method for solving some of these problems is know as the Finite
Element Method (FEM). Although it is by no means the only method for solving
some of these problems, it is one of the more important techniques, and there
are often courses devoted to this approach. Not only are these numerical
techniques important for computer animation, they also arise frequently in 3D
modeling problems.
Ordinary Differential Equations
The animation of characters (people, animals, robots) is often performed by
representing the character as a collection of rigid objects that are connected
by joints. For example, a person’s arm can be described as an upper arm
segment, a lower arm segment, and an elbow joint that connects these two
segments. The motion of a character described in this way is governed by the
numerical integration of Ordinary Differential Equations (ODE’s). Alas, a
typical course in ODE’s will most likely give you very little in the way of
help for this, because such courses are heavy on symbolic solutions instead of
numerical solutions. A course on numerical methods is much more likely to
discuss the relevant numerical methods (forward Euler, midpoint method,
implicit integration, Runge-Kutta, etc.)
Signal Processing
Many areas in image synthesis and image manipulation touch upon signal
processing. Indeed, these techniques are sometimes also relevant to modeling
and animation as well. We usually represent an image as 2D grid of pixels,
where each pixel is given a color. This regular array of color values can be
thought of as a digital representation of a 2D function, and this is a
“signal”. We can perform operations on our image (the signal) such as contrast
modification, blurring, warping, sharpening, and so on. The shape of a surface
or the motion of an animated character can also be thought of as a signal,
making these techniques relevant to modeling and animation as well. Often the
best way to analyze and process signals is to convert them into another
representation by using tools such as the Fourier transform. Signal processing
is heavily used in the study of electronics and audio, so courses on this topic
are often taught in an electrical engineering department.
Monte Carlo Integration Methods
While the problems in animation usually lead to differential equations, those
of image synthesis are usually integral equations. The amount of light that
reaches a light-detecting element in a camera or our eye is the sum of all the
light coming from all different directions, and that light may have come from
several different light sources and bounced off a number of different
materials. Such as sum of light paths can be written as an integral equation.
While you may learn of basic quadrature methods for calculating integrals in an
introductory calculus class, it turns out that such methods do not work well
for light transport problems. Instead, random sampling of many different light
paths is a much better way to go. These techniques are referred to as Monte
Carlo Methods, and these randomization techniques were named for the resort of
the same name where gambling casinos are big business. Unfortunately, courses
on Monte Carlo techniques are pretty rare.
The Rise of Machine Learning
If you are studying computer science, you are undoubtably aware that the area
of machine learning has recently become huge. (I am writing this in 2019.) In
particular, the methods of deep neural networks have seen an explosion of
activity. It probably comes as no surprise that deep learning has had a large
impact in computer graphics. Neural networks are used for numerous graphics
tasks, including: where to shoot rays for better lighting calculations,
de-noising images, controlling the motion of virtual characters, classifying 3D
models, and for image editing. If you want to study graphics, it is important
to learn the tools of machine learning, and especially to learn about neural
networks. Note that machine learning is closely related the mathematical
topics of probability and statistics.
Off The Beaten Path
Some topics in mathematics are not as commonly used in graphics as those that I
have mentioned above. In the old version of this essay, I said that Topology
and Abstract Algebra were not useful for graphics. Now I have to correct
myself.
Topology
As it turns out, one of my own PhD students, Eugene Zhang, did his dissertation
work in computer graphics that drew primarily from the area of topology. He
studied how to create and edit vector and tensor fields based on the critical
points of the fields. Analyzing the connections between these critical points
is very much a problem of topology. His work is not the only such case, and
there are several other techniques in graphics that draw heavily upon ideas
from topology.
Abstract Algebra
Abstract algebra is the study of objects such as groups, rings and fields.
While many of these mathematical constructs are not particularly useful to
computer graphics, a researcher named Ken Turkowski pointed out to me that
group theory does in fact play an important role in graphics. When we describe
the orientation of a 3D object, and when we want to change its orientation, we
are using group theory. The space of all 3D orientations is known as the group
SO(3), and it turns out this is a fairly counter-intuitive mathematical object.
Researchers in graphics have used several different ways of describing elements
in this group and operations over these elements, including 3x3 matrices,
quaternions, and exponential maps. Describing smooth changes in orientation
often leads graphics researchers to study SO(3).
Number Theory
The topic of number theory is the study of the integers, and researchers in
this area investigates questions such as the distribution of prime numbers.
Famously, Fermat’s Last Theorem (now solved!) is a problem in number theory.
The mathematician G. H. Hardy wrote a book entitled “A Mathematician’s
Apology”, in which he describes the beauty of pure mathematics. One of the
themes of his book is that his own area of expertise, number theory, is a topic
that is to be appreciated in and of itself. He goes on to say that number
theory really doesn’t have much in the way of practical applications to
real-world problems. So far as I know, number theory is not particularly
useful in computer graphics. If you choose to study number theory, you should
do it for the beauty of the topic and not for any possible application in
graphics.