算法
中序遍历二叉树
给定一个二叉树，返回它的中序 遍历。
示例:
输入: [1,null,2,3]
1
\
2
/
3
输出: [1,3,2]
var inorderTraversal = function(root) {
const result = [];
const inorder = node => {
if(!node) return;
inorder(node.left);
result.push(node.val);
inorder(node.right);
}
inorder(root);
return result;
};
光照
我们所看到的物体需要具备立体效果需要有光源，造成阴影，才会有所呈现。光源分为三类：平行光、点光源、环境光
- 平行光：光线与光线之间是平行的
- 点光源：点光源光是从一个点向周围的所有方向发出的光
- 环境光：那些经光源发出后，被墙壁等物体多次反射，然后照到物体表面的光。
反射的类型分为漫反射和环境反射
- 漫反射：漫反射的反射光在各个方向上市均匀的，反射光的颜色取决于入射光的颜色、表面的基底色、入射光与表面形成的入射角
- 环境反射：认为被光照的物体的方式各方向均匀、强度相等，所以反射方向也是均匀的。取决于入射光的颜色和方向
法向量：垂直于表面的方向又称法线或者法向量，一个表面具有两个法向量，正面和背面
整个光照的计算就是不同种类的光照，根据不同的规则算出来的，平行光就是会取法向量与平行光之间的夹角。
<漫反射光颜色> = <入射光颜色> x <表面基底色> x (<光线方向与法线方向的夹角>) <环境反射光颜色> = <入射光颜色> x <表面基底色> <表面的反射光颜色> = <漫反射光颜色> + <环境反射光颜色> 如果单纯使用漫反射就不会那么自然，因为我们现实中看到的光照都会有周围环境对于光照的漫反射之后的照射，不可能存在空间中只有一个单独的物体。所以光照是需要漫反射 + 环境光反射进行叠加的 ### 漫反射光源 ``` var VSHADER_SOURCE = ` attribute vec4 a_Position; attribute vec4 a_Color; attribute vec4 a_Normal; uniform mat4 u_MvpMatrix; uniform mat4 u_NormalMatrix; uniform vec3 u_LightDirection; varying vec4 v_Color; void main() { gl_Position = u_MvpMatrix * a_Position; vec4 normal = u_NormalMatrix * a_Normal; float nDotL = max(dot(u_LightDirection, normalize(normal.xyz)), 0.0); v_Color = vec4(a_Color.xyz * nDotL, a_Color.a); } `; var FSHADER_SOURCE = ` #ifdef GL_ES precision mediump float; #endif varying vec4 v_Color; void main() { gl_FragColor = v_Color; } `; var gl = canvas.getContext('webgl'); initShaders(gl, VSHADER_SOURCE, FSHADER_SOURCE) this.gl = gl; var n = this.initVertexBuffers(gl) gl.clearColor(0, 0, 0, 1); gl.enable(gl.DEPTH_TEST); var u_MvpMatrix = gl.getUniformLocation(gl.program, 'u_MvpMatrix');//模型视图投影矩阵 var u_NormalMatrix = gl.getUniformLocation(gl.program, 'u_NormalMatrix'); var u_LightDirection = gl.getUniformLocation(gl.program, 'u_LightDirection'); if (!u_MvpMatrix || !u_NormalMatrix || !u_LightDirection) { console.log('Failed to get the storage location'); return; } var lightDirection = new Vector3([0.5, 3.0, 4.0]);//设置光线方向（世界坐标系下） lightDirection.normalize();//归一化 gl.uniform3fv(u_LightDirection, lightDirection.elements); var mvpMatrix = new Matrix4();//视图投影矩阵 mvpMatrix.setPerspective(30, canvas.width / canvas.height, 1, 100); mvpMatrix.lookAt(3, 3, 7, 0, 0, 0, 0, 1, 0); var currentAngle = 0.0; //目前的旋转角度 var modelMatrix = new Matrix4(); //模型矩阵 var vpMatrix = new Matrix4();//模型视图投影矩阵 var normalMatrix = new Matrix4();//法线变换矩阵 var tick = function () { currentAngle = animate(currentAngle);//更新当前旋转角度 //计算模型矩阵 modelMatrix.setRotate(currentAngle, 0, 1, 0); //围绕y轴旋转 vpMatrix.set(mvpMatrix).multiply(modelMatrix); gl.uniformMatrix4fv(u_MvpMatrix, false, vpMatrix.elements); // Pass the matrix to transform the normal based on the model matrix to u_NormalMatrix normalMatrix.setInverseOf(modelMatrix); normalMatrix.transpose(); gl.uniformMatrix4fv(u_NormalMatrix, false, normalMatrix.elements); // Clear color and depth buffer gl.clear(gl.COLOR_BUFFER_BIT | gl.DEPTH_BUFFER_BIT); // Draw the cube gl.drawElements(gl.TRIANGLES, n, gl.UNSIGNED_BYTE, 0); requestAnimationFrame(tick, canvas); // Request that the browser ?calls tick }; tick(); initVertexBuffers(gl){ var vertices = new Float32Array([ // Vertex coordinates 1.0, 1.0, 1.0, -1.0, 1.0, 1.0, -1.0,-1.0, 1.0, 1.0,-1.0, 1.0, // v0-v1-v2-v3 front 1.0, 1.0, 1.0, 1.0,-1.0, 1.0, 1.0,-1.0,-1.0, 1.0, 1.0,-1.0, // v0-v3-v4-v5 right 1.0, 1.0, 1.0, 1.0, 1.0,-1.0, -1.0, 1.0,-1.0, -1.0, 1.0, 1.0, // v0-v5-v6-v1 up -1.0, 1.0, 1.0, -1.0, 1.0,-1.0, -1.0,-1.0,-1.0, -1.0,-1.0, 1.0, // v1-v6-v7-v2 left -1.0,-1.0,-1.0, 1.0,-1.0,-1.0, 1.0,-1.0, 1.0, -1.0,-1.0, 1.0, // v7-v4-v3-v2 down 1.0,-1.0,-1.0, -1.0,-1.0,-1.0, -1.0, 1.0,-1.0, 1.0, 1.0,-1.0 // v4-v7-v6-v5 back ]); var colors = new Float32Array([ // Colors 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, // v0-v1-v2-v3 front 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, // v0-v3-v4-v5 right 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, // v0-v5-v6-v1 up 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, // v1-v6-v7-v2 left 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, // v7-v4-v3-v2 down 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0 // v4-v7-v6-v5 back ]); var normals = new Float32Array([ // Normal 0.0, 0.0, 1.0, 0.0, 0.0, 1.0, 0.0, 0.0, 1.0, 0.0, 0.0, 1.0, // v0-v1-v2-v3 front 1.0, 0.0, 0.0, 1.0, 0.0, 0.0, 1.0, 0.0, 0.0, 1.0, 0.0, 0.0, // v0-v3-v4-v5 right 0.0, 1.0, 0.0, 0.0, 1.0, 0.0, 0.0, 1.0, 0.0, 0.0, 1.0, 0.0, // v0-v5-v6-v1 up -1.0, 0.0, 0.0, -1.0, 0.0, 0.0, -1.0, 0.0, 0.0, -1.0, 0.0, 0.0, // v1-v6-v7-v2 left 0.0,-1.0, 0.0, 0.0,-1.0, 0.0, 0.0,-1.0, 0.0, 0.0,-1.0, 0.0, // v7-v4-v3-v2 down 0.0, 0.0,-1.0, 0.0, 0.0,-1.0, 0.0, 0.0,-1.0, 0.0, 0.0,-1.0 // v4-v7-v6-v5 back ]); var indices = new Uint8Array([ // Indices of the vertices 0, 1, 2, 0, 2, 3, // front 4, 5, 6, 4, 6, 7, // right 8, 9,10, 8,10,11, // up 12,13,14, 12,14,15, // left 16,17,18, 16,18,19, // down 20,21,22, 20,22,23 // back ]); // Write the vertex coordinates and color to the buffer object if (!initArrayBuffer(gl, vertices, 3, gl.FLOAT, 'a_Position')) return -1; if (!initArrayBuffer(gl, colors, 3, gl.FLOAT, 'a_Color')) return -1; if (!initArrayBuffer(gl, normals, 3, gl.FLOAT, 'a_Normal')) return -1; // Create a buffer object var indexBuffer = gl.createBuffer(); if (!indexBuffer) { console.log('Failed to create the buffer object'); return false; } // Write the indices to the buffer object gl.bindBuffer(gl.ELEMENT_ARRAY_BUFFER, indexBuffer); gl.bufferData(gl.ELEMENT_ARRAY_BUFFER, indices, gl.STATIC_DRAW); return indices.length; } function initArrayBuffer(gl, data, num, type, attribute) { var buffer = gl.createBuffer(); // Create a buffer object if (!buffer) { console.log('Failed to create the buffer object'); return false; } // Write date into the buffer object gl.bindBuffer(gl.ARRAY_BUFFER, buffer); gl.bufferData(gl.ARRAY_BUFFER, data, gl.STATIC_DRAW); // Assign the buffer object to the attribute variable var a_attribute = gl.getAttribLocation(gl.program, attribute); if (a_attribute < 0) { console.log('Failed to get the storage location of ' + attribute); return false; } gl.vertexAttribPointer(a_attribute, num, type, false, 0, 0); // Enable the assignment of the buffer object to the attribute variable gl.enableVertexAttribArray(a_attribute); gl.bindBuffer(gl.ARRAY_BUFFER, null); return true; } // Rotation angle (degrees/second) var ANGLE_STEP = 30.0; // Last time that this function was called var g_last = Date.now(); function animate(angle) { // Calculate the elapsed time var now = Date.now(); var elapsed = now - g_last; g_last = now; // Update the current rotation angle (adjusted by the elapsed time) var newAngle = angle + (ANGLE_STEP * elapsed) / 1000.0; return newAngle %= 360; } ```