Многогранники. Видимость рёбер. Точка на многограннике. Пересечение многогранника плоскостью, прямой. Взаимное пересечение многогранников.
Развёртки многогранников.*
План лекции
1. Проекции многогранников. Видимость проекций их ребер.
2. Точка на многограннике.
3. Пересечение многогранника проецирующей плоскостью.
4. Пересечение многогранника плоскостью общего положения.
5. Пересечение многогранника прямой линией.
6. Взаимное пересечение многогранников.
7. Развертки многогранников.
Проекции многогранников. Видимость проекций их ребер
Многогранником называется замкнутая пространственная фигура, ограниченная плоскими многоугольниками.Форму многогранников имеют многие детали сельскохозяйственных машин и инструменты.
Наибольший практический интерес представляют призмы, пирамиды и выпуклые однородные многогранники – тела Платона (тетраэдр, гекаэдр, октаэдр, додекаэдр, икосаэдр), а также и многие другие многогранники.
Кратко охарактеризуем геометрические свойства наиболее распространенных многогранников.
ПИРАМИДА – это многогранник, одна грань которого – многоугольник, а остальные грани – треугольники с общей вершиной. Пирамиду называют правильной, если основанием ее является правильный многоугольник и высота пирамиды (перпендикуляр, опущенный из вершины на основание) проходит через центр этого многоугольника.
Пирамида называется усеченной, если вершина её отсекается плоскостью, пересекающей все ребра, исходящие из этой вершины.
На эпюре пирамида задается проекциями ее основания и вершины, а усеченная пирамида проекциями обоих оснований (рис. 1– 3).
ПРИЗМОЙ называют многогранник, две грани которого (основания призмы) представляют собой равные многоугольники с взаимно- параллельными сторонами, все другие грани – параллелограммы(рис. 4).
Призму называют прямой, если ребра её перпендикулярны плоскости основания. Если основанием призмы является прямоугольник, призму называют параллепипедом(рис. 5).
Выбирая положение призмы или пирамиды для изображения, целесообразно располагать их основания параллельно плоскости проекций.
Для пирамиды достаточно двух проекций при условии, что на одной из них показана форма основания.
Рис. 1 Рис. 2
Рис. 3 Рис. 4
Рис. 5
Видимость ребер определяется по расположению конкурирующих точек, принадлежащих ребрам(рис. 6).
Чтобы определить видимость горизонтальной проекции ребра SA пирамиды SABC, нужно провести проецирующий луч S1. Точка 1, принадлежащая ребру SA, расположена выше, чем точка 2, принадлежащая ребру SC. Отсюда ясно, что горизонтальная проекция точки 1 будет видимой, а горизонтальная проекция точки 2 – невидимой. Следовательно, и горизонтальная проекция ребра SA будет видимой.
Чтобы определить видимость фронтальной проекции ребра SC, проведем проецирующий луч S2. Точка 3, расположенная на стороне АВ основания пирамиды SABC, находится к наблюдателю ближе, чем точка 4 на ребре SC. Отсюда ясно, что фронтальная проекция точки 3 будет видимой, а фронтальная проекция точки 4 – невидимой; Следовательно, фронтальная проекция ребра SC будет невидимой.
Рис. 6
Точка на многограннике
Если нужно на обеих проекциях многогранника построить точку, лежащую на одной из его граней, то следует «связать» точку с соответствующей гранью при помощи какой-либо прямой, находящейся на этой грани.
На рисунке 7 показано построение точки К на грани АSC пирамиды SABC.
Рис. 7
По данной горизонтальной проекции (К’) точки К необходимо построить ее фронтальную проекцию. Для этого через горизонтальную проекцию вершины S пирамиды и точку К’ проведена горизонтальная проекция прямой SM. Затем по горизонтальной проекции прямой SM построена её фронтальная проекция, на которой и определяется с помощью линии связи фронтальная проекция точки – К».
На рисунке 8 показано построение недостающей горизонтальной проекции точки М по известной её фронтальной проекции – М», причем эта проекция является видимой.
Рис. 8
Чтобы определить недостающую горизонтальную проекцию точки М, построена фронтальная проекция вспомогательной прямой – K′′N′′, проходящая через грань AGND и точку М.
Затем по фронтальной проекции прямой KN, c помощью линий связи найдена её горизонтальная проекция – K’N’ на которой и определилась горизонтальная проекция точки – М’.
Что такое видимые и невидимые ребра
Алгоритм Робертса представляет собой первое известное решение задачи об удалении невидимых линий. Это математически элегантный метод, работающий в объектном пространстве. Алгоритм прежде всего удаляет из каждого тела те ребра или грани, которые экранируются самим телом. Затем каждое из видимых ребер каждого тела сравнивается с каждым из оставшихся тел для определения того, какая его часть или части, если таковые есть, экранируются этими телами. Поэтому вычислительная трудоемкость алгоритма Робертса растет теоретически, как квадрат числа объектов. Это в сочетании с ростом интереса к растровым дисплеям, работающим в пространстве изображения, привело к снижению интереса к алгоритму Робертса. Однако математические методы, используемые в этом алгоритме, просты, мощны и точны. Кроме того, этот алгоритм можно использовать для иллюстрации некоторых важных концепций. Наконец, более поздние реализации алгоритма, использующие предварительную приоритетную сортировку вдоль оси z и простые габаритные или минимаксные тесты, демонстрируют почти линейную зависимость от числа объектов.
Работа Алгоритм Робертса проходит в два этапа:
1. Определение нелицевых граней для каждого тела отдельно.
2. Определение и удаление невидимых ребер.
5.3.1. Определение нелицевых граней
Пусть F — некоторая грань многогранника. Плоскость, несущая эту грань, разделяет пространство на два подпространства. Назовем положительным то из них, в которое смотрит внешняя нормаль к грани. Если точка наблюдения – в положительном подпространстве, то грань – лицевая, в противном случае – нелицевая. Если многогранник выпуклый, то удаление всех нелицевых граней полностью решает задачу визуализации с удалением невидимых граней.
В матричной форме этот результат выглядит так:
где [P] T = [a b c d] представляет собой плоскость. Поэтому любое выпуклое твердое тело можно выразить матрицей тела, состоящей из коэффициентов уравнений плоскостей, т. е.
| [ V ] = |  | , |
где каждый столбец содержит коэффициенты одной плоскости.
Напомним, что любая точка пространства представима в однородных координатах вектором [S] = [х у z 1]. Более того, если точка [S] лежит на плоскости, то [S]·[P] T = 0. Если же [S] не лежит на плоскости, то знак этого скалярного произведения показывает, по какую сторону от плоскости расположена точка. В алгоритме Робертса предполагается, что точки, лежащие внутри тела, дают отрицательное скалярное произведение, т. е. нормали направлены наружу. Чтобы проиллюстрировать эти идеи, рассмотрим следующий пример.
Рассмотрим единичный куб с центром в начале координат (рис.5.8 ).
Рис. 5.8. Куб с центром в начале координат
Шесть плоскостей, описывающих данный куб, таковы:
Более подробно уравнение правой плоскости можно записать как
Полная матрица тела такова:
| [ V ] = |  | = |  | . |
[ S ] = [1/4 1/4 1/4 1] = [1 1 1 4].
Скалярное произведение этого вектора на матрицу объема равно
| [ V ] = |  | , |
В приведенном примере корректность уравнений плоскостей была проверена экспериментально. Разумеется, это не всегда возможно. Существует несколько полезных методов для более общего случая. Хотя уравнение плоскости содержит четыре неизвестных коэффициента, его можно нормировать так, чтобы d = 1. Следовательно, трех неколлинеарных точек достаточно для определения этих коэффициентов. Подстановка координат трех неколлинеарных точек (x1, y1, z1), (x2, y2, z2), (х3, у3, z3) в нормированное уравнение (5.1. ) дает
В матричной форме это выглядит так:
Другой способ используется, если известен вектор нормали к плоскости, т. е.
где i, j, k – единичные векторы осей х, у, z соответственно. Тогда уравнение плоскости примет вид
Величина d вычисляется с помощью произвольной точки на плоскости. В частности, если компоненты этой точки на плоскости (х1, у1, z1), то
Перед началом работы алгоритма удаления невидимых линий или поверхностей для получения желаемого вида сцены часто применяется трехмерное видовое преобразование. Матрицы тел для объектов преобразованной сцены можно получить или преобразованием исходных матриц тел, или вычислением новых матриц тел, используя преобразованные вершины или точки.
Если [В] – матрица однородных координат, представляющая исходные вершины тела, а [T] – матрица размером 4 ´ 4 видового преобразования, то преобразованные вершины таковы:
где [BT] – преобразованная матрица вершин. Использование уравнения (5.2.) позволяет получить уравнения исходных плоскостей, ограничивающих тело:
где [V] – матрица тела, а [D] в правой части – нулевая матрица. Аналогично уравнения преобразованных плоскостей задаются следующим образом:
где [VT] – преобразованная матрица тела. Приравнивая левые части уравнения (5.6.) и (5.7.), получаем
Итак, преобразованная матрица тела получается умножением исходной матрицы тела слева на обратную матрицу видового преобразования.
Тот факт, что плоскости имеют бесконечную протяженность и что скалярное произведение точки (вектора точки) на матрицу тела положительно, если точка лежит вне этого тела, позволяет предложить метод, в котором матрица тела используется для определения граней, которые экранируются самим этим телом.
Положительное скалярное произведение дает только такая плоскость (столбец) в матрице тела, относительно которой точка лежит снаружи, т. е. в положительном подпространстве. Проиллюстрируем это на примере уже рассмотренного единичного куба (рис. 5.9.):
Рис. 5.9. Точка наблюдения вне тела
Отрицательное число в шестом столбце показывает, что грань с этим номером нелицевая. Положительное число в пятом столбце показывает, что грань лицевая. Нулевые результаты соответствуют плоскостям, параллельным направлению взгляда.
Положительный результат вектора E и вектора нормали можно интерпретировать как острый угол между этими векторами, отрицательный результат – как тупой угол. Если угол между векторами острый, то грань является лицевой; если угол тупой, то грань – нелицевая.
Этот метод является простейшим алгоритмом удаления невидимых поверхностей для тел, представляющих собой одиночные выпуклые многогранники. Он также используется для удаления нелицевых или задних граней из сцены перед применением одного из алгоритмов удаления невидимых линий, которые обсуждаются ниже. Этот способ часто называют отбрасыванием задних плоскостей. Для выпуклых многогранников число граней при этом сокращается примерно наполовину. Метод эквивалентен вычислению нормали к поверхности для каждого отдельного многоугольника.
Данный метод определения нелицевых граней в результате формирует аксонометрическую проекцию на некую плоскость, расположенную бесконечно далеко от любой точки трехмерного пространства. Видовые преобразования, включая перспективное, производятся до определения нелицевых плоскостей. Когда видовое преобразование включает в себя перспективу, то нужно использовать полное перспективное преобразование одного трехмерного пространства в другое, а не перспективное проецирование на некоторую двумерную плоскость. Полное перспективное преобразование приводит к искажению трехмерного тела, которое затем проецируется на некую плоскость в бесконечности, когда нелицевые плоскости уже определены. Этот результат эквивалентен перспективному проецированию из некоторого центра на конечную плоскость проекции.
В литературе описаны и другие способы удаления невидимых граней. Так, в источнике [4] все нормали к граням тела направляются внутрь тела и используется вектор, направленный от наблюдателя к проекционной плоскости.
5.3.2. Удаление невидимых ребер
После первого этапа удаления нелицевых отрезков необходимо выяснить, существуют ли такие отрезки, которые экранируются другими телами в картинке или в сцене. Для этого каждый оставшийся отрезок или ребро нужно сравнить с другими телами сцены или картинки.
Возможны следующие случаи:
¨ Грань ребра не закрывает. Ребро остается в списке ребер.
¨ Грань полностью закрывает ребро. Ребро удаляется из списка рассматриваемых ребер.
¨ Грань частично закрывает ребро. В этом случае ребро разбивается на несколько частей, видимыми из которых являются не более двух. Само ребро удаляется из списка рассматриваемых ребер, но в список проверяемых ребер добавляются те его части, которые данной гранью не закрываются.
Для оптимизации используется приоритетная сортировка (z-сортировка), а также, сравнения с прямоугольными объемлющими оболочками тел. Такой подход позволяет удалить целые группы или кластеры отрезков и тел. Например, если все тела в сцене упорядочены в некотором приоритетном списке, использующем значения z ближайших вершин для представления расстояния до наблюдателя, то никакое тело из этого списка, у которого ближайшая вершина находится дальше от наблюдателя, чем самая удаленная из концевых точек ребра, не может закрывать это ребро. Более того, ни одно из оставшихся тел, прямоугольная оболочка которого расположена полностью справа, слева, над или под ребром, не может экранировать это ребро. Использование этих приемов значительно сокращает число тел, с которыми нужно сравнивать каждый отрезок или ребро. Рис. 5.10 иллюстрирует работу алгоритма.
Рис. 5.10. Результат работы алгоритма Робертса
Управление видимостью ребер
Ребра не скрыты, а скорее сделаны «невидимыми». Невидимые ребра ведут себя иначе, чем скрытые грани и вершины. С другой стороны, скрытые грани и вершины «защищают» себя от дальнейшей модификации; скрытые ребра этого не делают. Даже не видя ребер, их можно выбирать, трансформировать, вытягивать, делить, поворачивать, разрушать и удалять. Хотя модификация невидимых ребер может оказаться удобной, она также и опасна, поскольку существует вероятность сделать гораздо больше, чем это необходимо.
Видимость ребер влияет на несколько вещей в модели. При моделировании видимые ребра определяют границу для выборки многоугольником. При визуализации визуализируются только видимые ребра, когда граням, которым они принадлежат, задается материал в виде проволочного каркаса (см. рис. 13.35). Скрытые ребра влияют также на ориентацию отображенных материалов грани. Однако в большинстве случаев единственными отличиями между видимыми и невидимыми ребрами являются организационная и визуальная ясность. Невидимые ребра часто делают модель более ясной и понятной, поскольку отображаются только рельефные линии. Кроме того, невидимые ребра увеличивают скорость перерисовки за счет уменьшения количества линий.
Невидимые ребра можно отображать при помощи опции Edges Only (только ребра), которая находится ниже Display Optimization (оптимизация отображения) в панели Display (см. рис. 13.36). Если планируется работа с ребрами, перед выполнением основного редактирования необходимо войти в панель Display и выключить Edges Only. Опция Edges Only на визуализацию влияния не оказывает.
СОВЕТ Если вы не хотите покидать панель Edit, чтобы выключить опцию Edges Only, выполните Select All на ребрах и AutoEdge при нулевом угле для отображения каждого ребра. Позже AutoEdge можно применить для того, чтобы сделать ребра невидимыми.
Алгоритм определения видимости ребер произвольного многогранника.
Дата добавления: 2013-12-23 ; просмотров: 3091 ; Нарушение авторских прав
Алгоритм Аппеля.
Определение нелицевых граней.
Рассмотрим многогранник и решим задачу видимости аналогично задаче освещенности, рассмотренной ранее.
Если вектор нормали какой-то грани Ни составляет с Л, задающим направление проецирования тупой угол, то эта грань видна и называется лицевой.
При параллельном проецировании скалярное произведение (n,l)
Для произвольного многогранника следует рассмотреть задачи удаления невидимых ребер и невидимых линий отдельно.
Удаление невидимых рёбер.
2) Проверяется каждое из оставшихся рёбер со всеми гранями многогранника на закрывание. Возможны 3 случая.
Можно сократить количество проверок если картинную плоскость разбить на клетки и для каждой составить список тех граней проекции, которые имеют непустое пересечение с данной клеткой. Для проверки произвольного ребра сначала находим клетки на проекции этого ребра, далее рассматриваем только те грани, которые содержатся в списках данных клеток.
Применим для произвольного многогранника, основан на понятии количественной невидимости точки количество лицевых граней закрывающих её.
Каждая точка видима только тогда, когда её количественная невидимость =0.
Количественная невидимость точек ребра изменяется, на 1 при прохождении ребра позади контурной линии.
А) Строится контурная линия
Б) Берётся вершина и определяется её количественная невидимость
В) Просматривается изменение количественной невидимости вдоль каждого из рёбер выходящего из этой точки. Рёбра проверяются на прохождение контурной линии и в соответствующих точках количественная невидимость изменяется. Те рёбра у которых кн=0 изображаются.
Г) Выполняется переход к следующей вершине и возврат к Б
Д) если ребро выходит из вершины, принадлежащей контурной линии, проверяется, не закрывается ли это ребро одной из граней (Дд»)
Так как у реальных многогранников количество ребер в контурной линии намного меньше общего числа ребер то алгоритм Аппеля более эффективен, чем алгоритм Робертса.
Не нашли то, что искали? Google вам в помощь!
5. Удаление невидимых линий и поверхностей
5.1. Введение
Задача удаления невидимых линий и поверхностей является одной из наиболее сложных в машинной графике. Алгоритмы удаления невидимых линий и поверхностей служат для определения линий ребер, поверхностей или объемов, которые видимы или невидимы для наблюдателя, находящегося в заданной точке пространства. Необходимость удаления невидимых линий, ребер, поверхностей или объемов проиллюстрирована рис. 5.1.
Рис.5.1. Необходимость удаления невидимых линий
Сложность задачи удаления невидимых линий и поверхностей привела к появлению большого числа различных способов ее решения. Многие из них ориентированы на специализированные приложения. Наилучшего решения обшей задачи удаления невидимых линий и поверхностей не существует. Для моделирования процессов в реальном времени, например для авиатренажеров, требуются быстрые алгоритмы, которые могут порождать результаты с частотой видеогенерации 30 кадр/с. Для машинной мультипликации, например, требуются алгоритмы, которые могут генерировать сложные реалистические изображения, в которых представлены тени, прозрачность и фактура, учитывающие эффекты отражения и преломления цвета в мельчайших оттенках. Подобные алгоритмы работают медленно, и зачастую на вычисления требуется несколько минут или даже часов. Строго говоря, учет эффектов прозрачности, фактуры, отражения и т. п. не входит в задачу удаления невидимых линий или поверхностей. Естественнее считать их частью процесса визуализации изображения. Однако многие из этих эффектов встроены в алгоритмы удаления невидимых поверхностей. Существует тесная взаимосвязь между скоростью работы алгоритма и детальностью его результата. Ни один из алгоритмов не может достигнуть хороших оценок для этих двух показателей одновременно. По мере создания все более быстрых алгоритмов можно строить все более детальные изображения. Реальные задачи, однако, всегда будут требовать учета еще большего количества деталей.
Все алгоритмы удаления невидимых линий (поверхностей) включают в себя сортировку. Порядок, в котором производится сортировка координат объектов, вообще говоря, не влияет на эффективность этих алгоритмов. Главная сортировка ведется по геометрическому расстоянию от тела, поверхности, ребра или точки до точки наблюдения. Основная идея, положенная в основу сортировки по расстоянию, заключается в том, что чем дальше расположен объект от точки наблюдения, тем больше вероятность, что он будет полностью или частично заслонен одним из объектов, более близких к точке наблюдения. После определения расстояний или приоритетов по глубине остается провести сортировку по горизонтали и по вертикали, чтобы выяснить, будет ли рассматриваемый объект действительно заслонен объектом, расположенным ближе к точке наблюдения. Эффективность любого алгоритма удаления невидимых линий или поверхностей в большой мере зависит от эффективности процесса сортировки. Для повышения эффективности сортировки используется также когерентность сцены, т. е. тенденция неизменяемости характеристик сцены в малом.
Алгоритмы удаления невидимых линий или поверхностей можно классифицировать по способу выбора системы координат или пространства, в котором они работают [4]. Выделяют три класса алгоритмов удаления невидимых линий или поверхностей:
¨ Алгоритмы, работающие в объектном пространстве.
¨ Алгоритмы, работающие в пространстве изображения (экрана).
¨ Алгоритмы, формирующие список приоритетов.
Алгоритмы, работающие в объектном пространстве, имеют дело с физической системой координат, в которой описаны эти объекты. При этом получаются весьма точные результаты, ограниченные лишь точностью вычислений. Полученные изображения можно свободно увеличивать во много раз. Алгоритмы, работающие в объектном пространстве, особенно полезны в тех приложениях, где необходима высокая точность.
Алгоритмы же, работающие в пространстве изображения, имеют дело с системой координат того экрана, на котором объекты визуализируются. При этом точность вычислений ограничена разрешающей способностью экрана. Обычно разрешение экрана бывает довольно низким, типичный пример: 512 ´ 512 точек. Результаты, полученные в пространстве изображения, а затем увеличенные во много раз, не будут соответствовать исходной сцене. Например, могут не совпасть концы отрезков. Алгоритмы, формирующие список приоритетов, работают попеременно в обеих упомянутых системах координат.
Объем вычислений для любого алгоритма, работающего в объектном пространстве и сравнивающего каждый объект сцены со всеми остальными объектами этой сцены, растет теоретически, как квадрат числа объектов (n 2 ). Аналогично, объем вычислений любого алгоритма, работающего в пространстве изображения и сравнивающего каждый объект сцены с позициями всех пикселов в системе координат экрана, растет теоретически, как nN. Здесь n обозначает количество объектов (тел, плоскостей или ребер) в сцене, а N — число пикселов. Теоретически трудоемкость алгоритмов, работающих в объектном пространстве, меньше трудоемкости алгоритмов, работающих в пространстве изображения, при n
