Вопрос по algorithm, graphics, geometry, rendering – Пересечение Луч-Треугольник

19

я видел этоБыстрое минимальное пересечение Луч / Треугольник от Moller и Trumbore часто рекомендуется.

Дело в том, что я неНе забывайте предварительно вычислять и хранить любые объемы данных, поскольку это ускоряет пересечение.

Итак, мой вопрос, не заботясь о памяти, каковы самые быстрые методы пересечения лучей и треугольников?

Изменить: я не буду перемещать треугольники, то есть это статическая сцена.

Я часто пользовался Fast Minimum Storage Ray / Triangle Intersecton от Moller и Trumbore. Но я впервые знаю газету. Я думаю, что для множества лучей и треугольников, кроме методов пространственного разделения, параллельный метод может рассматриваться одновременно. Я'Я делаю реализацию OpenCL, но я не знаю, кто-то уже сделал это. Вы слышали что-нибудь об этом? squid
@squid Вы можете попробовать посмотреть на LuxRender.с LuxRaysВот Ecir Hana

Ваш Ответ

4   ответа
9

самый эффективный способ ускорить процесс - это использовать ускоряющую структуру, чтобы уменьшить количество необходимых пересечений лучей и треугольников. Тем не менее, вы все еще хотите, чтобы ваши пересечения лучей и треугольников были быстрыми. Если ты'Если вы готовы предварительно вычислить материал, вы можете попробовать следующее:

Преобразуйте ваши лучевые линии и ваши треугольные края вPLUкоординаты cker, Это позволяет вам определить, проходит ли ваша лучевая линия через треугольник на 6 умножить / сложить 'с каждого края. Вам все равно нужно будет сравнить начальную и конечную точки вашего луча с плоскостью треугольника (при 4 умножить / сложить 'на точку), чтобы убедиться, что он действительно попадает в треугольник.

В худшем случае затраты времени выполнения составляют 26 умножить / добавить 'итого. Также обратите внимание, что вам нужно вычислять знак луч / край только один раз для комбинации луч / край, так что если выПересматривая сетку, вы можете использовать каждую оценку ребра дважды.

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

Спасибо. Любое изменение, неВы знаете, где живет пример кода? Кстати, какую структуру ускорения вы рекомендуете и почему? Ecir Hana
Несколько лет назад на современном уровне техники использовались высокооптимизированные k-d-деревья. Особенно для статичной сцены, это может быть вашим лучшим выбором. Пример кода, я нашел что-тоСоответствующий с гуглом. Никаких гарантий - бумага кажется староватой, но ее объяснения кажутся достаточно ясными, а ее контрольные показатели придают значительный плюсКод Cker. comingstorm
4

много ориентиры, и я могу с уверенностью сказать, чтобыстрый (опубликованный) метод изобретен Гавелом и Хероутом и представлен в их статье.Еще быстрее пересечение лучей и треугольников (с использованием SSE4), Четноебез использования SSE это примерно в два раза быстрее, чем MöЛлер и Трумбореалгоритм

Моя реализация C Havel-Herout:

typedef struct {
    vec3 n0; float d0;
    vec3 n1; float d1;
    vec3 n2; float d2;
} isect_hh_data;
void
isect_hh_pre(vec3 v0, vec3 v1, vec3 v2, isect_hh_data *D) {
    vec3 e1 = v3_sub(v1, v0);
    vec3 e2 = v3_sub(v2, v0);
    D->n0 = v3_cross(e1, e2);
    D->d0 = v3_dot(D->n0, v0);

    float inv_denom = 1 / v3_dot(D->n0, D->n0);

    D->n1 = v3_scale(v3_cross(e2, D->n0), inv_denom);
    D->d1 = -v3_dot(D->n1, v0);

    D->n2 = v3_scale(v3_cross(D->n0, e1), inv_denom);
    D->d2 = -v3_dot(D->n2, v0);
}
inline bool
isect_hh(vec3 o, vec3 d, float *t, vec2 *uv, isect_hh_data *D) {
    float det = v3_dot(D->n0, d);
    float dett = D->d0 - v3_dot(o, D->n0);
    vec3 wr = v3_add(v3_scale(o, det), v3_scale(d, dett));
    uv->x = v3_dot(wr, D->n1) + det * D->d1;
    uv->y = v3_dot(wr, D->n2) + det * D->d2;
    float tmpdet0 = det - uv->x - uv->y;
    int pdet0 = ((int_or_float)tmpdet0).i;
    int pdetu = ((int_or_float)uv->x).i;
    int pdetv = ((int_or_float)uv->y).i;
    pdet0 = pdet0 ^ pdetu;
    pdet0 = pdet0 | (pdetu ^ pdetv);
    if (pdet0 & 0x80000000)
        return false;
    float rdet = 1 / det;
    uv->x *= rdet;
    uv->y *= rdet;
    *t = dett * rdet;
    return *t >= ISECT_NEAR && *t <= ISECT_FAR;
}
2

//en.wikipedia.org/wiki/Octree) для разделения вашего трехмерного пространства на очень тонкие блоки. Чем тоньше разбиение, тем больше требуется памяти, но тем выше точность дерева.

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

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

Спасибо! Треугольники не будут двигаться. Проблема с Октри, и, может быть, я неправильно понимаю, что в одном листе может быть несколько треугольников, верно? В этом случае яМне все еще понадобится быстрая процедура пересечения. Ecir Hana
2

Основываясь на подсчете операций, выполненных до первого теста на отклонение, этот алгоритм немного менее эффективен, чем MT (MöLler & Trumbore) алгоритм, [...]. Однако алгоритм MT использует два перекрестных произведения, тогда как наш алгоритм использует только одно, а тот, который мы используем, вычисляет вектор нормали треугольника 'плоскость s, которая необходима для вычисления параметра линииРод-Айленд, Но, когда нормальные векторы были предварительно вычислены и сохранены для всех треугольников в сцене (что часто имеет место), наш алгоритм не должен был бы вычислять это перекрестное произведение вообще. Но в этом случае алгоритм MT по-прежнему вычисляет два перекрестных произведения и будет менее эффективным, чем наш алгоритм.

http://geomalgorithms.com/a06-_intersect-2.html

Похожие вопросы