Методы построчного сканирования

Построчное сканирование хорошо согласуется с растеризацией примитивов по спанам, и требует минимального дополнительного времени и памяти. При этом, каждой строке пикселов соответствует сечение сцены плоскостью, проходящей через эту строку. Таким образом, задача сводится к набору плоских задач удаления невидимых отрезков для каждой строки.

Определить, какие грани попадают в строку i очень просто, достаточно определить, попадает ли Y-координата центров пикселей этой строки в интервал между минимальной и максимальной Y-координатами точек грани Ymin<= i+0.5 <Ymax. Можно поступить следующим образом, при растеризации очередной грани, вместо того, чтобы рисовать спан его заносят в список спанов соответствующей ему строки (ListSpans[i]). Но это требует больших затрат по памяти (нужно хранить все спаны всех граней). Можно работать более эффективно, если воспользоваться когерентностью в картинной плоскости. Достаточно занести каждую грань в списки тех строк, в которые попадает ее первый спан (ListFaces[i]). Строки выводятся последовательно сверху вниз, существует список активных граней ActiveFaces. При переходе на очередную строку i из этого списка выбрасываются все грани, которые заканчиваются в этой строке (Ymax < i+0.5) и заносятся все грани из списка начинающихся в этой строке ListFaces[i]. Затем рассчитываются спаны для всех граней из ActiveFaces. В каждой грани нужно хранить все параметры для формирования следующего спана (s1,s2,k1,k2 и т.д.).

Наконец, можно хранить списки не граней а ребер. Есть списки начинающихся ребер ListEdges[i] и список активных ребер ActiveEdges. Очевидно, что ребра каждой грани можно разделить на три группы: левые, правые и горизонтальные. Горизонтальные ребра – не пересекают горизонтальных прямых, проходящих через центры пикселов и отбрасываются. Левые ребра ограничивают грань слева, правые – справа. Для каждой строки грань ограничена ровно двумя ребрами – левым и правым. Поэтому для получения спана нужно лишь знать эту пару, для этого в ребро заносят указатели на грань, а в грани – два указателя на активные ребра.

При переходе на очередную строку i из списка ActiveEdges выбрасываются все ребра, которые заканчиваются в этой строке (Ymax < i+0.5) и заносятся все ребра из списка начинающихся в этой строке ListEdges[i]. Указатели на закончившиеся ребра удаляются из соответствующих полей граней, которым они соответствуют, а указатели на начинающиеся ребра наоборот заносятся в эти поля. Затем рассчитываются спаны для всех граней, которым соответствуют ребра из ActiveEdges. При этом, пары ребер можно определить либо выбирая из списка только левые (это определяется при расчете ребер) и строя спаны от них до соответствующих правых ребер. Либо отсортировать активные ребра по возрастанию x, тогда первое встреченное ребро будет левым, для него следует выбрать правое, и пометить, его, чтобы не выбрать снова.

struct Edge { Face *face; float x,dx; int Ymax; Edge *next,*prev; };

struct Face { Edge *active_edges[2]; };