US 6,285,376 B1Granted

Triangle traversing method and a rasterizer adopting the same

AssigneeSamsung Electronics Co., Ltd.

InventorsSang-gil Choi, Young-cheul Wee

Life of this patent

Estimating the term…

Loading patent…

Abstract

A triangle traversing method includes a primary traversing and a secondary traversing wherein the primary and secondary traversings are orthogonally related to each other. In the primary traversing, a primary proceeding is performed for producing a reference point and if the primary proceeding passes over an edge of the triangle, a shifting is made to the outermost point related to the previous reference point and then the primary proceeding is again performed. In the secondary traversing, outward proceedings from the reference point produced in the primary traversing are repeatedly performed until all corresponding line points within the triangle are traversed. The primary and secondary traversings are repeatedly and alternately performed, until all the points within the triangle are traversed.

Claims9

Dependent claims

In a computer graphics system including a rasterizer, a method of operation of the rasterizer including a method for traversing a triangle defined by three vertices, comprising:

assigning first and second vertices as a starting point and a final point, respectively;
assigning a reference point, a first edge point and a second edge point to the starting point;
conducting primary traversing including 1) shifting the reference point by one pixel in a primary traversing direction 2) producing a plurality of edge function values of the shifted reference point to determine whether the shifted reference point is located within the triangle,
conducting secondary traversing from the shifted reference point including further shifting the shifted reference point in a secondary traversing direction until the points of a line within the triangle connecting first and second edges are all traversed and 2) storing the two outermost points traversed in the secondary traversing as updated first and second edge points, respectively, 3) producing image values of the shifted reference point when the shifted reference point is within the triangle;
and
repeatedly performing said primary traversing and said secondary traversing, until said final point is traversed.

3 more elements

In a computer graphics system including a rasterizer, a method of operation of the rasterizer including a method for traversing a triangle defined by three vertices, the method comprising:

determining first and second vertices of the triangle as a starting point and a final point, respectively, based on a primary traversing direction;
assigning the starting point to a reference point, a first edge point and a second edge point;
performing primary traversing including 1) shifting the reference point by one pixel in the primary traversing direction, 2) determining whether the shifted reference point is within the triangle, and 3) if the shifted reference point is not within the triangle, further shifting the reference point in the primary traversing direction to one of the first and second edge points and in a secondary traversing direction to the other of the first and second edge points.

Dependencies are inferred from the claim text.