ЛАБОРАТОРНАЯ РАБОТА № 11
Методы удаления  невидимых  ребер и граней
 
1. Цель работы
 
1) Освоить программирование алгоритмов удаления невидимых ребер и граней с использованием методов объектно-полигонального моделирования.
2) Разработать программу в среде  C++Builder, для демонстрации удаления невидимых граней при вращении заданной трехмерной фигуры в двух плоскостях в режиме аксонометрического проецирования.
3) Освоить методы анимационного управления графическими объектами с использованием клавиатуры и мыши.
 
2.  Постановка задачи
 
2.1. В проект, разработанный для лабораторных работ по 3D-графике добавить новый модуль с формой Form6.
2.2. В графическом окне Form6 изобразить фигуру, заданную по варианту, из таблицы 1. Фигура должна быть прорисована в режиме аксонометрического (или любого другого) проецирования с удаленными невидимыми ребрами и гранями.
2.3. Используя средства управления, расположенные на панели, продемонстрировать следующее:
1) Изменение масштаба фигуры;
2) Изменение положения (перенос) фигуры с применением кнопок клавиатуры;
3) Включение или выключение закраски поверхностей фигуры разными цветами;
4) Вращение фигуры в двух плоскостях при нажатии на кнопки "Влево", "Вправо", "Вверх", "Вниз", расположенных на панели управления окна проекта, а также при движении мыши в горизонтальных или вертикальных направлениях (при зажатой левой кнопке мыши);
5) Изменение скорости вращения фигуры при нажатии на заданную кнопку клавиатуры.


3.  Основные теоретические сведения
3.1.  Обзор  алгоритмов  удаления  невидимых  линий  и  поверхностей
 
Задача удаления невидимых линий и поверхностей является одной из наиболее сложных в машинной графике. Алгоритмы удаления невидимых линий и поверхностей служат для определения линии ребер, поверхностей или объемов, которые видимы или невидимы для наблюдателя, находящегося в заданной точке пространства.
Сложность задачи удаления невидимых линий и поверхностей привела к появлению большого числа различных способов ее решения. Многие из них ориентированы на специализированные приложения. Наилучшего решения общей задачи удаления невидимых линий и поверхностей не существует. Ни один из алгоритмов не может достигнуть хороших оценок для показателей одновременно: детальностью прорисовки и скоростью работы.
Все алгоритмы удаления невидимых линий (поверхностей) включают в себя сортировку. Порядок, в котором производится сортировка координат объектов, не влияет на эффективность этих алгоритмов. Главная сортировка ведется по геометрическому расстоянию от тела, поверхности, ребра или точки до точки наблюдения. Основная идея, положенная в основу сортировки по расстоянию, заключается в том, что чем дальше расположен объект от точки наблюдения, тем больше вероятность, что он будет полностью или частично заслонен одним из объектов, более близких к точке наблюдения. После определения расстояний или приоритетов по глубине остается провести сортировку по горизонтали и по вертикали, чтобы выяснить, будет ли рассматриваемый объект действительно заслонен объектом, расположенным ближе к точке наблюдения.
Алгоритмы удаления невидимых линий или поверхностей можно классифицировать по способу выбора системы координат или пространства, в котором они работают. Алгоритмы, работающие в объектном пространстве, имеют дело с физической системой координат, в которой описаны эти объекты. При этом получаются весьма точные результаты, ограниченные лишь точностью вычислений. Полученные изображения можно свободно увеличивать во много раз. Алгоритмы же, работающие в пространстве изображения, имеют дело с системой координат того экрана, на котором объекты визуализируются. При этом точность вычислений ограничена разрешающей способностью экрана. Результаты, полученные в пространстве изображения, а затем увеличенные во много раз, не будут соответствовать исходной сцене.
Здесь будут рассмотрены такие алгоритмы удаления невидимых линий как:
- алгоритм плавающего горизонта;
- алгоритм Варнока;
- алгоритм Вейлера-Азертона;
- алгоритм Z-буфера;
- алгоритм Робертса.
 
3.2. Алгоритм  плавающего горизонта
 
Алгоритм плавающего горизонта чаще всего используется для удаления невидимых линий трехмерного представления функций, описывающих поверхность в виде F(x,y,z) = 0.
Поскольку в приложениях в основном интересуются описанием поверхности, этот алгоритм обычно работает в пространстве изображения. Главная идея данного метода заключается в сведении трехмерной задачи к двумерной путем пересечения исходной поверхности последовательностью параллельных секущих плоскостей, имеющих постоянные значения координат x, y или z. Функция F(x,у,z) = 0 сводится к последовательности кривых, лежащих в каждой из этих параллельных плоскостей, например к последовательности y = f(x,z) или х = g(y,z), где z постоянно на каждой из заданных параллельных плоскостей.
Поверхность теперь складывается из последовательности кривых, лежащих в каждой из этих плоскостей, как показано на рисунке 1. Если спроецировать полученные кривые на плоскость z = 0, то сразу становится ясна идея алгоритма удаления невидимых участков исходной поверхности. Алгоритм сначала упорядочивает плоскости z = const по возрастанию расстояния до них от точки наблюдения. Затем для каждой плоскости, начиная с ближайшей к точке наблюдения, строится кривая, лежащая на ней, т. е. для каждого значения координаты х в пространстве изображения определяется соответствующее значение y.
Алгоритм удаления невидимой линии заключается в следующем: если на текущей плоскости при некотором заданном значении х соответствующее значение y на кривой больше значения y для всех предыдущих кривых при этом значении х, то текущая кривая видима в этой точке; в противном случае она невидима.
 
Рисунок 1 – Кривые в секущих плоскостях с постоянной координатой
 
Реализация данного алгоритма достаточно проста. Для хранения максимальных значений y при каждом значении х используется массив, длина которого равна числу различимых точек (разрешению) по оси х в пространстве изображения. Значения, хранящиеся в этом массиве, представляют собой текущие значения «горизонта». Поэтому по мере рисования каждой очередной кривой этот горизонт «всплывает». Фактически этот алгоритм удаления невидимых линий работает каждый раз с одной линией.
 
3.3.  Алгоритм  Варнока
 
Основные идеи, на которые опирается алгоритм Варнока, обладают большой общностью. Они основываются на гипотезе о способе обработки информации, содержащейся в сцене, глазом и мозгом человека. Эта гипотеза заключается в том, что тратится очень мало времени и усилий на обработку тех областей, которые содержат мало информации. Большая часть времени и труда затрачивается на области с высоким информационным содержимым. В алгоритме Варнока и его вариантах делается попытка извлечь преимущество из того факта, что большие области изображения однородны. Такое свойство известно как когерентность, т.е. смежные области (пиксели) вдоль обеих осей х и y имеют тенденцию к однородности.
Поскольку алгоритм Варнока нацелен на обработку картинки, он работает в пространстве изображения. В пространстве изображения рассматривается окно и решается вопрос о том, пусто ли оно, или его содержимое достаточно просто для визуализации. Если это не так, то окно разбивается на фрагменты до тех пор, пока содержимое подокна не станет достаточно простым для визуализации или его размер не достигнет требуемого предела разрешения. В последнем случае информация, содержащаяся в окне, усредняется, и результат изображается с одинаковой интенсивностью или цветом. При достижении подокном уровня пикселя существует два дальнейших пути реализации алгоритма: удаление невидимых линий и удаление невидимых поверхностей. Если необходимо применить алгоритм удаления невидимых линий, то пиксель, соответствующий данному подокну, активируется в случае, если через него проходят видимые ребра. В результате получается изображение видимых ребер многоугольников в виде последовательности точек размером с пиксель каждая. Для алгоритма удаления невидимых поверхностей проверяется охват этого подокна каждым многоугольником сцены. Если такой охват обнаружен, то среди охватывающих пиксель многоугольников выбирается ближайший к точке наблюдения на направлении наблюдения, проходящим через данный пиксель. Затем этот пиксель изображается с интенсивностью или цветом ближайшего многоугольника. Если охватывающие многоугольники не найдены, тот окно размером с пиксель пусто, и оно изображается с фоновой интенсивностью или цветом.
 
3.4.  Алгоритм  Вейлера-Азертона
 
Данный алгоритм является разновидностью алгоритма Варнока и здесь разбиение окна происходит вдоль границ многоугольника. Выходными данными этого алгоритма, который для достижения необходимой точности работает в пространстве объекта, служат многоугольники. Поскольку выходом являются многоугольники, то алгоритм можно легко использовать для удаления как невидимых линий, так и невидимых поверхностей. Алгоритм удаления невидимых поверхностей состоит из четырех шагов:
1. Предварительная сортировка по глубине.
2. Отсечение по границе ближайшего к наблюдателю многоугольника, называемое сортировкой многоугольников на плоскости.
3. Удаление многоугольников, экранированных многоугольником, ближайшим к точке наблюдения.
4. Если требуется, то рекурсивное подразбиение и окончательная сортировка для устранения всех неопределенностей.
Предварительная сортировка по глубине нужна для формирования списка приблизительных приоритетов. Если точка наблюдения расположена в бесконечности на положительной полуоси z, тогда ближайшим к ней и первым в списке будет тот многоугольник, который обладает вершиной с максимальной координатой z.
В качестве отсекающего многоугольника используется копия первого многоугольника из предварительного списка приоритетов по глубине. Отсекаться будут остающиеся в этом списке многоугольники, включая и первый многоугольник. Вводятся два списка: внутренний и внешний. С помощью алгоритма отсечения Вейлера-Азертона все многоугольники отсекаются по границам отсекающего многоугольника. Фактически это двумерная операция отсечения проекций отсекающего и отсекаемого многоугольников. Та часть каждого отсекаемого многоугольника, которая оказывается внутри отсекающего, если она имеется, попадает во внутренний список. Оставшаяся часть, если таковая есть, попадает во внешний список. Этот этап алгоритма является сортировкой на плоскости или xy-сортировкой [1]. После этого сравниваются глубины каждого многоугольника из внутреннего списка с глубиной отсекающего многоугольника. С использованием координат (х, y) вершин отсекаемых многоугольников и уравнений несущих плоскостей вычисляются глубины (координаты z) каждой вершины. Затем они сравниваются с минимальной координатой z (zc min) для отсекающего многоугольника. Если глубина ни одной из этих вершин не будет больше zc min, то все многоугольники из внутреннего списка экранируются отсекающим многоугольником. Эти многоугольники удаляются, и изображается внутренний список. При этом во внутреннем списке остается лишь отсекающий многоугольник. Работа алгоритма затем продолжается с внешним списком.
Если координата z какого-либо многоугольника из внутреннего списка окажется больше, чем zc min, то такой многоугольник по крайней мере частично экранирует отсекающий многоугольник. В подобном случае результат предварительной сортировки по глубине ошибочен. Поэтому алгоритм рекурсивно подразделяет плоскость (х,y), используя многоугольник, нарушивший порядок, в качестве нового отсекающего многоугольника. Отсечению подлежат многоугольники из внутреннего списка, причем старый отсекающий многоугольник теперь сам будет подвергнут отсечению новым отсекающим многоугольником. Здесь новый отсекающий многоугольник является копией исходного многоугольника, а не его остатка после первого отсечения.
 
3.5. Алгоритм  Z-буфера
 
Это один из простейших алгоритмов удаления невидимых поверхностей. Работает этот алгоритм в пространстве изображения. Идея Z-буфера является простым обобщением идеи о буфере кадра. Буфер кадра используется для запоминания интенсивности каждого пикселя в пространстве изображения. Z-буфер – это отдельный буфер глубины, используемый для запоминания координаты z или глубины каждого видимого пикселя в пространстве изображения. В процессе работы глубина или значение z каждого нового пикселя, который нужно занести в буфер кадра, сравнивается с глубиной того пикселя, который уже занесен в Z-буфер. Если это сравнение показывает, что новый пиксель расположен впереди пикселя, находящегося в буфере кадра, то новый пиксель заносится в этот буфер и, кроме того, производится корректировка Z-буфера новым значением z. Если же сравнение дает противоположный результат, то никаких действий не производится. По сути, алгоритм является поиском по х и y наибольшего значения функции z(х,y).
Главное преимущество алгоритма - его простота. Кроме того, этот алгоритм решает задачу об удалении невидимых поверхностей и делает тривиальной визуализацию пересечений сложных поверхностей. Сцены могут быть любой сложности. Поскольку габариты пространства изображения фиксированы, оценка вычислительной трудоемкости алгоритма не более чем линейна. Поскольку элементы сцены или картинки можно заносить в буфер кадра или в Z-буфер в произвольном порядке, их не нужно предварительно сортировать по приоритету глубины. Поэтому экономится вычислительное время, затрачиваемое на сортировку по глубине.
Основной недостаток алгоритма - большой объем требуемой памяти. Если сцена подвергается видовому преобразованию и отсекается до фиксированного диапазона координат z значений, то можно использовать Z-буфер с фиксированной точностью. Информацию о глубине нужно обрабатывать с большей точностью, чем координатную информацию на плоскости (х, у); обычно бывает достаточно 20 бит. Буфер кадра размером 512х512х24 бит в комбинации с Z-буфером размером 512х512х20 бит требует почти 1.5 мегабайт памяти.
Другой недостаток алгоритма Z-буфера состоит в трудоемкости и высокой стоимости устранения лестничного эффекта, а также реализации эффектов прозрачности и просвечивания. Поскольку алгоритм заносит пиксели в буфер кадра в произвольном порядке, то нелегко получить информацию, необходимую для методов устранения лестничного эффекта, основывающихся на предварительной фильтрации. При реализации эффектов прозрачности и просвечивания, пиксели могут заноситься в буфер кадра в некорректном порядке, что ведет к локальным ошибкам. Более формальное описание алгоритма буфера таково:
1) Заполнить буфер кадра фоновым значением интенсивности или цвета.
2) Заполнить Z-буфер минимальным значением z.
3) Преобразовать каждый многоугольник в растровую форму в произвольном порядке.
4) Для каждого Пиксел(х,y) в многоугольнике вычислить его глубину z(x,y).
5) Сравнить глубину z(x,y) со значением Z-буфер(x,y), хранящимся в Z-буфере в этой же позиции.
6) Если z(x,y) > Z-буфер(x,y), то записать атрибут этого многоугольника (интенсивность, цвет и т. п.) в буфер кадра и заменить Z-буфер(х,у) на z(х,у). В противном случае никаких действий не производить.
 
 
3.6.  Алгоритм  Робертса
 
Алгоритм Робертса представляет первое известное решение задачи об удалении невидимых линий. Это математически точный метод, работающий в объектном пространстве и использующий аппарат матричного анализа. Поэтому алгоритм Робертса хорошо согласуется с любыми видовыми преобразованиями трехмерной компьютерной графики, в основе которых лежит матричный анализ. Алгоритм, прежде всего, удаляет из каждого тела те ребра или грани, которые экранируются самим телом. В нем требуется, чтобы все изображаемые тела или объекты были выпуклыми. Невыпуклые тела должны быть разбиты на выпуклые [1, 3, 4].
Каждое выпуклое тело с плоскими гранями представляется набором пересекающихся плоскостей. Уравнение произвольной плоскости в трехмерном пространстве имеет вид
 
Ax + By + Cz + D = 0                                                    (1)
 
В матричной форме уравнение (1) запишется как:
                        
или                                                   [x y z 1][P]T = 0,                                                             (3)
 
где   [P]T = [ABCD]  представляет собой матрицу - строку из коэффициентов плоскости.
Что представляют собой коэффициенты уравнения плоскости?
A, B, C - проекции нормали, восстановленной к плоскости, на главные оси координат X, Y, Z, а D - расстояние от начала координат до плоскости. Любое выпуклое твердое тело, ограниченное несколькими гранями может быть представлено в виде матрицы тела
 
 
где каждый столбец содержит коэффициенты одной плоскости.
Известно, что любая точка пространства в однородных координатах представляется следующим образом:
 
s = [x y z 1]                                                       (5)
 
 
 
Если точка  s  лежит на плоскости, то скалярное произведение матриц точки и плоскости равно нулю. Если же точка  s  не лежит на плоскости, то знак этого произведения показывает, по какую сторону от плоскости расположена эта точка.
Пусть дан единичный куб, в центре которого находится начало системы координат. Такие объекты принято называть "центрированными". Куб изображен на рисунке 2. Пронумеруем ограничивающие его плоскости: 1 - правая, 2 - левая, 3 - верхняя, 4 - нижняя, 5 -передняя, 6 - задняя. Считаем, что наблюдатель при этом находится на положительном конце оси  Z  и смотрит в начало координат.
 
  
Рисунок 2 - Единичный куб с центром в начале координат.
 
 
Составим матрицу этого тела, для чего нам необходимо записать полные уравнения всех шести ограничивающих куб плоскостей:
 
1. 1x1 + 0y1 + 0z1 - 0.5 = 0,      после нормировки на D:      2x1 + 0y1 + 0z1 - 1 = 0
 2. 1x2 + 0y2 + 0z2 + 0.5 = 0,     после нормировки на D:      2x2 + 0y2 + 0z2 + 1 = 0
3. 0x3 + 1y3 + 0z3 - 0.5 = 0,      после нормировки на D:      0x3 + 2y3 + 0z3 - 1 = 0
                         4. 0x4 + 1y4 + 0z4 + 0.5 = 0,     после нормировки на D:      0x4 + 2y4 + 0z4 + 1 = 0                    (6)
5. 0x5 + 0y5 + 1z5 - 0.5 = 0,      после нормировки на D:      0x5 + 0y5 + 2z5 - 2 = 0
 6. 0x6 + 0y6 + 1z6 + 0.5 = 0,     после нормировки на D:      0x6 + 0y6 + 2z6 + 1 = 0
 
На основании нормированных соотношений (6) матрица тела запишется:
 
 
Полученную матрицу тела проверяют на корректность. Для этого берут точку внутри тела и находят скалярные произведения матриц точки и тела. В соответствии с алгоритмом Робертса все произведения должны быть положительными. Пусть внутри тела выбрана точка s(0.25 0.25 0.25 1) или s(1 1 1 4). Тогда произведение матрицы-строки точки s[1 1 1 4] на матрицу тела (7) даст в результате также матрицу-строку с шестью элементами (по количеству плоскостей):
 
Из (8) видно, что результаты умножения для первого, третьего и пятого столбцов отрицательны. Следовательно, уравнения первой, третьей и пятой плоскостей составлены не корректно. Эти столбцы, в соответствии с алгоритмом Робертса, необходимо умножить на -1. После чего корректная матрица тела запишется:
 
В общем случае расположения и формы исходного трехмерного объекта не удается так просто, как это только что было сделано, построить матрицу тела. Рассмотрим несколько полезных методов, позволяющих справиться с этой проблемой. В первую очередь необходимо найти уравнения плоскостей, ограничивающих исходный объект или тело.
Первый способ. Общее уравнение плоскости содержит четыре коэффициента. Если его нормировать так, чтобы коэффициент D стал равен единице (Dн), тогда неизвестных коэффициентов останется только три и трех неколлинеарных точек достаточно для определения коэффициентов A, B, C. Подставив координаты трех неколлинеарных точек (x1, y1, z1), (x2, y2, z2), (x3, y3, z3), в нормированное уравнение плоскости, получим:
  
В матричной форме система уравнений (10) запишется:
 
или                                                                          [X][K] = [Dн]                                                                 (12)
 
в (12) – [X] - матрица известных координат трех, принадлежащих плоскости точек, [K] - матрица неизвестных коэффициентов плоскости.
Решение матричного уравнения (12) дает значения коэффициентов искомой плоскости
 
[K] = [X]-1[Dн]                                                           (13)
 
Второй способ используется, если известен вектор нормали к плоскости, т.е.
 
где  i, j, k - единичные векторы главных осей координат X, Y, Z соответственно. Тогда искомое уравнение плоскости запишется
 
Ax + By + Cz + D = 0                                                 (15)
 
Коэффициент D вычисляется подстановкой координат произвольной точки, лежащей на плоскости, например, точки  (x1, y1, z1)
 
D = -(Ax1 + By1 + Cz1)                                               (16)
 
 
 
3.7. Удаление  невидимых  ребер  и  граней трехмерных  объектов,
подвергнутых  различным  видовым  преобразованиям.
 
Видовые преобразования трехмерных объектов, такие как перенос, масштабирование, отображение, сдвиг, вращение, проектирование должны выполняться перед началом работы алгоритма удаления невидимых ребер и граней. Ортографическая проекция в этом случае должна выполняться последней.
Пусть [B] - матрица однородных координат вершин исходного трехмерного тела, [T] - матрица четвертого ранга некоторого видового преобразования, тогда координаты вершин преобразованного тела найдутся их матричного уравнения
[BT] = [B][T]                                                    (17)
 
При умножении матрицы вершин исходного объекта на корректную матрицу тела этого объекта в результате получим нулевую матрицу. Такой результат соответствует правилам скалярного умножения матрицы точки, лежащей на плоскости, на матрицу коэффициентов этой плоскости, т.е.
 
[B][VKT] = [0]                                                    (18)
 
Рассуждая аналогичным образом о произведении матрицы координат вершин преобразованного тела на корректную матрицу преобразованного тела, получаем в результате нулевую матрицу
 
[BT][VKTP] = [0]                                                (19)
 
Приравнивая левые части матричных уравнений (19) и (18), получим:
 
[BT][VKTP] = [B][VKT]                                      (20)
 
Заменяя в (20) [BT] на [B][T] из (17), получим:
 
[B][T][VKTP] = [B][VKT]                                      (21)
 
Сокращая (21) на [B] и решая полученное матричное уравнение относительно корректной матрицы преобразованного тела [VKTP], получим:
 
[VKTP] = [T]-1[VKT]                                           (22)
 
Таким образом, корректная матрица преобразованного тела [VKTP] равна корректной матрице исходного тела [VKT], умноженной слева на обратную матрицу видового преобразования [T]-1.
Тот факт, что плоскости имеют бесконечную протяженность и что скалярное произведение точки на корректную матрицу исходного или преобразованного тела отрицательно, если точка лежит вне тела, позволяет предложить метод, в котором эта матрица используется для определения граней, которые экранируются самим телом. Суть метода заключается в следующем.
Если зритель находится в бесконечности на положительной полуоси Z и смотрит на начало координат, то его взгляд направлен в сторону отрицательной полуоси Z. В однородных координатах вектор такого направления записывается в виде:
 
[E] = [0 0 -1 0]                                                 (23)
 
Этот вектор является образом точки, лежащей в бесконечности на отрицательной полуоси Z. Фактически вектор [E] представляет любую точку, лежащую на плоскости Z в минус бесконечности, то есть, любую точку типа (x, y, -∞).
Поэтому, если скалярное произведение точки [E] на столбец, соответствующий какой-нибудь плоскости в корректной матрице исходного или преобразованного тела отрицательно, то это означает, что точка [E] лежит по отрицательную сторону от этой плоскости. Следовательно, такие плоскости невидимы из любой точки наблюдения, лежащей в плоскости  Z = ∞,  а пробная точка на плоскости  Z = -∞  экранируется самим телом. Такие плоскости называются нелицевыми, а соответствующие им грани - задними. Таким образом, условие
 
[E] [VKT] < 0      или       [E] [VKTP] < 0                     (24)
 
является условием того, что данные плоскости тела нелицевые, а грани, образуемые пересечением таких плоскостей - задние.
Этот метод является простейшим алгоритмом удаления невидимых поверхностей для тел, представляющих собой одиночные выпуклые многогранники. Метод эквивалентен вычислению нормали к поверхности для каждой отдельной грани. Отрицательный знак нормали к поверхности показывает, что нормаль направлена в сторону от наблюдателя и, следовательно, данный многоугольник не виден с позиции наблюдателя.
Суммируя приведенные выше теоретические рассуждения, приведем порядок действий при удалении невидимых ребер и граней трехмерных объектов с использованием алгоритма Робертса.
1. Находим уравнения плоскостей, ограничивающих преобразуемое тело.
2. Из коэффициентов найденных плоскостей составляем матрицу тела [VT].
3. Находим корректную матрицу исходного тела [VKT].
4. Находим результирующую объемную матрицу видового преобразования Трез.объемн.. В выводе матрицы необходимо предусмотреть предстоящий в конце работы алгоритма вывод объемных изображений исходного и преобразованного объектов. В этом пункте при выводе результирующей матрицы видового преобразования не используем матрицу ортографической проекции Торт.
5. Находим обратную матрицу от результирующей объемной матрицы видового преобразования  [Трез.объемн.]-1.
6. Находим корректную матрицу преобразованного тела [VKTP].
7. Находим нелицевые грани преобразованного тела, используя точку [E]. Отрицательные числа в матрице-строке результата укажут номера нелицевых граней.
8. Преобразование и вывод на картинную плоскость (экран ПК) исходных и преобразованных объектов. Перед выполнением этого пункта результирующая матрица видовых преобразований, должна быть умножена на соответствующую матрицу ортографических проекций.
9. Невидимые ребра, которые образуются при пересечении невидимых граней на картинной плоскости не изображаются.
 
После первого этапа удаления нелицевых отрезков необходимо выяснить, существуют ли такие отрезки, которые экранируются другими телами в сцене. Для этого каждый оставшийся отрезок или ребро нужно сравнить с другими телами сцены. При этом использование приоритетной сортировки (z - сортировки) и простого минимаксного или габаритного с прямоугольной объемлющей оболочкой тестов позволяет удалить целые группы отрезков и тел.

4.  Рекомендации  по  выполнению  лабораторной  работы
 
Разработка  формы Form6 для данной лабораторной работы аналогична предыдущим работам, и состоит из следующих частей и этапов:
1-ая часть –  компоновка формы Form6;
2-ая часть – разработка файла реализации unit5.cpp:
- 1-й этап – подготовительный;
- 2-й этап – разработка управляющих функции;
- 3-й этап – разработка функций построения фигуры;
- 4-й этап – реализация вращения фигуры в горизонтальной и вертикальной плоскостях;
- 5-й этап – разработка функций алгоритма удаления невидимых граней.
 
Компоновку формы для данного проекта выполните самостоятельно, аналогично предыдущим лабораторным работам. На поле формы установите графическое окно, с использованием режима двойной буферизации и панель управления. На панели управления должны располагаться кнопки и движки, позволяющие запускать процесс вращения заданной фигуры в двух плоскостях, выполнять перенос и масштабирование, а также регулировать скорость вращения фигуры. Установите также флажки включения алгоритма удаления невидимых граней и заливки плоскостей фигуры различными цветами.
 
В процессе разработки файла реализации при выполнении его первого этапа необходимо описать и проинициализировать все используемые в программе переменные и функции. Главное отличие от предыдущих программ будет связано с тем, что здесь мы будем описывать фигуру не как совокупность вершин, а как совокупность полигонов, каждый из которых будет задавать конкретную плоскость (грань) заданной фигуры. Сколько плоскостей будет содержать фигура, столько полигонов необходимо будет создать. Для их описания используем методы объектного программирования. Создадим класс, например, "figura", и в состав его введем описание объектов с атрибутами задания цвета и масштаба для каждого полигона, с методами для вычисления координат вершин каждого полигона, в зависимости от координат центра фигуры и т.п.
Пример описания и использования классов, объектов и полигонов можно посмотреть в лабораторной работе №4.
 
Процесс разработки управляющих функций на втором этапе в основном аналогичен предыдущей лабораторной работе. Здесь также надо будет разработать функции GrafKonv() и ShowAll() с необходимыми отличиями.
 
Построение фигуры на третьем этапе необходимо осуществлять в цикле, при котором должны последовательно прорисовываться все полигональные объекты, с помощью которых сформирована наша фигура. Перед прорисовкой необходимо, с использованием алгоритма удаления, выявить те полигоны фигуры, которые при данном развороте её в пространстве являются невидимыми для наблюдателя, находящегося перед монитором.
 
Разработку функции алгоритма удаления невидимых граней выполните самостоятельно, с использованием лекционного материала, теоретических сведений данного пособия и электронных учебников.
 
 
5.  Контрольные  вопросы
 
1. С какой целью выполняется удаление невидимых ребер и граней в изображениях трехмерных объектов?
2. Перечислите существующие алгоритмы удаления невидимых ребер и граней и отличительные особенности каждого из них.
3. Опишите работу алгоритма плавающего горизонта.
4. Опишите работу алгоритма Робертса.
5. Опишите работу алгоритма Варнока.
6. Опишите работу алгоритма Вейлера-Азертона.
7. Опишите работу алгоритма Z – буфера.
8. Объясните назначение сортировок и их виды, применяемых для удаления невидимых ребер и граней.