Finding the Oriented Bounding Box of a Convex Hull in XNA Using Rotating Calipers

Question

Perhaps this is more of a math question than a programming question, but I've been trying to implement the rotating calipers algorithm in XNA.

I've deduced a convex hull from my point set using a monotone chain as detailed on wikipedia.

Now I'm trying to model my algorithm to find the OBB after the one found here: http://www.cs.purdue.edu/research/technical_reports/1983/TR%2083-463.pdf

However, I don't understand what the DOTPR and CROSSPR methods it mentions on the final page are supposed to return.

I understand how to get the Dot Product of two points and the Cross Product of two points, but it seems these functions are supposed to return the Dot and Cross Products of two edges / line segments. My knowledge of mathematics is admittedly limited but this is my best guess as to what the algorithm is looking for

    public static float PolygonCross(List<Vector2> polygon, int indexA, int indexB)
    {
        var segmentA1 = NextVertice(indexA, polygon) - polygon[indexA];
        var segmentB1 = NextVertice(indexB, polygon) - polygon[indexB];

        float crossProduct1 = CrossProduct(segmentA1, segmentB1);
        return crossProduct1;
    }

    public static float CrossProduct(Vector2 v1, Vector2 v2)
    {
        return (v1.X * v2.Y - v1.Y * v2.X);
    }

    public static float PolygonDot(List<Vector2> polygon, int indexA, int indexB)
    {
        var segmentA1 = NextVertice(indexA, polygon) - polygon[indexA];
        var segmentB1 = NextVertice(indexB, polygon) - polygon[indexB];

        float dotProduct = Vector2.Dot(segmentA1, segmentB1);
        return dotProduct;
    }

However, when I use those methods as directed in this portion of my code...

            while (PolygonDot(polygon, i, j) > 0)
            {
                j = NextIndex(j, polygon);
            }

            if (i == 0)
            {
                k = j;
            }
            while (PolygonCross(polygon, i, k) > 0)
            {
                k = NextIndex(k, polygon);
            }

            if (i == 0)
            {
                m = k;
            }
            while (PolygonDot(polygon, i, m) < 0)
            {
                m = NextIndex(m, polygon);
            }

..it returns the same index for j, k when I give it a test set of points:

    List<Vector2> polygon = new List<Vector2>() 
        { 
            new Vector2(0, 138),
            new Vector2(1, 138), 
            new Vector2(150, 110), 
            new Vector2(199, 68), 
            new Vector2(204, 63), 
            new Vector2(131, 0), 
            new Vector2(129, 0), 
            new Vector2(115, 14), 
            new Vector2(0, 138), 
        };

Note, that I call polygon.Reverse to place these points in Counter-clockwise order as indicated in the technical document from perdue.edu. My algorithm for finding a convex-hull of a point set generates a list of points in counter-clockwise order, but does so assuming y < 0 is higher than y > 0 because when drawing to the screen 0,0 is the top left corner. Reversing the list seems sufficient. I also remove the duplicate point at the end.

After this process, the data becomes:

• Vector2(115, 14)
• Vector2(129, 0)
• Vector2(131, 0)
• Vector2(204, 63)
• Vector2(199, 68)
• Vector2(150, 110)
• Vector2(1, 138)
• Vector2(0, 138)

This test fails on the first loop when i equals 0 and j equals 3. It finds that the cross-product of the line (115,14) to (204,63) and the line (204,63) to (199,68) is 0. It then find that the dot product of the same lines is also 0, so j and k share the same index.

In contrast, when given this test set: http://www.wolframalpha.com/input/?i=polygon+%282%2C1%29%2C%281%2C2%29%2C%281%2C3%29%2C%282%2C4%29%2C%284%2C4%29%2C%285%2C3%29%2C%283%2C1%29

My code successfully returns this OBB: http://www.wolframalpha.com/input/?i=polygon+%282.5%2C0.5%29%2C%280.5%2C2.5%29%2C%283%2C5%29%2C%285%2C3%29

I've read over the C++ algorithm found on http://www.geometrictools.com/LibMathematics/Containment/Wm5ContMinBox2.cpp but I'm too dense to follow it completely. It also appears to be very different than the other one detailed in the paper above.

Does anyone know what step I'm skipping or see some error in my code for finding the dot product and cross product of two line segments? Has anyone successfully implemented this code before in C# and have an example?

Vickivickie

Answer 1

Points and vectors as data structures are essentially the same thing; both consist of two floats (or three if you're working in three dimensions). So, when asked to take the dot product of the edges, I suppose it means taking the dot product of the vectors that the edges define. The code you provided does exactly this.

Your implementation of CrossProduct seems correct (see Wolfram MathWorld). However, in PolygonCross and PolygonDot I think you shouldn't normalize the segments. It will affect the magnitude of the return values of PolygonDot and PolygonCross. By removing the superfluous calls to Vector2.Normalize you can speed up your code and reduce the amount of noise in your floating point values. However, normalization is not relevant to the correctness of the code that you have pasted as it only compares the results with zero.

Note that the paper you refer to assumes that the polygon vertices are listed in counterclockwise order (page 5, first paragraph after "Beginning of comments") but your example polygon is defined in clockwise order. That's why PolygonCross(polygon, 0, 1) is negative and you get the same value for j and k.

Ruelu

This polygon: List polygon = new List() { new Vector2(2, 0), new Vector2(0, 2), new Vector2(2, 4), new Vector2(4, 2), }; is counter clockwise isn't it? 0,2 is to the left and down from 2,0. 2,4 is to the right and down from 0,2. 4,2 is to the right and up from 2,4. 2,0 is to the left and up from 4,2. It's a counter clockwise diamond. – Vickivickie

Wait. I've been working with video games for so long that I forgot people typically work in the 1st quadrant and not the 4th where the lower the y value the higher it is. I hope this is my problem. – Vickivickie

That was it! Thank you so much. I'm embarassed it was that simple. – Vickivickie

I'm having further troubles now with new test data. I've update the question above. I very much appreciate your help. – Vickivickie

Answer 2

I assume DOTPR is a normal vector dot product, crosspr is a crossproduct. dotproduct will return a normal number , crossproduct will return a vector which is perpendicular to the two vectors given. (basic vector math,check wikipedia)

they are actually defined in the paper as DOTPR(i,j) returns dotproduct of vectors from vertex i to i+1 and j to j+1. same for CROSSPR but with cross product.

Shang