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

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

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

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

Алгоритм

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

Будемо слідувати загальноприйнятій домовленості, що координати ростуть вниз і праворуч, а також, що ми використовуємо центри пікселів, що мають цілочисельні координати. Кінцевими точками відрізка є пікселі з координатами (x₀, y₀) та (x₁, y₁), де перша координата за горизонталлю, друга за вертикаллю.

Спочатку алгоритм буде розглянутий для октанта в якому відрізок спрямований праворуч і донизу (x₀≤x₁ and y₀≤y₁), і його горизонтальна проекція $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);
    }
  }
}

Див. також

• Алгоритм Ву