Алгоритм Брезенхэма в приложениях реального времени

Есть вот такие устройства — называются сканаторами или сканерами, обычно с прилагательным «лазерный»

используют их в различных технологиях лазерного сканирования ^[1].

С точки зрения программиста лазерный сканатор — это два поворотных зеркала, которые отклоняют лазерный луч в двух взаимно перпендикулярных плоскостях, углы задается с помощью пары ЦАПов (и стоящими после ЦАПов усилителями с обратной связью). Обычно ЦАПы могут быть 12-16 разрядными. Фактически задача рисования картинки или, говоря чуть более научным языком, вывода информации на таком устройстве ничуть не отличается от вывода информации на древних аналоговых графических дисплеях.

Управляются такие сканатары обычно с помощью отдельного (микро)контроллера, на который с компьютера подаются «высокоуровневые команды». Основная команда — это «нарисовать линию от сих до сих с такой-то скоростью». Раз «нарисовать линию» и микроконтроллер, то вспоминаем классический алгоритма Брезенхэма. Алгоритм Брезенхэма хорош тем, что он не использует никаких «медленных» операций с плавающей точкой, хотя для современных 32 разрядных микроконтроллеров это уже не так существенно, как для 8 или 16 разрядных.

/* 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) */
}

В нашем случае нет никакого цвета, поэтому color игнорируем. Зато у нас есть скорость.
Например, если у нас есть горизонтальный или вертикальный отрезок из n пикселей и заданная скорость — V (пикселей в секунду), то каждый пиксель должен выводится время tp = 1 / V

Если отрезок не горизонтальный, то его длина l = hypot(x0-x1, y0-y1), время вывода всего отрезка t0 = l/V, а вот для вычисления задержки на точку нужно будет t0 разделить на число вызовов функции putpixel, т.е.

tp = t0 / max(|x0-x1|, |y0-y1|)

Тогда в алгоритме color просто заменяется на «задержку на точку» wait (=tp)

void Line(int x1, int y1, int x2, int y2, int wait)

......
         putpixel(x,y, wait));

сама функция putpixel на первый взгляд должна выглядеть примерно так

void   putpixel(int x, int y, int wait))
{
      outPortX(x);  // установить на ЦАП X значение x
      outPortY(y);  // установить на ЦАП Y значение y 
      delay(wait); // задержка wait  единиц таймера
}  

Однако тут начинаются ньюансы, связанные с реализацией работы ЦАПов.

ЦАПы могут работать как последовательно, так и параллельно. Последовательно — это когда нужно выбрать номер ЦАПА, установить нужное значение и дождаться готовности, конца преобразования или просто подождать некоторое время. Если ЦАПы работают параллельно, то можно записывать значения x и y в соответствующие регистры микроконтроллера, а потом одновременно ждать готовности или конца преобразования.

В первом случае, время, затрачиваемое на вывод только X или только Y примерно в два раза меньше последовательного вывода X и Y. Соответственно исходник выглядит уже вот так

void Line(int x1, int y1, int x2, int y2, int wait,  int waitXY)
{  int 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;
           putXY(x,y,waitXY);
         } else {
            d += d1;
            putX(x, wait);
         }   
      } 

   } 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;
            putXY(x,y,waitXY);
         } else {
            d += d1;
            putY(y, wait);
         }   
      } 

   } /* endif(dy <=dx) */
}

void   putXY(int x, int y, int wait))
{     outPortXY(x,y);  // установить на ЦАПах X и Y значения x и y 
                                  // в простейшем случае   #define outPortXY(x,y)   outPortX(x); outPortY(y); 
      delay(wait); // задержка wait  единиц таймера
}  

void   putX(int x,  int wait))
{     outPortX(x);  // установить на ЦАП X значение x
      delay(wait); // задержка wait  единиц таймера
}  

void   putY(int y,  int wait))
{     outPortY(y);  // установить на ЦАП Y значение y
      delay(wait); // задержка wait  единиц таймера
}  

Значения wait и waitXY при вызове Line можно рассчитать исходя из того, что:

l = hypot(x0-x1, y0-y1), время вывода всего отрезка t0 = l/V, число вызовов putXY n1 = min(|x0-x1|, |y0-y1|), число вызовов putX или и putY n0 = max(|x0-x1|, |y0-y1|) — min(|x0-x1|, |y0-y1|).

Кроме того, можно ввести поправку на время выполнения функций outPortX, outPortY и outPortXY. Время выполнения этих функций можно заранее определить в процессе калибровки.

Напомню, что все расчеты задержек мы делаем в управляющем компьютере, а не в микропроцессоре, а сами времена и задержки, о которых идет речь — микросекунды и их доли…

Ну вот, собственно пока всё.

Собираем установку, пишем программы для управляющего компьютера и микропроцессора, включаем и смотрим на получившуюся картинку.

Кто-нибудь догадается, что мы увидим? (продолжение следует)

Автор: buratino

Источник ^[2]