exception: std::bad_alloc

[Alerion]

Hello everyone,
I've been a regular of this forum but this is my first post, generally I can find the answer to my question already, but this time I'm having a somewhat specific problem.
For fun I've been working on making a 3d game (who hasn't haha) and while it's nothing special at the moment I was making some decent headway. I'm working on constructing an octree for my triangle data, but I keep getting this pesky bad_alloc runtime error. I've looked up online for more information on it, including this post here on TheScripts http://www.thescripts.com/forum/thread523575.html. Unfortunately it just reaffirmed that I'm probably doing something stupid without giving me any direction. Here is the octree class:

Header:

#pragma once
 
#include <d3dx9.h>
#include <d3d9.h>
#include <string>
#include <vector>
 
#include <iostream>
#include <fstream>
 
#pragma comment(lib, "d3dx9.lib")
#pragma comment(lib, "d3d9.lib")
 
class czOctree
{
    public:
        czOctree( );
 
        ~czOctree( ) { }
 
        void Release( );
        void Create(D3DXVECTOR3* pVerts, int iNumVerticies);
 
    private:
        static const int maxNodes = 3;
        static const int minNumTriangles = 250;
 
    protected:
        int numVerticies;
        D3DXVECTOR3* pVerticies;
        D3DXVECTOR3 center;
        float diameter;
        bool containsTriangles;
        czOctree* oChildren[8];
 
        enum octreeParts { TOP_FRONT_LEFT, TOP_FRONT_RIGHT, TOP_BACK_LEFT, TOP_BACK_RIGHT,
            BOTTOM_FRONT_LEFT, BOTTOM_FRONT_RIGHT, BOTTOM_BACK_LEFT, BOTTOM_BACK_RIGHT };
 
        inline float abs_f(float f) { if(f<0) return -f; return f; };
        inline D3DXVECTOR3 GetNodeCenter(D3DXVECTOR3 currentCenter, float fDiameter, int iWhichNode);
 
        void SetData(D3DXVECTOR3* pVerts, int numVerts);
        void SetNode(D3DXVECTOR3* pVerts, int numVerts);
        void CreateNode(D3DXVECTOR3* pVerts, int numVerts, D3DXVECTOR3 vCenter, float fDiameter);
        void CreateNodeEnd(D3DXVECTOR3* pTotalVerts, int NumTotalVerts, bool* pBools, D3DXVECTOR3 vCenter, float fDiameter, int iTriangles, int iWhichNode);
 
 
};
 

and the source file

#include "octrees.h"
 
const bool DEBUG = true;
#define DMSGBOX( a ) { if(DEBUG) MessageBox(NULL, a, "DEBUG", 0); }
#define DMSGFILE( file, a ) { if(DEBUG && f.is_open()) file << a << std::endl; }
int g_currentLevel;
 
czOctree::czOctree( )
{
    numVerticies = NULL;
    pVerticies = NULL;
    center = D3DXVECTOR3(0,0,0);
    diameter = 0.0f;
    ZeroMemory(oChildren, sizeof(oChildren));
}
 
void czOctree::SetData(D3DXVECTOR3 *pVerts, int numVerts)
{
    if( pVerts == NULL || numVerts == 0 )
        return;
 
    for(int i=0; i<numVerts; i++)
    {
        center.x = center.x + pVerts[i].x;
        center.y = center.y + pVerts[i].y;
        center.z = center.z + pVerts[i].z;
    }
 
    center.x = center.x / (float)numVerts;
    center.y = center.y / (float)numVerts;
    center.z = center.z / (float)numVerts;
 
    float widthMax = 0.0f;
    float heightMax = 0.0f;
    float depthMax = 0.0f;
 
    for(int i=0; i<numVerts; i++)
    {
        float width = abs_f(pVerts[i].x - center.x);
        float height = abs_f(pVerts[i].y - center.y);
        float depth = abs_f(pVerts[i].z - center.z);
 
        if( width > widthMax )        widthMax = width;
        if( height > heightMax )    heightMax = height;
        if( depth > depthMax )        depthMax = depth;
    }
 
    widthMax *= 2;
    heightMax *= 2;
    depthMax *= 2;
 
    diameter = max( widthMax, max(heightMax,depthMax) );
}
 
void czOctree::CreateNode(D3DXVECTOR3 *pVerts, int numVerts, D3DXVECTOR3 vCenter, float fDiameter)
{
 
    center = vCenter;
    int numTriangles = numVerts / 3;
    diameter = fDiameter;
 
    if( (numTriangles < minNumTriangles) || (g_currentLevel >= maxNodes) )
    {
        SetNode(pVerts, numVerts);
        containsTriangles = true;
    }
    else
    {
        containsTriangles = false;
        bool* pBoolArray1 = new bool[numTriangles];
        bool* pBoolArray2 = new bool[numTriangles];
        bool* pBoolArray3 = new bool[numTriangles];
        bool* pBoolArray4 = new bool[numTriangles];
        bool* pBoolArray5 = new bool[numTriangles];
        bool* pBoolArray6 = new bool[numTriangles];
        bool* pBoolArray7 = new bool[numTriangles];
        bool* pBoolArray8 = new bool[numTriangles];
 
        ZeroMemory(pBoolArray1, numTriangles);
        ZeroMemory(pBoolArray2, numTriangles);
        ZeroMemory(pBoolArray3, numTriangles);
        ZeroMemory(pBoolArray4, numTriangles);
        ZeroMemory(pBoolArray5, numTriangles);
        ZeroMemory(pBoolArray6, numTriangles);
        ZeroMemory(pBoolArray7, numTriangles);
        ZeroMemory(pBoolArray8, numTriangles);
 
        D3DXVECTOR3 cntr = center;
        for(int i=0; i< numVerts; i++)
        {
            D3DXVECTOR3 point = pVerts[i];
            if((point.y >= cntr.y) && (point.x <= cntr.x) && (point.z >= cntr.z) )
                pBoolArray1[i/3] = true;                
            if( (point.y >= cntr.y) && (point.x >= cntr.x) && (point.z >= cntr.z) )
                pBoolArray2[i/3] = true;
            if( (point.y >= cntr.y) && (point.x <= cntr.x) && (point.z <= cntr.z) )
                pBoolArray3[i/3] = true;
            if( (point.y >= cntr.y) && (point.x >= cntr.x) && (point.z <= cntr.z) )
                pBoolArray4[i/3] = true;
            if( (point.y <= cntr.y) && (point.x <= cntr.x) && (point.z >= cntr.z) )
                pBoolArray5[i/3] = true;
            if( (point.y <= cntr.y) && (point.x >= cntr.x) && (point.z >= cntr.z) )
                pBoolArray6[i/3] = true;
            if( (point.y <= cntr.y) && (point.x <= cntr.x) && (point.z <= cntr.z) )
                pBoolArray7[i/3] = true;
            if( (point.y <= cntr.y) && (point.x >= cntr.x) && (point.z <= cntr.z) )
                pBoolArray8[i/3] = true;
 
        }
 
        int iCount1, iCount2, iCount3, iCount4, iCount5, iCount6, iCount7, iCount8;
        iCount1 = iCount2 = iCount3 = iCount4 = iCount5 = iCount6 = iCount7 = iCount8 = 0;
 
        for(int i=0; i<numTriangles; i++)
        {
            if(pBoolArray1[i]) iCount1++;
            if(pBoolArray2[i]) iCount2++;
            if(pBoolArray3[i]) iCount3++;
            if(pBoolArray4[i]) iCount4++;
            if(pBoolArray5[i]) iCount5++;
            if(pBoolArray6[i]) iCount6++;
            if(pBoolArray7[i]) iCount7++;
            if(pBoolArray8[i]) iCount8++;
        }
 
        CreateNodeEnd(pVerts, numVerts, pBoolArray1, cntr, fDiameter, iCount1, TOP_FRONT_LEFT );
        CreateNodeEnd(pVerts, numVerts, pBoolArray2, cntr, fDiameter, iCount2, TOP_FRONT_RIGHT);
        CreateNodeEnd(pVerts, numVerts, pBoolArray3, cntr, fDiameter, iCount3, TOP_BACK_LEFT);
        CreateNodeEnd(pVerts, numVerts, pBoolArray4, cntr, fDiameter, iCount4, TOP_BACK_RIGHT);
        CreateNodeEnd(pVerts, numVerts, pBoolArray5, cntr, fDiameter, iCount5, BOTTOM_FRONT_LEFT);
        CreateNodeEnd(pVerts, numVerts, pBoolArray6, cntr, fDiameter, iCount6, BOTTOM_FRONT_RIGHT);
        CreateNodeEnd(pVerts, numVerts, pBoolArray7, cntr, fDiameter, iCount7, BOTTOM_BACK_LEFT);
        CreateNodeEnd(pVerts, numVerts, pBoolArray8, cntr, fDiameter, iCount8, BOTTOM_BACK_RIGHT);
 
        delete[] pBoolArray1;
        delete[] pBoolArray2;
        delete[] pBoolArray3;
        delete[] pBoolArray4;
        delete[] pBoolArray5;
        delete[] pBoolArray6;
        delete[] pBoolArray7;
        delete[] pBoolArray8;
    }
}
 
void czOctree::CreateNodeEnd(D3DXVECTOR3 *pTotalVerts, int NumTotalVerts, bool *pBools, D3DXVECTOR3 vCenter, float fDiameter, int iTriangles, int iWhichNode)
{
    if( iTriangles = 0 )
        return;
 
    D3DXVECTOR3* nodeVerts = new D3DXVECTOR3[iTriangles*3];
    int count = 0;
 
    for(int i=0; i<NumTotalVerts; i++)
    {
        if( pBools[i/3] ) 
        {
            nodeVerts[count] = pTotalVerts[i];
            count++;
        }
    }
 
    oChildren[iWhichNode] = new czOctree;
    D3DXVECTOR3 newCenter = GetNodeCenter(vCenter, fDiameter, iWhichNode);
    g_currentLevel++;
    oChildren[iWhichNode]->CreateNode(nodeVerts, iTriangles*3, newCenter, fDiameter/2);
    g_currentLevel--;
 
    delete[] nodeVerts;
}
 
void czOctree::SetNode(D3DXVECTOR3 *pVerts, int numVerts)
{
    containsTriangles = true;
    numVerticies = numVerts;
    pVerticies = new D3DXVECTOR3[numVerts];
    ZeroMemory(pVerticies, sizeof(D3DXVECTOR3)*numVerticies);
 
    memcpy(pVerticies, pVerts, sizeof(D3DXVECTOR3)*numVerticies);
}
 
D3DXVECTOR3 czOctree::GetNodeCenter(D3DXVECTOR3 currentCenter, float fDiameter, int iWhichNode)
{
    D3DXVECTOR3 vCenter = currentCenter;
    D3DXVECTOR3 vNewCenter = D3DXVECTOR3(0.0f,0.0f,0.0f);
    float fDia = fDiameter;
 
    switch(iWhichNode)
    {
        case TOP_FRONT_LEFT:
            {   vNewCenter = D3DXVECTOR3( vCenter.x - fDia/4, vCenter.y + fDia/4, vCenter.z + fDia/4 );
                break; }
        case TOP_FRONT_RIGHT:
            {    vNewCenter = D3DXVECTOR3( vCenter.x + fDia/4, vCenter.y + fDia/4, vCenter.z + fDia/4 );
                break; }
        case TOP_BACK_LEFT:
            {    vNewCenter = D3DXVECTOR3( vCenter.x - fDia/4, vCenter.y + fDia/4, vCenter.z - fDia/4 );
                break; }
        case TOP_BACK_RIGHT:
            {   vNewCenter = D3DXVECTOR3( vCenter.x + fDia/4, vCenter.y + fDia/4, vCenter.z - fDia/4 );
                break; }
        case BOTTOM_FRONT_LEFT:
            {   vNewCenter = D3DXVECTOR3( vCenter.x - fDia/4, vCenter.y - fDia/4, vCenter.z + fDia/4 );
                break; }
        case BOTTOM_FRONT_RIGHT:
            {   vNewCenter = D3DXVECTOR3( vCenter.x + fDia/4, vCenter.y - fDia/4, vCenter.z + fDia/4 );
                break; }
        case BOTTOM_BACK_LEFT:
            {   vNewCenter = D3DXVECTOR3( vCenter.x - fDia/4, vCenter.y - fDia/4, vCenter.z - fDia/4 );
                break; }
        case BOTTOM_BACK_RIGHT:
            {   vNewCenter = D3DXVECTOR3( vCenter.x + fDia/4, vCenter.y - fDia/4, vCenter.z - fDia/4 );
                break; }
    }
 
    return vNewCenter;
}
 
void czOctree::Release( )
{
    if(pVerticies)
    {
        delete[] pVerticies;
        pVerticies = NULL;
    }
 
    for(int i=0; i<8; i++)
    {
        if( oChildren[i] )
        {
            oChildren[i]->Release( );
            oChildren[i] = NULL;
        }
    }
}
 
void czOctree::Create(D3DXVECTOR3* pVerts, int iNumVerticies)
{
    numVerticies = iNumVerticies;
 
    SetData(pVerts, iNumVerticies);
 
    CreateNode(pVerts, numVerticies, center, diameter);
}
 

the offending line is:

oChildren[iWhichNode] = new czOctree;
 

Line 163 from the source.

Any small level of impressiveness that might've been achieved by this code is negated by the fact that I did it following very closely this guide on xbdev.net: http://www.xbdev.net/maths_of_3d/octree/tutorial/index.php

The output from debug reads:

First-chance exception at 0x7c91b3fb in zombie1.exe: 0xC0000005: Access violation reading location 0x44080000.
First-chance exception at 0x7c81eb33 in zombie1.exe: Microsoft C++ exception: std::bad_alloc at memory location 0x0012fbc4..
Unhandled exception at 0x7c81eb33 in zombie1.exe: Microsoft C++ exception: std::bad_alloc at memory location 0x0012fbc4..
 

I'm fairly sure the error in code is here and not in the implementation from the engine, and so I've neglected to post that here. Mostly because I was able to call new on the bool arrays which precede this call. I added the lines:

delete[] pBoolArray1;
...
delete[] pBoolArray8;
 

which were not present in the original source at xbdev.net. Not that I assumed I was a better programmer but because I thought it was right. Even commenting this out I get the same error at the same location.

Please forgive my poor programming style. I am pretty noobish.

If anyone can help me narrow down my problem I'd be greatly appreciative. If you've read this far, I thank you for reading this cumbersome post ^^;;

-Ally

[Alerion]

Following some leads I found on the net, and it would seem this would mean I have run out of memory. Is it possible it's from all those boolean arrays? This recursive function is not getting to deallocate those arrays before moving on to the deeper iterations...

Just a thought.

[OuaisBla]

 
 
ASSERT(iTriangles*3 >=NumTotalVerts);
 
 D3DXVECTOR3* nodeVerts = new D3DXVECTOR3[iTriangles*3];
    int count = 0;
 
    for(int i=0; i<NumTotalVerts; i++)
    {
        if( pBools[i/3] ) 
        {
            ASSERT(count < iTriangles*3);
 
            nodeVerts[count] = pTotalVerts[i];
            count++;
        }
    }

Try those check.

Your errors means that somehow the memory was corrupted and a runtime check failed. This is likely to be en error created before the allocation that failed. Also the 0XC000005 is an exception throw when accessing memory not in your adress space. Accessing memory that was deleted is marked 0xFEFEFEFE. Memory that is uninitilized is marked 0XCDCDCDCD. I assumed that this error occurs more in release than in debug right? If it does in crash in debug, it should be easy to fix.

[weaknessforcats]

Your errors means that somehow the memory was corrupted and a runtime check failed. This is likely to be en error created before the allocation that failed. Also the 0XC000005 is an exception throw when accessing memory not in your adress space. Accessing memory that was deleted is marked 0xFEFEFEFE. Memory that is uninitilized is marked 0XCDCDCDCD. I assumed that this error occurs more in release than in debug right? If it does in crash in debug, it should be easy to fix.

This is my feeling also. Besides, I don't think Visual Studio.NET throws a bad_alloc. To do that free memory is down to the amount required to throw the exception. Long before you get into this condition the message box "Windows running low on resources...." has appeared for hours and the hard disc is vibrating your machine acrosss the floor.

Almost certainly the problem is with oChildren[iWhichNode].

[OuaisBla]

The thing is that you might have no more RAM available but Windows will get virtually new one for you using its paging file system.

The only thing you really can be short of is a valid range of adress in the adress space. Each program under windows have 2gig of adress space no matter how much RAM you got on your system.

On Windows CE 5.0 the limit is 32 meg per process, even if more RAM is available.

So a new() call can only fails if not enough contiguous addresses are free in the adress space. If there isn't enough RAM at that point, Windows will start moving page of memory to disk to get some RAM free. This is call virtual memory mapping. This is very powerful.

Long before you get into this condition the message box "Windows running low on resources...." has appeared for hours and the hard disc is vibrating your machine acrosss the floor.

Your are totally right. Moving page file to disk in low ressources conditions is very painful to hear :)....