Лекции по "Компьютерной графике"

Алгоритм  разбиения произвольного  полигона на выпуклые

 

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

1. Полигон представляется, как набор контуров. Каждый контур – циклический список ребер. Может быть много внутренних и внешних контуров, в конце должны получиться только контуры выпуклых полигонов.
2. В двойном цикле обходятся все вершины полигона и находится пара вершин, наиболее подходящая для создания хорды. Хорда не должна пересекаться или совпадать ни с одним ребром из существующих контуров и убирать максимальное число вогнутых углов. Если две хорды убирают одинаковое число вогнутых углов, то предпочтение имеет смысл отдать наиболее короткой.
3. Если не найдено ни одного вогнутого угла – завершаем работу.
4. Создаем два противоположно направленных ребра и добавляем их к контурам. Нужно отметить, что если мы соединяем точки одного контура, то он разделяется на два контура, а если точки с разных контуров – два контура сливаются в один.
5. Продолжаем искать хорды.

 

В худшем случае алгоритм требует времени  O(N³), где N – количество ребер в полигоне, но если алгоритм немного модифицировать (например, обходить не все вершины, а только вогнутые) то он становится достаточно эффективным.  
 
 
 
 
 
 
 
 

Плоскость

 

Общее уравнение  плоскости a*Px+b*Py+c*Pz+d=0 или или . Параметрически задается в виде  , где L1,L2 – два непараллельных вектора в плоскости.

Расстояния  от точки до плоскости  .

Прямая 

Уравнение прямой, проходящей, через две точки.

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

Получить  направление и точку для параметрического задания можно следующим образом  (должен лежать в обеих плоскостях, а значит – быть перпендикулярным обеим нормалям). А точку получить из пересечения трех плоскостей, двух исходных и третьей – с нормалью L и проходящей через начало координат. Получаем систему

, ее решением будет  .

В конце  имеет смысл нормализовать вектор L. 

Расстояния  от точки до прямой . 

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

Две наиболее близкие точки прямых, проецируются в ту же точку, что и точка пересечения проекций прямых на плоскость с нормалью N. Поэтому можно воспользоваться формулами пересечения прямых для плоского случая. При этом плоскость задана базисом (L2,M) M=L2xN.

,  

Пересечение прямой с плоскостью . , . 

Сфера 

Общее уравнение  , или

Практически все формулы остаются как у  окружности.

Полигон

 

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

,

Конечно затем нужно нормализовать N.

Более простая формула Ньэла  .

Все алгоритмы  для 2D случая можно применять и в 3D, это можно делать тремя способами:

1. Совместить плоскость полигона с плоскостью OXY и далее работать как в 2D случае.
2. Работать с проекциями полигона (правда, в проекциях нельзя правильно посчитать площадь) на одну из ортогональных плоскостей OXY, OXZ, OYZ. Плоскость выбирается в зависимости от нормали (например, если максимальным является модуль компоненты z выбирается плоскость OXY).
3. Работать в 3D пространстве с некоторыми модификациями формул. В основном это касается pdp, оно заменяется на смешанное произведение .

 
 

Отсечение отрезка и полигона плоскостью 

В 3D отсечение обычно выполняют по алгоритму по Кируса-Бэка, только расстояния от вершин отрезков до прямой заменяются на расстояния до плоскости. В остальном, все происходит тем же образом, что и на плоскости. 

Полиэдр (многогранник) 

Обычно под словом полиэдр (polyhedron) понимают выпуклые многогранники. Многогранник состоит из вершин, ребер и граней. Самый простой полиэдр – тетраэдр. Выпуклый – это значит, что все точки полиэдра находятся с одной стороны от плоскостей, образующих его грани (обычно с отрицательной стороны, так, что нормали плоскостей смотрят наружу). Наиболее часто полиэдры задаются просто набором ограничивающих плоскостей. Но полиэдр можно задать и набором полигонов – граней полиэдра, но это избыточное задание. Если полиэдр задан набором плоскостей, то получить его грани можно отсечением. Обычно создается начальный достаточно большой полигон в плоскости, для которой требуется получить грань, а затем отсекается всеми остальными плоскостями полиэдра. Можно поступить иначе – найти все прямые, по которым текущая плоскость пересекается с остальными, а затем отсечь их по оставшимся плоскостям, т.о. получатся ребра грани останется только объединить их в полигон (здесь правда могут возникнуть сложности с близкими точками).  

Положение точки относительно полиэдра 

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

Объем полиэдра

Объем тетраэдра 

Объем полиэдра – сумма объемов тетраэдров, построенных на начале координат  и треугольниках на гранях полиэдра.  
 
 
 

Булевы  операции с полиэдрами 

Это операции над множествами точек, внутри полиэдров. Операция «И» (получение пересечения (общей части) двух полиэдров), «ИЛИ» (объединение двух полиэдров), «НЕ-И» (вычитание одного полиэдра из другого). Они используются при работе с конструктивной геометрией (Constructive solid geometry). 

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

В результате вычитания одного полиэдра h1 из другого h2 («НЕ-И») получается набор полиэдров. Обычно поступают следующим образом, находят грань h1, которая находится внутри h2 (отсекают грань h1 плоскостями полиэдра h2) и разделяют h1 плоскостью этой грани, полиэдр с положительной стороны записывают в выходной набор, а с оставшуюся часть продолжают делить остальными плоскостями. В случае, если нет ни одной грани h1 внутри h2, полиэдры либо не пересекаются (операция «И» дает пустой полиэдр), тогда результатом является h1, либо h2 целиком находится внутри h2, тогда результатом является пустой набор полиэдров. 

Объединение двух полиэдров («ИЛИ») это один из них  и результат вычитания его  из второго. В особых случаях, когда  один полиэдр лежит внутри другого (все вершины одного внутри или  на границе другого) имеет смысл просто оставить больший полиэдр. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Лекция 9-10-11-12 

Удаление  невидимых линий  и поверхностей 

Задача состоит в том, чтобы  определить, какие части объектов, спроектированных на картинную плоскость (экран), будут видны, а какие –  заслонены другими объектами. Методы различаются по следующим параметрам:

• Способу представления объектов (Brep, CSG)
• Способу визуализации сцены (каркасное или сплошное)
• Пространству, в котором проводится анализ видимости (объектное или картинная плоскость)
• Виду получаемого результата (непрерывный (участки ребер) или дискретный (пиксели))

 

Самый простой непрерывный метод удаления невидимых линий это перебор  ребер всех объектов и сравнение  их со всеми остальными объектами, такой  алгоритм требует времени O(N²). Дискретные методы требуют времени O(CN), С – кол-во пикселей на экране (300 000).

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

• Когерентность в картинной плоскости, если данный пиксель соответствует определенной грани, то и соседние пиксели скорее всего соответствуют этой грани.
• Когерентность в объектном пространстве, если данный объект виден (невиден), то и соседние, скорее всего, видны (невидны).
• Когерентность во времени, если данный объект виден (невиден) на текущем кадре, то и на следующем кадре он, скорее всего, будет виден (невиден).

 

Алгоритм  плавающего горизонта

Этот  алгоритм применяют для удаления невидимых линий в параллельных проекциях графика функции двух переменных. Функция задана в виде Z=F(X,Y). Это может быть как аналитически заданная функция, так и любая другая (например, задана карта высот для некоторых точек, а промежуточные значения – получаются линейной интерполяцией).

Самый простой алгоритм рисования графика  – выбрать некоторый шаг сетки  вдоль осей X и Y, рассчитать точки для узлов такой сетки, и вывести их на экран. При этом, чтобы не было разрывов, можно выводить не точки, а отрезки между соседними узлами сетки. Можно заметить, что все отрезки в одном ряде узлов сетки вдоль оси OX будут лежать в одной вертикальной плоскости. Плоскости всех таких рядов будут параллельны, а значит, отрезок из более дальней от наблюдателя плоскости никогда не загородит отрезок из более близкой.

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

Алгоритм  работает в картинной плоскости  и является дискретным.

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

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

Void PP(x,y) { if (y<MinHor[x]) MinHor[x]=y; else

if (y>MaxHor[x]) MaxHor [x]=y; else return; ... }