UPI YPTK - Padang
Mathematical Foundation
for Graphics
Eko Syamsuddin Hasrito, PhD
204481 Foundation of Computer Graphics April 18, 2020 1
Acknowledgement
This lecture note has been summarized from
lecture note on Foundation of Computer
Graphics, Introduction to Computer Graphics
all over the world. I can’t remember where
those slide come from. However, I’d like to
thank all professors who create such a good
work on those lecture notes. Without those
lectures, this slide can’t be finished.
204481 Foundation of Computer Graphics April 18, 2020 2
Objectives
Introduce the elements of geometry
Scalars
Vectors
Points
Develop mathematical operations among them
in a coordinate-free manner
Define basic primitives
Line segments
Polygons
204481 Foundation of Computer Graphics April 18, 2020 3
Basic Elements
Geometry is the study of the relationships
among objects in an n-dimensional space
In computer graphics, we are interested in objects
that exist in three dimensions
Want a minimum set of primitives from which we
can build more sophisticated objects
We will need three basic elements
Scalars
Vectors
Points
204481 Foundation of Computer Graphics April 18, 2020 4
Coordinate-Free Geometry
When we learned simple geometry, most of us
started with a Cartesian approach
Points were at locations in space p=(x,y,z)
We derived results by algebraic manipulations
involving these coordinates
This approach was nonphysical
Physically, points exist regardless of the location of
an arbitrary coordinate system
Most geometric results are independent of the
coordinate system
Euclidean geometry: two triangles are identical if two
corresponding sides and the angle between them are
identical
204481 Foundation of Computer Graphics April 18, 2020 5
Geometry
Geometry provides a mathematical foundation
for much of computer graphics:
Geometric Spaces: Vector, Affine, Euclidean,
Cartesian, Projective
Affine Geometry
Affine Transformations
Perspective
Projective Transformations
Matrix Representation of Transformations
Viewing Transformations
204481 Foundation of Computer Graphics April 18, 2020 6
Introduction (1/2)
Points are associated with locations of space
Vectors represent displacements between
points or directions
Points, vectors, and operators that combine
them are the common tools for solving many
geometric problems that arise in Geometric
Modeling, Computer Graphics, Animation,
Visualization, and Computational Geometry.
204481 Foundation of Computer Graphics April 18, 2020 7
Introduction (2/2)
The three most fundamental operators on
vectors are the dot product, the cross
product, and the mixed product (sometimes
called the triple product).
Although a point and a vector may be
represented by its three coordinates, they are
of different type and should not be mixed
Avoid, whenever possible, using coordinates
when formulating geometric constructions.
Instead use vectors and points.
204481 Foundation of Computer Graphics April 18, 2020 8
What will you learn here? (1/2)
Properties of dot, cross, and mixed products
How to write simple tests for
4-points and 2-lines coplanarity
Intersection of two coplanar edges
Parallelism of two edges or of two lines
Clockwise orientation of a triangle from a
viewpoint
Positive orientation of a tetrahedron
Edge/triangle and ray/triangle intersection
204481 Foundation of Computer Graphics April 18, 2020 9
What will you learn here? (2/2)
How to compute
Center of mass of a triangle
Volume of a tetrahedron
“Shadow” (orthogonal projection) of a vector
on a plane
Line/plane intersection
Plane/plane intersection
Plane/plane/plane intersection
204481 Foundation of Computer Graphics April 18, 2020 10
Terminology
Orthogonal to = Normal to = forms a 90o angle
with
Norm of a vector = length of the vector
Are coplanar = there is a plane containing them
204481 Foundation of Computer Graphics April 18, 2020 11
Notation
means “is always equal to” or “by definition”
== means the test “is equal to” used in Boolean expressions
:= is the assignment “is computed as” and is used in construction
algorithms
s (italic type) Boolean
v (normal type) scalar
a (bold type lower-case) point
A (bold upper-case) pointset (edge, curve, triangle, surface, solid)
U (bold underscored upper-case) vector
u (bold underscored lower-case) unit vector
T (bold upper-case) transformation
204481 Foundation of Computer Graphics April 18, 2020 12
Scalars
Need three basic elements in geometry
Scalars, Vectors, Points
Scalars can be defined as members of sets
which can be combined by two operations
(addition and multiplication) obeying some
fundamental axioms (associativity,
commutivity, inverses)
Examples include the real and complex
number systems under the ordinary rules with
which we are familiar
Scalars alone have no geometric properties
204481 Foundation of Computer Graphics April 18, 2020 13
Vectors And Point
We commonly use vectors to represent:
Points in space (i.e., location)
Displacements from point to point
Direction (i.e., orientation)
But we want points and directions to behave
differently
Ex: To translate something means to move it without
changing its orientation
Translation of a point = different point
Translation of a direction = same direction
204481 Foundation of Computer Graphics April 18, 2020 14
Vectors
Physical definition: a vector is a quantity with
two attributes
Direction
Magnitude
Examples include
Force
Velocity
Directed line segments
Most important example for graphics
v
Can map to other types
204481 Foundation of Computer Graphics April 18, 2020 15
Vector Operations
Every vector has an inverse
Same magnitude but points in opposite
direction
Every vector can be multiplied by a scalar
There is a zero vector
Zero magnitude, undefined orientation
The sum of any two vectors is a vector
Use head-to-tail axiom
v w
v -v v
u
204481 Foundation of Computer Graphics April 18, 2020 16
Vectors Lack Position
These vectors are identical
Same length and magnitude
Vectors spaces insufficient for geometry
Need points
204481 Foundation of Computer Graphics April 18, 2020 17
Vectors (1/2)
Vector space (analytic definition from Descartes in the
1600s)
U+V=V+U (vector addition)
U+(V+W)=(U+V)+W
0 is the zero (or null) vector if V, 0+V=V
–V is the inverse of V, so that the vector subtraction
V–V= 0
s(U+V)=sU+sV (scalar multiplication)
U/s is the scalar division (same as multiplication by
s–1)
(a+b)V=aV+bV
204481 Foundation of Computer Graphics April 18, 2020 18
Vectors (2/2)
Vectors are used to represent displacement
between points
Each vector V has a norm (length) denoted ||V||
V / ||V|| is the unit vector (length 1) of V. We denote
it Vu
If ||V||==0, then V is the null vector 0
Unit vectors are used to represent
Basis vectors of a coordinate system
Directions of tangents or normals in definitions of
lines or planes
204481 Foundation of Computer Graphics April 18, 2020 19
Vector Spaces
A linear combination of vectors results in a new
vector:
v = 1v1 + 2v2 + … + nvn
If the only set of scalars such that
1v1 + 2v2 + … + nvn = 0
is 1 = 2 = … = 3 = 0
then we say the vectors are linearly independent
The dimension of a space is the greatest number of
linearly independent vectors possible in a vector set
For a vector space of dimension n, any set of n linearly
independent vectors form a basis
204481 Foundation of Computer Graphics April 18, 2020 20
Vector Spaces: An Example
Our common notion of vectors in a 2D plane
is (you guessed it) a vector space:
Vectors are “arrows” rooted at the origin
Scalar multiplication “streches” the arrow,
changing its length (magnitude) but not its direction
Addition uses the “trapezoid rule”:
u+v
y
v
u
x
204481 Foundation of Computer Graphics April 18, 2020 21
Vector Spaces: Basis Vectors
Given a basis for a vector space:
Each vector in the space is a unique linear
combination of the basis vectors
The coordinates of a vector are the scalars from this
linear combination
Best-known example: Cartesian coordinates
Draw example on the board
Note that a given vector v will have different
coordinates for different bases
204481 Foundation of Computer Graphics April 18, 2020 22
Points
Location in space
Operations allowed between points and vectors
Point-point subtraction yields a vector
Equivalent to point-vector addition
v=P-Q
P=v+Q
204481 Foundation of Computer Graphics April 18, 2020 23
Affine Spaces
Point + a vector space
Operations
Vector-vector addition
Scalar-vector multiplication
Point-vector addition
Scalar-scalar operations
For any point define
1 • P = P
0 • P = 0 (zero vector)
204481 Foundation of Computer Graphics April 18, 2020 24
Affine Space (1/2)
Definition: Set of Vectors V and a Set of Points
P
Vectors V form a vector space.
Points can be combined with vectors to make
new points:
P +v =Q with P,Q P and v V
Dimension: The dimension of an affine space is
the same as that of V .
204481 Foundation of Computer Graphics April 18, 2020 25
Affine Space (2/2)
Note:
All other point operations are just variations
on the
P + v operation.
No distinguished origin
No notion of distances or angles.
Most of what we do in graphics is affine.
204481 Foundation of Computer Graphics April 18, 2020 26
Affine space
Defined together with a vector space and the
point difference mapping
V=b–a (vector V is the displacement from point
a to point b)
Notation: ab stands for the vector b – a
c– a = (c – b) + (b – a). Written ac = ab + bc
Point b is uniquely defined, given point a and
vector (b – a)
204481 Foundation of Computer Graphics April 18, 2020 27
Affine space
If we pick a as origin, then there is a 1-to-1 mapping
between a point b and the vector b –a.
We may extend the vector operations to points, but
usually only when the result is independent of the
choice of the origin!
A + b is not allowed (the result depends on the
origin)
(a + b)/2 is OK
Points may be used to represent
The vertices of a triangle or polyhedron
The origin of a coordinate system
Points in the definition of lines or plane
204481 Foundation of Computer Graphics April 18, 2020 28
Lines
Consider all points of the form
P()=P0 + d
Set of all points that pass through P0 in the direction
of the vector d
204481 Foundation of Computer Graphics April 18, 2020 29
Parametric Form
This form is known as the parametric form of the
line
More robust and general than other forms
Extends to curves and surfaces
Two-dimensional forms
Explicit: y = mx +h
Implicit: ax + by +c =0
Parametric:
x() = x0 + (1-)x1
y() = y0 + (1-)y1
204481 Foundation of Computer Graphics April 18, 2020 30
Rays and Line Segments
If >= 0, then P() is the ray leaving P0 in the
direction d
If we use two points to define v, then
P( ) = Q + (R-Q)=Q+v
=R + (1-)Q
For 0<=<=1 we get all the
points on the line segment
joining R and Q
204481 Foundation of Computer Graphics April 18, 2020 31
Convexity
An object is convex iff for any two points in the
object all points on the line segment between
these points are also in the object
P
P
Q Q
not convex
convex
204481 Foundation of Computer Graphics April 18, 2020 32
Affine Sums
Consider the “sum”
P=1P1+2P2+…..+nPn
Can show by induction that this sum makes
sense iff
1+2+…..n=1
in which case we have the affine sum of the
points P1,P2,…..Pn
If, in addition, i>=0, we have the convex hull of
P1,P2,…..Pn
204481 Foundation of Computer Graphics April 18, 2020 33
Convex Hull
Smallest convex object containing P1,P2,…..Pn
Formed by “shrink wrapping” points
204481 Foundation of Computer Graphics April 18, 2020 34
Curves and Surfaces
Curves are one parameter entities of the form
P() where the function is nonlinear
Surfaces are formed from two-parameter
functions P(, b)
Linear functions give planes and polygons
P() P(, b)
204481 Foundation of Computer Graphics April 18, 2020 35
Planes
A plane be determined by a point and two
vectors or by three points
P(,b)=R+u+bv P(,b)=R+(Q-R)+b(P-Q)
204481 Foundation of Computer Graphics April 18, 2020 36
Triangles
convex sum of S() and R
convex sum of P and Q
for 0<=,b<=1, we get all points in triangle
204481 Foundation of Computer Graphics April 18, 2020 37
Normals
Every plane has a vector n normal (perpendicular,
orthogonal) to it
From point-two vector form P(,b)=R+u+bv, we know
we can use the cross product to find n = u v and
the equivalent form
(P()-P) n=0
u
P
204481 Foundation of Computer Graphics April 18, 2020 38
Dot Product (1/2)
UV denotes the dot product (also called the
inner product)
UV = ||U||||V||cos(angle(U,V))
UV is a scalar.
UV==0 ( U==0 or V==0 or (U and V are
orthogonal))
v
cos(angle(u,v)) u
VU = UV > 0 here VU = UV < 0 here
204481 Foundation of Computer Graphics April 18, 2020 39
Dot Product (2/2)
UV is positive if the angle between U and V is
less than 90o
Note that UV = VU, because: cos(a)=cos(–a).
uv = cos(angle(u,v) # unit vectors: ||u|| 1
the dot product of two unit vectors is the cosine of
their angle
Vu = length of the orthogonal projection of V
onto the direction of u
||U||= sqrt(UU) = length of U = norm of U
204481 Foundation of Computer Graphics April 18, 2020 40
Dot Product
The dot product or, more generally, inner
product of two vectors is a scalar:
v1 • v2 = x1x2 + y1y2 + z1z2 (in 3D)
Useful for many purposes
Computing the length of a vector: length(v) = sqrt(v • v)
Normalizing a vector, making it unit-length
Computing the angle between two vectors:
u • v = |u| |v| cos(θ)
Checking two vectors for orthogonality
Projecting one vector onto another v
θ
u
204481 Foundation of Computer Graphics April 18, 2020 41
Computing the reflection vector
Given the unit normal n to a mirror surface and
the unit direction l towards the light, compute
the direction r of the reflected light.
By symmetry, l+r is parallel to n and
has a norm that is twice the length of
the projection nl of l upon n. Hence:
r = 2(nl)n–l
n –l
l r
l r
204481 Foundation of Computer Graphics April 18, 2020 42
Computing a “shadow” vector (projection)
Given the unit up-vector u and the unit
direction d, compute the shadow T of d onto
the floor (orthogonal to u).
T and u are orthogonal.
u
d is the vector sum T+ (du)u . d
Hence:
T = d – (du)u T
204481 Foundation of Computer Graphics April 18, 2020 43
Cross product (1/3)
UV denotes the cross product
UV is either 0 or a vector orthogonal to both U
and V
When U==0 or V==0 or U//V (parallel) then
UV= 0
Otherwise, UV is orthogonal to both U and V
204481 Foundation of Computer Graphics April 18, 2020 44
Cross product (2/3)
The direction of UV is defined by the thumb of
the right hand
Curling the fingers from U to V
Or standing parallel to U and looking at V, UV goes
left
||UV|| ||U||||V||sin(angle(U,V))
sin(angle(u,v)2 1–(uv)2 # unit vectors
(uv== 0) u//v (parallel)
UV –VU
Useful identity: U(VW) (UW)V – (UV)W
204481 Foundation of Computer Graphics April 18, 2020 45
Cross Product (3/3)
The cross product or vector product of two
vectors is a vector:
y1 z 2 y 2 z1
v1 v 2 ( x1 z 2 x 2 z1)
x1 y 2 x 2 y1
The cross product of two vectors is orthogonal
to both
Right-hand rule dictates direction of cross
product
204481 Foundation of Computer Graphics April 18, 2020 46
When are two edges parallel in 3D?
Edge(a,b) is parallel to Edge(c,d) if abcd == 0
204481 Foundation of Computer Graphics April 18, 2020 47
Mixed product
U(VW) is called a mixed product
U(VW) is a scalar
U(VW) ==0 when one of the vectors is null or all 3
are coplanar
U(VW) is the determinant | U V W |
U(VW) V(WU) – U(WV) # cyclic
permutation
204481 Foundation of Computer Graphics April 18, 2020 48
Testing whether a triangle is front-facing
When does the triangle a, b, c appear
clockwise from d?
when da(dbdc) > 0
c
a
204481 Foundation of Computer Graphics April 18, 2020 49
Volume of a tetrahedron
Volume of a tetrahedron with vertices a, b, c and d is
v | da(dbdc) | / 6
a
dbdc da
c
dc
d db b
204481 Foundation of Computer Graphics April 18, 2020 50
z, s, and v functions (1/2)
zero: z(a,b,c,d) da(dbdc)==0 # tests co-planarity of 4 points
Returns Boolean TRUE when a,b,c,d are coplanar
sign: s(a,b,c,d) da(dbdc)>0 # test orientation or side
Returns Boolean TRUE when a,b,c appear clockwise from d
Used to test whether d in on the “good” side of plane through a,b,c
a
a
dbdc da
d
c
dc
b
c d b
db
204481 Foundation of Computer Graphics April 18, 2020 51
z, s, and v functions (2/2)
value: v(a,b,c,d) da(dbdc) # compute volume
Returns scalar whose absolute value is 6 times the volume of
tetrahedron a,b,c,d
v(a,b,c,d) v(d,a,b,c) –v(b,a,c,d)
204481 Foundation of Computer Graphics April 18, 2020 52
Testing whether an edge is concave
How to test whether the edge (c,b) shared by triangles
(a,b,c) and (c,b,d) is concave?
204481 Foundation of Computer Graphics April 18, 2020 53
When do two edges intersect in 2D?
Write a geometric expression that returns true when
two coplanar edges (a,b) and (c,d) intersect
0 (abac)•(abad) and 0 (cdca)•(cdcb)
d
d
a b
c b
a
c
204481 Foundation of Computer Graphics April 18, 2020 54
When do two edges intersect in 3D?
Consider two edges: edge(a,b) and edge(c,d)
When are they co-planar? When z(a,b,c,d)
When do they intersect?
When they are co-planar and
0 (abac)•(abad) and 0 (cdca)•(cdcb)
d d
q
a b a b
p
c c
204481 Foundation of Computer Graphics April 18, 2020 55
What is the common normal to 2 edges in 3D?
Consider two edges: edge(a,b) and edge(c,d)
What is their common normal n? n=(abcd)u
n
a b
204481 Foundation of Computer Graphics April 18, 2020 56
When is a point inside a tetrahedron?
When does point p lie inside tetrahedron a, b, c, d ?
Assume z(a,b,c,d) is FALSE (not coplanar)
When
s(a,b,c,d), d
s(p,b,c,d),
s(a,p,c,d), p
s(a,b,p,d), and c
s(a,b,c,p)
(i.e. all return TRUE or all a b
are identical. return FALSE)
When is p on the boundary of the tetrahedron?
Do as an exercise for practice.
204481 Foundation of Computer Graphics April 18, 2020 57
A faster point-in-tetrahedron test ?
Suggested by Nguyen Truong
Write ap = sab+tac+uad
Solve for s, t, u (linear system of 3 equations)
Requires 17 multiplications, 3 divisions, and 11 additions
Check that s, t, and u are positive and that s+u+t<1
A more expensive Variation:
d
Compute s, t, u, w
w = v(a,b,c,d)
s = v(a,p,c,d)
p
u = v(a,b,p,d) c
t = v(a,b,c,p)
Check that a b
w, s, t, u have the same sign and that s+u+t<w
204481 Foundation of Computer Graphics April 18, 2020 58
When is a 3D point inside a triangle
When does point p lie inside triangle with vertices a, b, c ?
When z(p,a,b,c) and (abap)•(bcbp)0 and (bcbp)•(cacp)0
a
p p
204481 Foundation of Computer Graphics April 18, 2020 59
Parametric representation of a line
Let Line(p,t) be the line through
point p with tangent t
Its parametric form associates a
scalar s with a point q(s) on the p
line
t
• s defines the distance from p
to q(s) s
• q(s) = p + st
Note that the direction of t q
gives an orientation to the line
(direction where s is positive)
We can represent a line by p and t
204481 Foundation of Computer Graphics April 18, 2020 60
Implicit representation of a plane
Let Plane(r,n) be the plane through point r with normal n
Its implicit form states that a point q lies on Plane(r,n) when
rqn=0
Remember that rq = q – r
Note that the direction of n defines an orientation of the plane
p
p not in plane
n n
q r
r
204481 Foundation of Computer Graphics April 18, 2020 61
Line/plane intersection
Compute the point q of intersection between Line(p,t) and
Plane(r,n)
Replacing q by p+st in (q–r)n=0 yields p
(p–r+st)n=0
Solving for s yields t
rpn+stn=0 and s
s = – rpn / tn n
s = prn / tn q r
Hence q = p + (prn)t / (tn)
204481 Foundation of Computer Graphics April 18, 2020 62
When are two lines coplanar in 3D?
L(p,t) and L(q,u) are coplanar
When tu == 0 OR pq•(tu) == 0
204481 Foundation of Computer Graphics April 18, 2020 63
What is the intersection of two planes
Consider two planes Plane(p,n) and Plane(q,m)
Assume that n and m are not parallel (i.e. nm ≠ 0)
Their intersection is a line Line(r,t). m
How can one compute r and t ?
q
t := (nm)u
let u := nt
r := p+(pq•m)u/(u•m) t n
r u p
If correct, then provide the derivation.
Otherwise, provided the correct answer.
204481 Foundation of Computer Graphics April 18, 2020 64
What is the intersection of three planes
Consider planes Plane(p,m), Plane(q,n), and
Plane(r,m).
How do you compute their intersection w ?
r
Write w=p+an+bm+ct then
solve the linear system t
{pw•n=0, qw•m=0, rw•t=0}
for a, b, and c q m w
n
or compute the line of
intersection between two of p
these planes and then intersect
it with the third one.
204481 Foundation of Computer Graphics April 18, 2020 65
Implementation
Points and vectors are each represented by their 3
coordinates
p=(px,py,pz) and v=(vx,vy,vz)
U•V = UxVx + UyVy + UzVz
UV = (UyVz – UzVy) – (UxVz – UzVx) + (UxVy – UyVx)
Implement:
Points and vectors
Dot, cross, and mixed products
z, s, and v functions from mixed products
Edge/triangle intersection
Lines and Planes
Line/Plane, Plane/Plane, and Plane/Plane/Plane intersections
Return exception for singular cases (parallelism…)
204481 Foundation of Computer Graphics April 18, 2020 66
Linear Transformations
A linear transformation:
Maps one vector to another
Preserves linear combinations
Thus behavior of linear transformation is
completely determined by what it does to a
basis
Turns out any linear transform can be
represented by a matrix
204481 Foundation of Computer Graphics April 18, 2020 67
Matrices
By convention, matrix element Mrc is located
at row r and column c:
M11 M12 M1n
M21 M22 M2n
M
Mm1 Mm2 Mmn
By (OpenGL) convention, v1
vectors are columns:
v v 2
v 3
204481 Foundation of Computer Graphics April 18, 2020 68
Matrices
Matrix-vector multiplication applies a linear
transformation to a vector:
M11 M12 M13 vx
M v M 21 M 22 M 23 vy
M 31 M 32 M 33 vz
Recall how to do matrix multiplication
204481 Foundation of Computer Graphics April 18, 2020 69
Matrix Transformations
A sequence or composition of linear
transformations corresponds to the product of
the corresponding matrices
Note: the matrices to the right affect vector first
Note: order of matrices matters!
The identity matrix I has no effect in
multiplication
Some (not all) matrices have an inverse:
M 1 Mv v
204481 Foundation of Computer Graphics April 18, 2020 70
Source :
Pradondet Nilagupta
Dept. of Computer Engineering
Kasetsart University
204481 Foundation of Computer Graphics April 18, 2020 71
Pertanyaan untuk Mahasiswa (3)
Masing-masing mahasiswa harus menjawab / memberi komentar terhadap minimal 1
pertanyaan di bawah ini di kolom komentar :
1. Jelaskan mengenai Geometric Spaces pada Komputer Grafik ?
2. Jelaskan mengenai konsep “mixed Product” pada Komputer Grafik ?
3. Jelaskan dalam Bahasa Indonesia penjelasan pada Slide No.14 ?
4. Jelaskan mengenai konsep “convexity” pada Komputer Grafik ?
5. Jelaskan dalam Bahasa Indonesia penjelasan dan gambar pada Slide No.21?
6. Jelaskan mengenai perbedaan konsep “perpotongan 2 garis pada 2
Dimensi dan ruang 3 Dimensi” pada Komputer Grafik
7. Jelaskan dalam Bahasa Indonesia penjelasan dan gambar pada Slide No.50?
8. Jelaskan dalam Bahasa Indonesia penjelasan pada Slide No.70?
Kesemua 8 pertanyaan ini harus dibahas oleh semua anggota kelas, maka 7 mahasiswa terakhir
yang akan jawaban pertanyaan harus menjawab topik-topik yang belum pernah terbahas ??
Setelah itu yang lain boleh beri komentar / koreksian atas jawaban temannya ? Nilai keaktifan !!
204481 Foundation of Computer Graphics April 18, 2020 72