Я прошу прощения за длину этого вопроса и благодарю всех, кто прочитал это!
Итак, я провел последние несколько дней, изучая алгоритм GJK. Я понимаю общие принципы, лежащие в его основе, и понимаю большинство мелких деталей его реализации в 2D благодаря замечательной статье Уильяма Биттла в http://www.codezealot.org/archives/88.
Я внедрил его псевдокод (см. В конце статьи) в свой собственный проект на C ++, однако я хочу сделать 3D-реализацию. Моя слабость заключается в использовании точечных продуктов для проверки областей вороной и тройных продуктов для получения перпендикулярных линий. Но я пытаюсь прочитать больше об этом.
Моя проблема сводится к функции containsOrigin. У меня проблемы с визуализацией и учетом новых областей вороной, которые добавляет ось Z. Я просто не могу обернуться, как определить, какие области содержат происхождение. Я предполагаю, что есть 4, которые я должен учитывать, каждая из которых простирается от треугольных плоскостей, которые составляют 4 грани простого тетраэдра. Если источник не находится ни в одном из этих регионов, он содержится, и мы столкнулись.
Как мне пройти тестирование, если оно содержится в определенной области вороной / какая треугольная грань указывает в направлении начала координат?
Текущий 2D алгоритм проверяет, сделан ли треугольник, если нет, то симплекс является линией и находит третью точку. Я предполагаю, что трехмерный алгоритм с проверкой, сделан ли тетраэдр, если нет, то он проверит треугольник, если true, тогда он найдет 4-ую точку, чтобы сделать тетраэдр (как бы я это получил? Используя нормальное направление происхождения?). Если я не сделаю, я найду третью точку, чтобы сделать треугольник (я все еще использую тройной продукт для этого, как в 2D?).
Любые предложения, схемы, ресурсы, дополнения кода, комментарии очень ценятся.