2002 · 30 citations · 22 references
ComputingComputer ScienceHigh-performance ComputingComputational GeometryComputer GraphicsRendering3D RenderingCollision DetectionComputer Graphics HardwareGeometry ProcessingIntersection DetectionMulti-view GeometryComputational Geometry For GraphicsDeformable ModelsDistance-based Collision DetectionGeometry Processing HardwareIntersection QueriesObject LocalizationProximity QueriesRigid Body Collision Detection
We present an approach for computing generalized proximity information between arbitrary polygonal models using graphics hardware acceleration. Our algorithm combines object-space localization, multi-pass rendering techniques, and accelerated distance field computation to perform complex proximity queries at interactive rates. It is applicable to any closed, possibly non-convex, polygonal object and requires no precomputation, making it suitable for both rigid and dynamically deformable geometry of relatively high complexity. The proximity queries include, not only collision detection, but also the computation of intersections, minimum separation distance, closest points, penetration depth and direction, and contact points and normals. The load is balanced between CPU and graphics subsystems through a hybrid geometry and image-based approach. Geometric object-space techniques coarsely localize potential interactions between two objects, and image-space techniques accelerated with graphics hardware provide the low-level proximity information. We have implemented our system using the OpenGL graphics library and have tested it on various hardware configurations with a wide range of object complexities and contact scenarios. In all cases, interactive frame rates are achieved. In addition, our algorithm’s performance is heavily based on the graphics hardware computational power growth curve which has exceeded the expectations of Moore’s Law for general CPU power growth.
22
S. Gottschalk, Ming C. Lin, Dinesh Manocha · 1996 · 2.1K citations
Fast computation of generalized Voronoi diagrams using graphics hardware
Kenneth E. Hoff, John Keyser, Dinesh Manocha et al. · 1999 · 577 citations