动机
想象一条黑色边界在白色图像上缓慢移动。只取中心样点的像素,在边界通过中心之前一直是白色,通过之后便突然变黑。几何形状连续地移动,存储值却跳变,原因是测量只在一个点问“在内还是在外”。整数直线或圆的算法可以把这个离散问题规定清楚,却不会改变问题的性质。选中一个附近的中心,不等于量度像素方格有多少面积被覆盖。
要得到不同的答案,首先要提出不同的测量问题。假设像素记录连续图像在一个矩形范围内的平均值。部分被覆盖的像素便会记录由面积决定的混合值。对直线边界,这个面积可以精确计算,不必用一大群测试点逼近。计算过程也会揭示:在什么假设下,单凭覆盖比例就足以决定颜色。
本节为单一直线边界,以及两条平行边界之间的带状区域,建立完整的有限公式。我们采用精确实数运算、各区域内均匀不变的颜色,以及明确选定的方框滤波器。本节不取代组装三角网格时的样点归属规则,也不把面积滤波等同理想的频率截断。一般曲线边界、互相遮挡的可见层,以及空间上变化的着色,都需要另外处理积分。
定义
设 P=[x0,x0+hx]×[y0,y0+hy] 是一个矩形像素的测量范围,其中 hx,hy>0。对有界可积、且每一点均已指定数值的标量图像 I,其归一化方框测量为
IP=hxhy1∫PI(x,y)dxdy.对向量颜色图像,逐分量积分。中心样点则是 I(x0+hx/2,y0+hy/2)。样点是在一个点求值;方框测量是在一个区域取平均。
归一化不可省略:常值为 c 的图像应该输出 c,不随像素大小改变。等价地,测量在 P 内采用权重 1/(hxhy),在外部采用零权重。我们假设这种均匀测量范围就是希望计算的测量,并不宣称它精确描述每一种显示器或相机。这里的“精确滤波”只表示对这个指定滤波器精确积分。
设 S 是可测的前景区域。它在 P 内的覆盖比例为
αP=hxhyarea(S∩P)=hxhy1∫P1S(x,y)dxdy.其中 1S 在 S 内等于一,在外部等于零。假设可见图像在 S 上具有常值的线性光颜色 CF,在补集上具有常值的线性光颜色 CB,便有
I=CB+(CF−CB)1S.在这些假设下,覆盖比例是几何面积比例,不是半透明材质的不透明度。
把最后一式积分,得到
IP=(1−αP)CB+αPCF.
这个恒等式来自积分的线性,并不是说任何着色器输出都可以直接按覆盖比例混合。若颜色在某个区域内变化,积分还必须包含这种变化。若颜色以非线性编码存储,应先解码为线性光数值,再作这个平均,最后重新编码。直接平均已编码的分量值,一般计算的是另一个量。
以下半平面是否包括边界,不影响任何面积结果:非常值仿射函数的等值集是一条直线,而直线的二维面积为零。不过,同一条边界可以通过指定的光栅样点;此时仍须有并列规则。所以样点归属与面积积分可以采用不同的边界记录方式,而不互相矛盾。
单一直线边界的精确有限公式
先考虑单位正方形 Q=[0,1]2 和半平面
Ht={(u,v):au+bv≤t},a,b>0.
记 z+=max(z,0),并定义 Fa,b(t)=area(Q∩Ht)。由于 Q 的面积为一,这个值本身就是比例。改变 t 会平移边界而保持其方向。
对所有实数 t 及正数 a,b,
Fa,b(t)=2abt+2−(t−a)+2−(t−b)+2+(t−a−b)+2.特别地,t≤0 时 Fa,b(t)=0;t≥a+b 时 Fa,b(t)=1。在两者之间,它是介于零与一的连续分段二次函数。
设 X=au、Y=bv。单位正方形变成 R=[0,a]×[0,b],面积乘以 ab。在非负象限中,区域 X+Y≤t 当 t≤0 时没有正面积;否则是一个两条直角边均长 t 的直角三角形,其面积为 t+2/2。
要只保留它在 R 内的部分,先扣去 X>a 的部分,以及 Y>b 的部分。对第一部分,平移 X′=X−a,得到非负坐标及 X′+Y≤t−a,所以面积为 (t−a)+2/2。第二部分同样具有面积 (t−b)+2/2。同时满足两个条件的部分被扣了两次,必须加回。把两个坐标都平移后,这个重叠部分的面积为 (t−a−b)+2/2。边界面积为零,因此扣除过程中的严格不等式不改变结果。除以 ab 便证得公式。
当 t≤0,正方形内的交集面积为零;当 t≥a+b,正方形内每一点都满足不等式。面积意义直接给出中间值的上下界;连续性和分段二次形式也可直接从有限公式看出。这个公式并不代表一个无限次采样的极限程序。□
证明透视
四个三角形:各个正负号从何而来
四项来自移除两个坐标上界,再把它们的重叠补回。平移后若门槛为负,相应三角形并不存在,所以该项为零。分母各有作用:因子二来自直角三角形面积,ab 则把伸缩后的矩形换回单位正方形。只有在 t≤a+b 时,省去重叠项才不影响答案;超过这个区间便会错误地少算面积。直接实现可以在两个外部情况先返回零或一。证明采用精确运算,没有为四项式的浮点相消误差提供界限。
对角线 u+v≤t 的公式尤其容易阅读:
F1,1(t)=⎩⎨⎧0,t2/2,1−(2−t)2/2,1,t≤0,0≤t≤1,1≤t≤2,t≥2.
第一段内部公式是角落三角形逐渐长大的面积。直线通过中心后,从一减去逐渐缩小的未覆盖角落,反而较简单。两式在 t=1 相等,此时对角线把正方形分成面积相等的两半。
定理不会除以为零的边界系数,因为它假设两者均为正。若 a=0、b>0,直接对水平带状区域积分:
F0,b(t)=clamp(t/b,0,1),clamp(z,0,1)=min(1,max(0,z)).
若 b=0、a>0,交换坐标即可。若两个系数均为零,不等式是常值条件:t≥0 时覆盖为一,t<0 时为零。最后这种情况没有直线边界,必须在套用直线公式前处理。
在实际像素与单位正方形之间转换
考虑实际坐标中的半平面 Ax+By≤c,其中 (A,B)=(0,0)。代入
x=x0+hxu,y=y0+hyv,
并记
a0=Ahx,b0=Bhy,t0=c−Ax0−By0.
覆盖比例便是单位正方形内 a0u+b0v≤t0 的面积比例。面积雅可比(Jacobian)行列式为 hxhy,恰好与实际像素的归一化因子抵消。所以 a0,b0 包括像素尺寸。系数 A,B 本身只直接对应单位尺寸像素。若两条边具有相同的非单位长度 h,保留 A,B 的同时,也要把 t0 除以 h。
负系数可用反射相应的单位坐标处理。若 a0<0,设 U=1−u,便有
a0u=a0+(−a0)U,
所以把系数换成 −a0,并把门槛换成 t0−a0。若 b0<0,采用相同替换。反射保持面积不变。完成两个可能的反射后,将非负系数记为 a,b,调整后的门槛记为 t,再使用正系数定理或单一零系数公式。对一组平行边界,应对每个门槛施加相同平移,从而保持它们的次序。
例题 2.4.4
(在两个中心判定之间移动的对角边界)
取单位像素 Q,前景为 u+v≤3/4,前景红色 CF=(1,0,0),背景蓝色 CB=(0,0,1);颜色分量均为线性光数值。中心的坐标和为一,位于前景之外,所以只测中心会输出蓝色。真正的方框覆盖比例为
α=F1,1(3/4)=2(3/4)2=329,IQ=(9/32,0,23/32).若边界移到 u+v≤5/4,中心位于前景之内,但覆盖比例仍未达一:
F1,1(5/4)=1−2(3/4)2=3223.两个样点结果为零及一;两个精确面积测量则为 9/32 及 23/32。即使运算完全精确,两种测量仍会得到不同答案。
设 P=[1,3]×[0,1],前景为 x−y≤2。写成 x=1+2u、y=v,不等式成为 2u−v≤1。反射 V=1−v 后,得到
2u+V≤2.因此 a=2、b=1、t=2,且
αP=F2,1(2)=44−0−1+0=43.直接核对:在实际高度 y∈[0,1],被覆盖的水平区间为 [1,2+y],长度为 1+y。其面积是 ∫01(1+y)dy=3/2;除以实际像素面积二,得到 3/4。只反射系数而不调整门槛,计算的会是另一个半平面。
带状区域、稳定性与可见性的作用
零宽度几何直线的面积为零。因此,把每个选中的直线样点涂成完整颜色,并不是对这个集合积分。要以方框滤波描述可见直线,必须指定非零宽度的区域、另一种测量,或两者一起指定。对正数 a,b,定义平行带状区域
Sℓ,r={(u,v):ℓ≤au+bv≤r},ℓ≤r.
由于两条边界直线的面积均为零,它在单位像素内的精确覆盖比例为
α=Fa,b(r)−Fa,b(ℓ).
若恰有一个系数为零,就在同一差式中采用其截断公式;下面的边界移动界限则使用非零系数。这直接来自截断函数的单调性,以及它不会放大差值的性质。
这是两个互相包含的区域相减,并不表示可以任意相减重叠形状的覆盖比例。在单位正方形的欧氏坐标中,两条直线的距离为 (r−ℓ)/a2+b2。因此,门槛区间的长度一般不等于沿边界法线量度的几何宽度。若实际像素的两个尺寸不等,应先在归一化之前,用实际直线法向量 (A,B) 处理所要求的实际宽度。
在 Q 内,取 1/5≤u+v≤3/10。它的法向宽度为 1/(102),精确覆盖比例为
α=2(3/10)2−(1/5)2=401.四个规则子像素中心 (1/4,1/4)、(1/4,3/4)、(3/4,1/4)、(3/4,3/4) 的坐标和为 1/2,1,1,3/2,没有一个在带状区域内,所以等权估计为零。像素中心也会漏掉它。两种估计都不同于正的精确覆盖比例;区域面积很小,并不表示忽略它便是数学上的精确答案。
对正数 a,b 以及所有实数 t,δ,
0≤Fa,b(t)≤1,Fa,b(t)+Fa,b(a+b−t)=1,而且
∣Fa,b(t+δ)−Fa,b(t)∣≤max(a,b)∣δ∣.因此,门槛宽度为 r−ℓ 的带状区域,其覆盖比例不超过 min(1,(r−ℓ)/max(a,b))。
上下界来自面积。反射 (u,v)↦(1−u,1−v) 把 au+bv≤t 变成 au+bv≥a+b−t。除了一条零面积边界外,反射后的区域正是门槛为 a+b−t 的半平面的补集,故得恒等式。
对移动界限,先设 δ≥0 且 a≥b。固定 v 时,原先被覆盖的水平区间长度是 clamp((t−bv)/a,0,1)。把门槛提高 δ 后,这个长度增加的量非负且至多为 δ/a:把两个有序数值截到指定区间内,不会放大它们的差。在 0≤v≤1 上积分便得界限。若 b>a,改用垂直截线;若 δ<0,交换两个门槛。最后在 ℓ 与 r 之间应用这个结果,再结合面积不超过一,便得带状区域的界限。□
对单位对角线,门槛移动 δ 所引致的覆盖变化不超过 ∣δ∣。相反,中心测试在 t=1 时跳变一,即使跨越该门槛的位移任意小。这解释了先滤波对平移边界的一项具体改善,但不证明所有采样动画都不再有时间混叠。
必须先决定要平均的连续图像中哪些部分可见。假设两个不透明物体各覆盖半个像素。若它们覆盖的是互不相交的两半,并集覆盖整个像素;若两半完全重合,并集只覆盖一半。两个场景中,各物体的个别覆盖比例完全相同。所以,单凭覆盖比例无法恢复重叠情况、深度次序或实际可见的子区域。本节的均匀单一前景模型,是通过一开始便指定完整可见图像,避开这个额外问题。
超采样与“理想”滤波器的意思
超采样规则在 P 中选取点 p1,…,pN,并使用权重 wi≥0,满足 i∑wi=1。它以
IP=i=1∑NwiI(pi)
估计平均值。对指示函数图像,估计就是加权计数。在本节均匀颜色模型下,估计覆盖比例为 α=i∑wi1S(pi)。这是指定积分的近似,而不是积分的定义。原生多重采样管线也可能让多个覆盖样点共用着色计算;存在多次覆盖测试,本身并不代表每个着色量都作了多次独立求值。
反例模式
任何固定的有限样点集都可能漏掉细带
固定 Q 内任意有限个样点。它们的坐标和 ui+vi 形成有限数集。因此,在 (0,1) 内必有一个开区间 (ℓ,r),满足 ℓ<r,且不包含任何这些数值。带状区域 ℓ<u+v<r 不包含任何选定样点,面积却是 (r2−ℓ2)/2>0。所以,上述每一个加权点估计均为零,而精确覆盖比例为正。这个细带依赖所选样点集;并不是说有一个固定细带能避开所有可能的采样安排。结论是:对所有这类细特征,不存在普遍精确的有限点采样规则。
增加样点数可以改善近似,但收敛叙述、误差速度及统计保证,需要关于图像与采样规则的假设。例如,均匀而独立的随机位置给出无偏的覆盖估计,因为样点落在 S 内的概率就是面积比例。这仍不会使某一次有限估计变得精确。前面的确定性反例,针对的是在几何形状选定之前已固定的规则。
“理想”一词同样要小心。精确方框平均,只能对明确选定的均匀矩形测量而言称为理想。它不是具有锐利频率截断的理想低通滤波器。不必使用完整傅里叶(Fourier)理论,也能看出差别。把一维振荡 eiωx 在宽度 h>0 的置中区间取平均:
h1∫−h/2h/2eiω(x+s)ds=eiωxωh/2sin(ωh/2),
其中最后因子在 ω=0 时按连续性取一。对 ω=0 直接积分指数函数便得到恒等式;取实部与虚部,便得正弦和余弦的相应结论。这个响应只有离散零点,还有非零旁瓣,并不是在某个截断频率之后处处为零。二维矩形平均的响应是两个坐标响应的乘积,因为积分可以分离。
理想频率截断是另一个数学算子;在一维,其空间折积核与 sinc 函数成正比,具有无限支撑。精确的有限范围覆盖计算没有作出这种频带限制假设。锐利的指示函数边界本身并非带限,而精确方框平均也不会移除所有高频。因此,把方框滤波称作“完美反锯齿”,会把结论延伸到计算假设以外。
常见误解与快速检查
覆盖比例 1/4 表示:在指定几何形状与均匀滤波器下,测量范围的四分之一是前景。它不表示整个像素装有不透明度 1/4 的材质,也不表示任意四个样点中必定恰有一个被覆盖。样点位置改变时,有限样点估计可以改变,而连续面积维持不变。
是否包括直线边界,不影响面积,但可以改变相等情况下的点结果。相反,把半平面边界移到另一个对齐格点的位置,会在一个正面积集合上改变区域,从而可能改变精确覆盖。不要把两种操作混淆。同样,零宽度直线的面积是零;有限宽度描边则需要区域定义,若描绘有限线段,还要规定端帽及接合。本节的带状区域具有无限延伸的平行边,并没有暗中指定端帽模型。
快速检查
(考虑 Q 内的 u+v≤1。它的精确覆盖比例是多少?中心测试能得到这个值吗?)
利用反射 (u,v)↦(1−u,1−v)。
解答 · 答案
反射告诉我们精确比例为 1/2。中心恰在边界上,所以中心测试可按所规定的并列策略返回零或一,两者都不是精确方框平均。不论把边界样点判给哪一区,这个差异仍然存在。
练习
快速检查
(求 Q 内 u+v≤−1/4、u+v≤1/2、u+v≤3/2 及 u+v≤9/4 的精确覆盖比例。对中间两个答案,给出一个几何核对。)
找出每个阈值相对于区间 [0,1] 和 [1,2] 的位置。
解答 · 答案
答案依次为 0、1/8、7/8 及 1。第二个门槛的覆盖角落三角形两条直角边均长 1/2,面积为 1/8。反射把它对应到第三个门槛的未覆盖角落,所以这两个比例之和为一。第一与第四个门槛位于可能坐标和的区间 [0,2] 之外。
快速检查
(计算 Q 内 2u+v≤5/4 的覆盖比例,再通过积分垂直截线长度核对,并指出公式在哪里改变。)
用 F2,1,再用竖直切片积分验证。
解答 · 引导解答
代入公式得到
F2,1(5/4)=4(5/4)2−0−(1/4)2+0=83.固定 u 时,被覆盖的垂直长度为 clamp(5/4−2u,0,1)。在 0≤u≤1/8 上为一,在 1/8≤u≤5/8 上为 5/4−2u,之后为零。所以
α=81+∫1/85/8(5/4−2u)du=81+41=83.
快速检查
(在 P=[−1,1]×[2,3] 中,求 −x+2y≤5 的覆盖比例。写出反射前后的归一化不等式。)
先代入 x=−1+2u 与 y=2+v。
解答 · 答案
代入 x=−1+2u、y=2+v,得到 −2u+2v≤0。反射 U=1−u 后,得到 2U+2v≤2,等价于 U+v≤1。比例为 1/2。原边界通过矩形像素中心 (0,5/2),中心对称交换两侧区域,提供几何核对。
快速检查
(Q 内一个带状区域是 3/4≤u+v≤5/4。求其面积比例及法向宽度,并解释为什么中心在内不足以确立完全覆盖。)
解答 · 答案
覆盖比例为 23/32−9/32=7/16。法向宽度为 (5/4−3/4)/2=1/(22)。中心的坐标和为一,但两个未覆盖角落三角形的面积各为 9/32。一个点在集合内,不表示它周围的整个测量范围都在内。
快速检查
(在 Q 上,设标量图像 I(u,v)=u1{u+v≤1}。计算精确方框平均,与“覆盖比例乘以像素中心的前景值”比较,并指出哪个假设不成立。)
解答 · 引导解答
先对 v 积分:
IQ=∫01∫01−uudvdu=∫01u(1−u)du=61.区域的覆盖比例为 1/2。若把前景设为中心值 1/2,便得 1/4,与精确答案不同。原因是前景强度随空间变化,并非常值。它在前景三角形内的真正平均为 (1/6)/(1/2)=1/3。覆盖比例乘以这个区域平均才会得到正确答案,但这个平均需要另外积分,不包含在覆盖比例之内。
快速检查
(对宽度为 h 的一维方框,求 ω=2π/h 及 ω=3π/h 时的响应因子。解释为什么第二个值表示它不是截断频率为 2π/h 的锐利低通滤波器。)
计算 sin(ωh/2)/(ωh/2)。
解答 · 答案
在 2π/h,因子为 sinπ/π=0;在 3π/h,因子为 sin(3π/2)/(3π/2)=−2/(3π)=0。负号表示这个振荡的相位反转,不表示平均权重为负。有频率高于所提截断频率的振荡仍然保留下来,所以一个响应零点不代表锐利截断。方框也会衰减所提通带内的频率:在 ω=π/h,因子为 2/π,并非一。
相关笔记与限制
光栅化与插值笔记提供点测试、边界归属及逐样点深度;整数直线与中点圆笔记规定离散边界选点。本节则为直线边界及无限平行带、在可见颜色均匀的条件下,加入精确面积测量。它们合起来说明:精确光栅化与反锯齿处理的是相关但不同的问题。
有限线段端帽及接合的精确覆盖、曲线边界面积公式、带变化属性的一般多边形积分、包含可见性判定的连续积分、重建滤波器设计,以及数值稳健性,仍需另外学习。本节没有确立原生 API 一致性或 GPU 实现。