光柵化矢量圖像的一般算法

Question

光柵化矢量圖像的一般算法是什麼？我發現了許多柵格化基元的算法，例如線條，圓，貝塞爾曲線等。但是對於一般情況，我該怎麼做？簡單地說，向矢量圖中的矢量圖中添加foreach，獲取其像素並將其放入光柵圖像中？或者是其他東西？

另一個問題，我該如何提高使用併發處理的時間？例如，我可以分離矢量圖並同時獲取像素。但也許有其他方法可以做到這一點？

Answer 1

一般的光柵化算法就是這樣，對於圖像中的每個多邊形。 （一個多邊形定義爲由直線段和參數樣條構成的一個或多個閉合曲線 - 在正常實踐中，這些曲線是二階（二次曲線）和三階（三次）Bézier樣條曲線。這些閉合曲線被定義爲內部總是在左側，因爲曲線是通過的;所以普通形狀逆時針運行並且孔順時針運行。）

（i）（投影）將多邊形轉換爲與目標位圖。分辨率不必相同，對於消除鋸齒的圖像往往更大：例如，FreeType使用64像素。 （ii）（使Y單調）必要時，將多邊形的每個分段分成連續向上或向下運行的較小段。這個階段僅適用於曲線段，並且在使用貝塞爾樣條時相對容易。通常的方法是反覆平分直到達到單調性。丟棄所有水平段。 （iii）（標記運行限制）將每個段繪製到臨時位圖中。使用Bresenham的直線算法;對於曲線，平分線直到線距離實際曲線的1/8像素（比如說），然後從頭到尾使用一條直線。繪製時，以某種方式標記像素以指示（a）它們是開始還是結束運行 - 向下的線開始，向上的線結束; （b）覆蓋率 - 形狀內像素的分數。這是算法細節不同的地方，以及纏繞規則（non-zero與even-odd）之間的區別。 （iv）（掃描）逐行遍歷臨時位圖。對於每一行，從左到右掃描。通過（例如）將存儲在位圖中的數字添加到存儲的數字來維護指示當前位置是否在形狀內部的狀態。在簡單的單色光柵化過程中，在前一階段編寫的這個數字將在邊緣進入形狀時爲+1，在形狀出來時爲-1。在相同的狀態下累積像素運行。將運行發送到您的繪圖模塊：例如，FreeType發出包含Y座標，開始和結束X座標以及覆蓋範圍從0到255的運行。繪圖模塊可以使用coverage作爲應用於當前繪圖顏色的Alpha值，或作爲應用於紋理的蒙版。

以上是一個偉大的過度簡化，但給出了一般的想法。

大多數開放源代碼程序使用從下列項目之一衍生光柵化代碼：

FreeType - 一字形生成它包含了相對容易使用單機單聲道和抗鋸齒光柵模塊 - 即對於任何形狀而言，不僅僅是字體。我已經在幾個商業可移植的C++項目中成功地使用了這個系統。

FreeType的系統靈感來自於Raph Levien的Libart。

Anti-Grain是另一個流行的和有影響力的C++庫。

還有由Kiia Kallio實施的scan-line edge flag system，它看起來很有前途，似乎比反穀物更快。

大多數但不是全部這些庫接受由二次和三次貝塞爾樣條以及直線段組成的形狀。那些沒有的（例如K. Kallio的圖書館）只能使用直邊多邊形;但是很容易將曲線「平坦化」成比距實際曲線的期望最大距離更近的一系列線段。 FreeType可以在內部執行此操作，並且可以在必要時借用它的代碼。