Остается решить три задачи: выполнить окончательное ортогональное проецирование, удалить невидимые поверхности и тонировать образ многоугольника. Тщательно продуманный алгоритм обработки г-буфера позволяет решать эти три задачи одновременно. Рассмотрим два варианта представления многоугольника, показанные на рис. 7.50. В левой части ри-
Алгоритмы формирования изображения
сунка многоугольник изображен в трехмерной нормализованной системе координат устройства отображения, а в правой - в двухмерной системе координат экрана.
Многоугольник обрабатывается построчно, и каждая строка соответствует отрезку на поверхности многоугольника, все точки которого имеют постоянное значение координаты у в нормализованной системе координат устройства отображения (рис. 7.51). Сканируя образ многоугольника в координатах экрана, мы перемещаемся на каждом шаге на один пиксель вправо, а использование нормализованных координат позволяет одновременно интерполировать параметр глубины очередной точки поверхности и анализировать ее видимость, используя информацию из г-буфера. Располагая данными об освещенности (цвете) каждой вершины обрабатываемого многоугольника, можно одновременно интерполировать и цвет точки поверхности. Каждая из описанных операций не требует громоздких вычислений, и все их можно выполнять в едином цикле сканирования. К описанным можно добавить и операции, необходимые для наложения текстур, о которых речь пойдет в главе 9.
7.10.4. Заполнение внутренней области и сортировка Другой подход к растровому преобразованию многоугольников основан на идее отдельного блока обработки многоугольников - процессора многоугольников. Концептуально такой процессор представляет собой "черный ящик", на вход которого подаются вершины множества двухмерных многоугольников, а выходом является корректно заполненный буфер кадра.
Рассмотрим частный случай - контур каждого многоугольника заполняется одним цветом. Это ограничение введено только для того, чтобы изложение идеи было более ясным. Сначала рассмотрим отдельный многоугольник. Основное правило заполнения его контура формулируется совершенно очевидно: если пиксель соответствует точке, которая находится внутри контура многоугольника, ей должен быть присвоен цвет, назначенный многоугольнику {цвет закраски). Из такой формулировки концепции следует, что закраска многоугольника сводится, в конце концов, к задаче сортировки - нужно рассортировать все пиксели в буфере кадра на те, которые принадлежат внутренней области многоугольника, и те, которые ей не принадлежат. С точки зрения этой концепции алгоритмы закраски многоугольников отличаются друг от друга способом сортировки точек. Мы рассмотрим три варианта алгоритмов: