Method and apparatus for the rendering of trimmed nurb surfaces

Claim 2

The method for the tessellation of graphic images comprising trimmed NURBS surfaces as set forth in claim 1, wherein said step of compiling comprising the steps of: reducing the NURBS into at least one Bezier patch; dividing the trimming loops into monotone trimming chains per Bezier patch; and dividing each patch into at least one u-v monotone "v-region", each v-region formed by a top base, bottom base, left side and right side, said top and bottom base defined by isoparametric lines along the u axis and said right and left sides defined by u, v monotone lines delineated by a trimming chain or a border of the patch.

Claim 3

The method for the tessellation of graphic images comprising trimmed NURBS surfaces as set forth in claim 2, further comprising the step of traversing each patch by determining a uniform step size for each patch, said step size used to tessellate each patch into a plurality of triangles.

Claim 4

The method for the tessellation of graphic images comprising trimmed NURBS surfaces as set forth in claim 3, wherein said step of traversing each v-region further comprises the step of superimposing a uniform grid of cells determined from the boundaries of the v-region and the uniform step size in u and v, wherein said step of tessellating each v-region comprises tessellating each row of cells into a plurality of triangles.

Claim 5

The method for the tessellation of graphic images comprising trimmed NURBS surfaces as set forth in claim 4, wherein each trimming chain comprises at least one segment, each segment identified by a coordinate in u,v and an indication whether the segment is increasing or decreasing in the u or v directions.

Claim 6

The method for the tessellation of graphic images comprising trimmed NURBS surfaces as set forth in claim 5, wherein each segment is a Bezier curve.

Claim 7

The method for the tessellation of graphic images comprising trimmed NURBS surfaces as set forth in claim 5, wherein each segment is a linear segment.

Claim 8

The method for the tessellation of graphic images comprising trimmed NURBS surfaces as set forth in claim 5, wherein said step of compiling further comprises the step of identifying the extreme vertices and intercept vertices at patch border crossings of the trimming chains.

Claim 9

The method for the tessellation of graphic images comprising trimmed NURBS surfaces as set forth in claim 8, wherein an extreme vertex is identified if a segment has an opposite u or v direction from a previous adjacent segment of the trimming chain or has a u/v extreme within itself if it is a Bezier curve, and a border vertex is identified at the location a segment crosses a patch boundary.

Claim 10

The method for the tessellation of graphic images comprising trimmed NURBS surfaces as set forth in claim 9, further comprising the step of classifying each vertex according to a type.

Claim 11

The method for the tessellation of graphic images comprising trimmed NURBS surfaces as set forth in claim 10, wherein the step of dividing each patch into at least one u-v monotone v-region comprises the step of: identifying at least one pair of intercept vertices on the left and right sides; identifying the beginning of an active v-region according to the identified intercept vertices on a top border; processing the remaining intercept vertices and extreme vertices in descending order according to the v coordinate value of the vertices, said step comprising inspecting the type of each vertex and forming the bottom and closure of active v-regions and the opening of new v-regions according to the type of vertex.

Claim 12

The method for the tessellation of graphic images comprising trimmed NURBS surfaces as set forth in claim 2, wherein the step of traversing each patch comprises the steps of: determining the derivative bounds of the curved surface to be tessellated and rendered; transforming the derivative bounds to a Lighting Coordinate (LC) Space in accordance with the norm of the transform from modeling coordinate (MC) space to LC space; transforming the control points to LC space in accordance with the transform from MC space to LC space; translating the tessellation criteria to LC space in accordance with the maximum scale of the viewing transformation from DC space to LC space; and determining the uniform step size in LC space using the derivative bounds, the control points and tessellation criteria.

Claim 13

The method for the tessellation of graphic images comprising trimmed NURBS surfaces as set forth in claim 1, wherein said step of compiling further comprising the step of providing gap avoidance information with each patch; said method further comprising the step of generating triangles to fill in gaps between patches.

Claim 14

The method for the tessellation of graphic images comprising trimmed NURBS surfaces as set forth in claim 13, wherein the step of generating triangles to fill in gaps between patches comprises the generation of an adjacency strip associated with a patch having the larger step size which adjusts the size of the triangles in the adjacency strip to remove gaps.

Claim 15

The method for the tessellation of graphic images comprising trimmed NURBS surfaces as set forth in claim 13, wherein the step of generating triangles to fill in gaps between patches comprises the generation of stitching strip by adding triangles between the patches.

Claim 16

In a computer system comprising a central processing unit (CPU), memory and input/output devices including a graphic display controller coupled to a graphic display device, an apparatus for the tessellation of graphic images comprising trimmed NURBS surfaces for rendering on the graphic display device, each trimmed NURBS having a first set of control points defining the surface and a second set of control points defining at least one trimming loop through the surface, said control points being defined in a Model Coordinate (MC) space, said graphic display device defined according to Device Coordinate (DC) space, said apparatus comprising: a compiler for compiling the trimmed NURBS into at least one patch comprising at least one u-v monotone v-region; means for traversing each v-region, comprising; means for tessellating each v-region into a plurality of triangles, and means for generating pixel data representative of each triangle, each pixel data specifying the intensity of the pixel to be displayed on the graphic display device; and a frame buffer memory coupled to the means for generating pixel data for storing each pixel data at a location corresponding to the location of the pixel in the device coordinate space; said graphic display controller reading the pixel data stored in the frame buffer and generating control signals to actuate the pixels at the location and intensity indicated by the pixel data; wherein trimmed NURBS surfaces are generated and displayed on the graphics display device.

Claim 17

The apparatus for the tessellation of graphic images comprising trimmed NURBS surfaces as set forth in claim 16, wherein said compiler comprises: means for reducing the NURBS into at least one Bezier patch, means for dividing the trimming loops into monotone trimming chains per Bezier patch; and means for dividing each patch into at least one u-v monotone v-region, each v-region formed by a top base, bottom base, left side and right side, said top and bottom base defined by isoparametric lines along the u axis and said right and left sides defined by u, v monotone lines delineated by a trimming chain or a border of the patch.

Claim 18

The apparatus for the tessellation of graphic images comprising trimmed NURBS surfaces as set forth in claim 17 further comprising means for traversing each patch, comprising means for determining a uniform step size for each patch, said step size used to tessellate each patch into a plurality of triangles.

Claim 19

The apparatus for the tessellation of graphic images comprising trimmed NURBS surfaces as set forth in claim 18, wherein said means for traversing each v-region further comprises a uniform grid of cells determined from the boundaries of the v-region and the uniform step size in u and v, wherein said means for tessellating comprises means for tessellating each row of cells into a plurality of triangles.

Claim 20

The apparatus for the tessellation of graphic images comprising trimmed NURBS surfaces as set forth in claim 19, wherein each trimming chain comprises at least one segment, each segment identified by a coordinate in u,v and an indication whether the segment is increasing or decreasing in the u or v directions.

Claim 21

The apparatus for the tessellation of graphic images comprising trimmed NURBS surfaces as set forth in claim 20, wherein said means for compiling further comprises means for identifying the extreme vertices and the intercept vertices at patch border crossings of the trimming chains.

Claim 22

The apparatus for the tessellation of graphic images comprising trimmed NURBS surfaces as set forth in claim 21, wherein an extreme vertex is identified if a segment has an opposite u or v direction from a previous adjacent segment of the trimming chain and a border vertex is identified at the location a segment crosses a patch boundary.

Claim 23

The apparatus for the tessellation of graphic images comprising trimmed NURBS surfaces as set forth in claim 22, further comprising a means for classifying each vertex according to a type.

Claim 24

The apparatus for the tessellation of graphic images comprising trimmed NURBS surfaces as set forth in claim 23, wherein the means for dividing each patch into at least one u-v monotone v-region comprises: means for identifying at least one pair of intercept vertices on the left and right sides; means for identifying the beginning of an active v-region according to the identified intercept vertices on the top border; means for processing the remaining intercept vertices and extreme vertices in descending order according to the v coordinate value of the vertices, said step comprising determining the type of each vertex and forming the bottom and closure of active v-regions and the opening of new v-regions according to the type of vertex.

Claim 25

A computer system for the tessellation of graphic images comprising trimmed NURBS surfaces for rendering on the graphic display device, each trimmed NURBS having a first set of control points defining the surface and a second set of control points defining at least one trimming loop through the surface, said control points being defined in a Model Coordinate (MC) space, said graphic display device defined according to Device Coordinate (DC) space, said apparatus comprising: a host processor, said host processor, compiling the trimmed NURBS surface into at least one patch comprising at least one v-region by reducing the NURBS into at least one Bezier patch, dividing the trimming loops into monotone trimming chains according to the patch the portion of the trimming loop delimits, and dividing each patch into at least one u-v monotone v-region, each v-region formed by a top base, bottom base, left side and right side, said top and bottom base defined by isoparametric lines along the u axis and said right and left sides defined by u, v monotone lines delineated by a trimming chain or a border of the patch, and traversing each patch, by determining a uniform step size for each patch, said step size used to tessellate each patch into a plurality of triangles; a graphics processing subsystem coupled to the host processor, said graphics processing subsystem superimposing a uniform grid of cells determined from the boundaries of the v-region and the uniform step size in u and v, tessellating each row of cells into a plurality of triangles, generating pixel data representative of each triangle, each pixel data specifying the intensity of the pixel to be displayed on the graphic display device; and a frame buffer coupled to the graphics processing subsystem, for storing each pixel data in a frame buffer, each pixel data being stored at a location in the frame buffer corresponding to the location of the pixel in the device coordinate space; and a graphic display controller coupled to the frame buffer and the graphic display device for reading the pixel data stored in the frame buffer and generating control signals to actuate the pixels on the graphic display device at the location and intensity indicated by the pixel data; wherein trimmed NURBS surfaces are generated and displayed on the graphics display device.

Claim 26

The apparatus as set forth in claim 25, wherein said graphics processing subsystem comprises: at least one floating point processing unit for generating triangles in accordance with the uniform step size, lighting the triangles in accordance with light sources defined for the graphic image to be rendered and transforming the polygon to DC space from LC space; and at least one dedicated graphics processor coupled to the floating point processor for receiving transformed polygons and for generating pixel data for each polygon received.