Быстрая линия Брезенхэма для холста HTML

Question

Медленный рендеринг

Я использую Алгоритм линии Брезенхема для рендеринга линий пиксельной графики в реальном времени.Он рендерит 1 пиксель за раз ctx.rect(x,y,1,1), что является медленной операцией.Я не могу использовать пиксельный буфер, который значительно уменьшит накладные расходы при рендеринге, так как я использую составные операции, альфа и фильтры (некоторые из которых портят холст).

Функция

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();        
};

Как я могу улучшить эту функцию?

Answer 1

Поскольку вы создаете пиксельную графику, почему бы не сделать ее на уровне пикселей: манипулировать ImageData напрямую.

Вы заявили, что ваш холст может быть испорчен, и на нем будут настроены фильтры и gCO.,Ничто из этого не имеет значения.

Используйте второй закадровый холст, только для генерации ваших пиксельных изображений.Установите его размер на одну из ваших сеток визуализированных пикселей (то есть originalCanvasSize / pixelSize).
Выполните математику непосредственно на ImageData вне экрана.
Поместите 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>

---

Answer 2

Я могу предложить два способа решения вашей проблемы.Во-первых, используйте ctx.createImageData (w, h) для создания объекта imageData, который содержит массив растровых изображений (ImageData.data, это Uint8ClampedArray). Как только вы закончите манипулировать данными, его можно поместить на холст с помощью ctx.putImageData (ImageData, 0,0).

Или вы можете использовать решение на основе WebGL, чтобы нарисовать свои линии для вас.(Если вы хотите отключить сглаживание для получения пиксельных линий, контекст gl просто необходимо создать с отключенным сглаживанием).

Использование WebGL предпочтительнее, так как любое решение, написанное в JS на данный момент, может реально работать только на одномпиксель за раз (Web Workers с буфером общего массива могут предоставить вам параллельный многопоточный 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>

Answer 3

Быстрая строка Брезенхэма для HTML5 canvas.

Решение

Визуализация может быть улучшена, если я уменьшу количество вызовов пути.например, меньше вызовов 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
// ###
//    ###
//       ###
//          ###
//             ###

Но это можетобрабатываться всего 5 вызовами с использованием прямоугольников шириной 3 пикселя.

Стандартный алгоритм требует максимальной длины координат плюс один вызов пути.Например, от 1,1 до 15,5 - это Math.max(15-1, 5-1) + 1 === 15, но это можно сделать за минимальную длину + 1 Например, Math.min(15-1, 5-1) + 1 === 5

Новый алгоритм

Используя тот же метод ошибок, что и в строке Брезенхэмаи, работая в октантах, расстояние до следующего шага y (октант 0) или шага x (октант 1) может быть вычислено из значения накопленной ошибки.Это расстояние дает длину ctx.rect в пикселях для рисования и сумму, добавляемую к ошибке для следующей строки.

Горизонтальные и вертикальные линии отображаются в одном вызове пути.Строки в 45 градусов требуют наибольшего количества вызовов пути, но в особом случае функция получает выигрыш в производительности JavaScript.

Для случайного выбора линий следует уменьшить количество вызовов отрисовки до 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% + быстрее.Это также дает дополнительное преимущество, так как этот алгоритм гораздо лучше подходит для рендеринга полигональных полигонов.