Введение
Алгоритм в компьютерной графике для добавления цвета или текстуры.
Заливка, также известная как заливка из начальной точки, — это алгоритм, который определяет и изменяет область, соединенную с заданным узлом в многомерном массиве, имеющую определенный атрибут. Он используется в инструменте "заливка ведром" графических редакторов для заполнения смежных областей, имеющих схожий цвет, другим цветом, а также в играх, таких как Го и Сапер, для определения, какие элементы очищаются. Вариант, называемый граничной заливкой, использует те же алгоритмы, но определяет область как соединенную с заданным узлом, не имеющую определенного атрибута. Следует отметить, что заливка не подходит для рисования заполненных многоугольников, поскольку может пропускать некоторые пиксели в острых углах. Вместо этого обратитесь к правилу четности и правилу ненулевого числа пересечений.
Параметры алгоритма
Традиционный алгоритм заливки принимает три параметра: начальную точку, целевой цвет и цвет замены. Алгоритм ищет все точки в массиве, соединенные с начальной точкой путем целевого цвета, и изменяет их на цвет замены. Для заливки границы вместо целевого цвета указывается цвет границы. Чтобы обобщить алгоритм наиболее распространенным способом, в дальнейшем описаниях вместо этого будут доступны две функции. Одна называется Inside (Внутри), которая возвращает true для незаполненных точек, которые по своему цвету должны находиться внутри заливаемой области, и другая называется Set (Установить), которая заполняет пиксель/точку. Любая точка, для которой была вызвана функция Set, больше не должна возвращать true при вызове функции Inside. В зависимости от того, считаем ли мы точки, соединенные по углам, связанными или нет, существуют два варианта: восьмисвязный и четырехсвязный соответственно.
Дальнейшие возможные оптимизации
Проверьте и установите цвет пикселя каждого узла перед добавлением его в стек/очередь, что позволит уменьшить размер стека/очереди. Используйте цикл для направлений восток/запад, добавляя в очередь пиксели выше и ниже по ходу (что делает алгоритм похожим на алгоритмы заполнения областей). Для обеспечения параллельной обработки на процессорах, работающих не последовательно, используйте несколько копий кода с дополнительными стеками/очередями. Примените многопоточность (в идеале, с немного отличающимися порядками обхода, чтобы потоки не задерживались в одной и той же области).
Преимущества
Очень простой алгоритм, который легко сделать безошибочным.
Недостатки
Использует много памяти, особенно при работе со стеком. Проверяет большинство заполненных пикселей в общей сложности четыре раза. Не подходит для заполнения узорами, поскольку требует изменения результатов проверки пикселей. Для варианта с очередью схема доступа к памяти неэффективна для кэша. Сложно оптимизировать для работы с многопиксельными словами или битовыми плоскостями.
Преимущества
В 2–8 раз быстрее, чем рекурсивный алгоритм обработки пикселей. Паттерн доступа оптимизирован для кэша и битовых плоскостей. Может рисовать горизонтальную линию вместо установки отдельных пикселей.
Недостатки
Все еще посещает пиксели, которые уже были заполнены. (Для распространенного алгоритма требуется 3 сканирования большинства пикселей. Для финального сканирования выполняются дополнительные сканирования только тех пикселей, где в заполненной области есть пробелы.) Не подходит для заполнения узорами, поскольку требует изменения результатов проверки пикселей.
Добавление поддержки заполнения шаблона
Два распространенных способа заставить алгоритмы, основанные на интервалах и пикселях, поддерживать заполнение узорами — это либо использовать уникальный цвет для простого заливки, а затем заменить его узором, либо отслеживать (в двумерном булевом массиве или в виде областей), какие пиксели уже были посещены, используя эту информацию для обозначения того, что пиксели больше не подлежат заполнению. Функция заполнения должна возвращать false для таких посещенных пикселей.
Графо-теоретическое заполнение
Некоторые теоретики применили теорию графов к этой проблеме, рассматривая области пикселей или их объединения как узлы и изучая их связность. Первый опубликованный алгоритм, основанный на теории графов, работал схожим образом с заполнением областей, описанным выше, но имел механизм для обнаружения дублирования заполнения областей. К сожалению, в нем были ошибки, из-за которых некоторые области заполнялись не полностью. Позже был опубликован исправленный алгоритм, также основанный на теории графов; однако он изменяет изображение в процессе работы, временно блокируя потенциальные циклы, что усложняет программный интерфейс. Другой опубликованный алгоритм требовал четкого выделения границы изображения, что ограничивает его применение в большинстве случаев; кроме того, он требует дополнительного бита на пиксель для служебной информации.
Преимущества
Подходит для заливки узорами, поскольку никогда не проверяет повторно уже залитые пиксели. Обеспечивает вдвое большую скорость по сравнению с исходным алгоритмом для простых заливок. Способ доступа к узору оптимизирован для кэша и битовой плоскости.
Недостатки
Регулярно необходимо сравнивать пролет с каждым другим элементом в очереди, что значительно замедляет выполнение сложных ордеров. Переключение между графо-теоретическим и пиксельным представлениями затрудняет понимание. Код достаточно сложен, что повышает вероятность ошибок.
Наполнение на ходу (метод с фиксированной памятью)
Существует метод, который практически не использует память для четырех связанных областей, представляя себя художником, пытающимся закрасить область, не загнав себя в угол. Это также метод решения лабиринтов. Исследуются четыре пикселя, формирующие первичную границу, чтобы определить, какое действие следует предпринять. Художник может оказаться в одном из следующих состояний:
Все четыре граничных пикселя заполнены. Три граничных пикселя заполнены. Два граничных пикселя заполнены. Один граничный пиксель заполнен. Ни один граничный пиксель не заполнен. Если необходимо следовать по пути или границе, используется правило правой руки. Художник следует за областью, прикладывая правую руку к стене (границе области) и продвигаясь по краю области, не отрывая руку. В случае №1 художник закрашивает (заполняет) пиксель, на котором он стоит, и останавливает алгоритм. В случае №2 существует путь, ведущий из области. Закрасьте пиксель, на котором стоит художник, и двигайтесь в направлении открытого пути. В случае №3 два граничных пикселя определяют путь, который, если мы закрасим текущий пиксель, может заблокировать нам возвращение на другую сторону пути. Нам нужна "метка", чтобы определить наше местоположение и направление движения, чтобы узнать, вернемся ли мы когда-нибудь к тому же пикселю. Если мы уже создали такую "метку", то сохраняем предыдущую метку и переходим к следующему пикселю, следуя правилу правой руки. Первая встреченная граница из двух пикселей используется для метки, чтобы запомнить, где начался проход и в каком направлении двигался художник. Если метка встречается снова, и художник движется в том же направлении, то художник знает, что безопасно закрасить пиксель с меткой и продолжить движение в том же направлении. Это связано с тем, что (через какой-то неизвестный путь) пиксели на другой стороне метки могут быть достигнуты и закрашены в будущем. Метка удаляется для дальнейшего использования. Если художник встречает метку, но движется в другом направлении, то произошла петля, которая вернула художника к метке. Эту петлю необходимо устранить. Метка поднимается, и художник затем продолжает движение в направлении, ранее указанном меткой, используя правило левой руки для границы (аналогично правилу правой руки, но с использованием левой руки художника). Это продолжается до тех пор, пока не будет найдено пересечение (с тремя или более открытыми граничными пикселями). Продолжая использовать правило левой руки, художник теперь ищет простой проход (образованный двумя граничными пикселями). Как только этот двухпиксельный граничный путь найден, этот пиксель закрашивается. Это разрывает петлю и позволяет алгоритму продолжить работу. В случае №4 необходимо проверить восемь противоположных соседних углов, чтобы узнать, заполнены они или нет. Если один или оба заполнены, это создает множество пересекающихся путей, и их нельзя закрасить. Если оба пусты, то текущий пиксель можно закрасить, и художник может двигаться по правилу правой руки. Алгоритм обменивает время на память. Для простых форм он очень эффективен. Однако, если форма сложная и имеет много деталей, алгоритм тратит много времени на отслеживание краев области, пытаясь убедиться, что все можно закрасить. Этот алгоритм впервые стал коммерчески доступен в 1981 году на системе обработки изображений Vicom, производимой компанией Vicom Systems, Inc. Алгоритм обхода был опубликован в 1994 году. Классический рекурсивный алгоритм заливки также был доступен на системе Vicom.
Преимущества
Постоянное использование памяти.
Недостатки
Образец доступа неэффективен для кэша или битовых плоскостей. Может потребоваться значительное время для последовательного перебора циклов перед их завершением.
Векторные реализации
Версия 0.46 Inkscape включает инструмент заливки, выдающий результат, аналогичный обычным растровым операциям и фактически использующий одну из них: холст рендерится, выполняется заливка выбранной области, а затем результат преобразуется обратно в векторный путь. В работе используется понятие граничных условий.