Title :
Real time collision detection in buildings using polygon presence grid
Author :
Razzaq, Shahid ; Shah, Asad Ali ; Mansoor, Shamyl Bin
Author_Institution :
Sch. of Electr. Eng. & Comput. Sci., Nat. Univ. of Sci. & Technol. (NUST), Islamabad, Pakistan
Abstract :
Achieving real time collision detection in high vertex count geometrical models like those of buildings, while maintaining an adequate frame rate, is a challenging problem. Time complexity of collision detection algorithms in such scenarios is an important factor and algorithms that provide constant time collision query processing are required. This paper presents a constant time collision detection algorithm for high vertex count and complex geometrical models by using uniform spatial grids and polygon surface subdivision technique. The algorithm thus shifts the performance balance in favor of the time constraints with a compromise on space complexity. We show the results of the proposed technique on a 400K+ vertex building model.
Keywords :
collision avoidance; computational complexity; computational geometry; structural engineering; collision detection algorithm; polygon presence grid; polygon surface subdivision technique; realtime collision detection; space complexity; vertex building model; vertex count geometrical model; Adaptation models; High definition video; Strontium; building; collision detection; constant time; high vertex count; motion planning; real time; robots; spatial uniform grid; triangle subdivision; voxel;
Conference_Titel :
Multitopic Conference (INMIC), 2011 IEEE 14th International
Conference_Location :
Karachi
Print_ISBN :
978-1-4577-0654-7
DOI :
10.1109/INMIC.2011.6151459