World Library  
Flag as Inappropriate
Email this Article

Back-face culling

Article Id: WHEBN0001874639
Reproduction Date:

Title: Back-face culling  
Author: World Heritage Encyclopedia
Language: English
Subject: 3D rendering, Noclip mode, Hidden surface determination, Desktop Window Manager
Collection: 3D Rendering, Computer Graphics Algorithms
Publisher: World Heritage Encyclopedia
Publication
Date:
 

Back-face culling

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

In computer graphics, back-face culling determines whether a polygon of a graphical object is visible. 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 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 which are covered from the viewpoint by other visible polygons.

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 \ge 0

where P is the view point, V0 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 V0

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 \ge 0

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

Another method exists based on reflection parity, which is more appropriate for two dimensions where 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 into it

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 odd number of reflections (facing the opposite way of unit triangle)

\left| M \right| < 0

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), even number of reflections will leave triangle facing the same side, as if no reflections were applied at all. An odd number of reflections will leave triangle facing the other side, as if exactly after one reflection. Transformations containing an odd number of reflections always have negative scaling factor, likewise scaling factor is positive if there are no reflections or even number of them. Scaling factor of a transformation is computed by determinant of its matrix.

References

  1. ^ 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.

Further reading

  • Geometry Culling in 3D Engines, by Pietari Laurila
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 


Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.