오다기리 박의 알고리즘 노트

렌더링 할 때 삼각형이 일반적으로 많이 사용되지만, 직선과 다각형의 교차점을 찾는 문제 역시 많이 사용되므로 알아볼만 하다. n 개의 정점을 가지는 닫힌 다각형(Closed polygon)과 다각형이 포함되는 평면을 다음 그림과 같이 정의하고 직선과 평면의 교차점 찾기를 이용하여 p를 먼저 찾는다. 평면과의 교차점 p를 찾았으면 그 점이 다각형 안에 있는지 밖에 있는지만 판단하면 된다. 여기서부터는 2D로 생각해도 되므로 다각형과 점 p를 xy/xz/yz 평면 중 한 곳으로 projection한다. 이 때 다각형을 사영(projection)했을 때 면적이 제일 큰 평면을 선택하면 된다. 면적을 제일 크게 만드는 평면을 고르는 방법은 평면의 법선벡터에서 절대값이 가장 큰값에 대응되는 좌표 성분은 건너뛰고 ..

기하객체가 용량이 큰 경우 컴퓨터 그래픽스 렌더링과정에서 시간이 오래 걸린다. 이를 가속화 하기 위해 기하개체를 3차원 공간 안에서 구조화하는 Spatial Data Structure를 주로 사용한다. Spatial Data Structure는 일반적으로 계층구조 (hierarchy)에 기반하여 구현한다. 계층구조는 부모/자식 노드로 구성되며 각 노드는 자신의 공간을 정의한다. 이런 구조를 이용해서 기하개체를 구성하는 각각의 요소에 빠르게 접근할 수 있다. Spatial Data Structure를 한번 생성하는 데 걸리는 시간은 기하개체의 용량, 구조의 퀄리티 등에 따라 좌우되므로 오래 걸릴 수도 있다. Spatial Data Structure에는 BVH, BSP Tree, Octree 등이 있는데, ..

삼각형과 박스의 교차여부를 알아보자. 여기서 박스는 AABB 로 생각하자. 우선 다음과 같이 정의되는 삼각형과 AABB가 있다고 하자. 문제를 단순화하기 위해서 박스의 중심 c가 원점에 위치하도록 다음과 같이 박스와 삼각형을 이동시킨다. 그리고 SAT 에 기반하여 다음 13개 축에 대한 테스트를 수행한다. [3 tests] AABB의 세 법선 e0=(1, 0, 0) e1=(0, 1, 0) e2=(0, 0, 1). (AABB와 삼각형을 감싸는 AABB간의 테스트) [1 tests] 삼각형의 법선. (평면과 박스의 교차 검사) [9 tests] aij = ei x fj , i, j = {0, 1, 2}. 모든 테스트를 통과하면 seprating axis가 없으므로 삼각형과 박스는 서로 만난다. [참고] Re..

분리된 두개의 convex 다면체 A, B 가 있을 때 다면체가 축에 투영된 구간 또한 최소 하나는 분리되어 있다. 만약 다면체가 concave하다면 이 법칙은 성립하지 않는다. 예를 들어 우물안에 바구니가 있다고 하자. 바구니와 우물은 서로 닿지 않지만 둘을 분리시키는 평면은 존재하지 않는다. 왜냐면 우물이 concave하기 때문이다. A와 B가 서로 떨어져 있을 때, 둘은 다음 중 하나에 직교하는 축으로 분리되는지 테스트해본다. A의 한 면 B의 한 면 각 다면체의 에지 첫번째와 두번째 테스트 : 한 오브젝트가 다른 오브젝트 모든 면의 반대편에 있다면 둘은 만나지 않음을 의미한다. 세번째 테스트 : 모든 면이 둘을 분리하는 평면을 형성할 수 없는 경우, 두 다면체의 에지를 서로 외적하여 얻은 벡터가 ..

3차원 공간에서 다음 방정식으로 표현되는 세 평면의 교차점을 구해보자. 여기서는 4가지 방법을 소개한다. 우선 예외처리를 위해 세 평면의 법선이 모두 한 평면위에 있는 경우는 제외한다. 즉 다음 그림처럼 두개 이상의 평면이 평행하거나, 세 평면이 한 직선을 공유하거나, 직선을 공유하지 않는 경우이다. 이를 조사하기 위해서는 세 평면의 법선으로 이루어진 행렬의 행렬식이 0인지 조사하면 된다. 행렬식이 0이라면 세 벡터로 이루어진 평행육면체의 부피가 0이므로 세 법선이 한 평면위에 존재하게 된다. 그 외의 경우에는 다음 그림처럼 세 평면이 하나의 유일한 점에서 교차한다. 첫번째 방식 첫번째 방식은 다음과 같이 교점 p를 세 평면의 방정식에 각각 대입하여 3개의 연립 방정식을 세운다. 결론적으로 다음 선형 시..

AABB rectangular box라고도 불리는 AABB(Axis-Aligned Bounding Box)는 모든 면의 법선이 좌표축에과 일치하는 박스를 말한다. 예를들어 A라는 AABB는 다음과 같이 대각선방향으로 서로 반대편에 있는 두 점에 의해 정의된다. OBB OBB(Oriented Bounding Box)는 각 세 쌍의 면들이 다른 면들과 수직인 박스, 즉 AABB를 임의의 방향으로 회전한 박스이다. OBB는 다음 그림과 같이 중심점과 박스의 세 방향을 나타내는 세개의 정규화된 벡터로 정의할 수 있다. 세개의 half 벡터는 중심점에서 각 면까지 길이를 갖는다. [참고] Real-time rendering. Akenine-Moller, Tomas, Eric Haines, and Naty Hoff..

아래 그림과 같이 3차원 공간에서 평관과 박스의 교차 여부를 검사해보자. 박스의 모든 점들을 평면의 방정식에 대입하여 모든 sigend distance값이 같은 부호라면 교차하지 않고, 부호가 다른값이 나왔다면 정점들이 평면의 양쪽에 존재하므로 둘은 교차하게 된다. 여기서는 AABB와 OBB 각각 다른 방식을 소개한다. 두 방식 모두 박스의 두 점만 평면의 방정식에 대입해보면 된다. 여기서 박스의 두 점은 박스의 중심을 지나는 4개의 대각선들 중 평면의 법선과의 내적값이 가장 큰 대각선의 두 점을 말한다. 우선 박스 B에서 양 끝점, 대각선의 half 벡터, 중심점을 다음과 같이 나타낸다. half 벡터 h는 박스에서 양 끝점을 어떻게 잡느냐에 따라 총 8개를 구할 수 있다. 이제 다음 그림처럼 3차원 ..

3차원 공간에서 직선과 평면의 교점을 구해보자. 아래 그림과 같이 3차원 공간에 직선과 평면이 존재한다고 하자. x는 평면위의 임의의 점이다. 교점을 찾기 위해서는 직선의 방정식의 파라미터 t*를 구해야 한다. 우선 예외처리를 위해 다음과 같이 직선의 방향벡터와 평면의 법선의 내적이 0인지 조사한다. 두 벡터의 내적이 0이라면 서로 수직하므로 직선이 평면과 평행하거나 평면에 완전히 포함되어 있는 경우다. 이 때는 교점이 존재하지 않는다. 그 외의 경우에는 직선 위의 점 r(t*)을 평면의 방정식에 대입하여 t* 를 구한다.