Реализация алгоритма Брезенхэма на FPGA

09.11.2025

В конце сентября — начале октября в Барнауле прошёл кейс-чемпионат «Код успеха». Одним из заданий, «Retro Game Console», было создание модуля на FPGA для отрисовки векторного каркаса без фреймбуфера: изображение формировалось «на лету» во время сканирования кадра. Вспомнив алгоритм Брезенхэма, я принялся за работу, хотя реализация заняла гораздо больше времени, чем ожидалось.

Краткое напоминание об алгоритме Брезенхэма

Рассмотрим линию с углом наклона от 0° до 45° между точками (x₁, y₁) и (x₂, y₂). Школьное уравнение прямой:

y = kx + c, где k = (y₂ − y₁)/(x₂ − x₁), c = y₁ − k·x₁.

В итерационном виде приращения координат:

x_{i+1} = x_i + 1
y_{i+1} = y_i + k

Чтобы обойтись целыми числами, вводят переменную error и накапливают в ней приращение Δy. Когда error превышает Δx, из error вычитают Δx и увеличивают y на 1. Формулы:

error_{i+1} = error_i + Δy - (error_i + Δy >= Δx ? Δx : 0)
y_{i+1}     = y_i     + ((error_i + Δy >= Δx) ? 1 : 0)

В SystemVerilog я использовал always_comb для вычисления следующей точки и always_ff для сохранения координат и ошибки:

always_comb begin
  new_y = dot_y;
  if (error + dy > dx) begin
    new_error = error + dy - dx;
    new_y     = dot_y + 1;
  end else begin
    new_error = error + dy;
  end
end

always_ff @(posedge clk) begin
  if (start_frame) begin
    dot_x <= in_x1;
    dot_y <= in_y1;
    error <= 0;
  end else if (en) begin
    dot_x <= dot_x + 1;
    dot_y <= new_y;
    error <= new_error;
  end
end

Синхронизируем расчёт и отображение точек, так как частота тактирования вдвое выше частоты вывода пикселей:

assign en  = (y == dot_y) & (x == dot_x) & (x <= in_x2);
assign out = (x == dot_x) & (y == dot_y);

Реализация алгоритма Брезенхэма на FPGA — Первые результаты: линия получилась слишком тусклой.

Чтобы усилить яркость, сигнал out сохраняют в триггер на время отображения пикселя:

always_ff @(posedge clk)
  pred_x <= x[0];
assign strobe_x = x ^ pred_x;

always_ff @(posedge clk)
  if (strobe_x)
    line_out <= (x == dot_x) & (y == dot_y);

assign out = line_out;

Сравнение яркости линий — Слева — старая линия, справа — более яркая.

Для отрисовки линий с углом от 45° до 90° достаточно поменять роли координат: наращивать y, а x корректировать по накопленному error. Вводятся сигналы s1 и s2 для выбора сектора:

assign s1 = ((x2 - x1) >= (y2 - y1));
assign s2 = ((x2 - x1) <  (y2 - y1));

always_comb begin
  new_x     = dot_x;
  new_y     = dot_y;
  new_error = error;
  case ({s2, s1})
    2'b01: // 0°–45°
      if (error + dy > dx) begin
        new_error = error + dy - dx;
        new_y     = dot_y + 1;
      end else
        new_error = error + dy;

    2'b10: // 45°–90°
      if (error + dx > dy) begin
        new_error = error + dx - dy;
        new_x     = dot_x + 1;
      end else
        new_error = error + dx;
  endcase
end

always_ff @(posedge clk) begin
  if (start_frame) begin
    dot_x <= in_x1;
    dot_y <= in_y1;
    error <= 0;
  end else begin
    if (en1) begin
      dot_x <= dot_x + 1;
      dot_y <= new_y;
      error <= new_error;
    end
    if (en2) begin
      dot_x <= new_x;
      dot_y <= dot_y + 1;
      error <= new_error;
    end
  end
end

Сектора 90°–135° обрабатываются аналогично, но с уменьшением x при накоплении ошибки. Самый сложный был диапазон 135°–180°, где точки предыдущих строк нужно было рисовать «задним числом». Решение: на каждой строке вычислять начало x_st и конец x_end горизонтального отрезка и подсвечивать их при выводе строки.

// Вычисление точек и границ отрезков 0°–180°
always_comb begin
  new_x     = dot_x;
  new_y     = dot_y;
  new_error = error;
  case ({s4, s3, s2, s1})
    4'b0001: // сектор 1
      if (error + dy > dx) begin
        new_error = error + dy - dx;
        new_y     = dot_y + 1;
      end else
        new_error = error + dy;

    4'b0010,
    4'b0100: // сектора 2 и 3
      if (error + dx > dy) begin
        new_error = error + dx - dy;
        new_x     = s2 ? dot_x + 1 : dot_x - 1;
      end else
        new_error = error + dx;

    4'b1000: // сектор 4
      new_error = error + dy;
  endcase
end

always_ff @(posedge clk) begin
  if (start_frame) begin
    dot_x <= in_x1;
    dot_y <= in_y1;
    error <= 0;
    x_end <= in_x1;
  end else begin
    if (en1) begin
      dot_x <= dot_x + 1;
      dot_y <= new_y;
      error <= new_error;
    end
    if (en2 || en3) begin
      dot_x <= new_x;
      dot_y <= dot_y + 1;
      error <= new_error;
    end
    if (en4) begin
      if (error <= dx) begin
        dot_x <= dot_x - 1;
        error <= new_error;
      end else if (x == screen_width) begin
        x_st  <= dot_x;
        x_end <= (y + 1 == y1) ? in_x1 : x_st;
        error <= error - dx;
      end
    end
  end
end

always_ff @(posedge clk)
  if (strobe_x)
    line_out <= (x == dot_x) & (y == dot_y);

Построение пирамиды из линий — Пример: любую фигуру, например пирамиду, можно построить одним алгоритмом.

Данная реализация демонстрирует возможности и может быть оптимизирована.
Алгоритм Брезенхэма отлично подходит для учебных и конкурсных задач на FPGA и часто выявляет необычные ограничения.
Благодарю организаторов «Код успеха» за интересные задания и надеюсь на новые мероприятия.

PS: Исходный код модуля доступен в моём репозитории.

Источник

Реализация алгоритма Брезенхэма на FPGA

Читайте также

Паблик ВКонтакте

Последние посты