Rendering Techniques HyoungSeok Kim Multimedia Workshop Rendering Techniques HyoungSeok Kim

VR Rendering Techniques 가시성 처리 Dongeui University

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

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

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

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

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

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

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

Back Face Culling 문제점 front face Dongeui University

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

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

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

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

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

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

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

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

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

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

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

Ray Casting Algorithm Dongeui University

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

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

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

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

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

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

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

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

Polygons을 BSP tree로 표현한 예 Dongeui University

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

Interactive BSP tree demo http://symbolcraft.com/graphics/bsp/bsptreedemo_korean.html Dongeui University

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

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

종류 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

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

예시 UC Berkeley campus 영화: 매트릭스 http://whatisthematrix.warnerbros.com/dld/NUMBER_THREE.mov UC Berkeley campus 영화: 매트릭스 Dongeui University

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

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

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

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

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

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

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

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

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

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

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

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

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