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.

.......

/**********************************************************************************/

/*                                                                                */

/* File: main.cpp                                                                 */

/* Author: bkenwright@xbdev.net                                                   */

/* bkenwright@xbdev.net                                                           */

/* Desciption: Tutorial Prt-1- Loading in the vertices.                           */

/*                                                                                */

/**********************************************************************************/

#include <windows.h>

#include <stdio.h>

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;

}

/**********************************************************************************/

/*                                                                                */

/* File: main.cpp                                                                 */

/* Author: bkenwright@xbdev.net                                                   */

/* bkenwright@xbdev.net                                                           */

/* Desciption: Tutorial Prt-2- Using DirectX3D to proove our triangles exist!     */

/*                                                                                */

/**********************************************************************************/

#include <windows.h>

#include <stdio.h>

#pragma comment(lib, "D3d8.lib") //directX 8

#pragma comment(lib, "D3dx8.lib")

#include <d3dx8.h>

////////////////////////////////////////////////////////////////////////////////////

//                                                                                \\

// Global variables                                                               \\

//                                                                                \\

//\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\

// These are our DirectX3D global variables.

LPDIRECT3D8             g_pD3D           = NULL; // Used to create the D3DDevice

LPDIRECT3DDEVICE8       g_pd3dDevice     = NULL; // Our rendering device

// These two variables holds our number of vertices and our vertice xyz values.

int          g_iNumVerts = 0;

D3DXVECTOR3* g_pVertices = NULL;

////////////////////////////////////////////////////////////////////////////////////

//                                                                                \\

// 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()

{     // Open our file for reading

      FILE *fp = fopen("world.raw", "r");

      // This is a structure of 3 floats, x,y,z

      D3DXVECTOR3 vTemp;

      // Read in all the data, and count how many vertices there are so we can now how

      // much memory we are going to need to allocate.

      while(1)

      {

            int result = fscanf(fp, "%f %f %f\n", &vTemp.x, &vTemp.y, &vTemp.z);

            if(result == EOF)

                  break;

            // Keep count of the number of vertices in our global int, which is declared

            // at the top of the file, as a global integer.

            g_iNumVerts++;

      }

      // Allocate memory for our vertices, note to delete this allocated memory before

      // exiting the program...else you'll get memory leaks.

      g_pVertices = new D3DXVECTOR3[g_iNumVerts];

      // Seek to the start of the file, so we can read in all the vertices.

      fseek(fp,0,SEEK_SET);

      int ii = 0;

      for(int i = 0; i < g_iNumVerts; i++)

      {

            fscanf(fp, "%f %f %f\n", &g_pVertices[ ii ].x,

                                                 &g_pVertices[ ii ].y,

                                                 &g_pVertices[ ii ].z);

            ii++;

      }

      // Lets close the file and exit!

      fclose(fp);

}

////////////////////////////////////////////////////////////////////////////////////

//                                                                                \\

// DirectX3D - Used to settup our DirectX3D world ...sets up the min/max range,   \\

// camera's position etc. ( world, view, and projection transform matrices.)      \\                                          \\

//                                                                                \\

//\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\

void SetupWorldMatrices()

{

    // For our world matrix, we will just leave it as the identity

    D3DXMATRIX matWorld;

      // Just stuck in these few lines of code so our 3D object rotates..make sure its

      // not crashes and let us see all the way around it.

      static float y_rot = 0.0f;

      y_rot += 0.005f;

      D3DXMatrixRotationY(&matWorld, y_rot);

    g_pd3dDevice->SetTransform( D3DTS_WORLD, &matWorld );

    D3DXMATRIX matView;

    D3DXMatrixLookAtLH( &matView, &D3DXVECTOR3( 0.0f, 1.0f,-80.0f ),

                                  &D3DXVECTOR3( 0.0f, 0.0f, 0.0f ),

                                  &D3DXVECTOR3( 0.0f, 1.0f, 0.0f ) );

    g_pd3dDevice->SetTransform( D3DTS_VIEW, &matView );

    D3DXMATRIX matProj;

    D3DXMatrixPerspectiveFovLH( &matProj, D3DX_PI/2, 1.0f, 1.0f, 1000.0f );

    g_pd3dDevice->SetTransform( D3DTS_PROJECTION, &matProj );

}

////////////////////////////////////////////////////////////////////////////////////

//                                                                                \\

// This little function is called over and over again, and does the rendering of  \\

// our triangles...or thousands and thousands of triangles...its called many      \\

// times a second.                                                                \\

//                                                                                \\

//\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\

void Render()

{

      if(!g_pd3dDevice)return;

    // Setup the world, view, and projection matrices

    SetupWorldMatrices();

      struct my_vertex

      {

            FLOAT x, y, z;  // D3DFVF_XYZ

      };

      UINT my_vertex_format = D3DFVF_XYZ ;

      IDirect3DVertexBuffer8 * pVertexBuffer;

      g_pd3dDevice->CreateVertexBuffer( g_iNumVerts*sizeof(my_vertex), 0,

                                    my_vertex_format, D3DPOOL_MANAGED, &pVertexBuffer );

      unsigned char *p;

    pVertexBuffer->Lock(0,0, &p, 0);

    memcpy(p, g_pVertices, g_iNumVerts*sizeof(my_vertex) );

    pVertexBuffer->Unlock();

      //Turn off lighting becuase we are specifying that our vertices have colour

    g_pd3dDevice->SetRenderState(D3DRS_LIGHTING, FALSE);

    g_pd3dDevice->SetTextureStageState(0, D3DTSS_COLOROP, D3DTOP_SELECTARG1);

    g_pd3dDevice->SetTextureStageState(0,D3DTSS_COLORARG1, D3DTA_DIFFUSE);

      // Clear the backbuffer and the zbuffer

    g_pd3dDevice->Clear( 0, NULL, D3DCLEAR_TARGET|D3DCLEAR_ZBUFFER,

                                            D3DCOLOR_XRGB(0x00,0x00,0x00), 1.0f, 0 );

      // Draw our triangle.

    g_pd3dDevice->SetStreamSource(0, pVertexBuffer, sizeof(my_vertex));

    g_pd3dDevice->SetVertexShader(my_vertex_format);

    //g_pd3dDevice->DrawPrimitive(D3DPT_TRIANGLELIST, 0, g_iNumVerts/3);

      g_pd3dDevice->DrawPrimitive(D3DPT_POINTLIST, 0, g_iNumVerts);

      // End the scene

    g_pd3dDevice->EndScene();

    // Present the backbuffer contents to the display

    g_pd3dDevice->Present( NULL, NULL, NULL, NULL );

      pVertexBuffer->Release();

}

////////////////////////////////////////////////////////////////////////////////////

//                                                                                \\

//  InitD3D is called once at the start of our program, and CleanUpDX is called   \\

//  once at the end of the program before closing.                                \\

//                                                                                \\

////////////////////////////////////////////////////////////////////////////////////

// Delete any allocated memory etc here.

void Cleanup()

{

      // Now notice how I've deleted the allocated memory before exiting!

      delete[] g_pVertices;

      // Release DirectX3D resources.

      g_pd3dDevice->Release();

      g_pD3D->Release();

}

// Initializes Direct3DX at the start.

bool InitD3D(HWND hwnd)

{

    g_pD3D = Direct3DCreate8( D3D_SDK_VERSION );

      D3DDISPLAYMODE d3ddm;

    g_pD3D->GetAdapterDisplayMode( D3DADAPTER_DEFAULT, &d3ddm );

      D3DPRESENT_PARAMETERS d3dpp={0,0, d3ddm.Format, 0, (D3DMULTISAMPLE_TYPE)0,

                                    D3DSWAPEFFECT_DISCARD, hwnd,TRUE,TRUE, D3DFMT_D16, 0, 0,0 };

    g_pD3D->CreateDevice( D3DADAPTER_DEFAULT, D3DDEVTYPE_HAL, NULL,

                                    D3DCREATE_SOFTWARE_VERTEXPROCESSING,&d3dpp, &g_pd3dDevice );

    g_pd3dDevice->SetRenderState( D3DRS_ZENABLE, TRUE );

      g_pd3dDevice->SetRenderState( D3DRS_CULLMODE, D3DCULL_NONE);

      g_pd3dDevice->SetRenderState(D3DRS_LIGHTING, FALSE);

      ReadVerticesFromFile();

    return true;

}

////////////////////////////////////////////////////////////////////////////////////

//                                                                                \\

//  Our Windows Code....this is the windows code...I cramed it together so that   \\

//  it has its bare essentials...couldn't get it any smaller than this...so that  \\

//  we could concentrate at the heart of our coding....Octee and not the windows  \\

//  code.                                                                         \\

//                                                                                \\

////////////////////////////////////////////////////////////////////////////////////

LRESULT WINAPI MsgProc( HWND hWnd, UINT msg, WPARAM wParam, LPARAM lParam )

{

    switch( msg )

    {

        case WM_DESTROY:

            PostQuitMessage( 0 );

            return 0;

    }

    return DefWindowProc( hWnd, msg, wParam, lParam );

}

INT WINAPI WinMain( HINSTANCE hInst, HINSTANCE, LPSTR, INT )

{

    // Register the window class

      char szName[] = "www.xbdev.net";

    WNDCLASSEX wc = { sizeof(WNDCLASSEX), CS_CLASSDC, MsgProc, 0L, 0L,

                      GetModuleHandle(NULL), NULL, NULL, NULL, NULL,

                      szName, NULL };

    RegisterClassEx( &wc );

    // Create the application's window

    HWND hWnd = CreateWindow( szName, szName,

                              WS_OVERLAPPEDWINDOW, 100, 100, 600, 600,

                              GetDesktopWindow(), NULL, wc.hInstance, NULL );

    // Initialize Direct3DX

    InitD3D( hWnd );

      // Show the window

    ShowWindow( hWnd, SW_SHOWDEFAULT );

    UpdateWindow( hWnd );

    // Enter the message loop

    MSG msg;

    ZeroMemory( &msg, sizeof(msg) );

    while( msg.message!=WM_QUIT )

    {

            if( PeekMessage( &msg, NULL, 0U, 0U, PM_REMOVE ) )

        {

                  TranslateMessage( &msg );

            DispatchMessage( &msg );

        }

        else

            Render();

    }

    // Clean up everything and exit the app

    Cleanup();

    UnregisterClass( szName, wc.hInstance );

    return 0;

}

class COctree

{

public:

      COctree(void){};

      ~COctree(void){};

};

// 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 <d3dx8.h>

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()

      {

      }

};

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()

      {

      }

};

// 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 <d3dx8.h>

// 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<iNumVertices; i++)

            {

                  m_vCenter.x = m_vCenter.x + pVertices[i].x;

                  m_vCenter.y = m_vCenter.y + pVertices[i].y;

                  m_vCenter.z = m_vCenter.z + pVertices[i].z;

            }

            m_vCenter.x = m_vCenter.x / (float)iNumVertices;

            m_vCenter.y = m_vCenter.y / (float)iNumVertices;

            m_vCenter.z = m_vCenter.z / (float)iNumVertices;

            //   /|\

            //    |

            //    +-----Center of our CUBE (e.g. each node is a cube shape)

            float fWidthMax  = 0.0f;

            float fHeightMax = 0.0f;

            float fDepthMax  = 0.0f;

            //<2> Now lets find the diameter

            for(int i=0; i<iNumVertices; i++)

            {

                  float fWidth  = abs_f(pVertices[i].x - m_vCenter.x);

                  float fHeight = abs_f(pVertices[i].y - m_vCenter.y);

                  float fDepth  = abs_f(pVertices[i].z - m_vCenter.z);

                  if( fWidth  > 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; i<iNumTriangles; i++)

                  {

                        if(pBoolArray1[i]==true) iCount1++;

                        if(pBoolArray2[i]==true) iCount2++;

                        if(pBoolArray3[i]==true) iCount3++;

                        if(pBoolArray4[i]==true) iCount4++;

                        if(pBoolArray5[i]==true) iCount5++;

                        if(pBoolArray6[i]==true) iCount6++;

                        if(pBoolArray7[i]==true) iCount7++;

                        if(pBoolArray8[i]==true) iCount8++;

                  }

                  CreateNodeEnd(pVertices, iNumVertices, pBoolArray1, vCenter, fDiameter, iCount1,TOP_FRONT_LEFT);

                  CreateNodeEnd(pVertices, iNumVertices, pBoolArray2, vCenter, fDiameter, iCount2,TOP_FRONT_RIGHT);

                  CreateNodeEnd(pVertices, iNumVertices, pBoolArray3, vCenter, fDiameter, iCount3,TOP_BACK_LEFT);

                  CreateNodeEnd(pVertices, iNumVertices, pBoolArray4, vCenter, fDiameter, iCount4,TOP_BACK_RIGHT);

                  CreateNodeEnd(pVertices, iNumVertices, pBoolArray5, vCenter, fDiameter, iCount5,BOTTOM_FRONT_LEFT);

                  CreateNodeEnd(pVertices, iNumVertices, pBoolArray6, vCenter, fDiameter, iCount6,BOTTOM_FRONT_RIGHT);

                  CreateNodeEnd(pVertices, iNumVertices, pBoolArray7, vCenter, fDiameter, iCount7,BOTTOM_BACK_LEFT);

                  CreateNodeEnd(pVertices, iNumVertices, pBoolArray8, vCenter, fDiameter, iCount8,BOTTOM_BACK_RIGHT);

            }

      }

      // When we create a new node, we call this function, and it initilises our new node, and copies

      // the vertices from its parent node into it...sets up its new diameter, center etc.

      void CreateNodeEnd(D3DXVECTOR3* pTotalVertices, int iNumTotalVertices, bool* pBools,

                           D3DXVECTOR3 vCenter, float fDiameter,

                                 int iTriangles, int iWhichNode)

      {

            // Is there any triangles in this node?

            if( iTriangles == 0 )

                  return;

            // We determine how many triangles are for this new node, loop through all the pBools

            // if its true then its within our cube, so we increment our counter.

            D3DXVECTOR3* pNodeVerts = new D3DXVECTOR3[iTriangles*3];

            int iCount=0;

            for(int i=0; i<iNumTotalVertices; i++)

            {

                  if( pBools[i/3] ) // if a single point is in the cube node, then the whole

                  {                 // triangle is in there.

                        pNodeVerts[iCount] = pTotalVertices[i];

                        iCount++;

                  }

            }

        // Create a new node.

            m_pOctreeNodes[iWhichNode] = new COctree;

            // Use another member function to find the center of this new node.

            D3DXVECTOR3 vNewCenter = GetNodeCenter(vCenter, fDiameter, iWhichNode);

            g_iCurrentNodeLevel++;

            // Call the funtion to create this new node, and pass in the details.

            m_pOctreeNodes[iWhichNode]->CreateNode(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; i<iNumTriangles*3; i+=3)

                  {

                        D3DXVECTOR3 p1 = pNode->m_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.