Пересечение луча с многоугольником. В данном случае задача разбивается на две

1. нахождение пересечения луча с плоскостью, в которой лежит многоугольник.

2. Проверка принадлежности точки пересечения многоугольнику.

1)Пусть плоскость задана общим уравнением

Ax+By+Cz+D=0

Где N=(A, B ,C)-нормальный вектор плоскости.

Заменяя в уравнении плоскости величины x,y и z их выражениями (*),

Получаем линейное уравнение относительно t :

Разрешая которое, находим, что

Если a=Al+Bm+Cn обращается в нуль, a=Al+Bm+Cn=0, то луч параллелен плоскости, и, следовательно, не пересекает ее.

В случае t*<0 луч не пересекает плоскости.

Если t*>0 то координаты точки пересечения вычисляются по формулам

2) Решение основано на нахождении пересечения с треугольником. Если у многоугольника n вершин (n>3), то он будет представляться как набор из n-2 треугольников. N — вектор нормали к плоскости, в которой лежит рассматриваемый многоугольник. Точка Р задается как

(4)

Точка Р будет внутри треугольника

если а>=0, b>=0, и a + b<= 1

В равенство (4) состоит из 3 равенств:

(5)

Решение существует и единственно. Чтобы упростить данную систему, можно спроектировать многоугольник на одну из координатных плоскостей.

В качестве направления проектирования рекомендуется брать ту ось, которой соответствует наибольшая координата у нормали.

Пусть

Пусть (u ,v) координаты вектора в плоскости, на которую был спроектирован многоугольник. Тогда векторы будут иметь следующие координаты:

Система (5) упроститься до системы:

Решением являются :

2*) Выпуклый n-угольник однозначно задается набором своих вершин

Будем считать, что вершины многоугольника занумерованы так, что соседние по номеру вершины примыкают к одной стороне. Обозначим через (x*,y*,z*) точку пересечения заданного луча с плоскостью Ax+By+Cz+D=0, в которой лежит рассматриваемый многоугольник.

Вследствие того, что нормальный вектор N=(A, B ,C) плоскости, несущей заданный многоугольник, отличен от нуля, этот n-угольник можно взаимно однозначно спроектировать на n-угольник, лежащий в одной из координатных плоскостей. В качестве направления проектирования рекомендуется брать ту ось, которой соответствует наибольшая координата у нормали.

Предположим для определенности, что C =Max(A, B,C).

Тогда в качестве такой плоскости можно взять координатную плоскость xy, а в качестве направления проектирования – ось аппликат (ось Z).

Легко видеть, что координаты вершин n-угольника, получающегося в результате такого проектирования, будут иметь вид

Координаты точки, получающейся в результате проектирования на плоскость xy точки (x* ,y* ,z*) будут соответственно (x*, y*).

Ясно, что если точка (x*, y*) лежит вне (внутри) n-угольника, получившегося на плоскости xy ,то исходная точка (x* ,y* ,z*) будет внешней (внутренней ) по отношению к исходному n-угольнику.

Для определения положения точки (x*, y*) относительно выпуклого n-угольника, лежащего на плоскости xy, можно поступить, например, следующим образом.

Передвинем n-угольник

в плоскости xy так, чтобы точка (x*, y*) попала в начало координат.

В новой координатной системе абсциссы и ординаты вершин n-угольника будут соответственно

Теперь остается выяснить, будет (или не будет) точка (0,0), в которую преобразуется точка (x*, y*), внутренней точкой n-угольника с вершинами

Возможны два случая.

I Абсциссы всех вершин n-угольника – одного знака.

Это означает, что рассматриваемая точка лежит вне n-угольника.

II Есть два ребра n-угольника с вершинами

соответственно ( i < j), такие, что

Если

то интересующая нас точка лежит внутри n-угольника.

Это означает, что точка (x* , y* ,z*) лежит внутри исходного n-угольника.

Если же последнее произведение положительно, то точка (x* , y* ,z*) лежит вне исходного n-угольника.

13. Алгоритм для определения точек пересечения луча со сферой.

14. Алгоритм для определения точек пересечения луча с произвольным параллелепипедом.

Пересечение луча с прямоугольным параллелепипедом.

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

Например, вершинами (x_, y_, z_), (x₊, y₊, z₊).

Рассмотрим луч, исходящий из точки (x₀, y₀, z₀) в направлении вектора

(l, m, n), где l² + m² + n² =1, и опишем алгоритм, посредством которого можно определить, пересекает ли этот луч заданный прямоугольный параллелепипед или нет.

Возьмем пару плоскостей, параллельных плоскости yz: x = x_ и x = x₊

При l=0 заданный луч параллелен этим плоскостям и, если x₀ < x₊ или x₀ > x₊, то он не пересекает рассматриваемый прямоугольный параллелепипед. Если же l не равно 0, то вычисляем отношения

t_1x = (x_ - x₀)/l, t_2x = (x₊ - x₀)/l.

Можно считать, что найденные величины связаны неравенством t_1x < t_2x.

Пусть tn = t_1x , tf = t_2x

Считая, что m0, и рассматривая вторую пару плоскостей, несущих грани заданного параллелепипеда, y = y_ и y = y₊, находим величины

t_1y = (y_ - y₀)/m, t_2y = (y₊ - y₀)/m.

Если t_1y > tn, тогда пусть tn = t_1y .

Если t_2y < tf, тогда пусть tf = t_2y.

При tn > tf или при tf < 0 заданный луч проходит мимо прямоугольного параллелепипеда.

Считая n0, рассматриваем последнюю пару плоскостей z = z_ и z = z₊ , находим величины t_1z = (z_ - z₀)/n, t_2z = (z₊ - z₀)/n и повторяем предыдущие сравнения.

Если в итоге всех проведенных операций мы получим, что 0 < tn < tf или

0 < tf, то заданный луч непременно пересечет исходный параллелепипед со сторонами, параллельными координатным осям.

Если луч протыкает прямоугольный параллелепипед (т.е. начальная точка лежит вне параллелепипеда), то расстояние от начала луча до точки его входа в параллелепипед равно tn, а до точки выхода луча из параллелепипеда tf.

15. Проективные преобразования.

Параллельное проектирование, при котором картинная плоскость совпадает с координатной плоскостью z==const описывается матрицей

[P]=

Метод параллельных проекций отличается от метода центральных проекций только тем, что проектирующие прямые не проходят через фиксированную точку, а параллельны фиксированному направлению (рисунок 2). Изображение в параллельной проекции напоминает предмет, рассматриваемый издалека: при неограниченном удалении глаза от оригинала лучи зрения становятся похожими на параллельные. Метод параллельных проекций используется в школе, так как он проще. Элементы оригинала обозначаются буквами со штрихом, а соответствующие элементы изображения - теми же буквами без штриха.

Основные свойства параллельных проекций

Свойство 1: Изображение прямой линии есть прямая или точка.

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

2)Если же прямая a' проектирующая, то все ее точки имеют одно и то же изображение, то есть прямая изображается точкой.

Свойство 2: Параллельные прямые изображаются параллельными прямыми или отдельными точками.

Свойство 3: Отношение, в котором любая точка отрезка делит этот отрезок, в изображении и в оригинале одинаково, в частности середина отрезка изображается серединой.

Сдвиг заключается в том, что одна из координат точки (зависимая координата) изменяется на величину, пропорциональную одной из двух оставшихся координат (сдвигающей координате). Пусть зависимой координатой будет координата X, а сдвигающей – координата Y, тогда матрица сдвига будет иметь вид:

где F – коэффициент сдвига. Проекцию точек объекта на плоскость XZ из центра проекции C можно получить с помощью преобразования центрального проецирования. Eго матрица:

Здесь центр проекции лежит на оси Y и имеет Y-координату, равную (-H), где H>0.

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

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

Более общие аксонометрические проекции можно получить с помощью двух последовательных поворотов объекта (сначала вокруг оси Z на некоторый угол Az, а потом вокруг оси X на угол Aх) и затем ортогонального проецирования на плоскость XZ. Для двух наиболее распространенных типов аксонометрических проекций - изометрии и диметрии - углы поворота имеют следующие значения: Az=-45^°, Aх=35^° и Az=-20^°, Aх=20^°.

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

1. сдвиг, в котором зависимой осью является ось X, сдвигающей осью - ось Y; коэффициент сдвига F=1 в случае, если задана "положительная" проекция, и F=-1, если требуется "отрицательная" проекция;

2. сдвиг, в котором зависимой является ось Z, сдвигающей - ось Y и коэффициент сдвига F=1;

3. проецирование на плоскость XZ.

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

Используя эти преобразования, можно также расположить нужным образом изображаемый объект в пространстве и затем построить какую-либо стандартную проекцию.

2) Параллельное проектирование

Cвойства параллельного проектирования:

1. Прямые линии переходят в прямые линии.

2. Параллельные прямые переходят в параллельные.

3. Сохраняется отношение длин отрезков, лежащих на одной прямой или на параллельных прямых.

4. При параллельном проектировании отношение площадей фигур сохраняется.

Центральное проектирование

Определение. Пусть a₁ и a₂ - две плоскости в пространстве, O - точка, не лежащая ни на одной из этих плоскостей. Центральным проектированием плоскости a₁ на плоскость a₂ с центром O называют отображение, которое точке A₁ плоскости a₁ ставит в соответствие точку пересечения прямой OA₁ с плоскостью a₂.

Определение. Прямую, на которой не определено центральное проектирование, называют исключительной прямой данной проекции.

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

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

Если ввести бесконечно удаленные точки и прямые, то центральное проектирование плоскости a₁ на плоскость a₂ с центром в точке O будет определено для всех точек плоскости a₁. При этом исключительная прямая будет проецироваться в бесконечно удаленную прямую плоскости a₂, а именно, образом точки M исключительной прямой будет бесконечно удаленная точка прямой OM; в этой точке пересекаются прямые плоскости a₂, параллельные прямой OM.

Определение. Отображение P плоскости a на плоскость b называют проективным, если оно является композицией центральных проектирований и аффинных преобразований, т. е. если существуют плоскости a₀ = a, a₁, ј, a_n = b и отображения P_i плоскостей a_i на a_i + 1, каждое из которых является либо центральным проектированием, либо аффинным преобразованием, причем P является композицией преобразований P_i. В случае, когда плоскость a совпадает с плоскостью b, отображение P называют проективным преобразованием плоскости a. Прообраз бесконечно удаленной прямой мы будем называть исключительной прямой данного проективного преобразования.

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

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

16. Параметрическое задание поверхности сложной формы.

17. Основные алгоритмы отсечения скрытых ребер и граней многогранника.