Как создать линию произвольной толщины с помощью Bresenham?

Ответ 1

Я думаю, что лучший способ - нарисовать прямоугольник, а не линию, поскольку линия с шириной - это двухмерный объект. Попытка нарисовать набор параллельных линий, чтобы избежать перерисовки (чтобы уменьшить пропускную способность записи) и перерисовки (отсутствующие пиксели), была бы довольно сложной. Это не слишком сложно вычислить угловые точки прямоугольника от начальной и конечной точки и ширины.

Итак, следуя комментарию ниже, процесс для этого будет:

1. Создайте прямоугольник той же длины, что и требуемая линия, и ширины, равной требуемой ширине, чтобы (от 0,0) до (ширина, длина)
2. Поверните и переведите координаты углов прямоугольников в нужное положение, используя 2D-преобразование
3. Растрируйте повернутый прямоугольник, используя аппаратное ускорение рендеринга (например, квадроцикл OpenGL *) или программный растеризатор. Он может быть визуализирован с использованием четырехугольного растеризатора или пары треугольников (например, вверху слева и внизу справа).

Примечание *: Если вы используете OpenGL, вы также можете выполнить Шаг 2 одновременно. Конечно, использование OpenGL означает понимание OpenGL (большого и сложного), и это приложение может сделать это сложной задачей для реализации на столь позднем этапе разработки.

Ответ 2

Возьмите другую петлю Bresenham и используйте ее, чтобы изменить начальное и конечное положение исходной строки в прямоугольном направлении. Проблема заключается в том, чтобы эффективно находить правильную отправную точку и не рисовать какой-либо пиксель дважды (или пропускать пиксель) при рисовании следующей строки.

Рабочий и протестированный C-код доступен из Github C-кода.

Здесь тестовая страница включает в себя несколько строк, созданных этим кодом. Черные пиксели являются отправными точками для алгоритма.

Ответ 3

Вот бумага и реализация Delphi модифицированной версии алгоритма Брешенема для рисования утолщенных линий.

Вы также можете взглянуть на Anti-Grain Geometry, библиотеку для высококачественного и высокопроизводительного программного обеспечения 2D графика. Взгляните на демонстрационную страницу чтобы получить представление о том, что она может сделать.

Ответ 4

Для лучшей точности, а также хорошей производительности для более толстых линий, вы можете нарисовать линию как многоугольник. Некоторые псевдо-коды:

draw_line(x1,y1,x2,y2,thickness)
  Point p[4];
  angle = atan2(y2-y1,x2-x1);
  p[0].x = x1 + thickness*cos(angle+PI/2);
  p[0].y = y1 + thickness*sin(angle+PI/2);
  p[1].x = x1 + thickness*cos(angle-PI/2);
  p[1].y = y1 + thickness*sin(angle-PI/2);
  p[2].x = x2 + thickness*cos(angle-PI/2);
  p[2].y = y2 + thickness*sin(angle-PI/2);
  p[3].x = x2 + thickness*cos(angle+PI/2);
  p[3].y = y2 + thickness*sin(angle+PI/2);
  draw_polygon(p,4)

И, возможно, круг может быть нарисован в каждой конечной точке.

Ответ 5

Некоторые простые способы использования:

• для любой ширины n, где n нечетно. для любой точки p, построенной на графике, также нарисуйте точки выше/ниже ее для n/2 (если линия > 45 градусов, нарисуйте сторону сбоку).
  • не действительно правильная линия правильной толщины, больше похожа на курсивом, но очень быстро.
• для начальной точки p (x, y) выбирают точки t0 и b такие, что они центрируются на p, но n пикселей друг от друга. для конечной точки делают то же самое, что и в t1 b1. Нарисуйте линии из t0 → t1, t1- > b1, b1 → t0, b0 → t1. Заполните полученный прямоугольник.
  • Трюк здесь - это выбор точек таким образом, чтобы они отображались ортогонально направлению пути.
• для каждой точки p на линии вместо того, чтобы нарисовать точку, нарисуйте круг.
  • Это имеет то преимущество, что конечные точки "чисты" независимо от ориентации.
  • не должно быть необходимости делать какие-либо круги сплошными, за исключением первого.
  • несколько медленный

Ответ 6

Я предполагаю, что вы будете рисовать горизонтальные промежутки от одной граничной линии к другой и вычислять x-значение каждой из строк методом Bresenham по ходу (в одном цикле).

Не пробовал.

Конечным точкам может потребоваться некоторое внимание, чтобы они не выглядели странно.

Ответ 7

Самый простой способ создать линию практически произвольной толщины - это сначала выполнить брезенхем, а затем применить столько итераций расширения, сколько пожелаете. Каждое расширение расширяет обе стороны вашей линии в равной степени, но используя различные маски, вы можете добиться как равномерной, так и неравномерной толщины.

РЕДАКТИРОВАТЬ: Стоит также отметить, что этот метод имеет приятную особенность: его легко обобщать в 3D, потому что и Брезенхем, и расширение можно легко обобщить в 3D.

Толщина 1:

Маска:

1 1 1
1 1 1
1 1 1

Результирующая толщина: 3

Маска:

0 1 0
1 1 1
0 1 0

Результирующая толщина: 2

Ответ 8

http://members.chello.at/~easyfilter/bresenham.html

Пример внизу этой ссылки - javascript, но должен быть достаточно легким для адаптации к C. Это довольно простой алгоритм сглаживания для рисования линий переменной толщины.

Ответ 9

Я делаю это довольно часто, чтобы генерировать изображения волокон и сфер для моделирования пористых сред. У меня хороший простой способ сделать это, используя очень стандартный метод анализа изображений, известный как "дистанционное преобразование". Для этого требуется доступ к некоторому пакету анализа изображений. Я использую Python со Scipy, поэтому это не проблема. Вот демоверсия для преобразования случайно распределенных точек в сферы:

import scipy as sp
import scipy.ndimage as spim

im1 = sp.rand(100, 100) < 0.995  # Create random points in space
dt = spim.distance_transform_edt(im1)
im2 = dt < 5  # To create sphere with a radius of 5

И это все! Преобразование расстояния может быть медленным для очень больших изображений, но есть эффективная версия. Например, ImageJ имеет параллельный. Очевидно, чтобы создать толстые волокна, вы просто создаете свой образ тонких, затем примените шаги 2 и 3. выше.

Ответ 10

Для моего встроенного термопринтера, использующего алгоритм Брешенема, линия была слишком тонкой. У меня нет GL или что-то необычное. Я закончил просто уменьшал значение Y и рисовал больше строк под первым. Каждое количество толщины добавляло другую линию. Очень быстро реализовать и сделать для желаемых результатов печать с монохромного растрового изображения на тепловую.

Ответ 11

Я столкнулся с той же проблемой некоторое время назад. Основываясь на этой статье, я создал справочную реализацию Matlab, которую хотел бы разделить на GitHub.

Ответ 12

Для тех, кто хочет версию Python, здесь приведен код (на основе ответа @Fabel):

def drawline(x1,y1,x2,y2,**kwargs):  
    if kwargs.get('thickness')==None:
        thickness=1
    else:
        thickness=kwargs['thickness']
    if kwargs.get('roundcap')==None:
        roundcap=False
    else:
        roundcap=True
    angle = np.arctan2(y2-y1,x2-x1)
    xx = np.zeros(4)
    yy = np.zeros(4)
    xx[0] = np.round(x1 + thickness*np.cos(angle+np.pi/2))
    yy[0] = np.round(y1 + thickness*np.sin(angle+np.pi/2))
    xx[1] = np.round(x1 + thickness*np.cos(angle-np.pi/2))
    yy[1] = np.round(y1 + thickness*np.sin(angle-np.pi/2))
    xx[2] = np.round(x2 + thickness*np.cos(angle-np.pi/2))
    yy[2] = np.round(y2 + thickness*np.sin(angle-np.pi/2))
    xx[3] = np.round(x2 + thickness*np.cos(angle+np.pi/2))
    yy[3] = np.round(y2 + thickness*np.sin(angle+np.pi/2))
    u,v=polygon(xx,yy)    
    if roundcap:
        temp1x, temp1y = circle(x1,y1,thickness)
        temp2x, temp2y = circle(x1,y1,thickness)
        u = np.append(u,temp1x,temp2x)
        v = np.append(v,temp1y,temp2y)
    return u,v

При вызове функции вы можете при желании указать толщину и круглую крышку. Например:

drawline(10,10,50,50,thickness=3,roundcap=False)