Back to results
US 7,253,816 B2Granted
Computer graphics acceleration method and apparatus for evaluating whether points are inside a triangle
AssigneeSTMicroelectronics S.r.l.
InventorToni Brkic
Life of this patent
Estimating the term…
Abstract
A computer graphics accelerator apparatus and method determines whether a pixel at predetermined pixel co-ordinates in an area being rasterized is within a triangle defining a sub-area of the area. The coordinate system in relation to which the triangle is defined is translated such that the pixel co-ordinates are disposed at the origin of the coordinate system. Determinants of matrices based on at least two of the coordinate values of at least two of the vertices are calculated and their signs compared. Based on this comparison a determination as to pixel location with respect to the triangle may be made.
Claims28
A method for displaying a pixel, comprising:
- determining whether a pixel at predetermined pixel co-ordinates in an area being rasterized is within a triangle defined by first, second and third coordinate values representing the triangle's vertices, wherein determining comprises the steps of:
- translating a coordinate system in relation to which the triangle is defined, such that the pixel co-ordinates are disposed at an origin of the coordinate system;
- calculating determinants of matrices defined by the coordinate values of at least two of the vertices;
- identifying the signs of the determinants;
- and
- identifying that the pixel is within the triangle on the basis of the signs of the determinants;
- displaying the pixel if the pixel is within the triangle;
- and
- repeating the step of determining for each one of a plurality of pixels in the area being rasterized.
6 more elements
A method for generating an output, comprising:
- determining whether a pixel at predetermined pixel co-ordinates in an area being rasterized is within a triangle defined by first, second and third coordinate values representing the triangle's vertices, wherein determining comprises the steps of:
- translating a coordinate system in relation to which the triangle is defined, such that the pixel co-ordinates are disposed at an origin of the coordinate system;
- calculating determinants of matrices defined by the coordinate values of at least two of the vertices;
- identifying the signs of the determinants;
- and
- identifying that the pixel is within the triangle on the basis of the signs of the determinants;
- determining the color of the pixel if the pixel is within the triangle;
- writing the color of the pixel to a framebuffer;
- and
- displaying an output of the contents of the framebuffer to the computer display screen;
- and
- repeating the step of determining for each one of a plurality of pixels in the area being rasterized.
9 more elements
Computer graphics accelerator hardware comprising:
- a texture memory containing texture data;
- and
- a graphics accelerator chip configured to:
- determine whether a pixel at predetermined pixel co-ordinates in an area being rasterized is within a triangle defined by first, second, and third coordinate values representing the triangle's vertices, wherein the determination comprises:
- translate a coordinate system in relation to which the triangle is defined, such that the pixel co-ordinates are disposed at the origin of the coordinate system;
- calculate determinants of matrices defined by the coordinate values of at least two of the vertices;
- identify the signs of the determinants;
- and
- identify that the pixel is within the triangle on the basis of the identified signs of the determinants;
- and
- repeat the operation to determine for each one of a plurality of pixels in the area being rasterized;
- wherein the graphics accelerator chip retrieves texture data from the texture memory for each pixel determined to be within the triangle.
9 more elements
A method for displaying a pixel, comprising:
- determining whether a pixel at a predetermined pixel coordinate in an area being rasterized is within a triangle defined by a first, second and third coordinate values representing the vertices of the triangle, wherein determining comprises the steps of:
- translating a coordinate system in relation to which the triangle is defined, such that the predetermined pixel coordinate is disposed at the origin of the coordinate system;
- calculating the determinants of three matrices defined by the coordinate values of the three vertices of the triangle;
- determining the signs of the determinants;
- and
- verifying that the pixel is within the triangle if the signs of the determinants are the same;
- displaying the pixel if the pixel is within the triangle;
- and
- repeating the step of determining for each one of a plurality of pixels in the area being rasterized.
6 more elements
A method for determining whether a pixel at a predetermined pixel coordinate in an area is within a triangle, the triangle being defined by a first, second and third coordinate values representing the vertices of the triangle, comprising the steps of:
- translating a coordinate system in relation to which the triangle is defined, such that the predetermined pixel coordinate is disposed at the origin of the coordinate system;
- calculating the determinants of matrices defined by the coordinate values of at least two of the vertices of the triangle, wherein if each vertex is in a different quadrant of the coordinate system, the matrices for which the determinants are calculated are based on a selected two vertices in diagonally opposite quadrants;
- and
- displaying the pixel if the signs of the determinants are different.
1 more element
A method for determining whether a pixel at a predetermined pixel coordinate in an area is within a triangle, the triangle being defined by a first, second and third coordinate values representing the vertices of the triangle, comprising the steps of:
- translating a coordinate system in relation to which the triangle is defined, such that the predetermined pixel coordinate is disposed at the origin of the coordinate system;
- calculating the determinants of matrices defined by the coordinate values of at least two of the vertices of the triangle, wherein if two vertices are in the same quadrant of the coordinate system, and the other vertex is in a diagonally opposite quadrant, the matrices for which the determinants are calculated are based on a selected two vertices in the same quadrant;
- and
- displaying the pixel if the signs of the determinants are different.
1 more element
A computer-based machine, comprising:
- means for determining whether a pixel having an input pixel coordinate in an area being rasterized is within a triangle defined by an input matrix comprising a coordinate value for each vertex of the triangle, said means for determining comprising:
- translation means operable on the input matrix and the input pixel coordinate for translating the coordinate values comprising the input matrix to a coordinate system having the input pixel coordinate at the origin and outputting a translated matrix;
- and
- determination means operable on the translated matrix for determining whether an area bounded by the triangle defined by the translated matrix includes the origin of the coordinate system, thus placing the pixel within the triangle;
- means for sending a display signal to a monitor;
- and
- wherein said means for determining repeats its operation with respect to each pixel in the area being rasterized.
4 more elements
A computer-based machine for determining whether a pixel having an input pixel coordinate in an area being rasterized is within a triangle defined by an input matrix comprising a coordinate value for each vertex of the triangle, comprising:
- translation means operable on the input matrix and the input pixel coordinate for translating the coordinate values comprising the input matrix to a coordinate system having the input pixel coordinate at the origin and outputting a translated matrix;
- and
- determination means operable on the translated matrix for determining whether an area bounded by the triangle defined by the translated matrix includes the origin of the coordinate system, thus placing the pixel within the triangle, wherein the determination means operates to:
- determine the quadrant location in the coordinate system of the vertices of the triangle;
- calculate the determinants of matrices based on the coordinate values of two of the vertices of the triangle in diagonally opposite quadrants if each vertex is in a different quadrant of the coordinate system;
- means for sending a display signal to a monitor;
- and
- identify that the pixel is within the triangle if the signs of the determinants are different.
5 more elements
A computer-based machine for determining whether a pixel having an input pixel coordinate in an area being rasterized is within a triangle defined by an input matrix comprising a coordinate value for each vertex of the triangle, comprising:
- translation means operable on the input matrix and the input pixel coordinate for translating the coordinate values comprising the input matrix to a coordinate system having the input pixel coordinate at the origin and outputting a translated matrix;
- and
- determination means operable on the translated matrix for determining whether an area bounded by the triangle defined by the translated matrix includes the origin of the coordinate system, thus placing the pixel within the triangle, wherein the determination means operates to:
- determine the quadrant location in the coordinate system of the vertices of the triangle;
- calculate the determinants of matrices based on the coordinate values of two of the vertices of the triangle in the same quadrant if the other vertex is in a diagonally opposite quadrant;
- means for sending a display signal to a monitor;
- and
- identify that the pixel is within the triangle if the signs of the determinants are different.
5 more elements
A method for displaying a pixel, comprising the steps of:
- determining whether a pixel having an input pixel coordinate in an area being rasterized is within a triangle defined by an input matrix comprising a coordinate value for each vertex of the triangle, the step of determining comprising the steps of:
- translating the coordinate values comprising the input matrix to a coordinate system having the input pixel coordinate at the origin and outputting a translated matrix;
- and
- identifying whether an area bounded by the triangle defined by the translated matrix includes the origin of the coordinate system, thus placing the pixel within the triangle;
- displaying the pixel if the pixel is within the triangle;
- and
- repeating the step of determining for each one of a plurality of pixels in the area being rasterized.
4 more elements
Dependencies are inferred from the claim text.