Пересечение луча-треугольника

17

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

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

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

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

    
задан Ecir Hana 31.10.2012 в 18:03
источник
  • Я использовал быстрый минимальный ремень памяти / треугольник Intersecton от Moller и Trumbore. Но это первый раз, когда я знаю газету. Я думаю, что для множества лучей и треугольников, помимо методов разделения пространства, параллельный метод можно рассматривать одновременно. Я выполняю реализацию OpenCL, но я не знаю, кто-то уже это сделал. Вы что-то слышали об этом? –  squid 22.10.2014 в 17:26
  • @squid Вы можете попробовать посмотреть LuxRender LuxRays здесь –  Ecir Hana 22.10.2014 в 17:40

4 ответа

9

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

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

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

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

    
ответ дан comingstorm 31.10.2012 в 22:35
  • Спасибо. Какими изменениями вы не знаете, где живет пример кода? Btw., Какую структуру ускорения вы рекомендуете и почему? –  Ecir Hana 01.11.2012 в 09:59
  • Несколько лет назад на современном уровне техники использовались сильно оптимизированные деревья k-d. Особенно для статической сцены, это может быть вашим лучшим выбором. Повторите пример кода, я нашел что-то актуальное с Google. Никаких гарантий - бумага кажется старой, но ее объяснения кажутся достаточно ясными, а ее контрольные показатели приписывают существенный краю к коду Плюккера. –  comingstorm 01.11.2012 в 21:54
  • Спасибо! Очень полезно! –  Ecir Hana 02.11.2012 в 00:11
4

Я выполнил тесты lot , и я могу с уверенностью сказать, что самый быстрый (опубликованный) метод - тот, который был изобретен Гавелом и Хероутом и представлен в их статье Тем не менее, более быстрое пересечение лучей треугольника (с использованием SSE4) . Даже без использования SSE он примерно в два раза быстрее, чем алгоритм Möller и Trumbore.

Моя реализация 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;
}
    
ответ дан Björn Lindqvist 30.06.2017 в 04:33
2

Одним из предложений может быть реализация алгоритма octree (http://en.wikipedia.org/wiki/Octree) для разбиения 3D-пространства на очень мелкие блоки. Чем более тонкое разделение, тем больше требуется памяти, но тем лучше получается дерево.

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

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

ответ дан Simon Ejsing 31.10.2012 в 18:13
  • Спасибо! Треугольники не будут двигаться. Дело с Octree и, может быть, я неправильно понял, что в одном листе может быть несколько треугольников, верно? В этом случае мне по-прежнему нужна быстрая процедура пересечения. –  Ecir Hana 31.10.2012 в 18:34
2

Нашел эту статью Дэн Воскресенье:

  

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

Ссылка

    
ответ дан Jack 01.11.2014 в 03:05