动机
画家先画远处,再把近处盖上去。对不透明图形,渲染器也可以按这个顺序写入像素:最后留下的颜色来自最近的表面。然而,给每个多边形只算一个中心深度,未必能为整幅图排出正确的顺序。两个倾斜的表面在画面的不同位置可能交换前后。二叉空间划分(BSP)的办法是先用平面切开跨越它的多边形,再按观察点的位置遍历这些碎片。
这里研究的是物体空间中的可见性算法,并不是说所有图形管线都使用 BSP。假设场景由有限个平面凸多边形组成,运算精确,观察点固定;射线参数越小表示越近。表面不透明,所讨论的采样射线有唯一的最近交点。重合情形和浮点误差需要另行约定。
平面如何划分问题
设分割平面为 ,其中 。正、负开半空间分别满足 与 。按凸多边形各顶点的符号分类;若多边形跨越平面,就把它裁成两个闭凸多边形,它们在平面上共用边界。跨越边从 到 的交点为
这是因为 。两个端点严格异号,保证 。已经落在平面上的顶点和整条位于平面内的边,需要统一的去重与归属规则;分母为零时不能使用这个交点公式。若顶点属性在原多边形上是仿射变化的,也要用同一个边参数去插值。
定义 2.7.1
(有限多边形 BSP)
在每个节点,选取某个尚未处理的多边形碎片所在的平面。把所有与该平面共面的碎片存放在该节点;切开跨越该平面的碎片,把不共面的部分分别送入正、负子树。重复直到没有碎片。树是针对场景建立的,之后由观察点决定遍历顺序。
命题 2.7.2
(构造必定终止)
设输入为有限个凸多边形,共有 个互不相同的支撑平面。在每条从根到叶的路径上,各节点的平面都是输入多边形互不相同的支撑平面,所以每条路径至多有 个节点,树是有限的。这里不声称树是平衡的,也不给出碎片个数的上界。
证明
(每个节点用掉自己的支撑平面)
用平面切割只是把多边形换成它自己的碎片,所以每个碎片都保留着它所属输入多边形的支撑平面。平面为 的节点存放了所有位于 中的碎片,因此送往子树的碎片都不以 为支撑平面。于是一条路径不会两次选用同一个支撑平面,节点数不超过 。每次切割凸多边形只得到两块,所以每个节点只向它的两个子树各送出有限个碎片。每条路径至多 个节点的二叉树是有限的。
这个论证并不保证树平衡,也不保证碎片很少:平面选得不好,可能造成大量切割。
遍历为什么正确
定义 2.7.3
(由远到近遍历)
设观察点 不在任何节点平面上。遍历平面为 的节点时,先访问位于平面中与 相异一侧的子树,再绘制存放在该节点的碎片,最后访问与 同侧的子树。每个子树按同一规则遍历。
定理 2.7.4
(每条射线上的由远到近顺序)
假设观察点 既不在任何节点平面上,也不在任何表面上。对从 出发的射线,按遍历顺序列出它与各碎片的交点,沿射线的距离不增,重合的交点除外。因此,按此顺序用不透明颜色依次覆盖时,每个有唯一最近交点的采样点最终保留的是最近交点的颜色。
证明
(一个平面把射线分成三个有序的区块)
设 ,射线为 ,。因为 是 的仿射函数,射线只有穿过平面之后才可能进入负半空间;位于正半空间的交点则出现在穿过平面之前。若射线始终不穿过平面,它就不会到达负半空间或该平面。因此在这条射线上,远侧子树的交点都在节点平面的交点之后,而节点平面的交点又在近侧子树的交点之后。当 时把正负号互换即可。对有限树作归纳:每个子树内部已经按由远到近排好,三个区块连接起来仍保持这个顺序。唯一的最近交点最后写入,所以不透明覆盖得到的就是它的颜色。
证明透视
遍历证明中各项假设的作用
条件 只用一次:它决定哪个子树是远侧,也是唯一需要严格分侧的地方。关键的一步是 关于 是仿射的。沿射线最多变号一次,意味着远侧子树、节点平面、近侧子树这三个区块占据射线参数上互不相交且有先后的区间,于是根本不需要比较距离。对树的归纳使论证闭合:每个子树都是更小的树,具有同样的性质,它的交点区块整个落在自己的区间之内。唯一最近交点的假设只在最后一句用到,用来把最后一次覆盖解读为可见表面。证明里没有用到任意两点之间的欧氏距离、树是否平衡,也没有用到碎片的形状。
这个结论比较的是同一条射线上的点,并不是说异侧半空间里的任意一点都比同侧任意一点更远。投影互不相交的两个碎片,可以按任一顺序绘制。存放在节点中的碎片是共面的;若它们在同一点重叠,图像中就出现深度相等的并列,需要另定规则。
如果观察点恰好在某个分割平面上,严格分侧的规则就没有定义。不包含于该平面的射线会立刻进入某一侧,并且与该平面上的节点碎片在正距离处没有交点;整条射线位于该平面内的情形则属于另一种退化。实现时必须明确选定并记录一种并列约定,或者改变观察点,而不能除以零,也不能假装观察点处在严格的某一侧。
概念视角算法
由正负号驱动的树遍历
遍历就是对二叉树做中序走访,节点上唯一的判断是 的正负,每个节点只根据观察点算一次,正负号决定先进入哪个子树。整个绘制顺序最多只需每个节点一次符号判断,不涉及射线、像素或深度比较,而且与定理中逐条射线的顺序是同一个对象。
例题
例题 2.7.5
(切割与改变观察点)
在 平面中,用直线 类比三维的分割平面。线段从 到 ,交点参数 ,所以 。把 到 一段放入负子树,把 到 一段放入正子树。
取观察点 ,再看三维射线 ,设三个小平面片分别在 处与它相交,位于中间的那一片存放在节点中。它们的参数依次为 ,于是按“访问负子树、绘制节点、访问正子树”的顺序, 处的颜色最后写入。上面被切开的线段不一定与这条射线相交:遍历只对实际出现的交点排序,并不保证每个碎片都会被击中。观察点移到负侧后,两个子树的访问顺序互换,而树本身无需重建。
平面的符号说明物体位于分割面的哪一侧;射线参数只对这条射线上实际遇到的交点排序。分清这两个概念,才能正确理解证明。
例题 2.7.6
(同一棵树,两个观察点)
在平面上计算,用线段代替多边形。令 是 、 的线段, 从 到 , 是 、 的线段。根节点存放 ,取 。对 ,,,所以 ,。从 到 的一段放入负子树;从 到 的一段以及整条 (其上 )放入正子树。
观察点为 时,,所以顺序是负子树、、正子树。沿 朝 减小的方向发出的射线,在 处与 相交,在 处与 相交,并且碰不到 的两段(它们的 )。遍历先访问负子树(没有交点),再到 (),最后访问正子树里的 ():参数不增。观察点为 时,,先访问正子树。同一条直线在 处与 相交,在 处与 相交,依然是不增的顺序,而树完全相同。
例题 2.7.7
(观察点在分割平面上(边界情形))
沿用上例的 和 ,把观察点放在 ,则 ,严格分侧的规则得不出结论。射线 立刻进入正半空间。它只在 处与直线 相交,而该点不在 上(因为 ),并在 处与 相交,交点为 。对这条射线,两种子树顺序给出相同的图像,因为节点中没有任何碎片能在正距离处被击中。射线 则整条位于该平面内:它沿整个区间 与 相交,不存在唯一的最近交点。这种恰好侧视的情形需要明确的约定,例如丢弃恰好侧视的多边形,或改变观察点。
画家顺序的局限
设两个表面在同一投影区间 上的深度函数为 与 ,深度较小者较近。在 处 较近,在 处 较近。无论怎样排列这两个完整的多边形,都不能同时在两个采样点上得到正确结果。可以沿交线 切开,再对碎片局部排序;交线上仍需处理深度相等的情形。两个中心深度相同,也无助于解决这一分歧。
反例模式
按中心深度对整个多边形排序
命题:把整个多边形按中心深度从大到小绘制,每个采样点必定留下最近的表面。上面两个多边形的中心深度都是 ,所以两种顺序都是合法的排序。若先画 、最后画 ,采样点 显示的是 ,但 ,实际上 更近。若先画 ,采样点 显示的是 ,但 ,实际上 更近。在交线 处把两个多边形都切开就能修正: 在 时更近, 在 时更近,每一对碎片都有合法的局部顺序。
定理依赖于不透明覆盖。透明表面通常都要贡献颜色,需要合适的合成规则,而不是只保留最后一次写入。光栅化还需要一致的裁剪和边界归属规则,才能避免裂缝或重复覆盖。精确的几何顺序本身并不能证明浮点实现是稳健的;曲面或运动的几何体也需要更新表示和树。
常见错误
常见错误
(把遍历顺序当作所有点的距离顺序)
取平面 和观察点 。点 位于远侧的负半空间,距离为 ;点 位于近侧的正半空间,距离为 。因此远侧半空间里可以有比近侧某点近得多的点。定理只对同一条射线上的交点排序。
常见错误
(对位于平面内的边使用交点公式)
对平面 和从 到 的边,,所以 ,求 的公式会除以零。应当先对顶点分类:两个端点都在平面上的边属于该节点的共面集合,不必切割;只有一个端点在平面上的边,只在该端点处与平面相交。
练习与解答
快速检查
(设 。切割从 到 的边。交点在哪里?哪一部分位于负侧?)
先算 和 。
解答 · 答案
,,所以 ,。从 到 (不含 )的点符号为负, 在平面上,其余的开线段符号为正。
快速检查
(若 ,三个遍历区块如何排列?解释穿过平面的射线。)
这时哪一侧是远侧?
解答 · 答案
先访问正子树,再绘制节点,最后访问负子树。射线从负侧出发,正侧的交点只能出现在穿过平面之后,所以比平面上的交点以及穿过之前的负侧交点都更远。这是沿射线的由远到近顺序,并不是对空间中任意两点的距离比较。
快速检查
(两个不透明碎片与同一条射线相交,参数分别为 和 。若按中心深度排序得到先画 再画 ,结果为什么是错的?)
哪个碎片最后写入?
解答 · 答案
参数为 的颜色覆盖了参数为 的颜色,留下的是较远的颜色。正确的画家顺序应先画 、后画 。深度缓冲区则可以在采样点处比较深度,但它也需要自己的清除值和深度相等时的规则。
快速检查
(节点中的两个共面多边形在同一射线距离处重叠,定理能选出唯一的颜色吗?)
检查唯一最近交点的假设。
解答 · 答案
不能。两个交点深度相等,唯一最近交点的假设不成立。必须规定并列时的规则,或调整场景的表示;交换子树的访问顺序也无法区分这两个节点碎片。