Methods, apparatus and computer program products for automatically generating nurbs models of triangulated surfaces using homeomorphisms
First Claim
1. A computer-implemented method of modeling a three-dimensional surface of an object, comprising the steps of:
- generating from an initial triangulation of the surface, a hierarchy of progressively coarser triangulations of the surface by performing a sequence of edge contractions to the initial triangulation;
connecting the triangulations in the hierarchy using homeomorphisms; and
homeomorphically mapping edges of a triangulation in the hierarchy back to the initial triangulation.
5 Assignments
0 Petitions
Accused Products
Abstract
Embodiments automatically generate an accurate network of watertight NURBS patches from polygonal models of objects while automatically detecting and preserving character lines thereon. These embodiments generate from an initial triangulation of the surface, a hierarchy of progressively coarser triangulations of the surface by performing a sequence of edge contractions using a greedy algorithm that selects edge contractions by their numerical properties. Operations are also performed to connect the triangulations in the hierarchy using homeomorphisms that preserve the topology of the initial triangulation in the coarsest triangulation. A desired quadrangulation of the surface can then be generated by homeomorphically mapping edges of a coarsest triangulation in the hierarchy back to the initial triangulation. This quadrangulation is topologically consistent with the initial triangulation and is defined by a plurality of quadrangular patches. These quadrangular patches are linked together by a (U, V) mesh that is guaranteed to be continuous at patch boundaries. A grid is then preferably fit to each of the quadrangles in the resulting quadrangulation by decomposing each of the quadrangles into k2 smaller quadrangles. A watertight NURBS model may be generated from the resulting quadrangulation.
116 Citations
36 Claims
-
1. A computer-implemented method of modeling a three-dimensional surface of an object, comprising the steps of:
-
generating from an initial triangulation of the surface, a hierarchy of progressively coarser triangulations of the surface by performing a sequence of edge contractions to the initial triangulation; connecting the triangulations in the hierarchy using homeomorphisms; and homeomorphically mapping edges of a triangulation in the hierarchy back to the initial triangulation. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
7. A computer-implemented method of modeling a three-dimensional surface of an object, comprising the steps of:
-
generating from an initial triangulation of the surface, a hierarchy of progressively coarser triangulations of the surface by decimating the initial triangulation using a sequence of edge contractions that are prioritized by an error function that measures a respective error caused by the edge contractions in the sequence; connecting the triangulations in the hierarchy using homeomorphisms; and homeomorphically mapping edges of a coarsest triangulation in the hierarchy back to the initial triangulation. - View Dependent Claims (8, 9)
-
-
10. A computer-implemented method of modeling a three-dimensional surface of an object, comprising the steps of:
-
generating from an initial triangulation of the surface, a hierarchy of progressively coarser triangulations of the surface by repeatedly decimating the initial triangulation using a sequence of edge contractions that are prioritized by an error function that measures a respective error caused by each of the edge contractions in the sequence, until a coarsest triangulation having a target density of triangles therein is achieved; connecting the triangulations in the hierarchy using homeomorphisms; and homeomorphically mapping edges of the coarsest triangulation in the hierarchy back to the initial triangulation. - View Dependent Claims (11, 12, 13, 14, 15)
-
-
16. A computer-implemented method of generating a three-dimensional model of an object, comprising the steps of:
decomposing an initial triangulation of the model into a quadrangulation of the model defined by a plurality of quadrangular patches that are joined together at patch boundaries by; generating from the initial triangulation of the model a hierarchy of progressively coarser triangulations of the model using a sequence of edge contractions to the initial triangulation; connecting the triangulations in the hierarchy using homeomorphisms; homeomorphically mapping edges of a coarsest triangulation in the hierarchy back to the initial triangulation; and converting the mapped coarsest triangulation to the quadrangulation by matching pairs of adjacent triangles In the coarsest triangulation. - View Dependent Claims (17, 18)
-
19. A computer-implemented method of modeling a three-dimensional surface of an object, comprising the steps of:
-
converting a first triangulation of the surface into a second triangulation of the surface by contracting a first edge in the first triangulation; determining a fuzzy rank associated with the first edge contraction; and determining a simplicial homeomorphism based on the fuzzy rank.
-
-
20. A computer-implemented method of modeling a three-dimensional surface of an object, comprising the step of:
converting an initial triangulation of the surface into a quadrangulation of the surface that is homeomorphic to the triangulation by; generating from the initial triangulation a hierarchy of progressively coarser triangulations of the surface by performing a sequence of edge contractions to the initial triangulation; and mapping edges of a triangulation in the hierarchy back to the initial triangulation. - View Dependent Claims (21, 22)
-
23. A computer program product that models a three-dimensional surface of an object and comprises a computer-readable storage medium having computer-readable program code embodied in said medium, said computer-readable program code comprising:
-
computer-readable program code that generates from an initial triangulation of the surface, a hierarchy of progressively coarser triangulations of the surface by performing a sequence of edge contractions to the initial triangulation; computer-readable program code that connects the triangulations in the hierarchy using homeomorphisms; and computer-readable program code that homeomorphically maps edges of a coarsest triangulation in the hierarchy back to the initial triangulation. - View Dependent Claims (24)
-
-
25. A computer program product that models a three-dimensional surface of an object and comprises a computer-readable storage medium having computer-readable program code embodied in said medium, said computer-readable program code comprising:
-
computer-readable program code means that generates from an initial triangulation of the surface, a hierarchy of progressively coarser triangulations of the surface by decimating the initial triangulation using a sequence of edge contractions that are prioritized by a quadratic error function that measures a respective error caused by each of the edge contractions in the sequence; computer-readable program code means that connects the triangulations in the hierarchy using homeomorphisms; and computer-readable program code means that homeomorphically maps edges of a coarsest triangulation in the hierarchy back to the initial triangulation. - View Dependent Claims (26, 27)
-
-
28. An apparatus that generates models of objects, comprising:
means for decomposing an initial triangulation of a model into a quadrangulation of the model defined by a plurality of quadrangular patches that are joined together at patch boundaries, said decomposing means comprising; means for generating from the initial triangulation of the model a hierarchy of progressively coarser triangulations of the model using a sequence of edge contractions to the initial triangulation; means for connecting the triangulations in the hierarchy using homeomorphisms; means for homeomorphically mapping edges of a coarsest triangulation in the hierarchy back to the initial triangulation; and means for converting the mapped coarsest triangulation to the quadrangulation by matching pairs of adjacent triangles in the coarsest triangulation. - View Dependent Claims (29, 30)
-
31. A computer-implemented method of modeling a three-dimensional surface of an object, comprising the steps of:
-
generating from an initial triangulation of the surface, a hierarchy of progressively coarser triangulations of the surface by performing a sequence of edge contractions to the initial triangulation using a greedy algorithm that selects edge contractions by their numerical properties; connecting the triangulations in the hierarchy using homeomorphisms; and homeomorphically mapping edges of a triangulation in the hierarchy back to the initial triangulation.
-
-
32. A computer program product comprising a computer-readable storage medium having computer-readable program code embodied in said medium, said computer-readable program code comprising:
-
computer-readable program code means configured to generate from an initial triangulation of a three-dimensional surface derived from measurement data collected by digitizing a physical object or sampling a digital representation of an object, a hierarchy of progressively coarser triangulations of the surface by decimating the initial triangulation using a sequence of edge contractions; computer-readable program code means configured to connect the progressively coarser triangulations in the hierarchy using homeomorphisms; computer-readable program code means configured to homeomorphically map edges of a triangulation in the hierarchy of progressively coarser triangulations back to the initial triangulation; computer-readable program code means configured to convert the triangulation into a quadrangulation by matching pairs of adjacent triangles in the triangulation; and computer-readable program code means configured to fit a respective grid to each of a plurality of quadrangles in the quadrangulation. - View Dependent Claims (33, 34)
-
-
35. An apparatus for modeling three-dimensional objects, comprising:
-
means configured to generate from an initial triangulation of a three-dimensional surface, a hierarchy of progressively coarser triangulations of the surface by decimating the initial triangulation using a sequence of edge contractions; means for connecting the triangulations in the hierarchy using homeomorphisms; means for homeomorphically mapping edges of a triangulation in the hierarchy of progressively coarser triangulations back to the initial triangulation; means for converting the triangulation into a quadrangulation by matching pairs of adjacent triangles in the triangulation; and means for fitting a respective grid to each of a plurality of quadrangles in the quadrangulation. - View Dependent Claims (36)
-
Specification