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

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

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

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

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

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

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

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

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

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

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

Зауважимо, що ${\displaystyle c_{0}=0}$ через те, що точка ${\displaystyle (x_{0},y_{0})}$ належить прямій ${\displaystyle 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, тому введемо нову допоміжну величину ${\displaystyle d_{i}=2c_{i}-1}$, зауважимо, що ${\displaystyle d_{1}=2k-1}$ (тому що ${\displaystyle 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);
  }
}

Попри те, що вхідні дані цілочисельні і всі операції здійснюються на цілочисельній ґратці, алгоритм використовує операції з дійсними числами. Щоб позбутися необхідності їх використання, зауважимо, що всі дійсні числа присутні в алгоритмі є числами виду ${\displaystyle {\frac {p}{\Delta {x}}},p\in {Z}}$. Тому можливо домножити ${\displaystyle d_{i}}$ та ${\displaystyle k}$ на ${\displaystyle \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);
  }
}

Також наведемо узагальнений алгоритм, який враховує можливі напрямки відрізка, а також співвідношення ${\displaystyle \Delta {x}}$ до ${\displaystyle \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);
    }
  }
}

• "Алгоритм малювання ліній Брезенхейма", Колін Фленегана (англ.)

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