теория, алгоритмы, примеры на С++ и OpenGL  
    2D теория 3D теория OpenGL        Обратная связь / Авторам

Мы vkontakte.ru


Rambler's Top100 Rambler's Top100
Каталог@Mail.ru - каталог ресурсов интернет

Друзья

Словарь синонимов русского языка

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

Этот алгоритм, разработанный Джеком Е. Брезенхэмом (Jack E. Bresenham) в 1962 году в компании IBM, является одним из самых старых алгоритмов в компьютерной графике. Он позволяет получить приближение идеальной прямой точками растровой сетки.

Прим. В зависимости от перевода, иногда его называют алгоритм Брезенхема.

Рассмотрим произвольный отрезок p1(x1, y1) – p2(x2, y2):
 

 
Чтобы растеризовать его можно поступить следующим образом (небольшая модификация алгоритма DDA-линии):
 
  • посчитаем длины отрезка по осям координат lengthX = |x2 – x1| и lengthY = |y2 – y1|;
  • выберем большую из них length = max(lengthX, lengthY);
  • случай length == 0 особый: закрашиваем пиксел (x1, y1) = (x2, y2) и завершаем работу алгоритма;
  • допустим большая длина оказалась lengthX. Установим начальную точку x = x1, y = y1;
  • сделаем length + 1 итераций:
    1. закрашиваем пиксел с координатами (x, roundf(y));
    2. координата x увеличивается на единицу, координата y увеличивается на lengthY / lengthX.
Прим. roundf – округление до ближайшего целого.
 
Прим. Обратите внимание, что |x2 – x1| и |y2 – y1| это расстояния между центрами первого и последнего пикселей.
 
#define roundf(x) floor(x + 0.5f)
 
void line(HDC hdc, int x1, int y1, int x2, int y2)
{
      int lengthX = abs(x2 - x1);
      int lengthY = abs(y2 - y1);
 
      int length = max(lengthX, lengthY);
 
      if (length == 0)
      {
            SetPixel(hdc, x1, y1, 0);
      }
 
      if (lengthY <= lengthX)
      {
            // Начальные значения
            int x = x1;
            float y = y1;
 
            // Основной цикл
            length++;
            while(length--)
            {
                  SetPixel(hdc, x, roundf(y), 0);
                  x++;
                  y += float(lengthY) / lengthX;
            }
      }
      else
      {
            // Начальные значения
            float x = x1;
            int y = y1;
 
            // Основной цикл
            length++;
            while(length--)
            {
                  SetPixel(hdc, roundf(x), y, 0);
                  x += float(lengthX) / lengthY;
                  y++;
            }
      }
}
 
При таком подходе x является целочисленной переменной, в то время как y – вещественная. Также заметим, что координата x всегда увеличивается на единицу, хотя x2 может быть меньше x1. То же замечание относится к координате y.
 
Итак, приведенный выше алгоритм обладает двумя существенными недостатками:
 
  1. Он работает только в первой четверти.
  2. Используются вычисления с плавающей точкой.

Распространение алгоритма на всю плоскость

Для того, чтобы устранить первый недостаток, перед работой основного цикла алгоритма вычислим приращения по осям x и y:
 

 
int dx = (x2 - x1 >= 0 ? 1 : -1);
int dy = (y2 - y1 >= 0 ? 1 : -1);
 
Теперь в основном цикле x и y меняются на dx и (dy * lengthY / lengthX), соответственно. Если координата y растет быстрее x, переменные x и y меняются ролями. Тогда y увеличивается на dy каждый шаг, а x увеличивается на lengthY / lengthX.
 
void line(HDC hdc, int x1, int y1, int x2, int y2)
{
      int dx = (x2 - x1 >= 0 ? 1 : -1);
      int dy = (y2 - y1 >= 0 ? 1 : -1);
 
      int lengthX = abs(x2 - x1);
      int lengthY = abs(y2 - y1);
 
      int length = max(lengthX, lengthY);
 
      if (length == 0)
      {
            SetPixel(hdc, x1, y1, 0);
      }
 
      if (lengthY <= lengthX)
      {
            // Начальные значения
            int x = x1;
            float y = y1;
 
            // Основной цикл
            length++;
            while(length--)
            {
                  SetPixel(hdc, x, roundf(y), 0);
                  x += dx;
                  y += dy * float(lengthY) / lengthX;
            }
      }
      else
      {
            // Начальные значения
            float x = x1;
            int y = y1;
 
            // Основной цикл
            length++;
            while(length--)
            {
                  SetPixel(hdc, roundf(x), y, 0);
                  x += dx * float(lengthX) / lengthY;
                  y += dy;
            }
      }
}
 
Прим. Сразу приходит мысль, почему не вычислить dy * float(lengthY) / lengthX заранее? Этот код не окончательный, поэтому “частичные” оптимизации опускаются.

Делений становится меньше

Теперь избавимся от вычислений с плавающей точкой. Можно поступить по аналогии с оптимизацией к алгоритму DDA, используя вычисления с фиксированной точкой. Но в данном случае можно даже не использовать операцию деления.

Рассмотрим основной цикл. Сначала оптимизируем цикл для случая lengthY <= lengthX, для другого случая все делается аналогично. Заметим, что изначально y является целой величиной. В цикле y изменяется на дробь со знаменателем lengthX. Т.о. х также является дробью со знаменателем lengthX. Избавимся от знаменателя, домножив на него:
 
            // Начальные значения
            int x = x1;
            int y = y1 * lengthX;
 
            // Основной цикл
            length++;
            while(length--)
            {
                  SetPixel(hdc, x, roundf(float(y) / lengthX), 0);
                  x += dx;
                  y += dy * lengthY;
            }
 
Увы, но при отрисовке пикселя мы снова должны прибегать к делению. Идея состоит в том, что величина y / lengthX за шаг меняется не более чем на единицу. Разобьем y на целую часть и приращение следующим образом:

y = z + c, где z это y, округленная до ближайшего целого, а с принадлежит отрезку [-0.5; 0.5].
 
То, что с принадлежит отрезку [-0.5; 0.5] гарантирует нам, что z - это действительно y, округленное до ближайшего целого. Нашей задачей будет поддержание величины c в этих границах.
 
Рассмотрим исходный вариант реализации основного цикла:

            // Начальные значения
            int x = x1;
            float y = y1;
 
            // Основной цикл
            length++;
            while(length--)
            {
                  SetPixel(hdc, x, roundf(y), 0);
                  x += dx;
                  y += dy * float(lengthY) / lengthX;
            }
 
Внесем необходимые изменения:
 
            // Начальные значения
            int x = x1;
            int y = y1;
            float c = 0;
 
            // Основной цикл
            length++;
            while(length--)
            {
                  SetPixel(hdc, x, y, 0);
                  x += dx;
                  c += dy * float(lengthY) / lengthX;
                  if (c > 0.5) {
                        c--;
                        y++;
                  }
                  if (c < -0.5) {
                        c++;
                        y--;
                  }
            }
 
Чтобы не делать несколько сравнений можно величину с всегда увеличивать в положительную сторону. Тем самым сравнивать придется только с 0.5, но при этом у будет менятся на dy:
 
            // Начальные значения
            int x = x1;
            int y = y1;
            float c = 0;
 
            // Основной цикл
            length++;
            while(length--)
            {
                  SetPixel(hdc, x, y, 0);
                  x += dx;
                  c += float(lengthY) / lengthX;
                  if (c > 0.5) {
                        c--;
                        y += dy;
                  }
            }
 
Начнем избавляться от дробей. Сперва заметим, что можно сделать замену d = 2 * c - 1, при этом d сравнивается с нулем:
 
            // Начальные значения
            int x = x1;
            int y = y1;
            float d = -1;
 
            // Основной цикл
            length++;
            while(length--)
            {
                  SetPixel(hdc, x, y, 0);
                  x += dx;
                  d += 2 * float(lengthY) / lengthX;
                  if (d > 0) {
                        d -= 2;
                        y += dy;
                  }
            }
 
Прим. При линейных заменах (u = a * v + b) правила следующие:

  1. Считаем, что замена имеет смысл, т.е. не рассматривются варианты a = 0. Тогда замена обратима:

v = (1 / a) – b / a

  1. Присвоение переменной преобразуется по линейному закону:

v = 2 > u = a * 2 + b

  1. При сравнении переменной, величина, с которой производится сравнение, преобразуется по линейному закону:

v > 0.5 > u > a * 0.5 + b

  1. Если v увеличивается на некоторую величину, то u увеличивается на ту же величину, помноженную на a:

v -= 4 > u -= 4 * a;

  1. В остальных ситуациях нужно внимательно следить, чтобы преобразования обоих величин сохраняли линейный закон их соответствия.
Вернемся к алгоритму. Последним штрихом будет применение оптимизации, рассмотренной в начале:
 
            // Начальные значения
            int x = x1;
            int y = y1;
            int d = -lengthX;
 
            // Основной цикл
            length++;
            while(length--)
            {
                  SetPixel(hdc, x, y, 0);
                  x += dx;
                  d += 2 * lengthY;
                  if (d > 0) {
                        d -= 2 * lengthX;
                        y += dy;
                  }
            }

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

Осталось распространить приведенные оптимизации на случай lengthY > lengthX. Получим алгоритм Брезенхэма:
 
#include <windows.h>
#include "math.h"
 
#define roundf(x) floor(x + 0.5f)
 
void line(HDC hdc, int x1, int y1, int x2, int y2)
{
      int dx = (x2 - x1 >= 0 ? 1 : -1);
      int dy = (y2 - y1 >= 0 ? 1 : -1);
 
      int lengthX = abs(x2 - x1);
      int lengthY = abs(y2 - y1);
 
      int length = max(lengthX, lengthY);
 
      if (length == 0)
      {
            SetPixel(hdc, x1, y1, 0);
      }
 
      if (lengthY <= lengthX)
      {
            // Начальные значения
            int x = x1;
            int y = y1;
            int d = -lengthX;
 
            // Основной цикл
            length++;
            while(length--)
            {
                  SetPixel(hdc, x, y, 0);
                  x += dx;
                  d += 2 * lengthY;
                  if (d > 0) {
                        d -= 2 * lengthX;
                        y += dy;
                  }
            }
      }
      else
      {
            // Начальные значения
            int x = x1;
            int y = y1;
            int d = - lengthY;
 
            // Основной цикл
            length++;
            while(length--)
            {
                  SetPixel(hdc, x, y, 0);
                  y += dy;
                  d += 2 * lengthX;
                  if (d > 0) {
                        d -= 2 * lengthY;
                        x += dx;
                  }
            }
      }
}

Скачать исходные тексты демонстрационных программ