octaves.html

<style type="text/css">
    canvas.perlin, img {
        max-width: 100%;
        width: auto;
        display: block;
        margin: auto;
    }
    canvas.plasma {
        height: 200px;
    }
    .terrain {
        margin:  auto;
        width: 500px;
        height: 300px;
    }
</style>

If you recall from the [last post](http://cateches.is/post/149353123260/perlin-noise), Perlin noise is a function to generate a gradient noise.  
We can apply frequency and amplitude to it to change its size.  We can also move through it in three dimensions to generate a plasma effect.  Great, you're all caught up.

If at the end of that post you felt unsatisfied because I talked about terrain generation and then all you got was a little blue orb, or if you thought "what's this about octaves?", then this is the post for you.

I should probably disclose that I don't really know what I'm talking about.  I'm not a mathematician or game developer.  I'm just a really curious person who likes to dive into the details on things I don't understand.  I'm sure there are way more efficient ways to do everything I'm talking about.  If you know them, I'd love to hear it.  I'm just presenting naive solutions that I stumble upon by reading other blogs, wikis, and trying it out.

### Octaves

Last time I ended by mentioning octaves.  We're going to talk more about them right now.

If you're not a musician, an octave is the set of eight notes between two tones that are twice (or half) of each other's frequencies [&#x1f50a;](https://en.wikipedia.org/wiki/File:Perfect_octave_on_C.mid).  A4 is a pitch standard that has a frequency of 440Hz.  The A above it has a frequency of 880Hz and the one below it is 220Hz.  All octaves are 8 notes apart.

![all Cs are an octave apart](https://upload.wikimedia.org/wikipedia/commons/thumb/f/ff/Common_Octave_Naming_Systems.png/400px-Common_Octave_Naming_Systems.png)

An octave in Perlin noise is simply two waveforms that have the same twice/half relationship in frequency.  We won't discuss the 6 frequencies in the middle.  If you're frustrated by the use of a term whose etymology is actually a number of subdivisions of distance rather than the distance itself, your frustration is outside the scope of this article.

But let's recall what the world looks like for a moment.  It's kind of a funny shape and we have a [hard time describing it](https://en.wikipedia.org/wiki/Geodetic_datum).  But generally:

  * mountains have a high amplitude and low frequency
  * hills have a medium amplitude and medium frequency
  * plains have an incredibly low amplitude

And if we look at mountains, they're pretty jagged.  They aren't nearly as smooth as a high amplitude/low frequency noise wave.  Up close, they have a pretty tiny frequency/amplitude texture.
Additionally, they usually have foothills that lead up to them.  It's almost like a mountain range is a combination of different wavelengths.

We can effectively add details to very large amplitude waves by adding much smaller amplitude waves to them.  This is typically done by repeatedly applying the noise function with halved amplitudes and periods.

In code it might look like this:

    function octavewave(x, y, z, octaves, period, amplitude) {
        var res = 0;
        for (var i = 0; i &lt; octaves; i++) {
            res += perlin.noise(x / period, y / period, z / period) * amplitude;
            period /= 2;
            amplitude /= 2;
        }
        return res;
    }

So we can take the following waves and sum the values at each point on the x axis...

<canvas id="overlaid-noise" class="perlin"></canvas>

...and they'll look something like this as they move through space:

<canvas id="moving-octaves" class="perlin"></canvas>

Again, it doesn't look like anything in the real world.  Fortunately, we can use that nice roughness to show something that at least looks a little bit like fire and embers.

We can generate an octave and use it to vary an HSV color on both hue _and_ color.

    var noise = octavewave(perlin, x, y, z, 6, freq, 1) + 1.5;
    var base = ((y * image.width) + x) * 4;
    var color = HSVtoRGB((16 + noise*5 -1)/360, 1, 1/ noise / 2)
    image.data[base] = color.r
    image.data[base + 1] = color.g
    image.data[base + 2] = color.b
    image.data[base + 3] = noise * amp

It's a little messy, but it works nicely.

<canvas id="fire-noise" class="perlin"></canvas>

### Three Dimensions

At this point you're probably not terribly pleased with the two dimensional graphs anymore.  Yes, you've seen them.  Yes, you understand how they work.  Let's move on.  Let's go from two dimensions to into three.

There's a very useful library called [three.js](http://threejs.org/) and it makes wireframing a snap.  We can use it to create a plane mesh.  The plane comes with a bunch of vertices because I can specify that it's an NxN grid.  Then we can iterate over those points and set the Y coordinate to the output of the noise function.

If we did this with an octave set, then we can wind up with a rough wireframe like so:

<div id="sixth" class="terrain"></div>

Normally we'd say "TADA" and see each other next post, but I'm actually pretty dissatisfied with this texture.  It's waaay to _uniform_, even with the octaves.  If we're primarily concerned with maps and terrains, what part of the world looks like this?  Where are the plains?  Where would the cities even go?

I'm going to reiterate what I said before about terrain:

  * mountains have a high amplitude and low frequency
  * hills have a medium amplitude and medium frequency
  * plains have an incredibly low amplitude

Mountains should be large, plains should not.  If you generate your map using too high of an amplitude, it's all mountains and boring.  If you use too low of an amplitude, then everything is flat and boring.  

But the world isn't all mountains or plains.
It's almost like there are gradients.

What would be great is if we could actually fluctuate the amplitude throughout the grid so that there could be both mountains _and_ plains.  If only there were a function we knew about that could generate a gradient over a space...

We can use Perlin noise to find a gradient of amplitudes over the plane.  Amplitude should change gradually, so it needs a _yuuuge_ period, but also a decently large amplitude itself (I know, it's turtles all the way down) so that we can wind up with mountains.  So for each point on the grid we can do this:

    var ampl = perlin.noise(vertex.x / 200, 0, vertex.z / 200) * 150;
    vertex.y = octavewave(perlin, vertex.x, 0, vertex.z, 8, 100, ampl);

And that will give us something more like real land.  Look at how nice the plains are next to the hills.  I'd put a city there.

<div id="seventh" class="terrain"></div>

If you liked this or if I'm spreading misinformation, let me know [on twitter](https://twitter.com/cateches).

Huge thanks to [Zeeshan](https://twitter.com/zeeshanlakhani) for proofreading this before I published it.   The code is available as a [gist](https://gist.github.com/samlecuyer/1de52412348728a0782ef3e058ee4f9f)

<script src="https://static.tumblr.com/me6da6z/VIZocbre9/improvednoise.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/three.js/r79/three.min.js"></script>

<script type="text/javascript">
    var ampliod = 100;
    var first = document.getElementById('overlaid-noise');
    drawPoints(first, ampliod, ampliod)
    drawPoints(first, ampliod/2, ampliod/2)
    drawPoints(first, ampliod/4, ampliod/4)

    var fourth = document.getElementById('moving-octaves');
    var ctx = fourth.getContext('2d');
    var fourthZ = 0.5;
    function animFourth(argument) {
        requestAnimationFrame(animFourth)
        fourthZ += 1
        ctx.clearRect(0,0, fourth.width, fourth.height)
        drawOctaveZ(ctx, 256, 100, fourthZ, '#595959');
    }
    requestAnimationFrame(animFourth);
    
    var fifth = document.getElementById('fire-noise');
    var z = 0;
    var delta = 2;
    function animPlasma() {
        requestAnimationFrame(animPlasma)
        z += delta;
        drawPlasma(fifth, 100, 255, z)
    }
    requestAnimationFrame(animPlasma);

    var sixth = document.getElementById('sixth');
    var perlin = new ImprovedNoise();
    drawTerrain(sixth, function(vertex, i) {
            vertex.y = octavewave(perlin, vertex.x, 0, vertex.z, 8, 100, 50)
    })()

    var seventh = document.getElementById('seventh');
    drawTerrain(seventh, function(vertex, i) {
            var ampl = perlin.noise(vertex.x / 200, 0, vertex.z / 200) * 150;
            vertex.y = octavewave(perlin, vertex.x, 0, vertex.z, 8, 100, ampl)
    })()

    // the rest of these are graphing functions

    function drawTerrain(container, heightMap) {
        var worldWidth = 64, worldDepth = 64;

        var scene = new THREE.Scene();
        var camera = new THREE.PerspectiveCamera( 
            60, container.clientWidth / container.clientHeight, 1, 20000
        );
        camera.position.y = 200;
        camera.position.z = -450
        camera.lookAt(scene.position);

        var geometry = new THREE.PlaneGeometry(500, 500, worldWidth-1, worldDepth-1);
        geometry.rotateX(- Math.PI/2);
        geometry.vertices.forEach(heightMap)

        var mesh = new THREE.Mesh(geometry, new THREE.MeshBasicMaterial({
            color: 0x333333,
            wireframe: true
        }));
        scene.add( mesh );

        var renderer = new THREE.WebGLRenderer();
        renderer.setClearColor( 0xffffff );
        renderer.setPixelRatio( window.devicePixelRatio );
        renderer.setSize(container.clientWidth, container.clientHeight);
        container.appendChild(renderer.domElement);

        return function animateTerrain() {
            // requestAnimationFrame(animateTerrain)
            // scene.rotation.y += 0.1;
            renderer.render(scene, camera)
        }
    }

    function drawPoints(canvas, freq, amp) {
        var ctx = canvas.getContext('2d');
    
        var perlin = new ImprovedNoise();
        var points = new Array(canvas.width).fill().map(function (_, x) { return perlin.noise(x/freq, 0, 0.5)});

        ctx.beginPath();
        points.forEach(function (val, i) {
            ctx.lineTo(i, val * amp + (canvas.height/2));
        });
        ctx.stroke();
    }

    function drawOctaveZ(ctx, freq, amp, z, color) {
        var perlin = new ImprovedNoise();
        var canvas = ctx.canvas;
        var points = new Array(canvas.width).fill().map(function (_, x) { 
            return octavewave(perlin, x, 0, z, 8, freq, amp);
        });

        ctx.beginPath();
        points.forEach(function (val, i) {
            ctx.lineTo(i, val + (canvas.height/2));
        });
        ctx.strokeStyle = color;
        ctx.stroke();
    }

    function octavewave(perlin, x, y, z, octaves, period, amplitude) {
        var res = 0;
        for (var i = 0; i < octaves; i++) {
            res += perlin.noise(x / period, y / period, z / period) * amplitude;
            period /= 2;
            amplitude /= 2;
        }
        return res;
    }

    function drawPointsZ(ctx, freq, amp, z, color) {
        var perlin = new ImprovedNoise();
        var canvas = ctx.canvas;
        var points = new Array(canvas.width).fill().map(function (_, x) { return  perlin.noise(x/freq, 0, z)});

        ctx.beginPath();
        points.forEach(function (val, i) {
            ctx.lineTo(i, val * amp + (canvas.height/2));
        });
        ctx.strokeStyle = color;
        ctx.stroke();
    }

    function drawPlasma(canvas, freq, amp, z) {
        var ctx = canvas.getContext('2d');
        var image = ctx.createImageData(canvas.width, canvas.height);    
        var perlin = new ImprovedNoise();

        for (var y = 0; y < image.height; y ++) {
            for (var x = 0; x < image.width; x ++) {
                var noise = octavewave(perlin, x, y, z, 6, freq, 1) + 1.5;
                var base = ((y * image.width) + x) * 4;
                var color = HSVtoRGB((16 + noise*5 -1)/360, 1, 1/ noise / 2)
                image.data[base] = color.r
                image.data[base + 1] = color.g
                image.data[base + 2] = color.b
                image.data[base + 3] = noise * amp
            }
        }

        ctx.putImageData(image, 0, 0);
    }

    // I copied this straight off of StackOverflow
    // http://stackoverflow.com/a/17243070
    function HSVtoRGB(h, s, v) {
        var r, g, b, i, f, p, q, t;
        if (arguments.length === 1) {
            s = h.s, v = h.v, h = h.h;
        }
        i = Math.floor(h * 6);
        f = h * 6 - i;
        p = v * (1 - s);
        q = v * (1 - f * s);
        t = v * (1 - (1 - f) * s);
        switch (i % 6) {
            case 0: r = v, g = t, b = p; break;
            case 1: r = q, g = v, b = p; break;
            case 2: r = p, g = v, b = t; break;
            case 3: r = p, g = q, b = v; break;
            case 4: r = t, g = p, b = v; break;
            case 5: r = v, g = p, b = q; break;
        }
        return {
            r: Math.round(r * 255),
            g: Math.round(g * 255),
            b: Math.round(b * 255)
        };
    }

</script>