US5905500A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for adaptive nonlinear projective rendering
Assignee: Seiko Epson Corp
•
Filing: 1997-03-18
•
Granted: 1999-05-18
•
Expires: 2017-03-18
Abstract
Abstract In three-dimensional graphics rendering, a method of texture mapping, or shading, applies to triangle-based graphical objects having undergone a perspective transformation. The present invention makes use of linear interpolation for determining the appropriate mapping for the interior points of each triangle, thus reducing the computation-intensive mathematical calculations otherwise required. In order to minimize visual artifacts due to high interpolation errors, the borders of each triangle are tested against a predetermined threshold, and the triangle subdivided if any of the borders contain a maximum error which exceeds the threshold. The subdivision continues until all triangle sides have maximum errors that are less than the threshold value. Linear interpolation is then used to determine all mappings for the sides and interior points of the triangle. In alternative embodiments, the triangle is subdivided without using recursive methods. In one non-recursive method, the entire triangle is subdivided uniformly based on the necessary number of segments into which the triangle sides must be broken to keep the maximum error below the threshold. In another non-recursive method, w-isosceles triangles are subdivided into trapezoids, each of which is then subdivided into w-isosceles, and mostly geometrically isosceles, triangles.
Inventors
- 👤 Yakov Kamen
- 👤 Leon Shirman
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-04 01:44
CPC Classifications
G; G06; G06T; G06T15/00; G06T15/10; G06T17/00; G06T17/20
Claims Analysis
Total Claims: 70
Claim 1
Independent Claim
126 words
A method of mapping a graphical surface model, comprising a plurality of model values, onto a polygon of a perspective projection of a polygon-based, graphically-represented object defined by points within an object coordinate system, the method comprising the steps of: a) subdividing the polygon into subpolygons each having a plurality of sides and a plurality of vertices, the subdivision being such that, given exact model values to be assigned to the vertices, the determination of model values by linear interpolation over the length of any one subpolygon side does not produce an interpolation error which exceeds a predetermined threshold value; b) determining the exact model values for the vertices of the sub-polygons; and c) determining the model values corresponding to the non-vertex object points by interpolation.
Claim 2
Independent Claim
126 words
A method of mapping a graphical surface model, comprising a plurality of model values, onto a polygon of a perspective projection of a polygon-based, graphically-represented object defined by points within an object coordinate system, the method comprising the steps of: a) subdividing the polygon into subpolygons each having a plurality of sides and a plurality of vertices, the subdivision being such that, given exact model values to be assigned to the vertices, the determination of model values by linear interpolation over the length of any one subpolygon side does not produce an interpolation error which exceeds a predetermined threshold value; b) determining the exact model values for the vertices of the sub-polygons; and c) determining the model values corresponding to the non-vertex object points by interpolation.
Claim 3
Dependent Claim
12 words
A method according to claim 1 wherein the polygon is a triangle.
Claim 4
Dependent Claim
95 words
A method according to claim 1 wherein, for a given subpolygon, the plurality of vertices includes a first vertex P 0 having object coordinates (x 0 , y 0 , w 0 ) and a second vertex P 1 having object coordinates (x 1 , y 1 , w 1 ), and wherein determining the maximum error for a subpolygon side bounded by vertex P 0 and vertex P 1 comprises finding a maximum error e such that: e=((x.sub.1 -x.sub.0).sup.2 +(y.sub.1 -y.sub.0).sup.2).sup.1/2 ·(1-√α)/(1+√α) where α=min(w 0 , w 1 )/max(w 0 , w 1 ).
Claim 5
Dependent Claim
39 words
A method according to claim 1 wherein subdividing the polygon further comprises subdividing the polygon such that a new vertex is created along a first side of the polygon for which a maximum interpolation error exceeds the threshold value.
Claim 6
Dependent Claim
24 words
A method according to claim 4 wherein said new vertex is located substantially at the point of maximum interpolation error for the first side.
Claim 7
Dependent Claim
67 words
A method according to claim 5 wherein the first side is bounded by a first vertex P 0 having object coordinates (x 0 , y 0 , w 0 ) and a second vertex P 1 having object coordinates (x 1 , y 1 , w 1 ), and wherein the point of maximum error t maxerror for the first side is determined as: t.sub.maxerror =1/(1+√(w.sub.1 /w.sub.0)).
Claim 8
Dependent Claim
20 words
A method according to claim 4 wherein said new vertex is located substantially at the midpoint of the first side.
Claim 9
Dependent Claim
40 words
A method according to claim 1 wherein the polygon is a triangle and subdividing the triangle comprises subdividing the triangle into four triangles such that a new vertex is created at the midpoint of each of the original triangle sides.
Claim 10
Dependent Claim
12 words
A method according to claim 1 wherein said interpolation is linear interpolation.
Claim 11
Independent Claim
156 words
A method of mapping a graphical surface model, comprising a plurality of model values, onto a triangle of a perspective projection of a triangle-based, graphically-represented object defined by points within an object coordinate system, the method comprising the steps of: a) obtaining the exact model values for each vertex of the triangle; b) determining, for each side of the triangle, a maximum interpolation error which would result from the use of interpolation, based on the model values of the vertices at the endpoints of that side, to assign model values to all object points along that triangle side; c) comparing the maximum error for each side to a predetermined threshold value; d) subdividing the triangle into subtriangles and repeating steps (a), (b), (c) and (d) for each subtriangle if the maximum error for any of the triangle sides exceeds the threshold value; and e) determining the model values corresponding to the non-vertex object points using interpolation.
Claim 12
Independent Claim
156 words
A method of mapping a graphical surface model, comprising a plurality of model values, onto a triangle of a perspective projection of a triangle-based, graphically-represented object defined by points within an object coordinate system, the method comprising the steps of: a) obtaining the exact model values for each vertex of the triangle; b) determining, for each side of the triangle, a maximum interpolation error which would result from the use of interpolation, based on the model values of the vertices at the endpoints of that side, to assign model values to all object points along that triangle side; c) comparing the maximum error for each side to a predetermined threshold value; d) subdividing the triangle into subtriangles and repeating steps (a), (b), (c) and (d) for each subtriangle if the maximum error for any of the triangle sides exceeds the threshold value; and e) determining the model values corresponding to the non-vertex object points using interpolation.
Claim 13
Dependent Claim
76 words
A method according to claim 10 wherein, for a side having a vertex P 1 with object coordinates (x 1 , y 1 , w 1 ) at a first end, and a vertex P 0 with object coordinates (x 0 , y 0 , w 0 ) at a second end, the maximum error for that side is: e=((x.sub.1 -x.sub.0).sup.2 +(y.sub.1 -y.sub.0).sup.2).sup.1/2 ·(1-√α)/(1+√α) where α=min(w 0 , w 1 )/max(w 0 , w 1 ).
Claim 14
Dependent Claim
84 words
A method according to claim 10 wherein subdividing the triangle comprises creating a new vertex substantially at the point of maximum interpolation error along one of the triangle sides, and wherein, if the side has a vertex P 1 at a first end with a homogeneous coordinate w 1 , and a vertex P 2 at a second end with a homogeneous coordinate w 2 , the point of maximum interpolation error t maxerror for that side is determined as: t.sub.maxerror =1/(1+√(w.sub.1 /w.sub.0)). 13.
Claim 15
Dependent Claim
28 words
A method according to claim 10 wherein subdividing the triangle comprises creating a new vertex substantially at the midpoint of a triangle side along which it is created.
Claim 16
Dependent Claim
34 words
A method according to claim 10 wherein subdividing the triangle comprises subdividing the triangle into four triangles such that a new vertex is created at the midpoint of each of the original triangle sides.
Claim 17
Independent Claim
174 words
A method of mapping a graphical surface model, comprising a plurality of model values, onto a triangle of a perspective projection of a triangle-based, graphically-represented object defined by points within an object coordinate system, the triangle having a plurality of sides and a plurality of vertices, the method comprising the steps of: a) creating new vertices along the triangle sides such that each of the triangle sides is divided into a plurality of sections, the length of each section being such that, given exact model values to be assigned to the vertices, the determination of model values by linear interpolation over the length of any one section does not produce an error which exceeds the threshold value; b) interconnecting the new vertices with line segments parallel to the original triangle sides, such as to create interior subtriangles having vertices at crossing points between the line segments; c) determining the exact model values for each of the vertices of the subtriangles; and d) determining the model values corresponding to the non-vertex object points using interpolation.
Claim 18
Independent Claim
174 words
A method of mapping a graphical surface model, comprising a plurality of model values, onto a triangle of a perspective projection of a triangle-based, graphically-represented object defined by points within an object coordinate system, the triangle having a plurality of sides and a plurality of vertices, the method comprising the steps of: a) creating new vertices along the triangle sides such that each of the triangle sides is divided into a plurality of sections, the length of each section being such that, given exact model values to be assigned to the vertices, the determination of model values by linear interpolation over the length of any one section does not produce an error which exceeds the threshold value; b) interconnecting the new vertices with line segments parallel to the original triangle sides, such as to create interior subtriangles having vertices at crossing points between the line segments; c) determining the exact model values for each of the vertices of the subtriangles; and d) determining the model values corresponding to the non-vertex object points using interpolation.
Claim 19
Dependent Claim
47 words
A method according to claim 15 further comprising omitting steps a-c if, for each side of the triangle, no interpolation error which would result from the use of interpolation in assigning model values to object points along that side of the triangle would exceed the threshold value.
Claim 20
Independent Claim
188 words
A method of mapping a graphical surface model, comprising a plurality of model values, onto a w-isosceles triangle of a perspective projection of a triangle-based, graphically-represented object defined by points within an object coordinate system, the triangle having two sides and a base, the base being bounded by two vertices each having a homogeneous coordinate w of the same value, the method comprising the steps of: a) dividing the triangle into a plurality of trapezoids each having four vertices, two bases parallel to the base of the triangle, and two sides, each of which is colinear with one of the triangle sides, the length of the trapezoid sides being such that, given the exact model values to be assigned to the vertices of the trapezoid, the interpolation of model values along the sides of the trapezoid results in no interpolation error that exceeds a predetermined threshold value; b) determining the exact model values for the vertices of each trapezoid; c) subdividing the interior of each trapezoid into a plurality of w-isosceles subtriangles; and d) determining the model values for the remaining object points of the triangle by interpolation.
Claim 21
Independent Claim
188 words
A method of mapping a graphical surface model, comprising a plurality of model values, onto a w-isosceles triangle of a perspective projection of a triangle-based, graphically-represented object defined by points within an object coordinate system, the triangle having two sides and a base, the base being bounded by two vertices each having a homogeneous coordinate w of the same value, the method comprising the steps of: a) dividing the triangle into a plurality of trapezoids each having four vertices, two bases parallel to the base of the triangle, and two sides, each of which is colinear with one of the triangle sides, the length of the trapezoid sides being such that, given the exact model values to be assigned to the vertices of the trapezoid, the interpolation of model values along the sides of the trapezoid results in no interpolation error that exceeds a predetermined threshold value; b) determining the exact model values for the vertices of each trapezoid; c) subdividing the interior of each trapezoid into a plurality of w-isosceles subtriangles; and d) determining the model values for the remaining object points of the triangle by interpolation.
Claim 22
Dependent Claim
21 words
A method according to claim 17 wherein step (c) further comprises forming a plurality of geometrically isosceles subtriangles within each trapezoid.
Claim 23
Dependent Claim
47 words
A method according to claim 17 further comprising omitting steps a-c if, for each side of the triangle, no interpolation error which would result from the use of interpolation in assigning model values to object points along that side of the triangle would exceed the threshold value.
Claim 24
Dependent Claim
24 words
A method according to claim 17 further comprising creating said w-isosceles triangle by dividing a triangle which is not w-isosceles into two w-isosceles triangles.
Claim 25
Dependent Claim
41 words
A method according to claim 17 wherein step (d) comprises first determining the model values for the vertices of the isosceles subtriangles by interpolation, and thereafter determining the model values for the other remaining object points of the triangle by interpolation.
Claim 26
Dependent Claim
147 words
A computer program product for mapping a graphical surface model, comprising a plurality of model values, onto a polygon of a perspective projection of a polygon-based, graphically-represented object defined by points within an object coordinate system, the program code including: program code for performing the step (a) of subdividing the polygon into subpolygons each having a plurality of sides and a plurality of vertices, the subdivision being such that, given exact model values to be assigned to the vertices, the determination of model values by linear interpolation over the length of any one subpolygon side does not produce an interpolation error which exceeds a predetermined threshold value; program code for performing the step (b) of determining the exact model values for the vertices of the sub-polygons; and program code for performing the step (c) of determining the model values corresponding to the non-vertex object points by interpolation.
Claim 27
Dependent Claim
147 words
A computer program product for mapping a graphical surface model, comprising a plurality of model values, onto a polygon of a perspective projection of a polygon-based, graphically-represented object defined by points within an object coordinate system, the program code including: program code for performing the step (a) of subdividing the polygon into subpolygons each having a plurality of sides and a plurality of vertices, the subdivision being such that, given exact model values to be assigned to the vertices, the determination of model values by linear interpolation over the length of any one subpolygon side does not produce an interpolation error which exceeds a predetermined threshold value; program code for performing the step (b) of determining the exact model values for the vertices of the sub-polygons; and program code for performing the step (c) of determining the model values corresponding to the non-vertex object points by interpolation.
Claim 28
Dependent Claim
44 words
A computer program product according to claim 22 wherein the program code for performing step (a) comprises program code for subdividing the polygon such that a new vertex is created along a first side for which the maximum interpolation error exceeds the threshold value.
Claim 29
Dependent Claim
33 words
A computer program product according to claim 22 wherein the program code for performing step (a) further comprises program code for locating the new vertex substantially at the midpoint of the first side.
Claim 30
Dependent Claim
51 words
A computer program product according to claim 22 wherein the polygon is a triangle, and wherein the program code for performing step (a) further comprises program code for subdividing the triangle into four triangles such that a new vertex is created at the midpoint of each of the original triangle sides.
Claim 31
Dependent Claim
190 words
A computer program product for mapping a graphical surface model, comprising a plurality of model values, onto a triangle of a perspective projection of a triangle-based, graphically-represented object defined by points within an object coordinate system, the program code including: program code for performing the step (a) of obtaining the exact model values for each vertex of the triangle; program code for performing the step (b) of determining, for each side of the triangle, a maximum interpolation error which would result from the use of interpolation, based on the model values of the vertices at the endpoints of that side, to assign model values to object points along that triangle side; program code for performing the step (c) of comparing the maximum error for each side to a predetermined threshold value; program code for performing the step (d) of subdividing the triangle into subtriangles and repeating steps (a), (b), (c) and (d) for each subtriangle, if the maximum error for any of the triangle sides exceeds the threshold value; and program code for performing the step (e) of determining the model values corresponding to the non-vertex object points using interpolation.
Claim 32
Dependent Claim
190 words
A computer program product for mapping a graphical surface model, comprising a plurality of model values, onto a triangle of a perspective projection of a triangle-based, graphically-represented object defined by points within an object coordinate system, the program code including: program code for performing the step (a) of obtaining the exact model values for each vertex of the triangle; program code for performing the step (b) of determining, for each side of the triangle, a maximum interpolation error which would result from the use of interpolation, based on the model values of the vertices at the endpoints of that side, to assign model values to object points along that triangle side; program code for performing the step (c) of comparing the maximum error for each side to a predetermined threshold value; program code for performing the step (d) of subdividing the triangle into subtriangles and repeating steps (a), (b), (c) and (d) for each subtriangle, if the maximum error for any of the triangle sides exceeds the threshold value; and program code for performing the step (e) of determining the model values corresponding to the non-vertex object points using interpolation.
Claim 33
Dependent Claim
203 words
A computer program product for mapping a graphical surface model, comprising a plurality of model values, onto a triangle of a perspective projection of a triangle-based, graphically-represented object defined by points within an object coordinate system, the triangle having a plurality of sides and a plurality of vertices, the program code including: program code for performing the step (a) of creating new vertices along the triangle sides such that each of the triangle sides is divided into a plurality of sections, the length of each section being such that, given exact model values to be assigned to the vertices, the determination of model values by linear interpolation over the length of any one section does not produce an error which exceeds the threshold value; program code for performing the step (b) of interconnecting the new vertices with line segments parallel to the original triangle sides, such as to create interior subtriangles having vertices at crossing points between the line segments; program code for performing the step (c) of determining the exact model values for each of the vertices of the subtriangles; and program code for performing the step (d) of determining the model values corresponding to each non-vertex object point using linear interpolation.
Claim 34
Dependent Claim
203 words
A computer program product for mapping a graphical surface model, comprising a plurality of model values, onto a triangle of a perspective projection of a triangle-based, graphically-represented object defined by points within an object coordinate system, the triangle having a plurality of sides and a plurality of vertices, the program code including: program code for performing the step (a) of creating new vertices along the triangle sides such that each of the triangle sides is divided into a plurality of sections, the length of each section being such that, given exact model values to be assigned to the vertices, the determination of model values by linear interpolation over the length of any one section does not produce an error which exceeds the threshold value; program code for performing the step (b) of interconnecting the new vertices with line segments parallel to the original triangle sides, such as to create interior subtriangles having vertices at crossing points between the line segments; program code for performing the step (c) of determining the exact model values for each of the vertices of the subtriangles; and program code for performing the step (d) of determining the model values corresponding to each non-vertex object point using linear interpolation.
Claim 35
Dependent Claim
52 words
A computer program product according to claim 27 further comprising program code for omitting steps (a)-(c) if, for each side of the triangle, no interpolation error which would result from the use of interpolation in assigning model values to object points along that side of the triangle would exceed the threshold value.
Claim 36
Dependent Claim
212 words
A computer program product for mapping a graphical surface model, comprising a plurality of model values, onto a w-isosceles triangle of a perspective projection of a triangle-based, graphically-represented object defined by points within an object coordinate system, the triangle having two sides and a base, the base being bounded by two vertices each having a homogeneous coordinate w of the same value, the program code including: program code for performing step (a) of dividing the triangle into a plurality of trapezoids each having four vertices, two bases parallel to the base of the triangle, and two sides, each of which is colinear with one of the triangle sides, the length of the trapezoid sides being such that, given the exact model values to be assigned to the vertices of the trapezoid, the interpolation of model values along the sides of the trapezoid results in no interpolation error that exceeds a predetermined threshold value; program code for performing step (b) of determining the exact model values for the vertices of each trapezoid; program code for performing step (c) of subdividing the interior of each trapezoid into a plurality of w-isosceles subtriangles; and program code for performing step (d) of determining the model values for the remaining object points of the triangle by interpolation.
Claim 37
Dependent Claim
212 words
A computer program product for mapping a graphical surface model, comprising a plurality of model values, onto a w-isosceles triangle of a perspective projection of a triangle-based, graphically-represented object defined by points within an object coordinate system, the triangle having two sides and a base, the base being bounded by two vertices each having a homogeneous coordinate w of the same value, the program code including: program code for performing step (a) of dividing the triangle into a plurality of trapezoids each having four vertices, two bases parallel to the base of the triangle, and two sides, each of which is colinear with one of the triangle sides, the length of the trapezoid sides being such that, given the exact model values to be assigned to the vertices of the trapezoid, the interpolation of model values along the sides of the trapezoid results in no interpolation error that exceeds a predetermined threshold value; program code for performing step (b) of determining the exact model values for the vertices of each trapezoid; program code for performing step (c) of subdividing the interior of each trapezoid into a plurality of w-isosceles subtriangles; and program code for performing step (d) of determining the model values for the remaining object points of the triangle by interpolation.
Claim 38
Dependent Claim
52 words
A computer program product according to claim 29 further comprising program code for omitting steps (a)-(c) if, for each side of the triangle, no interpolation error which would result from the use of interpolation in assigning model values to object points along that side of the triangle would exceed the threshold value.
Claim 39
Dependent Claim
31 words
A computer program product according to claim 29 wherein the program code for performing step (c) further comprises program code for forming a plurality of geometrically isosceles subtriangles within each trapezoid.
Claim 40
Dependent Claim
29 words
A computer program product according to claim 29 further comprising program code for creating said w-isosceles triangle by dividing a triangle which is not w-isosceles into two w-isosceles triangles.
Claim 41
Dependent Claim
156 words
A computer apparatus comprising a storage medium in which is stored program code for mapping a graphical surface model, comprising a plurality of model values, onto a polygon of a perspective projection of a polygon-based, graphically-represented object defined by points within an object coordinate system, the storage medium comprising: program code for performing the step (a) of subdividing the polygon into subpolygons each having a plurality of sides and a plurality of vertices, the subdivision being such that, given exact model values to be assigned to the vertices, the determination of model values by linear interpolation over the length of any one subpolygon side does not produce an interpolation error which exceeds a predetermined threshold value; program code for performing the step (b) of determining the exact model values for the vertices of the sub-polygons; and program code for performing the step (c) of determining the model values corresponding to the non-vertex object points by interpolation.
Claim 42
Dependent Claim
156 words
A computer apparatus comprising a storage medium in which is stored program code for mapping a graphical surface model, comprising a plurality of model values, onto a polygon of a perspective projection of a polygon-based, graphically-represented object defined by points within an object coordinate system, the storage medium comprising: program code for performing the step (a) of subdividing the polygon into subpolygons each having a plurality of sides and a plurality of vertices, the subdivision being such that, given exact model values to be assigned to the vertices, the determination of model values by linear interpolation over the length of any one subpolygon side does not produce an interpolation error which exceeds a predetermined threshold value; program code for performing the step (b) of determining the exact model values for the vertices of the sub-polygons; and program code for performing the step (c) of determining the model values corresponding to the non-vertex object points by interpolation.
Claim 43
Dependent Claim
41 words
Apparatus according to claim 33 wherein the program code for performing step (a) comprises program code for subdividing the polygon such that a new vertex is created along a first side for which the maximum interpolation error exceeds the threshold value.
Claim 44
Dependent Claim
30 words
Apparatus according to claim 33 wherein the program code for performing step (a) further comprises program code for locating the new vertex substantially at the midpoint of the first side.
Claim 45
Dependent Claim
48 words
Apparatus according to claim 33 wherein the polygon is a triangle, and wherein the program code for performing step (a) further comprises program code for subdividing the triangle into four triangles such that a new vertex is created at the midpoint of each of the original triangle sides.
Claim 46
Dependent Claim
199 words
A computer apparatus comprising a storage medium in which is stored program code for mapping a graphical surface model, comprising a plurality of model values, onto a triangle of a perspective projection of a triangle-based, graphically-represented object defined by points within an object coordinate system, the storage medium comprising: program code for performing the step (a) of obtaining the exact model values for each vertex of the triangle; program code for performing the step (b) of determining, for each side of the triangle, a maximum interpolation error which would result from the use of interpolation, based on the model values of the vertices at the endpoints of that side, to assign model values to object points along that triangle side; program code for performing the step (c) of comparing the maximum error for each side to a predetermined threshold value; program code for performing the step (d) of subdividing the triangle into subtriangles and repeating steps (a), (b), (c) and (d) for each subtriangle, if the maximum error for any of the triangle sides exceeds the threshold value; and program code for performing the step (e) of determining the model values corresponding to the non-vertex object points using interpolation.
Claim 47
Dependent Claim
199 words
A computer apparatus comprising a storage medium in which is stored program code for mapping a graphical surface model, comprising a plurality of model values, onto a triangle of a perspective projection of a triangle-based, graphically-represented object defined by points within an object coordinate system, the storage medium comprising: program code for performing the step (a) of obtaining the exact model values for each vertex of the triangle; program code for performing the step (b) of determining, for each side of the triangle, a maximum interpolation error which would result from the use of interpolation, based on the model values of the vertices at the endpoints of that side, to assign model values to object points along that triangle side; program code for performing the step (c) of comparing the maximum error for each side to a predetermined threshold value; program code for performing the step (d) of subdividing the triangle into subtriangles and repeating steps (a), (b), (c) and (d) for each subtriangle, if the maximum error for any of the triangle sides exceeds the threshold value; and program code for performing the step (e) of determining the model values corresponding to the non-vertex object points using interpolation.
Claim 48
Dependent Claim
212 words
A computer apparatus comprising a storage medium in which is stored program code for mapping a graphical surface model, comprising a plurality of model values, onto a triangle of a perspective projection of a triangle-based, graphically-represented object defined by points within an object coordinate system, the triangle having a plurality of sides and a plurality of vertices, the storage medium comprising: program code for performing the step (a) of creating new vertices along the triangle sides such that each of the triangle sides is divided into a plurality of sections, the length of each section being such that, given exact model values to be assigned to the vertices, the determination of model values by linear interpolation over the length of any one section does not produce an error which exceeds the threshold value; program code for performing the step (b) of interconnecting the new vertices with line segments parallel to the original triangle sides, such as to create interior subtriangles having vertices at crossing points between the line segments; program code for performing the step (c) of determining the exact model values for each of the vertices of the subtriangles; and program code for performing the step (d) of determining the model values corresponding to each non-vertex object point using linear interpolation.
Claim 49
Dependent Claim
212 words
A computer apparatus comprising a storage medium in which is stored program code for mapping a graphical surface model, comprising a plurality of model values, onto a triangle of a perspective projection of a triangle-based, graphically-represented object defined by points within an object coordinate system, the triangle having a plurality of sides and a plurality of vertices, the storage medium comprising: program code for performing the step (a) of creating new vertices along the triangle sides such that each of the triangle sides is divided into a plurality of sections, the length of each section being such that, given exact model values to be assigned to the vertices, the determination of model values by linear interpolation over the length of any one section does not produce an error which exceeds the threshold value; program code for performing the step (b) of interconnecting the new vertices with line segments parallel to the original triangle sides, such as to create interior subtriangles having vertices at crossing points between the line segments; program code for performing the step (c) of determining the exact model values for each of the vertices of the subtriangles; and program code for performing the step (d) of determining the model values corresponding to each non-vertex object point using linear interpolation.
Claim 50
Dependent Claim
53 words
Apparatus according to claim 38 wherein the storage medium further comprises program code for omitting steps (a)-(c) if, for each side of the triangle, no interpolation error which would result from the use of interpolation in assigning model values to object points along that side of the triangle would exceed the threshold value.
Claim 51
Dependent Claim
221 words
A computer apparatus comprising a storage medium in which is stored program code for mapping a graphical surface model, comprising a plurality of model values, onto a w-isosceles triangle of a perspective projection of a triangle-based, graphically-represented object defined by points within an object coordinate system, the triangle having two sides and a base, the base being bounded by two vertices each having a homogeneous coordinate w of the same value, the storage medium comprising: program code for performing step (a) of dividing the triangle into a plurality of trapezoids each having four vertices, two bases parallel to the base of the triangle, and two sides, each of which is colinear with one of the triangle sides, the length of the trapezoid sides being such that, given the exact model values to be assigned to the vertices of the trapezoid, the interpolation of model values along the sides of the trapezoid results in no interpolation error that exceeds a predetermined threshold value; program code for performing step (b) of determining the exact model values for the vertices of each trapezoid; program code for performing step (c) of subdividing the interior of each trapezoid into a plurality of w-isosceles subtriangles; and program code for performing step (d) of determining the model values for the remaining object points of the triangle by interpolation.
Claim 52
Dependent Claim
221 words
A computer apparatus comprising a storage medium in which is stored program code for mapping a graphical surface model, comprising a plurality of model values, onto a w-isosceles triangle of a perspective projection of a triangle-based, graphically-represented object defined by points within an object coordinate system, the triangle having two sides and a base, the base being bounded by two vertices each having a homogeneous coordinate w of the same value, the storage medium comprising: program code for performing step (a) of dividing the triangle into a plurality of trapezoids each having four vertices, two bases parallel to the base of the triangle, and two sides, each of which is colinear with one of the triangle sides, the length of the trapezoid sides being such that, given the exact model values to be assigned to the vertices of the trapezoid, the interpolation of model values along the sides of the trapezoid results in no interpolation error that exceeds a predetermined threshold value; program code for performing step (b) of determining the exact model values for the vertices of each trapezoid; program code for performing step (c) of subdividing the interior of each trapezoid into a plurality of w-isosceles subtriangles; and program code for performing step (d) of determining the model values for the remaining object points of the triangle by interpolation.
Claim 53
Dependent Claim
53 words
Apparatus according to claim 40 wherein the storage medium further comprises program code for omitting steps (a)-(c) if, for each side of the triangle, no interpolation error which would result from the use of interpolation in assigning model values to object points along that side of the triangle would exceed the threshold value.
Claim 54
Dependent Claim
28 words
Apparatus according to claim 40 wherein the program code for performing step (c) further comprises program code for forming a plurality of geometrically isosceles subtriangles within each trapezoid.
Claim 55
Dependent Claim
30 words
Apparatus according to claim 40 wherein the storage medium further comprises program code for creating said w-isosceles triangle by dividing a triangle which is not w-isosceles into two w-isosceles triangles.
Claim 56
Dependent Claim
184 words
A video controller apparatus for exchanging graphics data between a host processor and a display that displays a graphical image to a user, the controller including a graphics processor in communication with a storage medium in which is stored program code for mapping a graphical surface model, comprising a plurality of model values, onto a polygon of a perspective projection of a polygon-based, graphically-represented object defined by points within an object coordinate system, the storage medium comprising: program code for performing the step (a) of subdividing the polygon into subpolygons each having a plurality of sides and a plurality of vertices, the subdivision being such that, given exact model values to be assigned to the vertices, the determination of model values by linear interpolation over the length of any one subpolygon side does not produce an interpolation error which exceeds a predetermined threshold value; program code for performing the step (b) of determining the exact model values for the vertices of the sub-polygons; and program code for performing the step (c) of determining the model values corresponding to the non-vertex object points by interpolation.
Claim 57
Dependent Claim
184 words
A video controller apparatus for exchanging graphics data between a host processor and a display that displays a graphical image to a user, the controller including a graphics processor in communication with a storage medium in which is stored program code for mapping a graphical surface model, comprising a plurality of model values, onto a polygon of a perspective projection of a polygon-based, graphically-represented object defined by points within an object coordinate system, the storage medium comprising: program code for performing the step (a) of subdividing the polygon into subpolygons each having a plurality of sides and a plurality of vertices, the subdivision being such that, given exact model values to be assigned to the vertices, the determination of model values by linear interpolation over the length of any one subpolygon side does not produce an interpolation error which exceeds a predetermined threshold value; program code for performing the step (b) of determining the exact model values for the vertices of the sub-polygons; and program code for performing the step (c) of determining the model values corresponding to the non-vertex object points by interpolation.
Claim 58
Dependent Claim
42 words
A controller according to claim 44 wherein the program code for performing step (a) comprises program code for subdividing the polygon such that a new vertex is created along a first side for which the maximum interpolation error exceeds the threshold value.
Claim 59
Dependent Claim
31 words
A controller according to claim 44 wherein the program code for performing step (a) further comprises program code for locating the new vertex substantially at the midpoint of the first side.
Claim 60
Dependent Claim
49 words
A controller according to claim 44 wherein the polygon is a triangle, and wherein the program code for performing step (a) further comprises program code for subdividing the triangle into four triangles such that a new vertex is created at the midpoint of each of the original triangle sides.
Claim 61
Dependent Claim
235 words
A video controller for exchanging graphics data between a host processor and a display that display a graphical image to a user, the controller including a graphics processor in communication with a storage medium in which is stored program code for mapping a graphical surface model, comprising a plurality of model values, onto a triangle of a perspective projection of a triangle-based, graphically-represented object defined by points within an object coordinate system, the storage medium comprising: program code for performing the step (a) of obtaining the exact model values for each vertex of the triangle; program code for performing the step (b) of determining, for each side of the triangle, a maximum interpolation error which would result from the use of interpolation, based on the model values of the vertices at the endpoints of the corresponding side for which the maximum interpolation error is determined, to assign model values to object points along the corresponding side; program code for performing the step (c) of comparing the maximum error for each side to a predetermined threshold value; program code for performing the step (d) of subdividing the triangle into substriangles and repeating steps (a), (b), (c) and (d) for each subtriangle, if the maximum error for any of the triangle sides exceeds the threshold value; and program code for performing the step (e) of determining the model values corresponding to the non-vertex object points using interpolation.
Claim 62
Dependent Claim
235 words
A video controller for exchanging graphics data between a host processor and a display that display a graphical image to a user, the controller including a graphics processor in communication with a storage medium in which is stored program code for mapping a graphical surface model, comprising a plurality of model values, onto a triangle of a perspective projection of a triangle-based, graphically-represented object defined by points within an object coordinate system, the storage medium comprising: program code for performing the step (a) of obtaining the exact model values for each vertex of the triangle; program code for performing the step (b) of determining, for each side of the triangle, a maximum interpolation error which would result from the use of interpolation, based on the model values of the vertices at the endpoints of the corresponding side for which the maximum interpolation error is determined, to assign model values to object points along the corresponding side; program code for performing the step (c) of comparing the maximum error for each side to a predetermined threshold value; program code for performing the step (d) of subdividing the triangle into substriangles and repeating steps (a), (b), (c) and (d) for each subtriangle, if the maximum error for any of the triangle sides exceeds the threshold value; and program code for performing the step (e) of determining the model values corresponding to the non-vertex object points using interpolation.
Claim 63
Dependent Claim
239 words
A video controller for exchanging graphics data between a host processor and a display that displays a graphical image to a user, the controller including a graphics processor in communication with a storage medium in which is stored program code for mapping a graphical surface model, comprising a plurality of model values, onto a triangle of a perspective projection of a triangle-based, graphically-represented object defined by points within an object coordinate system, the triangle having a plurality of sides and a plurality of vertices, the storage medium comprising: program code for performing the step (a) of creating new vertices along the triangle sides such that each of the triangle sides is divided into a plurality of sections, the length of each section being such that, given exact model values to be assigned to the vertices, the determination of model values by linear interpolation over the length of any one section does not produce an error which exceeds the threshold value; program code for performing the step (b) of interconnecting the new vertices with line segments parallel to the original triangle sides, such as to create interior subtriangles having vertices at crossing points between the line segments; program code for performing the step (c) of determining the exact model values for each of the vertices of the subtriangles; and program code for performing the step (d) of determining the model values corresponding to each non-vertex object point using linear interpolation.
Claim 64
Dependent Claim
239 words
A video controller for exchanging graphics data between a host processor and a display that displays a graphical image to a user, the controller including a graphics processor in communication with a storage medium in which is stored program code for mapping a graphical surface model, comprising a plurality of model values, onto a triangle of a perspective projection of a triangle-based, graphically-represented object defined by points within an object coordinate system, the triangle having a plurality of sides and a plurality of vertices, the storage medium comprising: program code for performing the step (a) of creating new vertices along the triangle sides such that each of the triangle sides is divided into a plurality of sections, the length of each section being such that, given exact model values to be assigned to the vertices, the determination of model values by linear interpolation over the length of any one section does not produce an error which exceeds the threshold value; program code for performing the step (b) of interconnecting the new vertices with line segments parallel to the original triangle sides, such as to create interior subtriangles having vertices at crossing points between the line segments; program code for performing the step (c) of determining the exact model values for each of the vertices of the subtriangles; and program code for performing the step (d) of determining the model values corresponding to each non-vertex object point using linear interpolation.
Claim 65
Dependent Claim
54 words
A controller according to claim 49 wherein the storage medium further comprises program code for omitting steps (a)-(c) if, for each side of the triangle, no interpolation error which would result from the use of interpolation in assigning model values to object points along that side of the triangle would exceed the threshold value.
Claim 66
Dependent Claim
248 words
A video controller for exchanging graphics data between a host processor and a display that displays a graphical image to a user, the controller including a graphics processor in communication with a storage medium in which is stored program code for mapping a graphical surface model, comprising a plurality of model values, onto a w-isosceles triangle of a perspective projection of a triangle-based, graphically-represented object defined by points within an object coordinate system, the triangle having two sides and a base, the base being bounded by two vertices each having a homogeneous coordinate w of the same value, the storage medium comprising: program code for performing step (a) of dividing the triangle into a plurality of trapezoids each having four vertices, two bases parallel to the base of the triangle, and two sides, each of which is colinear with one of the triangle sides, the length of the trapezoid sides being such that, given the exact model values to be assigned to the vertices of the trapezoid, the interpolation of model values along the sides of the trapezoid results in no interpolation error that exceeds a predetermined threshold value; program code for performing step (b) of determining the exact model values for the vertices of each trapezoid; program code for performing step (c) of subdividing the interior of each trapezoid into a plurality of w-isosceles subtriangles; and program code for performing step (d) of determining the model values for the remaining object points of the triangle by interpolation.
Claim 67
Dependent Claim
248 words
A video controller for exchanging graphics data between a host processor and a display that displays a graphical image to a user, the controller including a graphics processor in communication with a storage medium in which is stored program code for mapping a graphical surface model, comprising a plurality of model values, onto a w-isosceles triangle of a perspective projection of a triangle-based, graphically-represented object defined by points within an object coordinate system, the triangle having two sides and a base, the base being bounded by two vertices each having a homogeneous coordinate w of the same value, the storage medium comprising: program code for performing step (a) of dividing the triangle into a plurality of trapezoids each having four vertices, two bases parallel to the base of the triangle, and two sides, each of which is colinear with one of the triangle sides, the length of the trapezoid sides being such that, given the exact model values to be assigned to the vertices of the trapezoid, the interpolation of model values along the sides of the trapezoid results in no interpolation error that exceeds a predetermined threshold value; program code for performing step (b) of determining the exact model values for the vertices of each trapezoid; program code for performing step (c) of subdividing the interior of each trapezoid into a plurality of w-isosceles subtriangles; and program code for performing step (d) of determining the model values for the remaining object points of the triangle by interpolation.
Claim 68
Dependent Claim
54 words
A controller according to claim 51 wherein the storage medium further comprises program code for omitting steps (a)-(c) if, for each side of the triangle, no interpolation error which would result from the use of interpolation in assigning model values to object points along that side of the triangle would exceed the threshold value.
Claim 69
Dependent Claim
29 words
A controller according to claim 51 wherein the program code for performing step (c) further comprises program code for forming a plurality of geometrically isosceles subtriangles within each trapezoid.
Claim 70
Dependent Claim
31 words
A controller according to claim 52 wherein the storage medium further comprises program code for creating said w-isosceles triangle by dividing a triangle which is not w-isosceles into two w-isosceles triangles.
References Cited (Backward Citations)
US5097427A
Cited
US5369736A
Cited
US5255352A
Cited
US5495563A
Cited
US5307450A
Cited
US5522019A
Cited
US5469535A
Cited
US5490240A
Cited
US5550960A
Cited
EP0680020A2
Cited
CA2164681A1
Cited
EP0718797A2
Cited
US5594846A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-05-17 | 2002-11-16 | 2003-05-18 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-05-17 | 2006-11-16 | 2007-05-18 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-05-17 | 2010-11-16 | 2011-05-18 | $7700.00 | Window Closed / Lapsed |