Fitting Sharp Features with Loop Subdivision Surfaces

Various methods have been proposed for fitting subdivision surfaces to different forms of shape data (e.g., dense meshes or point clouds), but none of these methods effectively deals with shapes with sharp features, that is, creases, darts and corners. We present an effective method for fitting a Loop subdivision surface to a dense triangle mesh with sharp features. Our contribution is a new exact evaluation scheme for the Loop subdivision with all types of sharp features, which enables us to compute a fitting Loop subdivision surface for shapes with sharp features in an optimization framework. With an initial control mesh obtained from simplifying the input dense mesh using QEM, our fitting algorithm employs an iterative method to solve a nonlinear least squares problem based on the squared distances from the input mesh vertices to the fitting subdivision surface. This optimization framework depends critically on the ability to express these distances as quadratic functions of control mesh vertices using our exact evaluation scheme near sharp features. Experimental results are presented to demonstrate the effectiveness of the method.     

Conjugate-Gradient Progressive-Iterative Approximation for Loop and Catmull-Clark Subdivision Surface Interpolation

Loop and Catmull-Clark are the most famous approximation subdivision schemes, but their limit surfaces do not interpolate the vertices of the given mesh. Progressive-iterative approximation (PIA) is an efficient method for data interpolation and has a wide range of applications in many fields such as subdivision surface fitting, parametric curve and surface fitting among others. However, the convergence rate of classical PIA is slow. In this paper, we present a new and fast PIA format for constructing interpolation subdivision surface that interpolates the vertices of a mesh with arbitrary topology. The proposed method, named Conjugate-Gradient Progressive-Iterative Approximation (CG-PIA), is based on the Conjugate-Gradient Iterative algorithm and the Progressive Iterative Approximation (PIA) algorithm. The method is presented using Loop and Catmull-Clark subdivision surfaces. CG-PIA preserves the features of the classical PIA method, such as the advantages of both the local and global scheme and resemblance with the given mesh. Moreover, CG-PIA has the following features. 1) It has a faster convergence rate compared with the classical PIA and W-PIA. 2) CG-PIA avoids the selection of weights compared with W-PIA. 3) CG-PIA does not need to modify the subdivision schemes compared with other methods with fairness measure. Numerous examples for Loop and Catmull-Clark subdivision surfaces are provided in this paper to demonstrate the efficiency and effectiveness of CG-PIA.     

Computation of the minimum distance between two Bézier curves/surfaces

We present an efficient and robust method based on the culling approach for computing the minimum distance between two Bézier curves or Bézier surfaces. Our contribution is a novel dynamic subdivision scheme that enables our method to converge faster than previous methods based on binary subdivision.     

Efficient skeleton-guided displaced subdivision surfaces

Displacement mapping is a computer graphics technique that uses scalar offsets along normals on a base surface to represent and render a model with highly geometric details. The technique natively compresses the model and saves memory I/O. A subdivision surface is the ideal base surface, due to its good geometric properties, such as arbitrary topology, global smoothness, and multi-resolution via hardware tessellation, among others. Two of the main challenges in displacement mapping representation are constructing the base surface faithfully and generating displacement maps efficiently. In this paper, we propose an efficient skeleton-guided displaced subdivision surfaces method. The construction of the base mesh is guided by a sketched skeleton. To make the shape of the base surface fit the input model well, we develop an efficient progressive GPU-based subdivision fitting method. Finally, a GPU-based raycasting method is proposed to sample the input model and generate the displacement maps. The experimental results demonstrate that the proposed method can efficiently generate a high-quality displacement mapping representation. Compared with the traditional displaced subdivision surface method, the proposed method is more suitable for the modern rendering pipeline and has higher efficiency.     

Subdivision Schemes for Thin Plate Splines

Thin plate splines are a well known entity of geometric design. They are defined as the minimizer of a variational problem whose differential operators approximate a simple notion of bending energy. Therefore, thin plate splines approximate surfaces with minimal bending energy and they are widely considered as the standard "fair" surface model. Such surfaces are desired for many modeling and design applications.
Traditionally, the way to construct such surfaces is to solve the associated variational problem using finite elements or by using analytic solutions based on radial basis functions. This paper presents a novel approach for defining and computing thin plate splines using subdivision methods. We present two methods for the construction of thin plate splines based on subdivision: A globally supported subdivision scheme which exactly minimizes the energy functional as well as a family of strictly local subdivision schemes which only utilize a small, finite number of distinct subdivision rules and approximately solve the variational problem. A tradeoff between the accuracy of the approximation and the locality of the subdivision scheme is used to pick a particular member of this family of subdivision schemes.
Later, we show applications of these approximating subdivision schemes to scattered data interpolation and the design of fair surfaces. In particular we suggest an efficient methodology for finding control points for the local subdivision scheme that will lead to an interpolating limit surface and demonstrate how the schemes can be used for the effective and efficient design of fair surfaces.     

Consistent Volumetric Discretizations Inside Self‐Intersecting Surfaces

Decades of research have culminated in a robust geometry processing pipeline for surfaces. Most steps in this pipeline, like deformation, smoothing, subdivision and decimation, may create self‐intersections. Volumetric processing of solid shapes then becomes difficult, because obtaining a correct volumetric discretization is impossible: existing tet‐meshing methods require watertight input. We propose an algorithm that produces a tetrahedral mesh that overlaps itself consistently with the self‐intersections in the input surface. This enables volumetric processing on self‐intersecting models. We leverage conformalized mean‐curvature flow, which removes self‐intersections, and define an intrinsically similar reverse flow, which prevents them. We tetrahedralize the resulting surface and map the mesh inside the original surface. We demonstrate the effectiveness of our method with applications to automatic skinning weight computation, physically based simulation and geodesic distance computation.     

基于凸包特征的细分曲面求交研究

主要针对具有凸包特征的细分曲面提出了一种有效的求交的方法,该方法适用于任意具有凸包特征的细分曲面中.该方法主要是利用二部图跟踪两个细分曲面中可能相交的面.在应用二部图的基础上,选择半边数据结构,应用轴向包围盒法进行相交检测,使得具有凸包特征的细分曲面的求交得以实现.     

Extrapolating Acceleration Algorithms for Finding B-Spline Intersections Using Recursive Subdivision Techniques

The new algorithms for finding B-Spline or Bezier curves and surfaces intersections using recursive subdivision techniques are presented,which use extrapolating acceleration technique,and have convergent precision of order 2.Matrix method is used to subdivide the curves or surfaces which makes the subdivision more concise and intuitive.Dividing depths of Bezier curves and surfaces are used to subdivide the curves or surfaces adaptively.Therefore the convergent precision and the computing efficiency of finding the intersections of curves and surfaces have been improved by the methods proposed in the paper.     

Geometric algorithm for point projection and inversion onto Bézier surfaces

This paper presents an accurate and efficient method for the computation of both point projection and inversion onto Bézier surfaces. First, these two problems are formulated in terms of solution of a polynomial equation with u and v variables expressed in the Bernstein basis. Then, based on subdivision of the Bézier surface and the recursive quadtree decomposition, a novel solution method is proposed. The computation of point projection is shown to be equivalent to the geometrically intuitive intersection of a surface with the u-v plane. Finally, by comparing the distances between the test point and the candidate points, the closest point is found. Examples illustrate the feasibility of this method.     

An improved rendering technique for ray tracing Bézier and B‐spline surfaces

Both numerical and subdivision methods are widely used approaches for ray tracing parametric surfaces. However, the expense of finding the ray–surface intersection points is a major drawback. Thus, simpler and less memory‐intensive strategies are needed to improve these methods without further complicating them. This work presents an efficient algorithm for enhancing the performance of both numerical and subdivision methods. The proposed technique can be extended to most applications based on these two methods. The computational time of both approaches is improved by 16–40%. Copyright © 2000 John Wiley & Sons, Ltd.     

Method for intersecting algebraic surfaces with rational polynomial patches

The paper presents a hybrid algorithm for the computation of the intersection of an algebraic surface and a rational polynomial parametric surface patch. This algorithm is based on analytic representation of the intersection as an algebraic curve expressed in the Bernstein basis; automatic computation of the significant points of the curve using numerical techniques, subdivision and convexity properties of the Bernstein basis; partitioning of the intersection domain at these points; and tracing of the resulting monotonic intersection segments using coarse subdivision and faceting methods coupled with Newton techniques. The algorithm described in the paper treats intersections of arbitrary order algebraic surfaces with rational biquadratic and bicubic patches and introduces efficiency enhancements in the partitioning and tracing parts of the solution process. The algorithm has been tested with up to degree four algebraics and bicubic patches.     

一种带噪声的密集三角网格细分曲面拟合算法

实现了一个从带噪声的密集三角形拟合出带尖锐特征的细分曲面拟合系统.该系统包括了一种改进的基于图像双边滤波器的网格噪声去除方法,模型的尖锐特征提取以及保持尖锐特征的网格简化和拓扑优化.为了处理局部细节特征和模型数据量问题,提出了自适应细分方法,并将根据给定精度估计最少细分深度引入到细分曲面拟合系统中,使得拟合得到的细分曲面模型具有良好的细节特征和数据量小等特点.大量3D模型实验结果和实际工程应用结果表明了该细分曲面拟合系统的有效性.     

Algebraic pruning: a fast technique for curve and surface intersection

Computing the intersection of parametric and algebraic curves and surfaces is a fundamental problem in computer graphics and geometric modeling. This problem has been extensively studied in the literature and different techniques based on subdivision, interval analysis and algebraic formulation are known. For low degree curves and surfaces algebraic methods are considered to be the fastest, whereas techniques based on subdivision and Bézier clipping perform better for higher degree intersections. In this paper, we introduce a new technique of algebraic pruning based on the algebraic approaches and eigenvalue formulation of the problem. The resulting algorithm corresponds to computing only selected eigenvalues in the domain of intersection. This is based on matrix formulation of the intersection problem, power iterations and geometric properties of Bézier curves and surfaces. The algorithm prunes the domain and converges to the solutions rapidly. It has been applied to intersection of parametric and algebraic curves, ray tracing and curve-surface intersections. The resulting algorithm compares favorably with earlier methods in terms of performance and accuracy.     

基于加权渐进插值的Loop 细分曲面等距逼近

等距曲面在CAD/CAM 领域有着重要的作用,由于细分曲面没有整体解 析表达式,使得计算细分曲面等距比参数曲面更加困难。针对目前已有的两种等距面逼近算 法进行了改进,利用加权渐进插值技术避免了传统细分等距逼近算法产生网格偏移的问题。 此外,提出了针对边界等距处理方案,使得等距后的细分曲面在内部和边界都均匀等距。该 方法无需求解线性方程组,具有全局和局部特性,能够处理闭网格和开网格,为Loop 细分 曲面数控加工奠定了良好的基础算法。最后给出的实例验证了算法的有效性。     

Robust and Efficient Ray Intersection of Implicit Surfaces

The generation of ray traced images of a variety of surfaces plays a central role in computer graphics. One of the main operations in ray tracing is the calculation of intersections between rays and surfaces. In case of implicitly given surfaces the intersection problem can be formulated as that of finding the smallest non-negative root of an equation in one variable. If the root finding is carried out by means of conventional numerical methods based on point sampling (such as bisection, regula-falsi or Newton) the resulting image can be wrong, e.g. when the surface is thin the ray may "miss" the surface, which may result in an image with background color spots on the surface. To obtain robust intersection detection, methods based either on Lipschitz constants for the function and its derivative or an interval inclusions for the function and its derivative have been suggested. In this paper robust methods are obtained with interval inclusions in a variant of Alefeld-Hansens globally convergent method for computing and bounding all the roots of a single equation. Alefeld-Hansens method has been modified so instead of searching for all roots, a recursive depth-first search is carried out to obtain the smallest non-negative root. When compared to other methods suggested, it is found that this variant of Alefeld-Hansens method is not only robust but also an efficient method for finding the ray intersections.     

Geometric algorithm for point projection and inversion onto Bézier surfaces

This paper presents an accurate and efficient method for the computation of both point projection and inversion onto Bézier surfaces. First, these two problems are formulated in terms of solution of a polynomial equation with u and v variables expressed in the Bernstein basis. Then, based on subdivision of the Bézier surface and the recursive quadtree decomposition, a novel solution method is proposed. The computation of point projection is shown to be equivalent to the geometrically intuitive intersection of asurface with the u-ν plane. Finally, by comparing the distances between the test point and the candidate points, the closest point is found. Examples illustrate the feasibility of this method.     

Surface-to-surface intersections

Techniques for computing intersections of algebraic surfaces with piecewise rational polynomial parametric surface patches and intersections of two piecewise rational polynomial parametric surface patches are discussed. The techniques are classified using four categories-lattice evolution methods, marching methods, subdivision methods, and analytic methods-and their principal features are discussed. It is shown that some of these methods also apply to the general parametric surface-intersection problem     

A hybrid parallel solver for systems of multivariate polynomials using CPUs and GPUs

This paper deals with a problem of finding valid solutions to systems of polynomial constraints. Although there have been several quite successful algorithms based on domain subdivision to resolve this problem, some major issues are still demanding further research. Prime obstacles in developing an efficient subdivision-based polynomial constraint solver are the exhaustive, although hierarchical, search of the zero-set in the parameter domain, which is computationally demanding, and their scalability in terms of the number of variables. In this paper, we present a hybrid parallel algorithm for solving systems of multivariate constraints by exploiting both the CPU and the GPU multicore architectures. We dedicate the CPU for the traversal of the subdivision tree and the GPU for the multivariate polynomial subdivision. By decomposing the constraint solving technique into two different components, hierarchy traversal and polynomial subdivision, each of which is more suitable to CPUs and GPUs, respectively, our solver can fully exploit the availability of hybrid, multicore architectures of CPUs and GPUs. Furthermore, our GPU-based subdivision method takes advantage of the inherent parallelism in the multivariate polynomial subdivision. We demonstrate the efficacy and scalability of the proposed parallel solver through several examples in geometric applications, including Hausdorff distance queries, contact point computations, surface–surface intersections, ray trap constructions, and bisector surface computations. In our experiments, the proposed parallel method achieves up to two orders of magnitude improvement in performance compared to the state-of-the-art subdivision-based CPU solver.     

Direct Segmentation of Algebraic Models for Reverse Engineering

In Reverse Engineering a physical object is digitally reconstructed from a set of boundary points. In the segmentation phase these points are grouped into subsets to facilitate consecutive steps as surface fitting. In this paper we present a segmentation method with subsequent classification of simple algebraic surfaces. Our method is direct in the sense that it operates directly on the point set in contrast to other approaches that are based on a triangulation of the data set. The segmentation process involves a fast algorithm for k-nearest neighbors search and an estimation of first and second order surface properties. The first order segmentation, that is based on normal vectors, provides an initial subdivision of the surface and detects sharp edges as well as flat or highly curved areas. One of the main features of our method is to proceed by alternating the steps of segmentation and normal vector estimation. The second order segmentation subdivides the surface according to principal curvatures and provides a sufficient foundation for the classification of simple algebraic surfaces. If the boundary of the original object contains such surfaces the segmentation is optimized based on the result of a surface fitting procedure.     

Improved techniques for ray tracing parametric surfaces

Several techniques for acceleration of ray tracing parametric surfaces are presented. Some of these are entirely new to ray tracing, while others are improvements of previously known techniques. First a uniform spatial subdivision scheme is adapted to parametric surfaces. A new space- and time-efficient algorithm for finding raysurface intersections is introduced. It combines numerical and subdivision techniques, thus allowing utilization of ray coherence and greatly reducing the average ray-surface intersection time. Non-scanline sampling orders of the image plane are proposed that facilitate utilization of coherence. Finally, a method to handle reflected, refracted, and shadow rays in a more efficient manner is described. Results of timing tests indicating the efficiency of these techniques for various environments are presented.