Ищем быстрый обрисованный алгоритм рендеринга линий - PullRequest
Новая
       32

Ищем быстрый обрисованный алгоритм рендеринга линий

2 голосов
/ 11 октября 2010

Я ищу быстрый алгоритм для рисования намеченной линии. Для этого приложения контур должен иметь ширину всего 1 пиксель. Должна быть возможность, по умолчанию или через опцию, соединить две линии без проблем, если они имеют общую точку.

Простите за искусство ASCII, но это, вероятно, лучший способ продемонстрировать это.

Нормальная строка: 

 ##
   ##
     ##
       ##
         ##
           ##

«Контурная» строка: 

 **
*##**
 **##**
   **##**
     **##**
       **##**
         **##*
           **

Я работаю над dsPIC33FJ128GP802. Это небольшой микроконтроллер / цифровой сигнальный процессор, способный обрабатывать 40 MIPS (миллион инструкций в секунду). Он способен только к целочисленной математике (сложение, вычитание и умножение: он может делить, но занимает ~ 19 циклов.) Он используется обрабатывать уровень OSD одновременно, и для вычислений доступно только 3-4 MIPS времени обработки, поэтому скорость имеет решающее значение. Пиксели занимают три состояния: черный, белый и прозрачный; и поле видео составляет 192x128 пикселей. Это для Super OSD, проект с открытым исходным кодом: http://code.google.com/p/super-osd/

Первое решение, о котором я подумал, - это нарисовать прямоугольники 3х3 с выделенными пикселями на первом проходе и обычными пикселями на втором проходе, но это может быть медленным, так как для каждого пикселя перезаписывается не менее 3 пикселей и время, затраченное на рисование их впустую. Поэтому я ищу более быстрый путь. Каждый пиксель стоит около 30 циклов. Цель - <50 000 циклов, чтобы нарисовать линию длиной 100 пикселей. </p>

Ответы [ 2 ]

1 голос
/ 13 октября 2010

Я предлагаю следующее (C / pseudocode mix): 

void draw_outline(int x1, int y1, int x2, int y2)
{
    int x, y;
    double slope;

    if (abs(x2-x1) >= abs(y2-y1)) {
        // line closer to horizontal than vertical
        if (x2 < x1) swap_points(1, 2);
        // now x1 <= x2
        slope = 1.0*(y2-y1)/(x2-x1);
        draw_pixel(x1-1, y1, '*');
        for (x = x1; x <= x2; x++) {
            y = y1 + round(slope*(x-x1));
            draw_pixel(x, y-1, '*');
            draw_pixel(x, y+1, '*');
            // here draw_line() does draw_pixel(x, y, '#');
        }
        draw_pixel(x2+1, y2, '*');
    }
    else {
        // same as above, but swap x and y
    }
}

Редактировать : Если вы хотите, чтобы последовательные линии соединялись без проблем, я думаю, вам действительно нужно нарисовать все контурыв первом проходе, а затем линии.Я отредактировал код выше, чтобы нарисовать только контуры.Функция draw_line() будет точно такой же, но с одним draw_pixel(x, y, '#'); вместо четырех draw_pixel(..., ..., '*');.И тогда вы просто: 

void draw_polyline(point p[], int n)
{
    int i;

    for (i = 0; i < n-1; i++)
        draw_outline(p[i].x, p[i].y, p[i+1].x, p[i+1].y);
    for (i = 0; i < n-1; i++)
        draw_line(p[i].x, p[i].y, p[i+1].x, p[i+1].y);
}
0 голосов
/ 01 марта 2015

Мой подход заключается в том, чтобы использовать Брезенхем для рисования нескольких линий. Взглянув на свое искусство ASCII, вы заметите, что контурные линии точно такие же, как линия Брезенхэма, просто смещены на 1 пиксель вверх и вниз - плюс один пиксель слева от первой точки и справа от последней .

Для универсальной версии вам необходимо определить, является ли ваша линия плоской или крутой, т. Е. abs(y1 - y0) <= abs(x1 - x0). Для крутых линий контуры сдвинуты на 1 пиксель влево и вправо, а закрывающие пиксели находятся выше начальной и ниже конечной точки.

Возможно, стоит оптимизировать это, рисуя линию и два контурных пикселя за один проход для каждого пикселя линии. Однако, если вам нужны плавные контуры, самое простое решение - сначала нарисовать все контуры, а затем сами линии - что не будет работать с оптимизацией «три пикселя-Брезенхэма».

...