fbm
2024-09-30 00:02:18

Intro

  • fBM stands for Fractional Brownian Motion. But before we talk about nature, fractals and procedural terrains, let’s get a bit theoretical for a moment.

  • A Brownian Motion (BM), without the “fractional” part, is a motion where the position of a given object over time changes in random increments (imagine a sequence of “position+=white_noise();”). Formally, BM is the integral of white noise. These movements define paths that are random yet (statistically) self similar, ie, a zoomed-in version of the path resembles the whole path.

  • A Fractional Brownian Motion is a similar process in which the increments are not completely independent from each other, but there’s some sort of memory to the process. If the memory is positively correlated, changes in a given direction will tend to produce future changes in the same direction, and the path will then be smoother than a vanilla BM. 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. The parameter that controls the behavior of the memory or the integration, and therefore the self-similarity, its fractal dimension and its power spectrum is called the Hurst Exponent, and it’s usually abbreviated as H. Mathematically speaking, H allows us to integrate white noise only partially (say, perform 1/3 of an integral, hence the “Fractional” part in the name) to design fBMs for any memory characteristics and visual look that we desire. In fact, H takes values between 0 and 1, describing rough and smooth fBMs respectively, where the normal BM happens for H=1/2.

  • Now, that’s all very theoretical, and not how us computer graphics folks generate fBM, but I wanted to describe it because it is important to keep its qualities in mind even when doing graphics. Let’s see how:

  • As we know, self-similar structures that are also random are very useful for modeling all sort of natural phenomena procedurally, from clouds to mountains to bark textures. It is intuitively evident that shapes in nature can be decomposed in few big shapes that describe the overall form, and a larger number of medium size shapes that distort the basic contour or surface of the initial shape, and even many more even smaller shapes that add extra detail to the contour and shape of the previous too. This incremental way of adding detail to an object, which allows for an easy way to band limit our shapes for the purposes of LOD (Level Of Detail) and filtering/antialiasing, is an easy one to code and produce visually stunning results. Because of that, it is widely used in films and games. However I believe fBM is not necessarily a well understood mechanism. So this article describes how it functions and their different spectral and visual characteristics for various values of their main parameter H, backed with some experiments and measurements.

    翻译

fBM代表分数布朗运动（Fractional Brownian Motion）。但在我们讨论自然、分形和程序化地形之前，让我们先进行一些理论性的讨论。

布朗运动（BM），没有“分数”部分，是一种物体随时间变化的位置以随机增量变化的运动（想象一个“位置+=白噪声();”的序列）。形式上，BM是白噪声的积分。这些运动定义的路径是随机的，但在统计上是自相似的，即路径的放大版本类似于整个路径。分数布朗运动是一种类似的进程，其中的增量并不完全独立，但过程中存在某种记忆。如果记忆是正相关的，那么在给定方向上的变化将倾向于产生相同方向的未来变化，路径将比普通的BM更平滑。如果记忆是负相关的，正变化很可能会被负变化所跟随，路径将更加随机。控制记忆行为或积分的参数，从而控制自相似性、分形维数和功率谱的，称为赫斯特指数（Hurst Exponent），通常缩写为H。从数学上讲，H允许我们仅部分地积分白噪声（比如说，执行1/3的积分，因此名字中有“分数”部分），来设计具有任何记忆特征和视觉外观的fBM。实际上，H的取值在0到1之间，分别描述了粗糙和平滑的fBM，其中正常的BM发生在H=1/2时。

现在，这些都是非常理论性的内容，并不是我们计算机图形学领域的人们生成分数布朗运动的方式，但我之所以要描述它，是因为即使在进行图形设计时，保持其特性在心中也是非常重要的。让我们看看如何操作：

众所周知，自相似且随机的结构对于程序化地模拟各种自然现象非常有用，比如云层、山脉和树皮纹理等。直观上很明显，自然界中的形状可以分解为几个大的形状来描述整体形态，以及更多的中等大小的形状来扭曲初始形状的基本轮廓或表面，甚至是更多的更小的形状来为前两者的轮廓和形状添加额外的细节。这种逐步向对象添加细节的方式，允许我们轻松地为LOD（细节层次）和过滤/抗锯齿的目的对形状进行带限制，是一种易于编码且能产生视觉震撼效果的方法。因此，它在电影和游戏中被广泛使用。然而，我相信分数布朗运动并不一定是一个被很好地理解的机制。所以，本文描述了它的工作原理以及其主要参数H的不同值的光谱和视觉特性，辅以一些实验和测量。

Basic Idea

  • The way fBMs are constructed normally (there are multiple methods) is to invoke deterministic and smooth randomness through some noise function of our choice (value, gradient, cellular, voronoise, trigonometric, simplex, …, you name it, the choice doesn’t matter much), and then construct self-similarity explicitly with it. The fBM does this by starting with a basic noise signal and continuously adding smaller and smaller detailed noise invocations to it. Something like this:

    翻译

分数布朗运动通常是通过调用我们选择的某种噪声函数（值噪声、梯度噪声、细胞噪声、Voronoi噪声、三角函数噪声、Simplex噪声……你随便说，选择并不重要），然后显式地用它来构建自相似性。fBM通过从一个基本噪声信号开始，不断地向其添加越来越小的细节噪声调用来实现这一点。类似于这样：

1
2
3
4
5
6
7
8
9
10
11
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;
}

  • This is the purest form of fBM. Each noise() signal (or “wave”), of which we have “numOctaves”, gets additively combined with the running total, but it gets compressed horizontally by two effectively reducing its wavelength by two as well, and its amplitude gets reduced exponentially. This accumulation of waves with coordinated reduction of wavelength and amplitude is what produces self-similarity like that seen in nature. After all, in a given space, there’s room for just a few big shape changes but there’s naturally room for a lot and a lot of tiny ones. Sounds pretty reasonable. In fact, these kind of Power-Law behaviors are found everywhere in nature.

  • The first thing you might have noticed is that the code above doesn’t completely look like most fBM implementations you might have seen in Shadertoy and other code snippets around. This following code is equivalent to the one bove, but is far more popular because it avoids the expensive pow() functions:

    翻译

这是fBM的最纯粹形式。每个noise()信号（或者说“波”），我们有“numOctaves”个，会加性地与运行总数结合，但它的水平被压缩了两倍，有效地减少了它的波长两倍，其振幅也呈指数级减少。这种波的积累，配合波长和振幅的协调减少，是产生自然中所见的自相似性的原因。毕竟，在给定的空间内，只有几个大的形状变
化的空间，但自然地有很多、很多微小的变化的空间。听起来相当合理。事实上，这种幂律行为在自然界中无处不在。

你可能首先注意到的是，上面的代码并不完全像你在Shadertoy和其他代码片段中看到的大多数fBM实现。下面的代码与上面的代码等效，但更受欢迎，因为它避免了昂贵的pow()函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
float fbm( in vecN x, in float H )
{    
    float G = exp2(-H);
    float f = 1.0;
    float a = 1.0;
    float t = 0.0;
    for( int i=0; i<numOctaves; i++ )
    {
        t += a*noise(f*x);
        f *= 2.0;
        a *= G;
    }
    return t;
}

  • So let’s talk about “numOctaves” first. Since each noise is half the wavelength of the previous one (or twice the frequency), the term for what otherwise should have been “numFrequencies” is replaced by “numOctaves” as a reference to the musical term where a separation of one octave between two notes corresponds to doubling the frequency of the base note. Now, fBMs can be constructed by incrementing the frequency of each noise by something different than two. In that case the term “octave” wouldn’t be technically correct anymore, but I’ve seen people use it regardless. There are cases where you might even want to create waves/noise of frequencies that increase at constant linear rate rather than geometrically, like in an FFT (which can be used indeed to generate periodic fBMs(), which can be useful for ocean textures). But, as we’ll later see in this article, for most base noise() functions we can actually increment frequencies in multiples of two, which means we only need a very few iterations, and still get good looking fBMS. In fact, synthetizing the fBM one octave at a time allows us to be very efficient - for example with just 24 octaves/iterations we can create and fBM that covers the whole planet Earth and provides details of just 2 meters. Doing the same with linearly increasing frequencies would take a few orders of magnitude more iterations.

  • One last note on the sequence of frequencies is that moving from a fi=2i approach to a fi = 2⋅fi-1, gives us some flexibility regarding the frequency doubling (or wavelength halving) - we can easily unroll the loop and detune each octave slightly by replacing 2.0 by 2.01, 1.99 and similar values, such that the zeros and peaks of the different noise waves we are accumulating don’t superspose exactly, which can sometimes creates unrealistic patterns. In the case of 2D fBM one can also rotate the domain a bit besides stretching it by an octave.

  • Now, in this new code implementation of fBM(), not only we’ve replaced the frequency generation from a power based formulation to an iterative process, but we’ve replaced the exponential amplitude decay as well, the Power Law, with a geometric series driven by a “gain” factor G. One needs to convert from H to G by doing G=2-H which you can derive easily from the first version of the code. However more often than not graphics programmers ignore or don’t even know about the Hurst exponent H, and only work with values of G directly. Since we know H goes from 0 to 1, G goes from 1 to 0.5. And indeed, G=0.5 is what most people have hardcoded into their fBM implementations. This hardcoding isn’t as flexible as leaving G variable, but there’s a good reason to do so, and we are about to see why.

    翻译

让我们先谈谈“numOctaves”。由于每个噪声的波长是前一个的一半（或者说频率是前一个的两倍），原本应该是“numFrequencies”的术语被“numOctaves”所取代，这是参照音乐术语，其中两个音符之间相差一个八度对应于将基础音符的频率加倍。现在，fBM可以通过以不同于两倍的频率递增来构建。在这种情况下，“八度”这个词在技术上就不再正确了，但我看到人们无论如何都在使用它。有些情况下，您甚至可能想要创建频率以恒定线性速率增加而不是几何级数增加的波/噪声，就像在FFT中一样（这确实可以用来生成周期性的fBM，这对于海洋纹理非常有用）。但是，正如我们将在本文后面看到的，对于大多数基础噪声()函数，我们实际上可以按二的倍数递增频率，这意味着我们只需要很少的迭代次数，仍然可以得到好看的fBM。事实上，一次一个八度地合成fBM可以让我们非常高效——例如，只需24个八度/迭代，我们就可以创建一个覆盖整个地球的fBM，并提供仅有2米的细节。如果使用线性增加的频率，将需要几个数量级的更多迭代。

关于频率序列的最后一点是，从fi=2i的方法转变为fi = 2⋅fi-1，给了我们一些关于频率加倍（或波长减半）的灵活性——我们可以很容易地展开循环，并通过将2.0替换为2.01、1.99等类似值，稍微调整每个八度，使得我们正在累积的不同噪声波的零点和峰值不完全重叠，这有时会产生不真实的模式。在2D fBM的情况下，除了通过一个八度拉伸它之外，还可以稍微旋转域。

现在，在这个新的fBM()代码实现中，我们不仅已经将频率生成从基于幂的公式替换为迭代过程，而且还将指数振幅衰减，即幂律，替换为由“增益”因子G驱动的几何级数。需要通过G=2-H将H转换为G，这可以从代码的第一版中很容易地推导出来。然而，更常见的情况是，图形程序员忽略或甚至不知道赫斯特指数H，而只直接使用G的值。由于我们知道H的范围是0到1，G的范围就是1到0.5。实际上，G=0.5是大多数人在他们的fBM实现中硬编码的值。这种硬编码没有让G变量那么灵活，但这样做有很好的理由，我们即将看到为什么。

Self Similarity

  • As we mentioned, the H parameter determines the selfimilarity of the curve. This is statistical self-similarity of course. So, in the case of a one-dimensional fBM(), if we horizontally zoom-in in it by a factor of U, how much would we need to zoom in vertically in V to get a curve that “looks” the same? Well, since a=f-H, then a⋅V = (f⋅U)-H = f-H⋅U-H = a⋅U-H, meaning V=U-H. So, if we are zooming in a fBM with a horizontal factor of two, then we’ll need to scale vertically with a factor of 2-H. But 2-H is G! Not coincidentally, when using G to scale our noise amplitudes, we are, by construction, building the self-similarity of fBM with a scale factor of G = 2-H.

    翻译

正如我们提到的，H参数决定了曲线的自相似性。这当然是统计的自相似性。因此，在一维fBM()的情况下，如果我们将它水平放大U倍，那么我们需要将V垂直放大多少才能得到“看起来”一样的曲线？既然a=f-H，那么a⋅V = (f⋅U)-H = f-H⋅U-H = a⋅U-H，意思是V=U-H。因此，如果我们放大一个水平因子为2的fBM，那么我们需要以因子2-H进行垂直缩放。但是2-H是g！并非巧合的是，当使用G来缩放我们的噪声幅度时，我们正在构建fBM的自相似性，缩放因子为G = 2-H。


Left, Brownian Motion (H=1/2) and anisotropic zooming. Right fBM (H=1) and isotropic zooming.

翻译

左，布朗运动(H=1/2)和各向异性变焦。右fBM (H=1)和各向同性缩放。

  • Now, what about our procedural mountains? A naive Brownian Motion has a value of H=1/2, which produces a G=0.707107… This generates a curve which looks like itself when zoomed in anisotropically in X and Y (if it’s a one-dimensional curve). Indeed, for every horizontal zoom factor U we’d need to scale the curve vertically by V=sqrt(U), which is not very natural. However, stock market curves do approach H=1/2 often, since in theory, each increment or decrement in the value of a stock is independent of its previous changes (remember BM is a process with no memory). In practice of course there are some dependencies and these curves are closer to H=0.6.

  • But natural processes have more “memory” into them, and the self-similarity is much more isotropic than that. For example a mountain that is higher is also wider at its base by the same amount, ie, mountains they don’t usually stretch or get thinner. So this suggests G should be 1/2 for mountains - equal zoom in the horizontal and vertical directions. That corresponds to H=1, which suggests mountain profiles should be smoother than a stock market curve. And they are, as we’ll be measuring actual profiles in a few moments later in this article to confirm this. But we do know from experience that G=0.5 produces beautiful fractal terrains and clouds, so G=0.5 is indeed the most popular value of G found in all fbm implementations.

  • But now we have a bit deeper understanding of H, G and fBMs in general. We know that a value of G closer to 1 will make our fBM even wilder than a pure BM, and indeed for G=1, which corresponds to H=0, we get the noisiests of all the fBMs.

  • Now, all these parametrized fBMs functions do have names, such as “Pink Noise” for H=0, G=1 or “Brown Noise” for H=1/2, G=sqrt(2), which are inherited from the field of Digital Signal Processing and well known to people who have sleeping problems. Actually, let’s dive a little bit into DSP and compute some spectral characteristics so we gain more intuitions about fBMs.

翻译

现在，我们的程序山怎么办？一个简单的布朗运动的值为H=1/2，产生G=0.707107…这产生了一条曲线，当在X和Y方向上各向异性放大时，该曲线看起来像它自己(如果它是一维曲线)。事实上，对于每个水平缩放因子U，我们需要通过V=sqrt(U)来垂直缩放曲线，这不是很自然。然而，股票市场曲线确实经常接近H=1/2，因为在理论上，股票价值的每次增加或减少都与其之前的变化无关(记住BM是一个没有记忆的过程)。实际上，当然存在一些相关性，这些曲线更接近H=0.6。

但是自然过程有更多的“记忆”，并且自相似性比这更各向同性。例如，一座更高的山其底部也同样更宽，也就是说，山通常不会伸展或变薄。所以这表明G应该是山的1/2——在水平和垂直方向上相等的缩放。这相当于H=1，这表明山脉轮廓应该比股市曲线更平滑。的确如此，我们将在本文稍后测量实际曲线来证实这一点。但是我们从经验中知道G=0.5会产生美丽的分形地形和云彩，所以G=0.5确实是所有fbm实现中最流行的G值。

但是现在我们对H，G和fbm有了更深入的了解。我们知道，更接近1的G值会使我们的fBM比纯BM更狂野，事实上，对于G=1，对应于H=0，我们得到所有fBM中最嘈杂的。

现在，所有这些参数化fBMs函数都有名称，如H=0，G=1的“粉红噪声”或H=1/2，G=sqrt(2)的“布朗噪声”,它们继承自数字信号处理领域，为有睡眠问题的人所熟知。实际上，让我们深入研究一下DSP，计算一些频谱特性，以便对fbm有更直观的了解。

A Signal Processing look

  • If you think of Fourier analysis, or additive sound synthesis, the fBM() implementation above is similar to that of an Inverse Fourier Transform that is discrete like DFT, although very sparse, and uses a different basic function (basically, it’s very different to an IFT, but bear with me). In fact, you can also generate fBM() and CG terrains and ever ocean surfaces by performing IFFTs, but it gets very costly quickly. The reason is that IFFT works by additively combining sine waves instead of noise waves, and sine waves are not very efficient at filling the power density spectrum, since each sine wave contributes to a single frequency. However, noise functions have wide spectrums that cover long ranges of frequencies with a single wave. Both Gradient Noise and Value noise have such rich and thick spectral density plots. Have a look:

    翻译

如果您想到傅立叶分析或加法声音合成，上面的fBM()实现类似于离散傅立叶逆变换，如DFT，尽管非常稀疏，并使用不同的基本函数(基本上，它与IFT非常不同，但请原谅我)。事实上，你也可以通过执行IFFTs来生成fBM()和CG地形，甚至海洋表面，但这很快就会变得非常昂贵。原因是IFFT通过叠加组合正弦波而不是噪声波来工作，正弦波在填充功率密度谱方面不是很有效，因为每个正弦波都贡献一个频率。然而，噪声函数具有很宽的频谱，用一个单一的波覆盖了很长的频率范围。梯度噪声和值噪声都具有如此丰富和厚的谱密度图。看一看:

  •
    sin value gradient

  • Note how the spectrum of both Value Noise and Gradient Noise have most of the energy concentrated in the low frequencies but are wide - perfect to fill the whole spectrum rapidly with few shifted and rescaled copies. The other problem with sine wave based fBM is that of course it generates repeating patterns which is not desirable most of the times, although it can become handy for generating tiling textures. The one advantage of sin() based fBM() is that it is super performant, since trigonometric functions run much faster in hardware than constructing noise with polynomials and hashes/luts, so sometimes it’s still worth using sin based fBM for performance reasons, even if it produces poor landscapes.

    翻译

请注意，值噪声和梯度噪声的频谱如何将大部分能量集中在低频，但却非常完美，可以用少量移位和重定比例的副本快速填充整个频谱。基于正弦波的fBM的另一个问题是，它当然会生成重复的图案，这在大多数时候是不可取的，尽管它可以方便地生成平铺纹理。基于sin()的fBM()的一个优点是它的性能非常好，因为三角函数在硬件中的运行速度比用多项式和散列/lut构造噪声要快得多，所以有时它还是值得使用基于sin的fBM出于性能原因，即使它会产生较差的景观。

  • Now let’s have a look at the spectral density plots for fBMs of different H values. Pay special attention to the vertical axis labels, since the three graphs are normalized and do not represent the same slopes even if at first glance they all look almost the same. If we call the negative slope of these spectral graphs “B”, then, since these graphics are in log-log scale, the spectrum follows a power law of the form f-B. For this test I am using 10 octaves of regular gradient noise to construct these fBMs below.

    翻译

现在让我们看看不同H值的fbm的谱密度图。请特别注意垂直轴标签，因为这三个图是归一化的，即使乍一看几乎一样，也不代表相同的斜率。如果我们称这些谱图的负斜率为“B”，那么，由于这些图是对数-对数标度的，所以谱图遵循形式为f的幂律-乙。对于这个测试，我使用10个八度的规则梯度噪声来构建下面的fbm。

  •
    G=1.0 (H=0) G=0.707 (H=1/2) G=0.5 (H=1)

  • As we can see, the energy of an fBM with H=0 (G=1) decays at 3db per octave, or basically, inversely to the frequency. This is a power law of f-1 (B=1), and is called Pink Noise. It sounds like rain.

  • An fBM() with H=1/2 (G=0.707) generates a spectrum that decays faster, at 6 db per octave, meaning it has less high frequencies. It does sound indeed deeper, like listening to rain again but from the inside of your room with the window closed. A 6db/Oct decay means the energy is proportional to f-2 (B=2), and this is indeed the characterization of a Brownian Motion in DSP.

  • Lastly, our computer graphics favourite fBM, H=1 (G=0.5), generates a spectral density plot with a 9 db/Octave decay, which means the energy is inversely proportional to the cube of the frequency (f-3, B=3). This is an even lower frequency signal, which corresponds with a process with positively correlated memory as we mentioned in the intro. This kind of signal doesn’t have a name as far as I know, so I am tempted to call it “Yellow Noise” (just because this color isn’t used for some other type of signal). As we know, being isotropic, it models many natural shapes that are self-similar.

翻译

正如我们所看到的，H=0 (G=1)的fBM的能量衰减为每八度3db，或者基本上与频率成反比。这是f-1 (B=1)的幂律，称为粉红噪声。听起来像是要下雨。

H=1/2 (G=0.707)的fBM()产生的频谱衰减更快，为每八度6 db，这意味着它具有更少的高频。它听起来确实更深沉，就像再次听到雨声，但从你关着窗户的房间里传来。6db/Oct衰减意味着能量与f-2成正比(B=2)，这确实是DSP中布朗运动的表征。

最后，我们最喜欢的计算机图形学fBM, H=1 (G=0.5)，生成一个9 db/Octave衰减的谱密度图，这意味着能量与频率的立方成反比(f-3, B=3)。这是一个更低频率的信号，它与我们在介绍中提到的具有正相关记忆的过程相对应。据我所知，这种信号还没有名字，所以我想把它叫做“黄色噪音”(因为这种颜色不用于其他类型的信号)。正如我们所知，由于各向同性，它模拟了许多自相似的自然形状。

alt text

Measuring

  • No, I did some claims about nature being isotropic and therefore being best simulated with yellow noise (H=1). So let’s put them to some form of testing.

  • I’d like to caveat that the following is not a rigorous/scientific experiment, but I want to share it here anyways. What I did was to take photos of mountain chains running parallel to the image plane, to prevent perspective distortion. Then I segmented the images in black and white, and converted the sky-mountain interface into a 1D signal. I then interpreted it as a WAV sound file and computed its frequency plot just as with the synthetic fBM() signals I analyzed earlier. I made sure the images were high enough resolution that the FFT algorithm would have something meaningful to work with.

翻译

不，我做了一些关于自然是各向同性的声明，因此最好用黄噪声(H=1)来模拟。让我们对它们进行一些测试。

我想提醒大家，下面的实验并不是严格的科学实验，但我还是想在这里分享一下。我所做的是拍摄与图像平面平行的山脉，以防止透视失真。然后对图像进行黑白分割，将天山界面转换成一维信号。然后我将其解释为WAV声音文件，并计算其频率图，就像我之前分析的合成fBM()信号一样。我确保图像的分辨率足够高，这样FFT算法就有意义了。

  • The results seem to indicate that, indeed, mountain profiles follow a -9dB/octave frequency distribution, which corresponds with B=-3 or H=1 or G=0.5, or in other words, Yellow Noise.

  • While not a rigorous study, this seems to validates our intuition, and also what we already know from experience as computer graphics programmers, namely that H=1 (G=0.5) produce realistic (isotropic) fractal terrain shapes. But now we just have a better understanding of it, I hope!

翻译

结果似乎表明，确实，山体轮廓遵循 -9dB/八度的频率分布，这与 B=-3 或 H=1 或 G=0.5 对应，换句话说，就是黄色噪声。

虽然这不是一个严格的研究，但这似乎验证了我们的直觉，也验证了我们作为计算机图形程序员从经验中已经知道的东西，即 H=1（G=0.5）能产生真实的（各向同性）分形地形形状。但现在我们对它有了更好的理解，希望如此！

Prev
Next