# More OctTree help

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

## Recommended Posts

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:
{
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 != NULL && m_pChildren->CheckTriangle(tri))
{
return;
}
}
}
else
{
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->m_Min, m_pChildren->m_Max))
{
delete m_pChildren;
m_pChildren = NULL;
}
}

m_bIsLeaf = false;

for(DWORD i=0; i < 8; i++)
{
cOctTreeNode* curr = m_pChildren;
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]))
}
}
}

for(DWORD i=0; i < m_NumMaterialGroups; i++)
m_pMaterialGroups.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 on other sites
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 on other sites
Wierd. My post came up as anonymous and I was logged in.

##### Share on other sites
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;
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]))
}
}
}

1. 1
2. 2
Rutin
16
3. 3
4. 4
5. 5

• 26
• 11
• 9
• 9
• 11
• ### Forum Statistics

• Total Topics
633702
• Total Posts
3013450
×