The Warnock area-subdivision algorithm solves the hidden-surface removal problem for polygonal faces by recursively subdividing a rectangular area of the screen until the depth comparisons within these rectangular regions allow for trivial depth comparisons that determine if the entire rectangle can be drawn with the frontmost polygon or if the entire rectangle can be filled with the background color. This method works at image precision (since it effectivly subdivides the screen or viewport to the pixel level if necessary) to simultaneously clip to the viewport, remove hidden surfaces, scan-convert the polygons, and even clear the framebuffer; however, the depth comparisons with the rectangular regions occur at object precision because the edges of the polygons are compared with the edges of the regions. Nevertheless, this routine does require "projected" polygons so, the world and viewing transformations and the perspective projection must already be applies to the scene (with pseudo-depth values maintained). In addition, Warnock's algorithm does no redundant drawing of pixels; illumination calculations need only be performed on the frontmost pixels since this routine recursively subdivides, to the pixel level if necessary, to ensure that only the "frontmost" polygon "pieces" are drawn. However, Warnock's algorithm still seems to be slower than the other forms of hidden-surface removal because of the many redundant rectangular region overlap and intersection calculations; we will reduce this redundancy later. The algorithm proceeds as follows:

Given a set of convex polygons, start with the entire viewport (the screen or framebuffer in most cases) as the initial rectangle (this hidden-surface removal algorithm is generalized to handle protrusion and cyclic overlap of polygons).

For the current rectangular region do the following:

• If the rectangle has been subdivided to pixel size, check and make depth comparisons for all triangles containing the pixel's center. The rectangular regions are defined by (l,r,t,b) which are the x and y extents in screen or viewport space. When the difference between top and bottom and between left and right is only one, the rectangular region is a pixel in size.
  
• If no triangles contain the pixel's center, set this pixel to the background color (clears out the framebuffer or double buffer - no explicit clearing is required in Warnock's algorithm).
  
• If one or more triangles contain the pixel's center, set this pixel to the color of the "closest" (the pixel is the largest z-value; smallest in the case of a left-handed coordinate system).
  
• If the rectangle is bigger than pixel size, find all of the triangles that overlap the current region:
  
• Bounding Box Testing : First go for a trivial rejection strategy by obtaining 2D bounding boxes for all the polygons. Compare these bounding boxes to the rectangular region for a simpler elimination method. So, given a bounding box for a polygon in the form (bl, br, bt, bb) representing the box's left, right, top, and bottom screen or viewport space coordinates, we can quickly determine is polygons do NOT overlap the current rectangular region defined by (l, r, t, b):

if (bl > r) OR (br < l) OR (bt > b) OR (bb < t) then the polygon clearly does NOT overlap the current region. Remember that the rectangular region and the bounding box are all in screen space; so, the coordinate system is the y-inverted first quadrant of the 2D cartesian coordinate system.

• Edge Testing : The remaining polygons whose bounding boxes do overlap with the rectangular region must be subjected to further more complicated overlap testing strategies since they could either be disjoint or be overlapping. The edge test proceeds as follows:
  
• This tests checks each edge AB of the polygon for intersection with the current rectangular region. We can express the edge AB in parametric form as the ray from A in the direction A to B:

s(t)=A+(B-A)t.

• Now, for example, if we want to check for intersection with the left edge of the rectangular region (x=l), we set the x component of the ray s(t) equal to l and solve for t:

s(t)x = Ax+(Bx-Ax)t = l
t = (l-Ax)/(Bx-Ax)

• If we substitute t back into the ray equation s(t), we will obtain the point of intersection with the left boundary of the rectangular region:

Pt on left boundary = A + (B-A)*[(1-Ax)/(Bx-Ax)]

• Remember that this point only intersects the left boundary of the rectangular region, not necessarily the left edge. It will intersect the actual region only if the edge AB does cross the left boundary and the intersection point's y-value is within the top and bottom bounds:

Pt intersects region if l is between Ax and Bx AND if Pty is between t and b.

Using a similar strategy for finding the intersections with the other sides of the rectangular region, proceed to process the current edge until an intersection with the region is found; if one is not found the edge does not intersect the region. We must repeat this process for all of the edges in the polygon or until an intersection is found. It is important to remember that for efficiency this routine need only find one intersection to prove the the polygon overlaps; if there are no intersections even further testing is required.

If an intersection if found, the region must be subdivided further since no overall decision for the rectangle as a whole can be made.

• By this point the polygon has failed the trivial rejection bounding box test and no intersections exist between its edges and the rectangular region. So now there are three possibilities: the polygon and rectangle could still be disjoint (even though the bounding boxes overlap), the polygon may completely surround the rectangle, or the polygon is completely contained in the rectangle. It is important to realize that the bounding box and edge tests would not uncover these situations.

We proceed to distinguish between these three cases by a general polygon-inside and rectangle-inside test; if both of these test fail (if the polygon is not contained or rectangle is not contained), then the polygon must be disjoint and is not included in further testing for this region.

Polygon-Inside Test : if any corner of the polygon is inside of the rectangle then the whole polygon must be inside. This polygon is referred to as an intersecting polygon.

Rectangle-Inside Test : if any corner of the rectangle is inside the polygon, then the entire rectangle must be inside the polygon. This polygon is referred to as a surrounding polygon.

• All surrounding or intersecting polygons overlap the region and must be subjected to depth comparison checks. So, first of all, we need a way of obtaining a z value for a particular point on the screen.

Remember that the polygons have been transformed and projected with pseudo-depth values associated with each vertex; so we can easily derive the plane equation coefficients for each polygon from the tranformed points. We need the normal and a "D" value to fulfill the point-normal form of the plane: N.P+D=0 (of the form Ax+By+Cz+D=0) where N is the normal to the plane obtained from the cross product of the first three points ABC (AB x AC) and the D value is the distance along the normal to the plane found by substituting the normal N and a point P into the plane equation and solving (note that actually in this form, -D is the distance along the normal to the plane).

Once we have a plane equation N.P+D=0 we can rewrite the equation and solve for z. Since these plane equations were derived from the projected points, the x,y values of the points correspond to the screen or viewport space points, and the resulting z value is a pseudo depth value based on the perspectively warped plane equations:

N.P+D=0
Nx*Px + Ny*Py + Nz*Pz + D = 0
Pz = (-D - Nx*Px - Ny*Py) / Nz

We can save the division by Nz, if we normalize the plane equation coefficients to Nz=1 (divide N and D through by Nz). This seems like a great deal of computation to obtain the plane equations each time we wish to obtain depth values for a region, but we can clearly see that these plane equations need only be computed once immediately after the polygons have been tranformed and projected (before the Warnock algorithm).

• Now that we have a way of obtaining a "depth" value for a particular point on the screen we must perform the depth comparison for all overlapping polygons in the current rectangular region.

Depth Check for Pixel-Sized Rectangular Regions : We can simply compute the depth (using the plane equation) for each overlapping polygon at this pixels x and y, and then simply draw the closest one (largest in a right-handed coordinate system, smallest in a left-handed).

Depth Check for General Rectangular Regions : Remember, we can only make a decision for the region as a whole (to draw or subdivide in this case), and so since we are also depth-checking intersecting polygons (not just surrounding) we can only draw if a surrounding polygon occludes all of the others. For all overlapping polygons (surrounding or intersecting), we can compute the depth of their respective planes at each of the rectangular region's corners. If one of the surrounding polygons has depth values at the four corners "closer" than all of other polygon's depth values, then this triangle is definitely the closest and the rectangular region can be drawn. Otherwise, the region must be subdivided.