Wednesday September 22, 2021
 home | about | contact | Donations
 The Maths of 3D You can't have 3D without a little maths...

Octrees and 3D Worlds

by bkenwright@xbdev.net

Well now...its one of those tutorials I had to write...yup..you can probably find loads and loads of tutorials out there already on the subject, so one more carn't harm.  Its only an outline of what an octree is and how you would code it with for example DirectX3D.  Again if you notice any errors in the code or have any feedback please feel free to email me any time....as I'm always open to criticism.

 Well in no way to scare you...but to demonstrate what a Octree would do to our 3D world...or 3D vertices...is divide them up into parts..  As what I've done here on the left it take a load of vertices, which makes up a 3D terrain, and apply an octree algorithm to it......of course I've turned on debugging...which basically draws the box's for the various octree nodes.  I must admit, when I first heard the word 'octree' and 'node' and subdivision...my face went pale....you can think of all nasty problems.... but stay with me and you'll soon see how easy it is.

So where should we start?...hmmm....well we don't want to get all messy and confused in the beginning...so first think is first....lets open a basic file and load in its data....so we have all our raw vertices...or triangles....you remember what they are...those x,y,z things.

Now we'll create a simple .raw file, which is just a raw set of xyz values...in order of triangles...so you read in the first 3 xyz values and you get a triangle...the next 3 xyz values give us the next triangle etc.....its the simplest format out there, and can typically be exported from 3D MilkShape.

Just to show what the data looks like in a .raw file, you can open it up in notepad...here is a snippet of it:

 -47.919212 -0.990297 47.910084 -45.841671 -1.437729 47.895947 -45.832878 -1.560482 45.789059 -45.832878 -1.560482 45.789059 -47.916328 -1.832262 45.819160 -47.919212 -0.990297 47.910084 -45.841671 -1.437729 47.895947.......

As you can see we have 3 values per line, and these are the x,y,z values.....3 lines per triangle face.

 /**********************************************************************************/ /*                                                                                */ /* File: main.cpp                                                                 */ /* Author: bkenwright@xbdev.net                                                   */ /* bkenwright@xbdev.net                                                           */ /* Desciption: Tutorial Prt-1- Loading in the vertices.                           */ /*                                                                                */ /**********************************************************************************/   #include #include   struct stVert {       float x,y,z; };   //////////////////////////////////////////////////////////////////////////////////// //                                                                                \\ // Now for our amazing little function that reads in all those vertices and       \\ // stores them in a buffer for use, so that we can use them.                      \\ //                                                                                \\ //\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\   void ReadVerticesFromFile() {       // Can't get any simpler than this, we open a file for reading.       FILE *fp = fopen("world.raw", "r");         // Just a temporary storage       stVert vTemp;       // We go through all the values in the file, once, and see how many of them there       // are, this is so we can see how much space we'll need to allocate etc....       // we could also do some file checking here etc.       int iNumVerts = 0;       while(1)       {             int result = fscanf(fp, "%f %f %f\n", &vTemp.x, &vTemp.y, &vTemp.z);               if(result == EOF)                   break;               iNumVerts++;       }         // Allocate memory for our data...as we know how many x,y,z value there are now.       stVert* pVertices = new stVert[iNumVerts];         // Seek back to the start of the file.       fseek(fp,0,SEEK_SET);         // Read the data in, using the fscanf function....x,y,z.       int ii = 0;       for(int i = 0; i < iNumVerts; i++)       {             fscanf(fp, "%f %f %f\n", &pVertices[ ii ].x,                                                  &pVertices[ ii ].y,                                                  &pVertices[ ii ].z);             ii++;       }       // Lets close up and where finished.       fclose(fp);         // Well for this code...where not using the vertices yet....thats for in a sec       // all our vertices are stored in the pVertices allocation we did...we can access       // them using pVertices[i].x pVertices[i].y ...etc etc....so lets tidy up and       // be a good coder for now...dont' want to use up windows memory do we..       delete[] pVertices; }         //////////////////////////////////////////////////////////////////////////////////// //                                                                                \\ // Our Application Entry Point                                                    \\ // This is the place it all begins...as they say....the start of our 1000 lines   \\ // of code...etc                                                                  \\ //                                                                                \\ //\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\     int WINAPI WinMain( HINSTANCE , HINSTANCE, LPSTR, INT ) {       // Call our function...read in the data, then exit for now.       ReadVerticesFromFile();         return 0; }

Well we can load or vertices in now...and the world.raw file in the example code above can be a massive file if we wanted it...millions of veritces..MegaBytes....and we wouldn't want to render or that 100 times a second or check through all of them in our collision detect every time we moved....so onto our next part.... we'll add in some basic DirectX3D code, and render our triangles shall we.....now don't get scared...I'll show you every step of the way what I'm doing and why I'm doing it.....

Now the important changes I'm going to make at this point I'm going to point out now...at the very start....I'll use the D3DXVECTOR3 structure of DirectX3D helper functions, its defined in D3dx8math.h, which is included in d3dx8.h...so you should only need to put "#include <d3dx8.h> at the top of your your file.

Its got the same data as our stVert structure above...and can be access in the same way....

The whole code and nothing but the whole code...Below shows the basic code which loads in the x,y,z vertices and also creates a window....I've cut out all the error checking code etc, and does the bare minimum...what it says on the tin!...and nothing more.  So what will happen if we run this baby up and see what it can do?...well you'll get a black screen and your 3D world.raw file will be rendered on the screen rotating!..... Now I put all the code below so you could go over it bit by bit...and see what makes up the whole thing.

 As I always say, a picture is worth a thousand words....and so on the right you can see a small screen shot of the 3D terrain when you run the above code.  Again it seems like so much code...but thats only because of the DirectX3D initialisation code and Windows Initialisation code etc.... and we havn't even got to the octree code yet...arrgggg.....  Well not to worrry...nearly 90% of the code for windows and DirectX3D is always included... the rest of our code will be added on from now on to build towards understanding the wondeful world of octrees.

So what we have is our few hundred vertices, and we're rendering them on the screen as they rotate.  Hmmm...not a bad effect if I say so myself....and where not even doing it efficently.

Now for our next coding exercise, where going to have to create our COctree class from scratch....and eventually we'll end up with a partitioned world :)

Of course we'll still use the code above, but we can pass in our vertices to our Octree, and it will divide them up for us....  But how?... Well be patient...where getting there.

 class COctree { public:       COctree(void){};       ~COctree(void){}; };

Taa-daa....our octree class is born!  Well its not much at the moment....in fact its just looks like an empty class.  But it will grow into a super cool piece of code.  And where going to watch it grow step by step :)

Now we've added in the main first parts of our octree code below, they are two member variables... m_iNumVertices and m_pVertices, which will keep our data count, and our data values.  So every time an instance of our class is created our member values will be set in the constructor.

But we will call Create(..) with our list of vertices and how many of them there are, and it will do the rest of the work for us.

 // This is declared at the top of main.cpp, and we'll want to use it here, to render // our trianges etc, so we put extern in front of it so the compiler knows its // declared somewhere else. extern IDirect3DDevice* g_pd3dDevice;   #include   class COctree { protected:       int            m_iNumVertices;  // The number of vertices in this Octree       D3DXVECTOR3    m_pVertices;     // Pointer to an array of vertices     public:       COctree(void)       {             m_iNumVertices = NULL;      // Set initial values in the constructor             m_pVertices    = NULL;      // Set the pointer to NULL       };       ~COctree(void){};   public:       // We call the Create member function with our vertices, to set, up our       // Octree...passing it the vital information it needs.       void Create( D3DXVECTOR3* pVertices, int iNumVertices )       {             m_iNumVertices = iNumVertices;       }       void Release()       {       } };

Now this is the point where the code could get pretty complicated if your not careful... so take this slowly and think about it....don't want you getting lost in the woods or more correctly the code.

Our octree code is going to use 'Recursion'...meaning it will call itself!  So it will create copies of itself, and pass data on down to itself.  So each node of itself, will contain 8 more octree classes, and each of them will contain 8....to a limit of course....depending on how far we want to split up our vertices.

An octree can be a node or a container....it can't be both.  If it contains vertices, then thats it, thats all it does.  On the other hand, if its a node it will have 8 COctree's...each possibly containing nodes or vertices.

We need to add a bit more code to our class now... to accommodate this feature:

D3DXVECTOR3 m_vCenter; // Center of our group of vertices

float m_fDiameter; // The diameter of our cube, which makes up our group of vertices....bounding box.

bool m_bAnyTriangels;  // If it contains any triangles...true for yes...false implies its a node, and has 8 further sub nodes in m_pOctreeNodes

COctree *m_pOctreeNodes[8];  // The 8 sub nodes

But theres more...how are we going to identify the various parts ....the front left, back left etc in our m_pOctreeNodes array... we could just say that 0 is for the Top Front Left, and 1 is for the Top Front Right etc...  but there's a nicer way to remember it...well it makes our code nicer anyhow...

enum OctreeParts
{
TOP_FRONT_LEFT,             // 0
TOP_FRONT_RIGHT,           // 1
TOP_BACK_LEFT,                // 2
TOP_BACK_RIGHT,             // 3
BOTTOM_FRONT_LEFT,     // 4
BOTTOM_FRONT_RIGHT,  // 5
BOTTOM_BACK_LEFT,      // 6
BOTTOM_BACK_RIGHT     // 7
};

Well there you have it....and now we add those few extra variable definitions to our class and where a step closer to our final solution

 class COctree { protected:       int            m_iNumVertices;    // The number of vertices in this Octree       D3DXVECTOR3    m_pVertices;       // Pointer to an array of vertices         D3DXVECTOR3    m_vCenter;         // Center of the 'Cube'       float          m_fDiameter;       // Diameter of our 'Cube'       bool           m_bAnyTriangels;   // Is it a node or an array of triangels (leaf)         COctree*       m_pOctreeNodes[8]; // Our 8 Sub-Nodes if bAnyTriangles is false   protected:       // Give each array reference number an easy to remember name :)       enum OctreeParts       {             TOP_FRONT_LEFT,       // 0             TOP_FRONT_RIGHT,      // 1             TOP_BACK_LEFT,        // 2             TOP_BACK_RIGHT,       // 3             BOTTOM_FRONT_LEFT,    // 4             BOTTOM_FRONT_RIGHT,   // 5             BOTTOM_BACK_LEFT,     // 6             BOTTOM_BACK_RIGHT     // 7       };   public:       COctree(void)       {             m_iNumVertices = NULL;      // Set initial values in the constructor             m_pVertices    = NULL;      // Set the pointer to NULL               m_vCenter      = D3DXVECTOR3(0,0,0); // Initial Center is 0,0,0             m_fDiameter    = 0;         // Initial diameter is 0                         ZeroMemory(m_pOctreeNodes, sizeof(m_pOctreeNodes)); // Set all the pointers to zero       };       ~COctree(void){};   public:       // We call the Create member function with our vertices, to set, up our       // Octree...passing it the vital information it needs.       void Create( D3DXVECTOR3* pVertices, int iNumVertices )       {             m_iNumVertices = iNumVertices;       }       void Release()       {       } };

Ooooo...its starting to look nice and efficient now isn't it, well it doesn't do much yet!.  But we've built a foundation out of stone.  We now have all our variables and have there intial values set in the constructor for us.  Now its time for us to add in the functions which will perform the octree division of our vertices...

Hmmm...so what functions could we possibly need?  Well for our first function, we'll need to calculate the center of our vertices, and the cubes diameter for them....so we'll create a SetData(..) function which will get that data from our vertices for us.

Now our two juicies function...these are at the heart of our code!  This is where the recursion and the subdivision take place, with our CreateNode(..) and CreateNodeEnd(..)

We also have to be careful with recussion...as we don't want to go to deep with our nodes.  So we'll add an external variable called g_iCurrentNodeLevel, which will increment each time we go down a level.

 DownloadCode / This is declared at the top of main.cpp, and we'll want to use it here, to render // our trianges etc at some point, so we can see where doing things right, // so we put extern in front of it so the compiler knows its // declared somewhere else. extern IDirect3DDevice8* g_pd3dDevice;   #include   // Used to keep track of how many levels we have gone down in our division. int g_iCurrentNodeLevel;   class COctree { protected:       int            m_iNumVertices;    // The number of vertices in this Octree       D3DXVECTOR3*   m_pVertices;       // Pointer to an array of vertices         D3DXVECTOR3    m_vCenter;         // Center of the 'Cube'       float          m_fDiameter;       // Diameter of our 'Cube'       bool           m_bAnyTriangles;   // Is it a node or an array of triangels (leaf)         COctree*       m_pOctreeNodes[8]; // Our 8 Sub-Nodes if bAnyTriangles is false   protected:       // Give each array reference number an easy to remember name :)       enum OctreeParts       {             TOP_FRONT_LEFT,       // 0             TOP_FRONT_RIGHT,      // 1             TOP_BACK_LEFT,        // 2             TOP_BACK_RIGHT,       // 3             BOTTOM_FRONT_LEFT,    // 4             BOTTOM_FRONT_RIGHT,   // 5             BOTTOM_BACK_LEFT,     // 6             BOTTOM_BACK_RIGHT     // 7       };   public:       COctree(void)       {             m_iNumVertices = NULL;      // Set initial values in the constructor             m_pVertices    = NULL;      // Set the pointer to NULL               m_vCenter      = D3DXVECTOR3(0,0,0); // Initial Center is 0,0,0             m_fDiameter    = 0;         // Initial diameter is 0                         ZeroMemory(m_pOctreeNodes, sizeof(m_pOctreeNodes)); // Set all the pointers to zero       };       ~COctree(void){};   public:       // We call the Create member function with our vertices, to set, up our       // Octree...passing it the vital information it needs.       void Create( D3DXVECTOR3* pVertices, int iNumVertices )       {             m_iNumVertices = iNumVertices;               // Call our Set Data function to itterate through or vertex's and get the diameter             // and center.             SetData(pVertices, iNumVertices);               // We have to start the recursion somewhere, so we start it here, and call             // it with our data.             CreateNode(pVertices, iNumVertices, m_vCenter, m_fDiameter);       }       void Release()       {             // Most tidy up functions are the same, if its not zero, then its got             // data in it...             if(m_pVertices)             {                   delete[] m_pVertices;                   m_pVertices = NULL;             }             // As each node is an octree, and it contains a pointer to 8 sub nodes, we should             // check if any of them are not NULL and again call there member function 'Release(..)'             for(int i=0; i<8; i++)             {                   if( m_pOctreeNodes[i] )                   {                         m_pOctreeNodes[i]->Release();                         m_pOctreeNodes[i] = NULL;                   }             }       }         // Now for our main functions, which will do the recursion, and Octree Generation! protected:       // Mini helper function       float abs_f(float f)       {             if( f<0 ) return -f;             return f;       }       // This little function, is very simple, but it looks long...but its purpose is to       // get the center point of our vertices, and the its diameter.       void SetData(D3DXVECTOR3* pVertices, int iNumVertices)       {             // Simple check, if we have NULL's then we return.             if( (pVertices==NULL) || (iNumVertices<=0)) return;               //<1> Lets find the center             for(int i=0; i Now lets find the diameter             for(int i=0; i fWidthMax )  fWidthMax=fWidth;                   if( fHeight > fHeightMax)  fHeightMax=fHeight;                   if( fDepth  > fDepthMax)   fDepthMax=fDepth;             }                         // Now fWidthMax, fHeightMax and not forgetting fDepthMax             // contain the largest radius's...not diameter..so we'll             // fix that now.             fWidthMax  *= 2;             fHeightMax *= 2;             fDepthMax  *= 2;               // Lets find out which is the largest...and will be our             // cubes diameter.             m_fDiameter = fWidthMax;             if( fHeightMax > m_fDiameter ) m_fDiameter=fHeightMax;             if( fDepthMax  > m_fDiameter ) m_fDiameter=fDepthMax;       }         // This function gets called if we need to go a node deeper, it checks if we've reached a       // depth limit, or if we have a certain number of triangles for that nodes, else it divide's up       // the node and goes deeper.       void CreateNode(D3DXVECTOR3* pVertices, int iNumVertices, D3DXVECTOR3 vCenter, float fDiameter)       {                         m_vCenter = vCenter;               int iNumTriangles = iNumVertices/3;               m_fDiameter = fDiameter;               // Try changing this line, from 1, to 2 to 3 etc...see what results you get.             int iMaxNodes = 3;         //     /|\             //      +------------- 1-> 8 sub division             //      |             //      +------------- 2-> Each node is further sub divided into another 8                 // We need a minimum number of triangles for it to be subdivided...no use dividing up             // 3 triangles as a silly example...well we can set the number here.             int iMinNumTriangles = 150;                         if( (iNumTriangles < iMinNumTriangles) || ( g_iCurrentNodeLevel >= iMaxNodes) )             {                   SetNode(pVertices, iNumVertices);                     m_bAnyTriangles = true;                               }             else             {                   //g_iCurrentNodeLevel++;                     m_bAnyTriangles = false;                     bool* pBoolArray1 = new bool[iNumTriangles];                   bool* pBoolArray2 = new bool[iNumTriangles];                   bool* pBoolArray3 = new bool[iNumTriangles];                   bool* pBoolArray4 = new bool[iNumTriangles];                   bool* pBoolArray5 = new bool[iNumTriangles];                   bool* pBoolArray6 = new bool[iNumTriangles];                   bool* pBoolArray7 = new bool[iNumTriangles];                   bool* pBoolArray8 = new bool[iNumTriangles];                                     ZeroMemory(pBoolArray1, iNumTriangles);                   ZeroMemory(pBoolArray2, iNumTriangles);                   ZeroMemory(pBoolArray3, iNumTriangles);                   ZeroMemory(pBoolArray4, iNumTriangles);                   ZeroMemory(pBoolArray5, iNumTriangles);                   ZeroMemory(pBoolArray6, iNumTriangles);                   ZeroMemory(pBoolArray7, iNumTriangles);                   ZeroMemory(pBoolArray8, iNumTriangles);                     D3DXVECTOR3 vCtr = vCenter;                                     // Loop through all our vertices, and allocate to the appropriate                   // cube area.                   for(int i=0; i< iNumVertices; i++)                   {                         D3DXVECTOR3 vPoint = pVertices[i];                                                 // TOP_FRONT_LEFT                         if( (vPoint.y >= vCtr.y) && (vPoint.x <= vCtr.x) && (vPoint.z >= vCtr.z) )                               pBoolArray1[i/3] = true;                         // TOP_FRONT_RIGHT                         if( (vPoint.y >= vCtr.y) && (vPoint.x >= vCtr.x) && (vPoint.z >= vCtr.z) )                               pBoolArray2[i/3] = true;                         // TOP_BACK_LEFT                         if( (vPoint.y >= vCtr.y) && (vPoint.x <= vCtr.x) && (vPoint.z <= vCtr.z) )                               pBoolArray3[i/3] = true;                         // TOP_BACK_RIGHT                         if( (vPoint.y >= vCtr.y) && (vPoint.x >= vCtr.x) && (vPoint.z <= vCtr.z) )                               pBoolArray4[i/3] = true;                           // BOTTOM_FRONT_LEFT                         if( (vPoint.y <= vCtr.y) && (vPoint.x <= vCtr.x) && (vPoint.z >= vCtr.z) )                               pBoolArray5[i/3] = true;                         // BOTTOM_FRONT_RIGHT                         if( (vPoint.y <= vCtr.y) && (vPoint.x >= vCtr.x) && (vPoint.z >= vCtr.z) )                               pBoolArray6[i/3] = true;                         // BOTTOM_BACK_LEFT                         if( (vPoint.y <= vCtr.y) && (vPoint.x <= vCtr.x) && (vPoint.z <= vCtr.z) )                               pBoolArray7[i/3] = true;                         // BOTTOM_BACK_RIGHT                         if( (vPoint.y <= vCtr.y) && (vPoint.x >= vCtr.x) && (vPoint.z <= vCtr.z) )                               pBoolArray8[i/3] = true;                   }                   // Shall we see how many triangles is in each space partition node?                   int iCount1 = 0;        int iCount5 = 0;                   int iCount2 = 0;        int iCount6 = 0;                   int iCount3 = 0;        int iCount7 = 0;                   int iCount4 = 0;        int iCount8 = 0;                     for(int i=0; iCreateNode(pNodeVerts, iTriangles*3, vNewCenter, fDiameter/2);               g_iCurrentNodeLevel--;               delete[] pNodeVerts;       }         // Helper funtion which calcuates the center of the new node, based upon its parent       // node.       D3DXVECTOR3 GetNodeCenter(D3DXVECTOR3 vCurrentCenter, float fDiameter, int iWhichNode)       {                         D3DXVECTOR3 vCtr = vCurrentCenter;             D3DXVECTOR3 vNewCtr = D3DXVECTOR3(0.0f, 0.0f, 0.0f);             float fDia = fDiameter;               switch( iWhichNode )             {             case TOP_FRONT_LEFT:      // 0                   vNewCtr = D3DXVECTOR3( vCtr.x - fDia/4, vCtr.y + fDia/4, vCtr.z + fDia/4 );                   break;             case TOP_FRONT_RIGHT:     // 1                   vNewCtr = D3DXVECTOR3( vCtr.x + fDia/4, vCtr.y + fDia/4, vCtr.z + fDia/4 );                   break;             case TOP_BACK_LEFT:       // 2                   vNewCtr = D3DXVECTOR3( vCtr.x - fDia/4, vCtr.y + fDia/4, vCtr.z - fDia/4 );                   break;             case TOP_BACK_RIGHT:      // 3                   vNewCtr = D3DXVECTOR3( vCtr.x + fDia/4, vCtr.y + fDia/4, vCtr.z - fDia/4 );                   break;             case BOTTOM_FRONT_LEFT:   // 4                   vNewCtr = D3DXVECTOR3( vCtr.x - fDia/4, vCtr.y - fDia/4, vCtr.z + fDia/4 );                   break;             case BOTTOM_FRONT_RIGHT:  // 5                   vNewCtr = D3DXVECTOR3( vCtr.x + fDia/4, vCtr.y - fDia/4, vCtr.z + fDia/4 );                   break;             case BOTTOM_BACK_LEFT:    // 6                   vNewCtr = D3DXVECTOR3( vCtr.x - fDia/4, vCtr.y - fDia/4, vCtr.z - fDia/4 );                   break;             case BOTTOM_BACK_RIGHT:   // 7                   vNewCtr = D3DXVECTOR3( vCtr.x + fDia/4, vCtr.y - fDia/4, vCtr.z - fDia/4 );                   break;             }               return vNewCtr;       }         // This little function is called when a node has reached its end...and the vertices       // are placed into its vertices pointer...and the m_bAnyTriangles boolean member       // is set to true.       // Think of it like this, this is where a node comes to die...when its reached its limits       // it comes here to be 'set' in stone...filled with vertices and a vertices count, a diameter etc.       void SetNode(D3DXVECTOR3* pVertices, int iNumVertices)       {             m_bAnyTriangles = true;               m_iNumVertices  = iNumVertices;               m_pVertices = new D3DXVECTOR3[iNumVertices];             ZeroMemory(m_pVertices, sizeof(D3DXVECTOR3)*m_iNumVertices);               memcpy(m_pVertices, pVertices, sizeof(D3DXVECTOR3)*iNumVertices);       }   public:       // I put this member function in here, so we could render our 3D world, and       // see the actual cubes.  I've passed in a parent node, which would be the       // global instance of it that we called at the start with Create(..).  Of course       // we could just keep a member variable that would point to the head, then we could       // just call Render() and call this function with our head.  Not letting our       // outside world know how it works.       // Of couse you could use this for debugging...pass in different nodes...and       // only see where they are...and what they look like etc.       void RenderOctree(COctree* pNode)       {             if( pNode == NULL ) return;               if( pNode->m_bAnyTriangles )             {                   if(pNode->m_pVertices == NULL) return;                     int iNumTriangles = pNode->m_iNumVertices/3;                                     float fDiameter = pNode->m_fDiameter;                                       D3DXVECTOR3 vMin = pNode->m_vCenter;                   vMin.x -= fDiameter/2.0f;                   vMin.y -= fDiameter/2.0f;                   vMin.z -= fDiameter/2.0f;                     D3DXVECTOR3 vMax = pNode->m_vCenter;                   vMax.x += fDiameter/2.0f;                   vMax.y += fDiameter/2.0f;                   vMax.z += fDiameter/2.0f;                     // This 'wire_cube' function is in graphics_helpers.cpp/.h and draws a cube                   // wire frame so we can see the subdivisions of our work!..our octree parts                   // again its only here for testing, in your final versin you would exclude                   // this.                   // DEBUG DEBUG DEBUG DEBUG DEBUG DEBUG DEBUG DEBUG DEBUG                   wire_cube(g_pd3dDevice, (float*)&vMin, (float*)&vMax);                     for(int i=0; im_pVertices[i];                         D3DXVECTOR3 p2 = pNode->m_pVertices[i+1];                         D3DXVECTOR3 p3 = pNode->m_pVertices[i+2];                           // Well we at this step, we have all the points of a triangle...so I did a                         // simple triangle drawing function, and put it in graphics_helpers.h/cpp...                         // is an invaluable tool when debugging testing octree's.                           // DEBUG DEBUG DEBUG DEBUG DEBUG DEBUG DEBUG DEBUG DEBUG                         triangle(g_pd3dDevice, (float*)&p1, (float*)&p2, (float*)& p3);                   }             }             else             {                   // We go on to call the nested nodes                   RenderOctree(pNode->m_pOctreeNodes[TOP_FRONT_LEFT]);                   RenderOctree(pNode->m_pOctreeNodes[TOP_FRONT_RIGHT]);                   RenderOctree(pNode->m_pOctreeNodes[TOP_BACK_LEFT]);                   RenderOctree(pNode->m_pOctreeNodes[TOP_BACK_RIGHT]);                     RenderOctree(pNode->m_pOctreeNodes[BOTTOM_FRONT_LEFT]);                   RenderOctree(pNode->m_pOctreeNodes[BOTTOM_FRONT_RIGHT]);                   RenderOctree(pNode->m_pOctreeNodes[BOTTOM_BACK_LEFT]);                   RenderOctree(pNode->m_pOctreeNodes[BOTTOM_BACK_RIGHT]);             }       } };// End of our Octree Class.

Now for a perfect DirectX3D COctree class we would need to optimise a few things, now instead of storing just vertices, we need to take colour into account...and textures...then save this information.  And create our VertexBuffer's as we progress through our Octree.

DirectX3D Optimised Version....comming soon..

 Visitor: 9534626 { 229.27.38.75 } Copyright (c) 2002-2020 xbdev.net - All rights reserved. Designated articles, tutorials and software are the property of their respective owners.