4
\$\begingroup\$

I'm currently working on my game. I would like to generate the world map with Perlin noise, and wrap it just like a real world map. I've found a algorithm to create a map wrapped along X and Y axis:

Procedurally Generating Wrapping World Maps

Wrapped map

The problem is that this map have no linear equator and poles. If you cross the north pole, you will end up in the south. A realistic map should be like this:

enter image description here

So when you cross the north pole you end up at the opposite longitude. So when you get an arial view of this flat map, you get something like this:

enter image description here

The problem is that I don't know how to generate a perlin noise that repeat itself like this. In the website I linked, they use a 4D Perlin noise. But I still can't figure out how to use it for my case. Here is the code used in the link:

for (var x = 0; x < Width; x++) {
    for (var y = 0; y < Height; y++) {

        // Noise range
        float x1 = 0, x2 = 2;
        float y1 = 0, y2 = 2;               
        float dx = x2 - x1;
        float dy = y2 - y1;

        // Sample noise at smaller intervals
        float s = x / (float)Width;
        float t = y / (float)Height;

        // Calculate our 4D coordinates
        float nx = x1 + Mathf.Cos (s*2*Mathf.PI) * dx/(2*Mathf.PI);
        float ny = y1 + Mathf.Cos (t*2*Mathf.PI) * dy/(2*Mathf.PI);
        float nz = x1 + Mathf.Sin (s*2*Mathf.PI) * dx/(2*Mathf.PI);
        float nw = y1 + Mathf.Sin (t*2*Mathf.PI) * dy/(2*Mathf.PI);

        float heightValue = (float)HeightMap.Get (nx, ny, nz, nw);

        mapData.Data[x,y] = heightValue;
    }
}

I'm currently using spherical coordinates, but the map is distorded at the poles.

\$\endgroup\$
  • \$\begingroup\$ I'd use 3D Perlin for this. When building the map, treat each texel's u,v coordinate as a latitude and longitude. Convert that point to a 3D point on the surface of the sphere, and use the result as input into the 3D Perlin function. This will give you a correctly-distorted texture that will map correctly to a sphere. You can also just do this in the shader, unless you need the map for collision detection, etc. \$\endgroup\$ – 3Dave Jul 30 '18 at 19:07
  • \$\begingroup\$ @3Dave You could post that as an answer. Note though that this will smear the result toward the top & bottom edges of the map (since the entire top/bottom row maps to a single 3D point at each pole). That might be the issue OP describes as "I'm currently using spherical coordinates, but the map is distorted at the poles" \$\endgroup\$ – DMGregory Jul 30 '18 at 19:57
  • \$\begingroup\$ @DMGregory Sure, but when you do this, the lat/long of the north and south poles will be the same across the width of the map, so you get the same point in Perlin space. There's less unique data towards the top and bottom of the map, which makes sense since their are few triangles (hopefully) in that area. (I realize you know this stuff very well, just clarifying.) I'll post an answer later if I get time, and no one else bothers. \$\endgroup\$ – 3Dave Jul 30 '18 at 20:00
  • 1
    \$\begingroup\$ @NereidRegulus To be clear - are you displaying this flat (on a plane / quad) or on a sphere? If flat (overhead view for instance), you could use the same method, but on a cylinder instead of a sphere. That will get you wrapping in one direction, at least. But, Perlin space doesn't really wrap. \$\endgroup\$ – 3Dave Jul 31 '18 at 13:55
  • 1
    \$\begingroup\$ Note that the wrapping pattern shown in the tiling diagram isn't really "just like a sphere." Because there's a mirror-flip in the tiling pattern, the resulting topology is non-orientable. If we were to draw a spinning plate on the map, the direction of spin would depend on which part of the tiling we were looking at - in some it spins clockwise, and in others it spins counter-clockwise. That's not the case for the sphere, which has a well-defined normal direction, such that we can orbit the sphere as many times as we want & still agree on which direction that plate on the surface is spinning. \$\endgroup\$ – DMGregory Jul 31 '18 at 15:54
7
\$\begingroup\$

For this particular mapping, I'd stick to 2D Perlin noise.

To recap, 2D Perlin noise works by...

  • dividing space into square cells, and examining the one cell our sample point falls inside
  • picking a pseudorandom gradient vector at each corner of the square cell
    (in a consistent way, so repeated samples in the same vicinity all agree)
  • interpolating the four gradient vectors according to our sample position inside the cell

Perlin noise diagram via http://www.angelcode.com/dev/perlin/perlin.html

So, to get clean tiling, we need to:

  1. ensure our sampling grid is aligned with the edges of the map (ie. there's an integer number of sampling grid cells across the map vertically & horizontally)

  2. choose our gradient vectors in a way that's consistent across tile seams

After that, we can let the rest of Perlin noise run as normal. If the inputs are consistent across the tile seams, then the outputs will be consistent too.

To get consistent gradients across tile seams, we'll insert a remapping step into the gradient selection process, so each corner of our grid gets mapped to a canonical point that matches its counterpart on the other side of the seam. (Note that for the particular mapping scheme shown in the question, we also need to vertically flip the gradients shown in red)

Diagram of remapping scheme

Here I'm choosing to treat the left half of the map as canonical, and remap the top-right, right, and bottom-right edges to match their counterparts on the left.

You can see the effect in this animation that shows a single octave of Perlin noise, cycling between the normal gradient lookup (shows seams at the edges), our corrected wrapping (seamless), and the difference between the two (highlights where the gradients change along the right edge of the tile)

Animated comparison of noise with & without wrapping

So, how do we do that?

Let's say we're given as input a 2D floating point vector, sample, such that 0 <= sample.x <= 2 * height, and 0 <= sample.y <= height, where height is the vertical sampling frequency of the current octave of noise (how many grid cells we want between the top & bottom edges of the map)

Our closest four corners are then initially (clockwise from the bottom-left):

a = (floor(sampleX), floor(sampleY))
b = (     a.x      ,    a.y + 1    )
c = (   a.x + 1    ,    a.y + 1    )
d = (   a.x + 1    ,      a.y      )

An ordinary Perlin Noise would then look something like this:

// Get our sample position within the cell, in the range 0 <= x,y < 1.
Vector2 fraction = sample - a;

// Look up our four pseudo-random vectors for the surrounding corners.
Vector2 gradientA = GetPerlinGradient(a);
Vector2 gradientB = GetPerlinGradient(b);
Vector2 gradientC = GetPerlinGradient(c);
Vector2 gradientD = GetPerlinGradient(d);

// Compute an intensity according to each corner.
float dotA = Dot(gradientA, fraction);
float dotB = Dot(gradientB, fraction - Vector2(0, 1));
float dotC = Dot(gradientC, fraction - Vector2(1, 1));
float dotD = Dot(gradientD, fraction - Vector2(1, 0));

// Interpolate the four intensities according to our sample position:
float bottom = Interpolate(  dotA, dotD, sample.x);
float top    = Interpolate(  dotB, dotC, sample.x);
float middle = Interpolate(bottom,  top, sample.y);

return middle;

We're going to modify this by sticking a wrapping "adapter" function in place of the GetPerlinGradient(a/b/c/d) calls above:

Vector2 GetWrappedPerlinGradient(int2 corner, int height) {

    // We'll use this to track whether we're sampling a mirrored point.
    float flipY = 1f;

    if(corner.x >= height) {
        if(corner.x == 2 * height) {
             corner.x = 0;
        } else if(corner.y == 0 || corner.y == height) {
             corner.x -= height;
             flipY = -1f;
        }       
    }

    Vector2 gradient = GetPerlinGradient(corner);
    // If you like, you can apply an offset here GetPerlinGradient(corner + seed);
    // to generate different maps from the same hash function.        

    gradient.y *= flipY;
    return gradient;
}

Now samples on both sides of the seam will use gradients that are compatible at the edges, resulting in the mapping you're looking for.

Here's an example of terrain generated world map with seamless tiling using this method:

Example world map

\$\endgroup\$
4
\$\begingroup\$

You have conflicting goals. A flat 2D map that wraps along the X & Y axis doesn't map to a sphere, it maps to a torus (donut). To visualize this, imagine you have a sheet of elastic. First, bend it into a horizontal tube. This corresponds to having the Y axis wrap. Next bend it so that the open ends of the tube meet. This corresponds to having the X axis wrap. The result looks something like this:

enter image description here

(taken from: Robert Hanson - Asteroids: What is the shape of your Universe?)

To come at the problem for the other side, consider a mercator projection map of the earth:

enter image description here

As you state, in real life you don't walk off the south pole onto the north pole. But if you use the actual map of the earth & assume X/Y wrapping, that's what would happen. The actual problem is that the topology of a sphere does not have X/Y wrapping. The idea of X/Y wrapping is a convenient fiction perpetuated by video games. I suspect many games use it because it is both easy both for developers to program & for players to understand.

Thus, you can have seamless X/Y wrapping or you can have something that maps to a sphere, but you cannot have both at the same time.

Incidentally, while an X/Y wrapped map doesn't provide north & south poles (because it can't represent a sphere), it does create a north & south equator! By selecting two horizontal lines that are half the image height apart, we can orient them such that one will paint a ring on the north side of the torus & the other will paint a ring on the south. For instance, let's select the top/bottom edge for one line & place the other in the middle:

enter image description here

Then we end up with the following in 3D:

enter image description hereenter image description here

Note: there's a small error in my 3d renderings - the texture is duplicated twice horizontally due to the way my mesh was generated.

\$\endgroup\$
  • \$\begingroup\$ The topology described in the question is different than what you've shown in the answer. Note that every alternating row of tiles is mirrored and offset by a half step. It's still not the same as a sphere (I think it ends up being a non-orientable surface like a Mobius strip, due to the mirroring), but it does have the desired property that north doesn't wrap to south, and it is possible to tile Perlin noise in this space. \$\endgroup\$ – DMGregory Jul 31 '18 at 12:15
  • \$\begingroup\$ @DMGregory I agree, it doesn't address how to achieve the example topology (which you did an excellent job of btw). My read of the question was that OP is trying to get to mutually exclusive properties; as such my intent is to explain that the visually illustrated topology does not & cannot match the verbally described topology. \$\endgroup\$ – Pikalek Jul 31 '18 at 20:21
  • \$\begingroup\$ Ah, my reading was different. I read it as "this tutorial gives X & Y wrapping, which is not what I want. Instead I want X wrapping and Y 'turnaround', where crossing a pole keeps you at the same latitude but the opposite longitude." Reading it that way, explaining the problems with X&Y wrapping is a little redundant, as OP already considered those problems and rejected it in favour of a different tiling scheme for those same reasons. \$\endgroup\$ – DMGregory Jul 31 '18 at 20:41
  • \$\begingroup\$ @DMGregory Hmm, I has thought there might have been some confusion about having north/south poles vs equators & that the X wrap Y turnaround was an error from attempting to reconcile the incompatibility. I've updated to include that; hopefully it's a bit more useful. Thanks for the feedback. \$\endgroup\$ – Pikalek Aug 1 '18 at 3:56
1
\$\begingroup\$

If you just need a repeating background, but don't need it all to fit in the viewport, this will work quite well.

If you consider a rectangle projected on to the surface of a sphere, you can get a pretty neat repeating background.

(Images borrowed from CambridgeInColour.com)

Take a look at this:

enter image description here

and this from math.stackexchange.com (https://math.stackexchange.com/questions/262809/spherical-projection)

enter image description here

Imagine that there is a large sphere floating behind your background. For each pixel in your background image, project a ray onto that imaginary sphere. (Simple ray/sphere intersection, documented all over the web.) At that intersection of the ray and the sphere, sample 3D Perlin space.

Now, here's the trick (if there is one): As your player moves to the right, rotate the sphere (really, rotating the intersection point about the center of the sphere) before sampling.

As the sphere rotates, the effect is the same as if the projected quad is moving across the surface of the sphere, and thus through Perlin space. Since the rectangle will eventually wrap around the sphere in whatever direction you're moving, the background will also repeat.

The larger the rectangle you use, the more distortion / fisheye you'll see near the edges of the viewport.

You could also do this using the Mercator projection method discussed in the comments above rather than generating it dynamically. The key to a good, hardly-distorted output, though, is the projection, and using only a relatively small portion of the sphere at a given time.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.