Алгоритм Брезенхейма

Алгоритм Брезенхейма — алгоритм, який визначає які точки в n-вимірному растрі мають бути накреслені для формування близького наближення для прямої лінії між двома заданими точками. Він загально використовується для малювання ліній на екрані через те, що використовує тільки цілочисельну суму, віднімання та бітові операції, всі ці операції дуже «дешеві» в стандартній архітектурі комп'ютерів. Це один з перших алгоритмів розроблених в галузі комп'ютерної графіки. Незначно розширений початковий алгоритм також обробляє малювання кіл.

Хоча алгоритм Ву також часто використовується в сучасній комп'ютерній графіці через підтримку згладжування, алгоритм Брезенхейма залишається вживаним завдяки його швидкісті і простоті. Алгоритм використовується в графобудівниках і графічних процесорах сучасних відеокарт. Також його можна знайти в багатьох програмних графічних бібліотеках. Через свою простоту алгоритм часто реалізується або як вбудована програма або як апаратне забезпечення сучасних відеокарт.

Позначка "Брезенхейм" використовується сьогодні для цілого сімейства алгоритмів, що розширюють або модифікують початковий алгоритм Брезенхейма.

Алгоритм

Ілюстрація результату роботи алгоритму Брезенхейма. (0,0) в верхньому лівому куті

Будемо слідувати загальноприйнятій домовленості, що координати ростуть вниз і праворуч, а також, що ми використовуємо центри пікселів, що мають цілочисельні координати. Кінцевими точками відрізка є пікселі з координатами $(x_{0},y_{0})$ та $(x_{1},y_{1})$, де перша координата за горизонталлю, друга за вертикаллю.

Спочатку алгоритм буде розглянутий для октанта в якому відрізок спрямований праворуч і донизу ($x_{0}\leqslant x_{1}\land y_{0}\leqslant y_{1}$), і його горизонтальна проєкція $x_{1}-x_{0}$ довша за вертикальну $y_{1}-y_{0}$ (лінія має кутовий коефіцієнт за модулем менше 1 і більше ніж 0.) В цьому октанті для кожного стовпця x між $x_{0}$ та $x_{1}$, існує лише один рядок y (обчислений за допомогою алгоритму) з пікселем на лінії, тоді як кожний рядок між $y_{0}$ та $y_{1}$ може містити декілька пікселів лінії.

Алгоритм Брезенхейма обирає ціле y таким чином, щоб центр пікселя був найближчим до ідеального (дробового) y для того ж x; y може залишитися тим самим або бути збільшеним на 1. Загальне рівняння лінії через дві точки таке:

${\frac {y-y_{0}}{y_{1}-y_{0}}}={\frac {x-x_{0}}{x_{1}-x_{0}}}.$

Тому що ми знаємо стовпець x, рядок y отримується шляхом округлення наступного результату:

$y={\frac {y_{1}-y_{0}}{x_{1}-x_{0}}}(x-x_{0})+y_{0}$ або $y=kx+b$,

де кутовий коефіцієнт $k=(y_{1}-y_{0})/(x_{1}-x_{0})$ залежить тільки від координат точок і може бути обчислений заздалегідь, і ідеальний y для відповідного цілого x може бути обчислений починаючи від $y_{0}$ додаючи кутовий коефіцієнт раз за разом, а $b=y_{0}-kx_{0}$.

На практиці, через те, що кутовий коефіцієнт за модулем менший ніж 1 і більший ніж 0, ми на кожному кроці або збільшуємо y на 1 або залишаємо попереднє значення, зберігаючи дробову частину в додатковій змінній c. Тоді $c_{i}=kx_{i}+b-[kx_{i}+b]$.

Тоді, якщо $c_{i}<0.5$, покладемо $y_{i}=[kx_{i}+b]$, інакше $y_{i}=[kx_{i}+b]+1$.

Зауважимо, що $c_{0}=0$ через те, що точка $(x_{0},y_{0})$ належить прямій $y=kx+b$.

В наступному псевдокоді plot(x,y) малює точку і abs повертає абсолютну величину:

 function line(x0, x1, y0, y1)
     int deltax := x1 - x0
     int deltay := y1 - y0
     real c := 0
     real k := deltay / deltax    // Припускаємо, що deltax != 0 (пряма не вертикальна),
           // зауважимо, що це ділення має бути зроблено у спосіб, що зберігає дробову частину
     int y := y0
     for x from x0 to x1
         plot(x,y)
         c := c + k
         if abs(c) ≥ 0.5 then
             y := y + 1
             c := c - 1.0

Порівнювати з нулем зручніше ніж з 0.5, тому введемо нову допоміжну величину $d_{i}=2c_{i}-1$, зауважимо, що $d_{1}=2k-1$ (тому що $c_{1}=k$).

void line(int x0, int y0, int x1, int y1, int color)
{
  double k = ((double)(y1 - y0))/(x1-x0);
  double d = 2*k - 1;
  int y = y0;

  putpixel(x0, y0, color);

  for (int x = x0 + 1; x <= x1; x++)
  {
    if (d > 0)
    {
      d += 2*k - 2;
      y++;
    }
    else
      d += 2*k;
    
    putpixel(x, y, color);
  }
}

Попри те, що вхідні дані цілочисельні і всі операції здійснюються на цілочисельній ґратці, алгоритм використовує операції з дійсними числами. Щоб позбутися необхідності їх використання, зауважимо, що всі дійсні числа присутні в алгоритмі є числами виду ${\frac {p}{\Delta {x}}},p\in {Z}$. Тому можливо домножити $d_{i}$ та $k$ на $\Delta {x}=x_{1}-x_{0}$, і отримати в результаті тільки цілі числа. Тим самим отримаємо алгоритм Брезенхейма.

// найпростіший алгоритм Брезенхейма. 0 <= y1 - y0 <= x1 - x0
void line (int x0, int x1, int y0, int y1, int color)
{
  int dx = x1 - x0;
  int dy = y1 - y0;
  int d = (dy << 1) - dx;
  int d1 = dy << 1;
  int d2 = (dy - dx) << 1;
  putpixel(x0, y0, color);
  for(int x = x0 + 1, y = y0; x <= x1; x++)
  {
    if ( d >0)
    {
      d += d2;
      y += 1;
    }
    else
      d += d1;
    putpixel(x, y, color);
  }
}

Також наведемо узагальнений алгоритм, який враховує можливі напрямки відрізка, а також співвідношення $\Delta {x}$ до $\Delta {y}$:

void segment(int x0, int y0, int x1, int y1, int color)
{
  int dx = abs(x1 - x0);
  int dy = abs(y1 - y0);
  int sx = x1 >= x0 ? 1 : -1;
  int sy = y1 >= y0 ? 1 : -1;
  
  if (dy <= dx)
  {
    int d = (dy << 1) - dx;
    int d1 = dy << 1;
    int d2 = (dy - dx) << 1;
    putpixel(x0, y0, color);
    for(int x = x0 + sx, y = y0, i = 1; i <= dx; i++, x += sx)
    {
      if ( d >0)
      {
        d += d2;
        y += sy;
      }
      else
        d += d1;
      putpixel(x, y, color);
    }
  }
  else
  {
    int d = (dx << 1) - dy;
    int d1 = dx << 1;
    int d2 = (dx - dy) << 1;
    putpixel(x0, y0, color);
    for(int y = y0 + sy, x = x0, i = 1; i <= dy; i++, y += sy)
    {
      if ( d >0)
      {
        d += d2;
        x += sx;
      }
      else
        d += d1;
      putpixel(x, y, color);
    }
  }
}

Посилання

• "Алгоритм малювання ліній Брезенхейма" [Архівовано 25 лютого 2021 у Wayback Machine.], Колін Фленегана (англ.)

Див. також

• Алгоритми побудови відрізка
• Алгоритм Ву
• Алгоритм DDA-лінії