Method and apparatus for adaptive nonlinear projective rendering

• US 5,905,500 A
• Filed: 03/18/1997
• Issued: 05/18/1999
• Est. Priority Date: 02/19/1997
• Status: Expired due to Term

• Current Assignee: Seiko Epson Corporation (Seiko Group)
• Original Assignee: Seiko Epson Corporation (Seiko Group)
• Inventors: Kamen, Yakov, Shirman, Leon
• Primary Examiner(s): Vo., Cliff N.
• Application Number:
  US08/819,312
• Time in Patent Office: 791 Days
• Field of Search: 345/418, 345/419, 345/420, 345/423, 345/424
• US Class Current: 345/419
• CPC Class Codes: G06T 15/10 Geometric effects

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.

Claims

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

2. A method according to claim 1 wherein the polygon is a triangle.

3. A method according to claim 1 wherein, for a given subpolygon, the plurality of vertices includes a first vertex P₀ having object coordinates (x₀, y₀, w₀) and a second vertex P₁ having object coordinates (x₁, y₁, w₁), and wherein determining the maximum error for a subpolygon side bounded by vertex P₀ and vertex P₁ comprises finding a maximum error e such that:

space="preserve" listing-type="equation">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₀, w₁)/max(w₀, w₁).

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

5. A method according to claim 4 wherein said new vertex is located substantially at the point of maximum interpolation error for the first side.

6. A method according to claim 5 wherein the first side is bounded by a first vertex P₀ having object coordinates (x₀, y₀, w₀) and a second vertex P₁ having object coordinates (x₁, y₁, w₁), and wherein the point of maximum error t_maxerror for the first side is determined as:

space="preserve" listing-type="equation">t.sub.maxerror =1/(1+√

(w.sub.1 /w.sub.0)).

7. A method according to claim 4 wherein said new vertex is located substantially at the midpoint of the first side.

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

9. A method according to claim 1 wherein said interpolation is linear interpolation.

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

11. A method according to claim 10 wherein, for a side having a vertex P₁ with object coordinates (x₁, y₁, w₁) at a first end, and a vertex P₀ with object coordinates (x₀, y₀, w₀) at a second end, the maximum error for that side is:

space="preserve" listing-type="equation">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₀, w₁)/max(w₀, w₁).

12. 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₁ at a first end with a homogeneous coordinate w₁, and a vertex P₂ at a second end with a homogeneous coordinate w₂, the point of maximum interpolation error t_maxerror for that side is determined as:

space="preserve" listing-type="equation">t.sub.maxerror =1/(1+√

(w.sub.1 /w.sub.0)).

13.

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

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

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

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

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

18. A method according to claim 17 wherein step (c) further comprises forming a plurality of geometrically isosceles subtriangles within each trapezoid.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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