일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
- 컴퓨터 아키텍쳐
- Mesh Processing
- modeling
- 윈도우
- window programming
- Win32 API
- 렌더링
- 핵심 API로 배우는 윈도우프로그래밍
- Geometry Modeling
- 윈도우 구조
- 그래픽스
- 오픈지엘
- shader
- shader programming
- MFC
- 컴퓨터 구조
- 윈도우프로그래밍
- bezier curve
- 운영체제
- 셰이더
- c4d
- OpenGL
- 그래픽스기초
- 셰이더프로그래밍
- 베지에 곡선
- win32
- Graphics
- MFC 윈도우 프로그래밍
- 윈도우 프로그래밍
- denoising
- Today
- Total
목록컴퓨터 그래픽스/메쉬 기하학 (36)
오다기리 박의 알고리즘 노트
삼각 메쉬 위의 정점들에 대한 근사화된 거리를 얻는 방법을 알아보자. 기준점 s에서 vi까지 거리는 국소적으로 최적화 되어야 하며 다음 식을 만족해야 한다. 여기서 U (y)는 s에서 y까지의 측지 거리의 국소 근사값이다. 다음과 같이 가상의 기준점 s' 를 정하면 U (y)를 쉽게 계산할 수 있다. 또한 다음 부등식을 만족한다면 삼각형Tijk에 의해 span되는 평면 위에 가상의 기준점s' 가 존재한다. 기준점 s' 존재 여부에 따라 s' 에서 vi 까지 거리를 다음과 같이 계산한다. Algorithm 메쉬위의 기준점에서 다른 점들까지의 최단거리를 구하는 알고리즘을 알아보자. Dijkstra 알고리즘과 비슷한 형태의 동적 프로그래밍 방식을 사용한다. 위에서 설명한 Ui 를 기준점에서 주변 영역까지 계산..
측지 극좌표 (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의 한 면 각 다면체의 에지 첫번째와 두번째 테스트 : 한 오브젝트가 다른 오브젝트 모든 면의 반대편에 있다면 둘은 만나지 않음을 의미한다. 세번째 테스트 : 모든 면이 둘을 분리하는 평면을 형성할 수 없는 경우, 두 다면체의 에지를 서로 외적하여 얻은 벡터가 ..
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..