從無到有實現球面Voronoi

美國畫家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建模，或許是某個應用程式，或者是開放原始碼之類的東西，這會是個難能可貴的經驗！