# 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:

1. Modeling - creating 3D shape descriptions of objects
2. Animation - making objects move
3. Image Synthesis, also called Rendering - making pictures from 3D shapes
4. 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.