Spatial Data Structures
목차
Spatial Data Structures
Data Structures for Computer Graphics
사실적인 그래픽스 화면을 랜더링하기 위해 필요한 요소
○ 더 많은 프레임
○ 더 높은 해상도 + 샘플링 비율
○ 더 사실적인 조명 표현
○ 더 복잡한 기하 모델 등등
→ 이를 위해 가속화 알고리즘 + 효율적인 자료구조가 필요합니다.
컴퓨터 그래픽스에서 사용하는 자료 구조들
○ 메시 (Mesh )
○ Scene Graph
○ 공간 자료 구조(Spatial Data Structures)
● Object partitioning : ex) bounding volume hierarchy (BVH)
● Space partitioning : ex) binary space partitioning (BSP)
Mesh Structure
* Triangular Mesh 조건
모든 edge는 두 triangle에 의해 공유되어야하며, 모든 vertex는 그 vertex를 공유하는 하나의 닫힌 Loop가 있어야 합니다.
(예외 : mesh에 boundary를 허용할 경우 열린 loop)
* 가장 단순한 경우
* Triangle - Neighbor Structure
삼각형이 각 주변 3개의 neighbor 삼각형을 저장하는 방식으로, 삼각형 메모리 사이즈가 고정적입니다.
* Winged - Edge Structure
각 edge에 주요 정보를 저장하는 방식으로, edge에 두 정점(head, tail)과 양옆 삼각형에 edge정보를 가집니다.
* Half - Edge Structure
Winged - edge를 두 단방향 edge로 나눈 것입니다. 이 때, V는 half-edge가 향하는 방향에 vertex이고 pair는 이 half edge의 반대 방향 half edge입니다. 즉 한 edge가 2개의 단방향으로 나뉘어 pair를 통해 방향을 뒤집을 수 있습니다.
Scene Graph
복잡한 Scene에서 여러 물체의 위치를 계층적 구조로 표현하는 방법으로, 물체에 적용되는 transformation을 tree 구조로 저장합니다.
Spatial Data Structure
그래픽스 연산을 가속화하기 위해 geometric object를 공간상에서 효율적으로 관리하는 자료구조가 필요합니다.
Ray tracing : 물체가 충돌하는지 빠르게 테스트
Computer game, physical simulation : scene에 있는 물체들이 서로 충돌하는지
Culling : viewing frustum안에 있지 않은 물체들을 제거하여 화면에서 제거
* Object partitioning method
물체를 겹치지 않는 그룹으로 나누고, 그룹의 계층을 둡니다. 물체가 중점이며, 물체를 묶은 그룹은 공간상에서 겹칠 수 있습니다.
* Space partitioning method
공간을 계층적으로 나눠 공간에 속하는 물체들을 묶습니다. 공간이 중점이며, 한 물체가 여러 partition에 속할 수 있습니다.
* Bounding Volume Hierarchy (Object Partitioning)
각 물체를 보다 단순한 물체로 완전히 감쌉니다. [박스(axis-aligned box, oriented box), 구, 사면체 등)
root부터 tree를 순회하며 기하 충돌을 감지합니다. 해당 서브 트리가 아닐 시 스킵가능합니다. Bounding volume들을 최대한 타이트하게 정의 할수록 더 많이 가속화됩니다.
* AABBox ray 체크
* AABBox vs Oriented Bounding Box
AABBox : 모든 면의 법선이 좌표축과 평행한 박스로 단순하다는 장점이 있지만, 박스가 물체에 비해 너무 클 수 있습니다.
바운딩 박스는 최대한 타이트하게 감싸야 합니다.
OBB : 타이트하게 박스를 축을 돌리며세팅해서 타이트하지만 축 계산도 포함되며 PCA 선형대수 작업이 필요하답니다.
(계층적인 하위 박스도 축 계산 필요)
* Uniform Spatial Partitioning
* Binary Space Partitioning
하나의 Scene을 cutting plane을 이용해서 좌우 서브트로리 나누고, 서브트리는 새로운 cutting plane을 이용해서 재귀적으로 나눕니다.
랜더링에서도 쓸 수 있는데 painter's algorithm이 있습니다. 물체를 뒤에서부터 앞의 순서로 그려(카메라 기준) 자연스럽게 물체간 가려지게 만듭니다.
