Рис. 7.17. Отсечение многоугольника
Алгоритмы формирования изображения
7.5. Отсечение примитивов других типов В главах 1-6 были рассмотрены программы, в которых все геометрические объекты формировались из прямолинейных отрезков и плоских многоугольников. Криволинейные объекты, которые мы еще будем подробно рассматривать в главе 10, в графических системах, как правило, аппроксимируются маленькими плоскими многоугольниками. В системах с конвейерной архитектурой вы практически всегда встретитесь с тем или иным вариантом модулей отсечения, ориентированных на работу с отрезками или плоскими многоугольниками. Но, тем не менее, встречаются ситуации, когда нужно выполнить отсечение геометрических объектов еще до того, как они "попадут" в аппаратный конвейер, или применить алгоритмы, оптимизированные с учетом специфики примитивов других типов.
7.5.1. Прямоугольные оболочки Предположим, что нам нужно обрабатывать многоугольники общего вида, имеющие довольно много вершин (рис. 7.18,а). Для этого можно воспользоваться одним из алгоритмов отсечения, рассмотренных выше, и применить его для обработки каждого из ребер многоугольника. Однако очень часто оказывается, что весь многоугольник лежит вне зоны видимости и что все усилия, затраченные на анализ его многочисленных ребер, пропали впустую. Значительно сократить затраты поможет предварительный анализ, в котором используется прямоугольная оболочка (bounding box) сложного объекта, в нашем примере- многоугольника (рис. 7.18,а). Такая оболочка- это прямоугольник минимального размера со сторонами, параллельными границам рамки отсечения, в который вписывается анализируемый объект. Определение параметров прямоугольной оболочки требует только последовательного просмотра всех вершин многоугольника и выявления максимального и минимального значений координат* и у.
Далее можно применить алгоритм отсечения к оболочке, что реализуется значительно быстрее, поскольку, во-первых, оболочка имеет только четыре стороны, а во-вторых, эти стороны параллельны границам рамки. Рассмотрим три варианта, представленные на рис. 7.19. Тот многоугольник, который находится выше рамки, сразу отбрасывается, поскольку нижняя сторона его оболочки находится выше верхней границы рамки. Многоугольник, который расположен внутри рамки отсечения, также не имеет смысла "запускать" на конвейер отсечения, поскольку его оболочка полностью умещается в зоне видимости. Процедуру отсечения нужно выполнять только по отношению к третьему многоугольнику, так как его оболочка частично перекрывает зону видимости. Прямоугольная оболочка может использоваться и в трехмерном пространстве, причем она формируется еще на этапе моделирования и сохраняется вместе с описанием объекта.