3D Axis Sweep and Prune added to CVS

[Erwin Coumans]

Simon Hobbs contributed a 3D Sweep and prune implementation, which has been added to Bullet CVS.

It required a bit of cleanup in Bullet, so some of the interfaces/code has been shuffled around.

Please let me know if this helps performance. SimpleBroadphase and AxisSweep3 both use the same interface now, so can be exchanged.
AxisSweep3 takes as input the world boundaries, because of internal storage (quantized integers), as well as optional maximum number of objects and overlap (both set to some arbitrary default).

Erwin

PS: Simon also contributed Win32 SIMD optimized classes and SAT (separating axis test) based convex hull code. But this requires more work to integrate, I'll post a message as soon as this is added to CVS.

[Erin Catto]

AxisSweep3 looks compact and efficient.

I'm curious though, why doesn't it use stabbing numbers for fast insertion, removal, and queries?

[omicron]

AxisSweep3 looks compact and efficient.

I'm curious though, why doesn't it use stabbing numbers for fast insertion, removal, and queries?

Using the stabbing numbers it wouldn't be necessary to add/remove overlapping pairs when sorting the endpoints of each AABB. As it is now overlapping pairs are being added and removed for nothing in cases where one AABB completely passes others.

So, it should be, sort endpoints normally but just without adding/removing overlapping pairs ( updating stabbing numbers only ), and in the end ( when the AABB is sorted ), stabbing numbers can be used to figure out what overlaps occured due to that AABB update. Am I right ? I already implemented this but didn't test it yet, however, it seems to make sense to me. Correct me if I'm wrong.

Bye!

[Erwin Coumans]

AxisSweep3 looks compact and efficient.

I'm curious though, why doesn't it use stabbing numbers for fast insertion, removal, and queries?

There are several solutions for fast insertion and removal, and stabbing numbers is just one. Perhaps it can be added, but I plan to use a method that is better in my opinion:

1) adding/removing objects in larger batches, and presort this batch in advance
2) for single queries and single add/removal: using marker objects

Add marker objects in the broadphase, and just search for the closest marker object, and insert from there.

Stabbing numbers are fine too, but the approach easily breaks if there are large objects in the broadphase.

I can ask the original author of this implementation, but likely it is on the todolist, or not a bottleneck in his applications.

[Erin Catto]

I noticed this code:

Code: Select all

bool AxisSweep3::TestOverlap(const Handle* pHandleA, const Handle* pHandleB)
{
	for (int axis = 0; axis < 3; axis++)
	{
		if (m_pEdges[axis][pHandleA->m_maxEdges[axis]].m_pos < m_pEdges[axis][pHandleB->m_minEdges[axis]].m_pos ||
			m_pEdges[axis][pHandleB->m_maxEdges[axis]].m_pos < m_pEdges[axis][pHandleA->m_minEdges[axis]].m_pos)
		{
			return false;
		}
	}

	return true;
}

Since indices sort the same as positions, couldn't this be optimized as (you mentioned this before):

Code: Select all

bool AxisSweep3::TestOverlap(const Handle* pHandleA, const Handle* pHandleB)
{
	for (int axis = 0; axis < 3; axis++)
	{
		if (pHandleA->m_maxEdges[axis] < pHandleB->m_minEdges[axis] ||
			pHandleB->m_maxEdges[axis] < pHandleA->m_minEdges[axis])
		{
			return false;
		}
	}

	return true;
}

I think some of the calling code would have to be re-organized for this to work correctly.

BTW, this optimization never came up in my SAP because I (redundantly) store the Vector3 min, max in my Handle structure.

[Erwin Coumans]

I noticed this code:


Since indices sort the same as positions, couldn't this be optimized as (you mentioned this before):

Code: Select all

bool AxisSweep3::TestOverlap(const Handle* pHandleA, const Handle* pHandleB)
{
	for (int axis = 0; axis < 3; axis++)
	{
		if (pHandleA->m_maxEdges[axis] < pHandleB->m_minEdges[axis] ||
			pHandleB->m_maxEdges[axis] < pHandleA->m_minEdges[axis])
		{
			return false;
		}
	}

	return true;
}

I think some of the calling code would have to be re-organized for this to work correctly.

BTW, this optimization never came up in my SAP because I (redundantly) store the Vector3 min, max in my Handle structure.

Thanks for the reminder, the version in CVS has your update. The only change in calling code was to pass the current axis index into TestOverlap, so it can be ignored: You only need to check the other two axis, not the current one.

Thanks,
Erwin