2e:null 2f:["$","title",null,{"children":"Heightmap generation using spatial subdivision algorithm | Philippe Deschaseaux | Observable"}] 34:T46c,viewof terrain = { const H = heightmap.data; const nb = H.length; // Adapt heightmap precision to canvas size const shading = { p1: 10, p2: 4, p3: 80 }; // Prepare terrain array const T = []; for (let i = 0; i < nb; i++) { T[i] = []; for (let j = 0; j < nb; j++) { T[i][j] = Math.max(0, H[i][j] - seaLevel); } } // Generate colormap const C = []; const pow = 1; const mask = ~(pow - 1); for (let i = 0; i < nb; i++) { C[i] = []; let I = i & mask; let max = 0; for (let j = 0; j < nb; j++) { // shading let J = j & mask; if (J == nb - 1) J -= pow; let JJ = J + pow; let d = (nb * (T[I][JJ] - T[I][J])) / pow - shading.p2; let color = shading.p3 / (1 + (d * d) / shading.p1); // shadowing max -= shadow / nb; let h = T[i][j]; if (h < max) { color *= 0.3; } else { max = h; } C[i][j] = Math.floor(color); } } const context = DOM.context2d(width, width / 2); // Render isoFloorCasting(context, T, C, width / 4); context.canvas.value = T; return context.canvas; }35:[] 32:{"id":"18dabf758f1a365c","slug":"heightmap-generation-using-spatial-subdivision-algorith","title":"Heightmap generation using spatial subdivision algorithm","thumbnail":"47c7726d8d7081d3249886632d8ac50ed0ceb1d5936714ec3861e178c46a6b67","access_level":"public","create_time":"$D2018-04-02T09:31:29.558Z","update_time":"$D2024-11-05T13:21:06.322Z","view_time":null,"first_public_time":"$D2018-04-14T11:04:48.420Z","fork":{"id":"89b5932c77eae070","slug":"heightmap-generation-using-diamond-square-algorithm","title":"Heightmap generation using diamond-square algorithm","owner":{"id":"cf2a83be2759e071","login":"ehouais","name":"Philippe Deschaseaux"}},"stars":8,"starred":false,"owner":{"type":"team","id":"cf2a83be2759e071","login":"ehouais","name":"Philippe Deschaseaux","avatar_url":"https://avatars-next.observableusercontent.com/59e97a66cd990ae4d696ee6feb742004d97f024d9bc0db66fbc4b60357d0005f","tier":"starter_2024"},"version":1838,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"7c1eebd3c1c51af1","login":"ehouais","name":"Philippe Deschaseaux","avatar_url":"https://avatars-next.observableusercontent.com/59e97a66cd990ae4d696ee6feb742004d97f024d9bc0db66fbc4b60357d0005f","tier":null}],"members":[{"type":"individual","id":"7c1eebd3c1c51af1","login":"ehouais","name":"Philippe Deschaseaux","avatar_url":"https://avatars-next.observableusercontent.com/59e97a66cd990ae4d696ee6feb742004d97f024d9bc0db66fbc4b60357d0005f","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":1,"collection":{"id":"003a31fb854ae2bf","slug":"procedural-terrain-generation","title":"Procedural terrain generation","owner":{"id":"cf2a83be2759e071","login":"ehouais","name":"Philippe Deschaseaux"}},"type":"notebook","body":{"title":"Heightmap generation using spatial subdivision algorithm","cells":[{"id":2,"value":"md`# Heightmap generation using spatial subdivision algorithm`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":141,"value":"md`This is a [yet](https://beta.observablehq.com/@ehouais/heightmap-generation-using-inverse-distance-weighting-in) [another](https://beta.observablehq.com/@ehouais/heightmap-generation-by-bell-shaped-functions-accumulati) method [again](https://beta.observablehq.com/@ehouais/heightmap-generation-using-diamond-square-algorithm) to generate terrain [heightmaps](https://en.wikipedia.org/wiki/Heightmap). It uses the [spatial subdivision algorithm](http://paulbourke.net/fractals/noise). It is similar to [diamond-square algorithm](https://beta.observablehq.com/@ehouais/heightmap-generation-using-diamond-square-algorithm), but simpler to implement and with less visual artefacts.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":584,"value":"md`We will be using the minstd_rand0 [seedable PRNG](https://en.wikipedia.org/wiki/Linear_congruential_generator#Parameters_in_common_use) for randomness.\n\nN.B: The PRNG would have been better implemented as a [generator](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Guide/Iterators_and_Generators), but this seems to slow down execution too much.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1042,"value":"md`The **spatialSubdivision** function implements an iteration of the algorithm, taking an array of dimension ${tex`N^2`}, where ${tex`N = 2k+1`}, and a randomness function. It interpolates the current values, adds some randomness, and returns an array of dimension ${tex`N'^2`}, where ${tex`N' = 2(2k)+1`}.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":701,"value":"spatialSubdivision = function(H, rnd) {\n const nb = 2*(H.length-1)+1;\n\n const H2 = [];\n // for each cell in new array\n for (let i = 0; i < nb; i++) {\n H2[i] = [];\n let I = i>>1;\n for (let j = 0; j < nb; j++) {\n let J = j>>1;\n // Interpolate current cells\n H2[i][j] = (H[I][J]+H[I+(i&1)][J]+H[I][J+(j&1)]+H[I+(i&1)][J+(j&1)])/4;\n // Add randomness on new cells\n if (i&1 || j&1) H2[i][j] += rnd();\n }\n }\n\n return H2;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1083,"value":"md`Randomness is controlled by two shaping parameters.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1053,"value":"viewof shaping = sliders({\n p1: {min: 0.1, max: 2, step: 0.01, value: 0.5},\n p2: {min: 0.5, max: 2, step: 0.01, value: 1.1}\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1067,"value":"md`We iterate the algorithm step 9 times, starting from a random 2x2 array to finally generate a 513x513 heightmap.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1833,"value":"generateHeightmap = (nbIters, seed, { p1 = 0.5, p2 = 1.1 } = {}) => {\n const prng = minstRand0(seed);\n let H = [\n [prng(), prng()],\n [prng(), prng()]\n ];\n\n // Generate heightmap array\n let f = p1;\n for (let n = 0; n < nbIters; n++) {\n let f2 = 2 * f;\n H = spatialSubdivision(H, function () {\n return prng() * f2 - f;\n });\n f /= 2 ** p2;\n }\n\n const N = H.length;\n console.log(N);\n\n // Compute heightmap stats\n let [min, max] = [+Infinity, -Infinity];\n for (let i = 0; i < N; i++) {\n for (let j = 0; j < N; j++) {\n let h = H[i][j];\n min = Math.min(min, h);\n max = Math.max(max, h);\n }\n }\n\n for (let i = 0; i < N; i++) {\n for (let j = 0; j < N; j++) {\n H[i][j] -= min;\n }\n }\n\n return { heightmap: H, max: max - min };\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1539,"value":"viewof heightmap = {\n const nbIters = 10;\n const { heightmap, max } = generateHeightmap(nbIters, seed, shaping);\n const N = heightmap.length - 1;\n const { context, dispatch } = viewofCanvas(256, 256);\n dispatch({ data: heightmap, hunit: 1, vunit: N / 4 });\n return canvas(context, samplePixel(heightmap, 256 / max));\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1604,"value":"viewof shademap = {\n const { data, hunit, vunit } = heightmap;\n const sun = 15 * (τ / 360); // sun elevation (in radians)\n const sunVector = [0, -Math.cos(sun), Math.sin(sun)];\n const S = computeShading(data, [hunit, vunit], sunVector, 0.7, 256);\n const hmap = { data, hunit, ratio: vunit / hunit };\n const { context, dispatch } = viewofCanvas(256, 256);\n dispatch({ heightmap: hmap, colormap: { data: S } });\n return canvas(context, samplePixel(S));\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1583,"value":"{\n const palette = colorShades([253, 205, 159], 256);\n const colormap = { ...shademap.colormap, palette };\n const dims = [width, Math.floor(width * 0.6)];\n return orbitalCanvas({ ...shademap, colormap }, dims);\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1791,"value":"({\n ...shademap,\n colormap: { ...shademap.colormap, palette: colorShades([253, 205, 159], 256) }\n})","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1740,"value":"html`direct link to this heightmap`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1077,"value":"md`The result is different for each value of the PRNG seed.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1073,"value":"viewof seed = {\n const params = new URLSearchParams(html``.search);\n return slider({\n min: 1,\n max: 2147483646,\n step: 1,\n value: params.has(\"seed\") ? params.get(\"seed\") : 307710644\n });\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":813,"value":"md`Then we apply shading/shadowing and raise sea level to mean altitude to obtain some realistic terrain.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":766,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":768,"value":"viewof shadow = slider({\n min: 0,\n max: 2,\n step: 0.005,\n value: 1\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":578,"value":"viewof seaLevel = slider({\n min: 0,\n max: 1,\n step: 0.01,\n value: heightmap.mean\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1451,"value":"md`As for diamond-square algorithm, biased interpolation generates visual artefacts, visible as sharp ridge lines.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":597,"value":"separator()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1545,"value":"md`## Utilitary functions and dependencies`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1700,"value":"τ = 2 * Math.PI","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":845,"value":"import {\n viewofCanvas,\n canvas,\n separator,\n floor,\n sliders,\n minstRand0,\n zoomAndPan,\n colorShades\n} from \"@ehouais/utils\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1535,"value":"import { orbitalCanvas } from \"@ehouais/heightmap-rendering-using-a-floorcasting-algorithm\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1715,"value":"import {computeShading} from \"@ehouais/normals-generation-on-a-heightmap-grid\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":713,"value":"import {isoFloorCasting, isoFloorCasting2} from '@ehouais/heightmap-rendering-techniques'","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":395,"value":"import {slider} from \"@jashkenas/inputs\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1772,"value":"samplePixel = (S, r = 1) => (i, j) => Array(3).fill(r * S[i * 4][j * 4])","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W35","stdlib":"1","titling":"auto"}} 33:"$32:body"