Method and apparatus for generating hollow and non-hollow solid representations of volumetric data

• US 5,506,785 A
• Filed: 02/11/1993
• Issued: 04/09/1996
• Est. Priority Date: 02/11/1993
• Status: Expired due to Fees

• Current Assignee: Dover Systems Corporation
• Original Assignee: Dover Systems Corporation
• Inventors: Jacobson, Rodney D., Blank, William C.
• Primary Examiner(s): Envall, Jr., Roy N.
• Assistant Examiner(s): BROWN, THOMAS
• Application Number:
  US08/016,705
• Time in Patent Office: 1,153 Days
• Field of Search: 364/468, 364/578, 364/474.24, 395/89, 395/93-95, 395/119-123, 395/124, 395/127, 340/723, 340/728, 340/747
• US Class Current: 700/98
• CPC Class Codes: G06T 17/30 Polynomial surface description

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.

Claims

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.