Back-face culling

Last updated March 11, 2024

In computer graphics, back-face culling determines whether a polygon 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.

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_{2}-V_{0}\right)\times \left(V_{1}-V_{0}\right)

Since cross product is anticommutative, 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)

Since vertex ordering is chosen such that front-facing triangles have clockwise winding, $N$ defined as above is the normal directed outward from the object.

If the points are already in view space, $P$ can be assumed to be $(0, 0, 0)$ , the origin, simplifying the above inequality:

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.

Related Research Articles

In geometry, a bipyramid, dipyramid, or double pyramid is a polyhedron formed by fusing two pyramids together base-to-base. The polygonal base of each pyramid must therefore be the same, and unless otherwise specified the base vertices are usually coplanar and a bipyramid is usually symmetric, meaning the two pyramids are mirror images across their common base plane. When each apex of the bipyramid is on a line perpendicular to the base and passing through its center, it is a right bipyramid; otherwise it is oblique. When the base is a regular polygon, the bipyramid is also called regular.

<span class="mw-page-title-main">Tetrahedron</span> Polyhedron with 4 faces

In geometry, a tetrahedron, also known as a triangular pyramid, is a polyhedron composed of four triangular faces, six straight edges, and four vertices. The tetrahedron is the simplest of all the ordinary convex polyhedra.

In Euclidean geometry, an affine transformation or affinity is a geometric transformation that preserves lines and parallelism, but not necessarily Euclidean distances and angles.

In mathematics, a dihedral group is the group of symmetries of a regular polygon, which includes rotations and reflections. Dihedral groups are among the simplest examples of finite groups, and they play an important role in group theory, geometry, and chemistry.

In linear algebra, an orthogonal matrix, or orthonormal matrix, is a real square matrix whose columns and rows are orthonormal vectors.

In geometry, a normal is an object that is perpendicular to a given object. For example, the normal line to a plane curve at a given point is the line perpendicular to the tangent line to the curve at the point.

In linear algebra and the theory of matrices, the Schur complement of a block matrix is defined as follows.

In mathematics, the matrix exponential is a matrix function on square matrices analogous to the ordinary exponential function. It is used to solve systems of linear differential equations. In the theory of Lie groups, the matrix exponential gives the exponential map between a matrix Lie algebra and the corresponding Lie group.

In linear algebra, linear transformations can be represented by matrices. If $is a linear transformation mapping to and is a column vector with entries, then$

In linear algebra, a rotation matrix is a transformation matrix that is used to perform a rotation in Euclidean space. For example, using the convention below, the matrix

In geometry, Euler's rotation theorem states that, in three-dimensional space, any displacement of a rigid body such that a point on the rigid body remains fixed, is equivalent to a single rotation about some axis that runs through the fixed point. It also means that the composition of two rotations is also a rotation. Therefore the set of rotations has a group structure, known as a rotation group.

The computer graphics pipeline, also known as the rendering pipeline or graphics pipeline, is a framework within computer graphics that outlines the necessary procedures for transforming a three-dimensional (3D) scene into a two-dimensional (2D) representation on a screen. Once a 3D model is generated, whether it's for a video game or any other form of 3D computer animation, the graphics pipeline converts the model into a visually perceivable format on the computer display. Due to the dependence on specific software, hardware configurations, and desired display attributes, a universally applicable graphics pipeline does not exist. Nevertheless, graphics application programming interfaces (APIs), such as Direct3D and OpenGL, were developed to standardize common procedures and oversee the graphics pipeline of a given hardware accelerator. These APIs provide an abstraction layer over the underlying hardware, relieving programmers from the need to write code explicitly targeting various graphics hardware accelerators like AMD, Intel, Nvidia, and others.

In geometry, the circumscribed circle or circumcircle of a triangle is a circle that passes through all three vertices. The center of this circle is called the circumcenter of the triangle, and its radius is called the circumradius. The circumcenter is the point of intersection between the three perpendicular bisectors of the triangle's sides, and is a triangle center.

The Rayleigh–Ritz method is a direct numerical method of approximating eigenvalues, originated in the context of solving physical boundary value problems and named after Lord Rayleigh and Walther Ritz.

<span class="mw-page-title-main">Geometry processing</span>

Geometry processing is an area of research that uses concepts from applied mathematics, computer science and engineering to design efficient algorithms for the acquisition, reconstruction, analysis, manipulation, simulation and transmission of complex 3D models. As the name implies, many of the concepts, data structures, and algorithms are directly analogous to signal processing and image processing. For example, where image smoothing might convolve an intensity signal with a blur kernel formed using the Laplace operator, geometric smoothing might be achieved by convolving a surface geometry with a blur kernel formed using the Laplace-Beltrami operator.

In mathematics, an orientation of a curve is the choice of one of the two possible directions for travelling on the curve. For example, for Cartesian coordinates, the $x$ -axis is traditionally oriented toward the right, and the $y$ -axis is upward oriented.

In computer graphics, a triangle strip is a subset of triangles in a triangle mesh with shared vertices, and is a more memory-efficient method of storing information about the mesh. They are more efficient than un-indexed lists of triangles, but usually equally fast or slower than indexed triangle lists. The primary reason to use triangle strips is to reduce the amount of data needed to create a series of triangles. The number of vertices stored in memory is reduced from $3 N$ to $N + 2$ , where $N$ is the number of triangles to be drawn. This allows for less use of disk space, as well as making them faster to load into RAM.

Camera resectioning is the process of estimating the parameters of a pinhole camera model approximating the camera that produced a given photograph or video; it determines which incoming light ray is associated with each pixel on the resulting image. Basically, the process determines the pose of the pinhole camera.

In statistics, Bayesian multivariate linear regression is a Bayesian approach to multivariate linear regression, i.e. linear regression where the predicted outcome is a vector of correlated random variables rather than a single scalar random variable. A more general treatment of this approach can be found in the article MMSE estimator.

The direct-quadrature-zerotransformation or zero-direct-quadraturetransformation is a tensor that rotates the reference frame of a three-element vector or a three-by-three element matrix in an effort to simplify analysis. The DQZ transform is the product of the Clarke transform and the Park transform, first proposed in 1929 by Robert H. Park.

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 page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[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.

[1]

[2]