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

베지에 곡선 위의 점을 효율적으로 계산하는 de Casteljau 알고리즘에 대해서 알아보자. CAGD(Computer Aided Geometric Design)에서는 곡선과 곡면을 주로 다루기 때문에 de Casteljau 알고리즘이 많이 사용된다. 알고리즘을 일반화시켜서 곡면 위의 점을 계산할 수도 있다. 1959년에 Paul de Casteljau이라는 수학자이자 물리학자가 고안했다. 3차 베지에 곡선 C(t)의 제어점이 다음과 같이 b0, b1, b2, b3 로 주어졌다고 하자. 예시로, 파라미터 t = 0.3일 때 곡선 위의 점 C(0.3)을 계산해보자. 각 제어점 사이마다 t = 0.3에서의 내분점을 계산하면 3개의 새로운 점을 구할 수 있다. 이 1단계 내분점들을 초록색으로 표기해보자. (1..

베지에 곡선 (Bézier curve)는 n개의 제어점(control point)으로부터 만들어지는 n-1차 곡선으로 수치 해석 분야에서 중요하게 사용된다. 특히 3차 베지에 곡선은 포스트스크립트 글꼴, 메타폰트(METAFONT), 김프 등에서 부드러운 폰트를 만드는데에 이용되고 있다. 이 글에서 3차 베지에 곡선의 수학적인 표현법에 대해 알아보자. 다음 그림처럼 실수 파라미터 t가 0과 1사이에서 움직인다고 하자. 움직이는 t의 값에 따라서 3차원 공간 위에 그려지는 곡선을 C(t)라고 표기한다. C(t)의 x, y, z 각 좌표를 t에 대한 식으로 표현할 수만 있다면 우리는 t를 마음대로 움직이면서 그에 대응되는 곡선 위의 점을 구할 수 있을 것이다. 그렇다면 C(t)의 식을 어떻게 쓸 수 있을까? ..

메쉬 위에서 두 점을 잇는 최단 경로를 구하는 방법에 대해 알아보자. 사실 측지 경로를 구하는 문제는 컴퓨터 그래픽스에서 많이 사용된다. 메쉬 측지선으로 메쉬 분할(Segmetation), 자르기(Cutting)가 가능하다. 또한 여러 알고리즘의 기반이 되는 곡면 위의 거리 측정에도 유용하다. 예를 들면 메쉬 위에서 방사형 기저 선형보간( Radial-Basis Interpolation)을 계산하려면 측지거리를 계산해야 되며 이런 기법이 스키닝(skinning), 메쉬 워터마킹(mesh watermarking), 곡면 벡터장(vector field)을 정의하는 등 여러 어플리케이션에서 사용된다. 여기서 소개할 알고리즘은 소스점 s를 고정하고 다른 모든 정점까지의 최단 거리장을 먼저 구한 다음 이에 기반하..

우리가 3D 모델링을 할 때 가상의 객체를 만들어 내는데 그러다 보면 현실에 존재할 수 없는 형태의 메쉬를 만들기도 한다. 이런 메쉬를 Non-manifold 메쉬라고 한다. (정확히는 Non-manifold topology인 메쉬) Non-manifold 메쉬는 일반적인 메쉬 알고리즘이 작동하지 않을 뿐더러, 3D 프린터로 출력할 수도 없기 때문에, 메쉬의 어느 부분이 non-manifold 요소인지 판별해서 고쳐나가는 작업을 진행해야 한다. 어떤 경우에 non-manifold 요소가 생기는지 알아보자. 여기서 메쉬는 orientable surface라고 가정한다. Non-manifold Vertex 그림과 같이 한 점을 공유하는 삼각형 집합이 2개 이상인 경우이다. 정점 주변의 삼각형을 그룹별로 묶어..

메쉬 위에서 가우스 곡률(Gauss curvature)에 대해 알아보자. 정점 p 주변에 m개의 인접 삼각형이 있을 때, 다음과 같이 2π에서 정점 주변각의 합을 뺀값이 가우스 곡률이다. 이 가우스 곡률에 따라 정점을 다음과 같이 3가지로 구분할 수 있다. 예를 들어 정육면체의 각 정점은 가우스 곡률이 π/2과 같다.

측지 극좌표 (Geodesic Polar Coordinates) 측지 극좌표 (Geodesic Polar Coordinates)에 대해 알아보자. 3차원 공간의 곡면 S 위에서 측지 극좌표란 곡면의 한 점을 길이와 방향을 써서 평면 위의 파라미터로 표현하는 로컬 좌표이다. 극좌표계는 두 점 사이의 관계가 각이나 거리로 쉽게 표현되는 경우에 가장 유용하다. 이 글에서는 삼각 메쉬 위에서 측지 극좌표를 근사시키는 방법을 소개한다. 아래 그림은 곡면 S 위의 점 v가 접평면 TsS 위의 극좌표 p로 매개화(parameterization)되는 상황을 보여준다. 접평면 대신 2차원 평면을 생각하면 v와 s를 연결하는 최단 측지선의 길이와 방향에 의해 매개화된다고 생각할 수도 있다. 이렇게 접평면을 사용해서 기준점..

렌더링 할 때 삼각형이 일반적으로 많이 사용되지만, 직선과 다각형의 교차점을 찾는 문제 역시 많이 사용되므로 알아볼만 하다. 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의 한 면 각 다면체의 에지 첫번째와 두번째 테스트 : 한 오브젝트가 다른 오브젝트 모든 면의 반대편에 있다면 둘은 만나지 않음을 의미한다. 세번째 테스트 : 모든 면이 둘을 분리하는 평면을 형성할 수 없는 경우, 두 다면체의 에지를 서로 외적하여 얻은 벡터가 ..