Введение
Думаю многие кто промышляли разработкой игровых движков сталкивались с такой веселой но жизненно необходимой для движка вещью как физика твердых тел. Хороший движок просто обязан делать за разработчика игр такие граничащие с фантастикой вещи как красивое сталкивание игровых объектов, поскольку реалистичная физика привычна игрокам и удобна в использовании. Объекты, хранимые движками как правило представляют собой скопища точек в 2- или 3D пространстве, соединенные отрезками и гранями, используемые главным образом для визуального представления тел на сцене.
Естественно, игровые объекты склонны менять свое положение друг относительно друга, из чего возникает закономерный вопрос: в какой момент времени объекты пересекаются? Заставить рикошетить футбольный мяч от солнца звучит не вполне реалистично, ведь привычная всем нам физика подразумевает контакт между взаимодействующими телами. Но тут поперек горла становится сама форма представления объектов в игровом пространстве, все они задаются точками (относительно немногочисленными и разреженными), однако рисуются прямыми и многоугольниками, состоящими из бесконечного многообразия вычисляемых точек, хранить и перебирать которые идея далеко за пределами безумия.
Картинка выше призвана показать, что происходит, когда вы не храните бесконечное количество точек в движке. Пересечение между двумя фигурами вполне может существовать, даже если вершины обоих тел не принадлежат друг другу. Это сразу наводит на мысль, что проверка отдельных точек дурная затея. Если отрезки и плоскости состоят из бесконечных множеств точек, то пересечение таких примитивов должно быть легче отследить.
И действительно, два кирпича выше пересекаются ребрами, а если представить, что эти кирпичи трехмерные, они пересекаются гранями (то есть, по меньшей мере один отрезок одного тела пересекает одну из граней другого). Однако тут тоже есть над чем поразмыслить: как собственно имея 4 конца двух отрезков сказать, пересекаются ли они? И уж куда более крутой вопрос: как определить, пересекает ли отрезок из двух точек треугольник в пространстве? Как я обычно люблю делать, зайду с козырей и расскажу как имея каких-то 5 точек в пространстве сказать, пересекается ли здесь что-нибудь?
Почему собственно треугольник? Ну это проще, чем четырехугольник, к тому же через любые 3 точки можно провести хотя бы одну плоскость, я гарантирую это, чего нельзя сказать про четырехугольник, четвертая вершина которого может одним маленьким подъемом над плоскостью сломать все что только можно. К тому же, трехмерные модели зачастую из треугольников и состоят, а если нет, то любую многоугольную грань можно запросто на них разбить. А почему пересечение с отрезком а не другим треугольником? Ну это проще, к тому же, соотнесение граней двух фигур не вполне эффективно, ведь одно и то же ребро может принадлежать сотням и даже десяткам разных треугольников, и какой смысл тогда это ребро лишний раз учитывать? Нельзя забывать, что квантовые компьютеры тоже чувствуют боль, поэтому если вы станете разработчиком игр, которому плевать на производительность, знайте:
Ближе к делу
Предположим что у нас есть некоторый набор из 4
точек в пространстве формирующих тетраэдр (возможно плоский или сжатый в
отрезок или даже в точку) и одна точка, положение которой мы хотим относительно
этого тетраэдра определить, а именно ответить на вопрос «находится ли точка в
тетраэдре?», при чем сделать это точно и за минимальное время.
Самое очевидное решение состоит в построении 4
уравнений плоскостей, проходящих через каждую отдельную грань тетраэдра. Каждое
из этих уравнений будет давать ноль для точек на соответствующей грани и
положительное или отрицательное значение для точек, находящихся по определенную
сторону от плоскости. Тетраэдр по своей сути представляет из себя
полупространство, ограниченное 4 такими плоскостями, все точки которого принимают
определенный знак для каждой отельной плоскости.
Естественно, мы не можем предполагать что это
всегда плюс или всегда минус, как и не можем предположить какие из 4 граней
должны отличаться по знаку от других. Однако, рассматривая любую отдельную
грань тетраэдра составленную из 3 его точек нельзя забывать что нам достоверно
известна еще одна – вершина, противолежащая грани. Подставив ее в уравнение
плоскости мы сможем наверняка сказать, какого знака должно быть неравенство на
основе этого уравнения, чтобы проверяемая точка была в со стороны
тетраэдра относительно грани. Таким
образом сказать, что точка лежит внутри тетраэдра можно исходя из условия, что
для уравнений плоскости на каждой грани, она принимает значение того же знака,
что и свободная вершина тетраэдра.
Решение звучит рабочим, однако если вдаться в
подробности реализации, возникают сомнения в его эффективности. Все дело в том,
что для построения какого-либо уравнения плоскости, проходящей через 3 точки
требуется вычислить 4 определителя 3х3. Даже если оптимизировать нахождение
уравнения путем переноса всех точек в начало координат и тем самым сводя
вычисления до 3 определителей 2х2 и пачки вычитаний для каждого уравнения,
совокупная вычислительная сложность остается неутешительно высокой, поэтому
следует рассмотреть другие варианты решения задачи.
А вот сейчас будет матан
Предположим, что мы можем задать положение
проверяемой точки относительно 4 вершин тетраэдра при помощи линейного
уравнения:
Такая форма представления точек называется
барицентрическими координатами и удобна тем, что параметры (a, b, c, d) не подвержены влиянию аффинных преобразований, приложенных
ко всем пяти точкам, что как минимум означает, что как бы мы тетраэдр и точку
не сдвинули, относительно тетраэдра положение точки (a, b, c, d) не поменяется. Также
следует обратить внимание, что вершины тетраэдра тоже могут быть выражены
относительно него самого, что даст ровно 1 для координаты соответствующей
вершине и 0 для всех остальных.
Как это поможет решить задачу? Если присмотреться к рисунку,
можно заметить, что у каждой 3 точек любой грани есть одна общая нулевая
координата, соответствующая противолежащей вершине. Учитывая то, что любая
точка на плоскости может быть представлена как линейная комбинация трех других
точек на этой плоскости, ноль по соответствующей координате характерен сразу
для всей плоскости, проходящей вдоль грани. Таким образом, мы можем определить
уравнение плоскости, проходящей через эту грань простым равенством нулю
соответствующей координаты.
Дальнейшая логика идентична описанной в предыдущем методе. Учитывая
то, что у свободной вершины соответствующая координата будет строго больше 0 и
достоверно равна 1 для того, чтобы проверяемая точка лежала со внутренней
стороны тетраэдра, достаточно, чтобы соответствующая координата была неотрицательной.
Важно прояснить, что несмотря на то, что точка может вылететь далеко за
свободную вершину и получить координату больше 1 будучи вне тетраэдра, при этом
она непременно пересечет одну из других плоскостей и другая ее координата
станет меньше 0. Из этого следует, что для того, чтобы сказать, что точка лежит
внутри тетраэдра или на его грани/вершине, достаточно, чтобы каждая из
барицентрических координат была неотрицательной.
Теперь мы знаем, как использовать такое предположение для
решения задачи, вопрос остается в реализации и в самом существовании таких (a, b, c, d), удовлетворяющих равенству:
Как уже было сказано ранее, смещение всех точек в пространстве
никак не повлияет на (a, b,
c, d), это дает нам возможность упростить
систему уравнений избавившись от одного столбца. Если мы сдвинем все точки
относительно проверяемой p (x,
y, z), мы получим такую систему:
Можно заметить, что, перенеся любой из столбцов вправо, мы
получим обычную систему линейных алгебраических уравнений:
Согласно правилу Крамера, если решение подобной системы
существует, оно может быть выражено следующим образом:
Решение существует и единственно тогда и только тогда, когда
главный определитель матрицы ∆≠0. Возможность главного определителя
оказаться нулевым создает опасность для алгоритма делением на ноль, поэтому
будем полагать, что свободная координата d которой пропорциональны все остальные
равна ему, что дает возможность избавиться от опасной операции:
Странная последовательность знаков, зависящая от порядка
следования вершин в нашем преобразовании, которое предполагается инвариантным к
этому, может вызвать путаницу и сомнения в правильности решения, поэтому для
красоты выполним перестановку столбцов определителей в порядке следования
вершин:
С такими выражениями определителей полученная система обретает
вид:
Выглядит красиво, однако для удобства дальнейших действий потребуется
вернуть все координаты на исходные места, в этом нам поможет следующая формула:
Применяя эту формулу к нашим четырем определителям получаем:
В конечном счете мы получаем простое инвариантное выражение
координат как определитель матрицы 4х4 с подменой столбца соответствующей
вершины проверяемой точкой. Однако эта форма не будет использоваться для
вычислений, поскольку слишком трудоемка, она нужна для прояснения одной важной
детали.
Если нашим методом считать барицентрические координаты
какой-либо вершины, в 3 из 4 матриц возникнет нулевой столбец, обращающий весь
определитель в ноль, как и полагается для несоответствующих координат, однако
при соответствующей координате этого столбца не будет и ее значение будет не 1,
а полноценным определителем (который вполне даже может быть отрицательным).
Для нормировки барицентрических координат необходимо каждую из
них разделить на соответствующий определитель в вершине a(p1), b(p2), c(p3), d(p4). В какой бы определитель мы ни
подставили соответствующую вершину, благодаря выражению в матрице 4х4 все они
обращаются в абсолютно одинаковое выражение:
Если развернуть определители для случайной точки (x, y, z), можно заметить, что у них очень много
общих подопределителей:
Благодаря тому, что в разных определителях один и тот же
подопределитель выступает в разных знаках, сумма координат для случайной точки
будет зависеть только от вершин тетраэдра и не будет зависеть от самой точки:
По совместительству вся эта сумма равна тому же определителю,
которому равны a(p1), b(p2), c(p3) и d(p4) что позволяет определить для них
нормирующий делитель как сумму n=a+b+c+d для любой точки. Это дает нам возможность не
задаваться лишними вычислениями и использовать для нормировки определители,
посчитанные после сдвига тетраэдра к проверяемой точке, что позволяет описать
конечный результат следующим образом:
На уровне математики кажется странной такая запись, где неясно,
что должно считаться первым – n или a,
b, c, d. Однако с точки зрения программной
реализации a,
b, c и d можно сперва рассчитать без нормировки, а
потом разделить на их сумму. Учитывая то, что сами модули a, b, c и d не имеют особого влияния на решение
задачи, а главным был и остается только их знак, операция деления как опасная
затея может быть легко заменена на простое условие:
В зависимости от знака n, соответствующая система неравенств определит находится ли точка p в пределах тетраэдра, ограниченного точками p1, p2, p3 и p4. Для того, чтобы сказать, пересекает ли какой-то отрезок треугольник в пространстве, нам всего-то и нужно, что составить тетраэдр из треугольника и любого конца отрезка, посчитать барицентрические координаты другого конца, и так же посравнивать их с нулем. Отличие будет ровно в одном знаке неравенства, соответствующего концу отрезка на вершине тетраэдра.
P.S.
