Algorithm for finding quads of intersection on a grid

Question

Here is my problem.

My game, for efficient rendering and collision is divided into regions. There will be many objects in each region that will dynamically move. When they move, I need a way to quickly determine which regions they are in.

An object can never be longer or wider than a region. Thus it can never be in more than 4 regions at once.

The tricky part is that the object's rectangles are Oriented Bounding Boxes using the separate axis theorem in 2D, thus they can be rotated.

The main way I have thought of doing this is by determining the regions of each point:

static public int colFromPos(float startX,float width, float x)
{
    x -= startX;
    return (int)Math.floor(x / width);

}

static public int rowFromPos(float startY,float height, float y)
{
    y -= startY;
    return (int)Math.floor(y / height);

}

This seems pretty fast.

I have thought of a couple ways to do it like this:

I generate a bounding rectangle of the OBB and find the 4 regions of this rectangle. The drawback here is that a furthur test must then be done to determine if the object really is in.

I determine the region of each corner and each midpoint of the OBB.

Are there better, faster ways of going about this? Are either of my solutions good ideas?

Thanks

enter image description here

Given that the object can never exceed the size of a region, would method 1 be exactly correct to determine what regions an OBB is in? — jmasterx
Performance and alternative methods are really dependent on the complexity and nature of your objects... constructing an OBB can be trivial or prohibitively expensive, depending. — user684934
In this case, the OBBs already get rebuilt when the object moves or rotates. Its bounding rect is also calculated too. Thus approach 1 would be very cheap for me. Does it do what I want? — jmasterx
Bounding shapes are useful for identifying (narrowing down) candidates for collision, but cannot be used by themselves for collision detection. — user684934

Patricia Shanahan Patricia Shanahan · Accepted Answer · 2012-11-08T20:16:49

Determine the region containing each vertex of the OBB.

If all four are in the same region, return that region.

If all four are in a pair of regions that share an X coordinate or share a Y coordinate, return that pair of regions.

If they are in four different regions, return that group of four regions.

If none of those conditions apply, you have two different region X coordinates and two different region Y coordinates, defining a group of four regions meeting at a single vertex, V.

If V is inside the OBB, return all four regions.

If V is outside the OBB, and the OBB vertices are in three different regions, return those three regions.

The remaining case is that a pair of diagonally adjacent regions contain the vertices of the OBB, and V is outside the OBB. Pick a side of the OBB that connects vertices that are not in the same region. Return the two vertex-containing regions, and the third region that line crosses.

I have not addressed the issues of e.g. V being exactly on a side of the OBB. Handling of those cases depends on program conventions.

Algorithm for finding quads of intersection on a grid

1 Answers