Fast Geometric Computations using GPUs 김영준 http://graphics.ewha.ac.kr 이화여자대학교컴퓨터학과
Topics Collision detection Closest point query Approximate arrangement computation Ewha Womans University http://graphics.ewha.ac.kr 2
Streaming AABBs Collision detection for deformable models Ewha Womans University http://graphics.ewha.ac.kr 3
Teaser Video Ewha Womans University http://graphics.ewha.ac.kr 4
Streaming AABB Pipeline 1. Stream setup 2. Stream calculation 3. Stream update Ewha Womans University http://graphics.ewha.ac.kr 5
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 http://graphics.ewha.ac.kr 6 trees
Streaming AABBs Vertex textures MAX MIN AABB Streams Ewha Womans University http://graphics.ewha.ac.kr 7
Streaming AABB Overlap Test Streaming AABBs of model B Ewha Womans University http://graphics.ewha.ac.kr 8
Streaming CD Results Collision result of AABB pairs stored at an off-screen buffer Intersected models Ewha Womans University http://graphics.ewha.ac.kr 9
Readback from GPU to CPU Readback from GPU to CPU is costly 50 milli-seconds for 1024x1024 frame buffer Hierarchical readback Ewha Womans University http://graphics.ewha.ac.kr 10
Stream Reduction Level n Level 1 Level 0 Ewha Womans University http://graphics.ewha.ac.kr 11
Readback Level 3 (P3) Level 2 (P2) Encoding Level 1 (P1) Level 0 (P0) Ewha Womans University http://graphics.ewha.ac.kr 12
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 http://graphics.ewha.ac.kr 13
Primitive Level Test Triangle-triangle overlap test using CPUs Ewha Womans University http://graphics.ewha.ac.kr 14
Stream Update Vertex textures Fragment shader Fragment program MAX MIN Framebuffer-1 Framebuffer-2 Multi-Rendering Targets (MRT) Ewha Womans University http://graphics.ewha.ac.kr 15
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 http://graphics.ewha.ac.kr 16
Benchmarking Scenarios (a) Interlocking torii (15000x2 triangles, 60-80 FPS) (b) Touching torii (15000x2 triangles, 90-100 FPS) (c) Merging torii (15000x2 triangles, 25-30 FPS) (d) Bump bunnies (15000x2 triangles, 50-60 FPS) (e) Happy buddhas (20000x2 triangles, 25-40 FPS) (f) Intimate animals (50000x2 triangles, 20-30 FPS) Ewha Womans University http://graphics.ewha.ac.kr 17
Performance Comparison Three times performance improvement over CULLIDE No collision misses up to floating point precision Ewha Womans University http://graphics.ewha.ac.kr 18
Demo Video Ewha Womans University http://graphics.ewha.ac.kr 19
Parallel Triangle Intersection Test Using CUDA Triangles of Object2 (n2) b_hig (tri1, tri2) Triangles of Object1 (n1) b_wid
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)
Intersection Results Sphere & Cylinder CPU vs. GPU(CUDA) Time (ms) CPU 11.84 GPU(CUDA) 2.34 5 times faster! Ewha Womans University
Intersection Results Cup & Azucar CPU vs. GPU(CUDA) Time (ms) CPU 2099.5 GPU(CUDA) 183.9 11 times faster! Ewha Womans University
Intersection Results Cup & Spoon CPU vs. GPU(CUDA) Time (ms) CPU 10377.62 GPU(CUDA) 1084.22 10 times faster! Ewha Womans University
Closest Point Query Application to penetration depth computation Ewha Womans University http://graphics.ewha.ac.kr 25
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
Closet Point Query Main Idea Incrementally expand the current front of the boundary Ewha Womans University Young J. Kim 27
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
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
Penetration Depth (PD) Minimum translational distance needed to separate objects Ewha Womans University Young J. Kim 30
Penetration Depth (PD) d Minimum translational distance needed to separate objects Ewha Womans University Young J. Kim 31
Penetration Depth PD determines the amount of repulsive forces in penalty-based, 6DOF haptic rendering Ewha Womans University Young J. Kim 32
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 http://graphics.ewha.ac.kr 33
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 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 http://graphics.ewha.ac.kr 35
Motivations Engine of a BMW 5 with 3,741,833 triangles [Ernst 04] Car door with 782,018 triangles Ewha Womans University http://graphics.ewha.ac.kr 36
Goal Remove invisible geometric elements when the inspection is performed from outside only Design reviews Visual inspection Training simulations Ewha Womans University http://graphics.ewha.ac.kr 37
Infinite Number of Viewpoint Render the scene from infinite # of viewpoint [Ernst 04] Ewha Womans University http://graphics.ewha.ac.kr 38
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 http://graphics.ewha.ac.kr 39
Algorithm Overview Distance field representations Use GPUs Fast marching method Use CPUs Extract visible surface Use CPUs Ewha Womans University http://graphics.ewha.ac.kr 40
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 http://graphics.ewha.ac.kr 41
Distance Fields Computations P P R P R P R P R P R P R R P R Ewha Womans University http://graphics.ewha.ac.kr 42 z
Distance Fields Computations primitive orthographic projection Z = D projection Y image plane X Z-buffer holds the directed distance values Ewha Womans University http://graphics.ewha.ac.kr 43
Distance Fields Generation Ewha Womans University http://graphics.ewha.ac.kr 44
Front Propagation Initial Front Final Front Ewha Womans University http://graphics.ewha.ac.kr 45
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 http://graphics.ewha.ac.kr 46
Front Propagation Initial Front Final Front Ewha Womans University http://graphics.ewha.ac.kr 47
Extract Visible Surface out out in out Ewha Womans University http://graphics.ewha.ac.kr 48
Implement Environment Microsoft Visual Studio.Net OpenGL, OpenSG library Dual AMD Athlon 64 2.6GHz PC with nvidia GeForce 7900 GX2 Ewha Womans University http://graphics.ewha.ac.kr 49
Benchmarking Models Car Model 3M triangles 0.25K scene graph nodes Engine Model 0.3 M triangles 7K scene graph nodes Ewha Womans University http://graphics.ewha.ac.kr 50
Results Grid Resolution: 128 3, Removal Rate: 71% Ewha Womans University http://graphics.ewha.ac.kr 51
Results Grid Resolution: 256 3, Removal Rate: 69% Ewha Womans University http://graphics.ewha.ac.kr 52
Results Grid Resolution: 64 3 Removal Rate: 82% Ewha Womans University http://graphics.ewha.ac.kr 53
Results Grid Resolution: 128 3 Removal Rate: 64% Ewha Womans University http://graphics.ewha.ac.kr 54
Computation Time Models Car (247 nodes, 3M Tri.) Engine (7177 nodes, 270K Tri.) Grid resolution directed distance field computation time Front propagation time 128 3.42sec 0.05sec 256 6.59sec 0.10sec 64 1.85sec 0.05sec 128 4.26sec 0.40sec Average : 4.18sec Ewha Womans University http://graphics.ewha.ac.kr 55
Application to Swept Volume Sweep Trajectory Arrangement Boundary of SV
Computational Pipeline 1. Enumerate surface primitives 2. Compute their arrangement 3. Traverse the arrangement and extract the outermost boundary
Results Trajectory Sweep Ewha Womans University http://graphics.ewha.ac.kr 58
Results Ewha Womans University http://graphics.ewha.ac.kr 59
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. 2006 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 2004. Ewha Womans University http://graphics.ewha.ac.kr 60
Thank you Questions to kimy@ewha.ac.kr Ewha Womans University http://graphics.ewha.ac.kr 61