碰撞检测之OBB-OBB检测

news/2025/3/14 19:21:43/
碰撞检测之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

http://www.ppmy.cn/news/897345.html

相关文章

MD5碰撞

MD5碰撞

MD5简介 HASH函数&#xff0c;又称杂凑函数&#xff0c;是在信息安全领域有广泛和重要应用的密码算法&#xff0c;它有一种类似于指纹的应用。在网络安全协议中&#xff0c;杂凑函数用来处理电子签名&#xff0c;将冗长的签名文件压缩为一段独特的数字信息&#xff0c;像指纹鉴…
阅读更多...
哈希碰撞与生日攻击

哈希碰撞与生日攻击

一、哈希碰撞是什么&#xff1f; 所谓哈希&#xff08;hash&#xff09;&#xff0c;就是将不同的输入映射成独一无二的、固定长度的值&#xff08;又称"哈希值"&#xff09;。它是最常见的软件运算之一。 如果不同的输入得到了同一个哈希值&#xff0c;就发生了&q…
阅读更多...
Linux 离线安装软件

Linux 离线安装软件

这里写目录标题 0.注意1.防火墙操作2.安装jdk1.上传jdk安装包2.安装3.配置环境变量 3.安装redis1.上传tar包2.安装命令3.项目连接时报错4.问题一保存信息解决 4.安装rabbitMq1.查看erlang与mq对应版本2.下载软件2.1下载erlang2.2下载rabbitMq 3.将文件拖放到linux4.安装5.开放端…
阅读更多...
数商云B2B供应链协同系统解决方案：搭建在线采购交易、数据网络化的协同办公系统

数商云B2B供应链协同系统解决方案：搭建在线采购交易、数据网络化的协同办公系统

“供应链协同”是指供应链的各成员企业在树立“合作共赢”意识的前提下&#xff0c;以信息的自由交流&#xff0c;知识创新成果的共享&#xff0c;相互信任、协同决策&#xff0c;无缝链接的供应链协同系统流程和共同的战略目标为基础&#xff0c;各节点企业通过协议或联合组织…
阅读更多...
企业采购管理系统|采购协同平台解决方案

企业采购管理系统|采购协同平台解决方案

在经济全球和客户需求的多元化背景下&#xff0c;市场竞争日益激烈&#xff0c;企业仅依靠自身资源进行自我调整已经不足以满足市场变化的需要&#xff0c;采购成本高&#xff0c;效率低&#xff0c;管理难&#xff0c;这是困扰着众多企业的难题。为了改进采购上存在的问题&…
阅读更多...
包装行业数智化采购管理系统提升企业采购效率，构筑智慧采购新生态

包装行业数智化采购管理系统提升企业采购效率，构筑智慧采购新生态

包装行业作为我国制造体系的重要组成部分&#xff0c;2020年市场规模已步入万亿量级&#xff0c;机会与挑战并存。然而&#xff0c;随着行业壮大&#xff0c;我国传统包装企业在采购环节中的发展痛点也逐渐凸显&#xff0c;如何借助新一代信息技术实现高效的采购流程管理&#…
阅读更多...
采购部门如何通过协同办公软件飞项管控采购流程

采购部门如何通过协同办公软件飞项管控采购流程

做过采购的同事都知道&#xff0c;采购工作是一个需要确保物资质量和注重采购效率的工作&#xff0c;只有把控好采购质量和规范好采购流程后&#xff0c;才能确保采购工作万无一失&#xff0c;搭起公司后勤坚实的后盾。 今天来看看协同办公软件飞项如何协助采购部门做好物资采…
阅读更多...
工程建材企业必看：应用集中采购协同系统，实现降本增效，提升企业效益！

工程建材企业必看：应用集中采购协同系统，实现降本增效，提升企业效益！

建材是土木工程和建筑工程中使用的材料&#xff0c;可分为结构材料、功能材料和某些专用材料。近年来&#xff0c;受益于科技的进步和建筑水平的提升&#xff0c;我国工程建材行业获得了蓬勃发展&#xff0c;成为拉动国民经济发展的重要产业。 当前&#xff0c;由于受到建筑材…
阅读更多...
最新文章

Copyright @ 2022~2023