CUDACUDAbased Rendering of 3D based Rendering of 3D CUDACUDAbased Rendering of 3D based Rendering of 3D CUDACUDA--based Rendering of 3D based Rendering of 3D Minkowski SumsMinkowski SumsCUDACUDA--based Rendering of 3D based Rendering of 3D Minkowski SumsMinkowski SumsCS267 ProjectjWei LiBackground and MotivationBackground and MotivationBackground and MotivationBackground and Motivationgggg• Minkowski sum• C = A ⊕ B = {a + b | a∈A, b ∈ B}=⊕• 3D Minkowski sumO(33)litf bjt=⊕•O(m3n3)complexity for concave objects• Existing computation algorithms very slow–Several minutes for simple objects with hundreds of triangles• Motivation• Fast visual feedback of Minkowski sum• Input as triangulated polyhedra• Fast morphing• tA ⊕ (1-t)BSurface PrimitivesSurface PrimitivesSurface PrimitivesSurface Primitives• Surface primitives of ∂C• Triangles (fAvB, or fBvA)•Quads (eAeB)Q(AB)• May trimmed•Culling of interior primitivesCulling of interior primitives• fAvBvalid if•∀einA•ei≤0nAfvB∀e, nA•e≤0• eAeBvalid if•∀ei,(eA×eB)•eiconstant signfAe0e1em……v32∀e, (eAeB)econstant sign• Not valid if eAor eBconcaveeBe2e0v2e1v1v4e3eAAlgorithm OverviewAlgorithm OverviewAlgorithm OverviewAlgorithm OverviewggggCompute and test eachCompute and test each primitive candidate, update the flag array0 1 1 0 1 1 0 1Flag array (1: valid 0: culled)Prescan the flag arrayPrescannedflag arrayCUDARecompute unculledprimitives, put them in VBO0 0 1 2 2 3 4 4Prescannedflag array (position in the VBO)p,pRendering VBO in OpenGLOpenGLVBODATAImplementation on Implementation on CUDACUDAImplementation on Implementation on CUDACUDApppp• Block size: 16 × 16• #triangles, #vertices, #edges rounded up by 16• Each thread compute a primitive• Memory Optimization25Uncoalesced global memory1520Coalesced global memoryShared memory + coalesced 510global memory0⊕⊕⊕Culling time with different memory techniques (second)Timing ResultsTiming ResultsTiming ResultsTiming ResultsggggTime for Rendering Minkowski Sums(second)250300(second)CPU CUDA15020020.3×20.5×19.5×27.0×28.6×0501000CPU: 3.00 GHz CPU w/ 2 GB RAM GPU: NVIDIA GeForce 9600 GTRendering ResultsRendering ResultsRendering ResultsRendering
View Full Document
Unlocking...