All Right ?

[Chapter 6]

 BSP-tree에 기반을 두는 3D엔진을 개발할 때 매우 흥미로운 문제들중 하나가 충돌 체크입니다. 이것을 매우 빠르게 처리해야 하지만 그만큼 어려운 것은 아닙니다. FPS게임에서 대부분의 프로세서 타임은 충돌체크를 할때 소비됩니다. 월드를 돌아다니는 오브젝트나 아바타를 생각해 봅시다. (이제부터 아바타도 오브젝트로 생각하겠습니다.) 오브젝트는 기하 요소들과 다른 오브젝트들에 대하여 이들을 통과하진 않는지 혹은 너무 가까이 있지 않은지 따져봐야 합니다. 하나의 아바타나 오브젝트는 이런 체크를 느린 알고리즘을 통해서도 수용할 만한 프레임으로 처리할 수 있습니다. 문제는 여러개의 오브젝트들과 아바타들을 다뤄야만 할때 매우 복잡해 진다는 것입니다. 화면에 월드를 렌더링하는 것은 프렘당 한번만 하면 되지만 충돌 체크는 현재 월드에서 움직이는 오브젝트의 개수에 따라서 프레임당 수백번을 필요로 할지 모릅니다. 따라서 충돌 체크 알고리즘을 매우 빠르게 하는 것은 아주 중요합니다.

 충돌을 다루는 알고리즘을 설계하기에 앞서 몇 가지 결정을 할 필요가 있습니다. 오브젝트들은 반드시 하나 또는 그 이상의 간단한 기하 도형들로 캡슐화해야 합니다. 왜냐하면 오브젝트에 있는 모든 폴리곤 하나하나를 다른 모든 것들과 체크하면서 수용할 만한 프레임율을 얻는 것은 불가능 하기 때문입니다. 저는 각각의 오브젝트를 xz평면에서 하나의 반지름과 y축으로 하나의 반지름을 가지는 타원체로 캡슐화하기로 선택했습니다. 만약 여러 개의 도형을 선택한다면 이들이 서로 상호작용하게 만들어야 할 필요가 있는데 이것은 매우 복잡한 문제입니다. 아래 예제는 사람을 캡슐화한 것입니다.

<Figure 16. A Human Encapsulated in an ellipsoid>

 그리고 나서 오브젝트가 어떤 것과 충돌했을 때 무슨 일이 일어날지 결정할 필요가 있습니다. 한 가지는 충돌이 감지되면 움직임을 멈추고 원래의 자리에 머무르게 하는 것입니다. 이것은 벽에서 튕기는 것과 같은 매우 나쁜 행동을 보여줍니다. 아래 그림의 두 이동은 같은 거리를 이동합니다. a의 위치로 이동하는 것은 금지되어 제자리에 머물게 될 것입니다. 그러나 b의 위치로 이동하는 것은 가능합니다. 이는 만약 벽을 따라 움직이게 되면 벽에 매우 가까이 갈수 있다는 것을 의미 합니다. 반면에 벽을 향해 직선으로 움직이는 것은 훨씬 그 이전에 금지될 것입니다. 따라서 오브젝트들은 벽에서 튕겨지게 됩니다.

<Figure 17. Prohibited and allowed move>

 위의 그림에서 a로 이동하는 것은 허락되지 않지만 b로 이동하는 것은 허락됩니다. 이 아이디어의 또 다른 약점은 오브젝트들이 벽에 붙은 것과 같이 움직일 것이라는 겁니다. 왜냐하면 오브젝트들이 벽을 따라 이동하려 할 수록 벽에 붙게되기 때문입니다.

 보다 좋은 방법은 오브젝트들이 벽이나 다른 오브젝트들에 대해서 미끄러지게 처리하는 것입니다. 이것이 비록 덜 효율적인 처리이지만 결과가 많이 부드러울 것입니다. 이것이 제가 선택한 방법입니다.

 오브젝트의 이동은 다음과 같이 세 부분으로 나눌 수 있습니다.

1. 다음 위치 계산
2. 충돌 체크
3. 충돌 핸들링

 매 프레임 마다 월드에서 움직이는 오브젝트는 이와 같은 단계를 거쳐야 합니다.

- Future Position Calculation -

 오브젝트의 원래 위치, 속도, 가속도, 방향, 현재 마찰 계수 그리고 흐른 시간이 주어진 상태에서 오브젝트의 다음 위치를 계산하는 것은 매우 쉬운 부분입니다. 우리는 계산에서 미터와 초단위를 사용하며 오브젝트의 질량은 무시합니다. 모든 오브젝트의 질량이 1임을 가정합니다. 간단히 하기 위해 중력은 항상 아래로 작용하고 힘은 xz평면에서만 작용한다는 것을 가정합니다. 다음 단계들이 오브젝트의 다음 위치를 구하는 우리의 해법입니다.

1. 마찰로 인한 속도 감소를 뺍니다. xz평면위의 가속도에서 마찰 계수(0.0, -1.0)를 뺍니다. 질량이 1임을 가정했기에 더 이상의 계산은 필요하지 않습니다.

Formula:
Acceleration(x,z) -= Friction

2. 사용자로 부터의 힘을 x,z방향의 가속 벡터에 더합니다. 사용자에 의해 더해진 힘과 프레임 시간을 곱하고 x,z 방향의 결과 벡터를 가속 벡터에 더합니다. 질량이 1이라고 생각하므로 힘의 단위는 Newton/kg 입니다.

Formula:
Acceleration(x,z) += Force * Normalize (Direction(x,z))

3. y 방향으로 중력 가속도를 정합니다. 전통적으로 사용되는 중력값은 9.82이나 게임에서 이렇게 하면 추락이 매우 빨라서 재미가 없기 때문에 이보다 낮은 중력값을 사용하는 것이 일반적입니다.

Formula:
Acceleration(y) = -Gravity

4. 이동 벡터에 가속 벡터를 더합니다. 이것은 x,z 방향의 가속에 프레임 타임을 곱한 것을 더하면 됩니다. x,z 방향으로 이동 속도를 제한하는 것은 좋은 생각입니다. 그러면 오브젝트들은 언젠가 최대 속도에 달하게 됩니다. 그렇지 않으면 계속적인 힘의 작용으로 오브젝트의 가속이 무한대로 가게 될 수 있습니다.

Formula:
Movement = Movement + Acceleration * FrameTime

5. 이제 이번 프레임에서의 위치 변경자를 계산해야 합니다. 프레임 타임과 이동 벡터를 곱하면 결과 벡터는 이번 프레임에서 오브젝트가 가야할 거리입니다.
 

Formula:
Distance = Movement * FrameTime

6. 이제 예상 위치를 계산할 수 있습니다. 현재 위치에 가야될 거리를 더하면 이번 프레임에서 오브젝트가 가야할 좌표가 나옵니다. 이 값은 모든 충돌 체크에 쓰일 것입니다.

Formula:
NewPosition = Position + Distance

자 인제 이 예상 위치가 유효한 위치인지 체크할 시간입니다.

- Collision Detection and Collision Handling -

 이것은 BSP-tree 엔진에서 가장 트릭적인 부분입니다. 물리 엔진에서 이 부분을 설계 할때는 몇 가지 고려해야할 것들이 있습니다. 무엇보다도 효율성이 가장 중요한데 이는 이 부분이 프로세서 타임을 대부분 독차지하기 때문입니다. 두번째는 충돌 체크의 정확성으로 매우 중요한 부분입니다. 알고리즘의 효율성을 감소시키지 않고 좋은 정확성을 얻기는 매우 어렵습니다. 따라서 정확성과 효율성 사이에 트레이드오프(trade-off)가 존재하게 됩니다. 충돌 핸들링은 이 만큼 어렵지 않지만 중요한 부분입니다. 왜냐하면 이것이 올바른 "느낌"을 주는 것으로 부족한 핸들링은 어떤 게임이든 보기 안좋게 만들 것입니다.

 여기가 BSP-trees의 힘을 보여주는 부분입니다. 대부분의 엔진들은 BSP-tree를 렌더링 속도를 높이기 위한 포탈 엔진들처럼 사용하지 않습니다. 하지만 아직도 대부분의 엔진들은 이런 기하하적 요소와 상관없이 BSP-tree를 만듭니다. 왜냐하면 충돌 체크 계산에서 대단한 이점이 있기 때문입니다. 말하자면 사용자를 BSP-tree에 위치시키는 것은 매우 쌉니다. 이렇게 하고 나서 체크가 필요한 폴리곤은 그 프레임에서 트리를 타고 내려온 오브젝트가 위치한 리프 노드에 있는 폴리곤들 뿐입니다.

 BPS-tree에서 또 다른 강점은 원래의 BSP-tree의 설계대로 각각의 리프 노드가 볼록 집합(convex set)인 폴리곤들 가지고 있다는 것입니다. 이는 어떤 순서로든 폴리곤들의 충돌을 체크할 수 있다는 의미입니다. 만약에 우리의 BSP-tree와 같이 볼록 집합이 아니라면 폴리곤들은 뱡항의 순서에 따라서 체크되어야만 합니다. //  정적인 오브젝트들을 추가되면 리프 노드의 폴리곤들이 볼록 집합이라고 할 수 없습니다. 5장에서 언급된 내용. // 우리는 방향값(facing value)이라는 것을 사용하는데 이는 비교되는 오브젝트에 대해 폴리곤이 어떻게 위치해 있는가를 말하는 값입니다. 이 값은 폴리곤의 법선 벡터와 오브젝트의 정규화된(normalized) 이동 벡터를 내적하여 얻을 수 있으며 -1과 1 사이의 값입니다. -1값은 폴리곤이 오브젝트가 이동하려는 방향에 정면을 향해 있다는 것이고 1값은 폴리곤이 오브젝트가 이동하려는 방향과 같은 쪽으로 향해 있다는 것을 의미합니다.

 테스트 순서는 가장 작은 방향값을 가지는 폴리곤에서 가장 높은 값을 가진 폴리곤 순서대로 체크합니다. 이어지는 그림들이 왜 이런 순서대로 체크해야만 하는지를 보여줍니다.

<Figure 18. Object move>

 위 그림에서 방향값이 작은 폴리곤은 폴리곤1 입니다. 왜냐하면 오브젝트의 이동 벡터와 폴리곤1의 법선벡터와의 내적이 폴리곤2와의 내적값보다 작기 때문입니다. 따라서 만약에 우리가 폴리곤2에 대해 먼저 체크를 한다면 결과는 다음과 같이 됩니다.

<Figure 19. Incorrect collision>

 위 그림은 폴리곤2와 충돌하지 않는 그림입니다. 최종 위치가 조정되어 그 결과 폴리곤2와 충돌하지 않게 됬습니다. 이 결과는 오브젝트가 폴리곤1을 통과했다는 느낌을 받게 합니다. 만약에 폴리곤1을 먼저 체크한다면 결과는 다음과 같이 됩니다.

<Figure 20. Correct collision>

 20번 그림에서 움직임이 보다 정확하게 조정되었습니다. 이는 폴리곤1과 먼저 체크하여 충돌하지 않게 만들었기 때문입니다. 최종 위치는 조정되어 폴리곤1과 충돌하지 않습니다.

 BSP-tree가 오직 볼록 집합들만을 가질때는 같은 노드에 있는 폴리곤들을 이와 같이 정렬시킬 필요가 없습니다. 하지만 여전히 노드들은 그들이 통과된 순서대로 검색되어져야 합니다.

 충돌 체크 알고리즘을 더욱 빠르게 하기 위해서, 테스트가 필요한지를 미리 가볍게 테스트하여 많은 양의 폴리곤들을 무시할 수 있습니다. 이것은 사이드 값(side value)이라고 불리는 것을 계산함으로써 이루어집니다. 사이드 값은 오브젝트의 중앙과 폴리곤이 놓인 면과의 거리를 뜻합니다. 다음 그림에서 보다 잘 표현됩니다.

<Figure 21. Side value.>

 21번 그림에서 점선의 길이가 바로 사이드 값입니다. 폴리곤에서 멀리 떨어져 있을 수록 사이드 값은 커지게 됩니다.

 사이드 값이 계산되면 오브젝트가 폴리곤을 통과하게 되는지를 판단할 수 있습니다. 사이드 값을 구하기 위해서는 면 다항식에 오브젝트의 위치를 넣으면 됩니다. 하지만 면 방정식에서 거리값은 더해지는 대신에 빼야합니다. 이런 식으로 우리는 오브젝트와 평면사이의 거리를 얻게 됩니다. 시작과 끝 위치에서의 사이드 값들을 계산하여 오브젝트가 면을 통과하는지 아닌지 알수 있습니다

 여기서 문제가 하나 있습니다. 우리가 오브젝트를 하나의 타원체로 선택했기 때문에 폴리곤의 법선 방향으로 오브젝트의 충돌 반지름(collision radius)을 계산해야 합니다. 이를 위해서 폴리곤의 법석 벡터의 x,z 성분은 오브젝트의 xz 충돌 반지름과 곱해지며 폴리곤의 법선 벡터의 y성분은 오브젝트의 y 충돌 반지름과 곱해집니다. 결과 벡터의 길이가 폴리곤과 오브젝트에 대한 충돌 반지름이 됩니다. 다음 그림과 식이 충돌 반지름에 대해 잘 나타내고 있습니다.

<Figure 22. Collision radius.>

 위의 그림에서 점선이 폴리곤을 향하는 오브젝트의 효과적인 충돌 반지름입니다. 이 선은 폴리곤과 수직임을 알수 있습니다.

CollisionRadius(Object, Polygon) =
Sqrt( (Object.xzColl * Polygon.Normal.x)^2 +
        (Object.yColl  * Polygon.Normal.y)^2 +
        (Object.xzColl * Polygon.Normal.z)^2 )

자 이제 우리는 오브젝트가 면을 통과하는지 판단할 수 있습니다. 다음의 알고리즘이 이 테스트를 수행하는 것이며 이와 함께 방향이 주어졌을때 오브젝트의 충돌 반지름을 구하는 도우미 함수입니다.

<CALCULATE-COLLISIONRADIUS>

<PRE-CHECK-COLLISION>

// 제가 충돌 반지름과 사이드 값을  제대로 이해 못한 것일지 모르겠지만 아래 그림만 봐도 알수 있듯이 이 알고리즘에는 헛점이 있는거 같습니다.

 파랑색선은 충돌반지름이며 빨간색은 사이드 값에서 충돌반지름을 빼고 남은 거리를 뜻하는데요. 여기서 아래서 위로 이동한 타원체가 폴리곤과 충돌했음에도 위나 아래나 빨간색 거리 값의 부호가 같기 때문에 충돌이 아닌것 으로 판명됩니다. 타원체가 아니라면 구의 중심과 반지름만을 이용해서 면과 충돌 여부를 판단할 수 있는데 타원체이기 때문에 다르게 처리한것은 알겠는데 먼가 처리가 깔끔하게 이해가 안됩니다. =+=

  이해되시는분 설명 부탁~ //

 PRE-CHECK-COLLISION은 오브젝트가 폴리곤으로 정의되는 면을 통과하는지 판단합니다. 하지만 폴리곤의 영역을 생각하지는 않습니다. 우리는 이 테스트를 통과한 후에 다른 테스트를 해야 합니다. 말하자면 이 테스트는 오브젝트가 폴리곤의 영역안을 통과하는지 여부입니다. 이 테스트는 매우 비싸기 때문에 위의 테스트로 많은 폴리곤들이 무시 될수록 좋습니다. 일단 우리는 오브젝트의 움직임으로 생성되는 실린더안에 폴리곤이 있는지 체크해야 합니다. 그림 23을 봅시다.

<Figure 23. Testing if a object passes through a polygon>

 위의 그림에서 오브젝트는 시작 위치에서 끝 위치까지 움직입니다. 두 위치는 두 폴리곤에 대해 모두 다른 면에 있습니다. 하지만 오브젝트의 움직임으로 생긴 실린더(그림에서 회색 영역)는 오직 폴리곤1만을 통과합니다.

 이 테스트를 수행하기 위해서는 폴리곤에 수직 면들(perpendicular planes)을 계산할 필요가 있습니다. 이들은 폴리곤이 생성될 때 딱 한번만 계산하여 시간을 아낄 수 있습니다. 수직 면들은 폴리곤의 법선과 수직인 법선을 가지며 안쪽을 향하는 면들 입니다. 삼각형의 경우 각 변에 해당하는 3개의 수직 면이 있습니다. 우리는 이것이 어떻게 보이는지 아래 그림으로 그려봤습니다.

<Figure 24. Perpendicular planes for a triangle>

 각각의 수직 면들은 변의 방향 벡터와 폴리곤의 법선 벡터를 외적하고 결과 벡터를 정규화하여 계산할 수 있습니다. // 수직 면의 법선 벡터를 구하는 것 // 만약에 결과가 바깥쪽을 향하는 법선이 되면 이를 전도 시킵니다. 수직 면의 거리값은 수직 면의 법선 벡터와 변의 한점을 내적하여 구할 수 있습니다. 예를 들어서 p1과 p2 사이의 면을 구한다면 다음과 같습니다.

1. PerPlane.Normal = Normalize (Direction (p1, p2) x Polygon.Normal)
2. if(Perplane.Normal * p3 < 0) invert(PerPlane.Normal)
3. PerPlane.Distance = PerPlane.Normal*p2

 만약에 오브젝트가 단순히 하나의 점이라면 이 점이 각각의 수직면에 대해 양의 방향에 있다는 것만 체크하여 오브젝트가 폴리곤 안에 있는지 알 수 있습니다. 하지만 오브젝트는 충돌 반지름을 가지기 때문에 단순히 변을 따라서 생성된 면을 취할 수 없습니다. 우리는 이들을 바깥쪽으로 옮길 필요가 있습니다. 따라서 각각의 수직 면들은 폴리곤의 중심으로부터 충돌 반지름 만큼 바깥쪽으로 이동되는데 이것은 수직 면 다항식의 거리 값을 충돌 반지름 만큼 빼는 것 계산됩니다. 그래도 여전히 한가지 문제가 남는데 다음 그림에서 알 수 있습니다.

<Figure 25. Moved perpendicular planes>

 이 수직 면들이 너무 큰 영역을 포괄하고 있음이 분명합니다. p1으로 부터 수직 면1과 3이 만나는 곳 까지의 거리가 매우 깁니다. 각각의 코너들 역시 마찬가지 입니다. 이것을 바로잡기 위해서 오브젝트의 위치는 추가적으로 또 다른 세 개의 면에 대해 체크를 필요로 합니다. 위 그림에 수직 면2를 복사해서 p1에 가져다 놓습니다. 그 다음에 이것을 충돌 반지름 만큼 바깥쪽으로 이동시키고 이 평면의 법선을 안쪽으로 향하게 전도 시킵니다. 이것으로 문제를 바로 잡았습니다. 각각에 점들에 대한 면들에 대해 이것을 수행합니다. 그러면 다음과 같은 그림이 됩니다.

<Figure 26. The effective collision area of a triangle>

 위 그림의 회색영역이 오브젝트가 폴리곤 안쪽에 있는지 판단하는 영역이 됩니다. 비록 각각의 코너들로 부터 약간 멀어져 있기에 이 영역이 정확하지는 않지만 결과는 충분히 좋습니다. 정확한 영역을 사용하는 것은 각각의 코너 영역에 무수히 많은 면들을 필요로 하므로 매우 비싸게 됩니다. 아래 그림은 정확한 영역을 나타냅니다.

<Figure 27. The correct collision area of a triangle>

 자 이제 우리는 폴리곤 안에서 충돌이 일어났는지 여부를 알 수 있습니다. 이 알고리즘은 이 뒤로 이어집니다.

<GET-COLLIDING-POLYGON>

Complexity analysis:
 이 함수는 런타임에 매우 자주 사용되는 함수이기 때문에 효율성이 무척 중요합니다. 지금으로선 충분히 효율적이지 않는데 이 함수의 복잡도는 라인1 에서 폴리곤들 정렬하는데 걸려있습니다. 퀵 정렬같은 효과적인 정렬 알고리즘을 사용한다면 복잡도는 O(N logN)이 되며 여기서 N은 입력되는 폴리곤 세트가 가지고 있는 폴리곤 개수입니다. 우리는 O(N)에 가까워질 필요가 있습니다. 이 함수는 나중에 재작성 되야만 할 것입니다.

 매 프레임마다 GET-COLLIDING-POLYGON함수는 오브젝트가 통과하는 모든 노드들에서 더 이상 충돌하는 폴리곤이 없을때 까지 호출 됩니다.

 이제 우리는 오브젝트가 폴리곤과 충돌하는지 여부를 판단할 수 있습니다. 이제는 오브젝트들 서로의 충돌을 다뤄야 합니다. 이것은 아주 간단한 작업이며 약간의 계산으로 이루어집니다. 일단 두 오브젝트의 중앙 사이의 방향 벡터를 계산하고 정규화 합니다. 그리고 나서 두 오브젝트를 위한 충돌 반지름을 방향 벡터를 통해서 계산합니다. 만약 두 오브젝트의 중심 거리가 두 오브젝트의 충돌 반지름을 더한 값보다 적으면 충돌한 것이고 충돌 핸들링 필요한 것입니다. 아래 알고리즘은 두 오브젝트의 충돌했는지 판단하는 것입니다.

<OBJECTS-COLLIDE>

 OBJECTS-COLLIDE함수는 움직이는 오브젝트가 통과하는 노드에 있는 오브젝트들에 대해서 한번씩 호출 됩니다.

// 이 알고리즘 역시 위에서 말한 것과 같은 헛점이 있을수 있다고 보이는데. 보다시피 두 타원체의 충돌반지름을 더해도 중심 사이의 거리보다 짧기 때문에 충돌이 안된 것으로 처리하나 실제 그림에서 보이듯 두 타원체는 충돌해 있거든요. //

 오브젝트와 폴리곤 혹은 오브젝트와 다른 오브젝트의 충돌이 일어났을때 움직이는 오브젝트의 끝 위치는 조정되야 합니다.

 폴리곤과 충돌한 경우 끝 위치를 조정하는 것은 다음과 같은 식을 따릅니다.

EndPosition += Polygon.Normal*(CollRadius-EndSideValue)

 이 식의 효과는 벽면을 타고 "미끄러지는(slide)" 것입니다. 만약 충돌이 발생할때 마다 처음 위치로 끝 위치를 고치게 되면 벽에 붙어버리는 것과 상반되는 효과입니다.

 두 오브젝트 사이의 충돌한 경우 움직이는 오브젝트의 끝 위치를 조정하는 것은 다음의 식을 따릅니다.

EndPosition += Direction * (CollRadius1 + (CollRadius2-Distance))

 위에 식에서 Direction은 움직이는 오브젝트의 끝 위치와 다른 오브젝트의 현재 위치 사이의 방향입니다. 이 방향에서 CollRadius1은 움직이는 오브젝트의 충돌 반지름이며 CollRadius2는 다른 오브젝트의 충돌 반지름입니다. Distance는 움직이는 오브젝트의 끝 위치와 다른 오브젝터의 현재 위치 사이의 거리입니다.

 위치가 조정되어 움직여진 오브젝트가 이미 충돌체크를 통과한 이전의 폴리곤이나 오브젝트들과 충돌할지도 모릅니다. 그렇기 때문에 매번 충돌이 일어나게 되면 처음 부터 다시 충돌 체크를 해야 합니다. // 다시말해 충돌로 인해 조정된 좌표값으로 다시 처음부터 충돌체크를 해서 충돌이 없어야 체크를 끝낼 수 있다는 말입니다. // 이것은 복잡한 환경에서 매우 비싼 연산입니다. 따라서 반복 체크 횟수에 제한을 걸어두길 추천합니다. 이 숫자 만큼 반복하고 나서도 여전히 충돌이 일어난다면 오브젝트의 시작 위치로 끝 위치를 조정합니다.

 매번 충돌 체크마다 노드에 있는 폴리곤들을 방향 값(facing value)으로 정렬하는 것은 많은 시간을 소비하기 때문에 다른 방법이 더 낫습니다. 모든 폴리곤을 체크하는 루프를 매번 순환할때 마다 움직이는 오브젝트와 충돌하는 폴리곤의 방향 값중 가장 작은 값을 기억하게 합니다. 리프에 있는 모든 폴리곤들과 충돌 체크를 할때 충돌이 감지되면 그 폴리곤에 대하여 충돌 핸들링이 일어날 것입니다. 그리고 나서 처음부터 다시 루프가 재시작 될 것입니다. 이렇게 하면 이 장에서 이전 언급한 방향 값에따라 순서대로 충돌 체크를 하게 되는 것입니다. 따라서 재작성한 우리의 GET-COLLIDING-POLYGON 함수는 다음과 같습니다.

<GET-COLLIDING-POLYGON>

Complexity analysis:
 인제 우리는 모든 폴리곤에 대하여 한번만 루프를 돌리므로 이 알고리즘의 복잡도는 O(N)이 되고 여기서 N은 입력되는 폴리곤 세트가 가지고 있는 폴리곤 개수입니다.

 우리의 경우 반복을 최대 5번으로 했습니다. 하지만 당연히 이것은 씬이 얼마나 복잡한지에 따라 매우 달라질수 있습니다. 씬이 복잡할수록 더 많은 반복이 필요할 겁니다. 이어지는 페이지는 매 프레임마다 모든 오브젝트들을 위한 충돌 루프입니다.

<COLLISION-HANDLING>

Complexity analysis:
 충돌 루프의 복잡도는 O(i n)이며, 여기서 n은 오브젝트가 통과하는 노드에 있는 폴리곤들의 개수이며 i는 반복 회수의 최대값 입니다. (i값은 다양할 수 있음)

 여기에는 적어도 한가지 명확한 최적화가 있습니다. 이는 구현하기도 매우 쉽습니다. 그것은 충돌 반지름 계산을 오브젝트-폴리곤 그리고 오브젝트-오브젝트에 대하여 오직 한번만 하는 것입니다. 그러나 우리는 이런 명확한 근거들과 상관없이 최적화되지 않은 방법으로 설명하기로 선택했습니다. 아마도 이 프로세스를 빠르게 할 수 있는 명확한 것들이 더 있을수 있습니다. 그것들은 당신에게 남겨두겠습니다.

Related reading:
[Nuydens, Tom. 3D Engine Column, Delphi3D]
[Magarshak, Greg. Theory and Practice]
[Lin, Ming C. Fast Collision Detection for Interactive games]
[UNC Collide Research Group, Collision Detection]
[Bikker, Jacco. Building a 3D Portal Engine]

번역 : 리안
블로그 : http://blog.naver.com/ryanii
MSN : ryanii@hotmail.com