 |
Алгоритм трассировки лучей
|
|
|
|
При рассмотрении этого алгоритма предполагается, что наблюдатель находится на положительной полуоси Z, а экран дисплея перпендикулярен оси Z и располагается между объектом и наблюдателем.
Удаление невидимых (скрытых) поверхностей в алгоритме трассировки лучей выполняется следующим образом:
· сцена преобразуется в пространство изображения,
· из точки наблюдения в каждый пиксель экрана проводится луч и определяется, какие именно объекты сцены пересекаются с лучом,
· вычисляются и упорядочиваются по Z координаты точек пересечения объектов с лучом. В простейшем случае для непрозрачных поверхностей без отражений и преломлений видимой точкой будет точка с максимальным значением Z-координаты. Для более сложных случаев требуется сортировка точек пересечения вдоль луча.
Ясно, что наиболее важная часть алгоритма - процедура определения пересечения, которая в принципе выполняется Rx×Ry×N раз (здесь Rx,Ry - разрешение дисплея по X и Y, соответственно, а N - количество многоугольников в сцене).
Очевидно, что повышение эффективности может достигаться сокращением времени вычисления пересечений и избавлением от ненужных вычислений. Последнее обеспечивается использованием геометрически простой оболочки, объемлющей объект - если луч не пересекает оболочку, то не нужно вычислять пересечения с ним многоугольников, составляющих исследуемый объект.
При использовании прямоугольной оболочки определяется преобразование, совмещающее луч с осью Z. Оболочка подвергается этому преобразованию, а затем попарно сравниваются знаки Xmin с Xmax и Ymin с Ymax. Если они различны, то есть пересечение луча с оболочкой (см. рис. 6.4.)
Рис. 6.4.: Определение пересечения луча и оболочки
|
|
|
При использовании сферической оболочки для определения пересечения луча со сферой достаточно сосчитать расстояние от луча до центра сферы. Если оно больше радиуса, то пересечения нет. Параметрическое уравнение луча, проходящего через две точки P1(x1,y1,z1) и P2(x2,y2,z2), имеет вид:
Минимальное расстояние от точки центра сферы P0(x0,y0,z0) до луча равно:
|
Этому соответствует значение t:
Если d2 > R2, то луч не пересекает объекты, заключенные в оболочку.
Дальнейшее сокращение расчетов пересечений основывается на использовании групп пространственно связанных объектов. Каждая такая группа окружается общей оболочкой. Получается иерархическая последовательность оболочек, вложенная в общую оболочку для всей сцены. Если луч не пересекает какую-либо оболочку, то из рассмотрения исключаются все оболочки, вложенные в нее и, следовательно, объекты. Если же луч пересекает некоторую оболочку, то рекурсивно анализируются все оболочки вложенные в нее.
Наряду с вложенными оболочками для сокращения расчетов пересечений используется отложенное вычисление пересечений с объектами. Если обнаруживается, что объект пересекается лучом, то он заносится в специальный список пересеченных. После завершения обработки всех объектов сцены объекты, попавшие в список пересеченных, упорядочиваются по глубине. Заведомо невидимые объекты отбрасываются, а для оставшихся выполняется расчет пересечений, и отображается точка пересечения наиболее близкая к наблюдателю.
Дополнительное сокращение объема вычислений может достигаться отбрасыванием нелицевых граней, учетов связности строк растрового разложения и т.д.
Для сокращения времени вычислений собственно пересечений предложено достаточно много алгоритмов, упрощающих вычисления для определенной формы задания поверхностей.
|
|
|
СПИСОК ЛИТЕРАТУРЫ
1. Никифоров, Ю.И. Компьютерная графика. Математический аппарат: метод. указания к лабораторным работам / Сост. Ю.И. Никифоров; Иван. гос. хим.-технол. ун-т.-Иваново, 2007.-48с.
2. Роджерс,Д., Адамс,Дж. Математические основы машинной графики/Пер. с англ.-М.:Машиностроение,2000.-240с.
3. Вельтмандер,П.В. Основные алгоритмы компьютерной графики. Машинная графика/Учебное пособие в 3-х книгах, Книга 2./ Новосибирский гос. ун-т. 1997/http://ermak.cs.nstu.ru/kg_rivs/kg02.htm.
Содержание
1. ПРОЕКЦИИ........................................................................................... 3
1.1. Введение.............................................................................................. 3
1.2. Параллельные проекции..................................................................... 5
1.3. Центральная проекция...................................................................... 11
2. ГЕНЕРАЦИЯ ВЕКТОРОВ................................................................ 13
2.1. Введение................................................................................................ 13
2.2. Алгоритм Брезенхема....................................................................... 14
3. ГЕНЕРАЦИЯ ОКРУЖНОСТИ........................................................ 16
3.1. Введение............................................................................................ 16
3.2. Алгоритм Брезенхема....................................................................... 16
4. ЗАПОЛНЕНИЕ МНОГОУГОЛЬНИКА.......................................... 21
4.1. Введение............................................................................................ 21
4.2. Заполнение многоугольника............................................................ 21
4.3. Построчное заполнение.................................................................... 22
4.4. Заливка области с затравкой............................................................ 24
4.5. Построчный алгоритм заливки с затравкой.................................... 26
5. ОТСЕЧЕНИЕ ОТРЕЗКОВ................................................................ 27
5.1. Введение............................................................................................ 27
5.2. Двумерный алгоритм Коэна-Сазерленда........................................ 28
5.3. Двумерный алгоритм Лианга-Барски.............................................. 30
6. УДАЛЕНИЕ СКРЫТЫХ ЛИНИЙ И ПОВЕРХНОСТЕЙ.................. 37
6.1. Введение............................................................................................ 37
6.2. Алгоритмы удаления линий............................................................. 37
6.3. Алгоритм удаления поверхностей с Z-буфером.............................. 38
6.4. Построчный алгоритм с Z-буфером................................................ 40
6.5. Алгоритм разбиения области Варнока............................................ 40
6.6. Построчный алгоритм Уоткинса...................................................... 44
6.7. Алгоритм трассировки лучей........................................................... 45
|
|
|
