Support-function in the GJK-algorithm

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, an开发者_运维百科d 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.

---

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.

---

Well, the GJK would give you the closest point of the Minkowski sum to the origin. If nothing else moves, then your Minkowski sum would be the same, and the closest point also.

Usually people assume the bodies are free to move and rotate. On that case, results change all the time.

On the translation case, you should be able to reuse your Minkowski difference. On the rotation case, you would need to recalculate. That would be a problem for many real-time applications.

If your algorithm uses the Minkowski difference implicitly, by means of support functions, then you don't have to recalculate anything. That is one of the advantages of using support functions.

Some shapes have a very easy form for the support function. In that case, you don't need to calculate anything. That's another advantage. And, finally, you can add the support functions to make for the support function of a Minkowski sum. A great property, since that way you can form a family of shapes using primitives, and get GJK to work on them.

If you have a convex hull of n points on the plane, the support function can be precalculated by finding the edges of the hull polygon and sorting the angles of the normal vectors. Every vertex on the hull will have two normals. Just go sequentially and find if your direction is between these normal vectors. That would give you O(n).

You can also change the comparison order and make it O(log(n)).