Fast 3D Triangle-Box overlap Testing
link : https://fileadmin.cs.lth.se/cs/Personal/Tomas_Akenine-Moller/pubs/tribox.pdf
Fast 3D Triangle-Box Overlap Testing
Tomas Akenine-Moller
Department of Computer Engineering,
Chalmers University of Technology
March 2001, updated June 2001
Abstract
삼각형과 상자가 3차원으로 중첩되어 있는지 여부를 테스트하는 빠른 루틴이 제공된다. 테스트는 분리 축 정리를 사용해 파생되며,
이후 테스트는 단순화되고 코드는 속도에 맞게 최적화된다. 대화 형 레이 트레이서에서 더 빠른 충돌 감지 및 더 빠른 복셀 처리에
사용할 수 있다. 이 코드는 온라인에서 사용할 수 있다.
Introduction
삼각형이 상자에 겹쳐지는지 여부를 테스트하는 것은 그래픽 프로그래머의 도구 상자에 있는 중요한 루틴이다.
예를 들어, 이 테스트는 광선 추적기의 삼각형 메쉬를 복셀화하는데 사용할 수 있으며 상자를 기반으로 하는 충돌 감지 알고리즘에
사용할 수 있다. Gottschalk 등의 충돌 감지 프레임 워크는 OBB/OBB 테스트와 삼각형/삼각형 테스트만 사용했다.
그러나 각 삼각형 주위에 OBB가 없기 때문에 메모리와 속도를 모두 얻을 수 있으며 대신 OBB에 대해 삼각형을 테스트 할 수 있다.
이전에 Voorhies는 원점에 중심을 둔 단위 큐브에 대해 삼각형을 테스트하는 코드를 제시했다. 그의 테스트는 초기에 간단한
acceptance/rejection 테스트를 수행 한 다음 큐브면과 교차하는 각 삼각형 가장자리를 테스트해 작업을 제거하려고 한다.
마지막으로 삼각형 내부가 큐브에 의해 관통되어 있는지 확인한다. Green과 Hatch는 Voorhies의 작업 효율을 향상시키고
임의의 다각형도 처리하도록 일반화한다. 그들은 또한 신속한 수용/거부 테스트를 사용하지만, 큐브에 대한 모서리의 테스트를
재구성해 비스듬한 마름모꼴의 12면체에 대한 점을 테스트한다.
마지막으로 큐브의 한 대각선이 다각형과 교차하는지 테스트해 효율성을 향상시킨다.
Derivation and Optimization
우리의 테스트는 분리 축 정리에서 파생되었다. 이 정리에 따르면 두 개의 볼록 다면체 A와 B는 A 또는 B면의 법선과 평행한 축을 따라
분리 될 수 있고, 또는 A로부터의 엣지와 B로부터의 엣지의 외적으로 형성되는 축을 따라 형성될 수 있다.
중심 c로 정의된 축 정렬 경계 상자(AABB)와 삼각형 ∆u0u1u2에 대한 절반의 길이 h의 벡터를 테스트하는데 초점을 맞춘다.
테스트를 단순화하기 위해, 상자가 원점을 중심으로 중심이 되도록 삼각형을 이동한다. (즉, vi = ui - c, i∈ {0, 1, 2})
Orientation box에 대해 테스트하려면 먼저 역 상자 변환을 사용해 삼각형 정점을 회전시킨 다음 제시된 테스트를 사용한다.
SAT를 기반으로 다음 13가지 축을 테스트한다:
그림1 : 삼각형 상자 중첩 테스트에 사용되는 표기법. 왼쪽에는 상자와 삼각형의 초기 위치가 표시되고, 오른쪽에는 상자 중심이 원점과
일치하도록 상자와 삼각형이 변환되었다.
1) [3 tests] e0 = (1,0,0), e1 = (0,1,0), e2 = (0,0,1). 삼각형 주위의 최소 AABB에 대해 AABB를 테스트해라.
2) [1 test] n, ∆의 법선. 우리는 방향이 삼각형의 법선에 가장 근접하게 정렬된 두 개의 대각선 정점만을 테스트하는
빠른 평면/AABB 중첩 테스트 [5,6]을 사용한다.
3) [9 test] aij = ei x fj, ( i, j ∈ {0, 1, 2}, ) 여기서, f0 = v1-v0, f1 = v2-v1, f2 = v0-v2.
이러한 테스트는 매우 유사하며 i=0, j=0인 경우의 파생어만 표시한다.
모든 테스트가 통과하면(즉, 분리 축이 없는 경우) 삼각형이 상자와 중첩된다.
또한, 분리 축이 발견되면 알고리즘이 종료되고 "중복 없음"을 반환한다.
다음으로 위의 글 머리 기호 3에서 i = 0 및 j = 0인 9가지 테스트 중 하나를 파생시킨다. 이것은 a0 = e0 x f0 = (0, -f0z, f0y)임을 의미한다.
이제 삼각형 정점을 a0에 투영해야한다:
일반적으로 우리는 min(p0, p1, p2)와 max(p0, p1, p2)를 찾아야했지만 다행스럽게도 p0=p1은 계산을 훨씬 단순하게 만들었다.
이제 우리는 min(p0,p2)와 max(p0,p2)를 찾을 필요가 있다. 이는 조건문이 현대 CPU에서 비싸기 때문에 상당히 빠르다.
a에 삼각형을 투영한 후에 상자를 a에 투영해야한다. r에 투여된 상자의 "반지름"을 계산한다.
여기서 마지막 단계는 이 특정 축에 대해 ax = 0에서 나온 것이다. 그런 다음 이 축 테스트는 다음과 같이 된다:
이제 13가지 테스트가 모두 통과하면 삼각형이 상자에 겹친다.