Patent ID: 7436414

Claim:
A method for rendering polygons in a virtual environment, prior to a rasterization step, comprising: For a plurality of polygons having at least one occluder polygon and at least one occludee polygon: (a) Adding to a non-winged edge list (NEL) each edge of each occluder polygon within the plurality of polygons; (b) Locating a y value of a next occluder edge discontinuity, wherein the edge discontinuity is determined to occur at each added edge, each removed edge, and each edge crossing of the occluder polygon; (c) If the next occluder edge discontinuity is not an edge crossing: (M) Inserting edges from the NEL that start at the current y value into an active edge list (AEL) in such a way as to preserve edges in the AEL ordered by increasing x values; (N) Retiring from the AEL edges in the NEL that end at the current y value; (d) If the next occluder edge discontinuity is an edge crossing, reordering edges that cross at the current y value in the AEL, wherein the reordering is directed towards preserving edges in the AEL ordered by increasing x values; (e) Advancing a current edge to a next edge in the AEL by skipping intermediary x values to a current x value associated with an edge at the current y value; (f) Maintaining an active surface list at the current x value sorted by z values at each x,y position; (g) If the next edge is coincident with the current edge, repeating steps (e) through (g); (h) If a topmost surface in the active surface list is not different from a previous topmost surface in the active surface list, repeating steps (e) through (h); (i) If there are no more occluder edges in the NEL at the current y value, repeat steps (b) through (i); (j) Repeating steps (b) through (j) while more discontinuities exist within the plurality of polygons; and (k) For each polygon set within the plurality of polygons: (I) Generating boundary boxes, each boundary box surrounding a respective polygon set; (II) Converting each boundary box into a boundary box WEL; and (III) Testing the boundary box WEL against the occluder WEL, and if any part of the boundary box polygons are determined to be un-occluded by the occluder polygons, rendering the occludee polygon set to a display screen.