%0 Journal Article
%T Parallel collision detection algorithm based on coloring algorithm<br>基于着色算法的并行碰撞检测算法*
%A ZHAO Wei
%A TAN Rui-pu
%A YANG Qiu-n
%A DING Wen-bao
%A LI Wen-hui
%A <br>赵伟
%A 谭睿璞
%A 杨秋娜
%A 丁文保
%A 李文辉
%J 计算机应用研究
%D 2009
%I 
%X This paper presented a new parallel collision detection algorithm based on coloring algorithm. At first, incorporated the merits of both AABB bounding box and bounding spheres to construct a hybrid bounding representation of arbitrary non-convex polyhedra (S-AABB) for attaining speed, balanced especially the S-AABB using divide-and-conquer technologies which were mostly primary technologies in parallel algorithm. Then applied symmetry breaking-k-coloring technology which was also important in parallel algorithm in order to reduce different categories, and assign them to different processors; also multi-thread was used in multi-processor computer. At last, experiments results show that the algorithm is advantageous over other current typical collision detection such as I-COLLIDE regarding efficiency and accuracy, so can meets the real-time and accurate requirements in complex interactive virtual environment.
%K collision detection
%K mixed BVH
%K parallel technology
%K symmetry breaking
%K coloring algorithm<br>碰撞检测
%K 混合包围体层次
%K 并行技术
%K 破对称
%K 着色算法
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=A9D9BE08CDC44144BE8B5685705D3AED&aid=3805C4597945FEBF0B62223EC0B1B569&yid=DE12191FBD62783C&vid=96C778EE049EE47D&iid=94C357A881DFC066&sid=4B35F43975EC564A&eid=7101D1EC58F693A9&journal_id=1001-3695&journal_name=计算机应用研究&referenced_num=0&reference_num=13