Overlap testing design notes

Back to Overlap testing

GJK vs specialized algorithms

Given `n` types of objects, one needs to implement `O(n^2)` algorithms to cover for all pairwise combinations. The GJK algorithm is able to avoid such a profileration of cases by abstracting a convex shape by using a so-called support mapping. One algorithm is then sufficient to handle all overlap testing (and more) in a large class of convex shapes. The advantages of specialized testing include:

• The results are exact (assuming exact arithmetic).
• The algorithms are probably somewhat faster, as they can use information specific to the problem.

The disadvantages include:

• Profileration of cases.
• No run-time abstraction for shapes.

The GJK and the specialized algorithms complement each other. An ideal case would be to provide both.

Remark 1.7.5 - Page generated 16.06.2017 01:36.