美國畫家Jackson Pollock曾經說過:「都是在玩構築罷了——有人用刷子,有些人用鏟子,有的人用筆」,我很喜歡這句話,在最後加了句「而有些人,例如我,用的是程式碼」,在我的GitHub、Twitter等網站的自我介紹上,都可以看到這句話。

用程式碼構築3D模型是我的樂趣之一,然而,在建立某個模型之後,開心的感覺並不會維持太久,有時甚至會覺得,在試圖建模前的苦惱、搜尋、嘗試,在興致的維持上,還比較耐久一些,有些甚至是維持了數年之久,例如:迷宮等,都是多年不斷的主題創作。

就我而言,長時間從事某個主題創作的好處是,可以看得出成長的足跡,在外觀上,模型的複雜度漸次提升,在程式層面是程式庫的逐漸豐富,在知識方面,是對數學、資料結構、演算法等的日積月累,而每一次層次提升,都成為下次創作的基石。

哈密瓜與球面Voronoi

最近我構築出一顆平凡無奇的哈密瓜,不明就理的人,應該會覺得發布一顆哈密瓜是要幹嘛?我想傳達什麼呢?

從我的第一個OpenSCAD作品算起,到寫出哈密瓜花了我六年的時間,如果你曾經處理過Voronoi,應該會知道重要的是瓜面的紋理,也就是球面的Voronoi。

球面Voronoi與極點投影

Voronoi圖案代表著勢力均衡,就程式設計來說,有多種實現的方式,像是半平面交集、Fortune演算,或者是透過Bowyer-Watson演算求Delaunay三角分割後,轉換為Voronoi,這些在先前專欄〈Voronoi與Delaunay〉談過,其中也提到一些文件鏈結,當中有說明與實作。

如果想實現球面Voronoi,第一個想到的是需要3D版本的Voronoi,問題在於:大多數文件都是談二維平面如何建立Voronoi。多年以來,我試著搜尋Voronoi 3D的文件,大多是附於CAD軟體中的功能,或者像是Scipy之類的程式庫,提供spatial.Voronoi之類的API,可以用來建立3D的Voronoi,我確實也曾基於CadQuery結合spatial.Voronoi來建模。

然而,我一直想挑戰純粹使用OpenSCAD來實現球面Voronoi。在難以尋得相關文件的情況下,我曾試著將半平面交集擴充為半空間交集,實現3D版本的Vornoi,但速度過於緩慢到難以忍受。

這個議題就擱置了好多年,直到前些日子,我在〈Red Blob Games〉中,找到了〈Delaunay+Voronoi on a sphere〉,那時,我才知道所欠缺的,其實並不是3D版本的Voronoi,而是球極平面投影

簡單來說,我想做的是在「球面」建立Voronoi,而不是整個「球體」建立Voronoi,亦即其實是像Scipy的spatial.SphericalVoronoi,在球面上布點、建立Voronoi,而不是在球體內佈點建立Voronoi。

至於球極平面投影,像是XY平面從球的赤道橫切,然後在球的北極點一盞燈,球面上的點沿著光行進的方向,全部映射至XY平面,若對XY平面上的點進行Delaunay三角分割,轉換為Voronoi,再將結果投影回球面,就會是正確的球面Voronoi。

其中要注意的是北極上的點,投影結果會在XY平面的無限遠點,因此在求XY平面的Voronoi時,必須有個無限遠點,如此投影回球時,北極點才不會有破洞,雖說需要無限遠點,實際在建模或繪圖時,只要有夠遠的點,讓投影後的破洞看不出來即可。

Delaunay+Voronoi on a sphere〉有可互動的動畫展示,其中也提供了原始碼可供參考,附帶一提的是,作者本人熱衷於數學與演算法的互動視覺開發,〈Red Blob Games〉還有不少關於數學與演算法的有趣主題可以挖掘。

實作資料結構與演算法

知道演算法與使用特定語言實現,其實這中間是有段距離的,畢竟語言特性不同,要用OpenSCAD實現Voronoi更是如此。因為有關Voronoi的演算法虛擬碼,多半是以命令式來描述,能找到的程式實作,也都是命令式語言,然而OpenSCAD是個偏向函數式典範的語言。

不過,將命令式演算拆解為函數式演算這方面,我已相當有經驗,麻煩的是其中需要的資料結構——OpenSCAD完全沒有排序、搜尋的現成函式,也沒有最重要的字典結構,雖然能用JavaScript之類的命令語言實現出Voronoi,但在OpenSCAD中,我必須先將這些資料結構實現出來。

為了能快速處理大量的頂點、索引,我在OpenSCAD要實現基於雜湊的字典結構,為此必須先解決如何計算雜湊的問題,在使用者沒有指定如何計算雜湊值的情況下,我預設會將鍵轉為字串表示,然後對字串進行雜湊,為此我還去看了一下Java原始碼中怎麼對字串做雜湊計算。

在能夠實現相關資料結構後,我實現了Bowyer-Watson演算求三角分割,但效能並不好。經過多次評測之後,我發現,字串雜湊值只能作為一種預設方案,針對特定情境,例如,鍵會是一組索引或者是點座標時,若是轉為字串再計算雜湊反而緩慢,此時,需要定義專用的雜湊方式,例如點座標p,我採取的方式是與[73856093,19349669,83492791](許多文件推薦的組合)進行內積運算,取整數部分的絕對值作為雜湊值,實際評測之後,也確實有不錯的效能改進。

然而,還有可以改進的地方。由於OpenSCAD採用不可變動(immutable)特性,Bowyer-Watson演算必須調整,像是一開始就為字典建立適合大小的雜湊桶(hash bucket),這能有效減少建立新狀態的次數,對於效能是否良好,會有很大的決定性。

在這之前我還真沒想過:有一天必須自行實現字典這類資料結構。然而透過這樣自行實現,一邊評測、一邊依語言特性調整資料結構、演算法的過程,得到了許多教科書沒看過的經驗;這讓我想起有些開發者會說:「學資料結構、演算法根本就沒有用,因為現代語言都會有標準實作,或者也會有第三方程式庫提供更好的實現」是這樣的嗎?

對我來說,資料結構、演算法除了能讓開發者在使用相關程式庫時,比較能掌握對應特性之外,若沒有這類基礎知識,我是不可能在OpenSCAD中實現字典等資料結構,寫出Voronoi,更不可能構築一顆哈密瓜吧!

長時間從事創作的積累

其實能寫出球面的Voronoi後,我試過幾個模型作為範例,目的是展現純OpenSCAD也能實現球面Voronoi。有網友問我用的是什麼演算法,他說他的2D版本若是幾百個點,就要花幾個小時,一千個點大概得花一天的時間。

這就是我最後選擇,只發布一顆平凡無奇的哈密瓜的原因,如果瓜面有1,000個左右的點,大概一分鐘就可以生成,這讓我有種「懂的人自然就懂了」的虛榮感,不過,雖然執行程式生成一顆瓜只要一分鐘,然而真的要講並不容易,因為,我可是花了六年的積累,才有可能實現!

你曾經長時間從事某個主題創作嗎?當然,主題不用像我一樣是3D建模,或許是某個應用程式,或者是開放原始碼之類的東西,這會是個難能可貴的經驗!

專欄作者


熱門新聞

Advertisement