Если изображение выходит за пределы экрана, то на части дисплеев увеличивается время построения за счет того, что изображение строится в "уме". В некоторых дисплеях выход за пределы экрана приводит к искажению картины, так как координаты просто ограничиваются при достижении ими граничных значений, а не выполняется точный расчет координат пересечения (эффект "стягивания" изображения). Некоторые, в основном, простые дисплеи просто не допускают выхода за пределы экрана. Все это, особенно в связи с широким использованием технологии просмотра окнами, требует выполнения отсечения сцены по границам окна видимости.
В простых графических системах достаточно двумерного отсечения, в трехмерных пакетах используется трех и четырехмерное отсечение. Последнее выполняется в ранее рассмотренных однородных координатах, позволяющих единым образом выполнять аффинные и перспективные преобразования.
Программное исполнение отсечения достаточно медленный процесс, поэтому, естественно, в мощные дисплеи встраивается соответствующая аппаратура. Первое сообщение об аппаратуре отсечения, использующей алгоритм отсечения делением отрезка пополам и реализованной в устройстве Clipping Divider, появилось в 1968 г. [38]. Этот алгоритм был рассмотрен при изучении технических средств. Здесь мы рассмотрим программные реализации алгоритма отсечения.
Отсекаемые отрезки могут быть трех классов - целиком видимые, целиком невидимые и пересекающие окно. Очевидно, что целесообразно возможно более рано, без выполнения большого объема вычислений принять решение об видимости целиком или отбрасывании. По способу выбора простого решения об отбрасывании невидимого отрезка целиком или принятия его существует два основных типа алгоритмов отсечения - алгоритмы, использующие кодирование концов отрезка или всего отрезка и алгоритмы, использующие параметрическое представление отсекаемых отрезков и окна отсечения. Представители первого типа алгоритмов - алгоритм Коэна-Сазерленда (Cohen-Sutherland, CS-алгоритм) [4] и FC-алгоритм (Fast Clipping - алгоритм) [37]. Представители алгоритмов второго типа - алгоритм Кируса-Бека (Curus-Beck, CB - алгоритм) и более поздний алгоритм Лианга-Барски (Liang-Barsky, LB-алгоритм) [32].
Алгоритмы с кодированием применимы для прямоугольного окна, стороны которого параллельны осям координат, в то время как алгоритмы с параметрическим представлением применимы для произвольного окна.
Вначале мы рассмотрим алгоритм Коэна-Сазерленда, являющийся стандартом де-факто алгоритма отсечения линий и обладающий одним из лучших быстродействий при компактной реализации. Затем рассмотрим наиболее быстрый, но и чрезвычайно громоздкий FC-алгоритм. Далее рассмотрим алгоритм Лианга-Барски для отсечения прямоугольным окном с использованием параметрического представления. Быстродействие этого алгоритма сравнимо с быстродействием алгоритма Коэна-Сазерленда при большей компактности и наличии 3D и 4D реализаций. Последним рассмотрим алгоритм Кируса-Бека, который использует параметрическое представление и позволяет отсекать произвольным выпуклым окном. В заключение сравним быстродействие различных алгоритмов.
В этом разделе :
8 Двумерный алгоритм Коэна-Сазерленда
Этот алгоритм позволяет быстро выявить отрезки, которые могут быть или приняты или отброшены целиком.
8 Двумерный FC-алгоритм
В 1987 г. Собков, Поспишил и Янг предложили алгоритм, названный ими FC-алгоритмом (Fast Clipping), также использующий кодирование, но не конечных точек, а линий целиком.
8 Двумерный алгоритм Лианга-Барски
В1982 г. Лианг и Барски предложили алгоритмы отсечения прямоугольным окном с использованием параметрического представления для двух, трех и четырехмерного отсечения. По утверждению авторов, данный алгоритм в целом превосходит алгоритм Коэна-Сазерленда.
8 Двумерный алгоритм Кируса-Бека
Все рассмотренные выше алгоритмы проводили отсечение по прямоугольному окну, стороны которого параллельны осям координат. Это, конечно, наиболее частый случай отсечения. Однако, во многих случаях требуется отсечение по произвольному многоугольнику, например, в алгоритмах удаления невидимых частей сцены. В этом случае наиболее удобно использование параметрического представления линий, не зависящего
от выбора системы координат.
8 Сравнение алгоритмов двумерного отсечения
Во многих работах приводятся качественные соображения по быстродействию различных алгоритмов отсечения. В части работ приводятся результаты численных экспериментов по измерению скорости. Как правило, авторы работ этими экспериментами подтверждают преимущество своих алгоритмов.
8 Приложение 7. Процедуры отсечения отрезка
8 Список литературы
| |
*
Обратная связь