Я хорошо знаю алгоритмы марша/DDA, но вместо этого я хотел бы иметь возможность выполнять проверку пары voxel-ray в постоянное время без необходимости " маршем "через воксельное пространство. Как я могу это сделать?Найти, если луч пересекает вокселя без марширования
Чтобы было ясно, я не пытаюсь найти первый воксельной луч пересекает, а, учитывая луч и вокселей, определить, является ли ячейка этого VOXEL даже лежит в пределах пути лучевом.
Луч является P = O + t D, где P, O, D векторы и t положительное действительное. Существует пересечение с вокселем [x,y,z]x[x+1,y+1,z+1] если ниже система имеет решение:
x < Ox + t Dx < x + 1
y < Oy + t Dy < y + 1
z < Oz + t Dz < z + 1
0 < t
который перепишет для краткости (с x' = (x - Ox)/Dx ...)
x' < t < x"
y' < t < y"
z' < t < z"
0 < t
Если Dx < 0, неравенство должен быть отменено , Если Dx == 0, то неравенство вырождается в x < Ox < x + 1, что может быть определено непосредственно.
Повторите то же обсуждение для всех трех осей и проверьте, совместимы ли все скобки.
Например, для Dx, Dy, Dz > 0, вы должны иметь
max(0, x', y', z') < min(x", y", z").
Есть 27 комбинаций знаков, которые необходимо учитывать, которые разделены на три каскадных трехходовых сравнений.
В микро-оптимизации, вы можете изменить масштаб последнее неравенство на Dx Dy Dz и упростить, торговать подразделения для (быстрее) умножений.
Если многие лучи не пропускают воксел, вы можете немного ускорить процесс, используя ограничительную сферу. Предполагая, что воксельный центр C, радиус R вокселей и вектор D нормализуется, предварительно тест
(OC x D)² < R²
Вы можете использовать любой алгоритм пересечения Ray Box (AABB).
Если вам нужно пересечения координат, а затем выбрать 3D линию отсечения алгоритм
Я, конечно, мог бы, хотя они обобщены на любые AABB.В моем случае у меня есть дополнительное ограничение однородной сетки с целыми индексами, и я бы хотел поверить, что существует более эффективный вариант, чем создание AABB из каждой ячейки сетки, которую нужно протестировать, и подавать ее алгоритму AABB. – Textfield
Я не верю, что целые числа дают некоторый выигрыш. Более важно - сделать возможными предварительные вычисления для данного луча и сетки (например, оптимизированная секция Алго в связанной бумаге) – MBo
Я боюсь, что это невозможно. Воксели независимы и нет ярлыка. Если бы можно было предсказать, на каком вокселе вы приземляетесь без похода, это просто означало бы, что представление воксела было неуместным. –
Я хорошо знаю, что невозможно найти * первый * пересеченный воксел без марша, и это не то, что я пытаюсь сделать. Я просто пытаюсь найти, если * * * воксель когда-либо пересекается бесконечно длинным лучом, предполагая, что ничто не может блокировать луч. Я понимаю, что мой оригинальный язык был неясным, поэтому я отредактировал вопрос, чтобы лучше сообщить это различие. – Textfield