###
DOI:
Journal of Software:2004.15(10):1505-1514

基于流的实时碰撞检测算法
范昭炜,万华根,高曙明
(浙江大学,CAD&CG国家重点实验室,浙江,杭州,310027)
Streaming Real Time Collision Detection Using Programmable Graphics Hardware
FAN Zhao-Wei,WAN Hua-Gen,GAO Shu-Ming
()
Abstract
Chart / table
Reference
Similar Articles
Article :Browse 2660   Download 3516
Received:October 13, 2003    Revised:May 08, 2004
> 中文摘要: 实时碰撞检测是计算机图形应用中不可或缺的问题之一,复杂物体间的实时碰撞检测至今仍未能得以很好的解决.高性能可编程图形硬件的出现,正在改变着通用计算仅能由CPU完成的传统观念.探索性地采用了可编程图形硬件来解决复杂物体间的实时碰撞检测问题.通过将两个任意物体间的碰撞检测计算映射到图形硬件以有效利用图形硬件的并行架构,由实时绘制过程快速产生碰撞检测结果.为此,算法首先将碰撞检测问题转化为一组线段集合与三角形的求交问题,以实现碰撞检测算法向可编程图形硬件的迁移.在对算法复杂度进行理性分析的基础上,给出了两种有效的优化技术以提升算法效率.实验结果表明,与现有的图像空间碰撞检测算法相比,该算法在效率、精确性和实用性方面具有明显优势.
Abstract:Real time collision detection is required by almost all computer graphics applications. However, the problem of real time collision detection is yet to be solved between complex objects. With the recent advent of high performance graphics processing units (GPUs), a dramatic shift is being seen in the traditional idea that general-purpose computation can only be performed by CPUs. This paper explores to solve the problem of real time collision detection between complex objects using programmable GPUs. The algorithm maps the computation of collision detection between two arbitrary objects onto programmable GPUs to match their parallel architectures, and produces on the fly the collision detection results via real time rendering. To do so, the problem is first converted into the problem of finding intersections between a collection of line segments and a set of triangles to realize the migration of collision detection algorithms to programmable GPUs. Based on reasonable analyses of the algorithm complexity, two optimized techniques is presented to improve its efficiency. Experimental results have shown that the optimized algorithm is advantageous over other current collision detection algorithms implemented in image space regarding efficiency, accuracy as well as practicability.
文章编号:     中图分类号:    文献标志码:
基金项目:Supported by the National Natural Science Foundation of China under Grant No.60103003, 60021201(国家自然科学基金);the National High-Tech Research and Development Plan of China under Grant No.2002AA411310(国家高技术研究发展计划(863));the National Grand Fundamental Research 973 Program of China under Grant No.2002CB312100(国家重点基础研究发展规划(973)) Supported by the National Natural Science Foundation of China under Grant No.60103003, 60021201(国家自然科学基金);the National High-Tech Research and Development Plan of China under Grant No.2002AA411310(国家高技术研究发展计划(863));the National Grand Fundamental Research 973 Program of China under Grant No.2002CB312100(国家重点基础研究发展规划(973))
Foundation items:
Reference text:

范昭炜,万华根,高曙明.基于流的实时碰撞检测算法.软件学报,2004,15(10):1505-1514

FAN Zhao-Wei,WAN Hua-Gen,GAO Shu-Ming.Streaming Real Time Collision Detection Using Programmable Graphics Hardware.Journal of Software,2004,15(10):1505-1514