A framework for quad/triangle subdivision surface fitting: Application to mechanical objects

In this paper we present a new framework for subdivision surface approximation of three‐dimensional models represented by polygonal meshes. Our approach, particularly suited for mechanical or Computer Aided Design (CAD) parts, produces a mixed quadrangle‐triangle control mesh, optimized in terms of face and vertex numbers while remaining independent of the connectivity of the input mesh. Our algorithm begins with a decomposition of the object into surface patches. The main idea is to approximate the region boundaries first and then the interior data. Thus, for each patch, a first step approximates the boundaries with subdivision curves (associated with control polygons) and creates an initial subdivision surface by linking the boundary control points with respect to the lines of curvature of the target surface. Then, a second step optimizes the initial subdivision surface by iteratively moving control points and enriching regions according to the error distribution. The final control mesh defining the whole model is then created assembling every local subdivision control meshes. This control polyhedron is much more compact than the original mesh and visually represents the same shape after several subdivision steps, hence it is particularly suitable for compression and visualization tasks. Experiments conducted on several mechanical models have proven the coherency and the efficiency of our algorithm, compared with existing methods.     

Partitioning 3D surface meshes using watershed segmentation

This paper describes a method for partitioning 3D surface meshes into useful segments. The proposed method generalizes morphological watersheds, an image segmentation technique, to 3D surfaces. This surface segmentation uses the total curvature of the surface as an indication of region boundaries. The surface is segmented into patches, where each patch has a relatively consistent curvature throughout, and is bounded by areas of higher, or drastically different, curvature. This algorithm has applications for a variety of important problems in visualization and geometrical modeling including 3D feature extraction, mesh reduction, texture mapping 3D surfaces, and computer aided design     

Surface Fairing towards Regular Principal Curvature Line Networks

Freeform surfaces whose principal curvature line network is regularly distributed, are essential to many real applications like CAD modeling, architecture design, and industrial fabrication. However, most designed surfaces do not hold this nice property because it is hard to enforce such constraints in the design process. In this paper, we present a novel method for surface fairing which takes a regular distribution of the principal curvature line network on a surface as an objective. Our method first removes the high‐frequency signals from the curvature tensor field of an input freeform surface by a novel rolling guidance tensor filter, which results in a more regular and smooth curvature tensor field, then deforms the input surface to match the smoothed field as much as possible. As an application, we solve the problem of approximating freeform surfaces with regular principal curvature line networks, discretized by quadrilateral meshes. By introducing the circular or conical conditions on the quadrilateral mesh to guarantee the existence of discrete principal curvature line networks, and minimizing the approximate error to the original surface and improving the fairness of the quad mesh, we obtain a regular discrete principal curvature line network that approximates the original surface. We evaluate the efficacy of our method on various freeform surfaces and demonstrate the superiority of the rolling guidance tensor filter over other tensor smoothing techniques. We also utilize our method to generate high‐quality circular/conical meshes for architecture design and cyclide spline surfaces for CAD modeling.     

基于区域离散曲率的三维网格分水岭分割

针对离散曲率估计对噪声敏感且特征值计算量大的特点提出了基于区域离散曲率的三维网格分水岭分割算法。寻找三维模型显著特征点;对三维模型进行预分割,确定分割带;在分割带区域上计算离散曲度极值点,利用测地距离和曲度极值点对三维模型进行分水岭分割。算法在分割前无需进行网格去噪,实验结果证明,对主体分支明显的模型具有较高的分割边缘准确度和较快的分割速度。     

Patch layout from feature graphs

The structuring of surface meshes is a labor intensive task in reverse engineering. For example, in CAD, scanned triangle meshes must be divided into characteristic/uniform patches to enable conversion into high-level spline surfaces. Typical industrial techniques, like rolling ball blends, are very labor intensive.We provide a novel, robust and quick algorithm for the automatic generation of a patch layout based on a topology consistent feature graph. The graph separates the surface along feature lines into functional and geometric building blocks. Our algorithm then thickens the edges of the feature graph and forms new regions with low varying curvature. Further, these new regions-so-called fillets and node patches-will have highly smooth boundary curves, making the algorithm an ideal preprocessor for a subsequent spline fitting algorithm.     

An efficient and robust algorithm for 3D mesh segmentation

This paper presents an efficient and robust algorithm for 3D mesh segmentation. Segmentation is one of the main areas of 3D object modeling. Most segmentation methods decompose 3D objects into parts based on curvature analysis. Most of the existing curvature estimation algorithms are computationally costly. The proposed algorithm extracts features using Gaussian curvature and concaveness estimation to partition a 3D model into meaningful parts. More importantly, this algorithm can process highly detailed objects using an eXtended Multi-Ring (XMR) neighborhood based feature extraction. After feature extraction, we also developed a fast marching watershed-based segmentation algorithm followed by an efficient region merging scheme. Experimental results show that this segmentation algorithm is efficient and robust.     

Triangulation of 3D surfaces

A simple generator of graded triangular meshes on spatial surfaces is introduced in this paper. The algorithm is based on the approximation of the surface by tensor product polynomial patches which are uniquely mappable on a planar parametric space. Each of the patches is triangulated separately in its parametric space, using modified advancing front technique allowing for generation of pre-stretched elements, and the obtained triangulation is mapped back onto the original surface. Large effort has been devoted to the treatment of singularities arising on surfaces approximated by degenerated patches.     

Procedural CAD Model Edge Tolerance Negotiation for Surface Meshing

Geometrical models output from CAD software often require modification before they may be used for analysis-quality mesh generation. This is due primarily to the inconsistencies in tolerances used by the CAD operator and the tolerances required for analysis. This paper presents a method for construction of watertight surface meshes directly on imperfect non-modified CAD models. The method is based on a hierarchical grid topology structure that defines a surface mesh by a grid and a collection of curves defining the boundary. Curve boundaries on component surfaces are iteratively split and merged according to user-set tolerances, allowing adjacent surface meshes to become computationally watertight via their shared edge curves. The collection of watertight surface meshes may then be made model-inde-pendent through interactive agglomeration of the surface meshes, followed by refinement and decimation sweeps to remove artifacts of original surface edges. Interactive procedures used for difficult cases are also explained, as are ongoing efforts for further automation.     

Automatic recognition of features from freeform surface CAD models

This paper reports the design and implementation of a system for automatic recognition of features from freeform surface CAD models of sheet metal parts represented in STL format. The developed methodology has three major steps viz. STL model preprocessing, Region segmentation and automated Feature recognition. The input CAD model is preprocessed to get a healed and topology enriched STL model. A new hybrid region segmentation algorithm based on both edge- and region-based approaches has been developed to segment the preprocessed STL model into meaningful regions. Geometrical properties of facets, edges and vertices such as gauss and mean curvature at vertices, orientations of facet normals, shape structure of triangles, dihedral edge angle (angle between facets), etc. have been computed to identify and classify the regions. Feature on a freeform surface is defined as a set of connected meaningful regions having a particular geometry and topology which has some significance in design and manufacturing. Feature recognition rules have been formulated for recognizing a variety of protrusion and depression features such as holes, bends, darts, beads, louvres, dimples, dents, ridges/channels (blind and through) etc. occurring on automotive sheet metal panels. The developed system has been extensively tested with various industrial sheet metal parts and is found to be robust and consistent. The features data can be post processed and linked to various downstream CAD/CAM applications like automated process planning, sheet metal tool design, refinement of FEM meshes and product redesign.     

Filling N-Sided Regions by Quad Meshes for Subdivision Surfaces

Given an n-sided region bounded by a loop of n polylines, we present a general algorithm to fill such a region by a quad mesh suitable for a subdivision scheme. Typically, the approach consists of two phases: the topological phase and the geometrical phase. In the first part, the connectivity of the mesh is based on determining a partitioning of the region into rectangular subregions across which regular grid could be constructed. The geometrical phase generalizes discrete Coon's patches to position the vertices in the 3D space. The generated mesh could be taken as input to any quad-based subdivision scheme, such as that of Catmull–Clark or Doo–Sabin to generate the corresponding limit surface. The goal of the algorithm is to generate smooth meshes with minimum number and less valence of extraordinary vertices deemed undesirable in such subdivision schemes.     

不可逆的3维网格模型数字水印算法

提出一种基于奇异值分解的三角网格模型数字水印算法,该算法主要思想在于把水印信息嵌入到奇异值为零的地方,由于零值的特点使得算法不可逆,从而成功抵御了解释攻击。该算法简单,并可以快速嵌入到大规模三角网格模型里。通过几种不同的攻击实验,验证了算法具有很好的鲁棒性,最后还对构造不可逆算法的必要条件进行了总结。     

Tensor rank one differential graph preserving analysis for facial expression recognition

This paper presents a new dimensionality reduction algorithm for multi-dimensional data based on the tensor rank-one decomposition and graph preserving criterion. Through finding proper rank-one tensors, the algorithm effectively enhances the pairwise inter-class margins and meanwhile preserves the intra-class local manifold structure. In the algorithm, a novel marginal neighboring graph is devised to describe the pairwise inter-class boundaries, and a differential formed objective function is adopted to ensure convergence. Furthermore, the algorithm has less computation in comparison with the vector representation based and the tensor-to-tensor projection based algorithms. The experiments for the basic facial expressions recognition show its effectiveness, especially when it is followed by a neural network classifier.     

Generation of bi-monotone patches from quadrilateral mesh for reverse engineering

Thanks to recent improvements, computational methods can now be used to convert triangular meshes into quadrilateral meshes so that the quadrilateral elements capture well the principal curvature directional fields of surfaces and intrinsically have surface parametric values. In this study, a quadrilateral mesh generated using the mixed integer quadrangulation technique of Bommes et al. is used for input. We first segment a quadrilateral mesh into four-sided patches. The feature curves inside these patches are then detected and are constrained to act as the patch boundaries. Finally, the patch configuration is improved to generate large patches. The proposed method produces bi-monotone patches, which are appropriate for use in reverse engineering to capture the surface details of an object. A shape control parameter that can be adjusted by the user during the patch generation process is also provided to support the creation of patches with good bi-monotone shapes. This study mainly targets shape models of mechanical parts consisting of major smooth surfaces with feature curves between them.     

Boundary-trimmed 3D triangular mesh segmentation based on iterative merging strategy

This paper presents a segmentation algorithm for 3D triangular mesh data. The proposed algorithm uses iterative merging of adjacent triangle pairs based on their orientations. The oversegmented regions are merged again in an iterative region merging process. Finally, the noisy boundaries of each region are refined. The boundaries of each region contain perceptually important geometric information of the entire mesh model. According to the purpose of the segmentation, the proposed mesh-segmentation algorithm supports various types of segmentation by controlling parameters.     

Anisotropic geodesics for live‐wire mesh segmentation

We present an interactive method for mesh segmentation that is inspired by the classical live‐wire interaction for image segmentation. The core contribution of the work is the definition and computation of wires on surfaces that are likely to lie at segment boundaries. We define wires as geodesics in a new tensor‐based anisotropic metric, which improves upon previous metrics in stability and feature‐awareness. We further introduce a simple but effective mesh embedding approach that allows geodesic paths in an anisotropic path to be computed efficiently using existing algorithms designed for Euclidean geodesics. Our tool is particularly suited for delineating segmentation boundaries that are aligned with features or curvature directions, and we demonstrate its use in creating artist‐guided segmentations.     

Object recognition using shape-from-shading

Investigates whether surface topography information extracted from intensity images using a shape-from-shading (SFS) algorithm can be used for the purposes of 3D object recognition. We consider how curvature and shape-index information delivered by this algorithm can be used to recognize objects based on their surface topography. We explore two contrasting object recognition strategies. The first of these is based on a low-level attribute summary and uses histograms of curvature and orientation measurements. The second approach is based on the structural arrangement of constant shape-index maximal patches and their associated region attributes. We show that region curvedness and a string ordering of the regions according to size provides recognition accuracy of about 96 percent. By polling various recognition schemes, including a graph matching method, we show that a recognition rate of 98-99 percent is achievable     

Bias–Variance Analysis for Controlling Adaptive Surface Meshes

This paper presents a statistical methodology for exerting control over adaptive surface meshes. The goal is to develop an adaptive mesh which uses split and merge operations to control the distribution of planar or quadric surface patches. The novelty of the work reported in this paper is to focus on the variance–bias tradeoff that exists between the size of the fitted patches and their associated parameter variances. In particular, we provide an analysis which shows that there is an optimal patch area. This area offers the best compromise between the noise-variance, which decreases with increasing area, and the model-bias, which increases in a polynomial manner with area. The computed optimal areas of the local surface patches are used to exert control over the facets of the adaptive mesh. We use a series of split and merge operations to distribute the faces of the mesh so that each resembles as closely as possible its optimal area. In this way the mesh automatically selects its own density by adjusting the number of control-points or nodes. We provide experiments on both real and synthetic data. This experimentation demonstrates that our mesh is capable of efficiently representing high curvature surface detail.     

Medial axis of a planar region by offset self-intersections

The medial axis (MA) of a planar region is the locus of those maximal disks contained within its boundary. This entity has many CAD/CAM applications. Approximations based on the Voronoi diagram are efficient for linear-arc boundaries, but such constructions are more difficult if the boundary is free. This paper proposes an algorithm for free-form boundaries that uses the relation between MA and offsets. It takes the curvature information from the boundary in order to find the self-intersections of successive offset curves. These self-intersection points belong to the MA and can be interpolated to obtain an approximation in Bézier form. This method also approximates the medial axis transform by using the offset distance to each self-intersection.     

An algorithm for filling complex holes in reverse engineering

The existence of holes in meshes makes it difficult for mesh operations, especially when comes to model rebuilding, rapid prototyping and finite element analysis. Existing hole-filling algorithms are capable of filling holes on small and smooth regions of a model. For large holes with complex boundaries or in curved region, they may not result in satisfactory results. This paper proposes an algorithm which first split the holes into flatter ones and then split the complex holes based the concept of edge expansion. It incrementally splits a complex hole into simple ones by respecting the 3D shape of its boundary and the neighboring meshes, and then fills each resulting simple hole with planar triangulation. The proposed algorithm works well for a variety of complex holes and can better preserve the detailed features of the original mesh.     

Direct extraction of surface meshes from implicitly represented heterogeneous volumes

This paper describes a novel algorithm to extract surface meshes directly from implicitly represented heterogeneous models made of different constituent materials. Our approach can directly convert implicitly represented heterogeneous objects into a surface model separating homogeneous material regions, where every homogeneous region in a heterogeneous structure is enclosed by a set of two-manifold surface meshes. Unlike other discretization techniques of implicitly represented heterogeneous objects, the intermediate surfaces between two constituent materials can be directly extracted by our algorithm. Therefore, it is more convenient to adopt the surface meshes from our approach in the boundary element method (BEM) or as a starting model to generate volumetric meshes preserving intermediate surfaces for the finite element method (FEM). The algorithm consists of three major steps: firstly, a set of assembled two-manifold surface patches coarsely approximating the interfaces between homogeneous regions are extracted and segmented; secondly, signed distance fields are constructed such that each field expresses the Euclidean distance from points to the surface of one homogeneous material region; and finally, coarse patches generated in the first step are dynamically optimized to give adaptive and high-quality surface meshes. The manifold topology is preserved on each surface patch.