 |
Claims  |
|
|
I claim:
1. In a graphic display system, a method of trimming a polygonal region in
a two dimensional (J,K) space, the method comprising the steps of:
a. selecting in a two dimensional (J,K) space an ordered collection of
original vertices describing an untrimmed polygonal region in the (J,K)
space;
b. selecting two points P1 and P2 along a trimming curve in (J,K) space, P1
and P2 representing a directed line segment P1P2 that is a portion of the
trimming curve;
c. setting a first flag to a first value when the directed line segment
P1P2 is at least partially within the untrimmed polygonal region and to a
second value when the directed line segment P1P2 is wholly outside and
separated from the untrimmed polygonal region;
d. setting a second flag to a third value when P1 is outside the untrimmed
polygonal region and the directed line segment P1P2 crosses into the
untrimmed polygonal region, and to a fourth value when P1 and the directed
line segment P1P2 are otherwise;
e. subsequent to setting the second flag to the third value in step (d),
replacing the existing value of P1 with an adjusted value equal to that of
the point where the directed line segment P1P2 crosses into the untrimmed
polygonal region;
f. setting a third flag to a fifth value when the directed line segment
P1P2 crosses out of the untrimmed polygonal region and P2 is outside the
untrimmed polygonal region, and to a sixth value when the directed line
segment P1P2 and P2 are otherwise;
g. subsequent to setting the third flag to the fifth value in step (f),
replacing the existing value of P2 with an adjusted value equal to that of
the point where the directed line segment P1P2 crosses out of the
untrimmed polygonal region;
h. collecting, in the order in which they occur, an initial adjusted value
for P1, any subsequent intervening value of P2 for which the first value
for the first flag is associated, followed by a final adjusted value for
P2, into an ordered list of points in (J,K) space along the trimming curve
and which belong to the untrimmed polygonal region;
i. combining the ordered collection of original vertices selected in step
(a) with the ordered list collected in step (h) into a linked data
structure of points in (J,K) space, the links in the data structure
allowing the points to be visited in a sequence corresponding to the order
in which adjacent vertices of a trimmed polygonal region in (J,K) space
are encountered during a traversal of the trimming curve and any remaining
untrimmed boundaries between the original untrimmed vertices;
j. traversing the linked data structure to produce a sequence of adjacent
vertices for a trimmed polygonal region in the two dimensional (J,K)
space; and
k. displaying a visual image upon the graphics display system in accordance
with the trimmed polygon region.
2. In a graphics display system, a method of trimming a polygonal region in
(u,v) parameter space, the vertices of the trimmed polygonal region used
as arguments in mapping functions to produce the vertices of a trimmed
polygon in (X,Y,Z) space, the method comprising the steps of:
a. selecting in a (u,v) parameter space an ordered collection of original
vertices describing an untrimmed polygonal region in the (u,v) parameter
space;
b. selecting two points P1 and P2 along a trimming curve in (u,v) space, P1
and P2 representing a directed line segment P1P2 that is a portion of the
trimming curve;
c. setting a first flag to a first value when the directed line segment
P1P2 is at least partially within the untrimmed polygonal region and to a
second value when the directed line segment P1P2 is wholly outside and
separated from the untrimmed polygonal region;
d. setting a second flag to a third value when P1 is outside the untrimmed
polygonal region and the directed line segment P1P2 crosses into the
untrimmed polygonal region, and to a fourth value when P1 and the directed
line segment P1P2 are otherwise;
e. subsequent to setting the second flag to the third value in step (d),
replacing the existing value of P1 with an adjusted value equal to that of
the point where the directed line segment P1P2 crosses into the untrimmed
polygonal region;
f. setting a third flag to a fifth value when the directed line segment
P1P2 crosses out of the untrimmed polygonal region and P2 is outside the
untrimmed polygonal region, and to a sixth value when the directed line
segment P1P2 and P2 are otherwise;
g. subsequent to setting the third flag to the fifth value in step (f),
replacing the existing value of P2 with an adjusted value equal to that of
the point where the directed line segment P1P2 crosses out of the
untrimmed polygonal region;
h. collecting, in the order in which they occur, an initial adjusted value
for P1, any subsequent intervening value of P2 for which the first value
for the first flag is associated, followed by a final adjusted value for
P2, into an ordered list of points in (u,v) parameter space along the
trimming curve and which belong to the untrimmed polygonal region;
i. combining the ordered collection of original vertices selected in step
(a) with the ordered list collected in step (h) into a linked data
structure of points in (u,v) parameter space, the links in the data
structure allowing the points to be visited in a sequence corresponding to
the order in which adjacent vertices of a trimmed polygonal region in
(u,v) space are encountered during a traversal of the trimming curve and
any remaining untrimmed boundaries between the original untrimmed
vertices;
j. traversing the linked data structure to produce a sequence of adjacent
vertices for a trimmed polygonal region in the (u,v) parameter space;
k. using the sequence of adjacent vertices in the (u,v) parameter space
produced by the traversal of step (j) as arguments for mapping functions
to produce a corresponding sequence of coordinates in (X,Y,Z) space for a
trimmed polygon; and
l. displaying upon a graphics display system a visible image of the
coordinates in (X,Y,Z) space of a trimmed polygonal region.
3. A method of trimming a polygonal region in (u,v) parameter space, the
vertices of the trimmed polygonal region used as arguments in mapping
functions to produce the vertices of a trimmed polygon in (X,Y,Z) space
and representing the surface of an object whose visual projection onto an
(X,Y) plane is electronically produced from a memory of at least xy-many
addressable locations, each location containing at least one pixel
intensity value and a Z value, the method comprising the steps of:
a. selecting in a (u,v) parameter space an ordered collection of original
vertices describing an untrimmed polygonal region in the (u,v) parameter
space;
b. selecting two points P1 and P2 along a trimming curve in (u,v) space, P1
and P2 representing a directed line segment P1P2 that is a portion of the
trimming curve;
c. setting a first flag to a first value when the directed line segment
P1P2 is at least partially within the untrimmed polygonal region and to a
second value when the directed line segment P1P2 is wholly outside and
separated from the untrimmed polygonal region;
d. setting a second flag to a third value when P1 is outside the untrimmed
polygonal region and the directed line segment P1P2 crosses into the
untrimmed polygonal region, and to a fourth value when P1 and the directed
line segment P1P2 are otherwise;
e. subsequent to setting the second flag to the third value in step (d),
replacing the existing value of P1 with an adjusted value equal to that of
the point where the directed line segment P1P2 crosses into the untrimmed
polygonal region;
f. setting a third flag to a fifth value when the directed line segment
P1P2 crosses out of the untrimmed polygonal region and P2 is outside the
untrimmed polygonal region, and to a sixth value when the directed line
segment P1P2 and P2 are otherwise;
g. subsequent to setting the third flag to the fifth value in step (f),
replacing the existing value of P2 with an adjusted value equal to that of
the point where the directed line segment P1P2 crosses out of the
untrimmed polygonal region;
h. collecting, in the order in which they occur, an initial adjusted value
for P1, any subsequent intervening value of P2 for which the first value
for the first flag is associated, followed by a final adjusted value for
P2, into an ordered list of points in (u,v) parameter space along the
trimming curve and which belong to the untrimmed polygonal region;
i. combining the ordered collection of original vertices selected in step
(a) with the ordered list collected in step (h) into a linked data
structure of points in (u,v) parameter space, the links in the data
structure allowing the points to be visited in a sequence corresponding to
the order in which adjacent vertices of a trimmed polygonal region in
(u,v) space are encountered during a traversal of the trimming curve and
any remaining untrimmed boundaries between the original untrimmed
vertices;
j. traversing the linked data structure to produce a sequence of adjacent
vertices for a trimmed polygonal region in the (u,v) parameter space;
k. using the sequence of adjacent vertices in the (u,v) parameter space
produced by the traversal of step (j) as arguments for mapping functions
to produce a corresponding sequence of coordinates in (X,Y,Z) space for a
trimmed polygon;
l. addressing a memory of at least xy-many addressable location according
to the X and Y coordinate values produced in step (k) and then storing in
the addressed location at least one pixel intensity value associated with
the (X,Y,Z) coordinate produced in step (k) and also storing in the
addressed location the Z value produced in step (k); and
m. electronically generating a visible display in an XY plane according to
the Z values and pixel intensity values stored by step (l). |
|
 |
|
 |
Claims |
|
|
|
Description |
|
|
BACKGROUND AND SUMMARY OF THE INVENTION
A typical high performance three dimensional graphics system will describe
a surface to be rendered as surface patches defined by functions for each
patch. Such functions might be, for example, nonuniform rational
B-splines. The use of B-splines imposes certain limitations upon the edges
of surface patches. Associated with B-spline functions is a normally
rectangular uv parameter space. Parametric patch generation functions of u
and v compute the values of the coordinates in XYZ space. The rectangular
uv space limits the exactness with which the B-spline patch generation
functions can represent surface patches having edges of certain shapes.
For example, it is difficult to produce a good B-spline description for a
patch that is a rectangular region with a circular portion removed from
its interior. Either of the rectangular region or the circular portion by
themselves would be practical, but their combination is too complex a
primitive for a single unified B-spline description at the patch level.
Subdividing the patch thwarts the motive for having patches in the first
place. Trimming is a way to augment the B-spline description of the
rectangular region with another one for the circular portion, and
producing a hybrid surface patch in which one B-spline description "trims
away" the surface described by another.
In the prior art, trimming has been performed by the software of the
graphics system prior to the sending of device coordinates to the display
hardware. Such trimming is necessarily a very complex task, and is
generally too slow for use with moving images or interactive systems. It
would be desirable to retain the use of B-splines and achieve the
advantages offered by that technique of surface description, but at the
same time allow high speed trimming.
According to a preferred method of the invention, trimming is performed on
B-spline surface patch descriptions in a hardware graphics accelerator. It
receives B-spline descriptions of the patch generation functions for the
untrimmed patches and B-spline descriptions of trimming curves in the uv
parameter space of the patch generation functions. The B-spline
descriptions of the trimming curves are themselves functions of a
parameter t. The graphics accelerator computes a sufficiently dense point
by point representation of each trimming curve in uv space, in addition to
point by point representations of the individual subspans in uv space
whose associated polygons in XYZ space approximate the patch. The graphics
accelerator determines where straight line approximating segments of the
trimming curves cross subspan boundaries and changes the vertices of the
subspans to trim away portions of the associated polygon. It does this by
building a data structure of linked lists of vertex tables that represent
the untrimmed polygon and any trimming curves that cut it. An appropriate
traversal of the lists in the data structure produces a list of trimmed
polygon vertices in device coordinates That list may then be further
processed to the pixel level by other hardware in the graphics
accelerator.
Considerable attention is paid to avoiding the evils of roundoff error. A
mechanism for describing where in a span a trimming curve is located
allows the trimming operation to exclude from consideration those trimming
curves that cannot possibly affect the polygon being processed. Another
mechanism compensates for the effects of a non-ideal parameterization of
the trimming curve functions, to prevent the production of an
unnecessarily high number of polygon vertices. The trimming method is also
compatible with recursive subdivision of patches to handle patches with a
high number of trimming curves.
BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 is an illustration of a surface in XYZ space approximated by patches
formed by mapping spans of a two dimensional uv parameter space into XYZ
space with parametric patch generation functions, such as nonuniform
rational B-splines
FIG. 2 shows how a parametric function of a one dimensional t space can
define a trimming curve in uv space that in turn can be mapped into XYZ
space to identify a region that is absent from the surface.
FIG. 3 illustrates a parametric trimming curve function segmented over
several spans of the one dimensional t space and defining a trimming curve
in the two dimensional uv space.
FIG. 4 illustrates how a segmented trimming curve function can cross
several spans of uv space to define a mapped trimming curve in a
corresponding number of patches in XYZ space.
FIG. 5 illustrates the segmented trimming curve of FIG. 4 in greater
detail.
FIG. 6 shows how the spans in uv space are divided into subspans to produce
surface approximating polygons for the surface in XYZ space, and also
indicates that the trimming curve in uv space crosses the subspans while
the mapped trimming curve trims the polygons on the surface.
FIG. 7 is an enlarged view of a portion of FIG. 6, illustrating the
presence of extra vertices along patch boundaries and along mapped
trimming curves for better patch-to-patch transitions, and the presence of
points along the mapped trimming curve defining points of intersection
with the polygon edges as well as approximating points within the interior
regions of polygons crossed by the mapped trimming curve.
FIG. 8 is an expansion of a portion of FIG. 7 showing how the shapes of
polygons are changed by being crossed by a mapped trimming curve.
FIGS. 9A-C comprise a simplified section of pseudocode describing the
processing steps used to produce polygons crossed by mapped trimming
curves and whose shapes have been adjusted accordingly, and include an
illustration of the structure of a polygon vertex table whose instances
are linked together into lists describing polygons.
FIG. 10 depicts the order within a span in which subspans are taken to
generate the approximating polygons for the surface in XYZ space.
FIG. 11 illustrates several types of trimming curves defined upon a span,
and indicates the presence of a guard region around the span to assist in
avoiding arithmetic rounding errors.
FIGS. 12A-B depict how a clipping mechanism operates upon approximating
straight line segments of trimming curves that cross subspans to produce
points of intersection between the straight line segments of the trimming
curve and the boundaries of the subspan.
FIGS. 13A-B describe certain special cases when trimming curves exhibit
points in uv space that are very close to the boundaries of the subspan of
interest.
FIG. 14 illustrates a useful example of a subsapn in uv space crossed by
certain particular trimming curves, and serves as the basis of an
explanation of how the linked boundary list of vertex tables and its
linked trimming curve sublists are traversed to produce polygons that are
present ON the surface.
FIG. 15 is a simplified schematic representation of a linked boundary list
and trimming curve sublists for the vertex tables corresponding to the
example of FIG. 14.
FIGS. 16A-C comprise a simplified flowchart for processing the linked list
of vertex tables in accordance with step 12 of FIG. 9C.
FIG. 17 is a simplified section of pseudocode pertaining to the same
subject matter as FIGS. 16A-C, but with more detail concerning the
structure of the vertex tables shown in FIG. 9B and FIG. 15.
FIG. 18 is a diagram of a trimming curve in uv space illustrating a
refinement in the selection of points in uv space representing the
trimming curve in the operations of clipping and trimming.
FIG. 19 is a simplified hardware block diagram of the component instruments
used in an embodiment incorporating the preferred method of the invention.
FIGS. 20A-C comprise a simplified hardware block diagram of the graphics
accelerator of FIG. 19.
DESCRIPTION OF A PREFERRED METHOD
We shall begin by considering one way that a three dimensional surface may
be represented within a graphics system. Suppose, for example, that a
saddle-shaped surface 1 such as the one depicted in FIG. 1 were to be
represented. This would be accomplished by dividing the entire surface 1
into smaller portions (commonly called patches), of which the patch 2 is
illustrative. To adequately render a surface as complicated as the saddle
shape 1 a great many patches would be required. For the sake of simplicity
we begin by showing only one patch 2; it will be understood that the
graphics system would include some means to divide the surface into
appropriate patches. Also, the various other curved lines in FIG. 1 are
not there to suggest other patches (although they might), but are instead
offered as an aid in appreciating the shape of the surface 1. Furthermore,
it will be understood that, although the surface 1 resembles a hyperbolic
paraboloid, the method to be described is particularly applicable to
irregular ("free-form") surfaces, especially those rendered from
parametric B-spline descriptions.
Associated with a patch is a portion 5 of a parameter space 3. The portion
is called a span. To describe a three dimensional surface in XYZ space a
two dimensional paramenter space is employed. In the present example the
two paramenters are u and v, and each is allowed to vary between
associated maximum and minimum values. As shown in the figure, a set of
parametric patch generation equations 4 map values in the parameter space
3 into XYZ space to produce the (X,Y,Z) triples that lie on the patch 2.
A modern high performance graphics system will store a complete description
of the object, independent of any particular view that may be desired.
Often this description takes the form of a data base, particularly when
subportions of the object are described separately and then deployed by
reference, perhaps a multiplicity of times Rather than store in the
database an exhaustive collection of points on the surface it is common to
instead employ a more compact type of description, such as approximating
functions that yield values to a desired degree of resolution. When a
particular view is wanted it is found by computing translations and or
rotations for points first found by evaluation of the approximating
functions in the database. B-splines are a technique for achieving such a
compact representation through parametric functions.
Even an introductory explanation of B-splines is beyond what can be
included here, and the reader is referred to the various reference works
on the subject (e.g.: Fundamentals of Interactive Computer Graphics by J.
D. Foley and A. Van Dam, Addison-Wesley, 1984; and an article entitled
Rational B-Splines for Curve and Surface Representation, IEEE Computer
Graphics and Applications, vol. 3 no. 6, Sept. 1983). Fortunately, it is
not necessary here to understand in depth what B-splines are and how they
work. Various software packages exist to produce B-spline descriptions of
desired solid objects and surfaces. The point to be made here is that,
while the method of the invention lends itself well to use with B-spline
descriptions of solid objects and surfaces, the use of B-splines is in no
way required. However, since the preferred method has been used in a
graphics system that does employ B-splines, it is most convenient to
describe the method in that setting. That graphics system is the
Hewlett-Packard 9000 Model 320SRX, which includes, in particular, an HP
Model 98720A Graphics Accelerator.
Specifically, FIG. 1 illustrates that each point 6 on a surface of interest
1 can be represented by a corresponding point 7 in some portion 5 of a
parameter space 3. The user of the graphics system interacts with that
system in defined ways set out in an operating manual for the system. By
using appropriate commands a desired surface may be constructed. In
general, the surface will be composed of a multiplicity of patches. For
each patch upon a surface in XYZ space, the internal activities of the
graphics system produce three (or perhaps four) patch generation functions
of u and v. The variables u and v belong to the parameter space 3. The x
coordinate of the point 6 is found by evaluating a (polynomial) function
F.sub.x (u,v). Corresponding functions F.sub.y and F.sub.z produce the y
and z coordinates of the point 6. A more general case (rational B-splines)
for three coordinates uses four functions:
______________________________________
x = F.sub.x (u,v)/H(u,v)
y = F.sub.y (u,v)/H(u,v)
z = F.sub.z (u,v)/H(u,v)
______________________________________
In this case each of the functions F.sub.x, F.sub.y and F.sub.z has been
rationalized through division by the function H. The method to be
described is compatible with either rational or nonrational nonuniform
B-spline representations.
Conceptually, one could compute all the pixel values for the surface by
evaluating the B-spline patch generation functions for a sufficiently
dense cartesian product of the variables u and v; i.e., by evaluating a
sufficiently dense collection of points in the parameter space 3. In
practice, however, such an approach requires an inordinate amount of
execution time, and is generally avoided in favor of one that requires
only quicker and more easily performed computations. The polylgon method
to be described in connection with FIGS. 6-8 is such a favored approach.
According to this approach the set of points evaluated in the parameter
space for a given patch are selected to be just dense enough to yield
polygons vertices for polygons that, when interpolated by shading, produce
an acceptably smooth surface. Since each polygon contains a multitude of
pixels whose values are relatively easily found by linear interpolation
done in hardware, a considerable reduction in image preparation time is
achieved.
It is unlikely that one set of functions 4 entirely describes a complete
surface of interest. Instead, collections of B-spline patch generation
functions are found that provide a good approximations of the desired
surface over small regions. This piecewise approximation divides the
parameter space into regions, called spans. The piecewise approximation is
what actually divides the surface into the corresponding patches. To
render a patch, its corresponding B-spline functions are evaluated over
the range of the associated span. Acccording to the desired resolution for
the displayed object (i.e., the polygon size), suitable step sizes are
selected for increments to u and v. The parameter u is allowed to range in
equal steps from u.sub.min to u.sub.max, while the parameter v ranges in
equal steps (not necessarily the same as those for u) from v.sub.min to
v.sub.max. This evaluation of the span produces "raw" polygon vertices
that are generally subjected to a fair amount of further processing prior
to being displayed.
Thus we see that the surface to be displayed is described as a collection
of patches, each of which has an associated span. Associated with each
span is a particular collection of B-spline patch generation functions.
Recall that it was said above that by using appropriate commands the user
can construct a desired surface. Suppose, for example, that a flat plate
having a hole in it were the desired object. With a typical solid modeling
package a user would select from a menu a suitable primitive shape, such
as a rectangular solid, and specify its dimensions. He would then specify
the location of the center of the hole, and "subtract" from the plate a
cylinder of the desired diameter. It is a practical matter to produce a
B-spline description of a rectangular plate. It is also a practical matter
to obtain a B-spline description of the cylinder to be removed by
"drilling" the hole. However, it is not a practical matter to consider the
plate with the hole already in it as a primitive shape having its own
particular B-spline description.
The method of the invention affords a solution to the problem of complex
surfaces that do not have practical B-spline descriptions. Just as the
hole in the plate has an edge in XYZ space, there are corresponding points
in uv space which, when evaluated, will exactly describe or closely
approximate the edge of the material to be removed to produce the hole.
These points lie along a curve in uv space, called a trimming curve. The
trimming curve can be represented by one or more functions. These
functions can be found by the solid modeling package. Thereafter, the
rendering of a patch having a "subtracted" portion can be accomplished by
a qualified evaluation of the patch generation functions for the
associated span. The qualification takes the form of determining, during
the evaluation of the patch generation functions, whether the (u,v) pair
at hand lies on, inside or outside of the timming curve. The qualification
produces a decision about whether or not to display the associated (X,Y,Z)
triple. If that triple is to be displayed, things proceed as previously
described. However, if the evaluation of that (u,v) pair would produce a
polygon vertex lying within the region to be subtracted, then the triple
cannot be displayed and the existing polygon structure must be modified.
FIG. 2 illustrates the use of a trimming curve 8 to describe the boundary
in XYZ space of a region 9 to be subtracted from patch 2. The trimming
curve 8 is defined in a span 5 of the parameter space 3. In the preferred
method the trimming curve 8 can itself be defined by B-splines. A pair of
parametric equations 9 of a parameter t can define a two dimensional
trimming curve in uv space. After the fashion of the patch generation
functions, trimming curve functions 9 can be either rational or
nonrational non uniform B-splines.
Just as a surface is composed of patches and their associated collections
of different patch generation functions, a trimming curve must generally
be piecewise assembled from subportions called segments. Each segment has
its own particular trimming curve functions 9.
This state of affairs is depicted in FIG. 3 for the trimming curve 8 of
FIG. 2. That trimming curve has been broken into a number of segments
S.sub.1 through S.sub.6. Note that each segment has its own functions that
are defined over corresponding spans of t space 10.
FIG. 4 describes a generalization of the application of trimming curves.
What is shown is similar to the situation depicted in FIGS. 2 and 3, but
with the difference that the trimming curve 11 now traverses several spans
12-15 in uv space. This situation arises because, as luck would have it,
the portion 9 to be subtracted from the surface 1 occupies the four
corresponding patches 16-19. The segment boundaries of the trimming curve
11 are shown on that curve in FIG. 4. Note that, in general, the
boundaries between the segments S.sub.1 through S.sub.9 may fall anywhere
along the trimming curve 11. In particular, they need not have any special
relationship to the boundaries between the spans 12-15.
FIG. 5 depicts the piecewise representation of the segmented trimming curve
11 of FIG. 4. Note the use of different parametric equations for each
segment, and that each set of those equations is defined over it own
associated span in t space 20.
During the discussion of FIG. 1 and the patch generation functions the
notion of polygons was briefly introduced. Beginning now with FIG. 6 we
return to this topic, and examine in more detail the effects of trimming
upon the technique of rendering a surface with polygons.
FIG. 6 shows four spans 12-15 that map, according to the heavy arrows, into
the four patches 16-19. Each of the spans is traversed by a trimming curve
11, whose purpose is to define the trimmed (or "subtracted") region 9 in
the resulting surface. At present our interest in FIG. 6 is in the
generation of (untrimmed) polygons; the effects of trimming curve 11 upon
those polygons will be considered beginning with the Figures and text that
follow FIG. 6.
The process of generating the patches is carried out one patch at a time.
Accordingly, spans are evaluated one at a time; each span produces one
associated patch. The evaluation of a span involves the determination of
step sizes for u and v. These step sizes are not necessarily the same for
u and v, and each is again determined upon beginning the evaluation of the
next span. That is, the step sizes delta u.sub.i and delta v.sub.i for
span 13 need not be equal to each other, nor need they bear any
relationship to the step sizes delta u.sub.j and delta v.sub.j for span
12. In particular, there is no requirement that delta u.sub.i equal delta
u.sub.m or equal delta u.sub.n, even though for simplicity they appear to
be equal in the figure. A similar statement applies to the delta v's.
The user of the graphics system will have at least indirect control over
the step sizes. In some systems it may be possible for the user to specify
them directly, although it is more likely that the specification is
arrived at indirectly. For example, the user may instruct the graphics
system to choose step sizes such that the resulting polygon edges have
approximately a particular number of pixels. Bear in mind that, in
general, the step sizes can be redetermined afresh for each span.
The selection of step sizes for a span determines a collection of (u,v)
pairs within that span. This is represented by the dotted lines withing
the spans 12-15. The intersections of the dotted lines with themselves,
and of the dotted lines with the solid lines representing the boundaries
of the spans, are the points at which the patch generation functions are
evaluated. For example, the evaluations of the patch generation functions
at points 21-23 produces polygon vertices 24-26 (These points are simply
arbitrary vertices in different polygons).
There are two further things to note before leaving FIG. 6. First, the
adjoining edges of the polygons in the patches 16-19 are straight line
segments. An attempt has been made in the figure to show this. In
contrast, the patch boundaries and the edge of the trimmed region 9 appear
much smoother. They too are rendered with straight line segments, but with
ones that are significantly shorter. That is, there are more points in uv
space evaluated to produce those lines in the patches. Essentially, there
is a mechansim for slipping extra points into the span evaluation process.
This notion of differential density will be further discussed among the
topics that follow. Second, the process described above of evaluating
patch generation functions at points in uv space evaluates points in in
all portions of the span, including those that will eventually be trimmed
away. Trimming is a fairly complicated process, requiring the analysis of
several possible situations. For example, a given vertex may belong to a
polygon that is totally unaffected by trimming, one that is to be trimmed
away in its entirety, or, to one that is crossed by the trimming curve (as
it is mapped into XYZ space). In this latter case part of the polygon
remains and part of it does not. This requires changing the shape of the
polygon to match the ("mapped") trimming curve. That, in turn, will
require the finding of new vertices for that polygon; ones that were not
produced by the evaluation of the span at the steps in u and v as shown in
FIG. 6.
Refer now to FIG. 7. What is shown there is an expansion of a portion of
FIG. 6. In particular, portions of patches 16 and 17 are depicted, along
with a portion of the mapped trimming curve 27. By "mapped" trimming
curve, we mean the trimming curve 11 as mapped into the patches by the
patch generation functions.
Two kinds of polygon vertices along patch boundaries are shown in FIG. 7.
The open (or hollow) circles correspond to the mapping into the patches
of: (a) the points of intersection of the dotted lines of FIG. 6 with the
span boundaries, and (b) the points of intersection of the dotted lines
with themselves. The closed (or solid) circles correspond to "extra"
vertices that are added by evaluating additional (u,v) pairs along the
span boundary. These extra points divide each step of delta u into equal
subportions; the steps of delta v are similarly divided. It is common for
the user to have some degree of control over the process of adding these
extra vertices.
FIG. 7 also shows polygon vertices along the mapped trimming curve 27. It
is clear from an examination of the figure that a good many extra vertices
have been added to the polygons as part of the trimming process. We shall
have much to say about this, and turn now to FIG. 8, which is a further
expansion of that portion of the mapped trimming curve 27 pertaining to
patch 17.
There are basically two topics that are of interest in connection with FIG.
8. The first is where the solid black squares come from. They are points
along the mapped trimming curve 27 that are taken to be polygon vertices
for polygons that are crossed by the mapped trimming curve 27. It will be
recalled (see FIG. 5) that the trimming curve 11 is composed of segments.
For the particular trimming curve 11 in FIG. 5 that serves as the basis of
our example here in FIG. 8, segments S.sub.6 through S.sub.8 are those
that trim patch 17.
Segments S.sub.6 through S.sub.8 (as well as all the other segments of that
or any other trimming curve) are evaluated by finding, for each segment, a
delta t that ideally produces steps in u and v that are each roughly equal
to the distance, in uv space, between the points along the span boundary
that correspond to an open circle and its nearest solid black circle
neighbor on patch boundaries of FIG. 7. This business of selecting the
delta t's is influenced by the user's choices made in connection with
extra vertices for patch boundaries. In reality (and in contrast with the
ideal case), the evaluation of the trimming curve 11, as described above,
produces many (u,v) pairs that are spaced too close together to be useful.
A further refinement is to examine the pairs produced by the evaluation of
the parametric functions (for the example at hand these are F.sub.u6 &
F.sub.v6, F.sub.u7 & F.sub.v7, F.sub.u8 & F.sub.v8) and suppress pairs
that are insufficiently distant from their predecessors. The solid black
squares of FIG. 8 (and those of FIG. 7, too) result from evaluating the
patch generation functions at these refined (u,v) pairs.
The second thing that is of interest in FIG. 8 is the open squares. These
represent the intersection of the mapped trimming curve 27 and the polygon
edges. Rather than find the intersections in XYZ space, the corresponding
point of intersection is found in uv space and then mapped into XYZ space.
Specifically, what is found is the intersection of two straight line
segments in uv space. One of the straight line segments is between two
consecutive refined (u,v) pairs along the trimming curve 11. The other
straight line segment would be a portion (e.g., 28 or 29 in FIG. 6) of the
dotted lines or span boundaries of FIG. 6.
Before leaving FIG. 8, notice also the dotted lines that represent polygon
portions and entire polygons that are determined to be invisible by the
trimming process, and so are not displayed.
We turn now to FIG. 9. That figure is a simplified pseudocode description
of activity performed by a transform engine portion of a high performance
graphics system hardware apparatus. That hardware apparatus is the subject
of description that appears in a later portion of this Specification and
its Figures. The activity mentioned above is primarily the trimming of
polygons as illustrated in FIG. 8. FIG. 9 may be understood as a condensed
road map for accomplishing the type of trimming described in connection
with FIG. 8.
In a preferred method the graphics system is capable of displaying several
B-spline surfaces, each of which may be variously trimmed. Each surface
would generally be composed of a plurality of patches. The trimming
activities occur at the level of polygon handling within each patch.
Accordingly, steps 1 and 2 (in conjunction with steps 15 and 16) of FIG. 9
apply the process to be described in connection with steps 3-14 to each of
the patches in all of the surfaces. Step 2 is accomplished in software
executed by the computer associated with the graphics system. Among other
things, step 2 divides the surface into patches, selects a patch to be
rendered, computes u.sub.min, u.sub.max, v.sub.min, and v.sub.max for the
associated span of uv space, and decides which segments of which trimming
curves will be needed for trimming the patch. Steps 3-14 generate trimmed
polygons vertices that can be displayed by a polygon rendering mechanism
in the hardware of the graphics system.
We now consider the activity within the range of the FOR loop of steps 3
through 14. That activity includes the primary generation of the various
polygons (as indicated by steps 3 and 14), and their subsequent (and
immediate) trimming (as indicated by steps 4 through 13).
The general order of polygon generation within a patch is illustrated in
the example span 30 of FIG. 10. That span is partitioned, in this example,
into sixteen subspans; one for each untrimmed polygon to be generated. The
size of each subspan is determined in accordance with the user's
instructions pertaining to the desired visual smoothness of the surface.
In a preferred method the polygons are generated by a technique called
forward differencing, which does not require the explicit calculation of
the u and v values for the boundaries of each of the subspans. Forward
differencing is preferred because it is faster than evaluating the patch
generation functions at each of the subspan corners. For a description of
forward differencing see Foley and Van Dam, pages 535-536.
The trimming activities that are to follow require the use of clip limits
that correspond to the subspan for the polygon being generated. As usual,
the term "clip limits" refers to a window of interest. Objects within the
window are retained, while those that fall outside are discarded. The clip
limits that will be of interest to the trimming described herein are the
subspan boundaries in uv space that are associated with the generated
polygons.
Unfortunately, as noted above the operation of computing polygon vertices
in XYZ space through forward differencing does not explicitly provide the
u and v values that are the subspan boundaries. If the clip limits noted
above are to be used, then they must be found separately. Step 4 computes
the clip limits (in uv space) for the polygon currently being generated
and trimmed. FIG. 9A includes a subspan 35 having clip limits u.sub.left,
u.sub.right, v.sub.top and v.sub.bottom. Subspan 35 could, for exa | | |
