View difference between Paste ID: WTihivb1 and RqNmfEVq

 /*
-* Copyright (c) 2006-2011 Erin Catto http://www.box2d.org
+* Copyright (c) 2006-2009 Erin Catto http://www.box2d.org
 *
 * This software is provided 'as-is', without any express or implied
 * warranty.  In no event will the authors be held liable for any damages
 * arising from the use of this software.
 * Permission is granted to anyone to use this software for any purpose,
 * including commercial applications, and to alter it and redistribute it
 * freely, subject to the following restrictions:
 * 1. The origin of this software must not be misrepresented; you must not
 * claim that you wrote the original software. If you use this software
 * in a product, an acknowledgment in the product documentation would be
 * appreciated but is not required.
 * 2. Altered source versions must be plainly marked as such, and must not be
 * misrepresented as being the original software.
 * 3. This notice may not be removed or altered from any source distribution.
 */
 
-#include <Box2D/Dynamics/b2World.h>
+#ifndef B2_BROAD_PHASE_H
-#include <Box2D/Dynamics/b2Body.h>
+#define B2_BROAD_PHASE_H
-#include <Box2D/Dynamics/b2Fixture.h>
+
-#include <Box2D/Dynamics/b2Island.h>
+#include <Box2D/Common/b2Settings.h>
-#include <Box2D/Dynamics/Joints/b2PulleyJoint.h>
+
-#include <Box2D/Dynamics/Contacts/b2Contact.h>
+#include <Box2D/Collision/b2DynamicTree.h>
-#include <Box2D/Dynamics/Contacts/b2ContactSolver.h>
+//#include <algorithm>
 #include <stdlib.h>
-#include <Box2D/Collision/b2BroadPhase.h>
+
-#include <Box2D/Collision/Shapes/b2CircleShape.h>
+
-#include <Box2D/Collision/Shapes/b2EdgeShape.h>
+
-#include <Box2D/Collision/Shapes/b2ChainShape.h>
+
-#include <Box2D/Collision/Shapes/b2PolygonShape.h>
+struct b2Pair
-#include <Box2D/Collision/b2TimeOfImpact.h>
+
-#include <Box2D/Common/b2Draw.h>
+	int32 proxyIdA;
-#include <Box2D/Common/b2Timer.h>
+	int32 proxyIdB;
-#include <new>
+
 
 /// The broad-phase is used for computing pairs and performing volume queries and ray casts.
 /// This broad-phase does not persist pairs. Instead, this reports potentially new pairs.
 /// It is up to the client to consume the new pairs and to track subsequent overlap.
-b2World::b2World(const b2Vec2& gravity)
+class b2BroadPhase
 {
-	m_destructionListener = NULL;
+public:
-	g_debugDraw = NULL;
+
 	enum
-	m_bodyList = NULL;
+
-	m_jointList = NULL;
+		e_nullProxy = -1
 	};
-	m_bodyCount = 0;
+
-	m_jointCount = 0;
+	b2BroadPhase();
 	~b2BroadPhase();
-	m_warmStarting = true;
+
-	m_continuousPhysics = true;
+	/// Create a proxy with an initial AABB. Pairs are not reported until
-	m_subStepping = false;
+	/// UpdatePairs is called.
 	int32 CreateProxy(const b2AABB& aabb, void* userData);
-	m_stepComplete = true;
+
 	/// Destroy a proxy. It is up to the client to remove any pairs.
-	m_allowSleep = true;
+	void DestroyProxy(int32 proxyId);
-	m_gravity = gravity;
+
 	/// Call MoveProxy as many times as you like, then when you are done
-	m_flags = e_clearForces;
+	/// call UpdatePairs to finalized the proxy pairs (for your time step).
 	void MoveProxy(int32 proxyId, const b2AABB& aabb, const b2Vec2& displacement);
-	m_inv_dt0 = 0.0f;
+
 	/// Call to trigger a re-processing of it's pairs on the next call to UpdatePairs.
-	m_contactManager.m_allocator = &m_blockAllocator;
+	void TouchProxy(int32 proxyId);
 
-	memset(&m_profile, 0, sizeof(b2Profile));
+	/// Get the fat AABB for a proxy.
 	const b2AABB& GetFatAABB(int32 proxyId) const;
 
-b2World::~b2World()
+	/// Get user data from a proxy. Returns NULL if the id is invalid.
 	void* GetUserData(int32 proxyId) const;
-	// Some shapes allocate using b2Alloc.
+
-	b2Body* b = m_bodyList;
+	/// Test overlap of fat AABBs.
-	while (b)
+	bool TestOverlap(int32 proxyIdA, int32 proxyIdB) const;
 
-		b2Body* bNext = b->m_next;
+	/// Get the number of proxies.
 	int32 GetProxyCount() const;
-		b2Fixture* f = b->m_fixtureList;
+
-		while (f)
+	/// Update the pairs. This results in pair callbacks. This can only add pairs.
 	template <typename T>
-			b2Fixture* fNext = f->m_next;
+	void UpdatePairs(T* callback);
-			f->m_proxyCount = 0;
+
-			f->Destroy(&m_blockAllocator);
+	/// Query an AABB for overlapping proxies. The callback class
-			f = fNext;
+	/// is called for each proxy that overlaps the supplied AABB.
 	template <typename T>
 	void Query(T* callback, const b2AABB& aabb) const;
-		b = bNext;
+
 	/// Ray-cast against the proxies in the tree. This relies on the callback
 	/// to perform a exact ray-cast in the case were the proxy contains a shape.
 	/// The callback also performs the any collision filtering. This has performance
-void b2World::SetDestructionListener(b2DestructionListener* listener)
+	/// roughly equal to k * log(n), where k is the number of collisions and n is the
 	/// number of proxies in the tree.
-	m_destructionListener = listener;
+	/// @param input the ray-cast input data. The ray extends from p1 to p1 + maxFraction * (p2 - p1).
 	/// @param callback a callback class that is called for each proxy that is hit by the ray.
 	template <typename T>
-void b2World::SetContactFilter(b2ContactFilter* filter)
+	void RayCast(T* callback, const b2RayCastInput& input) const;
 
-	m_contactManager.m_contactFilter = filter;
+	/// Get the height of the embedded tree.
 	int32 GetTreeHeight() const;
 
-void b2World::SetContactListener(b2ContactListener* listener)
+	/// Get the balance of the embedded tree.
 	int32 GetTreeBalance() const;
-	m_contactManager.m_contactListener = listener;
+
 	/// Get the quality metric of the embedded tree.
 	float32 GetTreeQuality() const;
-void b2World::SetDebugDraw(b2Draw* debugDraw)
+
 	/// Shift the world origin. Useful for large worlds.
-	g_debugDraw = debugDraw;
+	/// The shift formula is: position -= newOrigin
 	/// @param newOrigin the new origin with respect to the old origin
 	void ShiftOrigin(const b2Vec2& newOrigin);
-b2Body* b2World::CreateBody(const b2BodyDef* def)
+
 private:
-	b2Assert(IsLocked() == false);
+
-	if (IsLocked())
+	friend class b2DynamicTree;
 
-		return NULL;
+	void BufferMove(int32 proxyId);
 	void UnBufferMove(int32 proxyId);
 
-	void* mem = m_blockAllocator.Allocate(sizeof(b2Body));
+	bool QueryCallback(int32 proxyId);
-	b2Body* b = new (mem) b2Body(def, this);
+
 	b2DynamicTree m_tree;
-	// Add to world doubly linked list.
+
-	b->m_prev = NULL;
+	int32 m_proxyCount;
-	b->m_next = m_bodyList;
+
-	if (m_bodyList)
+	int32* m_moveBuffer;
 	int32 m_moveCapacity;
-		m_bodyList->m_prev = b;
+	int32 m_moveCount;
 
-	m_bodyList = b;
+	b2Pair* m_pairBuffer;
-	++m_bodyCount;
+	int32 m_pairCapacity;
 	int32 m_pairCount;
-	return b;
+
 	int32 m_queryProxyId;
 };
-void b2World::DestroyBody(b2Body* b)
+
 //The return value of this function should represent whether elem1 is considered less than,
-	b2Assert(m_bodyCount > 0);
+//equal to, or greater than elem2 by returning, respectively, a negative value, zero or a positive value.
-	b2Assert(IsLocked() == false);
+inline int b2PairCompareQSort(const void * elem1, const void * elem2)
-	if (IsLocked())
+
    b2Pair* pair1 = (b2Pair*) elem1;
-		return;
+   b2Pair* pair2 = (b2Pair*) elem2;
 
    if (pair1->proxyIdA < pair2->proxyIdA)
-	// Delete the attached joints.
+   {
-	b2JointEdge* je = b->m_jointList;
+      return -1;
-	while (je)
+   }
 
-		b2JointEdge* je0 = je;
+   if (pair1->proxyIdA == pair2->proxyIdA)
-		je = je->next;
+   {
       if( pair1->proxyIdB < pair2->proxyIdB ) {
-		if (m_destructionListener)
+         return -1;
       }
-			m_destructionListener->SayGoodbye(je0->joint);
+      else if(pair1->proxyIdB > pair2->proxyIdB) {
          return 1;
       }
-		DestroyJoint(je0->joint);
+      else {
          return 0;
-		b->m_jointList = je;
+      }
    }
-	b->m_jointList = NULL;
+   else {
       return 1;
-	// Delete the attached contacts.
+   }
-	b2ContactEdge* ce = b->m_contactList;
+
-	while (ce)
+
 
-		b2ContactEdge* ce0 = ce;
+/// This is used to sort pairs.
-		ce = ce->next;
+inline bool b2PairLessThan(const b2Pair& pair1, const b2Pair& pair2)
-		m_contactManager.Destroy(ce0->contact);
+
 	if (pair1.proxyIdA < pair2.proxyIdA)
-	b->m_contactList = NULL;
+
 		return true;
-	// Delete the attached fixtures. This destroys broad-phase proxies.
+
-	b2Fixture* f = b->m_fixtureList;
+
-	while (f)
+	if (pair1.proxyIdA == pair2.proxyIdA)
 	{
-		b2Fixture* f0 = f;
+		return pair1.proxyIdB < pair2.proxyIdB;
-		f = f->m_next;
+
 
-		if (m_destructionListener)
+	return false;
 }
-			m_destructionListener->SayGoodbye(f0);
+
 inline void* b2BroadPhase::GetUserData(int32 proxyId) const
 {
-		f0->DestroyProxies(&m_contactManager.m_broadPhase);
+	return m_tree.GetUserData(proxyId);
-		f0->Destroy(&m_blockAllocator);
+
-		f0->~b2Fixture();
+
-		m_blockAllocator.Free(f0, sizeof(b2Fixture));
+inline bool b2BroadPhase::TestOverlap(int32 proxyIdA, int32 proxyIdB) const
 {
-		b->m_fixtureList = f;
+	const b2AABB& aabbA = m_tree.GetFatAABB(proxyIdA);
-		b->m_fixtureCount -= 1;
+	const b2AABB& aabbB = m_tree.GetFatAABB(proxyIdB);
 	return b2TestOverlap(aabbA, aabbB);
-	b->m_fixtureList = NULL;
+
-	b->m_fixtureCount = 0;
+
 inline const b2AABB& b2BroadPhase::GetFatAABB(int32 proxyId) const
-	// Remove world body list.
+
-	if (b->m_prev)
+	return m_tree.GetFatAABB(proxyId);
 }
-		b->m_prev->m_next = b->m_next;
+
 inline int32 b2BroadPhase::GetProxyCount() const
 {
-	if (b->m_next)
+	return m_proxyCount;
 }
-		b->m_next->m_prev = b->m_prev;
+
 inline int32 b2BroadPhase::GetTreeHeight() const
 {
-	if (b == m_bodyList)
+	return m_tree.GetHeight();
 }
-		m_bodyList = b->m_next;
+
 inline int32 b2BroadPhase::GetTreeBalance() const
 {
-	--m_bodyCount;
+	return m_tree.GetMaxBalance();
-	b->~b2Body();
+
-	m_blockAllocator.Free(b, sizeof(b2Body));
+
 inline float32 b2BroadPhase::GetTreeQuality() const
 {
-b2Joint* b2World::CreateJoint(const b2JointDef* def)
+	return m_tree.GetAreaRatio();
 }
-	b2Assert(IsLocked() == false);
+
-	if (IsLocked())
+template <typename T>
 void b2BroadPhase::UpdatePairs(T* callback)
-		return NULL;
+
 
 	printf("\n");
-	b2Joint* j = b2Joint::Create(def, &m_blockAllocator);
+	printf("{");
 	printf("%d",m_moveCount);
-	// Connect to the world list.
+
-	j->m_prev = NULL;
+
-	j->m_next = m_jointList;
+
-	if (m_jointList)
+	// Reset pair buffer
 	m_pairCount = 0;
-		m_jointList->m_prev = j;
+
 	// Perform tree queries for all moving proxies.
-	m_jointList = j;
+	for (int32 i = 0; i < m_moveCount; ++i)
-	++m_jointCount;
+
 		m_queryProxyId = m_moveBuffer[i];
-	// Connect to the bodies' doubly linked lists.
+		if (m_queryProxyId == e_nullProxy)
-	j->m_edgeA.joint = j;
+
-	j->m_edgeA.other = j->m_bodyB;
+
-	j->m_edgeA.prev = NULL;
+
-	j->m_edgeA.next = j->m_bodyA->m_jointList;
+
-	if (j->m_bodyA->m_jointList) j->m_bodyA->m_jointList->prev = &j->m_edgeA;
+		// We have to query the tree with the fat AABB so that
-	j->m_bodyA->m_jointList = &j->m_edgeA;
+		// we don't fail to create a pair that may touch later.
 		const b2AABB& fatAABB = m_tree.GetFatAABB(m_queryProxyId);
-	j->m_edgeB.joint = j;
+
-	j->m_edgeB.other = j->m_bodyA;
+		// Query tree, create pairs and add them pair buffer.
-	j->m_edgeB.prev = NULL;
+		m_tree.Query(this, fatAABB);
-	j->m_edgeB.next = j->m_bodyB->m_jointList;
+
-	if (j->m_bodyB->m_jointList) j->m_bodyB->m_jointList->prev = &j->m_edgeB;
+
-	j->m_bodyB->m_jointList = &j->m_edgeB;
+	// Reset move buffer
 	m_moveCount = 0;
-	b2Body* bodyA = def->bodyA;
+
-	b2Body* bodyB = def->bodyB;
+	// Sort the pair buffer to expose duplicates.
 	//std::sort(m_pairBuffer, m_pairBuffer + m_pairCount, b2PairLessThan);
-	// If the joint prevents collisions, then flag any contacts for filtering.
+
-	if (def->collideConnected == false)
+	// FIX from http://www.box2d.org/forum/viewtopic.php?f=7&t=4756&start=0 to get rid of stl dependency
 	qsort(m_pairBuffer, sizeof(m_pairBuffer) / sizeof(struct b2Pair) , sizeof(struct b2Pair), b2PairCompareQSort);
-		b2ContactEdge* edge = bodyB->GetContactList();
+	// Send the pairs back to the client.
-		while (edge)
+
 	int32 i = 0;
-			if (edge->other == bodyA)
+
 	printf("|");
-				// Flag the contact for filtering at the next time step (where either
+	printf("%d",m_pairCount);
-				// body is awake).
+
-				edge->contact->FlagForFiltering();
+
 
 	while (i < m_pairCount)
-			edge = edge->next;
+
 		b2Pair* primaryPair = m_pairBuffer + i;
 		void* userDataA = m_tree.GetUserData(primaryPair->proxyIdA);
 		void* userDataB = m_tree.GetUserData(primaryPair->proxyIdB);
-	// Note: creating a joint doesn't wake the bodies.
+
 		callback->AddPair(userDataA, userDataB);
-	return j;
+
 
 		// Skip any duplicate pairs.
-void b2World::DestroyJoint(b2Joint* j)
+		while (i < m_pairCount)
 		{
-	b2Assert(IsLocked() == false);
+			b2Pair* pair = m_pairBuffer + i;
-	if (IsLocked())
+			if (pair->proxyIdA != primaryPair->proxyIdA || pair->proxyIdB != primaryPair->proxyIdB)
 			{
-		return;
+				break;
 			}
 			++i;
-	bool collideConnected = j->m_collideConnected;
+
 	}
-	// Remove from the doubly linked list.
+
-	if (j->m_prev)
+	printf("{*}");
 	fflush(stdout);
-		j->m_prev->m_next = j->m_next;
+
 	// Try to keep the tree balanced.
 	//m_tree.Rebalance(4);
-	if (j->m_next)
+
 
-		j->m_next->m_prev = j->m_prev;
+template <typename T>
 inline void b2BroadPhase::Query(T* callback, const b2AABB& aabb) const
 {
-	if (j == m_jointList)
+	m_tree.Query(callback, aabb);
 }
-		m_jointList = j->m_next;
+
 template <typename T>
 inline void b2BroadPhase::RayCast(T* callback, const b2RayCastInput& input) const
-	// Disconnect from island graph.
+
-	b2Body* bodyA = j->m_bodyA;
+	m_tree.RayCast(callback, input);
-	b2Body* bodyB = j->m_bodyB;
+
 
-	// Wake up connected bodies.
+inline void b2BroadPhase::ShiftOrigin(const b2Vec2& newOrigin)
-	bodyA->SetAwake(true);
+
-	bodyB->SetAwake(true);
+	m_tree.ShiftOrigin(newOrigin);
 }
-	// Remove from body 1.
+
-	if (j->m_edgeA.prev)
+#endif