加速三维场景的真实感绘制一直是计算机图形学中的研究热点。其中，光线跟踪是真实感绘制的重要方法之一，它能精确地模拟再现场景，产生高度真实的绘制结果。但是，这种方法的计算量巨大，妨碍了它的绘制速度，难以进行实时绘制。因此，光线跟踪加速算法一直是计算机图形学中的重要研究内容。因为这方面的工作涉及大量的基本几何运算，本文旨在探索相关的基础几何运算的高效实现，并由此发展先进的光线跟踪技术，以提高三维场景的绘制速度。本文对点在多边形/多面体内的判定计算、任意多边形的线裁剪、多面体的凸剖分等基本几何运算进行了深入研究，并发展了若于创新技术;提出了新颖的空间组织技术，极大地提高了光线跟踪计算的速度，能交互地对大规模动态场景进行高度真实感的绘制。　　 本文的主要贡献和创新点如下：　　 ●提出两种多边形点包容性的高效判定算法，即基于边层的判定算法和基于凸剖分的判定算法。前者通过将多边形的边划分为一些边层来进行加速。其空间复杂度为O(n)，预处理时间复杂度介于O(n)和O(n2)之间，判定时间复杂度介于O(logn)和O(n)之间，但在大多数情况下小于O((logn)2)。后者的加速则基于将多边形剖分为一些凸多边形。其期望预处理时间复杂度为O(nlogn)，空间开销为O(n)，判定时间复杂度为O(logn)，与现有的先进算法(如梯形法)相当。但由于该算法需要处理的对象(凸多边形)个数较少，因此它能比其它先进算法更快。此外，这两种算法均无需处理奇异情况，优于许多常用算法。　　 ●提出一种基于层次的多面体表示方法，并以其为基础给出了一种解决多面体点包容性问题的有效方法，即对多面体的面和边进行顺序组织，从而可以用二分查找法加速点的包容性检测。由于许多几何信息被隐含表示，因此该算法的空间需求大大小于传统表示法。其预处理时间介于O(n)与O(n2)之间;其判定时间复杂度在O(n)至O(logn)之间变化，且在大多数情况下小于O(log3n)。当它与组织多面体面片的八叉树结构结合后，其判定速度与目前最快的基于BSP的点包容性判定算法相若，但能显著降低预处理时间和空间需求，特别适合处理大模型。　　 ●提出两种多边形窗口线裁剪算法，一种是通过将多边形剖分成一些凸多边形进行加速，另一种则是通过将多边形的边分解为凸片段进行加速。两者的裁剪计算复杂度均在O(logn)和O(n)之间自适应变化，并在大多数情况下小于O(n)。它们非常适合对同一复杂多边形窗口进行多次裁剪的应用。实验表明，在某些情况下，如多边形对多边形的裁剪，新方法的总执行速度(包括预处理时间和裁剪时间)依然要比已有的不要预处理的裁剪算法快很多。　　 ●提出一种多面体凸剖分新算法，它利用多面体各个元素(点、边、面)之间的遮挡关系将多面体分割成一些单层多面体，然后再对各个单层多面体进行凸剖分。对于实践中的常用模型，新方法的时间复杂度、空间复杂度、剖分结果凸多面体个数皆近似为O(n)，其新增加顶点数的复杂度近似为O(r+n1/2)，其中n为多面体的点数，r为多面体凹边个数。由于该方法对凹边数量不敏感且易于处理多种非流形情况，因此在处理复杂多面体时具有很高的效率，优于目前国际上的类似工作。　　 ●提出了一项光线跟踪新方法，能有效提高光线在空白区域的行进速度。该方法首先用一种新方法创建网格，然后用较少的空盒自适应聚集空网格单元，以加快光线跟踪的计算。新加速结构的创建时间复杂度和空间复杂度均是O(n)，而在光线跟踪计算时的时间复杂度为O(logn)，与kd树结构相当。当它与已有的一些加速结构相结合后，能极大地提高光线跟踪计算速度，很好地处理大规模动态场景。