渐进插值的LOOP曲面细分*

目前很多细分方法都存在不能用同一种方法处理封闭网格和开放网格的问题。对此,一种新的基于插值技术的LOOP曲面细分方法,其主要思想就是给定一个初始三角网格M,反复生成新的顶点,新顶点是通过其相邻顶点的约束求解得到的,从而构造一个新的控制网格M,在取极限的情况下,可以证明插值过程是收敛的;因为生成新顶点使用的是与其相连顶点的约束求解得到的,本质上是一种局部方法,所以,该方法很容易定义。它在本地方法和全局方法中都有优势,能处理任意顶点数量和任意拓扑结构的网格,从而产生一个光滑的曲面并忠实于给定曲面的形状,其控制     

Approximating digital 3D shapes by rational Gaussian surfaces

A method for approximating spherical topology digital shapes by rational Gaussian (RaG) surfaces is presented. Points in a shape are parametrized by approximating the shape with a triangular mesh, determining parameter coordinates at mesh vertices, and finding parameter coordinates at shape points from interpolation of parameter coordinates at mesh vertices. Knowing the locations and parameter coordinates of the shape points, the control points of a RaG surface are determined to approximate the shape with a required accuracy. The process starts from a small set of control points and gradually increases the control points until the error between the surface and the digital shape reduces to a required tolerance. Both triangulation and surface approximation proceed from coarse to fine. Therefore, the method is particularly suitable for multiresolution creation and transmission of digital shapes over the Internet. Application of the proposed method in editing of 3D shapes is demonstrated.     

三次NURBS曲线的插值方法

本文提出了一个用于3次NURBS曲线插值的新方法,该方法首先用二次规划算出控制顶点的权因子,然后反算出所有的控制顶点,它能确保由型值点的权W_i(>0)所算出的控制顶点的权也均大于0,插值曲线具有C~2连续性,当W_i均为一个大于0的常数时,插值曲线退化为非均匀B样条曲线。     

Similarity based interpolation using Catmull–Clark subdivision surfaces

A new method for constructing a Catmull–Clark subdivision surface (CCSS) that interpolates the vertices of a given mesh with arbitrary topology is presented. The new method handles both open and closed meshes. Normals or derivatives specified at any vertices of the mesh (which can actually be anywhere) can also be interpolated. The construction process is based on the assumption that, in addition to interpolating the vertices of the given mesh, the interpolating surface is also similar to the limit surface of the given mesh. Therefore, construction of the interpolating surface can use information from the given mesh as well as its limit surface. This approach, called similarity based interpolation, gives us more control on the smoothness of the interpolating surface and, consequently, avoids the need of shape fairing in the construction of the interpolating surface. The computation of the interpolating surface’s control mesh follows a new approach, which does not require the resulting global linear system to be solvable. An approximate solution provided by any fast iterative linear system solver is sufficient. Nevertheless, interpolation of the given mesh is guaranteed. This is an important improvement over previous methods because with these features, the new method can handle meshes with large number of vertices efficiently. Although the new method is presented for CCSSs, the concept of similarity based interpolation can be used for other subdivision surfaces as well.     

正三角形容器内等圆Packing问题的启发式算法

等圆Packing问题研究如何将n个单位半径的圆形物体互不嵌入地置入一个边长尽量小的正三角形容器内,作为一类经典的NP难度问题,其有着重要的理论价值和广泛的应用背景.模拟退火算法是一种随机的全局寻优算法,通过将启发式格局更新策略与基于梯度法的局部搜索策略融入模拟退火算法,并与二分搜索相结合,提出一种求解正三角形容器内等圆Packing问题的启发式算法.该算法将启发式格局更新策略用来产生新格局和跳坑,用梯度法搜索新产生格局附近能量更低的格局,并用二分搜索得到正三角形容器的最小边长.对41个算例进行测试的实验结果表明,文中算法改进了其中38个实例的目前最优结果,是求解正三角形容器内等圆Packing问题的一种有效算法.     

An elegant algorithm of the analytical calculation for the volume of fused spheres with different radii

We propose a new algorithm for calculating the volume of fused spheres. The new algorithm is superior to the old methods in two aspects. One is the separation of the algorithm into topological and analytical parts. This makes the mathematical nature of the problem “what is the minimum topological information required to calculate the volume of fused spheres?” clear. The number of conditional branches is drastically reduced. The remaining conditional branches are those which are topologically essential. For practical use, only the list of the spheres forming isolated spheres, isolated sphere circles, exposed vertices, and buried vertices are required. The other aspect which makes the new algorithm superior to the old ones is the analytical expression which is independent of the choice of the coordinate frame. All equations are written only in terms of radii of spheres and distances between spheres. This enables us to calculate derivatives of the excluded volume with respect to a scaling parameter which is used in the scaled particle theory of liquids.     

基于顶点法向量约束的Catmull-Clark细分插值方法

提出一种基于顶点法向量约束实现插值的两步Catmull-Clark细分方法.第一步,通过改造型Catmull-Clark细分生成新网格.第二步,通过顶点法向量约束对新网格进行调整.两步细分分别运用渐进迭代方法和拉格朗日乘子法,使得极限曲面插值于初始控制顶点和法向量.实验结果证明了该方法可同时实现插值初始控制顶点和法向量,极限曲面具有较好的造型效果.     

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.     

Reconstruction of 2D polygonal curves and 3D triangular surfaces via clustering of Delaunay circles/spheres

A simple and efficient method is presented in this paper to reliably reconstruct 2D polygonal curves and 3D triangular surfaces from discrete points based on the respective clustering of Delaunay circles and spheres. A Delaunay circle is the circumcircle of a Delaunay triangle in the 2D space, and a Delaunay sphere is the circumsphere of a Delaunay tetrahedron in the 3D space. The basic concept of the presented method is that all the incident Delaunay circles/spheres of a point are supposed to be clustered into two groups along the original curve/surface with satisfactory point density. The required point density is considered equivalent to that of meeting the well-documented r-sampling condition. With the clustering of Delaunay circles/spheres at each point, an initial partial mesh can be generated. An extrapolation heuristic is then applied to reconstructing the remainder mesh, often around sharp corners. This leads to the unique benefit of the presented method that point density around sharp corners does not have to be infinite. Implementation results have shown that the presented method can correctly reconstruct 2D curves and 3D surfaces for known point cloud data sets employed in the literature.     

Mesh-based morphing method for rapid hull form generation

Morphing is an interpolation technique that changes one form into another through a seamless transition, producing, in the process, an infinite number of ‘intermediate’ forms between the original and the target. This paper examines the possibility of using the morphing technique for generating a large number of hull forms rapidly based on a number of target forms, existing or newly generated.The paper discusses the technique developed for applying morphing technique to hull form definition. The algorithm first projects the vertices of the original and target 3D surfaces onto 2D planes. After ‘regularising’ the vertices on 2D, they are projected back on the 3D surfaces. The corresponding vertices of the two surfaces are then used for interpolation. It has been found that the interpolated hull forms can be generated almost instantaneously, allowing the whole algorithm to be embedded in an optimisation program.     

Curve interpolation in recursively generated B-spline surfaces over arbitrary topology

Recursive subdivision is receiving a great deal of attention in the definition of B-spline surfaces over arbitrary topology. The technique has recently been extended to generate interpolating surfaces with given normal vectors at the interpolated vertices. This paper describes an algorithm to generate recursive subdivision surfaces that interpolate B-spline curves. The control polygon of each curve is defined by a path of vertices of the polyhedral network describing the surface. The method consists of applying a one-step subdivision of the initial network and modifying the topology in the neighborhood of the vertices generated from the control polygons. Subsequent subdivisions of the modified network generate sequences of polygons each of which converges to a curve interpolated by the limit surface. In the case of regular networks, the method can be reduced to a knot insertion process.     

Curves with rational chord-length parametrization

It has been recently proved that rational quadratic circles in standard Bézier form are parameterized by chord-length. If we consider that standard circles coincide with the isoparametric curves in a system of bipolar coordinates, this property comes as a straightforward consequence. General curves with chord-length parametrization are simply the analogue in bipolar coordinates of nonparametric curves. This interpretation furnishes a compact explicit expression for all planar curves with rational chord-length parametrization. In addition to straight lines and circles in standard form, they include remarkable curves, such as the equilateral hyperbola, Lemniscate of Bernoulli and Limaçon of Pascal. The extension to 3D rational curves is also tackled.     

Periodic Bézier curves

We construct closed trigonometric curves in a Bézier-like fashion. A closed control polygon defines the curves, and the control points exert a push-pull effect on the curve. The representation of circles and derived curves turns out to be surprisingly simple. Fourier and Bézier coefficients of a curve relate via Discrete Fourier Transform (DFT). As a consequence, DFT also applies to several operations, including parameter shift, successive differentiation and degree-elevation. This Bézier model is a particular instance of a general periodic scheme, where radial basis functions are generated as translates of a symmetric function. In addition to Bézier-like approximation, such a periodic scheme subsumes trigonometric Lagrange interpolation. The change of basis between Bézier and Lagrange proceeds via DFT too, which can be applied to sample the curve at regularly spaced parameter values. The Bézier curve defined by certain control points is a low-pass filtered version of the Lagrange curve interpolating the same set of points.     

2D and 3D shape retrieval using skeleton filling rate

As an increasing number of digital images are generated, a demand for an efficient and effective image retrieval mechanisms grows. In this work, we present a new skeleton-based algorithm for 2D and 3D shape retrieval. The algorithm starts by drawing circles (spheres for 3D) of increasing radius around skeletons. Since each skeleton corresponds to the center of a maximally inscribed circle (sphere), this process results in circles (spheres) that are partially inside the shape. Computing the ratio between pixels that lie within the shape and the total number of pixels allows us to distinguish shapes with similar skeletons. Experimental evaluation of the proposed approach including a comprehensive comparison with the previous techniques demonstrates both effectiveness and robustness of our algorithm for shape retrieval using several 2D and 3D datasets.     

Generating cutter swept envelopes in five-axis milling by two-parameter families of spheres

This paper presents an efficient parametric approach of determining the shape of the envelope surface by a generalized cutter that follows five-axis tool path during NC machining. In this approach the cutter is modeled as a canal surface. By considering the tool motions the cutter is decomposed into a set of characteristic and great circles which are generated by two-parameter families of spheres. The center of a sphere from these families is described by two parameters which represent the spine curve and the tool path, and the radius of the sphere is described by one parameter representing the spine curve. Considering the relationship between characteristic and great circles the grazing points on the tool surface are identified. Analytically it is proven for the NC cutter geometries that any point on the envelope surface is located at the intersection of the characteristic and great circles. Then based on the proofs a closed-form solution for computing the grazing points generated by a surface of revolution is presented. The presented methodology is reduced to a simpler parametric form when the NC cutters are described by pipe surfaces.     

细分曲面拟合的局部渐进插值方法

逼近型细分方法生成的细分曲面其品质要优于插值型细分方法生成的细分曲面.然而,逼近型细分方法生成的细分曲面不能插值于初始控制网格顶点.为使逼近型细分曲面具有插值能力,一般通过求解全局线性方程组,使其插值于网格顶点.当网格顶点较多时,求解线性方程组的计算量很大,因此,难以处理稠密网格.与此不同,在不直接求解线性方程组的情况下,渐进插值方法通过迭代调整控制网格顶点,最终达到插值的效果.渐进插值方法可以处理稠密的任意拓扑网格,生成插值于初始网格顶点的光滑细分曲面.并且经证明,逼近型细分曲面渐进插值具有局部性质,也就是迭代调整初始网格的若干控制顶点,且保持剩余顶点不变,最终生成的极限细分曲面仍插值于初始网格中被调整的那些顶点.这种局部渐进插值性质给形状控制带来了更多的灵活性,并且使得自适应拟合成为可能.实验结果验证了局部渐进插值的形状控制以及自适应拟合能力.     

平面轮廓的螺旋填充轨迹生成算法

在快速成型和数控领域中对平面轮廓区域的填充是比较繁琐复杂的步骤。为充分扬弃顶点偏置和线段偏置的优缺点,提出了顶点线段混合偏置算法,即在凹点处采用线段偏置,而在凸点处则采用顶点偏置或插入线段方式;为优化起落刀次数,提出用对角曲线连接偏置曲线形成螺旋轨迹的算法,即在归类相同的相邻两条偏置曲线中,以顶点较多的作为主偏置曲线,利用K-D树在相邻多边形查找主偏置曲线每个顶点的最近点,依次求出对角曲线的离散点并且连接获得螺旋轨迹。     

Envelopes and tubular splines

Envelopes of monoparametric families of spheres determine canal surfaces. In the particular case of a quadratic family of spheres the envelope is an algebraic surface of degree four that is composed of circles. We are interested in the construction of smooth tubular splines with pieces of envelopes of quadratic families of spheres. We present a scheme for the construction of a tubular spline that interpolates a sequence of circles in 3D. We control the shape near each circle by prescribing a sphere that contains it and is tangent to the spline. We offer further shape handles for local control through weights that are assigned to the controlling spheres.     

Merging polyhedral shapes with scattered features

1. initial embeddings of the polyhedra on unit spheres are computed, 2. the embeddings are deformed so that user-defined features (vertices) coincide on the spheres, and 3. an overlay of the subdivisions is computed and the aligned vertices are fused in the merged model.