基于三维TIN的精细表面建模方法(1.武汉大学测绘遥感信息工程国家重点实验室，湖北武汉430079;2.浙江大学CADCG国家重点实验室，浙江杭州310027)摘要：对现有三维不规则三角网（3DTIN）生成算法作了简要分类，回顾和评价了各类典型方法的优缺点和适用性，然后在此基础上提出了一种融合雕刻算法和生长算法优势的合成算法，给出了相应的数据结构。算法基于表面三角形任意一边的邻域结构，采用加权最小长度准则实现表面的快速生长。应用实例表明，算法可以重构具有任意拓扑的复杂表面，并且重构的三角网格表面与被采样的物体表面拓扑差别最小。关键词：三维TIN;表面重构;3DDelaunay;三维可视化??中图法分类号：TP391文献标识码：A：10013695(2006)08015903??HighlyRefinedSurfaceReconstructionMethodBasedon3DTINLIFengchun??1,GONGJun??1,WANGQing??2(1.StateKeyLaboratoryofInformationEngineeringinSurveyingMappingRemoteSensing,WuhanUniversity,WuhanHubei430079,China;2.StateKeyLaboratoryofCADCG,Zhe激angUniversity,HangzhouZhe激ang310027,China)Abstract:Thispaperfirstlybyanalysingandclassifyingthewidevarietyof3DTINgenerationmethods,providesaclearoveralloutlineofallthosetypicalmethods.Secondly,acombinatorialalgorithmforsurfacereconstructionfromthreedimensionalpointsispresented,whichisacombinationofthesculpturealgorithmandgrowingalgorithm.Aregiongrowingstartingfromarbitrarysideoftheseedtriangleispreformed.Duringthegrowingprocedure,aweightedminimallengthcriterionisemployedtoensuredgeometricintegrityandautomaticboundarydetection.Experimentalresultsshowthatthealgorithmcanefficientlyobtainthereconstructedmeshsurfacewitharbitrarytopologyandwithonlysmalltopologicaldifferencefromthesurfaceoftheoriginalobject.?ぁ?Keywords:3DTIN;SurfaceReconstruction;3DDelaunayTriangulation;ThreeDimensionalVisualization?お?根据影像匹配和激光扫描获得的大量三维离散点集数据快速准确地重建物体的几何表面模型，在虚拟环境、计算机视觉、逆向工程等诸多领域具有重要的意义。随着数字摄影测量、高分辨率遥感技术，特别是激光扫描系统的发展，包含被测目标更多细节的三维点云数据获取成为可能，并且成为高精细测量建模的发展方向。由于将真实世界从三维空间投影到二维平面，二维TIN模型及其相关算法的弊端已经表现得越来越明显，如何实现快速准确的真三维表面构模已经成为目前亟待解决的问题。1三维TIN算法回顾??三维TIN构网算法种类繁多，Mencl[1]的分类方法曾经是一种广为接受的分类方法，但是它并不能很好地概括现有方法的特点。根据每类方法的原理和主要特点，本文将现有典型---本文来源于网络，仅供参考，勿照抄，如有侵权请联系删除---的三维TIN构网方法从宏观上分为直接法和间接法两大类。直接法包括雕刻算法、距离函数法、表面生长法；间接法主要有映射法。1.1雕刻算法??雕刻算法(SculptureAlgorithm)是三维表面构网应用最为广泛的方法。这类算法的基本思想首先是计算离散点集的拓扑邻接关系，然后根据特定的规则或知识提取表面三角形面片。根据提取策略的不同，其代表算法又有αshape算法[2,3]、Crust算法[4]、Cocone算法[5]、伞形过滤算法等[6,7]。法国INRIA的Boissonnat[8]最早提出了雕刻算法，首先对点集进行Delaunay三角化，然后通过对外接球半径的判断剥离冗余四面体和三角形使物体表面的所有散乱点可见。冗余四面体的剔除规则和剔除的先后顺序对最终构网结果的影响很大，因此不同的提出了各自的剔除策略。αshape算法和γindicator算法[9]实际上是一种参数构造的方法，根据参数值以递增次序删除冗余四面体，这种方法处理密度不均匀的数据需要更多的人工干预。Attene[10]的方法采用欧几里德最小空间树(EuclideanMinimumSpanningTree,EMST)和扩展的Gabriel超图(ExtendedGabrielHypergraph,EGH)作为约束剔除准则。Crust算法和Cocone算法在提取表面时利用了表面的近似法向和角度参数，但是往...