CAGD&CG Group of Zhejiang University

Welcome to visit us, the Group of Computer Aided Geometric Design and Computer Graphics (CAGD&CG Group) at Department of Mathematics, Zhejiang University!
The core of computer aided geometric design and computer graphics (CAGD&CG) is the fundamental problem of defining, representing, and manipulating shape. CAGD&CG are vital tools in the task of modeling and analyzing the physical world for scentists and engineers. Applications of these technologies include the design and manufacture of car bodies, ship hulls, airplane wings, and a wide variety of mechanical components and assemblies. The scope of CAGD&CG is rather broad, including shape design and analysis, solid modeling, mesh generation, automated design and manufacture, computer animation, scientific visualization, image and signal processing, and computer vision. Our CAGD&CG group explores the fundamental mathematics associated with shape and applications of shape to these areas.

Research Areas People Publications Teaching Seminars Resources

Research Areas

Mathematics of curves and surfaces
Shape representations
Digital geometry processing
Computer animation
Applications in industry
Image and signal processing

People

Faculty

◦ Guozhao Wang	Professor	wanggz@zju.edu.cn	(Retired in 2011)
◦ Guojin Wang	Professor	wanggj@zju.edu.cn	(Retired in 2011)
◦ Ligang Liu	Professor	ligangliu@zju.edu.cn
◦ Xunnian Yang	Associate Professor	yxn@zju.edu.cn

Recent Publications

List of All Publications

We introduce an algorithm for 3D object modeling where the user draws creative inspiration from an object captured in a single photograph. Our method leverages the rich source of photographs for creative 3D modeling. However, with only a photo as a guide, creating a 3D model from scratch is a daunting task. We support the modeling process by utilizing an available set of 3D candidate models. Specifically, the user creates a digital 3D model as a geometric variation from a 3D candidate. Our modeling technique consists of two major steps. The first step is a user-guided image-space object segmentation to reveal the structure of the photographed object. The core step is the second one, in which a 3D candidate is automatically deformed to fit the photographed target under the guidance of silhouette correspondence. The set of candidate models have been pre-analyzed to possess useful high-level structural information, which is heavily utilized in both steps to compensate for the ill-posedness of the modeling problems based only on content in a single image. Equally important, the structural information is preserved by the geometric variation so that the final product is coherent with its inherited structural information readily usable for subsequent model refinement or processing.

Kai Xu, Hanlin Zheng, Hao Zhang, Daniel Cohen-Or, Ligang Liu, Yueshan Xiong. Photo-Inspired Model-Driven 3D Object Modeling. ACM Transactions on Graphics (Proc. SIGGRAPH), 2011, to appear. [Project page]

We present a novel progressive painting-based mesh cutout tool, called Paint Mesh Cutting, for interactive mesh segmentation. Different from the previous user interfaces, the user only needs to draw a single stroke on the foreground region and then obtains the desired cutting part at an interactive rate. Moreover, the user progressively paints the region of interest using a brush and have the instant feedback on cutting results as he/she drags the mouse. This is achieved by efficient graph-cut based optimizations based on the Gaussian mixture models (GMM) on the shape diameter function (SDF) metric of the shape. We demonstrate a number of various examples to illustrate the flexibility and applicability of our system and present a user study that supports the advantages of our user interface.

Lubin Fan, Ligang Liu, Kun Liu. Paint Mesh Cutting. Computer Graphics Forum (Proc. Eurographics), 30(2), 603-611, 2011. [Project page]

Guo Li, Ligang Liu, Hanlin Zheng, Niloy Mitra. Analysis, Reconstruction and Manipulation using Arterial Snakes. ACM Transactions on Graphics (Proc. ACM SIGGRAPH ASIA), 29(5), Article No.152: 1-10, 2010. [Project page]

Detailed and interleaving structures, common on many man-made objects, are often created using cane, coils, metal wires, rods, etc. The delicate structures, although manufactured using simple procedures, are challenging to scan and reconstruct. We observe that such structures are inherently 1D in nature, and hence are naturally represented using an arrangement of generating curves. We refer to the resultant surfaces as arterial surfaces. In this paper we propose a novel approach for scanning, analyzing, and manipulating such arterial surfaces. The core of the algorithm is a novel deformable model, called arterial snake, that simultaneously captures the topology and geometry of the arterial objects. The recovered snakes produce a natural decomposition of the raw scans, with the decomposed parts often capturing meaningful object sections. We demonstrate the robustness of our algorithm on a variety of relief and arterial objects corrupted with noise, outliers, and with large parts missing. We present a range of applications including reconstruction, topology repairing, and manipulation of the arterial surface by directly controlling the underlying curve network and the associated profile section sections, which are difficult to perform without such the recovered shape structure.

Shizhe Zhou, Hongbo Fu, Ligang Liu, Daniel Cohen-Or, Xiaoguang Han. Parametric Reshaping of Human Bodies in Images. Transactions on Graphics (Proc. ACM SIGGRAPH), 29(4), Article No.126: 1-10, 2010. [Project page]

We present an easy-to-use image retouching technique for realistic reshaping of human bodies in a single image. A model-based approach is taken by integrating a 3D whole-body morphable model into the reshaping process to achieve globally consistent editing effects. A novel body-aware image warping approach is introduced to reliably transfer the reshaping effects from the model to the image, even under moderate fitting errors. Thanks to the parametric nature of the model, our technique parameterizes the degree of reshaping by a small set of semantic attributes, such as weight and height. It allows easy creation of desired reshaping effects by changing the full-body attributes, while producing visually pleasing results even for loosely-dressed humans in casual photographs with a variety of poses and shapes.

Ligang Liu, Renjie Chen, Lior Wolf, Daniel Cohen-Or. Optimizing Photo Composition. Computer Graphics Forum (Proceedings of Eurographics), 29(2): 469-478, 2010. [Project page]

Aesthetic images evoke an emotional response that transcends mere visual appreciation. In this work we develop a novel computational means for evaluating the composition aesthetics of a given image based on measuring several well-grounded composition guidelines. A compound operator of crop-and-retarget is employed to change the relative position of salient regions in the image and thus to modify the composition aesthetics of the image. We propose an optimization method for automatically producing a maximally-aesthetic version of the input image. We validate the performance of the method and show its effectiveness in variety of experiments.

We demonstrate that aesthetics can be evaluated computationally with high enough accuracy to be useful. This opens a new avenue for various applications to be enhanced by the ability to automatically assign aesthetic scores. For example, optimally aesthetic views of 3D models can be automatically generated, the layout of documents can be arranged to maximize aesthetic criteria, and appealing logos can be generated given a set of user requirements.
　

Shi-Qing Xin and Guo-Jin Wang. Improving Chen and Han’s Algorithm on the Discrete Geodesic Problem. ACM Transactions on Graphics, 28(4), Article No.104, 2009. [PDF, 1.4M]

The computation of geodesic distances or paths between two points on triangulated meshes is a common operation in many computer graphics applications. In this article, we present an exact algorithm for the single-source all-vertices shortest path problem.
Mitchell et al. [1987] proposed an O(n2 log n) method (MMP), based on Dijkstra’s algorithm, where n is the complexity of the polyhedral surface. Then, Chen and Han [1990] (CH) improved the running time to O(n2). Interestingly Surazhsky et al. [2005] provided experimental evidence demonstrating that the MMP algorithm runs many times faster, in practice, than the CH algorithm.
The CH algorithm encodes the structure of the set of shortest paths using a set of windows on the edges of the polyhedron. Our experiments showed that in many examples over 99% of the windows created by the CH algorithm are of no use to define a shortest path. So this article proposes to improve the CH algorithm by two separate techniques. One is to filter out useless windows using the current estimates of the distances to the vertices, the other is to maintain a priority queue like that achieved in Dijkstra’s algorithm. Our experimental results suggest that the improved CH algorithm, in spite of an O(n2 log n) asymptotic time complexity, greatly outperforms the original CH algorithm in both time and space. Furthermore, it generally runs faster than the MMP algorithm and uses considerably less space.
　

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, Yueshan Xiong. Feature-Aligned Shape Texturing. ACM Transactions on Graphics (Proc. ACM SIGGRAPH ASIA), 28(5), Article No. 108: 1-7, 2009. [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, Yueshan Xiong. Partial Intrinsic Reflectional Symmetry of 3D Shapes. ACM Transactions on Graphics (Proc. ACM SIGGRAPH ASIA), 28(5), Article No. 138: 1-10, 2009.[Project page]

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

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, Chiew-Lan Tai, Zhongping Ji, Guojin Wang. Non-Iterative Approach for Global Mesh Optimization. Computer-Aided Design, 39(9): 772-782, 2007. [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.

Jianwei Hu, Ligang Liu, Guozhao Wang. Dual Laplacian Morphing for Triangular Meshes. Computer Animation and Virtual Worlds (Proc. International Conference on Computer Animation and Social Agents (CASA)), 18: 271-277, 2007. [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.

Zhongping Ji, Ligang Liu, Zhonggui Chen, Guojin Wang. Easy Mesh Cutting. Computer Graphics Forum (Proc. Eurographics), 25(3): 283-291, 2006. [Project page]

In this paper, 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 three applications including sketching mesh editing, mesh cut and paste, and component based mesh morphing, for geometry processing.

Lei Zhang, Ligang Liu, Zhongping Ji, Guojin Wang. Manifold Parameterization. Lecture Notes in Computer Science (Proc. Computer Graphics International), 4035: 160-171, 2006. [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.

Oscar Kin-Chung Au, Chiew-Lan Tai, Ligang Liu, Hongbo Fu. Dual Laplacian Editing for Meshes. IEEE Transactions on Visualization and Computer Graphics, 12(3): 386-395, 2006. [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.

Wenhao Song and Xunnian Yang. Free-form deformation with weighted T-spline. The Visual Computer,21(3): 139-151, 2005.

A new method of free-form deformation, w-TFFD, is proposed, for which an original shape is deformed by using weighted T-spline volumes. We generalize T-splines [24] to weighted T-spline volumes that also permit T-junctions. Weighted T-spline volumes are a natural generalization of NURBS volumes but permit more flexible control lattices. Thus, w-TFFD holds many virtues of traditional FFDs and is more adaptive to objects with arbitrary topology or complex shape. The lattices can be automatically generated and approximate the shape of the object arbitrarily close by octree subdivision. Besides constructing and deforming a multiresolution lattice, users can also sculpt specific local details to their required shape by modifying weights. A set of direct-acting tools that are similar to the techniques proposed by Noble et al. [21] can be applied to w-TFFD.

Xunnian Yang. Surface interpolation of meshes by geometric subdivision. Computer-Aided Design, 37(5): 497-508, 2005.
also: Xunnian Yang. Surface interpolation of meshes with shape optimization. Proceedings of Geometric Modeling and Processing, IEEE CS Press, pp103-112, 2004.

Subdivision surfaces are generated by repeated approximation or interpolation from initial control meshes. In this paper two new nonlinear subdivision schemes, face based subdivision scheme and normal based subdivision scheme, are introduced for surface interpolation of triangular meshes. With a given coarse mesh more and more details will be added to the surface when the triangles have been split and refined. Because every intermediate mesh is a piecewise linear approximation to the final surface, the first type of subdivision scheme computes each new vertex as the solution to a least square fitting problem of selected old vertices and their neighboring triangles. Consequently, sharp features as well as smooth regions are generated automatically. For the second type of subdivision, the displacement for every new vertex is computed as a combination of normals at old vertices. By computing the vertex normals adaptively, the limit surface is $G^1$ smooth. The fairness of the interpolating surface can be improved further by using the neighboring faces. Because the new vertices by either of these two schemes depend on the local geometry, but not the vertex valences, the interpolating surface inherits the shape of the initial control mesh more fairly and naturally. Several examples are also presented to show the efficiency of the new algorithms.

Wujun Che, Xunnian Yang, and Guozhao Wang. Skeleton-driven 2D distance field metamorphosis using intrinsic shape parameters. Graphical Models, 66(2):102-126, 2004.

In this article a novel algorithm is presented for 2-D shape interpolation using the intrinsic shape parameters of a piecewise linear curve. The skeletons of two given shapes are computed and the smooth transformation of distance fields is driven by metamorphosis from the skeleton of the source object to that of the target one. We introduce feature graphs, linear forms of skeletons, to guide the construction of intermediate skeleton. If the topologies of the source object and the target one are different, their feature graphs will be automatically extended with equivalent topologies. Then we apply the technique of intrinsic shape parameters to the smooth transition of the extended feature graphs, which will guide the metamorphosis of the skeletons. Not only can the new approach be capable of morphing between objects with different topological genus, but also the topologies and the shapes of the intermediate objects can be controlled efficiently.

Xunnian Yang. Curve fitting and fairing using conic splines. Computer-Aided Design, 36(5): 461-472, 2004.

We present an efficient geometric algorithm for conic spline curve fitting and fairing through conic arc scaling. Given a set of planar points, we first construct a tangent continuous conic spline by interpolating the points with a quadratic Bezier spline curve or fitting the data with a smooth arc spline. The arc spline can be represented as a piecewise quadratic rational Bezier spline curve. For parts of the G1 conic spline without an inflection, we can obtain a curvature continuous conic spline by adjusting the tangent direction at the joint point and scaling the weights for every two adjacent rational Bezier curves. The unwanted curvature extrema within conic segments or at some joint points can be removed efficiently by scaling the weights of the conic segments or moving the joint points along the normal direction of the curve at the point. In the end, a fair conic spline curve is obtained that is G2 continuous at convex or concave parts and G1 continuous at inflection points. The main advantages of the method lies in two aspects, one advantage is that we can construct a curvature continuous conic spline by a local algorithm, the other one is that the curvature plot of the conic spline can be controlled efficiently. The method can be used in the field where fair shape is desired by interpolating or approximating a given point set. Numerical examples from simulated and real data are presented to show the efficiency of the new method.

Guozhao Wang, Qinyu Chen, and Minhua Zhou. NUAT B-Spline curves. Computer Aided Geometric Design, 21(2): 193-205, 2004.

This paper presents a new kind of splines, called non-uniform algebraic-trigonometric B-splines (NUAT B-splines), generated over the space spanned by {1, t, . . ., t\(k-3), cos t, sin t} in which k is an arbitrary integer larger than or equal to 3.We show that the NUAT B-splines share most properties of the usual polynomial B-splines. The subdivision formulae of this new kind of curves are given. The generation of tensor product surfaces by these new splines is straightforward.

Guojin Wang, Kai Tang, and Chiew-Lan Tai. Parametric representations of the surface pencil with a same spatial geodesic. Computer-Aided Design, 36(5): 447-459, 2004.

In this paper, we study the problem of constructing a family of surfaces from a given spatial geodesic curve. We derive a parametric representation for a surface pencil whose members share the same geodesic curve as an isoparametric curve. By utilizing the Frenet trihedron frame along the given geodesic, we express the surface pencil as a linear combination of the components of this local coordinate frame, and derive the necessary and sufficient conditions for the coefficients to satisfy both the geodesic and the isoparametric requirements. We illustrate and verify the method by finding exact surface pencil formulations for some simple surfaces, such as surfaces of revolution and ruled surfaces. Finally, we demonstrate the use of this method in a garment design application.

Hongwei Lin, Chiew-Lan Tai, Guojin Wang. A mesh reconstruction algorithm driven by intrinsic property of point cloud. Computer-Aided Design, 36(1): 1-9, 2004.

This paper presents an algorithm for reconstructing a triangle mesh surface from a given point cloud. Starting with a seed triangle, the algorithm grows a partially reconstructed triangle mesh by selecting a new point based on an intrinsic property of the point cloud, namely, the sampling uniformity degree. The reconstructed mesh is essentially an approximate minimum-weight triangulation to the point cloud constrained to be on a two-dimensional manifold. Thus, the reconstructed surface has only small topological difference from the surface of the sampled object. Topological correct reconstruction can be guaranteed by adding a post-processing step.

Teaching

Undergraduate