University of California, Berkeley
EECS Dept, CS Division
SLIDE: Scene Language for
Interactive Dynamic Environments
|Prof. Carlo H. Séquin|
Back face culling is when you do not render a polygon because its normal is pointing away from the viewer's eye point. A naive way of preforming this check would be to construct a vector from the eye point to a point on the face and compute the dot product of this line of sight vector and the normal vector. If this scalar is positive then the face is pointing away and consequently can be culled. A more sophisticated way of making this check is to transform the face's normal into the projection space, where the line of sight vector is always the negative Z-axis. Then the check for back face culling is just to see if the Z component of the transformed normal is negative.
The problem now is to find a way to transform face normals, and to find a good representation for the normal to make this transformation easy.
If we have a plane vector n = [a, b, c, d] which describes a plane then for any point p = [x, y, z, 1] in that plane the follow equation holds:
nt p = ax + by + cz + d = 0
If for a point p on the plane, we apply an invertible transformation R to get the transformed point p1, then the plane vector n1 of the transformed plane is given by applying a corresponding transformation Q to the original plane vector n where Q is unknown.
p1 = R p
n1 = Q n
n1t p1 = 0
(Q n)t (R p) = 0
nt Qt R p = 0
Qt R = I
Qt = R-1
Q = (R-1)t
n1 = Q n = (R-1)t n
Transforming normals is very similar to transforming planes. A normal norm can be represented by a vector norm = [a, b, c, 0]. This is equivalent to the plane perpendicular the normal and passing through the origin n = [a, b, c, 0]. If we then transform this plane vector by (R-1)t, we will correctly transform the normal for a certain set of transformations:norm1 = (R-1)t norm
This set of transformations includes our ordinary modelling transformations and the parallel projection transformation where our transformation matrices are always of the form:
For this set of transformations, the d component of n has no effect on the transformed normal direction norm1 because it is multiplied by 0 in the terms for the a1, b1, and c1 components. But our transformations will not stay in this family once we introduce the perspective projection transformation, so we might as well compute and use the full plane equations for our face normals.
So we will represent the normal of face by the best fit plane vector for that face n = [a, b, c, d] where for a point p = [x, y, z, 1] on the face the follow equation holds:nt p = 0
Now when we apply (R-1)
we will correctly transform the plane and consequently the normal. We are only interested in the orientation of this plane equation, so we can forget the d1 component of n1 to get norm1 = [a1, b1, c1]. norm1 can then be normalized to unit length if necessary.
This is very close to being correct, but unfortunately plane equations have one less degree of freedom than normal vectors. So after the plane vector is transformed the [a1, b1, c1] components can equal either norm1 or -norm1. Fortunately, we can distinguish between these two cases by looking at the determinant of the transformation matrix R.If Det(R) > 0 then norm1 = [a1, b1, c1]
Det(R) switches sign for every scale transformation with an odd number of negative scale components.
We will use Newell's algorithm for computing the normal for a polygon loop which may have noisy data. This algorithm comes close to making a least squares best fit, but computes it in a closed form. This algorithm makes use of the fact that the components of the normal of a polygon are proportional to the signed projected areas of the polygon onto the YZ, XZ, and YZ planes. In the figure below, the white polygon's normal norm = [Area(ProjYZ), Area(ProjXZ), Area(ProjXY)].
The areas of the projected polygons can be computed by treating each edge of the projected polygon as a trapezoid with a signed area. In the example below we are looking at the projection onto the XY plane, so the area is proportional to the Z component of the normal. The formula for the area of the trapezoids shown isArea = width * height / 2 = (xi+1 - xi) (yi + yi+1) / 2
The areas of the trazepoids who are constructed from left pointing polygon edges are considered positive, right pointing polygon edges are considered negative, and vertical edges make zero areas. This follows from the area formula. This choice of sign is consistent with our standard counterclockwise polygon loop orientation. In the figure below, positive trapezoids ([P3, P4]) are colored blue, negative trapezoids ([P1, P2] and [P2, P3]) are colored white, and zero trapezoids ([P4, P1]) do not appear. The net area appears in blue and the areas where positive and negative trapezoids cancel appear in lighter blue.
With this in mind, if we are given a polygon described by a list of vertices p1, p2, p3, ... pn. We can find a normal vector norm = (nx, ny, nz) whose components are equal to the signed projected areas of the polygon using these equations:
|(zi + zi+1) (yi+1 - yi)|
|(xi + xi+1) (zi+1 - zi)|
|(yi + yi+1) (xi+1 - xi)|
where xn+1 = x1, yn+1 = y1, and zn+1 = z1.
Then we need to find the d value for the complete plane equation n = [a, b, c, d]. We pin down the specific plane by using a pmean which is the average of the vertex values for x, y, and z. We can then find d using norm and pmean:d = -normt pmean
Now n = [norm, d] = [a, b, c, d] which is the plane equation that best fits the list of vertices of the polygon contour.
This page was originally built by Jordan Smith.
Last modified: Monday, 07-Oct-2002 18:27:00 PDT