BGE bug #17491 fixed: BGE, Dupli instance with different scale, massive slowdown.

The root cause of this bug is the fact that Bullet shapes 
are shared between duplicated game objects. As the physics
object scale is stored in the shape, all duplicas must 
have the same scale otherwise the physics representation
is incorrect.
This fix introduces a mechanism to duplicate shapes at
runtime so that Bullet shapes are not shared anymore.
The drawback is an increased memory consuption. 
A reference count mechanism will be introduced in a 
later revision to keep Bullet shape shared between
duplicas that have the same scale.

4 files changed, 359 insertions, 14 deletions

diff --git a/source/gameengine/Physics/Bullet/CcdPhysicsController.cpp b/source/gameengine/Physics/Bullet/CcdPhysicsController.cpp
index b872fae6138..a28af5f9635 100644
--- a/source/gameengine/Physics/Bullet/CcdPhysicsController.cpp
+++ b/source/gameengine/Physics/Bullet/CcdPhysicsController.cpp
@@ -18,6 +18,7 @@ subject to the following restrictions:
 
 #include "PHY_IMotionState.h"
 #include "CcdPhysicsEnvironment.h"
+#include "RAS_MeshObject.h"
 
 
 class BP_Proxy;
@@ -44,7 +45,14 @@ CcdPhysicsController::CcdPhysicsController (const CcdConstructionInfo& ci)
 	m_newClientInfo = 0;
 	m_registerCount = 0;
 		
+	// copy pointers locally to allow smart release
 	m_MotionState = ci.m_MotionState;
+	m_collisionShape = ci.m_collisionShape;
+	// shape info is shared, increment ref count
+	m_shapeInfo = ci.m_shapeInfo;
+	if (m_shapeInfo)
+		m_shapeInfo->AddRef();
+	
 	m_bulletMotionState = 0;
 	
 	
@@ -116,7 +124,7 @@ void CcdPhysicsController::CreateRigidbody()
 
 	m_body = new btRigidBody(m_cci.m_mass,
 		m_bulletMotionState,
-		m_cci.m_collisionShape,
+		m_collisionShape,
 		m_cci.m_localInertiaTensor * m_cci.m_inertiaFactor,
 		m_cci.m_linearDamping,m_cci.m_angularDamping,
 		m_cci.m_friction,m_cci.m_restitution);
@@ -144,6 +152,19 @@ void CcdPhysicsController::CreateRigidbody()
 	}
 }
 
+static void DeleteBulletShape(btCollisionShape* shape)
+{
+	if (shape->getShapeType() == TRIANGLE_MESH_SHAPE_PROXYTYPE)
+	{
+		// shapes based on meshes use an interface that contains the vertices.
+		btTriangleMeshShape* meshShape = static_cast<btTriangleMeshShape*>(shape);
+		btStridingMeshInterface* meshInterface = meshShape->getMeshInterface();
+		if (meshInterface)
+			delete meshInterface;
+	}
+	delete shape;
+}
+
 CcdPhysicsController::~CcdPhysicsController()
 {
 	//will be reference counted, due to sharing
@@ -155,6 +176,27 @@ CcdPhysicsController::~CcdPhysicsController()
 	if (m_bulletMotionState)
 		delete m_bulletMotionState;
 	delete m_body;
+
+	if (m_collisionShape)
+	{
+		// collision shape is always unique to the controller, can delete it here
+		if (m_collisionShape->isCompound())
+		{
+			// bullet does not delete the child shape, must do it here
+			btCompoundShape* compoundShape = (btCompoundShape*)m_collisionShape;
+			int numChild = compoundShape->getNumChildShapes();
+			for (int i=numChild-1 ; i >= 0; i--)
+			{
+				btCollisionShape* childShape = compoundShape->getChildShape(i);
+				DeleteBulletShape(childShape);
+			}
+		}
+		DeleteBulletShape(m_collisionShape);
+	}
+	if (m_shapeInfo)
+	{
+		m_shapeInfo->Release();
+	}
 }
 
 
@@ -219,11 +261,33 @@ void		CcdPhysicsController::PostProcessReplica(class PHY_IMotionState* motionsta
 {
 	m_MotionState = motionstate;
 	m_registerCount = 0;
-	
+	m_collisionShape = NULL;
+
+	// always create a new shape to avoid scaling bug
+	if (m_shapeInfo)
+	{
+		m_shapeInfo->AddRef();
+		m_collisionShape = m_shapeInfo->CreateBulletShape();
+
+		if (m_collisionShape)
+		{
+			// new shape has no scaling, apply initial scaling
+			m_collisionShape->setLocalScaling(m_cci.m_scaling);
+			if (m_cci.m_mass)
+				m_collisionShape->calculateLocalInertia(m_cci.m_mass, m_cci.m_localInertiaTensor);
+		}
+	}
 
 	m_body = 0;
 	CreateRigidbody();
-	
+
+	if (m_body)
+	{
+		if (m_cci.m_mass)
+		{
+			m_body->setMassProps(m_cci.m_mass, m_cci.m_localInertiaTensor * m_cci.m_inertiaFactor);
+		} 
+	}			
 	m_cci.m_physicsEnv->addCcdPhysicsController(this);
 
 
@@ -597,29 +661,32 @@ bool CcdPhysicsController::wantsSleeping()
 
 PHY_IPhysicsController*	CcdPhysicsController::GetReplica()
 {
-	//very experimental, shape sharing is not implemented yet.
-	//just support btSphereShape/ConeShape for now
-
+	// This is used only to replicate Near and Radar sensor controllers
+	// The replication of object physics controller is done in KX_BulletPhysicsController::GetReplica()
 	CcdConstructionInfo cinfo = m_cci;
-	if (cinfo.m_collisionShape)
+	if (m_shapeInfo)
+	{
+		// This situation does not normally happen
+		cinfo.m_collisionShape = m_shapeInfo->CreateBulletShape();
+	} 
+	else if (m_collisionShape)
 	{
-		switch (cinfo.m_collisionShape->getShapeType())
+		switch (m_collisionShape->getShapeType())
 		{
 		case SPHERE_SHAPE_PROXYTYPE:
 			{
-				btSphereShape* orgShape = (btSphereShape*)cinfo.m_collisionShape;
+				btSphereShape* orgShape = (btSphereShape*)m_collisionShape;
 				cinfo.m_collisionShape = new btSphereShape(*orgShape);
 				break;
 			}
 
-			case CONE_SHAPE_PROXYTYPE:
+		case CONE_SHAPE_PROXYTYPE:
 			{
-				btConeShape* orgShape = (btConeShape*)cinfo.m_collisionShape;
+				btConeShape* orgShape = (btConeShape*)m_collisionShape;
 				cinfo.m_collisionShape = new btConeShape(*orgShape);
 				break;
 			}
 
-
 		default:
 			{
 				return 0;
@@ -628,6 +695,7 @@ PHY_IPhysicsController*	CcdPhysicsController::GetReplica()
 	}
 
 	cinfo.m_MotionState = new DefaultMotionState();
+	cinfo.m_shapeInfo = m_shapeInfo;
 
 	CcdPhysicsController* replica = new CcdPhysicsController(cinfo);
 	return replica;
@@ -689,3 +757,198 @@ void	DefaultMotionState::calculateWorldTransformations()
 
 }
 
+// Shape constructor
+bool CcdShapeConstructionInfo::SetMesh(RAS_MeshObject* meshobj, bool polytope)
+{
+	// assume no shape information
+	m_shapeType = PHY_SHAPE_NONE;
+	m_vertexArray.clear();
+
+	if (!meshobj)
+		return false;
+
+	// Mesh has no polygons!
+	int numpolys = meshobj->NumPolygons();
+	if (!numpolys)
+	{
+		return false;
+	}
+
+	// check that we have at least one colliding polygon
+	int numvalidpolys = 0;
+
+	for (int p=0; p<numpolys; p++)
+	{
+		RAS_Polygon* poly = meshobj->GetPolygon(p);
+
+		// only add polygons that have the collisionflag set
+		if (poly->IsCollider())
+		{
+			numvalidpolys++;
+			break;
+		}
+	}
+
+	// No collision polygons
+	if (numvalidpolys < 1)
+		return false;
+
+	m_shapeType = (polytope) ? PHY_SHAPE_POLYTOPE : PHY_SHAPE_MESH;
+
+	numvalidpolys = 0;
+
+	for (int p2=0; p2<numpolys; p2++)
+	{
+		RAS_Polygon* poly = meshobj->GetPolygon(p2);
+
+		// only add polygons that have the collisionflag set
+		if (poly->IsCollider())
+		{   
+			//Bullet can raycast any shape, so
+			if (polytope)
+			{
+				for (int i=0;i<poly->VertexCount();i++)
+				{
+					const float* vtx = meshobj->GetVertex(poly->GetVertexIndexBase().m_vtxarray, 
+						poly->GetVertexIndexBase().m_indexarray[i],
+						poly->GetMaterial()->GetPolyMaterial())->getLocalXYZ();
+					btPoint3 point(vtx[0],vtx[1],vtx[2]);
+					m_vertexArray.push_back(point);
+					numvalidpolys++;
+				}
+			} else
+			{
+				{
+					const float* vtx = meshobj->GetVertex(poly->GetVertexIndexBase().m_vtxarray, 
+						poly->GetVertexIndexBase().m_indexarray[2],
+						poly->GetMaterial()->GetPolyMaterial())->getLocalXYZ();
+					btPoint3 vertex0(vtx[0],vtx[1],vtx[2]);
+					vtx = meshobj->GetVertex(poly->GetVertexIndexBase().m_vtxarray, 
+						poly->GetVertexIndexBase().m_indexarray[1],
+						poly->GetMaterial()->GetPolyMaterial())->getLocalXYZ();
+					btPoint3 vertex1(vtx[0],vtx[1],vtx[2]);
+					vtx = meshobj->GetVertex(poly->GetVertexIndexBase().m_vtxarray, 
+						poly->GetVertexIndexBase().m_indexarray[0],
+						poly->GetMaterial()->GetPolyMaterial())->getLocalXYZ();
+					btPoint3 vertex2(vtx[0],vtx[1],vtx[2]);
+					m_vertexArray.push_back(vertex0);
+					m_vertexArray.push_back(vertex1);
+					m_vertexArray.push_back(vertex2);
+					numvalidpolys++;
+				}
+				if (poly->VertexCount() == 4)
+				{
+					const float* vtx = meshobj->GetVertex(poly->GetVertexIndexBase().m_vtxarray, 
+						poly->GetVertexIndexBase().m_indexarray[3],
+						poly->GetMaterial()->GetPolyMaterial())->getLocalXYZ();
+					btPoint3 vertex0(vtx[0],vtx[1],vtx[2]);
+					vtx = meshobj->GetVertex(poly->GetVertexIndexBase().m_vtxarray, 
+						poly->GetVertexIndexBase().m_indexarray[2],
+						poly->GetMaterial()->GetPolyMaterial())->getLocalXYZ();
+					btPoint3 vertex1(vtx[0],vtx[1],vtx[2]);
+					vtx = meshobj->GetVertex(poly->GetVertexIndexBase().m_vtxarray, 
+						poly->GetVertexIndexBase().m_indexarray[0],
+						poly->GetMaterial()->GetPolyMaterial())->getLocalXYZ();
+					btPoint3 vertex2(vtx[0],vtx[1],vtx[2]);
+					m_vertexArray.push_back(vertex0);
+					m_vertexArray.push_back(vertex1);
+					m_vertexArray.push_back(vertex2);
+					numvalidpolys++;
+				}
+			}		
+		}
+	}
+
+	if (!numvalidpolys)
+	{
+		// should not happen
+		m_shapeType = PHY_SHAPE_NONE;
+		return false;
+	}
+	return true;
+}
+
+btCollisionShape* CcdShapeConstructionInfo::CreateBulletShape()
+{
+	btCollisionShape* collisionShape = 0;
+	btTriangleMeshShape* concaveShape = 0;
+	btTriangleMesh* collisionMeshData = 0;
+	btCompoundShape* compoundShape = 0;
+	CcdShapeConstructionInfo* nextShapeInfo;
+
+	switch (m_shapeType) 
+	{
+	case PHY_SHAPE_BOX:
+		collisionShape = new btBoxShape(m_halfExtend);
+		break;
+
+	case PHY_SHAPE_SPHERE:
+		collisionShape = new btSphereShape(m_radius);
+		break;
+
+	case PHY_SHAPE_CYLINDER:
+		collisionShape = new btCylinderShapeZ(m_halfExtend);
+		break;
+
+	case PHY_SHAPE_CONE:
+		collisionShape = new btConeShapeZ(m_radius, m_height);
+		break;
+
+	case PHY_SHAPE_POLYTOPE:
+		collisionShape = new btConvexHullShape(&m_vertexArray.begin()->getX(), m_vertexArray.size());
+		break;
+
+	case PHY_SHAPE_MESH:
+		collisionMeshData = new btTriangleMesh();
+		// m_vertexArray is necessarily a multiple of 3
+		for (std::vector<btPoint3>::iterator it=m_vertexArray.begin(); it != m_vertexArray.end(); )
+		{
+            collisionMeshData->addTriangle(*it++,*it++,*it++);
+		}
+		concaveShape = new btBvhTriangleMeshShape( collisionMeshData, true );
+		concaveShape->recalcLocalAabb();
+		collisionShape = concaveShape;
+		break;
+
+	case PHY_SHAPE_COMPOUND:
+		if (m_nextShape)
+		{
+			compoundShape = new btCompoundShape();
+			for (nextShapeInfo=m_nextShape; nextShapeInfo; nextShapeInfo = nextShapeInfo->m_nextShape)
+			{
+				collisionShape = nextShapeInfo->CreateBulletShape();
+				if (collisionShape)
+				{
+					compoundShape->addChildShape(nextShapeInfo->m_childTrans, collisionShape);
+				}
+			}
+			collisionShape = compoundShape;
+		}
+	}
+	return collisionShape;
+}
+
+void CcdShapeConstructionInfo::AddShape(CcdShapeConstructionInfo* shapeInfo)
+{
+	CcdShapeConstructionInfo* nextShape = this;
+	while (nextShape->m_nextShape != NULL)
+		nextShape = nextShape->m_nextShape;
+	nextShape->m_nextShape = shapeInfo;
+}
+
+CcdShapeConstructionInfo::~CcdShapeConstructionInfo()
+{
+	CcdShapeConstructionInfo* childShape = m_nextShape;
+
+	while (childShape)
+	{
+		CcdShapeConstructionInfo* nextShape = childShape->m_nextShape;
+		childShape->m_nextShape = NULL;
+		childShape->Release();
+		childShape = nextShape;
+	}
+	
+	m_vertexArray.clear();
+}
+
+
diff --git a/source/gameengine/Physics/Bullet/CcdPhysicsController.h b/source/gameengine/Physics/Bullet/CcdPhysicsController.h
index 448e5622eff..1e1a38aa2a6 100644
--- a/source/gameengine/Physics/Bullet/CcdPhysicsController.h
+++ b/source/gameengine/Physics/Bullet/CcdPhysicsController.h
@@ -17,11 +17,14 @@ subject to the following restrictions:
 #ifndef BULLET2_PHYSICSCONTROLLER_H
 #define BULLET2_PHYSICSCONTROLLER_H
 
+#include <vector>
+
 #include "PHY_IPhysicsController.h"
 
 ///	PHY_IPhysicsController is the abstract simplified Interface to a physical object.
 ///	It contains the IMotionState and IDeformableMesh Interfaces.
 #include "btBulletDynamicsCommon.h"
+#include "LinearMath/btTransform.h"
 
 #include "PHY_IMotionState.h"
 
@@ -31,8 +34,66 @@ extern float gAngularSleepingTreshold;
 extern bool gDisableDeactivation;
 class CcdPhysicsEnvironment;
 class btMotionState;
+class RAS_MeshObject;
+class btCollisionShape;
+
+// Shape contructor
+// It contains all the information needed to create a simple bullet shape at runtime
+class CcdShapeConstructionInfo
+{
+public:
+	CcdShapeConstructionInfo() :
+		m_shapeType(PHY_SHAPE_NONE),
+		m_radius(1.0),
+		m_height(1.0),
+		m_halfExtend(0.f,0.f,0.f),
+		m_nextShape(NULL),
+		m_refCount(1)
+	{
+		m_childTrans.setIdentity();
+	}
 
+	~CcdShapeConstructionInfo();
 
+	CcdShapeConstructionInfo* AddRef()
+	{ 
+		m_refCount++;
+		return this;
+	}
+
+	int Release()
+	{
+		if (--m_refCount > 0)
+			return m_refCount;
+		delete this;
+		return 0;
+	}
+
+	void AddShape(CcdShapeConstructionInfo* shapeInfo);
+
+	CcdShapeConstructionInfo* GetNextShape()
+	{
+		return m_nextShape;
+	}
+
+	bool SetMesh(RAS_MeshObject* mesh, bool polytope);
+
+	btCollisionShape* CreateBulletShape();
+
+	// member variables
+	PHY_ShapeType			m_shapeType;
+	btScalar				m_radius;
+	btScalar				m_height;
+	btVector3				m_halfExtend;
+	btTransform				m_childTrans;
+	std::vector<btPoint3>	m_vertexArray;	// Contains both vertex array for polytope shape and
+											// triangle array for concave mesh shape.
+											// In this case a triangle is made of 3 consecutive points
+protected:
+	CcdShapeConstructionInfo* m_nextShape;	// for compound shape
+	int						m_refCount;		// this class is shared between replicas
+											// keep track of users so that we can release it 
+};
 
 struct CcdConstructionInfo
 {
@@ -65,6 +126,7 @@ struct CcdConstructionInfo
 		m_collisionFilterMask(AllFilter),
 		m_collisionShape(0),
 		m_MotionState(0),
+		m_shapeInfo(0),
 		m_physicsEnv(0),
 		m_inertiaFactor(1.f)
 	{
@@ -89,8 +151,11 @@ struct CcdConstructionInfo
 	short int	m_collisionFilterGroup;
 	short int	m_collisionFilterMask;
 
+	///these pointers are used as argument passing for the CcdPhysicsController constructor
+	///and not anymore after that
 	class btCollisionShape*	m_collisionShape;
 	class PHY_IMotionState*	m_MotionState;
+	class CcdShapeConstructionInfo* m_shapeInfo;
 	
 	CcdPhysicsEnvironment*	m_physicsEnv; //needed for self-replication
 	float	m_inertiaFactor;//tweak the inertia (hooked up to Blender 'formfactor'
@@ -106,6 +171,9 @@ class CcdPhysicsController : public PHY_IPhysicsController
 	btRigidBody* m_body;
 	class PHY_IMotionState*		m_MotionState;
 	btMotionState* 	m_bulletMotionState;
+	class btCollisionShape*	m_collisionShape;
+	class CcdShapeConstructionInfo* m_shapeInfo;
+
 	friend class CcdPhysicsEnvironment;	// needed when updating the controller
 
 
@@ -137,6 +205,7 @@ class CcdPhysicsController : public PHY_IPhysicsController
 
 
 		btRigidBody* GetRigidBody() { return m_body;}
+		CcdShapeConstructionInfo* GetShapeInfo() { return m_shapeInfo; }
 
 		btCollisionShape*	GetCollisionShape() { 
 			return m_body->getCollisionShape();
diff --git a/source/gameengine/Physics/Bullet/CcdPhysicsEnvironment.cpp b/source/gameengine/Physics/Bullet/CcdPhysicsEnvironment.cpp
index dfbcf115fd7..d8e05fab839 100644
--- a/source/gameengine/Physics/Bullet/CcdPhysicsEnvironment.cpp
+++ b/source/gameengine/Physics/Bullet/CcdPhysicsEnvironment.cpp
@@ -1370,8 +1370,9 @@ int			CcdPhysicsEnvironment::createConstraint(class PHY_IPhysicsController* ctrl
 PHY_IPhysicsController* CcdPhysicsEnvironment::CreateConeController(float coneradius,float coneheight)
 {
 	CcdConstructionInfo	cinfo;
-	//This is a memory leak: Bullet does not delete the shape and it cannot be added to 
-	//the KX_Scene.m_shapes list -- too bad but that's not a lot of data
+
+	// we don't need a CcdShapeConstructionInfo for this shape:
+	// it is simple enough for the standard copy constructor (see CcdPhysicsController::GetReplica)
 	cinfo.m_collisionShape = new btConeShape(coneradius,coneheight);
 	cinfo.m_MotionState = 0;
 	cinfo.m_physicsEnv = this;
diff --git a/source/gameengine/Physics/common/PHY_DynamicTypes.h b/source/gameengine/Physics/common/PHY_DynamicTypes.h
index c289b9d8bcb..3b3e42c38d2 100644
--- a/source/gameengine/Physics/common/PHY_DynamicTypes.h
+++ b/source/gameengine/Physics/common/PHY_DynamicTypes.h
@@ -87,6 +87,18 @@ typedef enum PHY_ConstraintType {
 
 } PHY_ConstraintType;
 
+typedef enum PHY_ShapeType {
+	PHY_SHAPE_NONE,
+	PHY_SHAPE_BOX,
+	PHY_SHAPE_SPHERE,
+	PHY_SHAPE_CYLINDER,
+	PHY_SHAPE_CONE,
+	PHY_SHAPE_MESH,
+	PHY_SHAPE_POLYTOPE,
+	PHY_SHAPE_COMPOUND
+} PHY_ShapeType;
+
+
 typedef float	PHY_Vector3[3];
 
 #endif //__PHY_DYNAMIC_TYPES