   Direct3D Octree
  Hi all,Coul anyoe give me some help on how to implent an ocree in direct3d. I''ve loaded a .x mesh and tried extracting the vertex buffer. I''m not sure were to go from here. Ive seen posts on here having many index buffers. I''m not sure on how to get many indexbuffers from 1 .x file. Please could someoe point me in the right direction, as ive been wrking on it for a cople of days now with no joy. Sry bit of a noob whe it comes to D3D.Thax alot o anyone an help!!Psyian 
  Well, Here''s one way to do it.  The first thing you need to do is construct the Octree.  You''ll need to lock both the index buffer and the vertex buffer that you get from your .x file so that you can access the individual vertices.Once you access the vertices, you can determine where in your Octree structure each triangle belongs.  Instead of storing the actual triangle vertices in the nodes of your Octree, you can store the indices into the model''s vertex buffer.  These indicies can be stored in a standard array (i.e. not a IDirect3DIndexBuffer object).When you go to render the scene, you traverse your Octree to determine which triangles you want to render.  The first thing you do is you create one dynamic index buffer (this can be done at initialization).  During each frame, when you figure out that you need to render the triangles in a particular node of your Octree, you take the indices that are stored in this node and copy them into your dynamic index buffer.Once you''ve copied the indices to all the triangles you need (could be from multiple nodes in your Octree) you call SetIndices with your dynamic index buffer, call SetStreamData with the one vertex buffer from your .x file, and finally call DrawIndexedPrimitve to render all the geometry.Of course, this assumes that there are no texture changes for the different parts of the .x model and such but you get the idea.There are many articles here on GameDev about constructing Octrees in general.  Even though they aren''t D3D specific, they don''t have to be.  The concepts are all identical.  The only thing you need to worry about is how to access the vertices from your .x file, which it seems that you''ve already done.Hope this helps,neneboricua ;  Thanx for responding dude!I understand you need the vertex and index data to find out what to render, but i cant figure out how to access the vertices/indices and their data this from the vertex/index buffer. I''ve tryed the SDK docs(!!) and the net, but no joy.I see you have to copy it from memory, but not sure on how, and how to extract the data.Don''t spose you could elaberate a bit?Thanx ;quote:Original post by Psyian  I see you have to copy it from memory, but not sure on how, and how to extract the data.Don''t spose you could elaberate a bit?Ok.  This question has been answered before in this forum.  You can try to do a search for "accessing vertex buffer" or something like that and it should come up with some info.The idea is that you have to lock both the index and vertex buffers so that you can access the individual vertices.  The idea is basically the same as if you were creating a vertex buffer and sticking a triangle into it.The main problem that you run into with models is that you don''t always know what kind of information is stored in the vertices.  For example, the model could contain vertex blending weights or some other type of data.However, your engine probably expects all data to be in a limited number of formats.  So what you do is you clone the mesh so that its vertices contain the information you want.  This is what you do:Load your .x file with D3DXLoadMeshFromXCall ID3DXMesh::CloneMesh or ID3DXMesh::CloneMeshFVF on this mesh to create a copy of the mesh that contains only the data you want it to contain.The docs say the following about this function: "ID3DXBaseMesh::CloneMeshFVF is used to reformat and change the vertex data layout. This is done by creating a new mesh object. For example, use it to to add space for normals, texture coordinates, colors, weights, etc. that were not present before."You have to pass CloneMesh{FVF} data that describes the format you want the model to be in.  For example, let''s say you want your mesh to have this vertex structure and FVF:struct VERTEX{  D3DXVECTOR3 vPosition;  D3DXVECTOR3 vNormal;  FLOAT tu, tv;};const DWORD D3DFVF_VERTEX = D3DFVF_XYZ | D3DFVF_NORMAL | D3DFVF_TEX1;  Your call to CloneMeshFVF could look like this:LPD3DXMESH pNewMesh = NULL;pMesh->CloneMeshFVF( D3DXMESH_MANAGED, D3DFVF_VERTEX, m_pd3dDevice, &pNewMesh );SAFE_RELEASE( pMesh );pMesh = pNewMesh;pNewMesh = NULL;Then to access the elements of your vertex buffer, you would do this (I left out error checking for simplicity): VERTEX *pVertices = NULL;WORD* pIndices = NULL;pMesh->LockVertexBuffer(D3DLOCK_READONLY, (VOID**)&pVertices);pMesh->LockIndexBuffer(D3DLOCK_READONLY, (VOID**)&pIndices);// To access the position of the first triangle...pVertices[pIndices[0]].vPosition;pVertices[pIndices[1]].vPosition;pVertices[pIndices[2]].vPosition;// To loop through all the triangles in your model....for( DWORD i = 0; i < pMesh->GetNumFaces(); i++ ){  D3DXVECTOR3 v0 = pVertices[pIndices[i*3+0]].vPosition;  D3DXVECTOR3 v1 = pVertices[pIndices[i*3+1]].vPosition;  D3DXVECTOR3 v2 = pVertices[pIndices[i*3+2]].vPosition;}// don''t forget to unlock your vertex and index buffers when you''re donepMesh->UnlockVertexBuffer();pMesh->UnlockIndexBuffer();Hope this helps,neneboricua ;  ahhhahhahahahah!!!I see now, i didn''t even think of needing to copy the mesh. Thats made me feel alot better now!! ThanxWhy does D3D have to be so.. complicated, i swear OGL wasnt this hard!!Oh, will this cause performance to drop in anyway, alot of posts say that locking/unlocking buffers reduces performance. Would there be a better way to implement an octree from a .x file, probably wouldn''t use .x heh???Thanx again for your help dude, should be back on track now!!!!Laters ;  You should only clip an object ot an octree if it''s a static object - like terrain.  Otherwise, use bounding spheres and boxes to check if an object is visible by clipping them to the view frustum - like rts units. ;  neneboricua19 and what about texture sorting?You talked about having only one dynamic vertex/index buffer where you put the vertices that are currently seen in each frame. But if you have lots of different textures?? The main problem is using DrawPrimetive as few as you can...   [edited by - helius on February 12, 2004 10:43:43 AM];quote:Original post by Helius  neneboricua19 and what about texture sorting?You talked about having only one dynamic vertex/index buffer where you put the vertices that are currently seen in each frame. But if you have lots of different textures?? The main problem is using DrawPrimetive as few as you can...   [edited by - helius on February 12, 2004 10:43:43 AM] Yes, that''s why my original post had this in itquote:Of course, this assumes that there are no texture changes for the different parts of the .x model and such but you get the idea.I didn''t want to make it more complicated than it had to be.  Since i didn''t know if the .x file he was talking about was a huge landscape or a small character, I couldn''t really assume how the .x model was built.  Also, since .x files do not support multiple texture coordinates by default, I thought it was safe to assume only one texture quote:Original post by Psyian  Why does D3D have to be so.. complicated, i swear OGL wasnt this hard!!Oh, will this cause performance to drop in anyway, alot of posts say that locking/unlocking buffers reduces performance. Would there be a better way to implement an octree from a .x file, probably wouldn''t use .x heh???OpenGL has a similar idea.  I think that the ARB_Vertex_Buffer does the same thing as the IDirect3DVertexBuffer.  They both place vertex data in video memory.  The problem is that since it''s in video memory, accessing it requires you to do some special steps.  You may be thinking that in OGL you just had to do something like:glBegin(GL_TRIANGLE);glVertex3f(...);glVertex3f(...);glVertex3f(...);glVertex3f(...);glVertex3f(...);glVertex3f(...);glEnd();And you''re right.  The problem is that this is the slowest method to render anything in OpenGL.  It''s good for prototyping something but I doubt you''ll actually see this used much in production code since vertex arrays and vertex buffer objects are so much faster.As far as a performance drop, yes, there is a performance drop when you lock/unlock data in video memory.  However, that''s why the sample code I wrote before created a copy of the mesh in MANAGED memory.  This creates a copy in both video and system memory.  So when you lock that mesh and specify that you''re only going to read from it, D3D will give you access to the copy of the mesh in system memory because it is much faster.But in general, you should try to avoid Lock/Unlock''ing something as much as possible.  Ideally, it should only be done during initialization.Hope this helps,neneboricua ;  HahaNo u were right to keep it simple dude. I am a noob. Its just a simple landscape i made in 3d max, with 1 texture. I''ve done a load since your post. Thanx alot you really did make it clear, very helpful!!At the moment im tryin to find the bounds of the mesh and the center point, proving tricky, keep coming out with weird values. I''m also trying to draw lines to outline the octree (well the 1st node), but they''re not working properly (hard to see).Well anyway thanx for u''re help, i''ll keep at it!!Laters;quote:Original post by Psyian    At the moment im tryin to find the bounds of the mesh and the center point, proving tricky, keep coming out with weird values. I'm also trying to draw lines to outline the octree (well the 1st node), but they're not working properly (hard to see).As far as bounds and a center point, you could use D3DXComputeBoundingBox.You would use it something like this: VERTEX* pVertices = NULL;pMesh->LockVertexBuffer(D3DLOCK_READONLY, (VOID**)&pVertices);D3DXVECTOR3 vMin, vMax;D3DXComputeBoundingBox(pVertices, pMesh->GetNumVertices(), pMesh->GetNumBytesPerVertex(), &vMin, &vMax);pMesh->Unlock();D3DXVECTOR3 vCenter = (vMin+vMax)/2.0f;Also, remember that an Octree might be a bit of overkill if the only thing you're using it for is your terrain.  A quadtree (the 2D version of an Octree) might be a better fit.  But if you're planning on using the Octree for terrain as well as other things, then it should be ok.neneboricua   [edited by - neneboricua19 on February 12, 2004 4:27:56 PM]