Terrain 2001.11.27 김 성 남

Contents Terrain Rendering Overview What is DEM? Lindstrom’s Algorithm Block-Based Simplification Vertex-Based Simplification Vertex Dependencies Other Issues Memory Menagement Summary

Overview(1/3) 응용분야 Flight Simulator Multi player 3D network game Prince of Darkness(PM of Hoppe) Tribes(Lindstrom algorithm)

Overview(2/3) Terrain Data representation TIN(Triangulated Irregular Network) DEM(Digital Elevation Model) or Height Field TIN(x,y,z) DEM(x,y,h(x,y))

Overview(3/3) DEM vs. TIN DEM TIN 저장 간단 저장 복잡 위성 데이터로부터 쉽게 획득 별도의 데이터 생성과정 요구 지형의 특성과 무관하게 vertex의 개수가 정해짐 지형의 특성에 따라 vertex의 개수가 달라짐

What is DEM? Height Field 높이 값만을 저장하고 있는 2차원 배열 배열의 Index가 x, y 좌표로 사용 LOD 적용 용이 x y z 18 20 15 30 25 10 7

Lindstrom’s Algorithm Bottom-up LOD Block-Based Simplification Vertex-Based Simplification Vertex Dependencies

Quadtree DEM Quadtree 3 X 3 vertex들로 이루어진 영역 : Block Level K block은 level K+1의 4개 Block을 자식으로 가짐 Level 1 Level 2 Level 3 low Resolution high high Level low

Vertex-Based Simplification Corner vetex를 제외한 block내 5개의 vertex 불필요한 vertex 제거 한 쌍(triangle, co-triangle)이 하나로 합쳐짐: base vertex 제거 Recursively !! Base vertex (Triangle, co-triangle) pair

Error Metric(1/5) vertex 간략화(제거) 기준 vertex 간략화를 통해 발생한 error가 어떤 임계치 τ 보다 작으면 vertex 제거 x y z C E B A

Error Metric(2/5) δ 선분의 중점 v가 눈 좌표계의 z축 상에 있다고 가정 Projection plane Eye coordinates e(view point) d C E v+ v v- B A

Error Metric(3/5) View matrix

Error Metric(4/5) Screen 에서 계산된 δ λ : world coordinates 단위 길이가 screen에서 차지하는 pixel 수

Error Metric(5/5) δscreen을 τ 와 비교 속도 향상을 위해 제곱값 비교

Block-Based Simplification(1/2) 모든 vertex에 대해 δscreen을 계산 DEM 간략화를 수행하면 계산량이 방대해짐 Block 내의 5개의 vertex를 한번에 제거 가능여부 검사 인접한 4개 block이 블록 간략화가 된다면 higher level로 이전

Block-Based Simplification(2/2) Block내에서 world coordintes의 δmax값을 미리 계산 “δmax<= δ0 가 성립하면 해당 block의 모든 제거 후보 vertex의 δ값 투영치가 임계치 τ 보다 작음이 보장” 되는 δ0 계산 인접한 4개 block이 블록 간략화되면 higher level(low resolution) 로 이전 이러한 과정은 재귀적(recursive)으로 수행

Crack Quadtree의 인접영역에서 vertex 불일치 발생 Crack 생성 crack Block 간략화 결과

Vertex Dependencies(1/3) 두개의 직각 이등변 삼각형이 합쳐져 하나의 이등변 삼각형 구성 두개의 직각 이등변 삼각형의 base vertex가 삭제되면서 두 삼각형의 shared edge가 제거 반대로, Base vertex가 mesh에 삽입되기 위해서는 shared edge, apex vertex가 반드시 필요 Base vertex

Vertex Dependencies(2/3) 어떤 vertex가 제거되지 않는다고 결정되면, 그 vertex가 종속되는 vertex가 반드시 존재 는 에 종속 ( depend on )

Vertex Dependencies(3/3) Forced split Vertex dependencies를 이용한 crack 제거 Refinement 될 필요가 없는 추가적인 triangles 생성

Block Rendering Binary tree 개념을 이용한 rendering Triangle strip을 이용한 rendering

Other Issues Terrain Pages Memory Management To minimize memory usage, apply unsigned short type for height and queue indices 광대한 지형을 한꺼번에 memory에 load할 수 없으므로, 효율적으로 memory에 load, computation할 수 있는 적당한 크기의 Terrain pages 생성 View 이동에 따라 page in and out, crack 방지 Memory Management Height field를 제외하고, 가능한 한 많은 부분(texture coordinates , etc)을 pages간에 공유 현재 지형 모델에서 가장 많이 연구되고 있는 분야

Lindstrom Demo Peter Lindstrom et al., “Real-Time, Continuous Level of Detail Rendering of Height Field”, SIGGRAPH96

Summary DEM(Digital Elevation Model) Lindstrom’s Algorithm(Bottom-up LOD) Block-Based Simplification Vertex-Based Simplification Vertex Dependencies(No crack and Forced Split) Memory Management