29. Алгоритмы заполнения произвольных областей
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).
30. Рисование стилизованных примитивов (толщина и начертание линий, текстуры)
Для рисования жирных линий (прямых, кривых Безье, и т.д.) надо вместо закраски пикселя закрашивать его окрестность некоторым пером, форма которого задаётся. Но чтобы одни и те же пиксели не перерисовывались несколько раз, нужно учитывать угол наклона линии и корректировать форму пера.
Для рисования пунктирных линий отводится массив битов, который задает маску для нужного типа линии (узор): 1 — пиксель надо рисовать, 0 — не надо. При рисовании линии маска последовательно накладывается, и определяется, рисовать пиксель или нет.
При рисовании жирной линии пунктиром за счет толщины пера могут закрашиваться пропуски в пунктире ⇒ необходимо подбирать форму пера исходя из наклона и типа линии.
|
