How Collision Detection works (v2020)

We provide two different CollisionDetection classes:

• CollisionDetection2D for the 2D version in which all the input entities have to lie on Plane.XY (it supports BlockReference, Region and ICurve);
• CollisionDetection for the 3D version with input entities in any position and orientation of the 3D space (it supports BlockReference and all entities implementing IFace interface).

Both versions can be set with some properties and constructor parameters. Here they are in detail below:

CheckMethod (default CollisionCheckType.OB)

The accuracy of the check performed. It can be set with the following types:

• CollisionCheckType.OB is the fastest but also the most approximate check, because it checks just the entities oriented bounding (OrientedBoundingBox for 3D, OrientedBoundingRect for 2D);

Difference between AABB and OB/OBB

• CollisionCheckType.SubdivisionTree is the best Choice for Mesh/Solid(defined by triangles) since it creates a SubdivisionTree (Octree for 3D, QuadTree for 2D) of the triangles of each entity (of type IFace). It uses the tessellation data of each entity and exploits the spatial tree subdivision to perform an optimized triangle-triangle accurate check. For Curved and/or geometrical Entities (e.g. Brep, Surface, ICurve ...) the accuracy of the check depends on the refinement tolerance used to Regen those entities. Also, the performance depends on the number of triangles involved during the build and check of the tree;

QuadTree of Bunny shape

• CollisionCheckType.OBBWithSubdivisionTree combines the OB check (as the first check used among BlockReferences) with the SubdivisionTree check (at the end between two leaves IFace entities). It's more useful than CollisionCheckType.SubdivisionTree with deep Assembly;
• CollisionCheckType.Accurate is the heaviest but most accurate check for curved entities (e.g. Brep, Surface, ICurve) performing geometrical checks. It uses OB as a threshold check; 

Warning: it’s better to avoid using Accurate type with Mesh/Solid or a miscellaneous list containing also Mesh/Solid entity. Use SubdivisionTree or OBBSubdivisionTree instead.

Difference between SubdivisionTree (affected by refinement tolerance) and Accurate (using geometrical data)

FirstOnly (default true)

With this flag, you can choose to stop collision detection at the first tuple of intersecting entities or find all the intersecting entities.

CoincidenceAsCollision (default true)

With this flag, you can choose to change the default behavior and discard as collisions the touching but not intersecting entities (like coplanar surfaces). Setting this to false requires CollisionDetection to perform additional computations to find the "just touching" collisions.

maxElemsNumForQuadTreeNode/maxTrianglesNumForOctreeNode (default = total Number of triangles/100)

It defines the maximum number of elements (triangles for 3D/ segments+triangles for 2D) admitted into a leaf voxel of each entity subdivision tree. The fewer triangles there are for each voxel, the quicker is the collision check between two voxels. At the same time, the fewer triangles, the bigger is the complexity of the Tree and the total amount of voxels to chek. The choice is a thread-off depending on the context and the tessellation type of the objects (an isotropic mesh will have a better-balanced tree and so better performance).

maxTriangleEdgelength (default = disabled) for Ultimate edition only

It is the maximum length that a tessellated triangle edge could have. It is used during the SubdivisionTree checkMethod for curved entities like Brep and Surface in order to build an isotropic tesselation that will result into a more balanced octree.
If the parameter is not specified, the already preexisting tessellation will be used during the build of the octree, otherwise, a new Regen will be forced to create an isotropic tessellation with the parameter as maxLength data. This regen will slow down the first pre-computation call (see below). The choice is a thread-off depending on the size of the objects to check and the desired accuracy. (an isotropic mesh will have a better-balanced tree and hence better performance).

Input Entities to check

You can choose between All-vs-All collision check (by specifying a unique entity list), to check the reciprocal collisions among all the entities, or a First-vs-Second check (by specifying two different entity lists), in order to avoid collision check among entities belong to the same list (e.g. you won't need to check if the components of a RobotArm intersect to their-selves).

Remarks: Input entities should already be regenerated before starting CollisionDetection.

GetCollisionVolume (available from v2020 forward - see tables below for detailed data)

• True: will perform additional computations (slowing down performances) to find Collision volumes (or collision surfaces/curve with open entities) of the intersecting entities tuple found.
• False: won't perform any additional computations, but -  when present - returns anyway some intersecting data that the standard check already uses to find collisions (like intersecting point and curves).

Result

It's of type List<CollisionResult> (from v2020 forward - BC-103). Each CollisionResult contains all the Collision data found between two Entities found intersecting.

public struct CollisionResult
{
     public Tuple<CollisionTupleItem, CollisionTupleItem> CollidedEntities;
     public List<Entity> CollisionItems;
}

 In detail, each CollisionTupleItem defines the following data of one of the entities in the colliding tuple:

• Transformation – the accumulated parent transformations from the input root to the leaf intersecting entity (for the entities already at root level it will be null);
• ParentName – a string containing the Block name of the first parent of the leaf entity (it will be null if the entity is at root level);
• Parents –  the stack of BlockReferences from the root given in input to CollisionDetection to the leaf hit entity (it will be null if the entity is at root level);
• Entity –  the reference to the leaf entity found intersecting to the entity saved into its adjacent CollisionTupleItem;

CollisionItems will be filled with volumes/surfaces/points and/or curves found as collisions during the computation. In detail:

When GetCollisionVolume = true:

CollisionDetection2D

CollisionCheckType.SubdivisionTree/OBBWithSubdivisionTree
	Region	ICurve
Region	Collision Area (Region)	Intersection Points among tessellated segments (Point)
ICurve	Intersection Points among tessellated segments (Point)	Intersection Points among tessellated segments (Point)

CollisionCheckType.Accurate
	Region	ICurve
Region	Collision Area (Region)	Intersection Points among geometrical curve (Point)
ICurve	Intersection Points among geometrical curve (Point)	Intersection Points among geometrical curve (Point)

CollisionDetection

CollisionCheckType.SubdivisionTree/OBBWithSubdivisionTree
	Entity (all internally converted to Mesh during Octree computation)
Entity	CollisionVolumes (Solid)

CollisionCheckType.Accurate
	Mesh (+ Bar, Joint, Triangle, Quad)	Solid	Brep	Surface	Region
Mesh (+ Bar, Joint, Triangle, Quad)	see <Solid,Solid>	see <Solid,Solid>	see <Solid,Solid>	see <Solid,Solid>	see <Solid,Solid>
Solid	see <Solid,Solid>	CollisionVolumes (Solid)	see <Solid,Solid>	see <Solid,Solid>	see <Solid,Solid>
Brep	see <Solid,Solid>	see <Solid,Solid>	CollisionVolumes (Brep)	see <Surface,Surface>	see <Surface,Surface>
Surface	see <Solid,Solid>	see <Solid,Solid>	see <Surface,Surface>	Intersection Curves (ICurve)	see <Surface,Surface>
Region	see <Solid,Solid>	see <Solid,Solid>	see <Brep,Brep>	see <Surface,Surface>	CollisionVolumes (Solid)

When GetCollisionVolume = false:

CollisionCheckType.Accurate during CollisionDetection (3D)
	Mesh (+ Bar, Joint, Triangle, Quad)	Solid	Brep	Surface	Region
Mesh (+ Bar, Joint, Triangle, Quad)	Intersection Points among triangles  (Point)	see <Solid,Solid>	see <Mesh,Mesh>	see <Mesh,Mesh>	see <Mesh,Mesh>
Solid	see <Solid,Solid>	Intersection Curves (ICurve)	see <Mesh,Mesh>	see <Solid,Solid>	see <Solid,Solid>
Brep	see <Mesh,Mesh>	see <Mesh,Mesh>	Intersection Points among Faces and edges (Point)	Intersection Points among Surface and Brep.Edges (Point)	see <Mesh,Mesh>
Surface	see <Mesh,Mesh>	see <Solid,Solid>	Intersection Points among Surface and Brep.Edges (Point)	_	_
Region	see <Mesh,Mesh>	see <Solid,Solid>	see <Mesh,Mesh>	_	Intersection Points among triangles  (Point)

WORKFLOW

CollisionDetection(CD) derives from WorkUnit, so it could be called synchronously with CD.DoWork() or asynchronously with model.StartWork(CD). When asynchronously, you can call more different CD at the time but during the collision checks the entities' data must remain constant, so no Translations or other transformations are allowed during that time. For this reason, if you want to perform the asynchronous check with the same entities (in different positions) you have to clone (and transform them after that) the interested entities used inside CD.

The workflow is the following:

1. Precomputation of the needed data during collision checks (like Octree/QuadTree, OBR/OBB) only for the entities that don't already have them. The method PrepareDataForCollision() performs this computation and it can be called separately from the DoWork() call. After this first computation, the entities will keep their data until:
   • The Entity.RegenMode won't be anymore regenType.NotNeeded (for Octree/Quadtree);
   • A non-uniform Scale is applied to the entity (for OBR/OBB);
2. Check for collisions by exploiting the data previously computed depending on the CheckMethod chosen.  The Collision check won't check entities that belong to the same Block/BlockReferences input hierarchy anyway (see Block/BlockReference documentations to find details on how assembly hierarchy works). It will check recursively all the entities (until the leaves) contained into each assembly (see sample below for details). If at least an intersecting tuple of entities is found then the result list won't be empty.

Remark: be sure to always register to the WorkFailed event when using the asynchronous approach! 

Sample:

Block b1 = new Block("b1");
b1.Entities.Add(entity1);

Block b2 = new Block("b2");
b2.Entities.Add(entity2);
BlockReference br1 = new BlockReference("b1");
b2.Entities.Add(br1);

Block b3 = new Block("b3");
b3.Entities.Add(entity3);

BlockKeyedCollection blocksCollection = new BlockKeyedCollection();
blocksCollection.Add(b1);
blocksCollection.Add(b2);
blocksCollection.Add(b3);

BlockReference br2 = new BlockReference("b2");
BlockReference br3 = new BlockReference("b3");

List<Entity> listToCheck = new List<Entity>();
listToCheck.Add(br2);
listToCheck.Add(br3);

CollisionDetection cd = new CollisionDetection(listToCheck, blocksCollection);
cd.DoWork();

CD won't check collisions among entity1 and entity2, neither entity2 and br1 because they belong to the same assembly (with br2 as root).

Collisions checks could be instead between:

1. br3 and br2;
2. br3 and entity2;
3. br3 and br1;
4. br3 and entity1;
5. entity3 and br2;
6. entity3 and entity2;
7. entity3 and br1;
8. entity3 and entity1;

 Have a look at CollisionDetection source code sample for a good start point.