Got a license from Intel for VTune, thanks! First performance analysis showed unexpected slowdown due to island management. Added path-compression to UnionFind, and iterate just over island-id's, rather then all objects, when filling islands.

4 files changed, 87 insertions, 59 deletions

diff --git a/extern/bullet/Bullet/CollisionDispatch/SimulationIslandManager.cpp b/extern/bullet/Bullet/CollisionDispatch/SimulationIslandManager.cpp
index 10a7f0b6f14..75f30847ff9 100644
--- a/extern/bullet/Bullet/CollisionDispatch/SimulationIslandManager.cpp
+++ b/extern/bullet/Bullet/CollisionDispatch/SimulationIslandManager.cpp
@@ -116,88 +116,96 @@ void SimulationIslandManager::BuildAndProcessIslands(Dispatcher* dispatcher,Coll
 	
 	int numBodies  = collisionObjects.size();
 
-	for (int islandId=0;islandId<numBodies;islandId++)
-	{
-
-		std::vector<PersistentManifold*>  islandmanifold;
-		
-		//int numSleeping = 0;
+	//first calculate the number of islands, and iterate over the islands id's
 
-		bool allSleeping = true;
+	const UnionFind& uf = this->GetUnionFind();
 
-		int i;
-		for (i=0;i<numBodies;i++)
+	for (int islandId=0;islandId<uf.getNumElements();islandId++)
+	{
+		if (uf.isRoot(islandId))
 		{
-			CollisionObject* colObj0 = collisionObjects[i];
-		
-			if (colObj0->m_islandTag1 == islandId)
-			{
-			
-				if (colObj0->GetActivationState()== ACTIVE_TAG)
-				{
-					allSleeping = false;
-				}
-				if (colObj0->GetActivationState()== DISABLE_DEACTIVATION)
-				{
-					allSleeping = false;
-				}
-			}
-		}
 
-		
-		for (i=0;i<dispatcher->GetNumManifolds();i++)
-		{
-			 PersistentManifold* manifold = dispatcher->GetManifoldByIndexInternal(i);
-			 
-			 //filtering for response
+			std::vector<PersistentManifold*>  islandmanifold;
+			
+			//int numSleeping = 0;
 
-			 CollisionObject* colObj0 = static_cast<CollisionObject*>(manifold->GetBody0());
-			 CollisionObject* colObj1 = static_cast<CollisionObject*>(manifold->GetBody1());
-			 {
-				if (((colObj0) && (colObj0)->m_islandTag1 == (islandId)) ||
-					((colObj1) && (colObj1)->m_islandTag1 == (islandId)))
-				{
+			bool allSleeping = true;
 
-					if (dispatcher->NeedsResponse(*colObj0,*colObj1))
-						islandmanifold.push_back(manifold);
-				}
-			 }
-		}
-		if (allSleeping)
-		{
 			int i;
 			for (i=0;i<numBodies;i++)
 			{
 				CollisionObject* colObj0 = collisionObjects[i];
+			
 				if (colObj0->m_islandTag1 == islandId)
 				{
-					colObj0->SetActivationState( ISLAND_SLEEPING );
+				
+					if (colObj0->GetActivationState()== ACTIVE_TAG)
+					{
+						allSleeping = false;
+					}
+					if (colObj0->GetActivationState()== DISABLE_DEACTIVATION)
+					{
+						allSleeping = false;
+					}
 				}
 			}
 
 			
-		} else
-		{
-
-			int i;
-			for (i=0;i<numBodies;i++)
+			for (i=0;i<dispatcher->GetNumManifolds();i++)
 			{
-				CollisionObject* colObj0 = collisionObjects[i];
-				if (colObj0->m_islandTag1 == islandId)
+				 PersistentManifold* manifold = dispatcher->GetManifoldByIndexInternal(i);
+				 
+				 //filtering for response
+
+				 CollisionObject* colObj0 = static_cast<CollisionObject*>(manifold->GetBody0());
+				 CollisionObject* colObj1 = static_cast<CollisionObject*>(manifold->GetBody1());
+				 assert(colObj0);
+				 assert(colObj1);
+				 {
+					if (((colObj0)->m_islandTag1 == (islandId)) ||
+						((colObj1)->m_islandTag1 == (islandId)))
+					{
+						if (dispatcher->NeedsResponse(*colObj0,*colObj1))
+							islandmanifold.push_back(manifold);
+					}
+				 }
+			}
+			if (allSleeping)
+			{
+				int i;
+				for (i=0;i<numBodies;i++)
 				{
-					if ( colObj0->GetActivationState() == ISLAND_SLEEPING)
+					CollisionObject* colObj0 = collisionObjects[i];
+					if (colObj0->m_islandTag1 == islandId)
 					{
-						colObj0->SetActivationState( WANTS_DEACTIVATION);
+						colObj0->SetActivationState( ISLAND_SLEEPING );
 					}
 				}
-			}
 
-			/// Process the actual simulation, only if not sleeping/deactivated
-			if (islandmanifold.size())
+				
+			} else
 			{
-				callback->ProcessIsland(&islandmanifold[0],islandmanifold.size());
-			}
 
+				int i;
+				for (i=0;i<numBodies;i++)
+				{
+					CollisionObject* colObj0 = collisionObjects[i];
+					if (colObj0->m_islandTag1 == islandId)
+					{
+						if ( colObj0->GetActivationState() == ISLAND_SLEEPING)
+						{
+							colObj0->SetActivationState( WANTS_DEACTIVATION);
+						}
+					}
+				}
+
+				/// Process the actual simulation, only if not sleeping/deactivated
+				if (islandmanifold.size())
+				{
+					callback->ProcessIsland(&islandmanifold[0],islandmanifold.size());
+				}
+
+			}
 		}
 	}
 }
diff --git a/extern/bullet/Bullet/CollisionDispatch/UnionFind.cpp b/extern/bullet/Bullet/CollisionDispatch/UnionFind.cpp
index 8f456ea17e5..43c87bb4f61 100644
--- a/extern/bullet/Bullet/CollisionDispatch/UnionFind.cpp
+++ b/extern/bullet/Bullet/CollisionDispatch/UnionFind.cpp
@@ -24,6 +24,12 @@ int UnionFind::find(int x)
 
 	while (x != m_id[x]) 
 	{
+//not really a reason not to use path compression, and it flattens the trees/improves find performance dramatically
+#define USE_PATH_COMPRESSION 1
+#ifdef USE_PATH_COMPRESSION
+		//
+		m_id[x] = m_id[m_id[x]];
+#endif //
 		x = m_id[x];
 		assert(x < m_N);
 		assert(x >= 0);
@@ -89,6 +95,8 @@ void UnionFind ::unite(int p, int q)
 	int i = find(p), j = find(q);
 	if (i == j) 
 		return;
+
+	//weighted quick union, this keeps the 'trees' balanced, and keeps performance of unite O( log(n) )
 	if (m_sz[i] < m_sz[j])
 	{ 
 		m_id[i] = j; m_sz[j] += m_sz[i]; 
diff --git a/extern/bullet/Bullet/CollisionDispatch/UnionFind.h b/extern/bullet/Bullet/CollisionDispatch/UnionFind.h
index f7e9feb6ea0..8705e579189 100644
--- a/extern/bullet/Bullet/CollisionDispatch/UnionFind.h
+++ b/extern/bullet/Bullet/CollisionDispatch/UnionFind.h
@@ -17,6 +17,8 @@ subject to the following restrictions:
 #define UNION_FIND_H
 
 ///UnionFind calculates connected subsets
+// Implements weighted Quick Union with path compression
+// optimization: could use short ints instead of ints (halving memory, would limit the number of rigid bodies to 64k, sounds reasonable)
 class UnionFind
   {
     private:
@@ -32,6 +34,15 @@ class UnionFind
 
 	  void	reset(int N);
 
+	  inline int	getNumElements() const
+	  {
+		  return m_N;
+	  }
+	  inline bool  isRoot(int x) const
+	  {
+		  return (x == m_id[x]);
+	  }
+
       int find(int p, int q);
       void unite(int p, int q);
 
diff --git a/extern/bullet/Extras/PhysicsInterface/CcdPhysics/CcdPhysicsEnvironment.h b/extern/bullet/Extras/PhysicsInterface/CcdPhysics/CcdPhysicsEnvironment.h
index 5f111c636bf..053abcbd3e7 100644
--- a/extern/bullet/Extras/PhysicsInterface/CcdPhysics/CcdPhysicsEnvironment.h
+++ b/extern/bullet/Extras/PhysicsInterface/CcdPhysics/CcdPhysicsEnvironment.h
@@ -41,6 +41,7 @@ class PersistentManifold;
 class BroadphaseInterface;
 class OverlappingPairCache;
 class IDebugDraw;
+class PHY_IVehicle;
 
 /// CcdPhysicsEnvironment is experimental mainloop for physics simulation using optional continuous collision detection.
 /// Physics Environment takes care of stepping the simulation and is a container for physics entities.
@@ -135,7 +136,7 @@ protected:
 			);
 
 
-	    virtual void		`straint(int	constraintid);
+	    virtual void		removeConstraint(int	constraintid);
 
 		virtual float		getAppliedImpulse(int	constraintid);