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.

9 files changed, 73 insertions, 13 deletions

diff --git a/source/gameengine/SceneGraph/SG_BBox.cpp b/source/gameengine/SceneGraph/SG_BBox.cpp
index a44262d04f7..66fcc5c7408 100644
--- a/source/gameengine/SceneGraph/SG_BBox.cpp
+++ b/source/gameengine/SceneGraph/SG_BBox.cpp
@@ -188,6 +188,13 @@ void SG_BBox::getaa(MT_Point3 *box, const MT_Transform &world) const
 	*box++ = max;
 }
 
+void SG_BBox::getmm(MT_Point3 *box, const MT_Transform &world) const
+{
+	const MT_Point3 min(world(m_min)), max(world(m_max));
+	*box++ = min;
+	*box++ = max;
+}
+
 void SG_BBox::split(SG_BBox &left, SG_BBox &right) const
 {
 	MT_Scalar sizex = m_max[0] - m_min[0];
diff --git a/source/gameengine/SceneGraph/SG_BBox.h b/source/gameengine/SceneGraph/SG_BBox.h
index b7e8ff65865..c39ad268e25 100644
--- a/source/gameengine/SceneGraph/SG_BBox.h
+++ b/source/gameengine/SceneGraph/SG_BBox.h
@@ -122,6 +122,8 @@ public:
 	 */
 	void getaa(MT_Point3 *box, const MT_Transform &world) const;
 	
+	void getmm(MT_Point3 *box, const MT_Transform &world) const;
+
 	void split(SG_BBox &left, SG_BBox &right) const;
 	
 	friend class SG_Tree;
diff --git a/source/gameengine/SceneGraph/SG_IObject.cpp b/source/gameengine/SceneGraph/SG_IObject.cpp
index d0bdac5c8f0..fbab4032a10 100644
--- a/source/gameengine/SceneGraph/SG_IObject.cpp
+++ b/source/gameengine/SceneGraph/SG_IObject.cpp
@@ -33,6 +33,8 @@
 #include <config.h>
 #endif
 
+SG_Stage gSG_Stage = SG_STAGE_UNKNOWN;
+
 SG_IObject::
 SG_IObject(
 	void* clientobj,
diff --git a/source/gameengine/SceneGraph/SG_IObject.h b/source/gameengine/SceneGraph/SG_IObject.h
index 7f6bdfbbb1c..9012b532059 100644
--- a/source/gameengine/SceneGraph/SG_IObject.h
+++ b/source/gameengine/SceneGraph/SG_IObject.h
@@ -31,6 +31,36 @@
 
 #include <vector>
 
+// used for debugging: stage of the game engine main loop at which a Scenegraph modification is done
+enum SG_Stage
+{
+	SG_STAGE_UNKNOWN = 0,
+	SG_STAGE_NETWORK,
+	SG_STAGE_NETWORK_UPDATE,
+	SG_STAGE_PHYSICS1,
+	SG_STAGE_PHYSICS1_UPDATE,
+	SG_STAGE_CONTROLLER,
+	SG_STAGE_CONTROLLER_UPDATE,
+	SG_STAGE_ACTUATOR,
+	SG_STAGE_ACTUATOR_UPDATE,
+	SG_STAGE_PHYSICS2,
+	SG_STAGE_PHYSICS2_UPDATE,
+	SG_STAGE_SCENE,
+	SG_STAGE_RENDER,
+	SG_STAGE_CONVERTER,
+	SG_STAGE_CULLING,
+	SG_STAGE_MAX
+};
+
+extern SG_Stage gSG_Stage;
+
+inline void SG_SetActiveStage(SG_Stage stage)
+{
+	gSG_Stage = stage;
+}
+	
+
+
 class SG_Controller;
 class SG_IObject;
 
diff --git a/source/gameengine/SceneGraph/SG_Node.cpp b/source/gameengine/SceneGraph/SG_Node.cpp
index 8de7ac83477..64d9019c86a 100644
--- a/source/gameengine/SceneGraph/SG_Node.cpp
+++ b/source/gameengine/SceneGraph/SG_Node.cpp
@@ -219,18 +219,19 @@ void SG_Node::RemoveChild(SG_Node* child)
 
 
 
-void SG_Node::UpdateWorldData(double time)
+void SG_Node::UpdateWorldData(double time, bool parentUpdated)
 {
 	//if (!GetSGParent())
 	//	return;
 
-	if (UpdateSpatialData(GetSGParent(),time))
+	if (UpdateSpatialData(GetSGParent(),time,parentUpdated))
+		// to update the 
 		ActivateUpdateTransformCallback();
 
 	// update children's worlddata
 	for (NodeList::iterator it = m_children.begin();it!=m_children.end();++it)
 	{
-		(*it)->UpdateWorldData(time);
+		(*it)->UpdateWorldData(time, parentUpdated);
 	}
 }
 
diff --git a/source/gameengine/SceneGraph/SG_Node.h b/source/gameengine/SceneGraph/SG_Node.h
index ffaaad861e2..29943653a81 100644
--- a/source/gameengine/SceneGraph/SG_Node.h
+++ b/source/gameengine/SceneGraph/SG_Node.h
@@ -175,7 +175,8 @@ public:
 
 		void		
 	UpdateWorldData(
-		double time
+		double time,
+		bool parentUpdated=false
 	);
 
 	/**
diff --git a/source/gameengine/SceneGraph/SG_ParentRelation.h b/source/gameengine/SceneGraph/SG_ParentRelation.h
index 6507cb98519..8f45df09b27 100644
--- a/source/gameengine/SceneGraph/SG_ParentRelation.h
+++ b/source/gameengine/SceneGraph/SG_ParentRelation.h
@@ -69,7 +69,8 @@ public :
 		bool
 	UpdateChildCoordinates(
 		SG_Spatial * child,
-		const SG_Spatial * parent
+		const SG_Spatial * parent,
+		bool& parentUpdated
 	) = 0;
 
 	virtual 
diff --git a/source/gameengine/SceneGraph/SG_Spatial.cpp b/source/gameengine/SceneGraph/SG_Spatial.cpp
index 99aeb3e72ee..2f3176816c6 100644
--- a/source/gameengine/SceneGraph/SG_Spatial.cpp
+++ b/source/gameengine/SceneGraph/SG_Spatial.cpp
@@ -55,7 +55,8 @@ SG_Spatial(
 	m_parent_relation (NULL),
 	
 	m_bbox(MT_Point3(-1.0, -1.0, -1.0), MT_Point3(1.0, 1.0, 1.0)),
-	m_radius(1.0)
+	m_radius(1.0),
+	m_modified(true)
 {
 }
 
@@ -101,6 +102,7 @@ SetParentRelation(
 ){
 	delete (m_parent_relation);
 	m_parent_relation = relation;
+	m_modified = true;
 }
 
 
@@ -114,7 +116,8 @@ SetParentRelation(
 SG_Spatial::
 UpdateSpatialData(
 	const SG_Spatial *parent,
-	double time
+	double time,
+	bool& parentUpdated
 ){
 
     bool bComputesWorldTransform = false;
@@ -135,14 +138,14 @@ UpdateSpatialData(
 	// our world coordinates.
 
 	if (!bComputesWorldTransform)
-		bComputesWorldTransform = ComputeWorldTransforms(parent);
+		bComputesWorldTransform = ComputeWorldTransforms(parent, parentUpdated);
 
 	return bComputesWorldTransform;
 }
 
-bool	SG_Spatial::ComputeWorldTransforms(const SG_Spatial *parent)
+bool	SG_Spatial::ComputeWorldTransforms(const SG_Spatial *parent, bool& parentUpdated)
 {
-	return m_parent_relation->UpdateChildCoordinates(this,parent);
+	return m_parent_relation->UpdateChildCoordinates(this,parent,parentUpdated);
 }
 
 /**
@@ -166,6 +169,7 @@ RelativeTranslate(
 			m_localPosition += trans;
 		}
 	}
+	m_modified = true;
 }	
 	
 	void 
@@ -174,6 +178,7 @@ SetLocalPosition(
 	const MT_Point3& trans
 ){
 	m_localPosition = trans;
+	m_modified = true;
 }
 
 	void				
@@ -194,6 +199,7 @@ RelativeScale(
 	const MT_Vector3& scale
 ){
 	m_localScaling = m_localScaling * scale;
+	m_modified = true;
 }
 
 	void 
@@ -202,6 +208,7 @@ SetLocalScale(
 	const MT_Vector3& scale
 ){
 	m_localScaling = scale;
+	m_modified = true;
 }
 
 
@@ -229,6 +236,7 @@ RelativeRotate(
 		rot 
 	:
 	(GetWorldOrientation().inverse() * rot * GetWorldOrientation()));
+	m_modified = true;
 }
 
 	void 
@@ -236,6 +244,7 @@ SG_Spatial::
 SetLocalOrientation(const MT_Matrix3x3& rot)
 {
 	m_localRotation = rot;
+	m_modified = true;
 }
 
 
diff --git a/source/gameengine/SceneGraph/SG_Spatial.h b/source/gameengine/SceneGraph/SG_Spatial.h
index 6ccec2aa9c1..c2ed80d21b2 100644
--- a/source/gameengine/SceneGraph/SG_Spatial.h
+++ b/source/gameengine/SceneGraph/SG_Spatial.h
@@ -61,7 +61,7 @@ protected:
 	
 	SG_BBox			m_bbox;
 	MT_Scalar		m_radius;
-	
+	bool			m_modified;
 
 public:
 
@@ -180,7 +180,7 @@ public:
 
 	MT_Transform GetWorldTransform() const;
 
-	bool	ComputeWorldTransforms(		const SG_Spatial *parent);
+	bool	ComputeWorldTransforms(const SG_Spatial *parent, bool& parentUpdated);
 
 	/**
 	 * Bounding box functions.
@@ -193,9 +193,14 @@ public:
 	
 	MT_Scalar Radius() const { return m_radius; }
 	void SetRadius(MT_Scalar radius) { m_radius = radius; }
+	bool IsModified() { return m_modified; }
 	
 protected:
 	friend class SG_Controller;
+	friend class KX_BoneParentRelation;
+	friend class KX_VertexParentRelation;
+	friend class KX_SlowParentRelation;
+	friend class KX_NormalParentRelation;
 	
 	/** 
 	 * Protected constructor this class is not
@@ -223,8 +228,10 @@ protected:
 		bool 
 	UpdateSpatialData(
 		const SG_Spatial *parent,
-		double time
+		double time,
+		bool& parentUpdated
 	);
+	void SetModified(bool modified) { m_modified = modified; }
 
 };