Frustum Culling.

- tests every object against the view frustum.
- Tree based culling is there, need to build tree.

2 files changed, 134 insertions, 7 deletions

diff --git a/source/gameengine/Ketsji/KX_Scene.cpp b/source/gameengine/Ketsji/KX_Scene.cpp
index 8a964e07eb5..5abd43574ba 100644
--- a/source/gameengine/Ketsji/KX_Scene.cpp
+++ b/source/gameengine/Ketsji/KX_Scene.cpp
@@ -65,6 +65,7 @@
 #include "SYS_System.h"
 #include "SG_Controller.h"
 #include "SG_IObject.h"
+#include "SG_Tree.h"
 
 #include "KX_SG_NodeRelationships.h"
 
@@ -613,6 +614,7 @@ SCA_IObject* KX_Scene::AddReplicaObject(class CValue* originalobject,
 	replica->NodeSetRelativeScale(newscale);
 
 	replica->GetSGNode()->UpdateWorldData(0);
+	replica->GetSGNode()->SetBBox(originalobj->GetSGNode()->BBox());
 	
 	return replica;
 }
@@ -798,25 +800,109 @@ void KX_Scene::UpdateMeshTransformations()
 	}
 }
 
-void KX_Scene::CalculateVisibleMeshes(RAS_IRasterizer* rasty)
+void KX_Scene::MarkVisible(SG_Tree *node, RAS_IRasterizer* rasty)
 {
+	int intersect = KX_Camera::INTERSECT;
 	
+	/* If the camera is inside the box, assume intersect. */
+	if (!node->inside(GetActiveCamera()->NodeGetWorldPosition()))
+	{
+		MT_Point3 box[8];
+		node->get(box);
+		intersect = GetActiveCamera()->BoxInsideFrustum(box);
+	}
+
+	switch (intersect)
+	{
+		case KX_Camera::OUTSIDE:
+			MarkSubTreeVisible(node, rasty, false);
+			break;
+		case KX_Camera::INTERSECT:
+			if (node->Client())
+			{
+				KX_GameObject *gameobj = (KX_GameObject*) node->Client()->GetSGClientObject();
+				int nummeshes = gameobj->GetMeshCount();
+				
+				for (int m=0;m<nummeshes;m++)
+				{
+					// this adds the vertices to the display list
+					(gameobj->GetMesh(m))->SchedulePolygons(rasty->GetDrawingMode(),rasty);
+				}
+				gameobj->MarkVisible();
+			}
+			if (node->Left())
+				MarkVisible(node->Left(), rasty);
+			if (node->Right())
+				MarkVisible(node->Right(), rasty);
+			break;
+		case KX_Camera::INSIDE:
+			MarkSubTreeVisible(node, rasty, true);
+			break;
+	}
+}
+
+void KX_Scene::MarkSubTreeVisible(SG_Tree *node, RAS_IRasterizer* rasty, bool visible)
+{
+	if (node->Client())
+	{
+		KX_GameObject *gameobj = (KX_GameObject*) node->Client()->GetSGClientObject();
+		if (visible)
+		{
+			int nummeshes = gameobj->GetMeshCount();
+			
+			for (int m=0;m<nummeshes;m++)
+			{
+				// this adds the vertices to the display list
+				(gameobj->GetMesh(m))->SchedulePolygons(rasty->GetDrawingMode(),rasty);
+			}
+		}
+		gameobj->MarkVisible(visible);
+	}
+	if (node->Left())
+		MarkSubTreeVisible(node->Left(), rasty, visible);
+	if (node->Right())
+		MarkSubTreeVisible(node->Right(), rasty, visible);
+}
+
+
+void KX_Scene::CalculateVisibleMeshes(RAS_IRasterizer* rasty)
+{
+// FIXME: When tree is operational
+#if 1
 	// do this incrementally in the future
 	for (int i = 0; i < m_objectlist->GetCount(); i++)
 	{
 		KX_GameObject* gameobj = (KX_GameObject*)m_objectlist->GetValue(i);
+		bool vis = !GetActiveCamera()->GetFrustumCulling();
+		if (!vis)
+			vis = gameobj->GetSGNode()->inside( GetActiveCamera()->GetCameraLocation() );
+		if (!vis)
+		{
+			MT_Point3 box[8];
+			gameobj->GetSGNode()->getBBox(box);
+			vis = GetActiveCamera()->BoxInsideFrustum(box) != KX_Camera::OUTSIDE;
+		}
 		
-		int nummeshes = gameobj->GetMeshCount();
-		
-		for (int m=0;m<nummeshes;m++)
+		if (vis)
 		{
-			// this adds the vertices to the display list
-			(gameobj->GetMesh(m))->SchedulePolygons(rasty->GetDrawingMode(),rasty);
+			
+			int nummeshes = gameobj->GetMeshCount();
+			
+			for (int m=0;m<nummeshes;m++)
+			{
+				// this adds the vertices to the display list
+				(gameobj->GetMesh(m))->SchedulePolygons(rasty->GetDrawingMode(),rasty);
+			}
 			// Visibility/ non-visibility are marked
 			// elsewhere now.
 			gameobj->MarkVisible();
+		} else {
+			gameobj->MarkVisible(false);
 		}
 	}
+#else
+	MarkVisible(m_objecttree, rasty);
+#endif
 }
 
 // logic stuff
@@ -978,6 +1064,11 @@ void	KX_Scene::SetGravity(const MT_Vector3& gravity)
 	GetPhysicsEnvironment()->setGravity(gravity[0],gravity[1],gravity[2]);
 }
 
+void KX_Scene::SetNodeTree(SG_Tree* root)
+{
+	m_objecttree = root;
+}
+
 void KX_Scene::SetPhysicsEnvironment(class PHY_IPhysicsEnvironment* physEnv)
 {
 	SumoPhysicsEnvironment *sme = dynamic_cast<SumoPhysicsEnvironment *>(physEnv);
diff --git a/source/gameengine/Ketsji/KX_Scene.h b/source/gameengine/Ketsji/KX_Scene.h
index 35f2f9dbb71..a468a8d1861 100644
--- a/source/gameengine/Ketsji/KX_Scene.h
+++ b/source/gameengine/Ketsji/KX_Scene.h
@@ -68,6 +68,7 @@ class SND_IAudioDevice;
 class NG_NetworkDeviceInterface;
 class NG_NetworkScene;
 class SG_Node;
+class SG_Tree;
 class KX_Camera;
 class GEN_HashedPtr;
 class KX_GameObject;
@@ -87,6 +88,8 @@ class SG_IObject;
  * */
 class KX_Scene : public SCA_IScene
 {
+	//Py_Header;
+protected:
 	RAS_BucketManager*	m_bucketmanager;
 	CListValue*			m_tempObjectList;
 
@@ -102,6 +105,11 @@ class KX_Scene : public SCA_IScene
 	CListValue*			m_lightlist;
 
 	/**
+	 *  The tree of objects in the scene.
+	 */
+	SG_Tree*			m_objecttree;
+
+	/**
 	 * The set of cameras for this scene
 	 */
 	set<class KX_Camera*>       m_cameras;
@@ -222,7 +230,7 @@ class KX_Scene : public SCA_IScene
 	 * Toggle to enable or disable activity culling.
 	 */
 	bool m_activity_culling;
-
+	
 	/**
 	 * The framing settings used by this scene
 	 */
@@ -235,6 +243,9 @@ class KX_Scene : public SCA_IScene
 	 */
 	RAS_Rect m_viewport;
 	
+	void MarkVisible(SG_Tree *node, RAS_IRasterizer* rasty);
+	void MarkSubTreeVisible(SG_Tree *node, RAS_IRasterizer* rasty, bool visible);
+
 public:
 	KX_Scene(class SCA_IInputDevice* keyboarddevice,
 		class SCA_IInputDevice* mousedevice,
@@ -469,6 +480,31 @@ public:
 	void SetPhysicsEnvironment(class PHY_IPhysicsEnvironment*	physEnv);
 
 	void	SetGravity(const MT_Vector3& gravity);
+	
+	/**
+	 * Sets the node tree for this scene.
+	 */
+	void SetNodeTree(SG_Tree* root);
+
+#if 0
+	KX_PYMETHOD_DOC(KX_Scene, GetLightList);
+	KX_PYMETHOD_DOC(KX_Scene, GetObjectList);
+	KX_PYMETHOD_DOC(KX_Scene, GetName);
+	
+	KX_PYMETHOD_DOC(KX_Scene, GetActiveCamera);
+	KX_PYMETHOD_DOC(KX_Scene, SetActiveCamera);
+	KX_PYMETHOD_DOC(KX_Scene, FindCamera);
+	
+	KX_PYMETHOD_DOC(KX_Scene, SetGravity);
+	
+	KX_PYMETHOD_DOC(KX_Scene, SetActivityCulling);
+	KX_PYMETHOD_DOC(KX_Scene, SetActivityCullingRadius);
+	
+	KX_PYMETHOD_DOC(KX_Scene, SetSceneViewport);
+	KX_PYMETHOD_DOC(KX_Scene, GetSceneViewport);
+
+	virtual PyObject* _getattr(const STR_String& attr); /* name, active_camera, gravity, suspended, viewport, framing, activity_culling, activity_culling_radius */
+#endif
 };
 
 typedef std::vector<KX_Scene*> KX_SceneList;