1
$\begingroup$

When I was writing a software rasterizer for my university class, we did culling in eye coordinates. Essentially, we use cross product to get a normal from the 3 vertices (in eye coordinates), then we dot product that normal with one of the 3 vertices (since we are in eye coordinate, that vertex is essentially a vector from eye [0, 0, 0,.1] to triangle surface). If the dot product is > 0, meaning the normal and the eye vector point in the same direction, we cull that triangle.

OpenGL however doesn't do culling in eye space, since culling is after vertex shader. So all they have are vertices in clip space. So how do they know which triangle to do culling? Our triangles, when fed into the graphic pipeline, are always in CCW order. How do some turn into CW order?

$\endgroup$
1
  • $\begingroup$ Graphics API's don't "know" which triangles to cull, we the developers tell them with 1) Winding direction...CW or CCW and 2) Which face to cull .. Front face or Back Face. OpenGL has these value preset to CCW, back face. And that little extra info is all that the API needs (using the math outlined below) to figure it out. $\endgroup$
    – pmw1234
    Feb 6 at 16:39
1
$\begingroup$

It's actually fairly simple (and in essence 'equivalent' to what you said above). If you represent triangle ABC's projected XY coordinates as a matrix...

$$M_{ABC} = \begin{bmatrix} X_A & X_B & X_C \\ Y_A & Y_B & Y_C \\ 1 & 1 & 1 \\ \end{bmatrix} $$

...then the sign of the determinant e.g. $X_A (Y_B - Y_C)+X_B(Y_C-Ya)+X_C(Y_A-Y_B)$ will allow you to decide how to cull. Further if the determinant is zero, then the on-screen triangle has zero area and can clearly be removed.

Another reason to use this notation is that the adjoint of $M_{ABC}$ gives you equations for the edges.

$\endgroup$
3
  • 1
    $\begingroup$ Can you expand on the math behind it? Why does the sign of determinant tell you which face the triangle is facing? $\endgroup$
    – Harry Kane
    Feb 3 '20 at 14:21
  • $\begingroup$ The determinant of that matrix is proportional to the signed area of the triangle (can't recall the exact relationship and am a bit busy to plug in the values at present - sorry). In the meantime, I will try to give some thought as to an explanation. $\endgroup$
    – Simon F
    Feb 4 '20 at 10:48
  • $\begingroup$ Positive is front facing, Negative is back facing...by default. Also, if you stare at the determinant of a 3x3 matrix for to long it starts to look an awful lot like the scalar triple product. In fact it is 1/scalar triple product. (edit because I inadvertently wrote vector triple...which of course it is not) $\endgroup$
    – pmw1234
    Feb 6 at 17:57
1
$\begingroup$

then we dot product that normal with one of the 3 vertices

That's incorrect. It's not difficult to construct a scenario where this will result in an incorrect determination of facing.

Imagine a triangle that is nearly edge-on with the view, but is still facing the view. Now, imagine that this triangle has a normal that, when edge-on, is pointed slightly away from the view. Remember: vertex normals on a surface that is supposed to be curved represent the normal at that portion of the curved surface. And therefore they don't have to be aligned with the face normal.

In any case, the math for determining the facing of a triangle happens in window space, not clip-space. It's pretty simple: you get the direction from the first position to the second and the direction from the second to the third. And you take the cross-product of them. If the Z component of the cross product is positive, then the triangle is counter-clockwise, relative to the window. So this doesn't even require the entire cross product; just the Z component (and just the sign of it at that).

$\endgroup$
2
  • 1
    $\begingroup$ actually I'm using about the face normal for the dot product, not the normals that go along with the vertices. But perhaps I'm misunderstanding your point? What do you mean by edge-on? $\endgroup$
    – Harry Kane
    Feb 3 '20 at 18:57
  • $\begingroup$ @HarryKane: "What do you mean by edge-on?" Hold your hand in front of your face, with the palm facing you. Now rotate your wrist 90 degrees. That's edge-on. $\endgroup$ Feb 3 '20 at 20:36
1
$\begingroup$

The OpenGL spec section 14.6.1 spells it out

14.6.1 Basic Polygon Rasterization

The first step of polygon rasterization is to determine if the polygon is back-facing or front-facing. This determination is made based on the sign of the (clipped or unclipped) polygon’s area computed in window coordinates. One way to compute this area is

enter image description here

where 𝑓 = 1 when the clip control origin is LOWER_LEFT and 𝑓 = −1 when the origin is UPPER_LEFT, xiw and yiw are the x and y window coordinates of the ith vertex of the n-vertex polygon (vertices are numbered starting at zero for purposes of this computation) and i ⊕ 1 is (i + 1) mod n. The interpretation of the sign of this value is controlled with

void FrontFace( enum dir );

Setting dir to CCW (corresponding to counter-clockwise orientation of the projected polygon in window coordinates) uses a as computed above. Setting dir to CW (corresponding to clockwise orientation) indicates that the sign of a should be reversed prior to use. Front face determination requires one bit of state, and is initially set to CCW.

If the sign of a (including the possible reversal of this sign as determined by FrontFace) is positive, the polygon is front-facing; otherwise, it is back-facing. This determination is used in conjunction with the CullFace enable bit and mode value to decide whether or not a particular polygon is rasterized. The CullFace mode is set by calling

void CullFace( enum mode );

mode must be FRONT, BACK or FRONT_AND_BACK. Culling is enabled or disabled by calling Enable or Disable with target CULL_FACE. Front-facing polygons are rasterized if either culling is disabled or the CullFace mode is BACK while back facing polygons are rasterized only if either culling is disabled or the CullFace mode is FRONT. The initial setting of the CullFace mode is BACK. Initially, culling is disabled

$\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.