|
Topics: Computer Graphics, Computer Aided Geometric Design, and Geometric Modeling |
|
|
G1-smooth planar parameterization of complex domains for isogeometric analysis.
Maodong Pan, Ruijie Zou, Weihua Tong, Yujie Guo, Falai Chen.
Computer Methods in Applied Mechanics and Engineering,
Vol. 417, No. 116330, 2023.
|
The construction of high-quality parameterizations for complex domains remains a significant challenge in isogeometric analysis. To address this issue, we propose a G1-smooth parameterization method for planar domains with arbitrary topology. Firstly, we generate a coarse decomposition of the given complex shape without internal singularities utilizing the extracted skeleton of the domain. We then perform a finer domain partition to obtain more accurate boundary representations. Both rectangular and triangular Bézier patches are employed to represent the geometry. Secondly, by imposing G1 continuity constraints on the adjacent patches, we construct an initial parameterization that is globally G1 continuous. Finally, we enhance the parameterization quality of each patch separately using the quasi-conformal mapping technique. Various examples are presented to justify the capability of the proposed method and to demonstrate its superiority over existing multi-patch parameterizations. |
|
|
A Spectral Segmentation Method for Large Meshes.
Xiaohan Bao, Weihua Tong, Falai Chen.
Communications in Mathematics and Statistics, Vol.11, No.3, pp. 583-607,
2023.
|
Mesh segmentation is a fundamental and critical task in mesh processing, and it has been studied extensively in computer graphics and geometric modeling communities. However, current methods are not well suited for segmenting large meshes which are now common in many applications. This paper proposes a new spectral segmentation method specifically designed for large meshes inspired by multi-resolution representations. Building on edge collapse operators and progressive mesh representations, we first devise a feature-aware simplification algorithm that can generate a coarse mesh which keeps the same topology as the input mesh and preserves as many features of the input mesh as possible. Then, using the spectral segmentation method proposed in Tong et al. (IEEE Trans Vis Comput Graph 26(4):1807–1820, 2020), we perform partition on the coarse mesh to obtain a coarse segmentation which mimics closely the desired segmentation of the input mesh. By reversing the simplification process through vertex split operators, we present a fast algorithm which maps the coarse segmentation to the input mesh and therefore obtain an initial segmentation of the input mesh. Finally, to smooth some jaggy boundaries between adjacent parts of the initial segmentation or align with the desired boundaries, we propose an efficient method to evolve those boundaries driven by geodesic curvature flows. As demonstrated by experimental results on a variety of large meshes, our method outperforms the state-of-the-art segmentation method in terms of not only speed but also usability. |
|
|
Curvature Transport Method for Solving Mesh Singularities.
Chen Jiang, Weihua Tong.
Journal of Computer-Aided Design & Computer Graphics(Chinese),
Vol. 33, No. 10, pp. 1563-1572, 2021.
|
Aiming at reducing angular and area distortions induced by 3D mesh parameterization, a curvature transport-based method is presented to determine the number of cone singularities and their positions. First, the Yamabe equation is solved to obtain the conformal scaling factors and persistence. Conformal scaling persistence can figure out the first part of cone singularities, which is used to calculate distortions of the mapping. Next, the second part of cone singularities is determined by the distortion of parameterization. The positions of cone singularities are also optimized. Finally, the optimal transport cost is solved by concentrating curvature per vertex on cone singularities, and the positions of cone singularities are iteratively updated until a given threshold is satisfied. Compared with some state-of-the-art methods, the experimental results show that proposed method can efficiently reduce the distortion of parameterization. |
|
|
A sufficient condition for 3D typical curves.
Weihua Tong, Ming Chen.
Computer Aided Geometric Design,
Vol. 87, 101991:1-14, 2021.
|
2D Typical curves (Mineur et al., 1998) are a class of special Bézier curves with monotone curvature, which play a key role in designing aesthetically pleasing surfaces for the automotive industry. To deal with 3D typical curves, Farin (2006) introduces the more general concept of Class A Bézier curves. These curves are defined by so-called Class A matrix that oughts to satisfy some appropriate conditions for guaranteeing the monotonicity of curvature and torsion. In this paper, we first present new conditions for Class A Bézier curves which complete the proof in Farin (2006). Then using these conditions, we propose a new sufficient condition for 3D typical curves. More, we discover that Farin's claim (Farin, 2006) on 3D typical curves is incorrect. Numerical examples are provided to validate the correctness of our theorems. |
|
|
Spectral Mesh Segmentation via ℓ0 Gradient Minimization.
Weihua Tong, Xiankang Yang, Maodong Pan, Falai Chen.
IEEE Transactions on Visualization and Computer Graphics,
Vol. 26, No. 4, pp. 1807-1820, 2020.
|
Mesh segmentation is a process of partitioning a mesh model into meaningful parts - a fundamental problem in various disciplines. This paper introduces a novel mesh segmentation method inspired by sparsity pursuit. Based on the local geometric and topological information of a given mesh, we build a Laplacian matrix whose Fiedler vector is used to characterize the uniformity among elements of the same segment. By analyzing the Fiedler vector, we reformulate the mesh segmentation problem as a ℓ0 gradient minimization problem. To solve this problem efficiently, we adopt a coarse-to-fine strategy. A fast heuristic algorithm is first devised to find a rational coarse segmentation, and then an optimization algorithm based on the alternating direction method of multiplier (ADMM) is proposed to refine the segment boundaries within their local regions. To extract the inherent hierarchical structure of the given mesh, our method performs segmentation in a recursive way. Experimental results demonstrate that the presented method outperforms the state-of-the-art segmentation methods when evaluated on the Princeton Segmentation Benchmark, the LIFL/LIRIS Segmentation Benchmark and a number of other complex meshes. |
|
|
Volumetric spline parameterization for isogeometric analysis.
Maodong Pan, Falai Chen, Weihua Tong.
Computer Methods in Applied Mechanics and Engineering,
Vol. 359, pp. 1-19, 2020.
|
Given the spline representation of the boundary of a three dimensional domain,constructing a volumetric spline parameterization of the domain (i.e., a map from a unit cube to the domain) with the given boundary is a fundamental problem in isogeometric analysis, and the quality of parameterization has a great influence on the accuracy and efficiency in subsequent analysis. In this paper, we propose a collocation-based approach for constructing volumetric parameterization with good quality. Firstly, a harmonic map is computed between a unit cube and the computational domain. Then the task of finding a good parameterization is modeled as a max–min optimization problem with a collocation-based formulation of the bijectivity condition of a map, and an algorithm based on the coarse-to-fine and divide-and-conquer strategy is proposed to solve the optimization problem efficiently. Finally, to further improve the quality of the parameterization, the MIPS (Most Isometric Parameterizations) method is adopted to reduce the conformal distortion of the solved map. We provide several examples to demonstrate the feasibility of our approach and to compare our approach with several state-of-the-art methods. The experimental results show that our algorithm can produce parameterizations with higher quality than previous approaches especially for complex domains. |
|
|
Feature Lines Extraction Algorithm on Meshes Based on L0 Optimization.
Xiankang Yang, Maodong Pan, Weihua Tong.
Computer Engineering(Chinese),
Vol. 45, No. 7, pp. 251-257, 2019.
|
Based on the sparse distribution of feature lines on meshes, the paper proposes an optimized algorithm for feature lines extraction. For a given mesh, compute a scalar or a vector for each triangle as the input. Then, an optimized model is established for the measurement of the input so that the jumps on the edge of the meshes are as few as possible and the changes before and after optimization are minimized. An alterning direction optimization algorithm based on variable splitting technique and penalty function appraoch. In addition, a heuristic strategy is introduced to improve the sparsity of the solution, thus achieving higher quality of feature lines. Experimental results demonstrate that this method can effectively extract feature lines. Compared with some state-of-the-art methods such as Crest lines algorithm, variation algorithm and others, the proposed algorithm can impove the qualtiy of feature lines extraction and the robustness for noisy data. |
|
|
Construction of B-spline Surfaces Interpolating Curvature and Feature Curves.
Wang Fei, Falai Chen, Weihua Tong.
Journal of Computer-Aided Design & Computer Graphics(Chinese),
Vol. 30, No. 12, pp. 2193-2202, 2018.
|
Construction of surfaces interpolating 3D curve network is an important research problem in geometric
modeling. Given a 3D curve network, a new method is proposed to interpolate the curve network by using the
product of two B-spline functions, the fundamental knowledge of differential geometry and the thin-plate-spline
energy optimization. The curve segments are specified into three categories: curvature lines of the B-spline surface,
feature lines across which the B-spline surface is G0 continuous, and smooth lines at which the B-spline
surface is G1 continuous. We derive constraint conditions of the control points of the B-spline surface at the curvature
lines and smooth lines. Then the B-spline surface patches are constructed by minimizing the
thin-plate-spline energy together with the curvature line and smooth constraints. That is fair surfaces using above
method which is widely used in the construction of B-spline surfaces. We perform experiments on several models.
The results demonstrate the correctness and effectiveness of our method. |
|
|
Low-rank parameterization of planar domains for isogeometric analysis.
Maodong Pan, Falai Chen, Weihua Tong.
Computer Aided Geometric Design,
Vol. 63, pp. 1-16, 2018.
|
Construction of spline surfaces from given boundary curves is one of the classical problems in computer aided geometric design, which regains much attention in isogeometric analysis in recent years and is called domain parameterization. However, for most of the state-of-the-art parameterization methods, the rank of the spline parameterization is usually large, which results in higher computational cost in solving numerical PDEs. In this paper, we propose a low-rank representation for the spline parameterization of planar domains using low-rank tensor approximation technique, and apply quasi-conformal map as the framework of the spline parameterization. Under given correspondence of boundary curves, a quasi-conformal map with low rank and low distortion between a unit square and the computational domain can be modeled as a non-linear optimization problem. We propose an efficient algorithm to compute the quasi-conformal map by solving two convex optimization problems alternatively. Experimental results show that our approach outperforms previous approaches in producing bijective and low-rank parametric spline representations of planar domains. |
|
|
Phase-field guided surface reconstruction based on implicit hierarchical B-splines.
Maodong Pan, Weihua Tong, Falai Chen.
Computer Aided Geometric Design,
Vol 52-53, pp. 154-169, 2017.
|
Constructing smooth surface representations from point clouds is a fundamental problem in geometric modeling and computer graphics, and a wealthy of literature has focused on this problem. Among the many approaches, implicit surface reconstruction has been a central topic in the past two decades due to its ability to represent objects with complicated geometry and topology. Recently, the problem of reducing the storage requirement for implicit representations has attracted much attention. In this paper, we propose a phase-field guided implicit surface reconstruction method to tackle this problem. The implicit function of our method behaves like the phase-field of a binary system, in which it takes distinct values (i.e., −1and 1) in each of the phases with a smooth transition between them. Given an unorganized point cloud, we present a method to construct a phase-filed function represented by a hierarchical B-spline whose zero level set approximates the point cloud as much as possible. Unlike previous approaches, our mathematical model avoids the use of the normal information of the point cloud. Furthermore, as demonstrated by experimental results, our method can achieve very compact representation since we mainly need to save the coefficients of the hierarchical B-spline function within a narrow band near the point cloud. The ability of our method to produce reconstruction results with high quality is also validated by experiments. |
|
|
Compact implicit surface reconstruction via low-rank tensor approximation.
Maodong Pan, Weihua Tong, Falai Chen.
Computer-Aided Design,
Vol 78, No. 9, pp. 158-167, 2016.
|
Implicit representations have gained an increasing popularity in geometric modeling and computer graphics due to their ability to represent shapes with complicated geometry and topology. However, the storage requirement, e.g. memory or disk usage, for implicit representations of complex models is relatively large. In this paper, we propose a compact representation for multilevel rational algebraic spline (MRAS) surfaces using low-rank tensor approximation technique, and exploit its applications in surface reconstruction. Given a set of 3D points equipped with oriented normals, we first fit them with an algebraic spline surface defined on a box that bounds the point cloud. We split the bounding box into eight sub-cells if the fitting error is greater than a given threshold. Then for each sub-cell over which the fitting error is greater than the threshold, an offset function represented by an algebraic spline function of low rank is computed by locally solving a convex optimization problem. An algorithm is presented to solve the optimization problem based on the alternating direction method of multipliers (ADMM) and the CANDECOMP/PARAFAC (CP) decomposition of tensors. The procedure is recursively performed until a certain accuracy is achieved. To ensure the global continuity of the MRAS surface, quadratic B-spline weight functions are used to blend the offset functions. Numerous experiments show that our approach can greatly reduce the storage of the reconstructed implicit surface while preserve the fitting accuracy compared with the state-of-the-art methods. Furthermore, our method has good adaptability and is able to produce reconstruction results with high quality. |
|
|
A Variational Approach for Detecting Feature Lines on Meshes.
Weihua Tong,
Xuecheng Tai.
Journal of Computational Mathematics,
Vol. 34, No. 1, pp.87-112, 2016.
|
Feature lines are fundamental shape descriptors and have been extensively applied to computer graphics, computer-aided design, image processing, and non-photorealistic rendering. This paper introduces a unified variational framework for detecting generic feature lines on polygonal meshes. The classic Mumford-Shah model is extended to surfaces. Using Γ-convergence method and discrete differential geometry, we discretize the proposed
variational model to sequential coupled sparse linear systems. Through quadratic polynomials fitting, we develop a method for extracting valleys of functions defined on surfaces. Our approach provides flexible and intuitive control over the detecting procedure, and is easy to implement. Several measure functions are devised for different types of feature lines, and we apply our approach to various polygonal meshes ranging from synthetic to
measured models. The experiments demonstrate both the effectiveness of our algorithms and the visual quality of results.
|
|
|
Cost-effective printing of 3D objects with skin-frame structures.
Weiming Wang, Tuanfeng Y. Wang, Zhouwang Yang, Ligang Liu, Xin Tong, Weihua Tong,
Jiansong Deng,
Falai Chen, Xiuping Liu.
ACM Transactions on Graphics,
Vol. 32, No. 6, Article No. 177, 2013.
|
3D printers have become popular in recent years and enable fabrication of custom objects for home users. However, the cost of the material used in printing remains high. In this paper, we present an automatic solution to design a skin-frame structure for the purpose of reducing the material cost in printing a given 3D object. The frame structure is designed by an optimization scheme which significantly reduces material volume and is guaranteed to be physically stable, geometrically approximate, and printable. Furthermore, the number of struts is minimized by solving an l0 sparsity optimization. We formulate it as a multi-objective programming problem and an iterative extension of the preemptive algorithm is developed to find a compromise solution. We demonstrate the applicability and practicability of our solution by printing various objects using both powder-type and extrusion-type 3D printers. Our method is shown to be more cost-effective than previous works.
|
|
|
Local and singularity-free G^1 triangular spline surfaces using a minimum degree scheme.
Weihua Tong,
Taewan Kim.
Computing,
Vol. 86, No. 2-3, pp. 235-255, 2009.
|
We develop a scheme for constructing G1 triangular spline surfaces of arbitrary topological type. To assure that the scheme is local and singularity-free, we analyze the selection of scalar weight functions and the construction of the boundary curve network in detail. With the further requirements of interpolating positions, normals, and surface curvatures, we show that the minimum degree of such a triangular spline surface is 6. And we present a method for constructing boundary curves network, which consists of cubic Bézier curves. To deal with certain singular cases, the base mesh must be locally subdivided and we proposed an adaptive subdivision strategy for it. An application of our G1 triangular spline surfaces to the approximation of implicit surfaces is described. The visual quality of this scheme is demonstrated by some examples.
|
|
|
High-order approximation of implicit surfaces by G1 triangular spline surfaces.
Weihua Tong,
Taewan Kim.
Computer-Aided Design,
Vol. 41, No. 6, pp. 441-455, 2009.
|
In this paper, we present a method for the approximation of implicit surface by G1 triangular spline surface. Compared with the polygonization technique, the presented method employs piecewise
polynomials of high degree, achieves G1 continuity and is capable of interpolating positions, normals, and normal curvatures at vertices of an underlying base mesh. To satisfy vertex enclosure constraints,
we develop a scheme to construct a C2 consistent boundary curves network which is based on the geometric Hermite interpolation of normal curvatures. By carefully choosing the degrees of scalar weight
functions, boundary Bézier curves and triangular Bézier patches, we propose a local and singularity free algorithm for constructing a G1 triangular spline surface of arbitrary topology. Our method achieves
high precision at low computational cost, and only involves local and linear solvers which leads to a straightforward implementation. Analyses of freedom and solvability are provided, and numerical
experiments demonstrate the high performance of algorithms and the visual quality of results.
|
|
|
Polynomial splines over hierarchical T-meshes.
Jiansong Deng,
Falai Chen,
Xin Li, Changqi Hu,
Weihua Tong, Zhouwang Yang, Yuyu Feng.
Graphical Models,
Vol. 70, No. 4, pp. 76-86, 2008.
|
In this paper, we introduce a new type of splines—polynomial splines over hierarchical T-meshes (called PHT-splines) to model geometric objects. PHT-splines are a generalization of B-splines over hierarchical T-meshes. We present the detailed construction process of
spline basis functions over T-meshes which have the same important properties as B-splines do, such as nonnegativity, local support and partition of unity. As two fundamental operations, cross insertion and cross removal of PHT-splines are discussed. With the new splines, surface models can be constructed efficiently and adaptively to fit open or closed mesh models, where only linear systems of equations with a few unknowns are involved. With this approach, a NURBS surface can be efficiently simplified into a PHTspline which dramatically reduces the superfluous control points of the NURBS surface. Furthermore, PHT-splines allow for several important types of geometry processing in a natural and efficient manner, such as conversion of a PHT-spline into an assembly of tensor-product spline patches, and shape simplification of PHT-splines over a coarser T-mesh. PHT-splines not only inherit many good properties of Sederberg's T-splines such as adaptivity and locality, but also extend T-splines in several aspects except that they are only C1 continuous. For example, PHT-splines are polynomial instead of rational; cross insertion/
removal of PHT-splines is local and simple.
|
|
|
Conversion between rational S-patches and rational triangular Bézier patches.
Xiuying Li,
Weihua Tong, Yuyu Feng.
Journal of Univeristy of Science and Technology of China(Chinese),
Vol. 38, No. 2, pp. 130-137, 2008.
|
The conversion problem between rational S-patches and rational triangular Bézier patches was investigated with the reparametrization method. The explicit conversion formulas of control points and weights between S-patches and rational triangular Bézier patches were presented. Algorithms and numerical exampels were also provided to illustrate the efficiency of this method.
|
|
|
Hierarchical Implicit Tensor-Product B-Spline Surface and Its Application in Surface Reconstruction.
Weihua Tong, Yuyu Feng, Falai chen.
Journal of Software(Chinese),
Vol. 17, No. suppl., pp. 11-20, 2006.
|
This paper proposes a hierarchical implicit surface representation which has good adaptability and is very suitable for representing level of detail models. The definition of hierarchical implicit tensor-product B-Spline surface (HITBS) is first given and a mathematical model for surface reconstruction is briefly reviewed. Then an optimization model is proposed based on HITBS and a method is introduced for decomposing the domain in an adaptive fashion. A hierarchical approximation algorithm is proposed to deduce a series of linear equation System. The partition of unity method is introduced to integrate the local approximate functions into a global one. Some examples are given and conclusion remarks are concluded.
|
|
|
A Surface Reconstruction Algorithm Based on Implicit T-Spline Surfaces.
Weihua Tong
, Yuyu Feng, Falai chen.
Journal of Computer-Aided Design & Computer Graphics(Chinese),
Vol. 18, No. 3, pp. 358-365, 2006.
|
In this paper , we int roduce the implicit T-spline surfaces , generalize the definition of T-meshes from 2D to 3D , and construct the T-meshes f rom the unorganized collection of sampling points based on the octrees and subdivision. By exploiting the surface fitting models , we transform the problem of surface reconst ruction to an optimization problem. Then based on the implicit T-spline surfaces , we describe the optimization problem in the mat rix forms , and convert it to a linear system by the theory of optimization. By
solving the linear system , we get the unknown coefficient s and the reconst ructed surfaces. Finally , we conclude the paper with some illust rating examples and conclusion remarks1 Our method can solve the surface reconst ruction problems well; ad hoc it can effectively reduce the unknown coefficient s compared with the implicit tensor product B-spline functions.
|
|
|
A Fast and Adaptive Surface Reconstruction Algorithm Based on the Implicit Tensor-Product B-Spline(ITPBS) Surfaces.
Weihua Tong,
Falai chen, Yuyu Feng.
In: Proceedings of The Seventh China-Japan Seminar on Numerical Mathematics,
pp. 161-178, 2006.
|
Based on the implicit tensor-product B-spline (ITPBS) representation
of surfaces, we propose a fast and adaptive algorithm to solve the surface reconstruction problem. Our algorithm is driven by a surface fitting model, which amounts to solving a quadratic optimization problem. We explore the matrix form of it, and with some elaborate analysis, we put forward a fast and low memory consumption algorithm which only requires O(M) operations and O(M) storage space, where U is the number points in the point clouds and M is the number of unknown coefficients. In addition, we present heuristic ideas on how to adaptively choose the knot vectors of the ITPBS surface. For non-uniform(adaptive) sampling point sets, two algorithms are provided for generating the adaptive knot sequences. We conclude the paper with some illustrating examples and conclusion remarks.
|
|
|
Fairing of Impl icit Surface Via Partial Differential Equations.
Weihua Tong,
Falai chen, Yuyu Feng.
Chinese Journal of Computers(Chinese),
Vol. 27, No. 9, pp. 1264-1271, 2004.
|
This paper put forward the fairing issue of implicit surfaces. We int roduce several energy models which characterize the smoothness of implicit surfaces , and treat the energy as the functional of implicit surfaces. Based on variational theory , we derive a partial differential equation(PDE) of the implicit function for each energy model. By solving the PDE , we get a series of implicit functions
whose faring energy diminish accordingly , and thus achieve the goal of fairing the implicit surface. Furthermore , in order to satisfy other const rains in surface fairing process , such as preserving surface areas and features , we present some techniques to modify the corresponding energy models. Finally, we present some practical numerical methods to solve the partial differential equations and illust rate some examples to demonst rate the computational result s. The experimental result s show that our methods are in general flexible , effective and simple to implement .
|
|
|
Solution of Difference Equations and Its Applications in CAGD.
Yuyu Feng, Weihua Tong, Xiaoqun Chen.
In: Proceedings of The 8th International Conference on CAD/Graphics (CAD/Graphics 2003), Macao,
2004.
|
In this paper, a solution of difference equations is given explicitly and then using obtained result, the dual bases for Bézier surface defined on a rectangular domain or a simplex in R^m are given.
|
|