Dec 31

在JS中执行高性能的几何数学运算(非webgl情况)

Lrdcq , 2020/12/31 19:03 , 程序 , 閱讀(449) , Via 本站原創
在js完成驱动式动画,复杂动效,物理引擎,与3d场景数据预处理(比如threejs)的过程中,不可避免的会遇到需要在js中执行几何数学运算的场景。具体来说,比如操作css的transform样式,直接计算输出matrix或者matrix3d的值(比如https://developer.mozilla.org/en-US/docs/Web/API/WebGL_API/Matrix_math_for_the_web写的这样)。只是一两个matrix还好,如果在dom中搭建了复杂的动效场景,并且动画效果需要逐帧驱动(requestAnimationFrame驱动)效果实效,并且保持在合理的60fps,几何数学运算的性能就相当关键了。

实际主要涉及到的运算方式:

- 二维/三维点与线的表示与相关计算(距离,碰撞测试类,骨骼/图像扭曲类)
- 三维空间向量运算(3d空间预运算,数据模型化3d空间搭建,)

涉及到的可用工具

一般涉及到图形图像相关的js lib相对来多都较大,动辄几大百kn,因此基本会自带数学库,比如three.js:
點擊在新視窗中瀏覽此圖片

另外,说到数学库,一定会提到math.js。关注mathjs和threejs的实现,除了mathjs兼容性好一些之外,其在常用范围内的数据储存结构(数据/二维数组),对象操作可变性,熟悉暴露,计算算法上基本一致。非要说细节的话,mathjs代码复杂度稍高,而threejs中的代码因为聚焦其内部使用,逻辑单一并简洁一些。

a. 因此我们首要提到的可用工具就是math.js与类似于three.js的自备精简几何数学库。

除了第三方工具之外,我们有没有什么浏览器内建对象能帮助我们完成几何运算任务呢?搜索一番还真有:

在Webkit文档中,我们注意到存在对象WebKitCSSMatrix(但是文档描述的getComputedStyle(element).webkitTransform()是无法获得该对象的),WebKitPoint等,同时DOM对象中也存在DOMPoint,DOMMatrix,DOMRect,DOMQuad,经查,Dom开头这一套对象均来自Geometry Interfaces Module Level 1(https://drafts.fxtf.org/geometry/)并且WebKit的对象看起来也在逐步迁移到这一套对象上,那可以视为虽然还在中期状态,浏览器提供了一套内建几何对象帮助我们完成几何操作。文档上的描述也是这样:
This specification provides basic geometric interfaces to represent points, rectangles, quadrilaterals and transformation matrices that can be used by other modules or specifications.

目前包括css,webvr,svg等部分都有涉及。

b. 因此DOM API也提供了一套内建对象的几何数学工具可以解决我们的问题。

还有其他方式么?从理论上图形学运算能力最强的莫过于GPU,因此:

c. 第三种工具是通过Webgl相关工具丢给Compute Shader进行几何运算。(目前不可行)

当然,这个方式目前判断可行性极差,基于以下几个因素:

- 目前Compute Shader对应的Webgl2.0或者直接上WebGPU再各个浏览器中均为实验状态,实际上不可真实使用
- 使用Compute Shader必然有较高的通信与类型转换成本的,然而我们实际场景(如上说的动画,物理引擎等)涉及到的cpu几何运算是密度大,但是单次计算的复杂度并不高,所以丢给GPU计算显然成本相当高,并不适合这样去使用。

d. 第四种方式,可能会成为未来10年展望的趋势,则是将数学/几何运算提升为js这门语言的第一公民。(目前不可行)

什么叫做js一等公民呢?先不说math.js那样js基础类型来表示数据结构,js函数来表示运算操作,就算DOMMatrix这样的对象,在js中typeof出来也是object。那是因为它在js中确实就是一个object,只是各个属性和方法关联到了一个单独的native对象而已而不是js中就存在一个DOMMatrix类型的对象。简单的说如果哪天我们能typeof出来一个matrix类型,这个matrix的地位等同于number,string,它就是一等公民了。如果matrix+matrix能合理运算并得到一个matrix,矩阵运算也是一等公民了。

听起来遥不可及的事情,不过真的有相关提案与实现。就是大名鼎鼎的quickjs(https://bellard.org/quickjs/)。作为一个胶水js引擎,quickjs通过实现这几个提案来实现数学对象提升为一级公民:

- Decimal proposal(https://github.com/tc39/proposal-decimal),将大数提升为一级公民,看起来是这样的:
點擊在新視窗中瀏覽此圖片

- Operator overloading(https://github.com/tc39/proposal-operator-overloading),将矩阵运算等特殊几何运算提升为一级公民,看起来是这样的:
點擊在新視窗中瀏覽此圖片

当然,现在也仅有quickjs尝试实现了相关js能力,因此从web开发的角度,以上更多是对未来美好的期许了。

可用工具对比

因此我们剩下的可用工具只有js自己实现与目前可用的DOM工具了。实际业界开源代码上统计,实际上即使DOMAPI的对象在对接各种css/js功能时可能会更方便,目前也几乎没人使用。因此怀疑是性能问题,实际进行了定性与定量分析。

定性分析(目测):

- DOMAPI中的几个对象属性,提供方法和一般的jslib提供的方法基本一致,覆盖了所有基本几何运算操作。当然jslib一般提供的helper类方法会更多,但是不构成成为负担的原因。

- DOMAPI的几个对象的构造器对浏览器的功能有高度兼容性,例如:
點擊在新視窗中瀏覽此圖片

这是一般jslib不会提供的(自己去拼接)。

- 大部分对象的操作都是不可变对象,比如DOMMatrix的绝大部分操作都是来自基类DOMMatrixReadOnly的,操作结果也是生产新对象。而各个jslib的设计思路也完全一致。延展来看,其他语言的几何数学库基本上也是类似的表现。

结论上,DOMAPI与jslib的能力与表现看起来不分伯仲,并没有明显应该使用某一个方案的倾向结论。

定量分析:采用可对比范围内最复杂/频繁/并且的对Matrix进行连续乘法:
    const matrix_0 = math.matrix([[0.5, 0.3, 0.3, 0.3], [0.3, 0.5, 0.3, 0.3], [0.3, 0.3, 0.5, 0.3], [0, 0, 0.1, 1]]);
    const matrix_tomultiply = math.matrix([[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1]]);
    let answer = matrix_0;
    console.time('math.js');
    for (let i = 0; i < 1000000; i++) {
      answer = math.multiply(answer, matrix_tomultiply)
    }
    console.timeEnd('math.js');
    //-----------------
    const matrixNative_0 = new DOMMatrix("matrix3d(0.5, 0.3, 0.3, 0.3, 0.3, 0.5, 0.3, 0.3,  0.3, 0.3, 0.5, 0.3, 0, 0, 0.1, 1)");
    const matrixNative_tomultiply = new DOMMatrix("matrix3d(1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1)");
    let answerNative = matrixNative_0;
    console.time('DOMMatrix');
    for (let i = 0; i < 1000000; i++) {
      answerNative = answerNative.multiply(matrixNative_tomultiply);
    }
    console.timeEnd('DOMMatrix');

结论数据:
點擊在新視窗中瀏覽此圖片

结论:

- 明显直接在JS中计算比使用DOMAPI计算高很多,因此我们还是保持直接在pureJS中进行几何数学计算

- 以上代码除了高强度计算,存在不可变数学对象频繁创建销毁的情况。这在实际使用中相当常见。

- 同时js的多次采样耗时变化比较大,可能和gc有关。DOMAPI对象既然具备native对象,应该是规律回收或者实时销毁的(和dom element对象内存管理表现一致)。

- DOMAPI对象的耗时高同样有可能是因为二级公民native对象的创建成本相对于纯js对象高(但是维护成本由于没有gc的缘故会更低)。同时目前js和native纯数字计算成本差距并不会太大。
关键词:js , dom , dommatrix
logo