Jump to content
  • Advertisement

Archived

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

DevLiquidKnight

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

This topic is 5230 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
Advertisement
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
im really looking to get this to work first then I can focus on making it more oct tree based and recursion is calling a function in itself but Ima go look up binary trees ect

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

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!