Быстрое сглаживание линий

11

Алгоритм линий Брезенхема - это способ рисовать прямые линии, используя только быстрые целочисленные операции (сложение, вычитание и умножение на 2). Тем не менее, он генерирует псевдонимы. Есть ли такой же быстрый способ рисовать сглаженные линии?

antialiasing pixel-graphics line-drawing отметка
источник
1
Пара вопросов ... Вы делаете логику рисования на процессоре или графическом процессоре? Кроме того, вы ищете целочисленные алгоритмы или с плавающей запятой?
Алан Вулф,
5
@AlanWolfe, целочисленные алгоритмы на процессоре - та же среда, для которой был разработан алгоритм Брезенхэма.
Марк
3
en.wikipedia.org/wiki/Xiaolin_Wu%27s_line_algorithm является классическим алгоритмом, хотя страница википедии довольно недоработана, и у меня нет доступа к статье. Это похоже на ленивый вопрос, так как это довольно легко найти, выполнив некоторые основные поиски в Google.
Юрикс
2
Просто подумав вслух, я полагаю, что Брезенхэму должно быть легко адаптировать рисование линий толщиной в несколько пикселей. Затем вы можете выполнить сглаживание, рассчитав расстояние каждого центра пикселя от математической идеальной линии и применив некоторую функцию спада.
Натан Рид,
2
Я не могу пометить комментарий как правильный, хотя.
Марк

Ответы:

9

Есть ли такой же быстрый способ рисовать сглаженные линии?

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

В программном растеризаторе повсеместным способом рисования сглаженных линий является алгоритм линий Xiaolin Wu . Это не сложно реализовать, и в любом случае по этой ссылке присутствует необычно высококачественный псевдокод.

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

В raytracer есть множество вариантов. Стоит подумать о том, как на самом деле вы хотите нарисовать одномерный объект. Может быть, как цилиндр (Ву тени!). Обратите внимание, что это приводит к проблемам перспективы / ракурса, которые могут (или не могут) быть тем, что вы хотите. Нет четкого обобщения. Тогда, очевидно, что бы вы ни делали, вы просто пробуете это.

imallett
источник
«и в любом случае по этой ссылке присутствует необычно высококачественный псевдокод», я не согласен. Этот псевдокод, вероятно, не является надлежащей реализацией алгоритма Ву, хотя, похоже, он использовался в бесчисленных местах в Интернете. Первоначальный алгоритм Ву тянулся с обоих концов внутрь к центру и был на самом деле быстрее, чем алгоритм Брезенхэма, потому что он выполняет примерно вдвое меньше операций, даже если записывает больше пикселей. Я говорю о фактическом алгоритме Ву, а не о том, который опубликован в связанной статье в Википедии.
Осьминог
@Octopus [Выражает смутный скептицизм, особенно в отношении более быстрого бита, но не хватает контекста для опровержения или подтверждения - если это так, источники, исправления и изменения, конечно, приветствуются.]
imallett
Зависит от того, на что вы рассчитываете. Если вы рисуете с обоих концов внутрь, то алгоритм У выполняет половину вычислений, но вдвое больше пикселей. Смотрите Таблицу 1 в статье Ву, на которой есть ссылка на Википедию. Таким образом, если запись пикселей стоит дорого, как в случае записи в TFT по последовательному соединению, то алгоритм Ву стоит дороже, чем алгоритм Брезенхэма. (Должен признать, я не понимаю, почему алгоритм Брезенхэма также не может использовать симметрию.)
Ян-Аке Ларссон
1
Но я согласен с @Octopus, даже принимая «рисование от одного конца до другого», псевдокод является алгоритмом Ву, только если повсюду используется целочисленная арифметика. Код, который я вижу в Интернете, использует арифметику с плавающей точкой, что является существенным изменением. В статье Ву алгоритм использует только целочисленную арифметику (или фактически арифметику с фиксированной точкой).
Ян-Оке Ларссон