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

3D 공간에 있는 어떤 물체(점p)를 원점O 기준으로 회전 시키는 상황을 생각해보자. 회전 행렬(Rotation Matrix)을 이용한 회전 길이가 1인 회전축 u를 기준으로 반시계 방향으로 θ 만큼 회전할 때 3차원 점 p에 곱해야 할 3x3 행렬은 다음과 같이 계산된다. 특히, 축 x = (1, 0, 0), y = (0, 1, 0), z = (0, 0, 1) 을 기준으로 하는 회전 행렬은 계산해보면 각각 다음과 같다. 모든 회전 행렬은 직교 행렬이다. 이러한 직교 행렬은 다음 성질들을 갖는다. 1. 열 벡터 또는 행 벡터는 모두 단위 길이이다. 2. 열 벡터끼리 또는 행 벡터끼리는 서로 수직 관계를 갖는다. 3. 직교 행렬의 역 행렬은 전치 행렬과 같다. 즉 회전 행렬의 역 변환 행렬은 다음과 같다...

발산 쉽게 말해 벡터장이 생성 또는 소멸하는 양을 나타낸다. 수학적인 정의는 미분 연산자를 참고하자. 아래 그림에서 왼쪽은 메쉬 위에서 기준점으로부터 다른 정점까지의 최단 측지거리를 색으로 표현한 것이다. 빨간색으로 갈 수록 가까운 곳, 보라색으로 갈 수록 먼 곳이다. 이 스칼라 장(Scalar Field)으로부터 그래디언트 장(Gradient Filed)을 계산하면 오른쪽 그림처럼 된다. 이 벡터 장(Vector Field)으로부터 발산 장(Divergence Field)를 계산해보자. 아래 그림처럼 기준 정점 x와 주변 삼각형이 있고 x에 연결된 한 에지의 방향을 e라고 하자. 양쪽 삼각형에 할당된 벡터는 fα, fβ 이다. 각 벡터와 에지 방향을 내적하고 반대편 각도의 cot값을 곱한 두 값을 평균..

그래디언트는 쉽게 말해 스칼라 함수가 최대로 변하는 방향을 나타낸다. 수학적인 정의는 미분 연산자를 참고하자. 아래 그림은 메쉬 위에서 기준점으로부터 다른 정점까지의 최단 측지거리를 색으로 표현한 것이다. 빨간색으로 갈 수록 가까운 곳, 보라색으로 갈 수록 먼 곳이다. 이 스칼라 장(Scalar Field)으로부터 그래디언트 장(Gradient Filed)을 계산해보자. 삼각형의 세 점의 위치를 x0, x1, x2 라고 하고 각 점의 스칼라를 f0, f1, f2 라고 하자. 그리고 각 에지 벡터를 반시계 방향으로 90도만큼 회전 시킨 벡터를 빨간색, 초록색, 파란색으로 나타내면 다음과 같다. 각 벡터와 마주보는 스칼라를 곱하여 모두 더한 다음 삼각형의 면적으로 나눈 벡터가 삼각형의 그래디언트이다. 메쉬의..

폴리곤이 평면에 대하여 어느 쪽에 위치하는지 알아보려면 각 점을 모두 평면의 방정식에 대입해보아야 한다. 다시 말해 평면에 대한 점의 signed distance를 계산해 봐야 한다. 만약 모든 점에서 평면까지의 signed distance가 모두 양수라면 그 폴리곤은 평면의 위쪽(+)에 위치할 것이고 양수, 음수가 섞여있다면 폴리곤은 평면에 걸쳐있는 상태일 것이다. signed distance가 모두 0이라면? 그 폴리곤은 평면에 완전히 포함되어 있을 것이다. 하지만 이론상으로나 그렇지 프로그래밍을 할 때에는 수치 정밀도를 정해서 판단하는 것이 좋다. 폴리곤과 평면의 위치 관계는 다음 네가지 중 하나에 해당된다. 1. 폴리곤이 평면 앞(+)에 위치한 경우 2. 폴리곤이 평면 뒤(-)에 위치한 경우 3...

우리가 흔히 말하는 폴리곤은 N개의 점을 가진 도형을 말한다. 그래픽스 또는 CAD에서 N개의 좌표로 폴리곤을 쉽게 표현할 수 있다. 하지만 이러한 명시적인(explicit) 표현법 말고 암시적인(implicit) 표현법을 사용할 때도 있다. 그 중에 하나가 평면 기반 표현법이다. 평면 기반 폴리곤 표현법은 convex한 폴리곤을 평면 s 위에서 경계 평면 { bi } i∈Zn 으로 둘러쌓인 영역으로 표현한다는 것이다. (경계 평면은 반시계 방향 순서이다.) 아래 그림에서는 폴리곤이 포함된 평면 s와 각 에지를 포함하면서 s에 직교하는 평면 5개를 나타낸다. 이렇게 되면 폴리곤의 각 점은 vi = (s, bi-1, bi) 로 표현할 수 있다. 즉 각 점을 세 평면의 조합으로 표현 가능하다. 그리고 점의 ..

평면으로 폴리곤을 자르는 방법에 대해 알아보자. 메쉬를 측지선으로 자르거나 평면으로 잘라서 양쪽으로 분할하거나, 메쉬에 대한 BSP 트리를 만들 때 폴리곤을 평면으로 잘라야하는 경우가 많이 생긴다. 여기서는 명시적(explicit) 방법과 암시적(implicit) 방법으로 구분해서 설명한다. 1. Explicit Split 폴리곤이 평면으로 잘려서 두 폴리곤으로 나뉜다고 할 때, 명시적 방법은 두 폴리곤의 꼭지점을 직접 계산하는 방법이다. CAD 프로그래밍을 할 때에는 수치오류를 고려하여 평면에 두께를 주는편이 좋다. 다시 말해서 점이 평면의 두께 안에만 들어온다면 점은 평면에 포함된다고 간주한다. 다음 그림처럼 폴리곤의 한 에지에 대하여 시작점을 A, 끝점을 B 라고 하고 두 점의 위치를 테이블에서 참..

BSP 트리란? 이진 공간 분할법(Binary Space Partitioning)은 재귀적으로 3차원 공간을 평면으로 분할하는 기법이다. 분할 과정으로 BSP 트리라 불리는 트리 구조가 만들어진다. BSP 트리는 컴퓨터 그래픽스에서 렌더링 효율을 높이기 위해서 도입되었지만, CAD에서의 CSG(Constructive Solid Geometry), 충돌 감지(collision detection)에도 쓰기 좋다. 또한 폴리곤 메쉬의 내/외부를 구분하기에도 좋다. BSP 트리는 쿼드트리, 옥트리, k-d 트리와 비슷하지만 보다 더 일반적인 구조이다. 분할하는 공간이 n차원이면 분할 평면은 (n - 1)차원 초평면이다. 초평면은 평면의 일반화된 개념이라 생각하면 된다. 분할하고자하는 공간이 3차원이면 분할 초평..

Hermite Spline 또는 Hermite Interpolation Curve는 곡선을 여러개 이어붙여 만든 스플라인을 말한다. 여기서는 일반적으로 많이 사용되는 방식에 대해 알아볼건데, 각 구간이 3차 베지에 곡선으로 구성되는 허밋 스플라인에 대한 내용이다. 스플라인의 어떤 한 구간에서 베지에 곡선 C(t)를 정의하기 위해서는 양 끝의 두 점 p0, p1과 접벡터(tangent vector) v0, v1가 필요하다. 그래야 스플라인의 각 보간점(Interpolation Point)에서 곡선이 기울기를 유지하며 부드럽게 이어질 수 있다. 여기서 각 곡선의 파라미터 범위는 [0, 1] 이다. 이렇게 주어진 양끝의 보간점과 접벡터로 식 C(t)를 어떻게 세울까? 3차 베지에 곡선 식을 세워야 하기 때문에..