程序员经验分享-hwhale

碰撞检测之OBB-OBB检测

2023-11-19
碰撞检测之OBB-OBB检测
2016年03月07日 02:20:14
阅读数：3732

2D情况

首先回顾一下SAP



两个凸包多边形，当且仅当存在一条线，这两个多边形在这条线上的投影不相交，则这两个多边形也不相交.


这条线称为Separating Axis.垂直Separating Axis存在一条Separating Line将两个多边形分开。


这里还有一个要确定的，就是如果两个矩形之间存在Separating Line，则一定存在一条和两个矩形中的一条边平行。每个矩形对边平行，则我们只需要检查四个方向是否存在Separating Line，如下图



找Separating Line 就是找Separating Axis, Separating Axis也只有四个方向，所以将矩形在四个轴上投影就可以了，如下图









下面来看具体的计算


定义下面几个变量

PA = coordinate position of the center of rectangle A
Ax = unit vector representing the local x-axis of A
Ay = unit vector representing the local y-axis of A
WA = half width of A (corresponds with the local x-axis of A)
HA = half height of A (corresponds with the local y-axis of A)


PB = coordinate position of the center of rectangle B

Bx = unit vector representing the local x-axis of B
By = unit vector representing the local y-axis of B
WB = half width of B (corresponds with the local x-axis of B)
HB = half height of B (corresponds with the local y-axis of B)


T= PB - PA

轴L是Seprating Axis的条件是

|Proj ( T )| > 0.5 * |Proj ( RectangleA )| + 0.5 *|Proj ( RectangleB )|


Proj是投影计算， 展开

| T • L | > | ( WA*Ax ) • L | + | ( HA*Ay ) • L | + | ( WB*Bx ) • L | + |( HB*By ) • L |

L只有四种情况，AX, AY, BX, BY

CASE 1:
// L = Ax
| T • Ax | > | ( WA*Ax ) • Ax | + | ( HA*Ay ) • Ax | + | ( WB*Bx ) • Ax | + |( HB*By ) • Ax |
| T • Ax | > WA + 0 + | ( WB*Bx ) • Ax | + |( HB*By ) • Ax |
| T • Ax | > WA + | ( WB*Bx ) • Ax | + |( HB*By ) • Ax |

如果成立，存在Separating Axis平行Ax。


CASE 2:
// L = Ay
| T • Ay | > HA + | ( WB*Bx ) • Ay | + |( HB*By ) • Ay |

如果成立，存在Separating Axis平行Ay。


CASE 3:
// L = Bx
| T • Bx | > | ( WA* Ax ) • Bx | + | ( HA*Ay ) • Bx | + WB

如果成立，存在Separating Axis平行Bx。


CASE 4:
// L = By
| T • By | > | ( WA* Ax ) • By | + | ( HA*Ay ) • By | + HB

如果成立，存在Separating Axis平行By。



三维情况

在三维情况下的，之前的Separating Line就变成了Separating Plane，如下图



每个Box都有三组面，每组面都是平行的，Separating Plane都是平行其中的一个面。则两个box的SAT（Separating AxisTheorem）中可能的Separating Axis有六个




下图中Separating Plane就平行于右边Box的一个面



然而还有一种情况，如下



这种情况，两个Box并不相交，但是他们并没有发生碰撞，这种情况，Separating Plane的法线是两条红线的叉乘



所以在三维情况下Box和Box的碰撞检测需要判定的情况有6+9种

CASE 1:L = Ax  CASE 2:L = Ay  CASE 3:L = Az   CASE 4:L = Bx   CASE 5:L = By  CASE 6:L = Bz

CASE 7:L = Ax Bx  CASE 8:L = Ax By  CASE 9:L = Ax Bz  CASE 10:L = Ay Bx  

CASE 11:L = Ay By  CASE 12:L = Ay Bz  CASE 13:L = Az Bx  CASE 14:L = Az By  CASE 15:L = Az Bz


判断条件还是

| T • L | > | ( WA*Ax ) • L | + | ( HA*Ay ) • L | + |( DA*Az ) • L |+ | ( WB*Bx ) • L | + |( HB*By ) • L | + |( DB*Bz ) • L |

一点优化，关于T • L 

T • (Ax * Bx) =(T •  Az)(Ay •  Bx) - (T•  Ay)(Az •  Bx)

这里将有叉乘的地方进行了转化，要看证明的请看参考资料。


好，可以上代码了

[csharp] view plain copy
  1. public static bool IntersectBoxBox(Box box0, Box box1)  
  2.       {  
  3.           Vector3 v = box1.center - box0.center;  
  4.   
  5.           //Compute A's basis  
  6.           Vector3 VAx = box0.rotation * new Vector3(1, 0, 0);  
  7.           Vector3 VAy = box0.rotation * new Vector3(0, 1, 0);  
  8.           Vector3 VAz = box0.rotation * new Vector3(0, 0, 1);  
  9.   
  10.           Vector3[] VA = new Vector3[3];  
  11.           VA[0] = VAx;  
  12.           VA[1] = VAy;  
  13.           VA[2] = VAz;  
  14.   
  15.           //Compute B's basis  
  16.           Vector3 VBx = box1.rotation * new Vector3(1, 0, 0);  
  17.           Vector3 VBy = box1.rotation * new Vector3(0, 1, 0);  
  18.           Vector3 VBz = box1.rotation * new Vector3(0, 0, 1);  
  19.   
  20.           Vector3[] VB = new Vector3[3];  
  21.           VB[0] = VBx;  
  22.           VB[1] = VBy;  
  23.           VB[2] = VBz;  
  24.   
  25.           Vector3 T = new Vector3(Vector3.Dot(v, VAx), Vector3.Dot(v, VAy), Vector3.Dot(v, VAz));  
  26.   
  27.           float[,] R = new float[3, 3];  
  28.           float[,] FR = new float[3, 3];  
  29.           float ra, rb, t;  
  30.   
  31.           for (int i = 0; i < 3; i++)  
  32.           {  
  33.               for (int k = 0; k < 3; k++)  
  34.               {  
  35.                   R[i, k] = Vector3.Dot(VA[i], VB[k]);  
  36.                   FR[i, k] = 1e-6f + Mathf.Abs(R[i, k]);  
  37.               }  
  38.           }  
  39.   
  40.           // A's basis vectors  
  41.           for (int i = 0; i < 3; i++)  
  42.           {  
  43.               ra = box0.extents[i];  
  44.               rb = box1.extents[0] * FR[i, 0] + box1.extents[1] * FR[i, 1] + box1.extents[2] * FR[i, 2];  
  45.               t = Mathf.Abs(T[i]);  
  46.               if (t > ra + rb) return false;  
  47.           }  
  48.   
  49.           // B's basis vectors  
  50.           for (int k = 0; k < 3; k++)  
  51.           {  
  52.               ra = box0.extents[0] * FR[0, k] + box0.extents[1] * FR[1, k] + box0.extents[2] * FR[2, k];  
  53.               rb = box1.extents[k];  
  54.               t = Mathf.Abs(T[0] * R[0, k] + T[1] * R[1, k] + T[2] * R[2, k]);  
  55.               if (t > ra + rb) return false;  
  56.           }  
  57.   
  58.           //9 cross products  
  59.   
  60.           //L = A0 x B0  
  61.           ra = box0.extents[1] * FR[2, 0] + box0.extents[2] * FR[1, 0];  
  62.           rb = box1.extents[1] * FR[0, 2] + box1.extents[2] * FR[0, 1];  
  63.           t = Mathf.Abs(T[2] * R[1, 0] - T[1] * R[2, 0]);  
  64.           if (t > ra + rb) return false;  
  65.   
  66.           //L = A0 x B1  
  67.           ra = box0.extents[1] * FR[2, 1] + box0.extents[2] * FR[1, 1];  
  68.           rb = box1.extents[0] * FR[0, 2] + box1.extents[2] * FR[0, 0];  
  69.           t = Mathf.Abs(T[2] * R[1, 1] - T[1] * R[2, 1]);  
  70.           if (t > ra + rb) return false;  
  71.   
  72.           //L = A0 x B2  
  73.           ra = box0.extents[1] * FR[2, 2] + box0.extents[2] * FR[1, 2];  
  74.           rb = box1.extents[0] * FR[0, 1] + box1.extents[1] * FR[0, 0];  
  75.           t = Mathf.Abs(T[2] * R[1, 2] - T[1] * R[2, 2]);  
  76.           if (t > ra + rb) return false;  
  77.   
  78.           //L = A1 x B0  
  79.           ra = box0.extents[0] * FR[2, 0] + box0.extents[2] * FR[0, 0];  
  80.           rb = box1.extents[1] * FR[1, 2] + box1.extents[2] * FR[1, 1];  
  81.           t = Mathf.Abs(T[0] * R[2, 0] - T[2] * R[0, 0]);  
  82.           if (t > ra + rb) return false;  
  83.   
  84.           //L = A1 x B1  
  85.           ra = box0.extents[0] * FR[2, 1] + box0.extents[2] * FR[0, 1];  
  86.           rb = box1.extents[0] * FR[1, 2] + box1.extents[2] * FR[1, 0];  
  87.           t = Mathf.Abs(T[0] * R[2, 1] - T[2] * R[0, 1]);  
  88.           if (t > ra + rb) return false;  
  89.   
  90.           //L = A1 x B2  
  91.           ra = box0.extents[0] * FR[2, 2] + box0.extents[2] * FR[0, 2];  
  92.           rb = box1.extents[0] * FR[1, 1] + box1.extents[1] * FR[1, 0];  
  93.           t = Mathf.Abs(T[0] * R[2, 2] - T[2] * R[0, 2]);  
  94.           if (t > ra + rb) return false;  
  95.   
  96.           //L = A2 x B0  
  97.           ra = box0.extents[0] * FR[1, 0] + box0.extents[1] * FR[0, 0];  
  98.           rb = box1.extents[1] * FR[2, 2] + box1.extents[2] * FR[2, 1];  
  99.           t = Mathf.Abs(T[1] * R[0, 0] - T[0] * R[1, 0]);  
  100.           if (t > ra + rb) return false;  
  101.   
  102.           //L = A2 x B1  
  103.           ra = box0.extents[0] * FR[1, 1] + box0.extents[1] * FR[0, 1];  
  104.           rb = box1.extents[0] * FR[2, 2] + box1.extents[2] * FR[2, 0];  
  105.           t = Mathf.Abs(T[1] * R[0, 1] - T[0] * R[1, 1]);  
  106.           if (t > ra + rb) return false;  
  107.   
  108.           //L = A2 x B2  
  109.           ra = box0.extents[0] * FR[1, 2] + box0.extents[1] * FR[0, 2];  
  110.           rb = box1.extents[0] * FR[2, 1] + box1.extents[1] * FR[2, 0];  
  111.           t = Mathf.Abs(T[1] * R[0, 2] - T[0] * R[1, 2]);  
  112.           if (t > ra + rb) return false;  
  113.   
  114.           return true;  
  115.       }  

测试代码
[csharp] view plain copy
  1. public class BoxBoxTester : MonoBehaviour {  
  2.     public GameObject box;  
  3.     public GameObject box1;  
  4.     Box _box;  
  5.     Box _box1;  
  6.     // Use this for initialization  
  7.     void Start()  
  8.     {  
  9.         _box = new Box();  
  10.         _box1 = new Box();  
  11.     }  
  12.   
  13.     // Update is called once per frame  
  14.     void Update()  
  15.     {  
  16.         _box.center = box.transform.position;  
  17.         _box.rotation = box.transform.rotation;  
  18.         _box.extents = 0.5f * box.transform.localScale;  
  19.   
  20.         _box1.center = box1.transform.position;  
  21.         _box1.rotation = box1.transform.rotation;  
  22.         _box1.extents = 0.5f * box1.transform.localScale;  
  23.   
  24.         if (NIntersectTests.IntersectBoxBox(_box, _box1))  
  25.         {  
  26.             box.GetComponent<MeshRenderer>().materials[0].SetColor("_Color", new Color(1, 0, 0));  
  27.         }  
  28.         else  
  29.         {  
  30.             box.GetComponent<MeshRenderer>().materials[0].SetColor("_Color", new Color(1, 1, 1));  
  31.         }  
  32.     }  
  33. }  


运行结果




参考

Separating Axis Theorem for Oriented Bounding Boxes
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

obb

碰撞检测之OBB-OBB检测 的相关文章

  • 用Python画一个生日蛋糕并写上生日祝福对象及生日祝福语

    用Python画一个生日蛋糕并写上生日祝福对象及生日祝福语 画一个双层蛋糕并点上蜡烛 代码运行时间较长 请静待惊喜出现 代码运行截图 完整程序代码 干货主要有 200 多本 Python 电子书 和经典的书籍 应该有 Python标准库资料

  • 掌握 Ajax，第 7 部分: 在请求和响应中使用 XML

    偶尔使用 Ajax 的开发人员也会注意到 Ajax 中的 x 并意识到它代表 XML XML 是编程中最常用的数据格式之一 对于异步应用程序中的服务器响应能够带来切实的好处 在本文中 您将看到服务器如何在请求响应中发送 XML 现在如果不使

  • Java设计模式：装饰者模式（Decorator Pattern）

    装饰者模式 涉及的重要设计原则 类应该对扩展开放 对修改关闭 装饰者模式定义 装饰者模式动态地将责任附加到对象上 若要扩展功能 装饰者提供了比继承更有弹性的替代方案 UML类图 装饰者模式事例 咖啡店 咖啡种类 1 深焙咖啡 DarkRoa

  • Python中如何使用boolean类型的数据

    在写代码的过程中 遇到了定义boolean类型变量的问题 之前一直试图用java或者c定义布尔变量的方法 一直不奏效 经过一旦学习之后才明白 和java竟然只是大小写的问题 在python中将java中的true携程True 将false携

  • Educational Codeforces Round 149 (Rated for Div. 2)A~D

    Grasshopper on a Line 题意 给出n和k 求从0到n最少走几步 以及步长 要求步长不能整除k 思路 从n往下找到 k不等于0的数 输出该数和n 该数即可 如果n k 0 那就只需要一步 代码 gt File Name a

  • 探索Java8——默认方法

    文章目录 什么是默认方法 不断演进的API 初始版本API 第二版API 概述默认方法 什么是默认方法 在传统的Java程序中 实现接口的方式是通过Implements把接口中的每一个方法提供一个实现 或者从父类继承他的实现 然而 在实际开

  • redis搜索 - KEYS命令

    文章目录 KEYS命令 使用 使用场景 KEYS命令 KEYS命令用于搜索匹配某个模式的所有key 例如常见的keys 命令 会返回所有的键 Time complexity O N 使用 KEYS命令支持以下正则匹配模式 h llo mat

  • [STM32]详解单片机GPIO输入模式配置-上拉下拉与浮空

    前面说到单片机的GPIO主要输出模式主要有推挽模式和开漏模式 除了连接到片内外设的模拟输入模式和复用输入功能以外 这里再说一下通用输入模式配置 STM32单片机的通用输入模式主要有输入浮空 输入上拉与输入下拉 当配置成上拉模式 即GPIO

  • python rsa加密之后byte类型存储到数据库中_python3 rsa加密

    遇到了跟你一样的问题 此js封装的源码 如下 希望看到的大神解决了的话帮我一下 RSA a suite of routines for performing RSA public key computations in JavaScript

  • c语言字符串相关函数的分析

    c语言中 常见的字符串相关函数主要分为两类 1 与字符串长度无关的函数 如strcpy strcat strcmp 2 与字符串长度有关的函数 如strlen strncpy strncat strncmp strlen 用于求字符串的长度

  • 1130：找第一个只出现一次的字符（C C++）

    题目描述 给定一个只包含小写字母的字符串 请你找到第一个仅出现一次的字符 如果没有 输出no 输入 一个字符串 长度小于100000 输出 输出第一个仅出现一次的字符 若没有则输出no 输入样例 abcabd 输出样例 c 代码 inclu

  • 【Unity】Delegate, Event, UnityEvent, Action, UnityAction, Func 傻傻分不清

    Unity Delegate Event UnityEvent Action UnityAction Func 傻傻分不清 Delegate 委托 函数指针 一个简单的例子 一对一依赖 一个简单的例子 一对多依赖 所以话说 委托有啥用呢 事

随机推荐

  • LDAP简介及其使用

    LDAP简介 LDAP Lightweight Directory Access Protocol 的意思是 轻量级目录访问协议 是一个用于访问 目录服务器 Directory Servers 的协议 这里所谓的 目录 是指一种按照树状结构

  • java button中加入背景图片不显示

    emmmm 写一下关于在button中添加图片作为背景的经历 就 先记录下错误的地方 JLabel stat new JLabel new ImageIcon img left png 这里再left png的路径的开头少了个点 就一直都不

  • Centos7安装Nessus教程

    本文为学习笔记 仅限学习交流 不得利用 从事危害国家或人民安全 荣誉和利益等活动 请参阅 中华人民共和国网络安全法 Nessus安装包 链接 https pan baidu com s 1FJMu8WMZPSjoqQpes GCng 提取码

  • C++中#ifndef, #define, #endif的作用和使用的注意事项

    在C 语言编程中 我们经常会接触到头文件 比如说声明类 或者声明命名空间等 而每次在编写xxx h的头文件时 编程书上都会让我们在代码的前后加上如下的三句代码 ifndef XXX H define XXX H endif 其中 代表中间具

  • DDP入门

    DDP 即动态动态规划 可以用于解决一类带修改的DP问题 我们从一个比较简单的东西入手 最大子段和 带修改的最大子段和其实是常规问题了 经典的解决方法是用线段树维护从左 右开始的最大子段和和区间最大子段和 然后进行合并 现在我们换一种方法来

  • 软件测试人员必备的60个测试工具清单，果断收藏了！

    据统计 中国软件外包市场的潜力和机会已远远超过软件王国印度 不过由于软件人才的严重不足致使我国软件发展遭遇 瓶颈 国家为了大力培养软件人才 不断采取积极有效的措施 我国对软件测试人才的需求数量还将持续增加 因此软件测试工程师也就成为了IT职

  • golang ---JSON-ITERATOR 使用

    jsoniter json iterator 是一款快且灵活的 JSON 解析器 Jsoniter 是最快的 JSON 解析器 它最多能比普通的解析器快 10 倍之多 独特的 iterator api 能够直接遍历 JSON 极致性能 0

  • 《图像分割Unet网络分析及其Pytorch版本代码实现》

    最近两个月在做学习图像分割方面的学习 踩了无数的坑 也学到了很多的东西 想了想还是趁着国庆节有时间来做个总结 以后有这方面需要可以来看看 神经网络被大规模的应用到计算机视觉中的分类任务中 说到神经网络的分类任务这里不得不提到CNN 卷积神经

  • 低代码，虽然有点毒瘤，但管用就好

    最近看到不少低门槛开发软件应用的新闻 30 分钟搭一款核酸检测登记应用 2 小时紧急上线抗疫求助应用 00 后低代码开发者毕业月薪过万 等等 近期 广西防城港市出现疫情 全市展开一轮大规模核酸检测 柳钢工人彭期文在钉钉上仅用 30 分钟就通

  • Sqli-labs靶场详细攻略Less 29-33

    Less 29 33 Less 29 GET Error based IMPIDENCE MISMATCH Having a WAF infront of web application 这一关在web应用前有一个waf 在关卡列表界面直接

  • Linux系统服务之inetd

    inetd进程介绍 inetd程序是一个Linux守护进程 您可能已经知道守护进程是一些特殊的程序 它们在被启动之后 自愿放弃对调用自己终端的控制权 守护进程与系统其余部分的接口只有依靠进程间通信 Interprocess Communic

  • sourcegraph下载安装介绍

    https chrome google com webstore detail sourcegraph dgjhfomjieaadpoljlnidmbgkdffpack related 1 打开chrome 打开以上网页 翻墙 页面右上角点

  • 解决问题：error: ‘QStringLiteral’ was not declared in this scope

    QT编译出现如下问题 error QStringLiteral was not declared in this scope resmodel gt setHorizontalHeaderLabels QStringList lt

  • CUDA 程序运行时 CPU 100%的一个解决方法

    CUDA 程序运行时CPU 100 的问题有点让人头痛 在实验过程中调用了kernel函数后 再调用cudaMemcpyAsync 但发现在还有会到block在这个所谓的async api strace 跟了一下 发现99 999 都是 c

  • Python中的None

    一 None None是python中的一个特殊的常量 表示一个空的对象 数据为空并不代表是空对象 例如空列表 等都不是None None有自己的数据类型NontType 你可以将None赋值给任意对象 但是不能创建一个NoneType对象

  • 在微信小程序上使用 mqtt

    大家知道 微信小程序的websocket API他们自己定制了 这样一些运行在浏览器里的库默认是运行不了的 比如mqttjs这个库 https github com mqttjs MQTT js 由于搜狗公司兄弟团队的一个微信小程序要跑mq

  • 强化学习实践三 ：编写通用的格子世界环境类

    gym里内置了许多好玩经典的环境用于训练一个更加智能的个体 不过这些环境类绝大多数不能用来实践前五讲的视频内容 主要是由于这些环境类的观测空间的某个维度是连续变量而不是离散变量 这是前五讲内容还未涉及到的知识 为了配合解释David Sil

  • CDH6 开启kerberos Hive的Sentry 用户权限分配

    Apache Sentry是Cloudera公司发布的一个Hadoop开源组件 截止目前还是Apache的孵化项目 它提供了细粒度级 基于角色的授权以及多租户的管理模式 Sentry当前可以和Hive Hcatalog Apache Sol

  • linux的/proc /sys目录的区别

    内核中有三个常用的伪文件系统 procfs debugfs和sysfs procfs The proc filesystem is a pseudo filesystem which provides an interface to ker

  • 碰撞检测之OBB-OBB检测

    碰撞检测之OBB OBB检测 2016年03月07日 02 20 14 阅读数 3732 2D情况 首先回顾一下SAP 两个凸包多边形 当且仅当存在一条线 这两个多边形在这条线上的投影不相交 则这两个多边形也不相交 这条线称为Separat

热门标签