Листинг 13.4. Алгоритм строки развертки (псевдокод)
for (each scan line, у)
// для каждой строки развертки
for(each pixel, х. on scan line у) // для каждого пиксела на строке развертки у
{find the closest face that "covers" the pixel: // находим ближайшую грань, «покрывающую» данный пиксел с - color at (х, у) of the closest face: // цвет ближайшей грани в точке (х. у) set the pixel at(x. у) to color с II устанавливаем цвет пиксела в точке (х. у) в с }
Общая схема этого алгоритма приведена в листинге 13.4. Он аналогичен алгоритму закраски полигона из главы 10, за исключением того, что для каждого пиксела рассматривается более одного полигона. Различные варианты данного алгоритма [Bouknight, 34; Watkins, 208] отличаются друг от друга главным образом методом определения ближайшей грани и тем порядком, в котором выполняются различные этапы.
Серии пикселов вдоль строки развертки закрашиваются цветом того полигона, который покрывает эту серию. Если пиксел покрывается более чем одним полигоном, то выбирается цвет полигона, обладающего наименьшей глубиной. Для большей эффективности в алгоритме создаются и поддерживаются различные списки, призванные в максимальной степени использовать связность вдоль строки развертки. То есть если пиксел покрывается несколькими полигонами, то вероятнее всего, что и соседний с ним пиксел также будет покрываться этими полигонами. В алгоритме также учитывается связность ребер - для этого ребра всех граней предварительно обрабатываются, сортируются и помещаются в специальный список.
В примере на рис. 13.12 показано, как к выполнению операции HSR приспособить алгоритм закраски из раздела 10.7.2. На рисунке приведены проекции трех перекрывающихся пространственных плоских граней А, В, С. В списке активных ребер (active-edge list) хранятся те значения абсцисс х, при которых ребро какой-либо грани пересекает текущую строку развертки L. Эти точки пересечений хранятся в списке в отсортированном виде. Каждый узел списка указывает на грань, ответственную за данное пересечение: значение numCovered означает число граней, покрывающих данный пиксел, а в логическом массиве covered [ ] покрывающим граням соответствуют значения true.