碰撞检测方法、装置、设备及存储介质

摘要

本申请一种碰撞检测方法，包括：获取场景数据，根据所述场景数据中的各实体数据建立碰撞检测模型；由所建立的两个以上的碰撞检测模型中提取出当前需要进行碰撞检测的第一碰撞模型和第二碰撞模型；由所述第一碰撞模型的首层节点和所述第二碰撞模型的首层节点开始，逐层对所述第一碰撞模型和所述第二碰撞模型中处于同一层节点的包围盒之间的距离进行计算，并根据计算得到的距离结果得到相应的碰撞检测结果。其通过对场景数据中的各实体建立相应的碰撞检测模型，所建立的碰撞检测模型均采用二叉树的数据结构，同时各碰撞检测模型中每层节点所包含的包围盒的数据均量化为整型数据，从而在保证精度的同时降低了内存占用量。

权利要求

1.一种碰撞检测方法，其特征在于，包括：获取场景数据，根据所述场景数据中的各实体数据建立碰撞检测模型；

其中，所述碰撞检测模型的个数为两个以上，两个以上的所述碰撞检测模型与所述场景数据中的实体相对应；且

所述碰撞检测模型的数据结构为二叉树结构；各所述碰撞检测模型中每层节点中的包围盒中的数据均为整型数据；

由所建立的两个以上的碰撞检测模型中提取出当前需要进行碰撞检测的第一碰撞模型和第二碰撞模型；

由所述第一碰撞模型的首层节点和所述第二碰撞模型的首层节点开始，逐层对所述第一碰撞模型和所述第二碰撞模型中处于同一层节点的包围盒之间的距离进行计算，并根据计算得到的距离结果得到相应的碰撞检测结果。

2.根据权利要求1所述的方法，其特征在于，根据所述场景数据中的各实体数据建立碰撞检测模型，包括：

由所述场景数据中读取各实体数据中的点数据和三角面索引；

基于所述点数据和所述三角面索引，建立各实体所对应的原始碰撞树；

对所述原始碰撞树进行优化，得到所述碰撞检测模型；

其中，对所述原始碰撞树进行优化，包括节点收敛和数据量化中的至少一种：所述节点收敛，包括：

收敛所述原始碰撞树中的叶节点，以叶节点包含的三角面索引替代在根节点中的指针，并将所述原始碰撞树中的当前叶节点所包含的三角形收录到当前节点的上一层节点中；

所述数据量化，包括：

获取所述原始碰撞树中各层节点的包围盒的数据，通过量化方式将所述原始碰撞树中各层节点的包围盒的数据由浮点型数据转换为整型数据。

3.根据权利要求2所述的方法，其特征在于，基于所述点数据和所述三角面索引，建立各实体所对应的原始碰撞树，包括：基于所述点数据和所述三角面索引，建立各所述实体的三维模型；

对各所述三维模型的包围盒进行至少一次空间分割，得到多个包围盒，并根据得到的多个所述包围盒建立所述原始碰撞树；

其中，对各所述三维模型的包围盒进行至少一次空间分割，包括：获取所述三维模型的包围盒在三维坐标系中的最长轴，按照所述最长轴方向对所述三维模型的包围盒进行初级分割，得到多个一级包围盒；

根据各所述一级包围盒内的三角形个数以及预设个数的大小关系，基于各所述一级包围盒进行逐级分割，直至分割后得到的包围盒内的三角形个数小于或等于预设个数为止；

其中，在按照所述最长轴方向不能对所述三维模型的包围盒进行初级分割时，按照次长轴方向对所述三维模型的包围盒进行初级分割；

在对所述三维模型的包围盒进行分割时，分割位置通过遍历所述包围盒内所有三角形，获取沿分割方向上的极大值和极小值并对所述极大值和所述极小值进行平均值计算的方式得到；

所述预设个数的取值为2。

4.根据权利要求1至3任一项所述的方法，其特征在于，根据计算得到的距离结果得到相应的碰撞检测结果，包括：

在所述距离结果均大于预设数值时，确定所述碰撞检测结果为未碰撞；

在所述距离结果中存在小于或等于所述预设数值的结果时，获取所述第一碰撞模型中当前节点所包含的第一包围盒和所述第二碰撞模型中当前节点所包含的第二包围盒，并基于所述第一包围盒内的三角形和所述第二包围盒内的三角形进行三角形碰撞检测，得到相应的碰撞检测结果；

其中，所述当前节点为小于或等于所述预设数值的距离结果所对应的节点；所述预设数值的取值为2。

5.根据权利要求4所述的方法，其特征在于，基于所述第一包围盒内的三角形和所述第二包围盒内的三角形进行三角形碰撞检测，包括：依次由所述第一包围盒内选取第一三角形，并由所述第二包围盒内选取第二三角形；

其中，所述第一三角形为所述第一包围盒内的所有三角形中的任意一个，所述第二三角形为所述第二包围盒内的所有三角形中的任意一个；

运用离合轴定理对当前选取出的所述第一三角形和所述第二三角形进行三角形碰撞检测。

6.根据权利要求4所述的方法，其特征在于，在所述距离结果中存在小于或等于所述预设数值时，还包括：

确定所述距离结果所对应的当前节点是否为叶节点；

在所述当前节点为叶节点时，获取所述第一碰撞模型中当前节点所包含的第一包围盒和所述第二碰撞模型中当前节点所包含的第二包围盒，并基于所述第一包围盒内的三角形和所述第二包围盒内的三角形进行三角形碰撞检测，得到相应的碰撞检测结果；

在所述当前节点为根节点时，对所述第一碰撞模型和所述第二碰撞模型中当前节点的下一层节点包含的包围盒之间的距离进行计算。

7.一种碰撞检测装置，其特征在于，包括模型建立模块、模型提取模块和碰撞检测模块；

所述模型建立模块，被配置为获取场景数据，根据所述场景数据中的各实体数据建立碰撞检测模型；

其中，所述碰撞检测模型与所述场景数据中的实体相对应；且所述碰撞检测模型的数据结构为二叉树结构；各所述碰撞检测模型中每层节点中的包围盒中的数据均为整型数据；

所述模型提取模块，被配置为由所建立的碰撞检测模型中提取第一碰撞模型和第二碰撞模型；

所述碰撞检测模块，被配置为由所述第一碰撞模型的首层节点和所述第二碰撞模型的首层节点开始，逐层对所述第一碰撞模型和所述第二碰撞模型中处于同一层节点的包围盒之间的距离进行计算，并根据计算得到的距离结果得到相应的碰撞检测结果。

8.根据权利要求7所述的装置，其特征在于，所述模型建立模块包括数据读取子模块、原始树建立子模块和原始树优化子模块；

所述数据读取子模块，被配置为由所述场景数据中读取各实体数据中的点数据和三角面索引；

所述原始树建立子模块，被配置为基于所述点数据和所述三角面索引，建立各实体所对应的原始碰撞树；

所述原始树优化子模块，被配置为对所述原始碰撞树进行优化，得到所述碰撞检测模型；

其中，所述原始树优化子模块包括节点收敛单元和数据量化单元；

所述节点收敛单元，被配置为收敛所述原始碰撞树中的叶节点，以叶节点包含的三角面索引替代在根节点中的指针，并将所述原始碰撞树中的当前叶节点所包含的三角形收录到当前节点的上一层节点中；

所述数据量化单元，被配置为获取所述原始碰撞树中各层节点的包围盒的数据，通过量化方式将所述原始碰撞树中各层节点的包围盒的数据由浮点型数据转换为整型数据。

9.一种碰撞检测设备，其特征在于，包括：处理器；

用于存储处理器可执行指令的存储器；

其中，所述处理器被配置为执行所述可执行指令时实现权利要求1至6中任意一项所述的方法。

10.一种非易失性计算机可读存储介质，其上存储有计算机程序指令，其特征在于，所述计算机程序指令被处理器执行时实现权利要求1至6中任意一项所述的方法。

说明书

碰撞检测方法、装置、设备及存储介质

技术领域

[0001] 本公开涉及3D建模技术领域，尤其涉及一种碰撞检测方法、装置、设备及存储介质。

背景技术

[0002] 碰撞检测在所有涉及到3D建模的游戏、科研和工作领域都有着无可避免的广泛应用。关于碰撞检测的建模也是各式各样，球形、胶囊体、轴对称包围盒、定向包围盒等。但是
目前大多数的碰撞检测引擎在精度达到需求的算法时，往往会导致内存占比较大。

发明内容

[0003] 有鉴于此，本公开提出了一种碰撞检测方法，可以有效减少内存占用量。

[0004] 根据本公开的一方面，提供了一种碰撞检测方法，包括：

[0005] 获取场景数据，根据所述场景数据中的各实体数据建立碰撞检测模型；

[0006] 其中，所述碰撞检测模型的个数为两个以上，两个以上的所述碰撞检测模型与所述场景数据中的实体相对应；且

[0007] 所述碰撞检测模型的数据结构为二叉树结构；各所述碰撞检测模型中每层节点中的包围盒中的数据均为整型数据；

[0008] 由所建立的两个以上的碰撞检测模型中提取出当前需要进行碰撞检测的第一碰撞模型和第二碰撞模型；

[0009] 由所述第一碰撞模型的首层节点和所述第二碰撞模型的首层节点开始，逐层对所述第一碰撞模型和所述第二碰撞模型中处于同一层节点的包围盒之间的距离进行计算，并
根据计算得到的距离结果得到相应的碰撞检测结果。

[0010] 在一种可能的实现方式中，根据所述场景数据中的各实体数据建立碰撞检测模型，包括：

[0011] 由所述场景数据中读取各实体数据中的点数据和三角面索引；

[0012] 基于所述点数据和所述三角面索引，建立各实体所对应的原始碰撞树；

[0013] 对所述原始碰撞树进行优化，得到所述碰撞检测模型；

[0014] 其中，对所述原始碰撞树进行优化，包括节点收敛和数据量化中的至少一种：

[0015] 所述节点收敛，包括：

[0016] 收敛所述原始碰撞树中的叶节点，以叶节点包含的三角面索引替代在根节点中的指针，并将所述原始碰撞树中的当前叶节点所包含的三角形收录到当前节点的上一层节点
中；

[0017] 所述数据量化，包括：

[0018] 获取所述原始碰撞树中各层节点的包围盒的数据，通过量化方式将所述原始碰撞树中各层节点的包围盒的数据由浮点型数据转换为整型数据。

[0019] 在一种可能的实现方式中，基于所述点数据和所述三角面索引，建立各实体所对应的原始碰撞树，包括：

[0020] 基于所述点数据和所述三角面索引，建立各所述实体的三维模型；

[0021] 对各所述三维模型的包围盒进行至少一次空间分割，得到多个包围盒，并根据得到的多个所述包围盒建立所述原始碰撞树；

[0022] 其中，对各所述三维模型的包围盒进行至少一次空间分割，包括：

[0023] 获取所述三维模型的包围盒在三维坐标系中的最长轴，按照所述最长轴方向对所述三维模型的包围盒进行初级分割，得到多个一级包围盒；

[0024] 根据各所述一级包围盒内的三角形个数以及预设个数的大小关系，基于各所述一级包围盒进行逐级分割，直至分割后得到的包围盒内的三角形个数小于或等于预设个数为
止；

[0025] 其中，在按照所述最长轴方向不能对所述三维模型的包围盒进行初级分割时，按照次长轴方向对所述三维模型的包围盒进行初级分割；

[0026] 在对所述三维模型的包围盒进行分割时，分割位置通过遍历所述包围盒内所有三角形，获取沿分割方向上的极大值和极小值并对所述极大值和所述极小值进行平均值计算
的方式得到；

[0027] 所述预设个数的取值为2。

[0028] 在一种可能的实现方式中，根据计算得到的距离结果得到相应的碰撞检测结果，包括：

[0029] 在所述距离结果均大于预设数值时，确定所述碰撞检测结果为未碰撞；

[0030] 在所述距离结果中存在小于或等于所述预设数值的结果时，获取所述第一碰撞模型中当前节点所包含的第一包围盒和所述第二碰撞模型中当前节点所包含的第二包围盒，
并基于所述第一包围盒内的三角形和所述第二包围盒内的三角形进行三角形碰撞检测，得
到相应的碰撞检测结果；

[0031] 其中，所述当前节点为小于或等于所述预设数值的距离结果所对应的节点；所述预设数值的取值为2。

[0032] 在一种可能的实现方式中，基于所述第一包围盒内的三角形和所述第二包围盒内的三角形进行三角形碰撞检测，包括：

[0033] 依次由所述第一包围盒内选取第一三角形，并由所述第二包围盒内选取第二三角形；其中，所述第一三角形为所述第一包围盒内的所有三角形中的任意一个，所述第二三角
形为所述第二包围盒内的所有三角形中的任意一个；

[0034] 运用离合轴定理对当前选取出的所述第一三角形和所述第二三角形进行三角形碰撞检测。

[0035] 在一种可能的实现方式中，在所述距离结果中存在小于或等于所述预设数值时，还包括：

[0036] 确定所述距离结果所对应的当前节点是否为叶节点；

[0037] 在所述当前节点为叶节点时，获取所述第一碰撞模型中当前节点所包含的第一包围盒和所述第二碰撞模型中当前节点所包含的第二包围盒，并基于所述第一包围盒内的三
角形和所述第二包围盒内的三角形进行三角形碰撞检测，得到相应的碰撞检测结果；

[0038] 在所述当前节点为根节点时，对所述第一碰撞模型和所述第二碰撞模型中当前节点的下一层节点包含的包围盒之间的距离进行计算。

[0039] 根据本公开的另一方面安，还提供了一种碰撞检测装置，包括模型建立模块、模型提取模块和碰撞检测模块；

[0040] 所述模型建立模块，被配置为获取场景数据，根据所述场景数据中的各实体数据建立碰撞检测模型；

[0041] 其中，所述碰撞检测模型与所述场景数据中的实体相对应；且

[0042] 所述碰撞检测模型的数据结构为二叉树结构；各所述碰撞检测模型中每层节点中的包围盒中的数据均为整型数据；

[0043] 所述模型提取模块，被配置为由所建立的碰撞检测模型中提取第一碰撞模型和第二碰撞模型；

[0044] 所述碰撞检测模块，被配置为由所述第一碰撞模型的首层节点和所述第二碰撞模型的首层节点开始，逐层对所述第一碰撞模型和所述第二碰撞模型中处于同一层节点的包
围盒之间的距离进行计算，并根据计算得到的距离结果得到相应的碰撞检测结果。

[0045] 在一种可能的实现方式中，所述模型建立模块包括数据读取子模块、原始树建立子模块和原始树优化子模块；

[0046] 所述数据读取子模块，被配置为由所述场景数据中读取各实体数据中的点数据和三角面索引；

[0047] 所述原始树建立子模块，被配置为基于所述点数据和所述三角面索引，建立各实体所对应的原始碰撞树；

[0048] 所述原始树优化子模块，被配置为对所述原始碰撞树进行优化，得到所述碰撞检测模型；

[0049] 其中，所述原始树优化子模块包括节点收敛单元和数据量化单元；

[0050] 所述节点收敛单元，被配置为收敛所述原始碰撞树中的叶节点，以叶节点包含的三角面索引替代在根节点中的指针，并将所述原始碰撞树中的当前叶节点所包含的三角形
收录到当前节点的上一层节点中；

[0051] 所述数据量化单元，被配置为获取所述原始碰撞树中各层节点的包围盒的数据，通过量化方式将所述原始碰撞树中各层节点的包围盒的数据由浮点型数据转换为整型数
据。

[0052] 根据本公开的一方面，还提供了一种碰撞检测设备，包括：

[0053] 处理器；

[0054] 用于存储处理器可执行指令的存储器；

[0055] 其中，所述处理器被配置为执行所述可执行指令时实现前面任一所述的方法。

[0056] 根据本公开的另一方面，还提供了一种非易失性计算机可读存储介质，其上存储有计算机程序指令，所述计算机程序指令被处理器执行时前面任一所述的方法。

[0057] 本申请的碰撞检测方法，通过对场景数据中的各实体建立相应的碰撞检测模型，所建立的碰撞检测模型均采用二叉树的数据结构，同时各碰撞检测模型中每层节点所包含
的包围盒的数据均量化为整型数据，从而在保证精度的同时降低了内存占用量。并且，还通
过采用计算两个碰撞检测模型在同一层节点所包含的包围盒之间的距离来实现对两个碰
撞检测模型的碰撞检测，检测方式简便，易于实现。

[0058] 根据下面参考附图对示例性实施例的详细说明，本公开的其它特征及方面将变得清楚。

附图说明

[0059] 包含在说明书中并且构成说明书的一部分的附图与说明书一起示出了本公开的示例性实施例、特征和方面，并且用于解释本公开的原理。

[0060] 图1示出本申请的碰撞检测方法的一实施例的流程图；

[0061] 图2示出本申请的碰撞检测方法中所建立的一个实体的原始碰撞树的数据结构图；

[0062] 图3示出本申请的碰撞检测方法中所建立的第一碰撞模型的部分数据结构图；

[0063] 图4示出本申请的碰撞检测方法中所建立的第二碰撞模型的部分数据结构图；

[0064] 图5示出本申请的碰撞检测装置的结构框图；

[0065] 图6示出本申请的碰撞检测设备的结构框图。

具体实施方式

[0066] 以下将参考附图详细说明本公开的各种示例性实施例、特征和方面。附图中相同的附图标记表示功能相同或相似的元件。尽管在附图中示出了实施例的各种方面，但是除
非特别指出，不必按比例绘制附图。

[0067] 在这里专用的词“示例性”意为“用作例子、实施例或说明性”。这里作为“示例性”所说明的任何实施例不必解释为优于或好于其它实施例。

[0068] 另外，为了更好的说明本公开，在下文的具体实施方式中给出了众多的具体细节。本领域技术人员应当理解，没有某些具体细节，本公开同样可以实施。在一些实例中，对于
本领域技术人员熟知的方法、手段、元件和电路未作详细描述，以便于凸显本公开的主旨。

[0069] 图1示出根据本公开一实施例的碰撞检测方法的流程图。如图1所示，该方法包括：步骤S100，获取场景数据，根据场景数据中的各实体数据建立碰撞检测模型。其中，需要指
出的是，参阅图2，在本申请方法中，对于场景数据中的每一个实体所建立的碰撞检测模型
的数据结构均为二叉树结构。并且，对于一个场景数据可建立两个以上的碰撞检测模型，两
个以上的碰撞检测模型与场景数据中的多个实体一一对应。即，场景数据中包含多少实体，
对应就会建立多少个碰撞检测模型。同时，在本申请方法中，各碰撞检测模型中每层节点所
包含的包围盒的数据均为整型数据。

[0070] 步骤S200，由所建立的两个以上的碰撞检测模型中提取出当前需要进行碰撞检测的第一碰撞模型和第二碰撞模型。此处，本领域技术人员可以理解的是，第一碰撞模型和第
二碰撞模型均为所建立的两个以上的碰撞检测模型中的任意一个，并且第一碰撞模型与第
二碰撞模型分别对应不同的实体。同时，还需要指出的是，由两个以上的碰撞检测模型中提
取出第一碰撞模型和第二碰撞模型时，可以按照一定的顺序依次进行提取，也可以通过两
两组合的方式进行提取，此处不进行具体限定。

[0071] 步骤S300，由第一碰撞模型的首层节点和第二碰撞模型的首层节点开始，逐层对第一碰撞模型和第二碰撞模型中处于同一层节点的包围盒之间的距离进行计算，并根据计
算得到的距离结果得到相应的碰撞检测结果。即，通过对提取出的第一碰撞模型和第二碰
撞模型中，处于同一层节点所包含的包围盒之间的距离进行计算来实现对第一碰撞模型所
对应的实体与第二碰撞模型所对应的实体的碰撞检测。

[0072] 由此，本申请的碰撞检测方法，通过对场景数据中的各实体建立相应的碰撞检测模型，所建立的碰撞检测模型均采用二叉树的数据结构，同时各碰撞检测模型中每层节点
所包含的包围盒的数据均量化为整型数据，从而在保证精度的同时降低了内存占用量。并
且，还通过采用计算两个碰撞检测模型在同一层节点所包含的包围盒之间的距离来实现对
两个碰撞检测模型的碰撞检测，检测方式简便，易于实现。

[0073] 在一种可能的实现方式中，根据场景数据中的各实体数据建立碰撞检测模型时，可以通过以下方式来实现。首先，由场景数据中读取各实体数据中的点数据和三角面索引。
进而再基于读取到的点数据和三角面索引建立各实体所对应的原始碰撞树。然后，再对建
立好的原始碰撞树进行优化即可得到碰撞检测模型。

[0074] 此处，需要说明的是，基于所读取到的点数据和三角面索引建立相应的原始碰撞树的过程可基于空间分割的方式来实现。在基于空间分割的方式建立相应的原始碰撞树
时，可以先基于所读取到的点数据和三角面索引建立实体的三维模型。进而对各三维模型
的包围盒进行至少一次空间分割，得到多个包围盒，并根据得到的多个包围盒建立原始碰
撞树。

[0075] 其中，在对三维模型的包围盒进行至少一次空间分割时，首先获取三维模型的包围盒在三维坐标系中的最长轴，以获取到的最长轴作为分割轴，按照最长轴方向对三维模
型的包围盒进行初级分割，得到多个一级包围盒。然后，根据各一级包围盒内的三角形个数
以及预设个数的大小关系，基于各一级包围盒进行逐级分割，直至分割后得到的包围盒内
的三角形个数小于或等于预设个数为止。

[0076] 此处，本领域技术人员可以理解的是，在对三维模型的包围盒进行空间分割时，所分割的包围盒即为原始碰撞树的首层节点。分割后所得到的多个一级包围盒即为原始碰撞
树的第二层节点。依此类推，最终分割后所得到的位于原始碰撞树的末层节点的包围盒内
的三角形个数不大于预设个数。

[0077] 其中，需要指出的是，在一种可能的实现方式中，预设个数的取值可以设置为2。并且，还需要说明的是，预设个数的取值也可以根据实际情况进行适应性修改，设置为其他数
值，此处不再进行具体限定。

[0078] 参阅图2，为在本申请的碰撞检测方法中对某一场景数据中的其中一个实体的三维模型进行空间分割后所建立的原始碰撞树的示例。其中，在该示例中，首层节点的包围盒
中三角形个数为100个，第二层节点中每个包围盒中三角形个数分别为50个，第三层节点中
每个包围盒中三角形个数分别25个，依此类推，直至末层节点(即，第N层节点)中每个包围
盒的三角形个数不大于3个为止。

[0079] 另外，在一种可能的实现方式中，在逐级对三维模型的包围盒进行空间分割过程中，当以获取到的最长轴为分割轴，按照最长轴方向不能对包围盒进行有效分割，并且此时
包围盒内的三角形个数大于预设个数时，则以次长轴作为分割轴，按照次长轴方向对包围
盒进行分割。

[0080] 另外，在上述基于空间分割的方式建立原始碰撞树时，在对三维模型的包围盒进行逐级分割过程中，每一次分割时的分割位置可以通过遍历包围盒内所有三角形，获取沿
分割方向上的极大值和极小值，并对极大值和极小值进行平均值计算的方式得到。此处，需
要指出的是，所获取到的极大值和极小值指的是通过遍历各三角形的三个顶点在沿分割方
向上坐标值，由各坐标值中选取出的最大值和最小值。如：分割方向为沿x轴方向时，极大值
和极小值为对某一特定三角形的三个顶点的x坐标上的最大值和最小值。

[0081] 如：在当前次的分割过程中，对于其中一个包围盒A’，其包含有四个三角形，分别为：Δ1，Δ2，Δ3和Δ4。通过遍历Δ1、Δ2、Δ3和Δ4，获取到在杨分割方向上的极大值和极
小值分别为x1和x2，由此可按照公式： 计算确定相应的分割位置。

[0082] 在按照上述任一种方式建立原始碰撞树之后，即可对原始碰撞树进行优化，得到相应的碰撞检测模型。在一种可能的实现方式中，对原始碰撞树进行优化可以包括节点收
敛和数据量化中的至少一种。

[0083] 其中，节点收敛可以通过以下方式来实现。即，收敛原始碰撞树中的叶节点，以叶节点包含的三角面索引替代在根节点中的指针，并将原始碰撞树中的当前叶节点所包含的
三角形收录到当前节点的上一层节点中。通过以叶节点所含的三角面索引替代6其自己在
根节点中的指针，节点数量从2n-1降低到n-1，内存占用降低一半左右。此处，本领域技术人
员可以理解的是，n表征原始碰撞树中叶节点的数量。同时，还通过将原叶节点所含三角形
收录到上一层节点中，进一步减少了内存占用，同时因为少了一层包围盒，对包围盒的检测
并不影响速度。

[0084] 数据量化则可以通过以下方式来实现。即，获取原始碰撞树中各层节点的包围盒数据，并通过量化方式将原始碰撞树中各层节点的包围盒的数据由浮点型数据转换为整型
数据。此处，需要说明的是，量化方式可以采用根据点数据的特性利用乘法将原有的数据进
行扩大，只要确保不超出int型限制，在去掉小数位的同时保证精度不会变化太大即可。其
中，需要指出的是，在根据点数据的特性利用乘法对原始碰撞树中各层节点的包围盒数据
进行整型转换后，在后续计算时，再采用量化方式的反向运算(即，乘以量化因子的倒数)来
得到量化前的浮点型数据进行计算，以提高碰撞检测的精确度。

[0085] 进一步的，在一种可能的实现方式中，数据量化方式还可以采用四舍五入的方式进行整型量化。

[0086] 举例来说，对于一个包围盒AB，其在原始碰撞树中的数据包括：max(22.21，21.05,5.33)；min(0.02,0.03,0.04)。通过采用四舍五入的方式对其进行整型量化后，得到AB的数
据为：max(22，21,5)；min(0,0,0)。由此即可实现采用int值替代float来来实现包围盒数据
的记录。量化方式简单，易于实现。

[0087] 通过采用上述方式对原始碰撞树进行优化后，使得优化后的原始碰撞树(即，碰撞检测模型)中的根节点包围盒大小覆盖整个实体，上层节点包围盒覆盖自身所含的下层节
点。

[0088] 在通过上述任一种方式对场景数据中各实体建立相应的碰撞检测模型后，即可进行任意两个碰撞检测模型的碰撞检测。其中，在进行任意两个碰撞检测模型的碰撞检测时，
可以通过两两组合的方式进行分组，每两个设置为一组。对于每一组碰撞检测模型的碰撞
检测可以并行执行，从而进一步地提高碰撞检测的速率。

[0089] 进一步地，在进行碰撞检测时，首先由所建立的多个碰撞检测模型中提取出当前需要进行碰撞检测的第一碰撞模型和第二碰撞模型。其中，在第一碰撞模型和第二碰撞模
型的提取时可以根据当前接收到的实体数据中的id进行提取。

[0090] 更进一步地，对第一碰撞模型和第二碰撞模型进行碰撞检测时，可以通过由第一碰撞模型的首层节点和第二碰撞模型的首层节点开始，逐层对第一碰撞模型和第二碰撞模
型中处于同一层节点的包围盒之间的距离进行计算，并根据计算得到的距离结果得到相应
的碰撞检测结果。

[0091] 此处，需要指出的是，在本申请中对第一碰撞模型和第二碰撞模型中处于同一层节点的包围盒之间的距离计算可以通过对包围盒的三角面对三角面之间的距离计算来实
现。即，包围盒之间的距离计算可以采用本领域的常规技术手段来实现，因此此处不再赘
述。

[0092] 需要进一步说明的是，在通过计算包围盒之间的距离来进行碰撞检测结果的确定时，由于处于同一层节点处的包围盒的个数可能会在两个以上，因此得到的距离结果可能
会有多个。因此，在根据计算得到的距离结果得到相应的碰撞检测结果时，可以根据所得到
的距离结果中是否存在小于或等于预设数值的结果来进行碰撞检测结果的确定。

[0093] 即，在所得到的距离结果均大于预设数值时，则可以确定当前正在进行碰撞检测的第一碰撞模型与第二碰撞模型不会出现接触的情况，因此可直接得到碰撞检测结果为未
碰撞。

[0094] 在所得到的距离结果中存在小于或等于预设数值的结果时，则表明第一碰撞模型与第二碰撞模型可能会出现接触，因此还需要进行进一步的检测。即，获取第一碰撞模型中
当前节点所包含的第一包围盒和第二碰撞模型中当前节点所包含的第二包围盒，并基于第
一包围盒内的三角形和第二包围盒内的三角形进行三角形碰撞检测，以得到相应的碰撞检
测结果。此处，本领域技术人员可以理解，当前节点为小于或等于预设数值的距离结果所对
应的节点。其中，预设数值的取值可以设置为2。

[0095] 进一步地，基于第一包围盒内的三角形和第二包围盒内的三角形进行三角形碰撞检测，可以通过以下方式来实现。即，依次由第一包围盒内选取第一三角形，并由第二包围
盒内选取第二三角形；其中，第一三角形为第一包围盒内的所有三角形中的任意一个，第二
三角形为所述第二包围盒内的所有三角形中的任意一个。进而，再运用离合轴定理对当前
选取出的第一三角形和第二三角形进行三角形碰撞检测。

[0096] 更进一步地，在一种可能的实现方式中，根据计算得到的距离结果得到相应的碰撞检测结果过程中，当判断出距离结果中存在小于或等于预设数值的距离结果时，还包括
确定距离结果所对应的当前节点是否为叶节点的步骤。

[0097] 即，确定存在小于或等于预设数值的距离结果所对应的节点是否为叶节点。在确定出当前节点为叶节点时，再获取第一碰撞模型中当前节点所包含的第一包围盒和第二碰
撞模型中当前节点所包含的第二包围盒，并基于第一包围盒内的三角形和第二包围盒内的
三角形进行三角形碰撞检测，得到相应的碰撞检测结果。

[0098] 在确定出当前节点为根节点时，表明当前节点还存在下一层节点，此时可继续对第一碰撞模型和第二碰撞模型中当前节点的下一层节点包含的包围盒之间的距离进行计
算。

[0099] 举例来说，参阅图3和图4，第一碰撞模型为A，第二碰撞模型为B，其中，对第一碰撞模型A和第二碰撞模型B进行包围盒间的距离计算，以进行第一碰撞模型A和第二碰撞模型B
的碰撞检测。在对第一碰撞模型A中的当前节点A0和第二碰撞模型B中的当前节点B0之间的
距离进行计算得到A0B0的结果小于2时，由此节点A0和节点B0均为根节点，因此此时直接对
节点A0和节点B0的下一层节点继续进行距离计算。

[0100] 其中，节点A0的下一层节点包括节点A1和节点A2，节点B0的下一层节点包括节点B1和节点B2，由此通过距离的计算得到的距离结果包括：A1B1＞2，A1B2＞2，A2B1＞2和A2B2
＜2。在本实施例中计算出的距离结果中存在小于2的距离结果(即，A2B2)。同时，判断节点
A2和节点B2是否为叶节点。在判断出节点A2和节点B2为叶节点后，此时获取节点A2和节点
B2所包含的三角形。其中，节点A2的包围盒所包含的三角形包括Δ01(A)和Δ02(A)；节点B2
的包围盒包含的三角形包括Δ01(B)和Δ01(B)。通过采用离合轴定理，分别对Δ01(A)和Δ
01(B)、Δ01(A)和Δ02(B)、Δ02(A)和Δ01(B)、以及Δ02(A)和Δ02(B)进行三角形碰撞检
测。在检测出的结果为碰撞时，返回true，结束计算。此处，需要说明的是，运用离合轴定理
对两个三角形进行碰撞检测为本领域常规技术手段，因此此处不再进行赘述。

[0101] 由此，本申请的碰撞检测方法通过采用空间分割的方式对场景数据中的各实体建立相应的原始碰撞树，并对建立的原始碰撞树进行节点收敛和数据量化以实现对原始碰撞
树的优化，从而达到减少内存占用的目的。并通过逐层计算两个碰撞检测模型中处于同一
层节点的包围盒之间的距离来实现对两个碰撞检测模型的碰撞检测，进一步提高了碰撞检
测结果的准确度。

[0102] 相应的，基于前面任一所述的碰撞检测方法，本申请还提供了一种碰撞检测装置。由于本申请提供的碰撞检测装置的工作原理与本申请的碰撞检测方法的原理相同或相似，
因此重复之处不再赘述。

[0103] 参阅图5，本申请的碰撞检测装置100包括模型建立模块110、模型提取模块120和碰撞检测模块130。其中，模型建立模块110，被配置为获取场景数据，根据场景数据中的各
实体数据建立碰撞检测模型。此处，需要指出的是，碰撞检测模型与场景数据中的实体相对
应；且碰撞检测模型的数据结构为二叉树结构；各碰撞检测模型中每层节点中的包围盒中
的数据均为整型数据。

[0104] 模型提取模块120，被配置为由所建立的碰撞检测模型中提取第一碰撞模型和第二碰撞模型。碰撞检测模块130，被配置为由第一碰撞模型的首层节点和第二碰撞模型的首
层节点开始，逐层对第一碰撞模型和第二碰撞模型中处于同一层节点的包围盒之间的距离
进行计算，并根据计算得到的距离结果得到相应的碰撞检测结果。

[0105] 在一种可能的实现方式中，模型建立模块110包括数据读取子模块、原始树建立子模块和原始树优化子模块(图中未示出)。其中，数据读取子模块，被配置为由场景数据中读
取各实体数据中的点数据和三角面索引。原始树建立子模块，被配置为基于点数据和三角
面索引，建立各实体所对应的原始碰撞树。原始树优化子模块，被配置为对原始碰撞树进行
优化，得到碰撞检测模型。其中，原始树优化子模块包括节点收敛单元和数据量化单元。节
点收敛单元，被配置为收敛原始碰撞树中的叶节点，以叶节点包含的三角面索引替代在根
节点中的指针，并将原始碰撞树中的当前叶节点所包含的三角形收录到当前节点的上一层
节点中。数据量化单元，被配置为获取原始碰撞树中各层节点的包围盒的数据，通过量化方
式将原始碰撞树中各层节点的包围盒的数据由浮点型数据转换为整型数据。

[0106] 更进一步地，根据本公开的另一方面，还提供了一种碰撞检测设备200。参阅图6，本公开实施例碰撞检测设备200包括处理器210以及用于存储处理器210可执行指令的存储
器220。其中，处理器210被配置为执行可执行指令时实现前面任一所述的碰撞检测方法。

[0107] 此处，应当指出的是，处理器210的个数可以为一个或多个。同时，在本公开实施例的碰撞检测设备200中，还可以包括输入装置230和输出装置240。其中，处理器210、存储器
220、输入装置230和输出装置240之间可以通过总线连接，也可以通过其他方式连接，此处
不进行具体限定。

[0108] 存储器220作为一种计算机可读存储介质，可用于存储软件程序、计算机可执行程序和各种模块，如：本公开实施例的碰撞检测方法所对应的程序或模块。处理器210通过运
行存储在存储器220中的软件程序或模块，从而执行碰撞检测设备200的各种功能应用及数
据处理。

[0109] 输入装置230可用于接收输入的数字或信号。其中，信号可以为产生与设备/终端/服务器的用户设置以及功能控制有关的键信号。输出装置240可以包括显示屏等显示设备。

[0110] 根据本公开的另一方面，还提供了一种非易失性计算机可读存储介质，其上存储有计算机程序指令，计算机程序指令被处理器210执行时实现前面任一所述的碰撞检测方
法。

[0111] 以上已经描述了本公开的各实施例，上述说明是示例性的，并非穷尽性的，并且也不限于所披露的各实施例。在不偏离所说明的各实施例的范围和精神的情况下，对于本技
术领域的普通技术人员来说许多修改和变更都是显而易见的。本文中所用术语的选择，旨
在最好地解释各实施例的原理、实际应用或对市场中的技术的技术改进，或者使本技术领
域的其它普通技术人员能理解本文披露的各实施例。