Оптимизация проверки SphereInFrustrum

Question

У меня есть эта функция SphereInFrustrum:

0.49%  int FrustumG::sphereInFrustum(Vec3 &p, float radius) {

        int result = INSIDE;
        float distance;

2.40%   for(int i=0; i < 6; i++) {
7.94%       distance = pl[i].distance(p);
12.21%      if (distance < -radius)
0.67%           return OUTSIDE;
3.67%       else if (distance < radius)
                result =  INTERSECT;
        }
        return(result);

       }

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

Спасибо

Если бы я указал минимальное и максимальное значения куба, это бы ускорило его?Я уверен, что должен быть способ сделать это без формулы расстояния с квадратным корнем израсходованного;

float Plane::distance(Vec3 &p) {

    return (d + normal.innerProduct(p));
}


float Vec3::innerProduct(Vec3 &v) {

    return (x * v.x + y * v.y + z * v.z);
}

Answer 1

Вы действительно выполняете этот код для каждой сферы? Если вы делаете, не удивительно, что это медленнее.

Вы должны использовать иерархический подход, который может отбирать целые части сцен за один вызов. Например, вы можете использовать квадродерево сфер.

Answer 2

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

Этот код действительно делает то, что вы хотите?

        int result = INSIDE;
        float distance;

2.40%   for(int i=0; i < 6; i++) {
7.94%       distance = pl[i].distance(p);
12.21%      if (distance < -radius)
0.67%           return OUTSIDE;
3.67%       else if (distance < radius)
                result =  INTERSECT;

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

То есть это возвращается рано, если у вас отрицательное расстояние меньше вашего отрицательного радиуса? Это действительно то, что вы хотите прямо здесь?

Answer 3

Несколько идей (в порядке возрастания сложности)

1. Устранить ветви - может быть быстрее (в зависимости от платформы и компилятора) вычислить все 6 расстоянийи вернуть на основе минимума из них.Например, на PowerPC minDist = (d < minDist) ? d : minDist можно вычислить с помощью инструкции fsel и избежать ветвлений.

2. Развернуть (часть I) - Развертывание цикла для всех шести плоскостей может дать компилятору больше шансов оптимизировать код (скрывая задержку инструкций).

3. Развернуть (часть II) - Можно ли обрабатывать несколько сфер одновременно?Опять же, вы можете скрыть некоторую задержку.

4. SIMD - Если вы не возражаете запачкать руки SIMD, вы можете сохранить"транспонировать" 3 самолета вместе в 4 квадраЭто позволяет более легко вычислять точечные продукты без необходимости выполнять «горизонтальные» операции SIMD.Символически это будет выглядеть так:

---

vec4 sphereX = sphere.splat(0);
vec4 sphereY = sphere.splat(1);
vec4 sphereZ = sphere.splat(2);

vec4 dot = sphereX * planesX; // planesX is the x components of 3 planes
dot += sphereY * planesY; 
dot += sphereZ * planesZ;
dot += planesDistance;
// dot now contains the results of 3 distances
// now do the same for the other 3 planes

---

Фактический код SIMD будет зависеть от платформы и компилятора.

Существуют также некоторые методыдля выполнения запросов frustum на kd-деревьях (т. е. MLRTA ) - я никогда не пробовал их, но это должно значительно сократить количество сфер, к которым нужно обращаться.

Надеюсь, чтоПомогите, дайте мне знать, если что-то неясно.