第２６卷，第１期中国铁道科学Ｖｄ．２６Ｎｏ．１２００５年１月ＣＨＩＮＡＲＡＩＩｊＷＡＹＳＣＩＥＮＣＥＪａｎｕａｒｙ，２００５文章编号：１００１—４６３２（２００５）０１—００７８—０５基于二次误差测度的带属性三角网格简化算法赵惠芳，阮秋琦（北京交通大学信息科学研究所，北京１０００４４）摘要：给出一种基于边折叠和二次误差测度的快速简便的算法来简化带属性的网格模型。该算法通过分别建立几何和颜色属性二次误差测度来计算几何和颜色属性误差，用几何与颜色属性误差的总和来控制网格简化的顺序和精度。边折叠是根据某种误差测度将候选的边按照折叠代价排序，每次取代价最小的边进行折叠操作，直至满足给定的终止条件。二次误差测度采用点到平面距离的平方作为误差测度。应用实例表明，该算法既能保证简化模型同初始模型在几何上尽可能相似，又能较好地保留初始模型的颜色、纹理等属性信息。关键词：三角网格模型；模型简化；网格简化；边折叠；二次误差测度；几何属性；颜色属性中图分类号：ＴＰ３０１．６文献标识码：Ａ随着利用卫星、扫描仪、医学图像仪器等获取格模型进行几何简化，建立简化网格模型与初始网数据的技术不断完善，人们可以得到越来越精细复格模型之间的映射，然后对初始网格模型进行属性杂的三维模型。这些模型在计算机图形学、计算机采样，生成包含属性细节的纹理，并将该纹理附给辅助设计、计算机视觉、虚拟现实等领域被广泛地简化网格模型中的三角片。第二类算法是在几何简使用。三维模型通常用多边形网格，尤其是三角形化过程中保持属性特征，即将几何信息和其他属性网格来描述。复杂的三角网格模型常常由几十万特征的处理集成在一起。根据使用的属性误差测个、几百万个甚至上亿个三角面片组成。为了满足度，第二类算法又可分为：采用顶点到顶点距离作计算机存储、传送和显示的要求，必须对这类模型为属性误差测度，如Ｅｒｉｋｓｏｎ等提出的ＧＡＰＳ顶点进行简化。近些年来，国内外就三角网格模型的简云算法［６］，通过计算顶点到其周围顶点云中各顶点化问题提出了很多算法，按照简化机制不同可以分屙ｆ生值的距离来计算属性误差，通过计算顶点到相为：自适应细分型【１］，首先建立原始模型的最简化关平面的距离来计算几何误差，再将几何误差和属形式，然后根据一定的规则通过细分把细节信息增性误差加权求和得到总误差；采用顶点到平面距离加到简化模型中；采样型［２］，类似于图象处理的滤作为属性误差测度，如Ｇａｒｌａｎｄ等提出的多维二次波方式，把几何包围盒中的一组顶点用一个代表顶误差度量算法［７］，用多维矢量来保存几何和属性信点代替；几何元素删除型【３“］，通过重复地把几何息，通过计算多维空间中顶点到平面的距离来计算元素从网格中“移去”得到简化模型。总误差；采用顶点到表面距离作为属性误差测度，但是其中大部分算法只考虑了简化网格与初始如Ｈｏｐｐｅ【８１将几何简化中的顶点到表面距离推广到网格在几何上的相似性，而三角网格模型常常还包属性误差计算中，分别计算几何和属性误差，相加含有颜色、纹理等属性。如果简化过程中没有考虑得到总误差。该算法实现简单，速度快，并且可以这些属性的作用，得到的简化模型就不能很好地保方便地建立带属性的渐进网格。留初始网格的这些特征。本文提出一种新的带属性的三角网格简化算目前带属性的三角网格模型简化算法大致可分法，通过为网格的属性特征建立独立的二次误差测为两类。第一类算法是对其他属性的处理独立于几度来控制属性误差。何简化。如Ｐ．Ｃｉｇｎｏｎｉ提出的算法【５ｊ，先对初始网收稿日期：２００３—１１．１０作者简介：赵惠芳（１９７８一），女，吉林大安人，硕士研究生。万 方数据第１期基于二次误差测度的带属性三角网格简化算法７９１算法描述１．１边折叠操作本算法对网格进行简化的基本操作是边折叠。边折叠是一种迭代的几何元素删除方法，它的基本思想是根据某种误差测度将候选的边按照折叠代价（折叠引入的误差）排序，每次取代价最小的边进行折叠操作，直至满足给定的终止条件。图１给出了边折叠操作的过程：将边（１，，，ｙ：）简化成一个新的顶点ｙ，并让与该边端点相连的各个顶点都与新顶点相连，同时删除所有退化的边和面。简化前图１边折叠操作边折叠后的新顶点的选取有两种策略。①优化选择法。计算空间位置ｖ，使折叠操作引起的误差代价最小。可以在两点连线上寻找１，，也可以在全空间寻找＇，。②子集选择法。选择边的两个端点＇，，和ｌ，：中使折叠代价较小的为新顶点位置。为了减小算法的复杂度和便于形成渐进网格，本文采取子集选择法。１．２二次误差测度二次误差测度最早由Ｇａｒｌａｎｄ［９］提出，采用点到平面的距离平方作为误差测度。它的优点是具有较高的计算速度，较小的内存消耗，而且得到的简化网格具有较高的质量。它是在速度非常快但简化质量很差、速度很慢但简化质量非常好的两类方法之间的一种折衷，是一种兼顾了速度和质量的较理想的误差测度。在三维欧氏空间中，一个平面可以表示为ｎＴｌ，＋ｄ＝０，其中ｎ＝［以。，咒。，咒：］Ｔ是平面的单位法线矢量，ｄ是常量。点ｌ，＝［ｏＺ＇，Ｙ，ｚ］Ｔ到该平面的距离的平方就可以表示为Ｄ２＝（ｎＴｌ，＋ｄ）２＝（１，Ｔｎ＋ｄ）（ｎＴ＇，＋ｄ）＝ｌ，Ｔ（ｎｎＴ）ｌ，＋２ｄｎＴｖ＋ｄ２（１）可以定义三元组Ｑ＝（Ａ，ｂ，Ｃ）＝（ｎｎ１，ｄｎ，万 方数据ｄ２）来表示Ｄ２，Ｄ２＝Ｑ（１，）＝ＶＴＡｖ＋２ｂＴｖ＋ｃ（２）Ｑ称作二次误差测度或二次矩阵，Ｑ（１，）称作二次误差。利用二次误差测度可以方便地实现误差累加Ｑ１（１，）＋Ｑ２（１，）＝（Ｑ。＋Ｑ２）（１，）（３）其中（Ｑ１＋Ｑ２）＝（Ａｌ＋Ａ２，ｂ１＋ｂ２，Ｃ１＋ｃ２）。二次误差测度在几何上可以解释为［７］：由Ｑ（ｖ）＝￡确定的等值面是椭球面（可能退化）；Ａ是一个对称的半正定矩阵，它的特征值和特征向量决定了椭球面的主轴。１．３表面属性在计算机图形学中，三角网格模型最常见的表面属性有颜色、纹理和法线。为了使简化模型同初响，可以比较准确地描述局部属性误差，同时又比网格模型的每个顶点除了空间坐标外，还具有比如对于颜色属性，可以用三维矢量［ｒ，ｇ，图２ＲＧＢ彩色空间始模型具有良好的相似性，必须在保持模型几何信息的同时保留这些属性特征。由于点到平面的距离考虑了简化操作对顶点周围区域属性值变化的影点到表面或表面到表面的距离计算简便快捷。因此，采用点到平面的距离作为属性误差测度，将二次误差测度应用到属性误差的计算中。描述其属性的数值。在网格模型的三角面上，属性值根据几何位置插值得到。因此，三角面上的属性值是连续的，而且两个属性值之间的距离用欧氏距离来度量。ｂＩＴ来表示（０≤ｒ，ｇ，ｂ≤１），所有颜色矢量构成了ＲＧＢ彩色空间，如图２所示。在ＲＧＢ彩色空间中点到平面的距离平方同样可以用二次误差Ｑ（１，）来计算。边折叠后的新顶点采用子集选择法，不用重新计算新顶点的空间位置和属性值，在计算误差的时候不用考虑空间坐标和属性值的相关陛，只需中国铁道科学第２６卷萋烹三曹氅要蠢苎总代价中的影响系数，可以堡篓耋堂重量黧翌！二。旧晡审一。苎婴室整竺堡誊孽磐孽，皂｝、＝：？曼：，ｎ要璧选边菜警‘菇菇巢答莘磊莛荔赢莛黼排毒：‘苎竺苎票萋里曩』ｏ，二ｌ』壁２：翌婴一≮兽量罗乎４“三蔷：议苌磊品菇；蒿荔。苫薪二玉搭釜乐晶目佰套茎荨苎纂耋垡竺罂趸两，问题尊要要意二：顶点。并寿薪荔蒜葚。矗≤……～～…“””≤ｆ荡藩高莉兰答薯名；矗差蟊边组成一个候“一Ｓ”ｔｅ羼ｐ４。：计算每条边的折叠代价和折叠后的新苎数据警行预竺｝，。孚三煮苎围璺，：邕堡‘篓墨边执藉并ｉ纛：器籀薪薪箸黼、。●川“。…和Ｅｃ型Ｃｏｓｔ竺影响苎等价曾；．二是会学翌三角警…‘当：；ｉｊｊ巢筷≤ｉ藁各茹薹麦三狺形数目已模型类型仅包含几何信息几何信息＋颜色＋Ｇａｒｌａｎｄ的多维二次误差测度算法顶点表示［ｚ，ｙ，ｚ］Ｔ［ｚ，ｙ，ｚ，ｒ，ｇ，６］ＴＡ本算法顶点表示Ｉｘ，ｙ，２］Ｔ［ｚ，ｙ，ｚ］Ｔ，［ｒ，ｇ，６］７ＡＱ的系数Ｑ的系数３×３６（ｉ）＝１０（！）＝２８３３３（ｉ）＝ｉ０２６３ｘ（ｉ）＝２０些笪堡星±鲨堡［兰：型：兰：兰：！：丛：！兰！！１２三垫［兰：２：！￡：［璺：！：！￡ｉ兰ｉ！兰！ｉ！三！！万方数据 第１期基于二次误差测度的带属性三角网格简化算法８１本算法不需要在每次边折叠操作前求解二次误图３中的（ａ），（ｃ），（ｅ），（ｇ）均为采用Ｃ－ｏｕｒ—差测度值的优化问题，因而省去了部分运算开销，ａｕｄ明暗处理方式显示的实体模型图；而（ｂ），运算速度较快。（ｄ），（ｆ），（ｈ）为（ａ），（ｃ），（ｅ），（ｇ）所对应的线但是，由于新顶点的选取采用子集法而不是优框图。其中图３（ａ）为初始模型图，图３（Ｃ）和化选择法，所以在简化幅度很大的情况下，简化模图３（ｅ）分别为采用本算法简化删减了７５％和型的视觉效果就相对较差一些。８５％的三角面片后的简化模型图；图３（ｇ）则为采用不考虑属性特征仅利用二次度量误差对初始模３实验结果型进行几何上的简化，删减了７５％后的简化模型图。从图３（Ｃ）、图３（ｅ）同图３（ｇ）的对比可以本算法已在主频２．０ＧＨｚ，内存１２８Ｍ的ＰＣ看到本文算法能够很好地保持属性特征，这是因为机上用Ｃ＋＋语言实现。图３和图４是本算法的两本算法在颜色属性变化剧烈的区域保留了较多的三个应用实例。角面片，从图３（ｄ）、图３（ｆ）同图３（ｈ）的对比图３的初始模型为一个带有螺旋图案的单位球可以清楚地看到。的一部分，共有９２０６个顶点，１８０５０个三角面图４的初始模型为彩色地球模型，共有３６８６６片。执行简化操作大约需要４ＭＢ的内存空间，其个顶点，７３７２９个三角面片。其中（ａ）为初始模中所有顶点的二次误差测度占大约０．７ＭＢ（每个型，（ｂ），（Ｃ），（ｄ）分别为采用本算法简化５０％，二次误差测度用１０个单精度浮点系数描述）。简化７５％，９０％的模型。原始模型的８５％耗时０．７２ｓ。（ａ）劫始模型图Ｏ））初始辏蹙线短露（；ｃ）本算法简纯７５９６（ｄ）图（ｃ）对应朗缝框图（ｅ）本文算法简化８５％（ｔ３图（０对应的线摇图（ｇ）不考虑属性箍化７５％（１１）图（囝对应的线框图图３算法应用实例１（ａ）韧始楱型匿（ｂ）本文算法简化５０％（ｃ）本文算法筒化７５％（ｃ）本文算渚简化９０％图４算法应用实例２万 方数据中国铁道科学第２６卷状，还能较好地保留网格的颜色等屙陛信息。本算４结论法速度快，占用存储空间小，能方便地用于建立带属性的渐进网格，很适合带属性网格模型的实时交提出基于二次误差测度的带属性网格简化算互、渐进传输等应用。法，在网格简化过程中不仅保持了网格的几何形参考文献ｎ１ＪＤｅｈａｅｍｅｒＪｒ，ＭｉｃｈａｅｌＪ．ＳｉｍｐｌｉｆｉｃａｔｉｏｎｏｆＯｂｊｅｃｔｓＲｅｎｄｅｒｅｄｂｙＰｏｌｙｇｏｎａｌＡｐｐｒｏｘｉｍａｔｉｏｎｓ［Ｊ］，Ｃｏｍｐｕｔｅｒ＆Ｇｒａｐｈｉｃｓ，１９９１，１５（２）：１７５—１８４．眨１ＪＲｏｓｓｉｇｎａｃＪ，ＢｏｒｒｅｌＰ．Ｍｕｌｔｉ—ｒｅｓｏｌｕｔｉｏｎ３ＤＡｐｐｒｏｘｉｍａｔｉｏｎｆｏｒＲｅｎｄｅｒｉｎｇＣｏｍｐｌｅｘＳｃｅｎｅｓ［Ｊ］．ＧｅｏｍｅｔｒｉｃＭｏｄｅｌｉｎｇｉｎＣｏｍｐｕｔｅｒＧｒａｐｈｉｃｓ，１９９３，５（２）：４５５－－４６５．ｂ１ＪＳｃｈｒｏｅｄｅｒＷ，ｚａｒｇｅＪ，ＬｏｒｅｎｓｅｎＷ．ＤｅｃｉｍａｔｉｏｎｏｆＴｒｉａｎｇｌｅＭｅｓｈｅｓ［Ａ］．ＣｏｍｐｕｔｅｒＧｒａｐｈｉｃｓ：ＳＩＧＧＲＡＰＨ１９９２，Ｐｒｏ—ｃｅｅｄｉｎｇｓ１９９２［Ｃ］．Ｃｈｉｃａｇｏ：ＡＣＭＰｒｅｓｓ，１９９２：６５—７０．Ｉ！Ｊ１ＪＣｏｈｅｎＪ，ＶａｒｓｈｎｅｙＡ，Ｍａｎｏｃｈａ．Ｄ，ｅｔａ１．ＳｉｍｐｌｉｆｉｃａｔｉｏｎＥｎｖｅｌｏｐｅｓ［Ａ］．ＣｏｍｐｕｔｅｒＧｒａｐｈｉｃｓ：ＳＩＧＧＲＡＰＨ１９９６，Ｐｒｏ—ｃｅｅｄｉｎｇｓＣ１．ＮｅｗＯｒｌｅＢＩ＇ＩＮ：ＡＣＭＰｒｅｓｓ，１９９６：１１９—１２８．ｂ１ＪＣｉｇｎｏｎｉＰ，ＭｏｎｔａｎｉＣ，ＲｏｃｃｈｉｎｉＣ，ｅｔａ１．ＰｒｅｓｅｒｖｉｎｇＡｔｔｒｉｂｕｔｅＶａｌｕｅｓｏｎＳｉｍｐｌｉｆｉｅｄＭｅｓｈｅｓｂｙＲｅｓａｍｐｌｉｎｇＤｅｔａｉｌＴｅｘ—ｔｕｒｅｓ［Ｊ］．ＴｈｅＶｉｓｕａｌＣｏｍｐｕｔｅｒ，１９９９，１５（１０）：５１卜５３９．№１ｊＥｒｉｋｓｏｎＣ，ＭａｎｏｃｈａＤ．ＧＡＰＳ：ＧｅｎｅｒａｌａｎｄＡｕｔｏｍａｔｉｃＰｏｌｙｇｏｎａｌＳｉｍｐｌｉｆｉｃａｔｉｏｎ［Ａ］．Ｐｒｏｃｅｅｄｉｎｇｓｏｆ１９９９ＡＣＭＳｙｍｐｏ—ｓｉｕｍＩｎｔｅｒａｃｔｉｖｅ３ＤＧｒａｐｈｉｃｓ［Ｃ］．Ａｔｌａｎｔａ：ＡＣＭＰｒｅｓｓ，１９９９：７９—８８．口ＧａｒｌａｎｄＭ，ＨｅｅｋｂｅｒｔＰＳ．ＳｉｍｐｌｉｆｙｉｎｇＳ１．１ｒｆａｃｅｓｗｉｔｈＣｏｌｏｒａｎｄＴｅｘｔｕｒｅｕｓｉｎｇＱｕａｄｒｉｃＥｒｒｏｒＭｅｔｒｉｃｓ［Ａ］．ＰｒｏｃｅｅｄｉｎｇｓｏｆＩＥＥＥＶｉｓｕａｌｉｚａｔｉｏｎ１９９８［Ｃ］．ＲｅｓｅａｒｃｈＴｒｉａｎｇｌｅＰａｒｋ：ＩＥＥＥＣｏｍｐｕｔｅｒＳｏｃｉｅｔｙａｎｄＡＣＭ，１９９８：２６３—－２６９．ＨｏｐｐｅＨ．ＰｒｏｇｒｅｓｓｉｖｅＭｅｓｈｅｓ［Ａ］．ＰｒｏｃｅｅｄｉｎｇｓｏｆＳＩＧＧＲＡＰＨｌ９９６［Ｃ］．ＮｅｗＯｒｌｅａｎｓ：ＡＣＭＰｒｅｓｓ，１９９６：９９—１０８．滔ｐ１ＪＧａｒｌａｎｄＭ，ＨｅｃｋｂｅｒｔＰＳ．ＳｕｒｆａｃｅＳｉｍｐｌｉｆｉｃａｔｉｏｎｕｓｉｎｇＱｕａｄｒｉｃＥｒｒｏｒＭｅｔｒｉｃｓ［Ａ］．ＣｏｍｐｕｔｅｒＧｒａｐｈｉｃｓ：ＳＩＧＧＲＡＰＨ１９９７，Ｐｒｏｃｅｅｄｉｎｇｓ［Ｃ］．ＬｏｓＡｎｇｅｌｅｓ：ＡＣＭＰｒｅｓｓ，１９９７：２０９—２１６．ＳｉｍｐｌｉｆｉｅｄＡｌｇｏｒｉｔｈｍｆｏｒＴｒｉｇｏｎｏｍｅｔｒｙＭｅｓｈｅｓｗｉｔｈＡｔｔｒｉｂｕｔｅｓＢａｓｅｄｏｎＱｕａｄｒｉｃＥｒｒｏｒＭｅｔｒｉｃＺＨＡＯＨｕｉ—ｆａｎｇ，ＲＵＡＮＱｉｕ—ｑｉ（ＩｎｓｔｉｔｕｔｅｏｆＩｎｆｏｒｍａｔｉｏｎＳｃｉｅｎｃｅ，ＢｅｉｊｉｎｇＪｉａｏｔｏｎｇＵｎｉｖｅｒｓｉｔｙ，Ｂｅｉｊｉｎｇ１０００４４，Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ：Ａｓｉｍｐｌｅａｎｄｆａｓｔａｌｇｏｒｉｔｈｍｉｓｐｒｅｓｅｎｔｅｄ，ｗｈｉｃｈｉｓｂａｓｅｄｏｎｉｔｅｒａｔｉｖｅｅｄｇｅｃｏｌｌａｐｓｅａｎｄｑｕａｄｒｉｃｅｒｒｏｒｍｅｔｒｉｃｔｏｓｉｍｐｌｉｆｙｍｅｓｈｍｏｄｅｌｓｗｉｔｈａｔｔｒｉｂｕｔｓｉ乃ｅａｌｇｏｒｉｔｈｍｕｓｅｓｑｕａｄｒｉｃｏｆｇｅｏｍｅｔｒｙｔｏｍｅａｓｕｒｅｅｒｒｏｒｓｉｎｇｅ—ｏｍｅｔｒｙａｎｄａｓｓｉｇｎｓａｓｅｐａｒａｔｅｑｕａｄｒｉｃｔｏｅａｃｈａｔｔｒｉｂｕｔｅｔｏｍｅａｓｕｒｅｅｒｒｏｒｓｉｎａｔｔｒｉｂｕｔｅ．Ｔｈｅｓｕｍｏｆｇｅｏｍｅｔｒｙｅｒｒｏｒａｎｄａｔｔｒｉｂｕｔｅｅｒｒｏｒｉｓｕｓｅｄｔｏｃｏｎｔｒｏｌｔｈｅｏｒｄｅｒｏｆｓｉｍｐｌｉｆｉｃａｔｉｏｎ．Ｅｄｇｅｃｏｌｌａｐｓｅｓｏｒｔｓａ１１ｔｈｅｅｄｇｅｓｂｙｔｈｅｉｒｃｏｌｌａｐｓｅｃｏｓｔａｎｄｅｖｅｒｙｔｉｍｅｃｈｏｏｓｅｓｔｈｅｅｄｇｅｗｉｔｈｍｉｎｉｍａｌｃｏｓｔｔｏｃｏｌｌａｐｓｅｉｔｅｒａｔｉｖｅｌｙｕｎｔｉｌｍｅｅｔｉｎｇｔｈｅｆｉｎａｌｃｏｎｄｉｔｉｏｎｓｇｉｖｅｎ．Ｑｕａｄｒｉｃｅｒｒｏｒｍｅｔｒｉｃｔａｋｅｓｔｈｅｓｑｕａｒｅｄｉｓｔａｎｃｅｂｅｔｗｅｅｎｐｏｉｎｔａｎｄｐｌａｎｅａｓｅｒｒｏｒｍｅｔｒｉｃ．Ｐｒａｃｔｉｃａｌｅｘａｌ＇ｎ—ｐｌｅｓｓｈｏｗｔｈａｔｔｈｅａｌｇｏｒｉｔｈｍｃａｎｐｒｅｓｅｒｖｅａｔｔｒｉｂｕｔｅｄｅｔａｉｌｏｆｔｈｅｏｒｉｇｉｎａｌｍｅｓｈａｎｄｇｕａｒａｎｔｅｅｔｈａｔｔｈｅｓｉｍｐｌｉｆｉｅｄｍｅｓｈｍａｔｃｈｅｓｗｅｌｌｗｉｔｈｔｈｅｏｒｉｇ‘ｉｎａｌｏｎｅｉｎｃｏｌｏｒａｎｄｔｅｘｔｕｒｅａｔｔｒｉｂｕｔｅｓ．Ｋｅｙｗｏｒｄｓ：Ｔｒｉｇｏｎｏｍｅｔｒｙｍｅｓｈｍｏｄｅｌ；Ｍｏｄｅｌｓｉｍｐｌｉｆｉｃａｔｉｏｎ；Ｍｅｓｈｓｉｍｐｌｉｆｉｃａｔｉｏｎ；Ｅｄｇｅｃｏｌｌａｐｓｅ；Ｑｕａｄｒｉｃｅｒ—ｍｒｍｅｔｒｉｃ；Ｇｅｏｍｅｔｒｙａｔｔｒｉｂｕｔｅ；Ｃｏｌｏｒａｔｔｒｉｂｕｔｅ（责任编辑刘卫华）万 方数据基于二次误差测度的带属性三角网格简化算法
作者：作者单位：刊名：英文刊名：年，卷(期)：被引用次数：
赵惠芳， 阮秋琦
北京交通大学,信息科学研究所,北京,100044中国铁道科学
CHINA RAILWAY SCIENCE2005，26(1)3次
1.Dehaemer Jr.Michael J Simplification of Objects Rendered by Polygonal Approximations 1991(02)2.Rossignac J.Borrel P Multi-resolution 3D Approximation for Rendering Complex Scenes 1993(02)3.Schroeder W.Zarge J.Lorensen W Decimation of Triangle Meshes 19924.Cohen J.Varshney A.Manocha. D Simplification Envelopes 1996
5.Cignoni P.Montani C.Rocchini C Preserving Attribute Values on Simplified Meshes by ResamplingDetail Textures 1999(10)
6.Erikson C.ManochaD GAPS: General and Automatic Polygonal Simplification 1999
7.Garland M.Heckbert P S Simplifying Surfaces with Color and Texture using Quariic Error Metrics1998
8.Hoppe H Progressive Meshes 1996
9.Garland M.Heckbert P S Surface Simplification using Quadric Error Metrics 1997
1.学位论文 刘湘云 基于概率函数的三角网格模型简化算法研究与系统实现 2004
在计算机辅助设计、计算机动画、科学计算可视化、虚拟现实等许多图形应用系统中,三维物体常用三角网格模型表示,复杂的三角网格模型将给计算机存储与传输三维物体带来困难.可是,很多情况下人们并不需要对每一模型的细节都作详细的刻画,如:一个复杂的场景中,远景物体就没有必要有过多的细节.因此,可根据对模型细节程度的要求不同而对复杂模型进行一定的简化.该文针对三角网格模型的快速简化方法进行研究.首先,论文介绍了三角网格模型的有关概念和误差的评估方法,对当前各种简化算法进行了详细的综述.然后,在总结折叠型简化算法简化过程的基础上,提出了一个基于概率值连续折叠的三角网格简化算法.算法以三角形折叠为基本简化操作,可调加权控制函数作为折叠误差控制三角形的简化顺序,根据所有三角形的误差分布,构造一个概率分布函数,为每个待折叠的三角形计算一个折叠概率值.在简化过程中,所有三角形按其概率进行折叠,误差较小、概率值较大的三角形优先得到简化.由于满足简化条件的三角形个数增加,每次误差排序后,三角形折叠的个数由传统的1个增加为若干个,折叠的方式也由传统的单次折叠简化改进为连续折叠简化.在简化率要求相同的条件下,连续折叠简化的排序次数大大减少.因此,从误差优先级排序的角度加快了简化速度.最后,该文设计了一个演示系统,实现了该文算法,并从理论分析与实际系统运行两方面验证了该文算法和传统的单次折叠简化算法的时间效率,得出了连续折叠简化的排序时间较单次折叠简化的排序时间快m倍的结论(m为平均连续折叠的三角形个数).演示系统的实验结果表明,该算法在保持误差基本相同的情况下,整体简化速度较单次折叠提高10倍以上.另外,该文还将本算法与包络控制简化算法进行了比较,结果表明,该算法简化速度快,简化结果更加均匀.最后通过一组实验验证了选择不同的控制权值可以得到不同形状的简化结果.
2.学位论文 郭震宇 三角网格模型的简化技术及多细节层次模型 2006
三维网格模型作为一种新的媒体形式，已经开始逐渐进入人们的生产和生活中，在虚拟现实、动画游戏、生产制造等各个方面的应用都越来越广泛。随着三维激光测距和建模技术的不断发展，三维模型的精度越来越高，数据量也随之飞速增长，给计算机的绘制、传输、编辑等系统都带来了巨大的压力。解决这些问题的一个途径就是对复杂的三维模型进行简化和多分辨率建模，用比较简单的几何模型来代替复杂的原始模型，以减少数据量，加快处理速度，节约存储空间。可见三维网格模型简化算法的研究课题具有一定的应用价值。
论文首先介绍了模型简化技术的由来，研究内容，意义及其应用领域。并论述了由空间点云数据重构出三角网格模型的方法。随后对当前国内外有关的三角网格模型的简化算法进行了分析和研究，讨论了静态简化算法和动态网格简化算法，并对一些常见的误差测量度量方法进行了介绍。随后，详细讨论了以二次误差作为度量方法的边折叠算法，论述了二次误差度量方法的原理，边权的定义，模型简化过程，以及生成新顶点的最佳位置。该方法高效地实现了静态模型简化，对原始模型的几何形态保存的较为完整。
由于静态模型简化不能实现在同一个模型中的多细节层次，因而在此重点介绍了一种动态模型简化方法，即渐进网格算法，简称PM算法。介绍了渐进网格算法的原理及实现过程，并给出了边收缩的合法条件，及论述了顶点分裂时产生的二义性和解决方法。该方法为三角网格中的每一条边计算了一个能够反映边长、邻域内的曲率和三角形形状等局部几何信息的权值，并通过比较边权的大小来确定边收缩操作的顺序。针对基于视点的多分辨率控制的模型构造，为简化的三角网格模型建立了一种紧凑、灵活的多分辨率数据结构，并且借助这种数据结构实现了网格的基于视点的绘制。在该方法重建出的多分辨率模型表面上，LOD呈连续分布，并且能够跟随注视点位置的变化发生动态变化。最后，给出了实验结果及相关讨论。
3.期刊论文 万定生.倪海涛.WAN Ding-sheng.NI Hai-tao 基于代价函数三角网格模型动态简化的研究 -计算机工程与应用2009,45(7)
模型简化是解决复杂三维模型存储、传输、实时绘制与硬件处理能力的局限性之间矛盾的主要方法.介绍了三角网格模型简化相关技术和算法.目前基于边折叠的三角网格模型简化算法边折叠计算复杂,没有有效进行动态简化,结合Garland的二次误差度量算法和Hoppe的累进网格算法,提出了基于代价函数的三角网格模型动态简化算法.
4.学位论文 曹彩霞 三角网格模型分割及其简化应用 2008
近年来，随着计算机技术和三维扫描技术的发展，出现的一种新的多媒体数据类型——三维几何模型。三维网格模型成为表示数字几何模型的重要手段，并且在娱乐、网络以及制造业中得到了广泛的应用。如何重用现有的网格模型以及如何根据新的设计目标修改现有网格模型，成为了一个重要的研究课题。网格分割由此提出，并成为近年网格模型处理领域的热点研究课题。网格模型的分割也有着重要的应用，如形状匹配、形状重建、网格编辑、模型简化、纹理映射、参数化等。本文围绕三角网格分割及其应用中的一种一基于分割的简化展开研究。
首先，研究了三角网格模型的分割问题，根据分割的对象和研究目的的不同，网格模型的分割类型主要有片面分割和部件分割两类，本文就片面分割提出一种新的方法一基于法向量差值的区域生长，在进行种子选择中，提出了在侯选种子中选择种子的方法，根据一种新的二面角的公式即法向量面积加权的差值进行区域生长，分割后对面积过小的面片区域进行优化处理。
其次，研究了网格分割的一种应用一基于分割的网格模型简化，首先将模型根据区域生长进行分割，在每个子区域中进行简化，以三角形折叠算法为基础，给出了基于离散高斯曲率和被折叠三角形为中心的法向量差值的折叠依据和新顶点的获取方法，分割保证了简化时可以避开特征的地方，同时也使简化的速度更快。
通过实验验证了以上算法是有效的。
5.学位论文 唐杰 逆向工程中三角网格模型的数据处理技术研究 2000
该文面向逆向工程曲面自动重建课题,深入研究了三角网格模型的重构、简化和修补技术,主要内容和成果如下:介绍了三角网格模型的数学描述及相关定义,研究了三角网格模型误差评估方法,给出了三角网格模型的数据结构和在计算机中表示.研究了三角网格模型的问题.给出了一处由空间—组散乱点集X重构三角网格模型的算法.重点研究了三角网格模型的简化技术,提出并实现了一种可控制简化精度的三角网格模型简化算法.该算法基于删除边单元操作,通过合理选择表征网格模型细节的检测点集及建立删除边的优先队列,使简化三角网格模型既保留了初始三角网格模型的细节特征,又有较大的压缩比例.提出并实现了一种带属性的三角网格模型简化算法,较好地解决了一般三角网格模型简化算法在简化过程中不能保存网格模型上颜色、纹理等初始信息的问题.针对复杂网格模型难以存储、传输和显示的问题,提出并实现了一种稳定、高效的递进网格模型生成算法.针对大多数三角网格模型存在孔洞,而这些孔洞往往会影响后续操作的问题,该文提出并实现了一种三维空间中边形孔洞的修补算法,并提出了孔洞多边形特征面的新概念.
6.期刊论文 邹北骥.申煜湘.彭群生.ZOU Bei-ji.SHEN Yu-xiang.PENG Qun-sheng 局部包络片控制误差简化三角网格模型 -电子学报2005,33(5)
利用内外包络控制三角网格模型简化误差是一种可行的方法.但构造整个模型的内外包络需要花费较多的时间,且每次简化操作时也会进行大量重复的三角形相交检测,使算法效率下降.针对这些问题,本文提出了局部包络片控制误差的思想,即每次简化操作仅利用相关部分的包络来控制误差.算法采用三角形收缩操作简化模型,当原始模型上的一个三角形被选中,并尝试进行收缩操作时,先构造其对应的局部包络片;在该三角形收缩后,原来与之相邻的三角形将发生形变,若这些形变后的三角形位于局部包络片之间,则认为此次三角形收缩操作可以接受,否则予以取消.实验结果表明,局部包络片保持了良好的误差控制效果,且由于构造简单,很少发生自交现象,减少了三角形相交检测次数,提高了计算效率.
7.学位论文 刘坚 虚拟现实中三维复杂模型简化技术研究 2005
模型简化是计算机图形学和虚拟现实的一个核心内容，主要研究在计算机图形系统环境中对模型的表示、设计和显示。它在处理中需要进行复杂的计算，并且消耗大量的计算机资源。而且，由于计算机图形显示对于真实性、实时性和交互性要求日益增强，图形工业迈向一体化、集成化和网络化步伐也不断加快，寻求快速的模型简化技术一直是研究的热点。
以几何元素删除实现模型的简化是多细节层次模型自动生成的常用方法。但由于复杂模型庞大的数据量以及模型简化复杂的计算，使得以往的LOD模型生成方法只能预先产生多个离散的简化模型，从而引起实时绘制时图形画面的跳跃。为解决这个问题，人们相继提出了渐进网格模型概念以及三维复杂模型的实时连续的多分辨率绘制技术。这种模型简化方法在快速生成模型和实时显示方面具有很大的优势。本文提出一种新颖的基于包络和三角形折叠的渐进网格生成方法和表示形式。在模型简化的整体效果方面，算法使用包络来控制模型简化的全局误差，保证了简化的整体特征。在生成包络时，本文提出了一种改进的方法来代替通用的数值计算方法，以提高包络的生成效率。在模型简化的局部效果方面，本文提出了三角形折叠和误差矩阵来共同控制模型简化的局部误差的方法，简化的速度比通常的边折叠方法和顶点删除方法更快，对简化过程中产生的空洞的三角化效果更好，使模型的局部特征得到很好的保持。在误差矩阵的设计中，算法能方便地加入颜色、纹理等属性因子，能保证在简化过程中模型的颜色、纹理等属性不失真。在简化过程中算法记录下整个模型简化过程中三角形删除的信息，并利用三角形删除与模型面片个数的对应关系，建立起渐进网格的表示形式。利用这种渐进网格表示形式我们实现了三维复杂模型的实时连续多分辨率绘制。该算法既能用于生成离散的LOD模型，又能用于生成连续的渐进网格。本算法的一个重要特点是可以根据当前视点参数产生连续的多分辨率近似模型，使得被绘制的三角网格模型的面片数目随视点的位置改变而产生连续的变化。
本文对下一步的工作进行了分析并且考虑从性能的优化等方面作进一步的改进。本文的成果对工业产品原型设计、计算机动画和虚拟现实技术中所需的形体表示等图形学与可视化研究方面的问题有一定的理论和实用参考价值。
8.期刊论文 韩丽.高小山.楚秉智.Han Li.Gao Xiaoshan.Chu Bingzhi 离散曲率约束的三角网格模型拓扑分割算法
-计算机辅助设计与图形学学报2009,21(6)
针对三角形网格模型简化中保持细节特征的要求,提出了依据离散曲率划分三角网格顶点的特性,并结合区域增长法自适应地确定拓扑分支的优化算法.每个顶点根据其相邻面片顶点的曲率值划分属性区域,并在区域生长过程中重复选择K-ring碟形区域中具有相似属性值的顶点作为种子.为了有效地探索凸凹形状区域,以曲率极值点作为初始点,提出了有效的区域增长及合并的策略,突出了模型的局部特征和拓扑结构.最后通过一系列实验验证了该算法的快捷性.
9.期刊论文 罗鹍.黄魁东.连明明.LUO Kun.HUANG Kui-dong.LIAN Ming-ming 基于顶点删除的三角网格模型简化新方法 -微电子学与计算机2009,26(5)
为进一步提高海量三角网格模型的简化速度,在经典顶点删除算法的基础上,从顶点法向量的保持、平均平面的近似获取、顶点删除后所留空洞的直接三角化3方面进行了改进.实验结果表明,改进后的顶点删除算法对三角网格模型的简化速度显著加快,简化后的模型与原模型相比在视觉上保持了良好的一致性,证明了该算法的有效性和可靠性.
10.期刊论文 潘家辉.鲍苏苏.Pan Jiahui.Bao Susu 虚拟手术仿真中三维模型简化方法的研究 -计算机与数字工程2009,37(11)
针对虚拟手术仿真中海量三角网格模型的特点,提出一种改进的基于边折叠的模型简化算法.该算法在经典边折叠算法的基础上,从误差估算、折叠点选取、模型平滑三方面进行了改进,进一步优化三维模型的简化速度和外观效果.实验结果表明,改进后的边折叠算法对海量三角网格的肝脏以及静脉模型的简化速度显著加快,简化后的模型与原模型相比在视觉上保持了良好的一致性,证明了该算法的有效性和可靠性.
1.李峰 基于二次误差测度的递进网格简化算法[期刊论文]-微处理机 2009(4)
2.袁天然.戴宁.程筱胜.廖文和 高质量保形三角网格简化算法[期刊论文]-系统仿真学报 2006(z1)3.刘秀文.解翠.金一丞 保持视觉外观特征的网格简化[期刊论文]-计算机辅助设计与图形学学报 2006(11)
本文链接：http://d.g.wanfangdata.com.cn/Periodical_zgtdkx200501015.aspx
授权使用：西北农林科技大学图书馆(wflsxbt)，授权号：c6d51a6b-3540-4cb8-876f-9e2200ffe8df
下载时间：2010年11月2日
