# Octree Implementation in DX

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

## Recommended Posts

can anyone provide me links or ideas on how to implement Octree in DX.. most of the tutorials I found on the net focuses on OGL.. I plan to load my scene from a Mesh .X file thanks in advance

##### Share on other sites
First of all you should understand that an octree is simply a data structure - it has nothing to do with either DX or OpenGL. Find some tutorials on the net that explains what a quadtree/octree really is. Once you know what the data structure does you can start thinking about how you'll extract the geometric information from the type of level/model/mesh you're using in your application.

- Kasper

##### Share on other sites
thnks for the reply ..yeah i knw wat an octree is i just wat to know how to implement it using .X MEsh in DX? :)

Anyone?

##### Share on other sites
Like Kasper said, often times you won't find EXACT code on the internet that you can just copy-and-paste into your application. The concept of an Octree is well-defined. It is general algorithm that does not depend on the particular API being used to implement it.

Read the tutorials and whitepapers on Octrees and think about how to implement it using D3D. If you truely understand the concept of the Octree to the point where you can write detailed pseudocode for it, implementing that pseudocode should not be too much trouble.

An Octree is a pretty advanced data structure. If you really want to use the ID3DXMesh interface for your rendering, make sure that you understand how to build this mesh from just a vertex and index buffer first before you try to build an Octree.

neneboricua

##### Share on other sites

HI there,

The way i did mine was to load your .x mesh, then strip out the indices into an array. You can keep your vertices in 1 static vertex buffer for speed. As you traverse your octree, subdividing as you go. You look at which tris lie in particular nodes. If you are not at the level of subdivision u want (say 250 - 500 tris) you subdivide again. And so on until u reach your limit. With each subdivision i only parsed the indices i needed to the lower levels, so each end node only has the index data the lies in them. Although, this is not strictly the case, see below. Once you've finished you can now render. you traverse you nodes, and gather all your index arrays, put them into 1 single array. Lock your index buffer and fill it. Now render.

Other points to consider:

1) Your triangles won't always fit neatly into each node. You have 2 options, either you can split triangles (but you have to carefull, you don't want to make too many). Or what i opted for was to check if a trinagle lies in two nodes, then place the indices in both, and render it twice. Although this is not good practice (in my opinion!) the overdraw should not be significant.

2) Multiple materials/textures - I solved this little doobie by seperating the indices for each material. You can do this when you clone your mesh with adjacent data (i think, can't quite remeber). Then create an index array for each material. You just have to collect you index data into different arrays when you render, when you fill your IB, do so by grouping the materials together, then when you render you can keep the material state changes and DIP calls to the minimum.

I found mine reasonably slow, i think because of the traversal, locking and the dynamic index buffer, actually thinking about it my VB was dynamic (shit!). A possibility is to keep static index buffers for each node & material, i believe index buffer state changes are reasonably (hmmm!) minimal. I spoke to a friend of mine who works for a game studios and he mentioned ROAM (Real-time optimally adapting meshes) a form of terrain LOD. So i've started looking into that, but i've had to re-design & build my engine (as i have done many a time), creating resource managers. I will get back to it, even so that can use an octree/quadtree.

Anyhow, ill stop my ramblings, hope this helps.

Laters

##### Share on other sites
Flipcode has information regarding this I belive.

##### Share on other sites
k thanks
one last thing
Do i need to EXtract ALL vertices/indices for ALL OBJECTS(Frame) found in my mesh?
or maybe i can just used static d3dMESH for my scene?

##### Share on other sites
where to find docs/whitepaper that describes the implementation?

##### Share on other sites

You need to extract the index and vertex data to be able to determine where your triangles lie in the structure. This is provided it is one mesh with only different subsets (material groups). Not sure on the old FRAME stuff, If an object is animatable i would be inclined to give it a bounding volume and keep a reference to it in a node, then when you traverse the list if the nodes visible so's the sub object (you could possibly extend this to subdivide the sub-object, using an octree or hierarchical sphere data structure). This depnds on how big it is. I haven't looked into that bit, just some ideas.

What kind of model is it?

As for docs and whitepapers, i had none, just used this forum, and some brain work.

Just have a go, test, modify and re-test. "Aint learning fun!"

Laters

1. 1
2. 2
Rutin
19
3. 3
khawk
18
4. 4
5. 5

• 9
• 12
• 16
• 26
• 10
• ### Forum Statistics

• Total Topics
633769
• Total Posts
3013759
×