В этой главе мы исследуем различные HLR- и HSR-алгоритмы, объединяя их в силу схожести под общим названием алгоритмов удаления невидимых поверхностей (hidden-surface-removal). Назначение этих алгоритмов - эффективно определить, какие части поверхности или ребра закрываются какой-нибудь другой поверхностью. Способы осуществления этого заключаются в сложном взаимодействии расположения наблюдателя и различных объектов на сцене.
Основное внимание в данной главе сосредоточено на сценах, составленных из полигональных каркасных объектов, однако рассматриваются и другие классы объектов. В главе 14 мы увидим, что совсем другим подходом к проблеме HSR является трассировка лучей. При трассировке лучей невидимые поверхности любой формы удаляются автоматически, хотя при этом требуется огромный объем вычислений.
26 Ф. Хилл
Удаление невидимых поверхностей
13.1.1. Два подхода: «точность по объекту» и «точность по изображению» Алгоритмы удаления невидимых линий или поверхностей имеют различную форму в зависимости от
следующего критерия, описанного в работе [Sutherland, 193]: О Точность по объекту1. Алгоритм с точностью данной машины вычисляет координаты каждого видимого ребра каждой грани. Алгоритмы этого типа реализуются в физической системе координат, в которой описаны объекты. Этот вид точности подходит для технического черчения. При использовании подхода точности по объекту изображение можно увеличивать во много раз, при этом результаты будут по-прежнему точными.
О Точность по изображению. Для каждого пиксела на дисплее алгоритм определяет, какой элемент какой грани является ближайшим к наблюдателю, и рисует этот пиксел соответствующим цветом. Алгоритмы точности по изображению реализуются только с точностью до оконной системы координат экрана.
HSR-алгоритмы должны работать настолько быстро, насколько это возможно. Нас интересует, как время вычисления зависит от сложности объектов на сцене, а также от числа объектов. Если мы обозначим количество элементов на сцене - ребер или граней - буквой п, то мы можем рассчитывать, что время работы HSR-алгоритма точности по объекту составит 0(п2),2 поскольку каждый элемент должен быть проверен относительно каждого другого элемента, чтобы выяснить, который из них заслоняет другой.