BGE Scenegraph and View frustrum culling improvement.

This commit contains a number of performance improvements for the
BGE in the Scenegraph (parent relation between objects in the
scene) and view frustrum culling.

The scenegraph improvement consists in avoiding position update
if the object has not moved since last update and the removal
of redundant updates and synchronization with the physics engine.

The view frustrum culling improvement consists in using the DBVT
broadphase facility of Bullet to build a tree of graphical objects
in the scene. The elements of the tree are Aabb boxes (Aligned 
Axis Bounding Boxes) enclosing the objects. This provides good
precision in closed and opened scenes. This new culling system
is enabled by default but just in case, it can be disabled with
a button in the World settings. There is no do_version in this
commit but it will be added before the 2.49 release. For now you
must manually enable the DBVT culling option in World settings
when you open an old file.

The above improvements speed up scenegraph and culling up to 5x.
However, this performance improvement is only visible when
you have hundreds or thousands of objects.

The main interest of the DBVT tree is to allow easy occlusion
culling and automatic LOD system. This will be the object of further
improvements.

17 files changed, 546 insertions, 16 deletions

diff --git a/source/gameengine/Physics/BlOde/OdePhysicsEnvironment.h b/source/gameengine/Physics/BlOde/OdePhysicsEnvironment.h
index dcc87d614c0..e4aaef1803d 100644
--- a/source/gameengine/Physics/BlOde/OdePhysicsEnvironment.h
+++ b/source/gameengine/Physics/BlOde/OdePhysicsEnvironment.h
@@ -55,6 +55,7 @@ public:
 
 	virtual void		removeConstraint(void * constraintid);
 	virtual PHY_IPhysicsController* rayTest(PHY_IRayCastFilterCallback &filterCallback,float fromX,float fromY,float fromZ, float toX,float toY,float toZ);
+	virtual bool cullingTest(PHY_CullingCallback callback, void* userData, PHY__Vector4* planes, int nplanes) { return false; }
 
 
 	//gamelogic callbacks
diff --git a/source/gameengine/Physics/Bullet/CcdGraphicController.cpp b/source/gameengine/Physics/Bullet/CcdGraphicController.cpp
new file mode 100644
index 00000000000..caf18fd28ba
--- /dev/null
+++ b/source/gameengine/Physics/Bullet/CcdGraphicController.cpp
@@ -0,0 +1,112 @@
+/*
+Bullet Continuous Collision Detection and Physics Library
+Copyright (c) 2003-2006 Erwin Coumans  http://continuousphysics.com/Bullet/
+
+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 "CcdPhysicsEnvironment.h"
+#include "CcdGraphicController.h"
+#include "btBulletDynamicsCommon.h"
+#include "MT_Point3.h"
+
+
+CcdGraphicController::CcdGraphicController (CcdPhysicsEnvironment* phyEnv, PHY_IMotionState* motionState) :
+	m_localAabbMin(0.f, 0.f, 0.f),
+	m_localAabbMax(0.f, 0.f, 0.f),
+	m_motionState(motionState),
+	m_phyEnv(phyEnv),
+	m_handle(NULL),
+	m_newClientInfo(NULL)
+{
+}
+
+CcdGraphicController::~CcdGraphicController()
+{
+	if (m_phyEnv)
+		m_phyEnv->removeCcdGraphicController(this);
+
+	if (m_motionState)
+		delete m_motionState;
+}
+
+void CcdGraphicController::setLocalAabb(const btVector3& aabbMin,const btVector3& aabbMax)
+{
+	m_localAabbMin = aabbMin;
+	m_localAabbMax = aabbMax;
+	SetGraphicTransform();
+}
+
+void CcdGraphicController::setLocalAabb(const MT_Point3& aabbMin,const MT_Point3& aabbMax)
+{
+	m_localAabbMin = btVector3(aabbMin[0],aabbMin[1],aabbMin[2]);
+	m_localAabbMax = btVector3(aabbMax[0],aabbMax[1],aabbMax[2]);
+	SetGraphicTransform();
+}
+
+
+void CcdGraphicController::getAabb(btVector3& aabbMin, btVector3& aabbMax)
+{
+	btVector3 pos;
+	btVector3 scale;
+	float ori[12];
+	m_motionState->getWorldPosition(pos.m_floats[0],pos.m_floats[1],pos.m_floats[2]);
+	m_motionState->getWorldScaling(scale.m_floats[0],scale.m_floats[1],scale.m_floats[2]);
+	m_motionState->getWorldOrientation(ori);
+	btMatrix3x3 rot(ori[0], ori[4], ori[8],
+					ori[1], ori[5], ori[9],
+					ori[2], ori[6], ori[10]);
+
+	btVector3 localAabbMin = m_localAabbMin;
+	btVector3 localAabbMax = m_localAabbMax;
+	btVector3 tmpAabbMin = m_localAabbMin * scale;
+	btVector3 tmpAabbMax = m_localAabbMax * scale;
+
+	localAabbMin[0] = (scale.getX() >= 0.) ? tmpAabbMin[0] : tmpAabbMax[0];
+	localAabbMin[1] = (scale.getY() >= 0.) ? tmpAabbMin[1] : tmpAabbMax[1];
+	localAabbMin[2] = (scale.getZ() >= 0.) ? tmpAabbMin[2] : tmpAabbMax[2];
+	localAabbMax[0] = (scale.getX() <= 0.) ? tmpAabbMin[0] : tmpAabbMax[0];
+	localAabbMax[1] = (scale.getY() <= 0.) ? tmpAabbMin[1] : tmpAabbMax[1];
+	localAabbMax[2] = (scale.getZ() <= 0.) ? tmpAabbMin[2] : tmpAabbMax[2];
+
+	btVector3 localHalfExtents = btScalar(0.5)*(localAabbMax-localAabbMin);
+	btVector3 localCenter = btScalar(0.5)*(localAabbMax+localAabbMin);
+	
+	btMatrix3x3 abs_b = rot.absolute();  
+	btVector3 center = rot*localCenter + pos;
+	btVector3 extent = abs_b*localHalfExtents;
+	aabbMin = center - extent;
+	aabbMax = center + extent;
+}
+
+bool CcdGraphicController::SetGraphicTransform()
+{
+	if (!m_handle) 
+		return false;
+	btVector3 aabbMin;
+	btVector3 aabbMax;
+	getAabb(aabbMin, aabbMax);
+	// update Aabb in broadphase
+	m_phyEnv->getCullingTree()->setAabb(m_handle,aabbMin,aabbMax,NULL);
+	return true;
+}
+
+PHY_IGraphicController* CcdGraphicController::GetReplica(class PHY_IMotionState* motionState)
+{
+	CcdGraphicController* replica = new CcdGraphicController(*this);
+	replica->m_motionState = motionState;
+	replica->m_newClientInfo = NULL;
+	replica->m_handle = NULL;
+	m_phyEnv->addCcdGraphicController(replica);
+	return replica;
+}
+
+
diff --git a/source/gameengine/Physics/Bullet/CcdGraphicController.h b/source/gameengine/Physics/Bullet/CcdGraphicController.h
new file mode 100644
index 00000000000..8faa0944313
--- /dev/null
+++ b/source/gameengine/Physics/Bullet/CcdGraphicController.h
@@ -0,0 +1,74 @@
+/*
+Bullet Continuous Collision Detection and Physics Library
+Copyright (c) 2003-2006 Erwin Coumans  http://continuousphysics.com/Bullet/
+
+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.
+*/
+
+
+#ifndef BULLET2_GRAPHICCONTROLLER_H
+#define BULLET2_GRAPHICCONTROLLER_H
+
+#include "PHY_IGraphicController.h"
+
+#include "btBulletDynamicsCommon.h"
+#include "LinearMath/btTransform.h"
+
+#include "PHY_IMotionState.h"
+#include "MT_Point3.h"
+
+class CcdPhysicsEnvironment;
+class btCollisionObject;
+
+///CcdGraphicController is a graphic object that supports view frustrum culling and occlusion
+class CcdGraphicController : public PHY_IGraphicController	
+{
+public:
+	CcdGraphicController(CcdPhysicsEnvironment* phyEnv, PHY_IMotionState* motionState);
+
+	virtual ~CcdGraphicController();
+
+	void setLocalAabb(const btVector3& aabbMin,const btVector3& aabbMax);
+	void setLocalAabb(const MT_Point3& aabbMin,const MT_Point3& aabbMax);
+
+	PHY_IMotionState* GetMotionState() { return m_motionState; }
+	void getAabb(btVector3& aabbMin, btVector3& aabbMax);
+
+	virtual void setBroadphaseHandle(btBroadphaseProxy* handle) { m_handle = handle; }
+	virtual btBroadphaseProxy* getBroadphaseHandle() { return m_handle; }
+
+	////////////////////////////////////
+	// PHY_IGraphicController interface
+	////////////////////////////////////
+
+	/**
+	 * Updates the Aabb based on the motion state
+	 */
+	virtual bool SetGraphicTransform();
+
+	// client info for culling
+	virtual	void* getNewClientInfo() { return m_newClientInfo; }
+	virtual	void setNewClientInfo(void* clientinfo) { m_newClientInfo = clientinfo; }
+	virtual PHY_IGraphicController*	GetReplica(class PHY_IMotionState* motionstate);
+		
+private:
+	// unscaled aabb corner
+	btVector3 m_localAabbMin;
+	btVector3 m_localAabbMax;
+
+	PHY_IMotionState* m_motionState;
+	CcdPhysicsEnvironment* m_phyEnv;
+	btBroadphaseProxy* m_handle;
+	void* m_newClientInfo;
+
+};
+
+#endif //BULLET2_PHYSICSCONTROLLER_H
diff --git a/source/gameengine/Physics/Bullet/CcdPhysicsController.cpp b/source/gameengine/Physics/Bullet/CcdPhysicsController.cpp
index bb2f53a1988..2283968801f 100644
--- a/source/gameengine/Physics/Bullet/CcdPhysicsController.cpp
+++ b/source/gameengine/Physics/Bullet/CcdPhysicsController.cpp
@@ -1245,6 +1245,22 @@ void	DefaultMotionState::getWorldOrientation(float& quatIma0,float& quatIma1,flo
 	quatReal = m_worldTransform.getRotation()[3];
 }
 		
+void	DefaultMotionState::getWorldOrientation(float* ori)
+{
+	*ori++ = m_worldTransform.getBasis()[0].x();
+	*ori++ = m_worldTransform.getBasis()[1].x();
+	*ori++ = m_worldTransform.getBasis()[1].x();
+	*ori++ = 0.f;
+	*ori++ = m_worldTransform.getBasis()[0].y();
+	*ori++ = m_worldTransform.getBasis()[1].y();
+	*ori++ = m_worldTransform.getBasis()[1].y();
+	*ori++ = 0.f;
+	*ori++ = m_worldTransform.getBasis()[0].z();
+	*ori++ = m_worldTransform.getBasis()[1].z();
+	*ori++ = m_worldTransform.getBasis()[1].z();
+	*ori++ = 0.f;
+}
+
 void	DefaultMotionState::setWorldPosition(float posX,float posY,float posZ)
 {
 	btVector3 pos(posX,posY,posZ);
diff --git a/source/gameengine/Physics/Bullet/CcdPhysicsController.h b/source/gameengine/Physics/Bullet/CcdPhysicsController.h
index 510454a7b63..245cde2baaa 100644
--- a/source/gameengine/Physics/Bullet/CcdPhysicsController.h
+++ b/source/gameengine/Physics/Bullet/CcdPhysicsController.h
@@ -544,6 +544,7 @@ class	DefaultMotionState : public PHY_IMotionState
 		
 		virtual void	setWorldPosition(float posX,float posY,float posZ);
 		virtual	void	setWorldOrientation(float quatIma0,float quatIma1,float quatIma2,float quatReal);
+		virtual void	getWorldOrientation(float* ori);
 		
 		virtual	void	calculateWorldTransformations();
 		
diff --git a/source/gameengine/Physics/Bullet/CcdPhysicsEnvironment.cpp b/source/gameengine/Physics/Bullet/CcdPhysicsEnvironment.cpp
index dd21e58bd68..cef2f2477b7 100644
--- a/source/gameengine/Physics/Bullet/CcdPhysicsEnvironment.cpp
+++ b/source/gameengine/Physics/Bullet/CcdPhysicsEnvironment.cpp
@@ -18,6 +18,7 @@ subject to the following restrictions:
 
 #include "CcdPhysicsEnvironment.h"
 #include "CcdPhysicsController.h"
+#include "CcdGraphicController.h"
 
 #include <algorithm>
 #include "btBulletDynamicsCommon.h"
@@ -316,8 +317,10 @@ static void DrawAabb(btIDebugDraw* debugDrawer,const btVector3& from,const btVec
 
 
 
-CcdPhysicsEnvironment::CcdPhysicsEnvironment(btDispatcher* dispatcher,btOverlappingPairCache* pairCache)
-:m_numIterations(10),
+CcdPhysicsEnvironment::CcdPhysicsEnvironment(bool useDbvtCulling,btDispatcher* dispatcher,btOverlappingPairCache* pairCache)
+:m_cullingCache(NULL),
+m_cullingTree(NULL),
+m_numIterations(10),
 m_scalingPropagated(false),
 m_numTimeSubSteps(1),
 m_ccdMode(0),
@@ -350,6 +353,11 @@ m_ownDispatcher(NULL)
 	//m_broadphase = new btAxisSweep3(btVector3(-1000,-1000,-1000),btVector3(1000,1000,1000));
 	//m_broadphase = new btSimpleBroadphase();
 	m_broadphase = new btDbvtBroadphase();
+	// avoid any collision in the culling tree
+	if (useDbvtCulling) {
+		m_cullingCache = new btNullPairCache();
+		m_cullingTree = new btDbvtBroadphase(m_cullingCache);
+	}
 
 	m_filterCallback = new CcdOverlapFilterCallBack(this);
 	m_broadphase->getOverlappingPairCache()->setOverlapFilterCallback(m_filterCallback);
@@ -364,7 +372,6 @@ m_ownDispatcher(NULL)
 	m_gravity = btVector3(0.f,-10.f,0.f);
 	m_dynamicsWorld->setGravity(m_gravity);
 
-
 }
 
 void	CcdPhysicsEnvironment::addCcdPhysicsController(CcdPhysicsController* ctrl)
@@ -558,6 +565,41 @@ void CcdPhysicsEnvironment::refreshCcdPhysicsController(CcdPhysicsController* ct
 	}
 }
 
+void CcdPhysicsEnvironment::addCcdGraphicController(CcdGraphicController* ctrl)
+{
+	if (m_cullingTree)
+	{
+		btVector3	minAabb;
+		btVector3	maxAabb;
+		ctrl->getAabb(minAabb, maxAabb);
+
+		ctrl->setBroadphaseHandle(m_cullingTree->createProxy(
+				minAabb,
+				maxAabb,
+				INVALID_SHAPE_PROXYTYPE,	// this parameter is not used
+				ctrl,
+				0,							// this object does not collision with anything
+				0,
+				NULL,						// dispatcher => this parameter is not used
+				0));
+
+		assert(ctrl->getBroadphaseHandle());
+	}
+}
+
+void CcdPhysicsEnvironment::removeCcdGraphicController(CcdGraphicController* ctrl)
+{
+	if (m_cullingTree)
+	{
+		btBroadphaseProxy* bp = ctrl->getBroadphaseHandle();
+		if (bp)
+		{
+			m_cullingTree->destroyProxy(bp,NULL);
+			ctrl->setBroadphaseHandle(0);
+		}
+	}
+}
+
 void	CcdPhysicsEnvironment::beginFrame()
 {
 
@@ -593,10 +635,10 @@ bool	CcdPhysicsEnvironment::proceedDeltaTime(double curTime,float timeStep)
 		(*it)->SynchronizeMotionStates(timeStep);
 	}
 
-	for (it=m_controllers.begin(); it!=m_controllers.end(); it++)
-	{
-		(*it)->SynchronizeMotionStates(timeStep);
-	}
+	//for (it=m_controllers.begin(); it!=m_controllers.end(); it++)
+	//{
+	//	(*it)->SynchronizeMotionStates(timeStep);
+	//}
 
 	for (i=0;i<m_wrapperVehicles.size();i++)
 	{
@@ -1146,6 +1188,50 @@ PHY_IPhysicsController* CcdPhysicsEnvironment::rayTest(PHY_IRayCastFilterCallbac
 	return result.m_controller;
 }
 
+struct	DbvtCullingCallback : btDbvt::ICollide
+{
+	PHY_CullingCallback m_clientCallback;
+	void* m_userData;
+
+	DbvtCullingCallback(PHY_CullingCallback clientCallback, void* userData)
+	{
+		m_clientCallback = clientCallback;
+		m_userData = userData;
+	}
+
+	void Process(const btDbvtNode* node,btScalar depth)
+	{
+		Process(node);
+	}
+	void Process(const btDbvtNode* leaf)
+	{	
+		btBroadphaseProxy*	proxy=(btBroadphaseProxy*)leaf->data;
+		// the client object is a graphic controller
+		CcdGraphicController* ctrl = static_cast<CcdGraphicController*>(proxy->m_clientObject);
+		KX_ClientObjectInfo* info = (KX_ClientObjectInfo*)ctrl->getNewClientInfo();
+		if (info)
+			(*m_clientCallback)(info, m_userData);
+	}
+};
+
+bool CcdPhysicsEnvironment::cullingTest(PHY_CullingCallback callback, void* userData, PHY__Vector4 *planes, int nplanes)
+{
+	if (!m_cullingTree)
+		return false;
+	DbvtCullingCallback dispatcher(callback, userData);
+	btVector3 planes_n[5];
+	btScalar planes_o[5];
+	if (nplanes > 5)
+		nplanes = 5;
+	for (int i=0; i<nplanes; i++)
+	{
+		planes_n[i].setValue(planes[i][0], planes[i][1], planes[i][2]);
+		planes_o[i] = planes[i][3];
+	}
+	btDbvt::collideKDOP(m_cullingTree->m_sets[1].m_root,planes_n,planes_o,nplanes,dispatcher);
+	btDbvt::collideKDOP(m_cullingTree->m_sets[0].m_root,planes_n,planes_o,nplanes,dispatcher);		
+	return true;
+}
 
 
 int	CcdPhysicsEnvironment::getNumContactPoints()
@@ -1211,6 +1297,13 @@ CcdPhysicsEnvironment::~CcdPhysicsEnvironment()
 
 	if (NULL != m_broadphase)
 		delete m_broadphase;
+
+	if (NULL != m_cullingTree)
+		delete m_cullingTree;
+
+	if (NULL != m_cullingCache)
+		delete m_cullingCache;
+
 }
 
 
diff --git a/source/gameengine/Physics/Bullet/CcdPhysicsEnvironment.h b/source/gameengine/Physics/Bullet/CcdPhysicsEnvironment.h
index 2f1f0bb254b..ddbcbe6b4d6 100644
--- a/source/gameengine/Physics/Bullet/CcdPhysicsEnvironment.h
+++ b/source/gameengine/Physics/Bullet/CcdPhysicsEnvironment.h
@@ -20,6 +20,7 @@ subject to the following restrictions:
 #include <vector>
 #include <set>
 class CcdPhysicsController;
+class CcdGraphicController;
 #include "LinearMath/btVector3.h"
 #include "LinearMath/btTransform.h"
 
@@ -40,6 +41,7 @@ class btDispatcher;
 class WrapperVehicle;
 class btPersistentManifold;
 class btBroadphaseInterface;
+struct btDbvtBroadphase;
 class btOverlappingPairCache;
 class btIDebugDraw;
 class PHY_IVehicle;
@@ -58,7 +60,10 @@ protected:
 	btIDebugDraw*	m_debugDrawer;
 	
 	class btDefaultCollisionConfiguration* m_collisionConfiguration;
-	class btBroadphaseInterface*			m_broadphase;
+    class btBroadphaseInterface*		m_broadphase;	// broadphase for dynamic world
+	// for culling only
+	btOverlappingPairCache*				m_cullingCache;
+	struct btDbvtBroadphase*			m_cullingTree;	// broadphase for culling
 
 	//solver iterations
 	int	m_numIterations;
@@ -77,7 +82,7 @@ protected:
 	void	processFhSprings(double curTime,float timeStep);
 
 	public:
-		CcdPhysicsEnvironment(btDispatcher* dispatcher=0, btOverlappingPairCache* pairCache=0);
+		CcdPhysicsEnvironment(bool useDbvtCulling, btDispatcher* dispatcher=0, btOverlappingPairCache* pairCache=0);
 
 		virtual		~CcdPhysicsEnvironment();
 
@@ -167,6 +172,7 @@ protected:
 		btTypedConstraint*	getConstraintById(int constraintId);
 
 		virtual PHY_IPhysicsController* rayTest(PHY_IRayCastFilterCallback &filterCallback, float fromX,float fromY,float fromZ, float toX,float toY,float toZ);
+		virtual bool cullingTest(PHY_CullingCallback callback, void* userData, PHY__Vector4* planes, int nplanes);
 
 
 		//Methods for gamelogic collision/physics callbacks
@@ -200,7 +206,12 @@ protected:
 
 		void	refreshCcdPhysicsController(CcdPhysicsController* ctrl);
 
+		void	addCcdGraphicController(CcdGraphicController* ctrl);
+
+		void	removeCcdGraphicController(CcdGraphicController* ctrl);
+
 		btBroadphaseInterface*	getBroadphase();
+		btDbvtBroadphase*	getCullingTree() { return m_cullingTree; }
 
 		btDispatcher*	getDispatcher();
 		
diff --git a/source/gameengine/Physics/Dummy/DummyPhysicsEnvironment.h b/source/gameengine/Physics/Dummy/DummyPhysicsEnvironment.h
index a92b1e7f4a6..fae1844d505 100644
--- a/source/gameengine/Physics/Dummy/DummyPhysicsEnvironment.h
+++ b/source/gameengine/Physics/Dummy/DummyPhysicsEnvironment.h
@@ -70,6 +70,7 @@ public:
 	}
 
 	virtual PHY_IPhysicsController* rayTest(PHY_IRayCastFilterCallback &filterCallback, float fromX,float fromY,float fromZ, float toX,float toY,float toZ);
+	virtual bool cullingTest(PHY_CullingCallback callback, void* userData, PHY__Vector4* planes, int nplanes) { return false; }
 
 
 	//gamelogic callbacks
diff --git a/source/gameengine/Physics/Sumo/SumoPhysicsEnvironment.h b/source/gameengine/Physics/Sumo/SumoPhysicsEnvironment.h
index 65b07a7a0be..9942a367451 100644
--- a/source/gameengine/Physics/Sumo/SumoPhysicsEnvironment.h
+++ b/source/gameengine/Physics/Sumo/SumoPhysicsEnvironment.h
@@ -76,6 +76,7 @@ public:
 	}
 
 	virtual PHY_IPhysicsController* rayTest(PHY_IRayCastFilterCallback &filterCallback,float fromX,float fromY,float fromZ, float toX,float toY,float toZ);
+	virtual bool cullingTest(PHY_CullingCallback callback, void* userData, PHY__Vector4 *planes, int nplanes) { return false; }
 
 	
 	//gamelogic callbacks
diff --git a/source/gameengine/Physics/common/PHY_DynamicTypes.h b/source/gameengine/Physics/common/PHY_DynamicTypes.h
index c5cf92b553a..7ce40001af7 100644
--- a/source/gameengine/Physics/common/PHY_DynamicTypes.h
+++ b/source/gameengine/Physics/common/PHY_DynamicTypes.h
@@ -19,12 +19,42 @@ subject to the following restrictions:
 
 
 
-
+struct KX_ClientObjectInfo;
 class PHY_Shape;
 
 struct	PHY__Vector3
 {
 	float	m_vec[4];
+
+	operator const float* () const 
+	{ 
+		return &m_vec[0];
+	}	
+	operator float* () 
+	{ 
+		return &m_vec[0];
+	}	
+};
+
+struct	PHY__Vector4
+{
+	float	m_vec[4];
+	PHY__Vector4() {}
+	void setValue(const float *value)
+	{
+		m_vec[0] = *value++;
+		m_vec[1] = *value++;
+		m_vec[2] = *value++;
+		m_vec[3] = *value++;
+	}
+	void setValue(const double *value)
+	{
+		m_vec[0] = (float)(*value++);
+		m_vec[1] = (float)(*value++);
+		m_vec[2] = (float)(*value++);
+		m_vec[3] = (float)(*value++);
+	}
+
 	operator const float* () const 
 	{ 
 		return &m_vec[0];
@@ -34,6 +64,7 @@ struct	PHY__Vector3
 		return &m_vec[0];
 	}	
 };
+
 //typedef 	float	PHY__Vector3[4];
 
 enum
@@ -59,7 +90,7 @@ enum
 										   void *client_object1,
 										   void *client_object2,
 										   const PHY_CollData *coll_data);
-		
+	typedef void (*PHY_CullingCallback)(KX_ClientObjectInfo* info, void* param);
 
 
 /// PHY_PhysicsType enumerates all possible Physics Entities.
diff --git a/source/gameengine/Physics/common/PHY_IController.cpp b/source/gameengine/Physics/common/PHY_IController.cpp
new file mode 100644
index 00000000000..47fe9a9eea8
--- /dev/null
+++ b/source/gameengine/Physics/common/PHY_IController.cpp
@@ -0,0 +1,39 @@
+/**
+ * $Id$
+ *
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
+ *
+ * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
+ * All rights reserved.
+ *
+ * The Original Code is: all of this file.
+ *
+ * Contributor(s): none yet.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+#include "PHY_IController.h"
+
+#ifdef HAVE_CONFIG_H
+#include <config.h>
+#endif
+
+PHY_IController::~PHY_IController()
+{
+
+}
+
diff --git a/source/gameengine/Physics/common/PHY_IController.h b/source/gameengine/Physics/common/PHY_IController.h
new file mode 100644
index 00000000000..45e93f9d24e
--- /dev/null
+++ b/source/gameengine/Physics/common/PHY_IController.h
@@ -0,0 +1,53 @@
+/**
+ * $Id$
+ *
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
+ *
+ * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
+ * All rights reserved.
+ *
+ * The Original Code is: all of this file.
+ *
+ * Contributor(s): none yet.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+#ifndef PHY_ICONTROLLER_H
+#define PHY_ICONTROLLER_H
+
+#include "PHY_DynamicTypes.h"
+
+
+
+/**
+	PHY_IController is the abstract simplified Interface to objects 
+	controlled by the physics engine. This includes the physics objects
+	and the graphics object for view frustrum and occlusion culling.
+*/
+class PHY_IController	
+{
+	public:
+		
+		virtual ~PHY_IController();
+		// clientinfo for raycasts for example
+		virtual	void*				getNewClientInfo()=0;
+		virtual	void				setNewClientInfo(void* clientinfo)=0;
+
+};
+
+#endif //PHY_ICONTROLLER_H
+
diff --git a/source/gameengine/Physics/common/PHY_IGraphicController.cpp b/source/gameengine/Physics/common/PHY_IGraphicController.cpp
new file mode 100644
index 00000000000..4dccecd3d29
--- /dev/null
+++ b/source/gameengine/Physics/common/PHY_IGraphicController.cpp
@@ -0,0 +1,39 @@
+/**
+ * $Id$
+ *
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
+ *
+ * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
+ * All rights reserved.
+ *
+ * The Original Code is: all of this file.
+ *
+ * Contributor(s): none yet.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+#include "PHY_IGraphicController.h"
+
+#ifdef HAVE_CONFIG_H
+#include <config.h>
+#endif
+
+PHY_IGraphicController::~PHY_IGraphicController()
+{
+
+}
+
diff --git a/source/gameengine/Physics/common/PHY_IGraphicController.h b/source/gameengine/Physics/common/PHY_IGraphicController.h
new file mode 100644
index 00000000000..36b8a978e87
--- /dev/null
+++ b/source/gameengine/Physics/common/PHY_IGraphicController.h
@@ -0,0 +1,56 @@
+/**
+ * $Id$
+ *
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
+ *
+ * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
+ * All rights reserved.
+ *
+ * The Original Code is: all of this file.
+ *
+ * Contributor(s): none yet.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+#ifndef PHY_IGRAPHICCONTROLLER_H
+#define PHY_IGRAPHICCONTROLLER_H
+
+#include "PHY_IController.h"
+
+
+
+/**
+	PHY_IPhysicsController is the abstract simplified Interface to a physical object.
+	It contains the IMotionState and IDeformableMesh Interfaces.
+*/
+class PHY_IGraphicController : public PHY_IController
+{
+
+	public:
+		
+		virtual ~PHY_IGraphicController();
+		/**
+			SynchronizeMotionStates ynchronizes dynas, kinematic and deformable entities (and do 'late binding')
+		*/
+		virtual bool SetGraphicTransform()=0;
+
+		virtual PHY_IGraphicController*	GetReplica(class PHY_IMotionState* motionstate) {return 0;}
+
+};
+
+#endif //PHY_IGRAPHICCONTROLLER_H
+
diff --git a/source/gameengine/Physics/common/PHY_IMotionState.h b/source/gameengine/Physics/common/PHY_IMotionState.h
index d759b0aeff4..64bb810ee7c 100644
--- a/source/gameengine/Physics/common/PHY_IMotionState.h
+++ b/source/gameengine/Physics/common/PHY_IMotionState.h
@@ -43,6 +43,8 @@ class	PHY_IMotionState
 		virtual void	getWorldPosition(float& posX,float& posY,float& posZ)=0;
 		virtual void	getWorldScaling(float& scaleX,float& scaleY,float& scaleZ)=0;
 		virtual void	getWorldOrientation(float& quatIma0,float& quatIma1,float& quatIma2,float& quatReal)=0;
+		// ori = array 12 floats, [0..3] = first column + 0, [4..7] = second colum, [8..11] = third column
+		virtual void	getWorldOrientation(float* ori)=0;
 		
 		virtual void	setWorldPosition(float posX,float posY,float posZ)=0;
 		virtual	void	setWorldOrientation(float quatIma0,float quatIma1,float quatIma2,float quatReal)=0;
diff --git a/source/gameengine/Physics/common/PHY_IPhysicsController.h b/source/gameengine/Physics/common/PHY_IPhysicsController.h
index 884e14cfb5a..6cba6fa88af 100644
--- a/source/gameengine/Physics/common/PHY_IPhysicsController.h
+++ b/source/gameengine/Physics/common/PHY_IPhysicsController.h
@@ -29,7 +29,7 @@
 #ifndef PHY_IPHYSICSCONTROLLER_H
 #define PHY_IPHYSICSCONTROLLER_H
 
-#include "PHY_DynamicTypes.h"
+#include "PHY_IController.h"
 
 
 
@@ -37,7 +37,7 @@
 	PHY_IPhysicsController is the abstract simplified Interface to a physical object.
 	It contains the IMotionState and IDeformableMesh Interfaces.
 */
-class PHY_IPhysicsController	
+class PHY_IPhysicsController : public PHY_IController
 {
 
 	public:
@@ -82,9 +82,7 @@ class PHY_IPhysicsController
 
 		// dyna's that are rigidbody are free in orientation, dyna's with non-rigidbody are restricted 
 		virtual	void		setRigidBody(bool rigid)=0;
-		// clientinfo for raycasts for example
-		virtual	void*				getNewClientInfo()=0;
-		virtual	void				setNewClientInfo(void* clientinfo)=0;
+
 		virtual PHY_IPhysicsController*	GetReplica() {return 0;}
 
 		virtual void	calcXform() =0;
diff --git a/source/gameengine/Physics/common/PHY_IPhysicsEnvironment.h b/source/gameengine/Physics/common/PHY_IPhysicsEnvironment.h
index 226ba3a7e74..5edafe6b51e 100644
--- a/source/gameengine/Physics/common/PHY_IPhysicsEnvironment.h
+++ b/source/gameengine/Physics/common/PHY_IPhysicsEnvironment.h
@@ -142,6 +142,8 @@ class PHY_IPhysicsEnvironment
 
 		virtual PHY_IPhysicsController* rayTest(PHY_IRayCastFilterCallback &filterCallback, float fromX,float fromY,float fromZ, float toX,float toY,float toZ)=0;
 
+		//culling based on physical broad phase
+		virtual bool cullingTest(PHY_CullingCallback callback, void *userData, PHY__Vector4* planeNormals, int planeNumber) = 0;
 
 		//Methods for gamelogic collision/physics callbacks
 		//todo: