NeHe Tutorials Народный учебник по OpenGL
Урок X2. OpenGL

Введение:

 

Представьте, что вы пишете программу, в которой можно бродить по виртуальному миру, который битком набит деревьями, зданиями, машинами, людьми и т.д. Интересно, как бы выглядела ваша функция рисования этого мира?

 

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

 

Конечно, если у вас немного объектов, этот метод годится. Но как только ваш мир немного разрастется, вы заметите, что скорость прорисовки будет стремительно падать.

 

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

 

Один из способов это сделать называется отсечением по пирамиде видимости (frustum сulling).

 

Определения:

 

Прежде, чем пойдем дальше, давайте ответим на несколько простых вопросов:

 

Что такое view frustum?

View frustum (пирамида видимости) – это часть пространства, в которой находятся все объекты, видимые из данной точки в данный момент. Она определяется шестью гранями усеченной пирамиды (т.е. пирамиды со срезанной вершиной). Если какая-то точка находится внутри пирамиды видимости, ее видно. Если вне пирамиды, значит, эту точку не видно.

 [Обратите внимание – я говорю, что точка видима, хотя это не совсем так. Ее может закрывать другой объект, но она по крайней мере в поле зрения.]

 

Что такое - плоскость?

(прим. перев. – интересно было бы посмотреть на программиста, который не знает, что такое плоскость J)

Плоскость можно представить как бесконечно широкий и длинный лист бумаги. Любая точка пространства либо принадлежит плоскости, либо «спереди» от плоскости, либо «за» плоскостью.

Плоскость определяется четырьмя числами: A,B,C и D, где {A,B,C} – вектор нормали к этой плоскости, а D – расстояние до начала координат. Если вы вообще ничего из этого не понимаете, не падайте духом – на самом деле чтоб это использовать, понимать этого не надо.

 

Профминимум

 

Итак, прежде всего, нам надо знать: какие числа определяют текущую пирамиду видимости.

 

Вычислять это вручную может быть достаточно сложно. К счастью, приложив минимум усилий, мы можем заставить OpenGL сделать это за нас. Все, что нам надо - это извлечь текущие матрицы PROJECTION и MODELVIEW, скомбинировать их и узнать нужные значения.

 

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

 

float frustum[6][4];

 

Это - двумерный массив 6*4 (шесть плоскостей, для каждой четыре числа: A, B, C, и D).

 

Теперь функция, которая извлекает числа и заполняет массив. Вам придется вызывать эту функцию для каждого кадра, строго перед рисованием.

 

ExtractFrustum()

{

   float   proj[16];

   float   modl[16];

   float   clip[16];

   float   t;

 

   /* Узнаем текущую матрицу PROJECTION */

   glGetFloatv( GL_PROJECTION_MATRIX, proj );

 

   /* Узнаем текущую матрицу MODELVIEW */

   glGetFloatv( GL_MODELVIEW_MATRIX, modl );

 

   /* Комбинируем матрицы(перемножаем) */

   clip[ 0] = modl[ 0] * proj[ 0] + modl[ 1] * proj[ 4] + modl[ 2] * proj[ 8] + modl[ 3] * proj[12];

   clip[ 1] = modl[ 0] * proj[ 1] + modl[ 1] * proj[ 5] + modl[ 2] * proj[ 9] + modl[ 3] * proj[13];

   clip[ 2] = modl[ 0] * proj[ 2] + modl[ 1] * proj[ 6] + modl[ 2] * proj[10] + modl[ 3] * proj[14];

   clip[ 3] = modl[ 0] * proj[ 3] + modl[ 1] * proj[ 7] + modl[ 2] * proj[11] + modl[ 3] * proj[15];

 

   clip[ 4] = modl[ 4] * proj[ 0] + modl[ 5] * proj[ 4] + modl[ 6] * proj[ 8] + modl[ 7] * proj[12];

   clip[ 5] = modl[ 4] * proj[ 1] + modl[ 5] * proj[ 5] + modl[ 6] * proj[ 9] + modl[ 7] * proj[13];

   clip[ 6] = modl[ 4] * proj[ 2] + modl[ 5] * proj[ 6] + modl[ 6] * proj[10] + modl[ 7] * proj[14];

   clip[ 7] = modl[ 4] * proj[ 3] + modl[ 5] * proj[ 7] + modl[ 6] * proj[11] + modl[ 7] * proj[15];

 

   clip[ 8] = modl[ 8] * proj[ 0] + modl[ 9] * proj[ 4] + modl[10] * proj[ 8] + modl[11] * proj[12];

   clip[ 9] = modl[ 8] * proj[ 1] + modl[ 9] * proj[ 5] + modl[10] * proj[ 9] + modl[11] * proj[13];

   clip[10] = modl[ 8] * proj[ 2] + modl[ 9] * proj[ 6] + modl[10] * proj[10] + modl[11] * proj[14];

   clip[11] = modl[ 8] * proj[ 3] + modl[ 9] * proj[ 7] + modl[10] * proj[11] + modl[11] * proj[15];

 

   clip[12] = modl[12] * proj[ 0] + modl[13] * proj[ 4] + modl[14] * proj[ 8] + modl[15] * proj[12];

   clip[13] = modl[12] * proj[ 1] + modl[13] * proj[ 5] + modl[14] * proj[ 9] + modl[15] * proj[13];

   clip[14] = modl[12] * proj[ 2] + modl[13] * proj[ 6] + modl[14] * proj[10] + modl[15] * proj[14];

   clip[15] = modl[12] * proj[ 3] + modl[13] * proj[ 7] + modl[14] * proj[11] + modl[15] * proj[15];

 

   /* Находим A, B, C, D для ПРАВОЙ плоскости */

   frustum[0][0] = clip[ 3] - clip[ 0];

   frustum[0][1] = clip[ 7] - clip[ 4];

   frustum[0][2] = clip[11] - clip[ 8];

   frustum[0][3] = clip[15] - clip[12];

 

   /* Приводим уравнение плоскости к нормальному виду */

   t = sqrt( frustum[0][0] * frustum[0][0] + frustum[0][1] * frustum[0][1] + frustum[0][2] * frustum[0][2] );

   frustum[0][0] /= t;

   frustum[0][1] /= t;

   frustum[0][2] /= t;

   frustum[0][3] /= t;

 

   /* Находим A, B, C, D для ЛЕВОЙ плоскости */

   frustum[1][0] = clip[ 3] + clip[ 0];

   frustum[1][1] = clip[ 7] + clip[ 4];

   frustum[1][2] = clip[11] + clip[ 8];

   frustum[1][3] = clip[15] + clip[12];

 

   /* Приводим уравнение плоскости к нормальному виду */

   t = sqrt( frustum[1][0] * frustum[1][0] + frustum[1][1] * frustum[1][1] + frustum[1][2] * frustum[1][2] );

   frustum[1][0] /= t;

   frustum[1][1] /= t;

   frustum[1][2] /= t;

   frustum[1][3] /= t;

 

   /* Находим A, B, C, D для НИЖНЕЙ плоскости */

   frustum[2][0] = clip[ 3] + clip[ 1];

   frustum[2][1] = clip[ 7] + clip[ 5];

   frustum[2][2] = clip[11] + clip[ 9];

   frustum[2][3] = clip[15] + clip[13];

 

   /* Приводим уравнение плоскости к нормальному */

   t = sqrt( frustum[2][0] * frustum[2][0] + frustum[2][1] * frustum[2][1] + frustum[2][2] * frustum[2][2] );

   frustum[2][0] /= t;

   frustum[2][1] /= t;

   frustum[2][2] /= t;

   frustum[2][3] /= t;

 

   /* ВЕРХНЯЯ плоскость */

   frustum[3][0] = clip[ 3] - clip[ 1];

   frustum[3][1] = clip[ 7] - clip[ 5];

   frustum[3][2] = clip[11] - clip[ 9];

   frustum[3][3] = clip[15] - clip[13];

 

   /* Нормальный вид */

   t = sqrt( frustum[3][0] * frustum[3][0] + frustum[3][1] * frustum[3][1] + frustum[3][2] * frustum[3][2] );

   frustum[3][0] /= t;

   frustum[3][1] /= t;

   frustum[3][2] /= t;

   frustum[3][3] /= t;

 

   /* ЗАДНЯЯ плоскость */

   frustum[4][0] = clip[ 3] - clip[ 2];

   frustum[4][1] = clip[ 7] - clip[ 6];

   frustum[4][2] = clip[11] - clip[10];

   frustum[4][3] = clip[15] - clip[14];

 

   /* Нормальный вид */

   t = sqrt( frustum[4][0] * frustum[4][0] + frustum[4][1] * frustum[4][1] + frustum[4][2] * frustum[4][2] );

   frustum[4][0] /= t;

   frustum[4][1] /= t;

   frustum[4][2] /= t;

   frustum[4][3] /= t;

 

   /* ПЕРЕДНЯЯ плоскость */

   frustum[5][0] = clip[ 3] + clip[ 2];

   frustum[5][1] = clip[ 7] + clip[ 6];

   frustum[5][2] = clip[11] + clip[10];

   frustum[5][3] = clip[15] + clip[14];

 

   /* Нормальный вид */

   t = sqrt( frustum[5][0] * frustum[5][0] + frustum[5][1] * frustum[5][1] + frustum[5][2] * frustum[5][2] );

   frustum[5][0] /= t;

   frustum[5][1] /= t;

   frustum[5][2] /= t;

   frustum[5][3] /= t;

}

 

Ууууф. Многовато. Как-то не очень похоже, что из-за этого программа будет работать быстрее, да? Будет, поверьте. Нам придется вызывать эту функцию только один раз для кадра, так что не волнуйтесь из-за этих громоздких функций типа sqrt() и вообще математики.

 

Точка лежит в пирамиде?

 

Хорошо, мы наконец-то получили уравнения плоскостей, как же мы будем проверять, видим объект или нет? Давайте начнем с одной точки.

 

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

 

Точка в пирамиде, если она находится перед всеми плоскостями одновременно.

 

 [ Это так, потому что наши 6 векторов нормалей вида {A,B,C} лежат в пирамиде (т.е. все плоскости как бы смотрят внутрь пирамиды). Если бы было наоборот, то точка бы лежала ЗА всеми плоскостями.]

 

Уже неплохо! Это и есть основа всех последующих вычислений. Следующий шаг – понять, находится ли точка перед плоскостью или нет. Для этого нам надо посчитать расстояние от точки плоскости. Если расстояние положительно, значит, точка лежит перед плоскостью, отрицательна – значит за плоскостью.

 

Вот - формула для вычисления расстояния точки до плоскости:

 

distance = A * X + B * Y + C * Z + D

 

Где A, B, C, и D - четыре числа, которые определяют плоскость и X, Y, и Z - координаты точки.

 

Теперь мы можем написать функцию для проверки  - видима точка или нет.

 

bool PointInFrustum( float x, float y, float z )

{

   int p;

 

   for( p = 0; p < 6; p++ )

      if( frustum[p][0] * x + frustum[p][1] * y + frustum[p][2] * z + frustum[p][3] <= 0 )

         return false;

   return true;

}

 

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

 

Просто, не так ли?

 

Кстати, эта функция выкидывает все точки, находящиеся НА плоскостях – мне так больше нравится. Если вы не хотите их выкидывать, измените оператор "<=" на "<".

 

Ограничивающие тела

 

Перед тем, как мы перейдем к более сложным проверкам, давайте поговорим об ограничивающих телах.

 

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

 

[Вообще-то, этот метод и не всегда бы правильно работал – если бы объект включает себя целиком пирамиду, то все точки объекта были бы вне пирамиды, но объект пришлось бы рисовать все равно.]

 

Что же мы делаем? Представьте сферу, которая включает в себя целиком объект. Теперь, вместо того, чтобы проверять на видимость сам объект, давайте лучше проверим эту сферу. Если хоть какая-то часть сферы видна, мы рисуем весь объект (саму сферу мы, конечно, не рисуем).

 

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

 

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

 

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

 

Так что же лучше, куб или сфера? Когда как. Мы вернемся к этому вопросу позже.

 

Эта сфера в пирамиде?

 

Теперь мы знаем – надо проверять сферу, но как? Да почти так же, как точку:

 

Here you go:

 

bool SphereInFrustum( float x, float y, float z, float radius )

{

   int p;

 

   for( p = 0; p < 6; p++ )

      if( frustum[p][0] * x + frustum[p][1] * y + frustum[p][2] * z + frustum[p][3] <= -radius )

         return false;

   return true;

}

 

В качестве параметров мы передаем X, Y и Z центра сферы и ее радиус. Единственное отличие в самой проверке от проверки точки – то, что мы сравниваем расстояние с радиусом, а не с нулем.

 

Забавный вариант

 

Посмотрите на этот вариант функции SphereInFrustum():

 

float SphereInFrustum( float x, float y, float z, float radius )

{

   int p;

   float d;

 

   for( p = 0; p < 6; p++ )

   {

      d = frustum[p][0] * x + frustum[p][1] * y + frustum[p][2] * z + frustum[p][3];

      if( d <= -radius )

         return 0;

   }

   return d + radius;

}

 

Это почти то же самое, только мы возвращаем 0, если сфера вне пирамиды, иначе мы возвращаем радиус плюс расстояние до последней проверенной плоскости.

 

Зачем нам это нужно? Последняя плоскость пирамиды – это ближняя грань пирамиды, поэтому мы сразу получаем расстояние от камеры до объекта.

 

Это здорово, потому что мы можем использовать это, чтобы изменять уровень детализации. Если объект очень близко, нам нужно будет рисовать очень много полигонов, а если он далеко, то бы обойдемся и менее детальным изображением. И это все не будет тратить дополнительного времени – все равно мы это вычисляем!

 

 [Заметьте, что просто использовать расстояние до объекта, чтобы регулировать детализацию - это не всегда правильно. Может, вам захочется учитывать и радиус сферы тоже. Например, очень большой объект, даже если он находится далеко, придется рисовать тщательно.]

 

Этот параллелепипед в пирамиде?

 

Точка не может превосходить по размеру пирамиду, да и тест со сферой работает правильно, даже если эта сфера включает в себя целиком пирамиду. Но с параллелепипедом будет немного сложнее.

 

Мы, конечно, можем проверить все 8 вершин параллелепипеда, но если он включает в себя целиком пирамиду, то все точки будут вне пирамиды, но объект будет виден.

 

В данном примере мы возьмем частный случай параллелепипеда – куб.

 

Вот это - (и это работает, даже если пирамида целиком внутри куба):

 

bool CubeInFrustum( float x, float y, float z, float size )

{

   int p;

 

   for( p = 0; p < 6; p++ )

   {

      if( frustum[p][0] * (x - size) + frustum[p][1] * (y - size) + frustum[p][2] * (z - size) + frustum[p][3] > 0 )

         continue;

      if( frustum[p][0] * (x + size) + frustum[p][1] * (y - size) + frustum[p][2] * (z - size) + frustum[p][3] > 0 )

         continue;

      if( frustum[p][0] * (x - size) + frustum[p][1] * (y + size) + frustum[p][2] * (z - size) + frustum[p][3] > 0 )

         continue;

      if( frustum[p][0] * (x + size) + frustum[p][1] * (y + size) + frustum[p][2] * (z - size) + frustum[p][3] > 0 )

         continue;

      if( frustum[p][0] * (x - size) + frustum[p][1] * (y - size) + frustum[p][2] * (z + size) + frustum[p][3] > 0 )

         continue;

      if( frustum[p][0] * (x + size) + frustum[p][1] * (y - size) + frustum[p][2] * (z + size) + frustum[p][3] > 0 )

         continue;

      if( frustum[p][0] * (x - size) + frustum[p][1] * (y + size) + frustum[p][2] * (z + size) + frustum[p][3] > 0 )

         continue;

      if( frustum[p][0] * (x + size) + frustum[p][1] * (y + size) + frustum[p][2] * (z + size) + frustum[p][3] > 0 )

         continue;

      return false;

   }

   return true;

}

 

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

 

ПРИМЕЧАНИЕ: Функция, приведенная выше, будет иногда выдавать ошибочные результаты: TRUE вместо FALSE, т.е. объект будет виден, хотя он вне пирамиды. Это происходит, когда все вершины куба находятся не за плоскостями пирамиды, но они все равно вне пирамиды. Поэтому иногда вам придется прорисовывать ненужные объекты. Но обычно такое расположение встречается достаточно редко, и, соответственно, не сильно сказывается на общей скорости.

 

Чтобы проверка была абсолютно правильной, нужно также проверять расположение 8 вершин пирамиды относительно шести граней ограничивающего параллелепипеда. Если плоскости параллелепипеда располагаются параллельно осям, то можно обойтись простыми проверками больше-меньше  вместо проверок плоскостей параллелепипеда. В любом случае, это будет упражнением для менее ленивых, чем я ;-)

 

 

Смешанные тесты

 

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

 

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

 

Вот версия функции SphereInFrusum(), которая возвращает 0, если сфера полностью вне пирамиды, 1 если частично и 2 или полностью внутри.

 

int SphereInFrustum( float x, float y, float z, float radius )

{

   int p;

   int c = 0;

   float d;

 

   for( p = 0; p < 6; p++ )

   {

      d = frustum[p][0] * x + frustum[p][1] * y + frustum[p][2] * z + frustum[p][3];

      if( d <= -radius )

         return 0;

      if( d > radius )

         c++;

   }

   return (c == 6) ? 2 : 1;

}

 

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

 

Вот версия CubeInFrustum(), делающая то же самое.

 

int CubeInFrustum( float x, float y, float z, float size )

{

   int p;

   int c;

   int c2 = 0;

 

   for( p = 0; p < 6; p++ )

   {

      c = 0;

      if( frustum[p][0] * (x - size) + frustum[p][1] * (y - size) + frustum[p][2] * (z - size) + frustum[p][3] > 0 )

         c++;

      if( frustum[p][0] * (x + size) + frustum[p][1] * (y - size) + frustum[p][2] * (z - size) + frustum[p][3] > 0 )

         c++;

      if( frustum[p][0] * (x - size) + frustum[p][1] * (y + size) + frustum[p][2] * (z - size) + frustum[p][3] > 0 )

         c++;

      if( frustum[p][0] * (x + size) + frustum[p][1] * (y + size) + frustum[p][2] * (z - size) + frustum[p][3] > 0 )

         c++;

      if( frustum[p][0] * (x - size) + frustum[p][1] * (y - size) + frustum[p][2] * (z + size) + frustum[p][3] > 0 )

         c++;

      if( frustum[p][0] * (x + size) + frustum[p][1] * (y - size) + frustum[p][2] * (z + size) + frustum[p][3] > 0 )

         c++;

      if( frustum[p][0] * (x - size) + frustum[p][1] * (y + size) + frustum[p][2] * (z + size) + frustum[p][3] > 0 )

         c++;

      if( frustum[p][0] * (x + size) + frustum[p][1] * (y + size) + frustum[p][2] * (z + size) + frustum[p][3] > 0 )

         c++;

      if( c == 0 )

         return 0;

      if( c == 8 )

         c2++;

   }

   return (c2 == 6) ? 2 : 1;

}

 

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

 

Можно также возвращать байт – каждый бит отвечает за какую-то плоскость пирамиды. Устанавливаем бит в единицу, если тело полностью находится перед соответствующей плоскостью, и оставить бит равным нулю в противном случае. Если в конце этот байт равен нулю, значит, тело вне пирамиды. Если он равен 255, значит,  , считая, сколько из вершин находятся перед гранью. ьюроверяем,тело полностью внутри пирамиды. Иначе – только частично внутри.

 

Сферы ПРОТИВ параллелепипедов

 

Голосов за использование ограничивающих сфер примерно столько же, сколько за параллелепипеды. Но мне кажется, что лучше использовать сферы, когда это возможно. Вот почему:

 

- Проверка сферы на видимость более правильная, чем у параллелепипеда – они никогда не возвращает неправильного значения.

- Проверка сферы проходит быстрее всего: примерно 3 операции сравнения, тогда как в случае с кубом это как минимум 6 сравнений, а как максимум – все 48!

- Если объект вращается вокруг центра ограничивающей сферы, сферу пересчитывать не надо. А вот если мы ограничиваем объект кубом, то некоторые части объекта могут «вылезти» за пределы куба.

- Сфера занимает меньше памяти. Конечно, если вы используете куб, то вы тоже можете обойтись четырьмя числами, но вот в случае с параллелепипедом вам нужно будет уже 8 чисел.

 

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

 

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

 

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

 

Есть еще один способ – не разбивать объект на части, а определить несколько ограничивающих сфер для него. Если хоть одна будет видна, рисуем весь объект. Так как сферы в этом случае могут перекрываться, ускорит эта проверка весь процесс или нет, зависит от объекта.

 

В общем, решение за вами. Может, вам захочется использовать некую комбинацию методов.

 

Испытание Треугольников и Других Многоугольников

 

Меня часто спрашивают, как проверить принадлежность многоугольника пирамиде. Действительно, это то же самое, что и CubeInFrustum () , но для произвольного числа точек. Действуем точно так же: если все точки находятся за какой-нибудь плоскостью пирамиды, значит, многоугольник невидим (конечно, мы предполагаем, что многоугольники выпуклые).

 

 [Примечание: Иногда такая функция возращает TRUE вместо FALSE – я объяснял это в CubeInFrustum()]

 

Вот функция:

 

bool PolygonInFrustum( int numpoints, POINT* pointlist )

{

   int f, p;

 

   for( f = 0; f < 6; f++ )

   {

      for( p = 0; p < numpoints; p++ )

      {

         if( frustum[f][0] * pointlist[p].x + frustum[f][1] * pointlist[p].y + frustum[f][2] * pointlist[p].z + frustum[f][3] > 0 )

            break;

      }

      if( p == numpoints )

         return false;

   }

   return true;

}

 

В качестве аргумента мы передаем функции количество проверяемых точек и указатель на сам массив точек (структура POINT в данном случае должна содержать координаты X, Y и Z, тогда как существующая структура содержит только две координаты). Мы проверяем расположение точек относительно каждой из граней пирамиды и обрываем проверку плоскости, если какая-то из точек находится перед текущей плоскостью. Если все точки находятся за какой-либо из граней, мы сразу же возвращаем FALSE. Если в конце оказывается, что перед каждой из плоскостей находится хотя бы по точке, то многоугольник потенциально видим.

 

 [Конечно, у этой функции есть свои применения, но в играх глупо проверять каждый многоугольник на видимость, легче предоставить это OpenGL. Лучше браковать целые группы многоугольников одним тестом. ]

 

Оптимизация

 

Вы можете проделать следующие оптимизации, правда, неясно, будет ли заметна разница:

- Вы можете убрать приведение уравнений плоскостей к нормальному виду в ExtractFrustum(). Тогда полученные расстояния от точек до плоскостей будут отличаться от настоящих ровно в несколько раз. Тесты точки и параллелепипеда будут работать правильно, а тест сферы – нет. Если вы не используете ограничивающие сферы, вы можете таким образом избежать выполнения лишних команд, правда, это будет в большинстве случаев незаметно.

- На самом деле функцию ExtractFrustum() необходимо вызывать, только если положение камеры изменилось. Если от кадра к кадру ваши матрицы PROJECTION и MODELVIEW не меняются, лучше не пересчитывать уравнения плоскостей.

- Попробуйте развернуть циклы в функциях проверки.

 

Пример

nehex2.zip (48 Kb)

 

Клавиши управления в примере:

 

Esc - Выход

Up – Переместить камеру вперед

Стрелка вниз – Переместить камеру назад

Стрелка влево - Повернуть камеру налево

Стрелка вправо - Повернуть камеру направо

U - Наклонить камеру вверх

D - Наклонить камеру вниз

Keypad + - Добавить объект (максимум 1000)

Keypad - - Убрать объект (минимум один)

W - Увеличить угол просмотра (FOV)

T – Уменьшить угол просмотра (FOV)

G - Включить/выключить сетку

M - Изменить режим (объекты могут быть точками, сферами и кубами)

C - Включить/выключить отсечение по пирамиде видимости

 

Примечания к примеру:

- Этот исходный текст основан на NeHe Production’s OpenGL tutorial (nehe.gamedev.net), и я старался сделать свой исходный код похожим на код NeHe.

- Вы, вероятно, заметили, что в режиме кубов программа работает быстрее. Это не из-за проверки пирамиды, это потому, что кубы легче рисовать.

- Включите отсечение и попробуйте разные значения FOV (т.е. угла обзора), и чем больше ваша пирамида, тем больше объектов надо прорисовывать.

- Главный цикл просто прокручивает все объекты. Было бы лучше хранить объекты в octree (восьмеричное дерево) или использовать какой-нибудь другой метод организации памяти, но все это вы сделаете сами.

 

© Mark Morley

PMG  18 августа 2004 (c)  Bessmeltsev Mikhail