Войти
ПрограммированиеФорумГрафика

Консервативная растеризация отрезков

Advanced: Тема повышенной сложности или важная.

#0
8:25, 31 дек. 2016

Нужен алгоритм, закрашивающий все клетки квадратного растра, которые затрагивает отрезок.
Знает кто такой?

Я тут свой навелосипедил, но не уверен в его правильности, скорости и краткости кода.
Хочется всё же не быть велосипедостроителем, а пользоваться проверенным решением.

#1
8:58, 31 дек. 2016

Брезенхем. Только за пиксели прими свои квадраты.

#2
10:37, 31 дек. 2016

k119_55524
> Брезенхем. Только за пиксели прими свои квадраты.
Мимо.
Этот алгоритм заполняет не все нужные пиксели.
Нагуглил модификацию этого алгоритма для моих нужд, но ам проблемы - там в цикле происходит x+= dx, y+= dy. Но это не хорошо, т. к. происходит накопление ошибки.

#3
10:52, 31 дек. 2016

Я бы посоветовал такой метод. Рисуешь один большой квад (каков размер линии, таков квад). И в фрагментом шейдере определяешь - близко к линии или нет. Вернее - пересекает ли пиксель линию или нет. Разумеется в 2D делаешь тесты. Вот и вся консервативная.

#4
10:59, 31 дек. 2016

Возьми за основу трассировку луча как в Wolfenstein 3D.
Изображение

dx, dy наверняка получаются делением чего-то на чего-то? Чтоб уменьшить ошибку можешь вместо предвычесленного dx сначала домножать шаг на делимое и потом уже делить. Медленнее но вроде как точнее должно быть. Хотя смотря про какую ты ошибку. У тебя floating point или fixed point?

#5
18:44, 31 дек. 2016

Panzerschrek[CN]
1) Брезенхем заполняет все пересекаемые линией квадраты
2) такой вариант:
  рассматриваешь движение точки из начала в конец отрезка со скоростью V
  находишь время tx до 1го пересечения с линией X сетки и время ty до 1го пересечения с линией Y сетки
  если tx<ty
    считаешь пересечение в tx
    tx+=dtx, где dtx=1./|vx| - время между пересечениями линий X сетки
  иначе
    считаешь пересечение в ty
    ty+=dty, где dty=1./|vy| - время между пересечениями линий Y сетки
  повторить

#6
7:44, 1 янв. 2017

Aslan
>   tx+=dtx
> ty+=dty
Не катит, ошибка накапливается.


Я реализовал два варианта для разных целей.
1) Модификация DDA. Для первичного заполнения растра подходит.

2) Для обхода растра по лучу реализовал следующий алгоритм:
Перебираем все точки вдоль луча с шагом 1 (или чуть меньше).
Для точки определяем в какую клетку она попала.
Если в ту же, что и предыдущая - ничего не делаем. Если в клетку, отличающуюся на 1 по x или по y, то обрабатываем только эту клетку. Если новая точка попала в клетку, отличающуюся от предыдущей по x и по y, то обрабатываем эту клетку, а так же  две соседние с предыдущей клетки.

Он, возможно, немного избыточен и перебирает лишние клетки, но зато удобен и относительно прост.

#7
12:07, 1 янв. 2017

Panzerschrek[CN]
Брезенхем получается из вполне конкретной формулы. Она есть ни вики: https://ru.m.wikipedia.org/wiki/Алгоритм_Брезенхэма
Вот она: Изображение
То есть чтобы получить то же, что выдает брезенхем просто подставляем в эту формулу X, получаем дробный Y, и округляем его.
Чтобы из этого брезензема получить консервативную растеризацию достаточно подставлять не только целый X, а еще и X+0.5, и так же округлять, и получать Y. Поскольку сам X+0.5 может быть округлен как вправо так и влево - нам нужно правило как это делать. Так вот, если Y(X)=Y(X+0.5), то округляем в X+1. В противном случае округляем в  X.

p.s. Не забудь, что формула для линий с угловым коэффициентом <= 1. Для коэффициентов > 1 X и Y в формуле меняются местами.

#8
13:31, 12 янв. 2017

Panzerschrek[CN]
> Не катит, ошибка накапливается
float 6 знаков точность, чтобы ошибится на 1 надо разрешение 1 млн

#9
16:18, 12 янв. 2017

Aslan
> float 6 знаков точность, чтобы ошибится на 1 надо разрешение 1 млн
Да не накапливается она там, всё компенсируется. Ссылку на доказательство формулы выше привели. Тем более, что брезенхейм могуч именно целочисленностью - там никаких флоатов ни на одном этапе.

ПрограммированиеФорумГрафика

Тема в архиве.