基于距离加权的二次误差测度的网格简化算法

摘要

随着科学技术的快速发展，计算机图形学与虚拟现实、医学图像系统、地理信息系统、计算机辅助设计技术等领域够构造出的模型数据量越来越庞大，为了描述这些复杂度与精度日益提高的三维形体，人们通常使用三角形网格模型。但存储、计算、交互显示、传送这些复杂的网格数据往往超出了目前计算机的存储能力、处理与绘制速度、传输效率，同时在实际应用中，远景物体没必要显示过多细节。因此，人们在研制性能更高、处理速度更快的计算机的同时，也加紧提出了多种简化模型的技术和算法，在这些技术与算法中细节层次(LOD)模型是当前对模型进行简化最常用与有效的方法之一。细节层次模型就是以不同的精度来表示场景中的各物体：以较精细的网格米表示离视点较近的物体，而以较粗糙的网格表示离视点较远的物体。 本义首先介绍网格简化相关的背景知识，并对当前几类简化算法做了深入探讨，进一步分析了各类算法的优缺点，讨论了简化处理中的关键技术如简化方法的选择以及误差度量准则，在此基础之上，重点研究了三角形网格模型的简化方法，给出了建立视点相关的多层次细节模型的网格简化算法：以三角形折叠为基本简化操作，加权二次误差测度作为折替误筹控制三角形的简化顺序。在简化过程中，引入了距离因子与三角形形态品质因子：网格顶点与视点的距离因子使得产生的网格符合观察需要的网格，与视点位萱相火；二角形形态品质因子的引入，提高了简化后新生成的二角形的形态品质。根据三角形的折替代价，构造一个简化序列，误差较小的二角形优先得剑简化，同时，采取了邻域冻结办法，避免了对模型的某个部位过度简化与过人三角形的出现；每次误差排序后，可以一次简化多个三角形，实现了连续折叠简化。在简化率要求相同的条件下，连续折叠简化的排序次数大大减少。 本文提出的改进网格简化算法在保持原有拓扑结构的基础上，保留了其细节特征，能适应各种特殊需求；由于采用了有效的误差度量方法，生成模型的精度可控，通过调整误差边界，可获得一系列多层次细节模型；改进算法采取用户给定误差阈值，使简化质量达到用户的不同化简需求：改进后算法的普遍性和实用性很强。最后，构造了基于二次误差测度的网格简化算法框架，从理论分析与实际运行两方面论证了本文算法和Garland算法的时间效率与简化效果。

目录

文摘

英文文摘

声明

第一章绪论

1.1引言

1.2国内外研究现状

1.3应用领域

1.4本文所做的工作

1.5本文组织结构

第二章网格简化算法研究

2.1引言

2.2模型简化的基本概念

2.3简化算法分类

2.3.1静态简化方法

2.3.2动态简化方法

2.3.3外存模型简化方法(Out-of-Core)

2.3.4简化方法特征对比

2.4模型简化研究内容

2.4.1网格模型表示方法

2.4.2 LOD模型

2.4.3误差度量准则

2.4.4视相关的网格简化准则

2.4.5模型简化算法的性能要求

2.5小结

第三章二次误差测度网格简化算法

3.1引言

3.2 Garland简化算法

3.2.1二次误差测度

3.2.2顶点对选择

3.2.3算法流程

3.2.4 Garland算法特点

3.3算法设计准则

3.4本文算法策略

3.4.1简化方法

3.4.2简化操作的合法性削断

3.4.3误差测度与新点位置计算

3.4.4邻域冻结机制

3.4.5简化序列的构造

3.4.6控制函数

3.5小结

第四章算法应用实例与性能评价

4.1数据结构设计

4.2数据预处理与三角形拓朴关系的建立

4.3算法流程

4.4实验结果

4.5性能分析

4.5.1时间复杂度

4.5.2简化效果

4.6小结

第五章结论与展望

5.1本文工作总结

5.2今后工作展望

致谢

参考文献

攻读硕士期间发表的论文