www.xbdev.net xbdev - software development
Saturday June 24, 2017
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.

 

DownloadCode

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

/*                                                                                */

/* 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;

}

 

 

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.

 

DownLoadCode

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

/*                                                                                */

/* 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;

}

 

 

 

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

      {

      }

};

 

 

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 <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.

 

 

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  { 209.237.238.175 } Copyright (c) 2002-2017 xbdev.net - All rights reserved.
Designated tutorial and software are the property of their respective owners.