Back-face culling

In computer graphics, back-face culling determines whether a polygon of a graphical object is drawn. It is a step in the graphical pipeline that tests whether the points in the polygon appear in clockwise or counter-clockwise order when projected onto the screen. If the user has specified that front-facing polygons have a clockwise winding, but the polygon projected on the screen has a counter-clockwise winding then it has been rotated to face away from the camera and will not be drawn.

On the left a model without BFC; on the right the same model with BFC: back-faces are removed.

The process makes rendering objects quicker and more efficient by reducing the number of polygons for the program to draw. For example, in a city street scene, there is generally no need to draw the polygons on the sides of the buildings facing away from the camera; they are completely occluded by the sides facing the camera.

In general, back-face culling can be assumed to produce no visible artifact in a rendered scene if it contains only closed and opaque geometry. In scenes containing transparent polygons, rear-facing polygons may become visible through the process of alpha composition. In wire-frame rendering, back-face culling can be used to partially address the problem of hidden-line removal, but only for closed convex geometry.

A related technique is clipping, which determines whether polygons are within the camera's field of view at all.

Another similar technique is Z-culling, also known as occlusion culling, which attempts to skip the drawing of polygons that are covered from the viewpoint by other visible polygons.

In non-realistic renders certain faces can be culled by whether or not they are visible, rather than facing away from the camera. "inverted hull" or "front face culling" can be used to simulate outlines or toon shaders without post-processing effects.[1]

Implementation

One method of implementing back-face culling is by discarding all triangles where the dot product of their surface normal and the camera-to-triangle vector is greater than or equal to zero

\left(V_{0}-P\right)\cdot N\geq 0

where $P$ is the view point, $V 0$ is the first vertex of a triangle and $N$ is its normal, defined as a cross product of two vectors representing sides of the triangle adjacent to $V 0$

N=\left(V_{1}-V_{0}\right)\times \left(V_{2}-V_{0}\right)

Since cross product is non-commutative, defining the normal in terms of cross product allows to specify normal direction relative to triangle surface using vertex order(winding):

\left(V_{1}-V_{0}\right)\times \left(V_{2}-V_{0}\right)=-\left(V_{2}-V_{0}\right)\times \left(V_{1}-V_{0}\right)

If points are already in view space, $P$ can be assumed to be $(0, 0, 0)$ , the origin.

-V_{0}\cdot N\geq 0

It is also possible to use this method in projection space by representing the above inequality as a determinant of a matrix and applying the projection matrix to it.[2]

Another method exists based on reflection parity, which is more appropriate for two dimensions where the surface normal cannot be computed (also known as CCW check).

Let a unit triangle in two dimensions (homogeneous coordinates) be defined as

U_{0}={\begin{bmatrix}0\\0\\1\end{bmatrix}},U_{1}={\begin{bmatrix}1\\0\\1\end{bmatrix}},U_{2}={\begin{bmatrix}0\\1\\1\end{bmatrix}}

Then for some other triangle, also in two dimensions,

V_{0}={\begin{bmatrix}x_{0}\\y_{0}\\1\end{bmatrix}},V_{1}={\begin{bmatrix}x_{1}\\y_{1}\\1\end{bmatrix}},V_{2}={\begin{bmatrix}x_{2}\\y_{2}\\1\end{bmatrix}}

define a matrix that transforms the unit triangle:

M={\begin{bmatrix}x_{1}-x_{0}&x_{2}-x_{0}&x_{0}\\y_{1}-y_{0}&y_{2}-y_{0}&y_{0}\\0&0&1\end{bmatrix}}

so that:

MU_{0}=V_{0}

MU_{1}=V_{1}

MU_{2}=V_{2}

Discard the triangle if matrix $M$ contained an odd number of reflections (facing the opposite way of the unit triangle)

\left|M\right|<0

The unit triangle is used as a reference and transformation $M$ is used as a trace to tell if vertex order is different between two triangles. The only way vertex order can change in two dimensions is by reflection. Reflection is an example of involutory function (with respect to vertex order), therefore an even number of reflections will leave the triangle facing the same side, as if no reflections were applied at all. An odd number of reflections will leave the triangle facing the other side, as if exactly after one reflection. Transformations containing an odd number of reflections always have a negative scaling factor, likewise, the scaling factor is positive if there are no reflections or even a number of them. The scaling factor of a transformation is computed by determinant of its matrix.

References

Hoeven, van der, Jorick. "Non-Photorealism in Interactive Rendering Systems" (PDF). Archived from the original (PDF) on 2021-11-02. Retrieved 2023-08-10.
David H. Eberly (2006). 3D Game Engine Design: A Practical Approach to Real-Time Computer Graphics, p. 69. Morgan Kaufmann Publishers, United States. ISBN 0122290631.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Hoeven, van der, Jorick. "Non-Photorealism in Interactive Rendering Systems" (PDF). Archived from the original (PDF) on 2021-11-02. Retrieved 2023-08-10.

[2] David H. Eberly (2006). 3D Game Engine Design: A Practical Approach to Real-Time Computer Graphics, p. 69. Morgan Kaufmann Publishers, United States. ISBN 0122290631.