15.1. Введение

Предположим, что заданы трехмерный объем и видовые пара­метры, описывающие тип проекции, проекционную плоскость и т. д., и требуется определить, какие ребра и поверхности объекта видимы, если смотреть из центра проекции (для центральных проекций) или вдоль направления проецирования (для параллельных проек­ций). Только эти ребра и поверхности мы будем выводить на экран. Хотя задача формулируется просто, для ее решения требуется много процессорного времени, поэтому поощряются разработки многочис­ленных и тщательно структурированных алгоритмов.

Необходимость этих разработок следует из анализа двух основ­ных подходов к решению проблемы. В первом подходе объект рас­сматривается как совокупность п-угольных граней и необходимо определить, какая грань видна в каждой точке разрешения экрана дисплея. Чтобы выяснить при этом, какая из граней является бли­жайшей к наблюдателю, необходимо проверить все п граней для каждой разрешаемой точки. Для N таких точек число проверок пропорционально nN, где N обычно лежит в диапазоне 250 000— 4 000 000.

Во втором подходе каждая из п граней сравнивается с остав­шимися п—1 гранями. Число проверок в этом случае пропорцио­нально п². Поэтому можно предположить, что второй подход лучше даже для наибольших из реально встречающихся значений п (100000—200000). Однако каждый из индивидуальных шагов при втором подходе требует больше времени, поэтому этот процесс ока­жется медленнее даже при меньших п.

Сазерленд, Спрулл и Шумахер [454] назвали эти подходы алго­ритмами, работающими соответственно в пространстве изображе­ния и в пространстве объекта. Они рассмотрели и классифициро­вали десять алгоритмов, разработанных до 1972 г. Ниже описаны четыре из них, а также некоторые другие алгоритмы, созданные после 1972 г.

Алгоритмы удаления скрытых поверхностей необходимо стро­ить так, чтобы каждый их шаг был как можно более эффективным. В двух следующих разделах приведены некоторые общие рекомен­дации. Затем изложены специализированные алгоритмы, которые позволяют стирать скрытые поверхности на изображениях трехмер­ных объектов, составленных из полигональных граней. Некоторые из этих алгоритмов можно использовать для удаления скрытых ребер. Кратко описаны алгоритмы, которые предназначены для изображения объектов, заданных кусками криволинейной поверх­ности. Класс специализированных алгоритмов, предназначенных : для отображения однозначных функций двух переменных [68, 514], здесь не рассматривается.