15.4. Пересечение луча и объекта

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

Однако, выполнение проверки пересечения с лучом для каждого треугольника сцены требует много времени на вычисления. Более быстрый, хотя и менее точный метод — представить каждый объект с помощью ограничивающей сферы. Тогда мы выполняем проверку пересечения луча и ограничивающей сферы и тот объект, чью ограничивающую сферу пересекает луч, считается выбранным.

Зная центральную точку c и радиус r сферы, мы можем проверить находится ли точка p на поверхности сферы с помощью следующей простой формулы:

где p — это точка на сфере, если условие выполняется (рис. 15.3).

Рис. 15.3. Длина вектора p – c, обозначаемая как |p – c|, равна радиусу сферы, если точка p лежит на поверхности сферы. Обратите внимание, что на иллюстрации для простоты изображен круг, но идея работает и в трех измерениях

Чтобы определить, пересекает ли луч p(t) = p₀ + tu сферу и, если да, то где, мы подставляем формулу луча в уравнение сферы и ищем значение параметра t, удовлетворяющее уравнению сферы, что позволит нам найти точки пересечения.

Подставляем формулу луча в уравнение сферы:

и получаем квадратное уравнение:

где A = u Ч u, B = 2(u Ч (p₀ – c)) и C = (p₀ – c) Ч (p₀ – c) – r². Если вектор u нормализован, то A = 1.

Предполагая, что вектор u нормализован, получаем решения для t₀ и t₁:

На рис. 15.4 показаны возможные результаты для t₀ и t₁ и объяснено, что эти результаты означают с точки зрения геометрии.

Рис. 15.4. a) Луч проходит мимо сферы; и t₀ и t₁ мнимые числа б) Луч находится за сферой; и t₀ и t₁ отрицательные числа. в) Луч начинается внутри сферы; одно из решений положительное, а другое — отрицательное. Положительное решение соответствует единственной точке пересечения. г) Луч пересекает сферу; и t₀ и t₁ положительные числа. д) Луч касается сферы в единственной точке; в этом случае оба решения положительны и t₀ = t₁.

Приведенный ниже метод возвращает true, если переданный в первом параметре луч пересекает переданную во втором параметре сферу. Если луч проходит мимо сферы, метод возвращает false:

bool PickApp::raySphereIntersectionTest(Ray* ray,
                                        BoundingSphere* sphere)
{
     D3DXVECTOR3 v = ray->_origin - sphere->_center;

     float b = 2.0f * D3DXVec3Dot(&ray->_direction, &v);
     float c = D3DXVec3Dot(&v, &v) –
               (sphere->_radius * sphere->_radius);

     // Находим дискриминант
     float discriminant = (b * b) - (4.0f * c);

     // Проверяем на мнимые числа
     if(discriminant < 0.0f)
          return false;

     discriminant = sqrtf(discriminant);

     float s0 = (-b + discriminant) / 2.0f;
     float s1 = (-b - discriminant) / 2.0f;

     // Если есть решение >= 0, луч пересекает сферу
     if(s0 >= 0.0f || s1 >= 0.0f)
          return true;

     return false;
}

Конечно, мы уже показывали объявление структуры BoundingSphere, но для удобства приведем его здесь еще раз:

struct BoundingSphere
{
     BoundingSphere();

     D3DXVECTOR3 _center;
     float _radius;
};