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

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

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

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

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

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

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

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

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

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

Ну, это зависит от того, что вы действительно пытаетесь сделать. Если вы хотите получить решение, правильное почти для каждого пикселя в простой сцене, чрезвычайно быстрый метод состоит в том, чтобы предварительно вычислить «что впереди» для каждого пикселя путем предварительного рендеринга всех объектов с уникальным идентификатором. цвет в буфер фонового элемента, используя преобразование сканирования (также известное как 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)

Первый вопрос, который я бы задал: «Пересекаются ли эти объекты»?

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

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

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