Отображение точек сплошного прямоугольника в четырехгранный сетчатый прямоугольник

Дана 3d сплошная коробка с точками в ней. Дана коробка с тетраэдой. Размеры обеих коробок одинаковы.

Мне нужно найти алгоритм, который отображает точки твердого тела в соответствующие тетраэдры в сетке.

Я использовал следующий алгоритм:

  1. Уточнение твердого тела с октри
  2. Выполните итерацию по тетраэдрам в сетке и проверьте, пересекается ли она с ветвью или выходом из октодерева. (Алгоритм Ращека и Рокна)
  3. Если он пересекается, отобразите точки от октодерева до тетраэдра.

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

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

ОБНОВЛЕНИЕ: у меня есть 2 миллиона твердых точек и 200 тысяч тетраэдров

ОБНОВЛЕНИЕ 2: я пытаюсь реализовать Ходьба в триангуляции

Источник

2 ответа

Решение

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

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

Чтобы подвести итог:

Form an octree T for your points X

for (all tetrahedrons ti in mesh M)

    Form a minimal axis-aligned bounding-box Bi for tetrahedron ti

    Traverse T from root, accumulating a list Li of all leaf nodes 
    that overlap with box Bi

    for (all leaf nodes li in list L)
        for (all points pi in leaf node li)

            if (point pi is inside tetrahedron ti /*exact test*/ )
                Associate point pi with tetrahedron ti
            endif

        endfor
    endfor

endfor

Этот алгоритм эффективен, если: (i) точки X хорошо распределены внутри сетки M, а также (ii) тетраэдры в M имеют разумные пропорции.

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

Проверка точки в тетраэдре может быть выполнена путем проверки, является ли данная точка pi лежит на "внутренней" стороне четырех граней тетраэдра. Учитывая тетраэдр [i,j,k,l], точка pi находится на "внутренней" стороне лица [i,j,k] если он лежит на одной стороне плоскости [i,j,k] как "противоположная" вершина l,

Эти тесты ориентации могут быть выполнены надежно, используя адаптивную точность арифметики. Джонатан Шевчук предлагает такую ​​реализацию здесь.

Источник

Предполагая, что вы знаете вершины тетраэдров, вы можете проверить, находится ли точка внутри тетраэдра, проверив, лежит ли она в left или же rightсторона каждой из его плоскостей, скажем, слева - сторона, направленная вдоль нормали.

Математика для определения, находится ли точка слева или справа от плоскости, является прямой.

Есть другой метод, который я нашел, но выглядит как вариант моего ответа.

Конечно, если точка находится в тете, она отображается в тет. Этот метод может быть реализован как вершинный шейдер или как ядро ​​OpenCL/CUDA, и это сделает его очень параллельным.

Источник
Другие вопросы по тегам