# US 5,353,389 A · Method and apparatus for trimming B-spline descriptions of patches in a high performance three dimensional graphics system

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 5,353,389 A
- Document ID: US5353389A
- Status: Granted
- Kind: A
- Application number: 07/804,863
- Filed: 1991-12-06
- Granted: 1994-10-04
- Earliest claimed: 1987-02-05
- Assignees: Hewlett-Packard Company
- Inventors: James G. Fiasconaro
- Web page: https://patentgrep.com/patent/US5353389A

## CPC

- G06T 17/00: Three-dimensional [3D] modelling for computer graphics
- G06T 17/20: Finite element generation, e.g. wire-frame surface description, {tesselation}
- G09G 1/06: using single beam tubes (G09G1/26, G09G1/28 take precedence), {e.g. three-dimensional or perspective representation, rotation or translation of display pattern, hidden lines, shadows (G09G1/28 takes precedence; stereoscopic TV-systems, details thereof H04N13/00; oscilloscopes for three-dimensional representation G01R13/206; vectorscopes G01R13/208)}
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G09G: ARRANGEMENTS OR CIRCUITS FOR CONTROL OF INDICATING DEVICES USING STATIC MEANS TO PRESENT VARIABLE INFORMATION (arrangements for transferring data between digital computers and displays G06F3/14; static indicating arrangements comprising an association of a number of separate sources or light control cells G09F9/00; static indicating arrangements comprising integral associations of a number of light sources H01J, H01K, H10H, H05B33/12; scanning, transmission or reproduction of documents or the like, e.g. facsimile transmission, details thereof H04N1/00)

## Abstract

A graphics accelerator responds to commands from a computer in a graphic system by storing the definitions of nonuniform rational B-spline patches and their associated triming curves. The graphics accelerator then produces device coordinates for trimmed polygons computed for each patch and sends these polygons to a display. Various improvements are incorporated to minimize the effects of roundoff error. The B-spline definitions of the trimming curves in the uv parameter space of each patch are converted to approximating short straight line segments. Untrimmed polygon vertices, the end points of the straight line segments and the intersections of the straight line segments with subspan boundaries corresponding to polygon edges are kept in a data structure of linked lists of vertex tables. The data structure is traversed to determine new polygon vertices for trimmed polygons. The trimming mechanism is compatible with recursive subdivision of patches to overcome pratical limitations on the number of trimming curves that may be associated with each patch. The length of the straight line segments of the trimming curves is adjusted to compensate for less than ideal parameterization of the trimming curve functions. Associated with each trimming curve within a patch is information about the position of that trimming curve in the span. As each polygon for that patch is generated, those trimming curves that are clearly outside the clip limits for that polygon are excluded from consideration. This reduces the average number of trimming curves that must be processed for the patch, and increases the speed of the graphics accelerator.

## Claims

### Claim 1

In a graphics display system where the shape of a polygon upon a surface in XYZ space is determined by a corresponding subspan, the subspan described by a collection of original vertices in a parameter space and trimmed according to a piecewise linear trimming curve having a sequence of consecutive segments in the parameter space, a method of polygon rendering comprising the steps of:
a. traversing the consecutive segments of the trimming curve in sequential order to find for each segment any points of intersection in the parameter space between the trimming curve and the boundaries of the subspan;
b. classifying those points of intersection as new vertices of the subspan and also as either points of entrance into the subspan, as points of exit from the subspan or as middle points between points of entrance and points of exit;
c. rendering a trimmed polygon described by the new vertices and those original vertices that lie upon that portion of the subspan remaining after being cut by the trimming curve; and
d. displaying upon a graphics system a visual image of the trimmed polygon rendered in step (c).