# How to solve Sweep and prune false positives concerning large floor plane

I am developing a 3d sweep and prune module for a project, and it is producing false positives.

The pair generation code is as follows:

    for (unsigned int i = 0; i < mXExtents.size(); i +=2)
{
if (mXExtents[i]->mOwner->getID() != mXExtents[i + 1]->mOwner->getID())
{
tempXPairs.push_back(new Pair(mXExtents[i]->mOwner, mXExtents[i + 1]->mOwner));
}
}
for (unsigned int i = 0; i < mYExtents.size(); i +=2)
{
if (mYExtents[i]->mOwner->getID() != mYExtents[i + 1]->mOwner->getID())
{
tempYPairs.push_back(new Pair(mYExtents[i]->mOwner, mYExtents[i + 1]->mOwner));
}
}
for (unsigned int i = 0; i < mZExtents.size(); i +=2)
{
if (mZExtents[i]->mOwner->getID() != mZExtents[i + 1]->mOwner->getID())
{
tempZPairs.push_back(new Pair(mZExtents[i]->mOwner, mZExtents[i + 1]->mOwner));
}
}


Where each object has a unique ID in the world. This works fine with small objects, but I have encountered a problem, where, If the ground is represented by a finite (albiet large) axis aligned plane, false positives and negatives are generated, preventing the Narrow-phase from doing it's job.

As you can see, each axis list is traversed in sets of 2 elements, and the unique ID's are compared. If they do not match, then a pair is generated for that axis.

Without the ground plane, The order of each list would be Amin, Amax, Bmin, Bmax etc. which would not generated false positives. However, with the addition of the ground plane, the order becomes Pmin, Amin, Amax, Bmin, BMax, PMax.

Even if A and B are far away from one another on the axis in question, the pair is still generated. Additionally, If there is a genuine overlap on that axis, eg. Pmin, Amin, Bmin, Bmax, Amax, Pmax, then genuine intersections are missed.

Also, I've just encountered another problem: Even when traversing the lists one element at a time, In the case of objects stacked on an axis, collisions can be missed. The following image illustrates this:

If anyone else has encountered this problem, I'd like to hear how they solved it.

## 1 Answer

I came up with a solution:

In order to record all possible intersections on a given axis, You must record a pair for every possible overlap. The code I posted wasn't doing this. Instead, my new code traverses the the list one at a time, and for each endpoint which is marked as a minimum, search the remaining elements until you find the max endpoint for the same object and generate a pair for all elements in between:

    for (unsigned int i = 0; i < mXExtents.size()-1; i++)
{
//if the endpoint is a minimum
if (!mXExtents[i]->mMax)
{
//search remaining elements for the max endpoint
for (unsigned int j = i + 1; j < mXExtents.size(); j++)
{
//objects only have two endpoints, so this is the max one.
if (mXExtents[j]->mOwner->getID() == mXExtents[i]->mOwner->getID())
{
break;
}
else
{
//between min and max is an intersection of AABB on this axis
tempXPairs.push_back(new Pair(mXExtents[i]->mOwner, mXExtents[j]->mOwner));
}
}
}
}


As each object has only two endpoints, min and max, once you reach it, it can be inferred that the other end point is the maximum extent, therefore beyond it, no further intersections are possible, and so no further traversing is necessary. Naturally, this does increase complexity, but as the checks are very simple integer/integer, and boolean checks, It shouldn't have too much of an impact on performance.