Поясните, в чём идея растровой развёртки полигонов? Как можно эффективно закрасить область внутри треугольника?
Многие замкнутые контуры являются простыми многоугольниками. Ели контур состоит из кривых линий, то его можно аппроксимировать подходящим многоугольником или многоугольниками. Простейший метод заполнения многоугольника состоит в проверке на принадлежность внутренности многоугольника каждого пиксела в растре. Этот метод слишком расточителен. Затраты можно уменьшить путем вычисления для многоугольника прямоугольной оболочки - наименьшего многоугольника, содержащего внутри себя многоугольник.
В случае, когда многоугольник, ограничивающий область, задан списком вершин и ребер (ребро определяется как пара вершин), можно предложить еще более экономный метод. Для каждой сканирующей строки определяются точки пересечения с ребрами многогранника, которые затем упорядочиваются по координате 
. Закрашиваются все пикселы между парами точек.
Одним из важнейших алгоритмов растеризации является алгоритм растеризации треугольника (заполнения треугольника), т.к. в большинстве моделей построения трехмерных объектов последние состоят именно из треугольников.
Схематично алгоритм можно описать следующим образом:
1. Треугольник разбивается на две части вертикальной линией, проходящей через среднюю точку:
2. Каждый из двух полученных треугольников растеризуется по отдельности.
3. В процессе растеризации обе стороны растеризуются параллельно, таким образом, чтобы координаты по оси y текущих точек на обоих отрезках совпадали. При этом связность растеризуемых линий (сторон треугольника) не обеспечивается:
|
|
|
4. При получении координат текущих точек горизонтальный отрезок между ними заполняется.
Поясните, какова идея заполнения с затравкой? Как можно эффективно залить сплошную область, используя стек?
Помещаем затравочный пиксель в стек. Далее, пока стек не пуст, будем извлекать из него очередной пиксель и, закрасив его, будем изучать соседние с ним пиксели. Если среди них будут пиксели, не принадлежащие границе и не окрашенные нужным цветом, то поместим их в стек, после этого вернемся к операции извлечения пикселя из стека. По окончанию алгоритма все пиксели будут закрашены.
Более эффективный алгоритм:
1. Затравочный пиксел на интервале извлекается из стека, содержащего затравочные пикселы.
2. Интервал с затравочным пикселом заполняется влево и вправо от затравки вдоль сканирующей строки до тех пор, пока не будет найдена граница.
3. В переменных Хлев и Хправ запоминаются крайний левый и крайний правый пикселы интервала.
4. В диапазоне Хлев <= x <= Xправ проверяются строки, расположенные непосредственно над и под текущей строкой. Определяется, есть ли на них еще не заполненные пикселы. Если такие пикселы есть (т. е. не все пикселы граничные, или уже заполненные), то в указанном диапазоне крайний правый пиксел в каждом интервале отмечается как затравочный и помещается в стек.
|
|
|
5. При инициализации алгоритма в стек помещается единственный затравочный пиксел, работа завершается при опустошении стека.
Поясните, для чего необходима процедура отсечения изображения границами окна? Какие идеи реализуются в алгоритме отсечения Сазерленда-Коэна?
Если изображение выходит за пределы экрана, то на части дисплеев увеличивается время построения за счет того, что изображение строится в "уме". В некоторых дисплеях выход за пределы экрана приводит к искажению картины, так как координаты просто ограничиваются при достижении ими граничных значений, а не выполняется точный расчет координат пересечения (эффект "стягивания" изображения). Некоторые, в основном, простые дисплеи просто не допускают выхода за пределы экрана. Все это, особенно в связи с широким использованием технологии просмотра окнами, требует выполнения отсечения сцены по границам окна видимости.
Отсекаемые отрезки могут быть трех классов - целиком видимые, целиком невидимые и пересекающие окно. Очевидно, что целесообразно возможно более рано, без выполнения большого объема вычислений принять решение об видимости целиком или отбрасывании. По способу выбора простого решения об отбрасывании невидимого отрезка целиком или принятия его существует два основных типа алгоритмов отсечения - алгоритмы, использующие кодирование концов отрезка или всего отрезка и алгоритмы, использующие параметрическое представление отсекаемых отрезков и окна отсечения. Представители первого типа алгоритмов - алгоритм Коэна-Сазерленда(Cohen-Sutherland,CS-алгоритм)иFC-алгоритм(Fast Clipping - алгоритм). Представители алгоритмов второго типа - алгоритмКируса-Бека(Curus-Beck,CB - алгоритм) и более поздний алгоритмЛианга-Барски(Liang-Barsky,LB-алгоритм).
|
|
|
Алгоритмы с кодированием применимы для прямоугольного окна, стороны которого параллельны осям координат, в то время как алгоритмы с параметрическим представлением применимы для произвольного окна.
Алгоритм Коэна-Сазерленда.
Этот алгоритм позволяет быстро выявить отрезки, которые могут быть или приняты или отброшены целиком. Вычисление пересечений требуется когда отрезок не попадает ни в один из этих классов.
|
|
|
Этот алгоритм особенно эффективен в двух крайних случаях:
•большинство примитивов содержится целиком в большом окне,
•большинство примитивов лежит целиком вне относительно маленького окна.
Идея алгоритма состоит в следующем:
Окно отсечения и прилегающие к нему части плоскости вместе образуют 9 областей (рис. 32). Каждой из областей присвоен4-хразрядный код. Две конечные точки отрезка получают4-хразрядные коды, соответствующие областям, в которые они попали. Смысл разрядов кода:
•1 рр = 1 - точка над верхним краем окна;
•2 рр = 2 - точка под нижним краем окна;
•3 рр = 4 - точка справа от правого края окна;
•4 рр = 8 - точка слева от левого края окна.
Определение того лежит ли отрезок целиком внутри окна или целиком вне окна выполняется следующим образом:
•если коды обоих концов отрезка равны 0 то отрезок целиком внутри окна, отсечение не нужно, отрезок принимается как тривиально видимый;
•если логическое & кодов обоих концов отрезка не равно нулю, то отрезок целиком вне окна, отсечение не нужно, отрезок отбрасывается как тривиально невидимый;
•если логическое & кодов обоих концов отрезка равно нулю, то отрезок подозрительный, он может быть частично видимым или целиком невидимым; для него нужно определить координаты пересечений со сторонами окна и для каждой полученной части определить тривиальную видимость или невидимость.
Дата добавления: 2018-04-04; просмотров: 616; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!