Concerning collisions

Motivation

Upon opening AdaOne, you are greeted by a big empty scene. This scene is like a sandbox where you can play with 3D objects: However, many times 3D objects do not comply with the rules of the physical world. They feel hollow and empty. They pass through each other without registering a collision. Representing real-world physical behavior in the virtual world implies significant efforts. Nevertheless, real-time collision detection solutions benefit applications like ours greatly.

Though we may not have realized it, the implementation of collision detection has already been adopted in games and physics simulations for the most part. Naturally, we looked at those applications for inspiration. Our application has some unique combination of constraints such as:

Manipulation of a few dynamic objects at a time (<10).
A wide range level of detail of objects models (from ~100 triangles to +1M triangles)
Real-time collision check with other dynamic objects (time latency of ~1ms)

Implementing real-time collision detection allows us to inform our users of a potential problem during the printing process. It helps identify the risk of material or equipment damage. With the collision check aspect solved, it is then much easier to go further, like establishing heuristics and rules to implement a robust and safe system that would enhance safety, such as penetration depth, angle of approach, safety perimeter, etc.

Collision on two different points between a robot and its positioner

Technical implementation

Naive force approach

To begin with, we evaluated the number of objects in our scene. Since the number is so small, we opted to detect collisions by checking whether every possible pair of solid objects could collide. This technique is called the naive approach.

You can probably notice the drawback of this approach. Let’s picture the situation from the point of view of one of the objects. This object needs to check if it collides with any other object in the scene. This collision detection check is repeated for every single object. That’s what we call an O(n²) complexity. For a scene displaying 10 objects, 100 checks are needed; for 1000 objects, it would be a million. So, it can get quickly out of hand.

A contrasting option, which in our case is not necessary, is the spatial partitioning algorithm that helps identify which groups of objects are more likely to collide.

The second aspect was dealing with very nonconvex shapes. Usually, computer games, for instance, will design their levels with primitives that are easy to work with, like boxes, spheres, etc. These primitives make collision checking much simpler.

AdaOne lets the user import any robot, part, and printing head shape. Presumably, these shapes are from real-life objects that may not conform to simple primitives. To better understand this situation, we must introduce some other key concepts hereafter.

Concavity

Concave polygons are polygons where a line segment joining two points can be connected partly or wholly outside the polygon. For example, a fork-like polygon is concave since the line connecting the spike is not inside the polygon. A knife is convex (the opposite of concave) since the line segment joining two points lies inside the polygon.

It is much easier to work only with convex polygons as they conform to some rules that we can put to good use for collision detection. On the other hand, concavity presents special cases and disregards generic properties making it difficult to detect collisions. To do this, we usually decompose the concave polygon into multiple convex ones. The breakdown can be exact or approximative. This method is an active area of research, particularly for convex hulls decomposition (https://github.com/kmammou/v-hacd). After breaking down a complex problem (concave polygons) into many simple problems (convex polygons), the initial problem becomes a reasonably solvable problem. Using this approach is easier than finding a generic solution to solve concave objects collision checks.

Spatial partitioning

When simulating a large space with many objects, it would be a waste of time and resources to test every possible pair of collisions. Furthermore, the number of checks would scale with the square root of the number of objects. Instead, we can capitalize on the spatial distribution of objects and build a spatial partitioning data structure such as a quadtree. Quadtrees are a way to decompose space into smaller and smaller partitions with much more details. Starting with a square, every time an object is added to the scene, the square where the object lies is subdivided into four equally sized quadrants. Then, when querying the collision state between two distinct objects, it is possible to know if they are colliding or not, provided they are in a different zone of the initial square. Assuming all objects are randomly distributed in the scene, this approach drops down our asymptotic complexity from O (n²) to O (n log n). Of course, there are many other different and more complex schemes to spatially partition a space (BVH/OctTree/Lattices).