包围体是筛选,不是物体交点
射线追踪器可能要测试很多图元。如果一个包含多个图元的区域被射线错过,便可跳过其中所有图元。包围体层次结构(BVH)把这些保守区域组织成树,目的是避免部分昂贵的图元测试;射线碰到盒子,本身不代表碰到盒内任何图元。
定义 6.1.1
(射线区间与闭轴对齐盒)
射线为 ,其中 且 。我们寻找 的交点,假设 ;上界可为 。轴对齐盒子是闭集合 ,所有界均有限且 。射线可以从盒内出发,碰到面、边或角在此闭盒模型中均算相遇。
相交三组平行板
定义 6.1.2
(单一坐标的平行板区间)
对 的第 个坐标,使 成立的参数 组成区间
最小值及最大值处理 的两种符号。若 ,该坐标永不改变:若 ,则没有任何 满足条件,否则每个 都满足。不要除以零。
定理 6.1.3
(闭盒测试)
若没有零方向坐标排除盒子,便把所有非零方向的 与 相交。射线区间与盒子相遇,当且仅当交集非空;等价地,其最大下端点不大于最小上端点。
证明
(坐标条件与同一个参数)
点 属于 ,当且仅当对 都有 ,而且三个条件在同一个 下成立。
若 ,不等式减去 后除以 ,方向不变,得 。若 ,除以 会使两个不等号反向,得 。两种情况的解集都是 ,较小的商在前;公式中的最小值与最大值自动完成选择。若 ,条件化为 ,与 无关:对所有 成立,或对所有 都不成立。
因此, 给出盒内一点,当且仅当它属于 与所有 的 的交集,并且没有任何零方向条件失败。若有一个失败,就没有 满足,射线错过盒子。最后,有限个闭区间 有公共点,当且仅当 :这样的公共点 对所有 满足 ;反过来, 内的任何 都属于每个区间。
证明透视
各项假设在哪里起作用
这个证明有一个不显眼的要点:三个坐标条件是作为参数的集合相交,而不是作为空间中点的集合相交,因为同一个 必须同时满足全部条件。所以射线可以穿过三个平行板在空间中的区域,却仍然错过盒子:区间 可以互不相交。
的符号只用了一次,就是决定哪个商是进入点、哪个是离开点。若去掉最小值与最大值, 时会得到进入大于离开的区间,被误当成空集。 要单独处理,因为此时商不存在,平行板条件只是对 的是非判断。盒子与区间的闭性用在最后一步:最大下端点等于最小上端点,就是一个公共参数,即边界接触;若盒子是开集,这种相等情形便是错过。界有限且 保证每个非零方向的 是真正的有界区间。
射线计算例子
例题 6.1.4
(平行坐标)
取 ,,其中 。第一组平行板允许 ;其余两个方向为零,起点坐标都在各自区间内。因此盒交区间为 。若第二个起点坐标改为 ,该平行板对所有 都会排除盒子。
例题 6.1.5
(从盒内出发的射线)
对 及 ,第一组平行板允许 。与 相交得到 :进入参数为负,不代表从盒内出发的射线会错过盒子。
例题 6.1.6
(正负混合的方向与擦过棱边)
取 ,,其中 。 平行板给出 。对 ,,两个商为 和 ,取最小值与最大值得 。 方向为零,且 ,没有附加限制。 与 的交集是 ,并非空集:射线在 碰到棱边 ,在闭盒模型中算作相交。
把起点移到 ,则 区间为 ,与 不相交,射线错过盒子。
常见错误
(对每条射线都以下界商作进入点)
对 , 平行板的两个商是 和 。若把 当进入点、 当离开点,便得到看似为空的 ,射线会被误判为错过。正确区间是 :射线在面 进入,在 离开。
常见错误
(把负的进入参数当作错过)
从盒内出发的射线,平行板进入参数为负,如第二个例子。测试会与 相交,把下端点抬高到 ;并不会因为进入参数为负而排除盒子。
反例模式
碰到盒子不代表碰到图元
一个小三角形可以位于大包围盒的一角。射线穿过盒子的另一部分时,会碰到盒子却错过三角形。只有当保证包含该三角形的盒子被排除时,平行板测试才能排除它;否则仍需要真正的三角形相交测试。
安全遍历与最近交点
定义 6.1.7
(保守层次结构)
包围体层次结构是保守的,指每个叶盒包含分配给该叶子的所有图元,每个图元至少出现在一个叶子中,且每个内部盒包含其全部子盒。
从根开始,盒交区间为空时排除节点;在未被排除的叶子测试图元。
命题 6.1.8
(保守剪枝)
设层次结构是保守的,且运算精确。(a) 排除盒交区间为空的节点,不会丢失参数在 内的图元交点。(b) 若已知有效图元交点 ,再排除盒区间下端点严格大于 的节点,不会丢失参数 的图元交点。
证明
(祖先盒在相同参数下包含交点)
设图元 在 被击中,, 是子树中有叶子存放 的任一节点。由保守性,该叶盒包含 ,而每个祖先盒都包含其下的盒,所以 。由闭盒测试, 的盒交区间非空且含 ;因此 (a) 不会排除 ,通往该叶子的所有祖先都会被访问。
对 (b),若 ,则 属于 的盒交区间,其下端点至多为 ,并非严格大于 。因此 同样不会被排除。
保留相等情况,可避免在平局规则重要时悄悄丢掉同距交点。先访问较近的盒子可能更早找到有用上界,但正确性不依赖遍历次序。对允许区间有限的“任何交点”阴影查询,找到区间内有效图元交点后可立即停止;此查询不要求最近交点。
若许多盒子重叠或射线穿过大多数节点,层次结构可能没有成效,最坏情况仍须检查整棵树。命题假设包围盒保守且比较精确;浮点舍入、无效数值、边界约定和稳健图元测试均须明确处理。包围盒若不能保证包含图元,无论树形如何都可能漏掉交点。
练习
快速检查
(第一条例子射线若限制 ,盒交区间是多少?)
把两个区间相交。
解答 · 答案
与 相交得到 。
快速检查
(对 、 且 ,求区间。)
方向为负,取较小的商作进入点。
解答 · 答案
第一坐标在 穿过 、在 穿过 ;其余坐标保持在盒内。区间为 。
快速检查
(节点盒交区间为 ,已知有效交点 。该节点能否包含更近交点?)
比较下端点与 。
解答 · 答案
不能。射线上所有位于该盒的点均有 ,而所有后代交点都在盒内。
快速检查
(为何盒交区间非空不足以报告三角形交点?)
想想三角形占包围盒的多少。
解答 · 答案
三角形可能只占包围盒的一小部分。射线可穿过盒子而不碰到三角形,故仍须测试图元相交。