1. Алгоритм заполнения с затравкой (=заливка)
Вход: граница фигуры, цвета заливки и границы, начальная точка.
Сначала закрашивается начальная точка, а также все те, которые могут быть с ней соединены непрерывным отрезком, не пересекая границу. Потом проверяются все соседние пиксели начальной точки: если их цвет отличается от цвета границы, то делаем рекурсивный вызов.
Недостатки:
● очень много рекурсивных вызовов ⇒ переполнение стека. Для защиты от переполнения можно использовать свой собственный стек, но тогда будет потрачено много памяти.
2. Построчный алгоритм заполнения с затравкой.
Входные параметры — те же самые.
От начальной точки движемся влево и вправо, пока не достигнем границы. Получаем точки, лежащие на границе, и рисуем отрезок. В цикле рассматриваются все точки над и под этим отрезком, и рекурсивно вызываем процедуру для всех найденных незакрашенных точек.
Оптимизация метода
При проверке строки над/под текущей все её пиксели проверяются на принадлежность границе:
● Если граничных точек нет, то в стек добавляется одна (произвольная) точка из проверяемой строки.
● Если граничные точки есть, то они разбивают строку на подстроки, от каждой из которых в стек добавляется по одной точке.
В обоих случаях добавляемые точки должны быть незакрашенными.
Цвет каждого пикселя определяется некоторой функцией f(x,y,с), где х,у — координаты, с — цвет.
● Если f ≡ const, то это монотонная закраска.
● Если c ≠ const, то это — корректировка заливки, а не заливка.
Например, эффект градиента состоит в закраске нескольких точек заданными цветами, а цвета остальных пикселей находятся аппроксимацией этих заданных цветов.
Если f задается явно, конкретными значениями, то мы получаем текстурирование. При закраске текстурой для каждой точки изображения (x,y) вычисляется соответствующая точка текстуры (i,j). Наложение текстуры тесно связано с задачей интерполяции, т.к. цвет одного пикселя может определяться исходя из нескольких соседних пикселей.
Если координаты (i,j) линейно зависят от (x,y), то задача вычисления текстурных координат может быть оптимизирована с помощью инкрементной реализации: если точке (x,y) соответствует точка (i,j), то
● точке будет соответствовать
● точке будет соответствовать
где
— частные производные от функций, связывающих (x,y) и (i,j).