Transcript Computer Graphics: Programming, Problem Solving, and Visual

Computer Graphics:
Programming, Problem Solving,
and Visual Communication
Steve Cunningham
California State University Stanislaus and Grinnell College
PowerPoint Instructor’s Resource
Mathematics for Modeling
Some mathematics tools to help
you develop your graphics
programs
Mathematics is an Important
Tool for Computer Graphics
• In this chapter we survey a number of
topics that are each helpful in one or
more places in graphics
• The presentation here may not be as
deep as you would like, but you can
consult mathematics textbooks for more
• The order is generally simpler to more
complex, but is not systematic
What Is a 2D or 3D Space?
• We use 2D and 3D Euclidean space
• Our points are (x,y) or (x,y,z)
• They correspond to points in 2D or 3D
space with X-Y or X-Y-Z coordinates
• We generally use right-hand coordinates
(right) rather than left-hand ones (left)
Points
• Geometrically, a point is a position in
space
• Algebraically, the point is defined by its
coordinates (x,y) or (x,y,z)
• We will usually see points as vertices in
a geometric object
• However, a triple (x,y,z) or a quadruple
(x,y,z,w) will sometimes have another
meaning, such as a color
Lines
• Lines are one-dimensional objects that
are associated with a point and a
direction vector
• The line through a given point P0 in a
given direction contains all points P so
that the direction from P to P0 is a scalar
multiple of the direction vector
• If you have two points, the vector from
one to the other can be the line’s vector
Lines (2)
• If you have two points P0 and P1, the line
containing them can be expressed by
P  P0  t P1  P0   (1 t)P0  tP1
for all possible real values of t; this is
called the parameter for the line
• This equation is about points, but you
can easily turn this into equations about
each component separately
Rays
• A ray is defined very much like a line, but
only points that lie in the same direction
as the line’s vector are included.
• This is given by the equation of the line
except that we only allow values of the
parameter t ≥ 0.
Line Segments
• A line segment is a portion of a line that
is given by parameters t in [0,1]
• With the two-point approach, the line
segment contains all the points between
P0 and P1
• When you define two adjacent vertices
of a graphics object, the edge between
them is a line segment
Line Segments (2)
• Often the parameter for a line segment
will be very important, so we need to
understand how parameters match their
corresponding points
Parametric Curves
• A parametric curve is defined by three
functions of one parameter x(t), y(t), z(t)
• For any value of t, the point (x(t), y(t), z(t))
is on the curve
• We will see a number of parametric
curves in our work
• The parameter is often limited to [0,1]
Parametric Surfaces
• A parametric surface is defined by three
functions of two parameters
x(s,t), y(s,t), z(s,t)
• For any values of the parameters (s, t),
the point (x(s,t),y(s,t),z(s,t)) is on the curve
• We will see even more parametric
surfaces in our work
• The parameters are often limited to [0,1]
Vectors
• Vectors are much like points and are
given by tuples of real numbers <x,y,z>
• Geometrically, vectors represent
directions rather than positions
• Vectors have length, given by
a,b,c 
a
2
 b2  c 2 
• A unit vector has length 1

Vector Operations
• Vectors have four primary operations
– Addition (componentwise)
a,b,c  x, y,z  a  x,b  y,c  z
– Scalar multiplication
c  x, y,z  c  x,c  y,c  z
 – Dot product
– Cross product

Dot Product
• This operation • takes two vectors and
returns a scalar
• Operates by adding the componentwise
products
a,b,c  x, y,z  ax  by  cz
• There are geometric meanings to the dot
product

Dot Product (2)
• Geometrically, the dot product depends
on the angle between the vectors
– For any two vectors A and B, if theta is the
angle between the vectors,
A  B  A  B  cos
– If two vectors have a dot product of zero,
they are orthogonal (perpendicular to each
 other)
Dot Product (3)
• The dot product is very helpful when
you consider the relationship between
two vectors
• The length of the projection of a vector
U onto a vector V is given by
U V / V
Cross Product
• The cross product of two vectors yields
another vector
• This vector is perpendicular to both of the
original vectors
• The computation is given by a
determinant calculation, but more simply:
a,b,c  u,v,w  bw  cv,cu  aw,av  bu
Cross Product (2)
• Cross products are not commutative:
U V  V U
• Cross products are very handy when
you want to compute
 a vector normal to
two given vectors
(e.g. vertex normals)
Reflection Vectors
• If you have a normal vector
at a point and an incoming
vector (e.g. a light vector),
you may need to compute
the reflection of the
incoming vector
• This is given by
Q  P – 2N  PN
Transformations
• When we talked about modeling
transformations, we focused on what
they do rather than on how they are done
• If we talk about the mathematics,
however, we must talk about how they
work
Transformations (2)
• Transformations include scaling,
translation, rotation
• Geometry is processed as 4-tuples
(x,y,z,w) and all transformations are
linear
• Thus transformations act as 4x4
matrices
Transformations (3)
• Scaling x  x  sx
matrix
y  y  sy
z  z  sz
• Translation x  x  tx matrix

y  y  ty


z  z  tz


sx

0
0

0
1

0
0

0
0
sy
0
0
0

0 0
sz 0

0 1
0
0 0 tx 

1 0 ty 
0 1 tz 

0 0 1 
Transformations (4)
• Rotations are more complex, and we
usually think of them only in terms of
rotations around coordinate axes
• For the 2D case:
the x-axis rotation R
cos – sin
R  

sin cos 
Transformations (5)
• Rotations by  around each axis:
around X
around Y
around Z
cos – sin

sin cos
 0
0

0
 0


0 0

0 0
1 0

0 1
 cos

 0
– sin

 0
0 sin 0

1
0
0
0 cos 0

0
0
1
1
0
0

0 cos – sin
0 sin cos

0
0
0
• The Y case is different because of the
axis order

0

0
0

1
Planes
• A plane can be defined several ways
– A plane is determined by three points
– Given a point P and a line L through P, a
plane is the set of points X so that the line
XP is perpendicular to L
• These are the same: the three points
determine two lines, and the cross
product of the lines determines the
normal line
Planes (2)
• Equation of a plane can be derived from
the second definition
A,B,C (x  x0, y  y0,z  z0 )  0
• Or, working through this equation and
collecting terms, we end up with

Ax  By  Cz  D  0
• Here the coefficients A, B, C are the
components of the normal vector

Convex Polygons
• A polygon is complex if for any two
points A and B in the polygon, the line
between them is all in the polygon
• Alternately, a convex polygon is the
convex sum of its vertices, or
P
 V
i i
vertices
for all points P in the polygon, where all
values of  are in [0,1]

Convex Polygons (2)
• One convex polygon (left) and two that
are not convex (middle and right)
Polar and Cylindrical
Coordinates
• You can identify points in the plane by
rectangular coordinates (x,y) or by angle
and distance (r,)
• This can be extended to 3D by adding
the z coordinate
Spherical Coordinates
• Use latitude and longitude along with
distance
• Similar to identifying points in space by
projecting them from the earth
Triangle-Based Collision
Detection
• With objects built from triangles, to test
for collisions you need only test for
spherical and triangle collisions