動機
想像一條黑色邊界在白色影像上緩慢移動。只取中心樣點的像素,在邊界通過中心之前一直是白色,通過之後便突然變黑。幾何形狀連續地移動,儲存值卻跳變,原因是測量只在一個點問「在內還是在外」。整數直線或圓的算法可以把這個離散問題規定清楚,卻不會改變問題的性質。選中一個附近的中心,不等於量度像素方格有多少面積被覆蓋。
要得到不同的答案,首先要提出不同的測量問題。假設像素記錄連續影像在一個矩形範圍內的平均值。部分被覆蓋的像素便會記錄由面積決定的混合值。對直線邊界,這個面積可以精確計算,不必用一大群測試點逼近。計算過程也會揭示:在甚麼假設下,單憑覆蓋比例就足以決定顏色。
本節為單一直線邊界,以及兩條平行邊界之間的帶狀區域,建立完整的有限公式。我們採用精確實數運算、各區域內均勻不變的顏色,以及明確選定的方框濾波器。本節不取代組裝三角網格時的樣點歸屬規則,也不把面積濾波等同理想的頻率截斷。一般曲線邊界、互相遮擋的可見層,以及空間上變化的著色,都需要另外處理積分。
定義
設 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 實作。