명시적 그리고 암시적 민코우스키 합을 이용한 강체 침투깊이 계산 알고리즘
Penetration Depth Computation for Rigid Models using Explicit and Implicit Minkowski Sums
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
본논문에서는3차원상의두강체사이의침투깊이(penetration depth)를명시적으로민코우스키합(explicit Minkowski sum)을 생성하는 방법 (PDe)과 암시적으로 민코우스키 합 (implicit Minkowski sum)을 생성 하는 방법 (PDi)을 이용하여 계산하는 알고리즘을 제안하고 이들의 성능을 비교한다. 3차원 강체들 간의 침투깊이를 구하는데 성능상에 큰 장애가 되는 것이 민코우스키 합의 생성이다. 본 논문의 알고리즘들은 우선 물체의 중심 차 (centroid difference)와 운동 일관성 (motion coherence)기법을 이용하여 침투깊이를 예측한다. 특히 PDe는 추측된 침투깊이에 부분 민코우스키 합을 명시적으로 생성 혹은 갱신하여 침투깊이를 빠르게 구한다. 반면에 PDi는 민코우스키 합을 명시적으로 생성하기보다는 민코우스키 합에 접하는 접평면만을 반복적으로 생성하여 국소적으로 최적화된 침투깊이를 계산한다. 본 연구의 알고리즘들을 수천 개의 삼각형으로 이루어진 강체를 이용해 실험한 결과 수 밀리초 (millisecond) 이내의 빠른 속도로 침투깊이를 계산할 수 있다는 것을 실험적으로 보인다.
Abstract
We present penetration depth (PD) computation algorithms using explicit Minkowski sum construction (PDe) and implicit Minkowski sum construction (PDi). Minkowski sum construction is the most time consuming part in fast PD computation. In order to address this issue, we find a candidate solution using a centroid difference and motion coherence. Then, PDe constructs or updates partial Minkowski sum around the candidate solution. In contrast, PDi constructs only a tangent plane to the Minkowski sums iteratively. In practice, our algorithms can compute PD for complicated models consisting of thousands of triangles in a few milli-seconds. We also discuss the benefits of using different construction of Minkowski sums in the context of PD.
참고문헌 (25)
- D. Dobkin, "Computing the intersection-depth of polyhedra", Algorithmica, 9, pp.518~533 (1993)
- R. V. Benson, "Euclidean Geometry and Convexity" (1966), McGraw-Hill
- S. Cameron, "Enhancing GJK : Computing minimum and penetration distance between convex polyhedra", Proceedings of International Conference on Robotics and Automation, pp.3112~3117 (1997)
- Y. J. Kim, "Incremental penetration depth estimation between convex polytopes using dualspace expansion", IEEE Transactions on Visualization and Computer Graphics, 10(2), pp.152~163 (2004)
- Y. J. Kim, "Fast penetration depth computation for physically-based animation", Proceedings of ACM SIGGRAPH, 2002, 23~31
- Y. J. Kim, "Algorithmic Foundations of Robotics V", pp.505~521 (2004), Springer Berlin Heidelberg
- S. Redon, "A fast method for local penetration depth computation", Journal of Graphics, GPU, and Game Tools, 11(2), pp.37~50 (2006)
- C. Je, "Polydepth : Real-time penetration depth computation using iterative contact-space projection", ACM Transaction on Graphics, 31(1), pp.5:1~5:14 (2012)
- Y. Lee, "Continuous penetration depth computation for rigid models using dynamic minkowski sums", Computer-Aided Design, 78, pp.14~25 (2016)
- P. K. Agarwal, "Penetration depth of two convex polytopes in 3d", Nordic Journal of Computing, 7(3), pp.227~240 (2000)
- P. Hachenberger, "Exact minkowksi sums of polyhedra and exact and efficient decomposition of polyhedra into convex pieces", Algorithmica, 55(2), pp.329~345 (2009)
- L. Zhang, "A fast and practical algorithm for generalized penetration depth computation", Proceedings of Robotics: Science and Systems Conference (2007)
- D. Halperin, "Handbook of Discrete and Computational Geometry", pp.389~412 (1997), CRC Press, Inc
- M. Tang, "Interactive generalized penetration depth computation for rigid and articulated models using object norm", ACM Transactions on Graphics, 33(1), pp.1:1~1:15 (2014)
- J. Allard, "Volume contact constraints at arbitrary resolution", ACM Transactions on Graphics (Proceedings of SIGGRAPH 2010), 29(4), pp.82:1~82:10 (2010)
- T. Lozano-Perez, "Spatial planning : A configuration space approach", IEEE Transactions on Computers, 32(2), pp.108~120 (1983)
- C. L. Bajaj, "Convex decomposition of polyhedra and robustness", SIAM Journal on Computing, 21(2), pp.339~326 (1992)
- G. Varadhan, "Accurate minkowski sum approximation of polyhedral models", Graphical Models, 68(4), pp.343~355 (2006)
- L. Guibas, "A kinetic framework for computational geometry", Proceedings of the 24th Annual Symposium on Foundations of Computer Science, pp.100~111 (1983)
- P. K. Ghosh, "A unified computational framework for minkowski operations", Computers & Graphics, 17(4), pp.357~378 (1993)
- R. Wein, "Exact and efficient construction of planar minkowski sums using the convolution method", Proceedings of 14th Annual European Symposium, pp.829~840 (2006), Springer Berlin Heidelberg
- J.-M. Lien, "A simple method for computing minkowski sum boundary in 3d using collision detection", Algorithmic Foundation of Robotics VIII: Selected Contributions of the Eight International Workshop on the Algorithmic Foundations of Robotics, pp.401~415 (2010), Springer Science&Business Media
- J.-M. Lien, "Covering minkowski sum boundary using points with applications", Computer Aided Geometric Design, 25(8), pp.652~666 (2008)
- J. Pan, "Efficient penetration depth approximation using active learning", ACM Transactions on Graphics, 32(6), pp.191:1~191:12 (2013)
- M. Tang, "C2a: Controlled conservative advancement for continuous collision detection of polygonal models", Proceedings of International Conference on Robotics and Automation (2009)