자, 이제 우리는 모든 브러쉬에 대해 텍스처 좌표계를 포함하고 있는 올바른 폴리곤을 갖기 위해 올바른 폴리곤을 생성하여야 한다.
CSG가 하는 일은 오버래핑 되어 있는 모든 폴리곤과 다른 브러쉬 내부에 존재하는 폴리곤들을 제거하는 것이다. 이것은 폴리곤의 수를 감소시켜 줄 뿐만 아니라 BSP 트리를 생성하는데 사용되는 지오메트리를 생성하는 일도 한다. .MAP 파일을 사용하는 대부분의 엔진은 BSP 트리를 사용한다. 다음 그림은 CSG가 하는 일을 보여주는 그림이다.
폴리곤들에 대해 CSG를 수행하는 두 개정도의 광범위한 알고리즘이 있다. Laidlaw는 폴리곤 리스트들만을 사용하여 CSG 연산을 수행한다. Naylor는 BSP 트리를 사용하여 CSG연산을 수행한다. BSP 트리는 모든 브러쉬에 대해 생성되고, 그 BSP 트리는 각각에 대해 클리핑 된다. (주 - 여기서는 Naylor 방식을 채택했다. ) 지은이는 Nalyor 방식을 선택했고, 이 상황에 가장 적합한 접근법이라고 믿고 있다. 다음 코드는 “Romoving illegal Geometry from Data imported from Quake MAP files( 퀘이크 맵파일에서 임포팅 한 데이터로부터 비정상적인 지오메트리 제거하기)”라는 튜토리얼과 매우 유사하다.
(http://www.3dtechdev.com/tutorials/illegalgeometry/illegalgeometrytut.html)
지은이의 코드는 해당 튜토리얼에서 아이디어를 얻어서 제작했음.
BSP 트리를 어떻게 생성할 것인가에 대해서는 걱정하지 않도록 하자. 왜냐하면 이 경우에는 불필요 하기 때문이다. CSG에 관한 두 개의 알고리즘 모두다 컨벡스나 컨케이브 둘다에 대해 개발되어 있다. 우리의 경우는 컨벡스인데 이건 굉장한 이점을 가지고 있다. 우리는 bsp 트리에 대한 전반적인 아이디어를 생략할 수 있다. 그 이유는, 만일 어떤 한 점이 브러쉬 안에 들어있는 어떤 폴리곤의 앞쪽(in front of)에 있다면, 그 점은 브러쉬의 외부에 존재한다는 것을 알고 있기 때문이다. (다음 그림 참조)
만일 한 점이 브러쉬에 들어 있는 모든 폴리곤의 뒤쪽에 있다고 한다면, 그 점은 브러쉬의 내부에 있게 된다. 이점은 상당히 스마트한 트릭이다. 어떤 점이든, 선이든, 폴리곤이든 그것들이 브러쉬의 내부에 있는지, 외부에 있는지, 가로지르고 있는지를 결정할 수 있기 때문이다.
CSG 연산에 대한 의사코드는 다음과 같다.
Brush *Brush::CSGUnion ( )
{
ClippedBrushes = CopyList ( ); // Copy the brush array
bool bClipOnPlane;
for i = 0 to NumberOfBrushes – 1
{
bClipOnPlane = false;
for j = 0 to NumberOfBrushes – 1
{
if ( i != j ) // Make sure we don’t clip a brush against itself
{
ClippedBrushes[ i ].ClipToBrush ( Brushes[ j ], bClipOnPlane );
}
else
{
bClipOnPlane = true;
}
}
}
// Brushes is no longer needed
return ClippedBrushes; // ClippedBrushes contains all the correct polygons
}
첫번째로, 브러쉬들의 복사본을 만들어야 한다. 왜냐하면 나머지 복사본이 브러쉬들에 의해 클리핑 되는 동안, 복사본 하나는 브러쉬들을 클리핑 하는데 사용할 것이기 때문이다. 자기 자신에 대해 브러쉬를 클리핑 할 것인지 말것인지를 체크하는 것은 중요하다. 만일 브러쉬가 자신에 대해 클리핑 하지 않을 거라면, 우리는 그 클리핑 할 수 있다. 루프가 완료되면, 브러쉬 배열은 더 이상 필요하지 않다. 클리핑된 브러쉬들의 배열은 올바른 폴리곤 모두를 포함하고 있게 된다. bClipOnPlane은 동일 평면상에 있는 폴리곤을 유지할 것인지 삭제할 것인지에 대한 플래그이다. 만일 동일 평면상에 있는 모든 폴리곤을 유지한다면 같은 영역을 커버링하는 여러 폴리곤들이 있게 될 것이다. 만일 동일 평면상에 있는 모든 폴리곤을 삭제한다면, 폴리곤 누락이 있게 될 것이다.
이 과정을 도식화 해서 이해를 돕기 위해 다음 그림을 보자.
각각에 대해 클리핑 될 두 개의 브러쉬가 있다. 브러쉬 A와 B의 카피본을 만들고 이를 A’, B’라고 하자. 우선, 브러쉬 A’는 브러쉬 B에 대해 클리핑 된다.
다음은 브러쉬 A에 대해 브러쉬 B’가 클리핑 된다.
더 이상 클리핑 할 브러쉬가 없기 때문에 끝나게 된다. A’와 B’그림을 보면 알겠지만, 이것이 올바른 형태이다.
이것이 어떻게 동작하는지는 다음 의사코드를 보면 이해가 갈 것이다. 그렇다 할 지라도 한가지 의문은 남아 있다. 어떻게 브러쉬에 대해 클리핑 할 것이냐 라는 점이다. ClipToBrush는 다음과 같이 동작한다.
void Brush::ClipToBrush ( Brush *pBrush, bool bClipOnPlane )
{
for i = 0 to NumberOfPolygons – 1
{
Polygons[ i ] = Polygons[ i ].ClipToList ( pBrush.Polygons, bClipOnPlane );
}
}
이것은 한 브러쉬가 다른 브러쉬에 대해 어떻게 클리핑 되는지에 관한 단순화된 버전이다. 브러쉬에 있는 각각의 폴리곤은 또 다른 브라쉬에 있는 각각의 폴리곤들에 대해 클리핑 된다. 그 결과로 얻은 폴리곤(클리핑 되서 나온)들은 원래의 폴리곤들을 대체하게 된다. 이게 좀 헷갈리겠지만 참아라. 이 과정을 도식화 시키면 다음과 같다. B에 대해 A’를 클리핑 한다.
B에 대해 클리핑 된 첫번째 폴리곤은 붉은 색으로 표시했다. (붉은 색으로 표시된)이 폴리곤은 B의 폴리곤들 중 어느 하나라도 그것 보다 앞에 있기 때문에, 이 폴리곤은 브러쉬의 외부에 존재하게 된다. A’의 다음 폴리곤으로 옮겨가자.
이제 뭔가 필이 올 것이다. (별다른 설명없이 다음 단계를 계속하자.)
다시 우리는 폴리곤이 브러쉬 B의 외부에 있는 단순한 경우를 만났다. (앞에서 한 것처럼 또 하게 되면) A’는 클리핑 될 것이고 끝나게 될 것이다.
그 다음의 의문점은 어떻게 폴리곤 목록들에 대해 폴리곤이 클리핑 될 것이냐 라는 점이다. 폴리곤의 목록들은 (각각에 대해 클리핑 된 브러쉬들인) 볼록 폴리곤의 덩어리들을(볼록 입방체 정도라고 해야 하나…) 이루고 있는 볼록 폴리곤들의 집합이다. 재귀함수는 폴리곤을 리스트들에 대해 클리핑 할 수 있다. 폴리곤 리스트에 대해 폴리곤을 클리핑하는 함수에 대한 의사코드는 다음과 같다.
Polygon *Polygon::ClipToList ( Polygon *pPolygon, bool bClipOnPlane )
{
switch ( ClassifyPolygon ( polygon ) )
{
case FRONT: // pPolygon is outside this brush
return polygon;
case BACK:
if ( IsLast ( ) ) // pPolygon is inside this brush
{
return NULL;
}
return pNext->ClipToList ( polygon, bClipOnPlane );
case ONPLANE:
double Angle = polygon.normal.Dot ( normal ) – 1;
if ( ( Angle > -epsilon ) && ( Angle < epsilon ) )
{
if ( !bClipOnPlane )
{
return polygon;
}
}
if ( IsLast ( ) )
{
return NULL;
}
return pNext->ClipToList ( polygon, bClipOnPlane );
case SPANNING:
SplitPoly ( polygon, front, back );
if ( IsLast ( ) ) // back must be inside the brush, so only return the front split
{
return front;
}
BackFrags = pNext->ClipToList ( back, bClipOnPlane );// Clip back fragment to see if any of it will survive
If ( BackFrags == NULL )
{
return front;
}
if ( BackFrags == back ) // There is no need to split this polygon, since all of it is in front of the brush
{
return polygon;
}
front.AddPolygon ( BackFrags ); // Add the back fragments to the front list
return front;
}
}
이 함수는 폴리곤의 평면에 대해 클리핑 되고 있는 폴리곤들을 클래시파이(식별)하는 것으로 시작한다. 평면보다 앞에 있는 폴리곤들이라면, 폴리곤들은 바뀌지 않고 리턴된다. 이는 폴리곤들이 브러쉬의 외부에 있기 때문이다. 만일 폴리곤이 평면보다 뒤에 있다면, 이 폴리곤은 리스트에 있는 다음 폴리곤에 대해 클리핑 된다. 그러나 목록의 맨끝에 도달하게 되면, 폴리곤은 브러쉬의 내부에 있게 됨을 의미하며, 이 폴리곤은 삭제 된다.
만일 평면상에 폴리곤이 있다면, 이것은 목록에서의 다음 폴리곤에 의해 클리핑 되야 할 필요가 있다. 앞의 조각은 확실히 유효하지만, 뒷 부분 조각은 목록의 다음 폴리곤에 의해 클리핑 되어야 한다. 만을 목록의 맨 끝에 도달하게 되면 앞 부분만이 반환 될 것이다. 이는 뒷 부분은 브러쉬의 내부에 있기 때문이다. 만일 뒷부분이 (폴리곤) 목록의 나머지에 대해 클리핑 된 후에 아무 것도 반환되지 않는다면, 이는 뒷 부분이 브러쉬 내부에 있고, 앞 부분은 반환되었음을 의미한다. 만일 뒷 부분조각을 클리핑 한것으로부터 반환된 폴리곤들과 뒷 부분조각이 같다면, 이것은 폴리곤을 쪼개는 일이 불필요 함을 의미한다. 다음 그림을 봐라.
여기서 필자는 폴리곤 목록을 사용하는데 있어서 때로는 배열로, 때로는 링크드 리스트로 사용한다. 루프문에선 배열을 사용하는게 더 쉽고, 반면에 폴리곤 목록에 item을 추가할 때, 데이터 하나 추가자하자고 배열을 재 할당하는 것보다는 링크드 리스트에 추가하는게 더 쉽다.
'Coding > Game Programming' 카테고리의 다른 글
| .MAP 파일로 만드는 BSP (7) - 평면에 대해 폴리곤 판별하기 (0) | 2010.12.22 |
|---|---|
| .MAP 파일로 만드는 BSP (5) - 버텍스 소팅하기 (0) | 2010.11.25 |
| .MAP 파일로 만드는 BSP (4) - 텍스처 좌표 계산하기 (0) | 2010.11.25 |
| .MAP 파일로 만드는 BSP (3) - 맵 파일 구조 (1) | 2010.11.18 |
| .MAP 파일로 만드는 BSP (CSG 이용) (2) - 브러쉬를 폴리곤으로 바꾸기 (0) | 2010.11.18 |
