Patent ID: 7129942

Claim:
A computer-implemented method to process a three dimensional model of an object, comprising: providing a representation of the model as an arbitrary triangle mesh M with manifold connectivity; decomposing the arbitrary triangle mesh M into components C 0 , . . . , C N−1 by extracting geometrically and topologically simpler sub-meshes that are more readily parameterized than the arbitrary triangle mesh M; for each component C i , determining a parameterization domain D i ; merging determined parameterization domains to obtain a parameterization domain D for the arbitrary triangle mesh M, where D is computed as a union of domains D 0 through D N−1 ; resampling the arbitrary triangle mesh M over the domain D; and performing a multiresolution analysis to create a three dimensional multiresolution hierarchy S, where the decomposing operation comprises: converting the model to a binary volumetric representation (V) by enclosing it within a three dimensional grid; identifying grid points that lie within the model; using the volumetric representation (V) to compute a Discrete Distance Transform (DDT) through which each grid point within the model is labeled with the distance to a surface of the model along grid lines; performing a volumetric segmentation of the model by computing a set of region seed values R 0 –R N−1 using the DDT corresponding to the regions of the model of differing thickness; starting from the seed values, employing a distance-driven region growing algorithm to partition the volume within the model into regions corresponding to parts of the model of different thickness; for each volumetric region V i (i=0 to N−1), extracting a corresponding iso-surface C i yielding a mesh representation for that region; and computing the topological genus of each mesh C i , and if a particular mesh C i is not of genus zero, converting the mesh to a genus zero mesh; and displaying the results of the multiresolution analysis.