.MAP 파일로 만드는 BSP (CSG 이용) (2) - 브러쉬를 폴리곤으로 바꾸기

2-1.     브러시를 폴리곤으로 바꾸기

 

일단 엔터티 목록이 메모리에 저장되면, 첫번째 작업은 브러시들을 폴리곤들로 변환하는 것이다.
여기에는 두 가지 방법이 있다.

 첫 번째로는 3개 평면 교차법이다. 이 방법은 빠르고 상대적으로 적은 코드를 필요로 한다.

두 번째로는 모든 face(면)들의 평면(plane)을 따라 거대하고 잠재적인 폴리곤들을 만드는 방법이다. 그리고 나서 각각에 대해 그 폴리곤들을 클리핑 하는 방법이다. (이 글을 쓴 사람은 개인적으로 이 방법을 싫어하기 때문에 3 평면 교차법을 사용한다. )

 

폴리곤을 브러시로 바꾸는 pseudo 코드는 다음과 같다.

 

face들은 브러시안의 모든 face에 대한 배열로 한다.

폴리곤은 배열로 만드는데, 이 폴리곤들은 많은 수의 face들을 가지고 있다.

For i = 0 to NumberOfFaces – 1

{

For j = 0 to NumberOfFaces – 1

{

For k = 0 to NumberOfFaces – 1

{

if ( i != j != k )

{

Polys[ i ].AddVertex ( GetIntersection ( i, j , k ) );

}

}

}

}

 

필자가 3개 평면의 교차를 계산하는 함수는 GetIntersection 함수를 생략했기 때문에 자세한 사항은 대충 넘어가도록 한다.(뭥미, 이사람 -_-) 또한 이 버전은 전혀 최적화되어 있지 않다. 마지막으로 나중에 보여줄 문제점 하나가 여전히 존재한다. 작업 방법은 하나의 교차에 대해 3개 면의 모든 조합을 체크하는 것이다. 그 결과 버텍스는 교차하는 평면에 해당하는 폴리곤에 저장된다. 3면이 교차하는 공식은 다음과 같다.

(공식 참조)

 

각각의 평면은 노말 n과 원점에서 평면까지의 거리 d로 구성되어 있다. 이 값들은 평면의 방정식으로부터 뽑아낼 수 있다. (좀 더 간단하게는 n dot x + d = 0)

만일 분모가 0이면 아무것도 교차하지 않는다(평면들은 평행하다)

3 평면이 교차하는 것을 발견하는 pseudo 코드는 다음과 같다.

 

bool GetIntersection ( n1, n2, n3, d1, d2, d3, &p )

{

double denom = n1.Dot ( n2.Cross ( n3 ) );

if ( denom == 0 )

{

return false;

}

p = -d1 * ( n2.Cross ( n3 ) ) – d2 * ( n3.Cross ( n1 ) ) – d3 * ( n1.Cross ( n2 ) ) / denom;

return true;

}

 

만일 교차가 일어난다면 해당값을 세팅하고 true 값을 반환하고 그렇지 않으면 false를 반환한다.

3 평면 교차법을 사용할 때 반드시 해결해야 하는 일반적인 캐치점이 있다. 다음 상황을 살펴보자.

 

 

3개의 평면이 교차하기 때문에 (다각형 외부에) 여분의(별도의) 한 점이 생기게 된다. 불행히도 이 점은 오브젝트의 일부가 아니다. 교차되는 첫 번째 평면은 수평라인이다. 두 번째 평면은 대각선이다. 세 번째 평면은 이 그림이 2d라서 보이지는 않는다. 그렇다 하더라도 교차가 존재하고, 점은 오브젝트 외부에 생기게 된다. 이 오류가 생기는 이유는 오른쪽에 대해 수직인 평면이 교차 테스트에 사용되지 않기 때문이다. 위 그림을 3차원으로 한번 보자.

 

 

노란색 선이 우리가 원하는 모델을 보여주고 있다. 붉은 선은 잘못된 교차점이 어디에 생기는지를 보여주고 있다. 

 

자, 이제 문제를 이해했을 것이며 해결책을 알려주도록 하겠다.

새로 생성된 폴리곤에 점을 추가하기 전에 오브젝트 외부에 점이 있는지에 대해 테스트 해야 한다. 이러한 테스트는 모든 브러시들이 볼록폴리곤(컨벡스)이기 때문에 쉽게 할 수 있다. 이는 브러시에서 어떤 점이라 할지라도 (어떤) 평면 앞에 놓이게 된다면 이는 해당 모델의 밖에 있다는 것을 의미한다. 이는 모든 컨벡스 브러시에 대해서 진리다. 개선된 pseudo 코드는 다음과 같다.

 

for i = 0 to NumberOfFaces – 1

{

for j = 0 to NumberOfFaces – 1

{

for k = 0 to NumberOfFaces – 1

{

if ( i != j != k )

{

illegal = false;

newVertex = GetIntersection ( i, j , k );

for m = 0 to NumberOfFaces – 1

{

if ( DotProduct ( Faces[ m ].normal, newVertex ) + Faces[ m ].d > 0 )

{

illegal = true;

}

}

if ( illegal == false )

{

Polys[ i ].AddVertex ( newVertex );

}

}

}

}

}

 

비록 이것이 데이터 구조에 의존적이라 할 지 라도, 이렇게 하면 최적화를 위한 여지가 생긴다. 이에 대한 아이디어는 가능한 한 모든 조합에서 다른 모든 면(face)들에 대해 각 면(face)을 체크하는 대신에 0부터 NumOfFaces-3까지 모든 면들에 대해 실행하는 첫 번째 루프를 가지는 것이다.

다른 두개의 루프는 i부터 NumOfFace-2와 j부터 NumOfFace-1까지 실행하는 루프들이다. 한번에 하나의 폴리곤에 새로운 버텍스를 추가하는 대신에, 한번에 세 다각형 모두에 추가할 수 있게 된다. 좀 더 최적화된 코드는 다음과 같다.

 

For i = 0 to NumberOfFaces – 3

{

For j = i to NumberOfFaces – 2

{

For k = j to NumberOfFaces – 1

{

if ( i != j != k )

{

legal = true;

newVertex = GetIntersection ( i, j , k );

 

for m = 0 to NumberOfFaces – 1

{

// Test if the point is outside the brush

if ( DotProduct ( Faces[ m ].normal, newVertex ) + Faces[ m ].d > 0 )

{

legal = false;

}

}

if ( legal )

{

Polys[ i ].AddVertex ( newVertex ); // Add vertex to

Polys[ j ].AddVertex ( newVertex ); // 3 polygons

Polys[ k ].AddVertex ( newVertex ); // at a time

}

}

}

}

}

 

브러시로부터 폴리곤을 어떻게 얻는가를 다 포함하고 있다. 각 버텍스에 대해 텍스처 좌표계를 계산하는 것은 다음 단계이다.