• Advertisement
Sign in to follow this  

Need help pin-pointing problem with Simplex Noise

This topic is 441 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I recently implemented simplex noise for world gen in the project, however I've ran into a problem where there seems to be seams horizontally, vertically, and diagonally. Screenshot here: http://i.imgur.com/JIOABPZ.png
 
I've gone over the noise gen algorithm a few times, even testing floats vs doubles but there doesn't seem to be much difference.
 

The screenshot shows my 4 chunks, each 128x128. The seams happen every 40 tiles or so. I can scale up the noise to try to hide it, but the features would be too large. 

 

Thanks for help

static u8 snPermSupply[] = {151,160,137,91,90,15, 131,13,201,95,96,53,194,233,7,225,140,36,103,30,69,142,8,99,37,240,21,10,23,
  190, 6,148,247,120,234,75,0,26,197,62,94,252,219,203,117,35,11,32,57,177,33,
  88,237,149,56,87,174,20,125,136,171,168, 68,175,74,165,71,134,139,48,27,166,
  77,146,158,231,83,111,229,122,60,211,133,230,220,105,92,41,55,46,245,40,244,
  102,143,54, 65,25,63,161, 1,216,80,73,209,76,132,187,208, 89,18,169,200,196,
  135,130,116,188,159,86,164,100,109,198,173,186, 3,64,52,217,226,250,124,123,
  5,202,38,147,118,126,255,82,85,212,207,206,59,227,47,16,58,17,182,189,28,42,
  223,183,170,213,119,248,152, 2,44,154,163, 70,221,153,101,155,167, 43,172,9,
  129,22,39,253, 19,98,108,110,79,113,224,232,178,185, 112,104,218,246,97,228,
  251,34,242,193,238,210,144,12,191,179,162,241, 81,51,145,235,249,14,239,107,
  49,192,214, 31,181,199,106,157,184, 84,204,176,115,121,50,45,127, 4,150,254,
  138,236,205,93,222,114,67,29,24,72,243,141,128,195,78,66,215,61,156,180};

static int snNumberOfSwaps = 800;

static v3 snGrad3[] = {{1,1,0}, {-1,1,0}, {1, -1, 0}, 
                      {-1,-1,0},{1,0,1},{-1,0,1},
                      {1,0,-1}, {-1,0,-1}, {0,1,1},
                      {0,-1,1},{0,1,-1},{0,-1,-1}};

struct SimplexNoiseGen
{
    int seed;
    u8 permSupply[256];
    u8 perm[512];
    //u8 permMod12[512];
};


r32
Grad(s32 hash, r32 x, r32 y)
{
	s32 h = hash & 15;
    r32 u;
    r32 v;
    
    if(h < 4)
    {
        u = x;
    	v = y;    
    }
    else
    {
    	u = y;
        v = x;
    }
       
    return ((h & 1) ? -u : u) + ((h & 2) ? -2.0f*v : 2.0f*v);
    
}

void
InitSimplexNoise(SimplexNoiseGen* sn, s32 seed)
{
    sn->seed = seed;
    memcpy(sn->permSupply, snPermSupply, 256);
    
    srand(seed);

    for(s32 i = 0; 
        i < snNumberOfSwaps; 
        i++)
    {
        u8 swapFrom = rand() % 256;
        u8 swapTo = rand() % 256;
        
        u8 temp = sn->permSupply[swapFrom];
        sn->permSupply[swapFrom] = sn->permSupply[swapTo];
        sn->permSupply[swapTo] = temp;
    }

    for(s32 i = 0;
        i < 512;
        i++)
    {
        sn->perm[i] = sn->permSupply[i & 255];
        //sn->permMod12[i] = (u8)(sn->perm[i] % 12);
    }
}

#define SQRT3 1.732050807568877293527446341505872366942805253810380628055

r64 
Noise(SimplexNoiseGen* sn, r64 x, r64 y)
{
    // Sqrt 3
    #define F2 0.5 * (SQRT3 - 1.0);
    #define G2 (3.0 - SQRT3) / 6.0;
    
	r64 n0, n1, n2;
    
    r64 s = (x + y) * F2;
    s32 i = FAST_FLOOR(x + s);
    s32 j = FAST_FLOOR(y + s);
    r64 t = (r64)(i+j) * G2;
    
	r64 xU = i - t;
    r64 yU = j - t;
    r64 x0 = x - xU;
    r64 y0 = y - yU;
    
    s32 i1;
    s32 j1;
    if(x0 > y0)
    {
    	i1 = 1;
        j1 = 0;
    }
    else
    {
    	i1 = 0;
        j1 = 1;
    }
    
    r64 x1 = x0 - i1 + G2;
    r64 y1 = y0 - j1 + G2;
    r64 x2 = x0 - 1.0 + 2.0 * G2;
    r64 y2 = y0 - 1.0 + 2.0 * G2;
    
    s32 ii = i & 255;
    s32 jj = j & 255;
    
    /*s32 gi0 = sn->permMod12[ii + sn->perm[jj]];
    s32 gi1 = sn->permMod12[ii + i1 + sn->perm[jj+j1]];
    s32 gi2 = sn->permMod12[ii + 1 + sn->perm[jj+1]];*/
    
    r64 t0 = 0.5 - x0*x0 - y0*y0;
    
    if(t0 < 0.f)
    {
    	n0 = 0.0;
    }
    else
    {
        t0 *= t0;
        //v3 grad = snGrad3[gi0];
        n0 = t0 * t0 * Grad(sn->perm[ii + sn->perm[jj]], x0, y0); /*((grad.x * x0) + (grad.y * x0));*/
    }
    
    r64 t1 = 0.5 - x1*x1 - y1*y1;
    
    if(t1 < 0.f)
    {
    	n1 = 0.0;
    }
    else
    {
    	t1 *= t1;
        //v3 grad = snGrad3[gi1];
        n1 = t1 * t1 * Grad(sn->perm[ii+ i1 + sn->perm[jj + j1]], x1, y1); /*((grad.x * x1) + (grad.y * y1));*/
    }
    
    r64 t2 = 0.5 - x2*x2 - y2*y2;
    if(t2 < 0.f)
    {
    	n2 = 0.0;
    }
    else
    {
    	t2 *= t2;
        //v3 grad = snGrad3[gi2];
        n2 = t2 * t2 * Grad(sn->perm[ii + 1 + sn->perm[jj + 1]], x2, y2); /*((grad.x * x2) + (grad.y * y2));*/
    }
    
    return 40.0 * (n0 + n1 + n2);
}

 
Here is where i call it
 
 

    HeightMapGen heightMapGen;
    heightMapGen.width = 128;
    heightMapGen.height = 128;
    heightMapGen.xOffset = (chunk->worldPosX * 128);
    heightMapGen.yOffset = (chunk->worldPosY * 128);
    heightMapGen.scale = 60.2f;
    heightMapGen.octaves = 3;
    heightMapGen.persistance = 0.5;
    heightMapGen.lacunarity = 2;


_INTERNAL void
GenHeightMap(SimplexNoiseGen* sn, HeightMapGen mapGen)
{
    
    ASSERT(mapGen.persistance >= 0 && mapGen.persistance <= 1);
    ASSERT(mapGen.lacunarity > 1);
    ASSERT(mapGen.octaves > 0);
    
    if(mapGen.scale == 0)
    {
    	mapGen.scale = 1.3145926;
    }
    
    r32 maxHeightVal = FLT_MIN;
    r32 minHeightVal = FLT_MAX;
    
    for(s32 yIndex = 0; 
        yIndex < mapGen.height; 
        yIndex++)
    {
        for(s32 xIndex = 0;
            xIndex < mapGen.width;
            xIndex++)
        {
            u32 index = xIndex + (yIndex * mapGen.width);
            r32 amplitude = 1.f;
            r32 frequency = 1.f;
            r32 noiseHeight = 0.f;
            
            for(u32 octave = 0;
                octave < mapGen.octaves;
                octave++)
            {
                
                r32 sampleX = ((r32)(xIndex + mapGen.xOffset) / mapGen.scale) * frequency;
                r32 sampleY = ((r32)(yIndex + mapGen.yOffset) / mapGen.scale) * frequency;
                
                r32 val = (r32)Noise(sn, sampleX, sampleY);
                noiseHeight += val * amplitude;
            
                amplitude *= mapGen.persistance;
                frequency *= mapGen.lacunarity;
            }
            
            if(noiseHeight > maxHeightVal)
            {
            	maxHeightVal = noiseHeight;
            }
            else if(noiseHeight < minHeightVal)
            {
            	minHeightVal = noiseHeight;
            }
            
            mapGen.heightValues[index] = noiseHeight;
            
        }
    }

    for(u32 yIndex = 0; 
        yIndex < mapGen.height; 
        yIndex++)
    {
        for(u32 xIndex = 0;
            xIndex < mapGen.width;
            xIndex++)
        {
            u32 index = xIndex + (yIndex * mapGen.width);
            mapGen.heightValues[index] = (mapGen.heightValues[index] - minHeightVal) / (maxHeightVal - minHeightVal);
        }
    }            

}

Share this post


Link to post
Share on other sites
Advertisement

As is with tradition, I think I fixed it. Apparently the problem was with my FAST_FLOOR(). If I use the standard floor() function everything comes out correctly, but doing the whole (x>0) ? (int)x : ((int)x - 1) doesn't work properly in this case.

Share this post


Link to post
Share on other sites

Upvoted (along with others, I suspect) for the sheer common decency of telling us HOW you fixed it. If you want to write an article / blog post with how you debugged it, including test steps, please do.

 

 

 

 

And link it here, for more upvotes. (Well, one at least!) :)

Share this post


Link to post
Share on other sites

If your macro looks like this...

#define FAST_FLOOR(x) ((x>0) ? (int)x : ((int)x-1))

...then trying changing it to:

#define FAST_FLOOR(x) (((x)>0) ? ((int)(x)) : (((int)(x))-1))
Edited by BFG

Share this post


Link to post
Share on other sites

That's not going to solve the main problem with FAST_FLOOR, namely that it gives incorrect results for nonpositive integers (eg if x is equal to 0, it will return -1. x=-1 will result in -2 etc).

Share this post


Link to post
Share on other sites

That's not going to solve the main problem with FAST_FLOOR, namely that it gives incorrect results for nonpositive integers (eg if x is equal to 0, it will return -1. x=-1 will result in -2 etc).

 

That's certainly a bug but I wouldn't say it's the main problem.  It wouldn't cause the discontinuities OP was getting.

 

Check out what happens when you do (1) floorf, (2) the "improved" second FAST_FLOOR macro above, and (3) the "original" first FAST_FLOOR macro above on the following arguments respectively:

#define FAST_FLOOR_ORIGINAL(x) ((x>0) ? (int)x : ((int)x-1))
#define FAST_FLOOR_IMPROVED(x) (((x)>0) ? ((int)(x)) : (((int)(x))-1)) // but still incorrect for floating point values that are exactly nonpositive integers

    for (float x = -1.5f; x < 2.f; x += 0.1f)
    {
        const int a = floorf(x + 1.2f);
        const int b = FAST_FLOOR_IMPROVED(x + 1.2f);
        const int c = FAST_FLOOR_ORIGINAL(x + 1.2f);
        fprintf(fp, "(%f + 1.2f):  %d %d %d\n", x, a, b, c);
    }

(-1.500000 + 1.2f):  -1 -1 0
(-1.400000 + 1.2f):  -1 -1 0
(-1.300000 + 1.2f):  -1 -1 0
(-1.200000 + 1.2f):  0 0 0
(-1.100000 + 1.2f):  0 0 0
(-1.000000 + 1.2f):  0 0 1
(-0.900000 + 1.2f):  0 0 1
(-0.800000 + 1.2f):  0 0 1
(-0.700000 + 1.2f):  0 0 1
(-0.600000 + 1.2f):  0 0 1
(-0.500000 + 1.2f):  0 0 1
(-0.400000 + 1.2f):  0 0 1
(-0.300000 + 1.2f):  0 0 1
(-0.200000 + 1.2f):  1 1 1
(-0.100000 + 1.2f):  1 1 1
(0.000000 + 1.2f):  1 1 1
(0.100000 + 1.2f):  1 1 1
(0.200000 + 1.2f):  1 1 1
(0.300000 + 1.2f):  1 1 1
(0.400000 + 1.2f):  1 1 1
(0.500000 + 1.2f):  1 1 1
(0.600000 + 1.2f):  1 1 1
(0.700000 + 1.2f):  1 1 1
(0.800000 + 1.2f):  2 2 1
(0.900000 + 1.2f):  2 2 1
(1.000000 + 1.2f):  2 2 2
(1.100000 + 1.2f):  2 2 2
(1.200000 + 1.2f):  2 2 2
(1.300000 + 1.2f):  2 2 2
(1.400000 + 1.2f):  2 2 2
(1.500000 + 1.2f):  2 2 2
(1.600000 + 1.2f):  2 2 2
(1.700000 + 1.2f):  2 2 2
(1.800000 + 1.2f):  3 3 2
(1.900000 + 1.2f):  3 3 2
 

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement