Сталкиваются с локусом сетки

Question

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

TL; DR, пожалуйста, предоставьте вариант классического алгоритма пересечения сегмента линия ->- треугольник, который тоже возвращает почти промахы, или решите задачу другим способом. Сегмент линии пересекается, если он проходит в пределах заданного расстояния треугольника. В этой проблеме много тонкости, например, закругленные углы локуса треугольника и если отрезок прямой является касательным к треугольнику.

У меня есть обычный код пересечения луч / треугольник.

Однако луч - очень плохое приближение движущегося игрока! У меня проблемы с отсутствующими краями центра игрока, но через них проходит сетка игрока.

Как эффективно определить, когда и где игрок сталкивается со стенами и препятствиями в трехмерной среде?

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

Общее решение, которое я попытался сделать, - представить игрока как сферу; вывернув это наизнанку, я попытался создать сетку, радиус которой больше, чем у реальных стен, и сделать на ней лучи столкновения. Я хочу вычислить сетку, которая находится на некотором фиксированном расстоянии перед этой сеткой, то есть куб расширится, чтобы стать немного большим кубом с закругленными краями и углами. (Мои сетки не так регулярны, как куб. Представьте сетку, представляющую внутреннюю часть котельной, и представьте, что вы пытаетесь вычислить сетку, которая находится на расстоянии 20 см от всех стен, котлов и дверных коробок и тому подобного в этой комнате.) Вот простая сетка вокруг бочки:

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

Мой мозговой штурм заставляет меня вообразить умножение нормали каждого лица на фиксированное расстояние и затем испускание треугольника с соответствующим смещением.

Это, однако, оставит отверстия по краям и, возможно, (?) Заставит некоторые края проходить через очень узкие острые углы?

Я также могу представить соединение каждого края в виде шариковых цилиндров и так далее.

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

Я буду вычислять эту сетку, а затем выполнять пересечения лучей в Javacsript. Так что производительность тоже важна. Слишком мелкая детализированная сетка будет дорогой для обнаружения столкновений.

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

Answer 1

(никто не взял награду:( Натан Рид из gamedev.stackexchange помог с терминологией. Она называется пересечением капсулы и треугольника.)

Его удивительно сложная математика и поиск в Google не находят много готового кода для копирования.

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

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

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

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

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