Three-dimensional models of input objects may be digitally modeled (e.g. on a computer system and/or other suitable processor(s)) in volumetric representations known as tetrahedral-meshes or “tet-meshes”. There are techniques known in the art for obtaining tet-mesh representations of objects. For example, isotropic volumetric tet-meshes can be generated from isotropic surface meshes using known software, such as Tetgen™. Non-isotropic surface meshes can be re-meshed using known software such as Graphite™ and the re-meshed surface meshes may then be used to generate suitable volumetric tet-meshes.
It can be desirable to generate polycubes (orthogonal polyhedral) or polycube representations of input objects. A polycube is a solid formed by joining several cubes face to face. Polycubes may be used as base complexes for parameterizing closed surfaces and volumes. Non-limiting examples of uses for polycube representations include: surface texture mapping (see TARINI, M., HORMANN, K., CIGNONI, P., AND MONTANI, C. 2004. PolyCube-Maps. ACM Transactions on Graphics 23, 3 (August), 853-860. Proc. of ACM SIGGRAPH 2004; and YAO, C., AND LEE, T. 2008. Adaptive geometry image. IEEE Transactions on Visualization and Computer Graphics 14, 4, 948-960); hexahedral meshing (see GREGSON, J., SHEFFER, A., AND ZHANG, E. 2011. All-hex mesh generation via volumetric polycube deformation. Computer Graphics Forum (Proc. SGP) 30, 5; and XIA, J., HE, Y., YIN, X., HAN, S., AND GU, X. 2010. Direct product volumetric parameterization of handle bodies via harmonic fields. In Proc. Shape Modeling International, IEEE, 3-12); trivariate spline fitting (see WANG, H., HE, Y., LI, X., GU, X., AND QIN, H. 2007. Polycube splines. In Proc. Symposium on Solid and physical modeling, 241-251); and volumetric texturing (see CHANG, C.-C., AND LIN, C.-Y. 2010. Texture tiling on 3d models using automatic polycube-maps and wang tiles. J. Inf. Sci. Eng. 26, 1, 291-305).
Polycubes are used in computer graphics applications because they may allow for efficient storage of geometry and/or texture information generally, and may specifically provide relatively regular and/or compact representations of graphical objects. Such representations can confer certain advantages in some computer-implemented graphical systems; for example, in some circumstances, such representations may be conveniently cached, allow for relatively straightforward texture filtering, and provide smooth face boundaries for texturing applications. Polycubes also find application in GPU subdivision and multiresolution representations, and can serve as intermediate primitives for quad meshing or hex meshing operations.
There is a general desire for methods and systems for converting input mesh representations of objects (e.g. tet-meshes) into polycube representations. A difficulty associated with generating polycube representations of input objects involves addressing the tradeoff between parametrization distortion and compactness. Parameterization distortion represents the distortion between the surface geometry of the input object and the surface geometry of the polycube representation. There is a general desire to provide a polycube representation with a low amount of parameterization distortion. Compactness may be indicated by the number of polycube faces and/or the number of singularities (corners of the polycube faces) and/or the length of the boundaries between polycube faces of the polycube representation. There is a general desire to provide a compact polycube representation (i.e. correspondingly low polycube face counts and/or singularity counts and/or correspondingly short chart boundaries). Compact polycube representations permit relatively low element counts for applications such as hex meshing, volume fitting and/or surface fitting.
Because of the difficulty associated with managing the tradeoff between parameterization distortion and polycube face or singularity counts, most techniques for generating and using polycube representations rely on manual and/or semi-manual construction of polycubes. Once generated, these (semi-)manually constructed polycubes may be processed by a computer system. However, it is desirable to have a computational approach for generating polycube representations so that computer systems may generate high-quality polycube constructions programmatically.
A prior art technique for programmatically generating polycube representations proposed by Gregson et al. (GREGSON, J., SHEFFER, A., AND ZHANG, E. 2011. All-hex mesh generation via volumetric polycube deformation. Computer Graphics Forum (Proc. SGP) 30, 5) used the angles between normal vectors of the surface vertices of the input mesh and the polycube axes as an implicit measure of parameterization distortion. This measure of distortion estimates the distortion caused by flattening each chart and rotating the charts so that they form polycube faces having ninety degree dihedral angles with one another.
A polycube segmentation of an input model corresponding to an input object may be used herein to describe an assignment of a polycube axis label (±X,±Y,±Z) to each outer surface face (e.g. each triangular surface face in the case of a tet-mesh model) on a surface of the object. Within a polycube segmentation, contiguous groups of surface faces (e.g. surface triangles) that are assigned the same label may be referred to herein as charts. A polycube representation (or, for brevity, a polycube) may be extracted from a polycube segmentation. When a polycube is extracted from a polycube segmentation, the charts of the polycube segmentation become the planar and axis-aligned surface faces of the polycube and the labels of the charts of the polycube segmentation become the directions of the normal vectors of the polycube faces.
When generating polycube representations, an additional source of parameterization distortion comes from the shape and directionality of chart boundaries of the polycube segmentation and the need to map chart boundaries of the polycube segmentation to the axis-aligned straight edges of the polycube. A chart boundary of a polycube segmentation may be defined between a pair of adjacent charts to be a sequence of edges shared by triangles belonging to the two different charts. In a polycube, such a boundary maps to an axially aligned straight boundary between a pair of polycube faces corresponding to the pair of charts. Since the faces of a polycube are oriented to have normal vectors aligned with the Cartesian axes (±X,±Y,±Z), it follows that the boundary between a pair of polycube faces having normal vectors along first and second Cartesian axes, should be oriented along the third Cartesian axis. For example, if two adjacent polycube faces have normal vectors oriented in the +X and +Y directions, the boundary between the pair of polycube faces will be oriented along the Z-axis and should have either a +Z direction or a −Z direction.
The Gregson et al. technique, which does not account for the shape and directionality of chart boundaries, tends to generate polycube segmentations having non-monotone boundaries. For a particular polycube segmentation, non-monotone chart boundaries are chart boundaries where the direction of the boundary switches sign with respect to the axis along which it should be oriented. Following with the preceding example where a pair of adjacent polycube faces has normal vectors oriented in the +X and +Y directions, we would expect that those polycube faces correspond to charts in a polycube segmentation where the charts were assigned +X and +Y labels. As discussed above, the boundary between these polycube faces should be oriented along the Z axis (i.e. either +Z or −Z). Accordingly, we would expect that the boundary between the corresponding charts should be oriented either in a +Z direction or a −Z direction. This chart boundary is considered to be non-monotone if its directionality changes from a +Z orientation to a −Z orientation or from a −Z direction to a +Z direction.
The locations where a non-monotone chart boundary changes sign with respect to the axis along which it should be oriented may be referred to as turning points. FIG. 1 is a schematic representation of a number of views of a polycube segmentation 4 of an input object 2 showing the charts of the polycube segmentation (as differently colored regions). The charts of the FIG. 1 segmentation comprise a number of turning points and, consequently, are non-monotone. Mapping a non-monotone chart boundary having a turning point to a corresponding polycube edge (which is straight and axis-aligned) involves introducing extreme distortion.
Accordingly, there is a general desire to generate polycube segmentations that have all-monotone boundaries (i.e. boundaries without turning points). However, computationally generating polycube segmentations with all-monotone boundaries presents significant technical challenges, as the number of possible segmentations (and thus the number of possible boundary definitions) increases exponentially with the number of elements in the tet-mesh. Further, existing approaches can, in some circumstances, provide relatively low gains in compactness for corresponding increases in parametrization distortion (and vice-versa). Accordingly, there is a general desire for computational approaches to polycube segmentation generation which provide improved efficiency and/or improved tradeoffs between parametrization distortion and compactness.
The foregoing examples of the related art and limitations related thereto are intended to be illustrative and not exclusive. Other limitations of the related art will become apparent to those of skill in the art upon a reading of the specification and a study of the drawings.