Предыдущая страница реферата | 11  12  13  14  15  16  17  18  19  20  21 | Следующая страница реферата



а параметр t, определяющий ближайшую точку Р(t) равен:

[pic]

Если d2 > R2, где R - радиус сферической оболочки, то луч не может пересечься с объектом.

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

Одной простой процедурой можно свести тест с прямоугольной оболочкой к сравнению знаков, упрощая тем самым вычисление пересечений с объектом, а также сравнения по глубине среди точек пересечения. В этой процедуре используются переносы и повороты вокруг координатных осей для того, чтобы добиться совпадения луча с осью z. Аналогичным преобразованиям подвергается и прямоугольная оболочка объекта. Луч пересекает оболочку, если в новой перенесенной и повернутой системе координат знаки xmin и xmax, а так же ymin и ymax. противоположны, как показано на рис. 3.14.

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

Q (x, y, z) = a1x2 + a2y2 + a3z2 + b1yz + b2xz + b3xy + c1x + c2y + c3z +d = 0

После применения преобразования, которое является комбинацией переноса и поворота и используется для совмещения луча с осью z, пересечение этого луча с поверхностью, если оно имеет место, возникает при x = y = 0. Поэтому в общем случае точки пересечения являются решениями уравнения:

[pic] т.е.

[pic]

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

Вычисления пересечений для элементов биполиномиальных параметрических поверхностей более сложны. Уиттед предложил простой метод разбиения для элемента бикубической поверхности. Вычисления выполняются с элементом поверхности в его исходном положении. Если луч пересекает сферическую оболочку элемента поверхности, то этот кусок разбивается с помощью алгоритма разбиения предложенного Кэтмулом. Затем луч проверяется на пересечение со сферическими оболочками подэлементов. Если пересечение не обнаружено, то луч не пересекается и с самим элементом. Если же луч пересекается со сферической оболочкой какого-нибудь подэлемента, то последний разбивается дальше. Процесс завершается, если ни одна из сферических оболочек не пересечена или если достигнут заранее определенный их минимальный размер. Эти сферические оболочки минимального размера и являются искомыми пересечениями луча и элемента поверхности.

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

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

Q (u, w) = 0 с компонентами x = f (u, w) y = g (u, w) z = h (u, w)

в преобразованной системе координат выполнено условие x = y = 0. Значит, f (u, w) = 0 g (u, w) = 0

Совместное решение этой пары уравнений дает значения u и w для точек пересечения. Подстановка этих значений в уравнение z = h (u, w) дает компоненту z для точек пересечения. Неудача попытки найти действительное решение означает, что луч не пересекает поверхность. Степень системы уравнений для u, w равна произведению степеней биполиномиальных поверхностей. Бикубическая поверхность, например, имеет шестую степень.
Следовательно, в общем случае потребуются численные методы решения. Там, где это допустимо, для начального приближения u и w можно использовать пересечения луча с выпуклой оболочкой. Для получения пересечений в исходной системе координат, как и ранее, следует использовать обратное преобразование.

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

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

Подготовка данных для сцены:

Создать список объектов, содержащий по меньшей мере следующую информацию:

Полное описание объекта: тип, поверхность, характеристики и т. п.

Описание сферической оболочки: центр и радиус,

Флаг прямоугольной оболочки. Если этот флаг поднят, то будет выполнен габаритный тест с прямоугольной оболочкой, если же он опушен, то тест выполняться не будет. Заметим, что габаритный тест необходим не для всех объектов, например для сферы он не нужен.

Описание прямоугольной оболочки: xmin, xmax, ymin, ymax, zmin, zmax.

Рекомендуем скачать другие рефераты по теме: предмет культурологии, реферат на тему организация.

Предыдущая страница реферата | 11  12  13  14  15  16  17  18  19  20  21 | Следующая страница реферата