Sign in to follow this  
ms291052

More OctTree help

Recommended Posts

ms291052    223
I recently made my octtree set a diffuse color equal to the depth of the node a triangle was in, and I think (ok, it was pretty obvious) that something was wrong. So once again, I hope some kind soul will be willing to look at these three functions and tell me where I went wrong, since this is the second rewrite and I'm clueless. Function 1: The triangle struct holds three points, p0, p1, and p2. I know this function doesn't take into consideration that the triangle could be larger than the whole node but my results don't show that to be the problem and at this stage I'm not worrying about it.
bool cOctTreeNode::CheckTriangle(TRIANGLE* tri)
{
	   if(((m_Min.x <= tri->p0.x && tri->p0.x <= m_Max.x) && (m_Min.y <= tri->p0.y && tri->p0.y <= m_Max.y) && (m_Min.z <= tri->p0.z && tri->p0.z <= m_Max.z)) ||
	      ((m_Min.x <= tri->p1.x && tri->p1.x <= m_Max.x) && (m_Min.y <= tri->p1.y && tri->p1.y <= m_Max.y) && (m_Min.z <= tri->p1.z && tri->p1.z <= m_Max.z)) ||
	      ((m_Min.x <= tri->p2.x && tri->p2.x <= m_Max.x) && (m_Min.y <= tri->p2.y && tri->p2.y <= m_Max.y) && (m_Min.z <= tri->p2.z && tri->p2.z <= m_Max.z)))
	   return true;
	else
		return false;
}

Function 2:
void cOctTreeNode::AddTriangle(TRIANGLE* tri)
{
	if(!m_bIsLeaf) //m_bIsLeaf is true if this is a leaf node, false otherwise
	{
		for(int i=0; i < 8; i++)
		{
			if(m_pChildren[i] != NULL && m_pChildren[i]->CheckTriangle(tri))
			{
				m_pChildren[i]->AddTriangle(tri);
				return;
			}
		}
	}
	else
	{
		m_pMaterialGroups[tri->material].AddTriangle(tri);
		if(GetTotalTris() > MAXTRIANGLESPERNODE)
			SplitNode();
	}
}

Function 3:
void cOctTreeNode::SplitNode()
{
	if(!m_bIsLeaf)
		return;

	float Mx = m_Max.x;
	float My = m_Max.y;
	float Mz = m_Max.z;
	float mx = m_Min.x;
	float my = m_Min.y;
	float mz = m_Min.z;
	float hx = (m_Max.x + m_Min.x)/2.0f;
	float hy = (m_Max.y + m_Min.y)/2.0f;
	float hz = (m_Max.z + m_Min.z)/2.0f;

	m_pChildren[0] = new cOctTreeNode;
	m_pChildren[0]->m_Min = Vector3(mx, hy, hz);
	m_pChildren[0]->m_Max = Vector3(hx, My, Mz);
	m_pChildren[0]->m_bIsLeaf = true;
	m_pChildren[0]->m_pParent = m_pParent;

	m_pChildren[1] = new cOctTreeNode;
	m_pChildren[1]->m_Min = Vector3(hx, hy, hz);
	m_pChildren[1]->m_Max = Vector3(Mx, My, Mz);
	m_pChildren[1]->m_bIsLeaf = true;
	m_pChildren[1]->m_pParent = m_pParent;

	m_pChildren[2] = new cOctTreeNode;
	m_pChildren[2]->m_Min = Vector3(mx, hy, mz);
	m_pChildren[2]->m_Max = Vector3(hx, My, hz);
	m_pChildren[2]->m_bIsLeaf = true;
	m_pChildren[2]->m_pParent = m_pParent;

	m_pChildren[3] = new cOctTreeNode;
	m_pChildren[3]->m_Min = Vector3(hx, hy, mz);
	m_pChildren[3]->m_Max = Vector3(Mx, My, hz);
	m_pChildren[3]->m_bIsLeaf = true;
	m_pChildren[3]->m_pParent = m_pParent;

	m_pChildren[4] = new cOctTreeNode;
	m_pChildren[4]->m_Min = Vector3(mx, my, hz);
	m_pChildren[4]->m_Max = Vector3(hx, hy, Mz);
	m_pChildren[4]->m_bIsLeaf = true;
	m_pChildren[4]->m_pParent = m_pParent;

	m_pChildren[5] = new cOctTreeNode;
	m_pChildren[5]->m_Min = Vector3(hx, my, hz);
	m_pChildren[5]->m_Max = Vector3(Mx, hy, Mz);
	m_pChildren[5]->m_bIsLeaf = true;
	m_pChildren[5]->m_pParent = m_pParent;

	m_pChildren[6] = new cOctTreeNode;
	m_pChildren[6]->m_Min = Vector3(mx, my, mz);
	m_pChildren[6]->m_Max = Vector3(hx, hy, hz);
	m_pChildren[6]->m_bIsLeaf = true;
	m_pChildren[6]->m_pParent = m_pParent;

	m_pChildren[7] = new cOctTreeNode;
	m_pChildren[7]->m_Min = Vector3(hx, my, mz);
	m_pChildren[7]->m_Max = Vector3(Mx, hy, hz);
	m_pChildren[7]->m_bIsLeaf = true;
	m_pChildren[7]->m_pParent = m_pParent;

	m_pChildren[0]->m_Depth = m_pChildren[1]->m_Depth = m_pChildren[2]->m_Depth = m_pChildren[3]->m_Depth = m_pChildren[4]->m_Depth = m_pChildren[5]->m_Depth = m_pChildren[6]->m_Depth = m_pChildren[7]->m_Depth = m_Depth + 1;

	for(DWORD i=0; i < 8; i++)
	{
		if(!m_pParent->CountTriangles(m_pChildren[i]->m_Min, m_pChildren[i]->m_Max))
		{
			delete m_pChildren[i];
			m_pChildren[i] = NULL;
		}
	}

	m_bIsLeaf = false;

	for(DWORD i=0; i < 8; i++)
	{
		cOctTreeNode* curr = m_pChildren[i];
		if(curr == NULL)
			continue;

		curr->m_NumMaterialGroups = m_NumMaterialGroups;
		curr->m_pMaterialGroups = new cMaterialGroup[m_NumMaterialGroups];
		for(DWORD j=0; j < m_NumMaterialGroups; j++)
		{
			curr->m_pMaterialGroups[j].Init(m_pMaterialGroups[j].GetDevice(), j, m_pMaterialGroups[j].m_pTextureFileName, m_pMaterialGroups[j].GetMaterial());
			curr->m_pMaterialGroups[j].m_pParent = curr;
			for(DWORD k = 0; k < m_pMaterialGroups[j].m_Triangles.size(); k++)
			{
				if(curr->CheckTriangle(m_pMaterialGroups[j].m_Triangles[k]))
					curr->AddTriangle(m_pMaterialGroups[j].m_Triangles[k]);
			}
		}
	}

	for(DWORD i=0; i < m_NumMaterialGroups; i++)
		m_pMaterialGroups[i].Shutdown();
	delete[] m_pMaterialGroups;
	m_pMaterialGroups = NULL;
	m_NumMaterialGroups = 0;
}

Thanks so much everyone who so much as reads this. I'd appreciate any advice! Thanks ms

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
In function 3 you are setting the childrens parent to the current leaf's parent. Try setting the children's parent to the leaf itself.

change:

// previous code
m_pChildren[0]->m_bIsLeaf = true;
m_pChildren[0]->m_pParent = m_pParent;
// rest of code

to:

// previous code
m_pChildren[0]->m_bIsLeaf = true;
m_pChildren[0]->m_pParent = this;
// rest of code


I stopped reading through your code at that point so if it doesn't help, I'll take a second look for you.

Share this post


Link to post
Share on other sites
ms291052    223
Thanks. I'm sorry I should have clarified. The m_pParent actually points to the cOctTree structure that is the parent of all the cOctTreeNodes. Does that make sense? That way each node has access to the cOctTree's vertex buffer, among other things. Thanks for the advice, though.


I know that third function is a bit tedious to read through. I believe most of it's correct. The part I seriously question is just this littler segment:

for(DWORD i=0; i < 8; i++)
{
cOctTreeNode* curr = m_pChildren[i];
if(curr == NULL)
continue;

curr->m_NumMaterialGroups = m_NumMaterialGroups;
curr->m_pMaterialGroups = new cMaterialGroup[m_NumMaterialGroups];
for(DWORD j=0; j < m_NumMaterialGroups; j++)
{
//Init takes a device object, a material index, a filename for the texture, and a material structure
curr->m_pMaterialGroups[j].Init(m_pMaterialGroups[j].GetDevice(), j, m_pMaterialGroups[j].m_pTextureFileName, m_pMaterialGroups[j].GetMaterial());
//A material group's parent is the cOctTreeNode [as opposed to cOctTreeNode's parent being of type cOctTree]
curr->m_pMaterialGroups[j].m_pParent = curr;
for(DWORD k = 0; k < m_pMaterialGroups[j].m_Triangles.size(); k++)
{
if(curr->CheckTriangle(m_pMaterialGroups[j].m_Triangles[k]))
curr->AddTriangle(m_pMaterialGroups[j].m_Triangles[k]);
}
}
}



Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this