Рис. 6.23. Этапы обработки многоугольной закрашенной области при отсечении прямоугольной областью
Рис. 6.24. Многоугольная закрашенная область, координатные границы которой находятся за правой границей отсечения Многоугольную закрашенную область можно извлечь из отсекающего окна, используя тот же общий подход, что и в отсечении линий. Отрезок определяется двумя его концами, и эти точки обрабатываются процедурой отсечения линий, для чего строится новый набор конечных точек, обрезанных на всех границах отсекающего окна. Таким образом, требуется следить, чтобы закрашенная область была единым объектом при обработке на этапах отсечения. Следовательно, для многоугольной закрашенной области можно определять новую форму при обработке каждой стороной отсекающего окна, как показано на рис. 6.23. Разумеется, внутренняя часть многоугольника не будет закрашена, пока не определится окончательная отсеченная граница.
В приведенных выше схемах первая проверка отрезка определяла, можно ли его полностью извлечь или полностью отбросить. Ту же процедуру можно выполнить и для многоугольной закрашенной области, проверив ее координатные границы. Если минимальная и максимальная координаты закрашенной области находятся внутри всех четырех линий отсечения, закрашенная область извлекается для дальнейшей обработки. Если все данные координатные границы находятся вне какой-то границы отсекающего окна, многоугольник исключается из описания сцены (рис. 6.24).
Если закрашенную область нельзя однозначно отнести к полностью внутренним или полностью внешним по отношению к отсекающему окну, необходимо определить точки пересечения с линиями отсечения. Один метод реализации отрезания заключается в создании нового списка вершин на каждой линии отсечения, а затем передаче этого нового списка вершин следующей процедуре отсечения по линии. Выход конечного этапа отсечения - список вершин извлеченного многоугольника (рис. 6.25). При отсечении вогнутым многоугольником данный базовый подход потребуется несколько модифицировать, так что генерироваться будет несколько списков вершин.
ОТСЕЧЕНИЕ МНОГОУГОЛЬНИКАМИ САЗЕРЛЕНДА-ХОДГМАНА
Эффективный метод извлечения закрашенного выпуклого многоугольника, разработанный Сазерлендом и Ходгманом (Нос^тап), заключается в следующем: так пропускать вершины многоугольника по всем этапам отсечения, чтобы отдельную отсеченную вершину можно было сразу передавать на следующий этап. Это позволяет не создавать на каждом этапе отсечения выходной набор вершин, а также реализовать процедуры отсечения по границам параллельно. Окончательный выход - это список вершин, описывающих стороны извлеченной многоугольной закрашенной области.
Поскольку алгоритм Сазерленда-Ходгмана дает только один список выходных вершин, он не может корректно сгенерировать два выходных многоугольника, показанных на рис. 6.22, б, полученных при отсечении вогнутого многоугольника, приведенного на рис. 6.22, а. В то же время, алгоритм можно изменить, чтобы он давал несколько выходных списков вершин и позволял обрабатывать вогнутые многоугольники общей формы. Стандартный алгоритм Сазерленда-Ходгмана может обрабатывать вогнутые многоугольники, если получающуюся в результате область можно описать одним списком вершин.