Home
Patent Search
IMT Blog
REGISTER
|
SIGN IN
United States Patent
5506785
Blank , ; et al.
April 9, 1996
Title
Method and apparatus for generating hollow and non-hollow solid representations of volumetric data
Abstract
The invention is directed toward a method and apparatus for generating hollow and non-hollow solid representations of an object represented in terms of volumetric data. The volumetric data represents the object in terms of a plurality of voxels, each voxel having a plurality of voxel faces that interconnect to enclose a voxel volume that represents a portion of the object volume or a portion of the volume of a background substance. A surface representation is generated that represents the object with a plurality of surface voxel faces defining a surface that encloses the voxels whose volumes represent the object volume. An array of control points is formed from the surface representation, each control point corresponding to a surface voxel face. A NURB based solid representation of the object is generated from the array of control points. The NURB based solid representation can be used to drive a CAD/CAM system to generate a replica of the object or can be used for various other purposes.
Inventors:
Blank; William C.
(Lebanon,
NH
)
, Jacobson; Rodney D.
(Lebanon,
NH
)
Assignee:
Dover Systems Corporation
(Lebanon,
NH
)
Appl. No.:
016705
Filed:
February 11, 1993
Current U.S. Class:
700/98
345/419
345/424
Current International Class:
G06T 17/30 (20060101)
Field of Search:
364/468,578,474.24 395/89,93-95,119-123,124,127 340/723,728,747
U.S. Patent Documents
4436684
March 1984
White
4782502
November 1988
Schulz
4841975
June 1989
Woolson
4888583
December 1989
Ligocki et al.
4961154
October 1990
Pomerantz et al.
5007936
April 1991
Woolson
5038302
August 1991
Kaufman
5086401
February 1992
Glassman et al.
5101475
March 1992
Kaufman et al.
5113490
May 1992
Winget
Other References
Fuchs, H., Kedem, Z. M. and Uselton, S. P., "Optimal Surface Reconstruction From Planar Contours", Communications of the ACM, Oct. 1977, vol. 20, No. 10, pp. 693-702. .
Glenn, Jr., William V. et al., "Multiplanar Display Computerized Body Tomogrpahy applications in the Lumbar Spine", Spein, vol. 4, No. 4, Jul./Aug. 1979. .
Wells, Michael K., "1979 Advances in Bioengineering", The Winter Annual Meeting of the American Society of Mechanical Engineers, pp. 87-89. .
Altschuler, Bruce R. and Herman, Gabor T., "Head and Neck 3-D Mapping Derived From Computed Tomographic Serial Scans", pp. 81-85, Proceedings, Sixth Conference on Computer Applications in Radiology computer/aided analysis of radiological images, Jun. 18-21, 1979. .
Alberti, C., "Three-Dimensional CT and Structure Models", British Journal of Radiology, v. 53 (1980), pp. 261-262. .
Artzy, E., et al., "Boundary Detection in 3-Dimensions with . . . ", Medical Image Processing Group, Technical Report No. MIPG9, State University of New York at Buffalo, Nov., 1978. .
Artzy, E., et al., "A System For Three-Dimensional Dynamic Display of Organs From Computed Tomograms", 1979 IEEE, pp. 285-290. .
Artzy, Ehud, "Display of Three-Dimensional Information In . . .", Computer Graphics and Image Processing 9, 196-198 (1979). .
"Department of Defense Tri-Service Precision Machine-Tool Program", Quarterly Report, Feb.-Apr. 1978, Jun. 1, 1978. .
Douglas S. S., Green, W. L., "A Machine tool Control System for Turning Nonaxisymmetric Surfaces", Distribution Category UC-38, Sep. 28, 1979. .
Gerngross, H., et al., "Moglichkeiten Geometrischer Rontgenuntersuchung des Beckens fur den Halbseitigen Beckenersatz", Z. Orthrop. 118 (1980) 331-336 (An English language translation is also enclosed, entitled Possibilities of Geometric X-Ray Examination of Pelvis for Replacing Half of the Pelvis by an Artificial Pelvis. .
Herman, Gabor T., et al., "Three-Dimensional Display of . . . ", Computer Graphics and Image Processing 9, 1-21 (1979). .
Herman, Gabor T., "Representation of 3-D Surfaces by a Large . . . ", Medical Image Processing Group, Technical Report No. MIPG26, State University of New York at Buffalo, Mar., 1979. .
Mazziotta, John C. et al., "Thread (Three-dimensional Reconstruction And Display) With Biomedical . . . ", Georgetown University Medical Center, National Computer Conference, 1976, pp. 241-250. .
McLain, D. H., "Interpolations Methods For Erroneous Data", pp. 86-103. .
McShan, D. L. et al, "A Computerized Three Dimensional Treatment Planning System . . . ", British Journal of Radiology, vol. 52, pp. 478-481, 1979. .
Real, B., "Technical Change and Economic Policy", Science and Technology in the New Economic and Social Context. .
Reinstein, L. E., et al, "A Computer-Assisted Three-Dimensional", Scientce Accessories, Storrs, Conn., Apr. 1978, pp.259-264. .
Sommer III, H. J., et al., "Regressive Osteometric Scaling . . . ", Department of Mechanical and Industrial Engineering, pp. 87-89. .
Sunguroff, A., et al., "Computer Generated Images for Medical Applications", Computer Graphics, vol. 12, No. 3, 196-202, Aug. 1978. .
Sutton, G. P., et al., "Precision Machine-Tool Program", Quarterly Report, May-Jul. 1978, Sep. 6, 1978. .
Tatcher, M., et al., "An Analog Patient Model Derived From Computed Tomograms for Three-Dimensional . . . ", Technical Notes, (Jul. 1980), pp. 236-238. .
Burri, L. et al, Total "Internal" Hemipelvectomy, 1979, Archives of Orthopaedic and Traumatic Surgery, 219-226. .
Glen, W. V., et al, Multiplanar Display . . . In The Lumbar Spine, Jul./Aug. 1979, SPIE, vol. 4, No. 4, 282-352. .
Glenn, Jr., W. V. et al, Image Generation . . . for CT Scan Data, 1975, Memorial Award Paper, 403-416. .
Herman, G. T. et al, Display of . . . Computed Tomography, 1977, Journal of Computer Assisted Tomography, 155-160. .
Hierholzer, E., The Display-Stereocomparator . . . , 1978, SPIE, vol. 166, 31-38. .
Hoffman, E. A. et al, Investigation of the Intrathoracic . . . , Biodynamics Research Unit, Mayo Medical School, (no date) 151-161. .
Huang, H. K. et al, Automated Cross-Sectional Geometry . . . , 21-25 Oct., 1978, 31st ACEMB (Atlanta Georgia), 208-209. .
Liu, H. K., Two-And Three-Dimensional Boundary Detection, 1977, Computer Graphics and Image Processing 6, 123-134. .
Nerubay, J. et al, Technique of Building . . . Using Computer Tomography, 1982, Alan R. Liss, Inc., N.Y.C., 147-152. .
Rhodes, M. L. et al, Anatomic Model and Prostheses Manufacturing Using CT Images, 1985, MPDI Medical Science Center, 110-150. .
Rhodes, M. L. et al, Computer Aided Prosthetic Implant . . . , 1982, IEEE, 585-588. .
Rhodes, M. L. et al, Three Dimensional Structure Isolation . . . , 1978, IEEE 78 CH 1331-8C, 584-591. .
Tonner, H. D. et al, Ein Neues Verfahren Zur . . . Den Beckenteilersatz, 1979, Fortschr. Med. 97, Nr. 16, 781-783. .
Udupa, Jayaram K., Ph.D., Herman, Gabor T., Ph.D., 3D Imaging in Medicine, 1991, CRC Press, Inc., 69-88. .
Wells, M. K., Ed., Regressive Osteometric Scaling Applications To Mirror Symmetry . . . , 1979, Amer. Society of Mech. Engr., 87-89..~
Primary Examiner:
Envall, Jr.; Roy N.
Assistant Examiner:
Brown; Thomas E.
Attorney, Agent or Firm:
Wolf, Greenfield & Sacks
Claims
What we claim is:
1. A method for operating a computer to generate a data structure representing a NURB based solid model of an object represented in terms of surface data, the computer having a memory and the surface data being stored in the memory, the object having a surface, the surface data representing the object surface in terms of a plurality of surface elements, each surface element representing a portion of the object surface and having coordinates indicating the relative three-dimensional location of the portion of the object surface that it represents, the method including the steps of:
generating first and second poles for the surface data representation of the object, each pole including at least one surface element, each pole representing a portion of the object surface;
storing the first and second poles in the memory;
generating a plurality of v-lines between the first and second poles, each v-line including a plurality of surface elements that represent a path between the respective portions of the object surface represented by the first and second poles;
storing each v-line in the memory;
generating a plurality of u-lines, each u-line including a plurality of surface elements that represent a path around the object surface, each u-line intersecting with each of the v-lines;
storing each u-line in the memory;
generating a list of intersection surface elements that represent portions of the object surface where v-lines intersect with u-lines, the intersection surface elements being surface elements that are included within the plurality of surface elements of both a u-line and a v-line;
storing the list of intersection surface elements in the memory;
generating an array of control points, each control point corresponding to an intersection surface element, each control point including the coordinates indicating the portion of the object represented by its corresponding intersection surface element;
storing the array of control points in the memory; and
generating a data structure representing a NURB based solid model of the object from the array of control points.
2. An apparatus for generating a data structure representing a NURB based solid model of an object, the object having a surface and a volume enclosed by the surface, the apparatus comprising:
a source for generating a volumetric data representation of the object, the volumetric data including a plurality of voxels, each voxel having a plurality of voxel faces that interconnect to enclose a voxel volume, each voxel volume representing a corresponding portion of the object volume or a portion of a volume of a background substance, each voxel having coordinates indicating the relative three-dimensional position of the portion of the object volume or background substance volume that it represents;
means for generating a surface model of the object from the volumetric data, the surface model including a plurality of surface elements that define a surface enclosing the voxels whose volumes represent the object volume, each surface element corresponding to at least one voxel;
means for generating first and second poles for the surface model, each pole including at least one surface element and representing a portion of the object surface;
means for generating a plurality of v-lines between the first and second poles, each v-line including a plurality of surface elements that represent a path between the respective portions of the object surface represented by the first and second poles;
means for generating a plurality of u-lines, each u-line including a plurality of surface elements that represent a path around the object surface, each u-line intersecting with each of the v-lines;
means for generating a list of intersection elements that represent portions of the object surface where v-lines intersect with u-lines, the intersection elements being surface elements that are included within the plurality of surface elements of both a u-line and a v-line;
means for generating an array of control points, each control point corresponding to an intersection element and including the coordinates of the at least one voxel corresponding to the intersection element; and
means for generating a data structure representing a NURB based solid model of the object based upon the array of control points.
3. An apparatus for generating a replica of an object represented in terms of volumetric data as claimed in claim 2 wherein each voxel face has coordinates indicating its orientation on its corresponding voxel and the relative three-dimensional position of the portion of the object volume or background substance volume that its corresponding voxel represents, and wherein the means for generating a surface model of the object from the volumetric data generates the surface model from a plurality of surface voxel faces such that each surface element is a surface voxel face.
4. A method for operating a computer to generate a NURB based solid representation of an object represented in terms of volumetric data, the computer having a memory and the volumetric data being stored in the memory, the object having a surface and a volume enclosed by the surface, the volumetric data representing the object and a background substance with a plurality of slices, each slice being represented by an array of voxels, each voxel having a plurality of voxel faces that interconnect to enclose a voxel volume, each voxel volume representing a corresponding portion of the object or background substance volume, each voxel face having coordinates indicating its orientation on its corresponding voxel and the relative three-dimensional position of the portion of the object volume or background substance volume that its corresponding voxel represents, the method including the steps of:
generating at least one contour for each slice that includes a voxel volume representing the object volume, each contour indicating a group of surface voxels on the slice, each surface voxel having a volume that represents the object and being adjacent to a voxel on the same slice whose volume does not represent the object;
storing each contour in the memory;
generating a surface representation for each slice for which a contour was generated, each surface representation including a plurality of surface voxel faces, each surface voxel face being a face of a surface voxel, each surface voxel face further being adjacent to a voxel whose volume does not represent the object;
storing each slice's surface representation in the memory;
combining the surface representations for each slice to generate a surface representation of the object;
storing the surface representation of the object in the memory;
generating first and second poles for the surface representation of the object, each pole including at least one surface voxel face, each pole representing a portion of the object surface;
storing the first and second poles in the memory;
generating a plurality of v-lines between the first and second poles, each v-line including a plurality of surface voxel faces that represent a path between the respective portions of the object surface represented by the first and second poles;
storing each v-line in the memory;
generating a plurality of u-lines, each u-line including a plurality of surface voxel faces that represent a path around the object surface, each u-line intersecting with each of the v-lines;
storing each u-line in the memory;
generating a list of intersection faces that represent portions of the object surface where v-lines intersect with u-lines, the intersection faces being surface voxel faces that are included within the plurality of surface voxel faces of both a u-line and a v-line;
storing the list of intersection faces in the memory;
generating an array of control points, each control point corresponding to an intersection face, each control point including the coordinates indicating the portion of the object represented by its corresponding intersection face;
storing the array of control points in the memory; and
generating a data structure representing a NURB based solid model of the object from the array of control points.
Description
FIELD OF THE INVENTION
This invention relates to a method for generating solid representations of hollow and non-hollow objects from volumetric data representing the object, such volumetric data being supplied by a probing source such as a computerized axial tomography (CAT) scanner. The solid representations can be used in a number of ways, such as for controlling a computer aided design/manufacturing (CAD/CAM) system to generate physical models of the solids.
BACKGROUND OF THE INVENTION
A number of apparatus are known for producing volumetric data representations of an object. An example of such an apparatus is a CAT scanner which generates representations of an object by subjecting the object to radiant energy (specifically X-rays) across a cross-sectional slice of the object and by detecting the radiant energy transmitted through that slice of the object. The detected radiant energy varies depending upon the characteristics of the substances that make up the object in the area of the slice. Therefore, by analyzing the detected radiant energy, a two-dimensional array of sampled radiographic densities is formed. This two-dimensional array can be displayed as an image of the object at the cross-sectional slice. A three-dimensional sample of the entire object can be constructed by combining multiple slices generated successively across the entire length of the object. In this manner, the object is represented by a three-dimensional array of data indicating the characteristics of the substances that make up the volume of the object.
Although the volumetric representation of an object is useful for many applications, it cannot interface directly with many computer aided design (CAD) or CAM systems. Most modern CAD/CAM systems receive input data in the form of geometric primitives, such as points, lines, arcs, b-spline (NURB) curves, planes, conics and b-spline (NURB) surfaces. Since the volumetric representations generated by a CAT scanner and other similar apparatus do not define the scanned object in terms of geometric primitives, these apparatus cannot interface directly with many modern CAD/CAM systems.
It is desirable to develop a method and apparatus for converting a volumetric data representation of an object into a collection of geometric primitives that constitute a single solid model representation which is more useful for certain applications, including interfacing with CAD/CAM systems. Two techniques have been developed for converting a volumetric data representation of an object into a solid model of the object. First, a method known as the polygonal method has been developed which attempts to model an object defined in volumetric data by a series of polygons, such as triangles. Initially, a series of polygons is formed that encloses the object volume. Thereafter, the method determines the area where the greatest difference exists between the polygon model and the object volume, and the polygon covering that area is sub-divided into smaller polygons. In this manner, the polygon model is continually sub-divided into greater numbers of polygons and the accuracy of the polygon model increases with each sub-division. This method is often used in graphics applications and generates an accurate representation when a close examination is conducted for small portions of the object surface. However, the polygon model generated from this method consists of a series of discrete entities and does not have any topological understanding. The model generated by the polygonal method is not a single contiguous solid model and therefore, it cannot be used for many applications such as interfacing with certain CAD/CAM systems.
A second method for modeling volumetric data is known as the contour or perimeter method. This method looks at each slice of volumetric data individually and models the shape of the object as defined on each slice. Thereafter, the model for each of the slices is combined together to form a model of the entire object. Since each slice is modeled individually, this method also results in a model having a plurality of discrete components. Therefore, this model does not generate a single contiguous solid model of the object and cannot be utilized effectively for certain applications. Additionally, this method cannot model multiple contours defined on any one slice.
Accordingly it is an object of the present invention to provide a method and apparatus for generating a NURB based solid model representation of an object represented in terms of volumetric data that can be used to drive a CAD/CAM system or for various other uses.
SUMMARY OF THE INVENTION
The foregoing objects are achieved and the foregoing problems are solved in one illustrative embodiment of the invention in which a method is provided for operating a computer to generate a surface representation of an object represented in terms of volumetric data, the computer having a memory and the volumetric data being stored in the memory, the object having a surface and a volume enclosed by the surface. The volumetric data represents the object and a background substance with a plurality of slices, each slice being represented by an array of voxels, each voxel having a plurality of voxel faces that interconnect to enclose a voxel volume, each voxel volume representing a corresponding portion of the object or background substance volume. In accordance with the invention, a method is provided for operating the computer to perform the steps of generating at least one contour for each slice that includes a voxel volume representing the object volume, each contour indicating a group of surface voxels on the slice, each surface voxel having a volume that represents the object and being adjacent to a voxel on the same slice whose volume does not represent the object; storing each contour in the memory; generating a surface representation for each slice for which a contour was generated, each surface representation including a plurality of surface voxel faces, each surface voxel face being a face of a surface voxel, each surface voxel face further being adjacent to a voxel whose volume does not represent the object; storing each slice's surface representation in the memory; and combining the surface representations for each slice to generate a surface representation of the object.
In another illustrative embodiment of the invention, a method is provided for operating a computer to generate a data structure representing a NURB solid model of an object represented in terms of surface data, the computer having a memory and the surface data being stored in the memory, the object having a surface. The surface data represents the object surface in terms of a plurality of faces, each face representing a portion of the object surface and having coordinates indicating the relative three-dimensional location of the portion of the object surface that it represents. In accordance with the invention, a method is provided for operating the computer to perform the steps of generating first and second poles for the surface data representation of the object, each pole including at least one face, each pole representing a portion of the object surface; storing the first and second poles in the memory; generating a plurality of v-lines between the first and second poles, each v-line including a plurality of faces that represent a path between the respective portions of the object surface represented by the first and second poles; storing each v-line in the memory; generating a plurality of u-lines, each u-line including a plurality of faces that represent a path around the object surface, the at least one u-line intersecting with each of the v-lines; storing each u-line in the memory; generating a list of intersection faces that represent portions of the object surface where v-lines intersect with u-lines, the intersection faces being faces that are included within the plurality of faces of both a u-line and a v-line; storing the list of intersection faces in the memory; generating an array of control points, each control point corresponding to an intersection face, each control point including the coordinates indicating the portion of the object represented by its corresponding intersection faced storing the array of control points in the memory; and generating a data structure representing a NURB solid model of the object from the array of control points.
In a further illustrative embodiment of the invention, a method is provided for combining the two above-described methods and for utilizing the data structure generated by the combined methods to manufacture an article having a surface topology that is substantially identical to the NURB solid model represented by the data structure, and to the volumetric representation of the object. As a result, a replica is generated of an object represented in terms of volumetric data.
In a further illustrative embodiment of the invention, a method is provided for generating a replica of a skeletal portion of a bone that is represented in terms of volumetric data output from a CAT scan or other volumetric data generation source. The replica of the skeletal portion can be used to generate a prosthetic.
A BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 is a perspective view of a portion of data output by a means for generating a volumetric representation of an object;
FIG. 2 is a flowchart illustrating the initial primary steps for implementing the method of the present invention;
FIG. 3 is a flowchart illustrating the final primary steps for implementing the method of the present invention;
FIG. 4 is a flowchart illustrating the pre-processing steps of the present invention;
FIG. 5 is a flowchart illustrating the initial steps of the contour generation process;
FIG. 6 is a flowchart showing the remaining steps of the contour generation process;
FIG. 7 is a top view of a slice of volumetric data on which a first outer contour has been generated by the contour generation process;
FIG. 8 is a top view of a slice of volumetric data on which first and second outer contours have been generated by the contour generation process;
FIG. 9 is a top view of a slice of volumetric data on which two outer contours and an inner contour have been generated by the contour generation process;
FIG. 10 is a top view of a slice of volumetric data on which two outer and two inner contours have been generated by the contour generation process;
FIG. 11 is a cross-sectional view of an object represented in terms of volumetric data; FIG. 12 is a flowchart illustrating the steps of the contour analysis process that store overlaps for each contour;
FIG. 13 is a flowchart illustrating the beginning of the discrete surface determination steps of the contour analysis process;
FIG. 14 is a flowchart that shows additional discrete surface determination steps for the contour analysis process;
FIG. 15 is a flowchart showing the remaining steps of the contour analysis process;
FIG. 16 is a cross-sectional view of an object represented in terms of volumetric data;
FIG. 17 is a flowchart showing the initial steps of the topological analysis process;
FIG. 18 is a flowchart showing additional steps of the topological analysis process;
FIG. 19 is a flowchart showing additional steps of the topological analysis process;
FIG. 20 is a flowchart showing additional steps of the topological analysis process;
FIGS. 21(a)-(k) illustrates various object topological classifications;
FIGS. 22(a)-(f) shows several special femur topological classifications;
FIGS. 23(a)-(b) are top views of two slices of volumetric data illustrating the manner in which wormhole can be formed;
FIG. 24 is a top view of a combination of the two slices shown in FIGS. 23(a)-(b);
FIG. 25 is a data structure utilized to implement a SVOX;
FIG. 26 is a perspective view of a rectilinear cube showing the SVOXs that can be used to model it;
FIGS. 27(a)-(b) illustrate the various orientations that a SVOX can be assigned;
FIG. 28 is a flowchart illustrating the steps of the subroutine SMAPGEN;
FIG. 29 is a flowchart illustrating additional steps of the subroutine SMAPGEN;
FIG. 30 is a flowchart illustrating additional steps of the subroutine SMAPGEN;
FIG. 31 is a cross-sectional view of an object represented in terms of volumetric data which illustrates how top and bottom SMAPs can be generated on slices other than the top and bottom slices;
FIG. 32 is a flowchart illustrating the initial steps of the SMAP generation process;
FIG. 33 is a flowchart illustrating additional steps of the SMAP generation process;
FIG. 34 is a flowchart showing additional steps of the SMAP generation process;
FIG. 35 is a flowchart showing additional steps of the SMAP generation process;
FIG. 36 is a flowchart illustrating additional steps of the SMAP generation process;
FIG. 37 is a flowchart illustrating additional steps of the SMAP generation process;
FIGS. 38(a)-(f) illustrate the manner in which the special femur topologies are modeled;
FIGS. 39(a)-(i) illustrate an object undergoing the reiterative DUV process and representations of the object in UV;
FIG. 40 is a cross-section view of a femur illustrating the landmark SVOXs to be utilized with the landmark method of generating initial V-lines during the reiterative DUV process;
FIG. 41 is a flowchart illustrating the initial steps of the reiterative DUV process;
FIG. 42 is a flowchart illustrating additional steps of the reiterative DUV process;
FIG. 43 is a flowchart illustrating additional steps of the reiterative DUV process;
FIG. 44 is a flowchart illustrating additional steps of the reiterative DUV process;
FIG. 45 is a flowchart illustrating additional steps of the reiterative DUV process;
FIG. 46(a)-(b) is a chart showing the correlation between object topology and the method utilized for generating the initial v-lines during the reiterative DUV process;
FIG. 47 is a flowchart showing the DUV post-processing steps;
FIGS. 48(a)-(b) are cross-sectional view of UV line illustrating the manner in which duplicate point removal can be performed;
FIG. 49 illustrates a hardware system for implementing the method of the present invention;
FIG. 50 is a flowchart illustrating the primary steps in a method for generating a replica of an object represented in terms of volumetric data;
FIG. 51 is a flowchart illustrating the primary steps in a method for operating a computer to generate a surface representation of an object represented in terms of volumetric data;
FIG. 52 is a flowchart illustrating the primary steps in a method for operating a computer to generate a data structure representing a NURB solid model of an object represented in terms of surface data;
FIG. 53 is a flowchart illustrating the primary steps in a method for operating a computer to generate a surface representation of an object represented in terms of volumetric data; and
FIGS. 54(a)-(j) illustrate several additional body types that can be supported by the method of the present invention and the manner in which they can be modeled.
DETAILED DESCRIPTION
The present invention is directed toward a method and apparatus for generating a contiguous solid model of an object defined in terms of volumetric data. A number of sources are known for generating a volumetric data representation of an object. These sources include, but are not restricted to, apparatus for performing the following processes CAT scanning, Magnetic Resonance Imaging (MRI), Radio Isotope Imaging (PET/SPECT), Digital Subtraction Angiography (DSA), ultrasound, core sampling, Pathological/manual slice/contour generation, surveying, sonar, simulations and laser scanning. In addition to these sources, the present invention could operate upon the data output from any other source for generating a volumetric data representation of an object. Therefore, when reference is made herein to a source for generating a volumetric data generation representation of an object, the source is intended to include any of the specific sources described above, as well as other sources that generate similar types of volumetric data representations.
FIG. 1 is a graphical representation of a portion 2 of a volumetric data output that may be generated by any of the sources described above. The smallest unit of information that makes up the volumetric data representation of the object is a voxel. As illustrated by the voxel 4 shown in cross-hatching in FIG. 1, a voxel is a rectilinear cube volume. The portion of volumetric data shown in FIG. 1 includes a group of eighty voxels. The number of voxels generated to model an object varies depending upon the particular source utilized for generating the volumetric model. When a CAT scan is utilized, a 512.times.512 array of voxels is generally generated. In the portion of volumetric data shown in FIG. 1, each row 6 of voxels corresponds to a slice of data output by the volumetric data generation source. Typically, ten to eighty slices of data will be utilized to generate a three-dimensional representation of the object. The volumetric data generation source assigns a density value to each voxel representing the density of the object in the volume corresponding to the voxel. The range of possible density values will vary depending upon the particular data generation source utilized. When a CAT scan is utilized, the density of each voxel is typically defined by a 12-bit data field.
As can be appreciated from the foregoing, the model of the object produced by the volumetric data generation source includes a large amount of data. For example, a typical CAT scan process will generate ten to eighty slices of 512.times.512
arrays of voxels, each voxel having a density value defined by a 12-bit data field. This volumetric representation of the object is very detailed and includes information relating to the manner in which the density of the object varies throughout its entire volume. Additionally, this model represents the object in terms of a plurality of discrete voxels.
As stated above, the present invention is directed toward a method and apparatus for generating a solid model of an object that is represented in the volumetric data format described above. The primary steps for implementing the method of the present invention are shown in FIGS. 2-3. Each of these primary steps is implemented by a plurality of sub-steps that are described in more detail below.
In step 100, the output from the volumetric data generation source is pre-processed. The representation of the object in terms of volumetric data is data-intensive and includes a large amount of information that is unnecessary for generating a solid model of the object. The purpose of the pre-processing step 100 is to discard unnecessary information and to convert the volumetric data into a format more easily operated upon by the remaining steps of the method.
In step 200, inner and outer contours of the object represented by the pre-processed volumetric data are generated to determine the inner and outer surfaces of the object. The contours are then analyzed in step 300 to determine whether they include certain relevant features that are useful during the topological analysis process conducted in step 400.
During step 400, the results of the contour analysis are reviewed and based upon its topology, the object is classified as falling within one of a group of pre-determined object types. Experience has shown that the best technique for generating a solid model of an object varies depending upon the topology of the object. Therefore, the classification done during step 400 is used in later steps of the method to determine the technique for generating the most accurate solid model of the object.
In step 500, one or more surface maps (SMAPs) are generated for the object. A SMAP is a data structure that describes the object volume as a collection of planar faces that enclose the volume. A SMAP is formed by connecting together a plurality of surface voxel faces (hereafter SVOXs) that enclose the volume. Each SVOX is defined in terms of the voxel to which it belongs, as well as the orientation of the SVOX on that voxel. SMAPs will be more fully described below.
In step 600, the reiterative directed U-V (DUV) process is performed on each SMAP generated in step 500. The reiterative DUV process involves the generation of a series of mesh lines across the SMAP surface. The intersections of the mesh lines define a plurality of control points for establishing a NURB surface representation of the SMAP as is more fully described below.
In step 700, the data generated by the reiterative DUV process is post-processed to enhance the accuracy and reliability of the NURB surface represented by the array of control points generated at step 600.
Finally, in step 800, the post-processed data is converted into IGES format. IGES (Initial Graphics Exchange Specification) format is a format recognized by the United States National Bureau of Standards. The IGES format provides a standard that represents the object in terms of parametric (NURB) surfaces, trimmed surfaces, and/or other geometric entities. The IGES file generated at step 800 can be used as an input to any CAD/CAM system that features an IGES translator.
FIG. 49 illustrates a hardware system upon which the above-described method can be implemented. A volumetric data generation source 800 is utilized to probe the object for which the solid model representation is to be generated and to generate a volumetric data representation of the object. The volumetric data generation source 800 can be any one of a number of different apparatus as described above. The volumetric data representation generated by the volumetric data generation source 800 is sourced to a computer 802. The computer 802 is coupled to a user interface 803 to enable a user to input and receive information regarding the method. The computer 802 is also coupled to a memory 804 which the computer utilizes for storing information during the execution of the method. The steps of the method described above are implemented in the computer 802 and the memory 804 to generate a NURB solid model of the object. In the configuration shown in FIG. 49, the computer 802 is coupled to a CAD/CAM system 806. As a result, the NURB solid model of the object generated by the method executed on computer 802 can be utilized to control the operation of the CAD/CAM system where various operations such as numerical control, finite element modeling, simulating procedures, measurement and CAD design can be performed. For example, the CAD/CAM system can be used to make tool paths for automatic milling and lathing machines through numerical control. The machines having these tool paths could then be operated to generate replicas of the object, or to make parts that engage the object and must be fitted thereto. For example, an automobile body part could be probed by the volumetric data generation source 800 and a NURB solid model generated for the part could then be utilized to make tool paths for manufacturing the part on milling and lathing machines.
The NURB solid model of the object generated by the method executed on computer 802 can also be utilized to control the operation of the CAD/CAM system to directly generate replicas of the object. When a CAD/CAM system is utilized to generate a replica of the object, it will utilize the NURB solid model to manufacture an article having a surface topology that is substantially identical to the NURB surface model. As used herein, the topology of the manufactured article is considered to be identical to that of the NURB solid model if it has a substantially identical shape, even if the article is scaled from the NURB surface model so that it has a different size.
Although the computer 802 is coupled to a CAD/CAM system in FIG. 49, it should be understood that various other systems that receive NURB solid models of an object as input data could also be coupled to computer 802 so that the NURB solid model generated by the method could be used in a variety of other ways. As stated above, each of the steps shown in FIGS. 2-3 is implemented by a plurality of sub-steps. The sub-steps for each will now be described.
PRE-PROCESSING
The steps for pre-processing the volumetric data are shown in FIG. 4. In step 102, the volumetric data is interpolated to achieve greater resolution. For example, if the volumetric data is generated by a CAT scan, it might consist of 67 slices spaced 3.0 mm apart. This information may be interpolated to 2.0 mm, resulting in 100 slices and providing greater resolution. Additionally, if the slices of volumetric data do not all have the same thickness, new slices may be created to equalize the thickness of the slices. Although it is desirable to interpolate the volumetric data for the reasons stated above, interpolation of the data is not a necessary step and the present invention can be performed on data that is not interpolated. After the data is interpolated, it is segmented in step 104. Segmenting is a process whereby only the voxels that correspond to the object to be modeled are selected. The output from the volumetric data generation source will often include information relating to background substances in addition to the object to be modeled. For example, one application in which the present invention can be utilized is for generating a solid model of a patient's bone which can then be used to drive a CAM system to generate a replica of the bone which can then be used to design a customized prosthesis. For that type of application, a CAT scan (or one of the other data generation source described above) is performed on the patient to generate a volumetric representation of the bone. The CAT scan output also includes information relating to background substances surrounding the bone, such as muscle tissue and the like. Therefore, in order to determine which portions of the volume represent the bone to be modeled, the volumetric data is segmented.
The volumetric data can be segmented in any number of different ways. For example, a user can examine a graphical representation of the volumetric data on a graphic display system and can manually select the voxels that correspond to the volume of the object to be modeled. Alternatively, a simple algorithm can be utilized to separate the voxels corresponding to the object from the other voxels in the volumetric data output from the volumetric data generation source. As stated above, the volumetric data generation source assigns a density value to each voxel, the density valve representing the density of the examined area in the volume corresponding to the voxel. One algorithm that has been developed for segmenting the data selects a range of density values that define the object to be modeled, and then analyzes each voxel to determine whether its density value falls within the selected range. If the density value of a voxel falls within the selected range, the voxel represents the object and is selected by setting its density value to "1". Conversely, if the density value for a voxel does not fall within the selected range, the voxel does not represent the object and it is not selected by setting its density value to "0". Segmenting of the data can also be performed by a combination of this algorithm and manual intervention by first performing the algorithm on the data and then having a user analyze the results and optimize them manually.
A gradient based algorithm could also be used to segment the volumetric data. A gradient based algorithm could determine the volume that defines the object to be modeled by examining the rate of change of voxel density values from one voxel to another to determine the outer edges of the object. Additionally, a percentage classification algorithm could be utilized that examines the density of each voxel in relation to the other voxels in its area of the volume to determine which voxels correspond to the object to be modeled.
As can be seen from the foregoing, after the data has been segmented, each voxel is set to either "1" if it is part of the volume that defines the object to be modeled and is set to "0" if it is not part of the object volume.
CONTOUR GENERATION
The contour generation process 200 will now be described making reference to FIGS. 5-10. By way of overview, the contour generation process 200 is performed on a slice-by-slice basis. Contours are generated on each slice that define the inner and outer surfaces of the object represented on that slice. As a result of the segmenting step 104, the object is represented volumetrically by voxels that are set to "1". Therefore, the contours of the object are determined based upon the density values for each voxel on the slice.
The contour generation process is begun in step 202 by examining the first voxel on the first slice. The selection of a particular voxel as being the first voxel is totally arbitrary. All that is required is that the process be able to iteratively step through the array of voxels on each slice in an organized manner so that each voxel can be examined. Similarly, the first slice can be arbitrarily selected as either the top or bottom slice.
Once the first voxel is located, a determination is made in step 204 as to whether it is set to "1". If the voxel is not set to "1", the method proceeds to step 206 where a determination is made as to whether the voxel examined in step 204 is the last voxel on the slice. If the last voxel has not been examined, the method proceeds, in step 208, to examine the next voxel and returns to step 204 wherein a determination is made as to whether the newly examined voxel is set to "1" In this manner the contour generation process iteratively examines the voxels on the slice being processed until it locates a voxel that is set to "1".
When it is determined at step 204 that a voxel is set to "1" (i.e. that it is selected), the contour generation process proceeds to step 210 wherein a contour is generated beginning with that voxel, the voxel defining a seed for the contour. The manner in which a contour is generated will now be described, making reference to FIG. 7.
A contour is a series of points, defined in terms of the voxel XY coordinates, that define an outer or inner surface of the object represented by the volumetric data. FIG. 7 shows an array of 11.times.10 voxels. If, for example, the voxel defined at x=2, y=5 were detected as the first voxel set to "1", a contour C1 illustrated by the bold line would be formed using this voxel as a seed. The contour C1 is defined by eight XY control points P1-P8 that define the points where the contour C1
changes direction. The contour C1 is generated by examining each voxel adjacent to the seed voxel, including those that are diagonally adjacent, and determining which of those voxels are selected. Thereafter, the adjacencies for the selected voxels adjacent the seed are also examined. This process continues until all the selected voxel adjacencies have been found. The contour is then generated, beginning with the seed, so as to include all the selected voxels on the slice for which an uninterrupted path of adjacent selected voxels can be drawn to the seed voxel.
After the contour is generated, the contour generation process proceeds to step 212 wherein a list of voxels enclosed by the contour is generated in terms of their XY coordinates. In the example shown in FIG. 7, the contour C1 encloses twenty-one voxels. After the list of enclosed voxels has been generated, the contour generation process proceeds to step 214 wherein the number of voxels enclosed by the contour is compared with a predetermined minimum voxel number that is defined by the user. This minimum voxel value is established for tolerancing reasons so that the method can detect whether a segmenting error has occurred. If the area enclosed by the contour is less than the minimum value established by the user, it is below the established tolerance and the process assumes that the voxels within the contour were set to "1" as a result of a segmenting error and do not accurately represent the object. Therefore, if it is determined at step 214 that the number of enclosed voxels is less than the required minimum value, the contour generation process proceeds to step 216 wherein the contour is discarded so that it will not be used by the later steps in the process. Additionally, a warning signal is also generated to indicate to the user that some portion of the segmented volume has been discarded. Thereafter, in step 218, the contour generation process advances to the next voxel and then returns to step 204 to continue with the generation of contours on the slice.
When it is determined at step 214 that the number of enclosed voxels exceeds the minimum established value, the contour generation process proceeds to step 220 wherein the voxel values of the voxels enclosed by the contour are converted in the following manner: (1) the enclosed voxels that were originally set to "0" are set to "2" and (2) the voxels that were originally set to "1" are set to "0" FIG. 8 shows the results of this conversion process for contour C1. The voxel values are converted in step 220 to assist in the generation of additional contours on a single slice. If there are voxels enclosed by the contour that were originally set to "0", it indicates that the object not only includes an outer surface for which the first contour was generated, but also includes an inner surface, enclosed within the outer contour, for which an additional contour will need to be generated. These voxels are set to "2" to enable the contour generation process to locate them later in the process in the manner described below.
After the enclosed voxel values are converted in step 220, the creation of the contour is complete. The contour generation process then proceeds to the next voxel in step 218 and returns to step 204. Through the execution of steps 204-208, the contour generation process successively examines the remaining voxels on the slice to determine whether any of them are set to "1". Because the voxel values for the voxels enclosed by the contours previously generated have been converted so that their values are set to either "0" or "2", they will not be detected at step 204. As a result, the only voxels that will be detected at step 204 are those that have values set to "1" and are not enclosed within any previously generated contour. In the example shown in FIGS. 7-10, there are some voxels set to "1" that are not enclosed by contour C1 and therefore did not have their values converted to "0" at step 212 following the generation of contour C1. Therefore, as the process proceeds to examine the remaining voxels on the slice, the process will detect, at step 204, another voxel on the slice that is set to "1". At that point, the process proceeds to step 210 wherein a contour C2 (FIG. 8) is generated. Thereafter, in steps 212 and 214, a list of voxels enclosed by contour C2 is generated and a determination is made as to whether the number of enclosed voxels exceeds the minimum value in the same manner as was described above with reference to contour C1. If the number of enclosed voxels does not exceed the minimum value, the process proceeds in step 216 to discard the newly generated contour C2. If it is determined at step 214 that the number of enclosed voxels exceeds the minimum established value, the voxel values are converted in step
220 in the same manner as was described above with reference to contour C1. The method then proceeds, in step 218, to the next voxel and returns to step 204. In this manner, the contour generation process establishes outer contours for every group of voxels that are set to "1" on the slice.
The contour generation process proceeds in the manner described above until it is determined at step 206 that the last voxel on the slice has been examined. At that point, the process proceeds to re-examine the first voxel at step 222 (FIG. 6) and then proceeds to step 224. At step 224, a determination is made as to whether the voxel value for the voxel being examined is set to "2" If the voxel value is not set to "2", the contour generation process proceeds in step 226 to determine whether the voxel being examined is the last voxel on the slice. If it is determined that the voxel is not the last voxel, the process proceeds in step 228 to examine the next voxel and then returns to step 224 wherein a determination is made as to whether the voxel has its value set to "2". In this manner, the contour generation process iteratively examines each voxel on the slice until the last voxel has been examined, or until it detects, at step 224, a voxel whose value is set to "2".
When a voxel having its value set to "2" is detected at step 224, the contour generation process proceeds to step 230 wherein a contour is generated utilizing the detected voxel as a seed. FIG. 9 illustrates an example of a contour C3 that encloses a group of voxels set to "2". After the contour is generated in step 230, the contour generation process proceeds to step 232 wherein a list of the voxels enclosed by the contour is generated. Thereafter, in step 234, the number of voxels enclosed is examined to determine whether it exceeds the minimum value in the same manner as was described above with regard to step 214. If the number of voxels does not exceed the minimum number, the contour is discarded in step 236. The contour generation process then proceeds to the next voxel in step 238 and returns to step 224.
If it is determined at step 234 that the number of enclosed voxels exceeds the minimum value, the voxel values for the enclosed voxels are converted from "2" to "0" in step 240. Thereafter, the contour generation process proceeds to the next voxel in step 238 and then returns to step 224. At step 224, a determination is made as to whether the newly examined voxel is set to "2". Since the voxels enclosed within the previously generated inner contour C3 have been converted to "0", they will not be detected at step 224 as having their values set to "2". Therefore, only voxels set to that are distinct from the groups of voxels enclosed by the inner contours already generated will be detected when the contour generation process returns to step 224 after generating an inner contour. As shown for example in FIG. 10, a voxel enclosed by contour C2 will be detected at step 224 as having its value set to "2" and, at step 230, a contour C4 will be generated utilizing the voxel as a seed in the manner described above with regard to the generation of contour C3.
In the manner described above, the contour generation process iteratively examines the voxels on the slice and generates inner contours for each group of voxels whose value is set to "2" until it is determined at step 226 that the last voxel on the slice has been examined. At that point, the contour generation process proceeds to step 242 wherein a determination is made as to whether the slice just processed was the last slice of the volumetric data. When it is determined at step 242 that the slice examined was not the last slice, the contour generation process, in step 244, proceeds to the next slice and returns to step 202 wherein the first voxel on the slice is examined. As a result, the contour generation process proceeds to generate contours for each slice of the volumetric data in the manner described above until it is determined at step 242 that the last slice has been processed. When it is determined at slice 242 that the last slice has been processed, the contour generation process terminates.
As described above, the specific steps of the contour generation process shown in FIGS. 5-6 enable an inner contour such as contour C3 to be generate within an outer contour such s contour C1. A key step that enables the generation of inner contours is step 220 which, after the outer contour has been generated, converts the voxels enclosed within the outer contour in the following manner: (1) the enclosed voxels that were originally set to "0" are set to "2" and (2) the enclosed voxels that were originally set to "1" are set to "0". As a result, the contour C3 can be generated later in the process around the voxels that are set to "2" In this manner, the contour generation process shown in FIGS. 5-6 can generate one contour that is enclosed within another contour, thereby enabling the process to create representations of objects having hollow areas defined within solid surfaces.
It should be appreciated that the specific steps of the contour generation process shown in FIGS. 5-6 can be modified to enable the process to generate additional layers of enclosed inner contours such that an inner contour could be enclosed within two or more larger contours. In order to generate additional enclosed contours, step 240 could be modified so that, rather than converting every enclosed voxel to "0" after the inner contour C3 is generated, enclosed voxels that were set to "0" could be converted to "0" or some another value other than "0". In this manner, step 240 would perform in much the same manner as step 220 described above in that it would enable further inner contours to be generated around the voxels that are set to "3". Additional steps could be added to detect voxels that are set to "3" and to generate contours around them. When those contours were generated, each enclosed voxel that was set to "0" could be converted to "4" and steps could be added to generate contours around the voxels set to "4". In this manner, additional steps could be added to the process shown in FIGS. 5-6 to generate enclosed inner contours that are enclosed within a large number of contours.
CONTOUR ANALYSIS
The contour analysis process 300 involves an analysis of the contours generated on each slice of the volumetric data, and a determination of how they interrelate to form the surfaces of the three-dimensional object represented thereby. FIG. 11
shows a cross-sectional view of an object 302 represented by twelve slices of volumetric data 300.sub.-- 1 through 300.sub.-- 12. The contour generation process 200 generates contours that define the inner and outer surfaces of the object on a slice-by-slice basis in the manner described above. For the object 302 shown in FIG. 11, the contour generation process generates two outer contours on each of slices 300.sub.-- 1 through 300.sub.-- 7 because on those slices, the object 302 has two distinct contours Ca and Cb. For slices 300.sub.-- 8 through 300.sub.-- 10, the contour generation process generates a single outer contour representing the object. The goal of the contour analysis process 300 is to examine the interrelationship of the contours on each slice in order to gain an understanding of how they form a three-dimensional representation of the object 302.
The first step in the contour analysis process is to determine the overlaps for each contour generated during the contour generation process 200. The contour analysis process begins by examining the first slice and, in step 304, determines whether there are any contours that were formed on that slice. If it is determined in step 304 that there are contours on the slice, the process proceeds to step 306 wherein overlap information is stored for each contour. An overlap is determined by examining the contours generated on the slices immediately above and below the slice being processed. A contour has an overlap if either of the slices above or below it has a contour that encloses at least one voxel with XY coordinates that match the XY coordinates of at least one voxel enclosed within the contour being processed.
After the overlaps are stored for each contour in step 306, the contour analysis process proceeds to step 308 wherein a determination is made as to whether the slice being processed is the last slice. When it is determined at step 308 that the slice being processed is not the last slice, the contour analysis process, in step 310, proceeds to the next slice and then returns to step 304. In this manner, the contour analysis process iteratively steps through each slice and stores the overlap information for every contour generated during the contour generation process 200. When it is detected at step 308 that the last slice has been processed, the contour analysis process proceeds to step 312 to begin a discrete surface determination as shown in FIGS. 13-15.
The discrete surface determination begins as step 312 wherein the process selects the first slice for processing. Thereafter, the contour analysis process proceeds to step 314 wherein a determination is made as to whether there are any contours on the slice being processed. When it is determined at step 314 that there are contours on the slice being processed, the process proceeds to step 316 wherein each of the contours on the slice is marked as corresponding to a null surface. The marking of all the contours to correspond to a null surface is an initialization step that simplifies the remaining steps in the process as will be understood from the description of the remaining steps in the process that are described below.
After all the contours on the slice being processed are marked at step 316, or when it is determined at step 314 that there are no contours on the slice being processed, the contour analysis process proceeds to step 318 wherein a determination is made as To whether the last slice is being processed. When it is determined at step 318 that the slice being processed is not the last slice, the contour analysis process proceeds to step 320 wherein it goes to the next slice for processing and then returns to step 314. In this manner, the contour analysis process iteratively processes each slice and marks each contour as corresponding to a null surface until it is determined at step 318 that the last slice has been processed.
When it is determined at step 318 that the last slice has been processed, the contour analysis process proceeds to step 322 wherein it identifies the surface to be formed as a first surface. The surface to be formed is identified because, as described above, the object may have multiple surfaces that need to be formed, thereby requiring that the surfaces be identified to distinguish them from one another. After the surface to be formed is identified at step 322, the contour analysis process proceeds to step 324 wherein it selects the first slice for processing and then proceeds to step 326 (FIG. 14).
At step 326, a determination is made as to whether there are any contours on the slice being processed that are marked as corresponding to the null surface. When it is determined at step 326 that there are no contours on the slice being processed that are marked as corresponding to the null surface, the contour analysis process proceeds to step 328 wherein a determination is made as to whether the last slice has been processed. When it is determined at step 328 that the last slice has not been processed, the contour analysis process proceeds to step 330 wherein it selects the next slice for processing and then returns to step 326. In this manner, the contour analysis process iteratively processes the slices until it locates a contour, at step 326, that is marked as corresponding to the null surface.
When it is determined at step 326 that the slice being processed includes at least one contour marked as the corresponding to the null surface, the contour analysis process proceeds to step 332 wherein the following two functions are performed: (1) one of the contours on the slice being processed that is marked as corresponding to the null surface is marked as corresponding to the surface currently being formed and (2) a list of contours to be marked is updated to include each of the contours that overlap with the marked contour.
When a contour is detected at step 326, it indicates that the object to be modeled includes at least a first surface. As described above, when the discrete surface determination process is begun, the surface currently being formed is initialized at step 322 (FIG. 13) to identify it as a first surface. Therefore, when the first contour is detected at step 326, it will be marked at step 332 as corresponding to a first surface. Thereafter, the contour analysis process will generate a first surface utilizing the first detected contour as a seed. As stated above, contours that overlap one another each define part of the same surface. Therefore, in order to generate a first surface from the seed contour, a list is created at step 332 of the contours that overlap the seed contour. The list created at step 332 indicates additional contours that are to be marked as corresponding to the same surface as the seed contour. Therefore, for the first seed contour detected, a list is formed at step
332 indicating that each of the contours that overlap the seed contour should also be marked as corresponding to the first surface. After the seed contour has been marked and the list of contours to be marked has been updated at step 332, the contour analysis process proceeds to step 334.
At step 334, the contour analysis process selects for processing the first contour on the list of contours to be marked. Thereafter, the contour analysis process proceeds to step 336 wherein the contour being processed is marked as corresponding to the surface that is currently being formed. The list of contours to be marked is updated to include the additional contours that are marked as corresponding to the null surface and that overlap with the contour currently being processed which has just been marked as corresponding to the surface being formed.
After the contour currently being processed is marked and the list is updated at step 336, the contour analysis process proceeds to step 338 wherein a determination is made as to whether there are any contours remaining in the list of contours to be marked. When it is determined at step 338 that there are contours remaining in the list, the contour analysis process proceeds to step 340 wherein selects the next contour on the list for processing and returns to step 336. In this manner, the contour analysis process reiteratively proceeds to mark each of the contours that correspond to the surface currently being formed, and continually updates the list of contours to be marked, until it is determined at step 338 that there are no contours remaining in the list of contours to be marked. At that point, the contour analysis process proceeds to step 342 wherein the identification of the surface currently being formed is incremented.
After the identification of the surface currently being formed is incremented at step 342, the contour analysis process returns to step 324 (FIG. 13) wherein it again selects the first slice processing. Thereafter, the contour analysis process proceeds to step 326 (FIG. 14) wherein a determination is made as to whether there are any contours on the slice being processed that are marked as corresponding to the null surface. As described above, when the first surface was formed, the contours corresponding thereto were marked, at either of steps 332 or 336, as corresponding to the first surface. Therefore, when the contour analysis process returns to step 326, these contours will no longer be detected as corresponding to the null surface. Therefore, after a first surface has been formed, a contour will only be detected at step 326 as corresponding to the null surface if the object includes a second discrete surface. If an object includes a second discrete surface, a contour will be detected at step 326 that is marked as corresponding to the null surface. Thereafter,.the contour analysis process will proceed, in the manner described above, to generate a second surface utilizing the detected contour as a seed.
In the manner described above, the contour analysis process iteratively steps through the slices of the object and forms the necessary number of discrete surfaces. Once all of the discrete surfaces have been formed, no additional contours will be detected at step 326 as corresponding to the null surface. Therefore, the contour analysis process will proceed, through steps 326,328 and 330, to iteratively step through each of the slices until it is determined at step 328 that the last slice has been processed. At that point, the discrete surface determination portion of the contour analysis process is complete.
After the discrete surface determination process has been completed, the contour analysis process proceeds to step 348 (FIG. 15) wherein the maximum and minimum Z-slices of each discrete surface are recorded. Depending upon the size and topology of the object, the discrete surfaces formed therefrom may not extend over the full range of volumetric data slices. When that occurs, each discrete surface has maximum and minimum Z slice. For example, Z slice 10 is the maximum Z slice for the object shown in FIG. 11.
The next step in the contour analysis process is to record the number of junctions in step 350. A junction occurs when a single contour on one slice is overlapped by two or more distinct contours on an adjacent slice. Making reference to FIG.
11, a junction is defined between slices 7 and 8 because the single contour on slice 8 is overlapped by the two distinct contours Ca and Cb on slice 7. The number of junctions for each discrete surface is utilized during the topological analysis process as is more fully described below.
The final step in the contour analysis process is step 352 wherein a determination is made as to whether any of the discrete surfaces has a true hole extending therethrough. A true hole is defined as one which extends through the entirety of the discrete surface and should be distinguished from wormholes which are described below. For example, FIG. 16 is a cross-sectional view of an object 354 having a true hole 356 extending therethrough. The determination in step 352 as to whether any of the discrete surfaces representing the object has a true hole is made by examining the junctions of each surface. Making reference to FIG. 16, the object 354 has an up junction J1 defined where two contours on slice 3 are overlapped by and are positioned above a single contour on slice 2. The object 354 also has a down junction J2 defined where two contours on slice 7 overlap and are positioned below a single contour on slice 8. When a true hole is formed in a discrete surface, the discrete surface has the following two characteristics: (1) a down junction positioned above an up junction and (2) paths of overlapping contours extending downward from each portion of the down junction that respectively intersect with paths of overlapping contours extending upward from the up junction. Therefore, by examining the junctions and the overlaps extending therefrom, the contour analysis process determines, at step 352, whether any of the discrete surfaces has a true hole. This determination is useful during the topological analysis process as is described below.
TOPOLOGICAL ANALYSIS
The accuracy of the NURB solid model generated by the method can be enhanced by conducting a topological analysis of the object and utilizing the information gained from this analysis in determining the particular manner in which SMAPs are generated for the object and the manner in which the reiterative DUV process is to be executed on those SMAPs. For varying object shapes, it has been found that different techniques for SMAP generation and reiterative DUV processing should be utilized in order to enhance the accuracy of the resulting NURB solid model. Therefore, before proceeding to the later steps in the process, the topological analysis process 400 is performed to examine the topology of the object.
The details of the topological analysis process will now be described making reference to FIGS. 17-22. In step 402, the object is classified as falling within one of five basic object types which are shown in FIGS. 21(a)-(e). The first of these object classifications is the non-hollow solid shown in FIG. 21(a). This type of object will be modeled with a single closed outer surface in the manner described below.
The second object classification is the solid with a completely enclosed hollow area that is shown in FIG. 21(b). This type of object is modeled with a combination of a closed outer surface and a closed inner surface. The object is defined as the Boolean subtraction of the inner surface from the outer surface.
The third object classification is the solid having a hollow area accessible from the top that is shown in FIG. 21(c). This type of solid is modeled as the composition of the following three surfaces: (1) an open outer surface; (2) an open inner surface; and (3) a trimmed planar surface at the top of the inner and outer surfaces. Open surfaces on the top or bottom of the object are generally created when an object extends beyond the range of the volumetric data representation generated by the CAT scan or other volumetric data generation source. As a result, the object is essentially cut-off at the edge of the volumetric data representation. Trimmed planar surfaces are similarly generated to "cap" the solid at the interface where it exits the volume. The generation of open and trimmed surfaces will be more fully described below.
The fourth basic object classification is the solid having a hollow area accessible from the bottom as shown in FIG. 21(d). This type of object is modeled as a composition of an open outer surface, an open inner surface and a trimmed planar surface at the bottom of the inner and outer surfaces.
The fifth basic object classification is a solid having a hollow area accessible from both the top and bottom as shown in FIG. 21(e). This type of object is modeled as the composition of four surfaces, i.e. an open outer surface, an open inner surface, a trimmed planar surface at the top and a trimmed planar surface at the bottom.
Following the initial object classification, the topological analysis process proceeds to further sub-classify the object. In step 404 (FIG. 18), a determination is made as to whether the object has been classified as a non-hollow solid during step 402. If the object has been so classified, the process proceeds to step 406 where a determination is made as to whether the object has a true hole. If it is determined that the object has a true hole, the process proceeds to step 408 where the classification of the object is updated to sub-classify the object as a non-hollow with a true hole, an example of which is shown in FIG. 21(f). Thereafter, a determination is made in step 410 as to whether the object is trimmed. If it determined that the object is trimmed, an error signal is generated in step 412 because the process currently does not recognize objects that are non-hollow, trimmed and have a true hole.
As currently implemented, the method of the present invention recognizes only the body types shown in FIGS. 21(a)-21(k). Therefore, if it is determined during the topological analysis process that the object to be modeled does not fall within one of the recognized classifications, the process generates an error signal indicating that the object cannot be modeled. However, it should be understood that the method of the present invention is not inherently limited to modeling only the particular object classifications shown in FIGS. 21(a)-(k). For example, at present, it is envisioned that the method will also support the body types shown in FIGS. 54(a)-(j), as well as others. Based upon the description of the present invention provided herein, routine modifications and/or additions could be made to the method of the present invention to enable the modeling of various additional object types. Therefore, although the description provided herein describes the current implementation of the method as being limited to the object types shown in FIGS. 21(a)-(k), the invention is not so limited.
If it is determined at step 406 that the non-hollow solid does not have a true hole, the process proceeds at step 414 to determine whether the object is trimmed on top. If it is determined that the object is trimmed on top, the classification of the object is updated in step 416 to sub-classify the object as a non-hollow solid that is trimmed on top, an example of which is shown in FIG. 21(g). If it is determined at step 414 that the object is not trimmed on top, the process proceeds to step
418 wherein a determination is made as to whether the object is trimmed on the bottom. If it is determined that the object is trimmed on the bottom, the classification of the object is updated in step 420 to sub-classify the object as a non-hollow solid trimmed on the bottom, an example of which is shown in FIG. 21(h). If it is determined at step 418 that the object is not trimmed at the bottom, then the object does not fall within any of the recognized sub-classifications and its classification will remain unchanged as indicating that the object is a non-hollow solid.
If it is determined at step 404 that the object is not a non-hollow solid, the topological analysis process proceeds to step 422 wherein a determination is made as to whether the object is a solid with an enclosed hollow area. If it is determined that the object is a solid with an enclosed hollow area, the process proceeds to step 424 wherein a further determination is made as to whether the object has a true hole. If it is determined that the object does not have a true hole, no further sub-classification of the object is done and the classification of the object remains unchanged as indicating that the object is a solid with an enclosed hollow area. However, if it is determined at step 424 that the object does have a true hole, the classification of the object is updated at step 426 to sub-classify the object as a solid having an enclosed hollow and a true hole, an example of which is shown in FIG. 21(i).
Following the sub-classification analysis of the non-hollow solids and the solids with enclosed hollow areas as described above, the topological analysis process proceeds to step 428 wherein a determination is made as to whether special processing has been requested by the user. If it is determined that special processing has been requested, the process proceeds to step 446 (FIG. 20) wherein special processing is performed in a manner that is described below. If it is determined at step 428 that special processing was not requested, the topological analysis process is terminated.
If it was determined at step 422 that the object was not a solid with an enclosed hollow area, the topological analysis process proceeds to step 430 (FIG. 19) wherein a determination is made as to whether the object has a true hole. If it is determined that the object has a true hole, the process proceeds to step 432 wherein an error signal is generated to indicate that the object does not fall within one of the recognized classifications as shown in FIGS. 21(a)-(k). The only recognized object classifications having true holes are the non-hollow solid and the solid having an enclosed hollow area. If the topological analysis process has progressed to step 430, the object does not broadly fit within either of these classifications and, therefore, the fact that the object has a true hole indicates that the object does not fall within one of the recognized classifications.
If it is determined at step 430 that the object does not have a true hole, the topological analysis process proceeds to step 434 wherein a determination is made as to whether there are two or more top or bottom openings in the object. If there are not, the generalized sub-classification of the object is complete and the process proceeds to step 436 wherein a determination is made as to whether special processing has been requested. However, if it is determined at step 434 that the object does have two or more top or bottom openings, the topological analysis process proceeds to step 438 wherein a determination is made as to whether the object is a hollow Y top, an example of which is shown in FIG. 21(j). If it is determined that the object is a hollow Y top, the classification of the object is updated at step 440 to sub-classify the object in this manner. Thereafter, the generalized sub-classification of the object is complete and the process proceeds to step 436 to determine whether special processing has been requested.
If it is determined at step 438 that the object is not a hollow Y top, a further determination is made at step 442 as to whether the object is a hollow Y bottom. If it is determined that the object is a hollow Y bottom, the process proceeds to step 444 wherein the classification of the object is updated to sub-classify the object in this manner. Thereafter, the generalized sub-classification of the object is complete and the method proceeds to step 436 to determine whether special processing is requested. If it is determined at step 442 that the object is not a hollow Y bottom, the method proceeds to step 432 wherein an error signal is generated to indicate that the object does not fall within any of the recognized object classifications. The only currently recognized object sub-classifications having two or more top or bottom openings are the hollow Y top and hollow Y bottom. Therefore, if it is determined at step 442 that the object does not fall within either of these sub-classifications, then an error signal must be generated.
As stated above, when the sub-classification of the object has been completed, the topological analysis process, at steps 428 or 436, makes a determination as to whether special processing has been requested. Special processing may be requested by the user when the object to be modeled has a particular topology known to the user. If the topology of the object is known in advance, the method of the present invention can be customized to generate a particularly accurate NURB solid model. As stated above, one application for the use of the method and apparatus of the present invention is in generating a medical prosthetic device for a skeletal portion of the body represented in terms of volumetric data. It has been found to be particularly desirable to generate accurate models for the femur which can be somewhat difficult to accurately model due to its irregular topology. As a result, the method of the present invention has been customized in several ways that are described below to enable the method to generate particularly accurate models of the femur.
The use of these customized features of the invention are selected by the user by simply indicating that the object being modeled is a femur. When the user indicates that the object is a femur, the topological process performs additional sub-classification steps to determine which one of the following representations of a femur is being modeled: (1) the femur illustrated in FIG. 22(a); (2) the femur non-hollow illustrated in FIG. 22(b); (3) the femur non-hollow shaft illustrated in FIG.
22(c); (4) the femur shaft shown in FIG. 22(d); (5) the femur non-hollow entire shown in FIG. 22(e); or (6) the femur entire illustrated in FIG. 22(f).
The manner in which the topological analysis process responds when it determines that special processing has been requested will now be described making reference to FIG. 20. The process initially proceeds to step 446 wherein a determination is made as to whether the object has been classified as a non-hollow solid. The following three femur types will be categorized as a non-hollow solid during the generalized topological analysis: (1) the femur non-hollow shown in FIG. 22(b); (2) the femur non-hollow shaft illustrated in FIG. 22(c); and (3) the femur non-hollow entire shown in FIG. 22(e).
Therefore, when it is determined at step 446 that the object has been classified as a non-hollow solid, the process proceeds to step 448 to determine which of these three femur types is being modeled.
At step 448, a determination is made as to whether the object is a femur non-hollow shaft as illustrated in FIG. 22(c). The determination is made at step 448 by examining the contours on selected slices of the object. For each selected slice, the center voxel for the contour is determined and the distance between the center voxel and each of the other voxels contained within the contour is measured. The largest and smallest distances are stored and their ratio is compared to a constant cut-off ratio that is determined by the user. This ratio is established such that it defines a contour that is more oblong than circular. When a contour has a ratio that exceeds the cut-off ratio, it indicates that the contour forms a portion of a femur shaft. As a result, by examining selected contours near the top and bottom of the object, the process determines whether the object is a femur shaft along its entire length and if it is, recognizes that the object is a femur non-hollow shaft.
When it is determined at step 448 that the object is a femur non-hollow shaft, the process proceeds to step 450 wherein the object classification is updated to indicate that the object is a femur non-hollow shaft. Thereafter, the topological analysis process terminates.
When it is determined at step 448 that the object is not a femur non-hollow shaft, the process proceeds to step 452 wherein a determination is made as to whether the object is a femur non-hollow as shown in FIG. 22(b). When the process proceeds to step 452, the object is either a femur non-hollow or a femur non-hollow entire. Therefore, by examining the object contours on the lower slices of the object to determine whether they are more oblong than circular, the process determines whether the lower portion of the object is a femur shaft and if it is, determines that the object is a femur non-hollow. When it is determined at step 452 that the object is a femur non-hollow, the process proceeds to step 454 wherein the object classification is updated to indicate that the object is a femur non-hollow. Thereafter, the topological analysis process terminates.
When it is determined at step 452 that the object is not a femur non-hollow, the object is a femur non-hollow entire. Therefore, the process proceeds to step 456 wherein the object classification is updated to indicate that the object is a femur non-hollow entire. Thereafter, the topological analysis process terminates.
When it is determined at step 446 that the object is not a non-hollow solid, the process proceeds to step 458 wherein a determination is made as to whether the object is a solid with an enclosed non-hollow area as shown in FIG. 21(b). When it is determined that the object is a solid with an enclosed non-hollow area, the process proceeds to step 460 wherein the object classification is updated to indicate that the object is a femur entire as shown in FIG. 22(f). Thereafter, the topological analysis process terminates.
When it is determined at step 458 that the object is not a solid with an enclosed hollow area, the process proceeds to step 462 wherein a determination is made as to whether the object is a solid having a hollow area accessible from the bottom as shown in FIG. 21(d). When it is determined that the object is a solid having a hollow area accessible from the bottom, the process proceeds to step 464 wherein the object classification is updated to indicate that the object is a femur as shown in FIG.
22(a). Thereafter, the topological analysis process terminates.
When it is determined at step 462 that the object is not a solid having a hollow area accessible from the bottom, the process proceeds to step 466 wherein a determination is made as to whether the object is a solid having a hollow area accessible from the top and bottom as shown in FIG. 21(e). When it is determined that the object is a solid having a hollow area accessible from the top and bottom, the process proceeds to step 468 wherein the object classification is updated to indicate that the object is a femur shaft as shown in FIG. 22(d). Thereafter, the topological analysis process terminates.
When it is determined at step 466 that the object is not a solid having a hollow area accessible from the top and bottom, the process proceeds to step 470 wherein an error signal is generated indicating that although special processing was requested, the object being modeled does not fall within one of the recognized femur classifications. Thereafter, the topological process terminates.
The topological classification of the six femur types is described as being performed by the specific steps explained above solely for illustrative purposes. It should be recognized that the femur types could also be classified in a number of other ways. For example, the sub-classifications of the object could be utilized as a basis for determining which femur type is being modeled, rather than utilizing just the five basic classification types.
Although the special processing feature has been described above as implementing only the six particular femur topologies, it should be understood that this feature of the present invention is not limited to those special topologies. The use of the special processing feature enables a user to indicate that the object being modeled has a particular topology and enables particularly accurate models to be generated for topologies that are frequently modeled or are particularly difficult to model. Through experimentation in the number and placement of the SMAPs utilized to represent the volumetric data, as well as in the particular manner in which the reiterative DUV process is performed on those SMAPs, optimum modeling techniques can be determined for any particular topology. These special processing techniques can be pre-programmed and the user can select them when modeling an object having the relevant topology to ensure that the object is modeled in the way that has been determined, through experimentation, to provide the most accurate model for that topology. Although special processing techniques have only been developed to date for the femur, techniques could be developed for any particular topology. For example, the vertabra and hip bone are objects that are frequently modeled and for which special processing techniques may be developed in the future.
WORMHOLE REMOVAL
Before the SMAP generation process is begun, the contours created during the contour generation process 200 are examined to determine whether any wormholes exist, and to patch any wormholes that are found. A wormhole results from imprecision during the segmentation step 104 and will be described by making reference to FIGS. 23-24.
FIG. 23 shows two contours, defined on adjacent segmented slices of 4.times.10 voxels, that would create a wormhole. FIG. 24 shows the sum of the selected (i.e. set to "1") voxels from slices 5 and 6. As can be seen from FIG. 24, the object has two separate non-contiguous paths that connect the contours that define it on slices 5 and 6. The path w has an area of one voxel and is a wormhole. Wormholes are generated as a result of errors in the segmentation process and create problems in generating a contiguous solid model of the object represented in volumetric data. Therefore, it is desirable to patch (i.e. remove) the wormhole. The wormhole can be patched by filling it in on any one or all of the slices through which it extends. A wormhole is filled in by converting a voxel that was set to "1" during the segmentation process to "0".
The wormholes are removed in the manner described above during step 540 (FIG. 32). Although this step is shown in FIG. 32 as being part of the SMAP generation process, it is essentially a pre-processing step that is performed before the SMAP generation process is begun.
SMAP GENERATION
As stated above, SMAP is an acronym for surface MAP and refers to a data structure created to equivalently describe the object represented in segmented volumetric data. A SMAP essentially describes an object represented volumetrically by voxels as a collection of surface elements that enclose the volume. In the particular embodiment illustrated herein, the surface elements that enclose the volume are planar voxel faces. However, if a different source of volumetric data were utilized that created voxels with non-planar faces, the faces that enclose the object volume would not be planar. Additionally, it should be understood that the surface representation of the object could be generated utilizing surface elements other than voxel faces. For example, larger surface elements can be defined that correspond to multiple voxels rather than utilizing voxel faces that each correspond to a single voxel.
In the particular embodiment illustrated herein, a SMAP is formed by connecting together a plurality of surface voxel faces (hereafter SVOXs). A data structure used to uniquely describe each SVOX is shown in FIG. 25. As shown by this data structure, each voxel is uniquely defined by the x, y and z coordinates of its parent voxel, as well as the orientation of the SVOX on the parent voxel. Each SVOX can have one of the following orientations: top, bottom, front, back, right or left. The data structure for each SVOX also includes the location in memory wherein each of the SVOX's four neighbors are stored as is more fully described below.
Each voxel in the segmented volumetric data representation of the object has the potential to have any of its six planar faces be considered a SVOX in defining a SMAP. When a SMAP is generated for an outer surface of an object, a planar face will be considered as a SVOX if the voxel with which it is associated has a voxel value of "1" (i.e. the voxel is selected) and the voxel adjacent the planar face has a voxel value of "0" (i.e. the adjacent voxel is non-selected). As a result, when an outer SMAP is generated, each planar face that is considered to be a SVOX in the SMAP is located on the outside of the object being modeled. Similarly, when a SMAP is generated for an inner surface of an object, a planar face is considered as a SVOX if the voxel for which it is associated is non-selected and the voxel adjacent the planar face is selected.
An example of a SMAP will now be described making reference to FIG. 26 wherein a 2.times.3.times.4 rectilinear cube is represented by a SMAP. The cube can be represented by a SMAP containing fifty-six SVOXs. Three of the six cube surfaces are visible in FIG. 26 and the visible surfaces are represented by SVOXs SV1-SV26. The three cube surfaces that are not visible in FIG. 26 are represented by an additional twenty-six SVOXs resulting in a total of fifty-two SVOXs to create a SMAP representing the cube. As can be appreciated from FIG. 26, only certain planar faces of the selected voxels are considered as SVOXs when creating the SMAP of the cube. For example, SVOX's SV6 and SV10 define different planar faces of a single voxel. These are the only two planar faces of that voxel which are considered as SVOXs in creating the SMAP. The other four planar faces of the voxel are not considered as SVOXs because they do not define an interface between selected and non-selected voxels. As illustrated in FIG. 26, a characteristic of a SMAP is that each and every SVOX that is part of the SMAP has exactly four neighboring SVOXs that are also part of the SMAP. For example, SVOX SV13 is adjacent to SVOX's SV9, SV14, SV17 and SV25. This characteristic holds true for every SVOX that is included within a SMAP. As was described above in reference to the data structure illustrated in FIG. 25, the locations of its four adjacent SVOXs are included in the definition of each SVOX when a SMAP is generated.
In order to refer to the four adjacencies for each SVOX in a consistent manner, the terms North, South, East and West are defined to represent the four adjacencies for a given SVOX based on its orientation. The definition of these terms depends upon the orientation of the SVOX in a manner shown in FIG. 27. The definitions of the terms North, South, East and West for SVOXs on the front, back, left or right of the SMAP are illustrated in FIG. 27(a). The definitions of the terms North, South, East and West for SVOXs on the top or bottom of the SMAP are illustrated in FIG. 27(b).
A SMAP is generated for any selected surface by the subroutine SMAPGEN that is shown in FIGS. 28-30. Initially, in step 502, the minimum Z slice of the discrete surface that was stored in step 348 of the contour analysis process is examined and the subroutine proceeds to that slice to begin processing. Thereafter, the subroutine proceeds to step 508 wherein, for each voxel enclosed by the contour defining the selected surface on the slice being processed, a bottom facing SVOX is created.
At step 510, the adjacencies for the bottom SVOXs are set. As stated above, the data structure that defines each SVOX includes information relating to the four SVOXs that are adjacent to the defined SVOX. Therefore, in step 510, adjacencies are set for each bottom SVOX indicating which of the other bottom SVOXs created at step 508 are adjacent thereto. In step 512, the subroutine proceeds around the contour defining the surface on the slice being processed and establishes side SVOXs for the surface. A side SVOX can be either a front, back, right or left SVOX. As stated above, the contour on each slice is a set of XY points that defines the outer contour of the surface on that slice. Therefore, side SVOXs are generated on each slice by stepping around the contour and forming a side SVOX for each voxel face that lies along the contour. Once the side SVOXs have been created, the subroutine, at step 514, sets the adjacencies for each side SVOX created at step 512 and also updates the adjacencies for each of the bottom SVOXs that are adjacent to a side SVOX created in step 512. After the completion of step 514, each bottom SVOX is fully defined because each of its four adjacencies have been set.
After the adjacencies for the side and bottom SVOXs are set in step 514, the subroutine proceeds to the next slice in step 516. Thereafter, in step 518, side SVOXs (i.e. front, back, left or right SVOXs) are created around the contour that defines the surface on the slice being processed. After the side SVOXs are created, the subroutine proceeds to step 520 wherein adjacencies are set for each of the side SVOXs created in step 518. Additionally, the adjacencies for each side SVOX on the previous slice that is adjacent to any of the side SVOXs created at step 518 are updated in step 520. As can be appreciated from the foregoing, each time a SVOX is created, the previously created SVOXs that are adjacent thereto are updated to reflect the fact that they are adjacent to the newly created SVOX.
After the side SVOXs are created, the subroutine proceeds to step 522 wherein a determination is made as to whether any upper overhangs exist between the slice being processed and the slice immediately below it. An upper overhang is defined when, for any portion of the surface, the contour on the slice being processed includes an enclosed voxel that is not enclosed by the contour of the surface on the slice immediately below. Overhangs can best be described by making reference to FIG. 31
which is a cross-sectional view of a portion of a surface S. The contour of the surface on slice SL4 encloses some SVOXs at X=1 which are not enclosed by the contour of the surface on slice SL3. Therefore, an upper overhang is defined on slice SL4. In order to connect the side SVOXs defining the surface S on slices SL3 and SL4, a bottom SVOX B is created on slice SL4. FIG. 31 also illustrates a lower overhang formed on slice SL6. A lower overhang is defined when the contour on the slice being processed does not enclose each of the SVOXs that are enclosed by the contour on the slice immediately below it. As shown in FIG. 31, the contour of the surface S on slice SL6 does not include the SVOXs defined at X=1 which are enclosed by the contour on slice SL5. Therefore, a lower overhang is defined on slice SL6. In order to connect the side SVOXs on slices SL5 and SL6, a top SVOX T is created on slice SL5.
When it is determined at step 522 that an upper overhang exists, the subroutine proceeds to step 524 wherein bottom SVOXs are created to connect the side SVOXs on the slice being processed and the slice immediately below it. Thereafter, in step
526, the adjacencies for the bottom SVOXs created at step 524 are set and the adjacencies for all SVOXs adjacent thereto are updated. If it is determined at step 522 that no overhangs exist on the slice being processed, the subroutine proceeds to step
528 wherein a determination is made as to whether any lower overhangs exist. A lower overhang is defined when the contour defining the surface on the slice being processed does not enclose every one of the SVOXs that are enclosed by the contour on the slice immediately below it. If it is determined at step 528 that lower overhangs exist, the subroutine proceeds to step 530 wherein top SVOXs are created for the voxels enclosed by the contour on the slice immediately below the one being processed that are not enclosed by the slice being processed. In this manner, a connection is formed between the side SVOXs on the slice being processed and the slice immediately below it. Thereafter, in step 532, adjacencies are set for the newly created top SVOXs and the adjacencies for each of the SVOXs adjacent thereto are updated.
After the adjacencies for each of the top SVOXs have been set in step 532, or after if it is determined at step 528 that no lower overhangs exist, the subroutine proceeds to step 534 (FIG. 30) wherein a determination is made as to whether the last slice is currently being processed. This determination is made by comparing the slice currently being processed with the maximum Z slice of the discrete surface that was stored during step 348 (FIG. 15) of the contour analysis process. If it is determined at step 534 that the slice being processed is not the last slice, the subroutine returns to step 516 wherein it proceeds to the next slice. In this manner, the subroutine iteratively steps through each slice creating the SVOXs for the SMAP until it is determined at step 534 that the last slice has been processed. At that point, the subroutine proceeds to step 536 wherein top SVOXs are created for each voxel enclosed by the contour on the last slice. Thereafter, in step 538, the adjacencies for the top SVOXs are set and the adjacencies for each SVOX adjacent to a top SVOX created at step 536 are updated. At the completion of step 538, a plurality of SVOXs enclosing the volume of the selected surface has been formed and the subroutine SMAPGEN returns to the portion of the process that called it.
The main steps in the SMAP generation process will now be described making reference to FIGS. 32-37. The first step in the SMAP generation process is to fill in any wormholes at step 540 (FIG. 32) in the manner previously described. Thereafter, in step 542, the first surface of the object is selected and the subroutine SMAPGEN is called to generate a SMAP for the first surface. The subroutine SMAPGEN generates a list of the SVOXs that completely enclose the volume defined by the first surface. When subroutine SMAPGEN is completed, it returns to step 544 of the SMAP generation process wherein a determination is made as to whether a second surface was detected at step 338 of the contour analysis process. If a second surface had been detected, the SMAP generation process proceeds in step 546 to select this second surface and to again call the subroutine SMAPGEN to generate a list of the SVOXs that completely enclose the volume defined by the second surface.
The generation of a SMAP for a particular surface involves not only the creation of a plurality of SVOXs enclosing the volume defined by the surface, but also the generation of North and South poles for the SMAP. The North and South poles of a SMAP are end points that are respectively located at the top and bottom portions of the SMAP. The poles are the points from which the v-lines generated during the reiterative DUV process 600 begin and end as will be more fully described below. Although the poles are utilized primarily during the reiterative DUV process, they are important parameters in defining a SMAP and are generated during the SMAP generation process. The manner in which the poles are generated is dependent upon the classification given to the object during the topological analysis process 400 in a manner that is described below.
There are two basic types of poles which are respectively labeled as flag poles and ring poles. The North flag pole is defined as either (1) the center SVOX of those SVOXs on the highest slice that have a top orientation, or (2) the center SVOX of those SVOXs having a top orientation at a major junction very near the highest slice of the object. A South flag pole is similar to a North flag pole except that it is a SVOX having a bottom orientation that is located on or near the lowest Z slice of the object.
A North ring pole is a ring of all the side SVOXs on the highest Z slice of the object. Similarly, a South ring pole is a ring of all the side SVOXs on the lowest Z slice of the object. When a ring pole is formed, it causes a modification to be made to the plurality of SVOXs generated by the SMAPGEN subroutine. When a North ring pole is formed, the TOP-facing SVOXS on the top slice are not considered to be part of the SMAP and the side SVOXs that had previously pointed to these TOP-facing SVOXs as their northern adjacencies are updated to point to themselves as their northern adjacencies. Similarly, when a South ring pole is formed, the BOTTOM-facing SVOXS on the bottom slice are not considered to be part of the SMAP and the side SVOXs that had previously pointed to these BOTTOM-facing SVOXs as their southern adjacencies are updated to point to themselves as their southern adjacencies.
The determination of whether to use flag or ring poles depends upon the classification that was given to the object during the topological analysis process 400. This classification is also utilized to determine how many SMAPs are generated to represent the object and consequently, the number of pole pairs that must be defined. Table 1 provided below illustrates, for each object classification, the number of SMAPs that will be generated, as well as the type of the poles utilized to define each SMAP. A SMAP can have one of the following pairs of poles:
(1) FF--indicating that the North and South poles utilize the flag method;
(2) RF--indicating that the North pole utilizes the ring method and the South pole utilizes the flag method;
(3) FR--indicating that the North and South poles respectively utilize the flag and ring methods; and
(4) RR--indicating that the North and South poles utilize the ring method.
TABLE 1 ______________________________________ Non-hollow solid One closed outer surface (FF) FIG. 21(a) Enclosed hollow area One closed outer surface (FF) FIG. 21(b) One closed inner surface (FF) Solid having an One open outer surface (RF) opening accessible One open inner surface (RF) from the top A trimmed planar surface is FIG. 21(c) defined at the top Solid having an One open outer surface (FR) opening accessible One open inner surface (FR) from the bottom A trimmed planar surface at FIG. 21(d) the bottom Solid having a hollow One open outer surface (RR) accessible from the One open inner surface (RR) top and bottom Trimmed planar surfaces are FIG. 21(e) also formed at the top and bottom A non-hollow with a Two open outer surfaces (FR) true hole and (RF) FIG. 21(f) The solid is the composition of the two surfaces A non-hollow trimmed One open outer surface (RF) on top A trimmed planar surface is FIG. 21(g) formed at the top A non-hollow trimmed One open outer surface (FR) on bottom A trimmed planar surface is FIG. 21(h) formed on the bottom A solid with an Two open outer surfaces (FR) enclosed hollow and a and (RF) true hole Two open inner surfaces (FR) FIG. 21(i) and (RF) The solid is the boolean subtraction of the composition of the inner surfaces from the composition of the outer surfaces Hollow Y top Three open outer surfaces FIG. 21(j) joined at the outer junction (RR) Three open inner surfaces joined at the inner junction (RR) A trimmed planar surface is formed at the bottom and two trimmed planar surfaces are formed at the top. The solid is the composition of the nine surfaces. Hollow Y bottom Three open outer surfaces FIG. 21(k) joined at the outer junction (RR) Three open inner surfaces joined at the outer junction (RR) A trimmed planar surface is formed at the top and two trimmed planar surfaces are formed at the bottom. The solid is the composition of the nine surfaces ______________________________________
As can be appreciated from the foregoing, multiple SMAPs are generated to represent certain of the object classifications. Although in many cases objects could be generated utilizing a fewer number of SMAPs than is shown in Table 1, it has been found that the reiterative DUV process 600 models some objects having complicated topologies most accurately when several simpler SMAPs are generated. For example, the hollow Y top shown in FIG. 21(g) could be modeled utilizing simply a single outer surface SMAP. However, it has been found that the reiterative DUV process more accurately models an object shaped in this manner as a combination of six SMAPs and three trimmed planar surfaces.
After the SMAPGEN subroutine has returned from generating a SMAP for a second surface at step 546, or if it is determined at step 544 that the object to be modeled does not include a second surface, the SMAP generation process proceeds to step
548 wherein a determination is made as to whether the object has been classified as a hollow Y top or bottom during the topological analysis process 400. If it is determined that the object has not been classified as a hollow Y top or bottom, the SMAP generation process proceeds to step 550 wherein a determination is made as to whether the object has a true hole. If it is determined that the object does not have a true hole, the process proceeds to step 552 (FIG. 33) wherein a determination is made as to whether special processing has been requested. When the SMAP generation process reaches step 552 and special processing is not requested, it indicates that the object is to be modeled utilizing only one or two SMAPs. One SMAP defines the outer surface of the object and, if necessary, a second SMAP defines the inner surface. At step 554, North and South poles are generated for each SMAP. The type of poles generated and the number of SMAPs created is determined in the manner shown in Table 1
based upon the classification of the object that was done during the topological analysis process 400.
The manner in which trimmed planar surfaces are utilized in the generation of a SMAP will now be described utilizing the object classification illustrated in FIG. 21(c) (solid with opening accessible from the top) as an example. As shown in Table 1 above, this type of object will be modeled utilizing SMAPs respectively defining its outer and inner surfaces and a trimmed planar surface at the top of each SMAP. The solid representation of the object is defined as the composition of the three surfaces. The group of interconnected SVOXs generated by the SMAPGEN subroutine for the outer surface will have top facing SVOXs extending across the top slice of the object. This will be understood by the fact that, at step 536 of subroutine SMAPGEN, top SVOXs are generated for each voxel enclosed by the contour of the surface for which the SMAP is being generated. Therefore, when the SMAPGEN subroutine is called from step 542 of the SMAP generation process, it will generate top SVOXs for all voxels enclosed by the contour of the outer surface on the top slice. Similarly, the group of interconnected SVOXs generated by the SMAPGEN subroutine for the inner surface will include top SVOXs on the top slice for the area enclosed within the inner surface. When the North and South poles for each SMAP are generated at step 554 of the SMAP generation process, the top SVOXs for both the inner and outer surfaces are disregarded and a ring pole is formed. The top surface of the object is modeled by a trimmed planar surface which, for an object having this topology, is a flat surface on the top slice consisting of top facing SVOXs extending between the inner and outer surfaces.
When the SMAP generation process proceeds to step 554, the object will be modeled with at most two SMAPs. Therefore, after the North and South poles have been generated for each SMAP at step 554, the SMAP generation process terminates.
When it is determined at step 548 that the object has been classified as a hollow Y top or bottom, the SMAP generation process proceeds to step 558 (FIG. 34) wherein the single group of interconnected SVOXs generated by the SMAPGEN subroutine for the outer surface of the object is separated into three separate groups of SVOXs. The groups of SVOXs are formed based upon the location of the junctions that were described above with regard to the contour analysis process 300. As described above, a junction is defined at a slice wherein a single surface contour is overlapped by two or more distinct contours on an adjacent slice. For a hollow Y top or bottom, a junction is formed at the slice wherein the main stem branches into two separate legs.
During step 558, the group of interconnected SVOXs formed during the SMAPGEN subroutine are split into three groups at the junction. The first group defines the outer surface of the main stem and the second and third groups respectively define the outer surfaces of the legs of the hollow Y top or bottom. The groups of SVOXs are split into two separate legs by examining the slices at the junction and creating two separate chains of overlapping contours that extend from the junction.
After the outer SVOXs have been separated into three groups, the SMAP generation process proceeds to step 560 wherein North and South poles are generated for each of the three groups of SVOXs defined in step 558. As shown in Table 1 above, the North and South poles for each of the three outer SMAPs are generated utilizing the ring pole method.
After the outer three SMAPs are generated, the SMAP generation process proceeds to step 562 wherein the group of interconnected SVOXs generated by the SMAPGEN subroutine for the inner surface of the object is separated into three separate groups. This separation is done based upon the junction of the inner surface of the