Немонотонная закраска

Алгоритмы заполнения произвольных областей

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).