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; }

__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; }

__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; }

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

Simple Culling

Sphere

AABB

OBB

Только кулинг

0,92

1,42

9,14

Весь кадр

1,94

2,5

10,3