Отсечение невидимой геометрии (14 стр) / Графика / Форум / Программирование игр / GameDev.ru

u960
> а то гуглиться много всего(
Daniil Petrov
>Я тоже ничего не нашёл :)
https://github.com/id-Software/DOOM-3/blob/a9c49da5afb18201d31e3f… stum.cpp#L150
Но там для новичка сложновато наверное

Начнем с простого:
frustum описывается 6ю плоскостями, которые извлекаются из матрицы вида-проекции
Для определения факта нахождения точки в пирамиде видимости достаточно проверить дистанцию от этой точки до каждой из плоскостей.
Дистанция может быть как положительной, так и отрицательной, что позволяет узнать находиться ли точка перед или за плоскостью.
В случае со сферой нужно учитывать радиус.
В случае с боксом проверяем все точки.

Пример реализации:

// VECTOR3

// Скалярное произведение векторов (dot product)
float Vector3::Dot(const Vector3& _rhs) const 
{ 
  return x * _rhs.x + y * _rhs.y + z * _rhs.z;
}

// PLANE

// Нормализация плоскости
void Plane::Normalize()
{
  float _length = normal.Length(); // sqrtf(x*x+y*y+z*z)
  if (_length > EPSILON2)
  {
    _length = 1 / _length;
    normal *= _length;
    dist *= _length;
  }
}

// Дистанция до плоскости
float Plane::Distance(const Vector3& _point) const
{
  return normal.Dot(_point) + dist;
}

// Дистанция до сферы
float Plane::Distance(const Vector3& _center, float _radius) const
{
  float _d = normal.Dot(_center) + dist;
  float _md = normal.AbsDot(_radius); // abs(x*_rhs.x)+ abs(y*_rhs.y)+ abs(z*_rhs.z) 
  return (Abs(_md) < Abs(_d)) ? _d : 0;
}

// AABB

// Получить все точки AABB
void AlignedBox::GetAllCorners(Vector3* _dst) const
{
  static const uint8 _idx[8][3] =
  {
    { 0, 1, 2 }, // mn.x, mn.y, mn.z  LeftBottomFar
    { 3, 1, 2 }, // mx.x, mn.y, mn.z  RightBottomFar
    { 3, 1, 5 }, // mx.x, mn.y, mx.z  RightBottomNear
    { 0, 1, 5 }, // mn.x, mn.y, mx.z  LeftBottomNear
    { 3, 4, 5 }, // mx.x, mx.y, mx.z  RightTopNear
    { 0, 4, 5 }, // mn.x, mx.y, mx.z  LeftTopNear
    { 0, 4, 2 }, // mn.x, mx.y, mn.z  LeftTopFar
    { 3, 4, 2 }, // mx.x, mx.y, mn.z  RightTopFar
  };

  const float* _v = &mn.x; 
  for (uint i = 0; i < 8; ++i)
    _dst[i] = Vector3(_v[_idx[i][0]], _v[_idx[i][1]], _v[_idx[i][2]]);
}

// Центр AABB
Vector3 AlignedBox::Center(void) const
{ 
  return (mx + mn) * 0.5f; 
}

// Радиус AABB
float AlignedBox::Radius(void) const
{
   return (mx - mn).Length() * 0.5f; // Diagonal() * 0.5f; 
}

// FRUSTUM

// Проверяем точку
bool Frustum::Intersects(const Vector3& _point) const
{
  for (uint i = 0; i < 6; ++i)
  {
    if (planes[i].Distance(_point) < 0)
      return false; // точка лежит за плоскостью
  }
  return true;
}

// Проверяем сферу
bool Frustum::Intersects(const Vector3& _center, float _radius) const
{
  for (uint i = 0; i < 6; ++i)
  {
    if (planes[i].Distance(_center, _radius) < 0) 
      return false; // точка лежит за плоскостью на дистанции больше радиуса сферы
  }
  return true;
}

// Проверяем факт пересечения с боксом
bool Frustum::Intersects(const AlignedBox& _box) const
{
  if (Intersects(_box.Center(), _box.Radius())) // сначала проверим возможность пересечения (делать не обязательно)
  {
    Vector3 _corners[8];
    _box.GetAllCorners(_corners); // получим все точки бокса
    
    for (uint i = 0; i < 6; ++i) // проверяем каждую плоскость
    {    
      int _outside = 0;
      for (uint j = 0; j < 8; ++j) // проверяем каждую точку
      {
        if(planes[i].Distance(_corners[j]) < 0)
          ++_outside; // точка находится за плоскостью
      }
      if (_outside == 8)
        return false; // все точки бокса находятся за одной из плоскостей - нет пересечения
    }
    return true; 
  }
  return false;
}

когда я понял что у меня объекты рисуются быстрее чем отсекаются, я отсекать перестал))

> когда я понял что у меня объекты рисуются быстрее чем отсекаются, я отсекать перестал))
Misanthrope, так я ж говорю - это дурь ) Люди сидят и выжимают наносекунды на куллинге (это, причём, в 10% случаев, в остальных - пессимизация кода), зато никто не сделает даже просто минимальный батчинг ))
Оптимизаторы хреновы xD

u960
> а что именно,где смотреть, а то гуглиться много всего(
Да хотябы сурсы ку3 или третьего дума)

Misanthrope
> когда я понял что у меня объекты рисуются быстрее чем отсекаются, я отсекать
> перестал))

Эх, были времена...
https://habrahabr.ru/post/321986/

Daniil Petrov
> Таки неправильно - всё исчезает!
Ну это при условии что весь код правильный, а всё равно почему-то не работает. Там надо смотреть какой ты используешь формат плоскостей.
В OpenGL стандартные плоскости, я ж чего и предположил.

Daniil Petrov
> В коде бы я ещё разобрался, но тут ещё и математика
В движках очень простая математика, если конечно речь не идет о рассчёте непрямого освещения. Выучи основные действия над векторами, кросс, дот и быстро разберёшься.

g-cont
> Выучи основные действия над векторами, кросс, дот и быстро разберёшься.
Так а никуда без этого не денешься :) разбираюсь потихоньку.
Тем более, что оно всё и в шейдерах то же самое идёт.

http://www.gamedev.ru/flame/forum/?id=229195&page=5#m64

Откровение сегодняшнего дня. Вершина пирамиды отсечения перспективной процекции в World Space находится между позицией камеры и передней отсекающей плоскостью.

Т.е. Camera Position != Top of the Frustum.

Как же я "люблю" 3d математику

Представьте, что я сижу такой за партой и тяну руку :))) "А можно, а можно???"
Я только сейчас вдумался - портал - это отсечение кучки объектов проверкой всего одного параллелепипеда или многоугольника :) да?
Сначала думал, что это слишком геморройно бить всё на порталы, но на самом деле оказывается очень эффективно для таких хитов, как Corridor 7 или Wolfenstein 3D :)))
P.S. Хотя для этого нужно сортировать объекты по порталам, да? Или хотя бы присваивать им номер портала и сверять с ними :)