Trangle Rasterization

less than 1 minute read

OpenMVS[Homogeneous Coordinate]

Line sweeping[线扫法]

Barycentric Coordinates[重心坐标系判定法 - 并行计算中的判定]

  • 遍历AABB内的所有点的重心坐标
  • For Convex
  • 重心坐标具有仿射不变性
  • As Area coordinates in trangle
    • 20210928223322
    • 对于三点$A,B,C$的坐标分别为$\mathbf{a,b,c}$
    • 对于任意点$P$的坐标$p$
    • 设$S_{\triangle{PBC}}:S_{\triangle{PBC}}:S_{\triangle{PBC}}=\lambda_1:\lambda_2:\lambda_3$
    • $\lambda_1+\lambda_2+\lambda_3=1$
    • 延长$AP$交$BC$于$D$
    • $$ \begin{aligned} &\because&BD:DC&=\lambda_3:\lambda_2\\ &\therefore& \mathbf{d}&=\frac{\lambda_2\mathbf{b}+\lambda_3\mathbf{c}}{\lambda_2+\lambda_3}\\ &\because&AP:PD&=(\lambda_2+\lambda_3):\lambda_1\\ &\therefore&\mathbf{p}&=\frac{(\lambda_2+\lambda_3)\mathbf{d}+\lambda_1\mathbf{a}}{\lambda_1+\lambda_2+\lambda_3}\\ &\therefore&\mathbf{p}&=\lambda_1\mathbf{a}+\lambda_2\mathbf{b}+\lambda_3\mathbf{c} \end{aligned} $$
    • 因此,重心坐标, 也是面积坐标
  • For each pixel we compute its barycentric coordinates. If it has at least one negative component, then the pixel is outside of the triangle.

  • 点在三角形内的问题转换为求解重心坐标
    • 面积法
      • $$ \lambda_1=\frac{S_{\triangle{PBC}}}{S_{\triangle{ABC}}}=\frac{\begin{vmatrix} 1&x_p&y_p\\ 1&x_b&y_b\\ 1&x_c&y_c\\ \end{vmatrix}}{\begin{vmatrix} 1&x_a&y_a\\ 1&x_b&y_b\\ 1&x_c&y_c\\ \end{vmatrix}} $$
      • 其中
      • $$ S_{\triangle_{ABC}}=\frac{1}{2}\begin{vmatrix} 1&x_a&y_a\\ 1&x_b&y_b\\ 1&x_c&y_c\\ \end{vmatrix} $$
    • 代数法
      • $$ \begin{cases} \lambda_1x_a+\lambda_2x_b+\lambda_3x_c&=x_p\\ \lambda_1y_a+\lambda_2y_b+\lambda_3y_c&=y_p\\ \lambda_1+\lambda_2+\lambda_3&=1\\ \end{cases} $$

Linear Edge Function, Line sweeping[线边法]

Categories:

Updated: