Cesium原理篇：3最长的⼀帧之地形（3：STK）有了之前⾼度图的基础，再介绍STK的地形相对轻松⼀些。STK的地形是TIN三⾓⽹的，基于特征值，坦⽩说，相⽐STK⽽⾔，⾼度图属于淘汰技术，但⾼度图对数据的要求相对简单，⽽且⽀持实时构建⽹格，STK具有诸多好处，但确实有⼀个不⾜，计算量⽐较⼤，所以必须预先⽣成。当然，Cesium也提供了⼀个Online的免费服务，不过因为是国外服务器，所以性能和不稳定因素都不⼩。好的东西⾃然得来不易，所以不同的层次，根据具体的情况选择不同的⽅案，技术并不是唯⼀决定因素，甚⾄不是主要因素。
CesiumTerrainProvider提供了⾼度图和STK两种地形服务。但⽬前只提供后者的在线服务，前者其实只是在维护了(HeightmapTesllator在计算Horizon Cull中有⼀处笔误，错把relativeToCenter写成relativetoCenter了，⼀直到⽬前最新的1.25版本还没有修改，说明已经不重视了)。
下⾯，我们通过CesiumTerrainProvider类，来详细介绍⼀下STK地形的细节。
layer.json
⾸先，CesiumTerrainProvider在初始化的时候会请求layer.json，这相当于⼀个配置⽂件，⽤来获取地形数据的基本属性信息，截图如下：
如上是STK对应的layer.json中的属性，包括版个性昵称
本，format(⾼度图 or STK)，extension扩展(是否包括法
线和⽔⾯)，层级数和范围。最主要的是available，⾥⾯记录有地形的切⽚数据，这样，如果该Tile的地形均为0，减少不必要的terrain请求。⽐如Level 11，在[startX,startY]到[endX,endY]范围下存在地形数据。当然，提供了TileDataAvailable来进⾏这个判断。
STK Structure
上⼀篇，我们讲到createHeightmapTerrainData⽅法，参数对应的是⼀张⾼度图，⾥⾯就是记录⾼程值的点串。⽽createQuantizedMeshTerrainData则不同，它对应的不是原始的，简单抽稀的点串，⽽是已经预处理的，缓存在服务器中的TIN地形格⽹。所以，⾸先我们要清楚该terrain⽂件的数据结构。
⾸先，在Cesium中是以ArrayBuffer形式传输的，也就是⼆进制形式。它的Header结构如下：
这个头介绍了该Tile的⼤概的位置和范围，之后就是该Tile对应的TIN三⾓⽹的顶点数据，该数据⾥⾯⽤到了zigzag编码⽅式，后⾯会具体介绍：
接要下雨了教案
着就是顶点索引了，采⽤了high water mark编码⽅式，同样后⾯⼀并介绍：
下⾯则是裙边，上⼀篇也提到过，主要就是勾勒⼀下四周，保证⽆缝合成，后⾯会给出⼀个STK的wireframe⽅式，让⼤家看清楚⾼度图和STK的差别，也体验⼀下STK数据的简单⾼效：
最后就是⼀些扩展属性，主要是⽔⾯和法线（光照效果），这⾥就不在赘述。有了这个数据结构，我们就可以按这个结构来解析对应的ArrayBuffer了，这个过程就不在此介绍了，对ArrayBuffer不了解的，可以参考《》。数据全部解析完后，我们知道了该Tile的范围以及⾼度的最⼤最⼩值，通过OrientedBoundingBox.fromRectangle⽅法，可以构造出OrientedBoundingBox。思路和中的介绍⼀样。最终，如上的参数构造了QuantizedMeshTerrainData对象。
Decode
Cesium在顶点数据中采⽤了zigzag的编码⽅式，在顶点索引中采⽤了high water mark⽅式，两个编码的解码⽅式都很简单，算法如下：
解码算法⽐较简单，但肯定会有⼀个疑问，为什么需要编码，还需要解码，这不是多此⼀举吗？当然，这样做是有原因的，或者说，通过这种⽅式可以更⾼效的压缩数据（整数）。当然要理解这些，还得先从varint这个类型说起。
Varint编码
Varint 是⼀种紧凑的表⽰数字的⽅法。它⽤⼀个或多个字节来表⽰⼀个数字，值越⼩的数字使⽤越少的字节数。这能减少⽤来表⽰数字的字节数。不过相应的，对于⼤数就要使⽤更多的字节去存储。在统计学上，⼀般消息中的数字以⼩数为主，所以⽤它可以省空间。如下图所⽰：
在⼀些通讯协议职位说明书模板
中，⽐如Google的ProtoBuffer，采⽤varint的⽅式来减少传输。如果整数⼤⼩在256以内，则只需要⼀个字节就可以存储该整数，则可以省去3个字节。因此，为了更好的发挥varint编码的优势，STK中则需要有⼀种策略，保证数值越⼩越好。
⾸先就是ZigZag编码，该编码会将有符号整型映射为⽆符号整型，以便绝对值较⼩的负数仍然可以有较⼩的varint编码值。因为对于负数，最⾼位是1，那么就相当于⼀个很⼤的整数，如果⽤varint，那么就很浪费空间了。ZigZag编码的原理就是按照绝对值⼤⼩来重新解析⼆进制。如下是⼀些具体数值经过zigzag编码后的值，转为⽆符号整型。
另外，对于顶点索引这样的整数，都为正数，⽽且遵赢得仓皇北顾
循⼀定的顺序，是否也能让他们变⼩⼀些，这样对处理后的数进⾏varint编码，也会提⾼顶点索引的压缩⽐。于是就有了high water mark算法，经过优化后的顶点索引，要么是你之前见过的，要么是你见过的最⼤值+1。这样就不需要对真实值（较⼤）编码，⽽是对相对值（较⼩）进⾏编码就可以。如下：
如上就是对zigzag和high water mark算法思路和作⽤的⼀个意会。详细的编码解码在⽹上也能找到，这⾥就不多介绍了。另外，可以看到他们解码的代价是很低的，因此在复杂度和压缩⽐之间，还是会有很⼤的受益，特别适合Web下的传输，当然⼀切的前提是你得使⽤varint这种编码⽅式，或者你在传输的过程中采⽤了体现这种价值的压缩⽅式。
另外，Cesium的顶点数据保存的是delta（当前值-前⼀个值），这个过程可能会产⽣负值，这是采⽤zigzag的主因。解码代码对应的也是相对值，注意是+=⽽不是=：
for (i = 0; i < vertexCount; ++i) {
u += zigZagDecode(uBuffer[i]);
v += zigZagDecode(vBuffer[i]);
height += zigZagDecode(heightBuffer[i]);
uBuffer[i] = u;
vBuffer[i] = v;
}
createMesh
数据解析完毕后，同⾼度图⼀样，把上⾯的参数，通过Workers技术，在线程中开始构建格⽹。这个过程是在ateMesh中完成了，格⽹的构建是在createVerticesFromQua
ntizedTerrainMesh⽅法中实现。这个过程和⾼度图是完全⼀样的，所以在此略去。
我们先看看STK的格⽹效果，如下图，相⽐⾼度图，这个看上去很简单，⽐较稀疏，所以数据量药⼩很多。
我们换⼀个视⾓再看看，就会发现，虽然稀疏，但把好⾝材（前凸后翘）都体现出来了，并且裙边也处理的很严谨：
举⼀个不恰当的例⼦，有橙汁英语
⼀个性感的模特，⼀个裁缝⼿艺不到家，就做了⼀件紧⾝⾐，来突出模特的⾝材；另⼀位⼿艺了得，根据模特的⾝材，量⾝制作了⼀件轻易的霓裳⽻⾐，穿在⾝上，模特的⾝材不仅表现的淋漓尽致，配上⾐服更有⼀番若隐若现的韵味。这就是⾼度图和TIN在三⾓⽹处理上的差距。
先对⽐了两者之间的差别后，我们正式进⼊构建⽹格的环节。因为STK的数据是预处理的，⽽且数据⽐较稀疏。如果很好的理解了之前的数据结构，这⼀块理解起来也不是问题，主要是把顶点数据解析成球⾯坐标下对应的真实值。简单来说，如上图所⽰，此时，格⽹中的每⼀个节点，⽬前是按照0~32767(short的最⼤值)的范围，保存的⼀个正整数（⽐例系数），现在就要根据该Tile的地理范围，实际的⾼度，通过这个⽐例系数，还原成真实的，具有地理意义的真实值。不知道⼤家是否理解这个意思，⼀⾔不合就上代码：
var maxShort = 32767;
// quantizedVertexCount为顶点数据的总数
for (var i = 0; i < quantizedVertexCount; ++i) {
// uv为该点对应该Tile下[0,1]范围内的位置
var u = uBuffer[i] / maxShort;
var v = vBuffer[i] / maxShort;
// ⾼度值，⽶单位
var height = CesiumMath.lerp(minimumHeight, maximumHeight, heightBuffer[i] / maxShort);
// 通过插值算法，计算对应的经纬度值，弧度单位
cartographicScratch.longitude = CesiumMath.lerp(west, east, u);
cartographicScratch.latitude = CesiumMath.lerp(south, north, v);
cartographicScratch.height = height;
// 经纬度转换为以地球球⼼为原点的笛卡尔坐标系的值，⽶单位
var position = ellipsoid.cartographicToCartesian(cartographicScratch);
uvs[i] = new Cartesian2(u, v);
heights[i] = height;
positions[i] = position;
// ……
}
TerrainEncoding
格⽹对应的节点构建完成后，Cesium还做了TerrainEncoding编码，主要是看数据是否可以压缩，⽐如把两个float值压缩为⼀个float，这样来降低显存的占⽤。⾸先，格那句XYZ三个轴的最⼤最⼩值，构造出aaBox和TerrainEncoding对象：
var aaBox = new AxisAlignedBoundingBox(minimum, maximum, center);
var encoding = new TerrainEncoding(aaBox, hMin, maximumHeight, fromENU, hasVertexNormals);
前者是⼀个包围盒，后者是后⾯需要⽤的压缩⼯具，如果包围盒三个维度中最⼤的差距在2^12 = 40女人腰酸的原因有哪些
96 范围内，则把两个float值压缩为⼀个float，如果差距太⼤，超过这个范围，认为这种压缩对精度的损失⽐较⼤，泽不进⾏编码，还是有原始数据。这⾥我有⼀个疑问，为什么范围设定在4096，⼀个float是32位，如果是⼆合⼀，理论上最⼤范围可以设定在2^16。我不确定我的推断是否正确：因为float的精度原因，尾数占23bit，精度只有7位，所以4096倍的放⼤取整就⾜够了。当然，⼀拆⼆的过程（把这⼀个float还原成两个float）是在shader中计算的，性能没有影响。通过这种⽅式，对⼩范围的Tile⽽⾔，可以减少50%顶点数据的显存占⽤，也是⼀种优化吧。下⾯给出⼆合⼀的压缩算法，不难理解就不多解释了：
var x = textureCoordinates.x === 1.0 ? 4095.0 : (textureCoordinates.x * 4096.0) | 0;
var y = t萨摩耶犬多少钱一只
extureCoordinates.y === 1.0 ? 4095.0 : (textureCoordinates.y * 4096.0) | 0;
return 4096.0 * x + y;
};
⾄此，我们的Mesh就构建完成了，细细的和⾼度图createMesh的过程对⽐ ，真的可以⽤疏归同途来形容，⽅法不⼀，但最终都能构建出TerrainMesh这个对象。
Horizon Cull
STK的TIN三⾓⽹⽅式就介绍到这了，上⼀篇因为篇幅问题，没有将⽔平裁剪，在这⾥补充⼀下，毕竟⽆论是⾼度图还是TIN，都⽤到了这个技术。下⾯介绍⼀下它的主要思路和关键实现点，详细内容可以访问。如下这个图很好的说明了⽔平裁剪的作⽤。
在⾼度图中我们提到了Frustum Cull（视锥体裁剪），⽆论是BoundingSphere还是OrientedBoundingBox，都是⽤来判断图⽚中红点区域的，⽽蓝点虽然也在椎体内，却在背⾯，其实可以不⽤渲染，⽽Frustum Cull不能判断出这种情况。⽽Horizon Cull就是⽤来解决这种情况的。
⾸先的问题是，怎样判断这个点是否在球的背⾯，这时⼀个挺有意思的话题，之前研究OpenWebGlobe的源码，他也有⽔平裁剪的判断，不过相⽐⽽⾔计算量就有点⼤，因为他计算的是该点和圆⼼的法线，以及相机和圆⼼的向量之间的⾓度，如果⼤于90度，则是背⾯。我觉得Cesium的数据功底真的很强，理论上打造的很扎实，不是随便凑凑，灵机⼀动就能想到的解决技术。如下图：
⼀个复杂的向量计算，转化成了⼀个相似三⾓形的问题，即判断VA和VP之间的⼤⼩。具体的推导过程就不再这⾥额外展开
了，Cesium的官⽹博⽂⾥⾯有很详细的推导，⽽且源码⾥⾯也有对应的判断。下⾯就是第⼆个问题，如何把每⼀个Tile⾯抽象成⼀个点，不然需要判断该TIle对应的所有点，这个计算量也是不实际的。同样，Cesium中也提供了推导过程和相关代码，请。额外说⼀下，在推导中，你需要注意你的球⾯参数是⽤的椭球和圆球，参数的不同，也会导致结果，有时候这种差异不是误差，⽽是错误，⽽Cesium中采⽤的是椭球，长轴、短轴和曲率相关的参数。
