Incremental penetration depth estimation between convex polytopes using dual-space expansion.
We present a fast algorithm to estimate the penetration depth between convex polytopes in 3D. The algorithm incrementally seeks a "locally optimal solution" by walking on the surface of the Minkowski sums. The surface of the Minkowski sums is computed implicitly by constructing a local dual mapping on the Gauss map. We also present three heuristic techniques that are used to estimate the initial features used by the walking algorithm. We have implemented the algorithm and compared its performance with earlier approaches. In our experiments, the algorithm is able to estimate the penetration depth in about a milli-second on an 1 GHz Pentium PC. Moreover, its performance is almost independent of model complexity in environments with high coherence between successive instances.
Kim
Young J
YJ
Department of Computer Science and Engineering, Ewha Womans University, Seoul, Korea. kimy@ewha.ac.kr
Lin
Ming C
MC
Manocha
Dinesh
D
D000465:Algorithms; D003196:Computer Graphics; D003198:Computer Simulation; D003867:Depth Perception; D007089:Image Enhancement / Q000379:methods*; D007090:Image Interpretation, Computer-Assisted / Q000379:methods*; D021621:Imaging, Three-Dimensional / Q000379:methods*; D016247:Information Storage and Retrieval / Q000379:methods*; D009716:Numerical Analysis, Computer-Assisted; D010363:Pattern Recognition, Automated; D010780:Photogrammetry / Q000379:methods; D015203:Reproducibility of Results; D012680:Sensitivity and Specificity; D012815:Signal Processing, Computer-Assisted; D014584:User-Computer Interface