Пересечение вершин 3D-сетки

Question

Представьте себе огромную трехмерную сетку (с точки зрения процедур и потенциально бесконечную, по крайней мере, 10^6 координат на каждую сторону). У каждой координаты сетки есть примитив (например, сфера, ящик или какая-либо другая простая, легко математически определенная функция).

Мне нужен алгоритм для пересечения луча с началом вне сетки и направлением, входящим в него, против элементов сетки. I., луч может перемещаться на полпути через эту огромную сетку, а затем ударить примитива. Из-за объема сетки итеративный метод [EDIT: (например, марширование луча)] неприемлемо медленный. Мне нужна некоторая закрытая форма [EDIT: постоянное время] решение для поиска примитивного хита.

Один из возможных подходов я думал, чтобы определить количество луча бы сходиться каждый раз шаг к примитивам на каждом из восьми координат окружающей ячейки сетки в некотором модульном арифметическом пространстве в каждом из х, у , и z, затем делим на направление луча и занимаем наименьшее расстояние. У меня нет никаких доказательств, кроме интуиции, чтобы думать, что это может сработать, а Google бесполезен; «пересечение сетки» означает пересечение линий сетки лиц.

Примечание:

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

Спасибо,
Ian

Answer 1

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

Это не быстро, поэтому здесь вам нужно будет сделать большую оптимизацию. Самое очевидное - использовать ограничивающие поля вместо реальных фигур. Оттуда вы можете делать такие вещи, как использовать Octrees или BST (двоичное пространственное разделение).

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

Answer 2

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

Итереть вместо кубов сетки, пересекающих линию, и для каждого куба испытайте 8 объектов, пересекающих куб. Посмотрите на Bresenham's line drawing algorithm, как найти, какие кубы пересекает линия. Обратите внимание, что Bresenham's не вернет абсолютно каждый куб, который пересекает луч, но для определения того, какие примитивы для тестирования я уверен, что он будет достаточно хорош. Он также имеет хорошие свойства:

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

Answer 3

Попробуйте этот подход:

1. Определить функцию луча;

2. Скажем, что сетка разделена на разные плоскости по оси z, луч будет пересекаться с каждой плоскостью z (плоскость, где лежат узлы сетки на одной высоте), и вы можете легко вычислить координату (x, y, z) точек пересечения от лучевой функции;

3. Проведите по плоскости z, вы можете легко определить, какие точки пересечения лежат в кубике или сфере;

4. Но луч может пересекаться с кубиками/сферами между плоскостями z, поэтому вам нужно повторить 1-3 шага по осям x, y. Это гарантирует, что пересечение не будет остановлено.

5. Выбросить повторяющиеся кубики/сферы, найденные по направлениям поиска x, y, z.

Answer 4

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

p=p0 + t * v 

где p0 является отправной точкой и v является направление вектора луча, мы можем построить расстояние от луча до целочисленное значение на каждой оси в зависимости от t. например:

dx = abs((p0.x + t * v.x + 0.5) % 1 - 0.5) 

Это даст три пилообразные участки, периоды которых зависит от компонентов вектора направления (например, если направление вектора является (1, 0, 0), х-участок будет изменяться линейно между 0 и 0,5, с периодом 1, в то время как другие графики останутся постоянными при любых значениях p0.

Вам нужно найти первое значение t, для которого все три графика находятся ниже некоторого порогового уровня, определенного размером вашего примитивов. Таким образом, вы можете значительно уменьшить количество значений t, которые нужно проверить, рассмотрев график с самым длинным (без бесконечного) периода, прежде чем проверять высокочастотные графики.

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