Title :
Derivation of contact states from geometric models of objects
Author :
Zhang, Lixin ; Xiao, Jing
Author_Institution :
Dept. of Comput. Sci., North Carolina Univ., Charlotte, NC, USA
Abstract :
An efficient algorithm is presented to identify the topological contacts between two contacting polytopes from their geometric models. The algorithm extends the result of the polytope distance algorithm by Gilbert et. al (1988) by exploring local topological information. Its worst-case time complexity is O(N+nev/2), where N is the total number of vertices of two contacting polytopes and ne v/ is the average number of edges at one vertex. The algorithm is fully implemented and used in a computer simulation system for a contact-based fine motion planning scheme. With its great efficiency and effectiveness, the algorithm can be used in any computer modeling and simulation environment which require reasoning about topological contacts
Keywords :
computational complexity; geometry; path planning; simulation; computer simulation system; contact states; contact-based fine motion planning scheme; contacting polytopes; geometric models; local topological information; topological contacts; worst-case time complexity; Algorithm design and analysis; Computational modeling; Computer errors; Computer simulation; Manipulator dynamics; Motion planning; Object detection; Robots; Solid modeling;
Conference_Titel :
Assembly and Task Planning, 1995. Proceedings., IEEE International Symposium on
Conference_Location :
Pittsburgh, PA
Print_ISBN :
0-8186-6995-0
DOI :
10.1109/ISATP.1995.518797