Рассмотрим, как работает процедура вставки нового отрезка newSpan в s-буфер.
Если отрезков в буфере нет, то новый отрезок просто добавляется. В противном случае сначала пропускаются все отрезки, лежащие левее нового отрезка (для которых х2 <^ newSpan->xl).
Пусть curSpan указывает на первый отрезок, не удовлетворяющий этому условию. Тогда возможна одна из следующих ситуаций (рис. 10.41).
Здесь жирным обозначен текущий отрезок (current). Тогда отрезки curSpan и new Span сравниваются и каждый из возможных случаев отрабатывается.
Существуют и другие реализации метода s-буфера, использующие связность отрезков между собой, разбиение пространства или иерархические структуры для оптимизации процедуры вставки и отсечения заведомо невидимых отрезков.
Здесь в отличие от рассмотренного ранее метода построчного сканирования строка может быть отрисована только тогда, когда будут обработаны все ее отрезки. Таким образом, сначала строится полное разложение строки (экрана) на набор отрезков, соответствующих видимым граням, а затем уже происходит отрисовка.
Вместо списка отрезков можно использовать бинарное дерево.
10. Удаление невидимых линий и поверхностей Следует иметь в виду, что при работе с .^-буфером необязательно работать только с одной строкой. Если для каждой строки завести свой указатель на список отрезков, то в 5-буфер можно выводить по граням: грань раскладывается на набор отрезков и производится вставка каждого отрезка в соответствующий список. Тем самым в отличие от традиционного метода построчного сканирования здесь циклы по граням и по строкам меняются местами.
По аналогии с методом иерархического 2-буфера можно рассмотреть метод иерархического ^-буфера. Понятия невидимости грани и куба относительно 5-буфера вводятся по аналогии, однако в этом случае производится уже не попиксельное сравнение, а сравнение на уровне отрезков. При этом отпадает необходимость в г-пирамиде; вместо нее для каждой строки 5-буфера нужно запомнить максимальное значение глубины и использовать полученные значения для быстрого отсечения граней куба. Вся сцена представляется в виде восьмеричного дерева, а процедура вывода сцены носит рекурсивный характер и состоит в вызове соответствующей процедуры, где в качестве параметра выступает корень дерева.