 |
Claims  |
|
|
What is claimed is:
1. A method of converting a continuous 3-D straight line segment into a
discrete set of voxels connected together in discrete 3-D voxel space,
said 3-D straight line segment being defined by two endpoints P.sub.1 and
P.sub.2 each having integer coordinates and specifying extents of x, y and
z coordinate directions of said 3-D straight line segment, said discrete
3-D voxel space being characterized by orthogonal x, y, and z coordinate
directions, the addresses of said discrete 3-D voxel space being specified
by integer x, y and z coordinate values of said voxels, said method
comprising the sequence of steps of:
(a) computing the value of an integer n to determine the number of sample
points sampled along said continuous 3-D straight line segment, said
sample points and said integer n represents the number of said voxels in
said discrete set;
(b) defining
integer voxel-coordinate error variables for said x, y, and z coordinate
directions, and
first and second error variable increments along each said x, y and z
coordinate directions;
(c) specifying the initial values of said integer error variables;
(d) placing into said discrete 3-D voxel space, said voxel having x, y and
z coordinate values of said first end point P.sub.1 of said sampled 3-D
straight line segment; and
(e) converting voxels corresponding to said sample points of said discrete
set of voxels, in said discrete 3-D voxel space.
2. The method of claim 1, wherein step (e) comprises, for the subsequent
voxel of said discrete set of voxels, in a symmetrical loop,
(i) determining said integer coordinate values in said x, y and z
coordinate directions which are closest to a corresponding sample point of
said continuous 3-D line segment, said determination of said integer x, y
and z coordinate values being determined on the basis of said integer
error voxel-coordinate variables and said first and second error variable
increments for x, y and z coordinate directions;
(ii) updating said error voxel-coordinate variables for said x, y and z
coordinate directions, on the basis of respective first and second error
variable increments;
(iii) placing into said discrete 3-D voxel space, said voxel having said
integer x, y and z coordinate values determined in step (e)(i); and
(f) repeating in a loop fashion, step (e) for the subsequent voxel of said
discrete set of voxels, until said integer coordinate values for the last
voxel is determined, whereby said continuous 3-D straight line segment is
converted into said discrete set of voxels connected together in said
discrete 3-D voxel space.
3. The method of claim 2, wherein step (b) comprises
defining said integer voxel-coordinate error variables for said x, y and z
coordinate directions and said first and second error variables increments
along each said x, y and z coordinate directions, each on the basis of
said x, y and z extents and said integer n.
4. The method of claim 2, wherein step (a) comprises
setting said integer n to an integer value proportional in magnitude to the
maximum of said x, y and z extents, and wherein step (e)(i) comprises
determining said x, y and z integer coordinate values by independently
stepping along said x, y and/or z coordinate directions.
5. The method of claim 2, wherein step (a) comprises
setting said integer n to an integer value proportional in magnitude to the
sum of said x, y and z extents, and
wherein said step (e)(i) comprises
determining said x, y and z integer coordinate values by stepping along
only one of said x, y and z coordinate directions.
6. The method of claim 2, wherein step (a) comprises
setting said integer value n to an integer value proportional in magnitude
to the maximum of
(1) the maximum of said x, y and z extents, and
(2) the ceiling of one-half of the sum of said x, y and z extents, and
wherein step (e)(i) comprises
determining said x, y and z integer coordinate values by stepping along
x and/or y,
or y and/or z,
or x and/or z coordinate directions.
7. A method of converting a continuous 3-D parametric polynomial curve
segment into a discrete set of voxels connected together in discrete,3-D
voxel space, said 3-D parametric curve segment having first and second
endpoints and being defined by a k.sup.th order polynomial vector T, a
geometric basis matrix M, a geometric control point vector G, parameter t,
and an integer step size along said parameter t, said discrete 3-D voxel
space being characterized by orthogonal x, y, z coordinate directions, the
addresses of said discrete 3-D voxel space being specified by integer x, y
and z coordinate values of said voxels, said method comprising the
sequence of steps of:
(a) computing the value of integer n corresponding to the number of sample
to be sampled along said parameter t of said continuous 3-D parametric
polynomial curve segment, said integer n being determined so that
consecutive voxels of said discrete set of voxels are connected;
(b) defining a K.sup.th order integer finite forward difference matrix for
said 3-D parametric polynomial curve segment, for which said parameter t
takes on integer values from o to n;
(c) determining an initial K.sup.th order finite forward difference vector
for said 3-D parametric polynomial curve segment, on the basis of said
K.sup.th order finite forward difference matrix, said geometric basis
matrix M, and said geometric control point vector G;
(d) defining integer decision variables for said x, y and z coordinate
directions, first and second decision thresholds based on n, and a
decision variable increment based on n;
(e) specifying an initial value for each said integer decision variable of
step (d);
(f) placing into said discrete 3-D voxel space, said voxel having x, y, and
z coordinate values corresponding to the first endpoint of said 3-D
parametric polynomial curve segment; and
(g) converting said continuous 3-D parametric polynomial curve segment into
said discrete set of voxels, said conversion being based on said integer
decision variables, said first and second thresholds, said decision
variable increment, and said first endpoint.
8. The method of claim 7, wherein step (g) comprises: for each integer
value of said parameter t from o to n,
(i) determining said integer coordinate values in the x, y and z coordinate
directions which are closest to a corresponding sample point of said 3-D
parametric polynomial curve segment, said determination of said integer x,
y and z coordinate values being determined on the basis of said integer
decision variables defined in step (d) and said first and second decision
thresholds;
(ii) updating said integer decision variables using said decision variable
increment, and updating said finite forward difference vector,
(iii) placing into said discrete 3-D voxel space, said voxel having said
integer x, y and z coordinate values determined in step (i); and
(iv) repeating in a loop fashion, steps (i), (ii) and (iii) for the
subsequent voxels of said discrete set of n voxels, until said integer
coordinate values for last voxel is determined, whereby said 3-D
continuous parametric polynomial curve segment is converted into said
discrete set of voxels connected together in said discrete 3-D voxel
space.
9. A method of converting a continuous 3-D parametric polynomial surface
patch into a discrete set of voxels connected together in discrete 3-D
voxel space, said 3-D parametric polynomial surface patch being defined by
bi-K.sup.th order polynomial vectors T and U, a geometric basis M, a
geometric control point matrix G, and parameters t and u each with an
integer step size, said 3-D parametric polynomial surface patch being
formed by a plurality of 3-D parametric polynomial curve segments each
having first and second endpoints, said discrete 3-D voxel space being
characterized by orthogonal x, y, and z coordinate directions, the
addresses of said discrete 3-D voxel space being specified by integer x,
y, and z coordinate values of said voxels, said method comprising the
sequence of steps of:
(a) computing the values of integers n and m corresponding to the number of
sample points to be sampled along said parameters t and u, respectively,
of said continuous 3-D parametric polynomial surface patch, said integers
n and m being determined so that a resulting set of voxels lack tunnels;
(b) defining first and second bi-K.sup.th order integer finite forward
difference matrices for said 3-D parametric polynomial surface patch, said
first bi-K.sup.th order finite forward difference matrix corresponding to
said parameter t which takes on integer values from o to n, and said
second bi-K.sup.th order finite forward difference matrix corresponding to
said parameter u which takes on integer values from o to m;
(c) determining an initial bi-K.sup.th order finite forward difference
matrix for said 3-D parametric polynomial surface patch, on the basis of
said first and second bi-K.sup.th order finite forward difference
matrices, said geometric basis matrix M, and said geometric control point
matrix G;
(d) defining surface integer decision variables for said x, y and z
coordinate directions, and first and second decision thresholds based on n
and m, and a decision variable increment based on n and m;
(e) specifying an initial value for each said surface integer decision
variable of step (d); and
(f) converting said continuous 3-D parametric polynomial surface patch into
said discrete set of voxels, said conversion being based on said integer
decision variables, said first and second thresholds, said decision
variable increment, and said first endpoint.
10. The method of claim 9, wherein step (f) comprises:
for each integer value of u from o to m, converting a u-th continuous 3-D
parametric polynomial curve segment by holding constant said parameter u
and varying parameter t from o to n, by
(i) placing into said discrete 3-D voxel space, said voxel corresponding
with said first endpoint of said u-th 3-D parametric polynomial curve
segment,
(ii) forming an initial K.sup.th order finite forward difference vector for
said u-th 3-D parametric polynomial curve segment on the basis of said
initial bi-K.sup.th order finite forward difference matrix for said 3-D
parametric polynomial surface patch,
(iii) defining curve integer decision variables for said x, y and z
coordinate directions for said u-th 3-D parametric polynomial curve
segment,
(iv) specifying an initial value for each curve integer decision variable,
(v) converting said u-th 3-D parametric polynomial curve segment into said
discrete set of voxels,
(vi) updating said finite forward difference matrix,
(vii) determining said integer coordinate values in said x, y, and z
coordinate directions which are closest to said first endpoint of the
(u+1).sup.st 3-D parametric polynomial curve segment, said determination
of said integer coordinate values being determined on the basis of said
surface integer decision variables defined in step (d) and said first and
second decision thresholds, and
(viii) updating said surface integer decision variables using said integer
decision variable increment.
11. The method of claim 10, wherein step (v) further comprises: for each
integer value of said parameter t from o to n,
(1) determining said integer coordinate values in the x, y and z coordinate
directions which are closest to a corresponding sample point of said u-th
3-D parametric polynomial curve segment, said determination of said
integer x, y, and z coordinate values being determined on the basis of
said curve integer decision variables and said first and second decision
thresholds;
(2) updating said curve integer decision variables using said decision
variable increment;
(3) updating said finite forward difference vector for the u-th 3-D
parametric polynomial curve segment, formed in step (ii);
(4) placing into said discrete 3-D voxel space, said voxel having said
integer x, y and z coordinate values determined in step (1); and
(5) repeating in a loop fashion, steps (1), (2), (3), and (4) for the
subsequent voxels of said discrete set of voxels, until said integer
coordinate values for last voxel are determined.
12. A method of converting a continuous 3-D parametric polynomial volume
element into a discrete set of voxels connected together in discrete 3-D
voxel space, said 3-D parametrical polynomial volume element being defined
by cubic order polynomial vectors T, U and V, a geometric basis M, a
geometrical control point tensor G, and parameters t, u, and v each with
an integer step size, said 3-D parametric polynomial volume element being
formed by a plurality of 3-D parametric polynomial surface patches each of
which is formed by a plurality of 3-D parametric polynomial curve segments
each having first and second endpoints, said discrete 3-D voxel space
being characterized by orthogonal x, y and z coordinate directions, the
addresses of said discrete 3-D voxel space being specified by integer x, y
and z coordinate values of said voxels said method comprising the sequence
of steps of:
(a) computing the values of integers n, m and 1 corresponding to the number
of sample points to be sampled along said parameters t, u and v,
respectively, of said 3-D parametric polynomial volume element, said
integers n, m and 1 being determined so that a resulting set of voxels
lack cavities;
(b) defining first, second and third integer finite forward difference
matrices for said 3-D parametric polynomial voxel element, said first
finite forward difference matrix corresponding to said parameter t which
takes on integer values from o to n, said second finite forward difference
matrix corresponding to said parameter u which take on integer values from
o to m, and said third finite forward difference matrix corresponding to
said parameter v which takes on integer values from o to 1;
(c) determining an initial order finite forward difference tensor for said
3-D parametric polynomial volume element, on the basis of said first,
second and third order finite forward difference matrices, said geometric
basis matrix M, and said geometric control point tensor G;
(d) defining volume integer decision variables for said x, y and z
coordinate directions, first and second decision thresholds based on n, m
and 1, and a decision variable increment based on n, m, and 1;
(e) specifying an initial value for each said integer decision variable of
step (d); and
(f) converting said continuous 3-D parametric polynomial volume element
into said discrete set of voxels, said conversion being based on said
integer decision variables, said first and second decision thresholds,
said decision variable increment, and said first endpoint.
13. The method of claim 12, wherein step (f) comprises:
for each integer value v from o to 1, converting a v-th continuous 3-D
parametric surface patch by holding constant said parameter v and varying
parameter u from o to m and varying parameter t from o to n,
(i) forming an initial K.sup.th order finite forward difference matrix for
said v-th 3-D parametric polynomial surface patch, on the basis of said
tri-K.sup.th order finite forward difference tensor for said 3-D
parametric polynomial volume element,
(ii) defining surface integer decision variables for said x, y and z
coordinate directions, for said v-th 3-D parametric polynomial surface
patch,
(iii) specifying an initial value for each said surface decision variable,
(iv) converting said v-th 3-D parametric polynomial surface patch into a
discrete set of voxels,
(v) updating said finite forward difference tensor,
(vi) determining said integer coordinate values in said x, y and z
coordinate directions which are closest to said first end point of said
(u=o).sup.th 3-D parametric polynomial curve segment of (v+1).sup.st 3-D
parametric polynomial surface patch, said determination of said integer
coordinate values being determined on the basis of said volume integer
decision variables defined in step (d) and said first and second decision
thresholds.
14. The method of claim 13, wherein step (iv) further comprises: for each
integer value u from o to m,
(I) placing into said discrete 3-D voxel space, said voxel corresponding
with said endpoint of the u-th 3-D parametric polynomial curve segment of
v-th 3-D parametric polynomial surface patch,
(II) forming an initial K.sup.th order finite forward difference vector for
said u-th 3-D parametric polynomial curve segment of v-th 3-D parametric
polynomial surface patch, said formation being on the basis of said
K.sup.th order finite forward difference matrix for said v-th 3-D
parametric polynomial surface patch,
(III) defining curve integer decision variables for said x, y and z
coordinate directions for said u-th 3-D parametric polynomial curve
segment,
(IV) specifying an initial value for each of said u-th curve integer
decision variables,
(V) converting said u-th 3-D parametric polynomial curve segment into said
discrete set of voxels,
(VI) updating said finite forward difference matrix for the v-th 3-D
parametric polynomial surface patch, and
(VII) determining said integer coordinate values in said x, y and z
coordinate directions which are closest to said first endpoint of the
(u+1).sup.st 3-D parametric polynomial curve segment, said determination
of said integer coordinate values being determined on the basis of said
surface integer decision variables defined in step (ii) and said first and
second decision thresholds.
15. The method of claim 14, wherein step (V) comprises for each integer
value of parameter t from o to n,
(1) determining said integer coordinate values in the x, y and z coordinate
directions which are closest to a corresponding sample point of said u-th
3-D parametric polynomial curve segment, said determination of said
integer x, y and z coordinate values being determined on the basis of said
curve integer decision variables and said first and second decision
thresholds,
(2) updating said curve integer decision variables using said decision
variable increment,
(3) updating said finite forward difference vector for the u-th 3-D
parametric polynomial curve segment, formed in step (II),
(4) placing into said discrete 3-D voxel space, said voxel having said
integer x, y and z coordinate values determined in step (1), and
(5) repeating in a loop fashion, steps (1), (2), (3) and (4) for the
subsequent voxels of said discrete set of n voxels, until said integer
coordinate values for last voxel are determined. |
|
 |
|
 |
Claims |
|
|
|
Description |
|
|
BACKGROUND OF THE INVENTION
The present invention relates generally to methods of converting continuous
geometrical representations into discrete representations, and more
particularly relates to methods of converting three-dimensional continuous
geometrical representations into discrete three-dimensional voxel-based
representations within a three-dimensional voxel-based system.
SETTING FOR THE INVENTION
Three-dimensional (hereinafter "3-D") computer graphic systems based upon
voxel (i.e., volume element) representation of 3-D objects in a large 3-D
memory, are known and have been described, for example, in the following
publications:
"A 3-D Cellular Frame Buffer," Arie Kaufman and R. Bakalash, in Proc.
EUROGRAPHICS '85, Nice, France, September 1985, pp. 215-220;
"Memory Organization for a Cubic Frame Buffer," Arie Kaufman, in Proc.
EUROGRAPHICS '86. Lisbon, Portugal, August 1986, pp. 93-100;
"Towards a 3-D Graphics Workstation," Arie Kaufman, in Advances in Graphics
Hardware I, W. Strasser (Ed.), Springer-Verlag, 1987, pp. 17-26;
"Voxel-Based Architectures for Three-Dimensional Graphics," Arie Kaufman,
in Proc. IFIP '86, 10th World Computer Congress, Dublin, Ireland,
September 1986, pp. 361-366;
"CUBE - An Architecture Based on a 3-D Voxel Map," Arie Kaufman and R.
Bakalash, to appear in Theoretical Foundations of Computer Graphics and
CAD, R. A. Earnshaw (Ed.), Springer-Verlag, 1988, pp. 689-701;
"Parallel Processing for 3D Voxel-Based Graphics," Arie Kaufman and R.
Bakalash, to appear in Parallel Processing for Computer Vision and
Display, P. M. Dew, R. A. Earnshaw, and T. R. Heywood (Eds.),
Addison-Wesley, 1988;
"Memory and Processing Architecture for 3-D Voxel-Based Imagery," Arie
Kaufman and R. Bakalash, in IEEE Computer Graphics and Applications, 1988;
and
"The CUBE Three-Dimensional Workstation," Arie Kaufman, in Proc. NCGA '88:
Ninth Annual Conference and Exposition, Anaheim, Calif., March 1988, pp.
344-354.
As disclosed in the above publications and generally illustrated in FIGS. 1
and 2, the 3-D computer graphic workstation 1 is based upon 3-D
voxel-based representation of objects within a large 3-D memory 2 referred
to hereinafter as a 3-D Cubic Frame Buffer, which comprises specially
organized memory modules (not shown) containing a cellular array of unit
cubic cells called voxels. The workstation 1 is a multiprocessor system
with three processors accessing the Cubic Frame Buffer 2 to input,
manipulate, and view and render the 3-D voxel images.
In general, the processors include a 3-D Frame Buffer Processor 3, a 3-D
Geometry Processor 4, and a 3-D Viewing Processor 5. The 3-D Frame Buffer
Processor 3 acts as a channel for 3-D voxel-based images which have been
"scanned" using a 3-D scanner 6 such as CAT and MRI medical scanners. The
3-D scanned voxel-based images are the primary source of Cubic Frame
Buffer data. Once the voxel images are stored in the Cubic Frame Buffer 2,
they can be manipulated and transformed by the 3-D Frame Buffer Processor
3, which also acts as a monitor for 3-D interaction.
The 3-D Geometry Processor 4 samples and thereafter converts or maps 3-D
continuous geometric representations of a 3-D object, into their 3-D
discrete voxel representation within the Cubic Frame Buffer 2. Notably,
the 3-D continuous geometric representations comprise a set of
mathematical functions which as a whole serve as a 3-D model of the 3-D
object. Together, this sampling and conversion (i.e. mapping) process is
typically referred to as a "scan-conversion" process.
The 3-D Viewing Processor 5 examines the voxels in the Cubic Frame Buffer 2
in a specified view direction which can be one of a variety of directions.
By taking into consideration depth, translucency, and color values, the
3-D Viewing Processor 5 generates a 2-D shaded projection (i.e., video
pixel image) of the cubic frame voxel-based image, inputs the same into a
conventional 2-D frame buffer 7 which in turn is scanned by a conventional
video processor 8, thereby updating a video screen 9 with the 2-D shaded
pixel image.
Referring to FIG. 3, in particular, a general overview of 2-D and 3-D
scan-conversion processes is given in terms of (i) mapping from continuous
3-D geometric models to 2-D discrete pixel-image space, and (ii) mapping
from continuous 3-D geometric models to 3-D discrete voxel-image space,
respectively. In the above-described 3-D voxel-based graphics system, the
2-D scan-conversion process illustrated in FIG. 3 is not carried out, as
such prior art processes are strictly limited to 2-D image data-base
generation and 2-D pixel-image modelling, whereas in contrast, the 3-D
scan-conversion process provides robust 3-D image data-base generation and
3-D voxel-image modelling.
In order to obtain in real-time 2-D images projections of 3-D voxel images,
a special common bus referred to as a Voxel-Multiple-Write-Bus (not shown)
can be provided which simultaneously processes a full beam of voxels along
a specified viewing direction and selects the first opaque voxel along the
beam in a time which is proportional to the log of length of the beam of
voxels. Also, in order to assist the special common bus in real-time
viewing and to support real-time "3-D scan conversion" of continuous 3-D
geometrical models into 3-D discrete voxel images, and manipulation of 3-D
voxel-based images stored in the Cubic Frame Buffer, a special skewed 3-D
memory organization can be provided which enables parallel retrieval and
storage of whole beams of voxels. In addition to the unique memory
organization of the Cubic Frame Buffer, a special addressing mechanism can
be provided as well which works in connection with the special common bus
and the 3-D skewed memory organization. Each of the above-mentioned system
features are more fully described in the above-referenced publications.
The workstation described in the above publications provides a full range
of inherent 3-D interactive operations in a simple yet general workbench
set-up, since the workstation operates in both discrete 3-D voxel space
and 3-D geometry space, and provides ways in which to interact the two
spaces. Accordingly, the workstation can be used with inherent 3-D
interaction devices, techniques and electronic tools, which support direct
and natural interaction, generation, and editing of 3-D continuous
geometrical models, 3-D discrete voxel images, and their transformations.
Such a 3-D voxel-based graphics workstation is appropriate for many 3-D
applications such as medical imaging, 3-D computer-aided design, 3-D
animation and simulation (e.g. flight simulation), 3-D image processing
and pattern recognition, quantitative microscopy, and general 3-D graphics
interaction.
Thus, when using a 3-D voxel-based graphic system of the type described
above and elsewhere in the literature, there arises the need for
computationally efficient methods which convert 3-D continuous geometrical
models of objects into 3-D discrete voxel-based representations, which can
be, for example, stored in the 3-D Cubic Frame Buffer memory 2 of the
voxel-based graphic system 1. Such computational processes are often
referred to as methods of scan converting of 3-D objects, and are carried
out in the 3-D Geometry Processor of the workstation described above. Scan
conversion methods generate discrete voxel representations of 3-D objects,
and provide computationally efficient ways in which to write voxel
representations for such objects into the Cubic Frame Buffer of the
workstation.
Typically, there are two principal approaches to writing into the Cubic
Frame Buffer 2, 3-D discrete voxel representations of 3-D objects. In the
case where a person desires to model in a voxel-based graphic system a
real 3-D object (e.g. a teapot), 3-D digitizers (i.e. coordinate measuring
devices) such as the 3Space Isotrack Stylus device can be used to measure
and convert into the Cubic Frame Buffer, the coordinates of the real 3-D
object, i.e., teapot. While this method is appropriate, it is often
time-consuming and it ceases to be effective for large objects, e.g. an
airplane, or objects in the design stage which do not yet exist.
An alternate approach to modeling 3-D objects involves using mathematical
representations of various sorts to model the various elements of the
objects, and subsequently to convert such 3-D continuous mathematical
representations into 3-D discrete voxel representations which are to be
stored in the 3-D Cubic Frame Buffer of the workstation. The types of
mathematical representations presently available to model 3-D objects,
either real or synthetic, include: 3-D lines, polygons (optionally
filled), polyhedra (optionally filled), cubic parametric curves, bi-cubic
parametric surface patches, circles (optionally filled) and quadratic
objects (optionally filled) like those used in constructive solid
geometry, such as cylinders, cones and spheres. Notably, the advantage of
using 3-D continuous mathematical representations for modelling 3-D
objects is that the objects can be either real, or synthetic, i e., having
an existence only within the 3-D voxel-based computer graphics system
itself.
It is appropriate at this juncture to discuss in general the nature of the
3-D scan-conversion process, and also the construction of 3-D voxel-based
images of scan-converted 3-D continuous geometrical models of 3-D objects.
Referring to FIGS. 3 and 4 in particular, the scan-conversion process is
illustrated as a mapping of a 3-D, geometrically-represented object in a
continuous 3-D space, into a tesselated voxel-cellular model in discrete
3-D voxel-image space. Notably, most of the 3-D discrete topology terms
used herein are generalizations of those used in 2-D discrete typology.
Thus, referring to FIGS. 3 and 4, the continuous 3-D space
(R.times.R.times.R) is designated as "R.sup.3 space", while the discrete
3-D voxel-image space (Z.times.Z.times.Z), which is a 3-D array of grid
points is hereinafter referred to as "Z.sup.3 space". A voxel, or the
region contained by a 3-D discrete point (x, y, z) shall be termed the
continuous region (u, v, w) such that
x-0.5<u.ltoreq.x+0.5,
y-0.5<v.ltoreq.y+0.5, and
z-0.5<w.ltoreq.z+0.5.
This condition assumes that the voxel "occupies" a unit cube centered at
the grid point (x, y, z) and the array of voxels tesselates Z.sup.3.
Although there is a slight difference between a grid point and a voxel,
they will be used interchangeably hereinafter.
As a child has a degree of flexibility regarding how he or she is to stack
building blocks to construct a particular model of some object, the
computer graphic designer using a voxel-based system as discussed above,
similarly has a degree of flexibility in his or her voxel construction
techniques. Thus, as a child learns that certain stacking arrangements of
building blocks (for example, cubic building blocks) have structural and
connectivity advantages over alternative stacking arrangements, so too
does the computer graphics designer realize that certain voxel connections
or stacking arrangements may be preferred over others under particular
circumstances.
How contiguous or neighboring voxels are connected or arranged with respect
to one another, is a very important concept in voxel-representation in
general, and in 3-D scan-conversion processes, in particular. This concept
of how neighboring voxels are connected, is referred to as "connectivity"
and is important enough to merit further discussion hereinbelow.
Referring to FIGS. 5A through 5C and 6A through 6C, the three types of
possible voxel connections among neighboring voxels are illustrated. Much
like an apartment dweller has different types of neighbors situated in
front, in back, along his sides and below him, each voxel (x, y, z) in
discrete 3-D voxel-image space Z.sup.3 (in the Cubic Frame Buffer), can
have three kinds of neighbors as well. These three types of neighboring
voxels are defined below by the following definitions:
(1) A voxel can have 6 direct neighbors at positions: (x+1, y, z), (x-1, y,
z), (x, y+1, z), (x, y-1, z), (x, y, z+1), and (x, y, z-1).
(2) A voxel has 12 indirect neighbors at positions: (x+1, y+1, z), (x-1,
y+1, z), (x+1, y-1, z), (x-1, y-1, z), (x+1, y, z+1), (x-1, y, z+1), (x+1,
y, z-1), (x-1, y, z-1), (x, y+1, z+1), (x, y-1, z+1), (x, y+1, z-1), and
(x, y-1, z-1).
(3) A voxel has 8 remote neighbors at positions:
(x+1, y+1, z+1), (x+1, y+1, z-1), (x+1, y-1, z+1),
(x+1, y-1, z-1), (x-1, y+1, z+1), (x-1, y+1, z-1),
(x-1, y-1, z+1), and (x-1, y-1, z-1).
Alternatively, the three kinds of neighboring voxels defined above, can be
specified in terms whether a voxel shares a face, a side (i.e. edge) or a
corner with a neighboring voxel, as illustrated in FIGS. 5A, 5B, and 5C,
respectively.
In discrete 3-D voxel image space Z.sup.3, the 6 direct neighbors are
defined as 6-connected neighbors and are graphically illustrated in FIG.
6A. Both the 6 direct and 12 indirect neighbors are defined as
18-connected neighbors and are graphically illustrated in FIG. 6B. All
three kinds of neighbors are defined as 26-connected neighbors and are
illustrated in FIG. 6C.
Referring now to FIGS. 7A, 7B and 7C, in particular, the three principal
types of paths of connected voxels in Z.sup.3 space, are graphically
illustrated. In FIG. 7A, a 6-connected path is defined as a sequence of
voxels such that consecutive pairs are 6-neighbors. In FIG. 7B, an
18-connected path is defined as a sequence of 18-neighbor voxels, while as
shown in FIG. 7C, a 26-connected path is defined as a sequence of
26-neighbor voxels. From the above-defined and described voxel path
connections and arrangements, any type of discrete 3-D voxel-based model
can be constructed in Z.sup.3 space of the 3-D Cubic Frame Buffer 2. For
example, FIGS. 8A and 8B provide two views of a three-dimensional teapot
modelled in discrete 3-D voxel-image space Z.sup.3. The discrete 3-D
voxel-image is created by connecting cubic voxels according to
"26-connectivity" as described hereinabove. Notably, FIG. 8B provides a
2-D side cross-sectional view of the 3-D voxel representation of the
teapot shown in FIG. 8A, and illustrates the "26-connectivity" nature of
the 3-D voxel-based image of 8A. When closely examined, FIG. 8B
illustrates the face-to-face and side-to-side (i.e. edge-to-edge) and even
corner-to-corner connections of neighboring voxels.
In summary, "connectivity" relates to how unit voxels are connected
together to synthesize voxel-based image representations of continuous 3-D
geometrical models. Also, the type of connectivity employed specifies the
number of "options" that are available when stepping in the coordinate
directions of discrete 3-D voxel space during 3-D scan-conversion
processes.
Turning now to other 2-D geometrical objects of interest in R.sup.3 space,
namely parametric surfaces, polygons and hollowed polyhedra, another
elementary concept arises concerning the nature of the connectivity of the
resultant filled 3-D objects which are represented as a set of voxels with
a 3-D Cubic Frame Buffer, in particular. The concept is defined as
"tunnels" and concerns "thickness" of voxel-represented surface, and how
easily it is penetratable using, for example voxel-based beams or rays.
There are three principal types of tunnels which are defined below. A
6-connected tunnel is a patch of 6-connected transparent voxels through a
surface. Such tunnels are actual holes in the voxel-based surface.
Similarly, an 18-connected tunnel is defined as a path of 18-connected
transparent voxels through the voxel-based surface. Surfaces with tunnels
of this kind are "thicker" than those surfaces lacking 6-connected
tunnels. Even "thicker" voxel-based surfaces can be formed by avoiding
26-connected tunnels which are paths of 26-connected transparent voxels
through the surface.
In addition to connectivity requirements, 3-D scan-conversion processes are
also required to satisfy fidelity and efficiency requirements. All three
of these requirements are met by the 3-D scan-conversion methods of the
present invention disclosed hereinafter.
The basic fidelity requirements in scan-converting an object from R.sup.3
to Z.sup.3 space, are that:
(1) The discrete points from which the region contained by them is entirely
inside the continuous object, are in the scan-converted discrete object.
(2) The discrete points from which the region contained by them is entirely
outside the continuous object, are not in the scan-converted discrete
object.
Obviously, some discrete points will not belong to either of the above
cases and more guidelines are necessary. Those are:
(3) If the object is a curve (i.e. 1-D object), then the converted object
will need certain connectivity requirements. In this case, the converted
end point will be in the converted object.
(4) If the object is a surface (i.e. 2-D object), then it must meet certain
"lack of tunnels" connectivity requirements. In this case, the converted
curved "edges" will be converted object.
(5) If the object is volume (i.e. 3-D object), then its "inside" will be
converted according to requirement (1) above. Other points will be treated
by a majority decision, i.e. the discrete point is decided in the object
if more than half its region is in the continuous object.
For curves, 6-connectivity, 18-connectivity or 26-connectivity can be
selected, depending on implementation needs or modelling requirements.
Regarding connectivity for surfaces and volumes, the following conditions
are required. For surfaces, 6-connected tunnels, 18-connected tunnels or
26-connected tunnels are disallowed depending on implementation needs or
modelling requirements. For solid volumes, 6-connectivity is usually
required to avoid any internal cavities.
Having discussed the conventional terminology and basic requirements of
scan conversion methods, it is now appropriate to turn to and discuss 3-D
scan-conversion methods known in the prior art, and point out with
particularity their shortcomings and drawbacks.
Conventional 3-D scan-conversion methods for voxel-based graphics systems
are described in the paper "3D Scan-Conversion Algorithms for Voxel-Based
Graphics," by Arie Kaufman and Eyal Shimony, published on pp. 45-76, in
Proc. 1986 ACM Workshop on Interactive 3D Graphics, held in Chapel-Hill,
N.C., on October 1986. In this publication, several different types of
methods for scan-converting 3-D continuous geometric objects (i.e.,
representations), are described. The 3-D geometric objects discussed
therein include 3-D lines, polygons (optionally filled), polyhedra
(optionally filled), cubic parametric curves, bi-cubic parametric surface
patches, circles (optionally filled), and quadratic objects (optionally
filled) like those used in constructive solid geometry: cylinders, cones
and spheres.
In general, prior art scan-conversion methods disclosed in "3D
Scan-Conversion Algorithms for Voxel-Based Graphics", are (i) incremental
in nature, (ii) perform scan-conversion with computational complexity
which is in linear proportion to the number of voxels written into the
Cubic Frame Buffer, and (iii) use only additions, subtractions, tests and
simpler operations inside the inner computational process loops. In
general, all of the prior art methods are characterized by non-symmetric
computational processes within the inside loops, thereby requiring
stepping only along the designated coordinate direction and thus place
severe constraints on the type of connections and connectivity that can be
formed in any particular voxel-image arrangement. In addition, there are
numerous other shortcomings and drawbacks as to make such processes less
than desirable in many applications, as will be described below.
In the publication "3D Scan-Conversion Algorithms for Voxel-Based
Graphics," a method for scan-converting 3-D straight lines is disclosed.
This method converts 3-D line segments into a discrete set of voxels
having 26-connectivity in discrete 3-D voxel-image space, Z.sup.3. While
the method uses only integer arithmetic and only addition, substraction,
shifting and testing operations, the decision loop for x, y and z
coordinate directions is non-symmetric and thus only 26-connected lines in
3-D voxel space can be generated. Thus while the x, y and z coordinates
for each voxel can be computed incrementally, this non-symmetric method is
incapable of drawing 6- and 18-connected type lines in 3-D discrete
voxel-space space Z.sup.3.
The above-referenced paper "3D Scan-Conversion Algorithms for Voxel-Based
Graphics" discloses a method of scan-converting 3-D parametric polynomial
curves and surfaces into 26-connected curves and surfaces lacking
6-connected tunnels, respectively, in discrete 3-D voxel-image space
Z.sup.3. The method for scan-converting 3-D parametric polynomial curves
suffers from numerous shortcomings and drawbacks. In particular, the
method requires floating-point arithmetic, numerical rounding operations
in the computational loops, and is strictly a computational-based process
which is quite slow and computationally inefficient. Also, while this
scan-conversion method is incremental in nature, the computational loops
for the x, y and z coordinate directions are non-symmetric, and therefore
the method is capable of only generating 26-connected curves, and not 6-
and 18-connected type curves, in 3-D discrete voxel-space, Z.sup.3.
The prior art method for scan-converting 3-D parametric polynomial surfaces
suffers from significant shortcomings and drawbacks as well. In
particular, the method requires floating-point arithmetic, numerical
rounding operations, and is a strictly computational-based process, which
is quite slow and computationally inefficient. Also, while being
incremental, the method's non-symmetrical nature limits the method to
drawing only voxel-based surfaces lacking only 6-connected tunnels in 3-D
discrete voxel-image space, Z.sup.3.
In view, therefore, of prior art scan-conversion methodologies, there is a
great need for scan-conversion methods which avoid the use of
floating-point arithmetic, numerical rounding or truncation operations,
and "brute-force" type computational processes for determining the voxel
coordinates in the x, y and z directions. In addition to scan-conversion
methods which are fast, computationally efficient, and lend themselves to
simplified hardware and software implementation, there is also a great
need for 3-D scan-conversion methods which generate voxel-based
representations with a wide variety of voxel connectivities.
Accordingly, it is a principal object of the present invention to provide a
method of converting continuous 3-D geometrical representations, into
discrete 3-D voxel-based representations in discrete 3-D voxel-image
space. In particular, the method is most suitable for use with a 3-D Cubic
Frame Buffer memory of a 3-D voxel-based graphics system. However, the
method can be used in numerous other environments and applications
including beam-casting, ray-tracing, flooding, Z-buffer processes in
pixel-image space, and other operations known in the art.
It is a further object to provide a method of converting 3-D continuous
geometrical representations into discrete 3-D voxel-based representations,
wherein the method has decisional process loops of a symmetric nature
which determine the x, y and z coordinates of voxels using very simple
comparisons, updat | | |
