# How does matrix based game physics (collision detection & response) work?

I'm familiar with how to do collision detection and response using shape intersection tests, the separating axis theorem, and by using MPR and GJK with minkowski sums and support vector defined shapes.

I know that there is another way to do collision detection and response using matrices, but I don't know anything about it.

Can anyone explain to me the basics of how that works, or link me to some resources? I've been unable to come up with the right terms to ask google apparently.

Thanks!

• Aside from using the matrices as transformations? (per instance translations, rotations, scales, etc.) Aside from transformations and maybe some optimizations (AABB collision could easily be reworked to use exclusively matrices, but that's still AABB collision), I don't think it's possible. A matrix just simply doesn't hold enough information for collision detection and response. Jul 22, 2015 at 23:12
• As best as i understand what i've heard of this technique, i believe it might be something like you put your constraints (like object position minimum distance constraint?) into a matrix and it can find a solution where there are no collisions? not really sure... Jul 22, 2015 at 23:18

The Wikipedia article on collision detection has this to say on the topic of matrices and collision detection;

So we reduce the problem to that of tracking, from frame to frame, which intervals do intersect. We have three lists of intervals (one for each axis) and all lists are the same length (since each list has length n, the number of bounding boxes.) In each list, each interval is allowed to intersect all other intervals in the list. So for each list, we will have an n \times n matrix M=(m_{ij}) of zeroes and ones: m_{ij} is 1 if intervals i and j intersect, and 0 if they do not intersect.

By our assumption, the matrix M associated to a list of intervals will remain essentially unchanged from one time step to the next. To exploit this, the list of intervals is actually maintained as a list of labeled endpoints. Each element of the list has the coordinate of an endpoint of an interval, as well as a unique integer identifying that interval. Then, we sort the list by coordinates, and update the matrix M as we go. It's not so hard to believe that this algorithm will work relatively quickly if indeed the configuration of bounding boxes does not change significantly from one time step to the next.

So it seems to me that you would use the matrices to store the results of various intersections gotten by more traditional calculations - IE, comparing points against bounding cubes.

• It definitely could be. I need to do some more searching and ask some physics programmers I know, but you've given me some stuff to look at. If this ends up being how it works I'll accept your answer (: Jul 23, 2015 at 20:20
• I think i misheard something somewhere along the way, your answer is the closest thing to what it was i was looking for, and i was looking for something non existent apparently hehe. Jul 28, 2015 at 20:22