С другой стороны, алгоритм точности по изображению может происходить другим способом. Если на дисплее имеется N пикселов, то мы можем ожидать, что скорость такого алгоритма составит 0(nN), поскольку для каждого из N пикселов нам нужно протестировать п элементов сцены. На практике N намного больше п.
Чтобы уменьшить количество необходимых проверок, часто используют связность; при этом HSR-алгоритм может стать очень длинным. Цель заключается в том, чтобы уменьшить количество вычислений с 0(п2) или 0(nN) до более приемлемых величин 0(п log(n)), 0(Nlog(n)) или даже 0(п). В исчерпывающем исследовании Сазерленда [Sutherland, 193] содержатся полезные оценки времени работы многих популярных HSR-алгоритмов.
13.1.2. Описание данных для полигональных сеток Для того чтобы перейти к исследованию различных HSR-методов, напомним из главы 8 процесс, которому подвергается каждая грань полигональной сетки при ее прохождении через графический конвейер (рис. 13.3). Мы рассуждаем в терминах графического конвейера, наподобие конвейера OpenGL, поскольку это естественная схема «предварительной обработки» вершин. В то же время мы исследуем схемы HSR, отличные от схем, предлагаемых OpenGL, поэтому непосредственно конвейер OpenGL применяться не будет. Вершины грани подвергаются преобразованиям моделирования-вида и проекции и отсечению границами канонического отображаемого объема - единичного куба с псевдоглубинами в диапазоне от 0 до 1. В результате отсечения одни вершины могут исчезнуть, а другие - появиться. Такие атрибуты, как псевдоглубина, текстурные координаты и нормали в вершинах, вычисляются для этих новых вершин с помощью интерполяции. Затем для однородных координат выполняется перспективное деление, и х- и ^-компоненты каждой вершины отображаются из единичного куба в текущий порт просмотра на экране. Теперь значения х и у выражены в экранных координатах, однако не округляются до целых чисел, поскольку HSR-алгоритму точности по объекту требуется высокоточная информация о координатах объектов.