Designing a quad mesh that meets aesthetic, anatomical, and numerical requirements often requires meticulous manual effort in conventional methods, making quadrilateral remeshing an “art of design”. Neural networks hold significant promise for automating this process. However, current approaches that directly predict cross fields cannot properly handle the discontinuous behavior of smooth cross fields: minor shape variations can lead to substantial changes in the cross field, even when singularities remain largely unchanged. Therefore, such methods often result in non-smooth outputs when combining multiple singularity instances. To avoid such discontinuity, we propose to learn the sparse singularities, including their locations and indices, then let the non-neural conventional method to smoothly connect them. The imbalanced ratio of singular and regular vertices poses a significant challenge for learning. We convert them into a geodesic distance field and an over-sampled index field to address it. This carefully designed two-stage strategy satisfies several key requirements, such as coordinate invariance and tessellation insensitivity, while enabling the generation of smooth cross fields with varying topologies. By shifting the focus from directly learning the cross field to learning singularities, we also simplify the dataset preparation process by requiring only sparse annotations.

For large-scale modal analysis problems, Component Mode Synthesis (CMS) methods are very attractive, as they reduce the global problem into smaller subproblems on substructures. However, the substructure bases do not span the desired solution space efficiently, thus the error decreases slowly as the number of substructure eigenmodes increases. We demonstrate that a much more effective subspace can be constructed by combining substructure eigenmodes from multiple spatially staggered partitions of the input domain. To further accelerate the method, we replace the bases on the substructure interfaces by low-frequency approximations excited from the substructure eigenmodes from other partitions. Compared with typical CMS methods, our approach improves the accuracy by 3 orders of magnitude and achieves better strong and weak scaling in both time and memory cost. The advantages inherited from CMS, i.e. fast local updating and low communication cost between Message Passing Interface (MPI) ranks in large-scale distributed computing clusters are verified as well.

Surface mesh offsetting is a fundamental operation in various applications (e.g., shape modeling). Implicit methods that contour a volumetric distance field are robust at handling intersection defects, but it is challenging to apply shape control (e.g., preserving sharp features in the input shape) and to avoid undesired topology changes. Explicit methods, which move vertices towards the offset surface (with possible adaptivity), can address the above issues, but it is hard to avoid intersection issues. To combine the advantages of both, we propose a variational framework that takes mesh vertex locations as variables while simultaneously involving a smooth winding-number field associated with the mesh. Under various shape regularizations (e.g., sharp feature preservation) formulated on the mesh, the objective function mainly requires that the input mesh lie on the offset contour of the field induced by the resulting mesh. Such a combination inherits the ability to apply flexible shape regularizations from explicit methods and significantly alleviates intersection issues because of the field. Moreover, the optimization problem is numerically friendly by virtue of the differentiability of the field w.r.t. the mesh vertices. Results show that we can offset a mesh while preserving sharp features of the original surface, restricting selected parts to quadric surfaces and penalizing intersections.

Scientific literature understanding is crucial for extracting targeted information and garnering insights, thereby significantly advancing scientific discovery. Despite the remarkable success of Large Language Models (LLMs), they face challenges in scientific literature understanding, primarily due to (1) a lack of scientific knowledge and (2) unfamiliarity with specialized scientific tasks. To develop an LLM specialized in scientific literature understanding, we propose a hybrid strategy that integrates continual pre-training (CPT) and supervised fine-tuning (SFT), to simultaneously infuse scientific domain knowledge and enhance instruction-following capabilities for domain-specific tasks. In this process, we identify two key challenges: (1) constructing high-quality CPT corpora, and (2) generating diverse SFT instructions. We address these challenges through a meticulous pipeline, including PDF text extraction, parsing content error correction, quality filtering, and synthetic instruction creation. Applying this strategy, we present a suite of LLMs: SciLitLLM, specialized in scientific literature understanding. These models demonstrate promising performance on scientific literature understanding benchmarks. (1) We present an effective framework that integrates CPT and SFT to adapt LLMs to scientific literature understanding, which can also be easily adapted to other domains. (2) We propose an LLM-based synthesis method to generate diverse and high-quality scientific instructions, resulting in a new instruction set -- SciLitIns -- for less-represented scientific domains. (3) SciLitLLM achieves promising performance in scientific literature understanding benchmarks.

News recommender systems rely on rich textual information from news articles to generate user-specific recommendations. This reliance may expose these systems to potential vulnerabilities through textual attacks. To explore this vulnerability, we propose LANCE, a LArge language model-based News Content rEwriting framework, designed to influence news rankings and highlight the unintended promotion of manipulated news. LANCE consists of two key components: an explorer and a reflector. The explorer first generates rewritten news using diverse prompts, incorporating different writing styles, sentiments, and personas. We then collect these rewrites, evaluate their ranking impact within news recommender systems, and apply a filtering mechanism to retain effective rewrites. Next, the reflector fine-tunes an open-source LLM using the successful rewrites, enhancing its ability to generate more effective textual attacks. Experimental results demonstrate the effectiveness of LANCE in manipulating rankings within news recommender systems. Unlike attacks in other recomendation domains, negative and neutral rewrites consistently outperform positive ones, revealing a unique vulnerability specific to news recommendation. Once trained, LANCE successfully attacks unseen news recommender systems (i.e., those for which LANCE received no information during training), highlighting its generalization ability and exposing shared vulnerabilities across different systems. Our work underscores the urgent need for research on textual attacks and paves the way for future studies on defense strategies.

Topology optimization can maximally leverage the high DOFs and mechanical potentiality of porous foams but faces challenges in adapting to free-form outer shapes, maintaining full connectivity between adjacent foam cells, and achieving high simulation accuracy. Utilizing the concept of Voronoi tessellation may help overcome the challenges owing to its distinguished properties on highly flexible topology, natural edge connectivity, and easy shape conforming. However, a variational optimization of the so-called Voronoi foams has not yet been fully explored. In addressing the issue, a concept of explicit topology optimization of open-cell Voronoi foams is proposed that can efficiently and reliably guide the foam's topology and geometry variations under critical physical and geometric requirements. Taking the site (or seed) positions and beam radii as the DOFs, we explore the differentiability of the open-cell Voronoi foams w.r.t. its seed locations, and propose a highly efficient local finite difference method to estimate the derivatives. During the gradient-based optimization, the foam topology can change freely, and some seeds may even be pushed out of shape, which greatly alleviates the challenges of prescribing a fixed underlying grid. The foam's mechanical property is also computed with a much-improved efficiency by an order of magnitude, in comparison with benchmark FEM, via a new material-aware numerical coarsening method on its highly heterogeneous density field counterpart. We show the improved performance of our Voronoi foam in comparison with classical topology optimization approaches and demonstrate its advantages in various settings.

Many 3D mesh processing tasks revolve around generating and manipulating curves on surface meshes. While it is intuitive to explicitly model these curves using mesh edges or parametric curves in the ambient space, these methods often suffer from numerical instability or inaccuracy due to the projection operation. Another natural strategy is to adapt spline based tools, these methods are quite fast but are hard to be extended to more versatile constraints and need heavy manual interactions. In this article, we present an efficient and versatile approach to curve design based on an implicit representation known as the level set. While previous works have explored the use of the level set to generate curves with minimal length, they typically have limitations in accommodating additional conditions for rich and robust control. To address these challenges, we formulate curve editing with constraints like smoothness, interpolation, tangent control, etc., via a level set based variational problem by constraining the values or derivatives of the level set function. However, the widely used gradient flow strategy converges very slowly for this complicated variational problem compared to the classical geodesic one. Thus, we propose to solve it via Newton's method enhanced by local Hessian correction and a trust-region strategy. As a result, our method not only enables versatile control, but also excels in terms of performance due to nearly quadratic convergence and almost linear complexity in each iteration via narrow band acceleration. In practice, these advantages effectively benefit various applications, such as interactive curve manipulation, boundary smoothing for surface segmentation and path planning with obstacles as demonstrated.

Train transfer plan ranking has become the core business of online travel platforms (OTPs), due to the flourish development of high- speed rail technology and convenience of booking trains online. Currently, mainstream OTPs adopt rule-based or simple preference- based strategies to rank train transfer plans. However, the insuf- ficient emphasis on the costs of plans and the negligence of con- sidering reference transfer plans make these existing strategies less effective in solving the personalized ranking problem of train transfer plans. To this end, a novel personalized deep network (Plan- Ranker) is presented in this paper to better address the problem. In PlanRanker, a personalized learning component is first proposed to capture both of the query semantics and the target transfer plan- relevant personalized interests of a user over the user's behavior log data. Then, we present a cost learning component, where both of the price cost and the time cost of a target transfer plan are emphasized and learned. Finally, a reference transfer plan learning component is designed to enable the whole framework of PlanRanker to learn from reference transfer plans which are pieced together by plat- form users and thus reflect the wisdom of crowd. PlanRanker is now successfully deployed at Alibaba Fliggy, one of the largest OTPs in China, serving millions of users every day for train ticket reservation. Offline experiments on two production datasets and a country-scale online A/B test at Fliggy both demonstrate the superiority of the proposed PlanRanker over baselines.

Controlling the size and shear of elements is crucial in pure hex or hex-dominant meshing. To this end, non-orthonormal frame fields that are almost everywhere integrable (except for the singularities) can play a key role. However, it is often challenging or impossible to generate such a frame field under the tight control of a general Riemannian metric field. Therefore, we propose to solve a relatively weaker problem, i.e., generating such a frame field for a Riemannian metric field that is flat away from singularities. Such a metric field admits a local isometry to 3D Euclidean space. Applying Cartans first structural equation to the associated rotation field, i.e., the rotation part of the frame field, we show that the rotation field must have zero covariant derivatives under the 3D connection induced by the metric field. This observation leads to a metric-aware smoothness measure, equivalent to local integrability. The use of such a measure can be justified on meshes associated with locally flat metric fields. We also propose a method to generate smooth metric fields under a few intuitive constraints. On cuboid shapes, our method generates singularities aware of the metric fields, which makes the parameterization match the input metric fields better than the conventional methods. For generic shapes, while our method generates visually similar results to those using boundary frame fields to guide the metric field generation, the integrability and consistency of the metric fields are still improved, as reflected by the statistics.

Origin-Destination recommendation that recom-mends personalized origin city (O) and destination city (D) of flight itinerary is of great value for both Online Travel Platforms (OTPs) and users. Existing studies on next location recommendation propose to model the sequential regularity of users' check-in location sequences, but cannot well solve two new challenges facing OTPs, namely the necessity of exploring O&D and learning O&D as a whole. To this end, we propose a novel personalized Origin-Destination ranking NETwork (ODNET) for flight recommendation. In particular, a heterogeneous spatial graph (HSG) which models historical interactions between users and cities is designed at first. HSG is then deployed in ODNET to identify user preference Os and Ds by exploring the neighbor-hood information in HSG. To cope with the second challenge, the idea of multi-task learning is employed by ODNET to learn$O$and$D$jointly so as to capture their correlations. Moreover, temporal information of Os and Ds are also considered to further improve the accuracy of origin-destination recommendation. An offline experiment on multiple real-world datasets and an online A/B test both show the superiority of ODNET towards the state-of-the-art methods. Further, the implementation and deployment details of the proposed ODNET at Fliggy, one of the most popular OTPs in China, are also described. ODNET has now been successfully applied to provide high-quality flight recommendation service at Fliggy, serving tens of millions of users.

Abstract Texture mapping is a ubiquitous technique to enrich the visual effect of a mesh, which represents the desired signal (e.g. diffuse color) on the mesh to a texture image discretized by pixels through a bijective parameterization. To achieve high visual quality, large number of pixels are generally required, which brings big burden in storage, memory and transmission. We propose to use a perceptual model and a rendering procedure to measure the loss coming from the discretization, then optimize a parameterization to improve the efficiency, i.e. using fewer pixels under a comparable perceptual loss. The general perceptual model and rendering procedure can be very complicated, and non‐isotropic property rooted in the square shape of pixels make the problem more difficult to solve. We adopt a two‐stage strategy and use the Bayesian optimization in the triangle‐wise stage. With our carefully designed weighting scheme, the mesh‐wise optimization can take the triangle‐wise perceptual loss into consideration under a global conforming requirement. Comparing with many parameterizations manually designed, driven by interpolation error, or driven by isotropic energy, ours can use significantly fewer pixels with comparable perception loss or vise vesa.

Abstract Piecewise linear inextensible Cosserat rods are usually represented by Cartesian coordinates of vertices and quaternions on the segments. Such representations use excessive degrees of freedom (DOFs), and need many additional constraints, which causes unnecessary numerical difficulties and computational burden for simulation. We propose a simple yet compact representation that exactly matches the intrinsic DOFs and naturally satisfies all such constraints. Specifically, viewing a rod as a chain of rigid segments, we encode its shape as the Cartesian coordinates of its root vertex, and use axis‐angle representation for the material frame on each segment. Under our representation, the Hessian of the implicit time‐stepping has special non‐zero patterns. Exploiting such specialties, we can solve the associated linear equations in nearly linear complexity. Furthermore, we carefully designed a preconditioner, which is proved to be always symmetric positive‐definite and accelerates the PCG solver in one or two orders of magnitude compared with the widely used block‐diagonal one. Compared with other technical choices including Super‐Helices, a specially designed compact representation for inextensible Cosserat rods, our method achieves better performance and stability, and can simulate an inextensible Cosserat rod with hundreds of vertices and tens of collisions in real time under relatively large time steps.

Abstract The Hausdorff distance is one of the most fundamental metrics for comparing 3D shapes. To compute the Hausdorff distance efficiently from a triangular mesh to another triangular mesh , one needs to cull the unnecessary triangles on quickly. These triangles have no chance to improve the Hausdorff distance estimation, that is the parts with local upper bound smaller than the global lower bound. The local upper bound estimation should be tight, use fast distance computation, and involve a small number of triangles in during the reduction phase for efficiency. In this paper, we propose to use point‐triangle distance, and only involve at most four triangles in in the reduction phase. Comparing with the state‐of‐the‐art proposed by Tang et al. in 2009, which uses more costly triangle‐triangle distance and may involve a large number of triangles in reduction phase, our local upper bound estimation is faster, and with only a small impact on the tightness of the bound on error estimation. Such a more economic strategy boosts the overall performance significantly. Experiments on the Thingi10K dataset show that our method can achieve several (even over 20) times speedup on average. On a few models with different placements and resolutions, we show that close placement and large difference in resolution bring big challenges to Hausdorff distance computation, and explain why our method can achieve more significant speedup on challenging cases.

Given a complex three-dimensional domain delimited by a closed and non-degenerate input triangle mesh without any self-intersection, a common geometry processing task consists in cutting up the domain into cells through a set of planar cuts, creating a "cut-cell mesh", i.e., a volumetric decomposition of the domain amenable to visualization (e.g., exploded views), animation (e.g., virtual surgery), or simulation (finite volume computations). A large number of methods have proposed either efficient or robust solutions, sometimes restricting the cuts to form a regular or adaptive grid for simplicity; yet, none can guarantee both properties, severely limiting their usefulness in practice. At the core of the difficulty is the determination of topological relationships among large numbers of vertices, edges, faces and cells in order to assemble a proper cut-cell mesh: while exact geometric computations provide a robust solution to this issue, their high computational cost has prompted a number of faster solutions based on, e.g., local floating-point angle sorting to significantly accelerate the process --- but losing robustness in doing so. In this paper, we introduce a new approach to planar cutting of 3D domains that substitutes topological inference for numerical ordering through a novel mesh data structure, and revert to exact numerical evaluations only in the few rare cases where it is strictly necessary. We show that our novel concept of topological cuts exploits the inherent structure of cut-cell mesh generation to save computational time while still guaranteeing exactness for, and robustness to, arbitrary cuts and surface geometry. We demonstrate the superiority of our approach over state-of-the-art methods on almost 10,000 meshes with a wide range of geometric and topological complexity. We also provide an open source implementation.

Many computer graphics applications boil down to solving sparse systems of linear equations. While the current arsenal of numerical solvers available in various specialized libraries and for different computer architectures often allow efficient and scalable solutions to image processing, modeling and simulation applications, an increasing number of graphics problems face large-scale and ill-conditioned sparse linear systems --- a numerical challenge which typically chokes both direct factorizations (due to high memory requirements) and iterative solvers (because of slow convergence). We propose a novel approach to the efficient preconditioning of such problems which often emerge from the discretization over unstructured meshes of partial differential equations with heterogeneous and anisotropic coefficients. Our numerical approach consists in simply performing a fine-to-coarse ordering and a multiscale sparsity pattern of the degrees of freedom, using which we apply an incomplete Cholesky factorization. By further leveraging supernodes for cache coherence, graph coloring to improve parallelism and partial diagonal shifting to remedy negative pivots, we obtain a preconditioner which, combined with a conjugate gradient solver, far exceeds the performance of existing carefully-engineered libraries for graphics problems involving bad mesh elements and/or high contrast of coefficients. We also back the core concepts behind our simple solver with theoretical foundations linking the recent method of operator-adapted wavelets used in numerical homogenization to the traditional Cholesky factorization of a matrix, providing us with a clear bridge between incomplete Cholesky factorization and multiscale analysis that we leverage numerically.

Multiphase flows exhibit a large realm of complex behaviors such as bubbling, glugging, wetting, and splashing which emerge from air-water and water-solid interactions. Current fluid solvers in graphics have demonstrated remarkable success in reproducing each of these visual effects, but none have offered a model general enough to capture all of them concurrently. In contrast, computational fluid dynamics have developed very general approaches to multiphase flows, typically based on kinetic models. Yet, in both communities, there is dearth of methods that can simulate density ratios and Reynolds numbers required for the type of challenging real-life simulations that movie productions strive to digitally create, such as air-water flows. In this article, we propose a kinetic model of the coupling of the Navier-Stokes equations with a conservative phase-field equation, and provide a series of numerical improvements over existing kinetic-based approaches to offer a general multiphase flow solver. The resulting algorithm is embarrassingly parallel, conservative, far more stable than current solvers even for real-life conditions, and general enough to capture the typical multiphase flow behaviors. Various simulation results are presented, including comparisons to both previous work and real footage, to highlight the advantages of our new method.

Abstract Rod‐like one‐dimensional elastic objects often exhibit complex behaviors which pose great challenges to the discretization method for pursuing a faithful simulation. By only moving a small portion of material points, the Eulerian‐on‐Lagrangian (EoL) method already shows great adaptivity to handle sharp contact, but it is still far from enough to reproduce rich and complex geometry details arising in simulations. In this paper, we extend the discrete configuration space by unifying all Lagrangian and EoL nodes in representation for even more adaptivity with every sample being assigned with a dynamic material coordinate. However, this great extension will immediately bring in much more redundancy in the dynamic system. Therefore, we propose additional energy to control the spatial distribution of all material points, seeking to equally space them with respect to a curvature‐based density field as a monitor. This flexible approach can effectively constrain the motion of material points to resolve numerical degeneracy, while simultaneously enables them to notably slide inside the parametric domain to account for the shape parameterization. Besides, to accurately respond to sharp contact, our method can also insert or remove nodes online and adjust the energy stiffness to suppress possible jittering artifacts that could be excited in a stiff system. As a result of this hybrid rh‐adaption, our proposed method is capable of reproducing many realistic rod dynamics, such as excessive bending, twisting and knotting while only using a limited number of elements.

In this paper, we introduce a hierarchical construction of material-adapted refinable basis functions and associated wavelets to offer efficient coarse-graining of linear elastic objects. While spectral methods rely on global basis functions to restrict the number of degrees of freedom, our basis functions are locally supported; yet, unlike typical polynomial basis functions, they are adapted to the material inhomogeneity of the elastic object to better capture its physical properties and behavior. In particular, they share spectral approximation properties with eigenfunctions, offering a good compromise between computational complexity and accuracy. Their construction involves only linear algebra and follows a fine-to-coarse approach, leading to a block-diagonalization of the stiffness matrix where each block corresponds to an intermediate scale space of the elastic object. Once this hierarchy has been precomputed, we can simulate an object at runtime on very coarse resolution grids and still capture the correct physical behavior, with orders of magnitude speedup compared to a fine simulation. We show on a variety of heterogeneous materials that our approach outperforms all previous coarse-graining methods for elasticity.

In this paper, an efficient and scalable approach for simulating inhomogeneous and non-linear elastic objects is introduced. Our numerical coarsening approach consists in optimizing non-conforming and matrix-valued shape functions to allow for predictive simulation of heterogeneous materials with non-linear constitutive laws even on coarse grids, thus saving orders of magnitude in computational time compared to traditional finite element computations. The set of local shape functions over coarse elements is carefully tailored in a preprocessing step to balance geometric continuity and local material stiffness. In particular, we do not impose continuity of our material-aware shape functions between neighboring elements to significantly reduce the fictitious numerical stiffness that conforming bases induce; however, we enforce crucial geometric and physical properties such as partition of unity and exact reproduction of representative fine displacements to eschew the use of discontinuous Galerkin methods. We demonstrate that we can simulate, with no parameter tuning, inhomogeneous and non-linear materials significantly better than previous approaches that traditionally try to homogenize the constitutive model instead.

We introduce an approach to quadrilateral meshing of arbitrary triangulated surfaces that combines the theoretical guarantees of Morse-based approaches with the practical advantages of parameterization methods. We first construct, through an eigensolver followed by a few Gauss-Newton iterations, a periodic four-dimensional vector field that aligns with a user-provided frame field and/or a set of features over the input mesh. A field-aligned parameterization is then greedily computed along a spanning tree based on the Dirichlet energy of the optimal periodic vector field, from which quad elements are efficiently extracted over most of the surface. The few regions not yet covered by elements are then upsampled and the first component of the periodic vector field is used as a Morse function to extract the remaining quadrangles. This hybrid parameterization- and Morse-based quad meshing method is not only fast (the parameterization is greedily constructed, and the Morse function only needs to be upsampled in the few uncovered patches), but is guaranteed to provide a feature-aligned quad mesh with non-degenerate cells that closely matches the input frame field over an arbitrary surface. We show that our approach is much faster than Morse-based techniques since it does not require a densely tessellated input mesh, and is significantly more robust than parameterization-based techniques on models with complex features.

Abstract Hexahedral (hex‐) meshes are important for solving partial differential equations (PDEs) in applications of scientific computing and mechanical engineering. Many methods have been proposed aiming to generate hex‐meshes with high scaled Jacobians. While it is well established that a hex‐mesh should be inversion‐free (i.e. have a positive Jacobian measured at every corner of its hexahedron), it is not well‐studied that whether the scaled Jacobian is the most effective indicator of the quality of simulations performed on inversion‐free hex‐meshes given the existing dozens of quality metrics for hex‐meshes. Due to the challenge of precisely defining the relations among metrics, studying the correlations among different quality metrics and their correlations with the stability and accuracy of the simulations is a first and effective approach to address the above question. In this work, we propose a correlation analysis framework to systematically study these correlations. Specifically, given a large hex‐mesh dataset, we classify the existing quality metrics into groups based on their correlations, which characterizes their similarity in measuring the quality of hex‐elements. In addition, we rank the individual metrics based on their correlations with the accuracy and stability metrics for simulations that solve a number of elliptic PDE problems. Our preliminary experiments suggest that metrics that assess the conditioning of the elements are more correlated to the quality of solving elliptic PDEs than the others. Furthermore, an inversion‐free hex‐mesh with higher average quality (measured by any quality metrics) usually leads to a more accurate and stable computation of elliptic PDEs. To support our correlation study and address the lack of a publicly available large hex‐mesh dataset with sufficiently varying quality metric values, we also propose a two‐level perturbation strategy to generate the desired dataset from a small number of meshes to exclude the influences of element numbers, vertex connectivity, and volume sizes to our study.

Abstract Representing rotational symmetry vector as a set of vectors is not suitable for design due to lacking of a consistent ordering for measurement. In this paper we introduce a spectral method to find rotation invariant harmonic functions for symmetry vector field design. This method is developed for 3D vector fields, but it is applicable in 2D. Given the finite symmetry group G of a symmetry vector fieldv(x) on a 3D domain Ω, we formulate the harmonic function h(s) as a stationary point of group G. Using the real spherical harmonic (SH) bases, we showed the coefficients of the harmonic functions are an eigenvector of the SH rotation matrices corresponding to group G. Instead of solving eigen problems to obtain the eigenvector, we developed a forward constructive method based on orthogonal group theory. The harmonic function found by our method is not only invariant under G, but also expressive and can distinguish different rotations with respect to G. At last, we demonstrate some vector field design results with tetrahedron‐symmetry, cube‐symmetry and dodecahedron‐symmetry groups.

Abstract In this paper, we formulate an automatic approach to the detection of partial, local, and global symmetries and orbits in arbitrary 3D datasets. We improve upon existing voting‐based symmetry detection techniques by leveraging the Lie group structure of geometric transformations. In particular, we introduce a logarithmic mapping that ensures that orbits are mapped to linear subspaces, hence unifying and extending many existing mappings in a single Lie‐algebra voting formulation. Compared to previous work, our resulting method offers significantly improved robustness as it guarantees that our symmetry detection of an input model is frame, scale, and reflection invariant. As a consequence, we demonstrate that our approach efficiently and reliably discovers symmetries and orbits of geometric datasets without requiring heavy parameter tuning.

The polycube-based hexahedralization methods are robust to generate all-hex meshes without internal singularities. They avoid the difficulty to control the global singularity structure for a valid hexahedralization in frame-field based methods. To thoroughly utilize this advantage, we propose to use a frame field without internal singularities to guide the polycube construction. Theoretically, our method extends the vector fields associated with the polycube from exact forms to closed forms, which are curl free everywhere but may be not globally integrable. The closed forms give additional degrees of freedom to deal with the topological structure of high-genus models, and also provide better initial axis alignment for subsequent polycube generation. We demonstrate the advantages of our method on various models, ranging from genus-zero models to high-genus ones, and from single-boundary models to multiple-boundary ones.

We present a stable and efficient simulator for deformable objects with collisions and contacts. For stability, an optimization derived from the implicit time integrator is solved in each timestep under the inequality constraints coming from collisions. To achieve fast convergence, we extend the MPRGP based solver from handling box constraints only to handling general linear constraints and prove its convergence. This generalization introduces a cost of solving dense linear systems in each step, but these systems can be reduced into diagonal ones for efficiency without affecting the general stability via pruning redundant collisions. Our solver is an order of magnitude faster, especially for elastic objects under large deformation compared with iterative constraint anticipation method (ICA), a typical method for stability. The efficiency, robustness and stability are further verified by our results.

Narrow, inextensible, and naturally flat ribbons have some special and interesting phenomena under isometric deformations. Although a ribbon has a shape between rod and shell, directly applying the geometric representation designed for them imposes a challenge to faithfully reproduce interesting behaviors. We thus parameterize the ribbon surface as a developable ruled surface along its centerline and represent it using a framed centerline curve. Then the elastic and kinetic energy of the ribbon surface can be equivalently yet compactly described by the framed centerline curve only. To avoid numerical singularity when develop ability is violated, a finite Taylor series approximation to the potential energy is adopted. Under the observation that the off-centerline part of ribbon contributes little dynamic effect, the kinetic energy is simplified with respect to the centerline velocity only. For efficiency, each time step is separated into two stages: dynamically evolving the centerline, and then quasi-statically updating the ruling. We validate the method with qualitative analysis and ribbon specific phenomena comparisons with real-world scenarios. A set of comparisons to rod and shell model is also provided to demonstrate the advantages of our method.

Exploring multivariate spatial data attracts much attention in the visualization community. The main challenge lies in that automatic analysis techniques is insufficient in discovering complicated patterns with the perspective of human beings, while visualization techniques are incapable of accurately identifying the features of interest. This paper addresses this contradiction by enhancing automatic analysis techniques with human intelligence in an iterative visual exploration process. The integrated system, called EasyXplorer, provides a suite of intuitive clustering, dimension reduction, visual encoding and filtering widgets within 2D and 3D views, allowing an inexperienced user to visually explore and reason undiscovered features with several simple interactions. Case studies show the quality and scalability of our approach in quite challenging examples.

This paper introduces a new particle-based approach to incompressible fluid simulation. We depart from previous Lagrangian methods by considering fluid particles no longer purely as material points, but also as volumetric parcels that partition the fluid domain. The fluid motion is described as a time series of well-shaped power diagrams (hence the name power particles ), offering evenly spaced particles and accurate pressure computations. As a result, we circumvent the typical excess damping arising from kernel-based evaluations of internal forces or density without having recourse to auxiliary Eulerian grids. The versatility of our solver is demonstrated by the simulation of multiphase flows and free surfaces.

This paper presents a new technique for frame field generation. As generic frame fields (with arbitrary anisotropy, orientation, and sizing) can be regarded as cross fields in a specific Riemannian metric, we tackle frame field design by first computing a discrete metric on the input surface that is compatible with a sparse or dense set of input constraints. The final frame field is then found by computing an optimal cross field in this customized metric. We propose frame field design constraints on alignment, size, and skewness at arbitrary locations on the mesh as well as along feature curves, offering much improved flexibility over previous approaches. We demonstrate the advantages of our frame field generation through the automatic quadrangulation of man-made and organic shapes with controllable anisotropy, robust handling of narrow surface strips, and precise feature alignment. We also extend our technique to the design of n -vector fields.

In this paper, we propose a full featured and efficient subspace simulation method in the rotation-strain (RS) space for elastic objects. Sharply different from previous methods using the rotation-strain space, except for the ability to handle non-linear elastic materials and external forces, our method correctly formulates the kinetic energy, centrifugal and Coriolis forces which significantly reduces the dynamic artifacts. We show many techniques used in the Euclidean space methods, such as modal derivatives, polynomial and cubature approximation, can be adapted to our RS simulator. Carefully designed experiments show that the equation of motion in RS space has less non-linearity than its Euclidean counterpart, and as a consequence, our method has great advantages of lower dimension and computational complexity than state-of-the-art methods in the Euclidean space.

Abstract Constructing locally injective mappings for 2D triangular meshes is vital in applications such as deformations. In such a highly constrained optimization, the prescribed tessellation may impose strong restriction on the solution. As a consequence, the feasible region may be too small to contain an ideal solution, which leads to problems of slow convergence, poor solution, or even that no solution can be found. We propose to integrate adaptive remeshing into interior point method to solve this issue. We update the vertex positions via a parameter‐free relaxation enhanced geometry optimization, and then use edge‐flip operations to reduce the residual and keep a reasonable condition number for better convergence. For more robustness, when the iteration of interior point method terminates but leaves the positional constraints unsatisfied, we estimate the edges in the current tessellation that block vertices moving based on the convergence information of the optimization, and then split neighboring edges to break the restriction. The results show that our method has better performance than the solely geometric optimization approaches, especially for extreme deformations.

Polycube maps of triangle meshes have proved useful in a wide range of applications, including texture mapping and hexahedral mesh generation. However, constructing either fully automatically or with limited user control a low-distortion polycube from a detailed surface remains challenging in practice. We propose a variational method for deforming an input triangle mesh into a polycube shape through minimization of the ℓ 1 -norm of the mesh normals, regularized via an as-rigid-as-possible volumetric distortion energy. Unlike previous work, our approach makes no assumption on the orientation, or on the presence of features in the input model. User-guided control over the resulting polycube map is also offered to increase design flexibility. We demonstrate the robustness, efficiency, and controllability of our method on a variety of examples, and explore applications in hexahedral remeshing and quadrangulation.

We present a novel method for elastic animation editing with space-time constraints. In a sharp departure from previous approaches, we not only optimize control forces added to a linearized dynamic model, but also optimize material properties to better match user constraints and provide plausible and consistent motion. Our approach achieves efficiency and scalability by performing all computations in a reduced rotation-strain (RS) space constructed with both cubature and geometric reduction, leading to two orders of magnitude improvement over the original RS method. We demonstrate the utility and versatility of our method in various applications, including motion editing, pose interpolation, and estimation of material parameters from existing animation sequences.

Existing methods for surface quadrangulation cannot ensure accurate alignment with feature or boundary curves and tight control of local element size, which are important requirements in many numerical applications (e.g., FEA). Some methods rely on a prescribed direction field to guide quadrangulation for feature alignment, but such a direction field may conflict with a desired density field, thus making it difficult to control the element size. We propose a new spectral method that achieves both accurate feature curve alignment and tight control of local element size according to a given density field. Specifically, the following three technical contributions are made. First, to make the quadrangulation align accurately with feature curves or surface boundary curves, we introduce novel boundary conditions for wave-like functions that satisfy the Helmholtz equation approximately in the least squares sense. Such functions, called quasi-eigenfunctions , are computed efficiently as the solutions to a variational problem. Second, the mesh element size is effectively controlled by locally modulating the Laplace operator in the Helmholtz equation according to a given density field. Third, to improve robustness, we propose a novel scheme to minimize the vibration difference of the quasi-eigenfunction in two orthogonal directions. It is demonstrated by extensive experiments that our method outperforms previous methods in generating feature-aligned quadrilateral meshes with tight control of local elememt size. We further present some preliminary results to show that our method can be extended to generating hex-dominant volume meshes.

We present an automatic hexahedralization tool, based on a systematic treatment that removes some of the singularities that would lead to degenerate volumetric parameterization. Such singularities could be abundant in automatically generated frame fields guiding the interior and boundary layouts of the hexahedra in an all hexahedral mesh. We first give the mathematical definitions of the inadmissible singularities prevalent in frame fields, including newly introduced surface singularity types. We then give a practical framework for adjusting singularity graphs by automatically modifying the rotational transition of frames between charts (cells of a tetrahedral mesh for the volume) to resolve the issues detected in the internal and boundary singularity graph. After applying an additional re-smoothing of the frame field with the modified transition conditions, we cut the volume into a topologically trivial domain, with the original topology encoded by the self-intersections of the boundary of the domain, and solve a mixed integer problem on this domain for a global parameterization. Finally, a properly connected hexahedral mesh is constructed from the integer isosurfaces of (u,v,w) in the parameterization. We demonstrate the applicability of the method on complex shapes, and discuss its limitations.

ABSTRACT We present an intuitive and interactive approach for motion editing through space–time constraints on positions. Given an input motion of an elastic body, our approach enables the user to interactively edit node positions in order to alter and fine‐tune the motion. We formulate our motion editing as an optimization problem with dynamics constraints to enforce a physically plausible result. Through linearization of the editing around the input trajectory, we simplify this constrained optimal control problem into an unconstrained quadratic optimization. The optimal motion thus becomes the solution of a dense linear system, which we solve efficiently by applying the adjoint method in each iteration of a conjugate gradient solver. We demonstrate the efficiency and quality of our motion editing technique on a series of examples. Copyright © 2013 John Wiley & Sons, Ltd.

Animation techniques for controlling liquid simulation are challenging: they commonly require carefully setting initial and boundary conditions or performing a costly numerical optimization scheme against user-provided keyframes or animation sequences. Either way, the whole process is laborious and computationally expensive. We introduce a novel method to provide intuitive and interactive control of liquid simulation. Our method enables a user to locally edit selected keyframes and automatically propagates the editing in a nearby temporal region using geometric deformation. We formulate our local editing techniques as a small-scale nonlinear optimization problem which can be solved interactively. With this uniformed formulation, we propose three editing metaphors, including (i) sketching local fluid features using a few user strokes, (ii) dragging a local fluid region, and (iii) controlling a local shape with a small mesh patch. Finally, we use the edited liquid animation to guide an offline high-resolution simulation to recover more surface details. We demonstrate the intuitiveness and efficacy of our method in various practical scenarios.

Image-space line integral convolution (LIC) is a popular scheme for visualizing surface vector fields due to its simplicity and high efficiency. To avoid inconsistencies or color blur during the user interactions, existing approaches employ surface parameterization or 3D volume texture schemes. However, they often require expensive computation or memory cost, and cannot achieve consistent results in terms of both the granularity and color distribution on different scales. This paper introduces a novel image-space surface flow visualization approach that preserves the coherence during user interactions. To make the noise texture under different viewpoints coherent, we propose to precompute a sequence of mipmap noise textures in a coarse-to-fine manner for consistent transition, and map the textures onto each triangle with randomly assigned and constant texture coordinates. Further, a standard image-space LIC is performed to generate the flow texture. The proposed approach is simple and GPU-friendly, and can be easily combined with various texture-based flow visualization techniques. By leveraging viewpoint-dependent backward tracing and mipmap noise phase, our method can be incorporated with the image-based flow visualization (IBFV) technique for coherent visualization of unsteady flows. We demonstrate consistent and highly efficient flow visualization on a variety of data sets.

Many natural and man-made objects consist of simple primitives, similar components, and various symmetry structures. This paper presents a divide-and-conquer quadrangulation approach that exploits such global structural information. Given a model represented in triangular mesh, we first segment it into a set of submeshes, and compare them with some predefined quad mesh templates. For the submeshes that are similar to a predefined template, we remesh them as the template up to a number of subdivisions. For the others, we adopt the wave-based quadrangulation technique to remesh them with extensions to preserve symmetric structure and generate compatible quad mesh boundary. To ensure that the individually remeshed submeshes can be seamlessly stitched together, we formulate a mixed-integer optimization problem and design a heuristic solver to optimize the subdivision numbers and the size fields on the submesh boundaries. With this divider-and-conquer quadrangulation framework, we are able to process very large models that are very difficult for the previous techniques. Since the submeshes can be remeshed individually in any order, the remeshing procedure can run in parallel. Experimental results showed that the proposed method can preserve the high-level structures, and process large complex surfaces robustly and efficiently.

Image-space line integral convolution (LIC) is a popular approach for visualizing surface vector fields due to its simplicity and high efficiency. To avoid inconsistencies or color blur during the user interactions in the image-space approach, some methods use surface parameterization or 3D volume texture for the effect of smooth transition, which often require expensive computational or memory cost. Furthermore, those methods cannot achieve consistent LIC results in both granularity and color distribution on different scales. This paper introduces a novel image-space LIC for surface flows that preserves the texture coherence during user interactions. To make the noise textures under different viewpoints coherent, we propose a simple texture mapping technique that is local, robust and effective. Meanwhile, our approach pre-computes a sequence of mipmap noise textures in a coarse-to-fine manner, leading to consistent transition when the model is zoomed. Prior to perform LIC in the image space, the mipmap noise textures are mapped onto each triangle with randomly assigned texture coordinates. Then, a standard image-space LIC based on the projected vector fields is performed to generate the flow texture. The proposed approach is simple and very suitable for GPU acceleration. Our implementation demonstrates consistent and highly efficient LIC visualization on a variety of datasets.

Abstract Recently, approaches have been put forward that focus on the recognition of mesh semantic meanings. These methods usually need prior knowledge learned from training dataset, but when the size of the training dataset is small, or the meshes are too complex, the segmentation performance will be greatly effected. This paper introduces an approach to the semantic mesh segmentation and labeling which incorporates knowledge imparted by both segmented, labeled meshes, and unsegmented, unlabeled meshes. A Conditional Random Fields (CRF) based objective function measuring the consistency of labels and faces, labels of neighbouring faces is proposed. To implant the information from the unlabeled meshes, we add an unlabeled conditional entropy into the objective function. With the entropy, the objective function is not convex and hard to optimize, so we modify the Virtual Evidence Boosting (VEB) to solve the semi‐supervised problem efficiently. Our approach yields better results than those methods which only use limited labeled meshes, especially when many unlabeled meshes exist. The approach reduces the overall system cost as well as the human labelling cost required during training. We also show that combining knowledge from labeled and unlabeled meshes outperforms using either type of meshes alone.

Abstract In fluid animation, wake is one of the most important phenomena usually seen when an object is moving relative to the flow. However, in current shallow water simulation for interactive applications, this effect is greatly smeared out. In this paper, we present a method to efficiently synthesize these wakes. We adopt a generalized SPH method for shallow water simulation and two way solid fluid coupling. In addition, a 2D discrete vortex method is used to capture the detailed wake motions behind an obstacle, enriching the motion of SWE simulation. Our method is highly efficient since only 2D simulation is required. Moreover, by using a physically inspired procedural approach for particle seeding, DVM particles are only created in the wake region. Therefore, very few particles are required while still generating realistic wake patterns. When coupled with SWE, we show that these patterns can be seen using our method with marginal overhead.

Abstract In this paper, we propose a GPU‐friendly shape interpolation method. In contrast with state‐of‐the‐art interpolation algorithms, our method computes the trajectory of each vertex independently instead of solving large linear systems in every interpolation step. Given two poses being interpolated, we find trajectory parameters for each vertex by optimization with the consideration of the key pose reconstruction and as‐rigid‐as‐possible deformation in the pre‐computing stage. During run‐time, the vertices coordinates on the intermediate shape can be computed in parallel according to a close form formulation. In the results we demonstrate that our method achieves extremely high performance on modern GPU and can be extended easily to multi‐pose interpolation. Copyright © 2011 John Wiley & Sons, Ltd.

In this paper, we present a method for constructing a 3D cross-frame field , a 3D extension of the 2D cross-frame field as applied to surfaces in applications such as quadrangulation and texture synthesis. In contrast to the surface cross-frame field (equivalent to a 4-Way Rotational-Symmetry vector field), symmetry for 3D cross-frame fields cannot be formulated by simple one-parameter 2D rotations in the tangent planes. To address this critical issue, we represent the 3D frames by spherical harmonics, in a manner invariant to combinations of rotations around any axis by multiples of π/2. With such a representation, we can formulate an efficient smoothness measure of the cross-frame field. Through minimization of this measure under certain boundary conditions, we can construct a smooth 3D cross-frame field that is aligned with the surface normal at the boundary. We visualize the resulting cross-frame field through restrictions to the boundary surface, streamline tracing in the volume, and singularities. We also demonstrate the application of the 3D cross-frame field to producing hexahedron-dominant meshes for given volumes, and discuss its potential in high-quality hexahedralization, much as its 2D counterpart has shown in quadrangulation.

In this paper, we introduce an interactive approach to generate physically based shape interpolation between poses. We extend linear modal analysis to offer an efficient and robust numerical technique to generate physically-plausible dynamics even for very large deformation. Our method also provides a rich set of intuitive editing tools with real-time feedback, including control over vibration frequencies, amplitudes, and damping of the resulting interpolation sequence. We demonstrate the versatility of our approach through a series of complex dynamic shape interpolations.

In this paper, we present a novel method to extract motion of a dynamic object from a video that is captured by a handheld camera, and apply it to a 3D character. Unlike the motion capture techniques, neither special sensors/trackers nor a controllable environment is required. Our system significantly automates motion imitation which is traditionally conducted by professional animators via manual keyframing. Given the input video sequence, we track the dynamic reference object to obtain trajectories of both 2D and 3D tracking points. With them as constraints, we then transfer the motion to the target 3D character by solving an optimization problem to maintain the motion gradients. We also provide a user-friendly editing environment for users to fine tune the motion details. As casual videos can be used, our system, therefore, greatly increases the supply source of motion data. Examples of imitating various types of animal motion are shown.

Abstract We propose a novel approach for repairing topological inconsistency of mesh sequences with a few user interactions. The main idea of our approach is to leverage curve skeletons to detect the inconsistency of a mesh sequence. The skeleton of one mesh in the sequence is edited by user, which produces a prototype skeleton. We propagate this prototype using graph matching in‐between frames. By using temporal coherence cues, the matching procedure can be dramatically accelerated. Finally, the mesh sequence is repaired according to the inconsistencies by comparing matched skeletons and original skeletons. As demonstrated in the results, our approach avoids manually editing in all meshes, and is able to output a mesh sequence with consistent topology. Copyright © 2010 John Wiley & Sons, Ltd.

This paper proposes a new method for remeshing a surface into anisotropically sized quads. The basic idea is to construct a special standing wave on the surface to generate the global quadrilateral structure. This wave based quadrangulation method is capable of controlling the quad size in two directions and precisely aligning the quads with feature lines. Similar to the previous methods, we augment the input surface with a vector field to guide the quad orientation. The anisotropic size control is achieved by using two size fields on the surface. In order to reduce singularity points, the size fields are optimized by a new curl minimization method. The experimental results show that the proposed method can successfully handle various quadrangulation requirements and complex shapes, which is difficult for the existing state-of-the-art methods.

Abstract Embedding geometric textures in a shell space around an arbitrary surface has been a popular way to add highly detailed geometric details and enhance visual richness in graphics community, but the dynamic effects of geometric textures have not been modeled and simulated. In this paper, we introduce an efficient algorithm for deforming geometric textures with dynamic effects. The algorithm consists of two steps. First, it computes a deformed shell space by optimizing a material related energy function, which is then used to evaluate the equilibrium position of the geometric texture. Second, an explicit time integration scheme is applied for vibrating the geometric texture around its equilibrium position. Users can deform the geometric textures by dragging its vertices directly, and the dynamic behavior of the geometric textures can be changed by adjusting several material parameters. The dynamic simulation of geometric textures can be easily implemented on GPU and runs at real‐time rates. Copyright © 2009 John Wiley & Sons, Ltd.

It is a challenging problem to interactively deform densely sampled complex objects. This paper proposed an easy but efficient approach to it by using coarse control meshes to embed the target objects. The control mesh can be efficiently deformed by various existing methods, and then the target object can be accordingly deformed by interpolation. One of the most simplest interpolation methods is to use the barycentric coordinates, which however generates apparent first-order discontinuity artifacts across the boundary due to its piecewise linear property. To avoid such artifacts, this paper introduced a modified barycentric interpolation (modified-BI) technique. The central idea is to add a local transformation at each control vertex for interpolation, so that we can minimize the first-order discontinuity by optimizing the local transformations. We also minimize the second order derivatives of the interpolation function to avoid undesired vibrations. While focus on deforming 3D objects embedded in tetrahedron meshes, the proposed method is applicable to 2D image objects embed in planar triangular meshes. The experimental results in both 2D and 3D demonstrated the success and advantages of the proposed method.

This paper presents a new quadrangulation algorithm, extending the spectral surface quadrangulation approach where the coarse quadrangular structure is derived from the Morse-Smale complex of an eigenfunction of the Laplacian operator on the input mesh. In contrast to the original scheme, we provide flexible explicit controls of the shape, size, orientation and feature alignment of the quadrangular faces. We achieve this by proper selection of the optimal eigenvalue (shape), by adaption of the area term in the Laplacian operator (size), and by adding special constraints to the Laplace eigenproblem (orientation and alignment). By solving a generalized eigen-problem we can generate a scalar field on the mesh whose Morse-Smale complex is of high quality and satisfies all the user requirements. The final quadrilateral mesh is generated from the Morse-Smale complex by computing a globally smooth parametrization. Here we additionally introduce edge constraints to preserve user specified feature lines accurately.

Abstract Shell becomes popular in a variety of modeling techniques for representing small‐scale features and increasing visual complexity. Current shell generation algorithms do not measure the volume distortion for geometric texture mapping. And when the object deforms, it is very challenging for existing algorithms to wrap the space inside the shell without large artifacts. We propose an approach to these problems by minimizing the difference between the deformation gradient of the space in the shell and the rotation component of it. Because the shell space is warped as rigid as possible, small features embedded in the shell can be preserved well. Furthermore, our algorithm can achieve shell‐like object deformation. We introduce a novel hierarchical dimension reduction method to solve the involved nonlinear optimization problem efficiently. Finally, several examples are presented to demonstrate the usefulness of our algorithm. Copyright © 2007 John Wiley & Sons, Ltd.

Abstract This paper presents a novel interactive mesh deformation method that can achieve various dynamic material effects, including elastic membrane and cloth effects. In our framework, a mesh is encoded by some differential quantities based on edge length and dihedral angle; and the deformation is formulated as a least square problem for preserving the edge length and dihedral angle via the differential quantities. In order to obtain anisotropic material effects, we further propose an edge‐weighting scheme based on a user‐specified vector field. To avoid specifying the local transformations, we set up an iterative scheme for solving the deformation. At last, several examples are presented to show that our approach can interactively generate visually pleasing deformations. Copyright © 2006 John Wiley & Sons, Ltd.

In this paper we present a general framework for performing constrained mesh deformation tasks with gradient domain techniques. We present a gradient domain technique that works well with a wide variety of linear and nonlinear constraints. The constraints we introduce include the nonlinear volume constraint for volume preservation, the nonlinear skeleton constraint for maintaining the rigidity of limb segments of articulated figures, and the projection constraint for easy manipulation of the mesh without having to frequently switch between multiple viewpoints. To handle nonlinear constraints, we cast mesh deformation as a nonlinear energy minimization problem and solve the problem using an iterative algorithm. The main challenges in solving this nonlinear problem are the slow convergence and numerical instability of the iterative solver. To address these issues, we develop a subspace technique that builds a coarse control mesh around the original mesh and projects the deformation energy and constraints onto the control mesh vertices using the mean value interpolation. The energy minimization is then carried out in the subspace formed by the control mesh vertices. Running in this subspace, our energy minimization solver is both fast and stable and it provides interactive responses. We demonstrate our deformation constraints and subspace deformation technique with a variety of constrained deformation examples.

We present a fast deformation method for flexible objects. The deformation of the object is physically modeled using a linear elasticity model with a displacement based finite elements method, yielding a linear system at each time step of simulation. We solve this linear system using a precomputed force-displacement matrix, which describes the object response in terms of displacement accelerations to the forces acting on each vertex. We exploit the spatial coherence to effectively compress the force-displacement matrix to make this method practical and efficient by applying the clustered principal component analysis method. And we developed a method to efficiently handle the additional constraints for interactive user manipulation. At last large deformations are addressed based upon the compressed force-displacement matrix by combining a domain decomposition method and tracking the rotational motions. The experimental results demonstrate fast performances on complex large scale objects under interactive user manipulations.

We present a novel technique for large deformations on 3D meshes using the volumetric graph Laplacian. We first construct a graph representing the volume inside the input mesh. The graph need not form a solid meshing of the input mesh's interior; its edges simply connect nearby points in the volume. This graph's Laplacian encodes volumetric details as the difference between each point in the graph and the average of its neighbors. Preserving these volumetric details during deformation imposes a volumetric constraint that prevents unnatural changes in volume. We also include in the graph points a short distance outside the mesh to avoid local self-intersections. Volumetric detail preservation is represented by a quadric energy function. Minimizing it preserves details in a least-squares sense, distributing error uniformly over the whole deformed mesh. It can also be combined with conventional constraints involving surface positions, details or smoothness, and efficiently minimized by solving a sparse linear system.We apply this technique in a 2D curve-based deformation system allowing novice users to create pleasing deformations with little effort. A novel application of this system is to apply nonrigid and exaggerated deformations of 2D cartoon characters to 3D meshes. We demonstrate our system's potential with several examples.