Support-function in the GJK-algorithm

Question

I am trying to implement the GJK-algorithm but I got stuck instantly.

The problem is to implement the Support-function that isn't O(n^2).

As it is now I'm computing the complete Minkowski difference, and then there is really no point in doing the GJK-algorithm. (or is it?)

What I mean by Support-function is the function that returns the point in the Minkowski difference that is furthest away in a specified direction. I assume this shouldn't be O(n^2) as it is in my current implementation.

Answer 1

The simplest support function would be 0(n), ie find the best dot product in a direction.

    public Vector3 MaxPointAlongDirection(Vector3 directionToMove)
    {
        float max = float.NegativeInfinity;
        int index = 0;
        for (int i = 0; i < vertices.Length; i++)
        {
            float dot = Vector3.Dot(vertices[i], directionToMove);
            if (dot > max)
            {
                max = dot;
                index = i;
            }
        }
        return vertices[index];
    }

Another faster approache for a triangulated convex hull would be hill climbing; 1 Compute adjacency information for every point. 2 Start at a random point find the best dot product for all adjacent points. 3 Make this new point the current point repeat step 2 4 stop when no better product is found (which would be valid since the object is convex therefore there a no local maxima)

or a Dobkin-Kirkpatrick hierarchy.

In the case where the objects are rotating the directionToMove vector can be transformed relative to the rotated object (still working on this). Thereby not requiring all points to be rotated.