三维物体碰撞检测包围盒算法分析
碰撞检测教程(C++)
简介 本文是阐述如何在2D动作游戏中进行精确而高效的碰撞检测。这里的碰撞是基于多边形而不是基于精灵的。这两者之间在设计上会有不同。 基于精灵的碰撞检测是通过精灵之间的重叠的像素来完成的。而多边形使用向量数学来精确计算交点，时间和碰撞方向。虽然多边形仅仅是精灵的一个近似，但是它比精灵系统要高级。 ?可以精确模拟逼真的简单物理学，例如反弹，摩擦，斜面的滑行 ?碰撞检测可以更精确的用于高速精灵系统。在基于精灵的系统中，如果物体移动过快就会在跳过另一个物体。 ?基于向量数学因此可以扩展到3D，然而精灵碰撞系统被严格限制在2D的情况下。 特性 本文使用的算法只适用于凸多边形，例如三角形，四边形，六边形，圆形。对于非凸多边形，你可以将其分解为多个凸多边形，例如三角形。 算法可以用于快速移动或慢速移动的多边形。不管物体移动多快，碰撞都不会丢失。它也可以处理重叠的问题，并促使交叠物体分离。 演示也支持分割多边形交叉。这可以用于子弹的建模。 同时提供了简单的物体系统，弹力，一些基本的摩擦和静摩擦力。用于确保物体不会从斜面上滑落。
有一个刚体系统的例子，使用了Chrsi Hecker的物理教程。 限制 有序碰撞。就是说并不是有序的进行碰撞。这对于快速移动的物体会出现一定的问题。一旦碰撞被检测到，它就被直接处理了。理想状态下你可能需要找到一个碰撞点并处理它，然后寻找更多的碰撞。但是对于2D动作游戏，这通常是不必要的。 一、分离坐标轴方法 这个方法是碰撞检测的核心。它的规则非常简单并且非常易于实现。这个方法也非常快并且非常可靠，因为计算中没有使用除法操作，下面给出一个简单的基于两个BOX的碰撞检测的例子。
碰撞检测
二维碰撞检测算法 碰撞检测（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 中 。 返 值: 位于多边 哪一边。 功 : 确定一 位于 多边定义 哪一边。
实时视频图像的清晰度检测算法研究教案
实时视频图像的清晰度检测算法研究 2010-12-18 17:11:42 来源:微型机与应用 关键字：实时视频图像背景提取Sobel算子清晰度检测 实时视频图像的质量分析已成为众多应用领域性能好坏的关键因素之一，因此实时视频图像的清晰度检测变得尤为重要。目前针对实时视频图像清晰度检测的研究较少，图像清晰度检测算法的研究对象主要针对静止的图像。现有的图像清晰度检测算法大致分为空域和频域两类。在空域中多采用基于梯度的算法，如拉普拉斯(Laplace)算法、差分平方和(SPSMD)算法、Sobel算子等。此类算法计算简洁、快速、抗噪性能好、可靠性较高。在频域中多采用图像的FFT变换(或其他变换)，如功率谱(Power-spectra)算法等[1-2]。此类算法的检测效果好，但计算复杂度高、计算时间长，不适合应用在基于软件实现的实时检测系统中。 当前对实时视频图像的一种重要应用是对运动目标的检测，常用的目标检测方法有帧差法、背景减法、光流法及运动能量法[3]，其中最简单而又快捷的方法是背景差法。其基本思想是通过对输入图像与背景图像进行比较来分割运动目标，关键环节是背景图像的提取。目前常用的背景提取方法有多帧图像平均法、灰度统计法、中值滤波法、基于帧差的选择方法、单高斯建模等。参考文献[4]中对以上算法做了充分的研究。 本文是针对实时视频图像的清晰度检测，基于实时视频图像背景基本保持不变的环境。通过比较上述算法，针对实时视频图像的特点，提出一种基于背景提取与Sobel算子相结合的实时视频图像的清晰度检测算法。 1 实时视频图像的清晰度检测算法原理 当视频播放画面超过24帧/s时，根据视觉暂留原理，人眼无法辨别每幅单独的静态画面，看上去是平滑连续的视觉效果。视频中的事物通常分为静止和运动两类，连续多帧画面中保持静止的物体可视为静止的背景，连续多帧画面中位置变化的物体可视为运动的前景。因此，实时视频图像中的每帧图像都可以划分为静止的背景和运动的前景两类区域。由于视频序列图像中运动的前景区域随机变化，引起图像像素点梯度值的随机改变，使得实时视频图像的清晰度检测较难实现。因此，本文的算法是利用实时视频图像中静止的背景区域检测视频序列图像的清晰度，即由背景提取和清晰度检测两部分组成。 1.1 实时视频图像的背景提取
碰撞检测技术
碰撞检测技术 碰撞检测技术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.wendangku.net/doc/ef18708000.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. 建模
(整理)3d碰撞检测技术
核心提示：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树是用来控制检测顺序和方向的数据描述。 在一个游戏场景中可能存在很多物体，它们之间大多属于较远位置或者相对无关的状态，一个物体的碰撞运算没必要遍历这些物体，同时还可以节省重要的时间。
(完整版)烟火检测算法
6.2 烟火检测算法的组成模块 运行烟火检测算法是为了确认在监测森林地区的相机的视野范围内是否有烟火的存在。这里提出的烟火检测算法由四个主要的子算法构成：（1）视图中缓慢移动物体的检测（2)烟色地区的检测（3）图像中上升物体的检测（4)阴影检测和消除阴影区域，在些子算法对于每一个n时刻输入的图像帧中x位置的像素都分别运用决策函数D1(x,n),D2(x,n),D3(x,n),D4(x,n)，选定高速率运算的算法是为了实现一个在标准个人电脑工作状况下的实时烟火检测系统。 子算法中的决策函数Di，i=1,...,m,不输出二进制的值如1（真）或者-1（假），但是输出代表每一个传入样本x的零均值实数。如果输出正（负）数，那么独立的算法判定出在相机观测范围内有（无）森林烟火。决策函数的输出值代表了了每个子算法的置信度。输出值越大，算法的置信度越高。 6.2.1缓慢移动物体的检测 视图中以相同速率运动的物体看起来在离相机距离远的地方比在离相机距离近的地方移动的要慢( 像素/秒）。假设在不同的背景图像Bfast（x,n）和Bslow（x,n)下把相机对焦，他们以不同的更新速率与现场通信【9】【65】，这里的x代表的是在第n帧图像中某个像素的位置。 在n+1帧时刻的背景图像B（x，n+1)是通过包含图像帧I（x，n）和背景图像B（x，n）的递推公式估算来的。公式如下： 此处的的I（x，n）指的是第n帧图像I中x X是固定的 X是移动的(6.1)
之间的一个常数。初始时，Bfast （x,0）和Bslow （x,0)可以取I （x ，0），固定的像素和移动的像素的定义见【19】。背景图像Bfast （x,n ）和Bslow （x,n)以不同的更新速率更新的方式如式6.1。在我们实现的算法中，Bfast （x,n ）取a=0.7每一帧更新一次，Bslow （x,n)取a=0,9每一秒更新一次。 通过比较两个不同的背景图像Bfast （x,n ）和Bslow （x,n)来检测在相机观测范围内的缓慢移动的物体【83】【9】【65】。如果在某一时间段两个图像中有实质的差异存在，那么就会有缓慢移动物体存在的警报产生，并且那个区域也会被标记。 表明第一个子函数置信度的决策函数输出值是由两个不同背景图像的差异决定的。决策函数D1（x ，n ）是如下定义的： （（ 这里的0
虚拟场景中基于包围盒的碰撞检测方法的研究与应用
虚拟场景中基于包围盒的碰撞检测方法的研究与应用 李红霞 河海大学计算机及信息工程学院，南京（210098） E-mail：lihongxia2005@https://www.wendangku.net/doc/ef18708000.html, 摘要：将一种改进算法应用于台球的碰撞检测算法。利用虚拟环境中发生碰撞的帧与帧之间的关联性，对已发生的碰撞进行缓冲，以便下一次的碰撞检测可以利用已检测的上一次的碰撞的信息，加快了碰撞检测的速度，同时利用预测式方法扩展了这种算法。实验结果证明，本算法可以有效地解决碰撞检测的计算复杂性问题和改进虚拟环境中碰撞检测的性能，使动画效果更加逼真。 关键词：计算机动画，台球，碰撞检测，虚拟环境 1.引言 虚拟现实（Virtual Reality, 简称VR），又译为临境，灵境等。虚拟现实是对虚拟想象或真实三维世界的模拟。当对某个特定环境真实再现后，用户通过接受和响应模拟环境给予的各种感官刺激，从而达到身临其境的感觉[1]。虚拟现实可被看成一个高级的人机界面，人们可以通过视听触等信息通道来感受设计者的意图。 虚拟现实的特点包括：“身临其境”的沉浸感；友好亲切的人机交互性；激动人心的刺激性。参与者在虚拟环境中的活动或经历主要有两种形式：一种是主观参与者与参与者是整个经历的中心，一切围绕参与者进行。另一种是客观参与者，参与者可以在虚拟环境中看到自己与其他物体的交互。 VR技术的主要目标之一是允许用户以尽可能自然的方式与虚拟世界直接交互。VR中动态物体与静态物体之间或动态物体之间的交互基础是碰撞检测[2]。 碰撞检测在机器人路径规划、计算机动画、虚拟环境仿真等领域都起着至关重要的作用。而提高虚拟环境的沉浸感、增强虚拟环境的真实性对碰撞检测的准确性、实时性提出了更高的要求。 2.碰撞检测概述 碰撞检测（Collision Detection）就是检测虚拟场景中不同对象之间是否发生了碰撞。从几何上讲，碰撞检测表现为两个多面体的求交问题；在虚拟现实系统中，主要是如何解决碰撞检测的实时性和精确性的矛盾。准确的碰撞检测对于增强虚拟场景的真实感和沉浸感起着至关重要的作用。而碰撞问题包括碰撞检测和碰撞响应两部分。碰撞检测的目标是发现碰撞并报告；碰撞响应是在碰撞发生后，根据碰撞点和其它参数促使发生碰撞的对象做出正确的动作，以反应真实的动态效果。碰撞响应涉及到力学反馈、运动物理学等领域的知识。 碰撞检测问题基于现实生活中一个普遍存在的事实：两个不可穿透的对象不可能共享相同的区域。碰撞检测的基本任务是确定两个或多个物体彼此之间是否发生接触或穿透。即确定在某一时刻两个几何模型是否发生干涉，如发生碰撞，则需确定碰撞点[3]。 碰撞检测是一个复杂又费时的过程，按过程可以分为三个部分，碰撞检测、碰撞分析与决断、碰撞信息反馈。碰撞检测主要是检测是否两个物体之间发生碰撞，这个过程有许多方法实现，但对于一个大的集成系统来说，仅仅做出判断是不够的，获取到碰撞发生的时间和位置以及发生碰撞物体的几何元素。碰撞检测信息反馈主要为集成系统提供相应的说明和对物体的状态作出改变，以便为更高层任务的完成提供参考依据。