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

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

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

Несмотря на то, что алгоритм Брезенхэма не поддерживает сглаживание (antialiasing), в отличии, от, например, алгоритма Ву, скорость и простота реализации алгоритма Брезенхэма делают его по-прежнему важным и актуальным алгоритмом компьютерной графики. Алгоритм используется в аппаратных реализациях в плоттерах и графических чипах современных видеокарт, а также в различных графичеких библиотеках. Существует целое семейство алгоритмов, которые модифицируют или расширяют оригинальный алгоритм Брезенхэма. В частности, существуют обобщения для построения окружностей и кривых 2-го порядка.

Реализация алгоритма Брезенхэма на C/C++

/* Bresenham algorithm implementation по книге Е.В. Шикин, А.В. Боресков, Компьютерная графика,*/
void Line(int x1, int y1, int x2, int y2, int color)
{  int x1,y1,dx,dy,sx,sy,d,d1,d2;
   int i, x,y;
 
   if( x2 >= x1)
   {  dx = x2 - x1;
      sx = 1;
   } else {
      dx = x1 - x2; 
      sx = -1;
   } 
   if( y2 >= y1)
   {  dy = y2 - y1;
      sy = 1;
   } else {
      dy = y1 - y2; 
      sy = -1;
   } 
 
   if(dy <= dx) 
   {  d = (dy << 1) - dx;
      d1 = dy << 1;
      d2 = (dy - dx) << 1;
 
      for(x=x1+sx,y=y1,i=1; i <= dx ; i++,x+=sx)
      {  if(d > 0)
         {  d += d2;
            y += sy;
         } else {
            d += d1;
         }   
         putpixel(x,y, color);
      } 
 
   } else {
      d  = (dx << 1) - dy;
      d1 = dx << 1;
      d2 = (dx - dy) << 1;
 
      for(x=x1,y=y1+sy,i=1;i <= dy ; i++,y += sy)
      {  if(d > 0)
         {  d += d2;
            x += sx;
         } else {
            d += d1;
         }   
         putpixel(x,y, color);
      } 
 
   } /* endif(dy <=dx) */
}

Литература

• Jack E. Bresenham, «Algorithm for computer control of a digital plotter», IBM Systems Journal, Vol. 4, No.1, January 1965, pp. 25-30
• Е. В. Шикин, А. В. Боресков, Компьютерная графика, М., Диалог-МИФИ,1995, ISBN 5-86404-061-4 , стр 112—115.
• Роджерс Д. Алгоритмические основы машинной графики. — М.: Мир, 1989. — С. 512.

См. также

• Алгоритм Брезенхэма для задач реального времени

Ссылки

• Алгоритм Брезенхэма //Википедия