A new approach to solid modeling with trivariate T-splines based on mesh optimization

We present a new method to construct a trivariate T-spline representation of complex genus-zero solids for the application of isogeometric analysis. The proposed technique only demands a surface triangulation of the solid as input data. The key of this method lies in obtaining a volumetric parameterization between the solid and the parametric domain, the unitary cube. To do that, an adaptive tetrahedral mesh of the parametric domain is isomorphically transformed onto the solid by applying a mesh untangling and smoothing procedure. The control points of the trivariate T-spline are calculated by imposing the interpolation conditions on points sited both on the inner and on the surface of the solid. The distribution of the interpolating points is adapted to the singularities of the domain in order to preserve the features of the surface triangulation.     

基于黎曼度量的复杂参数曲面有限元网格生成方法

给出了三维空间的黎曼度量和曲面自身的黎曼度量相结合的三维复杂参数曲面自适应网格生成的改进波前推进算法.详细阐述了曲面参数域上任意一点的黎曼度量的计算和插值方法;采用可细化的栅格作为背景网格,在降低了程序实现的难度的同时提高了网格生成的速度;提出按层推进和按最短边推进相结合的方法,在保证边界网格质量的同时,提高曲面内部网格的质量.三维自适应黎曼度量的引入,提高了算法剖分复杂曲面的自适应性.算例表明,该算法对复杂曲面能够生成高质量的网格,而且整个算法具有很好的时间特性和可靠性.     

Generation of a finite element MESH from stereolithography (STL) files

The aim of the method proposed here is to show the possibility of generating adaptive surface meshes suitable for the finite element method, directly from an approximated boundary representation of an object created with CAD software. First, we describe the boundary representation, which is composed of a simple triangulation of the surface of the object. Then we will show how to obtain a conforming size-adapted mesh. The size adaptation is made considering geometrical approximation and with respect to an isotropic size map provided by an error estimator. The mesh can be used “as is” for a finite element computation (with shell elements), or can be used as a surface mesh to initiate a volume meshing algorithm (Delaunay or advancing front). The principle used to generate the mesh is based on the Delaunay method, which is associated with refinement algorithms, and smoothing. Finally, we will show that not using the parametric representation of the geometrical model allows us to override some of the limitations of conventional meshing software that is based on an exact representation of the geometry.     

Generating a nice triangular mesh on a regular parametric surface

In this paper, we present an iterative algorithm to generate a nice triangular curvilinear mesh on a regular parametric surface. The main idea is to obtain a reparametrization of the surface that behaves approximately like a conformal map in a finite number of points. These points are the vertices of a planar triangulation T ^op in the parameter space, which we would like to lift on the surface. The image of T ^op by means of the reparametrization provides us a triangular curvilinear mesh on the surface which reflects the properties of T ^op .     

The meccano method for isogeometric solid modeling and applications

We present a new method to construct a trivariate T-spline representation of complex solids for the application of isogeometric analysis. We take a genus-zero solid as a basis of our study, but at the end of the work we explain the way to generalize the results to any genus solids. The proposed technique only demands a surface triangulation of the solid as input data. The key of this method lies in obtaining a volumetric parameterization between the solid and the parametric domain, the unitary cube. To do that, an adaptive tetrahedral mesh of the parametric domain is isomorphically transformed onto the solid by applying a mesh untangling and smoothing procedure. The control points of the trivariate T-spline are calculated by imposing the interpolation conditions on points sited both on the inner and on the surface of the solid. The distribution of the interpolating points is adapted to the singularities of the domain to preserve the features of the surface triangulation. We present some results of the application of isogeometric analysis with T-splines to the resolution of Poisson equation in solids parameterized with this technique.     

Feature-based design and finite element mesh generation for functional surfaces

This paper describes an approach to feature-based design and feature-based mesh generation for multi-featured functional surfaces. Unlike standard free-form parametric surface representation where the parametric surface patch plays the key role in both surface design and finite element mesh generation, we propose an approach to these two tasks which proceeds from the level of a complete feature (for example, a pocket or channel). The result is a more direct method for modeling functional surface characteristics and a more efficient feature-based implementation of Delaunay surface triangulation.     

自适应T样条曲面重建

为了进行快速高精度的曲面重建,提出了一种新的基于T样条的曲面自动重建算法。由于T样条控制网格具有特殊性质,因此在使用T样条进行曲面重建时,一个关键的问题是如何构造好一个T网格。该新算法在进行曲面重建时,用三角网格的参数化方法,先将数据点同胚映射到平面,然后再利用平面四叉树细分的方法将无结构散乱数据自动生成合理有效的T网格,最后将曲面重构模型转化为最优化问题,并由最小二乘法求解,同时在误差较大的区域辅以T样条的局部修正,以使重建曲面与原网格面的最大误差小于指定的误差值。由于该新的曲面重建方法是一个基于细节的重建方法,因此采样点密集区域所插入的T网格点也就相应地增多,这样既抓住了网格曲面的特征,又能很好地减少过多的T网格控制顶点,这就提高了算法效率。另外,该新算法还具有高效、易操作、能适应复杂曲面重建、曲面自动生成且满足相应精度要求等优点。重构结果显示,该新的曲面重建算法不仅重构应用范围广,且重构精度高。     

Quadratic approximation to plane parametric curves and its application in approximate implicitization

Expressing complex curves with simple parametric curve segments is widely used in computer graphics, CAD and so on. This paper applies rational quadratic B-spline curves to give a global C ¹ continuous approximation to a large class of plane parametric curves including rational parametric curves. Its application in approximate implicitization is also explored. The approximated parametric curve is first divided into intrinsic triangle convex segments which can be efficiently approximated with rational quadratic Bézier curves. With this approximation, we keep the convexity and the cusp (sharp) points of the approximated curve with simple computations. High accuracy approximation is achieved with a small number of quadratic segments. Experimental results are given to demonstrate the operation and efficiency of the algorithm.     

Accuracy-Based Sampling and Reconstruction with Adaptive Meshes for Parallel Hierarchical Triangulation

Recent advances in range finding techniques have made the task of acquiring surface data for 3-D objects easier and more accurate. With most advanced techniques, range and color data are acquired simultaneously. Since the number of such acquired data is generally very large, a surface model capable of compressing data while maintaining a specified accuracy is required. The objective of this work is to construct a polyhedral representation of input data for surfaces. This representation adapts to local intrinsic surface properties while preserving their discontinuities. In this paper, we present an accuracy-based adaptive sampling and reconstruction technique for hierarchical triangulation of 3D objects. We have developed a parallel algorithm for adaptive mesh generation that recursively bisects mesh elements by increasing the number of mesh nodes according to local surface properties, such as surface orientation, curvature, and color. The recursive subdivision based on such viewpoint-invariant properties yields a hierarchical surface triangulation that is intrinsic to the surface. This approach also satisfies the absolute accuracy criteria, since nodes are generated as required until the entire surface has been approximated within a specified level of accuracy. We have also developed a parallel algorithm that detects and preserves both depth (C⁰) and orientation (C¹) discontinuities, without the formation of cracks which normally occur during independent subdivision. The algorithm has been successfully applied to adaptive sampling and reconstruction of both range and color images of human faces and Japanese antique dolls with fine grained color-texture.     

参数曲面网格生成的改进波前法

采用从曲面两条边界向曲面中心推进的方法．避免了常规波前法中由于曲面角点的不良形态导致网格规划的失败和生成低质量网格．提出了一种新的节点生成方法,直接在三维空间中生成节点,然后映射到参数平面,使得在平面上进行节点及单元的合法性检查成为可能．针对从两侧推进的波前法,给出一种新的判断网格收敛的疗法．算例表明．文中方法易于实施、稳定性好,生成的网格质量高．     

Triangulation of <Emphasis Type="Italic">p</Emphasis>-Order Parametric Surfaces

The generation of triangulations on p-order parametric surfaces is a fundamental first step to numerical solutions for multidomain problems involving complex geometries such as those encountered in biological fluid dynamics and other applications. In this study we develop a novel, computationally efficient method for generating triangulations in computational space, which, under parametric mapping, are of high geometric quality. Computational efficiency is maintained over parametric orders (p) through approximating the parametric surface by a grid of simplified vector functions. Unlike other length metric approximations, a maximum bound on the error introduced to the calculation of lengths by this approximation is defined to ensure the fidelity of the transformation. This technique is applied to three parametric functions which demonstrate its robustness in handling high mesh distortions, singularities, and high order surfaces. Further, three complex high-order biological finite element meshes are triangulated. High mesh quality and a linear relationship between triangle generation and CPU time is observed for each of these meshes.     

几何自适应参数曲面网格生成

为满足有限元分析的需要,针对参数曲面提出一种几何自适应的网格生成方法.通过黎曼度量控制下的曲面约束Delaunay三角化获得曲面中轴,将其用于自动识别曲面邻近特征,并通过曲率计算自动识别曲率特征;根据邻近特征和曲率特征,融合传统网格尺寸控制技术控制边界曲线离散,并创建密度场;结合映射法和前沿推进技术对组合参数曲面生成几何自适应的网格.实验结果表明,该方法能够处理复杂的几何外形,生成的网格具有很好的自适应效果和质量.     

On the meshing of trimmed 3D surfaces

A novel approach for generating quadrilateral meshes on trimmed three-dimensional surfaces is proposed. The parametric plane to Cartesian space mapping technique is extensively employed in this approach. Newly defined ‘separators’, are created on a given surface and nodes are generated on them. The relationship between nodes and separators, which is invariant in both the parametric plane and Cartesian space, is maintained for the ease of triangulation. Trimmed surfaces are discretized and the resulting meshes are presented to validate the proposed algorithm.     

Continuous point projection to planar freeform curves using spiral curves

We present an efficient algorithm for projecting a continuously moving query point to a family of planar freeform curves. The algorithm is based on the one-sided Hausdorff distance from the trajectory curve (of the query point) to the planar curves. Using a bounding volume hierarchy (BVH) of the planar curves, we estimate an upper bound [`(h)]\overline{h} of the one-sided Hausdorff distance and eliminate redundant curve segments when they are more than distance [`(h)]\overline{h} away from the trajectory curve. Recursively subdividing the trajectory curve and repeating the same elimination procedure to the BVH of the remaining curves, we can efficiently determine where to project the moving query point. The explicit continuous point projection is then interpreted as a curve reparameterization problem, for which we propose a few simple approximation techniques. Using several experimental results, we demonstrate the effectiveness of the proposed approach.     

Parameterization and parametric design of mannequins

This paper presents a novel feature based parameterization approach of human bodies from the unorganized cloud points and the parametric design method for generating new models based on the parameterization. The parameterization consists of two phases. First, the semantic feature extraction technique is applied to construct the feature wireframe of a human body from laser scanned 3D unorganized points. Secondly, the symmetric detail mesh surface of the human body is modeled. Gregory patches are utilized to generate G¹ continuous mesh surface interpolating the curves on feature wireframe. After that, a voxel-based algorithm adds details on the smooth G¹ continuous surface by the cloud points. Finally, the mesh surface is adjusted to become symmetric. Compared to other template fitting based approaches, the parameterization approach introduced in this paper is more efficient. The parametric design approach synthesizes parameterized sample models to a new human body according to user input sizing dimensions. It is based on a numerical optimization process. The strategy of choosing samples for synthesis is also introduced. Human bodies according to a wide range of dimensions can be generated by our approach. Different from the mathematical interpolation function based human body synthesis methods, the models generated in our method have the approximation errors minimized. All mannequins constructed by our approach have consistent feature patches, which benefits the design automation of customized clothes around human bodies a lot.     

Freeform Shape Representations for Efficient Geometry Processing

The most important concepts for the handling and storage of freeform shapes in geometry processing applications are parametric representations and volumetric representations. Both have their specific advantages and drawbacks. While the algebraic complexity of volumetric representations is independent from the shape complexity, the domain of a parametric representation usually has to have the same structure as the surface itself (which sometimes makes it necessary to update the domain when the surface is modified). On the other hand, the topology of a parametrically defined surface can be controlled explicitly while in a volumetric representation, the surface topology can change accidentally during deformation. A volumetric representation reduces distance queries or inside/outside tests to mere function evaluations but the geodesic neighborhood relation between surface points is difficult to resolve. As a consequence, it seems promising to combine parametric and volumetric representations to effectively exploit both advantages. In this talk, a number of projects are presented and discussed in which such a combination leads to efficient and numerically stable algorithms for the solution of various geometry processing tasks. Applications include global error control for mesh decimation and smoothing, topology control for level‐set surfaces, and shape modeling with unstructured point clouds.     

Interpolating an Unlimited Number of Curves Meeting at Extraordinary Points on Subdivision Surfaces*

Interpolating curves by subdivision surfaces is one of the major constraints that is partially addressed in the literature. So far, no more than two intersecting curves can be interpolated by a subdivision surface such as Doo‐Sabin or Catmull‐Clark surfaces. One approach that has been used in both of theses surfaces is the polygonal complex approach where a curve can be defined by a control mesh rather than a control polygon. Such a definition allows a curve to carry with it cross derivative information which can be naturally embodied in the mesh of a subdivision surface. This paper extends the use of this approach to interpolate an unlimited number of curves meeting at an extraordinary point on a subdivision surface. At that point, the curves can all meet with either C ⁰ or C ¹ continuity, yet still have common tangent plane. A straight forward application is the generation of subdivision surfaces through 3‐regular meshes of curves for which an easy interface can be used.     

Geometric surface mesh optimization

This paper presents a surface mesh optimization method suitable to obtain a geometric finite element mesh, given an initial arbitrary surface triangulation. The first step consists of constructing a geometric support, continuous, associated with the initial surface triangulation, which represents an adequate approximation of the underlying surface geometry. The initial triangulation is then optimized with respect to this geometry as well as to the element shape quality. A specific application of this technique to the geometric mesh simplification is then outlined, which aims at reducing the number of mesh entities while preserving the geometric approximation of the surface. Several examples of surface meshes intended for different application areas emphasize the efficiency of the proposed approach. Received: 11 September 1997 / Accepted: 19 February 1998     

Evolution of T-spline level sets for meshing non-uniformly sampled and incomplete data

Given a large set of unorganized point sample data, we propose a new framework for computing a triangular mesh representing an approximating piecewise smooth surface. The data may be non-uniformly distributed, noisy, and may contain holes. This framework is based on the combination of two types of surface representations, triangular meshes and T-spline level sets, which are implicit surfaces defined by refinable spline functions allowing T-junctions. Our method contains three main steps. Firstly, we construct an implicit representation of a smooth (C ² in our case) surface, by using an evolution process of T-spline level sets, such that the implicit surface captures the topology and outline of the object to be reconstructed. The initial mesh with high quality is obtained through the marching triangulation of the implicit surface. Secondly, we project each data point to the initial mesh, and get a scalar displacement field. Detailed features will be captured by the displaced mesh. Finally, we present an additional evolution process, which combines data-driven velocities and feature-preserving bilateral filters, in order to reproduce sharp features. We also show that various shape constraints, such as distance field constraints, range constraints and volume constraints can be naturally added to our framework, which is helpful to obtain a desired reconstruction result, especially when the given data contains noise and inaccuracies.