Surface interpolation of meshes by geometric subdivision

Subdivision surfaces are generated by repeated approximation or interpolation from initial control meshes. In this paper, two new non-linear 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¹ 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.     

Surface intersection by switching from recursive subdivision to iterative refinement

This paper discusses an attempt to devise an efficient (involving minimal computations), accurate (numerically high precision), exhaustive (detecting all possible solutions), and robust (working without failures) method for detecting intersection of two parametric surfaces. The method starts with subdivision to ensure that all solutions are detected. Later it switches over to numerical iterative refinement for efficient and accurate evaluation of the intersection curve. The switching takes place only when the convergence of the refinement method is guaranteed. The necessary theory to arrive at a computable condition leading to this guarantee has been developed using fixed-point and contractionmapping theorems from topology and mathematical analysis. The implementation is discussed elaborating the data structures and the algorithms used for (1) detecting segments of the intersection curve, (2) generating points on these segments using refinement, and (3) tracing a continuous curve by identifying neighboring segments and joining them in order.     

Curve subdivision schemes for geometric modelling

A new binary four-point approximating subdivision scheme has been presented that generates the limiting curve of C ¹ continuity. A global tension parameter has been introduced to improve the performance of the binary four-point approximating subdivision scheme that generates a family of C ¹ limiting curves. The ternary four-point approximating subdivision scheme has also been introduced that generates a limiting curve of C ² continuity. The proposed schemes are close to being interpolating. The Laurent polynomial method has been used to investigate the order of derivative continuity of the schemes and Hölder exponents of the schemes have also been calculated. Performances of the subdivision schemes have been exposed by considering several examples.     

A cascadic geometric filtering approach to subdivision

A new approach to subdivision based on the evolution of surfaces under curvature motion is presented. Such an evolution can be understood as a natural geometric filter process where time corresponds to the filter width. Thus, subdivision can be interpreted as the application of a geometric filter on an initial surface. The concrete scheme is a model of such a filtering based on a successively improved spatial approximation starting with some initial coarse mesh and leading to a smooth limit surface.

In every subdivision step the underlying grid is refined by some regular refinement rule and a linear finite element problem is either solved exactly or, especially on fine grid levels, one confines to a small number of smoothing steps within the corresponding iterative linear solver. The approach closely connects subdivision to surface fairing concerning the geometric smoothing and to cascadic multigrid methods with respect to the actual numerical procedure. The derived method does not distinguish between different valences of nodes nor between different mesh refinement types. Furthermore, the method comes along with a new approach for the theoretical treatment of subdivision.     

细分参数对细分曲线形状的控制作用分析

多数有关细分法的文献侧重于研究细分法的构造、收敛性光滑性分析及其在光滑曲线曲面造型中的应用,少有文献致力于细分参数对细分曲线形状影响的理论分析。首先引入仿射坐标的观点,从几何直观的角度对三点ternary插值细分法中细分参数的几何意义进行研究。接着通过对细分法的C0和C1参数域及新顶点域的等价描述,从理论化的角度对细分参数对细分曲线形状的局部和整体控制作用进行分析,描述它们对细分曲线行为的影响。在给定初始数据的条件下,可通过对形状参数的适当选择来有的放矢地实现对三点ternary插值细分曲线曲面的形状调整和控制。该结果可用于工业领域中产品的外形设计及形状控制。     

Recursive subdivision without the convex hull property

Recursive subdivision is a standard technique in computer aided geometric design for intersecting and rendering curves and surfaces. The convergence of recursive subdivision is critical for its effective use. Bézier and B-spline curves and surfaces have recursive subdivision algorithms that are known to converge. We show more generally that if a recursive subdivision algorithm exists for a given curve or surface type, then convergence is guaranteed if the blending functions are continuous, form a partition of unity, and are linearly independent. Thus, convergence of recursive subdivision does not depend on the convex hull property. We also show that even in the absence of the convex hull property, it is possible to define termination tests based on the flatness of control polygons, and to construct intersection algorithms based on recursive subdivision. Examples are given of polynomial curves to which our theorems apply.     

Taxonomy of interpolation constraints on recursive subdivision curves

Published online: 14 May 2002     

A new algorithm for recursive estimation of parameters in controlled ARMA processes

A recursive algorithm for estimating the constant but unknown parameters of a controlled ARMA process is presented. The algorithm is a recursive version of an off-line algorithm using three stages of standard least-squares. In the first stage the parameters of a controlled AR model of degree p are estimated. The residuals used in this stage are employed in the second stage to estimate the parameters of a controlled ARMA process. The first two stages constitute a recursive version of Durbin's algorithm. The model obtained in the second stage is used to filter the input, output and residuals and these filtered variables are used in the final stage to obtain improved estimates of the controlled ARMA process. It is shown that the estimate is (globally) p-consistent, i.e. that the estimate converges a.s. as the number of data tends to infinity, to a vector which, in turn, converges to the true parameter vector as the degree p of the AR model tends to infinity.     

A new recursive identification algorithm for singularity free adaptive control

Reportedly, guaranteeing the controllability of the estimated system is a crucial problem in adaptive control. In this paper, we introduce a least-squares-based identification algorithm for stochastic SISO systems, which secures the uniform controllability of the estimated system and presents closed-loop identification properties similar to those of the least-squares algorithm. The proposed algorithm is recursive and, therefore, easily implementable. Its use, however, is confined to cases in which the parameter uncertainly is highly structured.     

Taxonomy of interpolation constraints on recursive subdivision surfaces

Published online: 14 May 2002     

曲面三参数binary细分法

在经典四点细分法的基础上,通过在曲线细分过程中引入三个参数,给出一种改进的细分曲线构造的算法,利用生成多项式等方法对细分法的一致收敛性、Ck连续性进行了分析。并把该方法扩展到曲面上,进而提出了曲面三参数binary细分法。在给定初始控制数据的条件下,可以通过对形状参数的适当选择来实现对细分极限曲面形状的调控。数值实验表明该算法较容易控制曲面形状,可方便地应用于工程实际,解决曲线、曲面位置调整和控制问题。     

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.     

Strong consistence of recursive identification for Wiener systems

The paper concerns identification of the Wiener system consisting of a linear subsystem followed by a static nonlinearity f(·) with no invertibility and structure assumption. Recursive estimates are given for coefficients of the linear subsystem and for the value f(v) at any fixed v. The main contribution of the paper consists in establishing convergence with probability one of the proposed algorithms to the true values. This probably is the first strong consistency result for this kind of Wiener systems. A numerical example is given, which justifies the theoretical analysis.     

A subdivision algorithm for axisymmetric sections

In the generation of curved surfaces through a subdivision process, Sabin and Doo applied and extended Chaikin's algorithm to three dimensions by using linear combinations of the vertices of a polyhedron. A similar smoothing subdivision algorithm was brought out by Catmull and Clark. This paper describes an alternative algorithm which uses a similar approach but applies to sections of axisymmetric objects. It shows that axisymmetric free-formed surfaces can be generated easily and effeciently.     

n-Dimensional multiresolution representation of subdivision meshes with arbitrary topology

We present a new model for the representation of n-dimensional multiresolution meshes. It provides a robust topological representation of arbitrary meshes that are combined in closely interlinked levels of resolution. The proposed combinatorial model is formalized through the mathematical model of combinatorial maps allowing us to give a general formulation, in any dimensions, of the topological subdivision process that is a key issue to robustly and soundly define mesh hierarchies. It fully supports multiresolution edition what allows the implementation of most mesh processing algorithms – like filtering or compression – for n-dimensional meshes with arbitrary topologies.We illustrate this model, in dimension 3, with an new truly multiresolution representation of subdivision volumes. It allows us to extend classical subdivision schemes to arbitrary polyhedrons and to handle adaptive subdivision with an elegant solution to compliance issues. We propose an implementation of this model as an effective and relatively inexpensive data structure.     

曲线插值的一种具有还圆性的细分方法

传统的线性四点插值细分方法不能表示圆等非多项式曲线,为了解决这种问题,基于几何特性提出了一种带有一个参数的四点插值型曲线细分方法。细分过程中,过相邻三插值点作圆,过相邻二插值点的圆弧有两个中点,将其加权平均得到新插值点,文中给出了插值公式和算法描述。所给方法具有还圆性,可以实现保凸性。实例分析对比了本方法与多种细分方法的差异,说明本方法是有效的,当参数取值较小时,曲线靠近控制多边形。     

保持尖锐特征的混合细分曲面生成

基于混合细分模式,提出了细分曲面尖锐特征生成方法,通过对初始混合控制网格上要生成的各种尖锐特征的顶点和边分别作标记,然后局部修改细分规则进行迭代细分,实现了光滑混合曲面上产生折痕、角点、刺点、尖点的尖锐特征效果,并对尖锐特征处的局部细分矩阵进行了详细的特征分析。实验结果表明,该文算法效果好,能很好地保持模型的尖锐特征。     

Catmull-Clark细分网格数据点拾取

针对将OpenGL选择拾取机制直接作用于Catmull-Clark细分网格数据点的拾取,可能会因细分网格数据量过大而导致名字堆栈溢出的问题,借鉴细分曲面求交的思想,提出一种新的细分网格数据点拾取方法.该方法通过提取拾取对象的邻域网格并进行局部细分,将对细分任意层次上网格数据点的拾取转化为对初始控制网格以及在达到细分层次要求以前每一次局部细分网格点、边、面的拾取和对最后一次局部细分网格数据点的拾取.采用多个拾取算例进行对比分析实验,当细分网格顶点数量较多时,所给拾取方法的拾取命名对象总量和拾取时间都远小于传统OpenGL选择拾取方法.实验结果表明,所给拾取方法能快速准确实现细分网格数据点的拾取,尤其适用于数据量较大的复杂细分模型,可有效避免因拾取名字堆栈溢出而导致的拾取错误.