Программирование игр, создание игрового движка, OpenGL, DirectX, физика, форум
GameDev.ru / Программирование / Статьи / Frustum Culling

Frustum Culling

Автор:

Одной из важных оптимизаций в компьютерных играх является отсечение геометрии, не видимой на экране (Frustum Culling, далее фрустум кулинг). Раз мы все равно не увидим объект, то и не зачем тратить ресурсы компьютера на его подготовку и отрисовку.
В этой статье я затрону следующие темы:
    - кулинг сфер (Bounding Sphere), AABB (axis-aligned bounding box), OBB (oriented Bounding Box).
    - кулинг большого количества объектов.
    - применение SSE.
    - многопоточный кулинг.
    - кулинг на стороне GPU.
    - сравнение по скорости всех методов.

Что не буду затрагивать:
    - использование иерархий, деревьев. Можно объединить объекты в достаточно большие группы по территориальному признаку и сперва определить их видимость.
    - различные оптимизации для одного объекта, вроде запоминание 'удачной' плоскости отсечения.
    - тест с учетом буфера глубины. Объект может попадать во фрустум, но при этом быть полностью загороженным другим более близким к камере объектом. Следовательно его тоже можно было бы не рисовать.
    - cофтверный кулинг. Можно определять загороженность объектов другими объектами на стороне CPU.
    - кулинг для теней.


Простейший кулинг.

Имеем область видимости, заданную фрустумом или пирамидой видимости. Объекты, не попавшие в него следует отбросить и не посылать на рендер. Фрустум удобно задавать 6 плоскостями (frustum_planes).

Изображение

Имеем объекты на сцене. Каждый объект можно аппроксимировать простейшей геометрией. Например сферой, боксом (BoundingSphere, BoundingBox). Вся геометрия объекта лежит внутри этого примитива.

Изображение
Окружающие примитивы


Тест на видимость такой простейшей геометрии проходит очень быстро.  Нашей задачей является — понять находится ли указанный примитив вне фрустума.

Рассмотрим определение видимости: сфер, боксов. Боксы бывают разными: ориентированные по мировым осям AABB (axis-aligned bounding box) и ориентированные по локальным осям объекта OBB (oriented Bounding Box). Видно, что OBB лучше апроксимирует объект, но при этом тест на видимость сложнее чем ABB.


 
Сфера-фрустум.

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

__forceinline bool SphereInFrustum(vec3 &pos, float &radius, vec4 *frustum_planes)
{
  bool res = true;
  //тестируем 6 плоскостей фрустума
  for (int i = 0; i < 6; i++)
  {
    //считаем расстояние от центра сферы до плоскости
    //если центр сферы находится за плоскостью и расстояние больше чем радиус сферы,
    //то объект не попадает во фрустум
    if (frustum_planes[i].x * pos.x + frustum_planes[i].y * pos.y +
        frustum_planes[i].z * pos.z + frustum_planes[i].w <= -radius)
      res = false;
      //return false; //флаг работает быстрее
  }
  return res;
  //return true;
}



AABB-фрустум.

Окружающая сфера не всегда точно апроксимирует объект. Для более точного теста чаще используют апроксимирующие боксы. Боксы бывают разными. Ориентированные по мировым осям AABB и ориентированные по локальным осям объекта OBB.

Общая идея теста боксов: если все 8 точек бокса находятся за какой-либо плоскостью фрустума, то бокс не попадает во фрустум. В следующем примере приводится тест ABB-фрустум, но если подставить world-space точки в уравнения, то получим тест OBB-фрустум.

__forceinline bool RightParallelepipedInFrustum2(vec4 &Min, vec4 &Max, vec4 *frustum_planes)
{
//этот код показывает общую идею - как работает кулинг боксов, AABB и OBB
    //Min & Max 2 точки AABB в мировом пространстве
    //Мы можем трансформировать 8 точек бокса в мировое пространство
    //и подставить (вместо Min и Max) в уравнения, получив кулинг OBB-фрустум

  //тестируем 6 плоскостей фрустума
  for (int i = 0; i<6; i++)
  {
  //пробуем найти такую плоскость, для которой все 8 точек находятся за ней
      //тестируем 8 точек бокса
      //считаем расстояние от точки до плоскости
      //если точка впереди плоскости, то данная плоскость не является разделяющей
    if (frustum_planes[i][0] * Min[0] + frustum_planes[i][1] * Max[1] +
        frustum_planes[i][2] * Min[2] + frustum_planes[i][3]>0)
      continue;
    if (frustum_planes[i][0] * Min[0] + frustum_planes[i][1] * Max[1] +
        frustum_planes[i][2] * Max[2] + frustum_planes[i][3]>0)
      continue;
    if (frustum_planes[i][0] * Max[0] + frustum_planes[i][1] * Max[1] +
        frustum_planes[i][2] * Max[2] + frustum_planes[i][3]>0)
      continue;
    if (frustum_planes[i][0] * Max[0] + frustum_planes[i][1] * Max[1] +
        frustum_planes[i][2] * Min[2] + frustum_planes[i][3]>0)
      continue;
    if (frustum_planes[i][0] * Max[0] + frustum_planes[i][1] * Min[1] +
        frustum_planes[i][2] * Min[2] + frustum_planes[i][3]>0)
      continue;
    if (frustum_planes[i][0] * Max[0] + frustum_planes[i][1] * Min[1] +
        frustum_planes[i][2] * Max[2] + frustum_planes[i][3]>0)
      continue;
    if (frustum_planes[i][0] * Min[0] + frustum_planes[i][1] * Min[1] +
        frustum_planes[i][2] * Max[2] + frustum_planes[i][3]>0)
      continue;
    if (frustum_planes[i][0] * Min[0] + frustum_planes[i][1] * Min[1] +
        frustum_planes[i][2] * Min[2] + frustum_planes[i][3]>0)
      continue;

    //если все вершины бокса находятся за плоскостью, то мы нашли разделяющую плоскость -
    //объект находится вне фрустума
    return false;
  }
  //если не нашли разделяющей плоскости, то считаем что объект видимый
  return true;
}

Тест AABB-фрустум можно сделать более оптимально.

Алгоритм: находим ближайшую из 8 точек к плоскости и проверяем, находится ли она за плоскостью. Если да - то объект находится вне фрустума.

__forceinline bool RightParallelepipedInFrustum(vec4 &Min, vec4 &Max, vec4 *frustum_planes)
{
  bool inside = true;
  //тестируем 6 плоскостей фрустума
  for (int i = 0; i<6; i++)
  {
    //находим ближайшую к плоскости вершину
    //проверяем, если она находится за плоскостью, то объект вне врустума
    float d = max(Min.x * frustum_planes[i].x, Max.x * frustum_planes[i].x)
        + max(Min.y * frustum_planes[i].y, Max.y * frustum_planes[i].y)
        + max(Min.z * frustum_planes[i].z, Max.z * frustum_planes[i].z)
        + frustum_planes[i].w;
    inside &= d > 0;
    //return false; //флаг работает быстрее
  }
  //если не нашли разделяющей плоскости, считаем объект видим
  return inside;
}



OBB-фрустум.

Алгоритм: трансформировать 8 точек бокса из локальной системы координат сразу в clip-space. Так легче проверять на нахождение за плоскостью фрустума. Т.к. в этом пространстве фрустум представляет собой единичный куб [-1..1] (нужно учитывать, что для DirectX по Z координате [0..1]) Соответственно, если по какой либо оси все 8 вершин либо <-1 либо > 1, то весь объект находится вне фрустума.

__forceinline bool OBBInFrustum(const vec3 &Min, const vec3 &Max, mat4 &obj_transform_mat, mat4 &cam_modelview_proj_mat)
{
  //трансформируем 8 вершин бокса сразу в clip-space
  //В clip-space пространстве фрустум представляет собой ортонормированный единичный куб [-1..1].
    //Можно очень легко понять, находятся ли все 8 вершин за какой либо плоскостью.
    //Пометка: в DirectX по оси z clip-box имеет размеры 0..1 (вместо -1..1 как в OpenGL), это стоит учесть в коде

  //матрица трансформаций точек в clip-space
  mat4 to_clip_space_mat = cam_modelview_proj_mat * obj_transform_mat;

  //трансформируем 8 локальных точек бокса в clip-space
  vec4 obb_points[8];
  obb_points[0] = to_clip_space_mat * vec4(Min[0], Max[1], Min[2], 1.f);
  obb_points[1] = to_clip_space_mat * vec4(Min[0], Max[1], Max[2], 1.f);
  obb_points[2] = to_clip_space_mat * vec4(Max[0], Max[1], Max[2], 1.f);
  obb_points[3] = to_clip_space_mat * vec4(Max[0], Max[1], Min[2], 1.f);
  obb_points[4] = to_clip_space_mat * vec4(Max[0], Min[1], Min[2], 1.f);
  obb_points[5] = to_clip_space_mat * vec4(Max[0], Min[1], Max[2], 1.f);
  obb_points[6] = to_clip_space_mat * vec4(Min[0], Min[1], Max[2], 1.f);
  obb_points[7] = to_clip_space_mat * vec4(Min[0], Min[1], Min[2], 1.f);

  bool outside = false, outside_positive_plane, outside_negative_plane;
  //имеем 6 плоскостей отсечения, 3 потому что тестируем 2 плоскости за раз (+1 и -1)
  for (int i = 0; i < 3; i++)
  {
    //находятся ли все 8 точек за плоскостью?
    //в общем то в приведенном коде можно было выполнить нормализацию координаты, делением на w (xyz / w),
    //после чего сравнить с -1 и 1. Если координаты < -1 или > 1, то объект вне фрустума
    outside_positive_plane =
      obb_points[0][i] > obb_points[0].w &&
      obb_points[1][i] > obb_points[1].w &&
      obb_points[2][i] > obb_points[2].w &&
      obb_points[3][i] > obb_points[3].w &&
      obb_points[4][i] > obb_points[4].w &&
      obb_points[5][i] > obb_points[5].w &&
      obb_points[6][i] > obb_points[6].w &&
      obb_points[7][i] > obb_points[7].w;

    //для DirectX для z координаты (i=3) следует сравнивать с 0
    outside_negative_plane =
       obb_points[0][i] < -obb_points[0].w &&
       obb_points[1][i] < -obb_points[1].w &&
       obb_points[2][i] < -obb_points[2].w &&
       obb_points[3][i] < -obb_points[3].w &&
       obb_points[4][i] < -obb_points[4].w &&
       obb_points[5][i] < -obb_points[5].w &&
       obb_points[6][i] < -obb_points[6].w &&
       obb_points[7][i] < -obb_points[7].w;

    outside = outside || outside_positive_plane || outside_negative_plane;
    //if (outside_positive_plane || outside_negative_plane)
      //return false;
  }
  return !outside;
  //return true;
}


Таблица 1. Кулинг 100к объектов. Intel Core i5-4460 3.2GHz. 1 Поток. Время в ms.

Simple Culling Sphere AABB OBB
Только кулинг 0,92 1,42 9,14
Весь кадр 1,94 2,5 10,3

Результаты очевидны. Чем сложнее вычисления тем медленнее. Зато получаем точнее кулинг. Кулинг OBB заметно медленнее кулинга сфер и AABB.

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

Также следует заметить что время всего кадра гораздо выше чем кулинг отдельно. В среднем чуть больше 1 ms. Сюда входит время пересылки данных видимых инстансов на GPU, несколько дипов и АПИ команд. Но тем не менее это необходимые действия.

Страницы: 1 2 3 4 5 Следующая »

8 февраля 2017

#Frustum Culling, #multithreading, #SSE


Обновление: 3 мая 2017

2001—2017 © GameDev.ru — Разработка игр