螢幕畫面或圖片資料的基本單元是像素,探討像素如何組成線、圓、多邊形等基本圖案,對於須自行打造繪圖程式庫的場合,是必要課題,就演算分析而言,也是不錯的基礎訓練。

像素的世界

像素英文為pixel,拆開來看是pix與el,也就是picture與element,意謂著圖像基本元素。如果呈現圖像可用的像素不多時,圖像就會明顯看出許多小方塊,現在電子產品多擁有高解析度,可呈現的圖像元素極高,若想看見這種小方塊,大概就是在LED點矩陣螢幕、小尺寸液晶螢幕,或者是故意將點陣圖降低解析度並拉大,才能看得到了。

繪圖軟體或程式庫,基本上,都會提供直線、曲線、圓、多邊形等基本圖案的繪製,既然螢幕或圖片是以像素組成圖像,這意謂著,線、圓、多邊形都是由小方塊組成,就算是向量圖,也是經適當的計算後,運用足夠數量的像素來繪製,這屬於Shape Rendering的領域。只不過繪圖軟體或程式庫都已經將相關演算法封裝好了,因此,在高解析度下,繪圖者或開發者不會意識到這些方塊的存在。

然而,有時候,我們必須親自處理這些方塊。就我個人的經驗來說,是為了開發Minecraft模組時,才接觸到相關的演算,而在Minecraft的世界中,一切都由方塊組成,就算只是要在玩家位置與左前方建築間畫條直線,都要使用方塊來構築,如果想寫程式自動化這些建築動作,勢必就要處理Shape Rendering的問題。

當然,在我之前,已經有人面臨相同的需求,也有類似的程式庫。例如,minecraftstuff,它提供了一個MinecraftDrawing類別可用來滿足以方塊繪圖的需求,不過,minecraftstuff不是原生的Minecraft模組,而是用Python開發,因此,必須結合其他模組來操作Minecraft進行建築。

為了使用Java開發原生的Minecraft模組,我閱讀了MinecraftDrawing類別相關的繪圖原始碼,將之翻譯、實作為Java版本,因而首次接觸了Shape Rendering相關演算。我後續在玩OpenSCAD時,也運用了這方面的知識,打造了體素(voxel)相關函式,也就是可用來3D建模的立體方塊版本。

像素直線與曲線

想要接觸Shape Rendering相關演算,最簡單的入門就是線段繪製,若給予兩個點的座標,許多人會很直覺地基於斜率來繪製,很可惜地,這行不通,因為方塊座標會是整數,無論是採ceil、round、或floor來取座標,只要斜率不是1,就會有方塊不連接、零落散置的可能性。

以座標第一象限為例,若斜率大於1並基於x來計算,方塊就會不連續,反之,若斜率小於1並基於y來計算,方塊也會不連續,為了解決這個問題,可以看看兩點座標的x差距大,還是y差距大。若x差距大,就以x來計算(此時斜率小於一),若y差距大,就以y來計算(此時斜率大於一)。

在注重效率的場合,我們可以進一步採用Bresenham直線演算,基本原理相同,然而可預先計算斜率,後續單純地基於累計及誤差值判斷,來尋找整數座標;對於Minecraft之類的繪圖需求,不需要反鋸齒的功能,然而,若需要這樣的呈現,可以使用Xiaolin Wu直線演算

如果要繪製像素曲線,例如貝茲曲線,方式之一是透過貝茲曲線函式求得每個點,接著以像素直線的函式來繪製,只不過稍嫌麻煩了一些,這時可以基於貝茲曲線的原理做些變化。以三個控制點為例,如果求得控制點間的中點,然後就兩個中點的中點,就可以求得曲線上的一點,接著以控制點間的中點來對分,持續遞迴,也可以求得貝茲曲線。

我們可以將以上概念擴充到四個控制點,接著基於它來實作Catmull-Rom樣條,就可以用一連串的控制點來繪製像素曲線,方塊將會通過第一與最後一個以外的其他控制點,實作細節方面,我們可以參考〈像素曲線〉

像素圓到簡單多邊形

若要繪製像素圓,雖然我們可以將圓看成是正多邊形,也就是多條直線接合組成,然後基於像素直線來繪製,但繪製出的圓會有不對稱的地方,這是因為像素直線並不考量對稱性,而圓是對稱的。若想讓像素圓有對稱感,應該善用對稱,也就是在繪製圓時,只要計算八分之一圓的像素就可以了,其餘像素可直接對稱處理。

另外,也不必將圓看成是正多邊形,因為圓的公式是x^2+y^2=r^2,若是實心圓,可以單純地跑(x,y),只有在(x,y)於圓內時才畫出來,若是空心圓,可以採用中點圓演算

以逆時針畫圓為例,圓的下個像素可能是在正上方或左上角,取這兩個像素座標的中點(x,y),若x^2+y^2-r^2小於零,表示中點在圓的內側,也就是圓比較靠正上方像素,這時就畫出正上方像素,若x^2+y^2-r^2大於零,表示中點在圓的外側,也就是圓比較靠左上角像素,這時就畫出左上方像素,對於等於零的情況,選哪個皆可,固定選一個就好。

若採用了中點圓演算,因為已經有圓的邊緣像素了,想填滿圓就只需使用掃描法,不必動用到圓公式,例如,在每個y列,從最左邊的像素掃到最右邊的像素,實作細節可以參考〈像素圓〉

若是任意的簡單多邊形(邊不相交的多邊形),因為任意表示不一定對稱,只要將每個點以像素線連接就可以了,問題在於如何填滿。若是凸多邊形,比較好解決,如同圓,找出每個y列,從最左邊的像素掃到最右邊的像素就可以了。

若不是凸多邊形,比較簡單的想法是試誤,也就是將可涵蓋多邊形的方形範圍內全部像素,拿來判斷判斷是否在多邊形內部。為了判斷座標是否在多邊形內部,我們可以從該點隨意畫一條直線,看看穿過多少條邊,如果穿過奇數次,表示點在簡單多邊形內部。

如果不想試誤,我們可以使用Flood Fill演算,也就是繪圖軟體中倒油漆填滿的原理──先用像素直線找出多邊形邊緣的像素,然後在多邊形內部選一個點,遞迴往四個方向填滿,直到抵觸邊緣的像素為止。

在繪圖軟體中,在哪個位置倒油漆是由使用者決定的,然而繪製多邊形就必須自動化選取多邊形內部的一個點,這可以逐一走訪多邊形邊緣的像素,若找到某像素的鄰居是在多邊形內就停止,然後從該鄰居進行Flood Fill演算。

演算分析的基礎訓練

談到Flood Fill,可能會有人想到,LeetCode好像就有一題Flood Fill!是的,這就是我在玩Shape Rendering的感覺,某些程度上,就像是玩LeetCode!

對我來說,這不但有著實作Minecraft模組、OpenSCAD程式庫的實用性,也是在進行相關演算的基礎訓練。由於有著明確的目標,也就能分析各個演算的優缺點,進一步地變化或結合各演算來達到自己的需求。

雖然(繪圖)程式庫早就將相關(且更好的)演算封裝好了,開發者可以基於更高階的概念,兜出想要的功能,然而有機會的話,探究一下底層使用的演算,著實會有不少的收穫。

作者簡介

熱門新聞


Advertisement