Efficient computation of a measure of depth between convex objects for graphics applications

摘要

Algorithms to compute a measure of depth of intersection between convex polygonal objects in R~2 and convex polyhedral objects in R~3 are presented. The algorithms have linear asymptotic complexity. Numerical experience with the algorithms is encouraging and the algorithms are shown to have linear expected running time. Parallelization of the algorithms is described. We present a new collision detection algorithm that uses the depth measure. Results of implementation are reported.