算法
从前序与中序遍历序列构造二叉树
根据一棵树的前序遍历与中序遍历构造二叉树。
注意: 你可以假设树中没有重复的元素。
例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
3
/ \
9 20
/ \
15 7
var buildTree = function(preorder, inorder) {
if(!preorder || preorder.length < 1){
return null;
}
let root = preorder[0];
let treeNode = new TreeNode(root);
if(preorder.length === 1) {
return treeNode;
}
let rootIndex = inorder.indexOf(root);
let inorderLeft = inorder.slice(0, rootIndex);
let inorderRight = inorder.slice(rootIndex + 1, inorder.length);
let preorderLeft = preorder.slice(1, inorderLeft.length + 1);
let preorderRight = preorder.slice(inorderLeft.length + 1, preorder.length);
treeNode.left = buildTree(preorderLeft, inorderLeft);
treeNode.right = buildTree(preorderRight, inorderRight);
return treeNode;
};
点光源
点光源是对顶点着色器进行逐顶点进行渲染，整体效果看起来就会散一些，明暗的分界线就不会那么明显，如果是进行逐片元进行渲染，明暗的分界线就会更明显一些
逐点渲染
var VSHADER_SOURCE = `
attribute vec4 a_Position;
attribute vec4 a_Color;
attribute vec4 a_Normal;
uniform mat4 u_MvpMatrix;
uniform mat4 u_ModelMatrix;
uniform mat4 u_NormalMatrix;
uniform vec3 u_LightColor;
uniform vec3 u_LightPosition;
uniform vec3 u_AmbientLight;
varying vec4 v_Color;
void main() {
gl_Position = u_MvpMatrix * a_Position;
vec3 normal = normalize(vec3(u_NormalMatrix * a_Normal));
vec4 vertexPosition = u_ModelMatrix * a_Position;
vec3 lightDirection = normalize(u_LightPosition - vec3(vertexPosition));
float nDotL = max(dot(lightDirection, normal), 0.0);
vec3 diffuse = u_LightColor * vec3(a_Color) * nDotL;
vec3 ambient = u_AmbientLight * vec3(a_Color);
v_Color = vec4(diffuse + ambient, 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_ModelMatrix = gl.getUniformLocation(gl.program, 'u_ModelMatrix');
var u_MvpMatrix = gl.getUniformLocation(gl.program, 'u_MvpMatrix');//模型视图投影矩阵
var u_NormalMatrix = gl.getUniformLocation(gl.program, 'u_NormalMatrix');
var u_LightColor = gl.getUniformLocation(gl.program, 'u_LightColor');
var u_LightPosition = gl.getUniformLocation(gl.program, 'u_LightPosition');
var u_AmbientLight = gl.getUniformLocation(gl.program, 'u_AmbientLight');
if (!u_MvpMatrix || !u_NormalMatrix || !u_LightColor || !u_LightPosition || !u_AmbientLight) {
console.log('Failed to get the storage location');
return;
}
var vpMatrix = new Matrix4(); // View projection matrix
vpMatrix.setPerspective(30, canvas.width/canvas.height, 1, 100);
vpMatrix.lookAt(6, 6, 14, 0, 0, 0, 0, 1, 0);
gl.uniform3f(u_LightColor, 1.0, 1.0, 1.0); //设置光线颜色为白色
gl.uniform3f(u_LightPosition, 2.3, 4.0, 3.5);//设置光线位置（在世界坐标系下）
gl.uniform3f(u_AmbientLight, 0.2, 0.2, 0.2); //设置环境光颜色
var currentAngle = 0.0;
var modelMatrix = new Matrix4(); // Model matrix
var mvpMatrix = new Matrix4(); // Model view projection matrix
var normalMatrix = new Matrix4(); // Transformation matrix for normals
var tick = function() {
currentAngle = animate(currentAngle); // Update the rotation angle
// Calculate the model matrix
modelMatrix.setRotate(currentAngle, 0, 1, 0); // Rotate around the y-axis
// Pass the model matrix to u_ModelMatrix
gl.uniformMatrix4fv(u_ModelMatrix, false, modelMatrix.elements);
// Pass the model view projection matrix to u_MvpMatrix
mvpMatrix.set(vpMatrix).multiply(modelMatrix);
gl.uniformMatrix4fv(u_MvpMatrix, false, mvpMatrix.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){
// Create a cube
// v6----- v5
// /| /|
// v1------v0|
// | | | |
// | |v7---|-|v4
// |/ |/
// v2------v3
var vertices = new Float32Array([ // Vertex coordinates
2.0, 2.0, 2.0, -2.0, 2.0, 2.0, -2.0,-2.0, 2.0, 2.0,-2.0, 2.0, // v0-v1-v2-v3 front
2.0, 2.0, 2.0, 2.0,-2.0, 2.0, 2.0,-2.0,-2.0, 2.0, 2.0,-2.0, // v0-v3-v4-v5 right
2.0, 2.0, 2.0, 2.0, 2.0,-2.0, -2.0, 2.0,-2.0, -2.0, 2.0, 2.0, // v0-v5-v6-v1 up
-2.0, 2.0, 2.0, -2.0, 2.0,-2.0, -2.0,-2.0,-2.0, -2.0,-2.0, 2.0, // v1-v6-v7-v2 left
-2.0,-2.0,-2.0, 2.0,-2.0,-2.0, 2.0,-2.0, 2.0, -2.0,-2.0, 2.0, // v7-v4-v3-v2 down
2.0,-2.0,-2.0, -2.0,-2.0,-2.0, -2.0, 2.0,-2.0, 2.0, 2.0,-2.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;
}
逐片元渲染
片元渲染时，就不用对顶点着色器有太多的操作，更多的在片元着色器中对每个片元进行操作。
首先对法向量进行归一化处理，然后计算片元处的光线方向并对其归一化，接着计算法向量与光线方向的点积，最后分别计算多个点光源光和环境光的反射光颜色，并将两个结果加起来。
var VSHADER_SOURCE = `
attribute vec4 a_Position;
attribute vec4 a_Color;
attribute vec4 a_Normal;
uniform mat4 u_MvpMatrix;
uniform mat4 u_ModelMatrix;
uniform mat4 u_NormalMatrix;
varying vec3 v_Normal;
varying vec3 v_Position;
varying vec4 v_Color;
void main() {
gl_Position = u_MvpMatrix * a_Position;
v_Position = vec3(u_ModelMatrix * a_Position);
v_Normal = normalize(vec3(u_NormalMatrix * a_Normal));
v_Color = a_Color;
}
`;
var FSHADER_SOURCE = `
#ifdef GL_ES
precision mediump float;
#endif
uniform vec3 u_LightColor;
uniform vec3 u_LightPosition;
uniform vec3 u_AmbientLight;
varying vec3 v_Normal;
varying vec3 v_Position;
varying vec4 v_Color;
void main() {
vec3 normal = normalize(v_Normal);
vec3 lightDirection = normalize(u_LightPosition - v_Position);
float nDotL = max(dot(lightDirection, normal), 0.0);
vec3 diffuse = u_LightColor * v_Color.rgb * nDotL;
vec3 ambient = u_AmbientLight * v_Color.rgb;
gl_FragColor = vec4(diffuse + ambient, v_Color.a);
}
`;
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_ModelMatrix = gl.getUniformLocation(gl.program, 'u_ModelMatrix');
var u_MvpMatrix = gl.getUniformLocation(gl.program, 'u_MvpMatrix');//模型视图投影矩阵
var u_NormalMatrix = gl.getUniformLocation(gl.program, 'u_NormalMatrix');
var u_LightColor = gl.getUniformLocation(gl.program, 'u_LightColor');
var u_LightPosition = gl.getUniformLocation(gl.program, 'u_LightPosition');
var u_AmbientLight = gl.getUniformLocation(gl.program, 'u_AmbientLight');
if (!u_MvpMatrix || !u_NormalMatrix || !u_LightColor || !u_LightPosition || !u_AmbientLight) {
console.log('Failed to get the storage location');
return;
}
gl.uniform3f(u_LightColor, 1.0, 1.0, 1.0); //设置光线颜色为白色
gl.uniform3f(u_LightPosition, 2.3, 4.0, 3.5);//设置光线位置（在世界坐标系下）
gl.uniform3f(u_AmbientLight, 0.2, 0.2, 0.2); //设置环境光颜色
var modelMatrix = new Matrix4(); // Model matrix
var mvpMatrix = new Matrix4(); // Model view projection matrix
var normalMatrix = new Matrix4(); // Transformation matrix for normals
var daginfo = 0
function tick() {
daginfo += 0.5;
modelMatrix.setRotate(daginfo, 0, 1, 0);
gl.uniformMatrix4fv(u_ModelMatrix, false, modelMatrix.elements);
mvpMatrix.setPerspective(30, canvas.width/canvas.height, 1 ,100);
mvpMatrix.lookAt(6, 6, 14, 0, 0, 0, 0, 1, 0);
mvpMatrix.multiply(modelMatrix);
gl.uniformMatrix4fv(u_MvpMatrix, false, mvpMatrix.elements);
normalMatrix.setInverseOf(modelMatrix);
normalMatrix.transpose();
gl.uniformMatrix4fv(u_NormalMatrix, false, normalMatrix.elements);
gl.clear(gl.COLOR_BUFFER_BIT | gl.DEPTH_BUFFER_BIT);
gl.drawElements(gl.TRIANGLES, n, gl.UNSIGNED_BYTE, 0);
requestAnimationFrame(tick)
}
tick()