碰撞检测 订阅
计算机边发送数据边检测信道上的信号电压大小。 展开全文
计算机边发送数据边检测信道上的信号电压大小。
信息
技术类别
互联网技术
方    法
模拟算法
中文名
碰撞检测
常见形式
3D游戏
监督学习监督学习词性解释
通信信道中的碰撞检测 就是计算机边发送数据边检测信道上的信号电压大小。当一个站检测到的信号电压摆动值超过了一定的门限值时,就会认为总线上至少有两个站同时在发送数据,表示产生了碰撞。在发生碰撞的时候,总线上传输信号产生了严重的失真,无法从中恢复出有用的信息来。每一个正在发送数据的站,一旦发现总线上产生了碰撞,就立即停止发送,以免继续浪费资源,再等待一段时间后再次发送。以太网取51.2μs为争用期长度。对于10Mb/s以太网,在争用期内可发送512bit,即64B。则以太网在发送数据时,若前64B没有冲突,则后续的数据就不会发生冲突。如果发生冲突了一定是在发送的前64B以内。由于一检测到冲突就立即中止发送,这时已经发出去的数据一定小于64B,因此,以太网规定最短有效长为64B,凡长度小于64B的帧都是由于冲突而异常中止的无效帧。发送数据的站一旦发现发生碰撞时,除了立即停止发送数据外,还要继续发送若干比特的认为干扰信号,以便让所有用户都知道已经发生了碰撞。3D游戏中的碰撞检测碰撞检测在3D游戏中至关重要,好的碰撞检测要求人物在场景中可以平滑移动,遇到一定高度内的台阶可以自动上去,而过高的台阶则把人挡住,遇到斜率较小的斜坡可以上去,斜率过大则把人挡住,在各种前进方向被挡住的情况下都要尽可能地让人物沿合理的方向滑动而不是被迫停下。在满足这些要求的同时还要做到足够精确和稳定,防止人物在特殊情况下穿墙而掉出场景。碰撞检测做得好了是应该的,不易被人注意到,因为这符合我们日常生活中的常识。做得差了却很容易让人发现,人物经常被卡住不能前进或者人物穿越了障碍。所以大部分人都觉得写碰撞检测代码是件吃力不讨好的事情,算法复杂、容易出bug、不容易出彩。下面还是回到正题,看看我们该如何解决这个难题。早期3D游戏的碰撞检测多数基于格子或者BSP树,基于格子的系统实现简单但精度不够,不属于严格意义的3D碰撞检测。基于BSP树的碰撞检测一度十分流行,算法基本已经成熟定型,但它的固有缺点却使它不太适合游戏。BSP树需要很长的预处理时间不适合加载时计算,BSP划分经常会产生原多边形数三到四倍的多边形,考虑到不用保存法线、颜色、uv等信息也要增加将近一倍的资源容量,在一个大的游戏中将模型资源的容量从200M增加到400M相信是大部分人都不愿接受的。对于任意复杂三角形集合(mesh)的碰撞检测多数基于BVTree(bounding volume tree),具体可以是aabb tree,obb tree或者K-dop tree,这也是当今各种物理引擎和碰撞检测引擎流行的做法。上面是碰撞检测按数据结构不同的分类,按检测方式又可以分为离散点的碰撞检测和连续碰撞检测(CCD continuous collision detection)。离散点的碰撞检测是指定某一时刻T的两个静态碰撞体,看它们之间是否交迭,如果没有交迭则返回它们最近点的距离,如果交迭则返回交迭深度,交迭方向等。连续碰撞检测则是分别指定在T1、T2两个时刻两个碰撞体的位置,看它们在由T1运动到T2时刻的过程中是否发生碰撞,如果碰撞则返回第一碰撞点的位置和法线。连续碰撞检测是最为自然的碰撞检测,可以大大方便碰撞响应逻辑的编写,可以很容易避免物体发生交迭或者穿越。离散点的碰撞检测则没有那么友好,当检测到碰撞时两个物体已经发生了交迭,如果其中有三角形网格对象那么已经有许多三角形发生了交迭,如何将两个交迭的对象分开并按合理的方式运动是一个挑战。虽然连续碰撞检测是最自然的方式,但它的实现非常复杂,运算开销也很大,所以大部分成熟的物理引擎和碰撞检测引擎还是采用了基于离散点的碰撞检测,为了避免物体交迭过深或者彼此穿越,大多都要采用比较小的模拟步长。成功商业3D游戏普遍采用的碰撞检测是采用BSP树及包装盒方式。简单讲就是采用一个描述用的正方体或者球型体包裹住3D物体对象整体(或者是主要部分),之后根据“描述用”包装盒的距离、位置等信息来计算是否发生碰撞。
收起全文
精华内容
参与话题
问答
  • 碰撞检测

    2020-11-09 20:48:14
    碰撞检测前言一、基本的碰撞检测二、基于BSP树的碰撞检测三、BVTree技术1.AABB包围盒2.方向包围盒OBB3.固定方向凸包FDH(K-dop)降低时间复杂度 前言 碰撞检测,俗称的体积碰撞,这一直是实时渲染研究中不可忽视的...

    前言

    碰撞检测,俗称的体积碰撞,这一直是实时渲染研究中不可忽视的方面。碰撞检测在终端用户的感觉中,应该是符合我们日常生活中的常识,不被感觉到才算做得好。

    一、基本的碰撞检测

    最基本的碰撞检测是通过空间中两个模型相互之间的所有线和所有三角形进行相交检测以达到碰撞检测的效果,这种穷举的算法,虽然精度极高但是消耗大量资源,并不适合实时渲染。
    而在早期三维碰撞检测大多基于格子,将空间分块,大概是二维算法的衍生,这种基于格子的系统实现简单,但是精度极低,不属于严格意义上的碰撞检测。

    二、基于BSP树的碰撞检测

    后来便有了基于BSP树的碰撞检测,这种算法是Melax提出的,这种算法事先进行预处理,能够达到动态的碰撞检测,但是预处理时间相当漫长,而且常常占用数倍的空间,这是很多用户所无法接受的。

    三、BVTree技术

    BVTree技术随之出现,在模型外面建立分层的包围盒,将问题进行分割降,以略微提升的空间复杂度为代价,大大降低了时间复杂度。BVTree根据实现的不同,具体可以是AABB Tree、Sphere Tree、OBB Tree、K-dop Tree等。 常见的包围盒大致有四种,AABB包围盒、包围球Sphere、方向包围盒OBB、固定方向凸包FDH(K-dop)。

    1.AABB包围盒

    AABB包围盒是最早出现的包围盒,是平行于坐标轴的最小六面体,AABB包围盒比较简单,除了大量冗余外,最大的问题是旋转物体后需要重新生成,而且只能处理刚性的对象。包围球是包含对象的最小球,解决了AABB不能旋转的问题,以所有元素的顶点的坐标的均值为球心,再由球心与三个最大值坐标所确定的点间的距离确定半径r,这就得到了包围球,依靠物体球形与半径的关系,很容易避免许多不必要的检测,然而,这种做法仍然冗余空间很大。

    2.方向包围盒OBB

    OBB是包围对象最小的长方体,这是较为常用的包围盒,可以根据物体表面的顶点,通过主成分分析获得特征向量(即OBB的主轴),以此建立包围盒,相对而言,这种方式的较为紧密,但是生成和相交检测较为复杂。

    3.固定方向凸包FDH(K-dop)

    FDH是 AABB的变体,继承了AABB的简洁,被定义为包含该对象且它的所有面的法向量都取自一个固定的方向集合的凸包,FDH是最为紧密的一种,但是相交检测最为复杂,可以用于软体对象的碰撞检测。在许多环境中,因为性能限制或者因为细节过于细微以至不易察觉,使用包围盒进行碰撞检测的结果直接看作最终结果的无限接近值也是一种选择。在空间中,一般都有许多物体,通过简单的计算,x个物体之间通过暴力求相互之间的碰撞检测需要x(x-1)/2次,时间复杂度为O(x平方),这样的性能开销是难以接受的。

    降低时间复杂度

    在1997年,Witkin 和Baraff提出可以用排序搜索降低时间复杂度,这种方法中我们可以将每个物体的边界映射到X、Y、Z三轴的其中一轴(也可以是一些其他的直线,但这三轴比较容易计算,可以略微降低计算的开销),以获得一维的数轴。如果在数轴中由两个物体边界得到的两个区间没有交集,那么便可以很容易知道,这两个两个物体不会发生碰撞。

    这也引出了下面的一种算法,将这些由物体在数轴上的端点插入2x个节点的链表之中,经过升序排序,再遍历链表。遇到每个物体的起始端点,就把该物体添加至另一个链表(活动物体)中,直到遇到该物体的结束端点,才将其从活动物体中移除。这样,每次对活动物体链表中所有物体执行碰撞检测就行了。因为在追求照片级作品中相邻两帧中空间基本相同,可以用时间复杂度为O(x平方)的插入排序来进一步加速算法,因为这个链表已经基本排好序,排序性能上可以达到O(x)。

    空间划分技术是上诉算法的一种替代方案,基本思想是将空间划分成三维的网格,保证每个网格的大小大于最大的物体。当两个物体都在网格中而且其中一个质心在网格中时这两个物体才会进行碰撞检测,以此来消除不必要的碰撞检测。但是如果物体间体积过于悬殊,会带来不必要的性能损耗,所以要保证网格要大于最大的物体,大小悬殊时可以通过Mirtich提出的“分层的网格”进一步提升效率。在实现中,使用一个物体的列表还有一个指向物体所属列表的hash函数,对列表排序后遍历每一个列表,依次执行碰撞检测。空间划分在并行执行中并不是十分容易实现,略微有些复杂,主要在于如果一个物体被牵扯到多个网格的碰撞检测,需要阻止多个线程或者进程对同一物体的同时修改。当然,碰撞检测的研究还没有结束,实时渲染其他方面的技术研究也在继续,更多的高效算法等着我们去寻找。

    HTML5 碰撞检测相关

    展开全文
  • 原生js实现碰撞检测

    2020-11-20 23:10:45
    本文实例为大家分享了js实现碰撞检测的具体代码,供大家参考,具体内容如下 随手写了个简单的碰撞检测的代码。检测box1和box2是否发生碰撞,若发生碰撞,box2颜色发生随机改变,并反弹到随机位置。 <!DOCTYPE ...
  • 在Canvas中进行碰撞检测,大家往往直接采用游戏引擎(Cocos2d-JS、Egret)或物理引擎(Box2D)内置的碰撞检测功能,好奇的你有思考过它们的内部运行机制吗?下面将针对基本的碰撞检测技术进行讲解: 1、基于矩形的碰撞...
  • 本文实例为大家分享了javascript实现拖拽碰撞检测的具体代码,供大家参考,具体内容如下 拖拽碰撞检测碰撞改变颜色 css: <style> .div1{width: 100px;height: 100px;background: pink;position: absolute;} ...
  • 论述了碰撞检测的种类以及应用BIM技术进行碰撞检测的方法,以广州地铁9号线岐山车辆段工程和伦敦维多利亚地铁站扩建工程为例,研究了如何应用BIM模型进行碰撞检测、软碰撞检测以及间隙碰撞检测。该项目使用BIM技术后...
  • 资源名称:实时碰撞检测算法技术内容简介:本书详细阐述了与碰撞检测问题相关的高效解决方案及相应的数据结构和算法,主要包括:碰撞检测系统中的设计问题、数学和几何学入门、包围体、基本图元测试、层次包围体技术...
  • 将末端姿态代入机械臂逆运动模型中,求出八组逆解角度,将八组逆解角度代入机械臂正运动学方程,判断机械臂与障碍物是否发生碰撞,进行碰撞检测,以实现机械臂避障路径规划。
  • 自己做了碰撞检测的封装,先看下实例demo,在看封装 <!DOCTYPE html> <html> <head> <meta charset="UTF-8"> <title>碰撞检测</title> <style type="text/css"> *{ ...
  • OpenGL小车 带碰撞检测

    2020-11-26 17:47:51
    从3ds导入的小车模型,配置了纹理光照和碰撞检测,带AI,从3ds导入的小车模型,配置了纹理光照和碰撞检测,带AI,从3ds导入的小车模型,配置了纹理光照和碰撞检测,带AI
  • 在布料仿真中,碰撞检测与响应十分复杂,很难同时具备真实感和实时性。针对此问题,采用质点弹簧模型进行建模,基于FDH包围盒提出一种快速的检测基本几何元素间碰撞的方法。通过分析点的位置向量与三角平面的夹角,...
  • 为实现虚拟环境中可变形物体与刚体间实时的碰撞检测,提出了一种快速的基于混合包围盒层次结构的并行碰撞检测算法。算法充分利用包围盒在检测速度和精度上的不同侧重,对可变形物体建立Sphere和AABB混合包围盒层次树...

空空如也

1 2 3 4 5 ... 20
收藏数 7,284
精华内容 2,913
关键字:

碰撞检测