点集求最小包围盒OBB算法_obb包围盒

需求分析

原始需求

在过去的开发中，客户端和服务端都使用的是手动编辑逻辑包围盒，但这是一个费时费力的工作。随着技术发展，骨骼包围盒这种简化编辑流程，表现效果又好的方式应用开来，新的需求也就出来了。

游戏客户端为了表现效果好，使用的是骨骼包围盒，而且是一个持续区间，而服务端并不支持，服务端只支持瞬时的逻辑包围盒。那么服务端在需要做包围盒判定和校验的时候，需要重新再设置一套逻辑包围盒，与客户端形成一一对应。这样又回到了老路上，并不可取。

所以，由骨骼包围盒绘制逻辑包围盒的需求就出来了——将持续一段时间的骨骼包围盒扫过的空间转化为一个瞬时的逻辑包围盒。

分析实现

在客户端，骨骼包围盒分三种——球体、胶囊体、立方体
在服务器，逻辑包围盒分多钟——立方体、圆柱、胶囊体、扇体、球体等

上图展示了其他类型包围盒的契合程度，很明显，带有旋转角度的立方体，也就是OBB是契合度最高的。OBB具有三个维度的长宽高和三个维度的旋转patch，yaw，roll，能够最大程度地还原骨骼包围盒范围，比其他类型的逻辑包围盒冗余是更小的。

那问题转换为如何将球体、胶囊体、立方体转换为立方体OBB，这里分2类讨论。

对球和胶囊体可以归为一类，先将其半径看成是零，算出立方体OBB后再对长宽高加上2倍半径值。那么原始数据就变成了1个点（球变为了点）的集合和2个点和1条线（胶囊体变成了线）的集合。
对立方体，原始数据是8个点和12条线的集合。

如果一个包围盒包含了所有的点，那么必然包含所有点之间的连线。这在数学上非常容易证明。

所以问题转换为点集求最小包围盒OBB的算法问题

执行流程

上图中蓝点为点集，红框为点集的OBB，青框为加上半径后的OBB

按照上述逻辑，流程总结为三步：

1. 通过动态模拟骨骼包围盒在时间段内的运动轨迹，获取轨迹形成的点集和半径
2. 依据点集，按照算法求出最小包围盒OBB
3. 将OBB和半径转换为逻辑包围盒保存

第1步和第3部，逻辑比较简单，就不展开讲了，本文主要讲第2步的算法问题。

算法设计

注：下文所指，都是三维空间，