User:Echolot-1/sandbox

This is the user sandbox of Echolot-1. A user sandbox is a subpage of the user's user page. It serves as a testing spot and page development space for the user and is not an encyclopedia article. Create or edit your own sandbox here.

Other sandboxes: Main sandbox | Template sandbox

Finished writing a draft article? Are you ready to request review of it by an experienced editor for possible inclusion in Wikipedia? Submit your draft for review!

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 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(P-V_{0}\right)\cdot N\geq 0

where $P$ is the view point, $V 0$ is the first vertex of a triangle and $N$ is it's 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 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(homogenous 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 involutary 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 it's matrix.

References

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

Implementation

References

Further reading