11.4. Ограничивающие объемы

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

Рис. 11.4. Сетка визуализированная с ограничивающей сферой и ограничивающим параллелепипедом. Сфера определяется путем задания центральной точки и радиуса. Параллелепипед определяется путем задания двух углов

Ограничивающие параллелепипеды и сферы, помимо прочего, часто используются для быстрой проверки видимости объектов и для обнаружения столкновений. Например, если не видна ограничивающая сфера или ограничивающий параллелепипед сетки, значит не видна и сама сетка. Проверка видимости сферы или параллелепипеда выполняется гораздо быстрее, чем проверка видимости каждого треугольника сетки. Что касается обнаружения столкновений, предположим, что в сцене выпущена ракета и нам необходимо определить, столкнулась ли она с каким-нибудь объектом сцены. Поскольку объекты состоят из треугольных граней, нам надо перебрать каждую грань каждого объекта и проверить столкнулась ли с ней ракета (которая математически моделируется с помощью луча). Этот подход требует огромного количества проверок пересечения луча с треугольником — по одной проверке для каждой грани каждого объекта сцены. Более эффективный подход заключается в вычислении для каждой сетки ограничивающей сферы или ограничивающего параллелепипеда и последующем выполнении для каждой сетки одной проверки на пересечение луча со сферой (или параллелепипедом). Тогда мы можем сказать, что объект поражен, если луч пересекается с его ограничивающим объемом. Это достаточно хорошая аппроксимация; если требуется большая точность, мы можем использовать проверку пересечения луча со сферой или параллелепипедом для того, чтобы отбросить те объекты, которые явно не задеты, а затем выполнить дополнительные более точные проверки для тех объектов сцены, чьи ограничивающие объемы пересекает луч.

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

HRESULT D3DXComputeBoundingSphere(
     LPD3DXVECTOR3 pFirstPosition,
     DWORD NumVertices,
     DWORD dwStride,
     D3DXVECTOR3* pCenter,
     FLOAT* pRadius
);

• pFirstPosition — Указатель на описывающий местоположение вектор в структуре данных первой вершины из массива вершин.

• NumVertices — Количество вершин в массиве вершин.

• dwStride — Размер данных каждой вершины в байтах. Эти сведения необходимы потому что в структуре данных вершины может храниться дополнительная информация, такая как вектор нормали или координаты текстуры, которая не требуется для вычисления ограничивающей сферы, и функция должна знать, сколько байт следует пропустить, чтобы перейти к данным местоположения следующей вершины.

• pCenter — Возвращает координаты центра ограничивающей сферы.

• pRadius — Возвращает радиус ограничивающей сферы.

HRESULT D3DXComputeBoundingBox(
     LPD3DXVECTOR3 pFirstPosition,
     DWORD NumVertices,
     DWORD dwStride,
     D3DXVECTOR3* pMin,
     D3DXVECTOR3* pMax
);

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

11.4.1. Новые константы

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

namespace d3d
{

     ...

     const float INFINITY = FLT_MAX;
     const float EPSILON  = 0.001f;

Константа INFINITY используется просто для представления наибольшего числа, которое может храниться в переменной типа float. Поскольку у нас не может быть значения типа float большего чем FLT_MAX, данное число будет служить для нас концепцией бесконечности, а использование именованной константы делает код более читаемым, явно указывая на те места, где подразумевается бесконечно большое значение. Константа EPSILON — это малое число, задав которое мы будем считать, что все числа меньше его равны нулю. Потребность в такой константе вызвана погрешностями огругления при вычислениях с плавающей точкой. Из-за них результат вычислений, который должен быть равен нулю, может немного отличаться от нуля. И, следовательно, сравнение его с нулем закончится неудачно. Поэтому для чисел с плавающей точкой мы заменяем операцию сравнения с нулем на проверку, что значение меньше, чем EPSILON. Приведенный ниже фрагмент кода показывает, как константа EPSILON используется при проверке равенства двух чисел с плавающей точкой:

bool Equals(float lhs, float rhs)
{
     // если lhs == rhs их разность должна быть равна нулю
     return fabs(lhs - rhs) < EPSILON ? true : false;
}

11.4.2. Типы ограничивающих объемов

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

struct BoundingBox
{
     BoundingBox();

     bool isPointInside(D3DXVECTOR3& p);

     D3DXVECTOR3 _min;
     D3DXVECTOR3 _max;
};

struct BoundingSphere
{
     BoundingSphere();

     D3DXVECTOR3 _center;
     float       _radius;
};

d3d::BoundingBox::BoundingBox()
{
     // ограничивающий параллелепипед
     // бесконечно малого размера
     _min.x = d3d::INFINITY;
     _min.y = d3d::INFINITY;
     _min.z = d3d::INFINITY;

     _max.x = -d3d::INFINITY;
     _max.y = -d3d::INFINITY;
     _max.z = -d3d::INFINITY;
}

bool d3d::BoundingBox::isPointInside(D3DXVECTOR3& p)
{
     // точка внутри ограничивающего параллелепипеда?
     if(p.x >= _min.x && p.y >= _min.y && p.z >= _min.z &&
        p.x <= _max.x && p.y <= _max.y && p.z <= _max.z)
     {
          return true;
     }
     else
     {
          return false;
     }
}

d3d::BoundingSphere::BoundingSphere()
{
     _radius = 0.0f;
}

11.4.3. Пример приложения: ограничивающие объемы

Приложение Bounding Volumes находящееся в папке примеров к данной главе, расположенной на диске с сопроводительными файлами, демонстрирует использование функций D3DXComputeBoundingSphere и D3DXComputeBoundingBox. Программа загружает сетку из X-файла и вычисляет для нее ограничивающую сферу и ограничивающий параллелепипед. Затем программа создает два объекта ID3DXMesh — один для моделирования ограничивающей сферы и другой для моделирования ограничивающего параллелепипеда. После этого визуализируется загруженная из X-файла сетка и вместе с ней либо сетка ограничивающей сферы, либо сетка ограничивающего параллелепипеда (рис. 11.5). Пользователь может выбирать, что именно (ограничивающая сфера или ограничивающий параллелепипед) отображается, нажимая на клавишу Space.

Рис. 11.5. Окно программы Bounding Volumes. Обратите внимание, чтобы ограничивающая сфера была прозрачной используется альфа-смешивание

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

bool ComputeBoundingSphere(
        ID3DXMesh* mesh, // сетка, для которой вычисляется ограничивающая сфера
        d3d::BoundingSphere* sphere) // возвращает ограничивающую сферу
{
     HRESULT hr = 0;

     BYTE* v = 0;
     mesh->LockVertexBuffer(0, (void**)&v);

     hr = D3DXComputeBoundingSphere(
            (D3DXVECTOR3*)v,
            mesh->GetNumVertices(),
            D3DXGetFVFVertexSize(mesh->GetFVF()),
            &sphere->_center,
            &sphere->_radius);

     mesh->UnlockVertexBuffer();

     if( FAILED(hr) )
          return false;

     return true;
}

bool ComputeBoundingBox(
        ID3DXMesh* mesh, // сетка, для которой вычисляется ограничивающий параллелепипед
        d3d::BoundingBox* box) // возвращает ограничивающий параллелепипед
{
     HRESULT hr = 0;

     BYTE* v = 0;
     mesh->LockVertexBuffer(0, (void**)&v);

     hr = D3DXComputeBoundingBox(
            (D3DXVECTOR3*)v,
            mesh->GetNumVertices(),
            D3DXGetFVFVertexSize(mesh->GetFVF()),
            &box->_min,
            &box->_max);

     mesh->UnlockVertexBuffer();

     if( FAILED(hr) )
          return false;

     return true;
}

Обратите внимание, что приведение типа (D3DXVECTOR3*)v подразумевает, что в используемой структуре данных вершины информация о координатах вершины хранится в самом начале. Также обратите внимание на использование функции D3DXGetFVFVertexSize для получения размера структуры данных вершины, соответствующей указанному описанию формата вершин.