 |
Description  |
|
|
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to methods and apparatus for clipping functions
representing models of objects which are computer generated.
2. Background Art
Computer generated images are created from models of objects. It is
desirable that the object depicted in a computer generated image resemble
the real object to the maximum extent possible. As one aspect of modeling
an object, it is desirable to accurately represent the shading of the
object. Changes in color and intensity of light reflected by an object
across its surface, or its shading, can be very complex. Variations in
shading may result from a wide variety of factors such as surface texture,
position, orientation, and the type, location and direction of the source
of light. To accurately represent shading of a modeled object, high order
shading functions may be used.
Another aspect of the modeling process is selecting that portion of the
object which is being modeled that will lie within a field of vision.
Commonly, an object to be modeled is represented as a number of smaller
polygons. Once the object is modeled with the polygons, the polygons are
"clipped" to eliminate that portion of the data which represents the
modeled object which lies outside of a selected field of view.
The object may be modeled with one or more first degree functions. The
polygon(s) used to model the object are planar in their three-dimensional
geometric coordinates. The shading function may also be a first degree
function representing a set of color or shading coordinates. Each
geometric point on the polygon may be represented by coordinates (x,y,z)
and the shading at each particular point represented by a color set (red
(r), green (g), blue (b)), these coordinates and color sets varying
linearly over the polygon.
When the geometric and shading functions are first degree, and are thus
linear, as described above, the clipping process requires only linear
interpolation of the data. For example, the geometric coordinates for each
point where a clipping line or plane intersects the polygon may be
determined from linear interpolation from other known points. Likewise,
the shading values at the clipped points can be determined by
interpolation the shading values linearly from those of known points.
This process of linear clipping is described in U.S. Pat. No. 3,816,726 to
Sutherland et al., and in Reentrant Polygon Clipping by Sutherland and
Hodges (Vol. 17, Number 1, Communications of the ACM, January 1974). These
references describe a process whereby a linear interpolant " is used to
calculate the intersection point of a clipping line or plane with an edge
of a polygon between two vertices of the polygon. The interpolant " is
derived from ratios of two similar triangles and the distances between
points on the triangles to the clipping line. As provided in these
references and referring to FIG. 1, the linear interpolant
"=SI/SP=SR.sub.1 /.vertline.SR.sub.1 +PR.sub.2.vertline. As described
therein, the interpolant " can be applied to other linear functions
associated with the polygon, such as color and intensity blending.
A problem is that many functions which are used to model objects are not
first order. In order to improve the accuracy of the representation of the
object's shading, it is now common to utilize a second or higher degree
polynomial shading function. For example, a shading function for an object
being modeled may be defined by a quadratic parametric surface. It is not
possible to use the simple linear clipping algorithm directly to such a
function in order to obtain the coordinates or parameters associated with
clipping points (i.e. it is not possible to apply a linear interpolant
such as that described above to the second or higher degree shading
function). Instead, quadratic or other second degree or higher
interpolation is necessary. Such a process is computationally demanding,
however, and negates some of the gains realized by using a high order
surface to obtain better shading results.
SUMMARY OF THE INVENTION
The invention is a method and apparatus for clipping a function, and in one
or more embodiments, defining a new reparameterized clipped function.
An embodiment of the invention comprises a method of effectuating clipping
of a second or higher order function in "linear" fashion by using
barycentric coordinates.
In accordance an embodiment of the invention, the method comprises the
steps of determining a second or higher order function to be clipped,
determining barycentric coordinates for at least one clipping point
associated with a first order function associated with the second or
higher order function and generating at least one clipping point
associated with the second or higher order function using the barycentric
coordinates.
In one or more embodiments, the barycentric coordinates for at least one
clipping point associated with the first order function are determined by
linear interpolation. The barycentric coordinates are then substituted
into the higher order function to define the clipped point(s) of the
higher order function.
In one or more embodiments, the higher order function comprises a quadratic
Bezier function defining a quadratic Bezier triangle. The first order
function comprises a linear vector-valued function representing a planar
triangle associated with the quadratic Bezier triangle.
In one or more embodiments of the invention, the method includes the steps
of using the barycentric coordinates to determine a reparameterized
clipped function.
In an embodiment where the higher order function comprises a quadratic
Bezier function, this step comprises using a blossoming algorithm to
generate six reparameterized points which define a new clipped quadratic
Bezier function.
In accordance with one or more embodiments, the higher order function is a
shading function for an object being modeled.
In one or more embodiments, computer hardware and/or software is arranged
to one or more aspects of the method of the invention.
Further objects, features and advantages of the invention will become
apparent from the detailed description of the drawings which follows, when
considered with the attached figures.
BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 illustrates a prior art method for determining a linear interpolant
for use in linearly interpolating a first order, linear function;
FIG. 2 is a flow diagram illustrating a method of clipping in accordance
with an embodiment of the invention;
FIG. 3 illustrates a quadratic Bezier triangle representing a shading
function;
FIG. 4 illustrates a first order planar Bezier triangle associated with the
function illustrated in FIG. 3;
FIG. 5 illustrates the Bezier triangle illustrated in FIG. 4 clipped to a
viewport;
FIG. 6 illustrates the quadratic Bezier triangle associated with the first
order Bezier triangle clipped to the viewport as in FIG. 5;
FIG. 7 illustrates a new quadratic shading function after clipping;
FIG. 8 diagrammatically illustrates one embodiment of a computer system
capable of providing a suitable execution environment for an embodiment of
the invention; and
FIG. 9 diagrammatically illustrates one embodiment of a clipping and
reparameterizing system for use with the computer system illustrated in
FIG. 2.
DETAILED DESCRIPTION OF THE INVENTION
The invention is a method and apparatus for providing a clipping function.
In the following description, numerous specific details are set forth in
order to provide a more thorough description of the present invention. It
will be apparent, however, to one skilled in the art, that the present
invention may be practiced without these specific details. In other
instances, well-known features have not been described in detail so as not
to obscure the invention.
Portions of the disclosure of this patent document may contain material
that is subject to copyright protection. The copyright owner has no
objection to the facsimile reproduction by anyone of the patent document
or the patent disclosure as it appears in the Patent and Trademark Office
file or records, but otherwise reserves all copyright rights whatsoever.
Sun Microsystems and Java are trademarks or registered trademarks of Sun
Microsystems, Inc. in the United States and other countries. All SPARC
trademarks are used under license and are trademarks or registered
trademarks of SPARC International in the United States and other
countries.
Method of Providing a Clipping Function
An embodiment of the invention comprises a method for clipping a function.
An embodiment of the invention also comprises a method for providing a
reparameterized clipped function.
A first aspect of the invention will be described with reference to FIG. 2.
In general, the first aspect of the invention is a method for clipping a
second or higher degree function in linear fashion.
A first step S1 of the method comprises determining a second or higher
degree or order function. As used herein, the terms "first order," "first
degree," "linear" and similar terms are generally intended to mean a
function in which no variable thereof is raised to higher than a first
power. An example of a first order function is f(x)=2x+5. As used herein,
the terms "second or higher order," "second degree" and similar terms are
generally intended to mean a function in which at least on variable
thereof is raised to higher than a first power. Examples of second or
higher order functions are f(x)=2x.sup.2 +9 and f(x,y)=x.sup.3 +4y.sup.2.
Second or higher order functions are well known and may comprise cubic,
quadratic or other high order polynomial functions. The function may
represent one or more features of the object which is being modeled. For
example, the function may represent a shading function of an object being
modeled. The shading function may comprise a specular highlight function,
a simple color function or the like.
The function may comprise a quadratic Bezier shading function as
illustrated in FIG. 3. Quadratic shading functions are well known. As
illustrated in FIG. 3, such a function defines a quadratic Bezier surface.
This surface is defined by six control points P.sub.200, P.sub.020,
P.sub.002, P.sub.110, P.sub.011 and P.sub.101.
Second, in a step S2 of the method, barycentric coordinates associated with
the function are determined. In one embodiment, the barycentric
coordinates are determined from a planar polygon and associated with the
higher order surface. In one or more embodiments, the determined
barycentric coordinates describe the intersection coordinates of a
clipping line or plane with one or more edges of the first degree polygon.
In the case of the function illustrated in FIG. 3, there is associated with
the quadratic Bezier surface (defined by the quadratic Bezier function) a
planar triangular polygon. This planar triangle can be represented by a
first degree or linear function and has vertices P.sub.0, P.sub.1 and
P.sub.2 corresponding to the quadratic Bezier surface vertices P.sub.200,
P.sub.020 and P.sub.002, respectively.
In accordance with one embodiment of the method, in Step S2, the
barycentric coordinates which are obtained correspond to each "clipping
point" representing the mathematical intersection of the first degree
function with a clipping line or plane. This clipping is visually
illustrated in FIG. 5. In the example given, the planar polygon (and
ultimately the higher order function with which it is associated, as
described below) is clipped by a vertical clipping line C. In one or more
embodiments, the clipping line C represents the left-hand edge of a
viewport V where that portion of the polygon to the right of the clipping
line C is to be retained as visible and that portion of the polygon to the
left of the clipping line C to be eliminated.
In accordance with this step, barycentric coordinates are determined for
the points of intersection of the clipping line C and the polygon edges
P.sub.2 P.sub.0 and P.sub.1 P.sub.2. As illustrated, these points are
T.sub.0 and T.sub.1. Importantly, the coordinates which are obtained for
each of these clipping points are their barycentric coordinates.
The relationship between any point on the planar triangle and the
barycentric coordinates is a linear (i.e. first order) vector-valued
function provided as follows:
p(b.sub.0,b.sub.1,b.sub.2)=P.sub.0 b.sub.0 +P.sub.1 b.sub.1 +P.sub.2
b.sub.2 (1)
Using this function and the known barycentric coordinates for the points
P.sub.0, P.sub.1 and P.sub.2, the barycentric coordinates for the
intersection points T.sub.0 and T.sub.1 can be obtained. In one or more
embodiments, in the method the barycentric coordinates (1,0,0), (0,1,0)
and (0,0,1) are associated with the vertices P.sub.0, P.sub.1 and P.sub.2,
and then the barycentric coordinates for the points of intersection are
determined. Most importantly, because the relationship of the barycentric
coordinates to any point on the polygon is linear, linear interpolation
may be used to determine the barycentric coordinates for any point on the
polygon.
Next, in a step S3, the barycentric coordinates determined in step S2 are
used to interpolate points on the quadratic or other second degree or
higher function. These coordinates are obtained using the following
equation when the function is a quadratic Bezier function (with reference
to the points illustrated in FIG. 3):
p(b.sub.0,b.sub.1,b.sub.2)=P.sub.200 b.sub.0.sup.2 +P.sub.020
b.sub.1.sup.2.sub.- +P.sub.002 b.sub.2.sup.2 +2P.sub.110 b.sub.0 b.sub.1
+2P.sub.011 b.sub.1 b.sub.2 +2P.sub.101 b.sub.2 b.sub.0 (2)
This equation relates each point on the planar polygon, by its barycentric
coordinates, to a particular point on the quadratic surface.
FIG. 6 graphically illustrates the quadratic Bezier surface associated with
the planar triangle in the clipping arrangement. Using equation (2) the
points T.sub.020 and T.sub.200 associated with the higher order
function/surface are determined using the barycentric coordinates for
points T.sub.1 and T.sub.0, respectively. The points T.sub.020 and
T.sub.200 are points on the clipped quadratic function.
Once determined, the points T.sub.020 and T.sub.200, along with point
P.sub.2 (which has been relabeled point T.sub.002 in FIG. 7) comprise the
three vertices of the newly clipped quadratic Bezier function.
In accordance with the above-described aspect of the invention, there is
provided a method for linearly interpolating a second or higher degree
function. The method takes advantage of the properties of barycentric
coordinates to substantially reduce the computational complexity
associated with clipping high order functions.
The method of steps S1-S3 yields only new clipping vertice points for the
high order function. When the function which is being clipped is a shading
or similar function, it is desirable to determine more than just the
clipping points for the function. It is desirable to determine the new
clipped function for use in the creation of data and raster conversion for
generating an image output, such as in the case of a computer.
For example, in order to compute shading, such as specular highlights
associated with portion of the object being modeled with the clipped
surface, it is necessary to create a completely new clipped highlight
function. In this manner, the shading at each point across the newly
clipped surface can be determined.
Thus, in accordance with another aspect of the invention, there is provided
a method for generating a reparameterized clipped function using the
barycentric coordinates determined in step S2.
Referring to FIG. 2 again, and in accordance with another aspect of the
invention, in a step S4 a reparameterized clipped function is generated.
In accordance with this step, the barycentric coordinates for the vertices
of the function (including the barycentric coordinates for the one or more
clipped points determined in step S2) are utilized to determine the
reparameterized and clipped function.
In the embodiment where the shading function is a quadratic Bezier function
six control points are necessary to define the surface. Referring to FIG.
7, these six points comprise the three vertices T.sub.200, T.sub.020 and
T.sub.002, Plus three additional points associated with the midpoints of
each of the curves referred to above, these points being illustrated as
T.sub.101, T.sub.110 and T.sub.011.
In accordance with a step S4 of the method, barycentric coordinates are
utilized to obtain these six control points and for defining a
reparameterized and clipped function. In accordance with one embodiment of
the method, a blossoming algorithm is utilized to determine
reparameterized values for these six points. As a first aspect of this
step, the equation representing the function being clipped is expressed as
a recursive de Casteljau formulation. In the case of the function listed
above, this formulation is as follows (the formulation is equation (2)
above, rewritten):
##EQU1##
Next, the parameters (d.sub.0,d.sub.1,d.sub.2) are substituted for the
barycentric coordinates outside of the parenthesis, and "T" (the desired
control point) is then represented as:
##EQU2##
A particular point T is then obtained by substituting appropriate pairs of
barycentric coordinates in this equation to obtain reparameterized control
points T.sub.200, T.sub.020, T.sub.002, T.sub.101, T.sub.110 and
T.sub.011. The barycentric coordinates which are substituted comprise the
barycentric coordinates for the points of the clipped base polygon, i.e.
T.sub.0, T.sub.1 and P.sub.2 in FIG. 6.
If the barycentric coordinates for the point To comprise
(b.sub.0,b.sub.1,b.sub.2).sub.0, the barycentric coordinates for the point
T.sub.1 comprise (b.sub.0,b.sub.1,b.sub.2).sub.1 and the barycentric
coordinates for P.sub.2 comprise (b.sub.0,b.sub.1,b.sub.2).sub.2, the
following table illustrates the combinations of barycentric coordinate
substitutions in the above-equation (4) to obtain each of the six control
points for the surface.
Control Point To Be Obtained (b.sub.0,b.sub.1,b.sub.2)
(d.sub.0,d.sub.1,d.sub.2)
T.sub.200 (b.sub.0,b.sub.1,b.sub.2).sub.0
(b.sub.0,b.sub.1,b.sub.2).sub.0
T.sub.020 (b.sub.0,b.sub.1,b.sub.2).sub.1
(b.sub.0,b.sub.1,b.sub.2).sub.1
T.sub.002 (b.sub.0,b.sub.1,b.sub.2).sub.2
(b.sub.0,b.sub.1,b.sub.2).sub.2
T.sub.110 (b.sub.0,b.sub.1,b.sub.2).sub.0
(b.sub.0,b.sub.1,b.sub.2).sub.1
T.sub.011 (b.sub.0,b.sub.1,b.sub.2).sub.1
(b.sub.0,b.sub.1,b.sub.2).sub.2
T.sub.101 (b.sub.0,b.sub.1,b.sub.2).sub.2
(b.sub.0,b.sub.1,b.sub.2).sub.0
In this method, all of the control points defining the new quadratic Bezier
function, being both clipped and reparameterized, are determined.
It should be appreciated that equations (1)-(4) apply to triangles only
(i.e. 3 points) any polygon associated with a function which is being used
to model an object must be decomposed into a set of triangles prior to
applying the equations of the method.
Embodiment of a Computer Execution Environment (Hardware)
An embodiment of the invention can be implemented as computer software in
the form of computer readable code executed on a computer 100 or other
device, such as that illustrated in FIG. 8, or in the form of bytecode
class files executable within a runtime environment (such as, e.g., a
Java.TM. runtime environment) running on such a computer or other device,
or in the form of bytecodes running on a processor (or devices enabled to
process bytecodes) existing in a distributed environment (e.g., one or
more processors on a network).
The computer 100 illustrated in FIG. 8 includes a keyboard 110 and mouse
111 coupled to a system bus 118. The keyboard and mouse are for
introducing user input to the computer system and communicating that user
input to processor 113. Other suitable input devices may be used in
addition to, or in place of, the mouse 111 and keyboard 110. I/O
(input/output) unit 119 coupled to system bus 118 represents such I/O
elements as a printer, A/V (audio/video) I/O, etc.
Computer 100 includes a video memory 114, main memory 115 and mass storage
112, all coupled to system bus 118 along with keyboard 110, mouse 111 and
processor 113. The mass storage 112 may include both fixed and removable
media, such as magnetic, optical or magnetic optical storage systems or
any other available mass storage technology. Bus 118 may contain, for
example, thirty-two address lines for addressing video memory 114 or main
memory 115. The system bus 118 also includes, for example, a 64-bit data
bus for transferring data between and among the components, such as
processor 113, main memory 115, video memory 114 and mass storage 112.
Alternatively, multiplex data/address lines may be used instead of
separate data and address lines.
In one embodiment of the invention, the processor 113 is a microprocessor
manufactured by Sun Microsystems, Inc., such as the SPARC.TM.
microprocessor, or a microprocessor manufactured by Motorola, such as the
680.times.0 processor, or a microprocessor manufactured by Intel, such as
the 80.times.86, or Pentium processor. However, any other suitable
microprocessor or microcomputer may be utilized. Main memory 115 is
comprised of dynamic random access memory (DRAM). Video memory 114 is a
dual-ported video random access memory. One port of the video memory 114
is coupled to video amplifier 116. The video amplifier 116 is used to
drive the cathode ray tube (CRT) raster monitor or display 117. Video
amplifier 116 is well known in the art and may be implemented by any
suitable apparatus. This circuitry converts pixel data stored in video
memory 114 to a raster signal suitable for use by monitor 117. Monitor 117
is a type of monitor suitable for displaying graphic images.
Computer 100 may also include a communication interface 120 coupled to bus
118. Communication interface 120 provides a two-way data communication
coupling via a network link 121 to a local network 122. For example, if
communication interface 120 is an integrated services digital network
(ISDN) card or a modem, communication interface 120 provides a data
communication connection to the corresponding type of telephone line,
which comprises part of network link 121. If communication interface 120
is a local area network (LAN) card, communication interface 120 provides a
data communication connection via network link 121 to a compatible LAN.
Wireless links are also possible. In any such implementation,
communication interface 120 sends and receives electrical, electromagnetic
or optical signals which carry digital data streams representing various
types of information.
Network link 121 typically provides data communication through one or more
networks to other data devices. For example, network link 121 may provide
a connection through local network 122 to local server computer 123 or to
data equipment operated by an Internet Service Provider (ISP) 124. ISP 124
in turn provides data communication services through the world wide packet
data communication network now commonly referred to as the "Internet" 125.
Local network 122 and Internet 125 both use electrical, electromagnetic or
optical signals which carry digital data streams. The signals through the
various networks and the signals on network link 121 and through
communication interface 120, which carry the digital data to and from
computer 100, are exemplary forms of carrier waves transporting the
information.
Computer 100 can send messages and receive data, including program code,
through the network(s), network link 121, and communication interface 120.
In the Internet example, remote server computer 126 might transmit a
requested code for an application program through Internet 125, ISP 124,
local network 122 and communication interface 120.
The received code may be executed by processor 113 as it is received,
and/or stored in mass storage 112, or other non-volatile storage for later
execution. In this manner, computer 100 may obtain application code in the
form of a carrier wave.
Application code may be embodied in any form of computer program product. A
computer program product comprises a medium configured to store or
transport computer readable code, or in which computer readable code may
be embedded. Some examples of computer program products are CD-ROM disks,
ROM cards, floppy disks, magnetic tapes, computer hard drives, servers on
a network, and carrier waves.
In one or more embodiments, the computer 100 and/or CPU 113 may include a
clipping system 200, such as that illustrated in FIG. 9. Such a system 200
may comprise hardware and/or software associated with the computer 100
and/or CPU 113.
In the arrangement illustrated in FIG. 9, the system 200 includes a
barycentric coordinate generator 202 for generating barycentric
coordinates for a clipped function such as in accordance with steps S1-S3
of the method described above. In addition, the system 202 includes a
function reparameterizer 204 for defining a clipped and reparameterized
function such as in accordance with step S4 of the method described above.
Of course, the foregoing description is that of preferred embodiments of
the invention, and various changes and modifications may be made without
departing from the spirit and scope of the invention, as defined by the
claims.
* * * * *
|
|
 |
|
 |
Description |
|
