如何將封閉的貝塞爾曲線轉換爲位圖？

Question

我需要一個算法來將封閉貝塞爾曲線（可能是自交）轉換爲二進制位圖：0表示內部像素，1表示外部。我在編寫需要在貝塞爾曲線上實現一些操作的代碼，有人可以給我一些關於貝塞爾的資源或教程嗎？維基百科和其他人沒有說優化，減，工會，結插入和刪除等操作任何:-)

alt text http://www.imagechicken.com/uploads/1271001073057545100.jpg

Answer 1

這paper by Charles Loop and Jim Blinn進入很多細節上你的問題。

另一種選擇是將貝塞爾曲線細分爲線段，然後使用您最喜歡的多邊形填充算法。

Answer 2

我想補充說，鑲嵌選項非常有效，並且可以提供出色的結果。用線段近似貝塞爾曲線聽起來是錯誤的，因爲你認爲輸出看起來像一個多邊形。訣竅是使線段足夠短，以便誤差非常小（比如，小於1/10像素）。

這裏是我已用於計算步長大小，以確保最大誤差（即，從真曲線線段的偏差）小於增量的公式：

設（X1，Y1） ，（X2，Y2），（X3，Y3），（X4，Y4）是貝塞爾曲線的控制點，在像素coordinates.j

 
    dd0 = square(x1-2*x2+x3) + square(y1-2*y2+y3); 
    dd1 = square(x2-2*x3+x4) + square(y2-2*y3+y4); 
    dd = 6*sqrt(max(dd0, dd1)); 

然後dd是第二導數的最大值超過曲線 - 因爲立方的二階導數是一個線性函數，這個最大值必須發生在一個端點上。這裏我用square（x）作爲x * x的縮寫。

 
    if (8*delta > dd) { 
    epsilon = 1; 
    } else { 
    epsilon = sqrt(8*delta/dd); 
    } 

然後小量是你的步長：如果您選擇線段的端點在t = 0，T =ε，T = 2 *ε，...，（和在t最後的終點= 1），那麼線段將在原始曲線的增量內。

選擇增量= 0.1，您會得到與原始曲線在視覺上難以區分的位圖輸出。