Как использовать линейный алгоритм Брезенхэма?

Делаю игру и столкнулся со странной проблемой. Итак, я нашел JS-код для рисования линии по алгоритму Брезенхема, без функции plot() (может быть, я пишу неправильно), и все это работает странно:

  1. Начало x, y и конец x, y для рисования линий по какой-то причине перевернуты
  2. В некоторых случаях линия не рисуется, как в приведенном ниже коде, где я вызвал функцию castRay(8,0,4,4)
  3. Линия не рисуется, кроме одной точки в черт знает где позиции

Что я делаю неправильно?

let ctx = canvas.getContext("2d");
const TILE = 30;
let map = [
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 1, 1, 0, 0, 0, 0, 0, 0],
  [0, 0, 1, 1, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 1, 1, 1, 1, 1, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
];
ctx.fillStyle = "rgba(0,50,200)";
ctx.fillRect(0, 0, canvas.width, canvas.height);
for (let i = 0; i < 10; i++) {
  for (let j = 0; j < 10; j++) {
    if (map[i][j] === 1) {
      ctx.fillStyle = "black";
      ctx.fillRect(j * TILE, i * TILE, TILE - 1, TILE - 1)
    }
    if (map[i][j] === 0) {
      ctx.fillStyle = "gray";
      ctx.fillRect(j * TILE, i * TILE, TILE - 1, TILE - 1)
    }
  }
}
let plot = (x, y) => {
  ctx.fillRect(x * TILE, y * TILE, TILE, TILE);
  return true;
}

let castRay = (x0, y0, x1, y1) => {
  let tmp;
  let steep = Math.abs(y1 - y0) > Math.abs(x1 - x0);
  if (steep) {
    tmp = x0;
    x0 = y0;
    y0 = tmp;
    tmp = x1;
    x1 = y1;
    y1 = tmp;
  }

  let sign = 1;
  if (x0 > x1) {
    sign = -1;
    x0 *= -1;
    x1 *= -1;
  }

  let dx = x1 - x0;
  let dy = Math.abs(y1 - y0);
  let err = ((dx / 2));
  let ystep = y0 < y1 ? 1 : -1;
  let y = y0;

  for (let x = 0; x <= x1; x++) {
    if (!(steep ? plot(y, sign * x) : plot(sign * x, y))) return;
    err = (err - dy);
    if (err < 0) {
      y += ystep;
      err += dx;
    }
  }
}

ctx.fillStyle = "green";
castRay(0, 0, 4, 4);
ctx.fillStyle = "rgb(0,0,255)";
castRay(8, 0, 4, 4)
<canvas width="300" height="300" id="canvas"></canvas>


javascript bresenham
person ran4erep    schedule 15.07.2020    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Я бы избавился от переменной sign и вместо этого просто поменял местами соответствующие переменные внутри условия if (x0 > x1). Кроме того, рисование линий всегда начинается с x=0, потому что вы не установили его на x0.

for (let x = 0; x <= x1; x++)

должно быть

for (let x = x0; x <= x1; x++)

Вот обновленный пример кода:

let ctx = canvas.getContext("2d");
const TILE = 30;
let map = [
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 1, 1, 0, 0, 0, 0, 0, 0],
  [0, 0, 1, 1, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 1, 1, 1, 1, 1, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
];
ctx.fillStyle = "rgba(0,50,200)";
ctx.fillRect(0, 0, canvas.width, canvas.height);
for (let i = 0; i < 10; i++) {
  for (let j = 0; j < 10; j++) {
    if (map[i][j] === 1) {
      ctx.fillStyle = "black";
      ctx.fillRect(j * TILE, i * TILE, TILE - 1, TILE - 1)
    }
    if (map[i][j] === 0) {
      ctx.fillStyle = "gray";
      ctx.fillRect(j * TILE, i * TILE, TILE - 1, TILE - 1)
    }
  }
}
let plot = (x, y) => {
  ctx.fillRect(x * TILE, y * TILE, TILE, TILE);
  return true;
}

let castRay = (x0, y0, x1, y1) => {
  let tmp = x0;
  let steep = Math.abs(y1 - y0) > Math.abs(x1 - x0);
  if (steep) {
    x0 = y0;
    y0 = tmp;
    tmp = x1;
    x1 = y1;
    y1 = tmp;
  }

  if (x0 > x1) {
    x0 = x1;
    x1 = tmp;
    tmp = y0;
    y0 = y1;
    y1 = tmp;
  }

  let dx = x1 - x0;
  let dy = Math.abs(y1 - y0);
  let err = ((dx / 2));
  let ystep = y0 < y1 ? 1 : -1;
  let y = y0;

  for (let x = x0; x <= x1; x++) {
    if (!(steep ? plot(y, x) : plot(x, y))) return;
    err = (err - dy);
    if (err < 0) {
      y += ystep;
      err += dx;
    }
  }
}

ctx.fillStyle = "green";
castRay(0, 0, 4, 4);
ctx.fillStyle = "rgb(0,0,255)";
castRay(8, 0, 4, 4)
<canvas width="300" height="300" id="canvas">

person obscure    schedule 15.07.2020
comment
спасибо, теперь это работает, но не совсем так, как ожидалось. Если я нарисую линию от координаты 4x4 до 0x0, то она построит линию от 0x0, а не от 4x4. Но если я построю линию от 4x4 до 0x9, она начнется с 4x4, как и должно быть. - person ran4erep; 15.07.2020
comment
Это потому, что ваша реализация Bresenham не завершена. Он не охватывает все крайние случаи. Вот хорошее чтение в Википедии https://en.wikipedia.org/wiki/Bresenham - person obscure; 15.07.2020