Sergey Belyov, Senior Math Software Engineer, C3D Labs, presents the C3D Collision Detection module, a new C3D Toolkit component. He explains what's under the hood of the collision detector and what it can do for our users.
The Collision Detector is a new component of the C3D Toolkit. In this paper, we will learn about the math behind the detector, and its basic functionality, consider a simple example that demonstrates the module's applications, and discuss the roadmap for the future.
Collision detection requires solving the following math problems. First, to quickly detect the fact of intersections between multiple objects without constructing the intersection curves. All we need is to answer the question immediately: "Yes, they overlap / No, they do not". The next problem is to categorize each tangency in the set of objects. Every tangency is an intersection, but not vice versa. It is important to distinguish this special case of intersection. There is also the problem of finding the minimum distance between assemblies and bodies or categorizing the mutual positions of objects. One example is the "embedded body" ("body-in-body") detection we recently implemented in response to numerous user requests. Note that all these problems need to be solved both statically and dynamically.
First, the C3D Collision Detection module implements "fast" algorithms to solve all these problems both statically (gap control) and dynamically (collision detection in assemblies). Second, we can fine-tune these problems and create their sequences. Third, because we need to quickly detect a tangency or intersection, the approach is fundamentally different from Boolean operations: we do not construct any additional objects.
This figure shows some of the Detector messages. If the Detector found no collisions, it returns the CDET_FINISHED value. If any intersections, tangencies, or “body-in-body” are detected, the Detector returns the CDET_INTERSECTED, CDET_TOUCHED, and CDET_INCLUDED values, respectively.
The basic functionality of the new module successfully solves all of the above problems. It was first implemented in 2001. For more than 20 years, the module has been greatly improved and optimized. The radical difference between the module and Boolean operations is performance. The module is really quick. It supports both polygonal meshes and B-Rep solids.
It also has some unique features. The C3D Collision Detection module allows you to add body instances and combine bodies into components to avoid detecting tangencies/intersections between bodies within the same component. It also provides flexible tangency/intersection detection and works both statically and dynamically. Another advantage is the support for both accurate and approximate calculations.
Take a look at the figure. We see an assembly.
As the model moves, we see the colliding faces highlighted. When the model moves in reverse, observe the collision between the cylinders and pistons.
To present the module’s API, let us consider a simple example. There are two solid bodies: solid1 and solid2. Their positions in space are described by the matrices placеment1 and placement2. First, we will create a detector and add these solids to the detector using the AddSolid function. Next, let us create a colQuery collision query. Now we run the main function CheckCollision. Its argument is the query. The detector returns the result.
Let us take a closer look at the collision detection query. To create a collision query, we create an inheriting class of the parent cdet_query class. A callback function that controls the behavior of the detector is passed to its constructor. The function arguments are the Detector message and the detected data (e.g., faces crossings, etc.). The Detector interprets the code returned by the function as a command: to stop detecting, to continue, etc. With this, we can flexibly control the Detector.
Our plans and roadmap are largely based on numerous user suggestions and requests. First, a new C3D Solver-style API will be added soon. The API will have a logging system, also in the C3D Solver style. For now, the Detector successfully detects tangencies, but mostly in standard cases. Since many user requests are related to tangency detection, we will add new functionality to provide the most detailed information about the scene analyzed by the Detector. Another important aspect is the customizable detection settings. The new API allows you to specify detection accuracy, penetration and gaps, and constants that distinguish tangency from intersection. We will also optimize The Detector's algorithms (advanced caching, even more clipping, etc.).
The roadmap is till the end of the year.
Senior Math Software Engineer