Basic Math for Computer Graphics
Sungkil Lee
Sungkyunkwan University
Objectives
• Much of graphics is just translating math directly into code.
– The cleaner the math, the cleaner the resulting code.
– Also, clean codes result in better performance in many cases.
• In this lecture, we review various tools from high school and college
mathematics.
• This chapter is not intended to be a rigorous treatment of the material;
instead, intuition and geometric interpretation are emphasized.
Basic Math for Computer Graphics. Sungkil Lee. 1/44
Sets and Mappings
• Sets
– a is a member of set S
a ∈ S
– Cartesian product of two sets: given any two sets A and B,
A×B = {(a, b)|a ∈ A and b ∈ B}
∗ As a shorthand, we use the notation A2 to denote A×A.
Basic Math for Computer Graphics. Sungkil Lee. 2/44
Sets and Mappings
• Common sets of interest include:
– R: the real numbers
– R+: the non-negative real numbers (includes zero)
– R2: the ordered pairs in the real 2D plane
– Rn: the points in n-dimensional Cartesian space
– Z: the integers
Basic Math for Computer Graphics. Sungkil Lee. 3/44
Sets and Mappings
• Mappings (also called functions)
f : R 7→ Z
– “There is a function called f that takes a real number as input and
maps it to an integer.”
– equivalent to the common programming notation :
integer f(real) ← equivalent → f : R 7→ Z
“There is a function called f which has one real argument and returns
an integer.”
Basic Math for Computer Graphics. Sungkil Lee. 4/44
Intervals
• Three common ways to represent an interval
a < x < b (a, b ] a b _ a to b that includes b but not a Basic Math for Computer Graphics. Sungkil Lee. 5/44 Intervals • Interval operations on [3, 5) and [4, 6] Basic Math for Computer Graphics. Sungkil Lee. 6/44 Logarithms • Every logarithm has a base a. “log base a” of x is written loga x • The exponent to which a must be raised to get x y = loga x⇔ ay = x Basic Math for Computer Graphics. Sungkil Lee. 7/44 Logarithms • Several consequences: – aloga x = x – loga a x = x loga a = x – loga xy = loga x+ loga y – loga x/y = loga x− loga y – loga x = loga b logb x Basic Math for Computer Graphics. Sungkil Lee. 8/44 Logarithms • Natural logarithm – The special number e = 2.718... – The logarithm with base e is called the natural logarithm lnx ≡ loge x ∗ Note that the “≡” symbol can be read “is equivalent by definition.” Basic Math for Computer Graphics. Sungkil Lee. 9/44 Logarithms • The derivatives of logarithms and exponents illuminate why the natural logarithm is “natural”: d dx loga x = 1 x ln a d dx ax = ax ln a The constant multipliers above are unity only for a = e. d dx lnx = 1 x ln e = 1 x d dx ex = ex ln e = ex Basic Math for Computer Graphics. Sungkil Lee. 10/44 Trigonometry • The conversion between degrees and radians: degrees = 180 π radians radians = π 180 degrees Basic Math for Computer Graphics. Sungkil Lee. 11/44 Trigonometry • Trigonometric functions – Pythagorean theorem: a2 + o2 = h2 sinφ ≡ o/h cscφ ≡ h/o cosφ ≡ a/h secφ ≡ h/a tanφ ≡ o/a cotφ ≡ a/o Basic Math for Computer Graphics. Sungkil Lee. 12/44 Trigonometry • The functions are not invertible when considered with the domain R. This problem can be avoided by restricting the range of standard inverse functions, and this is done in a standard way in almost all modern math libraries. • The domains and ranges are: arcsin (asin) : [−1, 1] 7→ [−π/2, π/2] arccos (acos) : [−1, 1] 7→ [0, π] arctan (atan) : R 7→ [−π/2, π/2] arctan 2 (atan2) : R2 7→ [−π, π] Basic Math for Computer Graphics. Sungkil Lee. 13/44 Trigonometry • The atan2(s, c) is often very useful in graphics: It takes an s value proportional to sinA and a c value that scales cosA by the same factor, and returns A. Basic Math for Computer Graphics. Sungkil Lee. 14/44 Vector Spaces (in Algebratic Math) • A vector space over a field F is a set V together with addition and multiplication that satisfy the eight axioms. Elements of V and F are called vectors and scalars. Axiom Meaning Associativity of addition u + (v + w) = (u + v) + w Commutativity of addition u + v = v + u Identity element of addition There exists an element 0 ∈ V such that v + 0 = v for all v ∈ V . Inverse elements of addition For every v ∈ V , there exists an element v ∈ V such that v + (−v) = 0. Distributivity of scalar multiplication a(u + v) = au + av with respect to vector addition Distributivity of scalar multiplication (a + b)v = av + bv with respect to field addition Compatibility of scalar multiplication a(bv) = (ab)v with field multiplication Identity element of scalar multiplication 1v = v, where 1 denotes the multiplicative identity in F . Basic Math for Computer Graphics. Sungkil Lee. 15/44 Vector Spaces (in Algebratic Math) • A vector space over a field F is a set V together with addition and multiplication that satisfy the eight axioms. Elements of V and F are called vectors and scalars. • Mathematical structures related to the concept of a field can be tracked as follows: - A field is a ring whose nonzero elements form a abelian group under multiplication. - A ring is an abelian group under addition and a semigroup under multiplication; addition is commutative, addition and multiplication are associative, multiplication distributes over addition, each element in the set has an additive inverse, and there exists an additive identity. - An abelian group (commutative group) is a group in which commutativity (a · b = b · a) is satisfied. - A semigroup is a set A in which a · b satisfies associativity for any two elements a and b and opeator ·. - A group is a set A in which a · b satisfies closure, associativity, identity element, and inverse element for any two elements a and b and opeator ·. Basic Math for Computer Graphics. Sungkil Lee. 16/44 Vectors (Simply) • A quantity that encompasses a length and a direction. • Represented by an arrow and not as coordinates or numbers • Length: ‖a‖ • A unit vector: Any vector whose length is one. • The zero vector: the vector of zero length. The direction of the zero vector is undefined. Basic Math for Computer Graphics. Sungkil Lee. 17/44 Vectors (Simply) • Two vectors are added by arranging them head to tail. This can be done in either order. a + b = b + a • Vectors can be used to store an offset, also called a displacement, and a location (or position) that is a displacement from the origin. Basic Math for Computer Graphics. Sungkil Lee. 18/44 Cartesian Coordinates of a Vector • Vectors in a n-D vector space are said to be linearly independent, iff a1v1 + a2v2 + · · ·+ anvn = 0 has only the trivial solution (a1 = a2 = · · · = an = 0). – The vectors are thus referred to as basis vectors. – For example, a 2D vector c may be expressed as a combination of two basis vectors a and b: c = aca + bcb, where ac and bc are the Cartesian coordinates of the vector c with respect to the basis vectors {a,b}. Basic Math for Computer Graphics. Sungkil Lee. 19/44 Cartesian Coordinates of a Vector • Assuming vectors, x and y, are orthonormal, a = xax + yay the length of a is ‖a‖ = √ xa2 + ya2 By convention we write the coordinates of a either as an ordered pair (xa, ya) or a column matrix: a = [ xa ya ] a> = [xa ya]
Basic Math for Computer Graphics. Sungkil Lee. 20/44
Dot Product
• The simplest way to multiply two vectors (also called the scalar product).
a · b = ‖a‖‖b‖ cosφ
• The projection of one vector onto another: the length a → b of the
projection of a that is projected onto b
a→ b = ‖a‖ cosφ =
a · b
‖b‖
Basic Math for Computer Graphics. Sungkil Lee. 21/44
Dot Product
• If 2D vectors a and b are expressed in Cartesian coordinates,
a · b = (xax + yay) · (xbx + yby)
= xaxb(x · x) + xayb(x · y) + xbya(y · x) + yayb(y · y)
= xaxb + yayb
• Similarly in 3D,
a · b = xaxb + yayb + zazb
Basic Math for Computer Graphics. Sungkil Lee. 22/44
Cross Product
‖a× b‖ = ‖a‖‖b‖ sinφ
• By definition the unit vectors in the positive direction of the x−, y− and
z−axes are given by
x = (1, 0, 0),
y = (0, 1, 0),
z = (0, 0, 1),
and we set as a convention that x × y must be in the plus or minus z
direction.
z = x× y
Basic Math for Computer Graphics. Sungkil Lee. 23/44
Cross Product
• The ”right-hand rule”:
Imagine placing the base of your right palm where a and b join at their
tails, and pushing the arrow of a toward b. Your extended right thumb
should point toward a× b.
Basic Math for Computer Graphics. Sungkil Lee. 24/44
2D Implicit Curves
• Curve: A set of points that can be drawn on a piece of paper without
lifting the pen.
• A common way to describe a curve is using an implicit equation.
f(x, y) = 0
f(x, y) = (x− xc)2 + (y − yc)2 − r2
• If f(x, y) = 0, the points where this equality hold are on the circle
with center (xc, yc) and radius r.
Basic Math for Computer Graphics. Sungkil Lee. 25/44
2D Implicit Curves
• “implicit” equation: The points (x, y) on the curve cannot be
immediately calculated from the equation, and instead must be
determined by plugging (x, y) into f and finding out whether it is
zero or by solving the equation.
• The curve partitions space into regions where f > 0, f < 0 and f = 0. Basic Math for Computer Graphics. Sungkil Lee. 26/44 The 2D Gradient • If the function f(x, y) is a height field with height = f(x, y), the gradient vector points in the direction of maximum upslope, i.e., straight uphill. The gradient vector ∇f(x, y) is given by ∇f(x, y) = ( ∂f ∂x , ∂f ∂y ) • The gradient vector evaluated at a point on the implicit curve f(x, y) = 0 is perpendicular to the tangent vector of the curve at that point. This perpendicular vector is usually called the normal vector to the curve. Basic Math for Computer Graphics. Sungkil Lee. 27/44 The 2D Gradient • The derivative of a 1D function measures the slope of the line tangent to the curve. • If we hold y constant, we can define an analog of the derivative, called the partial derivative : ∂f ∂x ≡ lim ∆x→0 f(x+ ∆x, y)− f(x, y) ∆x Basic Math for Computer Graphics. Sungkil Lee. 28/44 Implicit 2D Lines • The familiar “slope-intercept” form of the line is y = mx+ b This can be converted easily to implicit form y −mx− b = 0 Ax+By + C = 0 Basic Math for Computer Graphics. Sungkil Lee. 29/44 Implicit 2D Lines • The gradient vector (A,B) is perpendicular to the implicit line Ax + By + C = 0 Basic Math for Computer Graphics. Sungkil Lee. 30/44 2D Parametric Curves • A parametric curve: controlled by a single parameter, t,[ x y ] = [ g(t) h(t) ] Vector form : p = f(t) where f is a vector valued function f : R 7→ R2 Basic Math for Computer Graphics. Sungkil Lee. 31/44 2D Parametric Lines • A parametric line in 2D that passes through points p0 = (x0, y0) and p1 = (x1, y1) can be written[ x y ] = [ x0 + t(x1 − x0) y0 + t(y1 − y0) ] Because the formulas for x and y have such similar structure, we can use the vector form for p = (x, y): p(t) = p0 + t(p1 − p0) Parametric lines can also be described as just a point o and a vector d: p(t) = o + t(d) Basic Math for Computer Graphics. Sungkil Lee. 32/44 2D Parametric Lines • A 2D parametric line through P0 and P1. The line segment defined by t ∈ [0, 1] is shown in bold. Basic Math for Computer Graphics. Sungkil Lee. 33/44 Linear Interpolation • Most common mathematical operation in graphics. • Example of linear interpolation: Position to form line segments in 2D and 3D p = (1− t)a + tb – interpolation: p goes through a and b exactly at t = 0 and t = 1 – linear interpolation: the weighting terms t and 1 − t are linear polynomials of t Basic Math for Computer Graphics. Sungkil Lee. 34/44 Linear Interpolation • Example of linear interpolation: A set of positions on the x-axis: x0, x1, ..., xn and for each xi we have an associated height, yi. – A continuous function y = f(x) that interpolates these positions, so that f goes through every data point, i.e., f(xi) = yi. – For linear interpolation, the points (xi, yi) are connected by straight line segments. – It is natural to use parametric line equations for these segments. The parameter t is just the fractional distance between xi and xi+1: f(x) = yi + x− xi xi+1 − xi (yi+1 − yi) Basic Math for Computer Graphics. Sungkil Lee. 35/44 Linear Interpolation • In the common form of linear interpolation, create a variable t that varies from 0 to 1 as we move from data A to data B. Intermediate values are just the function (1− t)A+ tB. t = x− xi xi+1 − xi Basic Math for Computer Graphics. Sungkil Lee. 36/44 2D Triangles • With origin and basis vectors, any point p can be written: p = (1− β − γ)a + βb + γc α ≡ 1− β − γ p(α, β, γ) = αa + βb + γc with the constraint that α+ β + γ = 1 • A particularly nice feature of barycentric coordinates is that a point p is inside the triangle formed by a, b, and c if and only if 0 < α < 1, 0 < β < 1, 0 < γ < 1. Basic Math for Computer Graphics. Sungkil Lee. 37/44 2D Triangles • A 2D triangle (vertices a, b, c) can be used to set up a non-orthogonal coordinate system with origin a and basis vectors (b − a) and (c − a). A point is then represented by an ordered pair (β, γ). For example, the point p = (2.0, 0.5), i.e., p = a + 2.0(b− a) + 0.5(c− a). Basic Math for Computer Graphics. Sungkil Lee. 38/44 2D Triangles • Defined by 2D points a, b, and c. Its area: area = 1 2 ‖(b− a)× (c− a)‖ = 1 2 ∥∥∥∥ xb − xa xc − xayb − ya yc − ya ∥∥∥∥ = 1 2 ((xb − xa)(yc − ya)− (xc − xa)(yb − ya)) = 1 2 (xayb + xbyc + xcya − xayc − xbya − xcyb) Basic Math for Computer Graphics. Sungkil Lee. 39/44 3D Triangles • Barycentric coordinates extend almost transparently to 3D. If we assume the points a, b, and c are 3D, p = (1− β − γ)a + βb + γc • The normal vector: taking the cross product of any two vectors. n = (b− a)× (c− a) Basic Math for Computer Graphics. Sungkil Lee. 40/44 3D Triangles This normal vector is not necessarily of unit length, and it obeys the right-hand rule of cross products. • The area of the triangle: Taking the length of the cross product. area = 1 2 ‖(b− a)× (c− a)‖ Basic Math for Computer Graphics. Sungkil Lee. 41/44 Vector Operations in Matrix Form • We can use matrix formalism to encode vector operations for vectors when using Cartesian coordinates; if we consider the result of the dot product a one by one matrix, it can be written: a · b = aTb • If we take two 3D vectors we get: [xa ya za] [ xb yb zb ] = [xaxb + yayb + zazb] Basic Math for Computer Graphics. Sungkil Lee. 42/44 Matrices and Determinants • The determinant in 2D is the area of the parallelogram formed by the vectors. We can use matrices to handle the mechanics of computing determinants. [ a A b B ] = [ a b A B ] = aB −Ab • For example, the determinant of a particular 3×3 matrix [ 0 1 2 3 4 5 6 7 8 ] = 0 [ 4 5 7 8 ] + 1 [ 5 3 8 6 ] + 2 [ 3 4 6 7 ] = 0(32− 35) + 1(30− 24) + 2(21− 24) = 0 Basic Math for Computer Graphics. Sungkil Lee. 43/44