Math Basics

There are a few basic math concepts used over and over again in computer graphics.

No attempt has been made to order these topics by presentation date (Under Construction).

Camera
Coherence and Incremental Algorithms
Cross Product
Coordinate Systems
Homogeneous Coordinates
Inner Product
Linear Interpolation
Matrices
Parametric Line Equation
Polygons

Convex
Concave

Projections
Spaces

Object Space
World Space
Image Space

Transformations
Triage
Vectors (a good review of terminology used in this class)

Vectors

For a reasonable tutorial on vectors try http://chortle.ccsu.edu/VectorLessons/vectorIndex.html or another in pdf form at allVectorChapters.pdf.

Transformations

Coordinate Systems

Parametric Line Equation

Example use(s): A way to think about lines that enables us to calculate the projection of a point easily.

Given a line segment from v₁ (x₁, y₁) to v₂ (x₂, y₂), how is the midpoint expressed?
x = 1/2 (x₁ + x₂) = 1/2x₁ + 1/2x₂
y = 1/2 (y₁ + y₂) = 1/2y₁ + 1/2y₂
Three-fourths of the way?
x = = 1/4x₁ + 3/4x₂
y = = 1/4y₁ + 3/4y₂
More generally, for a parameter t (e.g.,time)
x = (1 - t) x₁ + tx₂
y = (1 - t) y₁ + ty₂
By varying "t", you can make (x, y) equal to any point on the line. It is easy to see that if t = 1, the parametric representation gives (x, y) = (x₂, y₂). If t = 0, the parametric representation gives (x, y) = (x₁, y₁). Thus we have verified that the line passes through the necessary two points.
v_t = (1 - t)v₁ + tv₂ is called a convex linear combination of v₁ and v₂ or a linearly weighted sum.

Advantage of Parametric vs. Explicit Line Definition

Explicit line definition:

y = mx + b, m = dx/dy;

how best to deal with vertical slope?
or finite lines (line segments)?

Parametric line definition:

x = (1 - t) x1 + tx2,
y = (1 - t) y1 + ty2, t in [0, 1]

For vertical slope
when t = 0, x = x1, y = y1
and t = 1, x = x2, y = y2

Restricted range of t defines a segment, not a whole line:
t < 0, (x, y) lies "before" it
t > 0, (x, y) lies "after" it

Inner Products

Example use(s):To determine if a polygon face is a front or back face and used to calculate scene lighting.

The inner, or dot, or scalar product of two vectors is a number. It can represent a length or the scaled cosine of the angle between two vectors. We are mostly interested in vectors of length three (3) or four (4). The inner product of vectors $\vec{v}$ and $\vec{w}$ is written as

$\begin{displaymath}\langle \vec{v} \vert \vec{w}\rangle=\sum_{i=0}^{n}v_iw_i.\end{displaymath}$

It is also useful to represent the inner product in matrix form

$\begin{displaymath}\langle \vec{v} \vert \vec{w}\rangle = v^T w = (v_0,\ldots,v_... ...}w_0\\ \vdots\\ w_n\\ \end{array}\right)= \sum_{i=0}^{n}v_iw_i.\end{displaymath}$

Matrices

Example use(s): Matrices are used to transform points from one coordinate system to another.

Matrices can be thought of as collections of vectors. Most of our matrices will be $4\times 4$ and are written as

$\begin{displaymath}M=\left(\begin{array}{cccc} a_{00} & a_{01} & a_{02} & a_{0... ...\\ a_{30} & a_{31} & a_{32} & a_{33} \\ \end{array}\right).\end{displaymath}$

Cross Products

Example use(s): The cross product of two incident vectors of a polygon define the normal to the polygon.

The cross product of two three dimensional vectors is another vector. The cross product vector is perpendicular to the other two vectors. Let $\vec{v}$ and $\vec{w}$ be two three dimensional vectors. Their cross product is

$\begin{displaymath}\vec{v} \times \vec{w} = (v_1w_2 - v_2w_1,\, v_2w_0 - v_0w_2,\, v_0w_1-v_1w_0).\end{displaymath}$

Polygons

Example use(s): Three dimensional objects are constructed from polygons.

Polygons are figures enclosed by contiguous line segments that connect points or vertices or corners of the polygon. A triangle is the simplest polygon, squares and rectangles are also simple. Polygons can become complex.

We'll need to make some restrictions on what types of polygons to allow in a graphics system - typically convex as these are easiest to render while concave polygons must be converted to convex before rendering.

Convex and Concave Polygons

Convex and concave polygons are mutually exclusive polygon types that span the whole set of polygons.

Convex Polygon

A polygon is defined to be convex if for any two points that lie within the polygon, the line segment connecting them is also inside the polygon.

Concave Polygon

For simplicity, let us define a concave polygon to be any polygon that is not convex. As can be seen below, line segments that are drawn between two points lying inside the polygons, do not always lie inside the polygon. Thus, the polygons are classified as concave polygons.

If you are a glutton for punishment or just "love" polygons try http://mathworld.wolfram.com/Polygon.html or http://www.cs.rit.edu/~icss571/filling/what_is_poly.html

Homogeneous Coordinates

Example use(s): Homogeneous coordinates are used when performing transformations, that is scaling, rotation and translation. This allows any sequence of transformations to be represented in a single $4\times 4$ matrix.

Homogeneous coordinates are formed by appending an extra coordinate with the value 1. For example, a 3D point with coordinates (x, y, z) is

$\begin{displaymath}(x,\,y,\,z) \rightarrow (x, \, y,\,z,\,1).\end{displaymath}$

More generally, we can multiply the homogeneous point by a parameter w as long as it is not zero.

$\begin{displaymath}(x,\,y,\,z) \rightarrow (wx, \, wy,\,wz,\,w),\,w\neq 0.\end{displaymath}$

Coherence and Incremental Algorithms

Example use(s): Hardware algorithms for drawing lines and circles use coherence for fast incremental rendering.

``Things close by in time or space are frequently similar.''

This concept applies in many areas of computer science, certainly not just in graphics. Incremental algorithms follow from noticing coherent patterns. They are distinguished by the use of one (or more) old values to generate a new value. For example, if you know $(x',\,y')$ is a point on a line y=mx+b and x' is incremented by 1, then we can compute a new y by simply adding the slope m, that is

(x'+1, y'+m)

is on the line.

Linear Interpolation

Example use(s): Linear interpolation is the basis for many incremental algorithms such as key frame animation.

When a value y changes via a linear formula: y=mx+b, a change in x by an amount $\triangle x$ , results in a new value of y that is produced by adding increment $m\triangle x$ to y. Another example is to think about linear interpolation using the parametric line equation (The following is a simple key frame with frames #1 and #2 initially defined. An animation would increment t to produce inbetween frames.).

vt = (1 - t)v1 + tv2
values of t range from 0 to 1
at t = 0, vt = (1 - 0)v1 + (0)v2 = v1
at t = 1, vt = (1 - 1)v1 + (1)v2 = v2
at t = 1/2, vt = (1/2)v1 + (1/2)v2, etc.

Triage

Example use(s): Applied in all real-time interactive computer graphics.

An algorithmic concept that says: ``serve the greatest good.'' Usually, this is interpreted as ``make the common case fast.''

Projection Basics

Camera Basics

The camera is specified by a position (COP - center of projection or VRP - view-reference position) and an orientation. Orientation requires three vectors - y direction or UP vector, z direction, and x direction. These vectors are referred to as the Euler Transform. In OpenGL, by default, the COP is at the origin, the y-axis is up, the negative z-axis is the z direction, and the x-axis is the x direction. So an observer in an OpenGL scene is at the origin looking down the negative z-axis. Note that all we need is the COP and two of the vectors to compute the third - it is normal to the two known vectors. Focal length of the lens gives us the depth of field or how much of the scene is visible while the size of the film plane (w X h) determines the viewport dimensions.

Spaces

The reference frames for image formation.

Object Space

A CG object is defined as an ordered list of vertices. The object is centered at the origin in a local 3D coordinate system - object coordinate system.

World Space

An application determines where an object and a camera are placed in a scene. Transforming object space (placing objects and camera) results in world space.

Image or Screen Space

Transforming world space into 2D results in image space.

Thanks to the following computer graphics course web sites:

"http://www.cs.fit.edu/~wds/classes/graphics/Basics/basics/basics.html"
"http://www.cs.brown.edu/stc/summer/"
"http://www.cc.gatech.edu/gvu/multimedia/nsfmmedia/graphics/"
"http://chortle.ccsu.edu/VectorLessons/vectorIndex.html"