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

 
 
 
 
 
 
 

Курс     Крен     Тангаж 

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

Таким образом, если предположить, что ось  Z камеры (направление зрения) не вертикальна, то можно найти ось X=Norm(Z´Up), где Up(0,0,1) вертикальный вектор (X получится перпендикулярен вертикальному вектору Up, а значит горизонтален). Наконец ось Y=X´Z (вверх). Следите за тем, чтобы система оставалась левой.

Чтобы преобразовать точки из мировой системы в экранные необходимо сначала применить перенос [T(-C)],  а затем повернуть на транспонированную матрицу ориентации камеры [Rс]^T.

Таким образом, для того, чтобы перевести  точку из модельных координат  в экранные необходимо произвести следующее  преобразование [Rm][T(M)][T(-C)] [Rс]^T. После таких преобразований ось Z будет направлена вдоль направления зрения и можно делать проектирование. 
 
 
 
 
 

Лекция 6-7-8 

Элементы  вычислительной геометрии  на плоскости. 

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

Прямая  на плоскости

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

Параметрическое уравнение  , где А – произвольная точка на прямой, L – направляющий вектор. Для отрезка AB, L=(B-A) 0<=k<=1. Для луча А –начало луча, k>=0.

Общее уравнение прямой a*Px+b*Py+d=0 или или . , - расстояние до начала координат. Здесь обозначение - вектор, перпендикулярный данному. Обычно вектор нормали нормализуют, но это не обязательно.

Расстояния  от точки до прямой , может быть как положительным, так и отрицательным в зависимости от того, с какой стороны от прямой лежит точка. Если вектор N не нормализован, нужно разделить на |N|.

Пересечение двух прямых и требует решения системы линейных уравнений , , откуда ,

Операция  , называется perp-dot-product (т.е. скалярное произведение (dot-product) с перпендикулятным вектором). Кстати, векторное произведение называется cross-product. Величина равна , в отличие от скалярного произведения .

Если  нужно найти пересечение двух отрезков, то после нахождения k₁ и k₂ нужно проверить их попадание в интервал [0,1]. 
 
 
 
 
 
 

Окружность 

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

Параметрическое , 0<=a<2p

Проверка  попадания точки в окружность

Проверка  пересечения двух окружностей  , здесь может быть случай, когда одна окружность лежит внутри другой, он отсеивается проверкой , если считать, что R₁< R₂.

Пересечение окружности с прямой . , отсюда квадратное уравнение

Если  нужно определить сам факт пересечение  с прямой, то можно просто рассчитать расстояние от центра окружности до прямой и его модуль должен быть меньше радиуса  .  

Полигон на плоскости 

Состоит из набора вершин Сi соединенных отрезками. Отрезки объединены в замкнутые непересекающиеся контура. Это выполняется при двух условиях: каждой вершине соответствуют ровно два отрезка, и никакая пара отрезков не пересекается. Отрезки считаются направленными, их направление выбирают таким образом, что внутренняя часть полигона всегда лежит с одной стороны от отрезков (обычно с отрицательной). Так как полигон может быть как одноконтурным, так и многоконтурным (один внешний контур и несколько внутренних), то направление отрезков во внутренних контурах получается противоположным направлению во внешнем контуре. Определить, с какой стороны от контура лежит полигон можно, посчитав сумму углов между соседними ребрами , где , размер угол можно получить из косинуса, а знак взять из синуса. Если S>0 полигон слева, иначе – справа.

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

Определение положения точки  относительно полигона. 

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

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

Вычисление  площади полигона.

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

Площадь полигона (внутри одного контура) это  сумма площадей всех треугольников  образованных всеми ребрами полигона и началом координат 

Если  есть внутренние контуры, то их площадь  нужно прибавить к площади  внешнего контура.  

Построение  выпуклой оболочки.

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

1. Выбираем самую левую точку в наборе, она, очевидно, будет принадлежать выпуклой оболочке. Обозначим ее С₀ , в начале она будет текущей точкой С_i.
2. Берем первую точку набора и делаем ее временно следующей точкой  оболочки С_i+1 .
3. Проверяем для остальных точек С_k набора условие , если оно не выполняется, то заменяем следующую точку оболочки С_i+1 на С_k и проверяем дальше.
4. Если все условия выполнены, значит, найдена корректная точка оболочки. Если это точка С₀ , завершаем работу, иначе делаем найденную точку текущей и ищем следующую.

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

 

По прямоугольнику (xmin,ymin,xmax,ymax).

Самое простое – последовательное отсечение  по всем сторонам прямоугольника. Сначала  – проверка, пересекает или нет, потом деление, в конце – замена координат одной из вершин отрезка на новые.

Уравнение прямой, проходящей, через две точки. , тогда, координата пересечения с вертикальной границей окна:

y=y1+(y2-y1)*(xmin-x1)/(x2-x1). 

Алгоритм  половинного деления 

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

Алгоритм  Сазерленда-Коэна

 

Для ускорения  отсечение предлагается ввести коды для точек отрезка (YmaxYminXmaxXmin). Затем, если логическое «И» над кодами отрезка не равно нулю, то отрезок полностью невидим. Если оба кода (логическое «ИЛИ») равны 0 то отрезок полностью внутри окна, иначе – нужно отсекать по тем сторонам, для которых биты логического «ИЛИ» кодов единичные. При получении очередной точки для нее считается код и история повторяется. 

Алгоритм  Кируса-Бэка 

Наиболее распространенный алгоритм, подходит для выпуклого  окна произвольной конфигурации. Отрезок отсекают последовательно по всем сторонам окна. Для точек отрезка находят расстояние до прямой, если оба положительные, то отрезок полностью невидим, если оба отрицательные, то он не пересекается с этой прямой, иначе – нужно найти точку пересечения, коэффициент k=d1/(d1-d2). P=A+k*(B-A).

Коэффициент k получается из подобия треугольников. , , ,

Невыпуклые  окна разбивают на выпуклые и производят отсечение по ним.  
 
 

Но можно  и не вычислять точки пересечения  при каждом пересечении. Достаточно только вычислить значение параметра, в котором происходит пересечение (k) и укорачивать интервал, который соответствует части отрезка, находящейся внутри окна. В начале этот интервал k1=0, k2=1, затем при пересечении в точке k, модифицируется коэффициент, соответствующий той точке, которая лежит вне окна (di>0) либо k1=max(k1,k), либо k2=min(k2,k). Если после пересечения окажется, что k1>k2, значит, отрезок находится полностью вне окна. После того, как обработаны все границы окна – следует рассчитать точки для k1,k2. Экономим на расчете точек, теряем на лишних расчетах коэффициентов пересечения.

Отсечение полигона выпуклым окном 

 

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

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

Алгоритм  Вейлера-Азертона

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

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