计算机图形学中若干基本问题及光线跟踪技术的研究
文献类型：学位论文
| 作者 | 李静 |
| 学位类别 | 博士 |
| 答辩日期 | 2007-06-08 |
| 授予单位 | 中国科学院软件研究所 |
| 授予地点 | 软件研究所 |
| 关键词 | 光线跟踪 加速 凸剖分 包容性检测 裁剪 点 多边形 多面体 |
| 其他题名 | Research on Several Fundamental Problems in Computer Graphics and Ray Tracing Techniques |
| 中文摘要 | 加速三维场景的真实感绘制一直是计算机图形学中的研究热点。其中，光线跟踪是真实感绘制的重要方法之一，它能精确地模拟再现场景，产生高度真实的绘制结果。但是，这种方法的计算量巨大，妨碍了它的绘制速度，难以进行实时绘制。因此，光线跟踪加速算法一直是计算机图形学中的重要研究内容。因为这方面的工作涉及大量的基本几何运算，本文旨在探索相关的基础几何运算的高效实现，并由此发展先进的光线跟踪技术，以提高三维场景的绘制速度。本文对点在多边形/多面体内的判定计算、任意多边形的线裁剪、多面体的凸剖分等基本几何运算进行了深入研究，并发展了若干创新技术；提出了新颖的空间组织技术，极大地提高了光线跟踪计算的速度，能交互地对大规模动态场景进行高度真实感的绘制。 本文的主要贡献和创新点如下： （1）提出两种多边形点包容性的高效判定算法，即基于边层的判定算法和基于凸剖分的判定算法。前者通过将多边形的边划分为一些边层来进行加速。其空间复杂度为O(n)，预处理时间复杂度介于O(n)和O(n2)之间，判定时间复杂度介于O(log n)和O(n)之间，但在大多数情况下小于O((log n)2)。后者的加速则基于将多边形剖分为一些凸多边形。其期望预处理时间复杂度为O(n log n)，空间开销为O(n)，判定时间复杂度为O(log n)，与现有的先进算法（如梯形法）相当。但由于该算法需要处理的对象（凸多边形）个数较少，因此它能比其它先进算法更快。此外，这两种算法均无需处理奇异情况，优于许多常用算法。 （2）提出一种基于层次的多面体表示方法，并以其为基础给出了一种解决多面体点包容性问题的有效方法，即对多面体的面和边进行顺序组织，从而可以用二分查找法加速点的包容性检测。由于许多几何信息被隐含表示，因此该算法的空间需求大大小于传统表示法。其预处理时间介于O(n)与O(n2)之间；其判定时间复杂度在O(n)至O(log n) 之间变化，且 在大多数情况下小于O(（log n）3)。当它与组织多面体面片的八叉树结构结合。后，其判定速度与目前最快的基于BSP的点包容性判定算法相若，但能显著降低预处理时间和空间需求，特别适合处理大模型。 （3）提出两种多边形窗口线裁剪算法，一种是通过将多边形剖分成一些凸多边形进行加速，另一种则是通过将多边形的边分解为凸片段进行加速。两者的裁剪计算复杂度均在O(log n)和O(n)之间自适应变化，并在大多数情况下小于O(n)。它们非常适合对同一复杂多边形窗口进行多次裁剪的应用。实验表明，在某些情况下，如多边形对多边形的裁剪，新方法的总执行速度（包括预处理时间和裁剪时间）依然要比已有的不要预处理的裁剪算法快很多。 （4）提出一种多面体凸剖分新算法，它利用多面体各个元素（点、边、面）之间的遮挡关系将多面体分割成一些单层多面体，然后再对各个单层多面体进行凸剖分。对于实践中的常用模型，新方法的时间复杂度、空间复杂度、剖分结果凸多面体个数皆近似为O(n)，其新增加顶点数的复杂度近似 为O(r + n1/2)，其中n为多面体的点数，r为多面体凹边个数。由于该方法对凹边数量不敏感且易于处理多种非流形情况，因此在处理复杂多面体时具有很高的效率，优于目前国际上的类似工作。 （5）提出了一项光线跟踪新方法，能有效提高光线在空白区域的行进速度。该方法首先用一种新方法创建网格，然后用较少的空盒自适应聚集空网格单元，以加快光线跟踪的计算。新加速结构的创建时间复杂度和空间复杂度均是O(n)，而在光线跟踪计算时的时间复杂度为O(log n)，与kd 树结构相当。当它与已有的一些加速结构相结合后，能极大地提高光线跟踪计算速度，很好地处理大规模动态场景。 |
| 语种 | 中文 |
| 公开日期 | 2011-03-17 |
| 页码 | 159 |
| 源URL | [http://ir.iscas.ac.cn/handle/311060/6796]  |
| 专题 | 软件研究所_中科院软件所_中科院软件所 |
| 推荐引用方式 GB/T 7714 | 李静. 计算机图形学中若干基本问题及光线跟踪技术的研究[D]. 软件研究所. 中国科学院软件研究所. 2007. |
入库方式： OAI收割
来源：软件研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。