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

в 10:35, , рубрики: алгоритм Брезенхэма, Алгоритмы, встроенные системы, Программинг микроконтроллеров, метки: ,

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

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

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

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

image

Управляются такие сканатары обычно с помощью отдельного (микро)контроллера, на который с компьютера подаются «высокоуровневые команды». Основная команда — это «нарисовать линию от сих до сих с такой-то скоростью». Раз «нарисовать линию» и микроконтроллер, то вспоминаем классический алгоритма Брезенхэма. Алгоритм Брезенхэма хорош тем, что он не использует никаких «медленных» операций с плавающей точкой, хотя для современных 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

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js