삼각형을 화면에 그릴 때는 각 픽셀의 샘플 위치가 삼각형 안에 있는지 판정해야 한다. 이때 자주 쓰이는 방법이 Edge Function이다.

식만 보면 Edge Function은 단순한 일차식이다.

$$ E(P)=Ax+By+C $$

하지만 이 식을 외적에서 출발해 보면 의미가 선명해진다. 핵심은 외적의 부호가 점이 변의 어느 쪽에 있는지 알려준다는 것이다.

변과 픽셀을 잇는 두 벡터

삼각형의 한 변을 $V_0\rightarrow V_1$이라고 하고, 위치를 검사할 픽셀 샘플을 $P$라고 하자. 둘 다 $V_0$를 기준으로 벡터를 만든다.

\vec e=V_1-V_0,\qquad \vec p=P-V_0

여기서 $\vec e$는 변의 진행 방향이고, $\vec p$는 변의 시작점에서 픽셀을 향하는 방향이다. 이 두 벡터의 2차원 외적을 계산하면 Edge Function을 얻는다.

E(P)=\vec e\times\vec p

외적의 부호는 변의 어느 쪽인지 나타낸다

2차원 외적의 크기는 두 벡터가 만드는 평행사변형의 넓이다. 한 벡터를 밑변으로 보면, 그 크기는 밑변 길이와 높이의 곱이다.

|\vec e\times\vec p|=\text{밑변 길이}\times\text{높이}

Edge Function은 이 넓이에 부호를 붙여 사용한다. 일반적인 수학 좌표계처럼 $y$축이 위를 향하고, 변을 $V_0$에서 $V_1$ 방향으로 바라볼 때:

$E(P)>0$이면 $P$는 변의 왼쪽에 있다.
$E(P)<0$이면 $P$는 변의 오른쪽에 있다.
$E(P)=0$이면 $P$는 변과 같은 직선 위에 있다.

따라서 Edge Function의 값 하나로 픽셀이 변의 어느 쪽에 놓이는지 알 수 있다. 부호는 방향을, 절댓값은 변과 점이 만드는 평행사변형의 넓이를 나타낸다.

외적을 좌표식으로 풀기

각 점의 좌표를 다음과 같이 놓자.

V_0=(x_0,y_0),\qquad V_1=(x_1,y_1),\qquad P=(x,y)

2차원 벡터의 외적은 스칼라로 계산할 수 있다.

(a,b)\times(c,d)=ad-bc

그러므로

$$ E(P)=(x_1-x_0)(y-y_0)-(y_1-y_0)(x-x_0) $$

변의 방향 성분을 $dx=x_1-x_0$, $dy=y_1-y_0$라고 두면 식이 간단해진다.

$$ E(P)=dx(y-y_0)-dy(x-x_0) $$

항을 정리하면 다음과 같다.

E(P)=-dy\,x+dx\,y+dy\,x_0-dx\,y_0

즉, Edge Function은 $Ax+By+C$ 형태의 선형식이며 계수는 다음과 같이 정해진다.

A=-dy,\qquad B=dx,\qquad C=dy\,x_0-dx\,y_0

법선 방향으로 잰 부호 있는 거리

변의 방향 벡터가 $\vec e=(dx,dy)$일 때, 이를 90도 반시계 방향으로 돌린 벡터는 다음과 같다.

\vec n=(-dy,dx)

이 벡터는 변에 수직인 법선 방향이다. 앞에서 구한 Edge Function을 내적으로 다시 쓰면,

E(P)=(-dy,dx)\cdot(x-x_0,y-y_0) =\vec n\cdot(P-V_0)

라고 할 수 있다. 즉, $V_0$에서 $P$로 향하는 벡터가 법선 방향으로 얼마나 나아갔는지를 측정한다. 변 위에서는 법선 방향으로 나아간 양이 0이므로 $E(P)=0$이다.

이렇게 보면 $Ax+By+C=0$은 낯선 직선 공식이 아니다. 점이 변의 법선 방향으로 어느 정도 떨어져 있는지 계산하는 식이다. 다만 $\vec n$을 정규화하지 않았기 때문에 $E(P)$ 자체가 실제 수직 거리와 같지는 않다. 실제 부호 있는 거리는 $E(P)/|\vec n|$이다.

세 변의 부호로 삼각형 내부 판정하기

삼각형의 정점을 반시계 방향(CCW)으로 나열하면, 삼각형 내부의 점은 각 변을 따라 진행할 때 모두 왼쪽에 놓인다. 따라서 세 변의 Edge Function이 모두 0 이상인 점을 삼각형 내부로 판정할 수 있다.

E_0(P)\ge 0,\qquad E_1(P)\ge 0,\qquad E_2(P)\ge 0

기하학적으로는 각 변이 만드는 왼쪽 반평면 세 개의 교집합이 삼각형이다. 래스터라이저는 화면의 각 픽셀 샘플에서 이 세 식을 평가해 삼각형 내부에 있는지 결정한다.

좌표계와 경계 처리

화면 좌표에서는 보통 $y$가 아래로 증가한다. 이 좌표계에서는 앞에서 설명한 왼쪽과 오른쪽의 부호 해석이 뒤집힐 수 있다. 정점의 감김 방향에 따라 내부 판정 조건도 함께 뒤집어야 한다. 중요한 것은 특정 부호 자체가 아니라, 선택한 좌표계와 정점 순서에 맞춰 세 변의 조건을 일관되게 적용하는 것이다.

또한 실제 래스터라이저는 공유 변 위의 픽셀 샘플을 이웃한 두 삼각형이 동시에 포함하거나 둘 다 놓치지 않도록 경계 규칙을 둔다. 흔히 쓰이는 top-left rule은 경계에 정확히 놓인 샘플을 어느 삼각형이 포함할지 정해 겹침이나 틈을 방지한다.

정리

Edge Function은 변의 방향과 픽셀을 향하는 벡터의 외적이다. 외적의 부호는 점이 변의 어느 쪽에 있는지 알려주고, 좌표로 풀면 $Ax+By+C$ 꼴의 식이 된다. 삼각형을 CCW로 두면 각 변에 대해 왼쪽에 있는 샘플, 즉 Edge Function이 모두 0 이상인 샘플을 삼각형 내부로 판정할 수 있다.

외적으로 이해하는 Edge Function

삼각형 래스터라이제이션에서 Edge Function이 점의 위치와 삼각형 내부 여부를 판정하는 원리