论文部分内容阅读
为了追求震撼的效果和绚丽的画质,现代电影、游戏中大量地使用了全局光照和物理模拟等技术,碰撞剔除算法是这些技术的基本算法之一。另外,多核处理器上的并行计算是近年的研究热点。因此本论文提出并设计了基于多核系统的大规模物体群的实时碰撞剔除算法,并通过实验证明该算法是有效可行的。CPUs计算能力全面,适合处理线程数目不多的任务,特别是拥有复杂控制流程和混合操作的任务;GPUs则更擅长于能高度并行化的计算密集型任务。因此,本论文提出了一种CPUs与GPUs协作完成大规模物体群碰撞剔除计算的混合算法。该算法由GPUs完成物体群中数量较多、大小均匀的物体的碰撞剔除计算;而CPUs完成数量相对较少、大小较为突兀的物体的碰撞剔除计算。在GPUs端,本论文提出一种结合Bounding Volume Hierarchies (BVH)和Sweep-and-Prune(SaP)的碰撞剔除算法。该算法使用Linear Bounding Volume Hierarchies(LBVH)对空间进行粗略划分,利用空间连贯性快速剔除因距离较远而不可能相交的碰撞对;然后对各子空间的物体使用一种并行化的SaP算法,完成最终的碰撞剔除计算。LBVH和并行化的SaP算法对GPUs体系结构友好度高,能在GPUs上高效地运行。在CPUs端,本论文提出的算法直接对数量较少的大物体使用并行化的SaP算法进行碰撞剔除计算。关于CPUs上线程的协作,本论文提出一种基于粗粒度任务的工作队列的多线程模型。这种模型既考虑了物体之间因大小、分布造成的负载不均衡情况,又考虑了线程之间同步的开销。另外CPUs端的算法实现上还使用了SIMD指令集,充分地发挥了现代CPUs数据级的并行性能。最后通过实验验证了本论文提出的CPUs/GPUs混合碰撞剔除算法,该算法能较好地发挥两种处理器的优势,实现实时大量物体的碰撞剔除。与传统串行碰撞剔除算法相比,本论文提出的算法在运算速度上有很大提高。