Browse Prior Art Database

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

IP.com Disclosure Number: IPCOM000006198D
Publication Date: 2001-Dec-12
Document File: 3 page(s) / 88K

## Publishing Venue

The IP.com Prior Art Database

## Abstract

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

This text was extracted from a Microsoft Word document.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 50% of the total text.

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