Эти алгоритмы функционируют в пространстве изображений, причем образ в них
генерируется построчно. Здесь будет описан общий подход. Этот подход является
расширением алгоритма преобразования многоугольника в растровую форму. Различие
заключается в том, что в этом случае мы имеем дело не с одним многоугольником, а
сразу со всеми многоугольниками, определяющими объект. На первом шаге создается
таблица ребер (ТР), содержащая все негоризонтальные ребра многоугольников,
элементы ТР отсортированы по группам на основе меньшей y-координаты каждого
ребра, а внутри групп _ в зависимости от величины тангенса угла наклона. Эти
элементы содержат:
    x-координату крайней точки ребра с меньшей y-координатой; y-координату
    другой крайней точки ребра;
    приращение dx координаты x, используемое для перехода от кажой сканирующей
    точки к следкющей (dx обратно тангенсу угла наклона ребра);
    идентификатор ногоугольника, указывающий, какому многоугольнику принадлежит
    данное ребро.

рис.1

На втором шаге создается таблица многоугольников (ТМ), в которой содержится, по
крайней мере, следующая информация о каждом многоугольнике:
    коэффициенты уравнения плоскости;
    информация о закраске многоугольника;
    булева переменная (флаг), определяющая положение внутри/вне многоугольника.
    (Она используется при обработке сканирующей строки; вначале этой переменной
    присваивается значение false (ложь).)
На третьем шаге создается таблица активных ребер (ТАР), которая всегда
упорядочена по возрастанию координат x. К тому времени, когда алгоритм дойдет до
сканирующей строки y=a, ТАР будет содержать AB и AC в указанном порядке. Ребра
рассматриваются в направлении слева направо. Приступая к обработке AB,
инвертируем, прежде всего, флаг треугольника ABC. Тогда флаг примет значение
true и, следовательно, мы окажемся "внутри" треугольника, который необходимо
рассмотреть. Теперь, поскольку мы находимся внутри только одного треугольника,
последний должен быть видимым и, следовательно, на интервале от ребра AB до
следующего ребра AC в ТАР будет вестись закраска, требуемая для текущего
треугольника. При прохождении ребра AC флаг треугольника меняется на
противоположное значение, то есть теперь мы не находимся внутри ни одного
треугольника. Поскольку AC является последним ребром в ТАР, обработка
сканирующей строки завершается. В ТАР вносятся изменения из ТР, она снова
упорядочивается по x и производится переход к обработке следующей строки.
Когда встретится сканирующая строка y=b, в отсортированной ТАР будут находиться
AB, AC, FD и FE. Обработка продолжается в основном так же, как прежде. Со
сканирующей строкой пересекаются два треугольника, но мы в каждый момент будем
находиться "внутри" только одного из них.
Наиболее интересна ситуация для строки y=g. При входе в ABC флаг треугольника
становится равным true. На интервале от точки входа до следующего ребра DE
ведется закраска, соответствующая треугольнику ABC. В точке пересечения с DF
флаг DEF также устанавливается в true, то есть мы будем находится внутри обоих
треугольников. Теперь требуется решить, какой из треугольников расположен ближе
к наблюдателю. Определение производится путем вычисления координаты z,
соответствующей каждому треугольнику. Правило закраски будет действовать для
треугольника z-координата которого меньше. Так проводится сканирование каждой
строки.
Можно значительно уменьшить количество расчетов, если воспользоваться
когерентностью по глубине. Если при обработке некоторой сканирующей строки ТАР
полностью совпадает с ТАР предшествующей строки, то соотношения глубин остаются
прежними, то есть нет необходимости в их вычислении. Такая ситуация показана на
рис. 1, для строк y=g и y=g + 1. Когерентность по глубине теряется при переходе
от y=g + 1 и y=g + 2, поскольку в ТАР меняется взаимная упорядоченность ребер DE
и FE. Хэмлин и Джир показали, как иногда может сохранятся когерентность по
глубине, даже если меняется порядок ребер в ТАР.
Для отображения фона можно в начальный момент заполнить буфер регенерации
пикселами, соответствующими фону или помещать фоновые пикселы в буфер в тех
случаях, когда мы не находимся "внутри" многоугольника.
Написал Вася Пупкин.