【作者】 刘成明；

【导师】 罗钟铉；

【作者基本信息】 大连理工大学 ， 计算数学， 2007， 博士

【摘要】 随着计算机技术的普及和应用的日益广泛，细分方法在近年来已经成为计算机辅助设计(CAD)和计算机图形学(CG)领域内的一个国际研究热点。近三十年来已有多种细分方法被相继提出，然而大多数细分方法难以控制极限曲线曲面的形状与位置，不能满足带约束条件的几何形状设计与精密机械设计的要求。为此，本文讨论了带几何约束条件的细分曲线曲面设计问题，通过控制松弛参数的值使极限曲线满足给定的弧长要求；局部地修改细分规则使极限曲线曲面满足局部插值的要求。并基于细分曲面的逼近性质给出了一种快速有效的曲面参数化方法。本文首先回顾了细分造型方法的发展概况与历史，然后对细分领域内多方面的国际研究成果及其应用进行了评述。介绍了细分的连续性分析方面的理论成果，并对几种常见的细分方法，特别是本文工作中经常用到的四种四点逼近细分方法进行了描述。在实际的工业产品外形设计中，常常要求满足若干几何或物理的约束条件，例如飞机的进气管道需要满足面积的要求，飞机、船舶的表面有流体力学方面的要求，甚至还要考虑美学。在计算机动画中，为了真实自然地模拟物体变形，应尽可能地保持物体骨架的长度不变。本文第3章针对四种新近提出的四点逼近细分方法，抓住松弛参数对极限曲线的调节作用，讨论了带弧长约束的细分曲线设计问题。首先给出了弧长约束的细分曲线设计问题的解存在的一个充分条件。并将四种四点逼近细分方法推广到非静态的细分模式，给出了非静态四点逼近细分C~1光滑的充分条件。针对弧长约束的细分曲线设计问题，发现了退化与强退化的控制多边形，以及(强)退化控制多边形之间的递推关系。利用弧长约束的曲线细分方法，给出了一种生成精确圆周的算法，使得旋转面的离散设计变得更加简单。根据细分曲线曲面与控制网格的关系，细分方法可以分为两类：插值细分与逼近细分。对于插值细分方法，由于每一步细分都保留旧一层网格的顶点，对于有扰动的初始数据会产生不光顺的曲线曲面。因此几何造型中常常采用逼近型的细分方法。但是机械设计等工程中的曲线曲面设计通常有局部插值的要求，因此本文第4章在第三种四点逼近细分的基础上讨论了带局部插值约束条件的四点逼近细分方法(称为修改的四点逼近细分)。类似于NURBS曲线具有端点插值的性质，修改的四点逼近细分可以插值任何一个初始控制顶点。除了被插值点外，修改的四点逼近细分方法具有C~2光滑度，而在被插值点处可达C~1光滑。利用修改的四点逼近细分方法，提出了一种细分曲线或曲面的G~1拼接条件。能够处理任意拓扑类型的网格是细分方法的一大优点，本文将第三种四点逼近细分格式推广到了能够处理任意拓扑网格的曲面细分格式。这种新的细分格式在正规点处为C~2光滑，在奇异点处达到C~1光滑。而且还可以通过调节松弛参数来调整极限曲面的形状。特别地，当松弛参数取值为0时，新的曲面细分格式就是著名的Catmull-Clark细分格式。在新的逼近曲面细分格式的基础上，本文提出了能够超限插值于给定的C~1光滑参数曲线的细分方法。极限曲面在被插值曲线和奇异点上为C~1光滑，其它位置为C~2光滑。区别于已有的局部插值细分方法，该方法既可以在曲面边界上也可以在曲面内部插值于一条任意给定的C~1光滑的参数曲线。三角网格曲面参数化以其在纹理映射技术、散乱数据拟和、多尺度网格编辑等方面的重要应用而成为CAGD中研究的热点问题。本文中，我们利用细分曲面的逼近性质，给出了一种新的基于细分曲面逼近的三角网格曲面片的参数化方法。首先证明了第三种四点逼近细分方法可以逼近一C~2光滑的曲线到二阶精度，这与经典的三次B-样条细分，四点插值细分具有相同的逼近阶。然后给出了一个细分曲面片的逼近算法，极限曲面由Catmull-Clark细分格式、张量积形式的四点插值细分和修改的四点逼近细分方法产生。数值实验表明，修改的四点逼近细分方法生成的极限曲面在Hausdorff度量下可以更好地逼近三角网格曲面。对一个三角网格曲面片，首先计算出充分逼近它的细分曲面，然后对每一个三角网格点，在细分曲面上搜索Hausdorff度量下距离最近的点，用该点的自然参数作为三角网格顶点上的参数值。该方法可以看作是曲线累加弦长参数化的推广，其效果类似于经典的保形参数化。与经典的参数化方法不同的是，基于细分的参数化方法不需要求解线性方程组。当三角网格中顶点和三角形数量较大时，该方法显著地快于经典的参数化方法。图像匹配技术在计算机视觉及其工程应用中起着至关重要的基础作用。在一些实际工程应用中，除了精度，图像匹配的速度也是大家所关心的问题。我们给出了一个快速的匹配算法，在速度上有数量级的改进。数值实验结果表明，我们的算法可以用于实时计算。更多还原

【Abstract】 With the rapid development and wide application of computer science, subdivisionhas become a powerful tool in the fields of computer aided design (CAD) and computergraphics (CG). Many subdivision schemes have been proposed in the recent three decades,but most of them have the difficulty of controlling the shape of limit curves or surfaces, andcan not satisfy the requirements of fine design in mechanism. So, in this theis, we discussthe problems of subdivision curves and surfaces design with some geometric constraintsand surface parametrization. We propose an algorithm to design a subdivision curvesatisfying given arc length constraint by adjusting the tension parameter, and we proposea modified 4-point approximating subdivision rule with local interpolated constraint tointerpolate a point or a curve. And we also give a novel parametrization algorithm basedon the approximating property of the modified 4-point approximating subdivision.This thesis reviews the general situation and history of subdivision at first, andappraises some research results and applications of subdivision. At the same time, weintroduce the researches on continuity analysis of subdivision, and several kinds of subdi-vision schemes in common use, especially 4 kinds of newly proposed 4-point approximatingsubdivision schemes which are the bases of our research in this thesis.There are usually some geometric or physical constraints in practical product design.For example, the design of the air-path in an airplane is to construct a smooth surfacewith constrained area. In the surface design of airplane or automobile, the aerodynamics,even aesthetics should be considered. In computer animation, the length of frameworkof objects should be kept in true and natural deformation. In this thesis, we discuss thesubdivision curve design with arc length constraint by using of the four newly proposed 4-point approximation subdivision schemes by adjusting the tension parameter. A sufficientcondition for the feasibility of the arc length constrained subdivision curve design is given.After extending the 4-point approximating subdivision schemes to non-stationary ones,we give sufficient conditions for C~1 continuity of the 4-point approximating subdivisionschemes. For the arc length constrained curve design problem, we find a kind of specialcontrol polygon named (strong) degenerated control polygon and prove the relationship between the strong degenerated control polygon and the degenerated control polygon. Anew algorithm of generating accurate circle based on arc length constrained subdivisionis given which facilitates the design of surfaces of revolution.There are two kinds of subdivision schemes according to the relationship of subdivi-sion limit surfaces and their control meshes: interpolatory subdivision and approximatingsubdivision. While interpolatory subdivision usually does not generate faring curves orsurfaces due to disturbance of initial data. For some interpolation requirements, approx-imating subdivision schemes should be modified to satisfy local interpolated constraint.In this thesis, we propose a modified 4-point approximating subdivision method with lo-cal interpolated constraint, the modified limit curve could interpolate any of the initialcontrol vertices, it is C~2 continuous except at the interpolated vertex where it is C~1 con-tinuous. We give a G~1 smooth condition for two subdivision curves or surfaces meetingat a common vertex or curve based on the modified 4-point approximating subdivision.We also extend the 4-point approximating curve subdivision to surface case on arbitrarytopological meshes. This novel surface subdivision produces limit surface of C~2 continu-ous on regular meshes, and C~1 continuous limit surfaces on irregular meshes. The novelsubdivision will become the famous Catmull-Clark subdivision if the tension parameteris set to be 0. The surface subdivision is also modified to interpolate a given C~1 parametercurve. It can interpolate not only on the boundary but also in the interior of the controlmesh, and the curve to be interpolated could be an arbitrary C~1 parameter curve.Parametrization of triangular mesh has become a key topic in CAGD because it playsan important role in texture mapping, spline surface approximation, scattered data fitting,animation, multi-resolution analysis, etc. In this thesis, we propose a new parametrizationmethod based on the approximating property of the 4-point approximating subdivision.By proving that the approximating property is the same as cubic B-spline subdivision and4-point interpolatory subdivision that they can approximating a C~2 smooth function tothe second order, we propose a simple mesh approximating algorithm by using subdivisionschemes, and the parametrization algorithm is a linear search on the subdivision surface,the parameter of the nearest vertex on subdivision surface is the required parametervalue. This algorithm can be considered as an extension of the chordal parametrizationto surface case. Since there is no computation of linear system of equations in the novelparametrization method, it is shown through some numerical examples in this thesis thatthe algorithm is faster than some classical surface parametrization methods when thenumbers of vertices and triangles are large. The technology of image matching plays an important role in computer vision andits application in engineering. Not only the accuracy but also the computation speed isusually considered by many scholars. In the last of the thesis, a fast image matchingalgorithm is given, and it could be used for real-time computation.更多还原