Ray-AABB交叉检测算法

  最近在解决三维问题时,需要判断线段是否与立方体交叉,这个问题可以引申为:射线是否穿过立方体AABB。   在3D游戏开发中碰撞检测普遍采用的算法是轴对齐矩形边界框(Axially Aligned Bounding Box, AABB)包装盒方法,其基本思想是用一个立方体或者球体完全包裹住3D物体对象,然后根据包装盒的距离、位置等相关信息来计算是否发生碰撞。

slab的碰撞检测算法

  本文接下来主要讨论射线与AABB的关系,主要对box2d碰撞检测使用的slab的碰撞检测算法(Slabs method)进行介绍,然后使用python语言实现slab碰撞检测方法,该方法可以用于3D物体拾取等应用场景。   Slab英文翻译是“平板”,本文是指两个平行平面/直线之间的空间。在2D空间中slab可以理解为平行于坐标轴的两条直线间的区域,3D空间中为平行于xy平面(或者yz面,xz面)的两个平面之间的区域。由此,我们可以把3D空间中的AABB盒子看做是由AABB的3组平行面形成的3个方向的slab的交集。   另外,引入候选面的概念:在3D空间中,我们先确定正对着射线的三个面,也就是说,我们可以通过某种方式将AABB相对于射线Ray的背面给忽略掉,从而确定三个候选的面。这三个候选的面,就是有可能和射线Ray发生交叉的最近的面。

  根据这个定义,我们可以得到以下三个结论:

  1. 性质一:如果一个点在AABB中,那么这个点必定同时在这3个slab中。
  2. 性质二:如果一条射线和AABB相交,那么这条射线和3个slab的相交部分必定有重合部分。
  3. 性质三:当射线与这三个候选面中的一个发生交叉之后,射线Ray的原点到这个面的距离要比到其他几个面的距离要长。

  性质一和性质二比较容易理解,如果射线和3个slab的相交线段没有重合,那么这些线段就不可能同时存在于3个slab中,也就不可能在AABB盒子中。   为了方便理解性质三,使用2D图形来讲解:

  在上图中,我们的射线在右下角,向左上角发射,射线经过一个A点,其中候选面是y1面和x2面。   根据上述性质,可以看到A点同时在2D空间中的2个slab中;此外,根据性质二,因为射线与平面相交,那么这条射线与slab的相交部分必有重合部分,因为A点在射线上,且在平面中,那么可以得到max(t1,t2)<=tA<=min(t3,t4);根据性质三:当交叉后,可以看出t2>t1。   同理,我们可以把上述的验证过程推广到三维中。在三维空间中,假设射线到3个候选面的距离分别是t1、t2、t3,到候选面对应的面的距离分别为t4、t5、t6,那么根据性质二,射线与AABB碰撞的条件是max(t1,t2,t3)<=min(t4,t5,t6);如果发生交叉,那么根据性质三,射线到最近的交叉面的距离是是max(t1,t2,t3)。

  在上述性质基础上,确定射线与AABB是否交叉需要三步骤:

  1. 如何确定候选面:只要将平面方程带入射线Ray的方程,求出这两个平面的t值,然后t值较小的那个自然先与射线交叉,那么就表示它是一个候选面。射线可以用参数方程表示为R(t) = P0 + t·d, (其中P0为射线起点,d为射线的方向向量)
  2. 如何确定候选面的方程。平面由隐式定义方程X·n=D, (其中X为平面上的点,n为平面法向量,D为原点到平面的距离)给出。由于AABB的slab平面都分别和两个坐标轴平行,它的面的法线总是有两个分量是0,而另外一个分量总是为1,所以我们一致使用某个轴分量为1的法线。如果上面的方程表示的是AABB盒的左面的面,那么公式中的n表示的就是(1,0,0),但上面的公式表示的是AABB盒的右边的面的时候,n表示的值依然是(1,0,0)。
  3. 如何对交叉点是否在AABB盒上进行判断。根据性质二判断,即射线与AABB碰撞的条件是max(t1,t2,t3)<=min(t4,t5,t6)。

碰撞检测算法公式推导

  求取t值的公式推导如下:


碰撞检测算法Python源代码

最后,附上我的Python代码片段,代码实时更新于GitHub

# Ray-AABB方法 相交返回True,否则返回False
# TDPoint = collections.namedtuple("TDPoint", ["x", "y","z"])
# AABB有最大和最小点组成,数据结构为{max=TDPoint,min=TDPoint}
# Ray由原点和方向组成,其中方向矢量为1,数据结构为{TDPoint,TDPoint}
def intersectWithAABB(AABB,Ray):
    tmin=0
    tmax=10000

    # <editor-fold desc="平行于x轴">
    if(math.fabs(Ray[1].x)<0.000001):
        if (Ray[0].x<AABB.min.x) or (Ray[0].x>AABB.max.x):
            return  False
    else:
        ood=1.0/Ray[1].x
        t1=(AABB.min.x-Ray[0].x)*ood
        t2=(AABB.max.x-Ray[0].x)*ood
        # t1做候选平面,t2做远平面
        if (t1>t2):
            temp=t1
            t1=t2
            t2=temp
        if t1>tmin:
            tmin=t1
        if t2<tmax:
            tmax=t2
        if tmin>tmax:
            return False
    # </editor-fold>

    # <editor-fold desc="平行于y轴">
    if(math.fabs(Ray[1].y)<0.000001):
        if (Ray[0].y<AABB.min.y) or (Ray[0].y>AABB.max.y):
            return  False
    else:
        ood=1.0/Ray[1].y
        t1=(AABB.min.y-Ray[0].y)*ood
        t2=(AABB.max.y-Ray[0].y)*ood
        # t1做候选平面,t2做远平面
        if (t1>t2):
            temp=t1
            t1=t2
            t2=temp
        if t1>tmin:
            tmin=t1
        if t2<tmax:
            tmax=t2
        if tmin>tmax:
            return False
    # </editor-fold>

    # <editor-fold desc="平行于z轴">
    if(math.fabs(Ray[1].z)<0.000001):
        if (Ray[0].z<AABB.min.z) or (Ray[0].z>AABB.max.z):
            return  False
    else:
        ood=1.0/Ray[1].z
        t1=(AABB.min.z-Ray[0].z)*ood
        t2=(AABB.max.z-Ray[0].z)*ood
        # t1做候选平面,t2做远平面
        if (t1>t2):
            temp=t1
            t1=t2
            t2=temp
        if t1>tmin:
            tmin=t1
        if t2<tmax:
            tmax=t2
        if tmin>tmax:
            return False
    # </editor-fold>
    return True

from 3D空间中射线与轴向包围盒AABB的交叉检测算法 from Box2D 射线和AABB的碰撞检测

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏专知

Facebook AI发布新版本FairSeq序列到序列(Seq2Seq)学习工具,可生成故事与快速推断

【导读】Facebook AI Research发布(PyTorch)序列到序列学习工具集fairseq新版本:实现“Scaling Neural Machin...

7245
来自专栏机器学习算法与Python学习

教程 | 一步一步,看图理解长短期记忆网络与门控循环网络

大家好,欢迎来到 LSTM 和 GRU 的图解指南。在本文中,Michael 将从 LSTM 和 GRU 的背后的原理开始,然后解释令 LSTM 和 GRU 具...

1153
来自专栏AI研习社

如何用 TensorFlow 实现基于 LSTM 的文本分类(附源码)

引言 学习一段时间的tensor flow之后,想找个项目试试手,然后想起了之前在看Theano教程中的一个文本分类的实例,这个星期就用tensorflow...

6627
来自专栏CSDN技术头条

LSTM实现详解

前言 在很长一段时间里,我一直忙于寻找一个实现LSTM网络的好教程。它们似乎很复杂,而且在此之前我从来没有使用它们做过任何东西。在互联网上快速搜索并没有什么帮助...

2319
来自专栏机器之心

谷歌终于开源BERT代码:3 亿参数量,机器之心全面解读

今日,谷歌终于放出官方代码和预训练模型,包括 BERT 模型的 TensorFlow 实现、BERT-Base 和 BERT-Large 预训练模型和论文中重要...

1792
来自专栏机器之心

教程 | 一步一步,看图理解长短期记忆网络与门控循环网络

循环神经网络(RNN)很大程度上会受到短期记忆的影响,如果序列足够长,它们将很难将信息从早期时间步传递到靠后的时间步。因此,如果你试图处理一段文字来做预测,RN...

1183
来自专栏IT派

教程 | 用TensorFlow Estimator实现文本分类

本文选自介绍 TensorFlow 的 Datasets 和 Estimators 模块系列博文的第四部分。读者无需阅读所有之前的内容,如果想重温某些概念,可以...

2713
来自专栏PPV课数据科学社区

百度校园招聘数据挖掘工程师面试题集锦(2013)

一、简答题(30分) 1、简述数据库操作的步骤(10分) 步骤:建立数据库连接、打开数据库连接、建立数据库命令、运行数据库命令、保存数据库命令、关闭数据库连接。...

3935
来自专栏人工智能

C+实现神经网络之六—实战手写数字识别

之前的五篇博客讲述的内容应该覆盖了如何编写神经网络的大部分内容,在经过之前的一系列努力之后,终于可以开始实战了。试试写出来的神经网络怎么样吧。 数据准备 有人说...

2499
来自专栏大数据文摘

安利一则深度学习新手神器:不用部署深度学习环境了!也不用上传数据集了!

1544

扫码关注云+社区

领取腾讯云代金券