Сергей Белёв, старший математик‑программист, C3D Labs, знакомит с новым компонентом C3D Toolkit — модулем C3D Collision Detection, рассказывает о том, что детектор столкновений представляет собой изнутри, и о том, какие возможности он предоставляет пользователям.

Детектор столкновений — новый компонент инструмента C3D Toolkit. В статье перечислим математические задачи, которые поставлены перед детектором, узнаем его основной функционал, рассмотрим несложный пример, демонстрирующий интерфейс модуля, и обратимся к планам и дорожной карте.

Обнаружение столкновений подразумевает постановку следующих математических задач.

Первая — это возможность уметь находить пересечения между собой среди множества объектов и делать это быстро, без поиска самого пересечения. Требуется оперативно отвечать на соответствующий вопрос — «да, пересекаются» / «нет, не пересекаются».
Следующая задача состоит в классификации касаний между собой этого множества объектов. Каждое касание является пересечением, но не наоборот, и важно уметь выделять этот частный случай пересечения.
Помимо этого, актуальна задача поиска минимального расстояния между сборками тел и телами, а также задача классификации взаимного расположения объектов. Примером служит детектирование «вложения тел» («тело в теле»), недавно внедренное нами в ответ на многочисленные запросы пользователей. Важно отметить, что все эти задачи нужно уметь решать как в статике, так и в динамике.

Модуль C3D Collision Detection, во‑первых, реализует «эффективные» алгоритмы решения всех поставленных задач — как в статических сценах, например контроль зазоров, так и в динамических сценах, в частности контроль соударений между элементами сборки. Во‑вторых, у нас есть возможность тонкой настройки всех формулируемых задач — можно даже создавать их комбинации. В‑третьих, исходя из необходимости быстро обнаруживать касание/пересечение, применяется принципиально иной подход, чем в булевой операции: мы не строим какие‑либо дополнительные объекты.

Варианты сообщения детектора: не обнаружено, пересечение, касание и объект внутри тела.

На рисунке продемонстрированы варианты сообщения детектора. Если детектор закончил работу и ничего не было обнаружено, код возврата будет таким — CDET_FINISHED. Если были обнаружены пересечения, касания или «тело в теле», сообщения детектора будут следующими: CDET_INTERSECTED, CDET_TOUCHED и CDET_INCLUDED соответственно.

Основной функционал модуля позволяет решать все перечисленные задачи. Его первая реализация появилась в 2001 году, и более чем за 20 лет произведено множество оптимизаций для его совершенствования. Кардинальное отличие модуля от тех же булевых операций — это производительность. Он решает поставленные задачи быстро. Модуль поддерживает как полигональные сетки, так и твердые тела в граничном представлении (B‑rep).

Есть несколько особенностей, присущих данному компоненту. Модуль C3D Collision Detection позволяет добавлять копии тел (инстансы), объединять тела в компоненты таким образом, чтобы, например, не детектировать касание/пересечение между телами, входящими в один компонент. Также он позволяет гибко настраивать поиск касаний/пересечений или их отсутствие и работает как в статике, так и в динамике. Отдельное преимущество — точные и приближенные вычисления.

Рассмотрим пример. Перед нами — упрощённая сборка карданного вала.

Модель двигается, и мы видим, как подсвечиваются сталкивающиеся грани.

Описывая интерфейс модуля, следует обратиться к примеру, который в упрощенном виде показывает, о чем идет речь. Возьмем два твердых тела — solid1 и solid2, положения которых в пространстве описываются матрицами placеment1 и placement2. Создадим детектор и с помощью функции AddSolid добавим эти твердые тела в детектор. Далее создадим запрос на поиск столкновений colQuery. Запустим основную функцию проверки коллизий CheckCollision, аргумент которой данный запрос, и получим результат от детектора.

Разберем подробнее запрос на поиск столкновений. Для того чтобы создать запрос на поиск столкновений, необходимо создать класс‑наследник от cdet_query. Его конструктор принимает callback‑функцию, которая управляет поведением детектора. Аргументы функции — это, собственно, сообщение детектора и данные, которые он обнаружил (например, пересечения граней и т. п.). Код возврата этой функции интерпретируется детектором как указание на то, что ему делать дальше: остановить работу, продолжить и т. д. Соответственно, поведением детектора можно гибко управлять.

Планы

Наши планы и дорожная карта во многом опираются на содержание многочисленных запросов пользователей. Прежде всего, в соответствии с их пожеланиями, в ближайшее время будет создан новый API в стиле C3D Solver. К этому API будет добавлена система журналирования, также в стиле C3D Solver.

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

И еще одна важная деталь — это настраиваемые параметры детектирования. Новый API будет позволять задавать точность детектирования, величину проникновения зазоров и константы, которые отличают касание от пересечения. Также планируется оптимизация внутренних алгоритмов детектора (продвинутое кэширование, дальнейшее внедрение алгоритмов клиппирования и т. д.).

Сергей Белёв

Старший математик-программист
C3D Labs

C3D Collision Detection: представление детектора столкновений в составе C3D Toolkit