Аналогично используется когерентность между соседними гранями одного тела. Заметим, что изменение видимости отрезков может происходить при переходе только через те концы отрезков, которые соответствуют ребрам, принадлежащим сразу лицевой и нелицевой граням. Тем самым возникает некоторое (сравнительно небольшое) множество концов отрезков, являющееся аналогом контурных линий, и проверку на изменение видимости можно производить только при переходе через такие точки.
Для ускорения метода применяются различные формы разбиения пространства, включая равномерное разбиение пространства, деревья и т. д. Грани обрабатываются по мере удаления, и обработки заведомо невидимых граней можно избежать.
Вариантом метода построчного сканирования является так называемый метод а-буфера.
Ключевыми элементами метода 5-буфера являются:
массив списков отрезков для строк экрана,
меггеджер отрезков,
процедура вставки.
Для каждой строки экрана поддерживается список отрезков граней, задающий фактически для каждого пиксела видимую в этом пикселе грань.
Процесс заполнения массива происходит построчно. Изначально, для очередно!] строки, список отрезков пуст. Далее для каждой грани, пересекаемой сканирующей
10. Удаление невидимых линий и поверхностей плоскостью, строится соответствующий отрезок, который затем вставляется в список отрезков данной строки.
Ключевым местом алгоритма является процедура вставки отрезка в список. При этом отрезок может быть усечен, если он виден лишь частично, или вообще отброшен, если он не виден целиком.
Процедура вставки фактически сравнивает данный отрезок со всеми отрезками, уже присутствующими в списке. Ниже приводится пример простейшей процедуры вставки отрезка в упорядоченный список отрезков текущей строки. 0 //File sbuffer.h
//
// SBuffer management routines //
#ifndef __S_BUFFER__ #define _S_BUFFER__
#include <alloc.h> //for NULL
#include "polygon.h"
struct Span // span of S-Buffer {
float x1, x2; // endpoints of the span, as floats to