System and Method for Performing Domain Decomposition for Multiresolution Surface Analysis

Abstract

A computer-implemented method to process a model of an object includes mapping a mesh representation of the model onto a plane to form a planarized mesh; generating a shape image by associating a shape descriptor with each vertex of the planarized mesh; forming a color image of the planarized mesh by using the shape descriptor to encode a color of each mesh vertex; creating a region map of the color image corresponding to areas of small shape variation; fitting a coarse two dimensional mesh to the region map and computing a target representation from the coarse two dimensional mesh. In the presently preferred embodiment the target representation is expressed as a multiresolution subdivision surface representation. The shape descriptors can include surface normals obtained from the mesh representation and, more generally, can be descriptive of one of surface normal, Gaussian curvature, mean curvature, shape index and curvedness. The colors assigned to the vertices therefore correspond to properties of the three dimensional surface of the object model. Creating the region map includes performing a color segmentation procedure, and in the preferred embodiment identifies clusters of mesh faces corresponding to portions of the mesh in which vertices have approximately the same value of shape descriptor. The process of creating the region map preferably identifies clusters of mesh faces corresponding to connected sets of faces representing aggregate properties of the mesh.

1 . A computer-implemented method to process a model of an object, comprising: 
 mapping a mesh of the model onto a plane to form a planarized mesh;    generating a shape image by associating a shape descriptor with each vertex of the planarized mesh;    forming a color image of the planarized mesh by encoding the shape descriptor as a color for each mesh vertex;    creating a region map of the color image corresponding to areas of small shape variation;    fitting a coarse two dimensional mesh to the region map;    computing a coarse three dimensional base mesh from the two dimensional mesh with faces that approximate regions of relatively constant shape on the input model; and    computing a target three dimensional multiresolution subdivision hierarchy over the three dimensional base mesh, wherein the method is image based and is not simplification based.    
   
   
       2 . A method as in  claim 1 , where mapping comprises parameterizing the input mesh onto a plane.  
   
   
       3 . (canceled)  
   
   
       4 . A method as in  claim 1 , where mapping comprises one of cutting and flattening the mesh, or decomposing the mesh and merging domains.  
   
   
       5 . A method as in  claim 1 , where said shape descriptors are descriptive of one of surface normal, Gaussian curvature, mean curvature, shape index and curvedness.  
   
   
       6 . A method as in  claim 1 , where colors assigned to the vertices correspond to properties of the three dimensional surface of the object model.  
   
   
       7 . A method as in  claim 1 , where creating the region map comprises performing a color segmentation procedure.  
   
   
       8 . A method as in  claim 1 , where creating the region map comprises identifying clusters of mesh faces corresponding to portions of the mesh in which vertices have approximately the same value of shape descriptor.  
   
   
       9 . A method as in  claim 1 , where creating the region map comprises identifying clusters of mesh faces corresponding to connected sets of faces representing aggregate properties of the mesh.  
   
   
       10 . A computer-implemented method to process a three dimensional model of an object, comprising: 
 computing a parameterization p of an input mesh M onto a plane, where P denotes a planarized input mesh and where M represents all or at least a part of the three dimensional model;    constructing a shape map S using P, where the S comprises a two dimensional image having properties selected to encode shape information of the three dimensional model;    identifying regions of small shape variation in S and building a region graph G;    generating a coarse two dimensional polygonal mesh D 2  using G, where D 2  comprises facets approximating the identified regions;    generating a coarse three dimensional mesh D as the image of D 2  through an inverse map p −1 , and computing a target three dimensional multiresolution subdivision hierarchy over the three dimensional mesh D, wherein the method is image based and is not simplification based.    
   
   
       11 . A method as in  claim 10 , where the mesh D comprises an initial base domain, and where a final domain is obtained from D after optimization to adjust positions of its vertices to best fit the input data in a least-squares sense.  
   
   
       12 . A method as in  claim 10 , where the image properties comprise color.  
   
   
       13 . A method as in  claim 10 , where the image properties are expressed using shape descriptors.  
   
   
       14 . A method as in  claim 13 , where computing the parameterization comprises one of cutting and flattening the input mesh, or decomposing the input mesh representation and merging domains.  
   
   
       15 . A method as in  claim 13 , where said shape descriptors are descriptive of one of surface normal, Gaussian curvature, mean curvature, shape index and curvedness.  
   
   
       16 . A method as in  claim 13 , where said shape descriptors are used to assign colors to vertices, where the assigned colors correspond to properties of a three dimensional surface of the object model.  
   
   
       17 . A data processing system for processing a three dimensional model of an object, comprising a computer coupled to a memory and comprising logic for operating in accordance with a stored program for mapping a mesh of arbitrary topology representing the model onto a plane to form a planarized mesh; for generating a shape image by associating a shape descriptor with each vertex of the planarized mesh; for forming a color image of the planarized mesh by encoding the shape descriptor as a color for each mesh vertex; for creating a region map of the color image corresponding to areas of small shape variation; for fitting a coarse two dimensional mesh to the region map; for back-projecting the two dimensional map onto the three dimensional model to obtain a three dimensional base domain; for fitting the three dimensional base domain to the geometry of the three dimensional model; and for computing a multiresolution subdivision surface representation of the object with respect to the three dimensional domain.  
   
   
       18 . A system as in  claim 17 , where said shape descriptors are descriptive of one of surface normal, Gaussian curvature, mean curvature, shape index and curvedness of the model.  
   
   
       19 . A system as in  claim 17 , where colors assigned to mesh vertices correspond to properties of the three dimensional surface of the model.  
   
   
       20 . A system as in  claim 17 , where creating the region map comprises performing a color segmentation procedure, and identifying clusters of mesh faces corresponding to portions of the mesh in which vertices have approximately the same value of shape descriptor.  
   
   
       21 . A computer readable medium storing a computer program the execution of which causes a computer coupled to a memory and comprising logic to process a three dimensional model of an object by mapping a mesh of arbitrary topology representing the model onto a plane to form a planarized mesh; generating a shape image by associating a shape descriptor with each vertex of the planarized mesh; forming a color image of the planarized mesh by encoding the shape descriptor as a color for each mesh vertex; creating a region map of the color image corresponding to areas of small shape variation; fitting a coarse two dimensional mesh to the region map; back-projecting the two dimensional map onto the three dimensional model to obtain a three dimensional base domain; fitting the three dimensional base domain to the geometry of the three dimensional model; and computing a multiresolution subdivision surface representation of the object with respect to the three dimensional domain.  
   
   
       22 . A computer readable medium as in  claim 21 , where said shape descriptors are descriptive of one of surface normal, Gaussian curvature, mean curvature, shape index and curvedness of the model.  
   
   
       23 . A computer readable medium as in  claim 21 , where colors assigned to mesh vertices correspond to properties of the three dimensional surface of the model.  
   
   
       24 . A computer readable medium as in  claim 21 , where creating the region map comprises performing a color segmentation procedure, and identifying clusters of mesh faces corresponding to portions of the mesh in which vertices have approximately the same value of shape descriptor.  
   
   
       25 . A data processing system to process a three dimensional model of an object, comprising means for mapping a mesh of arbitrary topology representing the model to a planarized mesh; means for generating a shape image by associating a shape descriptor with each vertex of the planarized mesh; means for forming a color image of the planarized mesh by encoding the shape descriptor as a color of individual ones of mesh vertices; means for creating a region map of the color image corresponding to areas of small shape variation; means for fitting a coarse two dimensional mesh to the region map; means for projecting the two dimensional map onto the three dimensional model to obtain a three dimensional base domain; means for fitting the three dimensional base domain to the geometry of the three dimensional model; and means for computing a multiresolution subdivision surface representation of the object with respect to the three dimensional domain.  
   
   
       26 . A system as in  claim 25 , where said shape descriptors are descriptive of at least one of surface normal, Gaussian curvature, mean curvature, shape index and curvedness of the model.  
   
   
       27 . A system as in  claim 25 , where colors assigned to mesh vertices correspond to properties of the three dimensional surface of the model.  
   
   
       28 . A system as in  claim 25 , where said means for creating the region map comprises means for performing a color segmentation procedure and identifying clusters of mesh faces corresponding to portions of the mesh in which vertices have approximately the same value of shape descriptor.  
   
   
       29 . A computer readable medium comprising program instructions the execution of which by a computer perform operations to process a model of an object, comprising: 
 providing a representation of the model as an arbitrary triangle mesh M with 2-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.    
   
   
       30 . The computer readable medium of  claim 29 , where the operation of determining the parameterization domain D i  comprises, for a genus zero mesh: 
 parameterizing the mesh over a sphere by assigning spherical coordinates (θ,φ) to each vertex to provide the spherical quantization;    using the spherical parameterization, flattening the surface into the (θ,φ)plane using a cylindrical projection from the sphere to the plane to create a parameterization P i , where the projection defines a map between an original three dimensional surface and a region of the plane which is interpretable as a two dimensional color image;    computing colors of the image by assigning colors to the vertices of a projected two dimensional mesh, where colors assigned to the vertices correspond to at least one property of the original three dimensional surface, where the resulting image having assigned colors comprises a shape map SH i ;    processing SH i  to detect regions of substantially constant shape; and    computing a two dimensional coarse mesh by fitting one of a triangle or quadrilateral mesh to the region map, where each face of the coarse mesh corresponds approximately to a region of constant shape of the shape map SH i , and where an image of the two dimensional coarse mesh gives the parameterization domain D i .    
   
   
       31 . The computer readable medium of  claim 29 , where the resampling operation comprises sampling faces of the base domain using a midpoint subdivision operation to generate grid points G i , i=0, . . . , K−1; where resampling of the geometry of the triangle mesh M with manifold connectivity is performed at a finest level by computing the positions of the vertices corresponding to the generated grid points G i , i=0, . . . , K−1.  
   
   
       32 . The computer readable medium of  claim 31 , where the multiresolution analysis operation comprises, when generating the multiresolution hierarchy from data on the finest level: 
 inputting a resampled mesh R, a course mesh D with K faces, and a number of subdivision levels L;    allocating a subdivision hierarchy S with K mesh faces having the number of L level for a resulting mesh;    assigning the finest level of the multiresolution hierarchy S values computed during the resampling operation; and    computing data on intermediate levels by applying one of a restriction or a smoothing operator; and    for each intermediate level, optimizing positions of the vertices using a relaxation procedure that comprises a least squares fitting of the data at a next resolution level, where coordinates of the next resolution level are computed by subdivision, and multiresolution details are computed as differences between original positions and the positions obtained by subdivision.    
   
   
       33 . A method as in  claim 10 , where computing a target three dimensional multiresolution subdivision hierarchy over the three dimensional base mesh comprises resampling using surface normals.  
   
   
       34 . A method as in  claim 1 , wherein mapping the mesh of the model onto a plane to form a planarized mesh comprises cutting the mesh of the model if the mesh is not of genus 0.  
   
   
       35 . A method as in  claim 34 , wherein the mesh is cut to form a planarized mesh using disc topology.