We present a novel approach to localization of sensors in a network given a subset of noisy intersensor distances. The algorithm is based on "stitching" together local structures by solving an optimization problem requiring the structures to fit together in an "As-Rigid-As-Possible" manner, hence the name ARAP. The local structures consist of reference "patches" and reference triangles, both obtained from inter-sensor distances. We elaborate on the relationship between the ARAP algorithm and other state-of-the-art algorithms, and provide experimental results demonstrating that ARAP is significantly less sensitive to sparse connectivity and measurement noise. We also show how ARAP may be distributed.

Lei Zhang, Ligang Liu, Craig Gotsman and Steven J. Gortler. An As-Rigid-As-Possible Approach to Sensor Network Localization. ACM Transactions on Sensor Networks, to appear. [PDF, 1.6M] [Project page]

The essence of a 3D shape can often be well captured by its salient feature curves. In this paper, we explore the use of salient curves in synthesizing intuitive, shape-revealing textures on surfaces. Our texture synthesis is guided by two principles: matching the direction of the texture patterns to those of the salient curves, and aligning the prominent feature lines in the texture to the salient curves exactly. We have observed that textures synthesized by these principles not only fit naturally to the surface geometry, but also visually reveal, even reinforce, the shape’s essential characteristics. We call these feature-aligned shape texturing. Our technique is fully automatic, and introduces two novel technical components in vector field-guided texture synthesis: an algorithm that orients the salient curves on a surface for constrained vector field generation, and a feature-to-feature texture optimization.

Kai Xu, Daniel Cohen-Or, Tao Ju, Ligang Liu, Hao Zhang, Shizhe Zhou and Yueshan Xiong. Feature-Aligned Shape Texturing, ACM Transactions on Graphics (SIGGRAPH Aisa 2009), 28(5), Article No. 108. [PDF, 20M] [Project page]

While many 3D objects exhibit various forms of global symmetries, prominent intrinsic symmetries which exist only on parts of an object are also well recognized. Such partial symmetries are often seen as more natural than a global one, even when the symmetric parts are under complex pose. We introduce an algorithm to extract partial intrinsic reflectional symmetries (PIRS) of a 3D shape. Given a closed 2-manifold mesh, we develop a voting scheme to obtain an intrinsic reflectional symmetry axis (IRSA) transform, which is a scalar field over the mesh that accentuates prominent IRSAs of the shape. We then extract a set of explicit IRSA curves on the shape based on a refined measure of local reflectional symmetry support along a curve. The iterative refinement procedure combines IRSA-induced region growing and region-constrained symmetry support refinement to improve accuracy and address potential issues arising from rotational symmetries in the shape. We show how the extracted IRSA curves can be incorporated into a conventional mesh segmentation scheme so that the implied symmetry cues can be utilized to obtain more meaningful results. We also demonstrate the use of IRSA curves for symmetry-driven part repair.

Kai Xu, Hao Zhang, Andrea Tagliasacchi, Ligang Liu, Guo Li, Min Meng, and Yueshan Xiong. Partial Intrinsic Reflectional Symmetry of 3D Shapes, ACM Transactions on Graphics (SIGGRAPH Aisa 2009), 28(5), Article No. 138. [PDF, 15.2M] [Project page]

In order to synthesize distortionless texture on surfaces, we develop a direct and accurate approach for local resampling in vector fields, and then use the approach to synthesize textures on 2-D manifold surfaces directly from a texture exemplar. Regular-grid patches produced by the local resampling are used as building blocks for texture synthesis. Then texture optimization and patch-based sampling are generalized to synthesize texture directly in vector fields. The first scheme can create texture of higher quality; however the second scheme is faster and simpler and works well for a wide range of textures. Users can control the vector field on the mesh to generate textures with local variations including the orientation and scale. Many experimental results are presented to demonstrate the ease of use and reliable results provided by our system.

Renjie Chen, Ligang Liu, Guangchang Dong. Local resampling for patch-based texture synthesis in vector fields. International Journal of Computer Applications in Technology, to appear. [PDF, 1.6M]

In this paper, we propose an image driven shape deformation approach for stylizing a 3D mesh using styles learned from existing 2D illustrations. Our approach models a 2D illustration as a planar mesh and represents the shape styles with four components: the object contour, the context curves, user-specified features and local shape details. After the correspondence between the input model and the 2D illustration is established, shape stylization is formulated as a style-constrained differential mesh editing problem. A distinguishing feature of our approach is that it allows users to directly transfer styles from hand-drawn 2D illustrations with individual perception and cognition, which are difficult to be identified and created with 3D modeling and editing approaches. We present a sequence of challenging examples including unrealistic and exaggerated paintings to illustrate the effectiveness of our approach.

Guanghua Tan, Wei Chen, Ligang Liu. Image Driven Shape Deformation using Styles. Journal of Zhejiang University (SCIENCE A), to appear. [PDF, 1.2M]

This paper presents a new approach, called cubic clipping, for computing all the roots of a given polynomial within an interval. In every iterative computation step, two cubic polynomials are generated to enclose the graph of the polynomial within the interval of interest. A sequence of intervals is then obtained by intersecting the sequence of strips with the abcissa axis. The sequence of these intervals converges to the corresponding root with the convergence rate 4 for the single roots, 2 for the double roots and super-linear 4/3 for the triple roots. Numerical examples show that cubic clipping has many expected advantages over Bezier clipping and quadratic clipping. We also extend our approach by enclosing the graph of the polynomial using two lower degree k<n polynomials by degree reduction. The sequence of intervals converges to the corresponding root of multiplicity s with convergence rate (k+1)/s.

Ligang Liu, Lei Zhang, Binbin Lin, Guojin Wang. Fast approach for computing roots of polynomials using cubic clipping. Computer Aided Geometric Design, 26(5): 547-559, 2009. [PDF, 0.4M]

We present a novel approach to parameterize a mesh with disk topology to the plane in a shape-preserving manner. Our key contribution is a local/global algorithm, which combines a local mapping of each 3D triangle to the plane, using transformations taken from a restricted set, with a global "stitch" operation of all triangles, involving a sparse linear system. The local transformations can be taken from a variety of families, e.g. similarities or rotations, generating different types of parameterizations. In the first case, the parameterization tries to force each 2D triangle to be an as-similar-as-possible version of its 3D counterpart. This is shown to yield results identical to those of the LSCM algorithm. In the second case, the parameterization tries to force each 2D triangle to be an as-rigid-as-possible version of its 3D counterpart. This approach preserves shape as much as possible. It is simple, effective, and fast, due to pre-factoring of the linear system involved in the global phase. Experimental results show that our approach provides almost isometric parameterizations and obtains more shape-preserving results than other state-of-the-art approaches.

We present also a more general "hybrid" parameterization model which provides a continuous spectrum of possibilities, controlled by a single parameter. The two cases described above lie at the two ends of the spectrum. We generalize our local/global algorithm to compute these parameterizations. The local phase may also be accelerated by parallelizing the independent computations per triangle.

Ligang Liu, Lei Zhang, Yin Xu, Craig Gotsman, Steven J. Gortler. A Local/Global Approach to Mesh Parameterization. Proceedings of Eurographics Symposium on Geometry Processing 2008 (SGP 2008), Copenhagen, July 2-4, 2008. Computer Graphics Forum, 2008, 27(5): 1495-1504. [PDF, 5.1M] [Project page]

This paper presents a global optimization operator for arbitrary meshes. The global optimization operator is composed of two main terms, one part is the global Laplacian operator of the mesh which keeps the fairness and another is the constraint condition which reserves the fidelity to the mesh. The global optimization operator is formulized as a quadratic optimization problem, which is easily solved by solving a sparse linear system. Our global mesh optimization approach can be effectively used in at least three applications: smoothing the noisy mesh, improving the simplified mesh, and geometric modeling with subdivision-connectivity. Many experimental results are presented to show the applicability and flexibility of the approach.

Ligang Liu, Chiew-Lan Tai, Zhongping Ji, Guojin Wang. Non-Iterative Approach for Global Mesh Optimization. Computer-Aided Design, 2007, 39(9), 772-782. [PDF, 1.9M] [Project page]

Recently, animations with deforming objects have been frequently used in various computer graphics applications. Morphing of objects is one of the techniques which realize shape transformation between two or more existing objects. In this paper, we present a novel morphing approach for 3D triangular meshes with the same topology. The basic idea of our method is to interpolate the mean curvature flow of the input meshes as the curvature flow Laplacian operator encodes the intrinsic local information of the mesh. The in-between meshes are recovered from the interpolated mean curvature flow in the dual mesh domain due to the simplicity of the neighborhood structure of dual mesh vertices. Our approach can generate visual pleasing and physical plausible morphing sequences and avoid the shrinkage and kinks appeared in the linear interpolation method. Experimental results are presented to show the applicability and flexibility of our approach.

Jianwei Hu, Ligang Liu, Guozhao Wang. Dual Laplacian Morphing for Triangular Meshes. Computer Animation and Virtual Worlds, 2007, 18: 271-277.  (Proceedings of CASA 2007) [PDF, 0.6M] [Project page]

We present a novel least scaling distortion metric to measure the deformation distortion for tetrahedral meshes. The stretch-like metric is a combination of Jacobian matrix norm and tetrahedron volume and has the properties of good shape preservation and rotation invariance. Based on our metric, we propose a uniform non-linear optimization solution to a variety of tetrahedral mesh manipulation applications including shape deformation, interpolation, deformation transfer, and deformation learning. Our approach can produce volume preserving and flip free tetrahedral mesh results, which performs much better than the previous tetrahedral manipulation approaches. We also demonstrate an efficient and practical application using free-form deformation technique. The object is embedded in a rough control tetrahedral mesh and deformed by editing the tetrahedral mesh with various constraints. Each vertex of the object can be obtained by its barycentric coordinates according to its embedding tetrahedron of the control tetrahedral mesh.

Wenhao Song, Ligang Liu. Stretch-based Tetrahedral Mesh Manipulation. ACM International Conference Proceedings of Graphics Interface 2007, Montreal, Canada, pp.319-325, 2007.  [PDF, 1.4M] [Talk, 4.7M]

We present Easy Mesh Cutting, an intuitive and easy-to-use mesh cutout tool. Users can cut meaningful components from meshes by simply drawing freehand sketches on the mesh. Our system provides instant visual feedback to obtain the cutting results based on an improved region growing algorithm using a feature sensitive metric. The cutting boundary can be automatically optimized or easily edited by users. Extensive experimentation shows that our approach produces good cutting results while requiring little skill or effort from the user and provides a good user experience. Based on the easy mesh cutting framework, we introduce two applications including sketch-based mesh editing and mesh merging for geometry processing.

Zhongping Ji, Ligang Liu, Zhonggui Chen, Guojin Wang. Easy Mesh Cutting. Proceedings of Eurographics, Vienna, Austria, Sep.,  2006. Computer Graphics Forum, 2006, 25(3): 283-291. [PDF, 4.4M] [Project page]

Manifold parameterization considers the problem of parameterizing a given triangular mesh onto another mesh surface, which could be particularly plane or sphere surfaces. In this paper we propose a unified framework for manifold parameterization between arbitrary meshes with identical genus. Our approach does this task by directly mapping the connectivity of the source mesh onto the target mesh surface without any intermediate domain and partition of the meshes. The connectivity graph of source mesh is used to approximate the geometry of target mesh using least squares meshes. A subset of user specified vertices are constrained to have the geometry information of the target mesh. The geometry of the mesh vertices is reconstructed while approximating the known geometry of the subset by positioning each vertex approximately at the center of its immediate neighbors. This leads to a sparse linear system which can be effectively solved. Our approach is simple and fast with less user interactions. Many experimental results and applications are presented to show the applicability and flexibility of the approach.

Lei Zhang, Ligang Liu, Zhongping Ji, Guojin Wang. Manifold Parameterization.  Proceedings of 24th Computer Graphics International Conference, June 2006, Hangzhou China. Lecture Notes in Computer Science, 2006, 4035: 160-171. [PDF, 3.9M] [Project page]

Recently, differential information as local intrinsic feature descriptors has been used for mesh editing. Given certain user input as constraints, a deformed mesh is reconstructed by minimizing the changes in the differential information. Since the differential information is encoded in a global coordinate system, it must somehow be transformed to fit the orientations of details in the deformed surface, otherwise distortion will appear. We observe that visually pleasing deformed meshes should preserve both local parameterization and geometry details. We propose to encode these two types of information in the dual mesh domain due to the simplicity of the neighborhood structure of dual mesh vertices. Both sets of information are nondirectional and nonlinearly dependent on the vertex positions. Thus, we present a novel editing framework that iteratively updates both the primal vertex positions and the dual Laplacian coordinates to progressively reduce distortion in parametrization and geometry. Unlike previous related work, our method can produce visually pleasing deformations with simple user interaction, requiring only the handle positions, not local frames at the handles.

Oscar Kin-Chung Au, Chiew-Lan Tai, Ligang Liu, and Hongbo Fu. Dual Laplacian editing for meshes. IEEE Transactions on Visualization and Computer Graphics, 2006, 12(3): 386-395. [PDF, 1.7M] [Project page]