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.
3D Axis Sweep and Prune added to CVS
-
- Site Admin
- Posts: 4221
- Joined: Sun Jun 26, 2005 6:43 pm
- Location: California, USA
-
- Posts: 316
- Joined: Fri Jul 01, 2005 5:29 am
- Location: Irvine
-
- Posts: 8
- Joined: Tue Jan 17, 2006 6:27 pm
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.Erin Catto wrote:AxisSweep3 looks compact and efficient.
I'm curious though, why doesn't it use stabbing numbers for fast insertion, removal, and queries?
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!
-
- Site Admin
- Posts: 4221
- Joined: Sun Jun 26, 2005 6:43 pm
- Location: California, USA
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:Erin Catto wrote:AxisSweep3 looks compact and efficient.
I'm curious though, why doesn't it use stabbing numbers for fast insertion, removal, and queries?
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.
-
- Posts: 316
- Joined: Fri Jul 01, 2005 5:29 am
- Location: Irvine
I noticed this code:
Since indices sort the same as positions, couldn't this be optimized as (you mentioned this before):
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.
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;
}
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;
}
BTW, this optimization never came up in my SAP because I (redundantly) store the Vector3 min, max in my Handle structure.
-
- Site Admin
- Posts: 4221
- Joined: Sun Jun 26, 2005 6:43 pm
- Location: California, USA
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.Erin Catto wrote:I noticed this code:
Since indices sort the same as positions, couldn't this be optimized as (you mentioned this before):
I think some of the calling code would have to be re-organized for this to work correctly.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; }
BTW, this optimization never came up in my SAP because I (redundantly) store the Vector3 min, max in my Handle structure.
Thanks,
Erwin