Hi,

Most people seem to prefer some version of Sutherland–Hodgman clipping when generating one-shot contacts. Sutherland–Hodgman has O(n*m) time complexity. Is this fast enough for most practical purposes or is there a compelling reason to pick a different algorithm with better time complexity?

I guess I could always profile, but I'm also asking in case there are other considerations that I may have overlooked... Is there for example some case of temporal coherency that can be exploited?

Thanks!

I've been using Sutherland-Hodgman for years with good results. Yes, it's fast enough and simple to implement. The good thing is that it preserves the polygon vertex order. 

Not informed about temporal coherency in the context of clipping. However, in the context of contact creation, temporal coherency can be exploited by reclipping the touching features. 

If two faces are chosen as the touching features in one frame, you run clipping and cache these features. If these two faces still are the touching features in the next frame, you check if the relative orientation of the shapes has changed up to some small tolerance. If not, you reclip those features.  

Of course we assume you can detect the touching features using an algorithm such as the SAT. 
 

Consider worst case of roughly 12 vertices against 12 vertices. That’s 144 loops. However this will operate on memory inside of a very small space in L1 cache. Pretty much, it’s going to be extremely fast.

It worked great, thanks for the help!