Алгоритмы компьютерной графики Пешков Анатолий Тимофеевич, БГУИР. 1 отображение просранства пользователя и машинного носителя 4
 Скачать 1.86 Mb.
|
4.1 Заливка с сортировкойСмысл данного способа заключается в следующем. Заливка осуществляется за счет закраски отдельных участков всех растровых линий, параллельных одной из координатных осей (допустим X), расположенных в заданном габарите (например, в диапазоне от xmin- xmax). Закраске подлежат участки растровых линий, которые находятся внутри заливаемой области Для определения отдельных фрагментов текущей растровой линии, которые находятся в заливаемой области и которые должны быть закрашены, сначала находят точки пересечения этой растровой линии со всеми ребрами заданной области, затем выполняется сортировка найденных точек по значению их координат x. Ребра для определения точек пересечения могут браться в любой последовательности. Если пронумеровать точки в отсортированной последовательности, начиная с 0, то закраске подлежат участки рассматриваемой растровой линии, которые начинаются с точки, имеющей в отсортированной последовательности четный номер, и заканчивается в ближайшей нечетной точке отсортированной последовательности. На приведенном рисунке (Рис. Заливка с сортировкой-34) для горизонтальной растровой линии с координатой ys точками пересечения с ребрами многоугольника, представляющего заливаемую область, являются точки: aп, bп, dп, eп, fп, iп , kп, nп. В этом случае отсортированная по координате X последовательность этих точек будет иметь следующий вид: iп , dп, kп, bп, eп, nп, fп, aп. На основании полученной отсортированной последовательности точек пересечения, в качестве закрашиваемых заданным цветом берутся следующие отрезки растровой линии ys: iп dп, kп bп, eп nп, fп aп. Недостатком данного способа является использование по сравнению с другими способами более сложных действий над точками. При реализации данного способа при выборе очередного ребра для определения его пересечения с растровой линией целесообразно  Рис. Заливка с сортировкой‑34 использовать так называемый список активных ребер, что позволяет искать точки пересечения не для всех ребер заливаемой области, а только для тех, у которых действительно имеется точка пересечения с текущей растровой линией. 4.2 Заливка по ребрам. Смысл данного способа заключается в следующем. Для обрабатываемых точек габаритного пространства, в котором находится заливаемая область, вводится признак цветности, который может принимать одно из двух противоположных значений: цвет закраски точек области; цвет фона. В исходном состоянии признак цветности всех точек соответствует значению «фон». При каждом обращении к точке ее признак цветности меняется на противоположный. В процессе заливки поочередно для каждого ребра закрашиваемой области меняется значение признака цветности на противоположное для всех точек области, расположенной между этим ребром и осью Y. Ребра могут браться в любой последовательности. После обработки последнего ребра нужным цветом будет закрашена все точки заданной области. На Рис. Заливка по ребрам. -35 приведен пример закраски многоугольника рассматриваемым способом. Разновидностью данного способа является заливка с перегородкой. При реализации способа заливки с перегородкой внутри габаритного прямоугольника задается перегородка в виде вертикальной линии. Действия при этом способе аналогичны действиям при способе заливки по ребрам с той лишь разницей, что для каждого ребра изменяется значение признака цветности для точек области, расположенной между текущим ребром и перегородкой.  Рис. Заливка по ребрам. ‑35 Способ поясняется ниже приведенным рисунком (Рис. Заливка по ребрам. -36). Достоинством способов заливки по ребрам является простота выполняемых действий над точками. Однако данные способы требует обработку большого количества точек, а некоторые точки обрабатываются многократно. Заливка с перегородкой предполагает уменьшение количества обрабатываемых точек по сравнению с заливкой по ребрам.   Рис. Заливка по ребрам. ‑36 4.2.1 Cписок активных ребер.Рассмотрим понятия списка активных ребер на конкретном примере. На Рис. Заливка по ребрам. -37 приведен многоугольник в пространстве, которое включает десять растровых линий. В Табл. Заливка по ребрам. -1 приведен изменяющийся в соответствии с номером текущей растровой строки список активных ребер заданного многоугольника. В полном списке ребер заданного многоугольника ребра упорядочены по координате «Y» их верхнего конца. Если несколько ребер начинаются на одной и той же координате «Y», то они располагаются в соответствии c координаты «Y» их нижнего конца. Начало каждого списка для каждой растровой линии отмечается на общем множестве ребер буквой «н», а конец – буквой «к». Перечень активных ребер можно представить в виде односвязного списка с групповой сортировкой. В этом случае используется несколько групп по количеству растровых строк. В каждую группу включаются ребра, верхняя точка которых начинается в соответствующей растровой строке. В группе ребра сортируются по координате X. Каждому ребру в группе соответствует одна запись, которая может включать: y – высота ребра; xп - координата X пересечения ребра с соответствующей растровой линией; x – величина изменения X для данного ребра при переходе к очередной растровой линии; Aс – адрес следующей записи в группе линией.  Рис. Заливка по ребрам. ‑37 Список активных ребер для очередной растровой линии представляет собой остаток списка активных ребер, использовавшийся для предыдущей растровой линии, увеличенный на группу ребер, соответствующую очередной растровой линии. При переходе к очередной растровой линии в записях активных ребер изменяется y на «-1», а поле xп изменяется на значение, равное содержимому поля x. Кроме того, при переходе к очередной растровой линии из списка активных ребер удаляются ребра, Табл. Заливка по ребрам. ‑1
в записи которых поле «y» после очередной модификации обнулилось. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||