struct TRIANGLE
{
Vector3 p0, p1, p2;
DWORD material;
};
class cOctTreeNode
{
public:
Vector3 m_Min;
Vector3 m_Max;
std::vector<TRIANGLE*> m_pTriangles;
DWORD m_NumTriangles;
cOctTreeNode* m_pChildren[8];
DWORD m_Depth;
cOctTreeNode();
void AddTriangle(TRIANGLE* triangle);
bool CheckTriangle(TRIANGLE* triangle);
void Shutdown();
};
cOctTreeNode::cOctTreeNode()
{
m_Min = m_Max = Vector3(0.0f, 0.0f, 0.0f);
m_pChildren[0] = m_pChildren[1] = m_pChildren[2] = m_pChildren[3] = m_pChildren[4] = m_pChildren[5] = m_pChildren[6] = m_pChildren[7] = NULL;
m_NumTriangles = 0;
m_Depth = -1;
}
void cOctTreeNode::AddTriangle(TRIANGLE* tri)
{
static DWORD MaxTrianglesPerNode = 200;
for(int i=0; i < 8; i++)
{
if(m_pChildren != NULL && m_pChildren->CheckTriangle(tri))
{
m_pChildren->AddTriangle(tri);
printf("Adding to child %lu (depth %lu)\n", i, m_Depth+1);
return;
}
}
m_pTriangles.push_back(tri);
++m_NumTriangles;
if(m_NumTriangles >= MaxTrianglesPerNode && m_pChildren[0] == NULL)
{
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[1] = new cOctTreeNode;
m_pChildren[1]->m_Min = Vector3(hx, hy, hz);
m_pChildren[1]->m_Max = Vector3(Mx, My, Mz);
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[3] = new cOctTreeNode;
m_pChildren[3]->m_Min = Vector3(hx, hy, mz);
m_pChildren[3]->m_Max = Vector3(Mx, My, hz);
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[5] = new cOctTreeNode;
m_pChildren[5]->m_Min = Vector3(hx, my, hz);
m_pChildren[5]->m_Max = Vector3(Mx, hy, Mz);
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[7] = new cOctTreeNode;
m_pChildren[7]->m_Min = Vector3(hx, my, mz);
m_pChildren[7]->m_Max = Vector3(Mx, hy, hz);
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;
vector<TRIANGLE*> temp = m_pTriangles;
m_pTriangles.erase(m_pTriangles.begin(), m_pTriangles.end());
m_NumTriangles = 0;
for(DWORD i=0; i < temp.size(); i++)
{
AddTriangle(temp);
}
}
}
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;
}
void cOctTreeNode::Shutdown()
{
for(DWORD i=0; i < 8; i++)
{
if(m_pChildren != NULL)
{
m_pChildren->Shutdown();
delete m_pChildren;
m_pChildren = NULL;
}
}
}
🔒 Locked
🎮 Unity
OctTree help!
Advertisement
Original Post
I'm having trouble loading my mesh into an octtree. I load a list of TRIANGLES and then call the AddTriangle method of my root node for each in the mesh. The root has m_Min and m_Max set properly, computed directly from the vertex buffer and m_Depth set to zero. The problem is that 90% of the triangles seem to end up in the root node despite my work. Thanks for any help!
I just took a quick look at your code, and it's hard to say what the problem is without knowing a little more about your input mesh. How many triangles does it have? Can you show the code where you set your initial octree bounds?
I admit I only looked quickly, so I may have missed an obvious problem. But maybe you could tell us a little more about your input data.
I admit I only looked quickly, so I may have missed an obvious problem. But maybe you could tell us a little more about your input data.
Initial Bounds and root creation code:
Current input mesh is a mesh representing a fairly small (128x128) terrain. Secondary is an untextured 'level' mesh that's just a couple of rooms slapped together. Problem occurs in both.
Current test mesh has 3250 triangles and just over 1K verts.
Vector3 min, max; OctTreeVertex* data; m_pVB->Lock(0, 0, (void**)&data, D3DLOCK_READONLY); D3DXComputeBoundingBox(&data[0].pos, m_NumVertices, sizeof(OctTreeVertex), &min, &max); m_pVB->Unlock(); m_Root = new cOctTreeNode; m_Root->m_Min = min m_Root->m_Max = max m_Root->m_Depth = 0; for(DWORD i=0; i < m_NumFaces; i++) { m_Root->AddTriangle(&m_pTriangles); }Current input mesh is a mesh representing a fairly small (128x128) terrain. Secondary is an untextured 'level' mesh that's just a couple of rooms slapped together. Problem occurs in both.
Current test mesh has 3250 triangles and just over 1K verts.
At a glance your code makes sense and seems like it should work. But there are places (setting the bounds of the children, testing the triangle) where there could be errors that I overlooked.
I would recommend doing some 'drawing' if you're still having problems. Write a function for cOctTreeNode that outlines the bounding box of the node in some solid color, and the triangles in another. Somehow set it up so you can 'step' through the nodes with a key press. Then look and just check visually. Are there triangles which are in node A that obviously should be in node B?
This might take a little work to set up, but it would probably help you track down your problem.
I would recommend doing some 'drawing' if you're still having problems. Write a function for cOctTreeNode that outlines the bounding box of the node in some solid color, and the triangles in another. Somehow set it up so you can 'step' through the nodes with a key press. Then look and just check visually. Are there triangles which are in node A that obviously should be in node B?
This might take a little work to set up, but it would probably help you track down your problem.
Thanks, jyk, for your advice. I wrote some code to draw the boxes and they look 100% perfect. I know the triangles are right because if I skip the whole octtree all together and just render them, they work. My CheckTriangle function and AddTriangle functions are therefore brought into question. However, the both look OK to me. Can anyone else spot any errors?
Hmm... taking another look at this makes me think that the problem is that the terrain's triangles do mostly cross the median y value of the root node, and as such don't fit into any of its children. This would cause most of them to be placed into the root. In the 'level' all the alls and such do something similar so it makes sense now.
I supposed I'll need so subdivide each triangle so that it fits into child nodes if it crosses a boundary. Does anyone have any good resources on how to accomplish this?
I supposed I'll need so subdivide each triangle so that it fits into child nodes if it crosses a boundary. Does anyone have any good resources on how to accomplish this?
I have never implemented an Octree, but it seems to me that CheckTriangle might be the problem. It requires that all vertices are strictly internal to the bounding box, so I believe all triangles lying along the children's bounding box walls will not find a home therein, and will instead be added to the root node by default.
Image this (in 2D):
triangle: (0, 0), (1, 0), (1, 1)
bounding rect: (0, 0) - (5, 5)
In believe the triangle should be within the rect, but using a 2D version of your algorithm, it would not be because they share a vertex.
As the space gets more partitioned, there is more "surface area" and thus more triangles get pushed into the root because they cannot be placed elsewhere.
Once again, I've never done it... so please smack me if I'm totally wrong. =p
Image this (in 2D):
triangle: (0, 0), (1, 0), (1, 1)
bounding rect: (0, 0) - (5, 5)
In believe the triangle should be within the rect, but using a 2D version of your algorithm, it would not be because they share a vertex.
As the space gets more partitioned, there is more "surface area" and thus more triangles get pushed into the root because they cannot be placed elsewhere.
Once again, I've never done it... so please smack me if I'm totally wrong. =p
Subdivision is best avoided, and there are two good alternatives. In both of these examples, triangles are not stored in nodes, but only in leaves.
1) Allow triangles to be referenced by more than one leaf. So for example, if a triangle crosses a plane, add it to both children rather then keeping it in that node. This does mean that naive traversal for rendering or collision detection may touch some triangles more than once. To fix that, just maintain a 'framecount' or 'testnumber' variable for each triangle to ensure that it is only touched once.
2) Use a loose octree, where you expand the bounds of each leaf by half the size of your largest object. Then, you can sort your triangles by their center only, and they will all only be referenced by one node.
Note that for the the first approach, you'll need a better tri/AABB test, i.e. one that uses a separating axis test to achieve exact results.
Anyway, there are quite a few details involved there, so ask if you have questions. Also, one of the first two GPG books has a decent article on loose octrees.
1) Allow triangles to be referenced by more than one leaf. So for example, if a triangle crosses a plane, add it to both children rather then keeping it in that node. This does mean that naive traversal for rendering or collision detection may touch some triangles more than once. To fix that, just maintain a 'framecount' or 'testnumber' variable for each triangle to ensure that it is only touched once.
2) Use a loose octree, where you expand the bounds of each leaf by half the size of your largest object. Then, you can sort your triangles by their center only, and they will all only be referenced by one node.
Note that for the the first approach, you'll need a better tri/AABB test, i.e. one that uses a separating axis test to achieve exact results.
Anyway, there are quite a few details involved there, so ask if you have questions. Also, one of the first two GPG books has a decent article on loose octrees.
For Octree, do you store a list of space partitioned triangles from the mesh into the nodes? So they are all static right?
Thanks in a advance,
Andy
Thanks in a advance,
Andy
Yes, each node keeps its own TRIANGLEs and then loads them into an index buffer.
Guys I have another question now. My OctTree is *mostly* rendering correctly. I'm now finding that with the dynamic list of triangles sorting by material has to be done on a per-frame basis. With upwards of 3000 triangles being sorted this slaughters my frametime. Does anyone have any advice on how to better render the dynamic list of triangles with proper material / texture?
Guys I have another question now. My OctTree is *mostly* rendering correctly. I'm now finding that with the dynamic list of triangles sorting by material has to be done on a per-frame basis. With upwards of 3000 triangles being sorted this slaughters my frametime. Does anyone have any advice on how to better render the dynamic list of triangles with proper material / texture?
Does anyone have any advice on how to better render the dynamic list of triangles with proper material / texture?
" you can create a texture group structure that counts the textures/materials, make sure to include a variable that trackes the last time when the textures are drawn "
" you can create a texture group structure that counts the textures/materials, make sure to include a variable that trackes the last time when the textures are drawn "
Topic Locked
This topic has been locked by a moderator. New replies are not allowed.
Sign in to reply to this topic.
Advertisement