Methods and systems for generating polycubes and all-hexahedral meshes of an object

Abstract

A method for generating a polycube representation of an input object comprises: receiving an input volumetric representation of the input object; deforming the input volumetric representation to provide a deformed object representation; and extracting, by the processor, a polycube representation of the object from the deformed object representation. Deforming the input volumetric representation to provide the deformed object representation comprises effecting a tradeoff between competing objectives of: deforming the input volumetric representation in a manner which provides surfaces having normal vectors closely aligned with one of the six directions aligned with the set of global Cartesian axes; and deforming the input volumetric representation in a manner which provides low-distortion deformations. Deforming the input volumetric representation to provide the deformed object may be performed iteratively.

What is claimed is: 
     
         1 . A method for generating a polycube representation of an input object, the method comprising:
 receiving, at a processor, an input volumetric representation of the input object;   deforming, by the processor, the input volumetric representation to provide a deformed object representation;   extracting, by the processor, a polycube representation of the object from the deformed object representation, the polycube representation comprising a solid figure made of cubes joined face to face, the solid figure comprising axis-aligned surface planes which having normal vectors that align with one of six directions (±X, ±Y, ±Z) aligned with a set of global Cartesian axes;   wherein deforming, by the processor, the input volumetric representation to provide the deformed object representation comprises effecting, by the processor, a tradeoff between competing objectives of: deforming the input volumetric representation in a manner which provides surfaces having normal vectors closely aligned with one of the six directions aligned with the set of global Cartesian axes; and deforming the input volumetric representation in a manner which provides low-distortion deformations.   
     
     
         2 . A method according to  claim 1  wherein the low-distortion deformations comprise spatially smooth deformations which have computationally optimally low spatial rates of deformation change. 
     
     
         3 . A method according to  claim 1  wherein the low-distortion deformations comprise deformations which are computationally optimally minimized when compared to the input volumetric representation. 
     
     
         4 . A method according to  claim 1  wherein effecting, by the processor, the tradeoff between the competing objectives comprises effecting, by the processor, a computationally optimized balance between the competing objectives of: deforming the input volumetric representation in a manner which provides surfaces having normal vectors closely aligned with one of the six directions aligned with the set of global Cartesian axes; and deforming the input volumetric representation in a manner which provides low-distortion deformations. 
     
     
         5 . A method according to  claim 1  wherein deforming, by the processor, the input volumetric representation to provide the deformed object representation comprises starting with the input volumetric representation as a current model and then iteratively deforming the current model, wherein each iteration comprises effecting, by the processor, a tradeoff between competing objectives of: deforming the current model in a manner which provides surfaces having normal vectors closely aligned with one of the six directions aligned with the set of global Cartesian axes; and deforming the current model in a manner which provides low-distortion deformations to the current model in each iteration. 
     
     
         6 . A method according to  claim 5  wherein, in each iteration, effecting, by the processor, the tradeoff between the competing objectives comprises effecting, by the processor, a computationally optimized balance between the competing objectives of: deforming the current model in a manner which provides surfaces having normal vectors closely aligned with one of the six directions aligned with the set of global Cartesian axes; and deforming the current model in a manner which provides low-distortion deformations to the current model in each iteration. 
     
     
         7 . A method according to  claim 5  wherein the input volumetric representation comprises a polyhedral-mesh representation of the input object, the polyhedral-mesh representation comprising a plurality of notional polyhedrons, each notional polyhedron comprising a corresponding plurality of vertices, a plurality of linear edges that extend between corresponding pairs of vertices and a plurality of polygonal faces defined by corresponding pluralities of edges. 
     
     
         8 . A method according to  claim 1  wherein the input volumetric representation comprises a polyhedral-mesh representation of the input object, the polyhedral-mesh representation comprising a plurality of notional polyhedrons, each notional polyhedron comprising a corresponding plurality of vertices, a plurality of linear edges that extend between corresponding pairs of vertices and a plurality of polygonal faces defined by corresponding pluralities of edges. 
     
     
         9 . A method according to  claim 8  wherein extracting, by the processor, the polycube representation from the deformed object representation comprises:
 labeling, by the processor, each surface face of the deformed object representation with a corresponding one of the six directions aligned with the set of global Cartesian axes; 
 segmenting, by the processor, the surface faces of the deformed object into charts, each chart comprising a contiguous patch of surface faces having the same label; and 
 warping, by the processor, the deformed object representation to output a polycube representation that complies with polycube constraints, wherein warping the deformed object representation comprises adjusting the positions of the vertices of the deformed object representation to obtain updated vertex positions for the polycube representation, such that, for each chart, the updated vertex positions of the surface vertices associated with the chart are constrained to a corresponding plane, the corresponding plane having a normal vector aligned with the one of the six directions aligned with the set of global Cartesian axes corresponding to the chart label. 
 
     
     
         10 . A method according to  claim 9  wherein labeling, by the processor, each surface face comprises, for each surface face, assigning, by the processor, the surface face a label with a corresponding one of the six directions that is most closely aligned with a surface normal vector of the surface face. 
     
     
         11 . A method according to  claim 9  wherein segmenting, by the processor, the surface faces of the deformed object into charts comprises determining if one or more of the charts meets relabeling criteria and, if so, relabeling the one or more of the charts. 
     
     
         12 . A method according to  claim 9  wherein segmenting, by the processor, the surface faces of the deformed object into charts comprises, determining if a particular surface face of the deformed object on a chart boundary has two or more immediately neighboring surface faces which share a common label different from the label of the particular surface face and, if so, relabeling the particular surface face to share the common label of its neighbors. 
     
     
         13 . A method according to  claim 9  wherein warping, by the processor, the deformed object representation to output the polycube representation that complies with polycube constraints comprises performing, by the processor, a computational constrained optimization which determines the updated vertex positions for the polycube representation wherein, for each chart, a constraint is that the updated vertex positions of the surface vertices associated with the chart are constrained to the corresponding plane. 
     
     
         14 . A method according to  claim 9  comprising:
 further adjusting the updated vertex positions of the polycube representation by quantizing the surface vertices of the polycube representation, such that for each chart, the surface vertices associated with the chart and the corresponding plane have common integer chart coordinates along one of the global Cartesian axes aligned with the chart label; and 
 further adjusting the updated vertex positions of the polycube representation to accommodate the quantized surface vertices while, for each chart, maintaining the common integer chart coordinates for the surface vertices associated with the chart. 
 
     
     
         15 . A method according to  claim 7  wherein iteratively deforming the current model comprises, in each iteration:
 for each surface vertex of the current model, determining, by the processor, a surface vertex anchor rotation that would align a normal vector associated with the surface vertex with a corresponding one of the six directions aligned with the set of global Cartesian axes; 
 performing, by the processor, a computational optimization which determines interior rotations for each of the interior vertices of the current model and which modifies the surface vertex anchor rotations to provide updated surface rotations for each of the surface vertices of the current model; 
 applying, by the processor, the interior rotations to the interior vertices and the updated surface rotations to the surface vertices to determine an iteration output model with new vertex positions; and 
 setting the iteration output model to be the current model for the next iteration. 
 
     
     
         16 . A method for generating a hex-mesh representation of an input object, the method comprising:
 generating, by the processor, a polycube representation of the input object in accordance with the method of  claim 1 ; and   determining, by the processor, a hex-mesh representation of the input object based on the polycube representation of the input object.   
     
     
         17 . A method according to  claim 16  wherein using the generated polycube representation to determine a hex-mesh representation of the input object comprises:
 generating, by the processor, parameterizations of points on a hexahedral grid corresponding to the polycube representation in a polycube domain; and 
 applying the parameterizations to the input volumetric representation in an input model domain to form the hex-mesh representation. 
 
     
     
         18 . A method according to  claim 17  wherein the points on the hexahedral grid corresponding to the polycube representation in the polycube domain comprise the vertices of hexahedrons in a hex-mesh in the polycube domain and wherein applying the parameterizations to the input volumetric representation in the input model domain generates corresponding vertices of hexahedrons in the input model domain. 
     
     
         19 . A system for generating a polycube representation of an input object, the system comprising a processor configured to perform the method of  claim 1 . 
     
     
         20 . A non-transitory computer-readable medium comprising instructions which when executed by a processor cause the processor to perform the method of  claim 1 .