实时虚拟场景中碰撞体之间碰撞探测的方法和装置的制造方法
实时虚拟场景中碰撞体之间碰撞探测的方法和装置的制造方法
【技术领域】
[0001] 本发明涉及计算机应用领域，特别是涉及一种实时虚拟场景中碰撞体之间碰撞探 测的方法和装置。
【背景技术】
[0002] 虚拟场景是指通过计算机模拟出来的场景，例如游戏场景、动漫场景等。以游戏场 景为例，当一个虚拟对象遇到一个障碍物，需要绕过该障碍物，即虚拟对象与障碍物之间的 碰撞，传统的处理方式是将虚拟对象和障碍物都简化处理为轴对齐包围盒的碰撞体，如图1 所示，虚拟对象简化成的碰撞体110要绕过墙角120,则按照图中所示的移动变化过程，需要 等碰撞体110在整个移出墙角后，才能继续沿着墙的下边沿前进。
[0003] 然而，这样的碰撞体110碰撞路过墙角时会让操作者操作不顺畅，需要控制碰撞体 移动整个身体才能越过墙角，移动效率低。
【发明内容】
[0004] 基于此，有必要针对传统的碰撞体之间碰撞操作不顺畅且移动效率低的问题，提 供一种实时虚拟场景中碰撞体之间碰撞探测的方法，能提高操作的流畅度，且能提高移动 效率。
[0005] 此外，还有必要提供一种实时虚拟场景中碰撞体之间碰撞探测的装置，能提高操 作的流畅度，且能提高移动效率。
[0006] -种实时虚拟场景中碰撞体之间碰撞探测的方法，包括以下步骤：
[0007] 获取虚拟场景中虚拟对象所对应的圆柱碰撞体到第一二叉空间分割碰撞体各个 平面的最短距离；
[0008] 根据所述最短距离扩展所述第一二叉空间分割碰撞体的各个平面形成第二二叉 空间分割碰撞体；
[0009] 将所述第一二叉空间分割碰撞体的轴对齐包围盒进行扩展生成扩展外边缘包围 盒；
[0010] 将所述生成的扩展外边缘包围盒与所述第二二叉空间分割碰撞体取交集；
[0011] 将所述圆柱碰撞体与所述扩展外边缘包围盒与所述第二二叉空间分割碰撞体取 交集得到的结果进行碰撞探测。
[0012] -种虚拟场景中碰撞体之间碰撞探测的装置，包括：
[0013] 距离获取模块，用于获取虚拟场景中虚拟对象所对应的圆柱碰撞体到第一二叉空 间分割碰撞体各个平面的最短距离；
[0014] 扩展模块，用于根据所述最短距离扩展所述第一二叉空间分割碰撞体的各个平面 形成第二二叉空间分割碰撞体；
[0015] 生成模块，用于将所述第一二叉空间分割碰撞体的轴对齐包围盒进行扩展生成扩 展外边缘包围盒；
[0016] 取值模块，用于将所述生成的扩展外边缘包围盒与所述第二二叉空间分割碰撞体 取交集；
[0017] 碰撞探测模块，用于将所述圆柱碰撞体与所述扩展外边缘包围盒与所述第二二叉 空间分割碰撞体取交集得到的结果进行碰撞探测。
[0018] 上述实时虚拟场景中碰撞体之间碰撞探测的方法和装置，通过将第一二叉空间分 割碰撞体的各个平面向外根据最短距离进行扩展得到第二二叉空间分割碰撞体，且以圆柱 碰撞体的中心点为基准对第一二叉空间分割碰撞体扩展得到扩展外边缘包围盒，将第二二 叉空间分割碰撞体和扩展外边缘包围盒取交集，通过圆柱碰撞体与交集进行碰撞，实现了 圆柱碰撞体与第一二叉空间分割碰撞体的碰撞，碰撞探测是为了避免碰撞体碰撞，采用圆 柱碰撞体与第一二叉空间分割碰撞体的轴对齐包围盒的碰撞探测，相比于传统的碰撞体以 两个轴对齐包围盒进行碰撞探测，不需像轴对齐包围盒一样控制虚拟对象移出整个身子才 能从第一二叉空间分割碰撞体的拐角越过，圆柱碰撞体在拐角处可以平滑的越过，即只需 移出较短的距离即可越过拐角，缩短了移出的距离，在移动速度相同的情况下，提高了移动 效率，且因是平滑的移动，使得操作更流畅。
【附图说明】
[0019] 图1为传统的实时虚拟场景中碰撞体之间碰撞探测的过程示意图；
[0020] 图2为一个实施例中实时虚拟场景中碰撞体之间碰撞探测的方法及装置的应用环 境不意图；
[0021] 图3A为一个实施例中终端的内部结构示意图；
[0022]图3B为一个实施例中服务器的内部结构示意图；
[0023]图4为一个实施例中实时虚拟场景中碰撞体之间碰撞探测的方法的流程图；
[0024]图5为三条线组成三角形的示意图；
[0025]图6为三维空间中三角锥划分形成的空间示意图；
[0026]图7为一个实施例中圆柱碰撞体的不意图；
[0027]图8为俯视情况下的圆柱碰撞体到BSP平面的最短距离示意图；
[0028]图9为圆柱碰撞体到BSP碰撞体的各个平面的距离与圆柱碰撞体到BSP碰撞体的实 际距离的差距示意图；
[0029]图10为BSP碰撞体的各个平面向外扩展的示意图；
[0030]图11为圆柱碰撞体在第二BSP碰撞体上移动情况的示意图；
[0031]图12为第二BSP碰撞体与扩展外边缘包围盒取交集的示意图；
[0032]图13为采用圆柱碰撞体碰撞探测的理论结果示意图；
[0033] 图14为一个实施例中扩展外边缘包围盒的四角添加斜面的示意图；
[0034] 图15为一个实施例中实时虚拟场景中碰撞体之间碰撞探测的装置的结构框图；
[0035] 图16为另一个实施例中实时虚拟场景中碰撞体之间碰撞探测的装置的结构框图；
[0036] 图17为另一个实施例中实时虚拟场景中碰撞体之间碰撞探测的装置的结构框图。
【具体实施方式】
[0037] 为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对 本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅仅用以解释本发明，并 不用于限定本发明。
[0038]图2为一个实施例中实时虚拟场景中碰撞体之间碰撞探测的方法及装置的应用环 境示意图。如图2所示，该应用环境包括终端210和服务器220,终端210可为多个。多个终端 210与服务器220进行通信。实时虚拟场景中碰撞体之间碰撞探测的方法可运行于终端210 上，终端210从服务器220上获取虚拟场景数据，终端210获取虚拟场景中第一二叉空间分割 碰撞体和虚拟对象所对应的圆柱碰撞体，对第一二叉空间分割碰撞体和圆柱碰撞体进行碰 撞探测。实时虚拟场景可为实时游戏场景或实时动漫场景等，虚拟对象可为人物或物体。第 一二叉空间分割碰撞体可为人物或物体等。
[0039]图3A为一个实施例中终端210的内部结构示意图。如图3A所示，该终端210包括通 过系统总线连接的处理器、存储介质、内存和网络接口、声音采集装置、显示屏、扬声器和输 入装置。其中，终端的存储介质存储有操作系统，还包括一种实时虚拟场景中碰撞体之间碰 撞的装置，该实时虚拟场景中碰撞体之间碰撞探测的装置用于实现一种实时虚拟场景中碰 撞体之间碰撞探测的方法。该处理器用于提供计算和控制能力，支撑整个终端的运行。终端 中的内存为存储介质中的实时虚拟场景中碰撞体之间碰撞探测的装置的运行提供环境，网 络接口用于与服务器进行网络通信，如发送数据请求至服务器，接收服务器返回的相应数 据等。终端的显示屏可以是液晶显示屏或者电子墨水显示屏等，输入装置可以是显示屏上 覆盖的触摸层，也可以是终端外壳上设置的按键、轨迹球或触控板，也可以是外接的键盘、 触控板或鼠标等。该终端可以是手机、台式计算机、平板电脑或者个人数字助理等。本领域 技术人员可以理解，图3A中示出的结构，仅仅是与本申请方案相关的部分结构的框图，并不 构成对本申请方案所应用于其上的终端的限定，具体的终端可以包括比图中所示更多或更 少的部件，或者组合某些部件，或者具有不同的部件布置。
[0040]图3B为一个实施例中服务器220的内部结构示意图。如图3B所示，该服务器包括通 过系统总线连接的处理器、存储介质、内存、网络接口、显示屏、输入装置。其中，该服务器的 存储介质存储有操作系统、数据库和实时虚拟场景中碰撞体之间碰撞的装置，数据库中存 储有虚拟场景数据等，该实时虚拟场景中碰撞体之间碰撞探测的装置用于实现适用于服务 器的一种实时虚拟场景中碰撞体之间碰撞探测的方法。该服务器的处理器用于提供计算和 控制能力，支撑整个服务器的运行。该服务器的内存为存储介质中的实时虚拟场景中碰撞 体之间碰撞探测的装置的运行提供环境。该服务器的显示屏可以是液晶显示屏或者电子墨 水显示屏等，输入装置可以是显示屏上覆盖的触摸层，也可以是终端外壳上设置的按键、轨 迹球或触控板，也可以是外接的键盘、触控板或鼠标等。该服务器的网络接口用于据以与外 部的终端通过网络连接通信，比如接收终端发送的数据交互请求以及向终端返回数据等。 服务器可以用独立的服务器或者是多个服务器组成的服务器集群来实现。本领域技术人员 可以理解，图3B中示出的结构，仅仅是与本申请方案相关的部分结构的框图，并不构成对本 申请方案所应用于其上的服务器的限定，具体的服务器可以包括比图中所示更多或更少的 部件，或者组合某些部件，或者具有不同的部件布置。
[0041] 在其他应用环境中，可只包括终端210或服务器220,即实时虚拟场景中碰撞体之 间的碰撞探测的方法可只需运行于终端或服务器上，例如单机的实时游戏场景或实时动漫 场景中虚拟对象的移动等。用户在终端上运行下载的单机游戏或测试人员在服务器上测试 单机游戏等。
[0042] 为了便于探测碰 撞体之间碰撞，在虚拟场景中，表示玩家控制的虚拟角色和其他 一些移动物体(如手雷、摄像机等)都是Actor类及其子类的对象，为此采用轴对齐进行碰撞 探测。为了改变虚拟角色的碰撞体，修改Actor类，让虚拟角色使用圆柱碰撞体，非角色 Actor使用轴对齐包围盒进行碰撞探测。在虚拟场景中，场景对象主要有两种，即包括BSP场 景对象和Component场景对象。按照不同的场景对象分类存储，即将对象分为BSP或 Component。在碰撞探测时，米用碰撞探测的入口函数UworId: :MoveActor()按照场景对象 分类做粗裁剪，判断该分类哪些对象可能会和传入的Actor对象碰撞体发生碰撞，然后再做 精细碰撞探测并获得返回结果。其中，粗裁剪是指做粗碰撞。精细碰撞是指按照下面所述实 时虚拟场景中碰撞体之间碰撞探测的方法实现圆柱碰撞体与BSP碰撞体（即BSP场景对象） 之间进行精细碰撞探测，碰撞探测结束后，采用Check系列函数将碰撞探测结果汇总给 Uworld: :MoveActor()，由其进一步汇总后用于后续计算，如状态改变、伤害计算等。在BSP 场景对象，以圆柱取代轴对齐包围盒作为传入MoveActor〇的碰撞体。实时虚拟场景可包括 实时游戏场景、实时动漫场景等，不限于此。
[0043] 图4为一个实施例中实时虚拟场景中碰撞体之间碰撞探测的方法的流程图。如图4 所示，一种实时虚拟场景中碰撞体之间碰撞探测的方法，运行于图2的应用环境中，包括以 下步骤：
[0044] 步骤402,获取虚拟场景中虚拟对象所对应的圆柱碰撞体到第一二叉空间分割碰 撞体各个平面的最短距离。
[0045] 本实施例中，首先采用BSP(Binary Space Partitioning，二叉空间分割)方法通 过面将空间划分为"面内"和"面外"来组成形体。采用若干平面将空间切割成若干凸体，然 后凸体之间以布尔运算组合成复杂的形状。采用Cy IinderPushOut ()函数测量圆柱碰撞体 至IjBSP碰撞体平面的最短距离。
[0046] 实时虚拟场景是指实时游戏场景或实时动漫场景等。实时游戏场景表示正在运行 的游戏中的场景。实时动漫场景表示正在运行的动漫中的场景。碰撞探测是指探测碰撞体 之间是否发生碰撞。碰撞发生后产生碰撞响应，即一碰撞体与另一碰撞体碰撞后无法沿原 来的移动方向继续移动调整一碰撞体的移动方向以绕过另一碰撞体或一碰撞体击中另一 碰撞体产生击中响应等。本实施例中，碰撞探测主要是指一碰撞体避免与另一碰撞体碰撞， 调整一碰撞体的移动方向以绕过另一碰撞体。
[0047]图5为三条线组成三角形的示意图。如图5所示，采用左侧的三角形划分空间得到 右侧三条线划分出来的空间，即右侧三条线的"里面"组成了这个三角形的区域，将其扩张 到三维空间，即可得出用面划分空间的情况。
[0048]图6为三维空间中三角锥划分形成的空间示意图。如图6所示，空间被三角锥划分 形成了三角锥里面的区域和外面的区域。
[0049] 第一二叉空间分割碰撞体是采用BSP划分出来的空间，第一二叉空间分割碰撞体 的面为BSP划分出的空间的表面。
[0050] 虚拟对象可为虚拟场景中可以动态运行的人物或物体等。将虚拟对象配置为圆柱 碰撞体。碰撞体是用于计算物体之间是否碰撞的物体，即实际参与碰撞算法计算的物体。碰 撞体的大小可根据虚拟场景中虚拟对象的大小设置，例如虚拟对象为球体，则虚拟对象对 应的圆柱碰撞体的高可设置球体的直径，圆柱体的半径可设置略大于球体的半径大小。因 采用竖直圆柱方式计算碰撞体到BSP平面的距离，比轴对齐包围盒(AABB，Axis Aligned Bounding Box)更短，效果更自然，所以，假设虚拟对象所对应的圆柱碰撞体一定是(世界坐 标系下)竖直圆柱。轴对齐包围盒是指各个边界均与坐标轴平行的包围盒。
[0051 ]对于BSP场景对象来说，首先测量圆柱碰撞体到第一 BSP碰撞体的某个平面的最短 距离。最短距离是指当圆柱碰撞体刚好接触该平面（即平面支撑圆柱碰撞体)时，圆柱碰撞 体的中心点到平面的距离。也就是该虚拟对象所对应的圆柱碰撞体到第一二叉空间分割碰 撞体各个平面的最短距离为该虚拟对象所对应的圆柱碰撞体接触第一二叉空间分割碰撞 体的平面时，该圆柱碰撞体的中心点到接触的该第一二叉空间分割碰撞体的平面的距离。 需要说明的是，平面可以是任意平面，平面可能紧贴圆柱碰撞体的一条线或者只支撑一个 点。
[0052]该获取虚拟场景中虚拟对象所对应的圆柱碰撞体到第一二叉空间分割碰撞体各 个平面的最短距离的步骤包括：
[0053]若虚拟对象所对应的圆柱碰撞体的轴向与第一二叉空间分割碰撞体的平面平行， 且第一二叉空间分割碰撞体的平面紧贴圆柱碰撞体的一条侧边线，则虚拟对象所对应的圆 柱碰撞体到该第一二叉空间分割碰撞体的平面的最短距离为圆柱碰撞体的半径；
[0054] 若第一二叉空间分割碰撞体的平面紧贴圆柱碰撞体的一个点，则获取并根据圆柱 碰撞体的半径、半高及第一二叉空间分割碰撞体的平面的法向量的XYZ坐标分量，得到圆柱 碰撞体到第一二叉空间分割碰撞体的平面的最短距离。
[0055] 具体地，根据圆柱碰撞体的半径、半高及第一二叉空间分割碰撞体的平面的法向 量的XYZ坐标分量，得到圆柱碰撞体到第一二叉空间分割碰撞体的平面的最短距离的计算 公式为先求取法向量的XY坐标分量的平方根与圆柱碰撞体半径的乘积，再求取圆柱碰撞体 的半高与法向量的Z坐标分量的绝对值的乘积，最后求取两个乘积的和得到，计算公式如下 式⑴：
[0057] 式（1)中，S为圆柱碰撞体到第一二叉空间分割碰撞体的平面的最短距离，R为圆柱 碰撞体的半径，X、y、Z为平面的法向量的三个XYZ坐标系下的三个坐标分量，H为圆柱碰撞体 的半高，I z I为法向量的z分量的绝对值。
[0058] 图7为一个实施例中圆柱碰撞体的示意图。如图7所示，采用Cylinder类表示竖直 圆柱，在Cyl inder类里，采用横线72表示Radius (半径），竖线74表示Height，取值为半高（即 圆柱碰撞体高度值的一半）。
[0059]图8为俯视情况下的圆柱碰撞体到BSP平面的最短距离示意图。如图7所示，在俯视 情况下，圆柱陪碰撞体为一个个的圆形，圆形的中点到BSP边(一个平面俯视情况下位一条 边)的垂线段即为圆柱到该BSP平面的距离。在圆柱刚好接触到BSP平面的情况下，得到的距 离即为最短距离。在三维实际情况中，如果是圆柱碰撞体的轴向刚好和BSP平面平行，平面 就紧贴圆柱碰撞体的一条侧边线，这种情况下圆柱碰撞体的半径就是圆柱碰撞体到该BSP 平面的距离。其它情况下平面紧贴圆柱碰撞体的一个点。假设圆柱碰撞体总是竖直向上的， 其半径为R，半高为H，平面的法向量为N(其基向量与圆柱碰撞体坐标空间基向量相同），法 向量的XYZ坐标轴的三个分量为[x，y，z ]，则圆柱碰撞体中心道BSP平面的最短距离采用公 式(1)进行计算得出。
[0060]图9为圆柱碰撞体到BSP碰撞体的各个平面的距离与圆柱碰撞体到BSP碰撞体的实 际距离的差距示意图。如图9所示，圆柱碰撞体到BSP横平面的最短距离采用92表示，圆柱碰 撞体到BSP竖平面的最短距离采用94表示。对于圆柱，即使能够算出圆柱到每个平面的距 离，也不能直接得出圆柱碰撞体到BSP碰撞体的平面之间的拐角处的实际距离，即图中的斜 线96〇
[0061]步骤404,根据该最短距离扩展该第一二叉空间分割碰撞体的各个平面形成第二 二叉空间分割碰撞体。
[0062] 本实施例中，将圆柱碰撞体退化为一个点（即中心点），将BSP碰撞体(第一二叉空 间分割碰撞体)的各个平面向外扩展，扩展长度为圆柱碰撞体到该平面的最短距离，形成新 的BSP碰撞体，即第二二叉空间分割碰撞体。
[0063] 图10为BSP碰撞体的各个平面向外扩展的示意图。如图10所示，第一BSP碰撞体 1002的各个平面分别向外扩展，各个平面向外扩展的距离为圆柱碰撞体到该平面的最短距 离，扩展后形成第二BSP碰撞体1004图中，1006为圆柱碰撞体。
[0064]图11为圆柱碰撞体在第二BSP碰撞体上移动情况的示意图。如图11所示，圆柱碰撞 体退化为点后，沿着扩展后的BSP碰撞体移动在锐角处圆柱碰撞体要走离开锐角较远距离 才能拐弯。
[0065]步骤406,将该第一二叉空间分割碰撞体的轴对齐包围盒进行扩展生成扩展外边 缘包围盒。
[0066]本实施例中，将该第一二叉空间分割碰撞体的轴对齐包围盒进行扩展生成扩展外 边缘包围盒的步骤包括:将该第一二叉空间分割碰撞体的轴对齐包围盒以圆柱碰撞体的中 心点为基准扫描整个第一二叉空间分割碰撞体的轴对齐包围盒，生成扩展外边缘包围盒。 [0067]步骤408,将该生成的扩展外边缘包围盒与该第二二叉空间分割碰撞体取交集。 [0068]图12为第二BSP碰撞体与扩展外边缘包围盒取交集的示意图。如图12所示，以BSP 碰撞体本身的轴对齐包围盒1202为基准，扫描BSP碰撞体的包围盒后扩展出一层外边缘包 围盒1204,然后将扩展外边缘包围盒与第二BSP1206取交集，即可实现让圆柱碰撞体在BSP 碰撞体周围的移动更自然，且节省距离。
[0069]步骤410,将该圆柱碰撞体与该扩展外边缘包围盒与该第二二叉空间分割碰撞体 取交集得到的结果进行 碰撞探测。
[0070]具体地，通过圆柱碰撞体与交集进行碰撞探测来实现圆柱碰撞体与第一二叉空间 分割碰撞体进行碰撞探测。
[0071 ] 上述实时虚拟场景中碰撞体之间碰撞探测的方法，通过将第一二叉空间分割碰撞 体的各个平面向外根据最短距离进行扩展得到第二二叉空间分割碰撞体，且以圆柱碰撞体 的中心点为基准对第一二叉空间分割碰撞体扩展得到扩展外边缘包围盒，将第二二叉空间 分割碰撞体和扩展外边缘包围盒取交集，通过圆柱碰撞体与交集进行碰撞，实现了圆柱碰 撞体与第一二叉空间分割碰撞体的碰撞探测，碰撞探测是为了避免两个碰撞体发生碰撞， 采用圆柱碰撞体与第一二叉空间分割碰撞体的轴对齐包围盒的碰撞探测，相比于传统的碰 撞体以两个轴对齐包围盒进行碰撞探测，不需像轴对齐包围盒一样控制虚拟对象移出整个 身子才能从第一二叉空间分割碰撞体的拐角越过，圆柱碰撞体在拐角处可以平滑的越过， 即只需移出较短的距离即可越过拐角，缩短了移出的距离，在移动速度相同的情况下，提高 了移动效率，且因是平滑的移动，使得操作更流畅。
[0072] 图13为采用圆柱碰撞体碰撞探测使用传统的算法效果和本发明中的碰撞探测的 理论结果示意图。如图13所示，左图为采用圆柱碰撞体按照传统的算法进行碰撞探测，其仍 然需要将圆柱碰撞体移出整个身体然后才能沿着黑色碰撞体底边移动，右图为采用圆柱碰 撞体采用上述实时虚拟场景中碰撞体之间碰撞探测的方法后所能达到的理论结果，圆柱碰 撞体在移动过程中移动的距离较短，移动效率高，且操作流畅。在一个实施例中，上述实时 虚拟场景中碰撞体之间碰撞探测的方法还包括:在将该第一二叉空间分割碰撞体的轴对齐 包围盒进行扩展生成扩展外边缘包围盒的步骤之后，将该扩展外边缘包围盒的四个角分别 添加斜面。
[0073] 其中，该第一二叉空间分割碰撞体中与该扩展外边缘包围盒的斜面对应的平面交 叉线到该斜面的距离为该圆柱碰撞体的半径。
[0074] 通过将扩展外边缘包围盒的四角添加斜面，再得到扩展外边缘包围盒与第二BSP 碰撞体的交集，交集也带有斜面，采用斜面模拟圆角，可进一步方便圆柱碰撞体移过拐角， 进一步缩短了距离，提高了移动效率。
[0075] 图14为一个实施例中扩展外边缘包围盒的四角添加斜面的示意图。如图14所示， 在扩展外边缘包围盒的四个角添加了斜面作为倒角面，即对扩展外边缘包围盒的四个角上 的直角做切割处理形成斜面，直角切割时，切割的部分投影到平面上形成的三角形内的锐 角为45度。
[0076] 在一个实施例中，上述实时虚拟场景中碰撞体之间碰撞探测的方法还包括:将该 第一二叉空间分割碰撞体的轴对齐包围盒进行扩展生成扩展外边缘包围盒的步骤之后，还 包括:将该扩展外边缘包围盒的四个角分别添加圆弧面。
[0077] 其中，该第一二叉空间分割碰撞体中与该扩展外边缘包围盒的圆弧面对应的平面 交叉线到该圆弧面的最短距离为该圆柱碰撞体的半径。
[0078] 通过将扩展外边缘包围盒的四角添加圆弧面，再得到扩展外边缘包围盒与第二 BSP碰撞体的交集，交集也带有圆弧面，采用圆弧面更贴合圆柱碰撞体，可进一步方便圆柱 碰撞体移过拐角，进一步缩短了距离，提高了移动效率。
[0079] 下面结合具体的应用场景说明实时虚拟场景中碰撞体之间碰撞探测的方法的实 现过程，以实时游戏场景为例，圆柱碰撞体为虚拟角色，第一二叉空间分割碰撞体为墙体， 结合图14,其中圆形为圆柱体的二维投影，三角形为第一二叉空间分割碰撞体的二维投影。 碰撞探测的过程包括：
[0080] (1)获取实时游戏场景中虚拟角色所对应的圆柱碰撞体到第一二叉空间分割碰撞 体各个平面的最短距离。
[0081] (2)根据该最短距离扩展该第一二叉空间分割碰撞体的各个平面形成第二二叉空 间分割碰撞体。
[0082] (3)将该第一二叉空间分割碰撞体的轴对齐包围盒进行扩展生成扩展外边缘包围 盒，将该扩展外边缘包围盒的四个角分别添加圆弧面。
[0083] (4)将该生成的扩展外边缘包围盒与该第二二叉空间分割碰撞体取交集。
[0084] (5)将该圆柱碰撞体与该扩展外边缘包围盒与该第二二叉空间分割碰撞体取交集 得到的结果进行碰撞探测。
[0085] 碰撞探测是指探测碰撞体之间是否发生碰撞，发生碰撞后调整圆柱碰撞体原来的 移动方向，绕过第二二叉空间分割碰撞体。
[0086] 圆柱碰撞体投影的圆形同扩展外边缘包围盒与第二二叉空间分割碰撞体所取的 交集进行碰撞探测，即得到圆柱碰撞体的移动路线，如图14所示。
[0087] 图15为一个实施例中实时虚拟场景中碰撞体之间碰撞探测的装置的结构框图。图 15中的实时虚拟场景中碰撞体之间碰撞探测的装置，为实现图4中实时虚拟场景中碰撞体 之间碰撞探测的方法所构建的功能架构，所包含的功能模块的划分不限于本实施例中所列 举的，也可采用其他方式进行划分。如图15所示，一种实时虚拟场景中碰撞体之间碰撞探测 的装置包括距离获取模块1510、扩展模块1520、生成模块1530、取值模块1540、碰撞探测模 块1550。
[0088]距离获取模块1510用于获取虚拟场景中虚拟对象所对应的圆柱碰撞体到第一二 叉空间分割碰撞体各个平面的最短距离。
[0089] 本实施例中，首先采用BSP方法通过面将空间划分为"面内"和"面外"来组成形体。 采用若干平面将空间切割成若干凸体，然后凸体之间以布尔运算组合成复杂的形状。
[0090] 第一二叉空间分割碰撞体是采用BSP划分出来的空间，第一二叉空间分割碰撞体 的面为BSP划分出的空间的表面。
[0091] 虚拟对象可为虚拟场景中可以动态运行的人物或物体等。将虚拟对象配置为圆柱 碰撞体。碰撞体是用于计算物体之间是否碰撞的物体，即实际参与碰撞算法计算的物体。 [0092]该虚拟对象所对应的圆柱碰撞体到第一二叉空间分割碰撞体各个平面的最短距 离为该虚拟对象所对应的圆柱碰撞体接触第一二叉空间分割碰撞体的平面时，该圆柱碰撞 体的中心点到接触的该第一二叉空间分割碰撞体的平面的距离。
[0093]本实施例中，距离获取模块1510还用于若虚拟对象所对应的圆柱碰撞体的轴向与 第一二叉空间分割碰撞体的平面平行，且第一二叉空间分割碰撞体的平面紧贴圆柱碰撞体 的一条侧边线，则虚拟对象所对应的圆柱碰撞体到该第一二叉空间分割碰撞体的平面的最 短距离为圆柱碰撞体的半径；以及
[0094] 若第一二叉空间分割碰撞体的平面紧贴圆柱碰撞体的一个点，则获取并根据圆柱 碰撞体的半径、半高及第一二叉空间分割碰撞体的平面的法向量的XYZ坐标分量，得到圆柱 碰撞体到第一二叉空间分割碰撞体的平面的最短距离。
[0095] 具体地，根据圆柱碰撞体的半径、半高及第一二叉空间分割碰撞体的平面的法向 量的XYZ坐标分量，得到圆柱碰撞体到第一二叉空间分割碰撞体的平面的最短距离的计算 公式为先求取法向量的XY坐标分量的平方根与圆柱碰撞体半径的乘积，再求取圆柱碰撞体 的半高与法向量的Z坐标分量的绝对值的乘积，最后求取两个乘积的和得到，计算公式如下 式⑴：
[0097]式（1)中，S为圆柱碰撞体到第一二叉空间分割碰撞体的平面的最短距离，R为圆柱 碰撞体的半径，X、y、Z为平面的法向量的三个XYZ坐标系下的三个坐标分量，H为圆柱碰撞体 的半高，I Z I为法向量的Z分量的绝对值。
[0098] 扩展模块1520用于根据该最短距离扩展该第一二叉空间分割碰撞体的各个平面 形成第二二叉空间分割碰撞体。
[0099] 本实施例中，将圆柱碰撞体退化为一个点（即中心点），将BSP碰撞体(第一二叉空 间分割碰撞体)的各个平面向外扩展，扩展长度为圆柱碰撞体到该平面的最短距离，形成新 的BSP碰撞体，即第二二叉空间分割碰撞体。
[0100]生成模块1530用于将该第一二叉空间分割碰撞体的轴对齐包围盒进行扩展生成 扩展外边缘包围盒。
[0101] 具体的，生成模块1530还用于将该第一二叉空间分割碰撞体的轴对齐包围盒以圆 柱碰撞体的中心点为基准扫描整个第一二叉空间分割碰撞体轴对齐包围盒，生成扩展外边 缘包围盒。
[0102] 取值模块1540用于将该生成的扩展外边缘包围盒与该第二二叉空间分割碰撞体 取交集。
[0103] 碰撞探测模块1550用于将该圆柱碰撞体与该扩展外边缘包围盒与该第二二叉空 间分割碰撞体取交集得到的结果进行碰撞探测。
[0104] 具体地，通过圆柱碰撞体与交集进行碰撞来实现圆柱碰撞体与第一二叉空间分割 碰撞体进行碰撞。
[0105] 上述实时虚拟场景中碰撞体之间碰撞探测的装置，通过将第一二叉空间分割碰撞 体的各个平面向外根据最短距离进行扩展得到第二二叉空间分割碰撞体，且以圆柱碰撞体 的中心点为基准对第一二叉空间分割碰撞体扩展得到扩展外边缘包围盒，将第二二叉空间 分割碰撞体和扩展外边缘包围盒取交集，通过圆柱碰撞体与交集进行碰撞，实现了圆柱碰 撞体与第一二叉空间分割碰撞体的碰撞探测，碰撞探测是为了避免碰撞体碰撞，采用圆柱 碰撞体与第一二叉空间分割碰撞体的轴对齐包围盒的碰撞探测，相比于传统的碰撞体以两 个轴对齐包围盒进行碰撞探测，不需像轴对齐包围盒一样控制虚拟对象移出整个身子才能 从第一二叉空间分割碰撞体的拐角越过，圆柱碰撞体在拐角处可以平滑的越过，即只 需移 出较短的距离即可越过拐角，缩短了移出的距离，在移动速度相同的情况下，提高了移动效 率，且因是平滑的移动，使得操作更流畅。
[0106] 图16为一个实施例中实时虚拟场景中碰撞体之间碰撞探测的装置的结构框图。如 图16所示，一种实时虚拟场景中碰撞体之间碰撞探测的装置，除了包括距离获取模块1510、 扩展模块1520、生成模块1530、取值模块1540、碰撞探测模块1550，还包括切割模块1560。
[0107] 切割模块1560用于将该第一二叉空间分割碰撞体的轴对齐包围盒进行扩展生成 扩展外边缘包围盒之后，将该扩展外边缘包围盒的四个角分别添加斜面。
[0108] 其中，该第一二叉空间分割碰撞体中与该扩展外边缘包围盒的斜面对应的平面交 叉线到该斜面的距离为该圆柱碰撞体的半径。
[0109] 通过将扩展外边缘包围盒的四角添加斜面，再得到扩展外边缘包围盒与第二BSP 碰撞体的交集，交集也带有斜面，采用斜面模拟圆角，可进一步方便圆柱碰撞体移过拐角， 进一步缩短了距离，提高了移动效率。
[0110] 图17为另一个实施例中实时虚拟场景中碰撞体之间碰撞探测的装置的结构框图。 如图17所示，一种实时虚拟场景中碰撞体之间碰撞探测的装置，除了包括距离获取模块 1510、扩展模块1520、生成模块1530、取值模块1540、碰撞探测模块1550,还包括分割模块 1570〇
[0111 ]分割模块1570用于将该第一二叉空间分割碰撞体的轴对齐包围盒进行扩展生成 扩展外边缘包围盒之后，将该扩展外边缘包围盒的四个角分别添加圆弧面。
[0112] 其中，该第一二叉空间分割碰撞体中与该扩展外边缘包围盒的圆弧面对应的平面 交叉线到该圆弧面的最短距离为该圆柱碰撞体的半径。
[0113] 通过将扩展外边缘包围盒的四角添加圆弧面，再得到扩展外边缘包围盒与第二 BSP碰撞体的交集，交集也带有圆弧面，采用圆弧面更贴合圆柱碰撞体，可进一步方便圆柱 碰撞体移过拐角，进一步缩短了距离，提高了移动效率。
[0114] 本领域普通技术人员可以理解实现上述实施例方法中的全部或部分流程，是可以 通过计算机程序来指令相关的硬件来完成，所述的程序可存储于一非易失性计算机可读取 存储介质中，该程序在执行时，可包括如上述各方法的实施例的流程。其中，所述的存储介 质可为磁碟、光盘、只读存储记忆体(Read-Only Memory，ROM)等。
[0115] 以上所述实施例仅表达了本发明的几种实施方式，其描述较为具体和详细，但并 不能因此而理解为对本发明专利范围的限制。应当指出的是，对于本领域的普通技术人员 来说，在不脱离本发明构思的前提下，还可以做出若干变形和改进，这些都属于本发明的保 护范围。因此，本发明专利的保护范围应以所附权利要求为准。
【主权项】
1. 一种实时虚拟场景中碰撞体之间碰撞探测的方法，包括以下步骤： 获取虚拟场景中虚拟对象所对应的圆柱碰撞体到第一二叉空间分割碰撞体各个平面 的最短距离； 根据所述最短距离扩展所述第一二叉空间分割碰撞体的各个平面形成第二二叉空间 分割碰撞体； 将所述第一二叉空间分割碰撞体的轴对齐包围盒进行扩展生成扩展外边缘包围盒； 将所述生成的扩展外边缘包围盒与所述第二二叉空间分割碰撞体取交集； 将所述圆柱碰撞体与所述扩展外边缘包围盒与所述第二二叉空间分割碰撞体取交集 得到的结果进行碰撞探测。2. 根据权利要求1所述的方法，其特征在于，将所述第一二叉空间分割碰撞体的轴对齐 包围盒进行扩展生成扩展外边缘包围盒的步骤之后，所述方法还包括： 将所述扩展外边缘包围盒的四个角分别添加斜面。3. 根据权利要求2所述的方法，其特征在于，所述第一二叉空间分割碰撞体中与所述扩 展外边缘包围盒的斜面对应的平面交叉线到所述斜面的距离为所述圆柱碰撞体的半径。4. 根据权利要求1所述的方法，其特征在于，将所述第一二叉空间分割碰撞体的轴对齐 包围盒进行扩展生成扩展外边缘包围盒的步骤之后，所述方法还包括： 将所述扩展外边缘包围盒的四个角分别添加圆弧面。5. 根据权利要求4所述的方法，其特征在于，所述第一二叉空间分割碰撞体中与所述扩 展外边缘包围盒的圆弧面对应的平面交叉线到所述圆弧面的最短距离为所述圆柱碰撞体 的半径。6. 根据权利要求1所述的方法，其特征在于，所述虚拟对象所对应的圆柱碰撞体到第一 二叉空间分割碰撞体各个平面的最短距离为所述虚拟对象所对应的圆柱碰撞体接触第一 二叉空间分割碰撞体的平面时，所述圆柱碰撞体的中心点到接触的所述第一二叉空间分割 碰撞体的平面的距离。7. 根据权利要求1所述的方法，其特征在于，所述获取虚拟场景中虚拟对象所对应的圆 柱碰撞体到第一二叉空间分割碰撞体各个平面的最短距离的步骤包括： 若虚拟对象所对应的圆柱碰撞体的轴向与第一二叉空间分割碰撞体的平面平行，且第 一二叉空间分割碰撞体的平面紧贴圆柱碰撞体的一条侧边线，则虚拟对象所对应的圆柱碰 撞体到所述第一二叉空间分割碰撞体的平面的最短距离为圆柱碰撞体的半径； 若第一二叉空间分割碰撞体的平面紧贴圆柱碰撞体的一个点，则获取并根据圆柱碰撞 体的半径、半高及第一二叉空间分割碰撞体的平面的法向量的XYZ坐标分量，得到圆柱碰撞 体到第一二叉空间分割碰撞体的平面的最短距离。8. 根据权利要求1所述的方法，其特征在于，将所述第一二叉空间分割碰撞体的轴对齐 包围盒进行扩展生成扩展外边缘包围盒的步骤包括： 将所述第一二叉空间分割碰撞体的轴对齐包围盒以圆柱碰撞体的中心点为基准扫描 整个所述第一二叉空间分割碰撞体的轴对齐包围盒，生成扩展外边缘包围盒。9. 一种实时虚拟场景中碰撞体之间碰撞探测的装置，其特征在于，包括： 距离获取模块，用于获取虚拟场景中虚拟对象所对应的圆柱碰撞体到第一二叉空间分 割碰撞体各个平面的最短距离； 扩展模块，用于根据所述最短距离扩展所述第一二叉空间分割碰撞体的各个平面形成 第二二叉空间分割碰撞体； 生成模块，用于将所述第一二叉空间分割碰撞体的轴对齐包围盒进行扩展生成扩展外 边缘包围盒； 取值模块，用于将所述生成的扩展外边缘包围盒与所述第二二叉空间分割碰撞体取交 集； 碰撞探测模块，用于将所述圆柱碰撞体与所述扩展外边缘包围盒与所述第二二叉空间 分割碰撞体取交集得到的结果进行碰撞探测。10. 根据权利要求9所述的装置，其特征在于，所述装置还包括： 切割模块，用于将所述第一二叉空间分割碰撞体的轴对齐包围盒进行扩展生成扩展外 边缘包围盒之后，将所述扩展外边缘包围盒的四个角分别添加斜面。11. 根据权利要求10所述的装置，其特征在于，所述第一二叉空间分割碰撞体中与所述 扩展外边缘包围盒的斜面对应的平面交叉线到所述斜面的距离为所述圆柱碰撞体的半径。12. 根据权利要求9所述的装置，其特征在于，所述装置还包括： 分割模块，用于将所述第一二叉空间分割碰撞体的轴对齐包围盒进行扩展生成扩展外 边缘包围盒之后，将所述扩展外边缘包围盒的四个角分别添加圆弧面。13. 根据权利要求12所述的装置，其特征在于，所述第一二叉空间分割碰撞体中与所述 扩展外边缘包围盒的圆弧面对应的平面交叉线到所述圆弧面的最短距离为所述圆柱碰撞 体的半径。14. 根据权利要求9所述的装置，其特征在于，所述虚拟对象所对应的圆柱碰撞体到第 一二叉空间分割碰撞体各个平面的最短距离为所述虚拟对象所对应的圆柱碰撞体接触第 一二叉空间分割碰撞体的平面时，所述圆柱碰撞体的中心点到接触的所述第一二叉空间分 割碰撞体的平面的距离。15. 根据权利要求9所述的装置，其特征在于，所述距离获取模块还用于若虚拟对象所 对应的圆柱碰撞体的轴向与第一二叉空间分割碰撞体的平面平行，且第一二叉空间分割碰 撞体的平面紧贴圆柱碰撞体的一条侧边线，则虚拟对象所对应的圆柱碰撞体到所述第一二 叉空间分割碰撞体的平面的最短距离为圆柱碰撞体的半径；以及 若第一二叉空间分割碰撞体的平面紧贴圆柱碰撞体的一个点，则获取并根据圆柱碰撞 体的半径、半高及第一二叉空间分割碰撞体的平面的法向量的XYZ坐标分量，得到圆柱碰撞 体到第一二叉空间分割碰撞体的平面的最短距离。16. 根据权利要求9所述的装置，其特征在于，所述生成模块还用于将所述第一二叉空 间分割碰撞体的轴对齐包围盒以圆柱碰撞体的中心点为基准扫描整个所述第一二叉空间 分割碰撞体的轴对齐包围盒，生成扩展外边缘包围盒。
【专利摘要】本发明涉及一种实时虚拟场景中碰撞体之间碰撞探测的方法和装置。所述方法包括以下步骤：获取虚拟场景中虚拟对象所对应的圆柱碰撞体到第一二叉空间分割碰撞体各个平面的最短距离；根据最短距离扩展第一二叉空间分割碰撞体的各个平面形成第二二叉空间分割碰撞体；将第一二叉空间分割碰撞体的轴对齐包围盒进行扩展生成扩展外边缘包围盒；将所述生成的扩展外边缘包围盒与所述第二二叉空间分割碰撞体取交集；将所述圆柱碰撞体与所述扩展外边缘包围盒与所述第二二叉空间分割碰撞体取交集得到的结果进行碰撞探测。上述实时虚拟场景中碰撞体之间碰撞探测的方法和装置，只需移出较短的距离即可越过拐角，提高了移动效率，且平滑越过，使得操作更流畅。
【IPC分类】G06T19/00, G06T7/00
【公开号】CN105488851
【申请号】CN201510860807
【发明人】匡西尼
【申请人】腾讯科技（深圳）有限公司
【公开日】2016年4月13日
【申请日】2015年11月30日
【技术领域】
[0001] 本发明涉及计算机应用领域，特别是涉及一种实时虚拟场景中碰撞体之间碰撞探 测的方法和装置。
【背景技术】
[0002] 虚拟场景是指通过计算机模拟出来的场景，例如游戏场景、动漫场景等。以游戏场 景为例，当一个虚拟对象遇到一个障碍物，需要绕过该障碍物，即虚拟对象与障碍物之间的 碰撞，传统的处理方式是将虚拟对象和障碍物都简化处理为轴对齐包围盒的碰撞体，如图1 所示，虚拟对象简化成的碰撞体110要绕过墙角120,则按照图中所示的移动变化过程，需要 等碰撞体110在整个移出墙角后，才能继续沿着墙的下边沿前进。
[0003] 然而，这样的碰撞体110碰撞路过墙角时会让操作者操作不顺畅，需要控制碰撞体 移动整个身体才能越过墙角，移动效率低。
【发明内容】
[0004] 基于此，有必要针对传统的碰撞体之间碰撞操作不顺畅且移动效率低的问题，提 供一种实时虚拟场景中碰撞体之间碰撞探测的方法，能提高操作的流畅度，且能提高移动 效率。
[0005] 此外，还有必要提供一种实时虚拟场景中碰撞体之间碰撞探测的装置，能提高操 作的流畅度，且能提高移动效率。
[0006] -种实时虚拟场景中碰撞体之间碰撞探测的方法，包括以下步骤：
[0007] 获取虚拟场景中虚拟对象所对应的圆柱碰撞体到第一二叉空间分割碰撞体各个 平面的最短距离；
[0008] 根据所述最短距离扩展所述第一二叉空间分割碰撞体的各个平面形成第二二叉 空间分割碰撞体；
[0009] 将所述第一二叉空间分割碰撞体的轴对齐包围盒进行扩展生成扩展外边缘包围 盒；
[0010] 将所述生成的扩展外边缘包围盒与所述第二二叉空间分割碰撞体取交集；
[0011] 将所述圆柱碰撞体与所述扩展外边缘包围盒与所述第二二叉空间分割碰撞体取 交集得到的结果进行碰撞探测。
[0012] -种虚拟场景中碰撞体之间碰撞探测的装置，包括：
[0013] 距离获取模块，用于获取虚拟场景中虚拟对象所对应的圆柱碰撞体到第一二叉空 间分割碰撞体各个平面的最短距离；
[0014] 扩展模块，用于根据所述最短距离扩展所述第一二叉空间分割碰撞体的各个平面 形成第二二叉空间分割碰撞体；
[0015] 生成模块，用于将所述第一二叉空间分割碰撞体的轴对齐包围盒进行扩展生成扩 展外边缘包围盒；
[0016] 取值模块，用于将所述生成的扩展外边缘包围盒与所述第二二叉空间分割碰撞体 取交集；
[0017] 碰撞探测模块，用于将所述圆柱碰撞体与所述扩展外边缘包围盒与所述第二二叉 空间分割碰撞体取交集得到的结果进行碰撞探测。
[0018] 上述实时虚拟场景中碰撞体之间碰撞探测的方法和装置，通过将第一二叉空间分 割碰撞体的各个平面向外根据最短距离进行扩展得到第二二叉空间分割碰撞体，且以圆柱 碰撞体的中心点为基准对第一二叉空间分割碰撞体扩展得到扩展外边缘包围盒，将第二二 叉空间分割碰撞体和扩展外边缘包围盒取交集，通过圆柱碰撞体与交集进行碰撞，实现了 圆柱碰撞体与第一二叉空间分割碰撞体的碰撞，碰撞探测是为了避免碰撞体碰撞，采用圆 柱碰撞体与第一二叉空间分割碰撞体的轴对齐包围盒的碰撞探测，相比于传统的碰撞体以 两个轴对齐包围盒进行碰撞探测，不需像轴对齐包围盒一样控制虚拟对象移出整个身子才 能从第一二叉空间分割碰撞体的拐角越过，圆柱碰撞体在拐角处可以平滑的越过，即只需 移出较短的距离即可越过拐角，缩短了移出的距离，在移动速度相同的情况下，提高了移动 效率，且因是平滑的移动，使得操作更流畅。
【附图说明】
[0019] 图1为传统的实时虚拟场景中碰撞体之间碰撞探测的过程示意图；
[0020] 图2为一个实施例中实时虚拟场景中碰撞体之间碰撞探测的方法及装置的应用环 境不意图；
[0021] 图3A为一个实施例中终端的内部结构示意图；
[0022]图3B为一个实施例中服务器的内部结构示意图；
[0023]图4为一个实施例中实时虚拟场景中碰撞体之间碰撞探测的方法的流程图；
[0024]图5为三条线组成三角形的示意图；
[0025]图6为三维空间中三角锥划分形成的空间示意图；
[0026]图7为一个实施例中圆柱碰撞体的不意图；
[0027]图8为俯视情况下的圆柱碰撞体到BSP平面的最短距离示意图；
[0028]图9为圆柱碰撞体到BSP碰撞体的各个平面的距离与圆柱碰撞体到BSP碰撞体的实 际距离的差距示意图；
[0029]图10为BSP碰撞体的各个平面向外扩展的示意图；
[0030]图11为圆柱碰撞体在第二BSP碰撞体上移动情况的示意图；
[0031]图12为第二BSP碰撞体与扩展外边缘包围盒取交集的示意图；
[0032]图13为采用圆柱碰撞体碰撞探测的理论结果示意图；
[0033] 图14为一个实施例中扩展外边缘包围盒的四角添加斜面的示意图；
[0034] 图15为一个实施例中实时虚拟场景中碰撞体之间碰撞探测的装置的结构框图；
[0035] 图16为另一个实施例中实时虚拟场景中碰撞体之间碰撞探测的装置的结构框图；
[0036] 图17为另一个实施例中实时虚拟场景中碰撞体之间碰撞探测的装置的结构框图。
【具体实施方式】
[0037] 为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对 本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅仅用以解释本发明，并 不用于限定本发明。
[0038]图2为一个实施例中实时虚拟场景中碰撞体之间碰撞探测的方法及装置的应用环 境示意图。如图2所示，该应用环境包括终端210和服务器220,终端210可为多个。多个终端 210与服务器220进行通信。实时虚拟场景中碰撞体之间碰撞探测的方法可运行于终端210 上，终端210从服务器220上获取虚拟场景数据，终端210获取虚拟场景中第一二叉空间分割 碰撞体和虚拟对象所对应的圆柱碰撞体，对第一二叉空间分割碰撞体和圆柱碰撞体进行碰 撞探测。实时虚拟场景可为实时游戏场景或实时动漫场景等，虚拟对象可为人物或物体。第 一二叉空间分割碰撞体可为人物或物体等。
[0039]图3A为一个实施例中终端210的内部结构示意图。如图3A所示，该终端210包括通 过系统总线连接的处理器、存储介质、内存和网络接口、声音采集装置、显示屏、扬声器和输 入装置。其中，终端的存储介质存储有操作系统，还包括一种实时虚拟场景中碰撞体之间碰 撞的装置，该实时虚拟场景中碰撞体之间碰撞探测的装置用于实现一种实时虚拟场景中碰 撞体之间碰撞探测的方法。该处理器用于提供计算和控制能力，支撑整个终端的运行。终端 中的内存为存储介质中的实时虚拟场景中碰撞体之间碰撞探测的装置的运行提供环境，网 络接口用于与服务器进行网络通信，如发送数据请求至服务器，接收服务器返回的相应数 据等。终端的显示屏可以是液晶显示屏或者电子墨水显示屏等，输入装置可以是显示屏上 覆盖的触摸层，也可以是终端外壳上设置的按键、轨迹球或触控板，也可以是外接的键盘、 触控板或鼠标等。该终端可以是手机、台式计算机、平板电脑或者个人数字助理等。本领域 技术人员可以理解，图3A中示出的结构，仅仅是与本申请方案相关的部分结构的框图，并不 构成对本申请方案所应用于其上的终端的限定，具体的终端可以包括比图中所示更多或更 少的部件，或者组合某些部件，或者具有不同的部件布置。
[0040]图3B为一个实施例中服务器220的内部结构示意图。如图3B所示，该服务器包括通 过系统总线连接的处理器、存储介质、内存、网络接口、显示屏、输入装置。其中，该服务器的 存储介质存储有操作系统、数据库和实时虚拟场景中碰撞体之间碰撞的装置，数据库中存 储有虚拟场景数据等，该实时虚拟场景中碰撞体之间碰撞探测的装置用于实现适用于服务 器的一种实时虚拟场景中碰撞体之间碰撞探测的方法。该服务器的处理器用于提供计算和 控制能力，支撑整个服务器的运行。该服务器的内存为存储介质中的实时虚拟场景中碰撞 体之间碰撞探测的装置的运行提供环境。该服务器的显示屏可以是液晶显示屏或者电子墨 水显示屏等，输入装置可以是显示屏上覆盖的触摸层，也可以是终端外壳上设置的按键、轨 迹球或触控板，也可以是外接的键盘、触控板或鼠标等。该服务器的网络接口用于据以与外 部的终端通过网络连接通信，比如接收终端发送的数据交互请求以及向终端返回数据等。 服务器可以用独立的服务器或者是多个服务器组成的服务器集群来实现。本领域技术人员 可以理解，图3B中示出的结构，仅仅是与本申请方案相关的部分结构的框图，并不构成对本 申请方案所应用于其上的服务器的限定，具体的服务器可以包括比图中所示更多或更少的 部件，或者组合某些部件，或者具有不同的部件布置。
[0041] 在其他应用环境中，可只包括终端210或服务器220,即实时虚拟场景中碰撞体之 间的碰撞探测的方法可只需运行于终端或服务器上，例如单机的实时游戏场景或实时动漫 场景中虚拟对象的移动等。用户在终端上运行下载的单机游戏或测试人员在服务器上测试 单机游戏等。
[0042] 为了便于探测碰 撞体之间碰撞，在虚拟场景中，表示玩家控制的虚拟角色和其他 一些移动物体(如手雷、摄像机等)都是Actor类及其子类的对象，为此采用轴对齐进行碰撞 探测。为了改变虚拟角色的碰撞体，修改Actor类，让虚拟角色使用圆柱碰撞体，非角色 Actor使用轴对齐包围盒进行碰撞探测。在虚拟场景中，场景对象主要有两种，即包括BSP场 景对象和Component场景对象。按照不同的场景对象分类存储，即将对象分为BSP或 Component。在碰撞探测时，米用碰撞探测的入口函数UworId: :MoveActor()按照场景对象 分类做粗裁剪，判断该分类哪些对象可能会和传入的Actor对象碰撞体发生碰撞，然后再做 精细碰撞探测并获得返回结果。其中，粗裁剪是指做粗碰撞。精细碰撞是指按照下面所述实 时虚拟场景中碰撞体之间碰撞探测的方法实现圆柱碰撞体与BSP碰撞体（即BSP场景对象） 之间进行精细碰撞探测，碰撞探测结束后，采用Check系列函数将碰撞探测结果汇总给 Uworld: :MoveActor()，由其进一步汇总后用于后续计算，如状态改变、伤害计算等。在BSP 场景对象，以圆柱取代轴对齐包围盒作为传入MoveActor〇的碰撞体。实时虚拟场景可包括 实时游戏场景、实时动漫场景等，不限于此。
[0043] 图4为一个实施例中实时虚拟场景中碰撞体之间碰撞探测的方法的流程图。如图4 所示，一种实时虚拟场景中碰撞体之间碰撞探测的方法，运行于图2的应用环境中，包括以 下步骤：
[0044] 步骤402,获取虚拟场景中虚拟对象所对应的圆柱碰撞体到第一二叉空间分割碰 撞体各个平面的最短距离。
[0045] 本实施例中，首先采用BSP(Binary Space Partitioning，二叉空间分割)方法通 过面将空间划分为"面内"和"面外"来组成形体。采用若干平面将空间切割成若干凸体，然 后凸体之间以布尔运算组合成复杂的形状。采用Cy IinderPushOut ()函数测量圆柱碰撞体 至IjBSP碰撞体平面的最短距离。
[0046] 实时虚拟场景是指实时游戏场景或实时动漫场景等。实时游戏场景表示正在运行 的游戏中的场景。实时动漫场景表示正在运行的动漫中的场景。碰撞探测是指探测碰撞体 之间是否发生碰撞。碰撞发生后产生碰撞响应，即一碰撞体与另一碰撞体碰撞后无法沿原 来的移动方向继续移动调整一碰撞体的移动方向以绕过另一碰撞体或一碰撞体击中另一 碰撞体产生击中响应等。本实施例中，碰撞探测主要是指一碰撞体避免与另一碰撞体碰撞， 调整一碰撞体的移动方向以绕过另一碰撞体。
[0047]图5为三条线组成三角形的示意图。如图5所示，采用左侧的三角形划分空间得到 右侧三条线划分出来的空间，即右侧三条线的"里面"组成了这个三角形的区域，将其扩张 到三维空间，即可得出用面划分空间的情况。
[0048]图6为三维空间中三角锥划分形成的空间示意图。如图6所示，空间被三角锥划分 形成了三角锥里面的区域和外面的区域。
[0049] 第一二叉空间分割碰撞体是采用BSP划分出来的空间，第一二叉空间分割碰撞体 的面为BSP划分出的空间的表面。
[0050] 虚拟对象可为虚拟场景中可以动态运行的人物或物体等。将虚拟对象配置为圆柱 碰撞体。碰撞体是用于计算物体之间是否碰撞的物体，即实际参与碰撞算法计算的物体。碰 撞体的大小可根据虚拟场景中虚拟对象的大小设置，例如虚拟对象为球体，则虚拟对象对 应的圆柱碰撞体的高可设置球体的直径，圆柱体的半径可设置略大于球体的半径大小。因 采用竖直圆柱方式计算碰撞体到BSP平面的距离，比轴对齐包围盒(AABB，Axis Aligned Bounding Box)更短，效果更自然，所以，假设虚拟对象所对应的圆柱碰撞体一定是(世界坐 标系下)竖直圆柱。轴对齐包围盒是指各个边界均与坐标轴平行的包围盒。
[0051 ]对于BSP场景对象来说，首先测量圆柱碰撞体到第一 BSP碰撞体的某个平面的最短 距离。最短距离是指当圆柱碰撞体刚好接触该平面（即平面支撑圆柱碰撞体)时，圆柱碰撞 体的中心点到平面的距离。也就是该虚拟对象所对应的圆柱碰撞体到第一二叉空间分割碰 撞体各个平面的最短距离为该虚拟对象所对应的圆柱碰撞体接触第一二叉空间分割碰撞 体的平面时，该圆柱碰撞体的中心点到接触的该第一二叉空间分割碰撞体的平面的距离。 需要说明的是，平面可以是任意平面，平面可能紧贴圆柱碰撞体的一条线或者只支撑一个 点。
[0052]该获取虚拟场景中虚拟对象所对应的圆柱碰撞体到第一二叉空间分割碰撞体各 个平面的最短距离的步骤包括：
[0053]若虚拟对象所对应的圆柱碰撞体的轴向与第一二叉空间分割碰撞体的平面平行， 且第一二叉空间分割碰撞体的平面紧贴圆柱碰撞体的一条侧边线，则虚拟对象所对应的圆 柱碰撞体到该第一二叉空间分割碰撞体的平面的最短距离为圆柱碰撞体的半径；
[0054] 若第一二叉空间分割碰撞体的平面紧贴圆柱碰撞体的一个点，则获取并根据圆柱 碰撞体的半径、半高及第一二叉空间分割碰撞体的平面的法向量的XYZ坐标分量，得到圆柱 碰撞体到第一二叉空间分割碰撞体的平面的最短距离。
[0055] 具体地，根据圆柱碰撞体的半径、半高及第一二叉空间分割碰撞体的平面的法向 量的XYZ坐标分量，得到圆柱碰撞体到第一二叉空间分割碰撞体的平面的最短距离的计算 公式为先求取法向量的XY坐标分量的平方根与圆柱碰撞体半径的乘积，再求取圆柱碰撞体 的半高与法向量的Z坐标分量的绝对值的乘积，最后求取两个乘积的和得到，计算公式如下 式⑴：
[0057] 式（1)中，S为圆柱碰撞体到第一二叉空间分割碰撞体的平面的最短距离，R为圆柱 碰撞体的半径，X、y、Z为平面的法向量的三个XYZ坐标系下的三个坐标分量，H为圆柱碰撞体 的半高，I z I为法向量的z分量的绝对值。
[0058] 图7为一个实施例中圆柱碰撞体的示意图。如图7所示，采用Cylinder类表示竖直 圆柱，在Cyl inder类里，采用横线72表示Radius (半径），竖线74表示Height，取值为半高（即 圆柱碰撞体高度值的一半）。
[0059]图8为俯视情况下的圆柱碰撞体到BSP平面的最短距离示意图。如图7所示，在俯视 情况下，圆柱陪碰撞体为一个个的圆形，圆形的中点到BSP边(一个平面俯视情况下位一条 边)的垂线段即为圆柱到该BSP平面的距离。在圆柱刚好接触到BSP平面的情况下，得到的距 离即为最短距离。在三维实际情况中，如果是圆柱碰撞体的轴向刚好和BSP平面平行，平面 就紧贴圆柱碰撞体的一条侧边线，这种情况下圆柱碰撞体的半径就是圆柱碰撞体到该BSP 平面的距离。其它情况下平面紧贴圆柱碰撞体的一个点。假设圆柱碰撞体总是竖直向上的， 其半径为R，半高为H，平面的法向量为N(其基向量与圆柱碰撞体坐标空间基向量相同），法 向量的XYZ坐标轴的三个分量为[x，y，z ]，则圆柱碰撞体中心道BSP平面的最短距离采用公 式(1)进行计算得出。
[0060]图9为圆柱碰撞体到BSP碰撞体的各个平面的距离与圆柱碰撞体到BSP碰撞体的实 际距离的差距示意图。如图9所示，圆柱碰撞体到BSP横平面的最短距离采用92表示，圆柱碰 撞体到BSP竖平面的最短距离采用94表示。对于圆柱，即使能够算出圆柱到每个平面的距 离，也不能直接得出圆柱碰撞体到BSP碰撞体的平面之间的拐角处的实际距离，即图中的斜 线96〇
[0061]步骤404,根据该最短距离扩展该第一二叉空间分割碰撞体的各个平面形成第二 二叉空间分割碰撞体。
[0062] 本实施例中，将圆柱碰撞体退化为一个点（即中心点），将BSP碰撞体(第一二叉空 间分割碰撞体)的各个平面向外扩展，扩展长度为圆柱碰撞体到该平面的最短距离，形成新 的BSP碰撞体，即第二二叉空间分割碰撞体。
[0063] 图10为BSP碰撞体的各个平面向外扩展的示意图。如图10所示，第一BSP碰撞体 1002的各个平面分别向外扩展，各个平面向外扩展的距离为圆柱碰撞体到该平面的最短距 离，扩展后形成第二BSP碰撞体1004图中，1006为圆柱碰撞体。
[0064]图11为圆柱碰撞体在第二BSP碰撞体上移动情况的示意图。如图11所示，圆柱碰撞 体退化为点后，沿着扩展后的BSP碰撞体移动在锐角处圆柱碰撞体要走离开锐角较远距离 才能拐弯。
[0065]步骤406,将该第一二叉空间分割碰撞体的轴对齐包围盒进行扩展生成扩展外边 缘包围盒。
[0066]本实施例中，将该第一二叉空间分割碰撞体的轴对齐包围盒进行扩展生成扩展外 边缘包围盒的步骤包括:将该第一二叉空间分割碰撞体的轴对齐包围盒以圆柱碰撞体的中 心点为基准扫描整个第一二叉空间分割碰撞体的轴对齐包围盒，生成扩展外边缘包围盒。 [0067]步骤408,将该生成的扩展外边缘包围盒与该第二二叉空间分割碰撞体取交集。 [0068]图12为第二BSP碰撞体与扩展外边缘包围盒取交集的示意图。如图12所示，以BSP 碰撞体本身的轴对齐包围盒1202为基准，扫描BSP碰撞体的包围盒后扩展出一层外边缘包 围盒1204,然后将扩展外边缘包围盒与第二BSP1206取交集，即可实现让圆柱碰撞体在BSP 碰撞体周围的移动更自然，且节省距离。
[0069]步骤410,将该圆柱碰撞体与该扩展外边缘包围盒与该第二二叉空间分割碰撞体 取交集得到的结果进行 碰撞探测。
[0070]具体地，通过圆柱碰撞体与交集进行碰撞探测来实现圆柱碰撞体与第一二叉空间 分割碰撞体进行碰撞探测。
[0071 ] 上述实时虚拟场景中碰撞体之间碰撞探测的方法，通过将第一二叉空间分割碰撞 体的各个平面向外根据最短距离进行扩展得到第二二叉空间分割碰撞体，且以圆柱碰撞体 的中心点为基准对第一二叉空间分割碰撞体扩展得到扩展外边缘包围盒，将第二二叉空间 分割碰撞体和扩展外边缘包围盒取交集，通过圆柱碰撞体与交集进行碰撞，实现了圆柱碰 撞体与第一二叉空间分割碰撞体的碰撞探测，碰撞探测是为了避免两个碰撞体发生碰撞， 采用圆柱碰撞体与第一二叉空间分割碰撞体的轴对齐包围盒的碰撞探测，相比于传统的碰 撞体以两个轴对齐包围盒进行碰撞探测，不需像轴对齐包围盒一样控制虚拟对象移出整个 身子才能从第一二叉空间分割碰撞体的拐角越过，圆柱碰撞体在拐角处可以平滑的越过， 即只需移出较短的距离即可越过拐角，缩短了移出的距离，在移动速度相同的情况下，提高 了移动效率，且因是平滑的移动，使得操作更流畅。
[0072] 图13为采用圆柱碰撞体碰撞探测使用传统的算法效果和本发明中的碰撞探测的 理论结果示意图。如图13所示，左图为采用圆柱碰撞体按照传统的算法进行碰撞探测，其仍 然需要将圆柱碰撞体移出整个身体然后才能沿着黑色碰撞体底边移动，右图为采用圆柱碰 撞体采用上述实时虚拟场景中碰撞体之间碰撞探测的方法后所能达到的理论结果，圆柱碰 撞体在移动过程中移动的距离较短，移动效率高，且操作流畅。在一个实施例中，上述实时 虚拟场景中碰撞体之间碰撞探测的方法还包括:在将该第一二叉空间分割碰撞体的轴对齐 包围盒进行扩展生成扩展外边缘包围盒的步骤之后，将该扩展外边缘包围盒的四个角分别 添加斜面。
[0073] 其中，该第一二叉空间分割碰撞体中与该扩展外边缘包围盒的斜面对应的平面交 叉线到该斜面的距离为该圆柱碰撞体的半径。
[0074] 通过将扩展外边缘包围盒的四角添加斜面，再得到扩展外边缘包围盒与第二BSP 碰撞体的交集，交集也带有斜面，采用斜面模拟圆角，可进一步方便圆柱碰撞体移过拐角， 进一步缩短了距离，提高了移动效率。
[0075] 图14为一个实施例中扩展外边缘包围盒的四角添加斜面的示意图。如图14所示， 在扩展外边缘包围盒的四个角添加了斜面作为倒角面，即对扩展外边缘包围盒的四个角上 的直角做切割处理形成斜面，直角切割时，切割的部分投影到平面上形成的三角形内的锐 角为45度。
[0076] 在一个实施例中，上述实时虚拟场景中碰撞体之间碰撞探测的方法还包括:将该 第一二叉空间分割碰撞体的轴对齐包围盒进行扩展生成扩展外边缘包围盒的步骤之后，还 包括:将该扩展外边缘包围盒的四个角分别添加圆弧面。
[0077] 其中，该第一二叉空间分割碰撞体中与该扩展外边缘包围盒的圆弧面对应的平面 交叉线到该圆弧面的最短距离为该圆柱碰撞体的半径。
[0078] 通过将扩展外边缘包围盒的四角添加圆弧面，再得到扩展外边缘包围盒与第二 BSP碰撞体的交集，交集也带有圆弧面，采用圆弧面更贴合圆柱碰撞体，可进一步方便圆柱 碰撞体移过拐角，进一步缩短了距离，提高了移动效率。
[0079] 下面结合具体的应用场景说明实时虚拟场景中碰撞体之间碰撞探测的方法的实 现过程，以实时游戏场景为例，圆柱碰撞体为虚拟角色，第一二叉空间分割碰撞体为墙体， 结合图14,其中圆形为圆柱体的二维投影，三角形为第一二叉空间分割碰撞体的二维投影。 碰撞探测的过程包括：
[0080] (1)获取实时游戏场景中虚拟角色所对应的圆柱碰撞体到第一二叉空间分割碰撞 体各个平面的最短距离。
[0081] (2)根据该最短距离扩展该第一二叉空间分割碰撞体的各个平面形成第二二叉空 间分割碰撞体。
[0082] (3)将该第一二叉空间分割碰撞体的轴对齐包围盒进行扩展生成扩展外边缘包围 盒，将该扩展外边缘包围盒的四个角分别添加圆弧面。
[0083] (4)将该生成的扩展外边缘包围盒与该第二二叉空间分割碰撞体取交集。
[0084] (5)将该圆柱碰撞体与该扩展外边缘包围盒与该第二二叉空间分割碰撞体取交集 得到的结果进行碰撞探测。
[0085] 碰撞探测是指探测碰撞体之间是否发生碰撞，发生碰撞后调整圆柱碰撞体原来的 移动方向，绕过第二二叉空间分割碰撞体。
[0086] 圆柱碰撞体投影的圆形同扩展外边缘包围盒与第二二叉空间分割碰撞体所取的 交集进行碰撞探测，即得到圆柱碰撞体的移动路线，如图14所示。
[0087] 图15为一个实施例中实时虚拟场景中碰撞体之间碰撞探测的装置的结构框图。图 15中的实时虚拟场景中碰撞体之间碰撞探测的装置，为实现图4中实时虚拟场景中碰撞体 之间碰撞探测的方法所构建的功能架构，所包含的功能模块的划分不限于本实施例中所列 举的，也可采用其他方式进行划分。如图15所示，一种实时虚拟场景中碰撞体之间碰撞探测 的装置包括距离获取模块1510、扩展模块1520、生成模块1530、取值模块1540、碰撞探测模 块1550。
[0088]距离获取模块1510用于获取虚拟场景中虚拟对象所对应的圆柱碰撞体到第一二 叉空间分割碰撞体各个平面的最短距离。
[0089] 本实施例中，首先采用BSP方法通过面将空间划分为"面内"和"面外"来组成形体。 采用若干平面将空间切割成若干凸体，然后凸体之间以布尔运算组合成复杂的形状。
[0090] 第一二叉空间分割碰撞体是采用BSP划分出来的空间，第一二叉空间分割碰撞体 的面为BSP划分出的空间的表面。
[0091] 虚拟对象可为虚拟场景中可以动态运行的人物或物体等。将虚拟对象配置为圆柱 碰撞体。碰撞体是用于计算物体之间是否碰撞的物体，即实际参与碰撞算法计算的物体。 [0092]该虚拟对象所对应的圆柱碰撞体到第一二叉空间分割碰撞体各个平面的最短距 离为该虚拟对象所对应的圆柱碰撞体接触第一二叉空间分割碰撞体的平面时，该圆柱碰撞 体的中心点到接触的该第一二叉空间分割碰撞体的平面的距离。
[0093]本实施例中，距离获取模块1510还用于若虚拟对象所对应的圆柱碰撞体的轴向与 第一二叉空间分割碰撞体的平面平行，且第一二叉空间分割碰撞体的平面紧贴圆柱碰撞体 的一条侧边线，则虚拟对象所对应的圆柱碰撞体到该第一二叉空间分割碰撞体的平面的最 短距离为圆柱碰撞体的半径；以及
[0094] 若第一二叉空间分割碰撞体的平面紧贴圆柱碰撞体的一个点，则获取并根据圆柱 碰撞体的半径、半高及第一二叉空间分割碰撞体的平面的法向量的XYZ坐标分量，得到圆柱 碰撞体到第一二叉空间分割碰撞体的平面的最短距离。
[0095] 具体地，根据圆柱碰撞体的半径、半高及第一二叉空间分割碰撞体的平面的法向 量的XYZ坐标分量，得到圆柱碰撞体到第一二叉空间分割碰撞体的平面的最短距离的计算 公式为先求取法向量的XY坐标分量的平方根与圆柱碰撞体半径的乘积，再求取圆柱碰撞体 的半高与法向量的Z坐标分量的绝对值的乘积，最后求取两个乘积的和得到，计算公式如下 式⑴：
[0097]式（1)中，S为圆柱碰撞体到第一二叉空间分割碰撞体的平面的最短距离，R为圆柱 碰撞体的半径，X、y、Z为平面的法向量的三个XYZ坐标系下的三个坐标分量，H为圆柱碰撞体 的半高，I Z I为法向量的Z分量的绝对值。
[0098] 扩展模块1520用于根据该最短距离扩展该第一二叉空间分割碰撞体的各个平面 形成第二二叉空间分割碰撞体。
[0099] 本实施例中，将圆柱碰撞体退化为一个点（即中心点），将BSP碰撞体(第一二叉空 间分割碰撞体)的各个平面向外扩展，扩展长度为圆柱碰撞体到该平面的最短距离，形成新 的BSP碰撞体，即第二二叉空间分割碰撞体。
[0100]生成模块1530用于将该第一二叉空间分割碰撞体的轴对齐包围盒进行扩展生成 扩展外边缘包围盒。
[0101] 具体的，生成模块1530还用于将该第一二叉空间分割碰撞体的轴对齐包围盒以圆 柱碰撞体的中心点为基准扫描整个第一二叉空间分割碰撞体轴对齐包围盒，生成扩展外边 缘包围盒。
[0102] 取值模块1540用于将该生成的扩展外边缘包围盒与该第二二叉空间分割碰撞体 取交集。
[0103] 碰撞探测模块1550用于将该圆柱碰撞体与该扩展外边缘包围盒与该第二二叉空 间分割碰撞体取交集得到的结果进行碰撞探测。
[0104] 具体地，通过圆柱碰撞体与交集进行碰撞来实现圆柱碰撞体与第一二叉空间分割 碰撞体进行碰撞。
[0105] 上述实时虚拟场景中碰撞体之间碰撞探测的装置，通过将第一二叉空间分割碰撞 体的各个平面向外根据最短距离进行扩展得到第二二叉空间分割碰撞体，且以圆柱碰撞体 的中心点为基准对第一二叉空间分割碰撞体扩展得到扩展外边缘包围盒，将第二二叉空间 分割碰撞体和扩展外边缘包围盒取交集，通过圆柱碰撞体与交集进行碰撞，实现了圆柱碰 撞体与第一二叉空间分割碰撞体的碰撞探测，碰撞探测是为了避免碰撞体碰撞，采用圆柱 碰撞体与第一二叉空间分割碰撞体的轴对齐包围盒的碰撞探测，相比于传统的碰撞体以两 个轴对齐包围盒进行碰撞探测，不需像轴对齐包围盒一样控制虚拟对象移出整个身子才能 从第一二叉空间分割碰撞体的拐角越过，圆柱碰撞体在拐角处可以平滑的越过，即只 需移 出较短的距离即可越过拐角，缩短了移出的距离，在移动速度相同的情况下，提高了移动效 率，且因是平滑的移动，使得操作更流畅。
[0106] 图16为一个实施例中实时虚拟场景中碰撞体之间碰撞探测的装置的结构框图。如 图16所示，一种实时虚拟场景中碰撞体之间碰撞探测的装置，除了包括距离获取模块1510、 扩展模块1520、生成模块1530、取值模块1540、碰撞探测模块1550，还包括切割模块1560。
[0107] 切割模块1560用于将该第一二叉空间分割碰撞体的轴对齐包围盒进行扩展生成 扩展外边缘包围盒之后，将该扩展外边缘包围盒的四个角分别添加斜面。
[0108] 其中，该第一二叉空间分割碰撞体中与该扩展外边缘包围盒的斜面对应的平面交 叉线到该斜面的距离为该圆柱碰撞体的半径。
[0109] 通过将扩展外边缘包围盒的四角添加斜面，再得到扩展外边缘包围盒与第二BSP 碰撞体的交集，交集也带有斜面，采用斜面模拟圆角，可进一步方便圆柱碰撞体移过拐角， 进一步缩短了距离，提高了移动效率。
[0110] 图17为另一个实施例中实时虚拟场景中碰撞体之间碰撞探测的装置的结构框图。 如图17所示，一种实时虚拟场景中碰撞体之间碰撞探测的装置，除了包括距离获取模块 1510、扩展模块1520、生成模块1530、取值模块1540、碰撞探测模块1550,还包括分割模块 1570〇
[0111 ]分割模块1570用于将该第一二叉空间分割碰撞体的轴对齐包围盒进行扩展生成 扩展外边缘包围盒之后，将该扩展外边缘包围盒的四个角分别添加圆弧面。
[0112] 其中，该第一二叉空间分割碰撞体中与该扩展外边缘包围盒的圆弧面对应的平面 交叉线到该圆弧面的最短距离为该圆柱碰撞体的半径。
[0113] 通过将扩展外边缘包围盒的四角添加圆弧面，再得到扩展外边缘包围盒与第二 BSP碰撞体的交集，交集也带有圆弧面，采用圆弧面更贴合圆柱碰撞体，可进一步方便圆柱 碰撞体移过拐角，进一步缩短了距离，提高了移动效率。
[0114] 本领域普通技术人员可以理解实现上述实施例方法中的全部或部分流程，是可以 通过计算机程序来指令相关的硬件来完成，所述的程序可存储于一非易失性计算机可读取 存储介质中，该程序在执行时，可包括如上述各方法的实施例的流程。其中，所述的存储介 质可为磁碟、光盘、只读存储记忆体(Read-Only Memory，ROM)等。
[0115] 以上所述实施例仅表达了本发明的几种实施方式，其描述较为具体和详细，但并 不能因此而理解为对本发明专利范围的限制。应当指出的是，对于本领域的普通技术人员 来说，在不脱离本发明构思的前提下，还可以做出若干变形和改进，这些都属于本发明的保 护范围。因此，本发明专利的保护范围应以所附权利要求为准。
【主权项】
1. 一种实时虚拟场景中碰撞体之间碰撞探测的方法，包括以下步骤： 获取虚拟场景中虚拟对象所对应的圆柱碰撞体到第一二叉空间分割碰撞体各个平面 的最短距离； 根据所述最短距离扩展所述第一二叉空间分割碰撞体的各个平面形成第二二叉空间 分割碰撞体； 将所述第一二叉空间分割碰撞体的轴对齐包围盒进行扩展生成扩展外边缘包围盒； 将所述生成的扩展外边缘包围盒与所述第二二叉空间分割碰撞体取交集； 将所述圆柱碰撞体与所述扩展外边缘包围盒与所述第二二叉空间分割碰撞体取交集 得到的结果进行碰撞探测。2. 根据权利要求1所述的方法，其特征在于，将所述第一二叉空间分割碰撞体的轴对齐 包围盒进行扩展生成扩展外边缘包围盒的步骤之后，所述方法还包括： 将所述扩展外边缘包围盒的四个角分别添加斜面。3. 根据权利要求2所述的方法，其特征在于，所述第一二叉空间分割碰撞体中与所述扩 展外边缘包围盒的斜面对应的平面交叉线到所述斜面的距离为所述圆柱碰撞体的半径。4. 根据权利要求1所述的方法，其特征在于，将所述第一二叉空间分割碰撞体的轴对齐 包围盒进行扩展生成扩展外边缘包围盒的步骤之后，所述方法还包括： 将所述扩展外边缘包围盒的四个角分别添加圆弧面。5. 根据权利要求4所述的方法，其特征在于，所述第一二叉空间分割碰撞体中与所述扩 展外边缘包围盒的圆弧面对应的平面交叉线到所述圆弧面的最短距离为所述圆柱碰撞体 的半径。6. 根据权利要求1所述的方法，其特征在于，所述虚拟对象所对应的圆柱碰撞体到第一 二叉空间分割碰撞体各个平面的最短距离为所述虚拟对象所对应的圆柱碰撞体接触第一 二叉空间分割碰撞体的平面时，所述圆柱碰撞体的中心点到接触的所述第一二叉空间分割 碰撞体的平面的距离。7. 根据权利要求1所述的方法，其特征在于，所述获取虚拟场景中虚拟对象所对应的圆 柱碰撞体到第一二叉空间分割碰撞体各个平面的最短距离的步骤包括： 若虚拟对象所对应的圆柱碰撞体的轴向与第一二叉空间分割碰撞体的平面平行，且第 一二叉空间分割碰撞体的平面紧贴圆柱碰撞体的一条侧边线，则虚拟对象所对应的圆柱碰 撞体到所述第一二叉空间分割碰撞体的平面的最短距离为圆柱碰撞体的半径； 若第一二叉空间分割碰撞体的平面紧贴圆柱碰撞体的一个点，则获取并根据圆柱碰撞 体的半径、半高及第一二叉空间分割碰撞体的平面的法向量的XYZ坐标分量，得到圆柱碰撞 体到第一二叉空间分割碰撞体的平面的最短距离。8. 根据权利要求1所述的方法，其特征在于，将所述第一二叉空间分割碰撞体的轴对齐 包围盒进行扩展生成扩展外边缘包围盒的步骤包括： 将所述第一二叉空间分割碰撞体的轴对齐包围盒以圆柱碰撞体的中心点为基准扫描 整个所述第一二叉空间分割碰撞体的轴对齐包围盒，生成扩展外边缘包围盒。9. 一种实时虚拟场景中碰撞体之间碰撞探测的装置，其特征在于，包括： 距离获取模块，用于获取虚拟场景中虚拟对象所对应的圆柱碰撞体到第一二叉空间分 割碰撞体各个平面的最短距离； 扩展模块，用于根据所述最短距离扩展所述第一二叉空间分割碰撞体的各个平面形成 第二二叉空间分割碰撞体； 生成模块，用于将所述第一二叉空间分割碰撞体的轴对齐包围盒进行扩展生成扩展外 边缘包围盒； 取值模块，用于将所述生成的扩展外边缘包围盒与所述第二二叉空间分割碰撞体取交 集； 碰撞探测模块，用于将所述圆柱碰撞体与所述扩展外边缘包围盒与所述第二二叉空间 分割碰撞体取交集得到的结果进行碰撞探测。10. 根据权利要求9所述的装置，其特征在于，所述装置还包括： 切割模块，用于将所述第一二叉空间分割碰撞体的轴对齐包围盒进行扩展生成扩展外 边缘包围盒之后，将所述扩展外边缘包围盒的四个角分别添加斜面。11. 根据权利要求10所述的装置，其特征在于，所述第一二叉空间分割碰撞体中与所述 扩展外边缘包围盒的斜面对应的平面交叉线到所述斜面的距离为所述圆柱碰撞体的半径。12. 根据权利要求9所述的装置，其特征在于，所述装置还包括： 分割模块，用于将所述第一二叉空间分割碰撞体的轴对齐包围盒进行扩展生成扩展外 边缘包围盒之后，将所述扩展外边缘包围盒的四个角分别添加圆弧面。13. 根据权利要求12所述的装置，其特征在于，所述第一二叉空间分割碰撞体中与所述 扩展外边缘包围盒的圆弧面对应的平面交叉线到所述圆弧面的最短距离为所述圆柱碰撞 体的半径。14. 根据权利要求9所述的装置，其特征在于，所述虚拟对象所对应的圆柱碰撞体到第 一二叉空间分割碰撞体各个平面的最短距离为所述虚拟对象所对应的圆柱碰撞体接触第 一二叉空间分割碰撞体的平面时，所述圆柱碰撞体的中心点到接触的所述第一二叉空间分 割碰撞体的平面的距离。15. 根据权利要求9所述的装置，其特征在于，所述距离获取模块还用于若虚拟对象所 对应的圆柱碰撞体的轴向与第一二叉空间分割碰撞体的平面平行，且第一二叉空间分割碰 撞体的平面紧贴圆柱碰撞体的一条侧边线，则虚拟对象所对应的圆柱碰撞体到所述第一二 叉空间分割碰撞体的平面的最短距离为圆柱碰撞体的半径；以及 若第一二叉空间分割碰撞体的平面紧贴圆柱碰撞体的一个点，则获取并根据圆柱碰撞 体的半径、半高及第一二叉空间分割碰撞体的平面的法向量的XYZ坐标分量，得到圆柱碰撞 体到第一二叉空间分割碰撞体的平面的最短距离。16. 根据权利要求9所述的装置，其特征在于，所述生成模块还用于将所述第一二叉空 间分割碰撞体的轴对齐包围盒以圆柱碰撞体的中心点为基准扫描整个所述第一二叉空间 分割碰撞体的轴对齐包围盒，生成扩展外边缘包围盒。
【专利摘要】本发明涉及一种实时虚拟场景中碰撞体之间碰撞探测的方法和装置。所述方法包括以下步骤：获取虚拟场景中虚拟对象所对应的圆柱碰撞体到第一二叉空间分割碰撞体各个平面的最短距离；根据最短距离扩展第一二叉空间分割碰撞体的各个平面形成第二二叉空间分割碰撞体；将第一二叉空间分割碰撞体的轴对齐包围盒进行扩展生成扩展外边缘包围盒；将所述生成的扩展外边缘包围盒与所述第二二叉空间分割碰撞体取交集；将所述圆柱碰撞体与所述扩展外边缘包围盒与所述第二二叉空间分割碰撞体取交集得到的结果进行碰撞探测。上述实时虚拟场景中碰撞体之间碰撞探测的方法和装置，只需移出较短的距离即可越过拐角，提高了移动效率，且平滑越过，使得操作更流畅。
【IPC分类】G06T19/00, G06T7/00
【公开号】CN105488851
【申请号】CN201510860807
【发明人】匡西尼
【申请人】腾讯科技（深圳）有限公司
【公开日】2016年4月13日
【申请日】2015年11月30日
最新回复(0)