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

a벡터를 평면에 사영(projection)시킨 c벡터를 구해보자. 여기서 평면은 n벡터를 법선으로 가진다. 계산 과정은 간단하다. 지난번 포스팅 벡터를 벡터에 사영하는 방법을 이용해서 a를 법선 n에 사영시켜서 b를 구하면 a - b가 바로 결과 c이다.

3차원 공간에서 a벡터를 b벡터에 사영(projection)하여 c벡터를 구해보자. c를 구하려면 길이와 방향이 필요하다. c의 길이는 a와 b를 내적하여 b의 길이로 나눈 값과 같다. 즉 a와 b의 사잇각이 θ일 때 a와 b의 내적값은 ||a||||b||cosθ이고 이 값을 b의 길이로 나눈다. c의 방향은 b를 정규화하면 된다. 결론적으로 위에서 구한 c의 길이와 방향을 곱하면 사영벡터 c가 계산된다.

베지에 곡선 위의 점을 효율적으로 계산하는 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를 연결하는 최단 측지선의 길이와 방향에 의해 매개화된다고 생각할 수도 있다. 이렇게 접평면을 사용해서 기준점..