Jump to content
  • Advertisement
Sign in to follow this  
CirdanValen

Need help pin-pointing problem with Simplex Noise

This topic is 670 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
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!