Microsoft PowerPoint - Class10_LOD와자료구조.pptx

Similar documents
Microsoft PowerPoint - Week04_DirectX9 프로그래밍의 기초2.pptx

Microsoft PowerPoint - GameProgramming15-MeshII

untitled

(Microsoft PowerPoint - \301\24615\260\255 - \303\346\265\271\303\263\270\256)

LIDAR와 영상 Data Fusion에 의한 건물 자동추출

Microsoft PowerPoint - gpgpu_proximity.ppt

MPEG-4 Visual & 응용 장의선 삼성종합기술원멀티미디어랩

12¿ù 1~30

2005CG01.PDF

Chap 6: Graphs

2002년 2학기 자료구조

04_오픈지엘API.key

PowerPoint Presentation

Chap 6: Graphs

14.이동천교수님수정

融合先验信息到三维重建 组会报 告[2]

<4D F736F F F696E74202D B30395FBAEDB7BBB5F95FBDBAC5D9BDC7B9F6C6DB5FB1D7B8B2C0DA2E >

untitled

chap 5: Trees

Microsoft PowerPoint - 05geometry.ppt

Microsoft PowerPoint - GameProgramming23-PixelShader.ppt

chap 5: Trees

서피스셰이더프로그램 셰이더개발을쉽게! Thursday, April 12, 12

Microsoft PowerPoint - Chap5 [호환 모드]

Microsoft PowerPoint - NV40_Korea_KR_2.ppt

Chap 6: Graphs

Microsoft PowerPoint - GameDesign6-Graphics.ppt [호환 모드]

Microsoft PowerPoint - 04-Model Class.pptx

LiDAR A utomatic D etection for Misclassified A erial LiD A R D TD

19_9_767.hwp

01이국세_ok.hwp

Microsoft PowerPoint - Week03_DirectX9 프로그래밍의 기초.pptx

슬라이드 1

Łø·ŸÕ=¤ ¬ ÇX±xÒ¸ 06 - Èpº– 1

05_tree


<4D F736F F F696E74202D20C1A63130B0AD202D20C1F6C7FCB0FA20C7CFB4C3C0C720B7BBB4F5B8B5>

63-69±è´ë¿µ

Your title goes here

周 縁 の 文 化 交 渉 学 シリーズ 3 陵 墓 からみた 東 アジア 諸 国 の 位 相 朝 鮮 王 陵 とその 周 縁 머리말 조선시대에 왕(비)이 사망하면 그 육신은 땅에 묻어 陵 을 조성하고, 삼년상이 지나면 그 혼을 국가 사당인 종묘에 모셔 놓았다. 양자는 모두 국가의

?

Microsoft PowerPoint - dev6_TCAD.ppt [호환 모드]

Microsoft PowerPoint - ch10 - 이진트리, AVL 트리, 트리 응용 pm0600

<C0E5B7C1BBF328BEEEB8B0C0CCB5E9C0C729202D20C3D6C1BE2E687770>

03.Agile.key

PowerPoint 프레젠테이션

(Microsoft PowerPoint - \301\24613\260\255 - oFusion \276\300 \261\270\274\272)

<4D F736F F F696E74202D20C1A63034B0AD202D20C7C1B7B9C0D3B8AEBDBAB3CABFCD20B9ABB9F6C6DBC0D4B7C2>

2014ijµåÄ·¾È³»Àå-µ¿°è ÃÖÁ¾

À±½Â¿í Ãâ·Â

[ReadyToCameral]RUF¹öÆÛ(CSTA02-29).hwp

VOL /2 Technical SmartPlant Materials - Document Management SmartPlant Materials에서 기본적인 Document를 관리하고자 할 때 필요한 세팅, 파일 업로드 방법 그리고 Path Type인 Ph

I

Microsoft PowerPoint - 제8장-트리.pptx

3월-기획특집1-4


Microsoft PowerPoint - ch12 - Graph, Graph Algorithms

Microsoft Word - 1-차우창.doc

슬라이드 1

산선생의 집입니다. 환영해요

금오공대 컴퓨터공학전공 강의자료

,. 3D 2D 3D. 3D. 3D.. 3D 90. Ross. Ross [1]. T. Okino MTD(modified time difference) [2], Y. Matsumoto (motion parallax) [3]. [4], [5,6,7,8] D/3

00내지1번2번


Çмú´ëȸ¿Ï¼º

2012³â8¿ùÈ£˙ȸš

example code are examined in this stage The low pressure pressurizer reactor trip module of the Plant Protection System was programmed as subject for


15_3oracle

유니 앞부속

슬라이드 1

이용석 박환용 - 베이비부머의 특성에 따른 주택유형 선택 변화 연구.hwp

PowerPoint Presentation

디지털영상처리3

( )업계소식

( )전국네트워크


( )업계소식

( )업계소식(14.01월)

Microsoft PowerPoint - ch12 - Graph, Graph Algorithms

숭실브로슈어 표지 [Converted]

untitled

슬라이드 1


기사전기산업_41-56

untitled

Dialog Box 실행파일을 Web에 포함시키는 방법

hwp

호-11

(1 일목 ) 제 3 발표장 47 수치기법 [I] 이은택 1, 안형택 2* SIMULATION ON FLOW PAST A CIRCULAR CYLINDER USING UNSTRUCTURED MESH BASED INCOMPRESSIBLE FLUID SOLVER(ULSAN3

<B0A3C1F6315FC6EDC1FDC0A7BFF8C8B82E687770>

ePapyrus PDF Document

8-15(3)-02(손태근).fm

제 출 문 국방부 장관 귀하 본 보고서를 국방부 군인연금과에서 당연구원에 의뢰한 군인연금기금 체 계적 관리방안 연구용역의 최종보고서로 제출합니다 (주)한국채권연구원 대표이사 오 규 철

7장

Microsoft PowerPoint - 알고리즘_5주차_1차시.pptx

001.hwp

(Microsoft PowerPoint - \301\24608\260\255 - \261\244\277\370\260\372 \300\347\301\372)

K&R2 Reference Manual 번역본

김기남_ATDC2016_160620_[키노트].key

Transcription:

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