性能优化之事件响应与相交算法

性能优化之事件响应与相交算法

故事背景

为了解决用户使用过程中的体验问题,我们团队进行了走访用户调研,在调研过程中发现:在一些配置较差的机器上存在拖动模型异常卡顿的情况。

QQ20190401-152442-HD.gif

从以上的交互动图中可以观察发现,在已经实现的功能中,家具拖动过程中包含有几种交互:

  • 家具移动
  • 框选多个家具移动
  • 与周围家具吸附交互
  • 与墙体吸附交互
  • 与墙体碰撞功能(在家具未完全移动出墙体时,保持模型在房间内)
  • 与其他家具叠放
  • 实时计算显示家具周围标注(实现模型周边感应功能

在这么多交互同时运行中,肯定会出现一些计算过程,那么如何能够在不影响原有交互的基础上,实现更加高效低耗的实现过程呢?

发现问题

首先,优化,就需要先知道我们目前的耗时及计算过程是什么样的。

模型移动过程中FPS

移动过程中事件调用过程

在这一段调用过程中,可以看到几个问题:

  • 有多次事件调用超出50ms
  • 家具移动事件平均调用耗时127ms!
  • 帧率调到14.7 FPS

从事件调用嵌套链中可以看出,主要耗时方法包含两部分:

  1. calculateAdsorbPos()计算吸附后的偏移位置
  2. Vector3D.copy()3D 向量改变后,对事件响应过程

在第二部分时间占比较高的方法中,看到一次 Move 时间竟然会出现两次getNearLines()

另外在hitWithWall()getNearLines()的方法中都调用了一个计算多边形重合的方法,而这个方法的耗时较为严重。

那么接下来,我们需要优化的优先级和问题就很明确了:

  1. 找出调用两次耗时方法的原因,解决它
  2. 找出更优的多边形相交的方法,替换它

解决过程

Mobx Action 使用不当导致响应调用两次

看到getNearLines()调用两次,我脑海里想到的第一个可能就是:是不是 x,y 的改变分别触发了事件的响应?

之前有介绍到,在项目中,我们采取了Mobx+数据模型的设计思路完成整个交互动作。也就是说,在模型移动的Event中,只需要算出最终模型的移动位置,至于后面的模型之后的 4 条标注线,则是由另外一个Event观察模型的位置变化自动触发计算的。

而触发这次计算的方法就是Vector3D.copy(),在这个方法中又调用了Vector3D.set(x,y,z),这个方法中分别为 x,y,z 做了赋值操作,代码如下:

import { observable } from "mobx";

// 有部分删减

export default class Vector3D {
  @observable
  public x: number;
  @observable
  public y: number;
  @observable
  public z: number;

  public copy(v: Vector3D) {
    this.set(v.x, v.y.v.z);
  }

  public set(x, y, z) {
    this.x = x;
    this.y = y;
    this.z = z;
  }
}

显然,如果是这样的调用过程,如果有一个事件方法需要在x,y,z任意一个状态改变时就触发,那么就会同时调用 3 次。

所以我们需要有一个装饰器(柯里化方法),来处理一个action中对多个状态的改变,节流合并所dispatch调用的公共方法。

其实在 Mobx 中,已经有这样的方法Action,这里之所以会出现这样的问题,其实就是忽略了对Action的定义。

看到 Mobx 的官方文档:

Mobx action 说明

这里的说明的意思就是,action中尤其对transaction会在无感知的情况下产生巨大的性能优势。action将会把一批变化状态作为一个计算属性处理,并且在整个action执行完成后运行。

简单来讲就是,action将会用柯里化的方式,在action结束后合并统一处理事件响应,来大大提高reaction性能!

柯里化(英语:Currying):a function and returns a function

所以,需要将set,copy这样的方法加入 Mobx 提供的action即可解决问题:

import { action, observable } from "mobx";

// 有部分删减

export default class Vector3D {
  @observable
  public x: number;
  @observable
  public y: number;
  @observable
  public z: number;

  // action.bound 自动处理this作用域
  @action.bound
  public copy(v: Vector3D) {
    this.set(v.x, v.y.v.z);
  }

  @action.bound
  public set(x, y, z) {
    this.x = x;
    this.y = y;
    this.z = z;
  }
}

经过这样处理,可以再次调试查看效果,发现之前调用两次的getNearLine()已经变成了一次调用,直接节省耗时30ms!

另外,这只是我们在这个方法之间中的优化处理,作为一个三维向量状态的类。Vector3D被大量使用到需要位置信息的订阅事件中。如果getNearLines()就这样的问题,就意味着其他 N 多的响应事件同样会有类似问题。

这里因为是在 2D 下的交互,只订阅了x,y的两个状态,所以响应了两次事件。那么如果在 3D 下那么就可能会响应 3 次订阅事件。

所以,这次对基类的优化,很有可能隐形为所有使用到位置信息订阅的事件响应都节省了至少一遍响应调用。

处理Mobx action后的效果

多边形是否相交算法优化

在优化了32ms的时间后,依旧不满足用户对流畅的感知,为了让整体交互体验良好,即使复杂动作也需要保持帧率在40FPS以上,换算下来也就是单次方法耗时应该<=25ms

Well, target is 25ms !!

而目前现状是95ms,距离我们的目标还有。。。。70ms

好吧,继续拉大调用栈,看看还有没有什么地方可以继续努力的,看到在下面的方法中存在多个判断多边形相交的方法intersectPolygon(),而每个这样的方法调用都需要耗时3ms左右。

getNearLines 调用栈

calculateAdsorbPos 调用栈

所以,进一步优化就需要定位到这里的intersectPolygon究竟为何调用,是否有更优解法。

查看到getNearLines()的方法实现中有这样一段代码:

if (!!srcPolygon.intersectPolygon(comparePolygon.boundingBox.polygon)) {
  return false;
}

return !!polygon.intersectPolygon(comparePolygon);

也就是说,在业务逻辑中,需要使用到该方法的作用是:判断对应多边形是否相交。

但该方法的返回值是:返回两个多边形的相交部分的多边形。

两者是有区别的,他们的计算复杂度完全不同。只需要判断两多边形是否相交完全有更快的方法实现,所以目标就变为实现一个判断多边形是否相交的高效算法。

实现过程我就不在此赘述了,总之,我重新实现了一个isIntersectPolygon(polygon:Polygon2D)的方法,对于 5 点以内的多边形,最长耗时(最差判断)0.75ms

最终,在最后的移动家具测试过程中,成功将单次调用时间稳定在22ms的平均值左右。

性能对比

Before

After

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×