【作者】 张冬梅；

【导师】 董光昌； 刘利刚；

【作者基本信息】 浙江大学 ， 应用数学， 2010， 博士

【摘要】 离散数据造型与处理是计算机辅助设计、计算机图形学和计算机动画中的重要研究课题之一.但是一方面由于现有的数据获取、数据传输以及数据存储技术本身都存在着一些问题,使得已有的离散曲线曲面形状往往会不可避免地存在着一些缺陷,另一方面随着实践中具体应用的不同,对曲线曲面形状的要求也会不同.所以形状优化就成为了当今离散数据造型与处理中的重要环节.本文就围绕着离散数据造型中曲线与曲面的形状优化问题与技术展开了研究,分别提出了几种不同的形状优化方法.首先,对于用平面离散曲线表示边界的二维形状,由于曲线上点的扰动或小的偏离都会在曲线上产生噪音,使得曲线看起来极不光顺.在对以前曲线去噪算法研究的基础上,我们分别提出了两种保特征的曲线光顺算法.一种算法是基于平面离散曲线的伸缩内在量表示与角度滤波的思想,由于曲线伸缩内在量中的有向转角既可以反应曲线局部的光滑程度,又可以反应曲线的全局走向与形状,对此角度进行双边滤波得到新的光滑伸缩内在量,基于新的伸缩内在量重构曲线就得到了原曲线的光滑形式.另一种算法是将曲线光顺看做是去除噪音与保持原曲线形状特征两个条件的相互妥协,基于加权最小二乘的思想提出一个关于光顺后曲线顶点的二次能量函数,最小化此能量函数得到光顺后的曲线.实验结果证明这两种算法都能在保持原曲线形状特征的条件下得到看起来比较光顺的曲线.其次,对于只用边界表示的二维形状,在形状编辑、形变等应用中,往往会出现局部自交或萎缩等不自然现象,所以给出形状的内部表示形式是非常有必要的.在分析已有的内部表示方法与生成算法的基础上,我们分别给出了单个平面形状的近似骨架抽取算法与两个或多个平面形状的同构三角化算法.针对平面形状骨架抽取中轮廓噪声严重影响骨架分支的问题,我们给出了一种保特征的近似骨架抽取算法.首先通过分水岭算法检测平面多边形的突起点,将其作为骨架分支的末端点引导骨架抽取,从而得到合理简洁的近似骨架.针对以往同构三角化算法的效率低与质量差的问题,我们提出一种高效高质量的同构三角化算法.首先在其中一个多边形内部及边界都加入一定数目的Steiner,点生成它的均匀三角化,然后根据此三角网格中顶点之间的邻接关系及相对几何位置关系来确定其他多边形的三角化结果,最后保持同构地优化三角化质量,从而得到同构三角化结果.该算法不仅适用于两个多边形,对多个多边形同样适用.我们还给出了它在平面形状混合中的应用,基于同构三角化结果及平面三角网格的伸缩内在量表示提出了一种保内部相似性的形状混合算法,该算法有效地解决了形状混合中的局部自交和萎缩等现象.最后,对于用三角网格表示的三维离散曲面,我们分别提出了一种保特征的加权最小二乘三角网格光顺算法与一种基于直推式学习的交互式三角网格分割算法.针对三角网格曲面光顺中的保特征问题,我们基于加权最小二乘的思想提出了一种光顺算法.首先根据三角网格光顺及保特征的要求,给出一个关于光顺后网格顶点或者法向的离散二次能量,通过求解对应的线性方程组来优化此能量,从而得到光顺后的网格曲面.我们将交互式网格曲面的分割看做是机器学习中的基于直推式学习的分类问题,并在直推式学习过程中用加权图Laplacian方法去逼近求解,大大降低了计算复杂度,使得直推式网格分割算法得以高效运行.更多还原

【Abstract】 Discrete data modeling and processing is an important research topic in computer aided design, computer graphics and computer animation. On the one hand, because existing technologies on data acquisition, data transmission and data storage have many limitations, the shape of curves and surfaces must be of many defects inevitably. On the other hand, the required shape quality of curves and surfaces often varies according to the different applications. Hence, shape optimization has been an inportant topic in discrete data modeling and processing. In this paper, we investigate the problem of 2D and 3D shape optimization and some associated algorithms in discrete data modeling.This paper presents three main contributions. Firstly, as for the planar shape represented by discrete curves. Two curve smoothing algorithms are presented based on previous works. The first one is based on the scaling invariant intrinsic variables of planar discrete curves and angle filtering. The orientation angles of scaling invariant intrinsic variables can reflect its degree of smoothing locally and its shape feature globally. The sequence of the original curve’s orientation angles is smoothed by a bilateral filtering, then the smoothed curve is reconstructed by the filtered scaling invariant variables. The second algorithm interpretates the curve smoothing as the compromise between the ramoval of noise and preservation of feature and introduce a quadratic energy related to the vertices of the smoothed curve based on the weighted least squares. The final smoothed curve is get by minimizing the quadratic energy. Experiments have shown that these two algorithms can not only remove noise but also preserve detail features.Secondly, we found that it is necessary to take both the boundary of shape and the interior of shape such as skeleton and triangulation into consideration in the context of shape editting and interpolation. Because small disturbance on the bounday of polygon often leads to some unnecessary branches in the extracted skeleton, a feature preserving approach for extracting approximated skeleton of planar polygon is proposed in order to solve this problem. Prong features guided as branch tips of skeleton are detected firstly by watershed algorithm, then an approximated joggling-free skeleton of the polygon is obtained. In order to overcome the inefficience and poor quality of existing algorithms on compatible triangulations, an approach for fast building high quality compatible triangulations between two planar polygons is presented. Specifically, an uniform triangulation for the first polygon is easily constructed by introducing some Steiner points on both the boundary and the interior, then its connectivity is transferred onto the second polygon, whose vertices’positions are determined by the relative geomtric measure in the first triangulation. Finally a joint optimization is emplyed to obatin high compatibility between these two triangulations. This approach is not only suitable for two polygons but also suitable for multiple polygons. An algorithm for planar shape blending is also introduced based on this compatible triangulations, this approach can preserve the similarity of the interiors of the polygons and can avoid local expansion and shrinkage.Finally, as for the 3D discrete surfaces represented by triangular mesh, a feature-preserving mesh smoothing algorithm based on the weighted least squares is proposed. A discrete quadratic energy related to the smoothed mesh vertices or normal is introduced, which considers not only the overall smoothness of the mesh but also the preservation of the fine features of the original model. Then a quadratic objective function based on this energy is minimized by solving a sparse linear system to get the smoothed mesh. The mesh segmentation is explicitly interpreted as the problem of transductive learning:Given a set of user-supplied labeled vertices as the training set, the algorithm needs to learn the label for the rest unlabeled vertices which are taken as the test set, and the weighted graph Laplacian method is employed to approximate the accurate solution in a transductive learning process, making the segmentation alogrithm much faster.更多还原