在《如何用 C 語言畫這個圖》提及有兩兩種方法繪畫圖形,一種是光柵化,另一種是取樣。本答案講述較簡單的取樣方法:把一個圖形可表示為函式 ,檢測一個座標是否在圖形之中。
三角形可用兩種描述方式:3 個頂點;或 3 個半空間(half-space)的交集。前者比較容易理解,通常用於定義三角形。後者則很方便去做點是否在內的檢測。所以檢測時,可以把頂點描述轉換為半空間描述。
但要做這種轉換,最好把頂點設定成固定的纏繞順序(winding order),例如以下采用順時針。
在轉換時,給定三角形的一條邊 ( ),計算出它的半空間的垂直方向:
由於我們需要 是指向三角形之外,根據順時針的纏繞順序,我們需要把 逆時針旋轉 。寫成矩陣形式:
然後要判斷一點 是否在半空間之外,可以檢測
如果 在任何一個半空間之外,就能判定它在三角形之外;若 都在三個半空間之內,則是在三角形之中。(注:(3) 用 代替 也是可以的,只要是邊上的點都可以。)
把數式寫成程式碼其實非常簡單。
除了三角形,這個方法可以用於任何凸多邊形,或稱為二維凸多胞形(convex 2-polytope)。甚至乎,它可以擴充套件至三維或更高維的多胞形。但在三維的時候,只有像四面體(tetrahedron)這種單純形(simplex)可以簡單地從頂點描述(V-description)轉換成半空間描述(H-description),所以最好能直接用半空間來做這種取樣。
最後,在《用 C 語言畫光(三):形狀》中也描述了三角形的 SDF,可以用於《用 C 語言畫直線》裡談及的抗鋸齒圖形渲染方法。
在《如何用 C 語言畫這個圖》提及有兩兩種方法繪畫圖形,一種是光柵化,另一種是取樣。本答案講述較簡單的取樣方法:把一個圖形可表示為函式 ,檢測一個座標是否在圖形之中。
三角形可用兩種描述方式:3 個頂點;或 3 個半空間(half-space)的交集。前者比較容易理解,通常用於定義三角形。後者則很方便去做點是否在內的檢測。所以檢測時,可以把頂點描述轉換為半空間描述。
但要做這種轉換,最好把頂點設定成固定的纏繞順序(winding order),例如以下采用順時針。
在轉換時,給定三角形的一條邊 ( ),計算出它的半空間的垂直方向:
由於我們需要 是指向三角形之外,根據順時針的纏繞順序,我們需要把 逆時針旋轉 。寫成矩陣形式:
然後要判斷一點 是否在半空間之外,可以檢測
如果 在任何一個半空間之外,就能判定它在三角形之外;若 都在三個半空間之內,則是在三角形之中。(注:(3) 用 代替 也是可以的,只要是邊上的點都可以。)
把數式寫成程式碼其實非常簡單。
除了三角形,這個方法可以用於任何凸多邊形,或稱為二維凸多胞形(convex 2-polytope)。甚至乎,它可以擴充套件至三維或更高維的多胞形。但在三維的時候,只有像四面體(tetrahedron)這種單純形(simplex)可以簡單地從頂點描述(V-description)轉換成半空間描述(H-description),所以最好能直接用半空間來做這種取樣。
最後,在《用 C 語言畫光(三):形狀》中也描述了三角形的 SDF,可以用於《用 C 語言畫直線》裡談及的抗鋸齒圖形渲染方法。