.
There is no way around mathematics. If you want to understand computer geometry, you need to master a few mathematical concepts. But not that many actually. I won't introduce everything since there is already a lot of tutorials online explaining the core concepts of linear algrebra, Euclidean geometry, homogeneous coordinates, projective geometry and quaternions (yes, those are the keywords to enter in your preferred search engine). The teaser image above comes from the Cyclopaedia, an Universal Dictionary of Arts and Sciences published by Ephraim Chambers in London in 1728 (sources History of Geometry).
Even though we're dealing with the three-dimensional Euclidean space, three dimensional coordinates are actually not the best representation we can use and this is the reason why we will use homogeneous coordinates that describe coordinates in a four-dimensional projective space (that includes the Euclidean space). We'll see in the next section that this allows us to express linear transformations (rotation, scaling), affine transformations (translations) and projection using 4×4 matrices. Homogeneous coordinates are tightly linked with regular 3D coordinates with the noticeable difference that they require a fourth w coordinate that corresponds to the fourth dimension, let's call it the projective dimension. In order to explain it, we'll use a 1-dimensional space where point coordinates are single scalars indicating the position of the points onto the X-axis. This will make everything clearer hopefully.
Let us consider for example a simple set of points [-1.0, -0.5, 0.0, +0.5, +1.0] in this unidimensional space. We want to project onto another segment [-2,+2] that represents the screen (any point projected outside this segment is discared and won't be visible into the final projection). The question now is how do we project the points onto the screen?
Figure
To answer this question, we need to know where is the camera (from where do we look at the scene) and where are the points positioned relatively to the screen. This is the reason why we introduce a supplementary w coordinate in order to indicate the distance to the screen. To go from our Euclidean representation to our new homogeneous representation, we'll use a conventional and default value of 1 for all the w such that our new point set is now [(-1.0,1.0), -(0.5,1.0), (0.0,1.0), (+0.5,1.0), (+1.0,1.0)]. Reciprocally, a point (x,w) in projective space corresponds to the point x/w (if w ≠ 0) in our unidimensional Euclidean space. From this conversion, we can see immediately that there exists actually an infinite set of homogenous coordinates that correspond to a single Cartesian coordinate as illustrated in the figure.
Figure
We are now ready to project our point set onto the screen. As shown in the figure above, we can use an orthographic (all rays are parallel) or a linear projection (rays originate from the camera point and hit the screen, passing through points to be projected). For these two projections, results are similar but different. In the first case, distances have been exactly conserved while in the second case, the distance between projected points has increased, but projected points are still equidistant. The third projection is where homogenous coordinates make sense. For this (arbitrary) projection, we decided that the further the point is from the origin, the further away from the origin its projection will be. To do that, we measure the distance of the point to the origin and we add this distance to its w value before projecting it (this corresponds to the black circles in the figure) using the linear projection. It is to be noted that this new projection does not conserve the distance relationship and if we consider the set of projected points [P(-1.0), P(-0.5), P(0.0), P(+0.5), P(+1.0)], we have ║P(-1.0)-P(-0.5)]║ > ║P(-0.5)- P(0.0)║.
Note
Quaternions are not homogenous coordinates even though they are usually represented in the form of a 4-tuple (a,b,c,d) that is a shortcut for the actual representation: a + bi⃗ + cj⃗ + dk⃗, where a, b, c, and d are real numbers, and i⃗, j⃗, k⃗ are the fundamental quaternion units.
Back to our regular 3D-Euclidean space, the principle remains the same and we have the following relationship between Cartesian and homogeneous coordinates:
If you didn't understand everything, you can stick to the description provided by Sam Hocevar:
- If w = 1, then the vector (x,y,z,1) is a position in space
- If w = 0, then the vector (x,y,z,0) is a direction
Figure
We'll now use homogeneous coordinates and express all our transformations using only 4×4 matrices. This will allow us to chain several transformations by multiplying transformation matrices. However, before diving into the actual definition of these matrices, we need to decide if we consider a four coordinates vector to be 4 rows and 1 column or 1 row and 4 columns. Depending on the answer, the multiplication with a matrix will happen on the left or on the right side of the vector. To be consistent with OpenGL convention, we'll consider a vector to be 4 rows and 1 columns, meaning transformations happen on the left side of vectors. To transform a vertex V by a transformation matrix M, we write: V' = M*V. To chain two transformations M1 and M2 (first M1, then M2), we write: V' = M2*M1*V which is different from V' = M1*M2*V because matrix multiplication is not commutative. As clearly illustrated by the figure on the right, this means for example that a rotation followed by a translation is not the same as a translation followed by a rotation.
Considering a vertex V = (x, y, z, 1) and a translation vector T = (tx, ty, tz, 0), the translation of V by T is (x+tx, y+ty, z+tz, 1). The corresponding matrix is given below:
Considering a vertex V = (x, y, z, 1) and a scaling vector S = (sx, sy, sz, 0), the scaling of V by S is (sx*x, sy*y, sz*z, 1). The corresponding matrix is given below:
A rotation is defined by an axis of rotation A and an angle of rotation d. We defined below only the most common rotations, that is, around the X-axis, Y-axis and Z-axis.
OpenGL uses a column-major representation of matrices. This mean that when reading a set of 16 contiguous values in memory, relative to a 4×4 matrix, the first 4 values correspond to the first column while in Numpy (using C default layout), this would correspond to the first row. In order to stay consistent with most OpenGL tutorials, we'll use a column-major order in the rest of this book. This means that any glumpy transformations will appear to be transposed when displayed, but the underlying memory representation will still be consistent with OpenGL and GLSL. This is all you need to know at this stage.
Considering a set of 16 contiguous values in memory:
We get different representations depending on the order convention (column major or row major):
For example, here is a translation matrix as returned by the glumpy.glm.translation function:
import glumpy
T = glumpy.glm.translation(1,2,3)
print(T)
[[ 1. 0. 0. 0.]
[ 0. 1. 0. 0.]
[ 0. 0. 1. 0.]
[ 1. 2. 3. 1.]]
print(T.ravel())
[ 1. 0. 0. 0. 0. 1. 0. 0. 0. 0. 1. 0. 1. 2. 3. 1.]
↑ ↑ ↑
13 14 15So this means you would use the translation on the left when uploading to the GPU, but you would use that on the right with Python/NumPy:
T = glumpy.glm.translation(1,2,3)
V = [3,2,1,1]
print(np.dot(V, T))
[ 4. 4. 4. 1.]In order to define a projection, we need to specify first what do we want to view, that is, we need to define a viewing volume such that any object within the volume (even partially) will be rendered while objects outside won't. In the image below, the yellow and red spheres are within the volume while the green one is not and does not appear in the projection.
There exist many different ways to project a 3D volume onto a 2D screen but we'll only use the `perspective projection`_ (distant objects appear smaller) and the `orthographic projection`_ which is a parallel projection (distant objects have the same size as closer ones) as illustrated in the image above. Until now (previous section), we have been using implicitly an orthographic projection in the z=0 plane.
Depending on the projection we want, we will use one of the two projection matrices below:
At this point, it is not necessary to understand how these matrices were built. Suffice it to say they are standard matrices in the 3D world. Both assume the viewer (=camera) is located at position (0,0,0) and is looking in the direction (0,0,1).
There exists a second form of the perpective matrix that might be easier to manipulate. Instead of specifying the right/left/top/bottom planes, we'll use field of view in the horizontal and vertical direction:
where fovy specifies the field of view angle in the y direction and aspect specifies the aspect ratio that determines the field of view in the x direction.
We are almost done with matrices. You may have guessed that the above matrices require the viewing volume to be in the z direction. We could design our 3D scene such that all objects are within this direction but it would not be very convenient. So instead, we use a view matrix that maps the world space to camera space. This is pretty much as if we were orienting the camera at a given position and look toward a given direction. In the meantime, we can further refine the whole pipeline by providing a model matrix that maps the object's local coordinate space into world space. For example, this is useful for rotating an object around its center. To sum up, we need:
- Model matrix maps from an object's local coordinate space into world space
- View matrix maps from world space to camera space
- Projection matrix maps from camera to screen space
This corresponds to the model-view-projection model. If you have read the whole chapter carefully, you may have guessed the corresponding GLSL shader:
uniform mat4 view;
uniform mat4 model;
uniform mat4 projection;
attribute vec3 P;
void main(void)
{
gl_Position = projection*view*model*vec4(P, 1.0);
}