Parametric surface evaluation method and apparatus for a computer graphics display system

• US 5,278,948 A
• Filed: 08/21/1992
• Issued: 01/11/1994
• Est. Priority Date: 10/24/1989
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Luken, William L. Jr.
• Primary Examiner(s): Zimmerman, Mark K.
• Application Number:
  US07/933,602
• Time in Patent Office: 508 Days
• Field of Search: 395/120, 395/123, 395/126, 395/127, 395/163
• US Class Current: 345/423
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation

Abstract

A method and apparatus for evaluating and rendering parametric surfaces. The apparatus includes a system memory connected to a graphics control processor, which is connected to local memory, and then connected in a pipelined arrangement to a plurality of parallel floating point processors, another floating point processor, a clipping processor and a frame buffer. The method includes: reading data from system memory and storing said data in local memory and/or registers within the graphics control processor; defining a control point stack containing kv by Nu transformed control points; multiplying the control points by a corresponding weight; evaluating the v dependence of homogeneous coordinates (wx,wy,wz,w) for successive parameter points separated by a v parameter interval; simultaneously within each parallel floating point processor evaluating the b-spline functions for one component of the coordinate set (wx,wy,wz,w) at successive u parameter points to obtain a top and bottom u coordinate, a top and bottom u derivative, and a top and bottom v derivative; eliminating the weight from each said coordinate yielding the geometric coordinates, and using the corresponding u and v derivatives to determine the geometric u and v tangents for a top and bottom point of an associated u value and therefrom the normal vector; clipping the polygon to the current viewing boundaries; and producing the shaded images of the polygon.

Claims

1. A method of converting NURBS data representative of a parametric surface into geometric coordinates and associated surface normal vectors of vertices of polygons for subsequent rendering on the screen of a computer graphics display system, the surface having one edge extending along a u parametric coordinate for Nu-ku+1successive u spans where Nu is the dimension and ku is the order along the u coordinate and a second edge extending along an orthogonal v parametric coordinate for Nv-kv+1 successive v span where Nv is the dimension and kv is the order along the v coordinate, the general geometry of the surface being defined by a matrix of Nv rows of Nu columns of control points, comprising the steps of:

(a) placing steps of view coordinates for the first kv successive rows of Nu control points of said matrix into a control point stack having kv rows and Nu columns so that the stack contains all of the control points for an initial v span;

(b) converting the view coordinates to homogeneous coordinates and evaluating the b-spline function of sets of coordinates in each column of said stack for an initial v parameter point and a successive v parameter point to obtain a series of Nu bottom coordinates and Nu bottom v derivatives, and a series of Nu top coordinates and Nu top v derivatives, respectively, for a first strip extending fully across the surface along the u coordinate and bounded in the v coordinate by said initial v parameter point and said successive v parameter point;

(c) evaluating the b-spline functions of the top coordinates, top v derivatives, bottom coordinates and bottom v derivatives at successive u parameter points for each successive u span of the first strip to obtain values for the u dependence of the top and bottom coordinates, for the top and bottom u derivatives and for the u dependence of the top and bottom v derivatives for each of said successive u parameter points;

(d) converting the values obtained from the preceding evaluation step into a set of geometric coordinates and a vertex normal for a top point and a bottom point of said strip for each u parameter point, the top and bottom points for each u parameter point in conjunction with the top and bottom points for an immediately succeeding u parameter point defining a 4-sided polygon to be subsequently rendered; and

(e) repeating steps (b)-(d) for additional successive v parameter points of said initial v span, and repeating steps (a)-(d) for successive v spans of the surface; and

(f) generating a shaded image of said polygons from the geometric coordinates and surface normal vectors of the points defining said polygons to render said surface on said screen.

2. The method of claim 1 wherein the top coordinates and top v derivatives of a strip are employed as the bottom coordinates and bottom v derivatives in evaluation step (c) for an immediately succeeding strip.

3. The method of claim 1 wherein an initial u span of the surface is defined by ku columns of the stack and each successive u span is defined by a successive column and the immediately preceding ku-1 columns;

wherein the initial v span of the surface is defined by the first kv successive rows of said matrix and each successive v span is defined by a corresponding successive row of said matrix and the kv-1 immediately preceding rows;

wherein said stack operates on a first in-first out row basis; and

further comprising the step of pushing a corresponding successive row of the matrix into the top of the stack for each successive v span.

4. The method of claim 1 wherein the control points in said matrix are represented in modelling coordinates and each control points has a weight w associated therewith;

and further comprising the steps of;

transforming the control points modelling coordinates to view coordinates;

multiplying the transformed coordinates of a control point by its associated weight to thereby convert the new coordinates to a set of homogeneous coordinates for each control point; and

calculating a v parametric coordinate interval for each v span and generating therefrom a series of v parameter points for the v span, successive v parameter points being spaced apart by said v coordinate interval.

5. The method of claim 4 further comprising the step of:

calculating a u parametric coordinate interval for each u span of a strip and generating therefrom a series of u parameter points for said u span, successive u parameter points being spaced apart by said u interval; and

wherein evaluation step (c) is implemented with four parallel floating point processors simultaneously evaluating the b-spline functions for a different one of the wx, wy, wz and w coordinate set.

6. The method of claim 1 wherein the values obtained in evaluation step (c) have a weight w associated therewith and wherein converting step (d) comprises:

eliminating the weight w from the values obtained in evaluation step (c) to yield a set of geometric coordinates and a u tangent and a v tangent for the top point and bottom point of said strip for each u parameter point;

computing a vertex normal by taking the cross product of the u and v tangents for each of said top and bottom points; and

computing the magnitudes of the vertex normals.

7. The method of claim 1 wherein evaluation steps (b) and (c) employ the Cox-DeBoor process.

8. The method of claim 1 further comprising the step of comparing the magnitude of the vertex normal at each top and bottom point to a normal threshold, and when the magnitude is less than said threshold replacing the vertex normal vector for that point with a normal vector from an adjacent point.

9. The method of claim 1 further comprising the step of determining the visibility of each u span within each v span.

10. The method of claim 1 further comprising the steps of:

clipping each polygon of step (d) against a current 3-dimensional viewing window;

interpolating the vertex normals along clipped edges; and

converting the interpolated vertex normals to unit vectors for subsequent rendering.

11. The method of claim 1 wherein said parametric surface is an untrimmed parametric surface.

12. A method of converting NURBS data representative of a parametric surface to geometric coordinates and associated surface normal vectors of vertices of polygons for subsequent rendering on the screen of a computer graphics display system, the surface having one edge extending along a u parametric coordinate for an Nu-ku+1 plurality of successive u spans where Nu is the dimension and ku is the order along the u coordinate and a second edge extending along an orthogonal v parametric coordinate for an Nv-kv+1plurality of successive v spans where Nv is the dimension and kv is the order along the v coordinate, the u spans and v spans dividing the surface into a number of patches each of which is define by a different polynomial function, comprising the steps of:

tessellating the surface into successive parallel strips, each strip having a bottom edge located at a bottom v parameter value and a top edge located at a top v parameter value, said edges extending along the u coordinate fully across the surface, the top edge of a strip being coincident with the bottom edge of the immediately succeeding strip, each v span comprising multiple such strips;

tessellating each u span of each strip at successive u parameter values to determine a pair of points, one on the top edge and the other on the bottom edge of the strip, associated with each of said u parameter values, each strip of said surface being tessellated at the same u parameter values;

determining through b-spline evaluation, using at least one polynomial function corresponding to each of said successive u spans, the geometric coordinates and surface normal vector for each point of each pair, each pair of points of a strip and the immediately succeeding pair of points of the strip defining the vertices of a polygon; and

generating a shaded image of said polygons from the geometric coordinates and surface normal vectors of the points defining the vertices of said polygons to render said surface on said screen.

13. The method of claim 12 wherein:

the step of determining the geometric coordinates and surface normal vector is applied at successive u parameter values along a first strip having a bottom edge coincident with the one edge of the surface and then at successive u parameter points of each successive strip; and

further comprising the steps of;

determining a v parameter interval for each v span and generating a series of v parameter values therefrom, successive v parameter values being spaced apart by said v parameter interval; and

determining a u parameter interval for each u span of each strip and generating a series of u parameter values therefrom, successive u parameter values being spaced apart by said u parameter interval.

14. The method of claim 12 wherein the general geometry of the surface is defined by a matrix of Nv rows of Nu columns of control points;

and wherein

the step of determining the geometric coordinates and surface normal vector comprises;

determining a series of bottom coordinates and bottom v derivatives for the bottom edge of a strip of a particular v span by evaluating at the bottom v parameter value of the strip the b-spline function with control points in each column of kv rows of said matrix, said kv rows being associated with said particular v span;

determining a series of top coordinates and top v derivatives for the top edge of said strip by evaluating at the top v parameter value of the strip the b-spline function with the control points in each column of said kv rows associated with said particular v span;

evaluating the b-spline functions of the top coordinates, top v derivatives, bottom coordinates, and bottom v derivatives at successive u parameter values for each successive u span of the strip to obtain values for the u dependence of the top and bottom coordinates, for the top and bottom u derivatives and for the u dependence of the top and bottom v derivatives for each of said successive u parameter values; and

converting the values obtained from the preceding evaluation step into a set of geometric coordinates and a vertex normal for a top point and a bottom point of the strip for each u parameter value.

15. The method of claim 12 wherein the step of determining the geometric coordinates and surface normal vector is performed for all u parameter values of all u spans of a strip before such step is performed for u parameter values of an immediately succeeding strip.

16. The method of claim 12 wherein said parametric surface is an untrimmed parametric surface.

17. The method of claim 12 wherein the b-spline evaluation uses a set of polynomial functions that are determined by a set of u knot values corresponding to each of said successive u spans.

18. Apparatus for converting NURBS data representative of a parametric surface into geometric coordinates and associated surface normal vectors of vertices of polygons for subsequent rendering on the screen of a computer graphics display system, the surface having one edge extending along a u parametric coordinate for Nu-ku+1successive u spans where Nu is the dimension and ku is the order along the u coordinate and a second edge extending along an orthogonal v parametric coordinate for Nv-kv+1 successive v spans where Nv is the dimension and kv is the order along the v coordinate, the general geometry of the surface being defined by a matrix of Nv rows of Nu columns of control points, comprising:

first memory means for storing NURBS data representative of a parametric surface to be rendered, said data including a set of modelling coordinates and an associated weight w for each control point of the matrix;

graphics control processor means for transforming the control points modelling coordinates to view coordinates, converting the transforming coordinates to homogeneous coordinates, and evaluating the b-spline function of said homogeneous coordinates at successive v parameter values to obtain top coordinates and top v derivatives for a current v parameter value and bottom coordinates and bottom v derivatives for an immediately preceding v parameter value;

a plurality of parallel floating point processors for receiving data and commands from said graphics control processor means and simultaneously evaluating the b-spline functions of the top and bottom coordinates and top and bottom v derivatives, at successive u parameter values, on a per coordinate basis, to obtain values for the u dependence of the top and bottom coordinates, the top and bottom u derivatives and the top and bottom u dependence on the top v derivatives for each of said successive u parameter values; and

a further floating point processor for receiving the values obtained by said parallel floating point processors and converting said values into a set of geometric coordinates and a vertex normal for vertices of polygons to be rendered.

19. The apparatus of claim 18 wherein said graphics control processor means, plurality of floating point processors, and further floating point processor operate in pipeline fashion.

20. The apparatus of claim 18 wherein the plurality of floating point processors comprises:

four processors, one of which provides an output representative of the weight for each of said u parameter values; and

wherein the further floating point processor multiplies the outputs of the other of said parallel floating point processors by the reciprocal of the output of said one floating point processor.

21. The apparatus of claim 18 wherein the parallel floating point processors and graphics control processor means employ the Cox-DeBoor process for evaluation;

and the outputs of the individual floating point processors of said plurality are provided sequentially to said further floating point processor.

22. The apparatus of claim 18 further comprising a FIFO control points stack associated with the graphics control processor means, the stack having kv rows and Nu columns to accommodate the kv rows of control points of the matrix defining a v span;

and

wherein the graphics control processor means loads an individual successive row of said matrix into the top of said stack to define each successive v span of the surface.

23. The apparatus of claim 18 wherein said graphics control processor means:

determines a v parametric coordinate interval for each v span and generates therefrom a series of successive v parameter values separated by said v interval; and

determines a u parametric coordinate interval for each u span and generates a series of successive u parameter values separated by said u interval.

24. The apparatus of claim 18 further comprising a clipping processor and a frame buffer connected in series to an output of said further floating point processor and operating in pipeline fashion therewith.

25. The apparatus of claim 18 wherein said parametric surface is an untrimmed parametric surface.