Bounding Volumes

 

3D 그래픽스에서 Bounding Volumes(경계 볼륨)은 객체 또는 그룹의 외곽을 근사적으로 표현하는 기법입니다. 이는 객체의 충돌 감지, 가시성 테스트 및 렌더링 최적화와 같은 작업에서 유용하게 사용됩니다. Bounding Volumes는 다양한 형태로 사용될 수 있으며, 가장 일반적인 형태는 다음과 같습니다.

1. Bounding Box (경계 상자): Bounding Box는 가장 간단한 형태의 경계 볼륨입니다. 이는 3차원 공간에서 객체를 사각형 상자로 근사화하는 방법입니다. 상자의 크기는 최소한의 정보만을 포함하도록 결정되며, 일반적으로 객체의 최소 및 최대 꼭짓점을 둘러싸는 가장 작은 상자로 정의됩니다.

2. Bounding Sphere (경계 구): Bounding Sphere은 객체를 하나의 구로 근사화하는 방법입니다. 구의 중심은 객체의 중심으로 설정되며, 반지름은 객체에서 가장 먼 지점까지의 거리로 설정됩니다. Bounding Sphere는 더 복잡한 형태의 객체를 근사화하기에는 부족할 수 있지만, 구의 간단한 수학적 특성을 활용하여 빠르게 계산할 수 있습니다.

3. Axis-Aligned Bounding Box (축 정렬 경계 상자): Axis-Aligned Bounding Box는 Bounding Box의 변형으로, 상자의 축이 세 개의 주 축(x, y, z)에 정렬되어 있는 형태입니다. 이는 객체의 회전을 고려하지 않고 충돌 감지나 가시성 테스트를 수행하는 데에 효율적입니다.

4. Oriented Bounding Box (방향성 경계 상자): Oriented Bounding Box는 객체의 방향성을 고려한 경계 상자입니다. 즉, 상자가 객체의 회전과 정렬되어 있으며, 객체에 가장 잘 맞는 상자로 정의됩니다. 이는 객체가 회전하거나 비정형적인 모양을 가질 때 더 정확한 표현을 제공합니다.

5. Convex Hull (볼록 껍질): Convex Hull은 객체를 둘러싸는 최소한의 볼록한 형태를 정의하는 경계입니다. 볼록한 모서리로 구성된 3D 모델을 근사화하는 데 사용됩니다. Convex Hull은 객체의 형태를 상대적으로 잘 표현하지만, 더 복잡한 모델에 대해서는 계산 비용이 높을 수 있습니다.

6. Bounding Cylinder (경계 실린더): Bounding Cylinder은 객체를 하나의 원통으로 근사화하는 방법입니다. 객체의 높이와 지름을 고려하여 원통의 위치와 크기를 결정합니다. Bounding Cylinder는 특히 길쭉한 객체나 회전하는 객체를 표현하는 데 유용합니다.

7. Bounding Capsule (경계 캡슐): Bounding Capsule은 객체를 두 개의 반구로 둘러싼 실린더로 근사화하는 방법입니다. 객체의 축을 따라 두 개의 반구가 연결된 형태로 정의됩니다. Bounding Capsule은 긴 객체 또는 관절을 가진 캐릭터와 같은 형태를 표현하는 데 사용됩니다.

이외에도 다양한 Bounding Volumes 기법이 존재하며, 사용하는 애플리케이션과 요구 사항에 따라 선택할 수 있습니다. Bounding Volumes는 3D 그래픽스와 충돌 감지 시스템에서 성능과 효율성을 개선하는 데 중요한 역할을 합니다.

 

 

각 캐릭터를 각 부분마다 위 바운딩 볼륨을 계층적으로 묶어놓으면 실제 게임에서 안 맞았는데 죽는 이러한 현상을 많이 줄일 수 있다.

 

만약 바운딩 볼륨을 사용하지 않고 더 정확한 피킹을 원한다면 우리는 실제 캐릭터의 폴리곤 메시와 Ray와의 충돌을 감지하는 알고리즘을 사용해야 한다.

 

Ray-Triangle Intersection(광선-삼각형 교차)은 광선과 삼각형이 교차하는지 확인하는 알고리즘입니다. 이 알고리즘은 렌더링이나 피킹(Picking) 등 다양한 그래픽스 작업에서 사용됩니다.

광선은 시작점(origin)과 방향(direction)으로 정의됩니다. 삼각형은 세 개의 정점(vertices)으로 구성되며, 각 정점은 3D 공간에서의 좌표로 표현됩니다.

Ray-Triangle Intersection 알고리즘은 다음과 같은 단계로 작동합니다:

1. 광선의 방향벡터를 정규화합니다. 이는 광선의 방향이 단위 벡터가 되도록 합니다.

2. 광선과 삼각형의 평면을 교차하는지 확인합니다. 삼각형의 평면은 세 개의 정점을 기반으로 계산됩니다. 이를 위해 광선의 방향벡터와 삼각형 평면의 법선 벡터의 내적을 계산합니다. 만약 내적이 0에 가까우면 광선은 평면과 평행하며, 교차하지 않습니다.

3. 평면과 광선이 교차하는 경우, 이제 교차 지점을 찾아야 합니다. 삼각형의 평면과 광선의 교차점을 찾는 것은 선형 방정식을 풀어야 합니다. 이를 위해 Möller-Trumbore 알고리즘이 널리 사용됩니다. 이 알고리즘은 교차점의 매개변수를 계산하여 교차점의 좌표를 구하는 방법입니다.

4. 계산된 교차점이 삼각형 내부에 있는지 확인합니다. 이를 위해 바리센트릭 좌표계(Barycentric coordinates)를 사용합니다. 바리 센트릭 좌표계는 삼각형 내부의 한 점을 나타내기 위해 각 정점에 대한 가중치로 표현하는 방법입니다. 교차점의 바리 센트릭 좌표를 계산하여 모든 가중치가 0보다 크고 1보다 작은지 확인하여 삼각형 내부에 있는지 판별합니다.

5. 만약 교차점이 삼각형 내부에 있다면, 교차가 확인되었습니다. 그렇지 않은 경우, 광선과 삼각형은 교차하지 않습니다. 따라서 광선이 삼각형을 통과하지 않고 그냥 지나가는 것입니다.

Ray-Triangle Intersection 알고리즘의 주요 목표는 삼각형과의 교차점을 정확하게 찾는 것입니다. 이를 통해 렌더링 작업에서 광선과 삼각형의 상호작용을 계산하거나, 피킹 작업에서 사용자가 클릭한 지점에 해당하는 삼각형을 찾을 수 있습니다.

Möller-Trumbore 알고리즘은 성능과 정확성을 모두 고려하여 일반적으로 많이 사용되는 알고리즘 중 하나입니다. 그러나 광선과 삼각형의 수가 많은 경우에는 다른 효율적인 알고리즘을 고려해야 할 수도 있습니다.

Ray-Triangle Intersection은 실시간 렌더링 및 그래픽스 애플리케이션에서 중요한 요소입니다. 예를 들어, 광선 추적(ray tracing) 알고리즘에서는 모든 광선과 장면 내의 모든 삼각형 간의 교차를 확인해야 하므로 이 알고리즘이 반복적으로 사용됩니다.

이를 Ray 방정식을 바리센트릭 좌표계로 구한 좌표로 구한 접점의 방정식이 같으면 이는 Ray와 충동하는 것이다.

그리고 이는 전부 3차원 벡터이기 때문에 크래이머 법칙을 통해 구할 수 있습니다.

 

크래이머의 법칙(Cramer's Rule)은 선형 방정식의 해를 구하는 데 사용되는 방법 중 하나입니다. 크래이머의 법칙은 행렬과 행렬식의 개념을 활용하여 선형 방정식의 해를 구할 수 있도록 도와줍니다.

크래이머의 법칙은 다음과 같은 선형 방정식을 고려합니다:

A⋅x = b

여기서 A는 n×n 크기의 계수 행렬(coefficient matrix)이고, x는 n차원의 미지수 벡터(unknown vector)이며, b는 n차원의 상수 벡터(constant vector)입니다.

크래이머의 법칙을 사용하여 선형 방정식의 해를 구하는 과정은 다음과 같습니다:

1. 우선, 계수 행렬 A의 행렬식을 계산합니다. 이는 det(A)로 표기됩니다. 행렬식은 행렬의 크기와 각 요소의 값을 기반으로 계산됩니다.

2. 다음으로, 계수 행렬 A에서 각 열을 상수 벡터 b로 바꿉니다. 이렇게 하면 새로운 행렬 Aᵢ가 생성됩니다. 여기서 Aᵢ는 A의 i번째 열이 b로 대체된 행렬입니다.

3. 이제 Aᵢ의 행렬식 det(Aᵢ)를 계산합니다.

4. 크래이머의 법칙에 따라, 각 미지수 xᵢ의 해는 다음과 같이 구할 수 있습니다: xᵢ = det(Aᵢ) / det(A), 여기서 i는 1부터 n까지의 값을 가집니다.

크래이머의 법칙은 각 미지수에 대한 해를 구할 수 있는 장점이 있지만, 다음과 같은 제약사항을 갖고 있습니다:

- 크래이머의 법칙은 선형 방정식의 해가 유일하고, 계수 행렬 A의 행렬식이 0이 아닌 경우에만 적용 가능합니다.
- 크래이머의 법칙은 행렬식을 계산해야 하므로, 계수 행렬이 크거나 복잡한 경우에는 연산 비용이 높아질 수 있습니다.