Transformations Involved in Gribb & Hartmann Frustum Construction

Question

I'm currently working on implementing a Gribb & Hartmann Frustum Construction algorithm into my 3D game engine for frustum culling, but I find I need more clarification on the transformations involved in order to get it working correctly. I would like to use terminology from the literature for brevity.

In the case where the matrix M is equal to the camera's projection matrix, is it correct that the resulting a, b, c, and d values represent coefficients for the frustum planes in the camera's local space? Then, which transformations are necessary to convert these values into world space? I've surely read section 3.1 in the text, but my results have errors.

On a related note, I find that the camera's model/view matrices I send to OpenGL need to be inverted while the model/view matrices for world geometry do not, which adds to confusion on this topic.

I'd like to paste my code on this algorithm for more context on my issues and possible advice.

// Gribb & Hartmann https://www.gamedevs.org/uploads/fast-extraction-viewing-frustum-planes-from-world-view-projection-matrix.pdf
void camera_update_frustum(camera* cam) {
 m4 trans = transform(cam->pos, cam->rot, v3new(1, 1, 1));
 m4 M = m4mult(trans, cam->proj);
 float* m = (float*)&M;
 float a, b, c, d;
 // loop through 3 axes left/right, bottom/top, near/far
 for (int i = 0; i < 3; i += 1) {
 // then through 2 opposite sides.
 for (int j = 0; j < 2; j += 1) {
 int s = j ? -1 : 1;
 a = m[12] + s * m[4 * i + 0];
 b = m[13] + s * m[4 * i + 1];
 c = m[14] + s * m[4 * i + 2];
 d = m[15] + s * m[4 * i + 3];
 float e = sqrt(a*a + b*b + c*c);
 v3 n = v3new(a/e, b/e, c/e);
 v3 h = v3scl(n, d/e);
 // into array for storage
 cam->frustum[6 * (2 * i + j) + 0] = h.x;
 cam->frustum[6 * (2 * i + j) + 1] = h.y;
 cam->frustum[6 * (2 * i + j) + 2] = h.z;
 cam->frustum[6 * (2 * i + j) + 3] = n.x;
 cam->frustum[6 * (2 * i + j) + 4] = n.y;
 cam->frustum[6 * (2 * i + j) + 5] = n.z;
 }
 }
}

Answer 1

In the case where the matrix M is equal to the camera's projection matrix, is it correct that the resulting a, b, c, and d values represent coefficients for the frustum planes in the camera's local space?

For OpenGL, this is the subject of most of section 3 of the Gribb & Hartmann paper. In this case, where a, b, c, and d are computed from a projection matrix, they are the coefficients of a plane in view coordinates (eye coordinates). This follows from the fact that the projection matrix defines the transformation from that coordinate system to clip coordinates. View coordinates are not necessarily the same as world or model (object) coordinates.

Then, which transformations are necessary to convert these values into world space? I've surely read section 3.1 in the text, but my results have errors.

What Gribb & Hartmann are telling you in section 3.1 is that if you want plane equations in a different coordinate system then start with a different matrix. In particular, start with a matrix that transforms to clip coordinates from whatever coordinate system it is in which you want to express the plane's formula. For planes in world coordinates, the wanted matrix would be the matrix product of the projection matrix times the view matrix. Of course OpenGL maintains only a combined model/view matrix, not a separate view matrix.

It is also possible, and not too hard algebraically, to use the inverse view matrix to convert the plane coefficients from view to world coordinates, but do you have an inverse view matrix? There isn't one in your example code.

Note also that matrix multiplication and matrix / vector multiplication are not commutative. You must be sure to get the operand order correct. The paper uses the convention that OpenGL does, that transformation matrices are applied on the left, so V' = M·V.

That order then also applies to multiplication of transformation matrices, so the matrix to transform from model coordinates to clip coordinates should be computed as M_projection·M_model/view. With that in mind, this looks suspicious:

 m4 M = m4mult(trans, cam->proj);

It appears to have the operands reversed. Moreover, note well that model coordinates are not necessarily the same as world coordinates. If you are defining matrix trans in terms of world coordinates then you are computing for world coordinates (or trying to do). On the other hand, if your world coordinates differ from model coordinates, and you are defining trans in terms of model coordinates, then you are not computing for world coordinates.

On a related note, I find that the camera's model/view matrices I send to OpenGL need to be inverted while the model/view matrices for world geometry do not, which adds to confusion on this topic.

Confusion indeed. In OpenGL, view coordinates have a defined relationship with the camera: it is at the origin of this system, looking along the -z axis, with its "up" being in the positive y direction. You can, in this sense, talk about "the camera's model/view matrices" as the ones defined by particular camera positions and orientations. If you use that terminology, however, then it does not make sense to talk about "model/view matrices for world geometry".

In fact, because OpenGL does not maintain separate model and view matrices, it's a little tricky to talk about world coordinates at all. The model/view matrix transforms straight from model coordinates to view coordinates, bypassing world coordinates, which are notionally in between.

Possibly what you're getting at is summed up by the observation that from the perspective of world coordinates, if a transformation T of the model produces a particular change on the screen, then you can produce the same change on the screen by applying the T^-1 to the camera. It does take some mental agility to skip around among all these different coordinate systems, but perhaps a visualization will help you get this particular idea:

• imagine that you are at a photo shoot, watching the photographer take pictures of an antique globe. You are standing out of the way, immobile in a corner. Your perspective defines world coordinates.

• The photographer has just taken a picture of Illinois, and they now want a picture of Germany. They have two choices:

  • rotate the globe 99 degrees clockwise, OR
  • walk 99 degrees counterclockwise around the globe.

From your perspective in world coordinates, you can see the difference between those choices, but the resulting photo is the same either way (supposing the same axis of rotation, and a few other details). The sense of the transformation required depends on which part of the overall system is changed. Rotating the globe corresponds to transforming the model part of the model/view matrix, whereas moving the camera around the globe corresponds to transforming the view part of the model/view matrix.