Archived

This topic is now archived and is closed to further replies.

I've been trying to solve this Linked List Oct tree problem for 5 hours...

This topic is 5012 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

The problem occurs when deleteing the data from the linked list.. also the data when I read it is not correctly drawing the bounding boxes for my oct tree its not even drawing them, when it should be.. I dont know whats wrong.. ive been messing with it forever trying to figure it out if anyone can help it would be great.
struct treeNode
{
	D3DXVECTOR3 min;
	D3DXVECTOR3 max;
	D3DXVECTOR3 pos;
};
#define OCTTREE_FVF   (D3DFVF_XYZ|D3DFVF_DIFFUSE)  
class OctTreeNode
{
public:
	OctTreeNode() {  };
	OctTreeNode(D3DXVECTOR3 pos, D3DXVECTOR3 min, D3DXVECTOR3 max)
	{
		thisNode.min = min;
		thisNode.max = max;
		thisNode.pos = pos;
	};
	treeNode	thisNode;
	OctTreeNode *pNextNode;
};
class COctTree
{
	private:
		OctTreeNode		*nodes;
		OctTreeNode		*pTail;
		int				iNumberOfNodes;
		D3DXVECTOR3		GetMinVector(int index);
		D3DXVECTOR3		GetMaxVector(int index);
	public:

						COctTree();
						~COctTree();
		void			AddNode(D3DXVECTOR3 pos, D3DXVECTOR3 min, D3DXVECTOR3 max);

		void			CreateOctTree(IDirect3DDevice9 *device, DWORD dwNumVertices);
		void			RenderOctTree(IDirect3DDevice9 *device);
		void			DestroyOctTree();
		void			RemoveNode(OctTreeNode *pNode);
	protected:
		LPDIRECT3DVERTEXBUFFER9		m_pOctTreeVB;			// Oct-Tree Vertex buffer

		D3DXVECTOR3					m_vOctTreeVert[8];
		D3DMATERIAL9				mtrl;
};
#endif

#include "COctTree.h"
#define SafeRelease(p) { if(p) { (p)->Release(); (p)=NULL; } }
COctTree::COctTree()
: nodes(NULL)
{
	mtrl.Diffuse.r = 1.0f;
	mtrl.Diffuse.g = 1.0f;
	mtrl.Diffuse.b = 1.0f;
	nodes = new OctTreeNode;
}
COctTree::~COctTree()
{
	DestroyOctTree();
	if(nodes)
	{
		delete nodes;
		nodes=NULL;
	}
	SafeRelease(m_pOctTreeVB);
}
void COctTree::RenderOctTree(IDirect3DDevice9 *device)
{
	// render the bounding boxes

	device->SetRenderState( D3DRS_LIGHTING, FALSE );
	device->SetTexture( 0, NULL );
	device->SetMaterial( &mtrl );
	device->SetFVF( OCTTREE_FVF );
	device->SetStreamSource( 0, m_pOctTreeVB, 0, sizeof(OCT_TREEVERTEX) );
	device->DrawPrimitive( D3DPT_LINELIST, 0, iNumberOfNodes);
	device->SetRenderState( D3DRS_LIGHTING, TRUE );
}
void COctTree::CreateOctTree(IDirect3DDevice9 *device, DWORD dwNumVertices)
{
	OCT_TREEVERTEX* pOctTreeVB = NULL;
	// create box VB

	device->CreateVertexBuffer(dwNumVertices*24*sizeof(OCT_TREEVERTEX),D3DUSAGE_WRITEONLY,OCTTREE_FVF,D3DPOOL_MANAGED,&m_pOctTreeVB, NULL);
	if( SUCCEEDED(m_pOctTreeVB->Lock( 0, 0, (void**) &pOctTreeVB, 0 )) )
	{
		for(int i=0; i<dwNumVertices; i++)
		{		
			DWORD dw[24] = { 0,1, 2,3, 0,2, 1,3, 4,5, 6,7, 4,6, 5,7, 0,4, 2,6, 1,5, 3,7 };
			D3DXVECTOR3  min = GetMinVector(i);
			D3DXVECTOR3  max = GetMaxVector(i);
			m_vOctTreeVert[0] = D3DXVECTOR3(min.x, min.y, min.z ); // xyz

			m_vOctTreeVert[1] = D3DXVECTOR3(max.x, min.y, min.z ); // Xyz


			m_vOctTreeVert[2] = D3DXVECTOR3(min.x, max.y, min.z  ); // xYz

			m_vOctTreeVert[3] = D3DXVECTOR3(max.x, max.y, min.z ); // XYz


			m_vOctTreeVert[4] = D3DXVECTOR3(min.x, min.y, max.z ); // xyZ

			m_vOctTreeVert[5] = D3DXVECTOR3(max.x, min.y, max.z ); // XyZ


			m_vOctTreeVert[6] = D3DXVECTOR3(min.x, max.y, max.z ); // xYZ

			m_vOctTreeVert[7] = D3DXVECTOR3(max.x, max.y, max.z); // XYZ

			for( int v=0; v<24; v++ )
			{
				pOctTreeVB->p = m_vOctTreeVert[ dw[v] ];
				pOctTreeVB->c = D3DXCOLOR(255,0,0,0);
				pOctTreeVB++;
			}
		}
	}
	m_pOctTreeVB->Unlock(); 
}
D3DXVECTOR3 COctTree::GetMinVector(int index)
{
	OctTreeNode *current=nodes;
	for(int i=0; i<index; i++)
	{
		if(nodes->pNextNode != NULL)
		{
			current=nodes->pNextNode;
		}
	}
	return current->thisNode.min;
}
D3DXVECTOR3 COctTree::GetMaxVector(int index)
{
	OctTreeNode *current=nodes;
	for(int i=0; i<index; i++)
	{
		if(nodes->pNextNode != NULL)
		{
			current=nodes->pNextNode;
		}
	}
	return current->thisNode.max;
}
void COctTree::AddNode(D3DXVECTOR3 pos, D3DXVECTOR3 min, D3DXVECTOR3 max)
{
	nodes->pNextNode = new OctTreeNode(pos,min,max);
	nodes->pNextNode->pNextNode = NULL;
	iNumberOfNodes++;
}
void COctTree::DestroyOctTree()
{
	if(nodes)
	{
		OctTreeNode *temp;  // stores next pointer before delete

		for (OctTreeNode *p = nodes; p != NULL; p = temp)
		{
			if(p)
			{
				//  Problem occurs at delete p

				temp = p->pNextNode;  // must save before delete

				delete p;
			}
			else
			{
				break;
			}
		}
	}
}
[edited by - DevLiquidKnight on March 26, 2004 9:16:30 PM]

Share this post


Link to post
Share on other sites
just as a "this doesn't help your problem but it's definitely wrong" comment:

each node of an octtree has up to 8 child nodes, not 1. it's not a linked list, it's a tree:


class OctTreeNode
{
private:
int numChildren;
OctTreeNode *children;
}


anyway, what's the "problem occurs"? does the app crash? run it through your debugger so you can tell us what line it crashes on. and give us the _exact_ error message that you get.

-me

[edited by - Palidine on March 26, 2004 9:21:30 PM]

Share this post


Link to post
Share on other sites
another problem is that you forgot to write a destructor for OctTreeNode that deletes it's children:


class OctTreeNode
{
public:
~OctTreeNode()
{
if (pNextNode)
{
delete pNextNode;
pNextNode = NULL;
}
}

};


then insead of your cumbersome DestroyOctTree method you can just call:


if (nodes)
{
delete nodes;
nodes = NULL;
}

-me

[edited by - Palidine on March 26, 2004 9:25:31 PM]

Share this post


Link to post
Share on other sites
As for the exact Error I get:
Unhandled exception at 0x004f5dcb in Direct3D.exe: 0xC0000005: Access violation reading location 0x0302ffc4.

The value of p
- p 0x0302ffd0 {thisNode={min={-4.31602e+008, -4.31602e+008, -4.31602e+008} max={-4.31602e+008, -4.31602e+008, -4.31602e+008} pos={-4.31602e+008, -4.31602e+008, -4.31602e+008} } pNextNode=0x05a88fd0 {thisNode={min={76.2122, 7.3129, 46.1707} max={76.2122, 7.3129, 46.1707} pos={81.2122, 12.3129, 51.1707} } pNextNode=0x00000000 {thisNode={min={...} max={...} pos={...} } pNextNode=??? } } } OctTreeNode *



quote:
Original post by Palidine
another problem is that you forgot to write a destructor for OctTreeNode that deletes it''s children:


class OctTreeNode
{
public:
~OctTreeNode()
{
if (pNextNode)
{
delete pNextNode;
pNextNode = NULL;
}
}

};


-me

I tried this exact thing the EXACT code even.. it dies. on the destruciton... when i did it that way so I thought I had to do it another way...

Share this post


Link to post
Share on other sites
wooo look at me i''m mr reply guy.

get rid of the tail pointer. a tail doesn''t make any sense for an octtree. an octtree has leaves. it can have hundreds or thousands of leaves. it''s a tree structure. if you''re not familliar with trees, look up binary tree and study the creation and "walking" of those data structures before you try and create an octtree. otherwise you''re going to lose your mind.

octtrees are all about recursion. if you don''t know what that is, no worries, you''ll learn all about it when you learn about binary trees. (an octtree is just a binary tree except that instead of just 2 children per node, you have up to 8)

-me

Share this post


Link to post
Share on other sites
this is bad:

OctTreeNode *temp; // stores next pointer before delete
for (OctTreeNode *p = nodes; p != NULL; p = temp)

you''re not initializing temp to anything. my guess is that the first line should look like this:

OctTreeNode *temp = nodes;

-me

Share this post


Link to post
Share on other sites
looks like you got the octrees all wrong.


struct treeNode
{
D3DXVECTOR3 min;
D3DXVECTOR3 max;
};

#define OCTTREE_FVF (D3DFVF_XYZ|D3DFVF_DIFFUSE)

class OctTreeNode
{
public:
OctTreeNode()
{
ZeroMemory(pBranch, sizeof(pBranch));
iNumberOfNodes = 0;
};

OctTreeNode(D3DXVECTOR3 pos, D3DXVECTOR3 min, D3DXVECTOR3 max)
{
thisNode.min = min;
thisNode.max = max;
thisNode.pos = pos;

ZeroMemory(pBranch, sizeof(pBranch));
iNumberOfNodes = 0;
};

~OcTreeNode()
{
for(int i = 0; i < 8; i ++)
{
if (pBranch[i])
delete pBranch[i];

pBranch = NULL;
}
}

treeNode thisNode;
OctTreeNode* pBranch[8];
int iNumberOfNodes;

LPDIRECT3DVERTEXBUFFER9 pObjectFragmentVB; // fragment of the object contained in the leaf

};


class COctTree
{
private:
OctTreeNode *root;
public:
COctTree()
{
root = NULL;
}

~COctTree()
{
if (root)
delete root;
}

void CreateOctTree(IDirect3DDevice9 *device);
void RenderOctTree(IDirect3DDevice9 *device,
LPDIRECT3DVERTEXBUFFER9 pObjectVB);
};
#endif


that octree structure won''t do much, unless you attach it to a mesh in need for some subdivision. if the octree branch is a leaf (no further subdivisions), it will contain a fragment of the original object contained in the leaf''s box. SO when the leaf is inside the frustum, only that fragment get rendered.

Share this post


Link to post
Share on other sites
Heres how I delete my linked list nodes. Mayhaps it''ll help you out.


// Deconstructor

~CLinkedList(void)
{
CListNode<T> *pNodeToDelete, *pCurrentNode = m_pHeadNode;
while(pCurrentNode)
{
pNodeToDelete = pCurrentNode;
pCurrentNode = pCurrentNode->GetNext();
delete pNodeToDelete;
}
}


Don''t worry about CListNode just change that to your Octree Node class.

Share this post


Link to post
Share on other sites
I think I did that before and it failed..
Could it be the way im adding my nodes?

nodes->pNextNode = new OctTreeNode(pos,min,max);
nodes->pNextNode->pNextNode = NULL;
iNumberOfNodes++;

Also the inlliense is all messed up on the add node part..
VERY MESSED UP
it tends to think its declared as somthing 100% differnt then what it is.


//header declariation:

void AddNode(D3DXVECTOR3 pos, D3DXVECTOR3 min, D3DXVECTOR3 max);




// code

void COctTree::AddNode(D3DXVECTOR3 pos, D3DXVECTOR3 min, D3DXVECTOR3 max)
{

pHeadNode->pNextNode = new OctTreeNode(pos,min,max);
pHeadNode->pNextNode->pNextNode = NULL;
iNumberOfNodes++;
}




Intellisense picks up this:

void COctTree::AddNode(D3DXVECTOR3 pos,D3DXVECTOR3(*)(D3DXVECTOR3 pos))
{
// and the code inside add node is all picked up as D3DXVECTOR3's which its not.....

}


[edited by - DevLiquidKnight on March 27, 2004 1:24:45 AM]

Share this post


Link to post
Share on other sites
I dont think this is a problem thats going to be solved with a quick one line fix. The way you're doing things is somewhat fubar'd and is going to need to be addressed on a bigger scale.

I'd first start off with Palidine's suggestion on the OctTreeNode object. You can use a linked list for the list of childnodes, but thats just going to make things unnecessarily complicated.

I'd personally use:


class OctTreeNode
{
public:
int numChildren;
OctTreeNode *children[8];
}



the constructor would look something like this


OctTreeNode::OctTreeNode()
{

for (x=0; x<8; x++) {
children[x]=NULL;
}

}


and the destructor:


OctTreeNode::~OctTreeNode()
{

for (x=0; x<8; x++) {
if (children[x]) {
delete children[x];
children[x]=NULL;
}
}
}




The OctTree class at its simplest level would look like this:


class OctTree
{

public:

OctTreeNode *root;

};


Don't forget to set root to NULL in the constructor!

then to create the tree and initilize the root node (which is basically the node that encapsulates your entire world) you'd do:


OctTree *tree = new OctTree;
tree->root = new OctTreeNode(whateverparamsyouwanttopass);


where "whateverparamsyouwanttopass" would prolly be the min and max coordinates of the bounding box.


Then to build the tree:


OctTree::BuildOctTree(OctTreeNode *node)
{

//Here you'd split the world up and figure out what polygons go where.

for (x=0; x<8; x++) {
children[x]= new OctTreeNode (whateverparamsyouwanttopass);
BuildOctTree(children[x]);
}

}


You may want to pass in a list of polygons to the BuildOctTree method, it really depends off how you're managing the dataset.

Finally after creating the root node above you'd basically call:


//recursive method
BuildOctTree(root); //maybe pass in the polylist here...

or

//recursive method
tree->BuildOctTree(tree->root); //maybe pass in the polylist here...

depending on where you actually call the BuildOctTree method.



Rendering the tree would be something like the following"


tree->RenderOctTree(tree->root); //recursive method


and the method to go along with it"


OctTree::RenderOctTree(OctTreeNode *node)
{
//Here you'd set various renderstates and stuff or whatever
for (x=0; x<8; x++) {
RenderOctTree(children[x]);
}

}




If you wanted to destroy the tree:

if (tree->root) {
delete tree->root;
tree->root = NULL;
}
delete tree;
tree = NULL;


This, due to the OctTreeNode destructor would set up a chain reaction that would destroy and free up the memory for every node in the octree.

Once you have a base foundation like this up and running, you can slowly start adding the DirectX, vertexbuffer and bounding box stuff back in.

This is by no means the best or most efficient way to do this, but hopefully it's enough to help you solve your problems and get you going.


-=[ Megahertz ]=-


Edit, seems using i as an array subscript was causing problems with italics.

[edited by - Megahertz on March 27, 2004 5:08:22 AM]

Share this post


Link to post
Share on other sites