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

Question

Например:

Подход для эффективного вычисления первого пересечения между лучом наблюдения и набором из трех объектов: одной сферы, одного конуса и одного цилиндра (другие трехмерные примитивы).

Answer 1

Что вам нужно, так это схема пространственного разделения. Есть много вариантов для решения этой проблемы, а также много исследований, проведенных в этой области. Хорошее чтение будет Обнаружение столкновений в реальном времени Кристер Эрикссон .

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

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

Другими интересными схемами разбиения являются различные древовидные структуры, такие как kd- , Oct- и BSP-деревья . Вы могли бы даже рассмотреть использование деревьев в сочетании с сеткой.

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

Answer 2

«вычислительно эффективен» зависит от размера набора.

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

Для больших наборов посмотрите на структуры данных, которые делят пространство (например, KD-Trees). Целые главы (и даже целые книги) посвящены этой проблеме. Мой любимый справочник - Введение в трассировку лучей (ред. Эндрю С. Гласснер)

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

Answer 3

Ну, это зависит от того, что вы действительно пытаетесь сделать. Если вы хотите создать решение, подходящее практически для каждого пикселя в простой сцене, чрезвычайно быстрый метод заключается в том, чтобы предварительно рассчитать «что впереди» для каждого пикселя, предварительно выполнив рендеринг всех объектов с уникальной идентификацией. цвет в буфер фонового элемента с помощью преобразования сканирования (он же z-буфер). Иногда это называется буфером элементов.

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

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

PS: я впервые прочитал об идее буфера элементов, когда делал поиск литературы в начале 90-х. Первоначально я обнаружил, что это упомянуто в (я полагаю) статье ACM конца 70-х годов. К сожалению, у меня нет ссылки на источник, но, короче говоря, это очень старая идея, которая очень хорошо работает на оборудовании для преобразования сканирования.

Answer 4

Я предполагаю, что у вас есть луч d = (dx, dy, dz), начинающийся с o = (ox, oy, oz), и вы находите параметр t такой, что точка пересечения p = o + d * t , (Как и эта страница , которая описывает пересечение плоскости луча с использованием P2-P1 для d, P1 для o и u для t)

Первый вопрос, который я хотел бы задать, - "Пересекаются ли эти объекты"?

Если нет, то вы можете немного обмануть и проверить по порядку столкновения лучей. Поскольку у вас есть три объекта, которые могут перемещаться или не перемещаться за кадр, стоит предварительно рассчитать их расстояние от камеры (например, от их центральных точек). Проверяйте каждый объект по очереди на расстоянии от камеры от наименьшего к наибольшему. Хотя пустое пространство является самой дорогой частью рендеринга в настоящее время, это более эффективно, чем просто тестирование по всем трем и принятие минимального значения. Если у вашего изображения высокое разрешение, это особенно эффективно, поскольку вы амортизируете стоимость по количеству пикселей.

В противном случае проверить все три и принять минимальное значение ...

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