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

Frustum Culling (2 стр)

Автор:

SSE.

SSE (Streaming SIMD Extensions). одной инструкцией выполняется действие сразу над некоторой группой однотипных операндов. SSE включает в архитектуру процессора восемь 128-битных регистров и набор инструкций для выполнения операция над данными.
Теоретически можно ускорить выполнение кода в 4 раза, т. к. выполняем операцию одновременно с 4мя операндами. Разумеется на практике прирост производительности будет меньше, за счет особенностей SSE:
    - не каждый алгоритм легко переводится на SSE.
    - нужно упаковывать данные соответствующим образом чтобы одновременно выполнять операцию над 4мя числами.
    - есть сложность вертикальных операций, вроде dot product.
    - нет условий. Используется так называемое статическое ветвление, когда выолняются одновременно 2 ветки кода. Но потом используется только одно.
    - загрузка данных в регистры и обратное сохранение в ячейки памяти.

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


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

Алгоритм кулинга сфер и AABB в целом идентичен  SphereInFrustum. За исключением того, что производим операции одновременно над 4мя объектами. Что очень удобно ложиться на архитектуру.

void sse_culling_spheres(BSphere *sphere_data, int num_objects, int *culling_res, vec4 *frustum_planes)
{
  float *sphere_data_ptr = reinterpret_cast<float*>(&sphere_data[0]);
  int *culling_res_sse = &culling_res[0];

  //для оптимизации вычислений, собираем xyzw компоненты в отдельные вектора
  __m128 zero_v = _mm_setzero_ps();
  __m128 frustum_planes_x[6];
  __m128 frustum_planes_y[6];
  __m128 frustum_planes_z[6];
  __m128 frustum_planes_d[6];
  int i, j;
  for (i = 0; i < 6; i++)
  {
    frustum_planes_x[i] = _mm_set1_ps(frustum_planes[i].x);
    frustum_planes_y[i] = _mm_set1_ps(frustum_planes[i].y);
    frustum_planes_z[i] = _mm_set1_ps(frustum_planes[i].z);
    frustum_planes_d[i] = _mm_set1_ps(frustum_planes[i].w);
  }

  //обрабатываем сразу 4 объекта за раз
  for (i = 0; i < num_objects; i += 4)
  {
    //загружаем данные окружающих сфер
    __m128 spheres_pos_x = _mm_load_ps(sphere_data_ptr);
    __m128 spheres_pos_y = _mm_load_ps(sphere_data_ptr + 4);
    __m128 spheres_pos_z = _mm_load_ps(sphere_data_ptr + 8);
    __m128 spheres_radius = _mm_load_ps(sphere_data_ptr + 12);
    sphere_data_ptr += 16;

    //но для вычислений нам нужно транспонировать данные в векторах,
    //чтобы собрать x, y, z и w координаты в отдельные вектора
    _MM_TRANSPOSE4_PS(spheres_pos_x, spheres_pos_y, spheres_pos_z, spheres_radius);

    //spheres_neg_radius = -spheres_radius
    __m128 spheres_neg_radius = _mm_sub_ps(zero_v, spheres_radius);

    __m128 intersection_res = _mm_setzero_ps(); // = 0

    for (j = 0; j < 6; j++) //нужно протестировать 6 плоскостей фрустума
    {
      //1. считаем расстояние от центра сферы дл плоскости. dot(sphere_pos.xyz, plane.xyz) + plane.w
      //2. если центр сферы находится за плоскостью и расстояние по модулю больше радиуса сферы,
         //то объект находится вне фрустума
      __m128 dot_x = _mm_mul_ps(spheres_pos_x, frustum_planes_x[j]); //sphere_pos_x * plane_x
      __m128 dot_y = _mm_mul_ps(spheres_pos_y, frustum_planes_y[j]); //sphere_pos_y * plane_y
      __m128 dot_z = _mm_mul_ps(spheres_pos_z, frustum_planes_z[j]); //sphere_pos_z * plane_z

      __m128 sum_xy = _mm_add_ps(dot_x, dot_y); //x+y
      __m128 sum_zw = _mm_add_ps(dot_z, frustum_planes_d[j]); //z+w

      //в distance_to_plane - расстояние от центров сфер до плоскости, dot(sphere_pos.xyz, plane.xyz) + plane.w
      //посчитанное для 4 сфер одновременно
      __m128 distance_to_plane = _mm_add_ps(sum_xy, sum_zw);

      //если расстояние < -sphere_r (т.е. сфера находится за плоскостью, на расстоянии большим чем радиус сферы)
      __m128 plane_res = _mm_cmple_ps(distance_to_plane, spheres_neg_radius);

      //если да - объект не попадает во фрустум
      intersection_res = _mm_or_ps(intersection_res, plane_res);
    }

    //сохраняем результат
    __m128i intersection_res_i = _mm_cvtps_epi32(intersection_res);
    _mm_store_si128((__m128i *)&culling_res_sse[i], intersection_res_i);
  }
}


SSE AABB-фрустум.

Алгоритм для AABB также идентичен исходному на с++. Аналогично sse кулинuу сфер производим операции одновременно над 4мя объектами.

void sse_culling_aabb(AABB *aabb_data, int num_objects, int *culling_res, vec4 *frustum_planes)
{
  float *aabb_data_ptr = reinterpret_cast<float*>(&aabb_data[0]);
  int *culling_res_sse = &culling_res[0];

  //для оптимизации вычислений, собираем xyzw компоненты в отдельные вектора
  __m128 zero_v = _mm_setzero_ps();
  __m128 frustum_planes_x[6];
  __m128 frustum_planes_y[6];
  __m128 frustum_planes_z[6];
  __m128 frustum_planes_d[6];
  int i, j;
  for (i = 0; i < 6; i++)
  {
    frustum_planes_x[i] = _mm_set1_ps(frustum_planes[i].x);
    frustum_planes_y[i] = _mm_set1_ps(frustum_planes[i].y);
    frustum_planes_z[i] = _mm_set1_ps(frustum_planes[i].z);
    frustum_planes_d[i] = _mm_set1_ps(frustum_planes[i].w);
  }

  __m128 zero = _mm_setzero_ps();
  //обрабатываем сразу 4 объекта за раз
  for (i = 0; i < num_objects; i += 4)
  {
    //загружаем данные объектов
    //загружаем в регистры aabb min
    __m128 aabb_min_x = _mm_load_ps(aabb_data_ptr);
    __m128 aabb_min_y = _mm_load_ps(aabb_data_ptr + 8);
    __m128 aabb_min_z = _mm_load_ps(aabb_data_ptr + 16);
    __m128 aabb_min_w = _mm_load_ps(aabb_data_ptr + 24);

    //загружаем в регистры aabb max
    __m128 aabb_max_x = _mm_load_ps(aabb_data_ptr + 4);
    __m128 aabb_max_y = _mm_load_ps(aabb_data_ptr + 12);
    __m128 aabb_max_z = _mm_load_ps(aabb_data_ptr + 20);
    __m128 aabb_max_w = _mm_load_ps(aabb_data_ptr + 28);

    aabb_data_ptr += 32;

    //в массиве aabb_data расположены вершины AABB (сразу в мировом пространстве!)
    //но для вычислений нам нужно иметь в векторах xxxx yyyy zzzz представление, просто транспонируем данные
    _MM_TRANSPOSE4_PS(aabb_min_x, aabb_min_y, aabb_min_z, aabb_min_w);
    _MM_TRANSPOSE4_PS(aabb_max_x, aabb_max_y, aabb_max_z, aabb_max_w);

    __m128 intersection_res = _mm_setzero_ps(); //=0
    for (j = 0; j < 6; j++) //plane index
    {
      //этот код идентичен тому что мы делали в с++ реализации
        //находим ближайшую вершину AABB к плоскости и проверяем находится ли она за плоскостью.
        //Если да - объект вне фрустума

      //dot product, отдельно для каждой координаты, для двух (min и max) вершин
      __m128 aabbMin_frustumPlane_x = _mm_mul_ps(aabb_min_x, frustum_planes_x[j]);
      __m128 aabbMin_frustumPlane_y = _mm_mul_ps(aabb_min_y, frustum_planes_y[j]);
      __m128 aabbMin_frustumPlane_z = _mm_mul_ps(aabb_min_z, frustum_planes_z[j]);

      __m128 aabbMax_frustumPlane_x = _mm_mul_ps(aabb_max_x, frustum_planes_x[j]);
      __m128 aabbMax_frustumPlane_y = _mm_mul_ps(aabb_max_y, frustum_planes_y[j]);
      __m128 aabbMax_frustumPlane_z = _mm_mul_ps(aabb_max_z, frustum_planes_z[j]);

      //мы имеем 8 вершин в боксе, но нам нужно выбрать одну ближайшуй к плоскости.
      //Берем максимальное значение по каждой компоненте, это и даст нам ближайшую точку
      __m128 res_x = _mm_max_ps(aabbMin_frustumPlane_x, aabbMax_frustumPlane_x);
      __m128 res_y = _mm_max_ps(aabbMin_frustumPlane_y, aabbMax_frustumPlane_y);
      __m128 res_z = _mm_max_ps(aabbMin_frustumPlane_z, aabbMax_frustumPlane_z);

      //считаем расстояние дл плоскости = dot(aabb_point.xyz, plane.xyz) + plane.w
      __m128 sum_xy = _mm_add_ps(res_x, res_y);
      __m128 sum_zw = _mm_add_ps(res_z, frustum_planes_d[j]);
      __m128 distance_to_plane = _mm_add_ps(sum_xy, sum_zw);

      __m128 plane_res = _mm_cmple_ps(distance_to_plane, zero); //расстояние до плоскости < 0 ?
      intersection_res = _mm_or_ps(intersection_res, plane_res); //если да, то объект вне врустума
    }

    //сохраняем результат
    __m128i intersection_res_i = _mm_cvtps_epi32(intersection_res);
    _mm_store_si128((__m128i *)&culling_res_sse[i], intersection_res_i);
  }
}

SSE OBB-фрустум.

Кулинг OBB немного сложнее. Мы производим вычисления над одним объектом. Но при этом проводим вычисления одновременно над тремя осями xyz. Это не самый оптимальный алгоритм, но он передает общую идею алгоритма. К тому же векторная математика (умножение матриц и трансформация векторов) с использованием SSE выполняются быстрее.

void sse_culling_obb(int firs_processing_object, int num_objects, int *culling_res, mat4 &cam_modelview_proj_mat)
{
  mat4_sse sse_camera_mat(cam_modelview_proj_mat);
  mat4_sse sse_clip_space_mat;

//вершины бокса в локальных координатах
  __m128 obb_points_sse[8];
  obb_points_sse[0] = _mm_set_ps(1.f, box_min[2], box_max[1], box_min[0]);
  obb_points_sse[1] = _mm_set_ps(1.f, box_max[2], box_max[1], box_min[0]);
  obb_points_sse[2] = _mm_set_ps(1.f, box_max[2], box_max[1], box_max[0]);
  obb_points_sse[3] = _mm_set_ps(1.f, box_min[2], box_max[1], box_max[0]);
  obb_points_sse[4] = _mm_set_ps(1.f, box_min[2], box_min[1], box_max[0]);
  obb_points_sse[5] = _mm_set_ps(1.f, box_max[2], box_min[1], box_max[0]);
  obb_points_sse[6] = _mm_set_ps(1.f, box_max[2], box_min[1], box_min[0]);
  obb_points_sse[7] = _mm_set_ps(1.f, box_min[2], box_min[1], box_min[0]);

  ALIGN_SSE int obj_culling_res[4];

  __m128 zero_v = _mm_setzero_ps();
  int i, j;

  //производим вычисления над одним объектов за раз
  for (i = firs_processing_object; i < firs_processing_object+num_objects; i++)
  {
  //матрица перевода координат сразу в clip space, space matrix = camera_view_proj * obj_mat
    sse_mat4_mul(sse_clip_space_mat, sse_camera_mat, sse_obj_mat[i]);

    //тут внимательно: в _mm_set1_ps() нужно передать именно отрицательное число
    //потому-что _mm_movemask_ps (при сохранении результата) проверяет 'первый значащий бит' (у float'а это знак)
    __m128 outside_positive_plane = _mm_set1_ps(-1.f);
    __m128 outside_negative_plane = _mm_set1_ps(-1.f);

    //для всех 8 точек
    for (j = 0; j < 8; j++)
    {
    //трансформируем в clip space (умножение вектора на матрицу)
      __m128 obb_transformed_point = sse_mat4_mul_vec4(sse_clip_space_mat, obb_points_sse[j]);

    //собираем w и -w в отдельные вектора, чтобы быстро сравнивать
      __m128 wwww = _mm_shuffle_ps(obb_transformed_point, obb_transformed_point, _MM_SHUFFLE(3, 3, 3, 3));
      __m128 wwww_neg = _mm_sub_ps(zero_v, wwww); //получаем -w-w-w-w

    //box_point.xyz > box_point.w || box_point.xyz < -box_point.w ?
    //можно нормализовать координаты (point.xyz /= point.w;) Затем сравнить с -1 и 1. point.xyz > 1 && point.xyz < -1
      __m128 outside_pos_plane = _mm_cmpge_ps(obb_transformed_point, wwww);
      __m128 outside_neg_plane = _mm_cmple_ps(obb_transformed_point, wwww_neg);

    //если хотя бы 1 из 8 вершин спереди плоскости, то получим 0 в outside_* flag.
      outside_positive_plane = _mm_and_ps(outside_positive_plane, outside_pos_plane);
      outside_negative_plane = _mm_and_ps(outside_negative_plane, outside_neg_plane);
    }

    //находятся ли все 8 вершин за какой плоскостью, по 3м осям результат хранится отдельно
    __m128 outside = _mm_or_ps(outside_positive_plane, outside_negative_plane);

    //сохраняем результат
    //сейчас у нас результат хранится отдельно по каждой оси
    //нужно скомбинировать результаты. Если хотя бы по одной оси все 8 вершин либо >1 либо < 1
    //то объект находится вне области видимости / фрустума
    //другими словами, если outside[0, 1 или 2] не 0... то по одной из осей наш объект вне фрустума
    culling_res[i] = _mm_movemask_ps(outside) & 0x7; // & 0x7 потому что интересуют только 3 оси
  }
}

Таблица 2. Результаты: кулинг 100к объектов. Intel Core i5-4460. 1 поток. SSE. Время в ms

SSE Culling Sphere AABB OBB
Только кулинг 0,26 0,46 3,48
Весь кадр 1,2 1,43 4,6

Реализация на SSE в среднем в 3 раза быстрее чем аналогичная на с++.

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

8 февраля 2017

#Frustum Culling, #multithreading, #SSE


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

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