.MAP 파일로 만드는 BSP (5) - 버텍스 소팅하기

모든 버텍스에 대해 텍스처 좌표계를 가지고 있는 유효한 다각형을 구했다면 이미 꽤 온 것이다. 그러나 현재 버텍스들은 순서가 랜덤으로 되어 있다. Back face culling(은면제거)의 장점을 이용하려면, 각 폴리곤의 버텍스들은 시계방향 또는 반 시계방향으로 소팅 되어야 한다. (여기 필자는 폴리곤이 반시계 방향으로 컬링되게 하기 위해서 시계방향으로 소팅하는 걸 더 선호한다. 아울러 DX를 이용하여 렌더링 할거면 시계방향으로 소팅해야 한다.) 이 방법을 간단하게 약간만 조정하면 반시계 방향으로 버텍스를 소팅할 수도 있다. 버텍스를 소팅하기 위하여, 폴리곤의 노말을 이미 알고 있어야 한다. 폴리곤을 통하여 face의 노말은 쉽게 얻을 수 있기 때문에 이건 쉽다.

우선, 폴리곤의 센터(중심)를 계산해야 한다. 이건 버텍스들의 평균을 내면 된다.

의사코드는 다음과 같다.

Point center;

for n = 0  to NumberOfVertices – 1

{

center += vertices[ n ];

}

center /= NumberOfVertices;

 

앞서 말한대로, 폴리곤의 중심을 사용하면 현재 버텍스에 대해 가장 작은 각을 가지는 버텍스를 찾을 수 있다. 이걸 세번째 버텍스에서 마지막 버텍스에 이르기까지 반복해서 한다. 다음 그림이 우리가 해야 할 것이다.

q는 가장 작은 각이다. 버텍스 1에 대해 가장 작은 각을 가진 버텍스는 2이다. 버텍스2에 대해 가장 작은 각을 가지는 버텍스는 3이다. 이제 소팅된 버텍스의 목록은 0, 1, 2, 3이 되는 것이다.  이제 버텍스 4만이 남았고, 따라서 이게 맨 마지막이 될 것이다.

이게 이해하기 쉬울지라도 이걸 어떻게 수학적으로 구현할 것인가. Dot 프로덕트는 두 벡터 사이의 각을 이용한다. 두 벡터 사이의 각을 계산하기 위해서 여기 또 다른 그림이 있다.

우리는 A 벡터와 b 벡터를 찾아내야 한다. 이것은 버텍스 0과 1과 중심( c )을 가지고 빼기를 이용하여 구한다. 그 결과인 a 벡터와 b 벡터는 노멀라이즈 되야 한다. 이 모든 것을 수학적으로 표현하면 다음과 같다.

노멀라이즈 된 a와 b벡터의 도트 프로덕트 결과는 -1과 1 사이의 숫자로 나올 것이다. -1은 두 벡터 사이의 각이 180도 라는 것을 의미한다. 0은 두 벡터 사이의 각이 90도이다. 1은 0도이다. 각을 구하려면 노멀라이즈 된(정규화된) 두 벡터 a와 b, 그리고 A를 이용한다.

불행히도, 이 메소드가 fail이 날 경우가 있다. 이 문제를 제거하려면 아무리 해도 다음에 올 수 없는(위치할 수 없는) 버텍스들은 건너띄는 것이다. 우선 문제가 되는 경우를 보여주겠다.

 

인 경우 잘못된 버텍스가 선택된다. 이 문제에 대한 해결책은 a 벡터로부터 180도가 넘는 모든 버텍스를 생략하는 것이다. 벡터의 도트 프로덕트 결과가 0부터 180도 사이가 나오기 때문에, 이 연산을 사용해서는 문제를 해결할 수 없다. (우리가 필요한 것은 360도 전체 범위이다)

그러나 a 벡터상에 있고 폴리곤 노멀을 따라 위치하는 평면을 생성하므로써 가능하게 된다. 이 평면은 폴리곤 평면에 수직이다. (해당 평면) 버텍스보다 아래에 있는 모든 점들은 다 생략(스킵)한다. 스킵되지 않은 점들은 a벡터로부터 0과 180도 이내에 위치할 것이다. 이해를 돕기 위해 2d로 그림을 그리면 다음과 같다.

회색영역에 있는 점들은 a벡터로부터 180도가 넘는 범위에 해당하므로 다 스킵된다. 확신할 수는 없지만 이 메소드는 볼록 폴리곤에 대해서만 잘 동작할 것 같다. 전체 알고리즘은 의사코드로 다음과 같다.

 

 

버텍스들이 소팅되었다 할지라도, 여전히 올바른 순서대로 있지는 않다. 그 이유는 이 코드는 폴리곤이 직면하고 있는 (예를 들면 노멀과 같은) 문제를 고려하지 않기 때문이다. 만일 폴리곤이 뒷면이라면 버텍스는 잘못된 순서로 놓여질 것이다. 이것은 다음 의사코드를 사용하면 체크할 수 있다. 

CalculateNormal 은 주어진 버텍스 집합의 노멀을 계산할 것이다. ReverseVertexOrder는 버텍스 집합의 순서를 역으로 바꿀 것이다. 여기서 필자는 시계 방향에서 버텍스를 소팅하는 함수를 만들었다. 소스코드에서 그 함수는 SortVerticesCW이다.