0
$\begingroup$

Now there has already been an answer here in this stackexchange, but I don't understand certain aspects of it. The author has MORE DETAILED DESCRIPTION HERE(#1) but the problem is he doesn't describe what the linear mapping is done or how is the frustum transformed into the bounding box, there's NOWHERE IN THE WORLD mentioned how these two subspaces overlap or one is transformed to the other, for example:
enter image description here
Is this how these two spaces exist and after projecting the point from inside the view frustum to the near plane a linear mapping is done where the author says:

"Our input to the linear mapping is x=x_near, and our output is the x coordinate in NDC space y=x_ndc, whose range is [-1.0, 1.0]" from the above page

It looks as if he somehow connects a line from the frustum to the NDC space but not clear on how it is done e.g. does he connect the top left vertex to the top left front vertex of the NDC cube? Are the four corners of the frustum mapped to four corners of the cube?

As much I'd like to make this answer self contained, I don't know if I can copy his materials in here, please be kind enough to check the link out and help me understand this. Thanks in advance.

$\endgroup$
2
$\begingroup$

The key trick is the perspective divide, This divides the position by the w component.

If you swap z and w (using a identity matrix that has swapped 3rd and 4th rows) and then do a perspective divide you end up with a double pyramid with a angle between the side (FoV) of 90° if applied to a unit cube.

Once you have that transformation you can remap you can do further remapping pre and post the swap to make the corners of the input and output match up. The well known algorithm to create a perspective matrix has all those remaps inlined as an optimization.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for answering but I meant to understand the equation that mapped the frustum to the standard NDC cube (in the link given in my question) $\endgroup$ – juztcode Feb 18 at 12:22
1
$\begingroup$

TL;DR:

The view frustum is the NDC box. It's just that NDC space is nonlinear because it occurs after the perspective divide by w. The tops and sides of the frustum are parallel in NDC space. All lines that project to the viewpoint are parallel in NDC space.

Explanation:

I don't like math. I dislike sites that try to explain all this with math and matrices and boring stuff like that. I prefer pictures. So I'll try to explain it with mainly pictures and descriptions. Unfortunately the one thing that I must refer to mathematically is the fact that we have to divide by Z to transform 3D points to 2D points according to the perspective transformation. But "divide by Z" is as mathematical as I'll get, I promise.

The spaces

Recall the different spaces. The View and Projection matrices are all linear transformations. World Space, Camera Space, and Homogeneous Clip Space are all linear spaces. The Normalized Device Coordinates are in a non-linear (projective) space and the Divide by w is a non-linear transformation. We reinterpret these coordinates as screen coordinates and do a linear transform from NDC to viewport coordinates.

The whole point of clip space is to keep the space linear and defer dividing by Z until the very end. The denominator of the perspective transformation is kept as its own coordinate in linear space and called W (it's the divisor for the homogeneous coordinates). At some point we can no longer defer this divide because we need screen coordinates so we must ultimately go from (X,Y,Z,W) to (X/W, Y/W, Z/W) and wind up in NDC space. (Technically we go from homogeneous coordinates to 3-space.)

So I think this is the mathematical part of the answer to your question: (X,Y,Z,W) → (X/W, Y/W, Z/W) is called the Perspective Divide by W and it's the operation you're looking for that maps from Clip space to NDC.

The transformations

enter image description here

Visualizing NDC

I've always hated how people draw the frustum with straight lines and draw the NDC box with straight lines but never show what's going on in the interior. It really betrays our understanding of the non-linearity of relationship between the two spaces. So here's a better diagram to help visualize the non-linearity of NDC space after the perspective projection.

enter image description here

Imagine you stand where the person with the camera is and take a picture. The red lines are the boundaries of what the camera can see. Some familiar properties:

  • All points along the top of the red frustum will be at the top of the camera image
  • All points along the bottom of the red frustum will be at the bottom of the camera image.
  • The side of the frustum closest to the camera (left of this diagram) is the near clipping plane
  • The side of the frustum farthest from the camera (right of this diagram) is the far clipping plane.

The top part of the diagram is World / View / Clip clip space. They are all linear transforms of one another, so for this diagram they are all basically the same.

The bottom part of the diagram is Normalized Device Coordinate space. In NDC space the top and bottom of that frustum are parallel. Notice the frustum in Clip space became a rectangle in NDC space. Because the near clipping plane and the far clipping plane both become the same size as the camera image (camera sensor / camera frame).

Note that any line that passes through the viewpoint is parallel to the top and bottom of this frustum in NDC space -- the magenta line is an example of this. Notice that the magenta line passes just over the roof of the first (near) car and just over the back tire of the yellow (far) car. Yet in NDC space, this line is parallel to the top of the frustum and the bottom of the frustum. All the points along that magenta line will have the same coordinates in the final camera image (will appear at the same point on the screen in your rendering). Cool, right?

The frustum becomes a box in NDC space, which, I'll admit, is deceptively linear-seeming. But you can tell the NDC space is non-linear (has that "divides by Z" property) because the lines of the sidewalk (which are parallel in world space or view/camera space) are not parallel in NDC space. They follow that characteristic 1/x style curve in the diagram.

In the diagram, for some distance away from the camera, everything is proportionally the same distance away from the top and bottom of the camera frustum in both Clip space, and NDC.

Summary

Hopefully this is a useful visual explanation of how to get between World / View / Clip space and NDC. This is intended to supplement the mathematical descriptions you've already been given, not replace them. Hopefully this gives you a visual with which you can ground your understanding of the non-linearity of projective transformations.

Just remember:

  • That although all the camera boundaries (red lines in the diagram) match between World space and NDC, it's a frustum in World space and a rectangle in NDC space. (So yes, the corners of the view frustum are the corners of the NDC "cube")
  • That straight lines (that run closer or farther to the camera and don't pass through the viewpoint) like the edges of the sidewalk are straight in World space but may be curved in NDC space. :)
| improve this answer | |
$\endgroup$
  • $\begingroup$ Part of your summary: "straight lines... are straight in World space but may be curved in NDC space," is totally incorrect. This might be technically true for a real camera, with real lenses - but for mathematical models being discussed - straight lines in WCS will always be straight lines after projection. $\endgroup$ – Brett Hale Feb 27 at 14:12
  • $\begingroup$ @BrettHale, You're partly right but also largely misunderstanding. You're thinking that the projected image of a 3D straight line into 2D space will always be straight. That's true -- in x & y only. But NDC space is a 3D space and the depth component is nonlinear because it has been divided by W. I thought my picture showed it pretty well especially since the sidewalk is clearly curved when you visualize the depth component (looking at it "from the side", like I did in the diagram). Looks like it didn't explain it well enough to you. $\endgroup$ – Wyck Feb 27 at 14:23
  • $\begingroup$ I see where you're coming from. It's why you can linearly interpolate vertex attributes correctly (or use barycentric interpolation on triangles) in homogeneous coordinates, but not after projection, for the reasons you describe. $\endgroup$ – Brett Hale Feb 27 at 14:45
  • $\begingroup$ @BrettHale, yes! That's exactly right. Your comment about interpolating attributes highlights the beauty of working in a homogeneous coordinate system / projective space. $\endgroup$ – Wyck Feb 27 at 14:50
1
$\begingroup$

Note: This is a work in progress - working on LaTeX and useful illustrations.


My derivation notes were based partially on the perspective projection matrix derivation in Computer Graphics: Principles and Practice (2nd Ed). My understanding is that the 3rd edition takes a more contemporary approach with references to OpenGL and Direct3D. I haven't read this edition, and can't vouch for it.

This derivation also assumes an understanding of homogeneous coordinates and the notion of a projective space. The wikipedia entry is concise, but lacks the intuition provided by a few good 2D example illustrations. (If you're really keen, search for early articles on the subject by Jim Blinn).

First, we need to outline a few assertions and conventions:

  • We always assume a 'right-handed' coordinate space, unless otherwise stated. The 'eye' is at: (0, 0, 0). (+Z) may be considered the direction pointing 'out' of the screen (or window / viewport), while (X, Y) are Cartesian coordinates, where: (0, 0) corresponds to the centre of that viewport.
  • The view frustum has a near plane at: Z = - N and a far plane at: Z = - F, with normals in the +Z direction. The near plane: Z = - N, has X: L <= X <= R, and Y: B <= Y <= T, which will eventually map to a 3D viewport. This frustum encapsulates all visible geometry. (Technically speaking, R < L, T < B, and N > F > 0 are permitted by glFrustum. Arbitrary matrices are of course permitted in core profile OpenGL contexts.)
  • The mathematics will use what are somewhat misleadingly called 'row-major' matrices, but I insist on the use of column vectors when describing a system of transforms, i.e., the column vector is 'pre-multiplied' by the matrix: v' = [M]v. Disagree all you want - just know that you are sick and need help.

    In all seriousness, either convention can be made to work; it's just a matter of being aware of the conventions and sticking with a choice. The 'column-vector' convention is typically the one taught in linear algebra. We apply successive transforms: [A], [B], [C] to a vector: v, like we would apply functions: C(B(A(v))), hence: v' = [C][B][A]v.


Any view frustum (camera) in space can be transformed by pre-multiplying the (homogeneous) coordinates by an 'orientation matrix'. That's beyond your question, but typically requires a general PRP (camera eye point), VRP (the centre of the 'near' projection plane), and the VUP point, which references a point defining 'up'. In effect, it's sufficient to form a orthonormal coordinate system. This is the view coordinate space (VCS).

The orthonormal basis, along with the PRP translation, can be used to construct an inverse transform that 'premultiplies' geometry to world coordinate space (WCS). Again, you can save the concept of orthonormal basis / coordinate system transforms for a rainy day...


We do not assume the view frustum is centred on the Z axis - although this is almost certainly the case for most projections. There are more exotic transforms (a mirror in a scene comes to mind); we'll concentrate on the general case.

The direction of projection: $\small\\\mathbf{DOP}=\left[(R+L)/2,\: (T+B)/2,\: -N\right]\,^T$. The view frustum is typically symmetric about the Z axis s.t. R = - L, T = - B, yielding: $\small\\\mathbf{DOP}=\left[0,\: 0,\: -N\right]\,^T$.

Of course, this is not required, so our first step in the perspective projection derivation is to apply a shear matrix that maps the $\small\\\mathbf{DOP}$ to the (negative) Z-axis:

(R + L) / 2 + shear.x (- N) = 0 => shear.x = (R + L) / (2.N)
(T + B) / 2 + shear.y (- N) = 0 => shear.y = (T + B) / (2.N)

Consider the shear transformation applied to the frustum's near-clipping plane vertex coordinates:

$\tiny\begin{pmatrix} 1 & 0 & (R+L)/(2.N) & 0 \\ 0 & 1 & (T+B)/(2.N) & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix} \cdot \begin{pmatrix} R \\ T \\ -N \\ 1 \end{pmatrix} = \begin{pmatrix} (R-L)/2 \\ (T-B)/2 \\ -N \\ 1 \end{pmatrix} \:,$

$\tiny\begin{pmatrix} 1 & 0 & (R+L)/(2.N) & 0 \\ 0 & 1 & (T+B)/(2.N) & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix} \cdot \begin{pmatrix} L \\ B \\ -N \\ 1 \end{pmatrix} = \begin{pmatrix} (L-R)/2 \\ (B-T)/2 \\ -N \\1 \end{pmatrix} $

Following this transform, the $\small\\\mathbf{DOP}$ is in direction of the - Z axis; specifically, the centre of the near view plane: $\small\left((R+L)/2,\: (T+B)/2,\: -N,\: 1\right)\,^T$ has been mapped to: $\small\left(0,\: 0,\: -N,\: 1\right)\,^T$.

Now we want to scale the perspective projection transform such that the R, L, T, B planes of the frustum have have a unit gradient. The current gradients are (R - L) / (2.N) (right and left), and (T - B) / (2.N) (top and bottom). The symmetry is due to the previous shearing transform.

(R - L) / (2.N) * scale.x = 1 => scale.x = 2.N / (R - L)
(T - B) / (2.N) * scale.y = 1 => scale.y = 2.N / (T - B)

Furthermore, we want to scale by (1 / F) s.t. the far clipping plane is mapped to: Z = - 1, while the unit slopes of the right, left, top, and bottom clipping planes are preserved. These scaling factors premultiply the perspective projection matrix:

$ \tiny\begin{pmatrix} 2.N/(F(R-L)) & 0 & 0 & 1 \\ 0 & 2.N/(F(T-B)) & 0 & 1 \\ 0 & 0 & 1/F & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix} \cdot \begin{pmatrix} 1 & 0 & (R+L)/(2.N) & 0 \\ 0 & 1 & (T+B)/(2.N) & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix} =\\ \tiny\begin{pmatrix} 2.N/(F(R-L)) & 0 & (R+L)/(F(R-L)) & 0 \\ 0 & 2.N/(F(T-B)) & (T+B)/(F(T-B)) & 0 \\ 0 & 0 & 1/F & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix} $

This transform yields what may be considered the normalized frustum.

(TODO: need an image to show this transform)

The vertices of near clipping plane are mapped to: $\small\left(\pm N/F,\: \pm N/F,\: -N/F,\: 1\right)\,^T$, while the vertices of the far-clipping plane are mapped to: $\small\left(\pm 1,\: \pm 1,\: -1,\: 1\right)\,^T$.


(TODO: perspective (projection) transform unification -> CCS)

As a homogeneous transform, the matrix can be simplified by scaling all elements by F, since: $\small\left(X,\: Y,\: Z,\: W\right)\,^T \equiv \left(F.X,\: F.Y,\: F.Z,\: F.W\right)\,^T$ :

$ \tiny\begin{pmatrix} 2.N/(R-L) & 0 & (R+L)/(R-L) & 0 \\ 0 & 2.N/(T-B) & (T+B)/(T-B) & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & F \end{pmatrix} $

The normalized perspective projection view volume can be transformed into a parallel projection view volume:

(TODO: partial justification for this step. Perspective projection is just another homogeneous transform. Final CCS / NDCS have exquisite clip test properties)

$ \tiny\begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & F/(F-N) & N/(F-N) \\ 0 & 0 & -1 & 0 \end{pmatrix} \cdot \begin{pmatrix} 2.N/(R-L) & 0 & (R+L)/(R-L) & 0 \\ 0 & 2.N/(T-B) & (T+B)/(T-B) & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & F \end{pmatrix} =\\ \tiny\begin{pmatrix} 2.N/(R-L) & 0 & (R+L)/(R-L) & 0 \\ 0 & 2.N/(T-B) & (T+B)/(T-B) & 0 \\ 0 & 0 & F/(F-N) & F.N/(F-N) \\ 0 & 0 & -1 & 0 \end{pmatrix} $

(TODO: need an image to show this transform)


Finally, we apply the following transforms to the current projection matrix:

  • Scale in Z by (2) to yield a cubic view volume.
  • Translate by: $\small\left(0,\: 0,\: 1,\: 1\right)\,^T$ to centre the cube at the origin.
  • Convert to a left-handed coordinate system to satisfy NDCS conventions.

$ \tiny\begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & -1 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix} \cdot \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 \end{pmatrix} \cdot \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 2 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix} =\ \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & -2 & -1 \\ 0 & 0 & 0 & 1 \end{pmatrix} $

This yields:

$ \tiny\begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & -2 & -1 \\ 0 & 0 & 0 & 1 \end{pmatrix} \cdot \begin{pmatrix} 2.N/(R-L) & 0 & (R+L)/(R-L) & 0 \\ 0 & 2.N/(T-B) & (T+B)/(T-B) & 0 \\ 0 & 0 & F/(F-N) & F.N/(F-N) \\ 0 & 0 & -1 & 0 \end{pmatrix} =\\ \tiny\begin{pmatrix} 2.N/(R-L) & 0 & (R+L)/(R-L) & 0 \\ 0 & 2.N/(T-B) & (T+B)/(T-B) & 0 \\ 0 & 0 & -(F+N)/(F-N) & -2.F.N/(F-N) \\ 0 & 0 & -1 & 0 \end{pmatrix} $

(TODO: need an image to show this transform)

This is the canonical OpenGL perspective projection matrix:

$ \small\begin{pmatrix} 2.N/(R-L) & 0 & (R+L)/(R-L) & 0 \\ 0 & 2.N/(T-B) & (T+B)/(T-B) & 0 \\ 0 & 0 & -(F+N)/(F-N) & -2.F.N/(F-N) \\ 0 & 0 & -1 & 0 \end{pmatrix} $

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.