Rasterizationメモ

2019-04-14 · Updated: 2025-07-11

ラスタライゼーションについて個人的に調べたものです。内容には間違いが含まれている場合があります。

数学

三角形(Triangles)

3つの｜頂点《vertex》、3つの｜辺《edge》を持つ｜多角形《polygon》
ある平面上に存在する
- ｜退化《degenerate》していなければ、その平面が一意に定まる
- 退化している三角形は、すべての頂点が一直線上にある(共線である)
｜内側《interior》と｜外側《exterior》がある
- 内側は有限空間、外側は無限空間
- 3つの辺から成る｜境界《boundary》で分けられる
常に｜凸《convex》である
- 三角形の内側にある2点から成る線分もまた常に三角形の内側にある
- $n$ 個の辺の凸多角形は $n$ 個の｜半空間《half-space》との交差として扱うことができる

向きを持つ辺(Oriented edges)

辺が $v_0$ から $v_1$ に向かうとき：
- 左側を”｜正《positive》”の半空間と呼ぶ
- 右側を”｜負《negative》”の半空間と呼ぶ

重心座標系(Barycentric coodinate system)

\left\{ \begin{aligned} \lambda_0(P) &= \text{Orient2D}(V_1, V_2, P) / |\text{Orient2D}(V_0, V_1, V_2)|, \\ \lambda_1(P) &= \text{Orient2D}(V_2, V_0, P) / |\text{Orient2D}(V_0, V_1, V_2)|, \\ \lambda_2(P) &= \text{Orient2D}(V_0, V_1, P) / |\text{Orient2D}(V_0, V_1, V_2)| \end{aligned} \right.

点 $V_i$ は三角形の頂点を表す
$\text{Orient2D}(A, B, C)$ は $\vec{AB}$ と $\vec{AC}$ の外積を求める
- $\vec{AB}$ と $\vec{AC}$ から成る平行四辺形の符号付き面積に等しい
  - 点 $C$ が $\vec{AB}$ の左側にあれば正になる
  - 点 $C$ が $\vec{AB}$ の右側にあれば負になる
$i = 0, 1, 2$ のすべてにおいて $0 \le \lambda_i(P) \le 1$ となれば、点 $P$ は三角形の内側または境界上にある
- このとき、 $\lambda_i(P) = 0$ ならば、点 $P$ は辺 $V_0V_i$ 上にある
$\lambda_0(P) + \lambda_1(P) + \lambda_2(P) = 1$

ラスタライゼーション(Rasterization)

三角形を”｜ラスタライズする《rasterize》”とは、その三角形の内側にあるピクセルを見つけること
- そうして見つけたピクセルを色付けする

Top-left rule

ピクセルの中心が三角形の内側に入るならば、それを描画する
｜上辺《top edge》と｜左辺《left edge》の上にあるピクセルを三角形の内側にあると定義する
- 上辺は｜完全に水平《exactly horizontal》であり、他の辺より上にある
- 左辺は完全に水平でなく、三角形の左側にある
これに従うと、隣接する三角形がどちらか一回だけピクセルを描画するようになる

Binning

Binningとは、隣接する要素をひとまとめにして扱うこと
スクリーンをタイルに分割して、タイルごとに処理を行う
- 計算に必要なデータをL2キャッシュに収まるくらいに小さくできる

参考資料

Share this post on:

Table of Contents: