视锥体裁剪几何算法与测试方法研究

《视锥体裁剪几何算法与测试方法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、东华大学硕士学位论文视锥体裁剪几何算法与测试方法研究专业名称：机械工程作者姓名：余沛文指导教师：于海燕学校代码：10255学号：2130670视锥体裁剪几何算法与测试方法研究THERESEARCHONVIEWFRUSTUMCULLINGGEOMETRICALGORITHMANDTESTINGMETHOD作者姓名：余沛文专业名称：机械工程指导老师：于海燕答辩日期：2016年01月东华大学硕士学位论文答辩委员会成员名单姓名职称职务工作单位备注奚鹰教授答辩委员会主席同济大学张敏良教授答辩委员会委员上海工程技术大学孙志宏教授答辩委员会委员东华大学

2、单鸿波教授答辩委员会委员东华大学吕宏展副教授答辩委员会委员东华大学兼秘书东华大学硕士学位论文摘要视锥体裁剪几何算法与测试方法研究摘要随着三维几何模型越来越逼真、越来越复杂，虚拟环境的场景规模越来越大，如何有效减少绘制对象，降低模型复杂度，是三维显示系统中实现复杂场景快速稳定绘制的关键所在。高性能的视锥体裁剪算法对于提高场景绘制效率，增强虚拟场景的真实感、沉浸感起着至关重要的作用。视锥体裁剪是计算机图形学绘制的一个重要而基础的算法。本文概述了各类典型算法，分析了这些算法的优点、应用范围与某些限制，从几何的角度讨论了视锥体的裁剪问题，并对算法的稳

3、定性检测作了深入的研究。主要内容如下：（1）已有算法大多基于代数方法，本论文则是从几何的角度，依据几何问题几何化的思想，设计了一个基于几何以及投影降维原理的视锥体裁剪算法。基本思想是：构建适合视锥体裁剪的计算坐标系；在这个计算坐标系下，通过简单的正投影，视锥体和被裁剪线段的空间位置被简化为平面上线段与等腰梯形的关系。这种几何化降维方法有助于空间几何奇异问题的解决。I东华大学硕士学位论文摘要（2）基于投影降维原理，通过对分类方法的讨论，设计了一套客观、完整、详细的算法测试样本，用来综合评估算法的稳定性和速度。由于降维以后的视锥体裁剪变成了平面问

4、题，空间关系用两个平面投影表述，使得几何奇异关系变得比较清晰、相对简单。本文通过二维关系的导引，构建了空间视锥体裁剪中线段与视锥体的各种位置关系的测试样本，特别是几何奇异状态的78种可能位置关系，使得裁剪算法的检测不会处于一种盲目、随机的检测方式。（3）在VC++平台上分别实现了几何以及投影降维的视锥体裁剪算法、经典的Liang-Barsky算法和与6个面求交的一般算法。在定性分析基础上，利用测试样本对3种算法均做了稳定性与速度方面的测试。这是对视锥体裁剪算法的首次全面梳理和测试，发现并指出了每种算法的特点。本文基于几何以及投影降维的视锥体裁

5、剪算法，几乎用到了计算机图形学中典型裁剪算法的基本思想、方法和技术，如分区编码、参数式、降维、包围盒等。它们在Cohen-Sutherland算法、Nicholl-Lee-Nicholl算法、Liang-Barsky算法、Cyrus-Beck算法和基于包围盒编码的三维线段裁剪算法中各有应用。因此，本文设计的测试样本对这些算法的稳定性测试均有效，等于对这些算法也作了一个全面的测试。由于本文强调了算法的稳定性，所以这套测试样本及其构建思想对那些稳定性要求较高的几何算法的测试也有参考价值。关键词：视锥体裁剪；几何算法；投影降维；稳定性测试；几何奇异

6、II东华大学硕士学位论文ABSTRACTTHERESEARCHONVIEWFRUSTUMCULLINGGEOMETRICALGORITHMANDTESTINGMETHODABSTRACTWiththedevelopmentof3Dgeometrymodelbecomingmoreandmorelifelikeandcomplex,themethodtoreducethecomplicatedlarge-scalevirtualenvironment,speeduptherenderingefficiencyandmaintainthesyst

7、emstabilityisthekeyto3-Ddisplaysystem.Thehigh-performanceviewfrustumcullingalgorithmplaysthevitalroleonimprovingthecollisiondetectionefficiencyandenhancingtherealismandimmersionofthevirtualenvironment.Theviewfrustumcullingalgorithmisanimportantandbasicalgorithmincomputergra

8、phics.Inthispaper,afterhavingsummarizedallkindsoftypicalalgorithms,analyzedtheirad