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

• US 4,987,554 A
• Filed: 08/24/1988
• Issued: 01/22/1991
• Est. Priority Date: 08/24/1988
• Status: Expired due to Term

• 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): Shaw, Dale M.
• Assistant Examiner(s): HERNDON, HEATHER R
• Application Number:
  US07/235,982
• Time in Patent Office: 881 Days
• Field of Search: 364/518, 364/522, 364/521, 364/413.13, 364/413.15, 364/413.16, 364/413.18, 364/413.19, 364/413.22, 364/474.36, 340/727, 340/747
• US Class Current: 345/424
• CPC Class Codes: G06T 17/00 Three dimensional [3D] modelling, e.g. data description of 3D objects

Abstract

A method of converting continuous 3-D (three dimension) geometrical representations of polygonal objects 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 polygon into a discrete set of voxels connected together in discrete 3-D voxel space. In this embodiment, voxel-based polygons having a wide variety of connectivities are generated. In another embodiment, a method is provided for converting a continuous 3-D polyhedron into a discrete set of voxels connected together in discrete 3-D voxel space. The method is incremental in nature and uses all integer arithmetic. The method is also characterized by decisional process loops, rather than brute-force type computational loops characteristic of prior art methodologies.

Claims

1. A method of converting a continuous 3-D geometrical representation of a 3-D polygon into a discrete set of connected voxels representing said 3-D polygon in 3-D discrete voxel space of a voxel-based system, each said voxel being specified by integer x, y and z coordinate values said 3-D polygon being defined by an edge list representing a closed sequence of edges, said edge list including edges being a 3-D straight line segment defined by first and second endpoints forming the vertices of said 3-D polygon, said vertices of said 3-D polygon specifying a plane equation of said 3-D polygon, said 3-D discrete voxel space being characterized by orthogonal x, y, and z coordinate directions, said method comprising the sequence of steps of:

(a) specifying a generalized coordinate system having orthogonal coordinate directions u, v and w, which form three principal planes u-v, u-2, and v-w, said 3-D discrete voxel space being characterized by said u, v and w coordinate directions, each said voxel being specified by integer u, v and w coordinate values, said u, v and w coordinate directions corresponding to said x, y and z coordinate directions in such a way that said polygon has a projection of greatest area on said u-v plane and has a coordinate direction extent of smallest value along said w coordinate direction, said approximate plane equation being specified by plane equation coefficient α

, β and

Γ

of said generalized coordinate directions u, v and w, respectively, and said coordinate direction w being defined as the depth direction of said polygon in said generalized coordinate direction;

(b) determining from said vertices, the minimum and maximum values of said u, v and w coordinate directions;

(c) defining an integer decision variable for said w coordinate direction, first and second integer decision threshold, integer decision variable increments and integer depth increments along each of said u and v coordinate directions, said definitions of said integer variables, decision thresholds, decision variable increments and depth increments being based on said α

, β and

Γ

plane equation coefficients;

(d) determining the initial value for said coordinate direction value w for said vertex having said minimum value for said v coordinate direction;

(e) for each said edge in said edge list, determining

(i) the slope of said edge in said u-v plane based on said first and second end points of said edge, and

(ii) the depth increment along said edge based upon said u-v slope determined in substep (i) and said integer depth increment along said u-coordinate direction;

(f) ordering said edge list by ascending value of said v coordinate direction of said first endpoint; and

(g) converting said continuous 3-D polygon into said discrete set of voxels by stepping along said coordinate directions u and v and using decisional logic process for determining the integer value of said coordinate direction w, said conversion employing said edge list, said slopes of said edges in said u-v plane, said depth increment along said edges, said integer decision variable, said first and second integer decision thresholds, and said integer depth increments along each of said u and v coordinate directions.

2. The method of claim 1, wherein step (g) comprises, for each integer value of v between said minimum and maximum values thereof which specify a v-th scan line parallel to said generalized coordinate direction u, performing in a loop fashion, the following sequence of steps:

(i) determining the coordinate values of said u coordinate direction corresponding to the endpoints of voxel runs along said v-th scan line which are contained within said polygon; and

(ii) determining for each voxel in said voxel run, the integer value of said coordinate direction w.

3. The method of claim 2, wherein step (i) comprises

(1) forming an active edge list from said edge list, said active edge list being a subset of said edge list in which said edges intersect with said v-th scan line and said active edge list being ordered by ascending said coordinate direction value u, said edge list having a first and last edge,

(2) for each said edge in said edge list, stepping along said edge according to said slope of said edge determined in step (d)(i),

(3) reordering said active edge list,

(4) for each edge in said edge list, in which the v-th coordinate of said first endpoint equals said coordinate value v, inserting said edge into said active edge list so as to preserve the order of said edges in said active edge list, and

(5) for each edge in said active edge list in which the v-th coordinate of said second endpoint equals said coordinate value v,

deleting said edge from said active edge list.

4. The method of claim 2, wherein step (ii) comprises

(1) setting an initial value for said integer coordinate direction value w on said first edge of said active edge list,

(2) for each coordinate direction value u in the range between said u coordinate values of said first and last edges in said active edge list,

(I) placing a voxel in said discrete 3-D voxel space at aid coordinate values, u, v and w if said coordinate direction value u is determined to be inside said polygon,

(110 for each voxel in said range, determining said integer coordinate value in said w coordinate direction, said determination of said integer coordinate value w being determined employing said integer decision variable, first and second integer decision thresholds and said integer depth increments, and

(III) updating said integer decision variable using said integer decision variable increments, and

(3) updating said initial value for said coordinate direction value w on said first edge of said active edge list, said updating employing said integer depth increment along said coordinate direction v, and said depth increment along said first edge.

5. The method of claim 2, wherein step (ii) comprises

(1) defining a deferment logic variable,

(2) setting an initial value for said integer coordinate direction value w on said first edge of said active edge list, said setting employing said deferment logic variable,

(3) for each coordinate direction value u in the range between said u-th coordinate values of said first and last edges in said active edge list,

(I) for each voxel in said range, determining said integer coordinate value in said w coordinate direction, said determination of said integer coordinate value w employing said integer decision variable, first and second integer decision thresholds and said integer depth increments,

(II) placing voxels in said discrete 3-D voxel space at said coordinate values if said coordinate direction value u is determined to be inside said polygon, and

(III) updating said integer decision valuable using said integer decision variable increments,

(4) updating said initial values for said coordinate direction value w on said first and last edges of said active edge list, said updating employing said integer depth increment along said coordinate direction v, said depth increment along said first and last edges, and said deferment logic variable, and

(5) determining the value of said deferment logic variable ion the basis of the amount of change in said initial values in step (4).

6. The method of claim 5, wherein step (3)(II) comprises

placing a pair of voxels in said discrete 3-D voxel space at coordinate values

7. The method of claim 5, wherein step (3)(II) comprises

placing a pair of voxels in said discrete 3-D voxel space at coordinate values

8. The method of claim 5, wherein step (3)(II) comprises

placing a triplet of voxels in said discrete 3-D voxel space at coordinate values

9. The method of claim 1, wherein said method further comprises before step (g), for each said edge in said edge list,

(1) defining an integer initial depth decision variable, integer initial depth thresholds, integer initial depth decision variable increments, and integer initial depth increments,

(2) determining said integer initial depth thresholds, said integer initial depth decision variable increments, and said integer initial depth increments, said determination employing said integer depth increments and said first and second endpoints of said edge,

(3) for each integer value of v between said first and last values thereof which specify a v-th scan line parallel to said generalized coordinate direction u, performing in a loop fashion, the following sequence of steps,

(i) determining the coordinate values of said u coordinate direction, corresponding to the endpoints of voxel runs along said v-th scan line which are contained within said polygon, and

(ii) for each coordinate direction value u in the range between said u coordinate values of said first and last edges in said active edge list, determining the integer value of said coordinate direction w, for each voxel in said range,

(4) determining said integer initial value for said coordinate direction value w on said first edge of said active edge list, said determination employing said integer initial depth decision variable, said integer initial depth threshold, and said integer initial depth increments, and

(5) updating said integer initial depth decision variable, using said integer initial depth decision variable increments.

10. The voxel-based representation formed by the method of claim 1.

11. The method of claim 1, wherein step (e) further comprises

defining an integer edge decision variable for said edge in said edge list, integer edge decision thresholds, integer u increments for said edge in said edge list, and integer edge decision variable increments, and

determining the values of said integer edge decision thresholds, said integer u increments and said integer edge decision variable increments, said determination using first and second end points of said edge, and wherein step (g) comprises

for each integer value of v between said first and last values thereof which specify a v-th scan line parallel to said generalized coordinate direction u, performing in a loop fashion, the following sequence of steps,

(i) determining the coordinate values of said u coordinate direction, corresponding to the endpoints of voxel runs along said v-th scan line which are contained within said polygon, said determination being carried out by performing the following steps,

(1) forming an active edge list from said edge list, said active edge list being a subset of said edge list in which said edges intersect with said v-th scan line and said active edge list being ordered by ascending said coordinate direction value u, said edge list having a first and last edge,

(2) for each said edge in said edge list, determining the integer value in said coordinate direction u along said edge, said determination being based upon said integer edge decision variable, said integer edge decision threshold, and said integer u increments, and updating said integer edge decision variable using said integer edge decision variable increments,

(3) reordering said active edge list,

(4) for each edge in said edge list, in which the v-th coordinate of said first endpoint equals said coordinate value v, inserting said edge into said active end list so as to preserve the order of said edges in said active edge list, and

(5) for each edge in said edge list in which the v-th coordinate of said second endpoint equals said coordinate value v, deleting said edge from said active edge list;

and

(ii) determining for each voxel in said voxel run, the integer value of said coordinate direction w.

12. The method of claim 1, wherein said polygonal object comprises a plurality of connected 3-D polygons;

and

said method further comprises

performing steps (a) and (b) for each said 3-D polygon so as to generate a 3-D voxel based representation for said plurality of connected 3-D polygons.

13. The method of claim 12, wherein said method further comprises before performing steps (a) and (b), for each said 3-D polygon,

defining a generalized coordinate system in which said polygon is represented in substantially the same form for any orientation of said polygon in said continuous 3-D geometric space.

14. The method of claim 13, where, in said definition step, said generalized coordinate system is expressed in terms of orthogonal coordinate directions u, v, and w which form three principal planes u-v, u-w, and v-w,

where said polygon has a projection of greatest area on said u-v plane and has a coordinate direction extent of smallest value along said w coordinate direction.