Cesium原理篇:2最长的一帧之网格划分

时间:2023-03-08 16:19:33

上一篇我们从宏观上介绍了Cesium的渲染过程,本章延续上一章的内容,详细介绍一下Cesium网格划分的一些细节,包括如下几个方面:

  • 流程
  • Tile四叉树的构建
  • LOD

流程

首先,通过上篇的类关系描述,我们可以看到,整个调度主要是update和endFrame两个函数中,前者分工,后者干活。

另外,QuadtreePrimitive类只要来维护整个地球的四叉树,而每一个Tile对应一个QuadtreeTile,另外多说一句QuadtreeTile只负责网格的维护,每一个网格对应的数据(地形&影像)则有GlobeSurfaceTile管理。

初始化的时候,当各类Provider准备就绪后,Cesium就开始构建地球,这个过程都发生在QuadtreePrimitive.prototype.update函数中。在update函数中,通过selectTilesForRendering实现网格的划分和调度。我们先根据时间和状态的变化来描述一下整个流程。

Cesium原理篇:2最长的一帧之网格划分

首先判断是否存在第零层的Tile,也就是整个四叉树的根节点。createLevelZeroTiles函数负责根节点的创建,参数tilingScheme表示地球网格采用的剖分方式,该参数值和地形的投影是一致的,因此只能是WGS1984的经纬度,也就是我们上一篇提到的剖分方式,第零层有两个根节点:

Cesium原理篇:2最长的一帧之网格划分

也就是说无论影像服务采用的是墨卡托的还是经纬度,但Cesium的地球是按照经纬度的剖分方式,和地形数据的规范保持一致。不管怎样,这样我们有了两个QuadtreeTile,一个是L0X0Y0,一个是L0X1Y0。

但此时的Tile只是一个有行列号的空壳,里面并没有实际的数据(needsLoading == true),也不能用于渲染(renderable == false)。作为一个新Tile,他被扔进了两个队列中,一个是_tileReplacementQueue,这个是一个双向链表,来统计所有加载进来的Tile,不过并没有发现它的价值,另一个是_tileLoadQueue,下载队列,该队列中的Tile,则会在下载函数中完成数据的加载,数据下载的过程会在下一篇详细介绍,此处一笔带过。

根据剧情需要,开始下载地形数据和影像数据,这个过程是异步的,当地形数据下载完成后,执行propagateNewLoadedDataToChildren函数。因为要给子节点的地形数据采样(地形中详细介绍),所以会创建出该Tile对应的四个子节点,不然还怎么叫四叉树,全部数据下载完成后就会更新该Tile的状态:

QuadtreeTile.renderable == true;

QuadtreeTile.state == QuadtreeTileLoadState.DONE;

Cesium原理篇:2最长的一帧之网格划分

生命不息,update不止,只是此时,根节点Tile已经整装待发,来到人生的第二个状态。这里判断一下该Tile在当前状态下是否可见,如果可见,则加入到traversalQueue队列,顾名思义,这个队列就是用来遍历四叉树的。一旦traversalQueue不再为空,好戏就开始了。

Cesium原理篇:2最长的一帧之网格划分

如上,是网格调度中最关键的一部分,通过其中的if & else if & else不难看出,一共有三个逻辑:

  • screenSpaceError
    该Tile的精细度是否满足LOD要求,是否不需要请求更精细的层级。如果满足精度要求,则该Tile加入到_tilesToRender渲染队列,如果不满足精度要求,则该if判断为false
  • queueChildrenLoadAndDetermineIfChildrenAreAllRenderable
    如果之前的判断为false,则需要判断该Tile的四个子节点是否可渲染,如果可以渲染,则将子节点加入到traversalQueue中,如果不可渲染,则加入到_tileLoadQueue来下载,这两个队列中的Tile遵循各自的调度流程,此时该else if判断为false
  • else
    如果进入该else的逻辑,则说明该Tile的精度达不到要求,但其子节点还处于不可渲染状态,这时候怎么办?只要先凑合一下,把当前的Tile先放到tilesToRender队列吧,寥胜于无

这三个逻辑都比较清楚,我们先不纠结于内部具体的算法实现,以时间顺序来描述一个简化的网格调度场景:

继续从之前的根节点说起,此时根节点的数据已经加载完毕,该Tile从tileLoadQueue切换到traversalQueue队列,进入到该while循环:

首先发现该Tile0的精度不够(此时Level = 0),需要进一步的请求下一层级的切片Tile1(Level = 1的Tile),然后发现Tile的4个Children子节点还不能渲染,则把这四个节点发到tileLoadQueue(这四个节点将经历和它们父亲一样的经历,然后进入到traversalQueue队列,继续这个while循环),这样,只好先渲染这个根节点,把Tile0加入到tilesToRender渲染队列。

While循环就这样一直判断,未来的某一段时间,Level = 1的节点们各自完成了数据下载的过程,这是再进入到该while循环,就会发生一些不一样的事情了:

首先发现该Tile0的精度不够,需要进一步的请求下一层级的切片Tile1,然后发现Tile的4个Children子节点都可以渲染了,则把可渲染的这四个Tile1加入到traversalQueue,不可渲染的还和以前一样。这样,while循环会遍历traversalQueue队列中的所有Tile,轮到Tile1了,发现这次精度满足要求了,则把Tile1加入到渲染队列tilesToRender,此时,Tile0并没有进入到渲染队列,只是起到了新老接替的作用。

这是一个最简化的过程,但无论调度有多复杂,都符合如上的一个逻辑,万变不离其宗。从根本来说,在渲染和update的过程中,Cesium并不面向过程来推动整个流程,而是面向对象(状态),每一个不同状态的Tile赋予一个不同的职能,各司其职,尽其所能。这样,一个Tile从下载队列到遍历队列,最后到渲染队列,然后交出接力棒,退出渲染队列。所以这个渲染过程本质就是一个状态维护的过程,这个思想来贯彻这个Cesium的各个模块。

Tile四叉树的构建

四叉树,简单而言,就是在当前的Tile上画一个田字格,这样就形成了四个子Tile,level++,整个过程就结束了。

Cesium里面四叉树的构建很简单,一目了然。但难能可贵的是,通过接口设计,并不需要可以的来进行这个过程,而是通过属性接口的设计方,在第一次需要getChildren的时候来构建,我觉得很巧妙。

这样避免了过多的逻辑判断,在需要Children的时候先要判断有没有,当这个链表层级多了,这个判断就很难维护了。集中在一起维护,提高代码重用,方便管理。

实现代码很简单,这里只给出代码片段,实现了一个子节点的构建,记住田字格,相信大家都能够一目了然:

Cesium原理篇:2最长的一帧之网格划分

LOD

下面涉及到LOD时关键的两个算法,第一是判断当前Tile是否满足精度的要求,如果不能满足,则需要继续请求下一级的Tile,满足渲染效果,第二是在Tile从根节点的遍历中,判断当前Tile是否可见。

screenSpaceError

Cesium就是通过该函数来判断是否适可而止,停止网格的进一步剖分。算法很简单,只有下面一句话:

Cesium原理篇:2最长的一帧之网格划分

我们把公式分解一下,先看看height/sseDenominator的涵义:1 height是整个屏幕像素高,而sseDenominator是相机fovy角度的tan值的2倍,如下图所示:

Cesium原理篇:2最长的一帧之网格划分

如上图所示,根据三角函数可知:tan(fov/2) == (height/2) / far;而height/sseDenominator == (height/2) / tan(fov/2) == far;也就是相机距离屏幕中心的像素距离。

而maxGeometricError是地球赤道的周长/像素数,也就是分辨率,可以认为是在Tile不拉伸的情况下(比如一个256的Tile就是按照256的像素显示,而不是被拉伸成300的像素)一个像素代表多少米。(maxGeometricError * height) / sseDenominator == maxGeometricError * (height/sseDenominator),也就是理想情况下,相机距离屏幕中心的米单位距离,我们记作L。

而distance是当前状态下,相机距离该Tile的真实距离,于是L / distance就是一个粗略的拉伸比,如果distance值小于L,说明当前观看的位置distance比真实的位置L要近,则需要更精细的层级效果,而distance是分母,分母越小,该值就越大。换句话说,就是该值越小,说明当前的拉伸越小。

GlobeSurfaceTileProvider.prototype.computeTileVisibility

这个函数主要是判断当前Tile是否可见,里面主要有两个算法:

computeDistanceToTile

判断相机距离Tile的距离。一个Tile在球面上是一个弧面,在TileBoundingBox中分别记录了四个边的法向量和四个顶点的位置,这样,根据每一个边的法向量和相机距离顶点的向量,点乘的结果就是相机的垂直距离,分别计算出四个边的距离,各取东西方向(a),南北方向中的一个(b),再加上相机到地球表面的距离c,sqrt(a^2 + b^2 + c^2),则是相机距离Tile的distance。

computeVisibility

判断该Tile是否在裁剪面的内部,参考上图,可以看到裁剪面有六个面,则在三维中,一个Tile和其中一个面则有三种关系:内部,外部,相交。

Cesium原理篇:2最长的一帧之网格划分

如上是一个简易图,我已经在mspaint中尽力了。红色的是其中的一个平面,而箭头是它法线的方向,这里有五个圆,对应了五种BoundingSphere的情况(Cesium里面抽象了Tile,把他们简化为一个原点+半径的圆球,方便计算,这也是三维中常见的一种思路。)

首先,还是点乘,法向量和绿色直线的点乘,就是该原点距离该plane的垂直距离,这里还有一个方向的问题,也就是当角度>90时,cos值小于0.

结合上图,在x轴以上的圆心,角度小于90,点乘的结果肯定大于0,肯定在plane平面内,而在x轴以下的,角度大于90,点乘结果为负数。这时计算圆心和平面的距离,和该圆的半径比较,则可以轻松的计算出两者的关系。代码如下:

Cesium原理篇:2最长的一帧之网格划分

本篇内容大致如上考虑的篇幅,并没有在这里和大家介绍horizon occlusion这个技术,也是用于Tile裁剪的,因为只是在STK地形时采用这个方式,所以会在地形这一篇中和大家交流,简单说,效果如下(前者不采用,后者采用):

Cesium原理篇:2最长的一帧之网格划分

你会发现采用这个方式的,地球背面,不需要显示的Tile会过滤点,以往这需要计算Tile的法线和相机的角度,比较繁琐,主要是处于性能的考虑,但通过这个方式,可以快速过滤,但在数据层面需要提前准备好,这也是为什么采用STK地形的时候开启该功能的原因,不多解释,下回分解。