each node will either contain vertices or 8 more nodes. I also have a structure which contains all the vertices I want to put in the octree where all the vertices are classes on their own and contain attributes such as position, normals and texcoords. The octree is set up where close vertices will be contained in the same node up to a maximum of 64 vertices where the node will be subdivided into 8 smaller parts. I am currently stumped on how to efficiently sort my data into it's respective nodes. Any suggestions?
Are you aware, that octree is a space-partitioning structure (opposed to object-partitioning), it cuts primitives (triangles) and therefore you might have to have all split triangles (or pointers to triangles) duplicated in all nodes that cut them? I'm assuming you want to cull triangle meshes. Triangles can then contain the vertex positions, normals and other attributes.
Anyway, you want to have a "list" (or a vector) of triangles in each leaf node. There are two principal possibilities to construct such structures - top-down and bottom-up. Top-down is easier, I believe and generally goes like this:
1. Compute scene AABB and allocate the root.
2. Push the root onto a queue.
3. Take out a node from the queue, if there is one, otherwise you're done.
4a If there are "many" primitives in it, allocate its 8 new subnodes, split primitives and push the new nodes onto the queue.
4b If there are " less than many" primitives in it, call the node a leaf.
5. Go to 3.
"Many" might be something in order of dozens to hundreds, possibly less, possibly more, heavily depending on the scene and many, many other factors. You will have to set this to some number beforehand.
A very simple (I do not claim extremely effective structure) might instead look like:
struct Triangle { vec3 pos[3]; vec3 normal[3]; ...}
struct OctreeNode { OctreeNode * kids[8]; vector<Triangle*> triangles; AABB box; void draw(); }
Just a quick question. What is the purpose of storing triangles/vertices in an octree?
best regards!
Frustum culling basically.
@ic0de: If you do not want to cut your triangles up then there is another way to build your octree, but your nodes in your oct tree will contain geometry and children both. Basically when you have triangles that can not be placed into child nodes, boundary condition geometry, that geometry will be added to the current node, and rendered. This is pretty horrid, but in practice it shouldn't be too much of a problem. So your draw routine would be something like:
void octTreeNode::Draw( const Frustum& _frustum ) {
// Only draw geometry if we have some, from when we created the oct tree and found some boundary intersecting triangles
if( mygeo ) {
mygeo->Draw();
}
// Frustum test and draw the subnodes
for( unsigned i = 0; i < 8; i++) {
if( _frustum.test( subnode ) == VISIBLE ) {
subnode.Draw();
}
}
}
I say Code! You say Build! Code! Build! Code! Build! Can I get a woop-woop? Woop! Woop!
The point of my question is that with modern GPU's culling geometry at that precision will probably have negative effect on the performance because a) to traverse such a tree takes CPU time b) drawing such small batches is inefficient / will result in numerous drawing calls c) can't handle instancing. Assuming of course that the structure is used with hardware renderer.
Better approach with GPUs is to store full objects in the octree and cull them in the mesh/object scale
kauna is definitely right with all three things. I would add that it might be worth considering implementing an object-partitioning structure such as BVH. It's quite as simple as octree and eliminates some problems (particularly splitting objects :-)).
Geometry is already culled on an object level but my terrain is one piece, should I just cut it into large chunks and not implement a full octree
This depends greatly on the type of terrain you have. If it is freeform and made in a modeler software, then you may not have other way than just split it as your describe.
If it is just a heightmap, then you have other options. Like, I treat my terrain as one object. The terrain is just a quad tree structure, but it doesn't contain any geometry. Instead, each node is split as long as the distance to camera is less than the node size (multiplied by some factor). So close to the camera I have more nodes and farther I have fewer nodes. Each node is drawn with a grid of 33x33 vertices, so this is practically a simple LOD-technique.
