[게임 수학] #13 | 삼각형(Triangle)

 *인프런 <게임 엔진을 지탱하는 게임수학, 이득우 교수님> 강의를 듣고 공부한 글입니다.

 

 

1. 세 점의 아핀 조합 (Affine combination of Three points)

이전에 두 점의 아핀 조합에서 계수의 합이 1이 되어야 한다는 걸 봤었습니다. 우리가 설정한 아핀 공간 내 규칙을 어기지 않으려면 마지막 차원의 값이 1이 되어야 하기 때문이었죠. 이러한 개념은 세 점의 아핀 조합으로 확장되어도 똑같이 적용됩니다.

 

$$ P' = s \cdot P_1 + t \cdot P_2 + (1-s-t) \cdot P_3 $$

 

위 식의 계산 결과는 항상 아핀 공간의 점을 보장 받게 되는 것이죠. 위의 식을 변형하여 다음과 같은 공간 형태로 나타낼 수도 있습니다.

 

$$ P' - P_3 = s(P_1 - P_3) + t(P_2 - P_3) $$

$$ \rightarrow \  \vec{w} = s\vec{u} + t\vec{v} $$

 

점 \(P_3\) 에서 시작하는 총 3개의 벡터가 위 식에 포함되어 있습니다. 우리는 어떤 두 2차원 벡터가 선형 독립이라면 평면을 만든다는 사실을 알고 있습니다. \(\vec{u}, \ \vec{v} \) 가 2차원 벡터이고 선형 독립이라면, 위 식을 통해 같은 평면 상에 존재하는 모든 점을 만들 수 있습니다.

 

그리고 계수의 범위를 0 이상 1 이하로 제한하면, 두 점을 이은 선분이 생성된다고 했었죠? 위 식에는 세 개의 점이 존재하고, 각 계수들의 범위를 \( 0\leq s\leq 1, \ 0 \leq t \leq1, \ 0 \leq (1-s-t) \leq1 \) 와 같이 제한하여 선분을 긋게 되면 우리가 익숙하게 봤던 모형이 나타나게 됩니다.

 

바로, 삼각형입니다.

 

삼각형

 

이와 같이, 아핀 조합에서 모든 계수의 크기가 0 이상 1 이하인 경우, 형상화 할 수 있는 물체의 범위가 만들어지고, 그것을 컨벡스 조합(Convex Combination)이라고 합니다. 아핀 조합에서 계수 \( c_i \) 의 범위를 \(0 \leq c_i \leq 1 \) 로 제한한다는 추가 조건만 붙으면 됩니다.

 

$$ \sum_{i = 0}^n c_i \cdot P_i $$

$$ 단, \ \sum_{i = 0}^n c_i = 1, \ 0 \leq c_i \leq 1 $$

 

 

볼록(Convex)과 오목(Concave)

돋보기를 알고 있다면 위의 두 단어는 흔히 들어봤을 겁니다. 볼록 렌즈와 오목 렌즈를 이야기 할 때에 말이죠. 하지만 볼록하다와 오목하다라는 표현은 수학에서 사용하기에는 개념이 명확하지 않습니다. 수학에서 사용하려면 좀 더 명확한 기준이 필요하죠. 

 

수학에서 볼록과 오목은 다음과 같이 규정할 수 있습니다. 어떠한 영역 내에서 임의의 두 점을 선택하여 연결했을 때, 

• 두 점을 이은 선분의 결과가 해당 영역 안에 항상 속한다.  👉🏻  볼록(Convex)
• 두 점을 이은 선분의 결과가 해당 영역 밖을 나간다.  👉🏻  오목(Concave)

 

볼록과 오목

 

위와 같은 개념으로 비추어 봤을 때, 삼각형은 볼록함(Convexity, 영역 내에서 임의로 연결한 점이 해당 영역을 벗어나지 않는 성질)을 가지고 있기에 대표적인 볼록(Convex)한 도형 영역이라고 볼 수 있습니다.

 

볼록한 도형인 삼각형

 

 

네 점의 컨벡스 조합

점을 한 개 더 추가하면 어떤 모형이 나오게 될까요?

 

$$ P'=a\cdot P_1+b\cdot P_2 + c\cdot P_3 + (1-a-b-c)\cdot P_4 $$

$$ \vec{x}=a\vec{u}+b\vec{v}+c\vec{w} $$

 

네 점의 컨벡스 조합을 통해 만들어지는 각 벡터가 선형 독립인 경우, 벡터가 3개이기 때문에 어떤 3차원 공간에 속한 점들을 무한히 만들 수 있을 겁니다. 이 때에도 마찬가지로 각 계수들의 범위를 0 이상 1 이하로 설정해주면 물체의 형상이 만들어 질 것이고, 그것은 다음과 같은 사면체의 모습이겠지요.

 

네 점의 컨벡스 조합으로 형성된 사면체

 

이렇게 두 점을 조합해서 선분, 세 점을 조합해서 삼각형, 네 점을 조합해서 사면체와 같은 컨벡스한 영역들을 만들었습니다. 이러한 컨벡스 도형들을 활용해 실제 현실과 유사한 3차원 공간에서의 물체를 표현하게 되는데, 이때 사용하는 대표적인 자료구조가 메시(Mesh)입니다.

 

 

---

2. 메시(Mesh)의 구조

앞서 설명한 선분, 삼각형, 사면체 등의 컴벡스 영역 중, 가장 효과적으로 활용할 수 있는 도형은 삼각형입니다. 1) 2차원 영역 표현이 가능하고, 2) 3차원도 2차원 표면을 조합하여 표현이 가능하기 때문이지요. 

 

삼각형으로 표면을 형성해 만든 의자

삼각형으로 표면을 형성해 만든 돌고래

 

이렇게 3차원 물체들은 결국 많은 삼각형들이 모여 형성된 집합이라고 볼 수 있는데, 이러한 정보들을 저장한 자료구조를 메시(Mesh)라고 하는 것입니다. 메시는 정점(Vertex)과 삼각형(Triangle) 정보를 별도로 구성하는 삼각형 리스트(Triangle List)라는 방식을 사용하여 데이터를 저장하게 되죠.

 

 

삼각형 리스트(Triangle List)

정점 정보만을 모아두는 정점 버퍼와 삼각형 정보만을 모아두는 인덱스 버퍼를 통해, 삼각형을 관리하는 방식입니다.

예를 들어, 사각형은 삼각형 두 개로 구성할 수 있고, 이는 다음과 같이 설계할 수 있습니다.

 

 

각 점에 대한 정보는 정점 버퍼에서 가져오고, 이를 이루는 삼각형에 대한 정보는 인덱스 버퍼에서 가져옵니다. 인덱스 버퍼에서 삼각형 0번에 해당하는 정점들은 (0, 1, 2)이고, 삼각형 1번에 해당하는 정점들은 (0, 2, 3)이며, 이들을 그리는 순서 또한 있는 것을 볼 수 있습니다.

 

이와 같은 방식을 통해, 삼각형이 맞닿아 겹쳐서 중복되는 정점이 생기지 않도록 관리할 수 있습니다. 그리고 이러한 삼각형마다 점을 연결하고 선을 그려, 메시를 형상화 한 결과 화면을 와이어프레임(Wireframe)이라고 부릅니다.

 

 

---

3. 무게중심 좌표 (Barycentric Coordinate)

세 점에 대한 아핀 조합 식에서, 3개의 계수를 조합해 생성한 좌표 \((s, \ t, \ 1-s-t) \) 를 무게중심 좌표라고 합니다.

 

$$ P' = s \cdot P_1 + t \cdot P_2 + (1-s-t) \cdot P_3 $$

 

그렇다면, 무게중심 좌표는 어떻게 계산하는 걸까요? 예제를 한 번 봅시다.

 

 

위와 같이, 점 \(P_1, \ P_2, \ P_3 \) 로 이루어진 삼각형과 동일한 평면 위에 점 \(P_4\) 에 대한 무게중심 좌표를 구하는 방법은 다음과 같습니다.

 

$$ \vec{w} = s \cdot \vec{u} + t \cdot \vec{v} $$

 

위 식의 양변에 \(\vec{u}, \ \vec{v} \) 를 각각 내적하여 2개의 방정식을 만듭니다.

 

$$ \vec{w} \cdot \vec{u} = s(\vec{u} \cdot \vec{u}) + t(\vec{v} \cdot \vec{u}) \ \ \ \ \ \ ... (1) $$

$$ \vec{w} \cdot \vec{v} = s(\vec{u} \cdot \vec{v}) + t(\vec{v} \cdot \vec{v}) \ \ \ \ \ \ ... (2) $$

 

(1)식에 \( (\vec{u} \cdot \vec{v})\) , (2)식에 \( (\vec{u} \cdot \vec{u}) \) 를 곱해줍니다.

 

$$ (\vec{w} \cdot \vec{u})(\vec{u} \cdot \vec{v}) = s(\vec{u} \cdot \vec{u})(\vec{u} \cdot \vec{v}) +t(\vec{u} \cdot \vec{v})(\vec{u} \cdot \vec{v}) \ \ \ \ \ \ ...(1a)  $$

$$ (\vec{w} \cdot \vec{v})(\vec{u} \cdot \vec{u}) = s(\vec{u} \cdot \vec{v})(\vec{u} \cdot \vec{u}) + t(\vec{v} \cdot \vec{v})(\vec{u} \cdot \vec{u}) \ \ \ \ \ \ ...(2a) $$

 

\((1a) - (2a)\) 를 통해 소거법을 진행해주면, \(s(\vec{u} \cdot \vec{u})(\vec{u} \cdot \vec{v})\) 가 제거되고, \(t\) 에 대해 식을 정리해주면 다음과 같습니다.

 

$$ t = \frac{(\vec{w} \cdot \vec{u})(\vec{u} \cdot \vec{v}) - (\vec{w} \cdot \vec{v})(\vec{u} \cdot \vec{u})}{(\vec{u} \cdot \vec{v})^2 - (\vec{v} \cdot \vec{v})(\vec{u} \cdot \vec{u})} $$

 

이번에는 (1)에 \((\vec{v} \cdot \vec{v})\) 를, (2)에 \( (\vec{v} \cdot \vec{u}) \) 를 곱해주고, \(t\) 를 소거해주면, \(s\) 에 구할 수 있습니다.

 

$$ s = \frac{(\vec{w} \cdot \vec{v})(\vec{u} \cdot \vec{v}) - (\vec{w} \cdot \vec{u})(\vec{v} \cdot \vec{v})}{(\vec{u} \cdot \vec{v})^2 - (\vec{v} \cdot \vec{v})(\vec{u} \cdot \vec{u})}$$

 

이렇게 구한 \(s, \ t\) 값을 통해 무게중심 좌표 \( (s, \ t, \ 1-s-t)\) 를 구할 수 있습니다. 이렇게 구한 각 좌표값이 모두 0 이상 1 이하를 만족한다면, 삼각형 내부에 있는 점이라는 걸 보장할 수 있습니다. 이를 활용하여, 삼각형 내부 영역을 색칠하는 등에 응용할 수 있습니다.