Microsoft PowerPoint - gpgpu_proximity.ppt

Size: px

Start display at page:

Download "Microsoft PowerPoint - gpgpu_proximity.ppt"

오현 채
5 years ago
Views:

1 Fast Geometric Computations using GPUs 김영준 이화여자대학교컴퓨터학과

2 Topics Collision detection Closest point query Approximate arrangement computation Ewha Womans University 2

3 Streaming AABBs Collision detection for deformable models Ewha Womans University 3

4 Teaser Video Ewha Womans University 4

5 Streaming AABB Pipeline 1. Stream setup 2. Stream calculation 3. Stream update Ewha Womans University 5

6 Streaming AABBs (a) Intersecting bunny models (b) Pre-computed AABB-trees (c) Intersecting AABB streams Pull Down Stream setup using pre-computed AABB Ewha Womans University 6 trees

7 Streaming AABBs Vertex textures MAX MIN AABB Streams Ewha Womans University 7

8 Streaming AABB Overlap Test Streaming AABBs of model B Ewha Womans University 8

9 Streaming CD Results Collision result of AABB pairs stored at an off-screen buffer Intersected models Ewha Womans University 9

10 Readback from GPU to CPU Readback from GPU to CPU is costly 50 milli-seconds for 1024x1024 frame buffer Hierarchical readback Ewha Womans University 10

11 Stream Reduction Level n Level 1 Level 0 Ewha Womans University 11

12 Readback Level 3 (P3) Level 2 (P2) Encoding Level 1 (P1) Level 0 (P0) Ewha Womans University 12

13 Readback Decoding Level 3 (P3) Level 2 (P2) Level 1 (P1) Level 0 (P0) Time (encoding) + Time (decoding) << Time (direct readback) Video Ewha Womans University 13

14 Primitive Level Test Triangle-triangle overlap test using CPUs Ewha Womans University 14

15 Stream Update Vertex textures Fragment shader Fragment program MAX MIN Framebuffer-1 Framebuffer-2 Multi-Rendering Targets (MRT) Ewha Womans University 15

16 Implemetation Streaming computation in GPUs nvidia GeForce 7800 GTX GPU (PCI-E) 512 MB video memory 32-bit floating point Serial computation in CPU 3.4 GHz Intel Dual Core Processor, 2.7 GB main memory Languange C++ in Windows nvidia s Cg (vp40 and fp40 profiles) OpenGL 2.0 Ewha Womans University 16

17 Benchmarking Scenarios (a) Interlocking torii (15000x2 triangles, FPS) (b) Touching torii (15000x2 triangles, FPS) (c) Merging torii (15000x2 triangles, FPS) (d) Bump bunnies (15000x2 triangles, FPS) (e) Happy buddhas (20000x2 triangles, FPS) (f) Intimate animals (50000x2 triangles, FPS) Ewha Womans University 17

18 Performance Comparison Three times performance improvement over CULLIDE No collision misses up to floating point precision Ewha Womans University 18

19 Demo Video Ewha Womans University 19

20 Parallel Triangle Intersection Test Using CUDA Triangles of Object2 (n2) b_hig (tri1, tri2) Triangles of Object1 (n1) b_wid

21 Implementation Environment Microsoft Visual Studio 2005 CUDA Toolkit/SDK 1.1 OpenGL Library Intel Core2Duo E6550 nvidia GeForce 8800 GTX Benchmarks Model 1 Model 2 Scenario 1 Sphere(960) Cylinder(216) Scenario 2 Cup(7580) Azucar(5250) Scenario 3 Cup(7580) Spoon(26012)

22 Intersection Results Sphere & Cylinder CPU vs. GPU(CUDA) Time (ms) CPU GPU(CUDA) times faster! Ewha Womans University

23 Intersection Results Cup & Azucar CPU vs. GPU(CUDA) Time (ms) CPU GPU(CUDA) times faster! Ewha Womans University

24 Intersection Results Cup & Spoon CPU vs. GPU(CUDA) Time (ms) CPU GPU(CUDA) times faster! Ewha Womans University

25 Closest Point Query Application to penetration depth computation Ewha Womans University 25

26 Closest Point Query Shortest distance from a point to the surface of the union of convex polytopes Approximate the query using GPUs easy difficult Ewha Womans University Young J. Kim 26

27 Closet Point Query Main Idea Incrementally expand the current front of the boundary Ewha Womans University Young J. Kim 27

28 Closest Point Query 1. Render front faces, and open up a window where z- value is less than the current front 2. Render back faces w/ z-greater-than test 3. Repeat the above m times, where m := # of obj s Ewha Womans University Young J. Kim 28

29 Closest Point Query 1. Render front faces, and open up a window where z- value is less than the current front 2. Render back faces w/ z-greater-than test 3. Repeat the above m times, where m := # of obj s Ewha Womans University Young J. Kim 29

30 Penetration Depth (PD) Minimum translational distance needed to separate objects Ewha Womans University Young J. Kim 30

31 Penetration Depth (PD) d Minimum translational distance needed to separate objects Ewha Womans University Young J. Kim 31

32 Penetration Depth PD determines the amount of repulsive forces in penalty-based, 6DOF haptic rendering Ewha Womans University Young J. Kim 32

33 Penetration Depth Shortest distance from the origin to the surface of convex Minkowski sum 0.3 sec 3.7 sec 1.9 sec 0.4 sec Ewha Womans University 33

34 Approximate Arrangement Computation Application to global visibility and swept volume

Arrangement C 44 C 11 C 33 C 22 A simple arrangement of 5 lines An arrangement of geometric objects is the decomposition of space induced by given geometric primitives The

35 Arrangement C 44 C 11 C 33 C 22 A simple arrangement of 5 lines An arrangement of geometric objects is the decomposition of space induced by given geometric primitives The outer envelope is defined as a boundary of the cell in an arrangement, which can be reached from the infinity [Halperin 97] Ewha Womans University 35

36 Motivations Engine of a BMW 5 with 3,741,833 triangles [Ernst 04] Car door with 782,018 triangles Ewha Womans University 36

37 Goal Remove invisible geometric elements when the inspection is performed from outside only Design reviews Visual inspection Training simulations Ewha Womans University 37

38 Infinite Number of Viewpoint Render the scene from infinite # of viewpoint [Ernst 04] Ewha Womans University 38

39 Main Contributions Robust and practical approach to find invisible elements from a given scene database Pose the problem as envelope computation Use of GPUs to accelerate the computation Ewha Womans University 39

40 Algorithm Overview Distance field representations Use GPUs Fast marching method Use CPUs Extract visible surface Use CPUs Ewha Womans University 40

41 Directional Distance Fields 3D voxel grid where each voxel contains a value of shortest distance to the surface We compute directional distance fields for six principal directions (+x, -x, +y, -y, +z, -z) Ewha Womans University 41

42 Distance Fields Computations P P R P R P R P R P R P R R P R Ewha Womans University 42 z

43 Distance Fields Computations primitive orthographic projection Z = D projection Y image plane X Z-buffer holds the directed distance values Ewha Womans University 43

44 Distance Fields Generation Ewha Womans University 44

45 Front Propagation Initial Front Final Front Ewha Womans University 45

46 Front Propagation Rules D Q P 1. Propagate d<d Q P Q P 2. Don t Propagate 3. Find envelope and don t propagate Ewha Womans University 46

47 Front Propagation Initial Front Final Front Ewha Womans University 47

48 Extract Visible Surface out out in out Ewha Womans University 48

49 Implement Environment Microsoft Visual Studio.Net OpenGL, OpenSG library Dual AMD Athlon GHz PC with nvidia GeForce 7900 GX2 Ewha Womans University 49

50 Benchmarking Models Car Model 3M triangles 0.25K scene graph nodes Engine Model 0.3 M triangles 7K scene graph nodes Ewha Womans University 50

51 Results Grid Resolution: 128 3, Removal Rate: 71% Ewha Womans University 51

52 Results Grid Resolution: 256 3, Removal Rate: 69% Ewha Womans University 52

53 Results Grid Resolution: 64 3 Removal Rate: 82% Ewha Womans University 53

Results Grid Resolution: 128 3 Removal Rate: 64%

54 Results Grid Resolution: Removal Rate: 64% Ewha Womans University 54

55 Computation Time Models Car (247 nodes, 3M Tri.) Engine (7177 nodes, 270K Tri.) Grid resolution directed distance field computation time Front propagation time sec 0.05sec sec 0.10sec sec 0.05sec sec 0.40sec Average : 4.18sec Ewha Womans University 55

56 Application to Swept Volume Sweep Trajectory Arrangement Boundary of SV

57 Computational Pipeline 1. Enumerate surface primitives 2. Compute their arrangement 3. Traverse the arrangement and extract the outermost boundary

58 Results Trajectory Sweep Ewha Womans University 58

59 Results Ewha Womans University 59

60 References Xinyu Zhang, Young J. Kim, Interactive collision detection for deformable models using Streaming AABBs, IEEE Transactions on Visualization and Computer Graphics, 13(2), Mar/Apr,2007 Y. J. Kim, K. Hoff, M. C. Lin and D. Manocha, Closest point query among the union of convex polytopes using rasterization hardware, Journal of Graphics Tools, 7.4, 2003 민혜정, 이민경, 김영준, 대용량모델렌더링을위한전역적가시화컬링알고리즘, 한국그래픽스학회, Nov Y. J. Kim, G. Varadhan, M. C. Lin and D. Manocha, Fast Swept Volume Approximation of Complex Polyhedral Models, Computer Aided Design, 36(11), Sep Ewha Womans University 60

61 Thank you Questions to Ewha Womans University 61

Ⅱ. Embedded GPU 모바일 프로세서의 발전방향은 저전력 고성능 컴퓨팅이다. 이 러한 목표를 달성하기 위해서 모바일 프로세서 기술은 멀티코 어 형태로 발전해 가고 있다. 예를 들어 NVIDIA의 최신 응용프 로세서인 Tegra3의 경우 쿼드코어 ARM Corte

Ⅱ. Embedded GPU 모바일 프로세서의 발전방향은 저전력 고성능 컴퓨팅이다. 이 러한 목표를 달성하기 위해서 모바일 프로세서 기술은 멀티코 어 형태로 발전해 가고 있다. 예를 들어 NVIDIA의 최신 응용프 로세서인 Tegra3의 경우 쿼드코어 ARM Corte 스마트폰을 위한 A/V 신호처리기술 편집위원 : 김홍국 (광주과학기술원) 스마트폰에서의 영상처리를 위한 GPU 활용 박인규, 최호열 인하대학교 요 약 본 기고에서는 최근 스마트폰에서 요구되는 다양한 멀티미 디어 어플리케이션을 embedded GPU(Graphics Processing Unit)를 이용하여 고속 병렬처리하기 위한 GPGPU (General- Purpose