Methods and apparatus for performing sampling based synthesis of three-dimensional geometric models

• US 6,278,457 B1
• Filed: 01/15/1998
• Issued: 08/21/2001
• Est. Priority Date: 01/15/1998
• Status: Expired due to Term

• Current Assignee: GlobalFoundries, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Borrel, Paul, Bernardini, Fausto, Menon, Jai P.
• Primary Examiner(s): SEALEY, LANCE W
• Application Number:
  US09/007,682
• Time in Patent Office: 1,314 Days
• Field of Search: 345/420, 345/423, 345/428, 345/419
• US Class Current: 345/420
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation

Abstract

A presently preferred computer implemented method for generating a simplified model of a geometric model includes a first step of visualizing a geometric model from at least one viewpoint and then sampling surfaces of the visualized geometric model, from the at least one viewpoint, to generate a set of primary sample points. A next step executes a polyhedral synthesis technique using the set of primary sample points by the steps of performing a three dimensional Delaunay triangulation of the primary sample points to generate triangles; performing alpha-solid extraction using the generated triangles; and executing a boundary computation on the extracted alpha-solid to obtain the simplified model. An optional step refines the simplified model using a set of secondary sample points.

Claims

1. A computer implemented method for generating an approximation of a geometric model of an object, comprising the steps of:

rendering the geometric model from a plurality of viewpoints to obtain a corresponding plurality of only surface views of the visible surface of the geometric model, the surface views being selected so as to mask parts of the object;

obtaining, from the plurality of surface views, a set of surface sample points; and

synthesizing a triangle mesh that interpolates the sample points for approximating the shape of the geometric model.

2. A method as in claim 1, wherein the step of synthesizing includes steps of:

computing a three dimensional triangulation of the sample points;

in accordance with the triangulation, using alpha-solids to select a subset of tetrahedra which approximate the shape of the geometric model; and

using a boundary of the selected subset of tetrahedra as the approximation of the geometric model.

3. A method as in claim 1, wherein the step of obtaining includes steps of:

for selected surface sample points, determining an associated depth value; and

transforming device coordinates for each selected surface sample point to model world coordinates.

4. A method as in claim 1, wherein said surface views are selected so as to mask internal details of the object.

5. A computer implemented method for generating a simplified model of a geometric model of an object, comprising the steps of:

sampling only visible surface views of the geometric model from at least one viewpoint to generate a set of primary sample points, said sample points being selected so as to mask parts of the object; and

executing a polyhedral synthesis using the set of primary sample points by the steps of,

performing a three dimensional Delaunay triangulation of the primary sample points to generate triangles;

performing alpha-solid extraction using the generated triangles; and

obtaining the simplified model from the boundary of the extracted alpha-solid.

6. A method as in claim 5, and further comprising a step of refining the simplified model using a set of secondary sample points.

7. A method as in claim 5, and further including a step of incorporating attribute information into the simplified model.

8. A method as in claim 5, wherein a plurality of sets of primary sample points are generated to produce a hierarchy of simplified models.

9. A method as in claim 5, wherein the step of sampling surfaces of the geometric model and the step of executing a polyhedral synthesis are performed with one data processor.

10. A method as in claim 5, wherein the step of sampling surfaces of the geometric model is performed with one data processor, and wherein the step of executing a polyhedral synthesis is performed with another data processor.

11. A method as in claim 5, wherein sample points are incrementally added so as to incrementally extend a triangle mesh on the surface by one new triangle, and wherein the new triangle is connected to the existing boundary of the triangle mesh.

12. A method as in claim 11, wherein sample points are incrementally added by projecting each additional point to a closest face in the boundary of the alpha-solid, retriangulating the face to accommodate the sample point which has been added, and reprojecting the sample points which have been added back to their original position.

13. A method as in claim 5, wherein said sample points are selected so as to mask internal details of the object.

14. A data processing system, comprising:

a rendering unit and display for visualizing an object model from at least one viewpoint;

a sampling unit for sampling only visible surface views of the visualized object model to generate a set of primary sample points, said sample points being selected so as to mask parts of the object; and

an execution unit for executing a polyhedral synthesis using the set of primary sample points, said execution unit comprising means for performing a three dimensional Delaunay triangulation of the primary sample points;

means for performing alpha-solid extraction using the Delaunay triangulation; and

means for obtaining a simplified object model from the boundary of the extracted alpha-solid.

15. A data processing system as in claim 14, wherein said execution unit further comprise means for refining the simplified model using a set of secondary sample points.

16. A data processing system as in claim 14, wherein said rendering unit is comprised of a z-buffer, and wherein said sampling unit obtains said primary sample points by transforming x, y, z display coordinates of each primary sample point to world coordinates on said object model.

17. A data processing system as in claim 14, wherein said sampling unit samples said points so that internal details of the object are masked.