精华内容
下载资源
问答
  • OBB包围盒

    千次阅读 2017-05-15 20:46:25
    前面提到了长条物体在旋转时AABB的变化,那么是否有能够在任意方向都更为精确的检测方式,答案是肯定的,这是一种基于OBB即定向包容盒子(Oriented Bounding Box,OBB)的技术,它已经广泛用于光线追踪和碰撞检测中...

    转自http://www.cnblogs.com/lyggqm/p/5386174.html

    OBB

    前面提到了长条物体在旋转时AABB盒的变化,那么是否有能够在任意方向都更为精确的检测方式,答案是肯定的,这是一种基于OBB即定向包容盒子(Oriented Bounding Box,OBB)的技术,它已经广泛用于光线追踪和碰撞检测中。

    OBB这种方法是根据物体本身的几何形状来决定盒子的大小和方向,盒子无须和坐标轴垂直。这样就可以选择最合适的最紧凑的包容盒子。OBB盒子的生成比较复杂。一般是考虑物体所有的顶点在空间的分布,通过一定的算法找到最好的方向(OBB盒子的几个轴)。

    一个2D示意图如图10-38所示。

    这种技术比AABB技术更精确而且更健壮,但OBB实现起来比较困难,执行速度慢,并且不太适合动态的或柔性的物体。特别注意的是,当把一个物体分得越来越小的时候,事实上是在创建一棵有层次的树,如图10-39所示。

    图10-39  OBB树的生成(曲折线为物体)

    为任意的网格模型创建OBB树可能是算法里最难的一个部分,而且它还要调整以适合特定的引擎或游戏类型。从图中可以看出,不得不找出包围给定模型的最近似的包装盒(或者其他3D体)。

    现在得到了所有的包装盒,下一步将构造一棵树。

    从最初的AABB包装盒开始从上至下地反复分割它。另外,还可以用从下至上的方式,逐步地合并小包装盒从而得到最大的包装盒。把大的包装盒分割成小的包装盒,应该遵守以下几条原则。

    (1)用一个面(这个面垂直于包装盒中的一条坐标轴)来分割包装盒上最长的轴,然后根据多边形处在分割轴的哪一边把多边形分离开来(如图10-38所示)。

    (2)如果不能沿着最长的轴进行分割,那就沿第二长的边分割。持续地分割直到包装盒不能再分割为止。

    (3)依据需要的精度(比如,是否真的要判断单个三角形的碰撞),可以按选择的方式(是按树的深度或是按包装盒中多边形的数目)以任意的条件停止分割。

    正如读者所看到的,创建阶段相当复杂,其中包括了大量的运算,很明显不能实时地创建树,只能是事先创建。事先创建可以免去实时改变多边形的可能。另一个缺点是OBB要求进行大量的矩阵运算,不得不把它们定位在适当的地方,并且每棵子树必须与矩阵相乘。

    现在假设已经有了OBB或者AABB树。那么该怎么进行碰撞检测呢?首先检测最大的包装盒是否相交(AABB级别),如果相交了,它们可能(注意,只是可能)发生了碰撞,接下来将进一步地递归处理它们(OBB级别,不断地递归用下一级进行处理)。

    如果沿着下一级,发现子树并没有发生相交,这时就可以停止,并得出结论没有发生碰撞。如果发现子树相交,那么要进一步处理它的子树直到到达叶子节点,并最终得出结论。

    碰撞检测最直观的想法是把一个OBB盒子的每个边都和另一个盒子的所有面来比较,如果这个边穿过了另一个OBB盒子的一个面,则两个OBB盒子发生了碰撞。显然这种方法的计算量是比较大的,因为要进行12×6×2=144次边和面的比较。

    但是,在考察两个没有碰撞的OBB盒子时,人们发现一些规律来简化比较。

    (1)如果两个OBB盒子不互相接触,则应该可以找到一个盒子上的一个面,这个面所在的平面可以把3D空间分为两部分,两个OBB盒子各在两边。

    (2)如果没有这样的表面存在,则一定可以在两个OBB盒子上各找出一条边,这两条边所在的平面可以把两个OBB盒子分在两边。有了这个平面,就可以找到垂直于它的分割轴(separating axis),如图10-40所示。

    (3)进行相交测试时,可以把包装盒投影到分割轴上,并检查它们是否线性相交。两个OBB盒子在这个分割轴上的投影将是分离的。

    如上所述,要判断两个OBB盒子是否碰撞,只需要看两个OBB盒子之间是否有这样的平面和分割轴存在。如果存在,则没有碰撞。如果不存在,则碰撞。 对第一种情况,每个盒子有6个表面(其中每两个平行),可以决定3个分割轴。两个OBB盒子一共有6个可能的分割轴需要考虑。对第二种情况,两个OBB盒 子之间的边的组合可以有3×3=9种情况,也就是有9个可能的分割轴。这样对任意两个OBB盒子,只需要考察15个分割轴就可以了。如果在任一分割轴上的 阴影不重合,则OBB盒子之间没有碰撞。

    选择AABB还是选择OBB应该根据所需的精确程度而定。对一个需要快速反应的3D射击游戏来说,可能用AABB来进行碰撞检测更好些——可以牺牲一些精度来换取速度和实现的简单化,因此总能在游戏中看到一些小疏漏。当然随着硬件能力的提高,OBB处理会逐渐被重视起来。

    在做碰撞检测时应当遵循以下的优化理论,这样可以改善检测速度。

    n     分两步检验,距离远时看作质点,距离近时采用包装盒。

    n     距离很远的物体不会在短时间内相撞(可以采用BSP树分割空间)。

    n     一个物体不能隔着第二个物体和第三个物体相撞。

    n     一旦一个物体检测到和另一物体碰撞,另一物体对这个物体不再检测。

    n     静止的物体不主动与其他物体碰撞。

    以下是另一个博客的OBB解释:

    方向包围盒(Oriented bounding box),简称OBB。方向包围盒类似于AABB,但是具有方向性、可以旋转,AABB不能旋转。如图3所示。

    clip_image005

    图3 矩形和矩形投影检测的四条轴

    要计算两个OBB是否碰撞,只需要计算他们在图3上的4个坐标轴上的投影是否有重叠,如果有,则两多边形有接触。这也可以扩展到任意多边形,如图4所示。

    clip_image007

    图4 矩形和三角形投影检测的五条轴

    投影轴来自于多边形自身边的垂线。

    判定方式:两个多边形在所有轴上的投影都发生重叠,则判定为碰撞;否则,没有发生碰撞

    OBB存在多种的表达方式,这里使用最常用的一种:一个中心点、2个矩形的边长、两个旋转轴(该轴垂直于多边形自身的边,用于投影计算)。代码如下所示:

    (function (window) {

    var OBB = function (centerPoint, width, height, rotation) {

    this.centerPoint = centerPoint;
    this.extents = [width / 2, height / 2];
    this.axes = [new Vector2(Math.cos(rotation), Math.sin(rotation)), new Vector2(-1 * Math.sin(rotation), Math.cos(rotation))];

    this._width = width;
    this._height = height;
    this._rotation = rotation;
    }

    window.OBB = OBB;
    })(window);

    其所依赖的Vector2这个类如下所示:

    (function (window) {
    Vector2 = function (x, y) {
    this.x = x || 0;
    this.y = y || 0;
    };

    Vector2.prototype = {
    sub: function (v) {
    return new Vector2(this.x - v.x, this.y - v.y)
    },
    dot: function (v) {
    return this.x * v.x + this.y * v.y;
    }
    };
    window.Vector2 = Vector2;
    } (window))

    然后基于这个数据结构,进行OBB之间的相交测试。为OBB扩展一个方法,即或者在任意轴上的投影半径:

    OBB.prototype = {
    getProjectionRadius: function (axis) {
    returnthis.extents[0] * Math.abs(axis.dot(this.axes[0])) + this.extents[1] * Math.abs(axis.dot(this.axes[1]));
    }
    }

    这里你可能需要读者了解Vector2.dot的几何意义:若b为单位矢量,则a与b的点积即为a在方向b的投影

    有了这些,就可以进行相交检测。由上面的判定方式,可以得出,两个矩形之间的碰撞检测需要判断四次(每个投影轴一次)。完整检测代码如下所示:

    (function (window) {

    var CollisionDetector = {

    detectorOBBvsOBB: function (OBB1, OBB2) {
    var nv = OBB1.centerPoint.sub(OBB2.centerPoint);
    var axisA1 = OBB1.axes[0];
    if (OBB1.getProjectionRadius(axisA1) + OBB2.getProjectionRadius(axisA1) <= Math.abs(nv.dot(axisA1))) return false;
    var axisA2 = OBB1.axes[1];
    if (OBB1.getProjectionRadius(axisA2) + OBB2.getProjectionRadius(axisA2) <= Math.abs(nv.dot(axisA2))) return false;
    var axisB1 = OBB2.axes[0];
    if (OBB1.getProjectionRadius(axisB1) + OBB2.getProjectionRadius(axisB1) <= Math.abs(nv.dot(axisB1))) return false;
    var axisB2 = OBB2.axes[1];
    if (OBB1.getProjectionRadius(axisB2) + OBB2.getProjectionRadius(axisB2) <= Math.abs(nv.dot(axisB2))) return false;
    return true;

    }
    }

    window.CollisionDetector = CollisionDetector;
    })(window)

    这里拿两个OBB的中心点连线在坐标轴上的投影长度和两个矩形投影半径之和进行对比,如果半径之后都小于或者等于中心连线之后才判定为碰撞,否则判定为分离状态。

    集成图形化测试接口

    为了更加直观的测试OBB碰撞检测方法,使用Easeljs输出碰撞的状态。当两个矩形没有发生碰撞的时候,两矩形呈现蓝色;当两个矩形发生碰撞的时候,两矩形呈现红色。先引入相关的脚本库以及用于显示的canvas画布:

    <script src="Vector2.js" type="text/javascript"></script>
    <script src="OBB.js" type="text/javascript"></script>
    <script src="CollisionDetector.js" type="text/javascript"></script>
    <script src="easel.js" type="text/javascript"></script>
    <canvas id="testCanvas" width="980" height="580">
    

    然后进行OBB初始化以及碰撞检测:

    var OBB1, OBB1x = 100, OBB1y = 150, OBB1w = 30, OBB1h = 140, OBB1r = 30;
    var OBB2, OBB2x = 100, OBB2y = 70, OBB2w = 40, OBB2h = 110, OBB2r = 40;
    var canvas;
    var stage;
    var color;

    function init() {

    canvas = document.getElementById("testCanvas");
    stage = new Stage(canvas);

    Ticker.addListener(window);
    }

    function tick() {
    stage.removeAllChildren();

    OBB1r += 2;
    OBB2r += 1;
    OBB1 = new OBB(new Vector2(OBB1x, OBB1y), OBB1w, OBB1h, OBB1r * Math.PI / 180);
    OBB2 = new OBB(new Vector2(OBB2x, OBB2y), OBB2w, OBB2h, OBB2r * Math.PI / 180);
    var r = CollisionDetector.detectorOBBvsOBB(OBB1, OBB2);

    color=r?"red":"#00F";
    OBB1 = new Container();
    stage.addChild(OBB1);
    OBB1.x = OBB1x;
    OBB1.y = OBB1y;
    var frame1 = new Shape();
    frame1.graphics.beginFill(color).drawRect(0, 0, OBB1w, OBB1h);
    frame1.rotation = OBB1r;
    frame1.regX = OBB1w / 2;
    frame1.regY = OBB1h / 2;
    OBB1.addChild(frame1);

    OBB2 = new Container();
    stage.addChild(OBB2);
    OBB2.x = OBB2x;
    OBB2.y = OBB2y;
    var frame2 = new Shape();
    frame2.graphics.beginFill(color).drawRect(0, 0, OBB2w, OBB2h);
    frame2.rotation = OBB2r;
    frame2.regX = OBB2w / 2;
    frame2.regY = OBB2h / 2;
    OBB2.addChild(frame2);

    stage.update();
    }
    init();

    以上代码定义了两个旋转的OBB包围盒,当他们发生碰撞则改变绘制的颜色,使其成为红色。运行代码,效果图5和6所示。

    clip_image009

    图5 未发生碰撞

    clip_image011

    图6 发生碰撞

    这里是2D情况下的OBB碰撞检测,对于3D OBB碰撞检测,更为复杂。需要测试15个分离轴以确定OBB的相交状态,两个OBB的坐标轴各3个,以及垂直于每个轴的9个轴。除了坐标轴个数不一样,其相交测试思路和本文一致,本文不再探讨。

    展开全文
  • 图形学中经常出现AABB包围盒、OBB包围盒、外接球等,这些概念初次接触时有点容易混淆; 2.概念 AABB:Axis-Aligned Bounding Box,轴对齐包围盒; OBB:Oriented Bounding Box,有向包围盒; 包围球:外接球; ...

    1.问题

    图形学中经常出现AABB包围盒、OBB包围盒、包围球等,这些概念初次接触时有点容易混淆;

    2.概念

    AABB:Axis-Aligned Bounding Box,轴对齐包围盒;

    OBB:Oriented Bounding Box,有向包围盒;

    包围球:外接球;

    OBB比包围球和AABB更加逼近物体,能显著减少包围体的个数

    3.其他

    类似的概念还有凸包、最小外接轮廓等,有兴趣的可以查阅相关资料。

    展开全文
  • AABB包围盒 OBB包围盒 包围球的比较

    分享一下我老师大神的人工智能教程!零基础,通俗易懂!http://blog.csdn.net/jiangjunshow

    也欢迎大家转载本篇文章。分享知识,造福人民,实现我们中华民族伟大复兴!

                   

    1) AABB 包围盒: AABB 包围盒是与坐标轴对齐的包围盒, 简单性好, 紧密性较差(尤其对斜对角方向放置的瘦长形对象, 采用AABB, 将留下很大的边角空隙, 导致大量没必要的包围盒相交测试)。当物体旋转之后需对AABB 进行同样的旋转并更新; 当物体变形之后只需对变形了的基本几何元素对应的包围盒重新计算; 然后可以自下向上由子结点的AABB 合成父结点的AABB, 最后进行包围盒树的更新。

     

    --------------------------------------------------------------------------------

     

    2) OBB 包围盒: OBB 碰撞检测方法紧密性是较好的, 可以大大减少参与相交测试的包围盒的数目, 因此总体性能要优于AABB 和包围球, 并且实时性程度较高。当物体发生旋转运动后, 只需对OBB 进行同样的旋转即可。因此, 对于刚体间的碰撞检测, OBB 不失为一种较好的选择。迄今为止, 还没一种有效的方法能够较好地解决对象变形后OBB 树的更新问题, 而重新计算每个结点的OBB 的代价又太大。所以OBB 不适用于包含软体对象的复杂环境中。

    扩展参考:

    http://hi.baidu.com/jorbin/blog/item/2e7c2df5c146f423bd310977.html/cmtid/c13785356aaa081f90ef39bf

    http://www.cnblogs.com/gamesoul/archive/2007/05/29/764523.html

     

    --------------------------------------------------------------------------------

     

    3) 包围球: 包围球碰撞检测方法是用球体包围整个几何体, 无论是几何体还是相交测试都很简单; 但是它的紧密性太差。因为除了在3 个坐标轴上分布得比较均匀的几何体外, 几乎都会留下较大的空隙, 需要花费大量的预处理时间, 以构造一个好的层次结构逼近对象。当物体变形之后,包围球树需要重新计算。因此,它是使用得比较少的一种包围盒。当对象发生旋转运动时, 包围球不需作任何更新, 这是包围球的较优秀特性; 当几何对象进行频繁的旋转运动时, 采用包围球可能得到较好结果。

     

    --------------------------------------------------------------------------------

    边美玲, 任建平. 包围盒碰撞检测技术的研究 . 机械管理开发.  2008

     

    本文来自CSDN博客,转载请标明出处:http://blog.csdn.net/wangjiannuaa/archive/2010/12/13/6073253.aspx

               

    给我老师的人工智能教程打call!http://blog.csdn.net/jiangjunshow

    这里写图片描述
    展开全文
  • 针对车铣复合数控加工仿真碰撞检测精确度低的问题,提出了一种基于改进 OBB包围盒的快速碰撞检测算法.该算法基于改进的OBB包围盒算法,利用车铣复合加工仿真碰撞检测的结果,创建碰撞单元组的包围盒及层次包围盒树...
  • OBB包围盒的生成方法

    千次阅读 2017-11-03 18:35:03
    OBB包围盒,具有两个显著的特点: 在包含所有给定点的前提下,能够使得包围盒面积最小; 所生成的包围盒带有方向。 这里,通过一段时间的积累,主要给出基于PCA主成分分析的OBB包围盒的生成方法(二维),如有不当的...

    OBB包围盒,具有两个显著的特点:

    • 在包含所有给定点的前提下,能够使得包围盒面积最小;
    • 所生成的包围盒带有方向。

    这里,通过一段时间的积累,主要给出基于PCA主成分分析的OBB包围盒的生成方法(二维),如有不当的地方,望指教^_^!
    有些基础的知识可以查阅其他资料

    问题描述:给定n个二维坐标点{(x1,y1), (x2,y2), …, (xn,yn)},求能够包围所有这些点的OBB包围盒(长,宽,方向,中心店)。

    求解概括:

    1. 按坐标类型对数据进行组合:x = {x1, x2, …, xn},y = {y1, y2, …, yn}
    2. 分别求出集合x和集合y的平均值averX和averY,并构建协方差矩阵:
      [cov(x,x)cov(y,x)cov(x,y)cov(y,y)](1)
    3. 再根据协方差矩阵求解其特征值和特征向量,其中特征值较大者为OBB包围盒的方向。
    4. 得到的特征向量即为新的坐标系,将原始数据回落到该坐标系下,即可求得OBB包围盒的长,宽以及中心点。

    具体实例:

    原始数据,第一列为x轴坐标,第二列为y轴坐标:

    3.74.14.75.26.06.39.710.011.012.51.43.82.92.84.03.66.34.93.66.4(2)

    计算得到协方差矩阵,网上方法很多,这里就不做介绍:
    [10.09293.859563.859562.40233](3)

    求出协方差的最大特征值为:11.6958
    特征向量为
    [0.9235250.383539](4)

    将原始数据回落至新的坐标轴上,(首先原始数据 - 平均值)*特征向量组:
    3.623.222.622.121.321.022.382.683.685.182.570.171.071.170.030.372.330.930.372.43[0.9235250.383539](5)

    得到最终结果:
    4.328853.038952.830022.406611.207551.08393.091642.831743.256665.715860.9850461.0780.01670180.267420.5339770.04950571.238990.1690081.753130.257431(6)

    长度:10.0447
    宽度:2.99212

    展开全文
  • 提出一种将场景图中的 OBB包围盒以八叉树的形式划分 , 并利用八叉树的层次结构实现有效碰撞检测的方法 ,该方法从宏观到微观的搜索方式可以快速确定需要进行相交检测的对象列表 , 有效地避免所有几何节点与运动节点的...
  • 包围盒在碰撞检测等方面有着非常重要的应用,网上关于OBB包围盒的介绍很多,介绍的很好的一篇文章为https://blog.csdn.net/qing101hua/article/details/53100112这篇,想了解原理的话可以仔细看一看这篇文章。...
  • OBB包围盒生成算法

    2016-11-22 19:21:25
    生成OBB(方向包围盒算法),java实现。
  • 关于obb包围盒

    千次阅读 2012-12-29 16:44:29
    判断obb包围盒和射线p+t*D是否相交的方法:把p和D变换到obb包围盒坐标系下,然后看p+t*D这个表达式的值是否超过obb包围盒的每个方向的伸展长度,具体方法是对于p+t*D的每个方向上判断D的正负,如果D为正的话意味着p+...
  • OBB包围盒碰撞检测算法验证

    千次阅读 2019-04-24 18:15:40
    OBB包围盒碰撞检测算法验证 投影轴来自于多边形自身边的垂线。 判定方式:两个多边形在所有轴上的投影都发生重叠,则判定为碰撞;否则,没有发生碰撞 附带CAD验证下载地址: ...
  • 用PCL绘制AABB和OBB包围盒

    千次阅读 2020-01-30 16:19:30
    本文主要介绍基于PCL的AABB包围盒和OBB包围盒代码,并对两个包围盒均进行了二次封装,函数输入为点云指针。 首先,包含必要的头文件: #include <iostream> #include <string> #include <vector> ...
  • OBB包围盒的碰撞检测unity3D实现

    千次阅读 2019-11-25 18:36:22
    最近在学习OBB包围盒算法,一直找不到关于unity3D方面的代码,OBB全称Oriented bounding box,方向包围盒算法。其表现效果和Unity的BoxCollider并无二致。由于3D空间的OBB需要多考虑一些情况。 代码链接:...
  • 对方向包围盒(OBB)的计算方法进行了分析,并针对其不足之处进行了...利用改进后的OBB包围盒碰撞检测技术实现导梁架桥机中部件间碰撞的精确快速检测,并最终在VC++和Open InventorAPI平台上实现了系统的逼真的仿真效果。
  • 最近在弄obb包围盒,有以下几个问题: 1.ComputeOBB (vtkDataSet *input, double corner[3], double max[3], double mid[3], double min[3], double size[3])中表示轴向的min,mix,mid不清楚具体是什么 2.尝试了...
  • 1) AABB 包围盒: AABB 包围盒是与坐标轴对齐的包围盒, 简单性好, 紧密性较差(尤其对斜对角方向放置的瘦长形对象, ...2) OBB 包围盒: OBB 碰撞检测方法紧密性是较好的, 可以大大减少参与相交测试的包围盒的数目, 因此总
  • 虚拟现实中的碰撞检测,一种基于八叉树的OBB包围盒碰撞检测方法.pdf
  • 20201011-pcl构造AABB\OBB包围盒 //TODO::头文件定义 #include<pcl/point_cloud.h> #include<pcl/io/pcd_io.h> #include<pcl/point_types.h> #include<vector> #include<vtkAutoInit.h&...
  • 这是一个基于osg的方向包围盒计算的实现,利用协方差矩阵计算一组点的最小包围盒
  • 我给出了两个点,并由此延伸出来8个点,所有可以构建三维的obb包围盒。请各位大佬帮我看一下我的代码哪里错了。x1=1600;x2=1430;y1=1600;y2=1430;z1=584.6;z2=584.6;inputdata = [x1-r,y1,z1;x2-r,y2,z2;x1,y1,z1;x2...
  • 球形包围盒的碰撞检测,生成原理: 生成方法是均值法,Ritter方法 均值法简单,快速,但是不准确,生成的包围盒不是特别贴近模型 Ritter方法步骤更多,要慢一些,但是包围盒更准确,更贴近模型 ...
  • 1) AABB 包围盒: AABB 包围盒是与坐标轴对齐的包围盒, 简单性好, 紧密性较差(尤其对斜对角方向放置的瘦长形对象, 採用AABB, 将留下非常大的边角空隙, 导致大量不是必需的包围盒相交測试)。当物体旋转之后需对AABB ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 616
精华内容 246
关键字:

obb包围盒