Heightmap generation using inverse distance weighting interpolation
This is a simple method to generate decent-looking terrain heightmaps. I used it (with power = 2) for my JS1k 2016 entry. While the algorithm is very straightforward and can be implemented with little code, it has a mn² complexity (where m the number of generators and n² is the number of cells in the heightmap) that may prove CPU-intensive if left unoptimized. This method generates different types of terrain when the weighting power varies, and when it tends to infinity, the heightmap becomes a Voronoï tessellation where each zone is a plateau determined by its generator point's altitude.
We first use a seedable PRNG of acceptable quality (minstd_rand0) to pick a set of generator points from the *[0,1)²* space.
viewof generators = sliders({ seed: {title: 'Seed', min: 1, max: 2147483646, step: 1, value: 1}, nb: {title: 'Nb.', min: 1, max: 200, step: 1, value: 100} }, function(val) { const X = []; const Y = []; const rnd = minstRand0(val.seed); for (let i = 0; i < val.nb; i++) { X.push(size*rnd()); Y.push(size*rnd()); } return {X, Y}; })
size = 512
Then we compute for each cell of the heightmap grid the influence of all the generators over this point's altitude using inverse distance weighting.
viewof heightmap = { const gpu = this ? this.gpu : new GPU(); let render = gpu.createKernel(function(X, Y) { let sw = 0; // sum of all weights let sn = 0; // sum of all weighted heights const nb = this.constants.numPoints; for (let k = 0; k < nb; k++) { const dx = this.thread.x-X[k]; const dy = this.thread.y-Y[k]; const dist2 = dx*dx+dy*dy; sw += nb/dist2; sn += k/dist2; // k/nb = influence of generator k } return sn/sw; }, { output: [size, size], constants: { numPoints: generators.X.length }, loopMaxIterations: 1000 }); const H = render(generators.X, generators.Y); render = gpu.createKernel(function(heightmap) { const val = heightmap[this.thread.x][this.thread.y]; this.color(val, val, val, 1); }, { output: [size, size], graphical: true, }); render(H); const canvas = render.getCanvas(); /*invalidation.then(() => { render.destroy(); gpu.destroy(); });*/ canvas.value = H; canvas.gpu = gpu; return canvas; // Draw active generators /*if (showGenerators) { for (let i = 0; i < nbGen; i++) { let [x, y, z] = generators[i]; z = (z - zOffset/100)*zStretching*w2; let [xc, yc] = iso(x*nb, y*nb); context.beginPath(); context.strokeStyle = 'black'; context.moveTo(xc, yc); context.lineTo(xc, yc-z); context.stroke(); context.beginPath(); context.fillStyle = 'red'; context.arc(xc, yc-z, 2, 0, Math.PI*2, true); context.fill(); } }*/ /*context.canvas.value = H; return context.canvas;*/ }
viewof seaLevel = slider({ title: "Sea level", min: 0, max: 100, step: 0.1, value: 40 })
viewof heightmap2 = { const gpu = this ? this.gpu : new GPU(); let render = gpu.createKernel(function(heightmap, seaLevel) { return Math.max(seaLevel, heightmap[this.thread.x][this.thread.y]); }, { output: [size, size], }); const H = render(heightmap, seaLevel/100); render = gpu.createKernel(function(heightmap) { const val = heightmap[this.thread.x][this.thread.y]; this.color(val, val, val, 1); }, { output: [size, size], graphical: true, }); render(H); const canvas = render.getCanvas(); /*invalidation.then(() => { render.destroy(); gpu.destroy(); });*/ canvas.value = H; canvas.gpu = gpu; return canvas; }
Then we apply shading and raise sea level to obtain some exotic-looking terrain...
viewof sunElevation = slider({ title: "Sun elevation", min: 0, max: 90, step: 0.1, value: 40 })
viewof shade = { const nb = heightmap2.length; const gpu = this ? this.gpu : new GPU(); const sun = sunElevation * (τ / 360); const S = computeShading(heightmap2, [1, 50], [0, -Math.cos(sun), Math.sin(sun)], 0.7, 256); const render = gpu.createKernel(function(H) { const val = H[this.thread.x][this.thread.y]/256; this.color(val, val, val, 1); }, { output: [size, size], graphical: true, }); render(S); const canvas = render.getCanvas(); canvas.value = S; canvas.gpu = gpu; return canvas; }
{ const context = DOM.context2d(width, (width * (3 / 5)) | 0); yield context.canvas; orbitalRenderer(heightmap2, {shade, color: [222, 168, 121]}, [1, 50], context); }
Appendix
τ = 2 * Math.PI
import { minstRand0, sliders, canvas2D, viewofCanvas } from "@ehouais/utils"
import { orbitalRenderer } from "@ehouais/heightmap-rendering-using-a-floorcasting-algorithm"
import { computeShading } from "@ehouais/normals-generation-on-a-heightmap-grid"
import {slider} from "@jashkenas/inputs"
import {formgen} from "@ehouais/form-generator"
GPU = require('https://bundle.run/gpu.js@1.8.1')