Sunday, May 29, 2011

Points, Vertices and Vectors

This post covers some facts about Points, Vertices and Vectors that might be useful. This is a collection of ideas to create a short math primer for engineers that want to explore computer graphics. The resulting material will be used in future computer graphics classes. Your feedback is highly welcome!

Points
A 3D point is a location in space, in a 3D coordinate system. We can find a point P with coordinates [Px, Py, Pz] by starting from the origin at [0, 0, 0] and moving the distance Px, Py and Pz along the x, y and z axis.

Two points define a line segment between them, three points define a triangle with corners at those points, and several interconnected triangles can be used to define the surface of an object; sometimes also called mesh.

Points that are used to define geometric entities like triangles, are often called vertices. In graphics programming, vertices are an array of structures or a structure of arrays and not only describe a position but also include other data like for example color, a normal vector or texture coordinates.

The difference of two points is a vector: V = P - Q

Vectors

While a point is a reference to a location, a vector is the difference between two points which describes a direction and a distance -length-, or a displacement.

Like points, vectors can be represented by three coordinates. Those three values are retrieved by subtracting the tail from the vector from its head.

Δx = (xh - xt)
Δy = (yh - yt)
Δz = (zh - zt)

Vector components
Figure 1 - Vector components Δx, Δy and Δz

Two vectors are equal if they have the same values. Thus considering a value as a difference of two points, there are any number of vectors with the same direction and length.



Figure 2 - Instances of one vector

The difference between between points and vectors is reiterated by saying they live in a different space, the Euclidean space and the vector space . Read more in [Farin].

The primary reason for differentiating between points and vectors is to achieve geometric constructions which are coordinate independent. Such constructions are manipulations applied to objects that produce the same result regardless of the location of the coordinate origin.



Scalar Multiplication, Addition and Subtraction of Vectors

A vector V can be multiplied by a scalar. Multiplying by 2 doubles the vectors components.





Similarly dividing the vector by 2 halves its components. The direction of the vector remains unchanged, only its magnitude changes.

The result of adding two vectors V and W can be obtained geometrically.


Figure 3 - Adding two vectors

Placing the tail of w to the head of V leads to the resulting vector, going from V's tail to W's head. In a similar manner vector subtraction can visualized.



Figure 4 - Subtracting two vectors

Similar to addition, the tail of the vector that should be subtracted -W- is placed to the head of V. Then the vector that should be subtracted is negated. The resulting vector runs from V's tail to W's head.

Alternatively, by the parallelogram law, the vector sum can be seen as the diagonal of the parallelogram formed by the two vectors.


Figure 5 - Parallelogram rule

The vectors V - W and V + W are the diagonals of the parallelogram defined by V and W. Arithmetically, vectors are added or subtracted by adding or subtracting the components of each vector.

All the vector additions and subtractions are coordinate independent operations, since vectors are defined as difference of points.

Homogeneous Coordinates

Representing both points and vectors with three coordinates can be confusing. Homogeneous coordinates are a useful tool to make the distinction explicit. Adding a fourth coordinate, named w, allows us to describe a direction or a vector by setting this coordinate to 0. In all other cases we have a point or location.

Dividing a homogeneous point [Px, Py, Pz, Pw] by the w component leads to the corresponding 3D point. If the w component equals to zero, the point would be infinitely far away, which is then interpreted as a direction. Using any non-zero value for w, will lead to points all corresponding to the same 3D point. For example the point (3, 4, 5) has homogeneous coordinates (6, 8, 10, 2) or (12, 16, 20, 4).

The reason why this coordinate system is called "homogeneous" is because it is possible to transform functions f(x, y, z) into the form f(x/w, y/w, z/w) without disturbing the degree of the curve. This is useful in the field of projective geometry. For example a collection of 2D homogeneous points (x/t, y/t, t) exist on a xy-plane where t is the z-coordinate as illustrated in figure 6.



Figure 6 - 2D homogenous coodinates can be visualized as a plane in 3D space

Figure 6 shows a triangle on the t = 1 plane, and a similar triangle much larger on a distant plane. This creates an arbitrary xy plane in three dimensions. The t- or z-coordinate of the plane is immaterial because the x- and y-coordinates are eventually scaled by t.
Homogeneous coordinates are also used to create a translation transform.

In game development, some math libraries have dedicated point and vector classes. The main distinction is made by setting the fourth channel to zero for vectors and one for points [Eberly].



Pythagorean Theorem

The length or magnitude of a vector can be obtained by applying the Pythagorean Theorem. The opposite -b- and adjacent -a- side of a right-angled triangle represents orthogonal directions. The hypotenuse is the shortest path distance between those.




Figure 7 - Pythagorean Theorem

It helps thinking of the Pythagorean Theorem as a tool to compare "things" moving at right angles. For example if a is 3, b equals 4, then c equals 5 [Azad].

The Pythagorean Theorem can also be applied to right-angled triangles chained together.



Figure 8 - Pythagorean Theorem with two triangles chained together





Replacing with leads to



is now written in three orthogonal components. Instead of lining the triangles flat, we can now tilt the green one a bit and therefore consider an additional dimension.


Figure 9 - Pythagorean Theorem in 3D

Renaming the sides to x, y and z instead of a, b and d we get:



This works with any number of dimensions.

The Pythagorean Theorem is the basis for computing distance between two points. Consider the following two triangles:



Figure 10 - Pythagorean Theorem used for distance calculations

The distance from the tip of the blue triangle at coordinate (4, 3) to the tip of the green triangle at coordinate (8, 5) can be calculated by creating a virtual triangle between those points. Subtracting the points leads to a 2D vector.

Δx = (xhead - xtail)
Δy = (yhead - ytail)



In this case

Δx = 8 - 4 = 4
Δy = 5 - 3 = 2







Extending the idea to three dimensions shows the well-known equation:





Unit Vectors

A unit vector has a length or magnitude of 1. This is a useful property for vector multiplications, because those consider the magnitude of a vector and the computation time can be reduced if this magnitude is one (more on this later). A unit column vector might look like this:



and



Converting a vector into a unit form is called normalizing and is achieved by dividing a vector's components by its magnitude. Its magnitude is retrieved by applying the Pythagorean Theorem.





An example might be:







Cartesian Unit Vectors

Now that we have investigated the scalar multiplication of vectors, vector addition and subtraction and unit vectors, we can combine those to permit the algebraic manipulation of vectors (read more at [Vince][Lengyel]). A tool that helps to achieve this is called Cartesian unit vectors. The three Cartesian unit vectors i, j and k are aligned with the x-, y- and z-axes.



Any vector aligned with the x-, y- and z-axes can be defined by a scalar multiple of the unit vectors i, j and k. For example a vector 15 units long aligned with the y-axis is simply 15j. A vector 25 units long aligned with the z axis is 25k.

By employing the rules of vector addition and subtraction, we can compose a vector R by summing three Cartesian unit vectors as follows.



This is equivalent to writing R as



The magnitude of R would then be computed as



Any pair of Cartesian vectors such as R and S can be combined as follows







An example would be









Vector Multiplication

Vector multiplication provides some powerful ways of computing angles and surface orientations. While the multiplication of two scalars is a familiar operation, the multiplication of vectors is a multiplication of two 3D lines, which is not an easy operation to visualize. In vector analysis, there are generally two ways to multiply vectors: one results in a scalar value and the other one in a vector.

Scalar or Dot Product

Multiplying the magnitude of two vectors |R| and |S| is a valid operation but it ignores the orientation of the vectors, which is one of their important features. Therefore we want to include the angles between the vectors. In case of the scalar product, this is done by projecting one vector onto the other.



Figure 11 - Projecting R on S

The projection of R on S creates the basis for the scalar product, because it takes into account their relative orientation. The length of R on S is



Then we can multiply the projected length of R with the magnitude of S



or commonly written



The symbol is used to represent scalar multiplications and to distinguish it from the vector product, which employs the symbol. Because of this symbol, the scalar product is often referred to as the dot product. This geometric interpretation of the scalar product shows that in case the magnitude of R and S is one -in other words they are unit vectors- the calculation of the scalar product only relies on . The following figure shows a number of dot product scenarios.



Figure 12 - Dot product

The geometric representation of the dot product is useful to imagine how it works but it doesn't map well to computer hardware. The algebraic representation maps better to computer hardware and is calculated with the help of Cartesian components:








There are various dot product terms such as etc. in this equation. With the help of the geometric representation of the dot product it can be determined that terms that are mutually perpendicular like are zero because the cosinus of 90 degrees is zero. This leads to



Finally, terms with two vectors that are parallel to themselve lead to a value of one because the cosinus of a degree of zero is one. Additionally the Cartesian vectors are all unit vectors, which leads to



So we end up with the familiar equation



An example:



The algebraic representation results in:





The geometric representation starts out with:







Solving for the angle between the vectors by plugging in the result of the algebraic representation:







Solving for  leads to the angle between the two vectors:



The resulting angle will be always between  and , because, as the angle between two vectors increases beyond the returned angle is always the smallest angle associated with the geometry.

Scalar Product in Lighting Calculations

Many games utilize the Blinn-Phong lighting model (see Wikipedia; ignore the code on this page). A part of the diffuse component of this lighting model is the Lambert's Law term published in 1760. Lambert stated that the intensity of illumination on a diffuse surface is proportional to the cosine of the angle between the surface normal vector and the light source direction.

Let's assume our light source is located in our reference space for lighting at (20, 30, 40), while our normal vector is normalized and located at (0, 11, 0). The point where the intensity of illumination is measured is located at (0, 10, 0).



Figure 13 - Lighting Calculation

The light and normal vector are calculated by subtracting the position of the point where the intensity is measured -representing their tails- from their heads.













Instead of using the original light vector, the following scalar product normalizes the light vector first, before using it in the lighting equation.





To test if the light vectors magnitude is one:


Plugging the unit light vector and the unit normal vector into the algebraic representation of the scalar product.



Now solving the geometrical representation for the cosine of the angle.





In case the light and the normal vector are unit vectors, the result of the algebraic scalar product calculation equals the cosinus of the angle. The algebraic scalar product is implemented in the dot product intrinsic available for the CPU and GPU. In other words, in case the involved vectors are unit vectors, a processor can calculate the cosine of the angle faster. This is the reason why normalized vectors might be more efficient in programming computer hardware.

Following Lambert's law, the intensity of illumination on a diffuse surface is proportional to the consine of the angle between the surface normal and the light source direction. That means that the point at (0, 10, 0) receives about 0.4082 of the original light intensity at (20, 30, 40) (attenuation is not considered in this example).

Coming back to image 12, in case, the unit light vector would have a y component that is one or minus one and therefore its x and  y component would be zero, it would point in the same or opposite direction as the normal and therefore the last equation would result in one or minus one. If the unit light vector would have a z or x component equaling to one and therefore the other components would be zero, those equations would result in zero.

The Vector Product

Like the scalar product, the vector or cross product depends on the modulus of two vectors and the angle between them, but the result of the vector product is essentially different: it is another vector, at right angles to both the original vectors.



and



For an understanding of the vector product R and S, it helps to imagine a plane through those two vectors as shown in figure 14.




Figure 14 - Vector Product

The angle between the directions of the vectors suffices . There are two possible choices for the direction of the vector, each the negation of the other; the one chosen here is determined by the right-hand rule. Hold your right hand so that your forefinger points forward, your middle finger points out to the left, and your thumb points up. If you roughly align your forefinger with R, and your middle finger with S, then the cross product will point in the direction of your thumb.



Figure 15 - Right-Hand rule Vector Product

The resulting vector of the cross product is perpendicular to R and S, that is



and



This makes the vector product an ideal way of computing normals. The two vectors R and S can be orthogonal but do not have to be. A property of the vector product that will be covered later is, that the magnitude of T is the area of the parallelogram defined by R and S.

Let's multiply two vectors together using the vector product.








There are various vector product terms such as  etc. in this equation. The terms will result in a vector whose magnitude is zero, because the angle between those vectors is , and sin. This leaves



The other products between the unit vectors can be reasoned as:



Those results show, that the commutative multiplication law is not applicable to vector products. In other words



Applying those findings reduces the vector product term to



Now re-grouping the equation to bring like terms together leads to:



To achieve a visual pattern for remembering the vector product, some authors reverse the sign of the j scalar term.



Re-writing the vector product as determinants might help to memorize it as well.



A 2x2 determinant is the difference between the product of the diagonal terms. With determinants a "recipe" for a vector product consists of the following steps:

1. Write the two vectors that should be multiplied as Cartesian vectors





2. Write the cross product of those two vectors in determinant form, if this helps to memorize the process; otherwise skip to step 3.



3. Then compute by plugging in the numbers into



A simple example of a vector product calculation is to show that the assumptions that were made above, while simplifying the vector product, hold up.



To show that there is a sign reversal when the vectors are reversed , let's calculate the cross product of those terms.









The i and k terms are both zero, but the j term is -1, which makes . Now reversing the vector product









Which shows

Deriving a Unit Normal Vector for a Triangle

Image 16 shows a triangle with vertices defined in anti-clockwise order. The side pointing towards the viewer is defined as the visible side in this scene. That means that the normal is expected to point roughly in the direction of where the viewer is located.



Figure 16 - Deriving a Unit Normal Vector
The vertices of the triangle are:

P1 (0, 2, 1)
P2 (0, 1, 4)
P3 (2, 0, 1)

The two vectors R and S are retrieved by subtracting the vertex at the head from the vertex at its tail.

Δx = (xh - xt)
Δy = (yh - yt)
Δz = (zh - zt)

Bringing the result into the Cartesian form


















It is a common mistake to believe that if R and S are unit vectors, the cross product will also be a unit vector. The vector product equation shows that this is only true when the angle between the two vectors is 90 degrees and therefore the sinus of the angle theta is 1.



Please read in [Van Verth] about CPU implementation details.

Areas
The vector product might be used to determine the area of a parallelogram or a triangle (with the vertices at P1 - P3). Image 17 shows the two vectors helping to form a parallelogram and a triangle.



Figure 17 - Deriving the Area of a Parallelogramm / Triangle with the Vector Product

The height h is , therefore the area of the parallelogram is



This equals the magnitude of the cross product vector T. Thus when we calculate the vector product of R and S, the length of the normal vector equals the area of the parallelogram formed by those vectors. The triangle forms half of the parallelogram and therefore half of the area.

area of parallelogram =
area of triangle =

or

area of triangle =

To compute the surface area of a mesh constructed from triangles or parallelograms, the magnitude of its non-normalized normals can be used like this.



The sign of the magnitude of the normal shows if the vertices are clockwise or counter-clockwise oriented.


References

[Azad] Kalid Azad, "Math Better Eplained", http://betterexplained.com/articles/math-betterexplained-ebook-available/

[Eberly] David H. Eberly, "3D Game Engine Design", p. 15, 2nd Edition, Morgan Kauffman 2007

[Farin] Gerald Farin, Dianne Hansford, "The Geometry Toolbox - For Graphics and Modeling", p. 16, AK Peters 1998

[Lengyel] Eric Lengyel, Mathematics for 3D Game Programming and Computer Graphics, Second Edition, Charles River Media 2003

[Vince] John Vince, "Mathematics for Computer Graphics", Springer, 3rd Edition, 2010

[Van Verth] James M. Van Verth, Lars M. Bishop, "Essential Mathematics for Games & Interactive Applications - A Programmer's Guide", Morgan Kaufmann 2004