像素圓


在〈像素直線〉的最後,試著用像素直線來繪像素圓,結果並不是很理想,因為顯然有不對稱的地方,是的!不若隨意畫的直線,圓是對稱的,若想讓圓更好看一些,應該善用對稱。

對於這個問題,可以只畫出八分之一圓,然後其他以對稱方式處理就可以了,例如逆時針算出以上綠色的點就可以了:

像素圓

另一方面,並不需要將圓看成是正多邊形並繪製直線,如果要繪實心圓的話,因為圓的公式是 x2 + y2 = r2,可以單純地跑 (x, y),只有在 (x, y) 於圓內時才畫出來,不過,若想繪製空心圓呢?

可以採用中點圓演算(Midpoint circle algorithm)來解決,假設已經圓上第一個像素已經畫出,如下圖的綠色:

像素圓

這邊對半徑採四捨五入,因此對紅色圓或綠色圓,第一個像素都會是在上圖中的綠色區域,若是逆時針繪製,就往綠色左上角取 I、O 點,以及這兩點的中點 M,如果 M 點座標 (x, y),x2 + y2 - r2 < 0,表示 M 在圓的內側,也就是圓比較靠 O 點,這時就畫出 O 點的像素,對於紅色圓與綠色圓,都可以畫出下圖:

像素圓

同樣地,現在 M 點座標也是在紅色圓與綠色圓內側,可以畫出下圖:

像素圓

對於紅色圓來說,如果 M 點座標 (x, y),x2 + y2 - r2 > 0,M 在紅色圓的外側,這表示圓比較靠 I 點,若是要繪紅色圓,應該畫出 I 點像素:

像素圓

對於藍色圓來說,M 在內側,這表示圓比較靠 O 點,若是要繪藍色圓,應該畫出 O 點像素:

像素圓

如果 M 正好在圓上呢?那就看你高興取 I 或 O,這篇文件後續會一律取 O,以上流程持續到 x < -y 就可以停止了,因為只要算出八分之一圓,其餘就對稱處理。

x2 + y2 - r2 有用到平方計算,你要直接計算也是可以,不過實際上可以基於前一次的計算結果來化簡,不需用到平方計算,假設現在畫到以下狀態了:

像素圓

上圖列出了目前像素左上座標,以及 I、M、O 點的座標,以 M 座標來計算 x2 + y2 - r2,就是 (xi - 1/2)2 + (yi - 1)2 - r2,若結果小於 0,那麼要選 O 作為下個像素點,其下個中點會是 (xi - 1/2, yi - 2),套入 x2 + y2 - r2 的話,就是 (xi - 1/2)2 + (yi - 2)2 - r2,來比較這兩條公式:

(xi - 1/2)2 + (yi - 1)2- r2
(xi - 1/2)2 + (yi - 2)2 - r2

若整理一下上列的公式,如果你有前一次 x2 + y2 - r2 的運算結果 f,那麼下一次運算結果其實會是 f - 2 * cy + 3。

接著來看 (xi - 1/2)2 + (yi - 1)2 - r2 大於等於 0 的情況,這時要選 I 作為下個像素點,其下個中點會是 (xi - 1, yi - 1),套入 x2 + y2 - r2 的話,就是 (xi - 3/2)2 + (yi - 2)2 - r2,來比較這兩條公式:

(xi - 1/2)2 + (yi - 1)2 - r2
(xi - 3/2)2 + (yi - 2)2 - r2

若整理一下上列的公式,如果你有前一次 x2 + y2 - r2 的運算結果 f,那麼下一次運算結果其實會是 f - 2 * (cx + cy) + 5。

那麼首次的 f 呢?如果半徑是 r,第一個像素的座標會是 (r, 0),套到 x2 + y2 - r2,計算後的結果會是 1.25 - 2 * r。

整理一下以上的結果,若最初像素座標 (x, y) 為 (r, 0),逆時針畫八分之一圓,也就是到 x < -y 停止繪製的話:

  • 最初的 f 是 1.25 - 2 * r。
  • 若 f < 0,下個像素座標會是 (x, y - 1),下個 f 會是 f - 2 * cy + 3。
  • 若 f >= 0,下個像素座標會是 (x - 1, y - 1),下個 f 會是 f - 2 * (cx + cy) + 5。

根據以上,可以寫出以下的 pxCircle

這樣就可以畫出圓來了,如果要填滿的圓,只要以對稱點來畫出直線就可以了:

基本上,以上的計算方式,也可以推廣至橢圓或拋物線,有興趣可以自行嘗試。