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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

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

Алгоритм[ред.ред. код]

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

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

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

Посилання[ред.ред. код]

Див. також[ред.ред. код]