三角形快速相交算法.doc

三角形快速相交算法 A Fast Triangle-Triangle Intersection Test To summarize, the steps of the algorithm are as follows 1. Compute plane equation of triangle 2.2. Reject as trivial if all points of triangle 1 are on same side.3. Compute plane equation of triangle 1.4. Reject as trivial if all points of triangle 2 are on same side.5. Compute intersection line and project onto largest axis.6. Compute the intervals for each triangle.7. Intersect the intervals. Devillers算法总体上最优; Tropp算法最适合于高相交率场合; Shen算法比较适合中低相交率场合;Mêller算法虽然整体性能稍弱,但它是其他算法的基础,且应用广泛;从相关材料分析结果看, Held算法的整体性能还略逊于Mêller算法,但其与Mêller算法类似,也起着基础的作用,其算法思想为其他算法所借鉴。以上算法的共同点都是在着力追求算法的快速性,分别采用几何方法和代数方法实现,同时从测试结果来看,各算法也有较好的精度和稳定性。随着场景规模的大型化和复杂化,检测速度是算法追求的主要指标之一。图形处理器(GPU)的数据处理能力比CPU强很多,因此许多研究者开始尝试着将GPU数据处理能力应用到通用计算领域,并获得了成功,特别是在流体计算领域,展现了其强大的计算能力。这是一个新的领域,有着巨大的潜力,越来越多的研究者开始关注这一领域,在三角形相交测试方面[ 13, 14 ]以及相关的碰撞检测领域[ 15～20 ]的研究工作也已开展。GPU以比CPU更快的速度发展,并进一步考虑了其在通用计算领域的应用。以NV ID IA 公司为例,其推出的新一代GeForce 8系列和Quadro系列GPU都采用了新的统一渲染构架,取消了原来的顶点着色器和像素着色器,取而代之的是统一的可编程流处理器,增加了对GPU的利用率, GeForce 8系列最多可拥有128个流处理器。为进一步挖掘GPU的通用计算性能,NV ID IA公司推出了CUDA技术,一种用于在NV ID IAGPU上进行计算的全新体系架构,这是该领域内的首个GPU用的C编译器开发环境,此举被誉为是揭开GPU计算革命的序幕。由此可见,基于GPU的计算及其算法研究将逐渐成为研究的热点。由于GPU本身在处理上的并行性特点,对更适合于在GPU上运行的三角形相交检测算法以及基于它的实时碰撞检测算法的研究将有着重要的科研和实践价值。 /* * * Triangle-Triangle Overlap Test Routines * July, 2002 * Updated December 2003 * * This file contains C implementation of algorithms for * performing two and three-dimensional triangle-triangle intersection test * The algorithms and underlying theory are described in * * Fast and Robust Triangle-Triangle Overlap Test * Using Orientation Predicates P. Guigue - O. Devillers *