System for polygon interpolation using instantaneous values in a variable

• US 5,361,386 A
• Filed: 08/17/1993
• Issued: 11/01/1994
• Est. Priority Date: 12/04/1987
• Status: Expired due to Term

• Current Assignee: NVIDIA Corporation
• Original Assignee: Evans & Sutherland Computer Corp. (Elevate Entertainment, Inc.)
• Inventors: Brown, Russell A., Watkins, Gary S.
• Primary Examiner(s): Nguyen, Phu K.
• Application Number:
  US08/108,942
• Time in Patent Office: 441 Days
• Field of Search: 395/129, 395/130, 395/126, 395/127, 395/191, 345/136, 345/137, 345/132, 345/133
• US Class Current: 345/647
• CPC Class Codes: G06T 15/80 Shading

Abstract

Barycentric coordinates are determined using data readily available in computer graphics systems and defining polygons in world space so as to interpolate such polygons with regard to pixels selected by scan conversion. The barycentric coordinates are employed to interpolate the polygons, for example to accomplish smooth shading or texture mapping. The process of the system involves defining primitive data (e.g. polygons) in a space not subject to nonlinear distortion (e.g. world space), transforming select primitive data to a space that is subject to nonlinear distortion, calculating in the space subject to nonlinear distortion (e.g. screen space) a set of areas (e.g. pixels) within a defined primitive (e.g. polygon) using data transformed to space subject to nonlinear distortion, transforming the set of areas to the space not subject to nonlinear distortion, determining at least one differential value (rate of change) of a variable for the primitive, calculating display data that is not subject to nonlinear distortion and using the differential to provide display data. For example, at a pixel, the rate of change in coordinate value (differential) is determined and utilized in texture mapping to facilitate the selection of levels of fuzziness with regard to picture detail for the pixel. Specifically, the differentials are in the coordinates of the texture du land dv.

Claims

1. A process for producing a computer graphics image in accordance with a defined characteristic in screen space based on primitive data defining primitives in space coordinates not subject to nonlinear distortion, said process comprising the steps of:

processing select of said primitive data to provide processed data representing certain specific of said primitives for said graphics image in space coordinates subject to nonlinear distortion;

from said processed data determining pixel image areas of said certain specific primitives for said graphics image, said pixel image areas being represented by pixel image area data;

transforming said pixel image area data to representative area data in said space coordinates not subject to nonlinear distortion;

determining at least one differential value for at least one variable specified in said space coordinates not subject to nonlinear distortion with respect to said primitive data, said differential value for selecting a scale for said defined characteristic from storage;

generating display data using said selected scale for said graphics image based on said representative area data and said differential value; and

displaying said graphics images in said space coordinates subject to nonlinear distortion.

2. A process according to claim 1 wherein said space coordinates not subject to nonlinear distortion comprise world space.

3. A process according to claim 1 wherein said space coordinates not subject to nonlinear distortion comprise eye space.

4. A process according to claim 1 wherein said space coordinates subject to nonlinear distortion comprise screen space.

5. A process according to claim 1 wherein said primitive data further includes texture data and wherein said differential value comprises a rate of change in said texture data.

6. A process according to claim 1 wherein said step of processing select of said primitive data includes identifying a primitive in the form of a polygon for display in said space coordinates subject to nonlinear distortion from a viewpoint.

7. A process according to claim 1 wherein said step of determining pixel image areas comprises scan converting of said primitives to specify pixel areas.

8. A process according to claim 1 wherein said step of transforming said pixel image area data to representative area data includes generating values in barycentric coordinates for said certain specific of said primitives.

9. A process according to claim 8 wherein said step of transforming said pixel image area data to representative area data includes determining texture values u and v.

10. A process according to claim 9 wherein said step of determining at least one differential value includes determining texture differential values du and dv.

11. A process according to claim 10 wherein said step of generating display data includes a table of look-up operation indexed by said differential values du and dv.

12. A process according to claim 11 wherein said table look-up operation comprises three table look-ups for three color component images.

13. A process according to claim 10 wherein said step of generating display data includes a table look-up operation indexed by said differential values du and dv and addressed by said values of u and v.

14. A process according to claim 1 wherein said step of transforming said pixel image area data to representative area data includes determining texture values u and v.

15. A process according to claim 1 wherein said step of generating display data includes a table look-up operation indexed by said differential value.

16. A process according to claim 15 wherein said one differential value is instantaneous value of texture value u and another differential value is instantaneous value of texture value v.

17. A component of a computer graphics system for producing dynamic computer graphics images using a display unit based on primitive data defining primitives in space coordinates not subject to nonlinear distortion, said computer graphics system providing processed data representing certain specific of said primitives for said graphics images in space coordinates subject to nonlinear distortion, said component comprising:

scan means for receiving said processed data for determining pixel image areas of said certain specific primitives for said graphics images, said pixel image areas being represented by pixel image area data;

means for transforming said pixel image area data to representative area data in said space coordinates not subject to nonlinear distortion;

means for determining at least one differential value for at least one variable specified in said space coordinates not subject to nonlinear distortion with respect to said primitive data;

means for providing a selected a texture scale in accordance with said differential value;

means for generating display data using said selected texture scale for said graphics images based on said representative area data and said differential value; and

means for providing said display data to said display unit.

18. A component according to claim 17 wherein said means for generating display data includes a barycentric coordinate computing network for computing barycentric coordinates for said certain primitives.

19. A component according to claim 18 wherein said means for transforming includes means for determining texture values u and v.

20. A component according to claim 19 wherein said means for determining includes means for determining texture differential values du and dr.

21. A component according to claim 20 wherein said means for generating includes a look-up table indexed by said differential values du and dr.

22. A computer graphics process of displaying a graphics image by interpolating a graphics object as for shading or texturing pixels in accordance with a defined characteristic, comprising the steps of:

mapping, in space coordinates not subject to nonlinear distortion, at least a part of said object as a planar polygon;

selecting vertices of a triangular polygon lying within said planar polygon, said vertices of said triangular polygon designated P₁, P₂ and P₃ ;

mapping an eyepoint O in relation to said planar polygon;

mapping a perspective plane in relation to said eyepoint and specifying pixel locations in said perspective plane;

generating signal-represented barycentric coordinates for said planar polygon at said vertices, in said space coordinates not subject to nonlinear distortion;

scan converting said planar polygon to identify points P thereof coinciding to said pixels, said points P being in said space coordinates not subject to nonlinear distortion;

interpolating said points P using said barycentric coordinates with respect to said defined characteristic to provide representative signal values;

storing said representative signal values for scan presentation in a display; and

driving a scan display structure with said representative signal values for scan presentation of an image.

23. A process according to claim 22 wherein said step of generating signal-represented barycentric coordinates includes the steps of:

mapping areas A₁, A₂ and A₃ of triangles defined by one of said points P and said vertices P₁, P₂ and P₃, as P₁ PP₃, P₁ PP₂ and P₂ PP₃ ;

specifying depth dimensions of said vertices as z'"'"'₁, z'"'"'₂ and z'"'"'₃ in said space coordinates not subject to nonlinear distortion; and

generating barycentric coordinates for said planar polygon as, ##EQU30##

24. A process according to claim 22 wherein said interpolating step comprises interpolation of intensity i of said pixels in accordance with said barycentric coordinates.

26. A process according to claim 22 wherein said interpolating step comprises interpolation of multiple components of surface normal vectors at said points P.

27. A process according to claim 22 wherein said interpolating step comprises interpolation of texture for said pixels.

28. A process according to claim 27 wherein texture coordinates for said vertices are designated as vectors (tx₁,tx₂,tx₃) and (ty₁,ty₂,ty₃) and said texture of said points P is interpolated as:

space="preserve" listing-type="equation">tx=(b'"'"'.sub.1,b'"'"'.sub.2,b'"'"'.sub.3)·

(tx.sub.1,tx.sub.2,tx.sub.3)

space="preserve" listing-type="equation">ty=(b'"'"'.sub.1,b'"'"'.sub.2,b'"'"'.sub.3)·

(ty.sub.1,ty.sub.2,ty.sub.3).

25. A process according to claim 60 wherein modulation of intensity i is accomplished by a form of the equation, i=b'"'"'₁ i₁ +b'"'"'₂ i₂ +b'"'"'₃ i₃ where i₁, i₂, and i₃ specify intensities at said vertices P₁, P₂, and P₃.

29. A computer graphics system for displaying a graphics image by interpolating a graphics object as for shading or texturing pixels in accordance with a defined characteristic, wherein said object is represented in space coordinates not subject to nonlinear distortion, at least in part by a planar polygon with defined vertices P₁, P₂, P₃ and further, wherein an eyepoint O is specified along with a perspective plane, said system comprising:

means for generating signal-represented barycentric coordinates for said planar polygon at said vertices, in said space coordinates not subject to nonlinear distortion;

means for scan converting said planar polygon to identify points P thereof coinciding to said pixels, said points P being in said space coordinates not subject to nonlinear distortion;

means for interpolating said points P using said barycentric coordinates with respect to said defined characteristic to provide representative signal values;

means for storing said representative signal values for scan presentation in a display; and

means for receiving said representative signal values from said means for storing to display a representation of said planar polygon as a graphics image.

30. A system according to claim 29 wherein said means for generating signal-represented barycentric coordinates includes,

means for mapping areas A₁, A₂ and A₃ of triangles defined by one of said points P and said vertices P₁, P₂ and P₃ as, P₁ PP₃, P₁ PP₂ and P₂ PP₃ ;

means for specifying depth dimensions of said vertices as z'"'"'₁, z'"'"'₂ and z'"'"'₃ in said space coordinates not subject to linear distortion; and

means for generating barycentric coordinates for said planar polygon as, ##EQU31##

31. A process according to claim 30 wherein modulation of intensity i is accomplished by a form of the equation, i=b'"'"'₁ i₁ +b'"'"'₂ i₂ +b'"'"'₃ i₃ where i₁, i₂, and i₃ specify intensities at said vertices P₁, P₂, and P₃.

32. A process according to claim 30 wherein said texture signals manifest tx₁, tx₂, tx₃, ty₁, ty₂, ty₃ and said means for interpolating functions to accomplish the formula,

33. A system according to claim 29 further including means for providing intensity signals and means for interpolation of said intensity signals in accordance with said barycentric coordinates to shade said pixels.

34. A system according to claim 29 wherein said means for interpolating comprises means for providing surface normal signals representative of multiple components of surface normal vectors for said planar polygon and means for interpolation of said surface normal signals in accordance with said signal-represented barycentric coordinates.

35. A system according to claim 29 wherein said means for interpolating includes means for providing texture signals and means for interpolation of said texture signals in accordance with said signal-represented barycentric coordinates.

36. A computer graphics process of displaying a graphics image by interpolating a graphics object as for shading or texturing in accordance with a defined characteristic, comprising the steps of:

mapping, in space coordinates not subject to nonlinear distortion, at least a part of said object as in form of a planar triangular polygon having at least three vertices;

selecting said vertices of said planar triangular polygon, said vertices of said triangular polygon being designated P₁, P₂ and P₃ ;

mapping an eyepoint O in relation to said planar triangular polygon;

mapping a perspective plane in relation to said eyepoint and specifying pixel locations in said perspective plane;

generating signal-represented barycentric coordinates for said planar triangular polygon at said vertices, in said space coordinates not subject to nonlinear distortion;

scan converting said planar triangular polygon to identify points P thereof coinciding to said pixels, said points P being in said space coordinates not subject to nonlinear distortion;

interpolating said points P using said barycentric coordinates with respect to said defined characteristic to provide representative signal values;

storing said representative signal values for scan presentation; and

driving a scan display structure with said representative signal values for scan presentation of an image.

37. A process according to claim 36 wherein said step of generating signal-represented barycentric coordinates includes the steps of:

mapping a first ray extending from said eyepoint to one of said pixels as a vector OC from said eyepoint to said one pixel;

mapping a second, a third and a fourth ray extending from said eyepoint to each of said vertices P₁, P₂, P₃ as vectors OP₁, OP₂, and OP₃ from said eyepoint to said vertices;

formulating digital signal representations for said vectors OC, OP₁, OP₂ and OP₃ ;

generating triple scalar products using said vectors OC, OP₁, OP₂ and OP₃, defined as K₁, K₂, K₃ ; and

generating barycentric coordinates for said planar triangular polygon as,

space="preserve" listing-type="equation">b'"'"'.sub.1 =K.sub.1 /(K.sub.1 +K.sub.2 +k.sub.3)

space="preserve" listing-type="equation">b'"'"'.sub.2 =K.sub.2 /(K.sub.1 +K.sub.2 +K.sub.3)

space="preserve" listing-type="equation">b'"'"'.sub.3 =K.sub.3 /(K.sub.1 +K.sub.2 +K.sub.3).

38. A process according to claim 36 wherein said step of generating signal-represented barycentric coordinates includes the steps of:

mapping areas A₁, A₂, and A₃ of triangles defined by one of said points P and said vertices P₁, P₂, and P₃, as P₁ PP₃, P₁ PP₂, and P₂ PP₃ ;

specifying depth dimensions of said vertices as z'"'"'₁, z'"'"'₂, and z'"'"'₃ in said space coordinates not subject to nonlinear distortion; and

generating barycentric coordinates for said planar triangular polygon as, ##EQU32##

39. A process according to claim 38 wherein modulation of intensity i is accomplished by a form of the equation, i= b'"'"'₁ i₁ +b'"'"'₂ i₂ +b'"'"'₃ i₃ where i₁, i₂, and i₃ specify intensities at said vertices P₁, P₂, and P₃.

40. A process according to claim 38 wherein said interpolating step comprises interpolation of texture for said pixels.

41. A process according to claim 40 wherein texture coordinates for said vertices are designated as vectors (tx₁, tx₂, tx₃) and (ty₁, ty₂, ty₃) and said texture of said one point is interpolated as:

space="preserve" listing-type="equation">tx=(b'"'"'.sub.1,b'"'"'.sub.2,b'"'"'.sub.3)·

(tx.sub.1,tx.sub.2,tx.sub.3)

space="preserve" listing-type="equation">ty=(b'"'"'.sub.1,b'"'"'.sub.2,b'"'"'.sub.3)·

(ty.sub.1,ty.sub.2,ty.sub.3).

42. A process according to claim 36 wherein said interpolating step comprises interpolation of intensity i of said pixels in accordance with said barycentric coordinates.

43. A process according to claim 36 wherein said interpolating step comprises interpolation of multiple components of a surface normal vector at said one point.

44. A computer graphics system for displaying a graphics image by interpolating a graphics object as for shading or texturing pixels in accordance with a defined characteristic, wherein said object is represented in space coordinates not subject to nonlinear distortion, at least in part by a planar polygon with defined vertices P₁, P₂, P₃ and further, wherein an eyepoint O is specified along with a perspective plane, said system comprising:

means for generating signal-represented barycentric coordinates for said planar polygon at said vertices, in said space coordinates not subject to nonlinear distortion;

means for scan converting said polygon to identify points P thereof coinciding to said pixels, said points P being in said space coordinates not subject to nonlinear distortion;

means for interpolating said points P using said barycentric coordinates with respect to said defined characteristic to provide representative signal values;

means for storing said representative signal values for scan presentation; and

means for receiving said representative signal values from said means for storing to display a representation of said planar polygon as a graphics image.

45. A system according to claim 44 wherein said means for generating signal-represented barycentric coordinates includes,

means for generating signal-represented triple scalar products using vectors OC, OP₁, OP₂, OP₃ to provide representations of K₁, K₂, K₃ ;

and

means for generating signal-represented barycentric coordinates b'"'"'₁, b'"'"'₂ and b'"'"'₃ for said planar polygon using a form of the equation,

space="preserve" listing-type="equation">b'"'"'.sub.1 =K.sub.1 /(K.sub.1 +K.sub.2 +K.sub.3)

space="preserve" listing-type="equation">b'"'"'.sub.2 =K.sub.2 /(K.sub.1 +K.sub.2 +K.sub.3)

space="preserve" listing-type="equation">b'"'"'.sub.3 =k.sub.3 /(K.sub.1 +K.sub.2 +K.sub.3).

46. A system according to claim 45 wherein said means for generating multiple products comprises means for generating said multiple products of said vectors by applying equations as a dot product and a cross-product as,

47. A system according to claim 44 wherein said means for generating signal-represented barycentric coordinates includes,

means for mapping areas A₁, A₂ and A₃ of triangles defined by one of said points P and said vertices P₁, P₂ and P₃ as, P₁ PP₃, P₁ PP₂ and P₂ PP₃ ;

means for specifying depth dimensions of said vertices as z'"'"'₁, z'"'"'₂ and z'"'"'₃ in said space coordinates not subject to nonlinear distortion; and

means for generating barycentric coordinates for said planar polygon as, ##EQU33##

48. A system according to claim 47 wherein said means for interpolation accords to a form of the equation, i=b'"'"'₁ i₁ +b'"'"'₂ i₂ +b'"'"'₃ i₃ where i₁, i₂, and i₃ specify intensities at said vertices P₁, P₂, and P₃.

49. A process according to claim 47 wherein texture signals manifest tx₁, tx₂, tx₃, ty₁, ty₂, ty₃ and said means for interpolating functions to accomplish the formula,

50. A system according to claim 44 further including means for providing intensity signals and means for interpolation of said intensity signals in accordance with said barycentric coordinates to shade said pixels.

51. A system according to claim 44 wherein said means for interpolation comprises means for providing surface normal signals representative of multiple components of surface normal vectors for said planar polygon and means for interpolation of said surface normals signals in accordance with said signal-represented barycentric coordinates.

52. A system according to claim 44 wherein said means for interpolating includes means for providing texture signals and means for interpolation of said texture signals in accordance with said signal-represented barycentric coordinates.