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

Простой рекурсивный алгоритм заполнения с затравкой

Основу алгоритма составляет рекурсивно вызываемая функция вида описанного ниже.

1. Текущая точка A = C

2. Если цвет точки А равен цвету границы или равен цвету заполнения, то выходим из процедуры

3. Если нет то задаем цвет для точки А равным цвету заполнения

4. вызываем эту же функцию для всех соседних точек с учетом связности

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

Построчный алгоритм заполнения с затравкой

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

В основе этого алгоритма лежит рекурсивный вызов процедуры для строки области. Для строки выполняются следующие вычисления:

1. Ищется х координата левой граница области в строке

2. Ищется х координата правая граница области в строке

3. Строиться горизонтальный отрезок

4. от x координаты левой границы до х координаты правой границы перебираются точки в строке расположенной выше данной

5. Если точка не принадлежит границе или уже залитой части то вызываем рекурсивно данную процедуру с обнаруженной точкой затравки

6. от x координаты левой границы до х координаты правой границы перебираются точки в строке расположенной ниже данной

7. Если точка не принадлежит границе или уже залитой части то вызываем рекурсивно данную процедуру с обнаруженной точкой затравки

Методы построчного сканирования для криволинейных поверхностей

алгоритмы сводят трехмерную задачу удаления невидимых линий и поверхностей к двумерной. Сканирующая плоскость определяется точкой наблюдения, расположенной в бесконечности на положительной полуоси z, и сканирующей строкой. Пересечение сканирующей плоскости и трехмерной сцены определяет окно размером в одну сканирующую строку. Задача удаления невидимых поверхностей решается в пределах этого окна, образованного сканирующей плоскостью. Она сводится к задаче о том, какой отрезок видим для каждой точки сканирующей строки.

Одним из простейших алгоритмов построчного сканирования, который решает задачу удаления невидимых поверхностей, является специальный случай алгоритма z-буфера - алгоритм построчного сканирования с z-буфером. Используемое в этом алгоритме окно визуализации имеет высоту в одну сканирующую строку и ширину во весь экран. Как для буфера кадра, так и для z-буфера требуется память высотой в 1 бит, шириной в горизонтальное разрешение экрана и глубиной в зависимости от требуемой точности. Концептуально этот алгоритм достаточно прост. Для каждой сканирующей строки буфер кадра инициализируется с фоновым значением интенсивности, а z-буфер - с минимальным значением z. Затем определяется пересечение сканирующей строки с двумерной проекцией каждого многоугольника сцены, если они существуют. Эти пересечения образуют пары. При рассмотрении каждого пиксела на сканирующей строке в интервале между концами пар его глубина сравнивается с глубиной, содержащейся в соответствующем элементе z-буфера. Если глубина этого пиксела больше глубины из z-буфера, то рассматриваемый отрезок будет текущим видимым отрезком.