化石原创文章，转载请注明来源并保留原文链接
这篇文章，我们能知道写Cesium shader，可以使用不少引擎已经定义好的变量和方法，而不必要造轮子。如果有心的话，你会发现Cesium并没有像其他大多3D引擎一样，需要你使用一些类似#include的手段去包含相关的文件。那么问题就来了，这些变量或者方法，在OpenGL ES驱动编译的时候，总是要提前申明和实现的。就一定程度上来说，我们写的，在眼睛里看到的代码并不完整。Cesium会在一定时候为我们补足缺失的部分。
还是以SkyBoxFS.glsl举个例子，这个glsl代码如下（原始的）：
uniform samplerCube u_cubeMap;
varying vec3 v_texCoord;
void main()
{
vec4 color = textureCube(u_cubeMap, normalize(v_texCoord));
gl_FragColor = vec4(czm_gammaCorrect(color).rgb, czm_morphTime);
}
经过Cesium在合适的时机处理后（其实在ShaderCache.prototype.getShaderProgram()方法中），最后完整的glsl代码是这样：
#ifdef GL_FRAGMENT_PRECISION_HIGH
precision highp float;
#else
precision mediump float;
#endif
#define HDR
#define OES_texture_float_linear
uniform float czm_gamma;
uniform float czm_morphTime;
vec3 czm_gammaCorrect(vec3 color) {
#ifdef HDR
color = pow(color, vec3(czm_gamma));
#endif
return color;
}
vec4 czm_gammaCorrect(vec4 color) {
#ifdef HDR
color.rgb = pow(color.rgb, vec3(czm_gamma));
#endif
return color;
}
#line 0
#line 0
uniform samplerCube u_cubeMap;
varying vec3 v_texCoord;
void main()
{
vec4 color = textureCube(u_cubeMap, normalize(v_texCoord));
gl_FragColor = vec4(czm_gammaCorrect(color).rgb, czm_morphTime);
}
两相对比，显然Cesium自动添加了关联的czm变量和方法到glsl代码中，使其成为了一个合格的glsl代码。我看了这段代码后，发现了Cesium在这个过程构造依赖树的方式，觉得很有用，遂记录下来。
涉及的方法是ShaderSource.js里的，getBuiltinsAndAutomaticUniforms（）。
function getBuiltinsAndAutomaticUniforms(shaderSource) {
// generate a dependency graph for builtin functions
var dependencyNodes = [];
var root = getDependencyNode('main', shaderSource, dependencyNodes);
generateDependencies(root, dependencyNodes);
sortDependencies(dependencyNodes);
// Concatenate the source code for the function dependencies.
// Iterate in reverse so that dependent items are declared before they are used.
var builtinsSource = '';
for (var i = dependencyNodes.length - 1; i >= 0; --i) {
builtinsSource = builtinsSource + dependencyNodes[i].glslSource + '\n';
}
return builtinsSource.replace(root.glslSource, '');
}
重要的三个方法：getDependencyNode(), generateDependencies(), sortDependencies()。我们一一来读。
function getDependencyNode(name, glslSource, nodes) {
var dependencyNode;
// check if already loaded
for (var i = 0; i < nodes.length; ++i) {
if (nodes[i].name === name) {
dependencyNode = nodes[i];
}
}
if (!defined(dependencyNode)) {
// strip doc comments so we don't accidentally try to determine a dependency for something found
// in a comment
glslSource = removeComments(glslSource);
// create new node
dependencyNode = {
name : name,
glslSource : glslSource,
dependsOn : [],
requiredBy : [],
evaluated : false
};
nodes.push(dependencyNode);
}
return dependencyNode;
}
第2行，定义了一个最后用来返回的节点。
第5到9行，轮询参数3代表的已经存在的节点集合，看参数1名字代表的节点是否已经在该节点集合中存在。如果存在，那么我们返回的就是这个节点。
第11到25行，如果上面没有查到节点，那么我们会创建一个节点出来，这个节点有name（名字，作为后续查询的key）、glslsource（原始的glsl代码）、dependsOn（依赖的节点集合）、requireBy（被依赖的节点集合）、evaluated（是否评估过的标志）。并且这个节点会放置到参数3代表的集合里。
所以，这个方法正如它的方法名，就是在参数3代表的集合中查询名字为参数1的节点是否存在，不存在就创建一个新的存入集合。返回的是已经存在的节点或者是新创建的节点。
以我们上面的 getBuiltinsAndAutomaticUniforms ()方法来说，第一次会创建出一个名字为“main”的节点出来。假设我们的glsl代码是这篇文章最开始的那段的话，那么这个节点的glslsource就是整个代码内容。dependsOn数组是空，表示不依赖任何节点。requireBy数组为空，表示也没有被其他任何节点依赖。evaluated是false，还未经评估。
然后就到generateDependencies：
function generateDependencies(currentNode, dependencyNodes) {
if (currentNode.evaluated) {
return;
}
currentNode.evaluated = true;
// identify all dependencies that are referenced from this glsl source code
var czmMatches = currentNode.glslSource.match(/\bczm_[a-zA-Z0-9_]*/g);
if (defined(czmMatches) && czmMatches !== null) {
// remove duplicates
czmMatches = czmMatches.filter(function(elem, pos) {
return czmMatches.indexOf(elem) === pos;
});
czmMatches.forEach(function(element) {
if (element !== currentNode.name && ShaderSource._czmBuiltinsAndUniforms.hasOwnProperty(element)) {
var referencedNode = getDependencyNode(element, ShaderSource._czmBuiltinsAndUniforms[element], dependencyNodes);
currentNode.dependsOn.push(referencedNode);
referencedNode.requiredBy.push(currentNode);
// recursive call to find any dependencies of the new node
generateDependencies(referencedNode, dependencyNodes);
}
});
}
}
第2行先检测节点的evaluated值，是false的才处理。true说明已经处理过了。
第9行在glslsource里面查找czm_开头的所有字符串，得到一个字符串数组。
第12行到14行，使用Array的filter方法，只取原来数组中的第一个出现的元素。就过滤掉了原来字符串中重复的字符串。
第16到25行，对每个字符串，以这个字符串为名字做节点，生成这个节点的依赖集合（第19行），和填充它的被依赖集合（第20行）。然后递归计算该节点的依赖（第23行）。
还是以上面我们的第一个glsl的main为例，上面一段我们可以看到，”main”节点生成，依赖集合空、被依赖集合空，evaluated是false。这个节点作为参数1送入方法，第一时间evaluated会被设置成true。第9行运行过后，czmMatches集合会放入czm_gammaCorrect、czm_morphTime字符串。
我们不管其他，到19行跑过，我们的main节点能想象到依赖集合里面添置czm_gammaCorrect依赖，下一个循环，这一行又会添置czm_morphTime依赖。
而20行的，referenceNode，以czm_gammaCorrect为例，它的requireBy就会加入我们的main节点。
所以，一个main依赖czm_gammaCorrect，czm_gammaCorrect被main依赖的代码表示就完成了。可以想象，如果是一段复杂的glsl代码，里面有很多的czm_xxx，而czm_xxx可能还依赖其他的czm_xxx，那么这个就可以形成一颗完整的依赖树。根节点如我们例子中的main，以它为根，它依赖的每个节点都是一棵树的枝干或者叶子。枝繁叶茂。
最后是sortDependencies方法：
function sortDependencies(dependencyNodes) {
//记录不被依赖任何节点的节点（比如我们的main）
var nodesWithoutIncomingEdges = [];
//记录所有的节点
var allNodes = [];
while (dependencyNodes.length > 0) {
//下面两行代码，从dependencyNodes中取出节点，放入allNodes
//整个while循环跑下来，dependencyNodes就空了，节点全部转移到allNodes
var node = dependencyNodes.pop();
allNodes.push(node);
if (node.requiredBy.length === 0) {
nodesWithoutIncomingEdges.push(node);
}
}
while (nodesWithoutIncomingEdges.length > 0) {
var currentNode = nodesWithoutIncomingEdges.shift();
dependencyNodes.push(currentNode);
for (var i = 0; i < currentNode.dependsOn.length; ++i) {
// remove the edge from the graph
//检测节点依赖的节点，让后者的requireBy去除检测的节点（用于检测相互依赖错误）
var referencedNode = currentNode.dependsOn[i];
var index = referencedNode.requiredBy.indexOf(currentNode);
referencedNode.requiredBy.splice(index, 1);
// if referenced node has no more incoming edges, add to list
//下面这一行的逻辑处理会这里导致的结果是：越是被依赖的多，在数组中的位置就越靠后。
//所有在后续的处理上，需要从数组后面倒着拿里面的节点的源代码数据组合成最后的shader源代码
if (referencedNode.requiredBy.length === 0) {
nodesWithoutIncomingEdges.push(referencedNode);
}
}
}
// if there are any nodes left with incoming edges, then there was a circular dependency somewhere in the graph
var badNodes = [];
for (var j = 0; j < allNodes.length; ++j) {
if (allNodes[j].requiredBy.length !== 0) {
badNodes.push(allNodes[j]);
}
}
//>>includeStart('debug', pragmas.debug);
if (badNodes.length !== 0) {
var message = 'A circular dependency was found in the following built-in functions/structs/constants: \n';
for (var k = 0; k < badNodes.length; ++k) {
message = message + badNodes[k].name + '\n';
}
throw new DeveloperError(message);
}
//>>includeEnd('debug');
//没有返回值，我们的参数就是处理过的数据，所有的节点的requireBy.length是0。
}
这里我换了个方式，一些代码细节说明放在了代码中，也就是上面的中文注释。唯一要说明的是，在节点的requireBy集合被处理成空后， 代码中的 nodesWithoutIncomingEdges 数组用来安置这个节点。整个方法是
1、侦测循环依赖（排错）和
2、给节点排序用的：一个节点被依赖的地方越多，它被放进 nodesWithoutIncomingEdges集合的位置就越晚。而 nodesWithoutIncomingEdges里面的值，在18行开始的循环中，会一个个在合适的时机都放入到参数1里面。因此参数1既是入参，又是出参。
三个重要的方法就说明到这里。
最后要说的是，生成依赖树、排序，最终目的都是为完整的glsl代码生成。也就是怎么从我们这篇文章的第一段glsl代码，得到第二段glsl代码。所以，getBuiltinsAndAutomaticUniforms方法中的
var builtinsSource = '';
for (var i = dependencyNodes.length - 1; i >= 0; --i) {
builtinsSource = builtinsSource + dependencyNodes[i].glslSource + '\n';
}
实际上在做的是最后的拼装工作。builtinsSource开始是空的，每个循环都从数组中取节点的glslsource，加入到builtinsSource中。注意到这个循环是从数组的最后一个元素开始，倒着轮询没？因为：“一个节点被依赖的地方越多，它被放进 nodesWithoutIncomingEdges集合的位置就越晚”。glsl代码本身类似c语言，被依赖的东西一定要先声明，所以才有了排序这个过程。
化石原创文章，转载请注明来源并保留原文链接