Поскольку HSR-методы основаны на принятии решения, какой из двух элементов «ближе» к глазу, чем другой, или какой элемент из группы является «ближайшим», то ядром каждого HSR-алгоритма являются сортировка и переупорядочивание. (Это обстоятельство становится особенно ясным после чтения превосходного обзора HSR-методов, сделанного Сазерлендом и другими авторами [Sutherland, 1931,) Поскольку сортировка может оказаться дорогостоящей, ключ к эффективности алгоритма - не делась эту сортировку больше, чем это абсолютно необходимо. В таких методах, как алгоритм буфера глуби.; ны, используется огромное количество памяти только для уменьшения расходов на сортировку (обычно она сводится просто к поиску ближайшего элемента).
13.8. Резюме Сортировка по х, у, z производится различными алгоритмами в различном порядке, в соответствии с порядком обработки данных, как это сделано в следующем псевдокоде:
for(each pixel){ // каждый пиксел
for(each face){…} } // каждая грань
в сравнении с таким порядком:
for(each face){
for(each pixel){…}Во всех этих алгоритмах сделан различный компромиссный выбор между скоростью, пространством памяти и простотой.
Для уменьшения вычислительных затрат при работе HSR-метода были разработаны хитроумные способы использования связности. Связность - это тенденция какого-нибудь аспекта сцены к плавному изменению в некотором направлении движения, так что свойство, имеющееся в одной точке, очень похоже на то же свойство в близлежащих точках. В рассмотренных здесь методах использовались различные типы связности, такие как связность области, связность глубин, связность строки развертки, а также связность ребра.
Мы рассмотрели три HSR-алгоритма со «списками приоритетов» - это технологии, основанные на хитроумной сортировке списка граней, так чтобы визуализатор мог рисовать грани в новом порядке, удаляя те из них, которые находятся позади других граней. В успешно действующих методах, таких как метод дерева двоичного разбиения пространства, определенные грани разделяются на две части. Подобно подходу с буфером глубины, методы со списками приоритетов несвободны от большого количества повторного рисования пикселов.