Каков наилучший подход для эффективного вычисления первого пересечения между лучом наблюдения и набором объектов?
Например:
Подход для эффективного вычисления первого пересечения между лучом наблюдения и набором из трех объектов: одной сферы, одного конуса и одного цилиндра (другие трехмерные примитивы).
4 ответа
То, что вы ищете, это схема пространственного разделения. Есть много вариантов для решения этой проблемы, а также много исследований, проведенных в этой области. Хорошее чтение будет в режиме реального времени обнаружения столкновений Кристер Эрикссон.
Один из простых подходов, рассматриваемых в этой книге, заключается в определении сетки, назначении всех объектов всем ячейкам, которые она пересекает, и прохождении вдоль ячеек сетки, пересекающих линию спереди назад, пересекающихся с каждым объектом, связанным с этой ячейкой сетки. Имейте в виду, что объект может быть связан с большим количеством ячеек сетки, поэтому вычисленная точка пересечения может фактически находиться не в текущей ячейке, а на самом деле позже.
Следующий вопрос будет, как вы определяете эту сетку. К сожалению, нет единого хорошего ответа, и вам нужно подумать, какой подход лучше всего подходит для вашего сценария.
Другими интересными схемами разбиения являются различные древовидные структуры, такие как kd-, Oct- и BSP-деревья. Вы могли бы даже рассмотреть использование деревьев в сочетании с сеткой.
РЕДАКТИРОВАТЬ
Как уже указывалось, если ваш набор на самом деле состоит из этих трех объектов, вам определенно лучше просто пересечь каждый из них и выбрать самый ранний. Если вы ищете лучевую сферу, лучевой цилиндр и т. Д., Тесты на пересечение, это не очень сложно, и быстрый Google должен предоставить всю математику, которая может вам понадобиться.:)
"вычислительно эффективный" зависит от того, насколько велик набор.
Для тривиального набора из трех, просто протестируйте каждый из них по очереди, действительно не стоит пытаться оптимизировать.
Для больших наборов посмотрите на структуры данных, которые делят пространство (например, KD-Trees). Целые главы (и даже целые книги) посвящены этой проблеме. Мой любимый справочник - "Введение в трассировку лучей" (изд. Эндрю С. Гласснер)
В качестве альтернативы, если я неправильно прочитал ваш вопрос и вы на самом деле спрашиваете алгоритмы пересечения луч-объект для определенных типов объектов, посмотрите ту же книгу!
Ну, это зависит от того, что вы действительно пытаетесь сделать. Если вы хотите создать решение, которое подходит практически для каждого пикселя в простой сцене, чрезвычайно быстрый метод состоит в том, чтобы предварительно рассчитать "что впереди" для каждого пикселя, предварительно выполнив рендеринг всех объектов с уникальной идентификацией. цвет в буфер фона элемента с помощью преобразования сканирования (он же z-буфер). Это иногда называют буфером элементов.
Используя это предварительное вычисление, вы узнаете, что будет видно практически для всех лучей, которые вы будете снимать на сцену. В результате ваша проблема пересечения луча с окружающей средой значительно упрощается: каждый луч попадает в один конкретный объект.
Когда я делал это много лет назад, я производил в реальном времени трассированные лучами изображения по общему признанию простых сцен. Я давно не пересматривал этот код, но подозреваю, что с современными компиляторами и графическим оборудованием производительность будет на порядок выше, чем я видел тогда.
PS: я впервые прочитал об идее буфера элементов, когда занимался поиском литературы в начале 90-х. Первоначально я обнаружил, что это упомянуто в (я полагаю) статье ACM конца 70-х годов. К сожалению, у меня нет ссылки на источник, но, короче говоря, это очень старая идея, которая очень хорошо работает на оборудовании для преобразования сканирования.
Я предполагаю, что у вас есть луч d = (dx,dy,dz), начинающийся с o = (ox,oy,oz), и вы находите параметр t такой, что точка пересечения p = o+d*t. (Как эта страница, которая описывает пересечение плоскости луча, используя P2-P1 для d, P1 для o и u для t)
Первый вопрос, который я хотел бы задать: "Пересекаются ли эти объекты"?
Если нет, то вы можете немного обмануть и проверить на предмет столкновения лучей по порядку. Поскольку у вас есть три объекта, которые могут перемещаться или не перемещаться в кадре, стоит предварительно рассчитать их расстояние от камеры (например, от их центральных точек). Проверяйте каждый объект по очереди, на расстоянии от камеры, от самого маленького до самого большого. Хотя пустое пространство сейчас является самой дорогой частью рендеринга, это более эффективно, чем просто тестирование по всем трем и принятие минимального значения. Если у вашего изображения высокое разрешение, это особенно эффективно, поскольку вы амортизируете стоимость по количеству пикселей.
В противном случае проверьте все три и примите минимальное значение...
В других ситуациях вы можете захотеть сделать гибрид этих двух методов. Если вы можете проверить два объекта по порядку, то сделайте это (например, сфера и куб, движущийся по цилиндрическому туннелю), но проверьте третий и возьмите минимальное значение, чтобы найти конечный объект.