碰撞检测

二维碰撞检测算法

碰撞检测（Collision Detection,CD）也称为干涉检测或者接触检测，用来检测不同对象之间是否发生了碰撞，它是计算机动画、系统仿真、计算机图形学、计算几何、机器人学、CAD\ CAM等研究领域的经典问题。

碰撞物体可以分为两类：面模型和体模型。面模型是采用边界来表示物体，而体模型则是使用体元表示物体。面模型又可根据碰撞后物体是否发生形变分为刚体和软体，刚体本身又可根据生成方式的不同分为曲面模型和非曲面模型。目前对于碰撞的研究多集中于面模型的研究，因为体模型是一种三维描述方式，对它进行碰撞检测代价较高。而在面模型的研究中，对刚体的研究技术更为成熟。

下面列举几种常用的碰撞检测技术：

1：包围盒（bounding box）是由Clark提出的，基本思想是使用简单的几何形体包围虚拟场景中复杂的几何物体，当对两个物体进行碰撞检测时，首先检查两个物体最外层的包围盒是否相交，若不相交，则说明两个物体没有发生碰撞，否则再对两个物体进行检测。基于这个原理，包围盒适合对远距离物体的碰撞检测，若距离很近，其物体之间的包围盒很容易相交，会产生大量的二次检测，这样就增大了计算量。

包围盒的类型主要有AABB(Aligned Axis Bounding Box)沿坐标轴的包围盒、包围球、OBB(Oriented Bounding Box)方向包围盒和k-DOP(k Discrete Orientation Polytopes)离散方向多面体等。

AABB是包含几何对象且各边平行于坐标轴的最小六面体，两个AABB包围盒相交当且仅当它们三个坐标轴上的投影均重叠，只要存在一个方向上的投影不重叠，那么它们就不相交。AABB间的相交测试和包围体的更新速度比其他算法

效率高，因此使用最广泛，尤其适用于多物体运动的大规模环境和变形体碰撞检测。

OBB包围盒的相交测试基于分离轴的理论的，它的构造关键在于包围盒最佳方向的确定，最佳方向必须保证在该方向上包围盒的尺寸最小。由于其较好的紧密性，大大提高了算法的效率，但需要较多的存储空间，构造和更新包围体的速度都比较慢，不能有效地处理变形体等情况。

k-DOP使用k/2对的平行平面来包围物体，如果在由k-DOP的边构成的固定方向集合种的某个方向上的投影不重叠，则包围盒必不相交；如果在所有方向上的投影都重叠，则包围盒必相交。通过调整k的取值，k-DOP可以在简单性、紧密性中达到一定的折衷，从而提高碰撞检测的效率。

包围盒是目前应用最为广泛的碰撞检测方法，包围盒本身的简单性和所包围物体的紧密性是相互矛盾的，简单性越高其紧密性差，反之如此，所以如何解决这个矛盾是包围盒技术的关键。

2.空间剖分法

空间剖分法是依据某种规则将场景空间划分成若干小单元，并记录所有单元内的特征，通过查询同一个单元或相邻单元内的特征间的相交情况来判断是否发生碰撞检测。按照剖分空间的方法可分为均匀剖分和非均匀剖分。均匀剖分是将场景中的空间均匀的划分为大小一致的单元格，非均匀剖分的方法很多，如BSP 树和Kd树等。

空间剖分法使用于物体之间距离较远的场景，因为如果物体之间的距离很近，需要对单元格进行更深的递归分割，这样需要更多的空间存储单元格，并需要进行更多的单元格相交测试，从而降低了效率。

3. 距离场

距离场是一种基本的图形表示模型，表示距离物体表面的最小距离。距离场是矢量场，距离的正负可表示物体在外部或内部，用距离场表示表面封闭的物体不需要物体的拓扑信息和约束信息，能快速计算碰撞后的穿刺距离和法向量。

距离场的空间划分方法有很多种，标准栅格法、八叉树和BSP树等，[1]中提出了自适应的采样距离场(ADFs)，它在距离场含有细节的时候采用较高的采样率，在场变化小的时候，采用较低的采样率，从而避免在细节部分采样数量不够多，导致整体碰撞检测精度下降。采样策略在建立距离场之前确定，从而控制了精确度，能最有效地利用内存。

距离场进行碰撞检测是逐点进行的，通过把一个物体的顶点逐个与另一个物体的距离场进行检测，确定是否发生碰撞。当然碰撞还存在边与边之间的相交，在[2]中提出了一种类似划分的方法，他们通过增加测试变形特征的每条边的中心来增加碰撞检测的精确度。

4. 图像空间方法

图像空间的碰撞检测方法不需要为物体建立层次包围体树模型，它利用图形硬件将三维物体降为二维图像，对二维图像进行采样并建立相应的深度信息，通过对信息的分析判断是否发生碰撞。

图像空间法不需要预处理，适合动态的变形体，但是它需要降物体光栅化，其精度取决于对物体的离散化程度，不能提供准确的碰撞信息，是用效率换取精度。但是，图像空间法是一类较新的碰撞检测方法，[3]和[4]提出过利用两个深度缓存分别保存物体的最小和最大深度(对应于物体的最前层和最后层)，通过判断第二个物体象素的最大深度值是否介于第一个物体象素的最大最小深度值之

间来确定是否碰撞，但只能判断凸体。[5]提出了利用模板缓存来保存窗口中每个象素上所代表的射线进入物体和离开其他物体的次数，之后读取模板缓存中的值来判断两物体是否相交，进一步改善了图像空间碰撞检测算法的局限性。[6]将图象空间碰撞检测算法率先用到动态布料仿真中，利用图形硬件的深度缓存和颜色缓存来判别衣服和虚拟人体模型是否发生碰撞，该算法也是只能用于凸体。

[7]提出了能检测任意物体碰撞的方法，为物体计算层次深度图LDI(Layered Depth Image)来标识物体的体积，先用AABB包围盒进行相交测试，对相交的包围盒中的物体构建LDI，再进行相交测试，计算相交体积，这就要求物体必须是封闭的。LDI是图像空间方法的基本结构，所以对LDI的改进是提高图像空间方法的关键。

[8]中用三中方法改进了LDI，两种是通过图形硬件加速，另一种是通过改进程序，结果显示图形硬件适合几何形态复杂的场景，而以使用程序加速的方法比较灵活，更适合场景较小的情况。

5. 随机碰撞检测方法

随机碰撞检测是用效率换取精度的一类碰撞检测方法，注重碰撞后的实时模拟，是碰撞领域的一个热点。随机碰撞检测可分为Average-case方法和基于随机选择几何元的碰撞检测方法。

Average-case方法是以包围盒相交区内两个物体的特征个数的比作为是否发生碰撞的标准，算法灵活，能控制碰撞检测的精确度。随机选择几何元的碰撞检测方法是通过在碰撞对象内部随机取样作为初始的潜在的碰撞区域，然后跟踪采样对。[9]中提出采用k-dop来限制采样点在两物体之间较接近的部分，采用爬山法来逐步逼近局部最小并保留一个哈希表纪录访问过的特征对。[10]和[11]分别提出利用时空一致性和时间一致性，对随机选择几何元的碰撞检测方法进行改

进。

6. 智能算法

智能算法是目前一个比较新的领域，是受自然规律的启迪，根据仿生原理，模仿求解问题的算法，这方面的内容很多，如人工神经网络技术、遗传算法、模拟退火算法、模拟退火技术和群集智能技术等。

[12]从求解物体的最短距离的角度判断物体碰撞的可能性，将对最短距离的计算问题变成对约束条件的非线性规划问题，利用遗传算法对其求解，实验证明，该算法计算速度快、计算精度高。

[13]提出利用粒子群算法和随机碰撞检测方法相结合，通过在物体特征域内采样把三维物体空间内碰撞检测问题转换到二维空间解决，增加了算法的适应性，实验证明该算法能有效的处理变形体的碰撞检测问题。

[14]提出用顶点的凸包来表示凸多面体，将物体间距离的问题归结为约束条件的非线性规划问题,利用模拟退火遗传算法对该问题进行求解，结果表明，该算法有较高的计算效率和计算速度。

智能算法在碰撞检测领域的应用目前还不广泛，但它本身在解决优化等问题上的优势，对今后碰撞检测技术的提高具有一定的意义。

由于对于不同的物体，比如刚体和软体，所采用的方法不同，并且对于不同的使用领域对碰撞检测要求的方面不同，比如速度和精确度更侧重哪一方面，等等这些要求，就决定了对碰撞检测算法的筛选和优化。碰撞检测技术在虚拟现实领域的重要性，决定了对它的研究将是一个漫长的过程，而且将会有更多新的算法融入其中。

参考文献：

[1]Frisken S.F.,Perry R.N.,Rockwood P.,Jones T.R.,Adaptively sampled distance fields:A general representation of shape for computer graphics.SIGGRAPH 2000,Computer Graphics Proceedings(2000),249-254.

[2]A.Fuhrmann,G.Sobotka,and C.Gross.Distance fields for rapid collision detection in physically based modeling.In Proceedings of GraphiCon,2003,58–65.

[3]Shinya and M.Forgue.Interference detection through rasterization.The Journal of Visualization and Computer Animation,1991,132-134.

[4]G.Baciu,W.S.-K.Wong,and H.Sun.RECODE:an image–based collision detection algorithm.The Journal of Visualization and Computer Animation,1999,181-192.

[5]K.Myszkowski,O.Okunev,and T.Kunii.Fast collision detection between complex solids using rasterizing graphics hardware.The Visual Computer,11(9),1995,497-12. [6]T.Vassilev,B.Spanlang,and Y.Chrysanthou.Fast cloth animation on walking avatars.In Proceedings of Eurographics,2001,137-150.

[7]B.Heidelberger,M.Teschner,and M.Gross.Real-time volumetric intersections of deforming objects.In Proceedings of Vision,Modeling,Visualization,2003，461–468.

[8]Stefan Kimmerle，collision detection and post-processing for physical cloth simulation,Dissertation,Tübingen,2005,28-31.

[9]S.Kimmerle,M.Nesme,and F.Faure.,Hierarchy accelerated stochastic collision detection.In Proceedings of Vision,Modeling,Visualization,2004,307–314.

[10]LIN.M.C，CANNY J．F．Efficient Collision Detection for Animation[C],Proc．3rd Eurographics Workshop on Animation and Simulation,Cambridge,1992．

[11]Laks Raghupathi,Laurent Grisoni,Francois Faure,et a1．An intestine surgery simulator：Real—time collision processing and visualization[J],IEEE Transaction on Visualization and Computer Graphics，2004，708-718

[12]金汉均,李朝晖,张晓亮等,基于遗传算法的凸多面体间碰撞检测算法研究[J],华中师范大学学报,2006.3,40卷1期，25-28

[13]李文辉,王天柱,王炜等,基于粒子群面向可变形物体的随机碰撞检测算法[J],系统仿真学报,2006.8,18卷8期，2206-2209

[14]夏云飞,赵伟,基于模拟退火遗传算法的凸多面体间碰撞检测算法研究[J],长春工业大学学报:自然科学版,2008, 29卷1期,82-86

碰撞检测

二维碰撞检测算法 碰撞检测（Collision Detection,CD）也称为干涉检测或者接触检测，用来检测不同对象之间是否发生了碰撞，它是计算机动画、系统仿真、计算机图形学、计算几何、机器人学、CAD\ CAM等研究领域的经典问题。 碰撞物体可以分为两类：面模型和体模型。面模型是采用边界来表示物体，而体模型则是使用体元表示物体。面模型又可根据碰撞后物体是否发生形变分为刚体和软体，刚体本身又可根据生成方式的不同分为曲面模型和非曲面模型。目前对于碰撞的研究多集中于面模型的研究，因为体模型是一种三维描述方式，对它进行碰撞检测代价较高。而在面模型的研究中，对刚体的研究技术更为成熟。 下面列举几种常用的碰撞检测技术： 1：包围盒（bounding box）是由Clark提出的，基本思想是使用简单的几何形体包围虚拟场景中复杂的几何物体，当对两个物体进行碰撞检测时，首先检查两个物体最外层的包围盒是否相交，若不相交，则说明两个物体没有发生碰撞，否则再对两个物体进行检测。基于这个原理，包围盒适合对远距离物体的碰撞检测，若距离很近，其物体之间的包围盒很容易相交，会产生大量的二次检测，这样就增大了计算量。 包围盒的类型主要有AABB(Aligned Axis Bounding Box)沿坐标轴的包围盒、包围球、OBB(Oriented Bounding Box)方向包围盒和k-DOP(k Discrete Orientation Polytopes)离散方向多面体等。 AABB是包含几何对象且各边平行于坐标轴的最小六面体，两个AABB包围盒相交当且仅当它们三个坐标轴上的投影均重叠，只要存在一个方向上的投影不重叠，那么它们就不相交。AABB间的相交测试和包围体的更新速度比其他算法

虚拟手术中实时碰撞检测技术

虚拟手术中实时碰撞检测技术研究 彭 磊 张裕飞 王秀娟 （泰山医学院 信息工程学院 山东 泰安 271016） 摘 要： 碰撞检测是虚拟手术的关键技术，为提高检测速度，满足系统实时性的要求，提出空间剖分和层次包围盒相结合的方法。使用八叉树表示法对虚拟场景进行空间剖分，在叶节点构建层次包围盒。进行碰撞检测时属于不同八叉树节点的几何元素不会相交，否则使用层次包围盒算法继续进行检测，对于有可能相交的几何元素再进行精确相交检测。 关键词： 虚拟手术；碰撞检测；空间剖分；层次包围盒 中图分类号：TP391.9 文献标识码：A 文章编号：1671－7597（2012）1120029－02 进行碰撞检测时从八叉树的根节点开始，计算两几何元素0 引言 是否属于同一节点，如果不属于同一节点则不相交，如果属于虚拟手术是集医学、生物力学、材料学、计算机图形学、同一节点，递归的到下一级节点进行检查，直到发现两几何元虚拟现实等诸多学科为一体的交叉研究领域。虚拟手术在医学素属于同一叶节点，则需要进一步使用层次包围盒进行检查。 中的应用主要包括：手术计划与过程模拟、术中导航与监护、 2 层次包围盒 手术教学与训练等。碰撞检测是虚拟手术系统中的关键技术，贯穿于虚拟手术的整个过程。 对于八叉树的每个叶节点包含的几何元素，建立层次包围虚拟手术系统中的对象根据材质可分为刚体组织和软件组盒（Bounding Volume Hierarchy ，BVH ）。相对于单纯的层次织。骨骼、手术器械等属于刚体组织，而人体的许多器官如肌包围盒技术，使用空间剖分与层次包围盒相结合的方法进行碰肉、血管、肝脏等属于软体组织。以往大部分碰撞检测的研究撞检测，构建的层次树规模更小，计算量更少。层次包围工作都是针对刚体对象的。与刚体相比较，软体组织由于其特殊的物理性质，在外力或某些操作的作用下会发生几何形状、位置甚至数量上的变化，因此基于软体组织的碰撞检测需要更详细的信息和更多的处理。 最简单的碰撞检测方法是对场景中的几何元素进行两两相2交测试，其时间复杂度为O(n )，虽然这种方法可以得到正确的结果，但是当场景中的几何模型稍微增多些，其实时性便无法满足实际的需求。为了尽可能地减少参与相交测试的几何元素的数量，提高系统的实时性，目前碰撞检测技术使用的主要算法有：层次包围盒法，空间分割法，基于网格剖分的方法[1]。但是这些经典的算法也都存在着构造难度大、紧密性差、相交测试复杂、效率低等缺点。 本文采用空间剖分和层次包围盒相结合的方法，简化了几何信息的表示，进行碰撞检测时可排除明显不相交的几何元素，无法排除的再进行精确相交检测，从而减少计算量，加速碰撞检测速度，提高系统实时性。 1 空间剖分技术 整个虚拟手术的场景空间递归的剖分成若干个网格单元，每一个几何元素都属于某个网格单元，处于同一网格单元内的几何元素才有相交的可能，不在同一网格单元的几何元素一定不会相交。采用八叉树的表示方法进行空间剖分。即包含整个场景的立方体作为八叉树的根节点，立方体的3条棱边分别与x ，y ，z 轴平行。递归的将立方体剖分为8个小块，如图1（a ）所示，生成8个子节点，直到达到指定的剖分层次为止，如图1（b ）所示，每个叶节点包含有限个几何元素。 图1 八叉树表示法 盒包括包围盒和层次树两种数据结构。 2.1 包围盒 包围盒技术是减少相交检测次数，降低碰撞检测复杂度的一种有效的方法。其基本思想是用几何形状相对简单的封闭表面将一复杂几何元素包裹起来，首先进行包围盒之间的相交测试，排除明显不相交的几何元素，无法排除的几何元素，再进一步进行精确的相交测试，从而达到减少相交测试计算量的目的。常见的包围盒类型有：包围球（Bounding Sphere ）、沿坐标轴的包围盒（Axis Aligned Bounding Box ，AABB ）、方向包围盒（Oriented Bounding Box ，OBB ）。离散方向包围盒（k-Discrete Orientation Polytopes ，k-DOPs ）等[2]，如图2所示。 图2 包围盒 由于虚拟手术对实时性要求较高，本文选择AABB 型包围盒，AABB 是平行于坐标轴的，包含几何元素的最小正立方体。其优点是：1）易于构建，只需要计算所包含几何元素的顶点的x ，y ，z 坐标的最大值和最小值，存储6个浮点数即可；2）相交测试计算量小，相交测试时只需对两个包围盒在三个坐标轴上的投影分别进行比较，最多6次比较运算即可。 2.2 包围盒层次树 包围盒层次树即包围盒的层次结构，层次树的根节点包含某个八叉树叶节点几何元素的全集，向下逐层分裂，直到每个叶节点表示一个基本几何元素。常用的构建策略有自顶向下和自底向上两种。 自顶向下的方法首先建立根结点，利用基于全集的信息递归地将每个节点分裂为两个或多个子集，直至生成只包含一个 基本图元的叶结点为止，从而建立一棵自顶向下的包围盒层次 （ ）八叉树结构 （ ）节点的剖分

实验四：基于BSP技术的室内场景渲染和碰撞检测

实验四：基于BSP???碰撞检测 姓名：班级：学号： 一、实验目 掌握BSP?原理； 熟悉Ogr?e中基于S P??法。 二、实验仪器 pc、visua?l studi?o 2010 、实验原理 ?过程 //网上检索B?S P相关 //利 Ogr?e实现基于B SP? 程?实现 ???A PI进行详细说明1、BSP相关? （1）BSP? BSP Trees??B i nar?y Space? Parti?o ning?trees? 二 ? 二 ?。 ： ?； 中?光照运算；BSP?预 。 （2）BSP原理? 顺 判定 BSP：二 ?。 ?????? 。 ??定过 ??? 一 ?B S P。 ?上 于 ?件Z Buf?f er?后向前画。

?于?Z B uff?e r?前向后 ? 于后画 ??遮挡而 Z?B uffe?r CUT 而 ?高。 筛选优化 ?进行顺 判?定? 中 ?上?? 过?筛选。 PVS ?减外BSP?过?进行进一 ?筛选优化?。 理?解Po?r tal： ??。Porta?l?于 一? 进行 ? 算 算 ?； 二 法??集合PV?S?候 同 ??? 关 候 ??PVS? 关 ? 。 前 ?D 候?BC?过PVS?测试 A一 ??C U T。

（3）BSP? BSP?流程： 1） ???PVS?信息； 2） ?； 3）??判 ????理； ? 中 判 上级 ?。 4） ????? 理（ ） 后 ?理 ； ? 理 ? 后 理? ； 5） ? 判 PVS??中? 进?行。 2、程 实现 ??相API? 详细?说明 多边 A 一 顶 位于多边 组 一 说多边 A位于多边 “前 ”参考左图。 想象一 一 盒 6 组 朝向盒说盒 一“凸多边 ”朝向盒 盒 “凸多边”。 图1.2 让 一 何确定一 图元集合 否一 “凸多边 ” 伪算法 ： （1） - 参 : o n –确定一 D 中 相 位置 参考多边 。 –待确定 D 中 。 返 值: 位于多边 哪一边。 功 : 确定一 位于 多边定义 哪一边。

3d碰撞检测技术共30页文档

核心提示：10.3 碰撞检测技术到目前为止，构造的各种对象都是相互独立的，在场景中漫游各种物体，墙壁、树木对玩家（视点）好像是虚设，可以任意从其中穿越。为了使场景人物更加完善，还需要使用碰撞检测技术。 10.3.1 碰撞检测技术简介无论是PC 游戏，还是移动应用， 10.3 碰撞检测技术 到目前为止，构造的各种对象都是相互独立的，在场景中漫游各种物体，墙壁、树木对玩家（视点）好像是虚设，可以任意从其中穿越。为了使场景人物更加完善，还需要使用碰撞检测技术。 10.3.1 碰撞检测技术简介 无论是PC游戏，还是移动应用，碰撞检测始终是程序开发的难点，甚至可以用碰撞检测作为衡量游戏引擎是否完善的标准。 好的碰撞检测要求人物在场景中可以平滑移动，遇到一定高度的台阶可以自动上去，而过高的台阶则把人物挡住，遇到斜率较小的斜坡可以上去，斜率过大则会把人物挡住，在各种前进方向被挡住的情况下都要尽可能地让人物沿合理的方向滑动而不是被迫停下。 在满足这些要求的同时还要做到足够精确和稳定，防止人物在特殊情况下穿墙而掉出场景。

做碰撞检测时，该技术的重要性容易被人忽视，因为这符合日常生活中的常识。如果出现Bug，很容易被人发现，例如人物无缘无故被卡住不能前进或者人物穿越了障碍。所以，碰撞检测是让很多程序员头疼的算法，算法复杂，容易出错。 对于移动终端有限的运算能力，几乎不可能检测每个物体的多边形和顶点的穿透，那样的运算量对手机等设备来讲是不可完成的，所以移动游戏上使用的碰撞检测不可能使用太精确的检测，而且对于3D碰撞检测问题，还没有几乎完美的解决方案。目前只能根据需要来取舍运算速度和精确性。 目前成功商业3D游戏普遍采用的碰撞检测是BSP树及AABB （axially aligned bounding box）包装盒（球）方式。简单地讲，AABB检测法就是采用一个描述用的立方体或者球形体包裹住3D物体对象的整体（或者是主要部分），之后根据包装盒的距离、位置等信息来计算是否发生碰撞，如图10-24所示。 除了球体和正方体以外，其他形状也可以作包装盒，但是相比计算量和方便性来讲还是立方体和球体更方便些，所以其他形状的包装只用在一些特殊场合使用。BSP树是用来控制检测顺序和方向的数据描述。 在一个游戏场景中可能存在很多物体，它们之间大多属于较远位置或者相对无关的状态，一个物体的碰撞运算没必要遍历这些物体，同时还可以节省重要的时间。

碰撞检测技术

碰撞检测技术 碰撞检测技术2011-05-06 23：00 技术--引擎2008-09-05 19：50：55阅读251 10.3碰撞检测技术 到目前为止，构造的各种对象都是相互独立的，在场景中漫游各种物体，墙壁、树木对玩家(视点)好像是虚设，可以任意从其中穿越。为了使场景人物更加完善，还需要使用碰撞检测技术。 10.3.1碰撞检测技术简介 无论是PC游戏，还是移动应用，碰撞检测始终是程序开发的难点，甚至可以用碰撞检测作为衡量游戏引擎是否完善的标准。 好的碰撞检测要求人物在场景中可以平滑移动，遇到一定高度的台阶可以自动上去，而过高的台阶则把人物挡住，遇到斜率较小的斜坡可以上去，斜率过大则会把人物挡住，在各种前进方向被挡住的情况下都要尽可能地让人物沿合理的方向滑动而不是被迫停下。 在满足这些要求的同时还要做到足够精确和稳定，防止人物在特殊情况下穿墙而掉出场景。 做碰撞检测时，该技术的重要性容易被人忽视，因为这符合日常生活中的常识。如果出现Bug，很容易被人发现，例如人物无缘无故被卡住不能前进或者人物穿越了障碍。所以，碰撞检测是让很多程序员头疼的算法，算法复杂，容易出错。 对于移动终端有限的运算能力，几乎不可能检测每个物体的多边形和顶点的穿透，那样的运算量对手机等设备来讲是不可完成的，所以移动游戏上使用的碰撞检测不可能使用太精确的检测，而且对于3D碰撞检测问题，还没有几乎完美的解决方案。目前只能根据需要来取舍运算速度和精确性。

目前成功商业3D游戏普遍采用的碰撞检测是BSP树及AABB(axially aligned bounding box)包装盒(球)方式。简单地讲，AABB检测法就是采用一 个描述用的立方体或者球形体包裹住3D物体对象的整体(或者是主要部分)，之后根据包装盒的距离、位置等信息来计算是否发生碰撞，如图10-24所示。 除了球体和正方体以外，其他形状也可以作包装盒，但是相比计算量和方 便性来讲还是立方体和球体更方便些，所以其他形状的包装只用在一些特殊场 合使用。BSP树是用来控制检测顺序和方向的数据描述。 在一个游戏场景中可能存在很多物体，它们之间大多属于较远位置或者相 对无关的状态，一个物体的碰撞运算没必要遍历这些物体，同时还可以节省重 要的时间。 如果使用单步碰撞检测，需要注意当时间步长较大时会发生两个物体完全 穿透而算法却未检测出来的问题，如图10-25所示。其解决方案是产生一个4D 空间，在物体运动的开始和结束时间之间产生一个4D超多面体，用于穿透测试。 图10-24 AABB包装盒图10-25碰撞检测的单步失控和4D测试 读者在程序开发初期有必要对碰撞检测有一个初步的估计，以免最后把大 量精力消耗在碰撞检测问题上，从而降低了在基础的图形编程之上的注意力。 10.3.2球体碰撞检测 真实的物理模拟系统需要非常精确的碰撞检测算法，但是游戏中常常只需 要较为简单的碰撞检测，因为只需要知道物体什么时候发生碰撞，而不用知道 模型的哪个多边形发生了碰撞，因此可以将不规则的物体投影成较规则的物体 进行碰撞检测。 球体只有一个自由度，其碰撞检测是最简单的数学模型，我们只需要知道 两个球体的球心和半径就能进行检测。 那么球体碰撞是如何工作的?主要过程如下。 n计算两个物体中心之间的距离，并且将其与两个球体的半径和进行比较。

基于GJK的凸体快速连续碰撞检测研究

龙源期刊网 https://www.sodocs.net/doc/0811302280.html, 基于GJK的凸体快速连续碰撞检测研究 作者：刘丽等 来源：《河北科技大学学报》2014年第05期 摘要：针对一段时间内的多个运动物体之间的碰撞检测，提出一种基于距离算法（GilbertJohnsonKeerthialgorithm，GJK算法）的凸体快速连续碰撞检测算法，该算法主要通过判断一段时间内两物体之间的最小距离是否为零来检测碰撞发生情况。首先利用GJK算法在有限步骤内计算得到最小距离，检测两物体是否发生碰撞；若两物体发生碰撞，进而利用raycasting算法确定发生碰撞的精确位置，根据环境要求做出相应响应，调整运动物体位置。仿真结果表明，对多个运动物体间的连续碰撞检测，该算法有较高的实时性和准确性。 关键词：连续碰撞；GJK算法；运动物体；碰撞检测；凸体 中图分类号：TP391.9文献标志码：A Abstract：This paper presents a fast continuous collision detection algorithm to dealing with moving multiple convex objects within a period of time， which is based on the GilbertJohnsonKeerthi algorithm. The algorithm is determined by whether the minimum distance between the two objects within a period of time is zero to detect the occurrence of a collision. First，the algorithm utilizes GJK algorithm to calculate the minimum distance between the two objects and to detect the collision in finite steps. If two objects collide， then， determine the precise collision position of two objects based on the raycasting algorithm， and respond according to the environmental requirements， adjust two objects' location. The simulation results show that this algorithm has high realtime and accurate characteristics for continuous collision detection between multiple moving objects. Key words：continuous collision； GilbertJohnsonKeerthi（GJK） algorithm； moving objects； collision detection； convex objects 碰撞检测在计算机图形学、CAD/CAM、虚拟现实、虚拟制造、三维游戏等诸多领域都有广泛的应用，是提高虚拟场景物理真实感的关键问题之一[14]。按照场景模式不同，碰撞检测主要分为静态检测和动态检测。动态检测针对场景中至少存在一个运动物体的情况；根据碰撞检测方式的不同，动态检测分为离散检测和连续检测[5]。离散碰撞检测算法是对运动物体进 行取样检测，因此容易造成漏检测，进而产生穿透现象[6]。针对两物体间的穿透现象，连续 碰撞检测算法通过对一段连续时间内物体的运动过程进行建模，判断两物体之间的碰撞情况，可以很好地解决漏检测问题[6]，但计算量相对较大。目前，虚拟环境的场景复杂度越来越 高，对碰撞检测的实时性及准确性的要求也越来越高。因此，提高检测实时性及准确性是连续碰撞检测要解决的关键问题。

BIM中的碰撞检测技术?在管线综合中的应用及分析

BIM中的碰撞检测技术 在管线综合中的应用及分析 作者：张骋 来源：《中华建设科技》2014年第06期 【摘要】本文介绍利用BIM中的管线碰撞检测功能优化管综设计，对比分析二维、三维设计中的不同，并对设计中常出现的碰撞原因进行分析，对碰撞现象进行分类，提出了管线分析及优化的工作流程。 【关键词】管线碰撞；检测优化管；综设计；碰撞原因 The using and analyzing of intercrossed pipeline in BIM MEPdetection Zhang Cheng (Tianjin architecture design institute BIM design center Tianjin 300074) 【Abstract】 Introduce the using and analyzing of intercrossed pipelinein BIM MEP detection ,and contrast the different between the model of 2D and 3D,analyze the reason of intercrossed pipeline familiar in usually design, range the phenomenon of intercrossed pipeline, suggest the flow of the pipeline location analyzing and optimizing 【Key words】 Intercrossed-pipeline-detection;Optimizing-the-pipeline-location;Pipeline-intercross-reason 1. 引言 碰撞检测是BIM技术应用初期最易实现、最直观、最易产生价值的功能之一。如图1所示，利用软件将二维图纸转换成三维模型的过程，不但是个校正的过程，解决漏和缺的问题，实际上更是个模拟施工的过程，在图纸中隐藏的空间问题可以轻易的暴露出来，解决错和碰的问题。这样的一个精细化的设计过程，能够提高设计质量，减少设计人现场服务的时间。并且，一个贴近实际施工的模型，对预算算量的精确度及工作量，能有巨大的提升和降低，对于施工、物业管理、后期维修等，均有裨益。一个质量良好的模型，对于整个建筑行业，都有着积极的意义。 2. 建模

虚拟场景中基于包围盒的碰撞检测方法的研究与应用

虚拟场景中基于包围盒的碰撞检测方法的研究与应用 李红霞 河海大学计算机及信息工程学院，南京（210098） E-mail：lihongxia2005@https://www.sodocs.net/doc/0811302280.html, 摘要：将一种改进算法应用于台球的碰撞检测算法。利用虚拟环境中发生碰撞的帧与帧之间的关联性，对已发生的碰撞进行缓冲，以便下一次的碰撞检测可以利用已检测的上一次的碰撞的信息，加快了碰撞检测的速度，同时利用预测式方法扩展了这种算法。实验结果证明，本算法可以有效地解决碰撞检测的计算复杂性问题和改进虚拟环境中碰撞检测的性能，使动画效果更加逼真。 关键词：计算机动画，台球，碰撞检测，虚拟环境 1.引言 虚拟现实（Virtual Reality, 简称VR），又译为临境，灵境等。虚拟现实是对虚拟想象或真实三维世界的模拟。当对某个特定环境真实再现后，用户通过接受和响应模拟环境给予的各种感官刺激，从而达到身临其境的感觉[1]。虚拟现实可被看成一个高级的人机界面，人们可以通过视听触等信息通道来感受设计者的意图。 虚拟现实的特点包括：“身临其境”的沉浸感；友好亲切的人机交互性；激动人心的刺激性。参与者在虚拟环境中的活动或经历主要有两种形式：一种是主观参与者与参与者是整个经历的中心，一切围绕参与者进行。另一种是客观参与者，参与者可以在虚拟环境中看到自己与其他物体的交互。 VR技术的主要目标之一是允许用户以尽可能自然的方式与虚拟世界直接交互。VR中动态物体与静态物体之间或动态物体之间的交互基础是碰撞检测[2]。 碰撞检测在机器人路径规划、计算机动画、虚拟环境仿真等领域都起着至关重要的作用。而提高虚拟环境的沉浸感、增强虚拟环境的真实性对碰撞检测的准确性、实时性提出了更高的要求。 2.碰撞检测概述 碰撞检测（Collision Detection）就是检测虚拟场景中不同对象之间是否发生了碰撞。从几何上讲，碰撞检测表现为两个多面体的求交问题；在虚拟现实系统中，主要是如何解决碰撞检测的实时性和精确性的矛盾。准确的碰撞检测对于增强虚拟场景的真实感和沉浸感起着至关重要的作用。而碰撞问题包括碰撞检测和碰撞响应两部分。碰撞检测的目标是发现碰撞并报告；碰撞响应是在碰撞发生后，根据碰撞点和其它参数促使发生碰撞的对象做出正确的动作，以反应真实的动态效果。碰撞响应涉及到力学反馈、运动物理学等领域的知识。 碰撞检测问题基于现实生活中一个普遍存在的事实：两个不可穿透的对象不可能共享相同的区域。碰撞检测的基本任务是确定两个或多个物体彼此之间是否发生接触或穿透。即确定在某一时刻两个几何模型是否发生干涉，如发生碰撞，则需确定碰撞点[3]。 碰撞检测是一个复杂又费时的过程，按过程可以分为三个部分，碰撞检测、碰撞分析与决断、碰撞信息反馈。碰撞检测主要是检测是否两个物体之间发生碰撞，这个过程有许多方法实现，但对于一个大的集成系统来说，仅仅做出判断是不够的，获取到碰撞发生的时间和位置以及发生碰撞物体的几何元素。碰撞检测信息反馈主要为集成系统提供相应的说明和对物体的状态作出改变，以便为更高层任务的完成提供参考依据。