Процедура вывода куба состоит из следующих шагов.
1. Проверка попадания куба в область видимости (если куб не попадает, то он сразу же отбрасывается).
2. Проверка видимости относительно текущего 5-буфера (если куб невидим, то он сразу же отбрасывается).
3. Если куб является листом дерева, то последовательно выводятся все содержащиеся в нем лицевые грани. В противном случае рекурсивно обрабатываются все 8 его подкубов в порядке их удаления от наблюдателя.
Если все грани - выпуклые многоугольники, то для ускорения сравнения сегментов можно воспользоваться следующим соображением: так как любые две выпуклые грани, не имеющие общих внутренних точек, можно упорядочить, результаты сравнения соответствующих отрезков для двух произвольно взятых граней будут постоянными (зависящими только от расположения граней). Следовательно, результат сравнения отрезка текущей грани с отрезком в 5-буфере можно кешировать для использования на следующих строках этой грани.
При построении серии кадров можно воспользоваться временной когерентностью. В этом случае запоминается список всех видимых в данном кадре граней и построение следующего кадра начинается с вывода этих граней.
В таком виде метод иерархического 5-буфера удачно использует все три вида когерентности - в объектном пространстве (благодаря использованию восьмеричного дерева), в картинной плоскости (благодаря использованию 5-буфера и кешированию результатов сравнения отрезков) и временную когерентность.
10.4.5. Алгоритм Варнака (\Varnock)
Алгоритм Варнака является еще одним примером алгоритма, основанного на разбиении картинной плоскости на части, для каждой из которых исходная задача может быть решегга достаточно ггросто.
Разобьем видимую часть картинной плоскости па четыре равные части и рассмотрим, каким образом могут соотноситься между собой проекции граней и получившиеся части картинной плоскости.
Компьютерная графика. Полигональные модели Возможны 4 различных случая:
1. Проекция грани полностью накрывает область (рис. 10.42, а);