Mesh-level acceleration structures for collision detection when mesh instances can be rotated, scaled and/or resized

Question

Short version: in the mid-phase or narrow-phase of collision-detection, does any acceleration structure organizing the mesh's vertices (e.g. AABB-trees, Octrees, Quadtrees) work for the mesh's instances that are re-scaled, re-sizes and/or rotated?

Long version: suppose a concave mesh composed of a very high number of triangles (e.g. 200k) and for which I cannot use convex decomposition in order to perform collision detection. The most efficient solution usually employed would be to organize the vertices of the mesh using acceleration structures to quickly prune which parts of the mesh are likely to have been collided with.

However, that mesh is used for generating instantiated copies - and each of these can have different size, rotation and/or scale at any of the X,Y,Z axis. Would any acceleration-structures work since the instances can be re-scaled, rotated and resized? Suggestions, tips, academic references, are all appreciated.

Answer 1

The best option is to perform all the mid and narrow phase in the local space of the instanced mesh object.

Most collision detection algorithms air pair-wise using two matrices, one for each objects transform. In this case create an inverse matrix from the instanced object's matrix and concatenate it with the other objects matrix. This effectively moves the collision detection into the local space of the instanced object. After detection is performed multiply the results by the instanced objects transform to get the results in world space. This removes the need to move every triangle into world space. It also allows you to use an acceleration structure shared with each instance.

Some pair-wise detection algorithms require extra treatment when dealing with scale but this is certainly where I would start.