Method for rendering high order rational surface patches

• US 5,995,109 A
• Filed: 04/08/1997
• Issued: 11/30/1999
• Est. Priority Date: 04/08/1997
• Status: Expired due to Term

• Current Assignee: Avago Technologies General IP PTE Limited (Broadcom, Inc.)
• Original Assignee: LSI Logic Corporation (Broadcom, Inc.)
• Inventors: Goel, Vineet, Vainsencher, Leonardo
• Primary Examiner(s): Powell, Mark R.
• Assistant Examiner(s): Nguyen, Kimbinh T.
• Application Number:
  US08/835,501
• Time in Patent Office: 966 Days
• Field of Search: 345/423, 345/426, 345/431, 345/442, 345/441
• US Class Current: 345/423
• CPC Class Codes: G06T 15/04 Texture mapping
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation

Abstract

A method for efficient, high quality rendering of a surface patch. The method tests a surface patch for flatness, and if the surface patch is not flat, the method divides the surface patch into a left surface patch and a right surface patch. Otherwise if the surface patch is flat, the method converts the surface patch into triangles. This method can be implemented to operate recursively, thereby ensuring that all portions of the patch are eventually converted into triangles when the portions become small enough to satisfy the flatness condition. A patch tests as flat only if all curves which form the patch do not deviate from straight lines by more than a predetermined tolerance. The division is efficiently performed by determining (i) left patch control points for a first portion of all curves along one axis of the surface patch, and (ii) right patch control points for a second portion of all curves along said axis of the surface patch. The axis of division preferably alternates, so that the dividing is done along a second axis if patch is not flat along the second axis and a preceding division occurred along a first axis. The method also includes tests for backfaced orientation of the patch and external location of the patch. The patch is discarded if it faces away from the viewpoint or does not appear inside the viewing region.

Claims

1. A method for rendering a Bezier surface patch which describes a portion of an object, wherein said surface patch has an original set of control points, comprising:

testing the surface patch for flatness; and

if the surface patch is not flat;

generating a second set of control points for a left subpatch from the original set of control points;

rendering the left subpatch;

generating a third set of control points for a right subpatch from the second set of control points;

rendering the right subpatch;

generating the original set of control points from the third set of control points; and

if the surface patch is flat;

converting the surface patch into triangles; and

presenting said triangles on a graphics display.

2. The method of claim 1, wherein said rendering of said left and right subpatches is recursively accomplished by performing said testing, generating, rendering and converting on both said left and right subpatches.

3. The method of claim 1, wherein said second set of control points L_0i, L_1i, L_2i, L_3i, 0≦

i≦

3, is generated from the original set of control points P_0i, P_1i, P_2i, P_3i, 0≦

i≦

3, according to the equations L_0i =P_0i, L_1i =(P_0i +P_1i)/2, L_2i =(P_0i +2P_1i +P_2i)/4, and L_3i =(P_0i +3P_1i +3P_2i +P_3i)/8 for 0≦

i≦

3.

4. The method of claim 1, wherein said second set of control points L_0i, L_1i, L_2i, L_3i, 0≦

i≦

3, is generated from the original set of control points P_0i, P_1i, P_2i, P_3i, 0≦

i≦

3, using intermediate values M_1i, N_1i, M_2i, 0≦

i≦

3, by a plurality of operations comprising L_0i =P_0i, L_1i =(P_0i +P_1i)/2, M_1i =(P_1i +P_2i)/2, N_1i =(P_2i +P_3i)/2, L_2i =(L_1i +M_1i)/2, M_2i =(M_1i +N_1i)/2, L_3i =(L_2i +M_2i)/2, for 0≦

i≦

3.

5. The method of claim 1, wherein said third set of control points R_0i, R_1i, R_2i, R_3i, 0≦

i≦

3, is generated from the second set of control points L_0i, L_1i, L_2i, L_3i, 0≦

i≦

3, according to the equations R_0i =L_3i, R_1i =-L_2i +2L_3i, R_2i =L_1i -4L_2i +4L_3i, and R_3i =-L_0i +6L_1i -12L_2i +8L_3i for 0≦

i≦

3.

6. The method of claim 1, wherein said third set of control points R_0i, R_1i, R_2i, R_3i, 0≦

i≦

3, is generated from the second set of control points L_0i, L_1i, L_2i, L_3i, 0≦

i≦

3, using intermediate values M_1i, N_1i, M_2i, 0≦

i≦

3, by a plurality of operations comprising R_0i =L_3i, R_1i =2L_3i -L_2i, M_1i =2L_2i -L_1i, N_1i =2L_1i -L_0i, R_2i =2R_1i -M_1i, M_2i =2M_1i -N_1i, R_3i =2R_2i -M_2i, for 0≦

i≦

3.

7. The method of claim 1, wherein said generation of the original set of control points P_0i, P_1i, P_2i, P_3i, 0≦

i≦

3, from the third set of control points R_0i, R_1i, R_2i, R_3i, 0≦

i≦

3, is determined according to the equations P_3i =R_3i, P_2i =-R_3i +2R_2i, P_1i =R_3i -4R_2i +4R_1i, and P_0i =-R_3i +6R_2i -12R_1i +8R_0i for 0≦

i≦

3.

8. The method of claim 1, wherein said generation of the original set of control points P_0i, P_1i, P_2i, P_3i, 0≦

i≦

3, from the third set of control points R_0i, R_1i, R_2i, R_3i, 0≦

i≦

3, is determined using mediate values M_1i, N_1i, M_2i, 0≦

i≦

3, by a plurality of operations comprising P_3i =R_3i, P_2i =-R_3i +2R_2i, M_1i =-R_2i +2R_1i, N_1i =-R_1i +2R_0i, P_1i =-P_2i +2M_1i, M_2i =-M_1i +2N_1i, P_0i =-P_1i 2M_2i, for 0≦

i≦

3.

9. The method of claim 1, wherein the generation of said second set of control points from said original set of control points is implemented to provide fixed point results, and wherein bits that are truncated from said second set of control points are stored for use in the generation of said third set of control points.

10. The method of claim 9, wherein said generation of said third set of control points is preceded by restoring said truncated bits to said second set of control points.

11. The method of claim 1, wherein said generation of said third set of control points from said second set of control points is implemented to provide fixed point results, and wherein bits that are truncated from said third set of control points are stored for use in the generation of said original set of control points.

12. The method of claim 11, wherein said generation of said original set of control points is preceded by restoring said bits that are truncated from the third set of control points to said third set of control points.

13. The method of claim 2, wherein said patches have curves along a first axis and curves along a second axis, wherein said generation of the second set of control points for a left subpatch is (1) performed for curves along the first axis if the patch tests as fat along the second axis, (2) performed for curves along the second axis if the patch tests as flat along the first axis, (3) performed for curves along the first axis if the patch tests as not-flat along the first axis and a prior generation of the second set of control points was not along the first axis, and (4) performed for curves along the second axis if the patch tests as not-flat along the second axis and a prior generation of the second set of control points was along the first axis.

14. The method of claim 1, wherein the testing for flatness is preceded by a determination of patch orientation, and wherein the surface patch is discarded if the surface patch has a backfaced orientation.

15. The method of claim 14, wherein the surface patch has control points having x and y coordinates (g_ij.x, g_ij.y) 0≦

i,j≦

N, and wherein the surface patch is determined to have a backfaced orientation by evaluating the relation

space="preserve" listing-type="equation">(g.sub.i+1,j.x-g.sub.i,j.x,g.sub.i+1,j.y-g.sub.i,j.y)x(g.sub.i,j+1.x=g.sub.i,j.x,g.sub.i,j+1.y-g.sub.i,j.y)<

0

to be true for 0≦

i,j<

N.

16. The method of claim 1, wherein the testing for flatness is preceded by a determination of patch location, and wherein the surface patch is discarded if the surface patch has a location external to a viewing window.

17. The method of claim 16, wherein the surface patch has control points having x, y, and z coordinates (g_i,j.x, g_i,j.y, g_i,j.z) 0≦

i,j≦

N, wherein ε

is a predetermined fraction of the viewing window size, and wherein the surface patch is determined to have a location external to the viewing window by determining that not all of the following relations are jointly true;

-(1+ε

)<

g_ij.x<

(1+ε

),

-(1+ε

)<

g_ij.y<

(1+ε

), and

-1<

g_ij.z<

0

for all combinations of i and j.

18. The method of claim 1, wherein said testing for flatness comprises determining straightness of Bezier curves within the Bezier surface patch, wherein said Bezier curves have end points and intermediate control points, and wherein said determination of straightness includes:

determining a horizontal distance between the end points; and

determining a vertical distance between the end points; and

comparing the horizontal distance to the vertical distance; and

if the horizontal distance is greater than the vertical distance,

comparing a vertical resolution to vertical deviations of the intermediate control points from a straight line between the end points; and

determining that the curve is not straight if any of the vertical deviations exceeds the vertical resolution; and

if the horizontal distance is less than the vertical distance,

comparing a horizontal resolution to horizontal deviations of the intermediate control points from a straight line between the end points; and

determining that the curve is not straight if any of the horizontal deviations exceeds the horizontal resolution.

19. The method of claim 18, wherein said determination of straightness further includes:

if the horizontal distance is greater than the vertical distance,

comparing a perpendicular resolution to first perpendicular deviations of the intermediate control points from a straight line between the end points; and

determining that the curve is not straight if any of the first perpendicular deviations exceeds the perpendicular resolution; and

if the horizontal distance is less than the vertical distance,

comparing the perpendicular resolution to second perpendicular deviations of the intermediate control points from a straight line between the end points; and

determining that the curve is not straight if any of the second perpendicular deviations exceeds the perpendicular resolution.

20. The method of claim 1, wherein said testing for flatness includes determining straightness of Bezier curves within a diffluse color patch associated with the surface patch.

21. The method of claim 20, wherein said Bezier curves have end points and intermediate control points, and wherein said determination of straightness includes:

determining a horizontal distance between the end points; and

determining a vertical distance between the end points; and

comparing the horizontal distance to the vertical distance; and

if the horizontal distance is greater than the vertical distance,

comparing a color resolution to first color deviations of the intermediate control points from a straight line between the end points; and

determining that the curve is not straight if any of the color deviations exceeds the color resolution; and

if the horizontal distance is less than the vertical distance,

comparing a color resolution to second color deviations of the intermediate control points from a straight line between the end points; and

determining that the curve is not straight if any of the color deviations exceeds the color resolution.

22. A device for converting a Bezier surface patch having an original set of control points to a plurality of triangles for display, comprising:

a floating point unit configured to receive said control points, wherein said floating point unit is also configured to apply a desired transformation to said control points;

a patch tessellator coupled to receive said transformed control points and configured to responsively produce a set of triangles which approximate said patch; and

a rasterizer coupled to receive said said triangles and responsively produce pixel data for an image of said patch;

wherein said patch tessellator is configured to (a) test the surface patch for flatness; and

if the surface patch is not flat;

(b) generate a second set of control points for a left subpatch from the transformed control points to generate the left subpatch;

(c) generate a third set of control points for a right subpatch from the second set of control points to generate the right subpatch;

(d) generate the transformed control points from the third set of control points; and

if the surface patch is flat;

(e) convert the surface patch into triangles.

23. The device of claim 22, wherein said patch tessellator is further configued to generate the left and right subpatches by iteratively performing steps (a) on a subpatch and (b), (c), (d) on the subpatch if the subpatch is not flat and (e) on the subpatch if the subpatch is flat, wherein said iteration occurs for the left and right subpatches and any new subpatches which are identified by performing steps (b) and (c).

24. The device of claim 22, wherein said patch tessellator generates said second set of control points L_0i, L_1i, L_2i, L_3i, 0≦

i≦

3, from the transformed control points P_0i, P_1i, P_2i, P_3i, 0≦

i≦

3, according to the equations L_0i =P_0i, L_1i =(P_0i +P_1i)/2, L_2i =(P_0i +2P_1i +P_2i)/4, and L_3i =(P_0i +3P_1i +3P_2i +P_3i)/8 for 0≦

i≦

3.

25. The device of claim 22, wherein said patch tessellator generated said third set of control points R_0i, R_1i, R_2i, R_3i, 0≦

i≦

3, from the second set of control points L_0i, L_1i, L_2i, L_3i, 0≦

i≦

3, according to the equations R_0i =L_3i, R_1i =-L_2i +2L_3i, R_2i =L_1i -4L_2i +4L_3i, and R_3i =-L_0i +6L_1i -12L_2i +8L_3i for 0≦

i≦

3.

26. The device of claim 22, wherein said generation of the transformed control points P_0i, P_1i, P_2i, P_3i, 0≦

i≦

3, from the third set of control points R_0i, R_1i, R_2i, R_3i, 0≦

i≦

3, is determined by the patch tessellator according to the equations P_3i =R_3i, P_2i =-R_3i +2R_2i, P_1i =R_3i -4R_2i +4R_1i, and P_0i =-R_3i +6R_2i -12R_1i +8R_0i for 0≦

i≦

3.

27. The device of claim 22, wherein said patch tessellator operates only on fixed point data, and wherein said patch tessellator stores bits that are truncated from said second set of control points, and wherein said patch tessellator restores said truncated bits to said second set of control points prior to generating said third set of control points.

28. The device of claim 22, wherein said patch tessellator operates only on fixed point data, and wherein said patch tessellator stores bits that are truncated from said third set of control points, and wherein said patch tessellator restores said truncated bits to said third set of control points prior to generating said transformed control points.

29. The device of claim 23, wherein said patches have curves along a first axis and curves along a second axis, and wherein said patch tessellator generates the second set of control points for a left subpatch is (1) for curves along the first axis if the patch tests as flat along the second axis, (2) for curves along the second axis if the patch tests as flat along the first axis, (3) for curves along the first axis if the patch tests as not-flat along the first axis and a prior generation of the second set of control points was not along the first axis, and (4) for curves along the second axis if the patch tests as not-flat along the second axis and a prior generation of the second set of control points was along the first axis.

30. The device of claim 22, wherein prior to testing for flatness the patch tessellator discards the patch if the patch tessellator determines that the patch has a backfaced orientation.

31. The device of claim 22, wherein prior to testing for flatness, the patch tessellator discards the patch if the patch tessellator determines that the surface patch has a location external to a viewing window.

32. The device of claim 22, wherein said the patch tessellator is configured to test for flatness by determining straightness of Bezier curves within the surface patch, wherein said Bezier curves have end points and intermediate control points, and wherein said patch tessellator is configured to perform the determination of straightness by:

determining a horizontal distance between the end points; and

determining a vertical distance between the end points; and

comparing the horizontal distance to the vertical distance; and

if the horizontal distance is greater than the vertical distance,

comparing a vertical resolution to vertical deviations of the intermediate control points from a straight line between the end points; and

determining that the curve is not straight if any of the vertical deviations exceeds the vertical resolution; and

if the horizontal distance is less than the vertical distance,

comparing a horizontal resolution to horizontal deviations of the intermediate control points from a straight line between the end points; and

determining that the curve is not straight if any of the horizontal deviations exceeds the horizontal resolution.

33. The device of claim 22, wherein the floating point unit is further configured to determine one or more attribute patches for said surface patch, wherein said one or more attribute patches include a diffuse color patch.

34. The device of claim 33, wherein the patch tessellator is configured to test for flatness by determining straightness of Bezier curves within the diffuse color patch associated with the surface patch.

35. The device of claim 34, wherein said Bezier curves have end points and intermediate control points, and wherein the patch tessellator performs the determination of straightness by:

determining a horizontal distance between the end points; and

determining a vertical distance between the end points; and

comparing the horizontal distance to the vertical distance; and

if the horizontal distance is greater than the vertical distance,

comparing a color resolution to first color deviations of the intermediate control points from a straight line between the end points; and

asserting that the curve is not straight if any of the color deviations exceeds the color resolution; and

if the horizontal distance is less than the vertical distance,

comparing a color resolution to second color deviations of the intermediate control points from a straight line between the end points; and

asserting that the curve is not straight if any of the color deviations exceeds the color resolution.

36. A method for rendering a Bezier surface patch which describes a portion of an object, wherein said Bezier surface patch includes Bezier curves which are to be tested for straightness, wherein said Bezier curves have end points and intermediate control points, and wherein said method comprises:

determining a horizontal distance between the end points; and

determining a vertical distance between the end points; and

comparing the horizontal distance to the vertical distance; and

if the horizontal distance is greater than the vertical distance,

comparing a vertical resolution to vertical deviations of the intermediate control points from a straight line between the end points; and

determining that the curve is not straight if any of the vertical deviations exceeds the vertical resolution; and

if the horizontal distance is less than the vertical distance,

comparing a horizontal resolution to horizontal deviations of the intermediate control points from a straight line between the end points; and

determining that the curve is not straight if any of the horizontal deviations exceeds the horizontal resolution.

37. The method of claim 36, further comprising:

if the horizontal distance is greater than the vertical distance,

comparing a perpendicular resolution to first perpendicular deviations of the intermediate control points from a straight line between the end points; and

asserting that the curve is not straight if any of the first perpendicular deviations exceeds the perpendicular resolution; and

if the horizontal distance is less than the vertical distance,

comparing the perpendicular resolution to second perpendicular deviations of the intermediate control points from a straight line between the end points; and

asserting that the curve is not straight if any of the second perpendicular deviations exceeds the perpendicular resolution.

38. A storage medium configured to provide instructions for patch tessellation to a graphics display system, wherein patches to be tessellated include Bezier curves which are to be tested for straightness, wherein said Bezier curves have end points and intermediate control points, and wherein said instructions comprise:

determining a horizontal distance between the end points; and

determining a vertical distance between the end points; and

comparing the horizontal distance to the vertical distance; and

if the horizontal distance is greater than the vertical distance,

comparing a vertical resolution to vertical deviations of the intermediate control points from a straight line between the end points; and

determining that the curve is not straight if any of the vertical deviations exceeds the vertical resolution; and

if the horizontal distance is less than the vertical distance,

comparing a horizontal resolution to horizontal deviations of the intermediate control points from a straight line between the end points; and

determining that the curve is not straight if any of the horizontal deviations exceeds the horizontal resolution.

39. A mehod for rendering a Bezier surface patch on a display having a horizontal resolution T_x and a vertical resolution T_y, wherein said Bezier surface patch describes a portion of an object, wherein said Bezier surface patch includes a Bezier curve which is to be tested for straightness, wherein said Bezier curve has end points (x₀,y₀), (x_e,y_e) and intermediate control points (x_i,y_i), 0<

i<

e, and wherein said method comprises;

determining a horizontal distance |x_e -x₀ |; and

determining a vertical distance |y_e -y₀ |; and

comparing the horizontal distance to the vertical distance; and

if the horizontal distance is greater than the vertical distance,

comparing deviation quantities |(y_i -y₀)(x_e -x₀)-(y_e -y₀)(x_i -x₀)|, 0<

i<

e, to a vertical resolution quantity T_y |(x_e -x₀)|; and

determining that the curve is straight if none of the deviation quantities exceeds the vertical resolution quantity; and

if the horizontal distance is less than the vertical distance,

comparing deviation quantities |(y_i -y₀)(x_e -x₀)-(y_e -y₀)(x_i -x₀)|, 0<

i<

e, to a horizontal resolution quantity T_x |(y_e -y₀)|; and

determining that the curve is straight if none of the deviation quantities exceeds the horizontal resolution quantity.

40. A method for rendering a Bezier surface patch on a display using a horizontal resolution T_x, a vertical resolution T_y, and a perpendicular resolution T_z, wherein said Bezier surface patch describes a portion of an object, wherein said Bezier surface patch includes a three-dimensional Bezier curve which is to be tested for straightness, wherein said Bezier curve has end points (x₀,y₀,z₀), (x_e,y_e,z_e) and intermediate control points (x_i,y_i,z_i), 0<

i<

e, and wherein said method comprises;

determining a horizontal distance |x_e -x₀ |; and

determining a vertical distance |y_e -y₀ |; and

comparing the horizontal distance to the vertical distance; and

if the horizontal distance is greater than the vertical distance,

comparing deviation quantities |(y_i -y₀)(x_e -x₀)-(y_e -y₀)(x_i -x₀)|, 0<

i<

e, to a vertical resolution quantity T_y |(x_e -x₀)|; and

comparing first perpendicular deviation quantities |(z_i -z₀)(x_e -x₀)-(z_e -z₀)(x_i -x₀)|, 0<

i<

e, to a first perpendicular resolution quantity T_z |(x_e -x₀)|; and

determining that the curve is straight if none of the deviation quantities exceeds the vertical resolution quantity and none of the first perpendicular deviation quantities exceeds the first perpendicular resolution quantity; and

if the horizontal distance is less than the vertical distance,

comparing deviation quantities |(y_i -y₀)(x_e -x₀)-(y_e -y₀)(x_i -x₀)|, 0<

i<

e, to a horizontal resolution quantity T_x |(y_e -y₀)|; and

comparing second perpendicular deviation quantities |(z_i -z₀)(y_e -y₀)-(z_e -z₀)(y_i -y₀)|, 0<

i<

e, to a second perpendicular resolution quantity T_z |(y_e -y₀)|; and

determming that the curve is straight if none of the deviation quantities exceeds the horizontal resolution quantity and none of the first perpendicular deviation quantities exceeds the first perpendicular resolution quantity.

41. A method for rendering a color Bezier surface patch which describes a portion of an object, wherein said Bezier surface patch has an associated diffuse color Bezier patch, wherein said method comprises determining straightness of Bezier curves within the diffluse color Bezier patch.

42. The method of claim 41, further comprising determining the diffuse color Bezier patch prior to determining the straightness of Bezier curves within the diffuse color patch.

43. The method of claim 41, further comprising determining a Coon'"'"'s patch approximation of the diffuse color Bezier patch.

44. The method of claim 41, wherein said Bezier curves have end points and intermediate control points, and wherein said determination of straightness includes:

determining a horizontal distance between the end points; and

determining a vertical distance between the end points; and

comparing the horizontal distance to the vertical distance; and

if the horizontal distance is greater than the vertical distance,

comparing a color resolution to first color deviations of the intermediate control points from a straight line between the end points; and

asserting that the curve is not straight if any of the color deviations exceeds the color resolution; and

if the horizontal distance is less than the vertical distance,

comparing a color resolution to second color deviations of the intermediate control points from a straight line between the end points; and

asserting that the curve is not straight if any of the color deviations exceeds the color resolution.

45. A method for rendering a surface patch having an associated color patch, wherein said surface patch represents a portion of an object, said method comprising:

testing the surface patch for flatness; and

if the surface patch is flat, testing the associated color patch for linearity of shading of the surface patch; and

if the surface patch is linearly shaded, converting the surface patch into triangles; and

if the surface patch is not flat or if the surface patch is not linearly shaded, dividing the surface patch and associated color patch into surface subpatches with associated color subpatches.

46. The method of claim 45, further comprising:

recursively performing said testing the surface patch for flatness, said testing the associated color patch for linearity of shading if the surface patch is flat, said converting the surface patch into triangles if the surface patch is linearly shaded, and said dividing the surface patch and associated color patch into surface subpatches with associated color subpatches otherwise.

47. The method of claim 45, wherein said testing for flatness determines that the surface patch is flat if all curves which form the surface patch do not deviate from straight lines by more than a predetermined tolerance.

48. The method of claim 45, wherein said testing for linearity of shading determines that the surface patch is linearly shaded if all curves which form the associated color patch do not deviate from straight lines by more than a predetermined tolerance.

49. The method of claim 45, wherein the testing for flatness is preceded by determining an orientation of said surface patch, and wherein said surface patch is discarded if the surface patch is backfaced.

50. The method of claim 49, wherein the testing for flatness is preceded by determining a location of said surface patch, and wherein said surface patch is discarded if the surface patch has a location external to a viewing window.