Rendering Techniques HyoungSeok Kim

Presentation on theme: "Rendering Techniques HyoungSeok Kim"— Presentation transcript:

1 Rendering Techniques HyoungSeok Kim
Multimedia Workshop Rendering Techniques HyoungSeok Kim

2 VR Rendering Techniques
가시성 처리 Dongeui University

3 가상현실 렌더링 기술 가시성 처리 영상 기반 모델링 & 렌더링 다중 해상도 기법
보이지 않는 부분에 대한 불필요한 계산을 제거하기 위해 영상 기반 모델링 & 렌더링 복잡한 모델을 텍스처로 대치 다중 해상도 기법 복잡한 물체에 대한 여러 개의 모델을 미리 생성한 후 시점에 따라 적당한 크기의 모델을 사용 Dongeui University

4 가시성 처리 Why? 앞, 뒤에 있는 물체간의 가림을 제대로 표현하기 위해 렌더링 속도 향상
보이지 않는 부분에 대한 불필요한 계산을 제거 Dongeui University

5 가시성 문제 현재 시점으로부터 보이는 물체만 선택 가상환경에 따라 전체 모델은 보이는 부분에 비해 매우 큰 경우 존재
Dongeui University

6 가시성 문제 어느 쪽 ? viewer 가 볼 수 없는 face를 제거하는 algorithm 물체를 화면에 표시할 때,
해결책 ? hidden-surface elimination algorithm 물체의 숨은 면을 제거 = visible-surface detection algorithm 어느 쪽 ? Dongeui University

7 Hidden-Surface Removal Algorithms
Back-face elimination Object-space approaches 3D 에서 face 간의 순서를 부여 painter’s algorithm Binary Space Partition Trees Image-space approaches pixel 마다 보이는 물체를 찾음 Z-buffer Ray Casting Dongeui University

8 Back Face Culling Front face : camera 쪽으로 향한 face –90    90
화면에 나와야 한다 Back face : camera 반대 쪽을 향한 face  < –90,  > 90 화면에 나오면 안 된다  Nfront V : view vector Nback Dongeui University

9 Back Face Culling back face front face
view coordinate system 에서는 back-face를 화면에 표시할 필요가 없다 다른 면에 의해서 가려지므로 back face front face Dongeui University

10 Back Face Culling 문제점 front face Dongeui University

11 Depth Sort Algorithm sorting (C,B,A) painting Painter’s Algorithm y -z
모든 물체를 카메라에서 먼 것부터 정렬 view coordinate system 에서 정렬 멀리 있는 것부터 그린다. 가려진 부분은 자동적으로 지워진다 A B C y x z -z sorting painting (C,B,A) Dongeui University

12 depth-sort (Newell의 방법)
Polygon P와 Q가 X-Y평면에서 겹치지 않으면 그리는 순서는 무관 P의 z값 범위가 Q 앞에 있으면 P를 Q보다 나중에 그림 Dongeui University

13 Depth Sort Algorithm P를 Q보다 먼저 그릴 조건 Does the order exist always ?
Z-extent of Q is wholly in front of P or Y-extent of Q does not overlap P or X-extent of Q does not overlap P or All points on P lie on the opposite side of Q than the COP or All points on Q lie on the same side of P as the COP or The projections of P and Q on the XY plane do not overlap (full 2D polygon overlap test) Does the order exist always ? No. What is a counterexample ? Dongeui University

14 Depth Sort Algorithm 문제점 B A B A C (C, A, B) 순서 순서대로 정렬할 수 없는 경우도 있다
해결책 : 물체를 2개 이상으로 분리 B A B A C (C, A, B) 순서 Dongeui University

15 Z-buffer Algorithm z1 아이디어 화면 상의 pixel 하나를 그릴 때 마다 z 좌표도 함께 기억
Dongeui University

16 Z-buffer Algorithm 초기 : 모든 pixel 의 z-좌표는 – pixel 을 그릴 필요가 있으면,
if (zpixel < zobject) then update zpixel = zobject update a new color at the pixel else ignore Dongeui University

17 Z-buffer Algorithm Coherence pixel 단위 처리일 때, 매번 다시 계산하지 않음
two points on a polygon (x1, y1, z1), (x2, y2, z2) a x + b y + c z + d = 0 plane equation x = x2 – x1, y = y2 – y1, z = z2 – z1 a x + b y + c z = 0 바로 옆 pixel 로 이동시, x = 1, y = 0 z = –(c/a) x Dongeui University

18 Z-buffer Algorithm Image space algorithm 모든 물체는 일단 화면까지 projection 된다
Simple & efficient 대부분의 video card 가 채택 OpenGL에서도 사용 단점 : 메모리가 많이 필요 pixel 하나 마다 (R, G, B, Z) 로 저장 Z 좌표를 저장하기 위한 메모리 필요 Dongeui University

19 Z-buffer Algorithm Original Mesh Backface culling Z-buffer algorithm
Dongeui University

20 Rasterize the polygon scan line by scan line
Scan-line Algorithm Rasterize the polygon scan line by scan line determine the visible polygon by incremental depth calculation used by Macintosh 3D video cards Dongeui University

21 Ray Casting Algorithm Rendering + visibility ALGORITHM loop y loop x
shoot ray from eye point through pixel (x,y) into scene intersect with all surfaces, find first one the ray hits shade that point to compute the color of pixel (x,y) Dongeui University

22 Ray Casting Algorithm Dongeui University

23 Comparison Z-buffer Scanline initialize z-buffer loop objects loop y
loop x if z(x,y) < zbuf[x,y] zbuf[x,y] = z(x,y) write image pixel; Scanline sort objects by y loop y sort active objects by x; loop x find active object with min z; write pixel; Dongeui University

24 Comparison Painter’s Ray Casting sort objects by z (back-to-front)
loop objects loop y loop x write pixel Ray Casting loop y loop x loop objects find object with min z; write pixel; Dongeui University

25 BSP Trees Binary Space Partition Trees 기존의 list ordering 방법은 일반적이지 못함
제대로 표현하지 못하는 경우 발생 BSP tree는 일반적인 방법 자동화된 방법 Shooting 게임 등에서 사용 두 단계 시점에 독립적인 BSP tree 생성 재귀적 또는 순차적 생성 현 시점으로부터 BSP tree를 방문하면서 가시성 순서 결정 Dongeui University

26 재귀적 BSP Tree 생성 BSP tree ? {1, 2, 3, 4, 5, 6} A set of polygons
Dongeui University

27 재귀적 BSP Tree 생성 Select one polygon and partition the space and the polygons Dongeui University

28 재귀적 BSP Tree 생성 Recursively partition each sub-tree until all polygons are used up Dongeui University

29 재귀적 BSP Tree 생성 방법 공간을 구분하는 polygon의 집합과 빈 BSP tree로부터 시작
하나의 polygon을 임의로 선택하고 root로 설정 선택한 polygon으로부터 나머지 전체 polygon들을 세 그룹으로 나눔 : 앞, 뒤, 동일 평면 선택된 polygon과 교차하는 polygon은 분할 위의 작업을 “앞”, “뒤”로 나뉜 집합에 따라 재귀적으로 적용 두개의 subtree를 생성: 앞/뒤 집합에 대해 Dongeui University

30 BSP 생성의 예 각 노드는 분할된 영역을 표시 (중간/최종) root는 전 영역 Leaf 노드들은 동일 영역에 해당
Dongeui University

31 Polygons을 BSP tree로 표현한 예
Dongeui University

32 Back-to-Front Traversal Algorithm
BSP 노드 방문 알고리즘 Back-to-Front Traversal Algorithm void traverse_btf(Tree *t, Point vp) { if (t = NULL) return; else { if (vp in-front of plane at root of t) { traverse_btf (t->back, vp); draw polygons on node of t; traverse_btf (t->front, vp); } traverse_btf(t->front, vp); traverse_btf(t->back, vp); Dongeui University

33 Interactive BSP tree demo
Dongeui University

34 VR Rendering Techniques
영상 기반 모델링 & 렌더링 Dongeui University

35 개요 2D images  3D model 방법 복잡한 모델을 실사의 텍스처로 대치 Photogrammetry (사진계측)
Disparity 를 이용 Stereo camera Solve Correspondence problem 소실점 이용 상세한 표현이 어려움 Dongeui University

36 종류 Image-based Modeling Image-based Rendering Image-based Acceleration
여러 시점의 2차원 영상을 이용하여 3차원 모델 생성 Image-based Rendering 2차원 영상의 조합으로부터 새로운 시점의 영상 생성 Image-based Acceleration 물체가 가까이 있을 때는 geometric model 사용, 멀리 있을 때는 영상으로 대체 Image-based lighting 2차원 영상으로부터 조명정보를 추출 새로운 광원을 부여 Dongeui University

37 기술 및 장단점 장점 문제점 Computer Vision + Computer Graphics 영상의 복잡도에 독립적
사실감이 높은 영상 생성 문제점 동적 환경에는 적용하기 어려움 영상 왜곡현상 부정확한 영상 (근접 영상) Dongeui University

38 예시 UC Berkeley campus 영화: 매트릭스
UC Berkeley campus 영화: 매트릭스 Dongeui University

39 예시 http://hyomin.deu.ac.kr/~hskim/hskim-lec/hskim-lec.html
Dongeui University

40 VR Rendering Techniques
다중 해상도 기법 Dongeui University

41 개요 Multi-resolution representation 시점으로부터 멀리 있는 물체는 보이는 정도의 복잡도만을 표현
복잡한 물체에 대한 여러 개의 모델을 미리 생성한 후 시점에 따라 적당한 크기의 모델을 사용 Dongeui University

42 LOD 선택의 기준 거리 크기 시각 속도 Dongeui University

43 Distance LOD 계산이 쉽다 (3-D Euclidean distance) Scale dependent
Resolution dependent Field of View dependent d1 d2 Dongeui University

44 Size LOD 3D  2D projection 필요 Scale invariant Resolution invariant
Field of View invariant Bounding Box Bounding Spheres Bounding ellipsoids Dongeui University

45 Eccentricity LOD  Visual periphery(시각)에 따라 결정
사용자가 정면으로 보고 있는 것을 고해상도로 표현 인간의 시각적 감지를 근거로 사용 옆에 있는 물체는 잘 감지하지 못함 Eye tracking system을 사용  Dongeui University

46 Velocity LOD 사용자를 지나는 각속도에 근거 빠르게 지나는 물체는 저해상도로 표현
빠르게 지나는 물체는 사람의 눈에 흐리게 보임 Eye tracking 장비를 사용하지 않고 각속도를 추정하여 사용 20 deg/s 1 deg/s Dongeui University

47 LOD 기법 Static LOD (Level of Detail) Dynamic LOD 시점에 무관 미리 다중 모델 생성
실시간으로 모델 변형 Dongeui University

48 Static LOD 미리 여러 가지 해상도의 모델 생성 실행 중, 물체와의 거리에 따라(또는 이와 유사한 기준) 모델을 선택
LOD가 정해진 해상도로 미리 만들어 지므로 Static LOD라 부름 Dongeui University

49 Static LOD 장점 단점 간단하다 실시간으로 모델을 변형시킬 필요가 없으므로 계산이 용이하다 모델이 갑자기 바뀌는 효과
복잡한 물체의 경우 부품마다 독립적으로 다루어져야 한다 Dongeui University

50 Dynamic LOD 실행 중 적당한 LOD를 계산하고 생성 시점에 따라 적당한 모델을 실시간으로 생성
Dongeui University

51 Dynamic LOD 장점 리소스의 효율적 사용 향상된 성능 모델이 갑자기 바뀌는 효과를 줄일 수 있음
view-dependent LOD (시점 종속적인 LOD) 구현이 가능 11,726 triangles 34,321 triangles Dongeui University