碰撞检测中的K_DOPS算法的研究(1)
2015-09-08 01:13
导读：计算机应用论文论文，碰撞检测中的K_DOPS算法的研究(1)应该怎么写，有什么格式要求，科教论文网提供的这篇文章是一个很好的范例：
摘 要 K_DOPS碰撞检测算法是一类重要的碰撞检测算法，本文从K
摘 要 K_DOPS碰撞检测算法是一类重要的碰撞检测算法，本文从K_DOPS的定义、包围盒的选择与计算、包围盒树的构造等几个方面对K_DOPS算法进行研究，并给出一种快速碰撞检测算法并对该算法进行改进，提高算法的效率。 关键词 碰撞检测；K_DOPS；包围盒树1 引言 碰撞检测问题在计算机图形学中有很长的研究历史，近年来，随着虚拟现实，分布交互仿真等技术的兴起，碰撞检测再一次成为研究的热点，精确的碰撞检测对提高虚拟环境的真实性、增强虚拟环境的沉浸感起着至关重要的作用，而虚拟环境自身的复杂性和实时性对碰撞检测提出了更高的要求。包围盒树[7]是解决碰撞检测问题的一种有效的方法，碰撞检测对包围盒树的构造有以下几方面的要求：尽可能平衡以使得树的高度比较低；树的所有结点的包围盒体积尽可能小；每个结点的所有子结点的包围盒的交集尽可能小。但虚拟环境中对象进入的自由性和不可预测性以及碰撞检测的实时性又不允许我们在构造树时进行太复杂的优化，因此如何构造包围盒树将直接影响到碰撞检测的效率。 K_DOPS可以看作是AABB[5]的扩展，它不再是用三对平面来包围对象，而是使用了k/2对平面，正是因这这种扩展，它弥补了AABB紧密性差的缺点。因此，K_DOPS是一种很好的包围盒类型。2 K_DOPS (Discrete Orientation Polytopes)的定义 Discrete Orientation Polytopes(K_DOPS)包围盒是一种多面体，它的面由一组半空间 所确定，这些半空间的外法向是从 k 个固定的方向（D1，D2，...Dk）中选取的[2] [5]。 设固定方向集K（D1，D2，...Dk） ，一元组 （d1，d2，...dk）∈Rk 其中：
半空间
在设计K_DOPS时，为使相关的耗费尽量小，通常只选择那些共线但方向完全相反的向量作为固定法向，因此，每个K_DOPS实际上只用到k/2个方向，即
K_DOPS是一组半空间的集合，无论是在表示、存储还是计算中都是十分不方便的，构成K_DOPS的任何一半空间都可以表示成不等式形式：
由于集合D 是固定不变的，可以用一个 k×n矩阵来表示集合 D，从而可以把k_dops表示成如下形式：
，其中
由于 方向是可预知的，所以存储每个K_DOPS时无需保存方向，只需保存K个值即可，每个值对应一个平面的位置。而且当对两个K_DOPS做重叠测试时，只需要进行 次测试，这种测试远比两个OBB或凸包间的重叠测试简单。 3 K_DOPS的选择与计算3 .1 固定方向集的选择 K_DOPS最简单的例子是6_DOPS，其中6个面的法向分别由3个坐标轴的正负轴所决定，三维空间AABB轴向包围实际上是一种6_DOPS的特例。 对于14_DOPS，其中除了沿用AABB的六个方向外，还增加了8个对角线的方向，以消除这些方向上可能存在的空缺。 对于18_DOPS，其中除了沿AABB的6个方向外，还加入了指向AABB的12条边的方向，以消除这些方向上可能存在的空缺。 对于26_DOPS，则沿14_DOPS和18_DOPS合起来的26个方向。 图1中分别列举了6_DOPS、8_DOPS、14_DOPS和18_DOPS。
图13.2 K_DOPS的计算 一个几何对象X的K_DOPS的包围盒的计算可以通过X的顶点与固定方向集D中的各个方向的最大点积得到。使用这个蛮力计算法计算有n个顶点的多面体对象的K_DOPS可以在O(kn)时间内完成。为了说明如何计算K_DOPS，我们来考虑一个如图2所示的二维三角形。
图2 图2给出了一个简单的二维空间中的例子，设D = {±(1，0)，±(0，1)，±(1，1)，±(1，-1) }，X是一个三角形，顶点坐标分别为(2，1)，(6，2)和(4，6)。我们可以通过依次计算三角形三个顶点和D中的方向向量的点积计算这个三角形的K_DOPS。例如，为找到方向(1，1)上的最大延伸，我们计算下面三个点积。 (1， 1) . (2， 1) = 3 (1， 1) . (4， 6) = 10 (1， 1) . (6， 2) = 8 最大值为10，故X在(1，1)上的最大延伸为10，值得注意的是，(-1，-1)是D中和(1，1)方向相反的向量，故X的顶点与(1，1)的点积的最小值即为X在(-1，-1)上的最大延伸。通过计算其它方向上的点积，可以得到X的K_DOPS为(6，2，6，1，10，3，6，-2)。这个过程可以很容易地修改为用于计算复杂的对象的K_DOPS。 4 构造BV-tree包围盒树 由K_DOPS的定义和计算可知，固定方向凸包是一类比较简单的几何体，它从k个方向上形成对对象的较为紧密的包围。一个复杂的对象是由成千上万个基本几何元素组成的，通过把它们的包围盒组织成层次结构可以逐渐逼近对象，以获得尽可能完善的几何特性。4.1 包围盒树 对给定的 n个基本几何元素的集合S ，定义 S上的包围盒层次结构BVT(S )为一棵树，简称包围盒树，它具有以下性质[1] [3] [4] [6]： ①树中的每个结点v 对应于 S的一个子集Sv(Sv∈S) ； ②与每个结点v 相关联的还有集合 Sv的包围盒 b（Sv）； ③根结点对应全集S 和 S的包围盒b（S）； ④树中的每个内部结点（非叶结点）有两个以上的子结点，内部结点的最大子结点数称作度，记为 δ； ⑤结点ν 的所有子结点所对应的基本几何元素的子集合构成了对 ν所对应的基本几何元素的子集Sv 的一个划分。共2页: 1 [2] 下一页 论文出处(作者):
