Материал: Конспект лекций по дисциплине «Компьютерная графика». Лейкин М.А

зонтальных, двух вертикальных и 4 диагональных направлениях Алгоритм заполнения 8-связной области заполнит и 4-связную область, однако обратное не верно.

ПОСТРОЧНЫЙ АЛГОРИТМ ЗАПОЛНЕНИЯ С ЗАТРАВКОЙ

Данный алгоритм применим к гранично-определенным областям. Гранично-определенная 4-связная область может быть как выпуклой, так и не выпуклой, а также может содержать дыры. В области, внешней и примыкающей к нашей гранично-определенной области, не должно быть пикселов с цветом, которым область или многоугольник заполняется. Схематично работу алгоритма можно разбить на четыре этапа.

Затравочный пиксел на интервале извлекается из стека, содержащего затравочные пикселы.

Интервал с затравочным пикселом заполняется влево и вправо от затравки вдоль сканирующей строки до тех пор, пока не будет найдена граница.

Впеременных Хлев и Xправ запоминаются крайний левый и крайний правый пикселы интервала.

Вдиапазоне Хлев <= X <= Xправ проверяются строки, расположенные непосредственно над и под текущей строкой. Определяется, есть ли на них еще не заполненные пикселы. Если такие пикселы есть (т. е. не все пикселы граничные, или уже заполненные), то в указанном диапазоне крайний правый пиксел в каждом интервале отмечается как затравочный и помещается в стек.

При инициализации алгоритма в стек помешается единственный затравочный пиксел, работа завершается при опустошении стека. Ниже приводится более подробное описание алгоритма на псевдокоде.

// Затравка (X, Y) выдает затравочный пиксел

Push Затравка (X, Y) while стек не пуст

//извлекаем пиксел из стека и присваиваем ему новое значение Рор Пиксел (X, Y)

Пиксел (X, Y) = Нов_значение

//сохраняем X-координату затравочного пиксела

temp_X = X

//заполняем интервал справа от затравки

X = X + 1

while Пиксел (X, Y) <> Гран_значение Пиксел (X, Y) = Нов_значение

X = X + 1 end while

//сохраняем крайний справа пиксел Хправ = X - 1

//восстанавливаем X-координату затравки

X = temp_X

//заполняем интервал слева от затравки

X = Х - 1

while Пиксел (X, Y) < > Гран_значение Пиксел (X, Y) = Нов_значение

X = X - 1 end while

//сохраняем крайний слева пиксел Хлев = X + 1

//восстанавливаем X-координату затравки

X = temp_X /*

проверим, что строка выше не является ни границей многоугольника, ни уже полностью заполненной; если это не так, то найти затравку, начиная с левого края подынтервала сканирующей строки

*/

X = Хлев

Y = Y + 1

while X <= Хправ

//ищем затравку на строке выше

Флаг =0

while Пиксел (X, Y) <> Гран_значение and Пиксел (х, у) <> Нов_значение and х < Хправ

If Флаг = 0 then Флаг = 1

X = X + 1 end while

//помещаем в стек крайний справа пиксел if Флаг = 1 then

If X = Хправ and

Пиксел (X, Y) < > Гран_значение and Пиксел (х, у) < > Нов-значение) then

Push Пиксел (X, Y)

else

Push Пиксел (X-1, Y) end if

Флаг = 0 end if

//продолжим проверку, если интервал был прерван Хвход = X

while (Пиксел (X, Y) = Гран_значение оr

Пиксел (X, Y) = Нов_значение) and

х< Хправ

х= х + 1 end while

//удостоверимся, что координата пиксела увеличена if X = Хвход then X = X + 1

end while /*

проверим, что строка ниже не является ни границей многоугольника, ни уже полностью заполненной

эта часть алгоритма совершенно аналогична проверке для строки выше. за исключением того, что вместо Y = Y + 1 надо подставить Y = Y - 1

*/ end while finish

ОСНОВЫ МЕТОДОВ УСТРАНЕНИЯ СТУПЕНЧАТОСТИ

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

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

Один тип усреднения предполагает, что каждый дисплейный пиксел делится на подпикселы в процессе формирования растра более высокого разрешения. Для получения атрибутов дисплейного пиксела определяются атрибуты в центре каждого подпиксела, которые затем усредняются. В некоторой степени можно получить лучшие результаты, если рассматривать больше подпикселов и учитывать их влияние с помощью весов при определении атрибутов.

Второй метод устранения искажений изображения состоит в том, чтобы трактовать пиксел не как точку, а как конечную область. Далее приводится эвристический метод, реализующий этот подход. Трактование пиксела как конечной области эквивалентно префильтрации изображения.

ПРОСТОЙ МЕТОД УСТРАНЕНИЯ ЛЕСТНИЧНОГО ЭФФЕКТА

Валгоритмах разложения отрезка в растр и заполнения много угольника, обсуждавшихся выше, интенсивность или цвет пиксела определялись интенсивностью или цветом единственной точки внутри области пиксела. В этих методах предполагалось, что пиксел является скорее математической точкой, нежели конечной областью. Например, вспомнив алгоритм Брезенхема, мы увидим, что интенсивность пикселов определялась местоположением одной точки пересечения отрезка и границы пиксела. В методах растровой развертки сплошной области определение местоположения пиксела (внутри или вне много угольника) основывалось на положении центра пиксела. Если центр находился внутри, то активировался весь пиксел. Если центр находился вне, то игнорировалась вся область пиксела. Этот метод необходим для простых двухуровневых изображений, т. е. черных или белых, цвета многоугольника или цвета фона.

Врезультате получается характерное ступенчатое или зазубренное ребро многоугольника или отрезок. Как отмечалось ранее, основной причиной лестничного эффекта является то, что дискретность отрезка или ребра недостаточна для того, чтобы соответствовать дискретным пикселам экрана дисплея.

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

Врезультате простой модификации алгоритма Брезенхема можно получить аппроксимацию площади части пиксела, находящейся внутри многоугольника. Эту аппроксимацию можно использовать для модуляции интенсивности.

При пересечении пиксела и отрезка с тангенсом угла наклона m (0<=m<=1) может быть задействован либо один, либо два пиксела. Если пересекается только один пиксел, то площадь правее и ниже

отрезка равна Yi + m/2. Если же надо рассмотреть два пиксела, то площадь нижнего пиксела составляет 1 - (1-Yi)*(1-Yi)/(2*m), а верхнего - (Yi1+m)*(Yi-1+m)/(2*m). Для отрезка в первом октанте с тангенсом угла наклона m площадь верхнего пиксела может быть достаточно мала, чтобы ее можно было проигнорировать в вышеописанном эвристическом методе. Однако, объединение этой площади с площадью нижнего пиксела позволит более реалистично представить ребро многоугольника. Суммарная площадь двух пикселов равна Yi + m/2.

Если к ошибке в исходном алгоритме Брезенхема добавить величину w=m-1, т.е. ввести преобразование E = е + w, то 0 <= E <= 1. Теперь ошибка - это мера площади той части пиксела, которая находится внутри многоугольника, т е. Yi+m/2. В связи с этими модификациями начальное значение ошибки равно 1/2. Приведем алгоритм:

//отрезок проводится из (X1, Y1) в (X2, Y2)

//I - число доступных уровней интенсивности

//все переменные целого типа

//инициализация переменных

Х = X1

Y = Y1

dX = X2 - X1 dY = Y2 - Y1

m = (I * dY)/dX w = I - m

е= 1/2

Plot (X, Y, m/2) while X < X2

if е < w then

X = X+ 1

е = е + m

else

X= X+ 1

Y = Y+ 1 e = е- w

end if

Plot (X, Y, е) end while

finish

Интенсивность для первого пиксела предполагает, что отрезок начинается с адреса пиксела. Распространить работу алгоритма на другие октанты можно тем же способом, что и для основного алгоритма Брезенхема.

АППРОКСИМАЦИЯ ПОЛУТОНАМИ

Сглаживание или устранение ступенчатости - это метод улучшения визуального разрешения с использованием нескольких уровней интенсивности. Аппроксимация полутонами, с другой стороны, - это метод, в котором используется минимальное число уровней интенсивности, обычно черный и белый, для улучшения визуального разрешения, т. е. получения нескольких полутонов серого или уровней интенсивности. Успех метода полутонов зависит от свойства зрительной системы человека быть интегратором т. е. объединять или сглаживать дискретную информацию.

Визуальное разрешение машинно-сгенерированных изображений можно улучшить с помощью метода, называемого конфигурированием. В противоположность полутоновой печати, в которой используются переменные размеры клеток, в данном методе обычно размеры клеток фиксированы. Для изображения с фиксированным разрешением несколь-

ко пикселов объединяются в конфигурации. Здесь ухудшение пространственного разрешения обменивается на улучшение визуального.

В методе, разработанном Флойдом и Стейнбергом, ошибка выводимой информации для каждого пиксела распределяется на окружающие пикселы. Распределение ошибки происходит всегда вниз и вправо. Следовательно, при генерации изображения в порядке сканирования возвращаться обратно не нужно, в частности, в алгоритме Флой- да-Стейнберга 3/8 ошибки распределяется вправо, 3/8 - вниз и 1/4 - по диагонали. Для порога, равного среднему между минимальной и максимальной интенсивностями, Т = (Белый + Черный)/2, алгоритм формулируется следующим образом:

// Xmin, Xmax, Ymin, Ymax - пределы растра Т = (Черный + Белый)/2

for Y = Ymax to Ymin step -1

// для каждого пиксела на строке (слева направо) fоr X = Xmin to Xmax

// определяем выводимое значение пиксела для

//пороговой величины Т и вычисляем ошибку if I(X, Y) < T

then

Пиксел (X, Y) = Черный Ошибка = I(X, Y) - Черный

else

Пиксел (X, Y) = Белый Ошибка = I(X, Y) - Белый

end if

//изображаем пиксел

Display Пиксел (X, Y)

// распределяем ошибку на соседние пикселы

I(X+1, Y) = I(X+1, Y)+3 * Ошибка/8

I(X, Y-1) = I(X, Y-1)+3 * Ошибка/8

I(X+1, Y-1) = I(X+1, Y-1) + Ошибка/4 next X

next Y finish

Распределение ошибки на соседние пикселы улучшает вид деталей изображения, так как информация, заключенная в изображении, не теряется.

Существует другой метод улучшения визуального разрешения для двухуровневых дисплеев без уменьшения пространственного разрешения - метод возбуждения. В изображение вводится случайная ошибка, которая добавляется к интенсивности каждого пиксела до ее сравнения с выбранной пороговой величиной. Добавление совершенно произвольной ошибки не приводит к оптимальному результату. Тем не менее существует оптимальная аддитивная матрица ошибки, минимизирующая эффекты появления фактуры на изображении. Матрица ошибки добавляется к изображению таким же способом, как расположены клетки на шахматной доске. Данный метод называется упорядоченным возбуждением. Минимальная матрица упорядоченного возбуждения имеет размер 2х2. Оптимальная 2 х 2-матрица, которую первым предложил Лим, имеет вид

0 2

D(2) =

3 1

Матрицы D(4) - 4 х 4, D(8) - 8 X 8 и больших размеров получают с помощью рекуррентных соотношений

где n - размер матрицы и U(n) - верхняя треугольная единичная матрица порядка n.

Например, матрица возбуждения размера 4х4 имеет вид

Из матрицы возбуждения D(n) можно породить n*n интенсивностей. С увеличением n изображение не теряет пространственного разрешения. Приведем алгоритм упорядоченного возбуждения.

/*

Xmin, Xmax, Ymin, Ymax - пределы растра

mod - операция, возвращающая остаток от целого деления первого аргумента на второй

*/

for Y = Ymax to Ymin step -1

// для каждого пиксела на строке (слева направо) for X = Xmin to Xmax

//определяем позицию в матрице возбуждения i = (X mod n) + 1

j = (Y mod n) + 1

//определяем выводимое значение пиксела

if I(x, у) < D(i, j) then Пиксел (X, Y) = Черный else Пиксел (X, Y) = Белый

end if

// изображаем пиксел

Display Пиксел (X, Y)

Next X next Y finish

ОТСЕЧЕНИЕ

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

Алгоритмы отсечения бывают двуили трехмерными и применяют-

ся как к регулярным, так и к нерегулярным областям и объемам. Эти алгоритмы можно реализовать аппаратно или программно. Алгоритмы отсечения, реализованные программно, зачастую оказываются недостаточно быстродействующими для приложений ориентированных на процессы, протекающие в реальном времени. Поэтому как трехтак и двyмepныe алгоритмы отсечения реализуются аппаратными или микропрограммными средствами. В подобных реализациях обычно ограничиваются двуили трехмерными отсекателями типовых форм. Однако с появлением сверхбольших интегральных схем (СБИС) открываются возможности для более общих реализаций, позволяющих работать в реальном времени как с регулярными, так и с нерегулярными областями и телами.

ДВУМЕРНОЕ ОТСЕЧЕНИЕ

Представим себе плоскую сцену и отсекающее окно регулярной формы. Окно задается левым (Л), правым (П), верхним (В) и нижним (Н) двумерными ребрами. Регулярным отсекающим окном является прямоугольник, стороны которого параллельны осям координат объектного пространства или осям координат экрана. Целью алгоритма отсечения является определение тех точек, отрезков или их частей, которые лежат внутри отсекающего окна. Эти точки, отрезки или их части остаются для визуализации. А все остальное отбрасывается.

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

Точки, лежащие внутри отсекающего окна, удовлетворяют условию: Xл <= X <= Xп и Yн <= Y <= Yн. Знак равенства здесь показывает, что точки, лежащие на границе окна, считаются находящимися внутри него.

Отрезок лежит внутри окна и, следовательно, является видимым, если обе его концевые точки лежат внутри окна. Однако если оба конца отрезка лежат вне окна, то этот отрезок не обязательно лежит целиком вне окна. Если же оба конца отрезка лежат справа, слева, выше или ниже окна, то этот отрезок целиком лежит вне окна, а значит, невидим. Пусть а и b - концы отрезка, тогда можно предложить алгоритм, определяющий все полностью видимые и большинство невидимых отрезков:

//для каждого отрезка проверить полную видимость отрезка,

//если одна из координат какого-нибудь

//конца отрезка находится вне окна, то отрезок не является

//полностью видимым

if Xа < Хл or Xa > Xп then 1 if Xb < Хл or Xb > Xп then 1 if Ya < Yн or Ya > Yв then 1 if Yb < Yн or Yb > Yв then 1

// отрезок полностью видимый визуализироватъ отрезок

gоto 3

//проверить полную невидимость отрезка

//если оба конца отрезка лежат слева, cправа, сверху или

//снизу от окна, то факт невидимости отрезка тривиален

1if Xа < Хл or Xb < Xл then 1 if Xa > Хп or Xb < Xп then 1

if Ya > Yв or Yb > Yв then 1 if Ya < Yн or Yb < Yн then 1

//отрезок частично видим или пересекает продолжение

//диагонали, оставаясь невидимым

определить пересечения отрезка с окном

2отрезок невидим

3переход к следующему отрезку

Порядок проведения сравнений при определении видимости или невидимости несуществен. Для некоторых отрезков может понадобиться проведение всех четырех сравнений, прежде чем определится их полная видимость или невидимость. Для других отрезков может потребоваться только одно сравнение. Несущественно также, что выявляется раньше - полностью видимые или полностью невидимые отрезки. Однако, поскольку определение пересечения отрезка с окном требует большого объема вычислений, его следует проводить в последнюю очередь.

Приведенные выше тесты полной видимости или невидимости отрезков можно формализовать, используя метод Д. Коэна и А. Сазерленда. В этом методе для определения той из девяти областей, которой принадлежит конец ребра, вводится четырехразрядный код. Коды этих областей показаны на рисунке. Крайний правый бит кода считается первым. В соответствующий бит заносится 1 при выполнении следующих условий:

для первого бита - если точка левее окна для второго бита - если точка правее окна для третьего бита - если точка ниже окна для четвертого бита - если точка выше окна

лп

Впротивном случае в бит заносится нуль. Отсюда, очевидно следует, что если коды обоих концов ребра равны нулю, то обе эти точки лежат внутри окна, и отрезок видимый. Коды концевых точек можно использовать также и для тривиального отбрасывания полностью невидимых отрезков. Если побитовое логическое произведение кодов концевых точек отрезка не равно нулю, то отрезок полностью невидим и его можно отбросить тривиально.

Чтобы разработать схему эффективного алгоритма отсечения, необходимо сначала рассмотреть несколько частных случаев. Если наклон бесконечен, то отрезок параллелен левой и правой сторонам окна и надо искать его пересечения только с верхней и нижней сторонами. Аналогично, если наклон равен нулю, то отрезок параллелен верхней и нижней сторонам окна, а искать его пересечения надо только с левой и правой сторонами. Наконец, если код одного из концов отрезка равен нулю, то этот конец лежит внутри окна, и поэтому отрезок может пересечь только одну сторону окна.

АЛГОРИТМ ОТСЕЧЕНИЯ САЗЕРЛЕНДА - KОЭHA, ОСНОВАННЫЙ НА РАЗБИЕНИИ ОТРЕЗКА

В алгоритме Сазерленда - Коэна отрезок разбивается сторонами

окна. Отличие состоит в том, что здесь не производится проверки попадания точки пересечения внутрь окна, вместо этого каждая из пары получающихся частей отрезка сохраняется или отбрасывается в результате анализа кодов ее концевых точек. Ключом к алгоритму Сазерленда - Коэна является информация о том, что одна из концевых точек отрезка лежит вне окна. Поэтому тот отрезок, который заключен между этой точкой и точкой пересечения, можно отвергнуть как невидимый. Фактически это означает замену исходной концевой точки на точку пересечения. В содержательных понятиях алгоритм Сазерленда - Коэна формулируется следующим образом:

Для каждой стороны окна выполнить:

Для каждого отрезка Р1Р2 определить, не является ли он полностью видимым или может быть тривиально отвергнут как невидимый.

Если Р1 вре окна, то продолжить выполнение, иначе поменять Р1 и Р2 местами.

Заменить Р1 на точку пересечения Р1Р2 со стороной окна.

АЛГОРИТМ РАЗБИЕНИЯ СРЕДНЕЙ ТОЧКОЙ

Валгоритме из предыдущего раздела требовалось вычислить пересечение отрезка со стороной окна. Можно избежать непосредственного вычисления, если реализовать двоичный поиск такого пересечения путем деления отрезка его средней точкой. Алгоритм, основанный на этой идее и являющийся частным случаем алгоритма Сазерленда - Коэна, был предложен Спруллом и Сазерлендом для аппаратной реализации. Программная реализация этого алгоритма медленнее, чем реализация предыдущего алгоритма. Аппаратная же реализация быстрее и эффективнее, поскольку можно использовать параллельную архитектуру, и, кроме того, аппаратные сложения и деления на 2 очень быстры.

Валгоритме используются коды концевых точек отрезка и про верки, выявляющие полную видимость отрезков. Данный алгоритм можно формально разбить на три этапа.

Для каждой концевой точки отрезка:

Если концевая точка видима, то она будет наиболее удаленной видимой точкой. Процесс завершен. Иначе - продолжить.

Если отрезок тривиально характеризуется как невидимый, то выходная информация не формируется. Процесс завершен. Иначе - продолжить.

Грубо оценить наиболее удаленную видимую точку путем деления отрезка Р1Р2 средней точкой Рm. Применить вышеизложенные тесты к двум кускам Р1Рm и PmP2. Если РmР2 тривиально отвергается как невидимый, то средняя точка дает верхнюю оценку для наиболее удаленной видимой точки. Продолжить процедуру с отрезком Р1Pm. Иначе - средняя точка дает оценку снизу для наиболее удаленной видимой точки. Продолжить процедуру с куском Р2Рm. Если отрезок становится настолько мал, что его средняя точка совпадает с его концами с машинной или наперед заданной точностью, то надо оценить ее видимость и закончить процесс.

УДАЛЕНИЕ НЕВИДИМЫХ ЛИНИЙ И ПОВЕРХНОСТЕЙ

Сложность задачи удаления невидимых линий и поверхностей

привела к появлению большого числа различных способов ее решения. Многие из них ориентированы на специализированные приложения. Наилучшего решения общей задачи удаления невидимых линий и поверхностей не существует. Для моделирования процессов в реальном времени, например, для авиатренажеров, требуются быстрые алгоритмы, которые могут порождать результаты с частотой видеогенерации (30 кадр/с). Для машинной мультипликации, например, требуются алгоритмы, которые могут генерировать сложные реалистические изображения, в которых представлены тени, прозрачность и фактура, учитывающие эффекты отражения и преломления цвета в мельчайших оттенках. Подобные алгоритмы работают медленно, и зачастую на вычисления требуется несколько минут или даже часов. Строго говоря, учет эффектов прозрачности, фактуры, отражения и т. п. не входит в задачу удаления невидимых линий или поверхностей. Естественнее считать их частью процесса визуализации изображения. Процесс визуализации является интерпретацией или представлением изображения или сцены в реалистической манере. Однако многие из этих эффектов встроены в алгоритмы удаления невидимых поверхностей. Существует тесная взаимосвязь между скоростью работы алгоритма и детальностью его результата. Ни один из алгоритмов не может достигнуть хороших оценок для этих двух показателей одновременно. По мере создания все более быстрых алгоритмов можно строить все более детальные изображения. Реальные задачи, однако, всегда будут требовать учета еще большего количества деталей.

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

Алгоритмы удаления невидимых линий или поверхностей можно классифицировать по способу выбора системы координат или пространства, в котором они работают. Алгоритмы, работающие в объектном пространстве, имеют дело с физической системой координат, в которой описаны эти объекты. При этом получаются весьма точные результаты, ограниченные, вообще говоря, лишь точностью вычислений. Полученные изображения можно свободно увеличивать во много раз. Алгоритмы, работающие в объектном пространстве, особенно полезны в b%e приложениях, где необходима высокая точность. Алгоритмы же, работающие в пространстве изображения, имеют дело с системой координат того экрана, на котором объекты визуализируются. При этом точность вычислений ограничена разрешающей способностью экрана. Результаты, полученные в пространстве изображения, а затем увеличенные во много раз, не будут соответствовать исходной сцене. Например, могут не совпасть концы отрезков. Алгоритмы,