Scene Graphs? | GameDev.net

I tried to implement a scene graph in my engine, but perhaps I was going about it the wrong way because it's pretty inefficient and seems to hurt performance. For each frame, I go through my scene's quadtree and add each visible object to the graph. The graph then uses a breadth-first search to find a "texture" node that matches the texture on the object, and then adds the object under that node. Traversing the scene graph goes: 1) draw the top node (the player perspective, so the camera is positioned) 2) draw each node of the next level and its children (so bind texture, draw all objects with the same texture, move on to next texture...) Then the graph is deleted at the end of the frame drawing code. Am I missing something crucial? Is there a way to keep the graph stable? I had z-sorting, but that made things even slower than they are now, which is still slower than immediate mode even with ~250 drawn objects of the same texture. What am I doing wrong?

I'll just give you the code I have:

SceneGraph:
.h:

#pragma once#include "Player.h"#include <vector>#include <list>enum SGNodeType{	ENTITY,	PLAYER,	TEXTURE};class SGNode{public:	SGNode() {}	~SGNode() {};	virtual void draw()=0;	void drawChildren()	{		std::list<SGNode*>::iterator iter=children.begin();		while(iter != children.end())		{			(*iter)->draw();			++iter;		}	}	SGNodeType GetType()	{return type;}	std::list<SGNode*> children;	SGNodeType type;};class SGEntNode:public SGNode{	public:	SGEntNode() { type=ENTITY;}	virtual void draw()	{		std::list<MemPtr<Entity> >::iterator iter=entities.begin();		while(iter != entities.end())		{			glPushMatrix();				(*iter)->draw();			glPopMatrix();			++iter;		}	}	std::list<MemPtr<Entity> > entities;};class SGTexNode:public SGNode{	public:	SGTexNode(ResourcePtr<RTexture> tex):texture(tex) { type=TEXTURE;}	virtual void draw(){		if(texture)			texture->Bind();		else			glBindTexture(GL_TEXTURE_2D, 0);			drawChildren();	}	ResourcePtr<RTexture> texture;};class SGPlayerNode:public SGNode{	public:		SGPlayerNode(MemPtr<Player> pl):player(pl){ type=PLAYER;}	virtual void draw(){		glPushMatrix();			player->draw();			drawChildren();		glPopMatrix();	}	MemPtr<Player> player;};class SceneGraph{public:	SceneGraph(void);	~SceneGraph(void);	void AddEntity(MemPtr<Entity> ent);	void AddEntity(MemPtr<Player> ent);	void draw();private:	SGNode *m_graph;	void RecurseDelete(SGNode *n);	SGNode *SortOnTexture(MemPtr<Entity> ent, SGNode *start);	void SortOnZ(MemPtr<Entity> ent, SGNode *start);};

.cpp:

#include ".\scenegraph.h"SceneGraph::SceneGraph(void){}SceneGraph::~SceneGraph(void){	RecurseDelete(m_graph);}//////////////////////////////////////////////////////////////////////////////////////////// Name: RecurseDelete// Desc: Recursively deletes the nodes in the scene graph// Notes: // ToFix: //////////////////////////////////////////////////////////////////////////////////////////void SceneGraph::RecurseDelete(SGNode *n){	std::list<SGNode*>::iterator iter=n->children.begin();	while(iter != n->children.end())	{		RecurseDelete(*iter);		++iter;	}	delete n;}//////////////////////////////////////////////////////////////////////////////////////////// Name: AddEntity// Desc: Adds a player's perspective to the scene graph// Notes: This should be expanded so that all rotations are hierarchical// ToFix: //////////////////////////////////////////////////////////////////////////////////////////void SceneGraph::AddEntity(MemPtr<Player> ent){	SGPlayerNode *n=new SGPlayerNode(ent);	m_graph=n;}//////////////////////////////////////////////////////////////////////////////////////////// Name: AddEntity// Desc: Wrapper for various tests// Notes: A player must be added before this is called!// ToFix: //////////////////////////////////////////////////////////////////////////////////////////void SceneGraph::AddEntity(MemPtr<Entity> ent){	SortOnTexture(ent, m_graph);}//////////////////////////////////////////////////////////////////////////////////////////// Name: SortOnTexture// Desc: Finds the node at or under start with the bound texture(or adds its own and returns)// Notes: // ToFix: //////////////////////////////////////////////////////////////////////////////////////////SGNode *SceneGraph::SortOnTexture(MemPtr<Entity> ent, SGNode *start){	std::list<SGNode*> q;	q.push_back(start);		SGNode *curr;	while(!q.empty())	{		curr=q.front();		if(curr->type == TEXTURE && ((SGTexNode*)curr)->texture == ent->m_texture)			break;				q.pop_front();			// put the pop here so if we break, the size will never be 0		std::list<SGNode*>::iterator iter=curr->children.begin();		while(iter != curr->children.end())		{			q.push_back(*iter);			++iter;		}	}		// if there was no texture match, add my own	if(q.empty())	{		curr=new SGTexNode(ent->m_texture);		curr->children.push_back(new SGEntNode());		start->children.push_back(curr);	}	((SGEntNode*)(curr->children.front()))->entities.push_back(ent);	return curr;}//////////////////////////////////////////////////////////////////////////////////////////// Name: draw// Desc: Draws the scene graph// Notes: // ToFix: //////////////////////////////////////////////////////////////////////////////////////////void SceneGraph::draw(){	m_graph->draw();}

Rendering (m_entities is a quadtree):

void EntityManager::Draw(){	if(!m_player)	{		LOG_ERROR(true, "m_player is NULL!");	}	m_player->UpdateMouse();	glLoadIdentity();	m_player->draw();	m_player->UpdateFrustum();	glLoadIdentity();	SceneGraph *graph=new SceneGraph();	graph->AddEntity(m_player);	m_entities->FillSceneGraph(graph, true);		graph->draw();	delete graph;}

Topic Locked