线段可以穿过视景边界
一个顶点位于视景体之外,并不意味着整条线段不可见。线段可能穿入视景体,再从另一个平面离开。我们可以在除以齐次坐标之前,通过求参数区间的交集精确找出保留部分。本篇在精确算术下研究线段。
使用列向量形式的裁剪坐标 ,并采用对称约定
其他图形 API 或深度约定可能使用不同的近平面不等式。下面的方法适用于任何明确给定的线性裁剪空间不等式集合。此约定与现有相机笔记一致,并不是说每个管线都相同。
定义 7.1.1
(裁剪空间中的线段裁剪)
输入是一对裁剪坐标 ,由同一个线性变换作用于原始端点得到,并保留它们实际的尺度。原始仿射参数为 ,而
六个裁剪函数为 ;裁剪体是这六个函数同时非负的点集。输出是集合 ;当 时,还有裁剪后的端点 与 。
若单独改变一个端点的尺度,这个参数化就会改变。若属性沿原线段按仿射方式变化,新端点的属性值必须使用同一个原始 。
每个平面给出一个区间
把六个不等式写成 ,其中 是六个裁剪函数之一。对某一平面,令 、。由 的线性性,
若两个值都非负,整段线段都满足该平面;若两个值都为负,原线段上没有点满足它。其余情形的边界参数为
当 时,保留 ;当 时,保留 。这两种穿越情形下分母都不为零。先把保留区间设为 ,再与每个平面允许的区间求交;若下界大于上界则拒绝。若两界相等,仍留下一个边界点;如何把它作为图元绘制需要另行约定。
定理 7.1.2
(区间裁剪的精确性)
对六个裁剪函数中的每个 ,令 ,并记 、。则:
- 若 且 ,则 ;
- 若 且 ,则 ;
- 若 ,则 ;若 ,则 ,其中 。
因此,位于裁剪体内的点的参数集合为 ,它是闭区间 (下界取各下界的最大值,上界取各上界的最小值),或者为空集。
证明
(每个平面给出闭区间,裁剪体对应它们的交集)
函数 是 的仿射函数。
若 ,则在 上 。若 ,则 是两个负数的凸组合,因而为负,所以 。
若 ,则 ,所以 严格递增,并且恰在一点 处取零。因为 ,所以 ;又 等价于 ,所以 。由严格单调性,,即 。若 ,则 严格递减,,且 ,即 。
点 位于裁剪体内,当且仅当六个不等式都成立,也就是 同时属于六个集合 。每个 是闭区间或空集,闭区间的交集仍是闭区间或空集;其下端是各下端的最大值,上端是各上端的最小值。
证明透视
区间论证中各个假设在哪里起作用
关键一步,是把一个几何问题(线段的哪一部分位于多面体内)换成六个单变量的符号问题。这个替换之所以合法,全靠 是仿射函数。有两个假设支撑它。第一, 是 的仿射函数,是因为端点取的是保留了实际尺度的裁剪坐标;若单独改变一个端点的尺度,被裁剪的曲线就变了。第二,每个裁剪函数对 是线性的,所以与 复合后仍是仿射函数。一元仿射函数是单调的,因此符号至多改变一次,其非负集合是单个区间。
论证能够收尾,是因为保留的集合是闭集,并且只取交集、不取并集:一个点必须通过每个平面才算在内。不等式不取严格形式,才使每个集合是闭的,下界与上界才属于区间。若不等式改为严格,同一论证只会得到半开区间,边界点就被丢掉了。
若条件是非线性的,论证就不成立。透视除法之后,条件 对 不再是仿射的;下面的反例展示会出什么问题。
齐次坐标不同的穿越例子
例题 7.1.3
( 变化时从左平面进入)
取 、。对左平面 ,端点值为 、,所以线段在 处进入。此时
其余五个不等式在 上全部成立: 在 处为 、在 处为 ,而 与 都等于 。因此保留区间是 。若某个沿原线段仿射变化的标量属性在两端分别为 和 ,新端点的属性值就是 。
反例模式
先做除法,再沿用同一个参数
一个诱人的说法:先投影两个端点,再用同一个 插值屏幕坐标。对上面的线段,两端的屏幕 坐标为 和 。在 处,这个做法得到 。但裁剪空间中 处的真实点是 ,其屏幕坐标为 ,恰好落在左边界上。由于 ,这个做法把新端点放错了位置。
当 变化时,透视除法对原参数不是仿射运算。应先裁剪齐次线段。投影之后,对指定为沿原表面参数仿射变化的属性使用透视校正插值;平坦属性或屏幕线性属性则按各自声明的插值规则处理。
概念视角代数
屏幕参数是 t 的分式线性函数
沿线段,屏幕点的参数为 ,即投影后的线段已走过的比例,其中 。因此除非 , 的等距步长在屏幕上并不等距。取 、, 得 ,屏幕坐标 恰好落在左边界,与裁剪空间的计算一致。把 当作 来用,正是反例所驳斥的做法。
例题 7.1.4
(两个端点都在外面,线段仍有一部分可见)
取 、,所以 恒为 。两个端点都违反某个平面,但线段的中段在内。对 :、,所以 ,允许集合为 。对 :、,所以 ,允许集合为 。 与 方向的四个平面给出 ,不产生限制。
保留区间为 ,裁剪后的端点是 与 。若某个属性沿原线段仿射变化,两端值为 和 ,则在这两点的值分别为 与 。
例题 7.1.5
(交集为空而被拒绝)
取 、。逐个平面来看: 有 、,所以 ,允许集合为 。平面 有 、,所以 ,允许集合为 。其余四个函数在两个端点处都非负: 取值 和 , 取值 和 ,。
交集 为空,所以线段被拒绝。这个判断是精确的:在 (即 )处,点的 ,线段从正方形的角外面经过。注意没有任何单个平面使两个端点同时为负;是交集为空才检测出线段没有碰到视景体。
边界与表示的检查
平面经过端点时,不应直接使用可能分母为零的穿越公式:先判断符号情形。若平面值均为零,整条线段都在平面上;若一个为零而另一个为负,与该半空间的交集可能只有端点。合并多个平面后,若当前下界大于上界,即使没有单个原端点违反所有平面,也必须拒绝。
六个不等式蕴含 。当 时,它们还迫使 ;这是没有射影像的零齐次向量。保留下来的零向量不能除以 ;实际管线需要对此退化输入制定规则,或使用保证 为正的适当裁剪范围。若只因一个保留端点奇异就丢掉整条线段,也可能丢掉其他点。数值容差、有限精度和边界归属规则须另行指定,不能由精确推导直接得到。
常见错误
(两端违反不同平面,不能就此作出判断)
两个端点对同一个平面都为负时,可以拒绝线段。反过来并不成立:在上面的拒绝例子中,两个端点违反不同的平面( 违反 , 违反 ),没有任何平面使两端同时为负,线段却没有碰到裁剪体。相反,两个端点各自违反某个平面,也不意味着必须拒绝,从 到 的线段就是例子。只有六个区间的交集才能作出判断。
常见错误
(第一次裁剪后重新开始计参数)
若逐个平面裁剪,第二次裁剪是在由 到 的缩短线段上进行的,带有新的参数 。属性仍须按原始参数插值,即 ;直接使用 会得到错误的值。在第一个例子中,裁剪到 后,缩短线段上 处的点是 ,所以属性值对应 ,而不是 。
练习与解答
快速检查
(对某平面,、。保留哪个区间?)
先判断哪个端点在允许的一侧。
解答 · 答案
此时 ,所以 ,保留区间为 。
快速检查
(若 ,线段上有点能通过该平面吗?)
把 用 与 表示。
解答 · 答案
没有。仿射值 对每个 都等于 ,所以允许集合为空。
快速检查
(在第一个例子中,若两端属性为 和 ,求新端点的属性值。)
使用原始参数 。
解答 · 答案
。
快速检查
(若保留区间的上下界都为 ,数学上的交集是否为空?)
与下界大于上界的情形比较。
解答 · 答案
不为空;它是一个边界点。它是否绘制出样本由另行约定决定。
关于裁剪空间管线及 API 的具体细节,可参阅 Khronos 的 OpenGL 4.6 Core Profile 规范第 13.7 节。本文推导的是明确给定的对称视景体线段模型,并不表示每个 API 都采用相同的深度约定。