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

GeoStamp: Detail Transfer Based on Mean Curvature Field (paper) Jung-Ho Park, Ji-Hye Moon, Sanghun Park and Seung-Hyun Yoon, Mathematics (SCIE), 10(3), 500

Parametric Blending of Hole Patches Based on Shape Difference (paper) Jung-Ho Park, Sanghun Park and Seung-Hyun Yoon Symmetry (SCIE), 12(11), 1759

렌더링 할 때 삼각형이 일반적으로 많이 사용되지만, 직선과 다각형의 교차점을 찾는 문제 역시 많이 사용되므로 알아볼만 하다. 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..