Outerra forum

Please login or register.

Login with username, password and session length
Advanced search  

News:

Outerra Tech Demo download. Help with graphics driver issues

Author Topic: Noise generation precision  (Read 23447 times)

Stumpeh

  • Newbie
  • Posts: 2
Noise generation precision
« on: January 23, 2011, 08:16:43 am »

Reading through the posts here (particularly this one) has raised a few questions I was hoping you'd be able to clarify. You don't appear to have issues with precision partly because you're using wavelet noise, but mostly because you're accessing the noise using integers rather than floats. My own investigations confirm that, using floats,  wavelet noise appears to be able to return useable values several levels lower than Perlin (where I define each "level" as a 2x zoom into the previous, much as I imagine you're doing if you're representing each planet's faces as six quadtrees). What I'm interested in is how you're indexing the noise using integers alone. From reading between the lines it looks like you split each face into a grid indexed from 0.0 -> 1.0 or 0 -> 0xffffffff in integers (giving you ~2mm accuracy over the surface of an earth sized planet with no tiling). This implies you're using a 0.32 fixed point format but how? Any attempt at mathematics is doomed to overflow, and you're working on the gpu so I'm guessing you're not emulating 64bit ints here as if you were wouldn't it be faster just to use doubles? The only implementation of wavelet noise I can find online expects the face position to be scaled up allowing it to use the integer portion of each component to index into its precalculated table and the fractional portion to modify the weightings placed on that index and its neighbours for the smoothing. You have no integer portion, so how are you choosing where to index, and your fractional portion allows no bit shifting without overflow.

Essentially I'm begging for an explanation/code/pseudocode for "float GetNoiseForPosition(int x, int y, int z)". I just can't figure out how you're doing it and it's driving me mad! :)
Logged

cameni

  • Brano Kemen
  • Outerra Administrator
  • Hero Member
  • *****
  • Posts: 6721
  • No sense of urgency.
    • outerra.com
Noise generation precision
« Reply #1 on: January 23, 2011, 09:45:49 am »

Faces are indexed using signed 32b integers from -2^30 to +2^30, leaving space for overflows.

I think integers can be used in case of Perlin as well, by computing auxiliary coordinates first that are kind of floating with level. In each level you would shift the integer coordinates to the right by 32-8-level bits and mask out the bits above eight lowest bits. Then you compute floating-point coordinates by multiplying with 1.0/256 and pass them further on. Could that work with that algorithm?

With all kinds of coherent noise one is basically computing an interpolated value between some discrete points in space when computing the value for given level, and the coordinates just have to change twice as fast with each level.

Also, we are not using a simple GetNoiseForPosition(int x, int y, int z) function as it has many disadvantages, slowness being just one of them. We are accumulating the noise and caching it so that we can also modify the values or to use height maps for certain levels etc.
Logged

Stumpeh

  • Newbie
  • Posts: 2
Noise generation precision
« Reply #2 on: January 25, 2011, 05:23:35 am »

Having had a good think about it your indexing system it looks rather promising. Thanks! I'll give it a go tonight and report back.

Now you've got me interested in how you're using the noise! I had thought you were simply descending down the levels until you ran out of externally supplied data then creating fractal based heights for each new point using the point's position on the unit cube's face, or some some such system - normal on the world sphere?) scaled by the average height of the bounding parent points, with extra weightings depending on slope, curvature, etc. (as shownhere). How are you actually doing it?

This is all absolutely facinating stuff. I'm very impressed with the results!
Logged

cameni

  • Brano Kemen
  • Outerra Administrator
  • Hero Member
  • *****
  • Posts: 6721
  • No sense of urgency.
    • outerra.com
Noise generation precision
« Reply #3 on: January 25, 2011, 09:43:33 am »

Basically it is indeed more or less like that, and we are also using a couple of techniques to speed it up - like caching the generated values at certain levels to be used as the basis for finer details, so that the more detailed levels do not have to compute all octaves of noise. The system is designed so that it can handle external data or generated noise almost transparently.

Here's an old screenshot from one of predecessors of the algorithm (from 2003), the colored profile curves seen on the right defined how various properties of noise generator changed with the level (X-axis corresponds to the level but the markings show the level size in meters instead). That version didn't handle existing terrain data, it was a pure fractal generator.

Logged

knackered

  • Jr. Member
  • *
  • Posts: 26
Noise generation precision
« Reply #4 on: January 26, 2011, 04:06:11 pm »

so you split a quad tree node, then for each child you bind the parents noise texture, offset it by another set of octaves with the amplitude scaled by half to generate the childs noise texture? etc.etc.?
these noise textures have multiple channels of noise, which you use for different things such as height displacement, tree distribution etc.?
Logged

knackered

  • Jr. Member
  • *
  • Posts: 26
Noise generation precision
« Reply #5 on: January 26, 2011, 04:12:42 pm »

by the way, this is definitely my favourite website in years, and I really do appreciate you contributing so generously to the forums, cameni.
Logged

cameni

  • Brano Kemen
  • Outerra Administrator
  • Hero Member
  • *****
  • Posts: 6721
  • No sense of urgency.
    • outerra.com
Noise generation precision
« Reply #6 on: January 26, 2011, 05:24:03 pm »

Quote from: knackered
so you split a quad tree node, then for each child you bind the parents noise texture, offset it by another set of octaves with the amplitude scaled by half to generate the childs noise texture? etc.etc.?
Well, with wavelets the noise for children can be an independent non-coherent noise, so you only need to get the basis value from parent and add a properly scaled noise value. The amount of scaling halves with each level as usual, but it can be parametrized. That's what the profile curves are about, you can determine the proportions of generated fractal features this way.

Yes, there are multiple channels of noise with different characteristic spectrum, used for multiple things within the engine.
Logged

Edding3000

  • Member
  • **
  • Posts: 93
Noise generation precision
« Reply #7 on: January 27, 2011, 11:09:02 am »

I still dont exactly get it :(.

My algorithms just went from -1 to 1 per cube face and then subdivided over the face.
this leads to precision errors when you get to very deep (16 of something) levels.

Do you use a -1 to + 1 (or 0 to 1) per created child and just add it to the parent or something? I just cant wrap my head around it.

Maybe some pseudo-code?
Logged

cameni

  • Brano Kemen
  • Outerra Administrator
  • Hero Member
  • *****
  • Posts: 6721
  • No sense of urgency.
    • outerra.com
Noise generation precision
« Reply #8 on: January 27, 2011, 02:41:20 pm »

Suppose you have unsigned integer coordinates ranging from 0 to 2³²-1, used to address the location on the face.
The following code is for 1D, using a 1D pregenerated noise texture, but can be easily extended to more dimensions.

Code: [Select]
float interpolated_noise( uint x, uint level )
{
    uint xm = x & (0xffffffffU >> level);    //mask out the bits that would cause repeat in tex lookup
    float c = ldexp(float(xm), level-32);    //convert to 0..1 floating point value

    //use c in noise tex lookup
    float v = texture(noise1D, c).x;

    //could be scaled here as well
    return ldexp(v, -level);
}

Then you just sum up the values for how many levels you need to get the result.

I hope I didn't make a mistake there :)
Logged

knackered

  • Jr. Member
  • *
  • Posts: 26
Re: Noise generation precision
« Reply #9 on: July 25, 2012, 09:02:52 am »

would you call that function on each axis of your face coordinate?
when you talk about face coordinates i'm getting the impression you mean a 2D grid coordinate. Is that not the case?
is this how you see it being used?
vec3f unitVector;   // in range of -1.0 to +1.0
vec3ui intVector = convertFloatToUINT(unitVector);
// intVector now in range 0 to 0xFFFFFFFF
float n = 0.0;
for (int o=0; o<octaves; ++o) {
  n += interpolated_noise(intVector.x, o);
  n += interpolated_noise(intVector.y, o);
  n += interpolated_noise(intVector.z, o);
}
Logged

cameni

  • Brano Kemen
  • Outerra Administrator
  • Hero Member
  • *****
  • Posts: 6721
  • No sense of urgency.
    • outerra.com
Re: Noise generation precision
« Reply #10 on: July 25, 2012, 11:02:53 am »

As I wrote earlier, we aren't using noise function that can give random noise value directly for given coordinates, instead we are aggregating the noise each LOD level and using parent data to compute the children. It's faster that way as it caches the computation results of lower octaves and only performs interpolation and adding of a simple noise layer, and it allows for other things like post-processing the noise values. In that approach we are indeed using 2D face coordinates instead of 3D, but it can be both - the noise layer being added is just a normal noise, and you only have to find a good deterministic way of computing it.

I came up with the code listed above only after everybody presented the same direct function for computing the noise and complained about the precision. So I wondered why people aren't using an integer version that can use more bits for computation. However, my version uses 2D coordinates as the input, I can see it would be simpler for people to use 3D there. Well, it should work as you have described.

Note that I haven't actually tried the code yet, so there may be other issues I could not foresee, but generally it should work.
Logged

knackered

  • Jr. Member
  • *
  • Posts: 26
Re: Noise generation precision
« Reply #11 on: July 25, 2012, 11:05:22 am »

but then how do you get the cubemap edges to match up?
Logged

cameni

  • Brano Kemen
  • Outerra Administrator
  • Hero Member
  • *****
  • Posts: 6721
  • No sense of urgency.
    • outerra.com
Re: Noise generation precision
« Reply #12 on: July 25, 2012, 12:43:53 pm »

Absolute value of face coordinates summed (give the same number on the edges), and inherited height from parent (it's the same on the face edges as well) to break the patterns. But if the face coordinates weren't already used in the lookups to coarse elevation data of the planet it would be probably simpler to use 3D coords instead as the seed to the random permutator.
Logged