网格曲面上离散高斯曲率计算方法的比较与研究毕业论文.pdf 59页

'网格曲面上离散高斯曲率计算方法的比较与研究作者姓名:翟晓雅指导教师:杨云副教授单位名称:东北大学理学院专业名称:信息与计算科学东北大学2015年6月 ComparisonandResearchofDiscreteGaussCurvaturesEstimationMethodsonMeshSurfacebyZhaiXiaoyaSupervisor:AssociateProfessorYangYunNortheasternUniversityJune2015 毕业设计(论文)任务书毕业设计(论文)题目:网格曲面上离散高斯曲率计算方法的比较与研究设计(论文)的基本内容:1.利用QT做用户交互,OpenGL做图像显示库,OpenMesh做网格存储,在VS平台上实现估算高斯曲率的四种算法.2.利用3DsMax进行简单的开曲面构造,并且作为试验模型.3.分析四种算法的运行效率及误差.4.利用层次分析法建立评价估算方法的综合模型,筛选出最优估算算法.5.翻译一篇关于主成分分析法的外文文献.毕业设计(论文)专题部分:题目:设计或论文专题的基本内容:学生接受毕业设计(论文)题目日期第周指导教师签字:年月日-i- 东北大学毕业设计(论文)摘要网格曲面上离散高斯曲率计算方法的比较与研究摘要随着计算机辅助设计和制造技术产业的快速发展,离散形式的曲面在计算机图形学和计算机辅助几何设计领域变得日益重要.离散形式的曲面主要分为三类:网格曲面,细分曲面和点云曲面.本文通过分析网格曲面上高斯曲率的变化来衡量其弯曲程度和结构性质.本文在第2章中首先对经典微分几何中曲率的计算和重要的公式定理作了简单的回顾,包括:参数曲线曲面上曲率的计算,曲面的第一基本形式、第二基本形式,主方向与主曲率,高斯曲率的计算,欧拉定理.然后详细介绍了四种离散曲面上估算高斯曲率的方法(Moreton和Sequin的方法,Meyer的Voronoi方法,Dyn和Hormann的方法,Cohen-Steiner和Morvan的方法),主要介绍了估算算法的基本思想,主要思路和数据结构的设计.本文的第3章为核心部分,首先利用3DsMax建模软件进行测试曲面的构造,为了全面评价四种估算方法的准确性,将测试曲面分为三种类型:抛物型,双曲型和椭圆型,最后进行运行效率和误差分析.运行效率分为时间复杂度和空间复杂度,误差包括最大误差,平均误差和标准误差.利用层次分析法建立综合评价模型并对不同的影响因子设置不同的权重,影响因子的权重依次为:0.1875(时间复杂度),0.0625(空间复杂度),0.54795(最大误差),0.06075(平均误差),0.1413(标准误差)最终得到Voronoi方法效果最优.最后运用统计学的方法利用colormap显示高斯曲率的波动大小.关键词:三角网格,高斯曲率,估算方法,层次分析模型,colormap显示-ii- 东北大学毕业设计(论文)AbstractComparisonandResearchofDiscreteGaussCurvaturesEstimationMethodsonMeshSurfaceAbstractWiththerapiddevelopmentofcomputeraideddesignandmanufacturingtechnology,thediscreteformofcurvedsurfaceplaysmoreandmoreimportantroleinthefieldofcomputergraphicsandcomputeraidedgeometricdesign.Thediscreteformsurfaceismainlydividedintothreecategories:meshsurface,thesubdivisionsurfaceandthepointcloudsurface.Inthisarticle,wemeasurethebendingandstructuralpropertiesofthesurfacethroughanalyzingthechangeoftheGaussiancurvatureongridsurfaces.Inthisarticlewefirstlygoovercurvaturecalculationandimportantformulasindifferentialgeometrytheorem,including:curvaturecalculationonparametriccurvesurface,thefirstfundamentalformandthesecondfundamentalformofthesurface,themaindirectionandthemaincurvature,Gaussiancurvaturecalculation,Euler"stheorem.ThenthepaperintroducesthefourkindsofdiscretesurfaceestimationmethodofGaussiancurvature,mainlyintroducesthebasicidea,themaintrainofthoughtanddatastructure.Thethirdchapteristhecorepartofthisarticle,firstofall,creatingthetestsurfacebyusing3DsMaxmodelingsoftware.Thesurfaceisdividedintothreetypes:parabolicsurface,hyperbolicsurfaceandellipticsurface.Forfourkindsofestimationalgorithmusingparametricsurfacetoexperimentandtest,wecalculatetheefficiencyandanalyzetheerror.Efficiencyisdividedintotimecomplexityandspacecomplexity,errorincludingmaximumerror,errorofthemean,standarderror.Usingtheanalytichierarchyprocess(AHP)toestablishacomprehensiveevaluationmodelandgetdifferentweightsofdifferentfactors:0.1875(timecomplexity),0.0625(spacecomplexity),0.54795(maximumerror),0.06075(averageerror),0.1413(standarderror)eventuallywegetVoronoimethodastheoptimalresults.FinallyweusethemethodofstatisticalandcolormaptoshowthatthefluctuationmagnitudeofGaussiancurvature.Keywords:Triangularmesh,Gaussiancurvature,estimationmethods,AHP,colormap-iii- 东北大学毕业设计(论文)目录目录任务书.........................................................................................................................i摘要........................................................................................................................iiABSTRACT...........................................................................................................iii第1章绪论..........................................................................................................11.1研究背景..............................................................................................................11.1.1计算机辅助设计与制造技术发展现状..........................................................11.1.2三角网格的应用..............................................................................................11.1.3离散高斯曲率估算方法的国内外研究现状..................................................21.2研究意义.............................................................................................................31.3本文主要的研究内容......................................................................................4第2章离散高斯曲率的估算.....................................................................52.1预备知识.............................................................................................................52.2离散高斯曲率的估算算法............................................................................72.2.1Moreton和Sequin的方法...............................................................................72.2.2Meyer的Voronoi方法.....................................................................................82.2.3Dyn和Hormann的方法................................................................................102.2.4Cohen-Steiner和Morvan的方法...................................................................112.3本章小结...........................................................................................................12第3章网格曲面上离散高斯曲率估算方法的比较分析........133.1试验模型的选取.............................................................................................133.2估算方法的运行效率与误差分析............................................................153.2.1运行效率分析.................................................................................................153.2.2误差分析.........................................................................................................163.3应用层次分析模型评判估算方法............................................................213.4应用统计学的方法进行colormap的显示.............................................243.5本章小结...........................................................................................................28-1- 东北大学毕业设计(论文)目录第4章总结与展望........................................................................................29参考文献................................................................................................................30结束语......................................................................................................................32附录1外文翻译...............................................................................................33附录2外文翻译原文....................................................................................44-2- 东北大学毕业设计(论文)第1章绪论第1章绪论近几年三维几何场景的模拟和绘制已经被广泛地应用于日常生活当中,比如三维立体游戏、电影特技、虚拟城市以及医疗诊断等.针对三维模型的模拟,三角网格曲面的表示方法被大家广泛地采用,并成为计算机几何设计领域的新宠.通过选择适当的计算方法求得离散网格曲面上的高斯曲率,可以很好地衡量一个曲面的结构,甚至是一个三维模型的好坏.1.1研究背景1.1.1计算机辅助设计与制造技术发展现状随着计算机技术的不断发展,人们越来越渴望通过计算机模拟现实生活中的实体模型,并对相应的模型实体进行计算、处理和显示,计算机辅助设计与制造技术便应运而生.计算机辅助设计与制造技术(ComputerAidedDesign&ComputerAidedManufacture)简称CAD/CAM技术,是计算机应用领域的最重要的技术之一.计算机辅助设计与制造技术的主要目的是利用计算机绘制出具有真实感的图形,并利用计算机技术完成设计过程中的信息检索、分析、计算、综合、修改及文件编辑工作.计算机辅助几何设计(ComputerAidedGeometricDesign,缩写为CAGD)作为计算机辅助设计与制造技术的理论基础,其主要的研究的内容是在计算机图像系统的环境中曲面的表示和逼近.其所用的理论工具却涉及数学中的很多分支,如逼近论、微分几何、计算数学、代数几何和交换代数等等,同时还与计算机图形学有紧密的联系.随着CAGD理论和应用的不断发展,从飞机,船舶,汽车设计到工程器件模具设计,到生物医学图像处理等都能看到其广泛的应用.1.1.2三角网格的应用三维模型建模方法是计算机辅助设计与制造技术的重要基础,是生成三维场景和逼真动态效果的前提.在计算机图形学领域,一般的曲面都是离散的.通常利用三角网格去模拟真实物体模型.三角网格是多边形网格的一种,多边形网格又被称为“Mesh”,用于为各种不规则物体建立模型的一种数据结构.现实世界中的物体表面直观上看都是由曲面构成的;而在计算机世界中,由于只能用离散的结构去模拟现实中连续的事物.所以现实世界中的曲面实际上在计算机里是由无数个小的多边形面片组成的.“Mesh”既可以由三角形组成,也可以由其他平面形状如四边形,五边形等组成;由于平面多边形实际上也能再细分成三角形.所以,使用全由三角形组成的三角网格(TriangleMesh)来表-1- 东北大学毕业设计(论文)第1章绪论示物体表面也是具有一般性的.三角网格是表示三维几何的有效手段.三角形边与边的邻接关系表示了网格模型的拓扑结构;每条边的长度表示了网格的离散度量;相邻三角形面之间的二面角表示了网格在空间的嵌入方式.用三角网格表示离散的模型的有如下优点[1]:三角网格模型易于存储可以表示任意复杂的拓扑表面;通过点的位置很容易表示出曲面的几何信息与嵌入方式;对光滑曲面的逼近精度可控;三角网格的应用获得了工业界的支持,尤其是图形硬件加速的支持.下面的图片表示三角网格实体建模的例子.图1.1三角网格的实体建模数字几何算法实现的基础是网格的数据结构表示,目前已经有一些关于网格的数据结构的实现,主要有翼边(Winged-edge)结构,四叉边(Quad-edge)结构和半边(Half-edge)结构[2].比较流行的是半边数据结构.网格曲面的表示方法中不仅包含曲面的形状信息,还可以包含曲面的其他属性,比如顶点透明度和纹理信息等等.1.1.3离散高斯曲率估算方法的国内外研究现状针对离散高斯曲率的估算,许多学者发表了一系列的文章提出了离散曲面微分量的新方法.离散高斯曲率的估算方法达四种以上.如Moreton和Sequin[3]的方法,其基本思想是利用微分几何学中的欧拉定理,建立曲面法曲率与曲面主曲率及主方向的关系.最后利用最小二乘法进行离散高斯曲率的求解.Mayer[4]的思想是引入Laplace-Beltrami算子和曲面的平均曲率流形.然后对进行积分.利用微分几何中的Green公式,再对该公式进行离散化处理求解.Meyer等人[5]提出了一种灵活的估算曲面的重要几何性质的方法,包括网格顶点的法向量及任意三角网格顶点的曲率,此方法的基本思想是把光滑曲面看作是一族网格的极限或者线性逼近,把三角网格中每个点的度量性质看作是此空间网格在此点一个小领域的平均度量.Dyn和Hormann[6]利用一系列小柱面拼成的光-2- 东北大学毕业设计(论文)第1章绪论滑曲面来近似代替,所以直接由微分几何中的定理可得离散高斯曲率和离散平均曲率的算式.Cohen-Steiner和Morvan[7]对网格上每个顶点取周围的测地邻域,按某一算式求得矩阵,利用矩阵的特征值与特征向量计算平均曲率和高斯曲率.1.2研究意义虽然随着科技的快速发展,计算机辅助几何设计的不断完善,很多产业的3D产品的设计开发与曲面造型技术取得了长足的发展,解决了人工的费时以及精确度不稳定的问题,但是高斯曲率的精确计算仍面临着巨大的挑战.三角网格上任意点处得到精确的法向量和曲率十分困难,主要原因是离散三角网格曲面并不是用传统微分几何中熟知的参数方程和隐式方程来定义,而是由离散点云以及点与点之间的拓扑关系定义的,所以经典微分几何中一阶微分和二阶微分的计算不能简单地应用于离散三角网格曲面上.通过估计离散曲面上的一阶微分和二阶微分,可以在网格曲面的特征提取[8-12]、网格简化[13-16]、网格光顺[17-20]、网格变形[21-23]、模型分块[24-25]等领域有重要的价值.在这些应用中,通常需要首先估计离散曲面上某点的法向量和曲率,然后根据这些法向量或曲率定义一个范数,作为一个优化的标准,利用该标准再进行离散网格的进一步处理,通常称为非线性优化问题.同时,精确的曲率计算和法向量估计也是网格去噪的基础.良好的平均曲率估算和法向量估计是无扭曲曲面光顺技术的关键.在计算机图形学、图像分析处理和几何建模等研究领域中,如自由曲面、反求工程、图像识别、三维医疗图像重建以及人脸识别等,经常需要计算主曲率,平均曲率和高斯曲率等值,用于折痕、棱边、隆起、沟壑等关键特征的提取、噪声的过滤和曲面的修补等,因此,离散曲面曲率的估计是众多离散曲面应用的重要基础.本文工作就是筛选高效的离散高斯曲率的估算方法,以便高斯曲率的相对精确的计算.这对于离散曲面重建、简化、区域分割、可展曲面优化及动画设计等诸多方面的应用有着非常重要的价值.1.3本文主要的研究内容本文将通过比较和研究离散曲面(用三角网格模拟光滑曲面)上高斯曲率的估算算法,从中筛选出最优的估算算法来对三角面片上高斯曲率尽可能准确地估计.论文共分为4个章节,各章的内容安排如下:第1章主要介绍了网格曲面上离散高斯曲率的研究背景,并对其研究意义进行了全面的阐述.对论文的结构安排和所做工作进行了简要的说明.第2章首先针对经典微分几何中高斯曲率的计算作了简单的回顾.其次详细介绍了-3- 东北大学毕业设计(论文)第1章绪论当前四大离散高斯曲率的计算方法并说明了数据结构的设计.第3章首先利用3DsMax建模软件建立了规整和顶点扰动的三种类型的参数曲面分别为:椭圆型曲面,双曲型曲面和抛物型曲面.根据表达式计算出基准高斯曲率与四种方法计算出的高斯曲率作对比,分析四种估算高斯曲率方法的运行效率和误差,利用层次分析模型建立估算方法的综合评价模型.将高斯曲率的变化趋势利用colormap显示出来.第4章首先对论文中所做的工作进行了全面的总结,为下一步研究提出建议和对今后工作的展望.-4- 东北大学毕业设计(论文)第2章离散高斯曲率的估算第2章离散高斯曲率的估算高斯曲率的概念最早是由德国物理学家、数学家高斯(1777.04~1855.02)首先提出,现在已经成为曲面论中重要的内蕴几何量.曲面在已知点邻近的弯曲性可以由曲面离开它的切平面的快慢决定,但是曲面在不同方向的弯曲程度不同即在不同的方向曲面以不同的速度离开切平面.利用曲面上过该点的不同的曲线的曲率刻画曲面在已知点邻近的弯曲性.高斯曲率确定了曲面在一点的邻近结构,该点与附近点的高斯曲率的比较,可以反映该点附近的形状变化.2.1预备知识微分几何学是运用数学分析的理论研究曲线或曲面在它一点邻域的性质.经典微分几何主要研究曲线和曲面上每一点的局部微分特性,包括每一点处的法向,主法向,主曲率,Gauss曲率和平均曲率,刻画了曲面上每一点邻近的一阶微分和二阶微分性质,可以根据这些微分性质进行局部重建[26].(1)参数曲线曲面上曲率的计算在微分几何中,曲线曲面的曲率起着重要的作用,本质上描述了曲面在局部区域的一些性质.对于空间中的一条曲线rt,3rtxt,yt,ztR,r是曲线的弧长参数,弧长的二阶倒数的大小度量了曲线上邻近两点的切向量的夹角对弧长的变化率,反映了曲线的“弯曲程度”,称kt|rt|为曲线r在t点的曲率.(2)曲面的第一基本形式、第二基本形式对于给定曲面:rruv,,uv,R,r和r连续且rr0此曲面成为正则曲uvuv面,则:2222IdrdsEdu2FdudvGdv,22称为曲面的第一基本形式.其中Er,Frr,Gr称为第一基本量.uuvv设Puv,为上一点,在点P的法线上的单位失为n(n称为曲面的法失),其中的n和曲面的第二基本形式定义如下:rrrruvuvn,|rr|EGF2uv-5- 东北大学毕业设计(论文)第2章离散高斯曲率的估算222IIrndsLdu2MdudvNdv,称曲面的第二基本形式.其中Lnr,Mnr,Nnr称为第二基本量.uuuvvv(3)主方向与主曲率曲面上一点P的两个方向,如果他们既正交又共轭,则称曲面在P点的主方向.利用正交与共轭性进行公式推导,设这两个方向是（d）dudv:（,）u:v,则有drr0EduuFduvdvu()Gdvv0,drn0drn0LduuMduvdvu()Ndvv0.以上两个条件改写为:(EduFdvu)(FduGdvv)0,(LduMdvu)(MduNdvv)0.22记为:(EMFLdu)(ENGLdudv)(FNGMdv)0其判别式总是大于等于0,EFGEFG当满足时,判别式等于0.说明曲面上每一点处(除了的情形外)LMNLMN总有两个主方向.曲面上一点处主方向上的法曲率称为曲面在此点的主曲率.也就是,曲面上一点处沿曲率线方向的法曲率.利用罗德里格斯定理,沿主方向有:dnkdr,其中k为主曲NN率,即k与k上式为:ndundvkrdurdv().经整理得:12uvNuvLEkNduMFkNdv0,MFkNduNGkNdv0.即得主曲率的计算公式为:LEkMFkNN0,MFkNGkNN222即:EGFkLG2MFNEkLNM0.NN(4)高斯曲率的计算设k,k为曲面上一点的两个主曲率,则他们的乘积称为曲面在这一点的高斯曲率12通常用K表示.高斯曲率的几何意义即:球面上的面积/曲面局部面积的极限,可以看出高斯曲率确实反映了曲面局部的弯曲程度.即为:2LNMKkk.122EGF利用高斯曲率的正负性,可以很方便地研究曲面在一点邻近的结构,高斯曲率K>0为椭圆点,K<0为双曲点,K=0为平面或抛物点.并且高斯曲率是曲面的内蕴量,只与曲-6- 东北大学毕业设计(论文)第2章离散高斯曲率的估算面的第一基本型相关,与坐标轴的选取和参数化表示无关.(5)欧拉定理计算点p处任意方向的法曲率k,即著名的Euler公式:设T是点p处的单位切向量,nTT1,2是点p处切平面的标准正交基,有Tcos()T1sin()T2,则沿着切向量的法曲率k可以表示为:n22kkcos()ksin().12由Euler公式主曲率kk与法曲率k的关系,推导出著名的平均曲率和高斯曲率的12n定义,其中高斯曲率反映了曲面的局部弯曲程度.平均曲率和高斯曲率的具体公式如下所示:kk12Kkk.KH,G1222.2离散高斯曲率的估算算法本文选取四个有代表性地算法进行阐述,在论文的第3章中会进行详细地分析与研究.统一把曲面的高斯曲率记为k,平均曲率记为k,法曲率记为k,主曲率记为GHkk,,法向量记为np,其1-邻域内的顶点的集合记为m112.考虑三角网格的顶点i{}pij0,其1-邻域内的下标集合记为Ni（）,其顶点的度数记为|Ni（）|,包含的三角面片的集合记为m1,包含点的三角片的面积之和记为Ap（）[27].{}Tij0i2.2.1Moreton和Sequin的方法针对微分几何的欧拉定理,建立曲面法曲率与曲面主曲率及主方向的关系.求解形如Axb的线性方程组.其中A为每一个点和其邻域点构成的向量在切平面上单位投影的坐标分量的线性组合.b为三维模型中每一个点在其邻域点方向上的法曲率.rpjptij图2.1三角网格曲面在点p处沿向量pp的法曲率的估算iij具体的计算方法如下:取点p周围三角面片各法向量的平均值作为三角网格在点pii-7- 东北大学毕业设计(论文)第2章离散高斯曲率的估算处的法向量,记为n.过点p与n垂直的平面称为网格曲面在此点的切平面,设t为向ij量ppij在此网格曲面的切平面上的单位投影.作过点ppij且在点pi有切向tj的圆,则把曲面在点pi处沿ppij方向的法曲率kj近似地取为此圆半径的倒数.如上图2.1所示.可以利用角度的关系建立方程,从而求解半径.半径可以由下面的公式求出:1npp||pp||ji2jicos.||pp||rji曲面在点pi处沿ppij方向的法曲率kj的计算公式如下:2(pp)nkji.j(pp)(pp)jiji设bx,by为网格曲面上由n确定的切平面上的一组基,取tjx,,tjy,为向量关于bx,by基的坐标.取ij,1,2,m,m为p的度则经过推导A,b矩阵的定义如下:it2ttt2k1x1x1y1y122t2xtt2x2yt2yk2A,b.22tmxttmxmytmykm求解Axb方程得到解向量:22xekek0x1y2xx12eexyk1k2.xek2ek22x2y12x1高斯曲率kkk,则2xxkk,所以可以利用上述方程的解来求得高斯曲G1202122率的值:2x1K2xx.G022数据结构设计:针对当前点计算其邻域点存储在temp_point_数组里,求解其与邻域之间的向量记为vector_point_.利用vector_point_内的向量计算法向量,并对其求平均值定义为当前点的法向量.利用法曲率的计算公式进行计算,并作为线性方程组的右端项.确定切平面上一组基(为标准正交基),计算vector_point_中的向量在基上的分量坐标,并初始化系数矩阵进行线性方程组求解,得到当前点的高斯曲率.-8- 东北大学毕业设计(论文)第2章离散高斯曲率的估算2.2.2Meyer的Voronoi方法Meyer的Voronoi方法[5]提出了一种可以灵活估算曲面的重要几何性质的方法,其基本思想是将光滑曲面看作是一族网格的极限或者线性逼近,把三角网格中每个顶点的度量性质看作是此空间网格在此点的一个小邻域的平均度量.针对每一个点计算其混合面积,再由公式得到当前点的高斯曲率.利用经典微分几何中GaussBonnet定理:KdA2j,Amj其中表示边vv与vv的夹角,对积分进行离散,得到高斯曲率的离散形式,如下公jijij1式所示:1KG()pi(2j).AmjNi()求解混合面积A(())Av:对于锐角三角形,取三角形的外心连接每条边的中点,得m到新的面积记为A;对于钝角三角形,是把钝角对应边的重点和另两条边的中点相连,锐得到的面积记为A.对任意的三角网格,则是用以上两种方法求得整个的混合面积钝A(())Av.m图2.2计算混合面积Av（）和三角示意图"""三维空间中三角形外心坐标的推导公式:设外心坐标为Oxyz,,,当前点坐标vxyz0,0,0,其相邻1-邻域点的坐标为vjxyz1,1,1,vj1xyz2,2,2.利用两个约束条件(到三点的距离相等,三个向量共面),求得唯一外心坐标.222222222"""""""""xx0yy0zz0xx1yy1zz1xx2yy2zz2,"""xxyyzz000"""xxyyzz0.111"""xxyyzz222-9- 东北大学毕业设计(论文)第2章离散高斯曲率的估算利用上述条件整理可得:xxyyzzb1010101xxyyzzb2020202.xxyyzzb2121213ABCb4其中:1222222b1x1y1z1x0y0z0,21222222b2x2y2z2x0y0z0,21222222b3x2y2z2x1y1z1,2bxyz(yz)yxz(xz)zxy(xy),4012210211201221Ayz(z)yz(z)yz(z),120012201Bxz(z)xz(z)xz(z),021102210Cx(yy)xy(y)xy(y).012120201数据结构设计:利用相邻点与当前点之间的向量的内积的反余弦进行累计求和来计算当前点与邻域点之间的角度之和.在计算混合面积时,判断包含当前点在内的所有三角形的性质(锐角,钝角,直角)来进行求解.若为锐角利用推导出来的外心公式求解方程组得到混合面积,若为钝角直角利用对角边中点与其余两边中点连线所组成的三角形作为混合面积进行求解.2.2.3Dyn和Hormann的方法在三角网格中,定义两端为点的边pp,的边epp,两边ee,的夹角为ijjjijj1jeej,j1,两边ppij,ppij1的夹角为j,两边ppij,ppjj1的夹角为j,再记边ejej1eej,j1所围成的三角形pppijj1为Tj,其单位法向量为nj.定义两个相邻面||ee||jj1片T,T的法向量之间的夹角为n,n.对具有公共边e的两个三角形T,Tj1jjj1jjj1j作一个内切的小柱面,这样整个三角网格曲面就由一系列小柱面拼成的光滑曲面来近似代替,所以直接由微分几何中的定理可得离散高斯曲率的算式:2jjK.A-10- 东北大学毕业设计(论文)第2章离散高斯曲率的估算当T为锐角三角形时:j122S{||pp||cot||pp||cot}.(2-1)piij1jjj1j8当为钝角时:i12S||pp||tan,(2-2)pjjj1j812S||pp||tan.(2-3)pj18ijjSSSS.(2-4)pipppijj1pjpj1上式中,ASp,Sp如下图所示:iii图2.3S为三角形ppp中一小块面积piijj1数据结构设计:计算角度的方法与Voronoi方法一致,在计算混合面积时利用公式(2-1)-(2-4)进行计算.2.2.4Cohen-Steiner和Morvan的方法对网格上每个顶点p,取点p周围的一个测地邻域B,其取法为所有满足到点p的iii测地距离小于等于给定距离r的点.本文直接选取以点p为球心,半径为r的球内的所有iii的点,下面只考虑球内的点和边.图2.4点p周围的Borel集B(左)与边e有关的角度(右).i1TEpBeeBee,i|B|eB-11- 东北大学毕业设计(论文)第2章离散高斯曲率的估算定义如上的矩阵,其中|B|为B的面积,e为B中网格的边,e为e方向上的单位向量,eB为eB的长度,总是在0和e之间,e是以e为公共边的两个三角形法向的夹角.考察矩阵的特征值和特征方向.最小和最大特征值可分别作为主曲率的估计式.于是平均曲率和高斯曲率就可以直接由主曲率依照经典微分几何的理论来求得.kkkkk,12G12kH.2数据结构设计:关于Borel集的取法,首先是取包含点p的所有三角形,再取往外辐i射一周的所有三角形.针对p依照算法公式计算矩阵,利用QR分解15次迭代的结果确i定最小特征值和最大特征值最后进行高斯曲率的计算.2.3本章小结本章主要对经典微分几何中曲率的相关知识,曲面的第一基本形式与第二基本形式,高斯曲率相关的计算方法与重要公式进行了简单的回顾.之后,对离散曲面上高斯曲率的四种估算方法(分别为Moreton和Sequin的方法,Meyer的Voronoi方法,Dyn和Hormann的方法,Cohen-Steiner和Morvan的方法)做了综合概述.针对四种算法分析了数据结构的设计和关键的编程步骤,为第3章中对四种估算算法的比较分析做准备工作.-12- 东北大学毕业设计(论文)第3章网格曲面上离散高斯曲率估算方法的比较分析第3章网格曲面上离散高斯曲率估算方法的比较分析第2章详细介绍了四种高斯曲率计算方法的基本思想和数据结构设计.本章利用C++的网格编程实现四种高斯曲率估算方法,利用3DsMax进行测试曲面的构造(主要为开曲面).利用产生的曲面进行估算方法的测试从运行效率与计算误差两方面进行分析,记录分析数据,利用层次分析法建立高斯曲率估算方法的综合评价模型.利用统计学方法进行colormap显示,表示为一个模型的高斯曲率的波动变化.3.1试验模型的选取利用3DsMax进行简单的网格开曲面的构造(球面除外).将测试曲面划分为两类,规整曲面和扰动曲面.利用规整曲面测试四种估算方法的原始计算高斯曲率的精确度,利用扰动曲面测试四种估算方法对扰动顶点的抵抗能力,主要模拟当3D模型出现噪声时,四种估算方法是否依旧可以尽可能的精确计算整体模型的高斯曲率.为了客观评价高斯曲率的计算方法,选取微分几何中的三大类曲面即:抛物型,椭圆型,双曲型.因为高斯曲率的计算方法产生于不同的数学背景,对不同曲面上的点的敏感程度是不一样的,即:某种方法针对抛物型曲面的高斯曲率计算精确度较高,但是对双曲型曲面的高斯曲率计算精确度低,为了整体衡量某种方法的计算精确度,只有将所有的曲面情况都考虑到才能对该种方法的高斯曲率评价准确[27].(1)规整的连续参数曲面的构造利用3DsMax建模软件进行连续参数曲面的构造:利用已知的参数方程进行构造,由于3DsMax建模中包含基本几何体的构造,对球面,锥面,柱面的建模都是精确的.针对椭圆抛物面的构造,利用绘制抛物线绕z轴旋转得到最终的椭圆抛物面.由初始的抛物线的方程推导最终椭圆抛物面的方程.同样地,双曲抛物面的构造利用两个抛物线,将其中一条作为母线另一条作为准线进行马鞍面的构造,计算出马鞍面的方程和基准高斯曲率.通过C++网格编程计算每种估算方法的高斯曲率与基准高斯曲率的差,越小说明估算方法越有效.(2)扰动的连续参数曲面的构造微小波动的两种方法:切平面波动和法向波动.切平面波动即:三维模型的顶点在-13- 东北大学毕业设计(论文)第3章网格曲面上离散高斯曲率估算方法的比较分析切平面上进行随机微小的波动.法向波动即:三维模型的顶点在法向方向进行随机微小的波动.利用上述两种方法针对顶点进行随机扰动.使得扰动后的顶点在原顶点附近测试四种算法对随机扰动的抵抗力.由于随机扰动参数曲面的离散网格顶点后,这些顶点已经不在原始参数曲面上,因而三角网格模拟的连续曲面在其顶点处的理想值不等于扰动前参数曲面在此处的精确曲率.不过因为在3DsMax中对顶点扰动设置的参数比较微小,因此与基准高斯曲率的相差应该不大.下面的表格介绍了测试曲面的参数表达式和基准高斯曲率:表3.1测试曲面类型及基准高斯曲率类型曲面名称参数表达基准高斯曲率222球面xyz11椭圆型46422椭圆型抛物面zxy25625锥面相关参数:H=50,R=500抛物型柱面相关参数:H=80,R=20022双曲型双曲型抛物面zx10y-40ABC图3.1椭圆型曲面和双曲抛物面A图为球面B图为旋转抛物面C图为马鞍面ABC图3.2抛物型曲面A图为柱面B图为锥面(不加顶点)C图为锥面-14- 东北大学毕业设计(论文)第3章网格曲面上离散高斯曲率估算方法的比较分析图3.3球面微调结果示意图微调程度大(左)微调程度小(右)3.2估算方法的运行效率与误差分析针对规整球面的高斯曲率的计算利用稀疏与密集两个模型进行度量.利用3DsMax进行随机扰动针对球面,柱面,锥面划分为三类:稀疏,较密集,密集.顶点的个数分级为2000个,4000个,8000个.针对每一类都随机扰动5次,计算5次的平均值作为某算法对顶点的高斯曲率的估计值.从两方面对高斯曲率的估算方法进行分析:运行效率和误差.运行效率包括时间效率和空间效率.误差包括最大误差,平均误差和标准误差.高斯曲率估算方法名称简写说明:Moreton和Sequin的方法简称为Moreton;Meyer的Voronoi方法简称Voronoi方法;Dyn和Hormann方法简称为Hormann方法;Cohen-Steiner和Morvan方法简称为Morvan方法.3.2.1运行效率分析程序效率包括时间复杂度(运行程序所需要的时间)和空间复杂度(占内存的多少来衡量).完成某项工作,执行的步骤的次数最少、占用内存最小是程序员所追求的.(1)时间复杂度(时间单位:ms)表3.2时间效率分析曲面类型MoretonVoronoiHormannMorvan柱面2648985894锥面27111445985球面6502519183182椭圆型抛物面702332528马鞍面672322630平均运行时间264.41005.270.283.8从时间角度分析,Hormann方法的用时最短.四种方法的时间效率排序为:Hormann方法>Morvan方法>Moreton方法>Voronoi方法.-15- 东北大学毕业设计(论文)第3章网格曲面上离散高斯曲率估算方法的比较分析(2)空间复杂度空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度.一个算法在计算机存储器上所占用的存储空间,包括存储算法本身所占用的存储空间,算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面.在编程实现时四种估算方法继承了共同的父类,共享了父类的数据成员,又分别实现了父类中计算方法函数的多态,在实现过程中随模型的顶点数n的增多内存逐渐增大.四种估算方法的空间复杂度即为父类的空间复杂度.在该项四种方法几乎无差异.从空间复杂度的角度分析,四种估算算法的排序为:Moreton方法Voronoi方法Hormann方法Morvan方法.3.2.2误差分析从最大误差,平均误差,标准误差三个方面分析.最大误差衡量了数据最大的偏离程度,平均误差衡量了总体偏离的大小,标准误差衡量了整体数据距离基准高斯曲率的偏离程度.最大误差用符号A表示;平均误差用符号B表示;标准误差用符号C表示.首先进行规整参数曲面的误差分析,其次进行扰动参数曲面的误差分析.说明:在本节中所有估算方法的排序都是初步的,并按照稀疏曲面最大误差的值进行的排序(密集曲面的误差与稀疏曲面的最大误差排序差别不大).下一节会更加深入科学地介绍排序方法.(1)规整参数曲面的计算①规整球面误差计算当测试曲面为规整的球面时,得到如下表所示的误差统计:表3.3球面误差估计球面误差MoretonVoronoiHormannMorvanA1.008410.08937991.003211.24442稀疏B1.003850.02044920.2470990.960193C1.004230.02757140.3858881.03508A0.415490.002477830.1595080.954151密集B0.9995330.0007805390.01689930.941443C0.9996110.0009503490.02049190.941501从上述数据中可以看出球面的点由稀疏到密集四种高斯曲率的计算方法的三种误差估计都明显降低.利用Matlab作图得到下图所示的分布.其中稀疏的球面误差用虚线表示,密集的球面误差用实线表示.Moreton方法用红色表示,Voronoi方法用蓝色表示,Hormann方法用绿色表示,Morvan方法用黄色表示.-16- 东北大学毕业设计(论文)第3章网格曲面上离散高斯曲率估算方法的比较分析theerrorofball1.41.210.80.60.40.2011.21.41.61.822.22.42.62.83图3.4球面误差估计折线图通过上图可以看出Hormann方法对顶点的密集程度最敏感,Voronoi方法对球的顶点高斯曲率的估算无论是密集还是稀疏都是最精确的.Moreton方法两次计算都有相对较大的误差.针对规整球面的计算高斯曲率的误差排序:Voronoi方法>Hormann方法>Morvan方法>Moreton方法.②规整锥面误差计算当测试曲面为锥面时,得到如下表所示的误差统计:表3.4规整的不加顶点的锥面分析锥面误差MoretonVoronoiHormannMorvan顶点A968.5414144.118223.386020.73稀疏B19.53071.659583.289922.4853C134.89382.8822164.468120.415A2.79111419.5874791.65245.615密集B42.05190.367369-6.05711.64634C7056.128.05249274.657615.191表3.5规整加顶点的锥面分析锥面误差MoretonVoronoiHormannMorvan无顶点A0.07433030.003089190.003576620.0669103稀疏B0.00164070.000742350.00079850.0397816C0.0022480.0010490.001143640.0430769A4.531381.1943541.333510.331788密集B0.2031310.1086581.053410.10184C0.3136630.171465132.3580.129881在加顶点时,锥面误差明显增大,当面带有“尖”时,四种估算方法不适用.利用3DsMax将圆锥面的上半部分除去,即可发现误差明显降低.-17- 东北大学毕业设计(论文)第3章网格曲面上离散高斯曲率估算方法的比较分析针对锥面的高斯曲率估算精准度排序:Voronoi方法>Hormann方法>Morvan方法>Moreton方法.③规整柱面误差计算当测试曲面为规整柱面时,和基准柱面高斯曲率的误差大小如下表所示:表3.6规整柱面误差分析柱面误差MoretonVoronoiHormannMorvanA0.01026080.005079330.00429350.1222203稀疏B2.045e-0054.912e-0055.323e-0050.117284C0.00031680.00016610.0001530.119677A0.465870.09649410.1376240.233364密集B0.6489990.002080260.00225570.14429C0.868730.008766520.01088990.16687根据上图所示,针对柱面的高斯曲率估算精准度排序如下:Hormann方法>Voronoi方法>Moreton方法>Morvan方法.④规整椭圆抛物面误差计算当测试曲面为规整椭圆抛物面,和基准椭圆抛物面高斯曲率的误差如下表所示:表3.7规整椭圆抛物面误差分析椭圆抛物面误差MoretonVoronoiHormannMorvanA0.5736740.2834120.7589211.04627稀疏B0.3678110.1928310.3615320.453671C0.4523510.2149890.4726580.678561A0.4637860.1149820.6912751.255552密集B0.6286410.2298610.1789370.758271C0.5465510.1673670.2189740.647265根据上图所示,针对旋转抛物面的高斯曲率估算精准度排序:Voronoi方法>Moreton方法>Hormann方法>Morvan方法.⑤规整马鞍面误差计算当测试曲面为规整马鞍面时,和基准柱面高斯曲率的误差大小如下表所示:表3.7规整马鞍面误差分析双曲抛物面误差MoretonVoronoiHormannMorvanA2.798244.785925.7892110.5782稀疏B-43.7897-46.8971-45.2489-48.78428C4.738973.185902.149318.32891A2.158902.175893.174809.78932密集B-42.9878-44.7892-46.7891-47.7489C3.8997112.325896.678167.79781根据上表所示,针对双曲抛物面的高斯曲率估算精准度排序:Moreton方法>Voronoi方法>Hormann方法>Morvan方法.-18- 东北大学毕业设计(论文)第3章网格曲面上离散高斯曲率估算方法的比较分析根据上述表格的误差得规整测试曲面高斯曲率计算精确度,将其进行整理并进行各类曲面的排序如下表所示:表3.9规整测试曲面高斯曲率计算精确度排行曲面排序MoretonVoronoiHormannMorvan柱面3214抛物型锥面4123球面3124椭圆型椭圆抛物面2134双曲型马鞍面1234根据上图所示规整测试曲面的误差排行可得Voronoi方法直观上最优.(2)微小扰动参数曲面的计算下面将针对扰动曲面进行高斯曲率估算方法的误差分析,按照规整曲面的思路进行如下的数据收集:①球体扰动误差计算表3.10球体扰动高斯曲率的计算离散程度误差MoretonVoronoiHormannMorvanA3.599431.448411.011677.281982000顶点B1.002820.05590430.2399310.961358C1.027180.1416110.3747420.981879A45.53853.859031.0705515.3384000顶点B1.156910.1091590.2483810.960632C1.802940.3335430.3842321.01274A1119.8213.5171.299431.97458000顶点B4.825230.2696910.2649420.959594C34.86210.9124720.4042841.07661根据上表所示,针对球体的高斯曲率估算精准度排序:Hormann方法>Voronoi方法>Moreton方法>Morvan方法.②椎体扰动误差计算表3.11锥体扰动高斯曲率的计算离散程度误差MoretonVoronoiHormannMorvanA0.4052920.2008380.2182980.01121742000顶点B0.05676460.0282680.03062770.0049903C0.08048910.03999150.04336140.0057085A1.549830.7617250.7416990.0471944000顶点B0.2526930.1259890.1181510.0191756C0.3400510.1691950.1590980.0207163A3.672771.829421.442810.07708398000顶点B0.6323080.3152510.2505920.0371158C0.8170470.4067560.3243410.039069根据上表所示,针椎体的高斯曲率估算精准度排序:Morvan方法>Voronoi方法>Hormann方法>Moreton方法.-19- 东北大学毕业设计(论文)第3章网格曲面上离散高斯曲率估算方法的比较分析③柱体扰动误差计算表3.12柱体扰动高斯曲率的计算离散程度误差MoretonVoronoiHormannMorvanA0.1285710.06005730.02783940.00033542000顶点B0.01422440.00733880.00246704.778e-005C0.02128750.01074370.00505156.842e-005A0.5653140.2826680.1823430.00278914000顶点B0.0737320.03793030.01378120.0005372C0.1048490.05285710.02392480.0071423A2.881991.417320.9163470.03258648000顶点B0.3164190.1621480.09899640.0050275C0.4428970.2220220.1302590.0064310根据上表所示,针对柱体的高斯曲率估算精准度排序:Morvan方法>Hormann方法>Voronoi方法>Moreton方法.④椭圆抛物面扰动误差计算表3.13椭圆抛物面扰动高斯曲率的计算离散程度误差MoretonVoronoiHormannMorvanA0.6723980.3578920.7897811.247892000顶点B0.7878920.8721080.9167610.718378C0.2567110.3657670.2187410.671112A0.8787810.4789110.9237891.673264000顶点B0.8311370.5572610.6787810.868471C0.3748910.2289570.7893210.673891A0.5487910.3675610.9718291.787848000顶点B0.2817110.3238900.4676740.784711C0.7894710.7481110.1389110.487289根据上表所示,针对椭圆抛物面的高斯曲率估算精准度排序:Voronoi方法>Moreton方法>Hormann方法>Morvan方法.⑤马鞍面扰动误差计算表3.14马鞍面扰动高斯曲率的计算离散程度误差MoretonVoronoiHormannMorvanA1.578294.137876.167848.673182000顶点B-43.7897-45.6786-48.6786-52.1657C1.221293.147897.163765.17461A2.187115.164876.776789.178314000顶点B-42.9873-46.6878-48.4451-52.1651C2.287513.189476.187118.17381A1.278495.164879.6716310.16318000顶点B-42.1676-45.7878-46.6761-53.5615C2.617643.185785.563159.61378根据上表所示,针对马鞍面的高斯曲率估算精准度排序:Moreton方法>Voronoi方法>Hormann方法>Morvan方法.说明:上述(规整测试曲面与扰动测试曲面)的计算误差都是精确的,但是排序的方式按照最大误差进行排序.只是初步地给出一个直观的顺序,将会在下一节结合平均误差,标准误差和运行效率进行更为精确的排序.-20- 东北大学毕业设计(论文)第3章网格曲面上离散高斯曲率估算方法的比较分析扰动测试曲面高斯曲率计算精确度排行如下表所示:表3.15扰动测试曲面高斯曲率计算精确度排行排序曲面MoretonVoronoiHormannMorvan柱面4321抛物型锥面4231球面3214椭圆型椭圆抛物面2134双曲型马鞍面12343.2.3分析产生误差的原因(1)3DsMax绘制一般的曲面不是直接输入参数绘制曲面,而是用户手动绘制连续线.在计算真实高斯曲率时,按照精确的曲面方程进行计算会产生一定的误差.(2)针对曲面计算问题,对连续高斯曲率公式进行离散化处理,按照点计算高斯曲率,高斯曲率的精度会受点的密集程度的影响.(3)开曲面边界点的计算会产生误差.3.3应用层次分析模型评判估算方法层次分析法在决策工作中有广泛的应用.主要用于确定综合评价的权重数.在本文中运用层次分析法先分解后综合的系统思想:首先将所要分析的问题层次化,根据问题的性质和要达到的总目标,将问题分解成不同的组成因素,按照因素间的相互关系及隶属关系,按不同层次聚集组合,形成一个多层分析结构模型,最终归结为最低层(方案、措施、指标等)相对于最高层(总目标)相对重要程度的权值或相对优劣次序.本节将对上一节得到的数据进行加权最终确定算法的科学排序.权重设置为层次分析法的结果.通过对问题的分析,得到了评估计算离散高斯曲率算法的三个主要方面:运行效率,准确度.由这两个方面建立如下四个评价指标:指标1:时间复杂度C.1指标2:空间复杂度C.2指标2:最大误差C.3指标3:平均误差C.4指标4:标准误差C.5(1)构造层次模型目标层A:离散高斯曲率的评估.准则层B:运行效率和准确度.方案层C:时间复杂度,空间复杂度,最大误差,平均误差,标准误差.-21- 东北大学毕业设计(论文)第3章网格曲面上离散高斯曲率估算方法的比较分析算法评估运行效率准确度时间复杂度空间复杂度最大误差平均误差标准误差图3.5层次分析模型(2)构建成对比较阵①建立判断矩阵元素之间进行两两对比,对比采用相对尺度.根据聚类因子指标体系图,将同一层中各因素相对于上一层而言两两进行比较,对每一层中各因素相对重要性给出一定的判断,采用1-9的比率进行两两因素之间的相对比较.例如,认为bi,bj同样重要,则bbi:j1;认为bi比bj稍微重要,则bbi:j3.构造出某一层次因素相对于上一层次的某一因素的判断矩阵.按照以下的标准对bb:赋值:ijbbi:j1,认为“bi与bj重要程度相同”,bbi:j3,认为“bi与bj重要程度略大”,bbi:j5,认为“bi与bj重要程度大”,bbi:j7,认为“bi与bj重要程度大很多”,bbi:j9,认为“bi与bj重要程度绝对大”,当比值为2,4,6,8时认为介于前后中间状态.C表示运行时间,C表示最大误差,C表示平均误差,C表示标准误差,B表示12341运行效率,B表示准确度.2②建立成对比较阵a.根据准则层B得到成对比较阵为A:11A3.31(1)T由此得出准则层B对目标层A的权向量为:0.25,0.75.b.建立子方案层C对准则层B的成对比较阵.-22- 东北大学毕业设计(论文)第3章网格曲面上离散高斯曲率估算方法的比较分析1CCi:jaij,A(aij)nn,aij0,aji.aij17513B,B2111.1117331315(2)T对于成对比较阵B,权重向量为:0.75,0.25最大特征值为:2.一致性111n1检验指标为:CI0.1n1(2)T对于成对比较阵B,权重向量为:0.7306,0.0810,0.1884最大特征值为:22n3.0649.一致性检验指标为:22CI20.03245.n1查找响应的平均随机一致性指标RI,对n1,2,3,4,Saaty给出了RI的值,如下所示:表3.16一致性检验RI值n123456789RI000.580.901.121.241.321.411.45通过查询上表可计算出所有的一致性检验指标都通过一致性检验.(3)组合权向量方案层C对目标层A的组合权向量3121W,TT3123221,0,0,0,0,0,0,2.其中23132310.1875,0.0625,0.54795,0.06075,0.1413.TW,.于是下面进行组合一致检验:ppppp1CICI,CI,CI,(3-1)12nppppp1RIRI,RI,RI,(3-2)12nppCICR,p3,4,s.(3-3)pRIs*pCRCR.(3-4)p2*根据(3-1)-(3-4),计算可得CR=0.029组合一致性检验通过,通过前面的结论,设A为评价算法的指标,则A的计算公式如下:-23- 东北大学毕业设计(论文)第3章网格曲面上离散高斯曲率估算方法的比较分析A0.1875C0.0625C+0.54795C+0.06075C+0.1413C.(3-5)12345则利用上述公式可以评价出估算离散高斯曲率算法的排序如下:表3.17评价排序算法类型MoretonVoronoiHormannMorvan评价排序3124由上表可得Voronoi方法估算离散高斯曲率最优,其次分别为Hormann方法,Moreton方法,Morvan方法.3.4应用统计学的方法进行colormap的显示3.4.1colormap显示说明(1)显示方法一准确显示双曲点,椭圆点,抛物点.曲面的高斯曲率确定了曲面在一点邻近的结构,该点与附近点的高斯曲率的比较可以反映该点附近的形状变化.高斯曲率k的计算公G22[28]式中EGF总是正的,高斯曲率与LNM是同号.2k①k>0时,即LNM0,给定点P是椭圆点.这时主曲率1,k2同号,不妨设k0,k0,那么对应的主方向的一条法截线会朝法向量n的正侧弯曲.由欧拉公式12kkcosksin所有法截线的曲率k都是正的,所有法截线都朝向量的正侧弯曲,n12n所以曲面沿所有方向都朝同一侧弯曲.同样地,当k都是负的时候,所有的法截线都朝n负侧弯曲.曲面在点P的邻近在切平面的同一侧.2k②k<0时,即LNM0,给定点P为双曲点.这是主曲率1与k2异号,不妨设k0,k0,那么对应的主方向的一条法截线会朝法向量n的负侧弯曲,另一条法截12线朝法向量n的正侧弯曲.由欧拉公式kkcosksin得到各个方向的法曲率的变n12化情况.2k0③k=0时,即LNM0,给定点P为抛物点.因此1,k20,至少有一个主曲率等于0,不妨设k0,k0,那么对应于第一主方向的法截线朝n的正侧弯曲,另12一条法截线一般以P为拐点.因此一般第二条法截线从它的切线的一侧朝另一侧弯曲.曲面在点P的邻近的形状近似于抛物柱面.(2)显示方法二(尽量多的显示模型的渐变色)主要克服的问题:当高斯曲率波动比较大时,如何显示所有高斯曲率的渐变色.将所有顶点的高斯曲率记录下来,并画出一条折线图,当波动较大时利用统计学的方法,-24- 东北大学毕业设计(论文)第3章网格曲面上离散高斯曲率估算方法的比较分析使得所有的高斯曲率都尽可能平均地分布在最大与最小高斯曲率之间.应用统计学方法如下:①判断高斯曲率主要分布的区间,在该区间内的高斯曲率的点的个数占总个数的比例大于50%.②针对该区间进行横向拉伸变换(一维坐标变换).③将所有的高斯曲率显示出来.根据Matlab中colormap的显示方法,总共有13种类型显示方法,分别为PCT_JET、PCT_COOL、PCT_HOT、PCT_BONE、PCT_FLAG、PCT_ZEBRA、PCT_SPACE_JET、PCT_JET_ISOLINE、PCT_SPRING、PCT_SUMMER、PCT_AUTUMN、PCT_WINTER,PCT_ME.上述显示方法,只能改变颜色,而不能改变高斯曲率的整体分布.从13种类型中,选取符合视觉感知的PCT_JET方法作为高斯曲率颜色显示的方法.为了显示从抛物点到双曲点的渐变过程,以多个3D模型为例进行验证colormap的显示方法的好坏.3.4.2colormap显示结果(1)第一种显示方法(显示顶点的特性)图3.6锥面图3.7球面图3.8马鞍面说明:锥面上的点都为抛物点,高斯曲率几乎为0即处处可展;球面上的点为椭圆点>0;马鞍面上的点为双曲点<0.下图为仅仅显示顶点特性的模型：ABCD图3.9Bunny模型A图为Moreton方法B图为Voronoi方法C图为Hormann方法D图为Morvan方法从上图可以看出前三种方法对于Bunny模型的测试结果相近,Morvan方法误差较大.Bunny的耳朵内侧有少量抛物点,其余的多数为双曲点.-25- 东北大学毕业设计(论文)第3章网格曲面上离散高斯曲率估算方法的比较分析更多模型显示结果:ABCD图3.10horse模型A图为Moreton方法B图为Voronoi方法C图为Hormann方法D图为Morvan方法ABCD图3.11圆环面模型A图为Moreton方法B图为Voronoi方法C图为Hormann方法D图为Morvan方法BACD图3.12Eight模型A图为Moreton方法B图为Voronoi方法C图为Hormann方法D图为Morvan方法-26- 东北大学毕业设计(论文)第3章网格曲面上离散高斯曲率估算方法的比较分析圆环面的方程如下:r,{bacoscos,bacossin,sin}.a分析圆环面的顶点颜色分布情况:23①若LNM0,即cos0,则0及2为椭圆点.2223②若LNM0,即cos0,则为双曲点.2223③若LNM0,即cos0,则及为抛物点.22根据上图显示结果蓝色为双曲点,红色为椭圆点.显示正确.(2)第二种方法的显示结果(显示顶点的渐变色)ABCD图3.13圆环面模型A图为Moreton方法B图为Voronoi方法C图为Hormann方法D图为Morvan方法ABCD图3.14Eight模型A图为Moreton方法B图为Voronoi方法C图为Hormann方法D图为Morvan方法通过上图显示Morvan方法的3D模型高斯曲率的计算误差最大.-27- 东北大学毕业设计(论文)第3章网格曲面上离散高斯曲率估算方法的比较分析3.5本章小结本章首先通过3D建模软件建立简单参数曲面的规整模型和扰动模型,针对规整球面的高斯曲率的计算利用稀疏与密集两个模型进行度量.利用3DsMax进行随机扰动针对球面,柱面,锥面划分为三类:稀疏,较密集,密集.顶点的个数分级为2000个,4000个,8000个.针对每一类都随机扰动5次,计算5次的平均值作为某算法对顶点的高斯曲率的估计值.其次分析四种估算高斯曲率计算方法的运行效率和误差.利用层次分析法建立综合评价模型得出结论:Voronoi方法估算离散高斯曲率最优,其次分别为Hormann方法,Morvan方法,Moreton方法.最后,利用colormap两种显示方法显示高斯曲率的分布.-28- 东北大学毕业设计(论文)第4章总结与展望第4章总结与展望本章将对全文的内容进行总结,并指出未来研究工作的方向.随着经济的发展,科技的进步,计算机作为一门新兴的技术在人类文明前进的过程中发挥越来越重要的作用.同时图形工业对任意拓扑结构光滑曲面造型的需求日益迫切,越来越多的离散型曲面涌现.其中曲率的计算成为了描述曲面局部结构特征的一项重要工作.本文针对高斯曲率进行研究.本文对经典微分几何中曲率的相关知识,曲面的第一基本形式与第二基本形式,高斯曲率相关的计算方法与重要公式进行了简单的回顾.之后,对离散曲面上高斯曲率的四种估算方法(分别为Moreton和Sequin的方法,Meyer的Voronoi方法,Dyn和Hormann的方法,Cohen-Steiner和Morvan的方法)做了综合概述.在第3章中首先利用3DsMax建模软件建立了规整和顶点扰动的三种类型的参数曲面分别为:椭圆型曲面,双曲型曲面和抛物型曲面.根据表达式计算出基准高斯曲率与四种方法计算出的高斯曲率作对比,分析四种估算高斯曲率方法的运行效率和误差,利用层次分析模型建立估算方法的综合评价模型.将高斯曲率的变化趋势利用colormap显示出来.经过层次分析法建立的综合评价模型分别对不同的影响因素附加了一个权重,最终结果为Voronoi方法为最优的计算方法,主要因为对精确度的需求远大于对节省时间的需求,为了降低Voronoi方法的时间复杂度和空间复杂度,可以从减少执行次数和减少占用空间入手改进算法.离散曲面高斯曲率的计算有很多种,在不同场合,效率不同,各有所长,没有一个绝对的优势.这也为追求更好的估算方法带来的无限的动力.随着计算机科学技术的发展和计算机图形学领域技术的不断成熟,离散几何模型大量出现,基于离散型曲面的曲率计算与形状分析将日益繁荣.如何快速精确地对这些海量数据的离散曲面的曲率的估算将是科研工作者追求的目标.-29- 东北大学毕业设计(论文)参考文献参考文献1.熊芳.离散曲面高斯曲率估算算法研究[D]:[硕士学位论文].湖南:湖南工业大学,20102.罗良峰.离散三角网格上的法向量和曲率估计[D]:[硕士学位论文].大连:大连理工大学,20073.MoretonHP,SequinCH.Functionaloptimizationforfairsurfacedesign[A].ComputerGraphicsProceedings[C].Chicago,Illinois:1992.167-1764.MayerUF.Numericalsolutionsforthesurfacediffusionflowinthethreespacedimension[J].COMPUTATIONAL&APPLIEDMATHEMATICS,2001,20(3):361-3795.MeyerN,DesbrunM,SchroderPetal.Discretedifferential-geometryoperatorsfortriangulated2-manifolds[A].VisualizationandMathematics[C].Berlin,Germany:2003.35-576.DynN,HormannK,KimS-Jetal.Optimizing3Dtriangulationsusingdiscretecurvatureanalysis[A].InnovationsinAppliedMathematics[C].OSLO,NORWAY:2001.135-1467.Cohen-SteinerD,MorvanJ–M.Restricteddelaunaytriangulationsandnormalcycle[A].ProceedingsofthenineteenthconferenceonComputationalGeometry[C].SanDiego,California,USA:2003.312-3218.黄丽雯,庞柯,王鑫等.基于小波包分析的颅颌面纹理特征提取方法[J].西南师范大学学报(自然科学版),2003,38(11):59-639.胡鑫,习俊通,金烨.基于图像法的点集数据边界自动提取[J].上海交通大学学报,2002,36(8):1118-112010.胡鑫,习俊通,金烨.GeometricFeatureExtractionandModelReconstructionBasedonScattedData[J].JournalofDongHuaUniversity,2004,21(4):86-8911.王鹤,李晶.复合不变矩的特征提取[J].现代电子技术,2011,34(20):103-11012.GarlandM,HeckbertPS.Fastpolygonalapproximationofterrainsandheightfields[J].TechnicalReport,1995,13(3):26-2913.刘伟明,王安兵,申卫昌等.一种基于特征区域划分的网格简化方法[J].西北大学学报(自然科学版),2010,40(2):229-23314.ZhuJZ,ZienkiewiczOC,HintonEetal.Anewapproachtothedevelopmentofautomaticquadrilateralmeshgeneration[J].InternationalJournalforNumericalMethodsinEngineering,1991,32(4):811-847-30- 东北大学毕业设计(论文)参考文献15.谷冬冬,潘正运.渐进网格简化模型的改进算法[J].计算机工程与设计,2008,29(18):4648-465016.唐慧,罗立民,周正东.基于曲线曲率的网格简化方法[J].中国图象图形学报,2008,13(11):2224-223017.GuoFH,QunSP,ForrestAR.Robustmeshsmoothing[J].JournalofComputerScienceandTechnology,2004,19(4):521-52818.纪小刚,杨艳,薛杰.任意分辨率小波光顺的光顺精度分析[J].计算机应用,2014,34(05):1423-142619.神会存,李建华,周来水.基于法矢比率的样条曲线光顺[J].计算机工程与应用,2005,41(31):38-4020.FleishmanS,DroriI,Cohen-orD.BilateralMeshDenoising[J].ACMTransactionsonGraphics,2003,30(22):950-95321.XuWW,ZhouK.GradientDomainMeshDeformation-ASurvey[J].JournalofComputerScience&Technology,2009,24(1):6-1822.卢涤非,邹万红,叶修梓.基于局部相似变换的网格变形复制[J].计算机辅助设计与图形学学报,2007,19(5):595-59923.崔普明,刘秀平,王小超等.一种基于网格变形的图像放缩方法[J].计算机辅助设计与图形学学报,2013,25(6):788-79324.KhalifaI,MoussaM,KamelM.RangeimagesegmentationusinglocalapproximationofscanlineswithapplicationtoCADmodelacquisition[J].MachineVisionandApplications,2003,13(5):263-27425.JiangXY,BunkeH.Fastsegmentationofrangeimagesintoplanarregionsbyscanlinegrouping[J].MachineVisionandApplications,2012,14(11):25-2926.梅向明,黄敬之.微分几何[M].北京:高等教育出版社,2013,37-10927.方惠兰.网格曲面上离散曲率计算方法的比较与研究[D]:[硕士学位论文].浙江：浙江大学,200528.徐天长.关于曲面的高斯曲率的应用[J].安庆师范学院学报(自然科学版),2007,13(1):30-31-31- 东北大学毕业设计(论文)结束语结束语感谢我的毕设指导老师杨云副教授.在整个毕设工作中杨老师对学生认真负责,对科研求真务实,对工作一丝不苟的态度深深感染了我.在保证毕设论文质量的同时督促我时刻保持课题的进展.在杨老师的鼓励下我更加坚定我今后的科研方向,是杨老师给我打开了知识殿堂的大门,使我在四年的本科学习生活中受益匪浅.感谢中国科学技术大学的刘利刚教授,本课题是在刘老师的认真指导和严格监督下完成的.在课题研究过程中,刘老师给予了我很多关键性的指导,帮助我解决生活和研究工作中遇到的问题,我才得以顺利完成毕设课题.我的每一次进步、每一点成绩无不浸透着刘老师的心血.刘老师渊博的专业知识,严谨的治学态度,为人师表宽厚的品格都深深影响了我,这必将成为我受益终身的财富.感谢中国科学技术大学图形与几何计算实验室的同学:杨阳,栾晓佳等14人,给予我学习和生活上的帮助.虽然只有短短的两个月时间,从他们身上我获益良多.他们学习上刻苦努力,生活上乐于助人,对自己严格要求,不断追求上进的精神将激励我以积极乐观的态度不断向困难挑战.感谢我的挚友张雅倩、郭晓洁、刘利敏、王风格等四年来的同窗共勉,陪我度过了许多难忘的时光.由衷地感谢在百忙之中阅读评审本文的各位专家学者.最后感激我的家人,是他们在背后默默无闻地资助和鼓励,才使得我能够顺利完成学业.父母的言传身教和无私付出将会影响我的一生.谨以此文献给所有曾经给过我支持、关心和帮助的老师、同学和朋友！-32- 东北大学毕业设计(论文)附录1外文翻译附录1外文翻译利用离散曲率优化三维模型的三角剖分NiraDyn,KaiHormann,Sun-JeongKim,DavidLevin摘要通过给定一系列三维模型顶点建立优良的三维模型的三角剖分工具成为正在快速地发展的研究课题.所构造的三角测量是“最佳”的,即为在某种程度上在生成的三角网格中利用某一离散曲率局部最小化成本函数来衡量.该算法获得最优的三角剖分是交换边缘顺序,这样每个交换函数是最大限度地降低了成本.本文利用定义三角网格模型中的离散曲率容易计算出成本函数的三种算法,将不同的成本函数的结果进行了比较,对简单的三维模型进行操作数采样,我们比较最终优化后的三角网格和样本模型在不同范数下的近似误差.结论是三个成本函数导致了相似的结果,并没有哪一种算法可以说是优于另外一种.当被认为初始网格用于碟式细分时,由我们的算法所生成的三角网格与通过给定一系列顶点的任意初始三角剖分更明显地限制于蝶式曲面.基于这一观点,我们认为如果建立良好的离散曲率的三角网格,则在三角网格上的任何操作例如网格细分,偏微分方程的有限元解法或者是网格简化中都可以得到更好的结论.因此我们的算法应用于造型表面的抽样数据的提取以及其他基于三角网算法的初始化.§1.引言三角网格普遍用于描述三维曲面.给出一系列光滑曲面上的顶点样本,带有顶点的三角网格为样本曲面的近似代表.这样的表示依赖于顶点之间的连接选择.在这篇文章中,假定样本曲面是光滑的.我们致力于选择固定顶点的三角剖分较好的算法.我们的观点是给出一系列离散的顶点在某种程度上代表绝大多数的突出特色(增长速度,曲率等等)可以从数据中提取,并且具有代表性的三角网格不应该增加不在原始数据显示特点的顶点.这导致我们选择相对于成本函数最优的三角测量,且成本函数衡量不同的离散曲率.从一个任意初始给定顶点的三角网格模型中,我们目前的主要算法以最大的方式互换边缘从而在每个步骤中最大限度地降低成本函数,并且终止在局部最低的成本函数.这种-33- 东北大学毕业设计(论文)附录1外文翻译算法也被用于优化二维三角剖分(近似的二元函数),例如依赖派生数据三角剖分[3,6,8,9].Alboul和vanDamme考虑在三角网格中离散度量L1范数高斯曲率的成本函数,在这一系列的论文中[1,2,11].尽管该成本函数需要大量的计算,但是其拥有非常重要的性质.在参考文献[2]中证明,凸表面的数据采样(凸数据),交换成本函数导致唯一的全局最低值对应于唯一的凸三角.我们介绍两个成本函数,凸三角似乎也是全局最低,而他们的计算更简单.这个观察的理论研究已经超出了本文的范围,我们把它设定为未来的工作.不幸的是,交换边缘与最大额交换算法并不总是导致凸三角因为成本函数可能有局部最小值.我们做了许多成本函数的数值实验得出结论,一组固定的三角网格顶点和增强特性线(“锋利边缘”)可以显著改善的视觉外观.对于复杂的模型,我们利用不同的成本函数都有非常相似的结果.对于简单的模型,我们与我们的成本函数也测试生成近似三角形网格的质量交换算法,发现他们减少近似误差显著(在第4部分见环的例子).我们也意识到,我们的算法可以作为其他三维三角网格算法的预处理操作(如细分、有限元、简化等).该算法通过提供一个更好的起点,导致更好的性能.论文的大纲如下:第2节提出了一种计算几个离散曲率的措施.在第3节中,我们讨论了交换算法和各种成本函数.第4节包括比较实验优化三维三角剖分的方法与原始剖分的不同之处.附录与显式公式计算所需的成本函数是本文的最后一部分.§2.离散曲率的计算从理论的角度三角网格没有曲率,因为所有面都是平的,曲率沿着边缘和顶点的定义是不准确的,因为曲面不是C2连续的.但想到一个三角网格作为未知光滑表面的分段线性近似,未知曲面的曲率估算可以仅仅利用三角网格本身给出的信息.我们格外感兴趣的地方是计算三角网格每个顶点的高斯曲率K和绝对平均曲率|H|.因为我们把成本函数以最小化在网格优化过程中这些值为基础.但是我们在解释如何从所给数据中定义K和|H|之前先固定符号.3符号定义说明:一个三角网格M中包含一系列顶点Vv并且与一系列边iiEejvj1,vj2和一系列三角形Ttkvk1,vk2,vk3.使得vV成为三角网格Mjk的顶点并且使vv,,v成为顶点v的有序的相邻顶点(见图1).我们定义边为evv12nii-34- 东北大学毕业设计(论文)附录1外文翻译和两个连续的边的角度ieei,i1.相邻的边ei和ei1构成的三角形定义为eeii1tivvv,,ii1.相应面的法向量定义为ni.一条边ei所夹的二面角是相邻||ee||ii1三角形的法向量之间的夹角,n,n.说明的是在这些定义中我们将所有的序号ii1i变为0和n配对,序号n+1和1配对.图1顶点v和和局部结构的相关变量(左)在三角边e和沿t和t的弯曲柱体(右)ii1i现在我们定义关于面积SS整体的高斯曲率KK和整体的绝对平均曲率vv|H||H|利用vnn1KK2i和|H||H||||||eii|.(1)Si1S4i1这些公式也被其他作者[1,2,4,11]所用并且可以按照以下的方法进行理解.假设我们用一个半径为r的小的圆柱体替换每一个边便会与相邻面的切线相连(见图1)并且光滑圆柱在每个顶点处按照C2方式弯曲.现在三角网格被近似看做光滑曲面,K和|H|都是在曲面上可以积分的函数,我们应用微分几何中著名的定理[5].一个直接计算方法[1,11]最终的结果见公式(1),该公式并不依赖参数r也不依赖在每一个顶点的特殊弯曲方法.从这些可积变量中追溯每个顶点v的曲率的计算,我们假设曲率是一致分布在一个顶点的周围并且是一个简单规范化的区域.K|H|K,|H|.SS当然这些不同方式定义对于一个顶点v的混合区域S,最终导致不同的曲率值.我v们限制周边地区所有顶点的方法总结三角网格M的面积,vVSvM,因此我们写出M上的积分,相当于关于每一个独立的区域片的总和.例如:KvVVK.这个MSv-35- 东北大学毕业设计(论文)附录1外文翻译B面积最常用的计算方式是中心区域S,其为邻接顶点v的三角形面积的三分之一,可以通过连接构造边缘中点与相邻的三角形的重心(见图2).然而受文献[12]的启发,我们决VV定用VoronoiS面积替换,其中S代表了顶点v的局部Voronoi面积,根据三角网格中距离顶点的欧几里得距离(见图2).显式公式计算泰森多边形区域在附录中给出(见第5部分).图2重心区域(左)和Voronoi面积(右)除了高斯曲率和绝对平均曲率,我们也对绝对主曲率|k|,|k|感兴趣.从Kkk121212和H(kk)关系中,我们可以得到kHHK.而且,我们可以得到绝对主121,22曲率的和并且不需要知道H,仅仅知道|H|即可:2|H|，K0,|k||k|1222|H|K,其他.22说明:|k||k|总是实数,即使|H|HK.根据复杂曲率值计算原则,这个显12然不会发生在光滑曲面上,然而我们会在类似的顶点上处理离散曲率.§3.网格优化在过去的几年里,网格平滑的问题受到了很多关注.这些方法的需求在工业中应用,其噪声来自于测量误差,且该误差是可以从测量数据中移除的,为了丰富应用,所需求的三维三角网格模型带有满意的视觉信息.最普通的网格平滑方法是移动网格模型中顶点的位置例如使一个确定的能量函数达到最小[4,7,10].然而,这些方法不能应用于原始点的位置移动,例如,数值模拟或者表面插值.唯一的参数是剩下的三角测量数据的改变.于此同时,二维三角测量的优化在九十年代早期被粗略的学习[3,6,8,9],对于三维数据模型的学习知道得少之又少[1,2,11].平面能量经常被用于网格以及连续曲面的光顺的能量泛函:-36- 东北大学毕业设计(论文)附录1外文翻译2FTP4aH21abK,带有确定参数ab,.然而,对于封闭的曲面或者曲面带有固定的边界可以被简化为2F4aH,因为Gauss-Bonnet阐述了K在这些情况中是连通的.值得说明的是,这TP也适用于离散高斯曲率的积分:nvKK2v#V2#T2M,iMvSvi1v在该公式中,M是M的欧拉特征.因为我们不会交换网格的边界,在我们的设置中我们可以假定高斯曲率为常数积分.1/2F2最小化TP等价于在L2范数下最小化H,||H||2H.同样地,最小化绝对积分平均曲率与L1范数下的H相关||H|||H|.除了两个能量函数,我们也利用了L1规范1下的曲率原则.||||k1|k1||k2|作为一个优化标准.最小化||||k2等价于最小化||H||2,222因为kk4H2K.利用(1),这三个能量泛函:122122F1||H||2|H||Hv|,MvVSvF2||H||1|H||Hv|,MvV2|H|K0,vvF3||||k1|k1||k2|2MvV2|H|SK,其他.vvv选择三种能量函数中的一个作为成本函数F并且从最初的三角网格M开始,我们采用局部变换算法,在每一步骤中离散成本函数.该算法最重要的因素是确定对每一条边e的变换值s和合适队列P的应用.交换价值的区别是交换前后的成本函数的值对应的jj边缘和减少,表明这个优势交换引起的成本函数减少.注意交换操作没有定义边界边缘,应该禁止连接到一个度数为3的顶点,因为它会导致两个相同的边缘和两个三角形粘在一起(见图3).我们避免利用设置其交换值为交换这些边.这个适合的队列P是一个一整组数的排列{1,,#},E例如:ss对于所有的1ij#E.使用这样一个优PiPj先级队列的主要优势是在构建和更新时的低复杂性.此外,P(1)总是最大的边缘的索引交换值和测试s0说明成本函数是否可以进一步降低交换边缘.优势交换实际上被P()1执行时,交换价值的边缘2-邻接边缘的变化(见图3)和优先级队列必须更新.定义一系列-37- 东北大学毕业设计(论文)附录1外文翻译指标I{1,,#}E的1-邻域NI():NI(){:jiIt,Te:和e是t的边}.ij2一条边的2-邻域指数集被如下方式给出:N{}iNN{}.i在这些定义下,局部变换算法可以阐述如下:swap_value(j)ifeisswappablejreturn(FF)beforeafterelsereturn()initializationforj=1,…,#Edosj:=swap_value(j)set_up(P)optimizationwhiles0doP1swapeP12forjN{P1}dosj:=swap_value(j)update(P)所有给定数据可能的三角剖分的数量是有限的和成本函数是交换下降的,该算法保证终止在一个有限步骤之内.不理想的是,他通常不可能确定该算法达到全局最低.对于L1范数的高斯曲率||K||,Alboul和vanDamme展示了凸三角的数据优化策略总是1收敛的,达到全局最低[2].我们还测试了三个成本函数在凸数据和观察到的三角在F2和F3达到全局最优.证明这个属性的准确性是未来的研究课题.然而,三个成本函数可能局部最小值的交换算法可能会有失误,当且仅当,它终止在一个包含凹边缘的三角数据.我们轻微修改局部交换算法并进行测试,保证找到相同或更好的局部最小值.这种超前策略在不同的方法内决定了交换值s[13].无论何时,s0,它测试了是否交换四jj个边缘ekk,N{}j在1-邻域可以减低成本函数,合并后的交换值sjk,sjsk对于某些k是积极的.如果类似双交换值可以被发现,最大的s被用作排序优先级队列的标准替jk,-38- 东北大学毕业设计(论文)附录1外文翻译代sj和当ej达到队首,边ej和ek被交换.图3交换边(左)它的交换值得计算只涉及顶点的离散曲率.当边交换之后,被交换边的交换值,边为1-邻接边(标准线)和边为2-邻接边(衰减线)都要更新.与同一价为3的顶点连接的交换边是不适用的(右).§4.优化举例我们利用各种各样在不同数据里的成本函数检测我们的优化方法,范围从一系列小的简单物体样本(例如:球体,柱体,环)到有几千顶点的复杂的模型.第一类我们所观察的数据包含一系列凸顶点,因为有很多原因(保形或者压缩[11])在所有三角形中判断凸顶点的三角测量是便捷的方法.在几乎所有情况下测试,不管最初的三角形的形状(钝角,锐角,直角)最小化的三个成本函数都导致凸三角形(见图4).图4一系列拥有7个顶点的凸数据和10个三角形151说明:7个顶点的数据分别为v12,0,0,v10,2,,v0,,,1231022151v410,2,,v512,0,0,v60,,,v70,0,10,有10个三角形分别为522vvv1,2,3,vvv3,4,5,vvv1,3,6,vvv3,5,6,vvv7,2,1,vvv7,4,3,vvv7,5,4,vvv7,6,5,vvv7,,16,从非凸三角形对应于一个局部最小值的任何成本函数F1,F2,F3-39- 东北大学毕业设计(论文)附录1外文翻译该数据显示在最低端的凸三角形.而且我们有测试生成的近似三角形网格的质量交换算法与我们三个成本函数为简单对象图5中的环.初始三角网由m=12,n=6数据点:cosiRrcosijPijsiniRrcosij,i0,,m1,j0,,n1rsinijj2,i为偶数in2,iijmj0.52，其他n样本来自于参数为R=5,r=2,有2mn个三角形的环面:PP,,P,iji1,jij,1Pij,1,Pi1,j,Pi1,j1,i0,,m1,j0,,n1.图5从环面优化三角网格样本(左上)利用不同的成本函数:F1(右上),F2(左下),F3(右下).-40- 东北大学毕业设计(论文)附录1外文翻译图6初始状态(左)和通过蝶式细分步骤优化网格(右)图5显示了运用不同成本函数优化过程的三角网格的结果,环面的近似误差被列举在表1中.利用测试许多中参数环面(m,n,r,R),我们观测到成本最小化降低了结果的近似误差显著但没有可以说是优于其他的方法.表1优化网格的最初近似误差L1L2L3初始0.2342735460.28241220920.7939588898F10.15812262380.18870441190.4019238949F20.16403621020.19319714350.4019238949F30.16609481380.19459304320.3892151477我们的优化过程的一个重要方面是,它可以用来作为其他算法在三角形网格上的预处理操作.作为例子,图6显示了应用蝶式细分步骤(通过极小化F1函数)后的优化网格与初始网格进行的对比.图7Mr.Spock的头部:初始状态(左)和网格模型优化(右)-41- 东北大学毕业设计(论文)附录1外文翻译图8工艺数据集:初始状态(左)和优化网格(右)图9油罐盖数据集:初始状态(左)和优化网格(右).图10泰森多边形法限制在于一个非凸三角形(左)和一个钝角三角形(右)我们也可以利用更多复杂的数据集测试本文的算法,例如在图7中Spock的头部有16386个顶点,在图8中工艺数据集有4100个顶点,在图9中油罐盖数据集有3374个顶点.所有数据显示,初始三角网格和获得的最小化F2的优化网格运用两个成本函数最小化的结果非常相似.在图8和图9中注意如何增强特征线优化网格看起来更为平滑.-42- 东北大学毕业设计(论文)附录1外文翻译作为结论,我们想要再次强调,在我们的调查范围内由于凸数据中所有三个成本函数表现非常相似,很难说哪一个最好的.但绝对平均曲率的计算是最简单的,不涉及计算顶点周围的区域,由于F2在凸数据情况下最优三角也是凸的,因此我们使用F2.§5.附录确定局部Voronoi区域的面积严格限制在三角形中,我们必须区分钝角三角形和非钝角三角形(见图10).后一种情况给出如下公式:V122SAbcotccot,8VV并且类似地对于S和S.对于钝角三角形:BCV12V12VVVSBctan,SCbtan,SASSBSC88致谢:本文工作受到欧洲联合研究项目“在几何模型中多分辨率的研究(MINGLE)”(编号为HPRN-CT-1999-00117)和德国研究委员会在特别领域603“模型分析和视觉复杂度”的支持并且获得以色列优秀项目中心的科研基金的支持.参考文献-43- 东北大学毕业设计(论文)附录2外文翻译原文附录2外文翻译原文-44-'