LOD 와자료구조
목 차 LOD 공간자료구조 LOD 바운딩볼륨계층구조 Selection Criteria BSP 트리 종류 8진트리 Errors 장면그래프 Operators Terrain LOD Progressive Mesh 애니메이션및게임실습 2
LOD
LOD 대용량 3D 데이터처리의필요성 Scientific and medical visualization Architectural and industrial CAD Training (military and otherwise) Entertainment 애니메이션및게임실습 4
LOD 700,000000 polygons Courtesy General Dynamics, Electric Boat Div. 애니메이션및게임실습 5
LOD 13,000,000 polygons (Anonymous) 애니메이션및게임실습 6
LOD 16,700,000 000 polygons Deussen et al: Realistic Modeling of Plant Ecosystems 애니메이션및게임실습 7
LOD 82,000,000 polygons Courtesy Newport News Shipbuilding 애니메이션및게임실습 8
LOD David D id 56,230,343 polygons St. Matthew 372,422,615 polygons Courtesy Digital Michelangelo Project 애니메이션 및 게임 실습 9
LOD Level of Detail 의생성 69,451 polys 2,502 polys 251 polys 76 polys 애니메이션및게임실습 10
LOD 거리에따른정밀도차등 애니메이션및게임실습 11
Selection Criteria LOD 레벨을선택하기위한기준 Distance Size Velocity Eccentricity Depth of Field Fixed-frame rate schedulers Hysteresis Priority schemes Alpha-blended transitions Geomorph transitions 애니메이션및게임실습 12
Selection Criteria Distance d 1 d 2 애니메이션및게임실습 13
Selection Criteria Size 애니메이션및게임실습 14
Selection Criteria Eccentricity it θ 애니메이션및게임실습 15
Selection Criteria Velocity 1 deg/s 20 deg/s 애니메이션및게임실습 16
Selection Criteria Depth of Field Panum s fusional area 애니메이션및게임실습 17
Selection Criteria Fixed-Frame F Rate Schedulers 애니메이션및게임실습 18
Selection Criteria Alpha-blended d transitions 애니메이션및게임실습 19
종류 LOD 의종류 Discrete LOD Continuous LOD View-Dependent LOD 애니메이션및게임실습 20
종류 Discrete LOD Static LOD 오프라인에서미리레벨별데이터생성 렌더링시레벨에맞는데이터선택 장점 가장단순한방식 가장빠른성능 실시간게임등에주로사용 애니메이션및게임실습 21
종류 Discrete LOD 단점 급격한변화 (popping) 애니메이션및게임실습 22
종류 Continuous LOD 실시간처리 장점 단점 정확한, 정밀한표현가능 부드러운전환 View-Dependent LOD 지원 실시간계산량의증대 애니메이션및게임실습 23
종류 View-Dependent Vi D d t LOD View from eyepoint Birds-eye y view 애니메이션 및 게임 실습 24
종류 View-Dependent LOD 애니메이션및게임실습 25
종류 View-Dependent LOD 34,321 triangles 애니메이션및게임실습 26
종류 View-Dependent LOD 11,726 triangles 애니메이션및게임실습 27
Errors 에러를계산하는이유 간략화과정의지침 결과의품질예측 특정 LOD 방법의선택 대용량환경을위한품질조절가능 애니메이션및게임실습 28
Errors 에러의종류 Geometric Error Attribute Error 애니메이션및게임실습 29
Errors Geometric Error 3D 데이터의모양변형에대한에러 스크린공간에서의모양유지 실루엣유지 Vertex-Vertex Distance Vertex-Plane Distance Point-Surface Distance Surface-Surface Distance 애니메이션및게임실습 30
Errors Vertex-Vertex V t Distance v 3 v 1 v 2 애니메이션및게임실습 31
Errors Vertex-Plane Distance Error Quadric c a b a b c 애니메이션및게임실습 32
Errors Vertex-Surface Distance Progressive Mesh 애니메이션및게임실습 33
Errors Surface-Surface S f Distance Simplification Envelopes 애니메이션및게임실습 34
Errors Attribute t Error 색상, 법선, 텍스처좌표에러 최종픽셀값의정확도향상 애니메이션및게임실습 35
Operators LOD Operators Local Operators Edge Collapse Vertex-Pair Collapse Triangle Collapse Cell Collapse Vertex Removal Polygon Merging General Geometric Replacement Global Operators Volume Processing Alpha-Hull-Based Topology Simplifications 애니메이션및게임실습 36
Operators Edge Collapse 애니메이션및게임실습 37
Operators Edge Collapse 애니메이션및게임실습 38
Operators Vertex-Pair Collapse 애니메이션및게임실습 39
Operators Ti Triangle Collapse 애니메이션및게임실습 40
Operators Cell Collapse 애니메이션및게임실습 41
Operators Vertex Removal and Polygon Merging 애니메이션및게임실습 42
Operators General Geometric Replacement 애니메이션및게임실습 43
Operators Volume Processing 애니메이션및게임실습 44
Operators Volume Processing 애니메이션및게임실습 45
Operators Alpha-Hull-Based ll Topology Simplifications 애니메이션및게임실습 46
Operators Alpha-Hull-Based ll Topology Simplifications 애니메이션및게임실습 47
Terrain LOD 지형 LOD LOD 가실제로가장많이사용되는분야 사용분야 Flight simulators Terrain-based computer games Geographic Information Systems (GIS) Virtual tourism, real-estate, mission planning 애니메이션및게임실습 48
Terrain LOD 지형 LOD vs 일반 LOD Terrain is easier... 일반기하는제약조건이많음 균등분할그리드를사용 특성화될수있고, 단순알고리즘의사용 Terrain is more difficult... 연속적이고거대한모델 매우가까우면서매우먼모델 뷰의존적인모델 out-of-core를이용한페이징이필요함 애니메이션및게임실습 49
Terrain LOD 대형지형데이터베이스 USGS GTOPO30 30 arc-second (~1 km) resolution elevation 43,200 x 21,600 = 1.8 billion triangles NASA EOS satellite ASTER 30-m resolution elevation data from 15-m near infrared stereo imagery USGS National Elevation Dataset (NED) 50,000 quads at around 50 GB 애니메이션및게임실습 50
Terrain LOD Regular Grid 균등분할 저장과처리가쉬움 고도를찾기위한보간이쉬움 디스크 / 메모리효율성 : Z 값만사용 뷰컬링과충돌검출이쉬움 애니메이션및게임실습 51
Terrain LOD TINs Triangulated Irregular Networks 적은수의삼각형사용 복잡한지역은세밀히, 단순한지역은단순하게 최대점, 최소점, 능선, 계곡, 동굴표현가능 애니메이션및게임실습 52
Terrain LOD 지형 LOD 예제 Hunter-Liggett US Army base 2-m res 8 x 8km 32 M polys 애니메이션및게임실습 53
Terrain LOD 지형 LOD 예제 애니메이션및게임실습 54
Terrain LOD 지형 LOD 예제 Hawai i 애니메이션및게임실습 55
Terrain LOD 지형 LOD 예제 애니메이션및게임실습 56
Terrain LOD 지형 LOD 예제 Puget Sound, Washington 16,385 x 16,385 512 MB 애니메이션및게임실습 57
Progressive Mesh Hugues Hoppe, 1996 Preserve appearance Lossless Continuous-resolution Efficient Progressive 애니메이션및게임실습 58
Progressive Mesh 간략화 v t ecol(v s,v t, v s ) v l v r v l v s v r v s (optimization) 애니메이션및게임실습 59
Progressive Mesh 간략화과정 13,546 500 152 150 ^ M=M n ecol n-1 M 175 M 1 ecol i ecol 0 M 0 애니메이션및게임실습 60
Progressive Mesh 상세화 attributes vspl(v p( s,v l,v r, v s,v t, ) v l v r v l v r v s v t v s 애니메이션및게임실습 61
Progressive Mesh 상세화과정 150 152 500 13,546 M 0 M 1 M 0 M 175 vspl 0 vspl i i vspl n-1 n-1 0 i n 1 progressive mesh (PM) representation M n =M^ 애니메이션및게임실습 62
Progressive Mesh M f M f-1 M f-2 M n v1 v1 v1 M 0 v 2 v 3 v 2 v 3 ecol v 2 v 3 ecol M c v 1 v 2 v 3 v 4 v 5 ecol v 4 v 5 v 4 v 5 v 6 v 6 v 6 v 7 v 7 v 8 애니메이션및게임실습 63
Progressive Mesh 프로그레시브메쉬생성 HRESULT D3DXGeneratePMesh( LPD3DXMESH pmesh, // 원본메쉬 CONST DWORD *padjacency, // 인접정보 CONST LPD3DXATTRIBUTEWEIGHTS pvertexattributeweights, // 속성영향력 CONST FLOAT *pvertexweights, // 정점영향력 DWORD MinValue, // 최소정점혹은면의수 DWORD Options, // 영향력의적용범위 LPD3DXPMESH **pppmesh // 생성된프로그레시브메쉬 ) Options D3DXMESHSIMP_VERTEX : MinValue 가정점에적용됨 D3DXMESHSIMP_FACE : MinValue가면에적용됨 애니메이션및게임실습 64
Progressive Mesh 정점속성영향력 typedef struct _D3DXATTRIBUTEWEIGHTS { FLOAT Position; FLOAT Boundary; FLOAT Normal; FLOAT Diffuse; FLOAT Specular; FLOAT Texcoord[8]; FLOAT Tangent; FLOAT Binormal; } D3DXATTRIBUTEWEIGHTS; D3DXATTRIBUTEWEIGHTS AttributeWeights; AttributeWeights.Position = 1.0; AttributeWeights.Boundary = 1.0; AttributeWeights.Normal = 1.0; AttributeWeights.Diffuse = 0.0; AttributeWeights.Specular = 0.0; AttributeWeights.Tex[8] = {0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0} 애니메이션및게임실습 65
Progressive Mesh ID3DXPMesh ID3DXBaseMesh 인터페이스의상속 DWORD GetMaxFaces(VOID) DWORD GetMaxVertices(VOID) DWORD GetMinFaces(VOID) DWORD GetMinVertices(VOID) : 최대면수 : 최대정점수 : 최소면수 : 최소정점수 HRESULT SetNumFaces(DWORD Faces) 메쉬의면수설정 HRESULT SetNumVertices(DWORD Vertices) 메쉬의정점수설정 애니메이션및게임실습 66
Progressive Mesh ID3DXPMesh // 새로운최소 / 최대면수설정 HRESULT TrimByFaces( DWORD NewFacesMin, DWORD NewFacesMax, a DWORD *rgifaceremap, DWORD *rgivertremap ) // 새로운최소 / 최대정점수설정 HRESULT TrimByVertices( DWORD NewVerticesMin, DWORD NewVerticesMax, DWORD *rgifaceremap, DWORD *rgivertremap ) // 면리맵정보 // 정점리맵정보 // 면리맵정보 // 정점리맵정보 애니메이션및게임실습 67
Progressive Mesh 예제 애니메이션및게임실습 68
공간자료구조
공간자료구조 개요 객체를 2D 또는 3D로분할하는자료구조 보다빠른처리를목표로함 Faster real-time rendering Faster intersection testing Faster collisioned detection Faster ray tracing and global illumination 사용분야 게임 영화렌더링툴 애니메이션및게임실습 70
공간자료구조 계층형분할 In 2D space Data structure 애니메이션및게임실습 71
공간자료구조 활용방법 애니메이션및게임실습 72
바운딩볼륨계층구조 바운딩볼륨 (BV) 일단의객체들을내포하는볼륨 BV 가포함하고있는물체들보다더단순한기하형태 구 (Sphere) 축에정렬된바운딩박스 (AABB) 방향성바운딩박스 (OBB) k-dops 렌더링, 다른계산, 각종검사기능을가속화하는데사용 애니메이션및게임실습 73
바운딩볼륨계층구조 바운딩볼륨 (BV) AABB 모든축 (X,Y,Z) 에대해최소, 최대인정점을가지고객체를감싸는육면체를만든것 객체회전시재생성필요 애니메이션및게임실습 74
바운딩볼륨계층구조 바운딩볼륨 (BV) Bounding Sphere 객체가길쭉한형태이거나구모양이아닐때비효율적 충돌검사시효율적 애니메이션및게임실습 75
바운딩볼륨계층구조 바운딩볼륨 (BV) OBB 주성분분석후객체를감쌀수있는가장작은육면체생성 경계구나 AABB보다경계볼륨의효율성이좋음 객체회전시 OBB 재생성필요없음 애니메이션및게임실습 76
바운딩볼륨계층구조 Bounding Volume Hierarchy 3차원장면의실시간렌더링을위한가장일반적인공간자료구조 계층적시각절두체선별에사용 루트노드 : 최상위노드, 부모가없음 내부노드 : 자식들에대한포인터 말단노드 : 렌더링될실제기하구조 애니메이션및게임실습 77
바운딩볼륨계층구조 BVH 의장점 다양한검사수행능력이탁월 동적으로변화하는장면에사용가능 애니메이션및게임실습 78
바운딩볼륨계층구조 BVH 의생성 (AABB) x is longest Find minimal boxes Split along longest axis Find minimal boxes 애니메이션및게임실습 79
BSP 트리 Binary Space Partitioning i 형태 축에정렬된형태 (axis-aligned) 다각형에정렬된형태 (polygon-aligned) 분할 공간을두개로분할하는평면사용 두공간으로기하구조들을정렬 반복 특징 트리에들어있는기하구조들이특정한시점을기준으로정렬 애니메이션및게임실습 80
BSP 트리 축에정렬된 (Axis-aligned) BSP 트리 Minimal box Split along plane Split along plane Split along plane 애니메이션및게임실습 81
BSP 트리 축에정렬된 (Axis-aligned) BSP 트리 B D Plane 2 E 1a 0 1b A Plane 1a Plane 0 Plane 1b C A B C 2 D E 애니메이션및게임실습 82
BSP 트리 축에정렬된 (Axis-aligned) BSP 트리 k-d 트리 루트노드 : x축을따라서분할 자식노드 : y축을따라서분할 손자노드 :z 축을따라서분할 박스의가장긴쪽을찾아서그방향으로분할 애니메이션및게임실습 83
BSP 트리 축에정렬된 (Axis-aligned) BSP 트리 Rough sorting 0 2 1a 1b 1a 0 1b A B C 2 eye 4 5 D E 1 3 2 애니메이션및게임실습 84
BSP 트리 다각형에정렬된 (Polygon-aligned) li BSP tree 다각형을공간분할을위한분할자로사용 애니메이션및게임실습 85
BSP 트리 다각형에정렬된 (Polygon-aligned) li BSP tree 최소교차기준법 (least-crossed criterion) 다각형선택방법 다수의후보다각형들을임의로선택 그중에서자신이속한평면이다른다각형들과교차하는횟수가가장적은다각형선택 애니메이션및게임실습 86
BSP 트리 다각형에정렬된 (Polygon-aligned) li BSP tree 장점 주어진관측조건에대해서그자료구조가뒤에서앞으로엄격하게순회될수있다 교차검사와충돌검출에유용 G, C, F, A, E, B, D 애니메이션및게임실습 87
8 진트리 Ot Octree 축에정렬된 BSP 트리와유사 하나의박스는세축을따라서동시에분할 분할되는점은박스의중심 8 개의새로운박스생성 애니메이션및게임실습 88
8 진트리 Ot Octree 애니메이션및게임실습 89
8 진트리 느슨한 8 진트리 (loose octree) 애니메이션및게임실습 90
장면그래프 Scene Graphs 높은수준의트리구조 기하의계층적구조 텍스처, 변환, 상세단계, 렌더링상태, 광원등추가 DAG(Directed Acyclic Graph) 우향비순환그래프 어떤루프나순환구조를가지지않으면서부모에서자식으로향하는일정한순서가있음 여러개의인스턴스를가지기때문 애니메이션및게임실습 91
장면그래프 Scene Graphs 애니메이션및게임실습 92
4 진트리와 LOD 예제 애니메이션및게임실습 93
4 진트리와 LOD 예제 애니메이션및게임실습 94
Question? 애니메이션및게임실습 95