韶关市建设局官方网站,濮阳市做网站,永久短链接,上海画册设计1.前言 前文说了Whitted-style光线追踪技术的原理以及光线与平面的交点计算方式#xff0c;对于现在应用最广的Polygon Mesh显式曲面来说#xff0c;一个复杂场景中的多边形面总数可能达到千万甚至亿万以上#xff0c;如果每个像素发射光线都和场景中每个平面进行求交点计算…1.前言 前文说了Whitted-style光线追踪技术的原理以及光线与平面的交点计算方式对于现在应用最广的Polygon Mesh显式曲面来说一个复杂场景中的多边形面总数可能达到千万甚至亿万以上如果每个像素发射光线都和场景中每个平面进行求交点计算那么会进行像素数量 x 光线弹射次数 x 多边形平面数量次光线与平面交点计算计算会非常庞大非常慢。 例如下图中的经典场景San Miguel面数达到10.7M渲染一张1080P图片光线平均3次弹射共需要进行66万亿次交点计算。 这样庞大的计算量是完全不能接受的而一条光线在场景中弹射时和绝大多数平面是不会相交的因此需要通过一些算法进行优化这个算法就是包围盒技术(Bounding Box)。
2.轴对齐包围盒(Axis-Aligned Bounding Box) 用简单的方盒子称为包围盒Bounding Box将物体完全包裹如果光线与包围盒没有交点那显然不会与物体中任何三角面有交点那也就没必要去遍历物体的三角面了。 在几种包围盒方式中AABB即轴对齐包围盒因为包围盒三组对面分别与三个空间坐标轴平行便于计算而使用最为广泛下图中间。 那么AABB包围盒就可以理解为三个不同的对面形成的交集这样可以方便进行光线与包围盒的求交运算。如下图所示。 那么到底如何求光线与包围盒的交点呢先将问题简化成直线与、两对平面的交点将三维转化成二维。 如上图最左边所示求光线与一对 x 平面(左右无限远)的交点将先进入的交点(距离光线起点 o 最近的那个)记为 tmin后出去的交点记为 tmax。紧接着如中间图所示计算出光线与 y 平面(上下无限远)的两个交点同样记为另外一组 tmin, tmax。注意如果任意的 t 0那么这代表的是光线反向传播与对应平面的交点。 那么如何知道光线在什么时候进入盒子又在什么时候出去了盒子呢 对于二维来说如上图最右边所示在 tmin 时间进入了盒子在 tmax 时间出去了盒子。这实际就是求两组交点构成的线段的交集。那么这个结论是怎么得出的呢 回想三维的情况三维的盒子就是三个对面最重要的核心思想 1.只有当光线进入了所有的平面才算是真正进入了盒子中。 2.只要当光线离开了任意平面就算是真正离开了盒子。 那么就可以得到一种算法在三维中三组不同的对面各计算一次进入对面的最小时间 tmin 和离开对面最大时间 tmax 时间不管是正还是负。最后算出三对进入和离开对面的时间交集就得出了进入盒子时间 和离开盒子时间 。如下图所示。 但光线不一定会与包围盒有交点那么什么条件下才会有交点呢 如果 的时候说明光线所在直线一定在盒子中待过一段时间也必然存在交点。但光线并不是直线而是射线除了保证 (光线在盒子待过一段时间)还要考虑时间 t 是否为负保证物理正确性。具体如下 1.如果 0说明包围盒在光线背后就不会有交点。 2.如果 0 并且 0说明光线是从包围盒内发射出来的就有一个交点。 3.如果 0 并且 0说明包围盒在光线前面有两个交点。 因此只要满足 并且 0 光线就一定和包围盒有交点。 根据前文中光线与平面的交点算法光线和包围盒的求交也很容易写出如下图下半部分所示。 以一对 x 轴的平面为例两个平面肯定垂直于 x 轴因此可以直接求光线在 x 轴方向的分量代入公式从而直接得到 t 值计算过程比光线与任意平面交点的算法要快速得多这也是AABB包围盒得到广泛使用的原因。
3.使用AABB加速光线追踪
3.1 AABB划分方法 虽然对场景中的每个物体使用AABB包围盒技术已经可以大幅加快光线追踪效率但实际使用中难免遇到以下两种极端情况
整个场景主要只有一个极其复杂的单一模型那么只对这一个物体做包围盒的话相当于对效率没有提升。整个场景充斥着大量的细小模型如植物、建筑之类的每个模型可能只有很少的面如果此时对每个物体求包围盒得到的包围盒数量会非常多效率提升有限。 基于以上两点考虑AABB不应只局限于以物体模型为单位可以更加精细的划分成以一定数量的三角面为单位并且对于场景的许许多多包围盒来说应该要有一种数据结构将其统一起来。 因此为了更好地划分场景形成不同的AABB使得划分之后的AABB能够更好的加速光线追踪在AABB的基础上出现了多种划分方法。
3.2 均匀网格划分(Uniform Grids Partitions)
3.2.1 步骤和定义 先从最简单的均匀网格划分开始。步骤如下。 1.创建一个包裹整个场景的大包围盒。如下图所示。 2.在大包围盒中创建均匀分布的网格。如下图所示。 3.将每个物体对象存储在重叠的单元格中。判定哪些小方格有物体信息也就是与物体表面相交的小方格。注意下图中右上角没涂对。 以上就是在光线追踪之前进行了预处理然后就可以进行光线追踪了。在光线追踪计算时根据光线的方向找到所有相交的小方格倘若小方格中存储有物体再进一步与方格中的物体模型或是三角形面求交(假设光线与小方格求交是很快的与物体求交比较慢)。如下图所示。 均匀网格划分将空间划分为多个均匀的小的AABB再根据光线方向找出相交的小方格(这一步并不需要判断所有方格可以用类似brenham的方法来做)再判断小包围盒中是否存储了模型信息若有则进一步求交。
3.2.2 网格分辨率影响 这种划分方法假设了找出相交方格要比直接判断与物体求交相对容易因此划分方格数的数量也是影响性能的关键方格太少就没有加速效果方格太多则判断与方格的求交可能会拖累效率。如下图所示左侧是方格只有一个没有加速效果而右侧是方格太过密集反而增加了判断影响效率。 所以网格的数量(分辨率)应该有一个平衡不能太稀疏也不能太密集。 所以这种方法最适合的场景就是大型对象集合并且大小在空间中均匀分布。如下图这种场景。 如果场景较为空旷物体较小且相互距离较远那么均匀分割的效果就会很差了因为会有很多无效的方格与光线的求交过程。
3.3 空间划分(Spatial Partitions)
3.3.1 定义 均匀网格划分适合场景中密集且均匀分布那么当场景中存在大量空白区域就不适合了。所以就需要使用空间划分密集的区域用小方格空白区域用大方格。
3.3.2 分类 空间划分主要有Oct-Tree、KD-Tree以及BSP-Tree等划分方法。如下图所示。注意这些划分在2D和3D中都可以使用以下以2D为例。 1.Oct-Tree也就是八叉树每次将空间分为8个相等的部分三维空间横竖平各切一刀因为图中是二维显示所以看起来只划分了4部分再递归的对子空间进行划分。当划分的子空间足够小或是空间中三角形面的数量很少的时候会停止划分。这种方法的显著缺点是随着维度的上升划分的空间数量会呈指数级增长。 2.KD-Tree其每次将空间划分为两部分且划分依次沿着 x 轴y 轴z 轴即如图中所示。第一次横着将二维空间分为上下第二次再竖着将上下两个子空间分别划分为左右部分依次交替划分划分时不是按空间大小而是按模型数量或者三角形数量进行均匀划分终止条件与八叉树类似。 3.BSP-Tree其与KD-Tree类似唯一不同的是划分不再沿着固定一轴可以任意方向划分。缺点自然是划分的空间没有规则性求交比较困难。 同样空间划分也是在光线追踪之前进行预计算。 接下来从一个例子具体介绍KD-Tree。
3.3.3 详解KD-Tree
3.3.3.1 划分过程 1.空间分为左右两部分。如下图所示。 2.对左右两个子空间换个方向再分为两部分(这里为方便展示只画出了右半部分其实左边也是一样)。如下图所示。 3.如此递归的划分下去如下图所示。 3.3.3.2 KD-Tree的数据结构 通过上述划分之后中遵循这样几点。 1 依次沿着x轴y轴z轴划分使得空间被划分的更加平衡。 2 划分的位置由空间中三角面的分布决定具体细节不展开。 3 叶子节点存储对应空间的所有物体或三角面信息中间节点仅存储指针指向两个子空间。 4 当划分空间太小或是子空间内只有少量三角形则停止划分。 当KD-Tree建立完成之后如何进行光线与物体求交判断呢
3.3.3.3 求光线与物体交点 如下图所示假设有一条光线进入场景里面的圆圈代表物体。那么如何去计算光线与物体的交点呢 1.判断光线是否与最外层的包围盒(A)相交。如下图所示。 2.如果相交则进一步判断是否与对应的两个子包围盒相交。 上图是为了显示方便所以左侧没有进行进一步的显示划分情况实际会继续划分下去的所以左半部分对应的 1号空间是叶子节点如果光线与之相交进一步判断与存储与叶子节点的所有物体求交。左半边判断完之后接着判断右半部分显然光线与左右两侧包围盒都相交。 对于左右两侧的所有子包围盒递归的执行这个步骤即可。 更加详细的过程就不再赘述。
3.3.3.4 优缺点 优点 利用KD-Tree的结构来构建AABB的好处是倘若光线与哪一部分空间不相交那么则可以省略该部分空间所有子空间的判断过程在原始的纯粹的AABB之上更进一步提升了加速效率。 缺点 1.判断包围盒与三角面的是否相交较难因此划分的过程不是那么想象的简单。 2.其次同一个三角面可能被不同的包围盒同时占有这两个不同包围盒内的叶节点会同时存储这一个三角形面。 基于KD-Tree的以上两个缺点这种方法渐渐地不再被广泛使用。
3.4 对象划分(Object Partitions)
3.4.1 BVH对象划分 对象划分与前几种方法最显著的区别就是不再以空间作为划分依据而是从对象的角度考虑即三角形面。而这种划分形成的加速结构就称为BVH对象划分(Bounding Volume Hierarchy Object Partitions)。 BVH对象划分得到非常广泛的应用。在现代图形学里无论是实时的光线追踪还是离线的光线追踪几乎都使用了这种方法因为它解决了KD-Tree的两个缺点。 具体划分步骤如下。 1.找出场景的整体包围盒作为根节点。 2.找到合适的划分点将最大包围盒内的三角形面分为两部分再分别重新计算新的包围盒。 注意包围盒会重叠但一个三角形面只会被存储在唯一的包围盒内而这也就解决了KD-Tree的缺点。 3.接下来与KD-Tree的建立类似递归的对所有子空间重复该步骤。 最终可以建立出如上图的所示的树形结构同样为了画图方便只进行了左半部分的划分右半部分其实同理。 划分细节每次划分一般选择最长的那一轴划分假设是x轴那么划分点选择所有三角面的重心坐标在x坐标上的中位数进行划分(快速选择算法找中位数)如此便能保证划分的三角形左右两边三角形数量尽可能差不多。当然也就使得树形结构建立的更加平衡深度更小平均搜索次数更少提高效率。 而与KD-Tree一样中间节点不存储物体三角面信息只在叶节点中存储划分终止条件为当前包围盒内三角形数量足够少(例如5个)。 光线与物体求交点与KD-Tree求交点是一样的如下图伪代码所示。 3.5 空间划分与对象划分的区别 空间划分(如kd -tree) 1.将空间划分为不重叠的区域。 2.一个对象可以包含在多个区域。 对象划分(如BVH) 1.将对象的集合划分为不相交的子集。 2.每个集合的边界框在空间上可能重叠。
