Homogeneous coordinate system

A homogeneous coordinate system is a coordinate system in which there is an extra dimension, used most commonly in computer science to specify whether the given coordinates represent a vector (if the last coordinate is zero) or a point (if the last coordinate is non-zero). A homogeneous coordinate system is used by OpenGL for representing position.

In other term :

One of the many purposes of using homogeneous coordinates is to capture the concept of infinity. In the Euclidean coordinate system, infinity is something that does not exist. Mathematicians have discovered that many geometric concepts and computations can be greatly simplified if the concept of infinity is used. This will become very clear when we move to curves and surfaces design. Without the use of homogeneous coordinates system, it would be difficult to design certain classes of very useful curves and surfaces in computer graphics and computer-aided design.

Let us consider two real numbers, a and w, and compute the value of a/w. Let us hold the value of a fixed and vary the value of w. As w getting smaller, the value of a/w is getting larger. If w approaches zero, a/w approaches to infinity! Thus, to capture the concept of infinity, we use two numbers a and w to represent a value v, v=a/w. If w is not zero, the value is exactly a/w. Otherwise, we identify the infinite value with (a,0). Therefore, the concept of infinity can be represented with a number pair like (a, w) or as a quotient a/w.

Let us apply this to the xy-coordinate plane. If we replace x and y with x/w and y/w, a function f(x,y)=0 becomes f(x/w,y/w)=0. If function f(x,y) = 0 is a polynomial, multiplying it with wn will clear all denominators, where n is the degree of the polynomial.

For example, suppose we have a line Ax + By + C = 0. Replacing x and y with x/w and y/w yields A(x/w) + B(y/w) + C = 0. Multiplying by w changes it to

Ax + By + Cw = 0. Let the given equation be a second degree polynomial Ax2 + 2Bxy + Cy2 + 2Dx + 2Ey + F = 0. After replacing x and y with x/w and y/w and multiplying the result with w2, we have

Ax2 + 2Bxy + Cy2 + 2Dxw + 2Eyw + Fw2 = 0 If you look at these two polynomials carefully, you will see that the degrees of all terms are equal. In the case of a line, terms x, y and w are of degree one, while in the second degree polynomial, all terms (i.e., x2, xy, y2, xw, yw and w2) are of degree two. Given a polynomial of degree n, after introducing w, all terms are of degree n. Consequently, these polynomials are called homogeneous polynomials and the coordinates (x,y,w) the homogeneous coordinates.

Given a degree n polynomial in a homogeneous coordinate system, dividing the polynomial with wn and replacing x/w, y/w with x and y, respectively, will convert the polynomial back to a conventional one. For example, if the given degree 3 homogeneous polynomial is the following:

x3 + 3xy2 - 5y2w + 10w3 = 0 the result is x3 + 3xy2 - 5y2 + 10 = 0 This works for three-dimension as well. One can replace a point (x, y, z) with (x/w, y/w, z/w) and multiply the result by w raised to certain power. The resulting polynomial is a homogeneous one. Converting a degree n homogeneous polynomial in x, y, z and w back to the conventional form is exactly identical to the two-variable case.

An Important Notes Given a point (x,y,w) in homogeneous coordinates, what is its corresponding point in the xy-plane? From what we discussed for converting a homogeneous polynomial back to its conventional form, you might easily guess that the answer must be (x/w,y/w). This is correct. Thus, a point (3,4,5) in homogeneous coordinates converts to point (3/5,4/5)=(0.6,0.8) in the xy-plane. Similarly, a point (x,y,z,w) in homogeneous coordinates converts to a point (x/w,y/w,z/w) in space. Conversely, what is the homogeneous coordinates of a point (x,y) in the xy-plane? It is simply (x,y,1)! That is, let the w component be 1. In fact, this is only part of the story, because the answer is not unique. The homogeneous coordinates of a point (x,y) in the xy-plane is (xw, yw, w) for any non-zero w. Why is this true? Because (xw, yw, w) is converted back to (x,y). As a result, the following is important for you to memorize:

Converting from a homogeneous coordinates to a conventional one is unique; but, converting a conventional coordinates to a homogeneous one is not. For example, a point (4,2,3) in space is convert to (4w, 2w, 3w, w) for any non-zero w.

The Dimensionality of Homogeneous Coordinates You perhaps have discovered that homogeneous coordinates need 3 and 4 components to represent a point in the xy-plane and a point in space, respectively. Therefore, a point in space (resp., the xy-plane) in homogeneous coordinates actually has four (resp., third) components. Adding a fourth (resp., third) component whose value is 1 to the coordinates of a point in space (resp., the xy-plane) converts it to its corresponding homogeneous coordinates.

Ideal Points or Points at Infinity As mentioned at the very beginning of this page, homogeneous coordinates can easily capture the concept of infinity. Let a point (x,y) be fixed and converted to a homogeneous coordinate by multiplying with 1/w, (x/w,y/w,1/w). Let the value of w approach to zero, then (x/w,y/w) moves farther and farther away in the direction of (x,y). When w becomes zero, (x/w,y/w) moves to infinity. Therefore, we would say, the homogeneous coordinate (x,y,0) is the ideal point or point at infinity in the direction of (x,y). Let us take a look at an example. Let (3,5) be a point in the xy-plane. Consider (3/w,5/w). If w is not zero, this point lies on the line y = (5/3) x. Or, if you like the vector form, (3/w,5/w) is a point on the line O + (1/w)d, where the base point O is the coordinate origin and d is the direction vector <3,5>. Therefore, as w approaches zero, the point moves to infinity on the line. This is why we say (x,y,0) is the ideal point or the point at infinity in the direction of (x,y).

The story is the same for points in space, where (x,y,z,0) is the ideal point or point at infinity in the direction of (x,y,z).

The concept of homogeneous coordinates and points at infinity in certain direction will become very important when we discuss representations of curves and surface.

A Simple Geometric Interpretation Given a homogeneous coordinate (x,y,w) of a point in the xy-plane, let us consider (x,y,w) to be a point in space whose coordinate values are x, y and w for the x-, y- and w- axes, respectively. The line joining this point and the coordinate origin intersects the plane w = 1 at a point (x/w, y/w, 1). Please verify this fact yourself. The following figure illustrates this concept.

This transformation treats a two-dimensional homogeneous point as a point in three-dimensional space and projects (from the coordinate origin) this three-dimensional point to the plane w=1. Therefore, as a homogeneous point moves on a curve defined by homogeneous polynomial f(x,y,w)=0, its corresponding point moves in three-dimensional space, which, in turn, is projected to the plane w=1. Of course, (x/w,y/w) moves on a curve in plane w=1.

The above figure also shows clearly that while the conversion from the conventional Euclidean coordinates to homogeneous coordinates is unique, the opposite direction is not because all points on the line joining the origin and (x,y,w) will be projected to (x/w,y/w,1). This is also an important concept to be used in later lectures.

in more :Homogeneous Coordinates

For reasons that hopefully will become clear in a moment, it's useful to represent 3D points in computer graphics using a 4-vector coordinate system, known as homogeneous coordinates.

To represent a point (x,y,z) in homogeneous coordinates, we add a 1 in the fourth column:

1. (x,y,z) -> (x,y,z,1)

To map an arbitrary point (x,y,z,w) in homogenous coordinates back to a 3D point, we divide the first three terms by the fourth (w) term. Thus:

2. (x,y,z,w) -> (x/w, y/w, z/w)

This sort of transformation has a few uses. For example, recall that one equation for determining points on a plane is the equation:

3. A point is on a plane if the point satifies the relationship

0 = A*x + B*y + C*z + D

We can use this to our advantage by representing a plane L = (A,B,C,D). It is trivial to see that a point is on the plane L if

4. P dot L = 0

What makes this relationship interesting that if we have a "normalized" homogeneous point P and a "normalized" plane L, defined as:

A homogeneous point P = (x,y,z,w) isnormalized iff w = 1.

Likewise, a homogeneous plane L = (A,B,C,D)is normalized iff sqrt(A*A+B*B+C*C) = 1.

then the dot product is the "signed" distance of the point P from the plane L. This can be a useful relationship for hit detection or collision detection, when we wish to determine where a path from P1 to P2 intersects L. In that case, we can easily calculate the intersection point P by:

a1 = P1 dot L;a2 = P2 dot L;a = a1 / (a1 - a2);P = (1-a)*P1 + a*P2

This is useful when we need to do clipping of lines and polygons to fit inside the screen, as well as in performing collision detection.

Transforming Homogeneous Coordinates

We can represent rotation, scaling, and translation using homogeneous coordinates by using a 4x4 matrix. Note that if we were to simply restrict ourselves to a 3x3 matrix, we could not perform translations-in that case, we would have to explicitly add. But using a full 4x4 matrix, not only can we represent a translation using a 4x4 matrix, but we can derive all sorts of interesting properties, including easily translating back from screen coordinates to world coordinates.

The standard transformation matricies used in computer graphics are:

Translation:

T(x,y,z) =
1 0 0 0
0 1 0 0
0 0 1 0
x y z 1

Scaling:

S(x,y,z) =
x 0 0 0
0 y 0 0
0 0 z 0
0 0 0 1

Rotation about X axis:

Rx(angle)=
1 0 0 0
0 c s 0
0 -s c 0
0 0 0 1

where c = cosine(angle) s = sine(angle)

Rotation about Y axis:

Ry(angle)=
c 0 -s 0
0 1 0 0
s 0 c 0
0 0 0 1

where c = cosine(angle) s = sine(angle)

Rotation about Z axis:

Rz(angle)=
c s 0 0
-s c 0 0
0 0 1 0
0 0 0 1

where c = cosine(angle) s = sine(angle)

To use these matricies, you would post-multiply the homogeneous point P by the matrix. Thus, to rotate the point around all three axises, and then translate to a new location, you would do:

P' = P * Rx * Ry * Rz * T

(Note: to post-multiply, you would perform the following operation:

P * M =(x y z w) *
a b c d
e f g h
i j k l
m n p q | =(x' y' z' w')

where x' = x*a + y*e + z*i + w*m y' = x*b + y*f + z*j + w*n z' = x*c + y*g + z*k + w*p w' = x*d + y*h + z*l + w*q

Normally this is implemented using a for loop, and is expanded explicitly just so it's clear in what order the rows and columns are evaluated.)

What makes this an interesting thing to do is that as the multiplication of matricies is associative, instead of performing four matrix multiplies for each point we want to transform, we can instead multiply the four matricies together into a single matrix, and perform one point/matrix multiply for each point we transform. This is especially useful when we don't know apriori the number of translations that need to be performed to a collection of points.