Help with Diamond Square algorithm implementation

Question

I'm trying to implement the Diamond-square algorithm, but the problem is only part of the bitmap is being filled and I'm not sure what's wrong. I'm doing it recursively:

    GLuint CreateDsquare()
    {
        std::vector<GLubyte> pdata(256 * 256 * 4);


        vector2i loc;
        vector2i sz;
        GLubyte val;

        sz.x = 256;
        sz.y = 256;

        val = rand() % 255;

        loc = vector2i(0,0);

         pdata[loc.y * 4 * sz.x + loc.x * 4 + 0] = val;
         pdata[loc.y * 4 * sz.x + loc.x * 4 + 1] = val;
         pdata[loc.y * 4 * sz.x + loc.x * 4 + 2] = val;
         pdata[loc.y * 4 * sz.x + loc.x * 4 + 3] = 255;

        loc.x = sz.x - 1;
        loc.y = 0;

        val = rand() % 255;

        pdata[loc.y * 4 * sz.x + loc.x * 4 + 0] = val;
        pdata[loc.y * 4 * sz.x + loc.x * 4 + 1] = val;
        pdata[loc.y * 4 * sz.x + loc.x * 4 + 2] = val;
        pdata[loc.y * 4 * sz.x + loc.x * 4 + 3] = 255;

        loc.x = sz.x - 1;
        loc.y = sz.y - 1;

        val = rand() % 255;

        pdata[loc.y * 4 * sz.x + loc.x * 4 + 0] = val;
        pdata[loc.y * 4 * sz.x + loc.x * 4 + 1] = val;
        pdata[loc.y * 4 * sz.x + loc.x * 4 + 2] = val;
        pdata[loc.y * 4 * sz.x + loc.x * 4 + 3] = 255;

        loc.x = 0;
        loc.y = sz.y - 1;

        val = rand() % 255;

        pdata[loc.y * 4 * sz.x + loc.x * 4 + 0] = val;
        pdata[loc.y * 4 * sz.x + loc.x * 4 + 1] = val;
        pdata[loc.y * 4 * sz.x + loc.x * 4 + 2] = val;
        pdata[loc.y * 4 * sz.x + loc.x * 4 + 3] = 255;

        RescursiveDiamond(pdata,sz,vector2i(0,0));

        return CreateTexture(pdata,256,256);
    }

void RescursiveDiamond(std::vector<GLubyte> &pdata,vector2i psz, vector2i offset)
{
    int val;
    int newnum;
    if(psz.x < 2 && psz.y  < 2)
    {
        return;
    }


    vector2i loc;
    vector2i sz = psz;

    std::vector<int> pvertz(4,0);

    loc = offset;
    pvertz[0] = pdata[loc.y * 4 * sz.x + loc.x * 4 + 0];

    loc.x = offset.x + (psz.x - 1);
    loc.y = offset.y;
    pvertz[1] = pdata[loc.y * 4 * sz.x + loc.x * 4 + 0];

    loc.x = offset.x + (psz.x - 1);
    loc.y = offset.y + (psz.y - 1);
    pvertz[2] = pdata[loc.y * 4 * sz.x + loc.x * 4 + 0];

    loc.x = offset.x;
    loc.y = offset.y + (psz.y - 1);
    pvertz[3] = pdata[loc.y * 4 * sz.x + loc.x * 4 + 0];


    val = (pvertz[0] + pvertz[1]) / 2;
    val += 255;
    loc.x = (offset.x + (sz.x - 1)) / 2;
    loc.y = offset.y;

    pdata[loc.y * 4 * sz.x + loc.x * 4 + 0] = val;
    pdata[loc.y * 4 * sz.x + loc.x * 4 + 1] = val;
    pdata[loc.y * 4 * sz.x + loc.x * 4 + 2] = val;
    pdata[loc.y * 4 * sz.x + loc.x * 4 + 3] = 255;


    val = (pvertz[1] + pvertz[2]) / 2;
    val += 255;
    loc.x = (offset.x + (sz.x)) - 1;
    loc.y = ((offset.y + (sz.y)) / 2) - 1;

    pdata[loc.y * 4 * sz.x + loc.x * 4 + 0] = val;
    pdata[loc.y * 4 * sz.x + loc.x * 4 + 1] = val;
    pdata[loc.y * 4 * sz.x + loc.x * 4 + 2] = val;
    pdata[loc.y * 4 * sz.x + loc.x * 4 + 3] = 255;


    val = (pvertz[3] + pvertz[2]) / 2;
    val += 255;
    loc.x = ((offset.x + (sz.x)) / 2) - 1;
    loc.y = (offset.y + (sz.y)) - 1 ;

    pdata[loc.y * 4 * sz.x + loc.x * 4 + 0] = val;
    pdata[loc.y * 4 * sz.x + loc.x * 4 + 1] = val;
    pdata[loc.y * 4 * sz.x + loc.x * 4 + 2] = val;
    pdata[loc.y * 4 * sz.x + loc.x * 4 + 3] = 255;


    val = (pvertz[0] + pvertz[3]) / 2;
    val += 255;
    loc.x =  offset.x;
    loc.y = (offset.y + (sz.y)) - 1 ;

    pdata[loc.y * 4 * sz.x + loc.x * 4 + 0] = val;
    pdata[loc.y * 4 * sz.x + loc.x * 4 + 1] = val;
    pdata[loc.y * 4 * sz.x + loc.x * 4 + 2] = val;
    pdata[loc.y * 4 * sz.x + loc.x * 4 + 3] = 255;

    //center

    val = (pdata[(offset.y) * 4 * sz.x + ((offset.x + (sz.x - 1)) / 2) * 4 + 0] +
        pdata[(offset.y + (sz.y - 1)) * 4 * sz.x + ((offset.x + (sz.x - 1)) / 2) * 4 + 0]) / 2;

    int ad = (rand() % 12) - 6;
    if(val + ad < 0)
    {
        val = 0;
    }
    else
    {
        val += ad;
    }

    val += 255;

    loc.x =  ((offset.x + (sz.x) ) / 2) - 1;
    loc.y = ((offset.y + (sz.y)) / 2) - 1;

    pdata[loc.y * 4 * sz.x + loc.x * 4 + 0] = val;
    pdata[loc.y * 4 * sz.x + loc.x * 4 + 1] = val;
    pdata[loc.y * 4 * sz.x + loc.x * 4 + 2] = val;
    pdata[loc.y * 4 * sz.x + loc.x * 4 + 3] = 255;



    vector2i newoffset;
    vector2i newparentsz;

    newoffset = offset;
    newparentsz = (psz / 2);

    RescursiveDiamond(pdata,newparentsz,newoffset);

    newoffset.x = offset.x + (newparentsz.x);
    newoffset.y = offset.y;

    RescursiveDiamond(pdata,newparentsz,newoffset);


    newoffset.x = offset.x;
    newoffset.y = offset.y + (newparentsz.y);

    RescursiveDiamond(pdata,newparentsz,newoffset);
    newoffset.x = offset.x + (newparentsz.x);
    newoffset.y = offset.y + (newparentsz.y);

    RescursiveDiamond(pdata,newparentsz,newoffset);



}

I suspect that I might be recalling the function with the wrong offset or something.

offset is like the top left and then there is the size, together these nake the square.

what could be wrong here?

Thanks

Answer 1

Ok, first, Let's start with cleaning up the violations of D-R-Y, your code should read more along the lines of this:

int position( _y, _x, _offset ){
    return _y * _x * 4 + _x * 4 + _offset;
}

void adjust(vector<GLubyte> &pdata, _x, _y){
    GLubyte val = rand() % 255;
    for(int j=0; j < 3; ++j){
        pdata[ position( _y, _x, j ) ] = val;
    }
    pdata[ position( _y, _x, 3 ) ] = 255;
}

GLuint CreateDsquare(){
    vector2i sz;

    sz.x = 256;
    sz.y = 256;

    adjust( pdata, 0, 0 );
    adjust( pdata, sz.x - 1, 0 );
    adjust( pdata, sz.x -1, sz.y - 1 );
    adjust( pdata, 0, sz.y - 1 );

    RescursiveDiamond(pdata,sz,vector2i(0,0));

    return CreateTexture(pdata,256,256);
}

Can you format the rest of it down so it's more readable/understandable? Then I'll update so that I can better answer your question (if someone hasn't beaten me to it or the woman decides I've had enough computer time.)

Answer 2

When you are calculating the offset into your height map for each row (y * pitch) you are using the current size of the square you are calculating instead of the actual pitch which is 256. The deeper you go into the recursion you are writing into your height map as if it was smaller and smaller until the last step of your recursion is writing into pixel (0, 0).