EP0277832A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Method for graphic display
Assignee: HP Inc
•
Filing: 1988-02-04
•
Granted: —
•
Expires: 2008-02-04
Abstract
Abstract A graphics accelerator (91) responds to commands from a computer (86) in a graphic system by storing the definitions of non-uniform rational B-spline patches (12,13,14,15) and their associated trimming curves S₁-S₉). The graphics accelerator then produces device coordinates for trimmed polygons computed for each patch and sends these polygons to a display (94). Various improvements are incorporated to minimize the effects of roundoff error. The B-spline definitions of the trimming curves (27) 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 (Fig 15). The data structure is traversed to determine new polygon vertices for trimmed polygons. The trimming mechanisms is compatible with recursive subdivision of patches to overcome practical 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.
Inventors
- 👤 James G. Fiasconaro
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-10-28 14:20
CPC Classifications
G; G06; G06T; G06T17/00; G06T17/20; G09; G09G; G09G1/00; G09G1/06
Claims Analysis
Total Claims: 26
Claim 1
Independent Claim
122 words
A method of producing a graphic representation of a surface by the generation of surface patches defined by first parametric functions, and trimming the surface patches with second parametric functions defining a trimming curve, characterised in that trimming is performed in a graphics accelerator (91) operable to compute point by point representations of the trimming curve (8) and the subspans (35, A1 - A16 in parameter space (30) whose associated polygons in coordinate space correspond to an associated patch, to build a data structure of linked lists of vertex tables each representing an untrimmed polygon and any trimming curves that cut it, and to traverse the lists in the data structure to produce a list of trimmed polygon vertices in device coordinates.
Claim 2
Independent Claim
122 words
A method of producing a graphic representation of a surface by the generation of surface patches defined by first parametric functions, and trimming the surface patches with second parametric functions defining a trimming curve, characterised in that trimming is performed in a graphics accelerator (91) operable to compute point by point representations of the trimming curve (8) and the subspans (35, A1 - A16 in parameter space (30) whose associated polygons in coordinate space correspond to an associated patch, to build a data structure of linked lists of vertex tables each representing an untrimmed polygon and any trimming curves that cut it, and to traverse the lists in the data structure to produce a list of trimmed polygon vertices in device coordinates.
Claim 3
Dependent Claim
37 words
A method according to claim 1 in which trimming is performed in the parameter space of untrimmed b-spline surface patches described by the first parametric functions and in which the second parametric functions are also b-spline functions.
Claim 4
Independent Claim
189 words
A method of trimming a parametric description (4) of a surface patch (2) with a trimming function (9) describing a region (8) in the parameter space (3) of the surface patch, the method comprising the steps of: a. selecting an ordered collection of untrimmed points in the parameter space (3) whose interconnecting line segmets (59, 60, 61, 62) are boundaries of a region (8) to be trimmed; b. evaluating a trimming function to obtain an ordered collection of trimming points (140-145) in the parameter space; c. determining points of intersection (B,E) between straight line segments connecting the trimming points and the boundaries (59,60,61,62) of an individual subspan within the surface patch to be trimmed; d. identifying an order collection of trimming points that are inside the region to be trimmed; e. interleaving the ordered collection of untrimmed points, the points of intersection and the ordered collection of points on the region to be trimmed into a data structure (Fig 15); f. traversing the data structure to identify and select the points therein that describe the trimmed region, and g. rendering the identified and selected points as the trimmed region.
Claim 5
Independent Claim
189 words
A method of trimming a parametric description (4) of a surface patch (2) with a trimming function (9) describing a region (8) in the parameter space (3) of the surface patch, the method comprising the steps of: a. selecting an ordered collection of untrimmed points in the parameter space (3) whose interconnecting line segmets (59, 60, 61, 62) are boundaries of a region (8) to be trimmed; b. evaluating a trimming function to obtain an ordered collection of trimming points (140-145) in the parameter space; c. determining points of intersection (B,E) between straight line segments connecting the trimming points and the boundaries (59,60,61,62) of an individual subspan within the surface patch to be trimmed; d. identifying an order collection of trimming points that are inside the region to be trimmed; e. interleaving the ordered collection of untrimmed points, the points of intersection and the ordered collection of points on the region to be trimmed into a data structure (Fig 15); f. traversing the data structure to identify and select the points therein that describe the trimmed region, and g. rendering the identified and selected points as the trimmed region.
Claim 6
Dependent Claim
99 words
A graphics accelerator for trimming a surface patch rendered from a description of a portion of a surface to be displayed, characterised in that it includes means for computing a point by point representation of a trimming curve in parameter space, means for computing a point to point representation of a subspan in parameter space whose associated polygon in coordinate space approximates a portion of the surface patch, and means for determining where straight line approximating segments of the trimming curves cross subspan boundaries and discarding selected vertices of the subspans to trim away portions of the associated polygon.
Claim 7
Dependent Claim
99 words
A graphics accelerator for trimming a surface patch rendered from a description of a portion of a surface to be displayed, characterised in that it includes means for computing a point by point representation of a trimming curve in parameter space, means for computing a point to point representation of a subspan in parameter space whose associated polygon in coordinate space approximates a portion of the surface patch, and means for determining where straight line approximating segments of the trimming curves cross subspan boundaries and discarding selected vertices of the subspans to trim away portions of the associated polygon.
Claim 8
Dependent Claim
57 words
A graphics accelerator according to Claim 4, characterised in that it includes means for building a data structure of linked lists of vertex tables representing the untrimmed polygon and any trimming curves that cut it, and means for traversing the lists in the data structure whereby to produce a list of trimmed polygon vertices in device coordinates.
Claim 9
Dependent Claim
98 words
In a graphics display system that represents a surface (1) in XYZ space with first parametric functions (4) in uv space, the first parametric functions trimmed by a trimming curve (8) defined by second parametric functions (9) in t space, a method of selecting a step size (73) in t space for evaluating the second parametric functions at uniform intervals of t characterized in that the successive steps in t being selected to yield a corresponding sequence of points (180,181,182) in uv space where, for each point in the sequence, its successor is approximately a selected distance away.
Claim 10
Dependent Claim
98 words
In a graphics display system that represents a surface (1) in XYZ space with first parametric functions (4) in uv space, the first parametric functions trimmed by a trimming curve (8) defined by second parametric functions (9) in t space, a method of selecting a step size (73) in t space for evaluating the second parametric functions at uniform intervals of t characterized in that the successive steps in t being selected to yield a corresponding sequence of points (180,181,182) in uv space where, for each point in the sequence, its successor is approximately a selected distance away.
Claim 11
Dependent Claim
119 words
In a graphics system where a portion of a subspan (49,55) is trimmed away according to a trimming curve (50,54), a method of compensating the errors of finite precision arithmetic characterized by detecting that for two different points along the trimming curve (50,54) there obtain identical points of intersection (52,53,56,57) with a boundary of the subspan (59,55), by treating the identical points of intersection (52,53) as new vertices of the trimmed subspan (49) when the trimming curve (50) contains an associated outside point (51) that is just barely outside the subspan (49), and by ignoring the points of intersection (56,57) when the trimming curve (54) contains an associated inside point (58) that is just barely inside the subspan (55).
Claim 12
Dependent Claim
119 words
In a graphics system where a portion of a subspan (49,55) is trimmed away according to a trimming curve (50,54), a method of compensating the errors of finite precision arithmetic characterized by detecting that for two different points along the trimming curve (50,54) there obtain identical points of intersection (52,53,56,57) with a boundary of the subspan (59,55), by treating the identical points of intersection (52,53) as new vertices of the trimmed subspan (49) when the trimming curve (50) contains an associated outside point (51) that is just barely outside the subspan (49), and by ignoring the points of intersection (56,57) when the trimming curve (54) contains an associated inside point (58) that is just barely inside the subspan (55).
Claim 13
Dependent Claim
139 words
In a graphics display system where a polygon upon a surface (1) in XYZ space is altered in shape by trimming of the correspondong subspan (5) in parameter space, a method of polygon rendering characterized by the steps of: a) traversing the trimming curve to find points of intersection (141,145) between the trimming curve and the subspan; b) classifying those points of intersection as new vertices of the subspan and as either points of entrance (141,B) into the subspan or as points of exit from (145,E) from the span; c) classifying points (142,143,144,M) along the trimming curve going from a point of entrance toward a point of exit as new vertices of the subspan; and d) rendering as a polygon of altered shape a portion of the subspan cut by the trimming curve in conjunction with the new vertices.
Claim 14
Dependent Claim
139 words
In a graphics display system where a polygon upon a surface (1) in XYZ space is altered in shape by trimming of the correspondong subspan (5) in parameter space, a method of polygon rendering characterized by the steps of: a) traversing the trimming curve to find points of intersection (141,145) between the trimming curve and the subspan; b) classifying those points of intersection as new vertices of the subspan and as either points of entrance (141,B) into the subspan or as points of exit from (145,E) from the span; c) classifying points (142,143,144,M) along the trimming curve going from a point of entrance toward a point of exit as new vertices of the subspan; and d) rendering as a polygon of altered shape a portion of the subspan cut by the trimming curve in conjunction with the new vertices.
Claim 15
Dependent Claim
91 words
In a graphics display system that represents a surface (1) in XYZ space with first parametric functions (4) in uv space, the first parametric functions trimmed by a trimming curve (8) defined by second parametric functions (9) in t space, a method of correcting for excessively close points in uv space along the trimming curve given a particular preselected step size (73) in t, characterized in that a succeeding point (76) along the trimming curve that is not at least a selected distance away from a preceding point (78) is discarded.
Claim 16
Dependent Claim
91 words
In a graphics display system that represents a surface (1) in XYZ space with first parametric functions (4) in uv space, the first parametric functions trimmed by a trimming curve (8) defined by second parametric functions (9) in t space, a method of correcting for excessively close points in uv space along the trimming curve given a particular preselected step size (73) in t, characterized in that a succeeding point (76) along the trimming curve that is not at least a selected distance away from a preceding point (78) is discarded.
Claim 17
Dependent Claim
107 words
In a graphics display system that represents a surface (1) in XYZ space with first parametric functions (4) in uv space, the first parametric functions trimmed by a trimming curve (8) composed of a plurality of segments (S₁-S₉) each defined by respective sets of parametric trimming functions, a method of correcting errors arising from finite precision arithmetic characterized in that when traversing the trimming curve to trim the first parametric function the point in uv space corresponding to the beginning of the next segment of the trimming curve is used in place of the point in uv space corresponding to the actual end of the present segment.
Claim 18
Dependent Claim
107 words
In a graphics display system that represents a surface (1) in XYZ space with first parametric functions (4) in uv space, the first parametric functions trimmed by a trimming curve (8) composed of a plurality of segments (S₁-S₉) each defined by respective sets of parametric trimming functions, a method of correcting errors arising from finite precision arithmetic characterized in that when traversing the trimming curve to trim the first parametric function the point in uv space corresponding to the beginning of the next segment of the trimming curve is used in place of the point in uv space corresponding to the actual end of the present segment.
Claim 19
Independent Claim
49 words
A method of rendering trimmed surface patches as polygons themselves rendered from trimmed subspans in a parameter space, the subspans trimmed by parametric trimming curves, characterized in that a surface patch is divided into subpatches when the number of trimming curves for the surface patch exceeds a selected number.
Claim 20
Independent Claim
49 words
A method of rendering trimmed surface patches as polygons themselves rendered from trimmed subspans in a parameter space, the subspans trimmed by parametric trimming curves, characterized in that a surface patch is divided into subpatches when the number of trimming curves for the surface patch exceeds a selected number.
Claim 21
Independent Claim
77 words
A method of compensating errors of finite precision arithmetric when determining points of intersection (NEW P₁, NEW P₂) between a piecewise representation of a trimming cure (42) and a clip window (43) the points of intersection, the piecewise representation and the clip window all being in the same coordinate system, characterized in that computed points of intersection are inspected to determine if they lie upon the boundary and are adjusted to do so if they do not.
Claim 22
Independent Claim
77 words
A method of compensating errors of finite precision arithmetric when determining points of intersection (NEW P₁, NEW P₂) between a piecewise representation of a trimming cure (42) and a clip window (43) the points of intersection, the piecewise representation and the clip window all being in the same coordinate system, characterized in that computed points of intersection are inspected to determine if they lie upon the boundary and are adjusted to do so if they do not.
Claim 23
Independent Claim
122 words
A method of avoiding errors of finite precision arithmetric when determining a point of intersection (NEW P₁, NEW P₂) between a piecewise approximate (P₁, P₂) of a trimming curve and a common boundary between two clip windows (WINDOW₁, WINDOW₂) having a mutual boundary, the point of intersection, the piecewise representation and the clip windows all being in the same coordinate system, characterized in that one end (P₁) of the straight line segment of the piecewise approximation that crosses the mutual boundary is selected as a reference relative to which both a first point of intersection (NEW P₂) for one of the clip windows (WINDOW₁) and a second identical point of intersection (NEW P₁) for the other clip window (WINDOW ₂) are computed.
Claim 24
Independent Claim
122 words
A method of avoiding errors of finite precision arithmetric when determining a point of intersection (NEW P₁, NEW P₂) between a piecewise approximate (P₁, P₂) of a trimming curve and a common boundary between two clip windows (WINDOW₁, WINDOW₂) having a mutual boundary, the point of intersection, the piecewise representation and the clip windows all being in the same coordinate system, characterized in that one end (P₁) of the straight line segment of the piecewise approximation that crosses the mutual boundary is selected as a reference relative to which both a first point of intersection (NEW P₂) for one of the clip windows (WINDOW₁) and a second identical point of intersection (NEW P₁) for the other clip window (WINDOW ₂) are computed.
Claim 25
Dependent Claim
93 words
In a graphics system where a portion of a subspan (59-62) is trimmed away according to a trimming curve (140-145), a method of rendering a trimmed polygon correspond to the trimmed subspan characterized by the steps traversing the trimming curve to build a list of points of intersection between the trimming curve and the subspan, combining into a data structure (45-48 & Fig 15) the list of points of intersection and a collection of vertex tables for the untrimmed subspan, and traversing the data structure to mark which vertices are to be visible.
Claim 26
Dependent Claim
93 words
In a graphics system where a portion of a subspan (59-62) is trimmed away according to a trimming curve (140-145), a method of rendering a trimmed polygon correspond to the trimmed subspan characterized by the steps traversing the trimming curve to build a list of points of intersection between the trimming curve and the subspan, combining into a data structure (45-48 & Fig 15) the list of points of intersection and a collection of vertex tables for the untrimmed subspan, and traversing the data structure to mark which vertices are to be visible.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.