 |
Claims  |
|
|
What I claim is:
1. In a graphics apparatus having a processor for processing signals
defining objects in a three-dimensional space, each object being comprised
of a plurality of parametric surface patches, an object-based method of
processing the signals to determine a rendering order for the surface
portions of the object, comprising the steps of:
(a) dividing each surface patch of the object into a plurality of polygons,
so as to generate a set of polygons defining the object;
(b) determining a polygon order in which the polygons in the set may be
rendered so as to effect hidden surface removal; and
(c) determining from said polygon order a patch order in which the patches
of the object may be rendered so as to effect hidden surface removal.
2. A method according to claim 1, wherein steps (b) and (c) are performed
for a plurality of different notional viewing positions in the
three-dimensional space, so as to produce a plurality of patch orders,
each patch order being for a respective notional viewing position, and
wherein the method further comprises the steps of:
receiving input data defining an actual viewing position in the
three-dimensional space; and
selecting one of said plurality of patch orders in dependence upon said
actual viewing position.
3. A method according to claim 1, wherein each surface patch is defined by
Bezier curves.
4. A method according to claim 1, wherein each parametric surface patch has
a curvature, and wherein, in step (a), each given parametric surface patch
is divided into a plurality of polygons by recursive sub-division by the
steps of:
generating processing values indicative of the curvature of the given
parametric surface patch;
calculating a division number for the given parametric surface patch using
said processing values; and
sub-dividing the given parametric surface patch a number of times
corresponding to the division number.
5. A method according to claim 4, wherein each given parametric surface
patch is defined by curves of different curvature and the step of
generating said processing values comprises determining which curve has
the highest curvature, this highest curvature then being taken as the
curvature of the given parametric surface patch.
6. A method according to claim 4, wherein said graphic apparatus is an
interactive three-dimensional system arranged for modelling movement of
said objects in said three-dimensional space in response to input
commands, said apparatus further comprising means for processing said
signals so as to project said objects into a viewing space defined by a
viewing position in said three dimensional space, and wherein the step of
sub-dividing said given parametric surface patch is performed after
projection into said viewing space.
7. A method according to claim 6, wherein the division number calculated
for each given surface patch is independent of said viewing position.
8. A method according to claim 4, wherein each given parametric surface
patch is defined by Bezier curves having a pair of end control points and
a pair of curvature control points.
9. A method according to claim 8, wherein the step of generating said
processing values comprises:
for each Bezier curve in the given patch connecting the end control points
and the curvature control points to define pairs of notional vectors, each
pair of notional vectors having an angle therebetween; and
calculating said processing values in dependence upon said angles.
10. A method according to claim 9, wherein each Bezier curve has a
curvature, wherein, for each Bezier curve, said pairs of notional vectors
comprise a notional connected sequence of vectors, wherein each said angle
is a turning angle from one of said notional vectors to a next one of said
notional vectors in said sequence, and wherein the step of calculating
said processing values includes the step of combining the turning angles
within each sequence of vectors to determine the curvature of each Bezier
curve.
11. A method according to claim 10, wherein the step of calculating said
processing values further includes the step determining which Bezier curve
has the highest curvature, and using this highest curvature as the
curvature of the given parametric surface patch.
12. A method according to claim 9, wherein, in said calculating step, the
angle between each pair of vectors is represented by its cosine.
13. A method according to claim 12, wherein said cosine is calculated by
calculating the dot product of the pair of vectors.
14. A method according to claim 1, wherein the patch order is determined
by:
(i) determining where in the polygon order a polygon from each patch first
occurs, thereby determining a first occurrence for each patch; and
(ii) ordering the patches in dependence upon their first occurrences.
15. A method according to claim 1, wherein the polygon order is determined
independent of a viewing position in the three-dimensional space.
16. A method according to claim 1 wherein, in step (b), the polygons in the
set are ordered using a topological sort.
17. A graphics apparatus for processing signals defining objects in a
three-dimensional space, each object being comprised of a plurality of
parametric surface patches, to determine a rendering order for the surface
patches of a said object, said apparatus comprising:
(a) a divider for dividing each surface patch of the object into a
plurality of polygons so as to generate a set of polygons defining the
object;
(b) a polygon orderer for determining a polygon order in which the polygons
in the set may be rendered so as to effect hidden surface removal; and
(c) a patch orderer for determining from said polygon order a patch order
in which the patches of the object may be rendered so as to effect hidden
surface removal.
18. Apparatus according to claim 17, wherein the polygon orderer and the
patch orderer operate for a plurality of different notional viewing
positions in the three-dimensional space so as to produce a plurality of
patch orders, each patch order being for a respective notional viewing
position, and wherein the apparatus further comprises:
a receiver for receiving input data defining an actual viewing position in
the three-dimensional space; and
a selector for selecting one of said plurality of patch orders in
dependence upon said actual viewing position.
19. Apparatus according to claim 17, wherein each surface patch is defined
by Bezier curves.
20. Apparatus according to claim 17, wherein each parametric surface patch
has a curvature, and wherein the divider divides each given parametric
surface patch into a plurality of polygons by recursive sub-division, said
divider comprising:
means for generating processing values indicative of the curvatures of the
given parametric surface patch;
means for calculating a division number for the given parametric surface
patch using said processing values; and
means for sub-dividing the given parametric surface patch a number of times
corresponding to the division number.
21. Apparatus according to claim 20, wherein each given parametric surface
patch is defined by Bezier curves, each of said Bezier curves having a
pair of end control points and a pair of curvature control points, and
wherein the means for generating said processing values comprises:
means for connecting, for each Bezier curve in the given patch, the end
control points and the curvature control points to define pairs of
notional vectors, each pair of notional vectors having an angle
therebetween; and
means for calculating said processing values in dependence upon said
angles.
22. Apparatus according to claim 21, wherein each Bezier curve has a
curvature, wherein, for each Bezier curve, said pairs of notional vectors
comprise a notional connected sequence of vectors, wherein each said angle
is a turning angle from one of said notional vectors to a next one of said
notional vectors in said sequence, and wherein the means for calculating
said processing values includes means for combining the turning angles
within each sequence of vectors to determine the curvature of each Bezier
curve.
23. Apparatus according to claim 22, wherein the means for calculating said
processing values further includes means for determining which Bezier
curve has the highest curvature, and using this highest curvature as the
curvature of the given parametric surface patch.
24. Apparatus according to claim 21, wherein in said calculating means, the
angle between each pair of vectors is represented by its cosine.
25. Apparatus according to claim 24, wherein said cosine is calculated by
calculating the dot product of the pair of vectors.
26. Apparatus according to claim 20 wherein each given parametric surface
patch is defined by curves of different curvature and the means for
generating said processing values determines which curve has the highest
curvature, this highest curvature then being taken as the curvature of the
given parametric surface patch.
27. Apparatus according to claim 20, wherein said graphic apparatus is an
interactive three-dimensional system arranged for modelling movement of
said objects in said three-dimensional space in response to input
commands, said apparatus further comprising means for processing said
signals so as to project said objects into a viewing space defined by a
viewing position in said three-dimensional space, and wherein the means
for sub-dividing said given parametric surface patch performs the
sub-division after projection into said viewing space.
28. Apparatus according to claim 27, wherein the division number calculated
for each given surface patch is independent of said viewing position.
29. Apparatus according to claim 7, wherein said patch orderer comprises:
(i) a first sorter for determining where in the polygon order a polygon
from each patch first occurs so as to determine a first occurrence for
each patch; and
(ii) a second sorter for ordering the patches in dependence upon their
first occurrences.
30. Apparatus according to claim 17, wherein the polygon orderer determines
the polygon order independent of a viewing position in the
three-dimensional space.
31. Apparatus according to claim 17, wherein the polygon orderer determines
the polygon order using a topological sort.
32. A computer-readable medium wherein there is embodied a program for
causing an image processing apparatus having a processor for processing
signals defining objects in a three-dimensional space, each object being
comprised of a plurality of parametric surface patches, to perform an
object-based method of processing the signals to determine a rendering
order for the surface portions of the object, which method comprises the
steps of:
(a) dividing each surface patch of the object into a plurality of polygons,
so as to generate a set of polygons defining the object;
(b) determining a polygon order in which the polygons in the set may be
rendered so as to effect hidden surface removal; and
(c) determining from said polygon order a patch order in which the patches
of the object may be rendered so as to effect hidden surface removal.
33. A computer-readable medium according to claim 32, wherein steps (b) and
(c) are performed for a plurality of different notional viewing positions
in the three-dimensional space, so as to produce a plurality of patch
orders, each patch order being for a respective notional viewing position,
and wherein the method further comprises the steps of:
receiving input data defining an actual viewing position in the
three-dimensional space; and
selecting one of said plurality of patch orders in dependence upon said
actual viewing position.
34. A computer-readable medium according to claim 32, wherein each surface
patch is defined by Bezier curves.
35. A computer-readable medium according to claim 32, wherein each
parametric surface patch has a curvature, and wherein, in step (a), each
given parametric surface patch is divided into a plurality of polygons by
recursive sub-division by the steps of:
generating processing values indicative of the curvature of the given
parametric surface patch;
calculating a division number for the given parametric surface patch using
said processing values; and
sub-dividing the given parametric surface patch a number of times
corresponding to the division number.
36. A computer-readable medium according to claim 35, wherein each given
parametric surface patch is defined by Bezier curves having a pair of end
control points and a pair of curvature control points.
37. A computer-readable medium according to claim 36, wherein the step of
generating said processing values comprises:
for each Bezier curve in the given patch connecting the end control points
and the curvature control points to define pairs of notional vectors, each
pair of notional vectors having an angle therebetween; and
calculating said processing values in dependence upon said angles.
38. A computer-readable medium according to claim 37, wherein each Bezier
curve has a curvature, wherein, for each Bezier curve, said pairs of
notional vectors comprise a notional connected sequence of vectors,
wherein each said angle is a turning angle from one of said notional
vectors to a next one of said notional vectors in said sequence, and
wherein the step of calculating said processing values includes the step
of combining the turning angles within each sequence of vectors to
determine the curvature of each Bezier curve.
39. A computer-readable medium according to claim 38, wherein the step of
calculating said processing values further includes the step determining
which Bezier curve has the highest curvature, and using this highest
curvature as the curvature of the given parametric surface patch.
40. A computer-readable medium according to claim 25, wherein the division
number calculated for each given surface patch is independent of said
viewing position.
41. A computer-readable medium according to claim 37, wherein, in said
calculating step, the angle between each pair of vectors is represented by
its cosine.
42. A computer-readable medium according to claim 41, wherein said cosine
is calculated by calculating the dot product of the pair of vectors.
43. A computer-readable medium according to claim 35, wherein each given
parametric surface patch is defined by curves of different curvature and
the step of generating said processing values comprises determining which
curve has the highest curvature, this highest curvature then being taken
as the curvature of the given parametric surface patch.
44. A computer-readable medium according to claim 35, wherein said graphic
apparatus is an interactive three-dimensional system arranged for
modelling movement of said objects in said three-dimensional space in
response to input commands, said apparatus further comprising means for
processing said signals so as to project said objects into a viewing space
defined by a viewing position in said three dimensional space, and wherein
the step of sub-dividing said given parametric surface patch is performed
after projection into said viewing space.
45. A computer-readable medium according to claim 32, wherein the patch
order is determined by:
(i) determining where in the polygon order a polygon from each patch first
occurs, thereby determining a first occurrence for each patch; and
(ii) ordering the patches in dependence upon their first occurrences.
46. A computer-readable medium according to claim 32, wherein the polygon
order is determined independent of a viewing position in the
three-dimensional space.
47. A computer-readable medium according to claim 32, wherein, in step (b),
the polygons in the set are ordered using a topological sort. |
|
 |
|
 |
Claims |
|
|
|
Description |
|
|
FIELD OF THE INVENTION
The present invention relates to apparatus and methods for processing image
data.
In particular, the present invention relates to apparatus and methods for
displaying three-dimensional images. Furthermore, the present invention
relates to an interactive graphics system in which objects are defined by
areas and said areas are split into a plurality of polygons.
BACKGROUND OF THE INVENTION
Graphics systems are known in which two-dimensional images are generated in
response to data defining elements within a three-dimensional space. The
final two-dimensional result may consist of a very large number of colored
picture elements (pixels) which may be viewed on a monitor or printed onto
an image carrying medium.
In interactive systems arranged to generate data representing a
three-dimensional space, objects appear to move within three-dimensional
space in response to input commands. Thus, in such systems, a machine is
required to render a two-dimensional image from data representing a
three-dimensional space repeatedly, as the position and/or orientation of
objects, light sources and view position change in response to input
commands. Typically, in an interactive environment, a machine is required
to produce output images at a rate of between five to twenty per second.
Traditional machines of this type require a significant amount of
computational overhead and, in the past, this requirement has placed
significant constraints on system availability. Many techniques have been
developed on behalf of the present Assignee, some of which provide the
basis for patent applications assigned to the present Assignee, which
reduce the computational overhead of an interactive three-dimensional
graphics system. These techniques allow three-dimensional interactive
graphic systems to be produced without requiring purpose built hardware.
In a system of this type, object geometry undergoes transformations in
response to transformation matrices. The geometry is defined by the
vertices of a plurality of polygons and, in order to effect a
transformation of the object, it is necessary to perform the matrix
transformation on each of said vertices. Thus, when a high number of
polygons are present, a significant amount of computation is required in
order to transform all of the object forming vertices.
As an alternative to transforming vertices, it is also known to transform
complete areas of an object which are then rendered into polygons after
the transformation has taken place. With this approach, it is not
necessary to transform a large number of vertices, provided that
sufficient data can be transformed to allow the object to be reconstituted
after the transformation has taken place.
An area defined by Bezier curves and referred to as a Bezier patch is a
suitable area for this type of transformation. Thus, a relatively large
patch, capable of defining a large range of curves, may be identified by
specifying sixteen control points, wherein each control point is either an
end control point or an intermediate curvature control point for two of
the eight Bezier curves defining the patch. A Bezier curve has finite
length and is terminated at each of its ends by end control points. The
intermediate curvature control points define the extent of curvature which
occurs between the end points but the actual curve does not pass through
the intermediate curvature control points. It should be noted that a
Bezier patch defines a three-dimensional patch and the control points of
the patch may be positioned anywhere within three-dimensional space.
However, to effect rendering, it is necessary to divide the plane into
polygons which are substantially flat or at least flat enough to effect a
convincing rendering.
To effect rendering, it is known to recursively or iteratively sub-divide
Bezier patches, effectively generating more points which are a closer
approximation to the actual curve. Rendering may then be performed by
using said points to define flat edged polygons, usually quadrilaterals
or, preferably, triangles, whereafter individual pixels are allocated to
the regions within the polygons by a process known as scan conversion.
When rendering polygons which have been obtained by sub-dividing an area,
it is preferable to render the polygons on an area-by-area basis. Given a
sequence of polygons, it is known that it is possible to produce rendering
order lists for said polygons. However, a problem exists in that the
availability of a list for polygons does not: facilitate the rendering of
said polygons on an area-by-area basis.
SUMMARY OF THE INVENTION
According to an aspect of the present invention, there is provided a method
of rendering objects defined by a plurality of areas, wherein each area is
reduced to a plurality of polygons, comprising sorting an order for
rendering said areas by: diving each area into a set of polygons,
selecting a rendering order for all of said polygons; and determining a
rendering order for said areas based on the first selection of a polygon
from each area set.
Thus, the present invention provides the advantage of, giving an order list
for polygons, being able to produce an ordering list for sub-divided areas
.
BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 shows an interactive three-dimensional graphics system, including a
processor for manipulating three-dimensional delta and generating
two-dimensional data;
FIG. 2 shows a Bezier curve, the control points for defining said curve and
the equations for calculating points on the curve from the position of
said control points;
FIG. 3 shows a Bezier patch, defined by Bezier curves;
FIG. 4 illustrates the operation of an interactive three-dimensional
graphics system, embodying the present invention.
FIGS. 5 and 6 illustrate a preferred procedure for calculating the
curvature of a Bezier patch and for determining the number of iterations
required to divide the patch into polygons;
FIG. 7 illustrates the procedure for determining the order in which patches
are to be rendered;
FIG. 8A shows conventional polygonisation of a Bezier patch; and
FIG. 8B shows a Bezier patch polygonisation produced by an embodiment of
the present invention.
DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS
A system for processing image data representing three-dimensional objects
is shown in FIG. 1. A processor 15 is arranged to write data to and read
data from local memory. Data stored in the processor's memory defines
three dimensional image data, two dimensional image data and instructions
to the processor 15.
The processor 15 receives input data, from input devices consisting of a
manually operable keyboard 17 and a position sensitive device, such as a
mouse, a trackerball 18 or a digitising stylus etc.
Two-dimensional images are displayed on a visual display unit 19, which
receives output image data at video rate by raster scanning a frame
buffer, often provided with proprietry display units. The visual display
unit has a definition of, typically, one thousand lines with one thousand
pixels on each line, requiring a frame buffer with one million pixel
locations. For the bulk transfer of program data and image data, a mass
storage device 20 is provided, such as a hard magnetic disk, optical disk
or tape drive etc.
In the present embodiment, data defining geometry is stored in the form of
control points defining Bezier patches, which may be manipulated in
three-dimensional space. Thereafter, once a viewing position has been
selected for rendering in two-dimensions, each Bezier patch is broken down
into a plurality of vertices defining polygons, whereafter pixel values
are calculated by scanning the area of each polygon.
A parametric Bezier curve 25 is shown in FIG. 2, consisting of a locus of
points moving from an end control point A to another end control point D,
in response to the position of curvature control points B and C. The locus
of points are calculated over the parameter space t=0 to t=1 and, for each
value of t, a point may be calculated which receives contributions from
the positions of points A, B, C and D. The blending contributions are
determined from a bi-cubic function known as the Bernstein blending
function, detailed below the Bezier curve in FIG. 2. Thus, points along
the curve are calculated by substituting the x, y and z coordinate values
of the control points A, B, C and D into the blending function for
calculating new values for x, y and z, as t varies between zero and unity.
An attractive feature of Bezier curves, within an interactive graphics
environment, is that the curve can be drawn to any requried resolution
from input data consisting of the coordinates for points A, B, C and D.
Thus, the whole curve can be manipulated in three-dimensional space by
manipulating the positions of just the four control points which define
it. Thereafter, rendering to create a displayable image can be performed
at any desired resolution, by dividing the surface into flat polygons and
then rendering each polygon.
As shown in FIG. 2, when points A, B, C and D are connected by vectors AB,
BC and CD it can be seen that the actual curve is tangential to vector AB
at point A and tangential to vector CD at the end control point D. It can
also be seen that the position of points B and C controls the extent of
the curvature and these points are therefore referred to herein as
curvature control points.
In a system such as than shown in FIG. 1, data defining the shape of the
Bezier curve 25 consists of three-dimensional coordinate locations for the
control points A, B, C and D. In order to render such a curve it is
necessary to approximate its shape by straight line segments defining
renderable flat polygons. As previously stated, an approach would be to
calculate points using the blending function detailed in FIG. 2, although
problems with this approach include deciding how many points need to be
calculated and executing the demanding calculations.
In the present embodiment, areas are divided into a plurality of polygons
by recursive or interative sub-division and this technique will be
detailed with reference to the single Bezier curve shown in FIG. 2. A
first approximation to the actual Bezier curve 25 would consist of vectors
AB, BC and CD joining the control points A, B, C anti D. As readily
appreciated from the example shown in FIG. 2, such an approximation would
rarely provide satisfactory results, given that the curvature control
points may be a significant distance away from the locus of the actual
curve.
Sub-division is performed by identifying an intermediate point E between
points A and B. This point is easily calculated because the x coordinate
of E is the average of the x coodinates for points A and B and similarly
averaged values can be determined for the y and z coordinates. Thus, a
similar intermediate point F is located halfway along the vector BC and a
third intermediate point G is identified halfway along the vector CD. This
process is continued by identifying an additional point H halfway along
vector EF and point I halfway along vector FG, from which a new vector HI
is defined. Finally, point J is calculated as a point halfway along vector
HI.
Points E, H, I and G do not lie on the Bezier curve 25 but point J is a
point of the Bezier locus. Furthermore, the Bezier curve 25 connecting
points A to D may now be considered as two Bezier curves, a first
connecting points A to J and a second connecting points J to D. Thus, the
curve not only passes through point J but, at point J, it is also
tangential to the vector HI. Thus, point J provides a new end control
point for two Bezier curves while points E and H provide a first set of
curvature control points and points I and G provide a second set of
curvature control points.
From a rendering point of view, an initial approximation consisting of the
three straight lines AB, BC and CD has being improved by the generation of
six straight lines AE, EH, HJ, JI, IG and GD.
In some situations, this first iteration will not be sufficient. However, a
better approximation to the curve 25 may be generated by considering the
curve to be made up of two separate Bezier curves, a first defined by
control points A, E, H and J and a second defined by control points J, I,
G and D. Thus, the sub-division procedure, performed and illustrated in
FIG. 2 for points A, B, C and D, may be repeated firstly for points A, E,
H and J and secondly for points J, I, G and D. Thus, this sub-dividing
could be repeated to the resolution limits of the system and the problem
with the technique, as previously identified, is that of deciding how many
sub-divisions are to be performed.
After each division it is possible to perform a flatness test, as described
in "Computer Graphics Principles and Practice", second edition, pp 513-514
by Foley, van Dam, Feiner and Hughes. However, if flatness tests are
performed each time, the overall computational overhead becomes excessive
and the computational reduction gained by using Bezier curves is
substantially lost, due to the repeated flatness testing.
A Bezier curve, consisting of a locus of points is defined in two
dimensions. However, a group of Bezier curves combined to define a plane,
referred to as a Bezier patch, includes control points which may be
positioned anywhere in three-dimensional space. The control points for a
Bezier patch of this type are shown in FIG. 3, in which points A1, B1, C1
and D1 define a Bezier curve, points A2, B2, C2 and D2 define a second
curve, points A3, B3, C3, D3 define a third curve and points A4, B4, C4
and D4 define a fourth curve. In addition, a second set of curves is
defined by points A1, A2, A3, A4, points B1, B2, B3 and B4, points C1, C2,
C3, C4 and points D1, D2, D3 and D4. Thus, the patch is defined by a total
of eight Bezier curves in three-dimensional space, configured from a total
of sixteen control points, in which each of said points provides a control
point for two of said curves. Some control points (A1, D1, A4 and D4) are
end control points for two curves, while some (B2, C2, B3, C4) are
curvature control points for two curves, while the reminder are end contol
points for one curve but curvature control points for the other.
As can be seen from FIG. 3, vectors connecting the control points divide
the patch into a total of nine segments. However, it should also be
understood that the lines shown connecting points in FIG. 3 do not
actually lie on the curve itself but are equivalent to vectors AB, BC and
CD of FIG. 2
Thus, the nine polygons shown in FIG. 3, formed by connecting the control
points of the Bezier patch, could be used to provide a first approximation
to the actual patch, for rendering purposes, in the same way in which
vectors AB, BC and CD form a first approximation to the Bezier curve 25 in
FIG. 2. This division consists of connecting all adjacent control points
and illustrates the accepted way of dividing the patch into renderable
polygons. Furthermore, more accurate polygonization can be provided by
sub-dividing each Bezier curve of FIG. 3, wherein each curve is divided
into a pair of curves, having a common end control point, similar to point
J in FIG. 2. Thus, by sub-dividing each curve, each quadrilateral polygon
is divided into four smaller quadrilateral polygons, resulting in a total
of 36 polygons for the whole patch.
As stated with reference to FIG. 2, the newly calculated point J is a point
which does actually lie on the Bezier curve. Similarly, when considering a
surface, newly calculated point K at the centre of the surface is a point
which actuality does lie on the surface. Thus, the patch may be considered
as being made up of four smaller patches and the sub-dividing process may
be repeated for each of these four patches.
As previously stated, a known problem with dividing patches in this way is
in performing tests to determine whether, after each division, a further
division is required. In the present embodiment pre-processing is
performed on each Bezier patch to determine how many iterations are
required for that patch, so that, after transformation into
two-dimensional viewing space, sub-division is performed n times for each
patch, where the value n for that particular patch was precalculated.
The operational stages performed by the apparatus shown in FIG. 1 and
embodying the present invention are shown in FIG. 4.
Geometry data, defining the shape of objects, is stored in the form of
control points for Bezier patches of the type shown in FIG. 3. Each patch
includes a total of sixteen vertices, A1 to D4 from which the overall
shape of the patch for any orientation in three-dimensional space and from
any viewing position, can be determined.
In FIG. 4, steps 42 to 44 are pre-processes performed prior to the
initiation of interactive operation. The pre-processes calculate data,
relevant to the objects under consideration, so as to reduce computational
demands during interactive operation: it being noted that many of the
processing requirements forming part of the interactive loop are required
to be performed during each iteration, therefore substantial savings can
be made by reducing the amount of processing required within the
interactive loop.
At step 42, a determination is made as to the number of iterations required
to produce a sufficient number of polygons for each Bezier patch. Thus,
although polygons are produced using the previously described sub-division
technique, it is not necessary, during this process, to determine whether
sufficient divisions have been made. The level of divisions required is
pre-calculated and whenever polygons are required to be produced from
Bezier patches, this data is recalled and sub-division is performed n
times, where n is generated during the pre-processing period.
At step 43, the polygons are generated in modelling space, also referred to
as object space, so that, in modelling space, the object is defined by its
Bezier control points and also by polygons, produced by n sub-divisions.
Furthermore a unit normal vector is calculated for each polygon, allowing
lighting calculations to be performed in modelling space.
At step 44, calculations are made to determine the order in which patches
should be rendered. An example of a technique for assessing the order in
which the polygons should be rendered is detailed in our copending U.S.
patent application Ser. No. 07/937,701 (corresponding to EP-A-0531157).
The technique detailed in this Patent Application is employed upon the
polygons produced at step 43. This information is then used to determine
the order in which whole patches should be rendered, wherein the first
occurence of a polygon from a particular patch in the priority order,
established the priority for the whole patch.
After the termination of step 44, the system is ready to enter interactive
operation, in which objects, light sources and the position of the viewer
appear to move within a synthesized three-dimensional space, in response
to input commands.
On initiating interactive operation, objects (defined by Bezier patches),
light sources and a viewing position are defined and the objects are
projected onto a two-dimensional viewing plane. Each iteration of the
interactive loop consists of receiving input data defining translations
within three-dimesional space, projecting three-dimensional data onto a
two-dimensional viewing plane and rendering the two-dimensional data into
an array of pixels. Given that objects are constructed from a plurality of
patches, the order in which said patches are rendered depends upon the
orientation of the object and the viewing position. At step 44, lists are
constructed specifying patch rendering orders for particular view
orientations. At step 46 the view orientation of the object is determined
and this information, in addition to data determined at step 44, is used
to calculate the order in which the patches themselves are rendered. Thus,
flow line 47 represents the transfer of information from step 44 to step
46.
At step 48, control points for the first patch to be rendered, as
determined at step 46, are transformed, under the operation of a
transformation matrix, to two-dimensional viewing space.
At step 49, the control points transformed into two-dimensional viewing
space are sub-divided n times, where the value n was previously calculated
at step 42 and the transfer of information from step 42 to step 49 is
illustrated by flow arrow 50.
When the whole patch has been scan converted at step 51, a question is
asked at step 52 as to whether further patches are present in the scene.
If this question is answered in the affirmative, control is returned to
step 48, which reads the next set of control points for transformation
into two-dimensional space. Thus, this reading of control points, with
subsequent sub-division and scan conversion is repeated until all of the
patches have been reduced to pixels. This results in the question asked at
step 52 being answered in the negative and, at step 53, calculated pixel
values are written to a frame buffer 55.
In addition to being written to the frame buffer at interactive rate, the
frame buffer 55 is also read repeatedly, at step 55A, at video rate,
thereby generating a video output signal for the monitor 19.
At step 54, interactive input commands are read and at step 54A new
transforms are calculated in response to the interactive inputs received
at step 54. Thus, in response to the interactive input supplied at step
54, modified transformations are effected at step 48.
After recalculating the transformations, control is returned to step 45,
thereby completing the interactive loop. If, in response to interactive
inputs received at step 54, the position of an object has not changed with
respect to the position of any light source, lighting calculations are
reused at step 45.
Curvature is determined by considering each Bezier curve making up the
patch and a notional value representing the curvature of the patch is
adopted based upon the most curved Bezier curve of the patch.
A Bezier curve similar to the curve shown in FIG. 2, is shown in FIG. 5.
Pre-processing performed at step 42 involves considering the positions of
points A, B, C and D, that is to say, the control points defining the
Bezier curve rather than the locus of the Bezier curve itself. The points
A, B, C and D are considered as connected by vectors AB, BC and CD. Vector
AB has a direction defined by that taken to move from A to B. Similarly,
vector BC has a direction, being that required to move from B to C, while
the direction of vector CD is that required to move from point C to point
D. When considered as a combined movement from point A to D via point B
and point C, a turn is encountered at point B and a similar turn is
encountered at point C. These turns may be defined by turning angles t1
and t2 respectively. Furthermore, the extent of these turning angles t1
and t2 are related to the curvature of the Bezier curve itself, therefore
an analysis of turning angles t1 and t2 provides a basis for calculating
the curvature of the patch, which is then used to determined the number of
sub-divisions required to divide the patch into a suitable number of
polygons.
Each patch is considered in turn and each set of control points (a total of
eight sets) defining the Bezier curves for the patch are considered in
turn. Thus, referring to the control points shown in FIG. 5, vectors AB,
BC and CD are converted to define vectors having equivalent directions but
of unit length. Thus, the converted vector derived from vector AB will be
identified herein as AB with similar representations BC and CD being used
to represent the unit vectors derived from vectors BC and CD respectively.
A value representing the curvature of the Bezier curve is calculated by
forming the sum of the dot product between unit vectors AB and BC and the
dot product between unit vectors BC and CD. Being of unit length, the
result of calculating the dot product of AB and BC will be equal to the
cosine of angle t1. Similarly, the dot product of BC with CD will be equal
to the cosine of angle t2.
In theory, angles t1 and t2 may have any value from zero to a full 360
degrees. A numerical value is calculated representing curvature by
considering the cosine of the turning angle determined, as previously
stated, by calculating the dot product of unit vectors. A major advantage
of using the cosine function is that a positive turn angle in excess or
180 degress yields the same result as its negative equivalent. Thus, the
cosine function only measures the amount of turn and is not influenced by
the direction of the turn.
The Bezier curve is least curved when angle t1 is small (or reflex)
therefore the curve is less curved when the cosine of t1 is positive.
Similarly, the curve becomes more curved as the cosine value becomes
negative, with the extreme condition being at 180 degrees, where the
cosine is -1.
The overall curvature of the curve is determined by adding together the
cosine of angle t1 with the cosine of angle t2, thereby giving curvature
values which range from +2 (least curved) to -2 (most curved).
The curvature of the whole patch is determined by the most curved curve
defining the patch. Thus, the patch as a whole will be accorded a notional
curvature value equal to the lowest (most negative) value calculated for
the Bezier curves making up the patch. This measure of notional curvature
provides a basis for determining the number of sub-divisions required to
divide the patch into renderable polygons. The number of sub-divisions
performed may vary from machine to machine and specific values for one
type of machine for a particular environment may be calculated
emperically. In the present embodiment the maximium number of
sub-divisions which may be performed is five.
The operations performed at step 42 in FIG. 4 are detailed in FIG. 6. A
first patch is selected and a first Bezier curve of said patch is
considered at step 61, which reads the three-dimensional coordinates for
the four control points defining the Bezier curve, A, B, C, D. At step 62
unit vectors AB, BC and CD are calculated by considering vectors AB, BC
and CD. As previously stated, each unit vector has a direction equivalent
to the vector from which it is derived but is of unit length.
At step 63 the combined cosine value COS is calculated as the sum of the
dot products between AB with BC and BC with CD.
At step 64, a question is asked as to whether there is another curve (of
the eight curves defining the patch) to be considered within the patch and
if this question is answered in the affirmative, control is returned to
step 61 and the coordinate values A, B, C, D for the next curve are
considered.
If the question asked at step 64 is answered in the negative, the smallest
| | |
