三角形の塗りつぶし

三角形の塗りつぶしとは、三角形の中にあるピクセルを見つけて、色をつけることです。ゲームや3D の絵は、小さな三角形をたくさん塗って作られています。

このレッスンでは、辺のテストで、ピクセルが三角形の中にあるかを調べます。さらに、重心座標という重みで、点の位置を表します。

三角形の1つの辺を、a から b への矢印と考えます。点 p が矢印のどちら側にあるかは、ある計算の符号で決まります。

計算は、(bx − ax) × (py − ay) − (by − ay) × (px − ax) です。この値が正なら一方の側、負ならもう一方の側、0 なら辺の上です。

点が三角形の内側にあるのは、3つの辺のテストの値が、すべて同じ向きのときです。つまり、すべて 0 以上か、すべて 0 以下です。

1つでも向きが違えば、外側です。辺の上の点、つまり値が 0 の点は、この課題では内側に数えます。

def side(start, end, point):
    return (end[0] - start[0]) * (point[1] - start[1]) - (end[1] - start[1]) * (point[0] - start[0])

a = [0, 0]
b = [6, 0]
c = [0, 6]
p = [1, 1]
print(side(a, b, p), side(b, c, p), side(c, a, p))
# p を [5, 5] に変えて、もう一度実行します。
# 3つの値の符号は、そろっていますか。

塗るときは、画面のすべてのピクセルを調べる必要はありません。三角形をぴったり囲む四角、バウンディングボックスの中だけを調べれば十分です。

四角の中の各ピクセルが、内側かどうかを判定し、内側なら色をつけます。内側の数を数えれば、塗ったピクセルの数が分かります。

Pillow の polygon は、多角形を塗りつぶします。次のコマンドは、16 × 16 の黒い画像に、(0, 0)、(15, 0)、(0, 15) の三角形を白で塗り、triangle.png に保存します。

triangle.png を開くと、左上が白い直角三角形が見えます。白いピクセルの数は 136 です。これは、x と y が 0 以上で、x + y が 15 以下の点の数と同じです。

docker exec jupyter python3 -c "from PIL import Image, ImageDraw; im = Image.new('L', (16, 16), 0); ImageDraw.Draw(im).polygon([(0, 0), (15, 0), (0, 15)], fill=255); im.resize((160, 160), Image.NEAREST).save('triangle.png'); print(sum(1 for p in im.getdata() if p)); print(im.getpixel((2, 2)), im.getpixel((14, 14)))"

三角形の中の点は、3つの頂点の重みつき平均で表せます。この3つの重みを重心座標と呼びます。重みは、足すと 1 になります。

重みは、点の向かい側にできる小さな三角形の面積を、全体の面積で割った値です。重みがすべて 0 以上なら、点は内側にあります。色を頂点の間でなめらかに変えるときにも使います。

次のコマンドは、三角形 (0, 0)、(4, 0)、(0, 4) の中の点 (1, 1) について、3つの重みを求めます。全体の面積は 8 で、3つの小さな三角形の面積は 4、2、2 です。

出力は 0.5 0.25 0.25 で、足すと 1 です。最初の頂点 (0, 0) に近い点なので、その重みがいちばん大きくなります。

docker exec jupyter python3 -c "a = (0, 0); b = (4, 0); c = (0, 4); p = (1, 1); area = lambda u, v, w: abs((v[0] - u[0]) * (w[1] - u[1]) - (w[0] - u[0]) * (v[1] - u[1])) / 2; t = area(a, b, c); print(area(p, b, c) / t, area(a, p, c) / t, area(a, b, p) / t)"