Вопрос о производительности для теста пересечения алгоритма трассировки лучей - PullRequest
Новая
       71

Вопрос о производительности для теста пересечения алгоритма трассировки лучей

0 голосов
/ 21 января 2019

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

В методе, который я проверяю для пересечения луча и объекта, я возвращаю структуру с расстоянием луча, пройденного до попадания, вектором положения попадания и вектором нормали или -1 для расстояние, если нет пересечения.

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

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

Мои варианты пока: сначала пройдитесь по массиву пересечений и исключите те с отрицательными расстояниями, затем найдите кратчайшее расстояние от остатков с помощью алгоритма сортировки (возможно, сортировка вставкой из-за быстрой реализации).

Или объедините их в один алгоритм и на каждом шаге сортировки проверяйте, отрицательно ли расстояние. 

typedef Point3f float[3];
typedef struct {
    float distance;
    Point3f point;
    Point3f normal;
} Intersection;

Intersection intersectObject (Ray-params, object) {
    Intersection intersection;
    //...
    if (hit) {
        intersection.distance = distance;
        intersection.point = point;
        intersection.normal = normal;
    } else {
        intersection.distance = -1.0f;
    }
    return intersection;
}

//loop over screen pixel
    Intersection* intersections;
    int amountIntersections;
    //loop over all objects
    //here I would handle the intersections
    if (amountIntersections) {
        //cast additional rays
    }

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

1 Ответ

0 голосов
/ 21 января 2019

Вот подход, который я успешно использовал для огромного количества объектов. (Специально для атомных моделей с шариковой ручкой; см. Мою страницу пользователя в Википедии для уравнений, которые я использовал для них.)

Сначала преобразуйте объекты в систему координат, где глаз находится в начале координат, и проецируемая плоскость параллельна плоскости xy с центром на положительной оси z. Это значительно упрощает необходимые уравнения, как вы можете видеть на приведенной выше странице.

Например, если у вас есть единичный луч n (т. Е. n · n = 1) и сфера радиуса r с центром в c , луч пересекает сферу тогда и только тогда, когда h ≥ 0,

ч = ( n · c ) 2 + r 2 - ( c · c )

и если да, то на расстоянии d ,

d = n · c ± sqrt ( h )

Если вы разработаете необходимый код и используете разумные временные переменные, вы увидите, что вы можете отклонять непересекающиеся сферы, используя восемь умножений и шесть сложений или вычитаний, и что это легко векторизуется по объектам с использованием встроенных функций SSE2 / AVX. (#include <x86intrin.h>). (То есть не пытайтесь использовать векторный регистр XMM / YMM для n или c , и вместо этого используйте каждый компонент регистра для другого объекта, вычисляя ч для 2/4/8 объектов одновременно.)

Для каждого луча сортируйте / выбирайте объекты для тестирования в соответствии с их известной минимальной координатой z (скажем, c z - r для сфер). Таким образом, когда вы найдете пересечение на расстоянии d , вы можете игнорировать все объекты с минимальной координатой z, превышающей d , потому что точка пересечения обязательно будет дальше, за уже известное пересечение.

Аналогично, вы должны игнорировать все пересечения, где расстояние меньше, чем расстояние до плоскости проекции (а это z d / n z , если плоскость имеет значение z = z d и нужно вычислять только один раз на луч), потому что эти пересечения находятся между глазом и плоскостью проекции. (Технически, тогда вы «врезались» во что-то, если думать о плоскости проекции как о камере.)

...