Поэтому тест со сферической оболочкой сводится к определению расстояния от точки до трехмерной прямой, т. е. луча. Будем использовать параметрическое представление прямой, проходящей через точки P1(x1, y1, z1) и P2(x2, y2, z2) т. е.:

Р(t) = P1 + (P2 - P1)t

с компонентами

x = x1 +(x2 - x1)t = x1 +at

y = y1 +(y2 - y1)t = y1 +bt

z = z1 +(z2 - z1)t = z1 +ct

Тогда минимальное расстояние d от этой прямой до точки P0(x0, y0, z0) равно:

d2 = (x - x0)2 + (y - y0)2 +(z - z0)2

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

Если 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. Поэтому в общем случае точки пересечения являются решениями уравнения:

т.е.

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

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

При реализации преобразования, совмещающего луч с осью 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.