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

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

Извините за ASCII-арт, но это, пожалуй, лучший способ его продемонстрировать.

Обычная строка:

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

«Обведенная» строка:

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

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

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


c algorithm line bresenham
person Thomas O    schedule 11.10.2010    source источник
comment
Я не думаю, что как мне создать линия произвольной толщины с использованием Bresenham? является дубликатом как таковым, но, вероятно, имеет значение.   -  person dmckee --- ex-moderator kitten    schedule 11.10.2010
comment
+1 и спасибо за ссылку. Это включает в себя контурные линии, поэтому я ищу эффективный способ рисования линии с рамкой. Рисование толстой линии, а затем тонкой линии будет по существу идентично тому, что я дал как вариант.   -  person Thomas O    schedule 11.10.2010
comment
да. Линия похожа на обычную Bresenham и имеет ширину 1 пиксель. Я хочу нарисовать контур в 1 пиксель на этой линии, поэтому ширина линии будет всего 3 пикселя.   -  person Thomas O    schedule 12.10.2010
comment
Это очевидно, не запрашивается сторонний ресурс, и сторонний ресурс не был предоставлен. Дорогие близкие избиратели, пожалуйста, научитесь читать. С любовью,   -  person Shog9    schedule 05.02.2015

Ответы (2)


arrow_upward
1
arrow_downward

Я предлагаю это (смесь C/псевдокод):

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);
}
person Edgar Bonet    schedule 12.10.2010
comment
Вот, собственно, и все — в этом примере не используется быстрый алгоритм Брезенхэма, но эту идею можно адаптировать. Словами, а не псевдокодом: каждому пикселю «линии» нужен пиксель «контура» вверх, вниз, влево и вправо. Итак, для каждого горизонтального отрезка ставим пиксель контура слева, идем вдоль отрезка, рисуя линию и обводя сверху+снизу, затем ставим пиксель контура справа. Аналогично для следующего горизонтального сегмента. Но вы можете оптимизировать, так как верхняя граница для этого горизонтального сегмента перекрывает правую границу последнего, поэтому вам нужно сделать пиксели L/R только для первого/последнего сегментов. - person psmears; 13.10.2010
comment
@psmears: вы действительно хотите нарисовать границы L / R для всех сегментов, потому что у вас может быть сегмент слева направо, за которым следует сегмент справа налево, например, при рисовании чего-то вроде символа «›». - person Edgar Bonet; 13.10.2010
comment
Если процессор не может выполнять арифметику с плавающей запятой аппаратно, я бы вместо этого вычислил наклон, используя фиксированную точку. Затем, предполагая, что вы можете выделить 16 бит для дробной части, вычисление y будет выглядеть так: hi_res_y += slope; y = hi_res_y >> 16;. Это всего лишь одно добавление и один битовый сдвиг. Я бы инициализировал hi_res_y = (y << 16) + 0x8000, чтобы получить правильный рандинг. - person Edgar Bonet; 13.10.2010
comment
Спасибо. :) Я буду исследовать это дальше. - person Thomas O; 13.10.2010
comment
Кроме того, спасибо за функцию полилинии - это было бы очень полезно. Я думал, что мне придется исправить это вручную, расставив пиксели. - person Thomas O; 13.10.2010
comment
@Edgar: у процессора нет FPU, так что спасибо за ваше предложение. Если я смогу обойтись без использования программного FPU, это будет намного быстрее. - person Thomas O; 13.10.2010
comment
@ Эдгар Боне: вопрос задан о прямой линии. Да, если вы рисуете более одной прямой линии, вам нужно будет делать заглавные буквы в конце каждой прямой линии, но внутри каждой прямой вы можете опустить концы горизонтальных сегментов, составляющих эту линию (как, впрочем, и ваше решение уже делает :-) Кстати, я бы не стал использовать арифметику с фиксированной или плавающей запятой, которая является приблизительной и может иметь ошибки округления, когда алгоритм Брезенхема использует только целочисленную арифметику и является точным (в пределах разрешения дисплея) -- см. en.wikipedia.org/wiki/Bresenham%27s_line_algorithm - person psmears; 13.10.2010
comment
@psmears: Извините, я перепутал горизонтальные отрезки и прямые линии. Вопрос задавался о прямой линии, а также о плавном соединении двух таких линий. Я интерпретировал это последнее требование как полилинии. - person Edgar Bonet; 13.10.2010
comment
@psmears снова: ссылка на Википедию, которую вы даете для алгоритма Брезенхэма, не является целочисленной арифметикой: error и deltaerr определяются как real. Ошибки округления не должны быть проблемой с фиксированной точкой, если у вас достаточно битов для дробной части. Если у вас недостаточно битов для хранения как целой, так и дробной части y в одной переменной, вам придется разделить их на две переменные и вручную обработать переполнение дробной части в целую часть. Это в основном то, что делает алгоритм Брезенхэма. - person Edgar Bonet; 13.10.2010
comment
@Edgar Bonet: (1) Конечно, это очень сбивает с толку, когда мы начинаем делать линии из линий, добавлять полилинии и т. д. — нам нужно больше слов :) (2) В первых частях для ясности используется real, но если вы прочитаете всю статью ( см. раздел «Оптимизация») он показывает, как его можно преобразовать для использования целочисленной арифметики без округления. На самом деле это не то же самое, что фиксированная точка, потому что фиксированная точка подразумевает постоянный знаменатель; здесь переменная знаменателя и выбрана для точности вычислений - поэтому алгоритм такой умный :) - но в остальном да, очень похоже :) - person psmears; 14.10.2010
comment
Это даст результат низкого качества, потому что граничные пиксели всегда находятся на расстоянии y+-1 от центра независимо от угла линии. Таким образом, линия будет sqrt(2)~=1,4 раза уже под углом 45 градусов. Лучше будет выбрать образец кисти, представляющий собой короткий отрезок линии, перпендикулярный тому, который вы рисуете, с конечными двумя пикселями, имеющими цвет границы. Нарисуйте два круга брезенхэма с окантовкой для торцевых заглушек, затем покрасьте такой кистью за 1 проход. Должен дать хороший результат. Если вы хотите увидеть целочисленную математику для этого, опубликуйте еще один комментарий. - person Gene; 26.06.2015

arrow_upward
0
arrow_downward

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

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

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

person Franz D.    schedule 01.03.2015