代码之家 › 专栏 › 技术社区 › Blindman67

更快的HTML画布bresenham行

2d html5-canvas canvas javascript

Blindman67 · 技术社区 · 7 年前

慢渲染

我在用 Bresenham's line algorithm 实时渲染像素艺术线条。一次渲染1个像素 ctx.rect(x,y,1,1) 这是一个缓慢的操作。我不能使用像素缓冲区,这将大大减少渲染开销,因为我正在使用复合操作、alpha和过滤器(其中一些会污染画布)。

功能

function pixelArtLine(ctx, x1, y1, x2, y2) {
    x1 = Math.round(x1);
    y1 = Math.round(y1);
    x2 = Math.round(x2);
    y2 = Math.round(y2);
    const dx = Math.abs(x2 - x1);
    const sx = x1 < x2 ? 1 : -1;
    const dy = -Math.abs(y2 - y1);
    const sy = y1 < y2 ? 1 : -1;
    var e2, er = dx + dy, end = false;
    ctx.beginPath();
    while (!end) {
        ctx.rect(x1, y1, 1, 1);
        if (x1 === x2 && y1 === y2) {
            end = true;
        } else {
            e2 = 2 * er;
            if (e2 > dy) {
                er += dy;
                x1 += sx;
            }
            if (e2 < dx) {
                er += dx;
                y1 += sy;
            }
        }
    }
    ctx.fill();        
};

如何改进此功能?

3 回复 | 直到 7 年前

Mr. Reddy 7 年前

我可以建议两种方法来解决你的问题。第一种方法是使用ctx.createImageData(w,h)创建包含位图数组(imageData.data,它是一个uint8clampedary)的imageData对象,一旦操作完数据,就可以使用ctx.putImageData(imageData,0,0)将其放在画布上。

或者可以使用webgl提供的解决方案为您绘制线条。(如果要禁用平滑以获取像素化线,则只需在禁用抗锯齿的情况下创建GL上下文即可)。

使用webgl更为可取,因为目前用js编写的任何解决方案实际上一次只能在一个像素上操作(具有共享数组缓冲区的web工作者可以为您提供并发多线程js,但今年年初在所有浏览器中都禁用了它)。

下面是一个由webgl驱动的模块,可以用来快速绘制不同厚度和颜色的线条。

(为了测试速度,下面的代码片段绘制了10000行)。

<!doctype html>
<html>
	<head>
		<meta charset="utf-8">
		<style>
			body {
				background-color: black;
			}
			
			canvas {
				display: block;
				margin-top: 30px;
				margin-left: auto;
				margin-right: auto;
				border: solid 1px white;
				border-radius: 10px;
				width: 180px;
				height: 160px;
			}
		</style>
	</head>
	
	<body>
		<canvas id="canvas"></canvas>
		<script type="application/javascript">
		
		var glLine = function() {
			
			"use strict";
			
			var width = 1;
			var height = 1;
			var lineWidth = 1;
			var tmpBuffer = new Float32Array(12);
			var canvas = document.createElement("canvas");
			var gl = canvas.getContext("webgl",{antialias: false,preserveDrawingBuffer: true});
				gl.clearColor(0.0,0.0,0.0,0.0);
			
			var buffer = function() {
				var b = gl.createBuffer();
				
				gl.bindBuffer(gl.ARRAY_BUFFER,b);
				gl.bufferData(gl.ARRAY_BUFFER,tmpBuffer,gl.DYNAMIC_DRAW);
			}();
			
			var uInvResolution = null;
			var uColour = null;
			
			var program = function() {
				var vs = gl.createShader(gl.VERTEX_SHADER);
				var fs = gl.createShader(gl.FRAGMENT_SHADER);
				
				gl.shaderSource(vs,`
					precision lowp float;
					
					attribute vec2 aPosition;
					
					uniform vec2 uInvResolution;
					
					void main() {
						vec2 vPosition = vec2(
							aPosition.x * uInvResolution.x * 2.0 - 1.0,
							-(aPosition.y * uInvResolution.y * 2.0 - 1.0)
						);
						
						gl_Position = vec4(vPosition,0.0,1.0);
					}
				`);
				
				gl.shaderSource(fs,`
					precision lowp float;
					
					uniform vec4 uColour;
					
					void main() {
						gl_FragColor = uColour;
					}
				`);
				
				gl.compileShader(vs);
				gl.compileShader(fs);
				
				var p = gl.createProgram();
				
				gl.attachShader(p,vs);
				gl.attachShader(p,fs);
				gl.linkProgram(p);
				gl.deleteShader(vs);
				gl.deleteShader(fs);
				gl.useProgram(p);
				
				uInvResolution = gl.getUniformLocation(p,"uInvResolution");
				uColour = gl.getUniformLocation(p,"uColour");
				
				return p;
			}();
			
			gl.vertexAttribPointer(0,2,gl.FLOAT,gl.FALSE,8,0);
			gl.enableVertexAttribArray(0);
			
			addEventListener("unload",function() {
				gl.deleteBuffer(buffer);
				gl.deleteProgram(program);
				gl = null;
			});
			
			return {
				clear: function() {
					gl.clear(gl.COLOR_BUFFER_BIT);
				},
				
				draw: function(x1,y1,x2,y2) {
					var x = x2 - x1;
					var y = y2 - y1;
					var invL = 1.0 / Math.sqrt(x * x + y * y);
					
					x = x * invL;
					y = y * invL;
					
					var hLineWidth = lineWidth * 0.5;
					var bl_x = x1 - y * hLineWidth;
					var bl_y = y1 + x * hLineWidth;
					var br_x = x1 + y * hLineWidth;
					var br_y = y1 - x * hLineWidth;
					var tl_x = x2 - y * hLineWidth;
					var tl_y = y2 + x * hLineWidth;
					var tr_x = x2 + y * hLineWidth;
					var tr_y = y2 - x * hLineWidth;
					
					tmpBuffer[0] = tr_x;
					tmpBuffer[1] = tr_y;
					tmpBuffer[2] = bl_x;
					tmpBuffer[3] = bl_y;
					tmpBuffer[4] = br_x;
					tmpBuffer[5] = br_y;
					tmpBuffer[6] = tr_x;
					tmpBuffer[7] = tr_y;
					tmpBuffer[8] = tl_x;
					tmpBuffer[9] = tl_y;
					tmpBuffer[10] = bl_x;
					tmpBuffer[11] = bl_y;
					
					gl.bufferSubData(gl.ARRAY_BUFFER,0,tmpBuffer);
					gl.drawArrays(gl.TRIANGLES,0,6);
				},
				
				setColour: function(r,g,b,a) {
					gl.uniform4f(
						uColour,
						r * 0.00392156862745098,
						g * 0.00392156862745098,
						b * 0.00392156862745098,
						a * 0.00392156862745098
					);
				},
				
				setLineWidth: function(width) {
					lineWidth = width;
				},
				
				setSize: function(_width,_height) {
					width = _width;
					height = _height;
					
					canvas.width = width;
					canvas.height = height;
					
					gl.uniform2f(uInvResolution,1.0 / width,1.0 / height);
					gl.viewport(0,0,width,height);
					gl.clear(gl.COLOR_BUFFER_BIT);
				},
				
				getImage: function() {
					return canvas;
				}
			};
			
		}();
		
		void function() {
			
			"use strict";
			
			var canvasWidth = 180;
			var canvasHeight = 160;
			var canvas = null;
			var ctx = null;
			
			onload = function() {
				canvas = document.getElementById("canvas");
				canvas.width = canvasWidth;
				canvas.height = canvasHeight;
				ctx = canvas.getContext("2d");
				
				glLine.setSize(canvasWidth,canvasHeight);
				
				ctx.fillStyle = "gray";
				ctx.fillRect(0,0,canvasWidth,canvasHeight);
				
				for (var i = 0, l = 10000; i < l; ++i) {
					glLine.setColour(
						(Math.random() * 255) | 0,
						(Math.random() * 255) | 0,
						(Math.random() * 255) | 0,
						255
					);
					
					glLine.setLineWidth(
						3 + (Math.random() * 5) | 0
					);
					
					glLine.draw(
						Math.random() * canvasWidth,
						Math.random() * canvasHeight,
						Math.random() * canvasWidth,
						Math.random() * canvasHeight
					);
				}
				
				ctx.drawImage(glLine.getImage(),0,0);
			}
			
		}();
		
		</script>
	</body>
</html>

Blindman67 7 年前

Fast Bresenham的HTML5画布系列。

解决方案

如果减少路径调用的数量,则可以改进渲染。例如少打电话给 ctx.rect(x,y,1,1);

一个1像素长的矩形和20像素长的矩形在渲染时间上的差异太小,我无法测量。所以减少通话次数会有很大的改善。

看一条从1,1到15,5的线路需要打10个电话 ctx.rect

//     shows 10 pixels render of line 1,1 to 15,5
// ###
//    ###
//       ###
//          ###
//             ###

但它只能用3个像素宽的矩形进行5次调用。

标准算法要求最大坐标长度加上一个路径调用。例1,1至15,5为 Math.max(15-1, 5-1) + 1 === 15 但它可以在最小长度+1 eg内完成 Math.min(15-1, 5-1) + 1 === 5

新算法

使用与bresenham线相同的误差方法,并以八度角工作,可从累积误差值计算到下一y步(八度角0)或x步(八度角1)的距离。这段距离使 ctx.rect公司 要绘制的像素长度和添加到下一行的错误的量。

水平线和垂直线在单个路径调用中呈现。45度的行需要最多的路径调用,但由于这是一种特殊情况,因此该函数可以获得javascript性能优势。

对于随机选择的行,它应该将draw调用的数量减少到42%

function BMFastPixelArtLine(ctx, x1, y1, x2, y2) {
    x1 = Math.round(x1);
    y1 = Math.round(y1);
    x2 = Math.round(x2);
    y2 = Math.round(y2);
    const dx = Math.abs(x2 - x1);
    const sx = x1 < x2 ? 1 : -1;
    const dy = Math.abs(y2 - y1);
    const sy = y1 < y2 ? 1 : -1;
    var error, len, rev, count = dx;
    ctx.beginPath();
    if (dx > dy) {
        error = dx / 2;
        rev = x1 > x2 ? 1 : 0;
        if (dy > 1) {
            error = 0;
            count = dy - 1;
            do {
                len = error / dy + 2 | 0;
                ctx.rect(x1 - len * rev, y1, len, 1);
                x1 += len * sx;
                y1 += sy;
                error -= len * dy - dx;
            } while (count--);
        }
        if (error > 0) {ctx.rect(x1, y2, x2 - x1, 1) }
    } else if (dx < dy) {
        error = dy / 2;
        rev = y1 > y2 ? 1 : 0;
        if (dx > 1) {
            error = 0;
            count --;
            do {
                len = error / dx + 2 | 0;
                ctx.rect(x1 ,y1 - len * rev, 1, len);
                y1 += len * sy;
                x1 += sx;
                error -= len * dx - dy;
            } while (count--);
        }
        if (error > 0) { ctx.rect(x2, y1, 1, y2 - y1) }
    } else {
        do {
            ctx.rect(x1, y1, 1, 1);
            x1 += sx;
            y1 += sy;
        } while (count --); 
    }
    ctx.fill();
}

缺点:生成的函数稍长,与原始的像素不完全匹配,错误仍然会使像素保持在直线上。
优点:随机均匀分布的线路平均性能提高了55%。最坏的情况是(接近45度的线路(在45度的线路上速度更快))太小,以至于无法调用。最佳情况(水平或垂直或近水平)快70-80%。还有一个额外的好处,因为该算法更适合渲染像素艺术多边形。

Kaiido NickSlash 7 年前

既然你在做像素艺术,为什么不在像素级:直接操作图像数据。

你说你的画布很可能会被污染,它会设置过滤器和GCO。这些都不重要。

使用第二个屏幕外画布,只生成像素艺术渲染。将其大小设置为渲染像素网格之一(即originalcanvassize/pixelsize)。
直接在屏幕外的图像数据上进行数学运算。
将imagedaat放到屏幕外的画布上使用GCO设置像素艺术颜色。使用 drawImage 无图像平滑( imageSmoothingEnbaled = false )

希望应用于路径图形的过滤器和GCO也将应用于此最终版本 drawImage(offscreenCanvas)

我相信你可以用更干净的方式重写它,但这里有一个粗略的概念证明:

class PixelArtDrawer {
  constructor(ctx, options = {}) {
    if (!(ctx instanceof CanvasRenderingContext2D)) {
      throw new TypeError('Invalid Argument 1, not a canvas 2d context');
    }
    this.cursor = {
      x: 0,
      y: 0
    };
    this.strokeStyle = '#000';
    this.renderer = ctx;
    this.ctx = document.createElement('canvas').getContext('2d');
    this.setPixelSize((options && options.pixelSize) || 10);
  }
  setPixelSize(pixelSize) {
    this.pixelSize = pixelSize;
    const ctx = this.ctx;
    const canvas = ctx.canvas;
    const renderer = this.renderer.canvas;

    canvas.width = (renderer.width / pixelSize) | 0;
    canvas.height = (renderer.height / pixelSize) | 0;
    ctx.globalCompositeOperation = 'source-in';
    this.image = ctx.createImageData(canvas.width, canvas.height);
    this.data = new Uint32Array(this.image.data.buffer);
  }
  beginPath() {
    this.data.fill(0);
    this.cursor.x = this.cursor.y = null;
  }
  stroke() {
    const renderer = this.renderer
    const currentSmoothing = renderer.imageSmoothingEnbaled;
    const ctx = this.ctx;
    ctx.putImageData(this.image, 0, 0);
    // put the color
    ctx.fillStyle = this.strokeStyle;
    ctx.fillRect(0, 0, this.image.width, this.image.height);
    renderer.imageSmoothingEnabled = false;
    renderer.drawImage(ctx.canvas, 0, 0, renderer.canvas.width, renderer.canvas.height);
    renderer.imageSmoothingEnabled = currentSmoothing;
  }
  moveTo(x, y) {
    this.cursor.x = (x / this.pixelSize) | 0;
    this.cursor.y = (y / this.pixelSize) | 0;
  }
  lineTo(x, y) {
    if (this.cursor.x === null) {
      this.moveTo(x, y);
      return;
    }
    const data = this.data;
    const width = this.image.width;
    const height = this.image.height;
    var x1 = this.cursor.x;
    var y1 = this.cursor.y;

    const x2 = (x / this.pixelSize) | 0;
    const y2 = (y / this.pixelSize) | 0;
    // from here it is OP's code
    const dx = Math.abs(x2 - x1);
    const sx = x1 < x2 ? 1 : -1;
    const dy = -Math.abs(y2 - y1);
    const sy = y1 < y2 ? 1 : -1;
    var e2, er = dx + dy,
      end = false;
    var index;
    while (!end) {
      // this check would probably be better done out of the loop
      if (x1 >= 0 && x1 <= width && y1 >= 0 && y1 <= height) {
        // here we need to convert x, y coords to array index
        index = ((y1 * width) + x1) | 0;
        data[index] = 0xff000000;
      }
      if (x1 === x2 && y1 === y2) {
        end = true;
      } else {
        e2 = 2 * er;
        if (e2 > dy) {
          er += dy;
          x1 += sx;
        }
        if (e2 < dx) {
          er += dx;
          y1 += sy;
        }
      }
    }
    this.cursor.x = x2;
    this.cursor.y = y2;
  }
}
const ctx = renderer.getContext('2d');
const pixelArt = new PixelArtDrawer(ctx);
const points = [{
  x: 0,
  y: 0
}, {
  x: 0,
  y: 0
}];

draw();

renderer.onmousemove = function(e) {
  const rect = this.getBoundingClientRect();
  const lastPoint = points[points.length - 1];
  lastPoint.x = e.clientX - rect.left;
  lastPoint.y = e.clientY - rect.top;
};
renderer.onclick = e => {
  const lastPoint = points[points.length - 1];
  points.push({
    x: lastPoint.x,
    y: lastPoint.y
  });
};

function draw() {
  ctx.clearRect(0, 0, renderer.width, renderer.height);
  pixelArt.beginPath();
  points.forEach(drawLine);
  pixelArt.stroke();
  requestAnimationFrame(draw);
}

function drawLine(pt) {
  pixelArt.lineTo(pt.x, pt.y);
}
color_picker.onchange = function() {
  pixelArt.strokeStyle = this.value;
}

<input type="color" id="color_picker"><br>
<canvas id="renderer" width="500" height="500"></canvas>