Fractional Brownian Motion for Terrain Generation | Hacker News Reader

Fractional Brownian Motion for Terrain Generation

iquilezles.org

187 pointssigna1128 comments

If anyone isn't aware of who Iniqo Quilez is, then explore the entire site and follow it up by looking at his work over at Shadertoy (username: iq) and any of his demoscene contributions at http://www.pouet.net and maybe read this fascinating article about his work with Pixar on Brave: http://www.cgw.com/Publications/CGW/2012/Volume-35-Issue-4-J...

Note that Shadertoy could very well crash your browser.

I really wish that their search page had a static thumbnail image version - or if it does, that I could find it.

If you ever need to produce a bunch of FBM or other noise on the cpu fast, these two libraries are handy. They use SIMD instructions to make noise ~3x to ~7x faster than usual.

C++: https://github.com/Auburns/FastNoiseSIMD

Rust: https://github.com/jackmott/rust-simd-noise

For truly high-resolution grids (or big ones I guess), would be nice if it could be generated via GPU.

I'm surprised that he does not mention that, if you can compute FFT really fast, then you can implement all these textures without a loop along the octaves, by simply specifying the spectral decay and using random phases.

do you mean ifft?

yes, but it's the same algorithm

yes but i'm asking about what you were really trying to say - are you trying to say one can generate these textures by specifying a filter (transfer function or whatever you want to call it) with a random phase component? and then take ifft to get the definition in space?

If I understand this correctly, it's not even a matter of using a filter, just a case of summing some random sinusoids with an appropriate weighting for each according to the frequency. You can do this by starting off with noise in the frequency domain and shaping it before doing an iFFT.

Yes, I meant exactly that. You build a spectrum by setting the amplitudes to the desired decay law, and the phases to random. It is an octave/matlab one-liner.

For 1-d time series analysis, the Autoregressive Fractionally Integrated Moving Average is the apparent analog: https://en.wikipedia.org/wiki/Autoregressive_fractionally_in.... "In a fractional model, the [differencing] power is allowed to be fractional, with the meaning of the term identified using the ... formal binomial series expansion"

The code examples have me confused because they return a single sample at a time, but if noise is to have the kind of different characteristics discussed at different scales, individual sample values cannot be independent of previous sample values.

I guess the provided code examples must return values which are ordered somehow by properties of the `noise` function, which must involve some memory of previously given values. But this function is described as:

>some noise function of our choice... the choice doesn't matter much

The nature of that function is really essential, if it has any independent random distribution, the examples will just return values with an independent random distribution that is bell or triangular or spike shaped.

The basic method of creating a sequence which has different variability at difference scales is to create separate random walks, scale (resample) them and then sum them together. This can be optimized by generating the component walks (with different scales) on the fly, but there is no way to create such a sequence on the fly from a function which returns values which are independent of the sequences previous values.

You missed that the noise function is given n-dimensional coordinates as an argument. Rather than picturing an RNG, you can think of it as a texture unit that samples from an n-dimensional image of some noise with certain characteristics.

The order in which sample values are retrieved doesn't matter — of course it doesn't! It's important that fragments (think 'pixels' in case you're wondering what fragments are) can be evaluated independently and in any order, as computing fragments is supposed to be a massively parallel operation.

It this context, you have to throw out the concept of 'previous' sample values and replace it with 'nearby' values.

Thanks, I wasn't clear on what that vector f*x was. So the noise function is mapping pattern values to coordinates, and the SBM function is combining/layering its patterns calculated with different powers at different scales.

Still on the face of it that advice "the choice of noise function doesn't matter much" is tricky, considering "white noise" is mentioned in the intro which takes no coordinates, but white noise walks of different scales can be combined I think to produce a non-white noise walk.

Besides this combining in a loop the same kind of noise/texture with different power over different scales, I would be interested in also varying the kinds of texture that are layered into different scales.

This reminds me of the time I generated (2d) terrain for a game by toggling a random bit every time I computed a new value in the height map. The bit controlled the second derivative of the height map; 1 for +1, 0 for -1. Also every time the terrain height fell outside the clamp bounds, it would "bounce" (its first derivative would switch sign). It produced decent "rocky" terrain for a cave which is what I was going for.

I think there's an error in the first bit of example code:

  float fbm( in vecN x, in float H )
  {    
      float t = 0.0;
      for( int i=0; i<numOctaves; i++ )
      {
          float f = pow( 2.0, float(i) );
          float a = pow( f, -H );
          t += a*noise(f*x);
      }
      return t;
  }

Shouldn't "float a = pow( f, -H );" be "float a = pow( i, -H );"?

Was interesting but a bit over my head honestly. However, I just wanted to make sure no one missed the demo that was linked, because I almost missed it: https://www.shadertoy.com/view/4ttSWf

It's a terrain + trees and other stuff written in about 1000 lines as a shader, using the algorithm described in the article.

> These movements define paths that are random yet (statistically) selfsimilar, ie, a zoomed-in version of the path resembles the whole path

This goes a bit against my intuition of self-similar, but I guess I should interpret "resembles" as *statistically resembles" here as well? Does it mean something like the distribution being the same at all zoom levels?

There is a visual resemblence between zoom levels because of the statistical self-similarity across zoom levels. I suppose the word resemblence was chosen by the author as a less strict variation of the concept. But even the self-similarity of for instance the convergence border of the Mandelbrot set isn't completely self-same either.

Yeah if you were to discretize it, then you'd get random walks with the only difference being the variance of movement from the last point. Wish I could find this one source that talked about continuous time noise processes - it was pretty interesting. If you assign a random variable to every point t on a continuum, it's not a real process (in terms of the definitions set forth in Measure Theory), so you have to use other methods to define them, like limits of discrete processes.

You should read Mandelbrot’s book “the fractal geometry of nature.” He talks quite a bit about ideas like this. It’s written with the intention that non mathematicians can read and understand the ideas too which is kind of neat.

Well yeah, that's the "(statistically) selfsimilar" bit. Random fractals like this aren't self-congruent, just self-resembling.

Someone check my understanding here:

>If the memory is negatively correlated, a positive change will be most likely followed by a negative change, and the path will be much more random.

Wouldn't the path be less random because you're introducing constraints? Perhaps a better phrasing would be "the path will be much more variable"?

Outlining the mountaintop, turning it into audio, and FFTing it is such a neat and simple way to cross examine the central idea.

I feel like a terrible adult for chuckling at the appropriateness of BM as the abbreviation for Brownian Motion.

"smoother than a vanilla BM."

Man, this kind of thing is why I first got into programming.

Reply on news.ycombinator.com