|Interactive motion planning in a dynamic environment using surface distance maps, demonstrating the motion of hundreds of human agents in a crowd simulation: (left-center) Two views of the environment with dynamic 3D obstacles, including cars and flying drones. Each human agent is represented as a cylinder and colored by its goal. (right) The nearest neighbor map of the obstacles and agents computed using surface distance maps. Each colored region is closer to one 3D obstacle than to any other. The path for one agent is shown using solid black lines. Our algorithm can perform the simulation, including distance computations and path planning, for 100 agents at 10fps on a high-end PC.|
We present a new parameterized representation called surface distance maps for distance computations on piecewise 2-manifold primitives. Given a set of orientable 2-manifold primitives, the surface distance map represents the (non-zero) signed distance-to-closest-primitive mapping at each point on a 2-manifold. We present an interactive algorithm for computing the surface distance map of triangulated meshes using graphics hardware. We precompute a surface parameterization and use the parameterization to define an affine transformation for each mesh primitive. Our algorithm efficiently computes the distance field by applying this affine transformation to the distance functions of the primitives and evaluate these functions using texture mapping hardware. In practice, our algorithm can compute very high resolution surface distance maps at interactive rates and provides tight error bounds on their accuracy. We use surface distance maps for path planning and proximity query computation among complex models in dynamic environments. Our approach can perform planning and proximity queries in a dynamic environment with hundreds of objects at intereactive rates and offer significant speedups over prior algorithms.
|Surface Distance map computation
on deforming letters"i3d2007": Deforming dynamic
simulation on 7 letters falling on an uneven terrain, (6K triangles
total). (a)-(b) Two frames
from the simulation. (c) The gradient of surface distance maps
between two letters shows the direction of the closest point on
the other letter. Our algorithm can perform proximity queries
using high resolution surface distance maps of resolution 512 ×
512 in 100-200 ms per frame.
Avneesh Sud, Naga Govindaraju, Russell Gayle, Erik Andersen and Dinesh Manocha Surface Distance Maps Proc of Graphics Interface 2007.
Fast Computation of Distance Fields and Generalized Voronoi Diagrams Using Graphics Hardware
Fast Proximity Queries among Deformable Models Using Discrete Voronoi Diagrams
Proximity Query and Collision Detection Research at the UNC Computer Science GAMMA Group.UNC GAMMA Group