 |
Description  |
|
|
FIELD OF THE INVENTION
The present invention relates to computer graphics and more specifically to
a method and apparatus for rendering a bicubic surface on a computer
system.
BACKGROUND OF THE INVENTION
Object models are often stored in computer systems in the form of surfaces.
The process of displaying the object (corresponding to the object model)
generally requires rendering, which usually refers to mapping the object
model onto a two dimensional surface. At least when the surfaces are
curved, the surfaces are generally subdivided or decomposed into triangles
in the process of rendering the images.
A cubic parametric curve is defined by the positions and tangents at the
curve's end points. A Bezier curve, for example, is defined by a geometry
matrix of four points (P1-P4) that are defined by the intersections of the
tangent vectors at the end points of the curve. Changing the locations of
the points changes the shape of the curve.
Cubic curves may be generalized to bicubic surfaces by defining cubic
equations of two parameters, s and t. In other words, bicubic surfaces are
defined as parametric surfaces where the (x,y,z) coordinates in a space
called "world coordinates" (WC) of each point of the surface are functions
of s and t. Varying both parameters from 0 to 1 defines all points on a
surface patch. If one parameter is assigned a constant value in the other
parameters vary from 0 to 1, the result is a cubic curve, defined by a
geometry matrix P comprising 16 control points (FIG. 4).
While the parameters s and t describe a closed unidimensional interval
(typically the interval [0,1]) the points (x,y,z) describe the surface:
x=f(s,t), y=g(s,t), z=h(s,t) s.OR left.[0,1], t.OR left.[0,1], where D
represents an interval between the two coordinates in the parenthesis.
The space determined by s and t, the bidimensional interval [0,1]x[0,1] is
called "parameter coordinates" (PC). Textures described in a space called
"texture coordinates" (TC) that can be two or even three dimensional are
described by sets of points of two ((u,v))or three coordinates ((u,v,q)).
The process of attaching a texture to a surface is called "texture--object
association" and consists of associating u, v and q with the parameters s
and t via some function:
u=a(s,t) v=b(s,t) (and q=c(s,t))
FIGS. 1A and 1B are diagrams illustrating a process for rendering bicubic
surfaces. As shown in FIG. 1A, the principle used for rendering such a
curved surface 10 is to subdivide it into smaller four sided surfaces or
tiles 12 by subdividing the intervals that define the parameters s and t.
The subdivision continues until the surfaces resulting from subdivision
have a curvature, measured in WC space, that is below a predetermined
threshold. The subdivision of the intervals defining s and t produces a
set of numbers {si}i=1,n and {tj}j=1,m that determine a subdivision of the
PC. This subdivision induces a subdivision of the TC, for each pair
(si,tj) we obtain a pair (ui,j,vi,j) (or a triplet (ui,j,vi,j,qi,j) ).
Here ui,j=a(si,tj), vi,j=b(si,tj), qi,j=c(si,tj). For each pair (si,tj) we
also obtain a point (called "vertex") in WC, Vi,j
(f(si,tj),g(si,tj),h(si,tj)).
This process is executed off-line because the subdivision of the surfaces
and the measurement of the resulting curvature are very time consuming. As
shown in FIG. 1B when all resulting four sided surfaces (tiles) 12 is
below a certain curvature threshold, each such resultant four-sided
surface 12 is then divided into two triangles 14 (because they are easily
rendered by dedicated hardware) and each triangle surface gets the normal
to its surface calculated and each triangle vertex also gets its normal
calculated. The normals are used later on for lighting calculations.
As shown in FIG. 2, bicubic surfaces 10A and 10B that share boundaries must
share the same subdivision along the common boundary (i.e., the tile 12
boundaries match). This is due to the fact that the triangles resulting
from subdivision must share the same vertices along the common surface
boundary, otherwise cracks will appear between them.
The conventional process for subdividing a set of bicubic surfaces in
pseudocode is as follows:
Step 1.
For each bicubic surface
Subdivide the s interval
Subdivide the t interval
Until each resultant four sided surface is below a certain
predetermined curvature range
Step 2
For all bicubic surfaces sharing a same parameter (either s or t)
boundary
Choose as the common subdivision the reunion of the
subdivisions in order to prevent cracks showing along the
common boundary
Step 3
For each bicubic surface
For each pair (si,tj)
Calculate (ui,j v,j qi,j Vi,j)
Generate triangles by connecting neighboring vertices
Step 4
For each vertex Vi,j
Calculate the normal Ni,j to that vertex
For each triangle
Calculate the normal to the triangle
The steps 1 through 4 are executed on general purpose computers and may
take up to several hours to execute. The steps of rendering the set of
bicubic surfaces that have been decomposed into triangles are as follows:
Step 5.
Transform the verices Vi,j and the normals Ni,j
Transform the normals to the triangles
Step 6.
For each vertex Vi,j
Calculate lighting
Step 7
For each triangle
Clip against the viewing viewport
Calculate lighting for the vertices produced by clipping
Step 8
Project all the vertices Vi,j into screen coordinates (SC)
Step 9
Render all the triangles produced after clipping and projection
Steps 5 through 9 are typically executed in real time with the assistance
of specialized hardware found in 3D graphics controllers.
The conventional process for rendering bicubic surfaces has several
disadvantages. For example, the process is slow because the subdivision is
so computationally intensive, and is therefore often executed off-line. In
addition, as the subdivision of the tiles into triangles is done off-line,
the partition is fixed, it may not account for the fact that more
triangles are needed when the surface is closer to the viewer versus fewer
triangles being needed when the surface is farther away. The process of
adaptively subdividing a surface as a function of distance is called
"automatic level of detail".
Furthermore, each vertex or triangle plane normal needs to be transformed
when the surface is transformed in response to a change of view of the
surface, a computationally intensive process that may need dedicated
hardware. Also, there is no accounting for the fact that the surfaces are
actually rendered in a space called "screen coordinates" (SC) after a
process called "projection" which distorts such surfaces to the point
where we need to take into consideration the curvature in SC, not in WC.
Because the steps required for surface subdivision are so slow and limited,
a method is needed for rendering a curved surface that minimizes the
number of required computations, such that the images can potentially be
rendered in real-time (as opposed to off-line). The present invention
addresses such a need.
SUMMARY OF THE INVENTION
The present invention provides a method and system for rendering bicubic
surfaces of an object on a computer system. Each bicubic surface is
defined by sixteen control points and bounded by four boundary curves, and
each boundary curve is formed by boundary box of line segments formed
between four of the control points. The method and system of include
transforming only the control points of the surface given a view of the
object, rather than points across the entire bicubic surface. Next, a pair
of orthogonal boundary curves to process is selected. After the boundary
curves have been selected, each of the curves is iteratively subdivided,
wherein two new curves are generated with each subdivision. The
subdivision of each of the curves is terminated when the curves satisfy a
flatness threshold expressed in screen coordinates, whereby the number of
computations required to render the object is minimized.
According to the system and method disclosed herein, the number of
computations required for rendering of an object model are minimized by
requiring that only two orthogonal curves of the surface be subdivided. As
the number of computations are decreased, the entire rendering process can
potentially be performed in real time. According to another aspect of the
present invention, the computations for subdivision are performed by
expressing the criteria of terminating the subdivision in the screen
coordinates (SC). As the curvature is estimated based on how flat it
appears to be in SC (pixels), rather than how curved it is in WC, the
number of computations required may further be minimized. As a result, the
possibility of rendering images in real time is further enhanced. In
addition, allowing the curvature to be measured in SC units also allows
for accommodating the distance to the viewer, thus giving the process an
"automatic level of detail" capability.
BRIEF DESCRIPTION OF THE DRAWINGS
The present invention will be described with reference to the accompanying
drawings, wherein:
FIGS. 1A and 1B show how bicubic surfaces are subdivided into tiles;
FIG. 2 shows how bicubic surfaces sharing a boundary also share the same
subdivision:
FIG. 3 is a block diagram of a computer system illustrating the details of
an embodiment in which the present invention can be implemented.
FIG. 4 is a diagram illustrating the theory of Bezier surfaces;
FIG. 5 depicts a graph illustrating an approach by which a Bezier curve may
be divided into connected segments of Bezier curves;
FIG. 6 is a diagram illustrating the criteria of terminating the
subdivision (decomposition) of a Bezier curve in the present invention;
FIG. 7 shows an example of prior art in terms of determining the flatness
of the surface;
FIG. 8 is diagram illustrating an implementation in accordance with the
present invention;
FIG. 9 is a diagram illustrating the criteria for termination of
decomposition in an embodiment of the present invention; and
FIG. 10 shows the effect of subdividing the parameter space (s,t) on
dividing the texture space (u,v).
FIG. 11 shows the calculation of the normal N to the vertex as the cross
product of the vectors that start in the vertex and connect it with the
neighboring vertices.
DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS
The present invention is directed to a method and apparatus for minimizing
the number of computations required for the subdivision of bicubic
surfaces into triangles. The following description is presented to enable
one of ordinary skill in the art to make and use the invention and is
provided in the context of a patent application and its requirements.
Various modifications to the preferred embodiments and the generic
principles and features described herein will be readily apparent to those
skilled in the art. Thus, the present invention is not intended to be
limited to the embodiments shown but is to be accorded the widest scope
consistent with the principles and features described herein.
According to the present invention, the reduction in computations is
attained by reducing the subdivision to the subdivision on only two
orthogonal curves. In addition, the criteria for sub-division may be
determined in SC. The description is provided with reference to Bezier
surfaces for illustration. Due to such features, the present invention may
enable objects to be subdivided and rendered in real-time. The partition
into triangles may also be adapted to the distance between the surface and
the viewer resulting in an optimal number of triangles. As a result, the
effect of automatic level of detail may be obtained, whereby the number of
resulting triangles is inversely proportional with the distance between
the surface and the viewer. The normals to the resulting tiles are also
generated in real time by using the cross product of the vectors that form
the edges of the tiles. The texture coordinates associated with the
vertices of the resulting triangles are computed in real time by
evaluating the functions: u=a(s,t) v=b(s,t). The whole process is directly
influenced by the distance between viewer and object, the SC space plays a
major role in the computations.
The present invention is described below in further detail with reference
to several examples for illustration. One skilled in the relevant art,
however, will readily recognize that the invention can be practiced in
other environments without one or more of the specific details, or with
other methods, etc. In other instances, well-known structures or
operations are not shown in detail to avoid obscuring the invention.
FIG. 3 is a block diagram of computer system 100 illustrating an example
embodiment in which the present invention can be implemented. Computer
system 100 may be implemented for example, as a stand-alone computer which
displays different images or as a server which renders the images for
display on another system connected by the Internet. Even though computer
system 100 is described with specific components and architecture for
illustration, it should be understood that the present invention may be
implemented in several other types of embodiments. For example, the
invention can be implemented on multiple cooperating networked computer
systems. In addition, each component can be implemented as a combination
of one or more of hardware, software and firmware.
Computer system 100 may contain one or more processors such as central
processing unit (CPU) 110, random access memory (RAM) 120, secondary
storage 130, graphics controller 160, display unit 170, network interface
180, and input interface 190. All the components except display unit 170
may communicate with each other over communication path 150, which may
contain several buses as is well known in the relevant arts. The
components of FIG. 8 are described below in further detail.
CPU 110 may execute instructions stored in RAM 120 to provide several
features of the present invention. RAM 120 may retrieve such instructions
from secondary storage 130 using communication path 150. In the
alternative, the instructions may be retrieved on network interface 180
from an external server provided, for example, by an application service
provider (ASP) or by another division within a same organization. Network
interface 180 may be implemented using Internet protocol (IP). Network
interface 180 may also provide communication with client system 410 during
the target application development process.
Graphics controller 160 may receive commands and data on communication path
150 from CPU 110, and generates display signals (e.g., in RGB format) to
display unit 170. The display signals are generated according to the
commands and data received on communication path 150. Display unit 170
contains a display screen to display the images defined by the display
signals. Input interface 190 may correspond to a key-board and/or mouse,
and generally enables a user to provide inputs. CPU 110, RAM 120, graphics
controller 160, display unit 170, network interface 180, and input
interface 190 may be implemented in a known way.
Secondary memory 130 may contain hard drive 135 and removable storage drive
137. Hard drive 135 may store the software instructions and data, which
enable computer system 100 to provide several features in accordance with
the present invention. Hard drive 135 may also store data representing
curved surfaces of different objects. In the alternative, some or all of
the data and instructions may be provided on removable storage unit 140,
and the data and instructions may be read and provided by removable
storage drive 137 to CPU 110. Floppy drive, magnetic tape drive, CD-ROM
drive, DVD Drive, removable memory chip (PCMCIA Card, EPROM) are examples
of such removable storage drive 137.
Removable storage unit 140 may be implemented using medium and storage
format compatible with removable storage drive 137 such that removable
storage drive 137 can read the data and instructions. Thus, removable
storage unit 140 includes a computer usable storage medium having stored
therein computer software and/or data. An embodiment of the present
invention is implemented using software running (that is, executing) in
computer system 100. In this document, the term .quadrature.computer
program product.quadrature. is used to generally refer to removable
storage unit 140 or hard disk installed in hard drive 135. These computer
program products are means for providing software to computer system 100.
As noted above, computer programs (also called computer control logic) and
data representing bicubic surfaces are stored in main memory (RAM 110)
and/or secondary storage 130. In the embodiments implemented using
software, the software may be stored in a computer program product and
loaded into computer system 100 using removable storage drive 137, hard
drive 135, or network interface 180. Alternatively, graphics controller
160 (implemented using a combination of hardware, software and/or
firmware) may execute the software to provide various features of the
present invention.
The control logic (software), when executed by CPU 120 (and/or graphics
controller 160) causes CPU 120 (and/or graphics controller 160) to perform
the functions of the invention as described herein. In one embodiment, CPU
120 receives the data representing the curved surfaces and instructions,
and processes the data to provide various features of the present
invention described below. Alternatively, CPU 120 may send control points
(described below) to graphics controller 160, which then renders the
image.
For simplicity, irrespective of the specific component(s) performing the
underlying operation, the operations are described as being performed by
computer system 100. The operation and implementation of the components
(including software) will be apparent to one skilled in the relevant arts
at least based on the description provided below. Several aspects of the
present invention are described below with reference to computer system
100 for illustration. The invention permits combining the steps of
subdivision and rendering such they are executed together and in real
time. The execution of both subdivision and rendering is made possible
inside the same graphics controller 160. Alternatively, the subdivision
can be executed by the CPU 110 while the rendering is executed by the
graphic controller 160.
The steps involved in the combined subdivision and rendering of bicubic
surfaces in accordance with the present invention are described below in
pseudo code. As will be appreciated by one of ordinary skill in the art,
the text between the "/*" and "*/" symbols denote comments explaining the
pseudo code.
Step 0. /* For each surface, transform only 16 points instead of
transforming all the
vertices inside the surface given a particular view. There is no need
to
transform the normals since they are generated at step 4 */
For each bicubic surface
Transform the 16 control points that determine the surface
Step 1. /* Simplify the three dimensional surface subdivision by reducing
it to the
subdivision of two dimensional curves */
For each bicubic surface
Subdivide the boundary curve representing s interval until the
projection
of the height of the curve bounding box is below a certain
predetermined
number of pixels as measured in screen coordinates (SC)
Subdivide the boundary curve representing t interval until the
projection
of the height of the curve bounding box is below a certain
predetermined
number of pixels as measured in screen coordinates (SC)
/*Simplify the subdivision termination criteria by expressing it in
screen (SC)
coordinates and by measuring the curvature in pixels. For each new
view, a
new subdivision can be generated, producing automatic level of
detail.*/
Step 2
For all bicubic surfaces sharing a same parameter (either s or t)
boundary
Choose as the common subdivision the reunion of the subdivisions in
order to prevent cracks showing along the common boundary
OR
Choose as the common subdivision the finest subdivision (the one
with
the most points inside the set)
/* Prevent cracks at the boundary between surfaces by using a common
subdivision for all surfaces sharing a boundary */
Step 3/* Generate the vertices, normals and the texture coordinates for the
present
subdivision */
For each bicubic surface
For each pair (si,tj)
Calculate (ui,j v,j qi,j Vi,j)
Generate triangles by connecting neighboring vertices
Step 4
For each vertex Vi,j
Calculate the normal Ni,j to that vertex
For each triangle
Calculate the normal to the triangle
Step 5.
For each vertex Vi,j
Calculate lighting
Step 6
For each triangle
Clip against the viewing viewport
Calculate lighting for the vertices produced by clipping
Step 7.
Project all the vertices Vi,j into screen coordinates (SC)
Step 8
Render all the triangles produced after clipping and projection
The combined subdivision and rendering process for bicubic surfaces will
now be explained in further detail, starting with a description of bezier
surfaces. FIG. 4 is a diagram illustrating the theory of Bezier surfaces.
Such surfaces are completely determined by 16 control points, P11 through
P44. The boundaries of a Bezier surface is defined by four boundary
curves, shown in FIG. 4 P1(t), P4(t), Q1(s) and Q4(s), which are all
Bezier curves. Each boundary curve is defined by a boundary box formed by
the control points that are located above and parallel to the curve. For
example, the boundary box for curve P1(t) is formed by line segments drawn
between control points P11, P12, P13, and P14. The coordinates of any
point on a Bezier surface can be expressed as:
x(s,t)=S*Mb*Px*Mb.sup.t *T
wherein
S=[s3 s2 s 1]
T=[t3 t2 t 1].sup.t The superscript t indicates transposition
##EQU1##
Mb.sup.t is the transposed of matrix Mb
##EQU2##
y(s,t)=S*Mb*Py*Mb.sup.t *T
where
##EQU3##
z(s,t)=S*Mb*Pz*Mb.sup.t *T
When rendering a Bezier surface, the conventional method is to subdivide
the surface into smaller four sided tiles, as shown in FIG. 1A, by
subdividing the intervals across the entire surface that define the
parameters s and t until the subdivision reaches a predetermined
threshold.
According to an aspect of the present invention, requiring that only two
orthogonal curves of the surface be subdivided minimizes the number of
computations required for rendering an object model.
In order to subdivide the surface determined by the sixteen control points
P11-P44 we need only to subdivide a pair of orthogonal curves, either the
pair {P11, P12, P13, P14} {P14, P24, P34, P44} (i.e. P1(t) and Q4(s)) or
the pair {P44, P43, P42, P41} {P41, P31, P21, P11}(i.e., P4(t) and Q1(s)).
It may be observed that one of the curves in the pair is a function only
of parameter s while the other is a function only of parameter t. The
reason this is true is that the curvature of a bicubic surface is a direct
function of the curvature of its boundaries. By controlling the curvature
of the boundaries, computer 100 controls the curvature of the surface.
FIG. 5 depicts a graph illustrating an approach by which computer system
100 may divide a Bezier curve into connected segments of Bezier curves.
The curves formed by the bounding box defining a Bezier curve comprises a
plurality of line segments where each segment lies between two control
points. The approach uses an iterative process that subdivides the
segments that form the bounding box of the curve. At each iteration the
Bezier curve is divided into two curve segments, producing two smaller
bounding boxes. Each subdivision step halves the parameter interval. The
algorithm uses the initial points P1, P2, P3, P4 of the initial boundary
box to produce the points:
L1=P1
L2=(P1+P2)/2
H=(P2+P3)/2
L3=(L2+H)/2
R4=P4
R3=(P3+P4)/2
R2=(R3+H)/2
R1=L4=(L3+R2)/2
The geometry vectors of the resulting left and right cubic curve segments
may be expressed as follows:
##EQU4##
FIG. 6 is a diagram illustrating the criteria which computer system 100 may
use for terminating the subdivision (decomposition) of the Bezier curve.
The subdivision is terminated when a curve reaches a predetermined
flatness. After a subdivision, the height of the bounding box in two
points is measured. If the maximum height of the bounding box is smaller
than a given error term, then a flatness threshold has been met and the
curve bounded by the box is no longer subdivided. In one preferred
embodiment, SC, computer system 100 is described as expressing the error
term to be one pixel.
Max {d1,d2}<1 where d1 and d2 are the distances of P2 respectively P3 to
the segment P1, P4
Subdividing only a pair of orthogonal curves, greatly speeds up the
subdivision because only two curves need to be subdivided instead of the
whole surface, which produces a net of orthogonal curves onto the surface.
In addition, only the curves need to be checked for flatness instead of
the whole surface, thus the subdivision termination criteria is also
simplified.
The manner in which a surface may be subdivided is described in further
detail with reference to FIGS. 7-9. Computer system 100 may subdivide two
of the boundary Bezier curves, P1(t) and Q4(s) for example. Any pair of
orthogonal curves may be chosen. The pairs that can be used are: (P1, Q1),
(P1, Q4),(P4, Q1) and (P4, Q4). For illustration, it will be assumed that
the pair (P1, Q4) is chosen. The curves P1 and Q4 are subdivided according
to the approach described above with reference to FIG. 5. Each subdivision
step for P1 and Q4 halves the parameter interval for t and s respectively.
Three different subdivision termination criteria are illustrated with
reference to FIGS. 7-9.
In FIG. 7 computer system 100 may use the distance from the control point
P22 (as is well known these points are referred to as control points
because their position determines the position of all the other points on
the surface) to the plane determined by points P11, P14, P41 (the
termination point of the pair of orthogonal boundary curves) and the
distance between the control point P33 to the plane formed by P14, P44,
P41 to decide if the surface is within the predetermined criteria of
flatness. Each of these distances may be compensated for the distance from
the viewer by a projection division by the factors P22z/d and P33z/d
respectively where P22z represents the z component of point P22 and P33z
is the z component of P33, d is the distance between the center of
projection and the screen. Using this compensation allows for expressing
the criteria of subdivision termination in terms of pixels, i.e., in SC.
The maximum of the two distances compensated for the distance to the
viewer needs to be less than a number of pixels (one in our example).
Computer system 100 could have used the pair of control points (P23, P32),
computer system 100 could also use groups of three control points (P22,
P23, P33) for example or computer system 100 could have used all four
control points (P22, P23, P32, P33). Two control points are sufficient in
the described embodiments.
FIG. 7 may be used to compare some aspects of the present invention with
some prior art embodiments in terms of determining flatness criteria. The
distance from one of the internal control points (P22 in the example) to
the plane formed by three other control points (P11, P14, P41) is adjusted
for the distance to the viewer by multiplication by the factor d/P22z and
the result may need to be less than one pixel. The same condition may need
to be satisfied for the control point P33:
distance (P22 to plane (P11, P14, P41))*d/P22z<1
AND
distance (P33 to plane (P14, P44, P41))*d/P22z<1
means the termination of the subdivision. What may make the algorithm slow
is the fact that it involves determining the control points P22 and P33
for each iteration. By contrast, an algorithm implemented according to an
aspect of the present invention may make use of the control points of two
of the boundary curves only.
In FIG. 8 is shown an implementation by using the distances of the control
points P12 and P13 to the line segment (P11, P14), the distance of the
control points P24 and P34 to the line segment (P14, P44) compensated for
distance to the viewer need to be less than a predetermined number of
pixels (one, in our case).
Maximum {distance (P12 to line (P11, P14), distance (P13 to line(P11,
P14)}*2d/(P12z+P13z)<1 AND
Maximum {distance (P24 to line (P14, P44), distance (P34 to line(P14,
P44)}* | | |
