算法
矩阵置零
给定一个 m x n 的矩阵,如果一个元素为 0,则将其所在行和列的所有元素都设为 0。请使用原地算法。
var setZeroes = function(matrix) {
var mapY = {};
for(let x=0; x<matrix.length; x++){
var tag = false;
for(let y=0; y< matrix[x].length; y++){
if(matrix[x][y] === 0){
tag = true;
mapY[y] = x;
}else if(mapY[y] !== void 0){
matrix[x][y] = 0;
}
}
if(tag){
matrix[x].fill(0);
}
}
for(let i in mapY){
for(let j=0; j<mapY[i]; j++){
matrix[j][i] = 0;
}
}
};
字谜分组
给定一个字符串数组,将字母异位词组合在一起。字母异位词指字母相同,但排列不同的字符串。
输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
输出:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
var groupAnagrams = function(strs) {
var map = [];
for(var i=0; i<strs.length; i++){
var sortStr = strs[i].split('').sort().join('');
if(!map[sortStr]){
map[sortStr] = [];
}
map[sortStr].push(strs[i]);
}
return Object.values(map)
};
无重复字符的最长子串
给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
var lengthOfLongestSubstring = function(s) {
var res = 0;
var str = "";
var len = s.length;
for(var i = 0; i < len; i++) {
var char = s.charAt(i);
var index = str.indexOf(char);
if(index === -1) {
str += char;
res = res < str.length ? str.length : res;
} else {
str = str.substr(index + 1) + char;
}
}
return res;
};
最长回文子串
给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
var longestPalindrome = function(s) {
if(s.length < 2) return s;
var res = '';
var x, y;
for(let i=0; i<s.length; i++){
if(res.length > (s.length - i) * 2 - 1) return res;
var _res = s[i];
if(s[i+1] === s[i]){
x = i;
y = i;
while(s[x] == s[y+1]){
_res += s[x];
++y;
}
}else{
x = y = i;
}
while(--x > -1 && ++y < s.length && s[x] === s[y]){
_res = s[x] + _res + s[y];
}
res = res.length > _res.length ? res : _res;
}
return res;
};
递增的三元子序列
给定一个未排序的数组,判断这个数组中是否存在长度为 3 的递增子序列。
数学表达式如下:
如果存在这样的 i, j, k, 且满足 0 ≤ i < j < k ≤ n-1,
使得 arr[i] < arr[j] < arr[k] ,返回 true ; 否则返回 false 。
var increasingTriplet = function(nums) {
if(nums.length < 3) return false;
var first = Number.MAX_SAFE_INTEGER;
var second = Number.MAX_SAFE_INTEGER;
for(let i=0; i<nums.length; i++){
if (nums[i] > second) {
return true
} else if (nums[i] < first) {
first = nums[i];
} else if(nums[i] > first && nums[i] < second){
second = nums[i]
}
}
return false;
};
webGL 缓冲区
// 准备数据
this.points.push({
x,
y,
colorR: `${Math.round(Math.random())}.0`,
colorG: `${Math.round(Math.random())}.0`,
colorB: `${Math.round(Math.random())}.0`
})
// 清空画布
this.gl.clearColor(0.0, 0.0, 0.0, 1.0);
// 给画布重新着色
this.gl.clear(this.gl.COLOR_BUFFER_BIT);
// 创建缓冲区
var vertexBuffer = this.gl.createBuffer();
// 创建数据 buffer
var arr = []
this.points.map(item => {
arr.push(item.x);
arr.push(item.y);
console.log(item);
})
var vertices = new Float32Array(arr)
// 绑定缓冲区
this.gl.bindBuffer(this.gl.ARRAY_BUFFER, vertexBuffer)
// 写入缓冲区数据
this.gl.bufferData(this.gl.ARRAY_BUFFER, vertices, this.gl.STATIC_DRAW);
// 将缓冲区数据赋值给变量
this.gl.vertexAttribPointer(this.a_Position, 2, this.gl.FLOAT, false, 0, 0);
// 连接缓冲区变量和缓冲区对象
this.gl.enableVertexAttribArray(this.a_Position);
// 画点
this.gl.drawArrays(this.gl.POINTS, 0, this.points.length);
创建缓冲区对象
使用缓冲区对象之前,你必须创建它
// 返回的是创建成功的缓存区对象
var vertexBuffer = this.gl.createBuffer();
// 删除缓冲区对象
this.gl.deleteBuffer(vertexBuffer)
绑定缓存区对象
将缓存区对象绑定在目标对象上
this.gl.bindBuffer(this.gl.ARRAY_BUFFER, vertexBuffer)
// 第一个参数有下列三种
// gl.ARRAY_BUFFER 缓冲区对象中包含了顶点的数据
// gl.ELEMENT_ARRAY_BUFFER 表示缓存区对象中包含了顶点的索引值
// buffer 指定之前由 gl.createBuffer 返回的待绑定的缓冲区对象
向缓冲区对象中写入数据
this.gl.bufferData(this.gl.ARRAY_BUFFER, vertices, this.gl.STATIC_DRAW);
// 向绑定的缓存区对象写入数据
// gl.STATIC_DRAW 只会向缓冲区对象中写入一次数据,但需要绘制很多次
// gl.STREAM_DRAW 只会向缓冲区对象中写入一次数据,然后绘制若干次
// gl.DYNAMIC_DRAW 会向缓冲区对象中多次写入数据,并绘制很多次
将缓冲区对象分配给 attribute 变量
// 分配变量
this.gl.vertexAttribPointer(this.a_Position, 2, this.gl.FLOAT, false, 0, 0);
// 开启 attribute 变量
this.gl.enableVertexAttribArray(this.a_Position);
绘制
一笔绘制就行了
webGL 基础图形
点 gl.POINT
线段 gl.LINES
线条 gl.LINE_STRIP
回路 gl.LINE_LOOP
三角形 gl.TRIANGLES
三角带 gl.TRIANGLE_STRIP
三角扇 gl.TRIANGLE_FAN
var canvas = this.$refs.canvas
canvas.width = window.innerWidth - 200;
canvas.height = window.innerHeight - 56;
var VSHADER_SOURCE = `
attribute vec4 a_Position;
uniform float u_CosB, u_SinB;
void main() {
gl_Position.x = a_Position.x * u_CosB - a_Position.y * u_SinB;
gl_Position.y = a_Position.x * u_SinB + a_Position.y * u_CosB;
gl_Position.z = a_Position.z;
gl_Position.w = 1.0;
}
`;
var FSHADER_SOURCE = `
precision mediump float;
uniform vec4 u_FragColor;
void main() {
gl_FragColor = u_FragColor;
}
`;
var gl = canvas.getContext('webgl');
this.gl = gl;
this.points = [];
initShaders(gl, VSHADER_SOURCE, FSHADER_SOURCE);
this.a_Position = gl.getAttribLocation(gl.program, 'a_Position');
var radian = Math.PI * 90 / 180;
var cosB = Math.cos(radian)
var sinB = Math.sin(radian)
this.u_CosB = gl.getUniformLocation(gl.program, 'u_CosB');
this.u_SinB = gl.getUniformLocation(gl.program, 'u_SinB');
gl.uniform1f(this.u_CosB, cosB)
gl.uniform1f(this.u_SinB, sinB)
this.u_FragColor = gl.getUniformLocation(gl.program, 'u_FragColor');
gl.clearColor(0.0, 0.0, 0.0, 1.0);
gl.clear(gl.COLOR_BUFFER_BIT);
clickAction(e) {
var canvas = this.$refs.canvas
var x = (e.offsetX - canvas.width / 2) / canvas.width * 2;
var y = (canvas.height / 2 - e.offsetY) / canvas.height * 2;
this.points.push({
x,
y,
colorR: `${Math.round(Math.random())}.0`,
colorG: `${Math.round(Math.random())}.0`,
colorB: `${Math.round(Math.random())}.0`
})
this.gl.clearColor(0.0, 0.0, 0.0, 1.0);
this.gl.clear(this.gl.COLOR_BUFFER_BIT);
var vertexBuffer = this.gl.createBuffer();
var arr = []
this.points.map(item => {
arr.push(item.x);
arr.push(item.y);
})
this.gl.bindBuffer(this.gl.ARRAY_BUFFER, vertexBuffer)
this.gl.bufferData(this.gl.ARRAY_BUFFER, new Float32Array(arr), this.gl.STATIC_DRAW);
this.gl.vertexAttribPointer(this.a_Position, 2, this.gl.FLOAT, false, 0, 0);
this.gl.enableVertexAttribArray(this.a_Position);
// this.points.map(item => {
// this.gl.vertexAttrib3f(this.a_Position, item.x, item.y, 0.0);
// this.gl.uniform4f(this.u_FragColor, item.colorR, item.colorG, item.colorB, 1.0)
// })
this.gl.drawArrays(this.gl.TRIANGLES, 0, this.points.length);
}
移动、旋转和缩放
平移
对顶点进行逐点操作,平移所有顶点向量
attribute vec4 a_Position;
attribute vec4 a_Translation;
void main() {
gl_Position = a_Position + a_Translation;
}
旋转
旋转需要:旋转轴、旋转方向、旋转角度
attribute vec4 a_Position;
uniform float u_CosB, u_SinB;
void main() {
gl_Position.x = a_Position.x * u_CosB - a_Position.y * u_SinB;
gl_Position.y = a_Position.x * u_SinB + a_Position.y * u_CosB;
gl_Position.z = a_Position.z;
gl_Position.w = 1.0;
}
var radian = Math.PI * 90 / 180;
var cosB = Math.cos(radian)
var sinB = Math.sin(radian)
this.u_CosB = gl.getUniformLocation(gl.program, 'u_CosB');
this.u_SinB = gl.getUniformLocation(gl.program, 'u_SinB');
gl.uniform1f(this.u_CosB, cosB)
gl.uniform1f(this.u_SinB, sinB)
webGL 动画
动画就是不断变化各个顶点的位置,然后进行重绘
/**
* Created by hushhw on 17/12/14.
*/
//RotatingTriangle.js
var VSHADER_SOURCE =
'attribute vec4 a_Position;\n' +
'uniform mat4 u_ModelMatrix;\n' +
'void main() {\n' +
'gl_Position = u_ModelMatrix * a_Position;\n' +
'}\n';
var FSHADER_SOURCE=
'void main(){'+
'gl_FragColor = vec4(1.0, 0.0, 0.0, 1.0);'+
'}';
var ANGLE_STEP = 45.0;
function main() {
var canvas = document.getElementById("webgl");
if (!canvas) {
console.log("Failed to retrieve the <canvas> element");
return;
}
var gl = getWebGLContext(canvas);
if (!gl) {
console.log("Failed to get the rendering context for WebGL");
return;
}
if (!initShaders(gl, VSHADER_SOURCE, FSHADER_SOURCE)) {
console.log("Failed to initialize shaders.");
return;
}
//设置顶点位置
var n = initVertexBuffers(gl);
if (n < 0) {
console.log('Failed to set the positions of the vertices');
return;
}
gl.clearColor(0.0, 0.0, 0.0, 1.0);
var u_ModelMatrix = gl.getUniformLocation(gl.program, 'u_ModelMatrix');
if (u_ModelMatrix < 0) {
console.log("Failed to get the storage location of u_xformMatrix");
return;
}
var modelMatrix = new Matrix4();
var currentAngle = 0.0;
var tick = function () {
currentAngle = animate(currentAngle);
draw(gl, n, currentAngle, modelMatrix, u_ModelMatrix);
requestAnimationFrame(tick);
};
tick();
}
function initVertexBuffers(gl) {
var vertices = new Float32Array(
[0.0, 0.5, -0.5, -0.5, 0.5, -0.5]
);
var n=3; //点的个数
//创建缓冲区对象
var vertexBuffer = gl.createBuffer();
if(!vertexBuffer){
console.log("Failed to create thie buffer object");
return -1;
}
//将缓冲区对象保存到目标上
gl.bindBuffer(gl.ARRAY_BUFFER, vertexBuffer);
//向缓存对象写入数据
gl.bufferData(gl.ARRAY_BUFFER, vertices, gl.STATIC_DRAW);
var a_Position = gl.getAttribLocation(gl.program, 'a_Position');
if(a_Position < 0){
console.log("Failed to get the storage location of a_Position");
return -1;
}
//将缓冲区对象分配给a_Postion变量
gl.vertexAttribPointer(a_Position, 2, gl.FLOAT, false, 0, 0);
//连接a_Postion变量与分配给它的缓冲区对象
gl.enableVertexAttribArray(a_Position);
return n;
}
function draw(gl, n, currentAngle, modelMatrix, u_ModelMatrix)
{
modelMatrix.setRotate(currentAngle, 0, 0, 1);
gl.uniformMatrix4fv( u_ModelMatrix, false, modelMatrix.elements);
gl.clear(gl.COLOR_BUFFER_BIT);
gl.drawArrays(gl.TRIANGLES, 0, n);
}
var g_last = Date.now();
function animate(angle)
{
var now = Date.now();
var elapsed = now - g_last;
g_last = now;
var newAngle = angle + (ANGLE_STEP * elapsed) / 1000.0;
return newAngle %= 360;
}
颜色及纹理
多个缓存区共存
var vertexBuffer = this.gl.createBuffer();
var arr = []
this.points.map((item, index) => {
arr.push(item.x);
arr.push(item.y);
arr.push(10 * ++index);
})
var verticesSizes = new Float32Array(arr)
this.gl.bindBuffer(this.gl.ARRAY_BUFFER, vertexBuffer)
this.gl.bufferData(this.gl.ARRAY_BUFFER, verticesSizes, this.gl.STATIC_DRAW);
var FSIZE = verticesSizes.BYTES_PER_ELEMENT;
this.gl.vertexAttribPointer(this.a_Position, 2, this.gl.FLOAT, false, FSIZE * 3, 0);
this.gl.enableVertexAttribArray(this.a_Position);
this.gl.vertexAttribPointer(this.a_PointSize, 1, this.gl.FLOAT, false, FSIZE * 3, FSIZE * 2);
this.gl.enableVertexAttribArray(this.a_PointSize);
this.gl.drawArrays(this.gl.POINTS, 0, this.points.length);
多个数据使用一个缓存区时,就可以用到字段数据的长度间隔和 offse 来表示,FSIZE 是 单个数据长度,FSIZE * 3 是间隔3个数据取一次,FSIZE * 2,是偏移两个数据开始取,前面的 1 参数就是取的数据长度。this.gl.vertexAttribPointer(this.a_PointSize, 1, this.gl.FLOAT, false, FSIZE * 3, FSIZE * 2);
从顶点着色器将数据传入片元着色器
在顶点着色器中声明颜色varying vec4 v_Color;,然后将颜色从顶点着色器传入片元着色器
var VSHADER_SOURCE = `
attribute vec4 a_Position;
attribute float a_PointSize;
attribute vec4 a_Color;
// 将变量通过光栅化插入片元着色器
varying vec4 v_Color;
void main() {
gl_Position = a_Position;
gl_PointSize = a_PointSize;
v_Color = a_Color;
}
`;
var FSHADER_SOURCE = `
precision mediump float;
varying vec4 v_Color;
void main() {
gl_FragColor = v_Color;
}
`;
var gl = canvas.getContext('webgl');
initShaders(gl, VSHADER_SOURCE, FSHADER_SOURCE)
this.gl = gl;
this.points = [];
this.a_Position = gl.getAttribLocation(gl.program, 'a_Position');
this.a_PointSize = gl.getAttribLocation(gl.program, 'a_PointSize');
this.a_Color = gl.getAttribLocation(gl.program, 'a_Color');
this.gl.clearColor(0.0, 0.0, 0.0, 1.0);
this.gl.clear(this.gl.COLOR_BUFFER_BIT);
var vertexBuffer = this.gl.createBuffer();
var arr = []
this.points.map((item, index) => {
arr.push(item.x);
arr.push(item.y);
arr.push(10 * ++index);
arr.push(item.colorR)
arr.push(item.colorG)
arr.push(item.colorB)
})
var verticesSizes = new Float32Array(arr)
this.gl.bindBuffer(this.gl.ARRAY_BUFFER, vertexBuffer)
this.gl.bufferData(this.gl.ARRAY_BUFFER, verticesSizes, this.gl.STATIC_DRAW);
var FSIZE = verticesSizes.BYTES_PER_ELEMENT;
this.gl.vertexAttribPointer(this.a_Position, 2, this.gl.FLOAT, false, FSIZE * 6, 0);
this.gl.enableVertexAttribArray(this.a_Position);
this.gl.vertexAttribPointer(this.a_PointSize, 1, this.gl.FLOAT, false, FSIZE * 6, FSIZE * 2);
this.gl.enableVertexAttribArray(this.a_PointSize);
this.gl.vertexAttribPointer(this.a_Color, 3, this.gl.FLOAT, false, FSIZE * 6, FSIZE * 3);
this.gl.enableVertexAttribArray(this.a_Color);
this.gl.drawArrays(this.gl.POINTS, 0, this.points.length);
绘制过程
绘制图形是通过缓冲区对象、顶点着色器、图形装配、光栅化、片元着色器。
第一步:执行着色器,将缓存区的数据写入到顶点着色器中,并将坐标点传入储存的装配区中
第二步:装配图形,通过 drawArrays 来确定装配的图形。
第三步:显示在屏幕上的三角形是由片元组成的,所以还需要将图形转化为片元,这个过程被称为光栅化
第四步:对光栅化之后的片元进行逐片着色,最后形成图像
纹理
向模型上贴的图片我们称之为纹理,将纹理贴到模型的过程我们成为纹理映射。
纹理映射
- 准备好映射到集合图形上的纹理图像
- 为几何图形配置纹理映射方式
- 加载纹理图像,对其进行一些配置,以在 WebGL 中使用它
- 在片元着色器中将相应的纹素从纹理中抽取出来,并将纹素的颜色赋给片元
纹理坐标
纹理坐标是纹理图像上的坐标,通过纹理坐标可以在纹理图像上获取纹素颜色。WebGL 中的纹理坐标系统是二维的。为了和常见的二维坐标系分开,使用 s 和 t 作为坐标轴
initVertexBuffers(gl){
var verticesTexCoords = new Float32Array(
[
// -0.5, 0.5, 0.0, 1.0,
// -0.5, -0.5, 0.0, 0.0,
// 0.5, 0.5, 1.0, 1.0,
// 0.5, -0.5, 1.0, 0.0,
-0.5, 0.5, -0.3, 1.7,
-0.5, -0.5, -0.3, -0.2,
0.5, 0.5, 1.7, 1.7,
0.5, -0.5, 1.7, -0.2
]
);
var n=4;//顶点数目
//创建缓冲区对象
var vertexTexCoordBuffer = gl.createBuffer();
if(!vertexTexCoordBuffer){
console.log("Failed to create thie buffer object");
return -1;
}
//将缓冲区对象保存到目标上
gl.bindBuffer(gl.ARRAY_BUFFER, vertexTexCoordBuffer);
//向缓存对象写入数据
gl.bufferData(gl.ARRAY_BUFFER, verticesTexCoords, gl.STATIC_DRAW);
var FSIZE = verticesTexCoords.BYTES_PER_ELEMENT;
var a_Position = gl.getAttribLocation(gl.program, 'a_Position');
if(a_Position < 0){
console.log("Failed to get the storage location of a_Position");
return -1;
}
//将缓冲区对象分配给a_Postion变量
gl.vertexAttribPointer(a_Position, 2, gl.FLOAT, false, FSIZE*4, 0);
//连接a_Postion变量与分配给它的缓冲区对象
gl.enableVertexAttribArray(a_Position);
//将纹理坐标分配给a_TexCoord并开启它
var a_TexCoord = gl.getAttribLocation(gl.program, 'a_TexCoord');
if(a_TexCoord < 0){
console.log("Failed to get the storage location of a_TexCoord");
return -1;
}
gl.vertexAttribPointer(a_TexCoord, 2, gl.FLOAT, false, FSIZE*4, FSIZE*2);
gl.enableVertexAttribArray(a_TexCoord);
return n;
},
initTextures(gl, n){
var texture = gl.createTexture(); //创建纹理对象
if(!texture){
console.log('Failed to create the texture object');
return false;
}
//获取u_Sampler的存储位置
var u_Sampler = gl.getUniformLocation(gl.program, 'u_Sampler');
if (!u_Sampler) {
console.log('Failed to get the storage location of u_Sampler');
return false;
}
var image = new Image();//创建一个image对象
if (!image) {
console.log('Failed to create the image object');
return false;
}
//注册图像加载时间的响应函数
image.onload = function () {
gl.pixelStorei(gl.UNPACK_FLIP_Y_WEBGL, 1);//对纹理图像进行y轴反转
//开启0号纹理单元
gl.activeTexture(gl.TEXTURE0);
//向target绑定纹理对象
gl.bindTexture(gl.TEXTURE_2D, texture);
//配置纹理参数
gl.texParameteri(gl.TEXTURE_2D, gl.TEXTURE_MIN_FILTER, gl.LINEAR);
gl.texParameteri(gl.TEXTURE_2D, gl.TEXTURE_WRAP_S, gl.CLAMP_TO_EDGE);
gl.texParameteri(gl.TEXTURE_2D, gl.TEXTURE_WRAP_T, gl.MIRRORED_REPEAT);
//配置纹理图像
gl.texImage2D(gl.TEXTURE_2D, 0, gl.RGB, gl.RGB, gl.UNSIGNED_BYTE, image);
//将0号纹理传递给着色器
gl.uniform1i(u_Sampler, 0);
gl.clear(gl.COLOR_BUFFER_BIT);
gl.drawArrays(gl.TRIANGLE_STRIP, 0, n);//绘制矩形
};
//浏览器开始加载图像
image.src = img
return true;
}
var VSHADER_SOURCE = `
attribute vec4 a_Position;
attribute vec2 a_TexCoord;
varying vec2 v_TexCoord;
void main() {
gl_Position = a_Position;
v_TexCoord = a_TexCoord;
}
`;
var FSHADER_SOURCE = `
#ifdef GL_ES
precision mediump float;
#endif
uniform sampler2D u_Sampler;
varying vec2 v_TexCoord;
void main() {
gl_FragColor = texture2D(u_Sampler, v_TexCoord);
}
`;
var gl = canvas.getContext('webgl');
initShaders(gl, VSHADER_SOURCE, FSHADER_SOURCE)
this.gl = gl;
var n = this.initVertexBuffers(gl)
gl.clearColor(0.0, 0.0, 0.0, 1.0);
this.initTextures(gl, n);
- 顶点着色器中接收顶点的纹理坐标,光栅化后传递给片元着色器
- 片元着色器根据片元的纹理坐标,从纹理图像中抽取出纹素颜色,赋给当前片元。
- 设置顶点的纹理坐标
- 准备待加载的纹理图像,令浏览器读取它
- 监听纹理图像的加载事件,一旦加载完成,就在 WebGL 系统中使用纹理
使用纹理之前需要先创建纹理,gl.createTexture(),通过gl.pixelStorei(gl.UNPACK_FLIP_Y_WEBGL, 1);对纹理进行 Y 轴转换,因为纹理坐标系和 webGL 坐标系 Y 轴是相反的,通过gl.activeTexture(gl.TEXTURE0);激活纹理单元(纹理单元一般有 8 个,一般都是通过对 8 个纹理单元进行处理),绑定纹理对象gl.bindTexture(gl.TEXTURE_2D, texture);,纹理对象不能单独处理,只能通过将纹理对象绑定到缓冲区对象上才能处理
纹理参数处理,纹理参数包括TEXTURE_MIN_FILTER(纹理放大)、TEXTURE_MAG_FILTER(纹理缩小)、TEXTURE_WRAP_S(纹理水平填充)、TEXTURE_WRAP_T(纹理垂直填充)
gl.texParameteri(gl.TEXTURE_2D, gl.TEXTURE_MIN_FILTER, gl.LINEAR);
gl.texParameteri(gl.TEXTURE_2D, gl.TEXTURE_WRAP_S, gl.CLAMP_TO_EDGE);
gl.texParameteri(gl.TEXTURE_2D, gl.TEXTURE_WRAP_T, gl.MIRRORED_REPEAT);