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

선형대수학에서, 크래머 공식은 유일한 해를 가지며 변수와 방정식의 수가 같은 연립 일차 방정식의 해를 구하는 공식이다. 2개의 연립 일차 방정식의 경우 연립 일차 방정식 이 유일한 해를 갖는다면, 그 해는 다음과 같다. 행렬 표현법으로 다시 써보면, 이다. 3개의 연립 일차 방정식의 경우 연립 일차 방정식 이 유일한 해를 갖는다면, 그 해는 다음과 같다. 행렬 표현법으로 다시 써보면, 크래머 공식은 이렇게 계수 행렬과 그 한 열을 상수항으로 대신하여 얻는 행렬들의 행렬식의 비를 통해 해를 구한다. 2~3개 이상의 연립 방정식의 경우 크래머 공식에 의한 알고리즘은 가우스 소거법보다 비효율적이다.

3차원 공간에서 두 직선사이의 교차점을 구해보자. 두 직선의 방정식을 다음과 같이 정의한다. 벡터 자기 자신과 외적을 하면 0벡터가 나온다는 사실을 이용하여 직선의 교점을 다음과 같이 구한다. 위에서 구한 s와 t 가 교차점에서 두 직선의 파라미터이다. 만약에 분모가 0이라면 두 직선은 평행하므로 만나지 않는다. 또한 두 직선이 서로 꼬인(skew) 위치에 있다면 즉, 공통 평면위에 있지 않으면 만나지 않으며 이때 s와 t는 두 직선의 가장 가까운 점을 나타낸다. 두 직선이 유한한 길이의 선분 (line segment)라면 s 와 t 가 0과 1 사이에 있는지도 확인해봐야한다. 이 범위를 벗어나면 선분 밖에서 만난다. [참고] Real-time rendering. Akenine-Moller, Tomas,..

메쉬에 뼈(bone)를 심어서 애니메이션을 만들어보았다. 영상에서는 3D shape, skeleton, animation 정보가 포함된 FBX파일을 임포트한 결과를 보여준다. 각 관절과 메쉬 정점은 서로 적절한 가중치로 바인딩되어 있어서 관절의 움직임에 따라 메쉬 skinning이 수행된다. [개발 환경] C++ / OpenGL / Visual Studio

지형 메쉬를 편집하는 툴을 만들어보았다. 쿼드 메쉬를 하나 만들어서 작은 삼각형으로 subdivision하고, 메쉬를 sculpting 및 deformation을 해서 지형 메쉬로 만들었다. [개발 환경] C++ / OpenGL / Visual Studio [참고] Botsch, Mario, and Leif Kobbelt. "An intuitive framework for real-time freeform modeling." ACM Transactions on Graphics (TOG) 23.3 (2004): 630-634.

메쉬에 존재하는 홀(hole)을 발견해서 부드러운 메쉬(초록색)로 채운 후, 그 위에 디테일을 추가하여 모델을 복원하는 툴을 만들어보았다. [개발 환경] C++ / OpenGL / Visual Studio [참고] Liepa, Peter. "Filling holes in meshes." Proceedings of the 2003 Eurographics/ACM SIGGRAPH symposium on Geometry processing. 2003. Park, Jung-Ho, et al. "GeoStamp: Detail Transfer Based on Mean Curvature Field." Mathematics 10.3 (2022): 500.

안녕하세요. C++과 이번 기술은 소스 영역(노란색 경계)의 디테일 형상을 추출하여 타겟 영역(보라색 경계)으로 전이하는 기술입니다. 소스 영역의 평균 곡률장을 타겟 영역으로 옮기는 방식입니다 . 형상 디테일 전이는 형상 변형, 메쉬 홀 필링등에 응용 가능합니다. This technique is that extracts geometric detail from the source region (yellow boundary) and transfers it to the target region (purple boundary). The method moves the mean curvature field of the source region to the target region. Shape detail trans..

용량이 큰 high polygon mesh를 단순화해보았다. 메쉬의 형상(shape)을 최대한 유지하면서 모델의 정점과 삼각형의 개수를 줄여나가는 방식이다. [개발 환경] C++ / OpenGL / Visual Studio [참고] Garland, Michael, and Paul S. Heckbert. "Surface simplification using quadric error metrics." Proceedings of the 24th annual conference on Computer graphics and interactive techniques. 1997.

메쉬를 부위별로 분할하고 선택하는 기능을 만들어보았다. 분홍색으로 나타나는 영역에서 메쉬 굴곡이 급격하게 변하는 부분까지 자동으로 분할이 가능하다. [개발 환경] C++ / OpenGL / Visual Studio [참고] Au, Oscar Kin-Chung, et al. "Mesh segmentation with concavity-aware fields." IEEE Transactions on Visualization and Computer Graphics 18.7 (2011): 1125-1134.

메쉬에서 일부 영역을 선택해서 Fairing 을 적용해보았다. mesh fairing은 디테일/노이즈를 제거하여 부드럽게 만드는 기법이다. [개발 환경] C++ / OpenGL / Visual Studio [참고] Moreton, Henry P., and Carlo H. Séquin. "Functional optimization for fair surface design." ACM SIGGRAPH Computer Graphics 26.2 (1992): 167-176. Desbrun, Mathieu, et al. "Implicit fairing of irregular meshes using diffusion and curvature flow." Proceedings of the 26th annual con..

메쉬의 재질(material)에 셰이더(shader)를 붙여서 표현해보았다. OpenGL에서는 기본적으로 삼각형 안에서 세 점의 조명색상을 보간하는 방식인 Gouraud 셰이딩을 사용하기 때문에 메쉬의 렌더링 퀄리티가 높지 않다. 영상에서는 GLSL을 사용하여 퐁(Phong) 셰이딩, 툰(Toon) 셰이딩, 환경 매핑(Environment mapping)등을 사용한다. 특히 퐁셰이딩은 삼각형 안에서 세 점의 법선을 보간하기 때문에 Specular 효과를 확실하게 표현할 수 있다. [개발 환경] C++ / OpenGL / Visual Studio