Method of converting continuous three-dimensional geometrical representations into discrete three-dimensional voxel-based representations within a three-dimensional voxel-based system

• US 5,038,302 A
• Filed: 07/26/1988
• Issued: 08/06/1991
• Est. Priority Date: 07/26/1988
• Status: Expired due to Fees

• Current Assignee: The Research Foundation for The State University of New York (State University of New York)
• Original Assignee: The Research Foundation for The State University of New York (State University of New York)
• Inventors: Kaufman, Arie E.
• Primary Examiner(s): Markcom, Gary V.
• Assistant Examiner(s): Nguyen, Phu K.
• Application Number:
  US07/224,545
• Time in Patent Office: 1,106 Days
• Field of Search: 364/518, 364/521, 364/522, 364/512, 340/750, 340/799, 340/747, 340/728, 340/729
• US Class Current: 345/424
• CPC Class Codes: G06T 17/005 Tree description, e.g. octree, quadtree

Abstract

Method of converting continuous 3-D geometrical representations into a discrete set of voxels in discrete 3-D voxel space. In one embodiment, a method is provided for converting a continuous 3-D straight line segment into a discrete set of voxels connected together in discrete 3-D voxel space. In another embodiment, a method is provided for converting a continuous 3-D parametric polynomial curve segment into a discrete set of voxels connected together in discrete 3-D voxel space. In an alternative embodiment, a method is provided for converting a continuous 3-D parametric polynomial surface patch into a discrete set of voxels connected together in discrete 3-D voxel space. Yet in another embodiment of the present invention, a method is provided for converting a continuous 3-D parametric polynomial volume element into a discrete set of voxels connected together in discrete 3-D voxel space. The method of the present invention is incremental in nature and uses all integer arithmetic. The method of the present invention is also characterized by symmetrical decisional process loops using substantially the same decisional process logic in each of the x, y and z coordinate directions, and thus is capable of generating discrete sets of voxels having a variety of connectivities.

Claims

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₁ and P₂ 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₁ 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^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^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^th order finite forward difference vector for said 3-D parametric polynomial curve segment, on the basis of said K^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^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^th order integer finite forward difference matrices for said 3-D parametric polynomial surface patch, said first bi-K^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^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^th order finite forward difference matrix for said 3-D parametric polynomial surface patch, on the basis of said first and second bi-K^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^th order finite forward difference vector for said u-th 3-D parametric polynomial curve segment on the basis of said initial bi-K^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)^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^th order finite forward difference matrix for said v-th 3-D parametric polynomial surface patch, on the basis of said tri-K^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)^th 3-D parametric polynomial curve segment of (v+1)^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^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^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)^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.