Method for determining the intersection between a triangle/line and a clip rectangle

Method for determining the intersection between a triangle/line and a clip rectangle

Disclosed is a method for determining the intersection between a triangle/line and a clip rectangle. Benefits include improved graphics processing.

Description

      The disclosed method includes algorithm to determine the intersection between a triangle/line and a clip rectangle. The number of clip-points required to be computed are reduced. This method can be applied toward determining the chunks that a polygon intersects in binning.

      Given the coordinates for a triangle and a clip rectangle, a trivial discard is performed if the triangle lies completely outside and on one side of the clip rectangle. The entire plane is broken up into nine regions based on the clip rectangle. The location of the triangle vertices in these regions is determined (see Figure 1). This information is used to minimize the number of clip-points that must be computed to identify intersection.

      If any of the triangle vertices lie inside the clip rectangle (R5) or if a pair of vertices lie in R2 and R8/R4 and R6, then no clip-points must be computed, and an intersection definitely occurs between the triangle and the clip rectangle.

      If a triangle vertex lies in any of R2/R4/R6/R8, then two clip-points must be computed on the top/left/right/bottom boundary of the clip rectangle respectively to determine intersection. If the three vertices lie in R1 and R3 and R9/R1 and R3 and R7/R1 and R7 and R9/R3 and R7 and R9, then two clip-points must be computed on the top or right/top or left/left or bottom/right or bottom boundaries respectively to determine intersection. If either of the two clip-points is valid (an intersect occurs within the clipping boundary) or if the two clip-points are on either side on the clipping boundary, then an intersection occurs between the triangle and the clip rectangle.

      If the triangle vertices lie in R1 and R9/R3 and R7, four clip-points must be computed on a pair of adjacent boundaries. If any of the four clip-points are valid...