Content-aware model resizing with symmetry-preservation

Abstract

This paper presents a new model resizing approach intended for preservation of important geometric content and geometric symmetries of the model to be resized. We first extract high-level symmetric regions and other low-level salient regions from the input model. Then, we map the extracted low-level and high-level geometry information to a protective tetrahedral mesh around the model, and we define a symmetry-preserving and content-aware resizing function on the tetrahedral mesh using 3D mean value coordinates space deformation. By interpolating within the resized tetrahedral mesh, we obtain the final resizing results for the embedded model. Interactively defined user constraints are also incorporated into our framework to produce more desirable results. Our results show that the resized models preserve the geometric features of important regions in addition to the symmetric aspects of the original model, and eliminate the undesirable distortion in other less important regions.

1 Introduction

Digital 3D models can be acquired from a variety of methods, such as reconstruction from 2D images, 3D data scanning, and CAD geometric modeling. However, the creation of models is a very tedious work, especially when complex models are needed. An alternative modeling approach is to reuse existing geometric models with manipulative controls for related applications, such as model assembly, engineering designs, and digital entertainment. One of the ways to reuse models is to resize them to fit other models or geometric scenes. However, model resizing is non-trivial work, especially for content-aware resizing that resizes the model while preserving important geometric regions and structures as well. Resizing by simply applying a naive global non-uniform scale usually cannot produce desirable results, because models constructed from multiple parts would be unavoidably distorted by the scaling, without effectively distributing the distortion of resized parts. Non-homogeneous model resizing [13] based on surface vulnerability works well for resizing some complex models such as mechanical models. However, it may not produce desirable resizing results to preserve the local or global symmetric regions of original models, as shown in Figs. 1 and 6.

An effective content-aware model resizing method, which resizes the model according to the content of the model or the designer’s intent, should have the following properties: (1) Preservation of important geometric content and structure. For example, geometric symmetry should be preserved to generate visually natural results. (2) Convenient user controls. User controls are also important to create the desirable results according to the user’s intent. (3) Minimization of resizing distortion artifacts. With the important parts well preserved, the resizing distortion should be distributed non-homogeneously throughout the model, and the visual artifacts should be eliminated as much as possible.

Fig. 1

Model resizing using geometric symmetry. a Original model, b non-homogeneous resizing [13], c original model with symmetric regions, d our resizing result using geometric symmetry

In this paper, to address the aforementioned issues, we present a new model resizing method based on content-aware space-deformation approach with symmetry-preservation. The geometry content of a model is based on the surface importance measure. We evaluate the surface importance from both the low-level and high-level geometry information. The low-level geometry analysis includes the differential surface properties, such as the surface curvature, slippage analysis [10], and surface saliency [14]. The high-level information used in our method is the geometric symmetry of the model. Most natural and man-made objects exhibit significant partial or approximate symmetries. Thus, when resizing geometric models, it is important to keep the geometric symmetries in the resized models for generating convincing results.

To process complex models with multiple components and non-manifold structures, our model resizing approach works as a space-deformation technique by embedding the input model into a protective box. We embed the model into a protective volumetric mesh, which is a tetrahedral mesh. By converting the surface importance values to tetrahedron cell values, we perform content-aware resizing on the protective box, and the model is resized according to the cell’s importance. The symmetry-preserving and content-aware resizing function on the protective mesh is defined using 3D mean value coordinates (MVC) parameterization. With a progressive content-aware resizing optimization, the protective mesh is resized into the target mesh, preserving the geometric saliency and geometric symmetry well. By transferring the resizing result of protective mesh via MVC back to the triangular mesh (interpolating process), we obtain the final model resizing result. User specified constraints are also incorporated into our framework to produce user desirable results. The diagram in Fig. 2 illustrates all the steps taken to resize an object/model.

Our model resizing method based on content-aware space-deformation in not new. The main contributions of our model resizing work is that we incorporate symmetry information and user interactions in the space-deformation system, which produce symmetry-preserving resized results, also following the designer’s intent.

Fig. 2

Diagram of the presented algorithm

2 Related work

Content-aware image and video resizing has attracted much attention in recent years, and many methods have been presented, see [5, 26, 29] and the references therein. Several 3D model resizing/retargeting methods also have been presented. The non-homogeneous method [13] embedded the input mesh into a protected grid, by evaluating the vulnerability of each cube, this method can produce convincing content-protected scaling results. However, this method did not take the high level information such as symmetry into account. Wang and Zhang [28] presented a model resizing method based on surface deformation. The method avoided using an auxiliary regular grid, and directly deformed the mesh models according to local sensitivity to geometric scaling, which can process single manifold surface but unable to resize complex models consisting of multiple components. Chen and Meng [5] presented a model resizing method based on geometric texture transfer, which automatically preserved geometric textures during the model resizing process. More recently, Lin et al. [20] retargeted the irregular 3D architecture models by performing automatic replication and scaling of the specified structural elements as well as preserving their structures. Different from Lin et al. [20], our method performs content-aware model resizing, and will not modify the structure of the models.

Resizing can be viewed as a special case of model deformation. Surface-based mesh deformation methods have been widely used in mesh editing and animation [4, 33]. These methods target the preservation of surface details on single-component models, i.e., a single connected mesh. Although potentially applicable to multiple components, these methods do not provide a mechanism to handle the spatial relationships between components. Traditional space deformation algorithms largely assume that an embedded object usually consists of multiple components [9]. There are 3D models, particularly those of man-made CAD objects, consisting of multiple components. Thus, the spatial relationships between components after deformation should be explored. Lately, research is progressing in making geometric deformations more content-aware, such as material-aware mesh deformation [24], and joint-aware deformable model manipulation [32].

Shape analysis has been widely used in mesh segmentation [17, 19], viewpoint selection, geometry reconstruction [18], shape retrieval, and content aware model resizing [10, 14, 15]. Gelfand and Guibase [10] provided a slippage motion analysis tool to detect rotationally and translationally symmetrical shapes, often found in mechanical models. Lee et al. [14] measured saliency as a combination of curvature at different scales, to measure the visual importance of surface details. Li and Guskov [15] detected a set of salient feature points using a scale-space representation. As for high-level geometry information, a variety of geometry symmetry detection and extraction algorithms have been presented [21–23, 31] (see [31] for a survey). These algorithms focused on analyzing partial and approximate symmetries, and utilized symmetries in shape analysis and geometry processing. Partial symmetries of the model also have been used in inverse procedural modeling [1], pattern-aware shape deformation [2] and parameterized shape editing [3]. Different from our methods, these methods explored structure-aware shape editing, altered the topology of the objects.

Mean-value coordinates are widely used in geometry and image processing. Floater [6] introduced MVC which is motivated by the Mean-value theorem for harmonic functions. These coordinates approximate a harmonic-like solution to the boundary interpolation problem. They are well defined over the entire plane for arbitrary planar polygons without self-intersections, smooth ($C^{\infty }$ except at the polygon vertices where they are $C^0$), and invariant under similarity transformations [11]. MVC coordinates have also been extended to 3D polyhedra and used for space deformation [7, 12]. More recently, Li et al. [16] presented cubic MVC for interpolating both boundary values and gradients over a 2D polygonal domain, and obtained impressive results. In this work, we explore the novel use of MVC as deformation and deformation transferring tool for solving complex model resizing.

3 Content-aware protective mesh construction

In this section, we first introduce the surface shape analysis used in our approach, then construct the content-aware protective mesh for the underlying model.

3.1 Surface shape analysis

For content-aware model resizing, it is important to preserve the important regions. We detect the salient geometry regions as the important ones, and compute the geometry saliency using the mesh saliency measure [14]. Based on the mean curvature at mesh vertices, the saliency $E_{S}(\nu )$ of each vertex $\nu$ of the input model $M$ is computed as the difference between mean curvatures filtered with narrow and broad Gaussian functions. In model resizing, for each given scaling direction, we distinguish regions that can scale non-uniformly along the given direction and those vulnerable to such scale. We define local surface vulnerability $E_{V}^u$ using [13] which analyzes a combination of local differential surface properties.

Many natural and man-made objects consist of significant symmetric substructures. It is important to preserve the geometric symmetry to obtain visually natural resized results. For one part $S$ of the input 3D model, we employ the method [22] to extract its partial or approximate symmetric region $S^{*}$ on geometric models. For each sample $p$ on the part $S$, we find the corresponding point $s$ on $S^{*}$, and the point pair $(p,s)$ is symmetric about the transformation $T_{ij}$, which can be translation, rotation, reflection, and uniform scaling [22]. As symmetry detection using mean shift clustering [22] is time-consuming, we use method [30] to accelerate the clustering step during symmetry detection, which can receive interactive clustering speed for models with moderate size.

3.2 Tetrahedral mesh construction

Similar to [13], we employ a space deformation strategy to perform model resizing, and construct a protective volume (a rectangular bounding box) for the underlying model. This enables to process complex models consisting of multiple components, and facilitates preservation of spatial relationships among parts.

Unlike [13] which builds a protective volumetric grid for the underlying model, we construct a protective tetrahedral mesh that works well for our method. Firstly, we take tetrahedral mesh as the protective box because it is convenient for defining 3D MVC, which works for content-aware optimization and vertex position interpolation in our system. Secondly, one benefit of tetrahedral mesh over uniform lattice grid is that we can define adaptive tetrahedral mesh adapted to the input model, for example, different solutions can be applied to different regions of the model according to their importance, thus, tetrahedral mesh is more flexible and adaptive. As shown in Fig. 3, we construct denser meshes for the barbell regions of the model. Finally, tetrahedral mesh can approximate the 3D model better than the grid using a smaller number of elements, since the tetrahedral mesh is more flexible to approximate a complex object.

Fig. 3

Tetrahedral mesh construction: a Input model, b uniform tetrahedral mesh, c adaptive tetrahedral mesh

We first define a bounding box (according to the size of the model) for the input triangular mesh model $M=\{V, E_{M}, F_{M}\}$, where $V = \{v_1,v_2,\dots ,v_m\} \in R^3$ is the set of vertex positions of the $M$, $m$ is the number of the vertices of $M$, and $E_{M}$ and $F_{M}$ are the edges and triangle faces of $M$. Then we employ the TetGen [27], a tetrahedral mesh generator, to generate a tetrahedral mesh $H = \{P, E_{H}, F_{H}\}$ for the box, where $P = \{p_1,p_2,\dots ,p_n\} \in R^3$ is the set of vertex positions of the tetrahedral meshes $H$, where $n$ is the number of the vertices of $H$, and $E_{H}$ and $F_{H}$ denote the edges and tetrahedron faces, respectively. The new deformed vertex positions of $H$ are denoted by $P^{'}= \{p_1',p_2',\dots ,p_n'\} \in R^3$, and the connectivity stays the same during the optimization process. Figure 4b shows the generated tetrahedral meshes for model (Fig. 4a) using the presented method [27] (Note that we give the cross section).

Fig. 4

Protective mesh construction and resizing. a Original model, b protective mesh constructed on model (a), c our resized result, d the resized protective mesh

We transfer the surface importance value (saliency, vulnerability) of model $M$ to the tetrahedral meshes $H$. As we have computed importance values ($E_{S}$ and $E_{V}$) for each vertex $v_{j}$ of $M$, for each vertex $p_{i}$ of $H$ locating interior of $M$, we first compute its mean value weight functions $\lambda _{j}$ with respect to each vertex $v_{j}$ in $M$ [11, 12]. Then, the importance value of vertex $p_{i}$, for example, the saliency value of $p_{i}$ can be computed using mean value interpolation: $E_{S-H}^{i}=\sum _{j}\lambda _{j}E_{S}^{j}/\sum _{j}\lambda _{j}$ ($E_{V-H}^{i}$ on the $H$ can be computed in similar way). Those parts of the tetrahedral mesh $H$ that are located in the exterior of $M$ are given a lower importance value, thus, these parts can provide flexible space for model resizing. In our experiments, for each vertex $p_{i}$ exterior to $M$, the importance value is set as one-fourth to one-third of the average saliency value of all vertices on model $M$. By extracting the symmetric vertex pairs on model surface, and then encoding them into the Tet mesh using MVC interpolation, we convert the surface symmetry regions of the mesh model $M$ to the tetrahedral mesh $H$.

With the importance map defined on each vertex of the tetrahedral mesh $H$, and the selected symmetric vertex pairs, the constructed tetrahedral mesh can be applied conveniently for performing 3D mean-value coordinate space deformation to produce symmetry-preserving and non-homogeneous resizing results.

4 Complex model resizing

With the protective mesh $H$, we compute an optimally resized mesh $H'$, such that the shape of tetrahedrons of higher significance appear preserved, and tetrahedrons of lower significance may be somewhat distorted (i.e., non-uniformly squeezed or stretched). In addition, we would preserve the shape of the salient and symmetric regions with minimal distortion in the resized mesh.

4.1 3D MVC

Once a protective tetrahedral mesh $H$ for the model is built, we define a 3D mean value coordinate on the tetrahedral mesh. MVC describe a point inside a closed region as a convex combination of the boundary vertices, and linearly interpolate data given at the boundary vertices. Floater at al. [7] generalized the 2D MVC [6] for planar polygons to 3D convex polyhedra and 3D kernels of star-shaped polyhedra.

Consider that $\varOmega$ is a closed polyhedron with triangular facets on the protective mesh $H$, and is centered at the vertex $p$ with one ring neighboring vertices. Suppose the boundary of $\varOmega$ is with triangular facets $\Gamma$ and vertices $p_1,\dots ,p_d \in R^3$. For vertex $p$ and the oriented triangle $[p_i,p_j,p_k] \in \Gamma$, $A=[p,p_i,p_j,p_k]$ is a tetrahedron with positive volume, as illustrated in Fig. 5. Then the 3D mean-value coordinates $\lambda _1,\dots ,\lambda _d$ on closed region $\varOmega$ can be defined such that $\sum _{i=1}^d{\lambda _i} = 1$. The defined functions $\lambda _1,\dots ,\lambda _d$ belong to $C^\infty (K)$, when $\varOmega$ is convex, $\lambda _i$ has a unique continuous extension to the boundary $\partial \varOmega$, the extended coordinates $\lambda _i$ are linear on each facet of $\varOmega$, and $\lambda _i(p_j) = \delta _{ij}$ [7].

Fig. 5

Tetrahedron

4.2 Content-aware term

We explore the novel use of MVC as a shape-preserving deformation tool, and incorporate MVC in the content-aware mesh resizing. For each internal vertex $p_i \in H$, we define the mean-value coordinates $\lambda _{i,j}$ with respect to its one-ring neighbors $p_{j1},\dots ,p_{jd_i}$ in $H$ in counter-clockwise sequence, where $(p_i,p_{j1},\dots ,p_{jd_i})$ constructs a closed polyhedron $\varOmega$ centered at $p_{i}$. Based on the properties of mean-value coordinates [7, 8, 11], we know that $p_i-\sum _{k=1}^{d_i}{\lambda _{i,j_k}{p_{j_k}}} = 0$, and $\sum _{k=1}^{d_i}{\lambda _{i,j_k}} = 1$. When the source mesh $\varOmega$ is resized to the target mesh $\varOmega '$, the salient objects should be shape-preserved and the content deformation of the model $M$ should be smooth. To achieve this goal, for the corresponding salient vertex $p'_i$ in $\varOmega '$ of each $p_i$, the distortion energy expression $(p'_i-\sum _{k=1}^{d_i}{\lambda _{i,j_k}{p'_{j_k}}})^2$ should be minimized. That is, each vertex $p'_i$ should keep the same mean-value coordinates $\lambda _{ij}$ with respect to its neighbors $p'_{j1},\dots ,p'_{jd_i}$ as vertex $p_i$ does.

To make the resizing content-aware, we define the total tetrahedral mesh’s importance energy by summing up the individual vertex energy terms for each internal vertex $(p_1,\dots ,p_n)$:

$$\begin{aligned} F_M =\sum _{i=1}^n{\omega _i \left( p'_i-\sum _{k=1}^{d_i}{\lambda _{i,j_k}{p'_{j_k}}}\right) ^2}, \end{aligned}$$

(1)

where we add the significance weights $\omega _i = \omega _sE_{S-H}(p_i)+\omega _vE_{V-H}(p_i)$ for each vertex ($\omega _s$ and $\omega _v$ are balance weights) such that less distortion would be allowed in areas of significance, and large deformation can be allowed in the less important regions.

4.3 Symmetry-preserving term

Mitra et al. [23] present a symmetrization algorithm for geometric objects, which enhances approximate symmetries of a model while minimally altering its shape. Inspired by this work, given a set of corresponding symmetric sample pairs, we present how to derive a solution for optimal symmetry-preserving resizing.

4.3.1 Reflection transform

We specify a set of symmetric vertex pairs $C = \{(p_1,s_1),\ldots ,(p_l,s_l)\}$ on tetrahedral meshes $H$, which corresponds to the symmetric subparts $S_1$ and $S_2$ on the boundary of a model $M$, respectively. Assuming that $S_1$ and $S_2$ are symmetric about reflective symmetry transform $T$, $S_2 = T(S_1)$, and $s_i = T(p_i)$, $\forall i$. The objective is to keep these point pairs symmetric during the resizing processing (iterative resizing). We try to find an optimal reflective symmetry transform $\hat{T}$ that makes the resized point set $C'$ still symmetric with respect to $\hat{T}$. Optimal here means that the transformation $\hat{T}$ minimizes the symmetry cost $E_T = \sum _{i=1}^l{{\Vert \hat{T}(s'_i)-p'_i\Vert }^2}/2$. If we represent the reflection plane $\hat{T}$ by its normal $\hat{n}$ and distance $\hat{d}$ from origin, then for any vertex $p'$, $\hat{T}(p') = p'+2(\hat{d}-\hat{n}^Tp')\hat{n}$, we have:

$$\begin{aligned} E_T = \sum _{i=1}^l{{\Vert s'_i-2(\hat{d}-\hat{n}^Ts'_i)\hat{n}-p'_i\Vert ^2}/2} \end{aligned}$$

(2)

where all point pairs $C' = \{(p'_1,s'_1),\dots ,(p'_l,s'_l)\}$, normals $\hat{n}$ and distances $\hat{d}$ are unknown during the resizing procedure, and are to be computed during the optimization iteration. During the resizing procedure, if some of the point pairs deviate from symmetry for the reflective symmetry transform $\hat{T}$ computed in the optimization iteration, corresponding displacements are to be computed for these point pairs to retract them to locations where symmetry is restored. Note that if there are several sets of symmetric point pairs $\{C_i\}$, the symmetry-preserving computing for each set $C_{i}$ can be processed in the same way.

4.3.2 Rigid transform

During resizing, we also want to make the vertex pairs $C = \{(p_1,s_1),\dots ,(p_l,s_l)\}$ remain symmetric with respect to some rigid transform composed of a rotation $R$ followed by a translation $t$, i.e., $s_i = Rp_i+t$ and $\mathrm{RC}_{p_i} = C_{s_i}$, $\forall i$. To keep the point pairs $C$ symmetric after the rigid transform, inspired by [23], we minimize the cost of the corresponding displacement of points and alignment of the coordinate frames.

$$\begin{aligned} E_{(R,t)} = \sum _i{({\Vert \hat{R}p'_i+\hat{t}-s'_i\Vert }^2+\kappa _{1}{\Vert \hat{R}C_{p'_i}-C_{s'_i}\Vert }_F^2)} \end{aligned}$$

(3)

where $\kappa _{1}$ is a positive constant, and ${\Vert \cdot \Vert }_F$ is Frobenius norm. Our goal is to find the optimal rigid transform $(\hat{R},\hat{t})$ which minimizes $E_{(R,t)}$.

Reflection transform and rigid transform have different functions. Symmetry constraint respecting to rigid transform works when the corresponding symmetric parts need to be kept rigid and symmetric during model resizing. Symmetry constraint respecting to reflection transform works if the corresponding symmetric parts need to be kept symmetric when these parts are deforming or resizing.

With the reflection transform and rigid transform defined, we define the symmetry-preserving term $F_S$ by combining $E_{(R,t)}$ with $E_T$:

$$\begin{aligned} F_S = E_T+\kappa _{2} E_{(R,t)} \end{aligned}$$

(4)

where $\kappa _{2}$ is the balance parameter between terms $E_{(R,t)}$ and $E_T$.

4.4 User-specified constraints

For model resizing, user interaction is helpful for producing user desirable results. To perform a user-specified resize, the user specifies desired positions $\{v_i^\prime \}$ for a subset $\{\hat{v}_i\}$ of the $M$ vertices of mesh model $M$. The points $\{\hat{v}_i\}$ are usually significant parts in the mesh object. We find the nearest vertex set $\{\hat{p}_i\}$ in tetrahedral meshes $H$ for the subset $\{\hat{v}_i\}$. The user can specify target position information $q_{i}$ in the resized mesh $H'$ for the specified vertices $\{\hat{p}_i\}$. The final optimized vertex positions $p'_{i}$ are computed by solving the following quadric minimization problem: $F_U =\sum {{\Vert p_i^\prime -q_i\Vert }^2}$. The term $F_U$ constrains the positions of the user specified vertices. In our system, the user-specified constraint term can perform the linear scaling operation. We first scale the specified regions $\{\hat{p}_i\}$, and then use the scaled regions as the constrained information incorporated into energy function, which makes the resizing more flexible to generate designer desired results.

4.5 Regularization

We further use a common regularization term $E_R$, which is also a smoothing term. The regularization term $E_R$ is defined as $F_R = \sum _i u_i\sum _{j \in N(i)}{\Vert \varphi _i-\varphi _j\Vert }_F^2$, which minimizes the deformation difference between every pair of adjacent tetrahedrons. Here, $\varphi$ is a 3D affine transformation that transforms the source tetrahedron $A$ in $H$ into the target tetrahedron $A'$ in the resized mesh $H'$: $\varphi A=A'$. The degree of penalization is controlled by weights $u_i$, which is defined as $u_i = u_s E_{S-H}(p_i)+ u_v E_{V-H}(p_i)$ ($u_s$ and $u_v$ are balance weights), which are computed as content saliency: regions with high importance deserve high weights to prevent serious distortion. The resulting optimization of $F_{R}$ is a quadratic function of vertices $P'$, which leads to a sparse linear system.

4.6 Energy function optimization

Based on the above analysis, we derive our model resizing function that consists of the content-aware deformation, user-interaction constraints, symmetry preservation, and regularization terms, subject to the boundary constraints:

$$\begin{aligned} F = F(q_1,q_2,\dots ,q_n) = F_M + \lambda _1 F_U + \lambda _2 F_R + \lambda _3 F_S\nonumber \\ \end{aligned}$$

(5)

The weights $\lambda _1$, $\lambda _2$ and $\lambda _3$ are used to balance the corresponding energy terms. Our system uses the default weights as: $\lambda _1 = 1$, $\lambda _2 = 1$ and $\lambda _3 = 2$. Users can increase (or decrease) symmetry preserving measure by intuitively increasing (or decreasing) values for $\lambda _3$. Note that we use a relatively small weight for $\lambda _1$ to receive approximate value to the constrained points, avoiding the potential mesh fold-over due to hard constraints.

As the computing of symmetric regions $\hat{C}$ and the parameters $\hat{n}$, $\hat{d}$, $(\hat{R},\hat{t})$ in the symmetry-preserving term $F_S$ are interleaved, we compute $\hat{C}$ and the parameters $(\hat{n}, \hat{d}, \hat{R},\hat{t})$ independently, and solve the energy (Eq. 5) in an iterative way to gradually resize the model to a given size in a symmetry-aware manner. Suppose that the size of source protective mesh $H$ is $(R_x,R_y,R_z)$, where $R_x$, $R_y$, $R_z$ are the size of three dimension of $H$, respectively, and the size of target mesh $H^{'}$ is $(R_x^\prime ,R_y^\prime ,R_z^\prime )$. We resize mesh $H$ into target mesh $H^{'}$ in $k$ progressive iterations, and then receive $k$ in-between mesh sequences $H^{i}$ with size of $\{(R_{x,i},R_{y,i}, R_{z,i})\}$.

In particular, for each progressive resizing step, based on the vertices $P^{i}$ in the in-between mesh $H^{i}$, we compute the parameters $\hat{n}, \hat{d}, (\hat{R},\hat{t})$ in symmetry-preserving term $E_S$ depending on the deformed symmetric point pairs $C^{i} = \{(p_1^{i},s_1^{i}),\dots ,(p_m^{i},s_m^{i})\}$, using the algorithm in [23]. These estimated parameters are used as constraints to optimize the function $F$. By optimizing $F$, we obtain a progressive mesh $H^{i+1}=(R_{x,i+1},R_{y,i+1},R_{z,i+1})$, where we receive the new deformed point pairs $\hat{C}$, which may not be symmetric after deformation. Then based on $\hat{C}$ and minimizing the symmetry-preserving term $F_{S}$, we compute new values of parameters $\hat{n}, \hat{d}, (\hat{R},\hat{t})$ and corresponding displacements $d_{\hat{p}_{i}}$ for each vertex in $\hat{C}$. By removing each vertex with the corresponding displacements $d_{\hat{p}_{i}}$ in $\hat{C}$: $\tilde{p}_{i}=\tilde{p}_{i}+d_{\hat{p}_{i}}$, we retract $\hat{C}$ to be symmetric and receive the new $C^{i+1} = \{(p_1^{i+1},s_1^{i+1}),\dots ,(p_m^{i+1},s_m^{i+1})\}$. The new point pairs $C^{i+1}$ are used to compute the new parameters $\hat{n}, \hat{d}, (\hat{R},\hat{t})$, these parameters are used as constraints for computing the next resizing mesh $H_{i+2}$. This procedure is repeated until we come to the retarget size $H'$.

In each progressive resizing step, given the energy function $F$ and the computed $\hat{n}, \hat{d}$ and $(\hat{R},\hat{t})$, to compute the resized mesh $H^{^{i}}=(R_{x,i},R_{y,i},R_{z,i})$ in each iteration, we minimize $F$ by setting $\partial F/\partial x_i = \partial F/\partial y_i = \partial F/\partial z_i = 0$ for all internal vertex $p_i$. We then have the linear system: $Ax = b$, where $A$ is a sparse and symmetric positive definite matrix, and $b$ is the constrained vertex position, including the boundary constrained vertices, user specified vertices, and the symmetric vertex pairs $C$. We solve the system iteratively using preconditioned conjugate gradients [25] with an incomplete Cholesky factorization of $A$ as preconditioner, which works well for our purpose.

For our examples, we usually compute 5–10 intermediate mesh sequences $H^{i}$ to receive the final target mesh $H'$. With the symmetry constraints incorporated in the progressive processing, the symmetric regions can be effectively preserved. If the model has several symmetry clusters $\{C_i\}$, to make a smooth result, the symmetry preserved term is computed in a weighted way $E_S = \sum _i{w_iE_{S_i}}$, where $w_{i}$ is the importance weight for the $i$th symmetric cluster $C_i$. Using these techniques, our system can manipulate both the partial and global geometry symmetries.

4.7 3D MVC interpolation

After receiving a resized target mesh $H'$, as shown in Fig. 4d, we compute the final resized model $M'$ by interpolating the vertex position in the target mesh $H'$, see Fig. 4c. We apply the 3D MVC as the interpolation tool. By creating functions that interpolate values assigned to the vertices of a closed mesh, MVC are a simple but powerful interpolation approach. MVC can be used in the non-convex setting and even more generally for sets of arbitrary planar polygons without self-intersections  [11].

Inspired by the 2D image warping [11], given 3D closed triangular meshes $\psi = [p_i,p_j,\dots ,p_k]$ in the source mesh $H$, and a topologically equivalent set of closed triangular meshes $\hat{\psi } = [p'_i,p'_j,\dots ,p'_k]$ in target $H'$, we construct a smooth warp function $f: \psi \rightarrow \hat{\psi }$ that maps each $p_i$ to $p'_{i}$: $f(x) = \sum {\lambda _i(x) p'_{i}}$, where $\lambda _i$ is MVC of $\psi$. In our experiments, both $\psi$ and $\hat{\psi }$ are closed regions centering at one vertex with one ring neighboring vertices. This warp function can then be used to deform a source volume $\psi$ into a target volume $\hat{\psi }$ by simply setting $p' = f(p)$, where $p$ is a vertex position located in the interior of $\psi$.

Using 3D MVC interpolation, we interpolate the vertex position value in the target mesh $H'$ to receive the final resized model $M'$. The interpolation is completed by performing two steps: Step 1—for each vertex $v$ in the source triangular mesh $M$, we find the closed triangular mesh set $\psi = [p_i,p_j,\dots ,p_k]$ in $H$ that contains $v$, and compute the MVC $\lambda _i$ of $\psi$ using the techniques described in Sect. 4.1. Step 2—we map vertex $v$ into the target closed triangular meshes $\hat{\psi } = [p'_i,p'_j,\dots ,p'_k]$ by using function $f(v) = \sum {\lambda _i(v)p'_i}$. Thus, all interior vertices in $\psi$ are mapped into the target closed mesh $\hat{\psi }$, and the boundary vertices on $\psi$ are computed in the similar way.

Mean value coordinates interpolation has the following properties. MVC can be computed easily with a simple and local formula. The MVC are well-defined in both the interior and exterior of the mesh (smooth (i.e., $C^\infty$) except at the vertices of the polygons where they are $C^0$-continuous), which makes them an ideal tool for the interpolation of data that is given at the vertices.

5 Testing results and discussion

We evaluated our model resizing system using a PC with an Intel Core 2 Duo 2.6 GHz and with 2 GB of RAM. We have tested our model resizing approach for a variety of 3D geometric models, including man-made models and mechanical models. Many of the models have dozens of components, global or local symmetric regions, and fairly large faces. Our test results demonstrate that the important properties of our model resizing approach (e.g., content-aware resizing, user interaction constraints, and symmetry-preservation) work well.

In Figs. 1, 6, and 7, we attempt to preserve the local or global symmetry of the model during the resizing process. In Fig. 1, we try to magnify the wings when resizing the model. In the resizing system, without good distortion distribution process, the large deformation of the wings will be distributed to the remaining parts, making these parts severely distorted. Especially for those models with symmetric components, the distortion would make the results visually unpleasant [13]. We incorporate the symmetric regions of the head as constraints into the resizing system, this greatly improves the result, and the symmetry is better preserved. In Fig. 6, we set left barbells and right barbells as symmetric parts. With the defined surface saliency and symmetry-preserving optimization, our method is better for preservation of the global and local geometric symmetry of the barbells (preventing barbell distortion) than a previous method [13]. In Fig. 7, we set high importance on the flower vase, which is protected well in resizing. For the boy, we set symmetry constraints for the head and hat parts. Using our method, the symmetric regions such as the head and hat are preserved better than [13].

Fig. 6

Symmetry-preserving feature of our method, a original model, b uniform resizing results (scaling), c non-homogeneous resizing [13], d our method incorporating geometric symmetry

Fig. 7

a Original model, b result of [13], c our symmetry-preserving resizing result

In Fig. 8, we give more resizing results on a man-made object. As illustrated in Fig. 8, we resize the original car to make sufficient space to hold the seats; note that we manually add the seats to the resized car model.

Fig. 8

Left original car model. Middle the resized car model with one seat manually added. Right the car is further resized with two seats manually added

s

In Figs. 9 and 10, our method performs shape deformation and shape resizing for two models. In Fig. 9, we set larger importance value on the tiger model, and less importance value on the stone. In Fig. 9b, we stretched the model horizontally by a factor of 1.4, and vertically by a factor of 1.2. In Fig. 9c, we stretched the model in the same directions by a factor of 1.6 and 1.3, respectively. As shown in Fig. 9b and c, our method faithfully preserves the intricate shapes of the tiger model, and the stone model is adaptively resized, i.e., left parts of the stone stretched (with less importance value) and right parts squeezed. This procedure is repeated for several times, we create the stylized pose for the tiger model with distortion as least as possible. In Fig. 10, we aim to stretch the wings and magnify the bird while making shape distortion of angel as least as possible. We set the high importance value for the body of the angel model, and set less importance value for the specified symmetric regions. As shown in Fig. 10d, the body is preserved well, while the bird model is magnified and wings are stretched, and the symmetry regions are preserved well.

Fig. 9

Left original model, middle: resized result, right resized result with different resizing factor

Fig. 10

Model resizing using our method and comparisons. a original model, b uniform resizing results, c original model with symmetric and important regions, d our content-aware resizing result

In Fig. 11, we perform our model resizing on one man-made model. We set a high importance value on the little boy model, and stretch other parts. By incorporating the vulnerability map into our saliency map, the vulnerable parts of the models are preserved well. Furthermore, as such models contain many evident parts, such as the sunshade, with the surface saliency extracted and incorporated into our system, our method works well to preserve these parts. Intuitively, the boy model is protected well, and other regions are stretched non-homogenously. Note that if using simple non-uniform scale on this model with multiple disconnected components, artifacts appear in Fig. 11b, as the distortion cannot be adaptively distributed across the model.

Fig. 11

a Original model, b non-uniform retargeting result, c our retargeting result, c our retargeting result with larger retargeting factor

In Fig. 12, we show the results of model resizing when incorporating user interactivity. We rotate the circle by an angle and apply the desirable positions as interaction constraints. We then resize the model based on the importance map and symmetry constraints using the global resizing optimization, and get the resized results with respect to the user interactivity and with little distortion. Note that if without using the symmetry-preserving term $F_{S}$ in our the Energy equation (5), the symmetric regions cannot be preserved well in the resized result, such as the rear-wheel in Fig. 12c. With the symmetry-preserving term, the result is much better (Fig. 12e).

Fig. 12

Model resizing incorporating the user interactivity term, a original model, b the rear wheel is rotated and the position is used as the constraints, c our resizing results without the symmetry-preserving term, d the symmetric regions using in our method, e our results using the symmetry-preserving term

In Fig. 13, we show the resized example using our method several times to produce personalized results. Our objective is to create two larger and thinner aerofoils and a larger passenger compartment. We resize the model in three steps to achieve the goal. We first squeeze the model (a) in the $Y$ direction to produce a thin plane with the two aerofoils squeezed heavily. Then we stretch model (b) in the $Z$ direction to create two larger aerofoils. Finally, we stretch model (c) in the $Y$ direction to create a larger passenger compartment by using our resizing approach.

Fig. 13

Resizing a model several times. a Original model, b squeeze the model a in $Y$ axis direction, c stretch model b in $Z$ axis direction, d stretch model c in $Y$ axis direction

Figure 14 shows another symmetry-preserving resizing result. In this example, we try to make the discobolus stronger, and to keep the shape of the discus and pedestal. As this model is not globally symmetric, we are working to preserve the local symmetry of the resized model. Incorporating geometric symmetry information (discus, pedestal and the chest of the discobolus) into our resizing system produces more visually pleasing results. Compared with [13] and our method without incorporating symmetry-preserving term, our method incorporating the symmetry-preserving term produces better results. For example, the local symmetry of the chest part in Fig. 14e is protected well. We also give results viewed from different view directions in Fig. 15 for Fig. 14e.

Fig. 14

Symmetry-preserving model resizing. a Original model, b non-homogeneous retargeting [13], c our method without geometric symmetry, d symmetric regions on the (a), e our method using geometric symmetry

Fig. 15

Viewing resized model (Fig. 14e) in different view directions. Top row input model, bottom row resized model

Table 1 outlines the size of the geometric models we have experimented with, and the time-consumption of the main steps of our resizing method. The initialization time is measured for computing the surface vulnerability, surface saliency and geometry symmetry, Choleski preconditioners of the matrix, mesh generation, which are performed only once. The run time is used for solving the sparse matrix. In our experiments, we generally used a protective mesh with size $30\times 30\times 30$ which also depends on the shape of the model, the number of components, and the size of the triangular faces. We also list the interpolation time using mean-value coordinates.

Table 1 Performance statistics of our method, the times are measured in seconds

6 Conclusion and future work

In this paper, we have presented a new content-aware model resizing method, which uses volume-mesh space deformation based on constrained 3D MVC parameterization. Our method resizes models non-homogeneously while preserving the geometric symmetry, structural features, and surface saliency. User interaction constraints are incorporated into our framework to create results desired by the user. These processing properties make our method attractive.

There are many interesting research directions. Currently our method performs poorly if there are many important regions in the scene, as shown in Fig. 16, where there are many characters in the model and cover most parts of the scene. In this case, if we preserve several important regions using our method, other important regions have to be stretched or squeezed because there is not enough non-important space left for these regions. Our current Tet mesh generation step does not take symmetry into account; in the future, we would like to address this problem to present more convincing resizing results. As animated surface sequences is becoming an important type of media data in computer animation, we will work on content-aware resizing of time-varying surfaces.

Fig. 16

Failed example. Left input model, right the resized model