Efficient collision detection for animation and robotics

摘要: We present efficient algorithms for collision detection and contact determination between geometric models, described by linear or curved boundaries, undergoing rigid motion. The heart of our algorithm is a simple fast incremental method to compute the distance two convex polyhedra. It utilizes convexity establish some local applicability criteria verifying closest features. A preprocessing procedure used subdivide each feature's neighboring features constant size thus guarantee expected running time test. The performance an attribute from exploiting coherence locality. Let n be total number features, run $O(\sqrt{n})$ O(n) depending on shape, if no special initialization done. This technique can dynamic detection, planning in three-dimensional space, physical simulation, other robotics problems. The set models we consider includes polyhedra objects with surfaces rational spline patches piecewise algebraic functions. use computation polyhedral extend it using hierarchical representation measurement non-convex polytopes. Next, global methods solving polynomial equations description devise arbitrary objects. We also describe different approaches reduce frequency from$$N\choose2$$pairwise comparisons environment moving objects. One them priority queue sorted lower bound collision; uses overlap test bounding boxes. Finally, opportunistic path planner which trace out one-dimensional skeleton purpose robot motion planning. The attests their promise real-time simulations as well applications computer generated virtual environment.