秉亮的个人日志


四叉树优化

二维上的二分搜索

2017-03-12

无关

上一篇日志已经是去年 7 月的时候了,一是自己也没养成写日志的习惯,二是这年生活还算充实,遇到大大小小的事情但总体上还算开心。过年时想写一篇但是后来也不知道写写什么,而且手里也还有欠的“债”得还。不过这个“债”已经从两个月又重新开始还起来,争取这个月就把它告一个段落,争取弄个 0.0.1 版本出来。

背景

在公司橱衣柜工具线的敏捷小组做图形前端开发,写吸附逻辑操作时发现之前的算法效率太低。因为在用户操作移动的时候会一直进行碰撞检测,找到碰撞的然后进行对应的吸附适配等操作,而之前的算法就是全局遍历一遍而已。算了一下随着模型的数量的增加,所耗时会占一个运算周期的 30-40%。这是个不小的时间,而碰撞检测这个有很多成熟方法进行减少计算次数。比如最后我采用的四叉树。这是工作产出,所以这里不会出现业务相关代码,也不可能邮件提供。

业务场景

场景一般是房子中的场景,而且现在我们公司也不怎么支持别墅,所以基本上面积比较大,而高度比较低,高度上一般最多分布1-3个柜体,而平面上可以根据户型大小分布几十至上百。考虑到这种情况,所以虽然整个空间是 3D,但是也没有使用游戏中常用于空间分割的八叉树。而实际计算碰撞的是需要使用柜体的 OBB 包围盒,主要瓶颈在于原方法是对所有模型进行了遍历,所以最后采用对模型的 AABB 包围盒建立四叉树,然后初步检测 AABB 包围盒筛选出 AABB 包围盒碰撞的这些柜体,然后遍历筛选出来的结果,一一进行 OBB 包围盒碰撞检测。空间分割的方式理应使期望为 O(N) 变为 O(logN),虽然情况并非如此。

一些四叉树的基本知识

https://en.wikipedia.org/wiki/Quadtree

简单地说就是定好场景边界,然后往里面插入一个节点,如果插入节点数量大于一个设定值,则将这个树拆分成四个子树,然后根据节点的位置,将这些节点放到对应子树中,删掉节点的时候则可以选择将节点聚合。拆分和聚合都是可以写成递归操作。总体上维持差不多这么一个状态。

可以搜索 “quadtree visualization”,能找到不少可视化的解释四叉树思想的网页。

以矩形作为节点的四叉树

四叉树的较简单形式是以座标点作为节点的点四叉树,并不能用在场景中,因为场景中有大大小小的柜子,跨度很大,所以使用矩形四叉树,但是矩形四叉树又有两种主要形式,主要区别在于如果一个节点的矩形不能完全放入四个子树时怎么办。

  1. 将这个节点就放在这个树节点处,不再细分。
  2. 只要这个节点的矩形和某一个子树矩形相交,就放个引用在那个子树里。

这两个方案都是可行的,主要区别在于:方案1的树构造出来的会更小,因为每一个节点在树中只有一个引用,而且在细分和聚合的时候的工作量少;而方案2在查找时会相比方案1少一些运算,比如在树根的第一个分割点上刚好有一个比较小的节点,那么如果使用方案1的话对任意位置的碰撞查询都会向上找到这个节点进行碰撞检测。

1和2的性能在当前使用场景(模型大多数放在不冲突的地方,不太可能出现很多模型都重叠在一起而且重叠在分割点上)中性能应该处于同一个数量级,理应只有少数偏差,考虑到写起来方便,于是采用方案1(真的需要方案2的时候换起来也方便)。

结果

拿了一个大概有 30 个模型左右的户型测试吧。使用老方法帧率大概在 4.3FPS,使用四叉树优化后帧率大概在 5.5FPS,帧率看上去比较惨:-),但看比例还行,总体帧率上升了大约 25%。在具体优化的那个函数中使用老方法平均每次需要 18ms,而使用四叉树优化之后平均只要 0.4ms,速度提升了 45 倍。

而场景中柜子越多则使用四叉树优化的效果越明显,我暂时也没有去测试具体情况吧。从上面那个测试结果来说使用四叉树优化还是卓有成效的。