2b:null 2c:["$","title",null,{"children":"Hidden-Line Removal | victor felder | Observable"}] 31:T7a8,md`# Hidden-Line Removal ## On a 2D Canvas, with JavaScript, without Ray Tracing Here are two recent drawings of mine, followed by closeups of both: ![](https://i.imgur.com/lMLGnA7.jpg) ![](https://i.imgur.com/lBkDvcs.jpg) The most notable difference between the two is *hidden-line removal*. On the left, no hidden line. On the right, the lines of which the view would be obstructed by lines in front of them are not removed, as if the imaginary hills depicted were transparent. Hidden-line removal (**hlr** for short) is how we name the procedure used to identify and remove lines that should not be visible to the camera. Although removing hidden lines is something that usually comes up when working in 3D, it can also make sense in plain 2D, without explicit projection. Colored, the lines we would remove from a 3D cube: ![](https://i.imgur.com/eJLM2uo.png) A straightforward way of removing hidden lines would be to implement [ray tracing](https://en.wikipedia.org/wiki/Ray_tracing_(graphics)). A naive implementation could split each line into short segments, shoot an arrow from each segment into the camera and remove it if it hits anything before reaching the camera. That's what I implemented for [this drawing](https://twitter.com/_vhf/status/1207776245221658629/photo/1). Imprecise, very slow, interesting nonetheless. (Note that for this drawing, I rotated my 3D model a little bit after ray tracing. That's why there are these nice 'empty' spots.) In this document I will demo a technique inspired by what [@anvaka](https://twitter.com/anvaka) implemented for [peak-map](https://anvaka.github.io/peak-map/) ([[#1](https://github.com/anvaka/peak-map/blob/225112cef4a149b01d4ada3cc0af1bdf7a3daf6c/src/lib/createHeightMapRenderer.js#L68-L73)] [[#2](https://github.com/anvaka/peak-map/blob/225112cef4a149b01d4ada3cc0af1bdf7a3daf6c/src/lib/createHeightMapRenderer.js#L178-L188)]). It's a fun one because of how simple and efficient it is. `32:T881,{ let height = 300; let ctx = DOM.context2d(width, height); const heightAmplifier = 100; const xDelta = 1; const yDelta = 2; // draw from bottom to top for (let y = height; y >= 0; y -= yDelta) { ctx.beginPath(); ctx.moveTo(0, y); // from left to right for (let x = 0; x < width; x += xDelta) { const heightAtX = heightAt(x, y) * heightAmplifier; // by default we'll draw this line segment let draw = true; /* Check the `n` lines below this one. On the Y axis, this line is at `y`. The line below is therefore at `y + yDelta`. */ for (let n = 1; n <= 20; n++) { const yBelowOffset = n * yDelta; if (y + yBelowOffset > height) { break; // 'y' is greater than the canvas height, it would be off canvas } // Get the height of the Nth line at the same `x` const belowLineHeight = heightAt(x, y + yBelowOffset) * heightAmplifier; /* Now for the tricky conditional. Remember that a higher Y means lower on the Y axis: y x 0 1 2 3 4 5 … 1 2 3 Since we draw the hills by *adding* to `y`, we check that the height we are currently considering drawing is *greater* than the height of a line below. If it is, it would be "behind" (below) some other line ; we don't want it so we exit. To put it differently, if we were drawing horizontal straight lines the current point would be (x,y). To create the 'hills' we do (x,y+height). Since height > 0 and because a greater y means 'closer to the bottom of the canvas', y+height is 'lower' than y. We avoid drawing a 'lower' point behind a 'higher' point. */ if (heightAtX > yBelowOffset + belowLineHeight) { draw = false; break; } } if (draw) { // Well, draw! ctx.lineTo(x, y + heightAtX); } else { // Move to where we would have drawn, we'll pick up from there at the next iteration // on the x axis. ctx.moveTo(x, y + heightAtX); } } ctx.stroke(); } return ctx.canvas; }33:Ta53,{ let height = 300; let ctx = DOM.context2d(width, height); const heightAmplifier = 100; const segments = []; const coils = 200; const rotation = 0; const thetaMax = coils * 2 * Math.PI; const chord = 1; const center = [width / 2, height * 1.5]; let radius = 400; const step = radius / thetaMax; let lastVertice; for (let i = 0, theta = chord / step; theta <= thetaMax; i++) { const away = step * theta; const around = theta + rotation; radius += 0.05; let x = center[0] + Math.cos(around) * away; let y = center[1] + Math.sin(around) * away; let h = heightAt(x, y) * heightAmplifier; x += Math.cos(around); y += h + Math.sin(around); if (i > 0 && y < height + 5) { segments.push({ x0: lastVertice.x, y0: lastVertice.y, x: x, y: y }); } lastVertice = { x, y, h }; theta += chord / away; } const minX = segments.reduce( (acc, segment) => Math.min(acc, segment.x0), Infinity ); const maxX = segments.reduce( (acc, segment) => Math.max(acc, segment.x0), -Infinity ); const minY = segments.reduce( (acc, segment) => Math.min(acc, segment.y0), Infinity ); const maxY = segments.reduce( (acc, segment) => Math.max(acc, segment.y0), -Infinity ); const layersX = []; const range = (maxX - minX) * (_bucketSize / 10000); console.log({ range, maxX, minX, maxY, minY }); // let's draw a single bucket around top/left ctx.fillStyle = 'blue'; ctx.fillRect(minX, minY, range, range); ctx.stroke(); // file segments into layers/buckets segments.forEach(segment => { const midX = (segment.x0 + segment.x) / 2; const indexX = Math.round((midX - minX) * range); if (!(indexX in layersX)) { layersX[indexX] = []; } const midY = (segment.y0 + segment.y) / 2; const indexY = Math.round((midY - minY) * range); if (!(indexY in layersX[indexX])) { layersX[indexX][indexY] = []; } layersX[indexX][indexY].push(segment); }); layersX.forEach((layerX, x) => { layerX.forEach((bucketXY, y) => { // let's find a few buckets below this one const bucketsBelow = [...Array(10).keys()] .map(i => layerX[y + i + 1]) .filter(Boolean); if (bucketsBelow.length > 2) { ctx.strokeStyle = 'green'; } else { ctx.strokeStyle = 'black'; } ctx.beginPath(); for (const segment of bucketXY) { ctx.lineTo(segment.x0, segment.y0); ctx.lineTo(segment.x, segment.y); } ctx.stroke(); }); }); return ctx.canvas; }34:[] 2f:{"id":"71d70409ea819ce6","slug":"hidden-line-removal","title":"Hidden-Line Removal","thumbnail":"8507dd689415a7d40fdf51305e119203cd3c38f713e9f65cea472ef736b4744e","access_level":"public","create_time":"$D2020-03-05T10:58:42.115Z","update_time":"$D2020-03-09T20:36:32.538Z","view_time":null,"first_public_time":"$D2020-03-09T20:27:59.120Z","fork":true,"stars":16,"starred":false,"owner":{"type":"team","id":"05d1812dcc8976d6","login":"vhf","name":"victor felder","avatar_url":"https://avatars-next.observableusercontent.com/dcbbf7d6396d08ca9306aeec9750db071932d173a4332deb357d15546daaac9d","tier":"starter_2024"},"version":1260,"publish_version":1260,"role":null,"authored":false,"authors":[{"type":"individual","id":"ad733cd65dbfe48e","login":"vhf","name":"victor felder","avatar_url":"https://avatars-next.observableusercontent.com/dcbbf7d6396d08ca9306aeec9750db071932d173a4332deb357d15546daaac9d","tier":null}],"members":[{"type":"individual","id":"ad733cd65dbfe48e","login":"vhf","name":"victor felder","avatar_url":"https://avatars-next.observableusercontent.com/dcbbf7d6396d08ca9306aeec9750db071932d173a4332deb357d15546daaac9d","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"subscribed":null,"forks":5,"collection":null,"type":"notebook","body":{"title":"Hidden-Line Removal","cells":[{"id":0,"value":"$31","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":19,"value":"seed = 0 // Date.now()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":89,"value":"viewof values = columns({\n altitude: slider({\n min: 0.001,\n max: 0.1,\n step: 0.005,\n value: 0.02,\n title: \"Altitude\"\n }),\n octaves: slider({\n min: 1,\n max: 5,\n step: 1,\n value: 2,\n title: \"Octaves\"\n })\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":72,"value":"heightAt = (x, y) => {\n // courtesy of https://cmaher.github.io/posts/working-with-simplex-noise/\n let maxAmp = 0;\n let amp = 1;\n let altitude = values.altitude;\n let noise = 0;\n\n for (let i = 0; i < values.octaves; ++i) {\n noise += noise2D(x * altitude, y * altitude) * amp;\n maxAmp += amp;\n amp *= 0.5;\n altitude *= 2;\n }\n noise /= maxAmp;\n\n return noise * 0.5 + 0.5;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":51,"value":"{\n let height = 300;\n let ctx = DOM.context2d(width, height);\n /*\n y\n x 0 1 2 3 4 5 …\n 1\n 2\n 3\n */\n for (let x = 0; x < width; x += 3) {\n for (let y = 0; y < height; y += 3) {\n ctx.fillRect(x, y, 3, 3);\n ctx.fillStyle = `rgba(0, 0, 0, ${heightAt(x, y)}`;\n ctx.save();\n }\n }\n return ctx.canvas;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":129,"value":"{\n let height = 300;\n let ctx = DOM.context2d(width, height);\n const heightAmplifier = 100;\n\n const xDelta = 1;\n const yDelta = 2;\n for (let y = 0; y < height; y += 2) {\n ctx.beginPath();\n ctx.moveTo(0, y);\n for (let x = 0; x < width; x += 1) {\n const heightAtX = heightAt(x, y) * heightAmplifier;\n ctx.lineTo(x, y + heightAtX);\n }\n ctx.stroke();\n }\n return ctx.canvas;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":163,"value":"md`Highlighted here, the spots were hidden lines are most visible (hit F5 to reset the sliders and you should see this right above): ![hills with hidden lines highlighted](https://i.imgur.com/Gw6IokA.png)\n\nThe idea is that instead of drawing from top to bottom, we'll draw from bottom to top. Whenever we are about to draw something that would fall \"behind\" another hill, we'll skip it instead.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":172,"value":"$32","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1202,"value":"md`*(At this point I suggest you reload the page to reset all sliders!)*\n\nWhat about situations where you don't have 'horizontal' lines, for instance a single line spiral?\nIt makes drawing \"from bottom to top\" a bit more complicated but there's always a workaround.\n\nOne idea is to think about the segments, not lines. You can create 'buckets' in which you file the segments. Here I define an array 'layerX' as all segments between \\`x\\` and \\`x + delta\\`. In this layerX, I'll create 'buckets' that will contain all segments in this layer between \\`y\\` and \\`y + delta\\`.\n\nThen for each bucket, I look for N buckets below this one by incrementing the layer index. If there are more than 2 buckets below this one, I draw it in green.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":765,"value":"viewof _bucketSize = slider({\n min: 10,\n max: 70,\n step: 1,\n value: 25,\n title: \"Bucket size\"\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":538,"value":"$33","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":489,"value":"md`## That's it\n\nThis simple algorithmic idea can be used in a variety of contexts. This document only shows a basic implementation using vanilla JavaScript + Canvas but there's more to do with it, for instance the very first drawing above ([this one](https://twitter.com/_vhf/status/1233362928742608896)) is actually a [3D model](https://imgur.com/1y9wo94)! I hide lines that would have a steeper slope than then camera/floor one.\n\nPlease consider following me on [twitter](https://twitter.com/_vhf) and [instagram](https://www.instagram.com/fax_paper/) for more.\n\nI hope you learned something, got inspired by this technique for your own drawings or simply had fun with the sliders.\n\nThanks to [@msurguy](https://twitter.com/msurguy) for *drawing* the peak-map source code to my attention and pushing me to write this!\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":454,"value":"md`And just for fun, let's only draw above a certain threshold…`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":433,"value":"viewof _waterLevel = slider({\n min: 0,\n max: 1,\n step: 0.01,\n value: 0.4,\n title: \"Water Level\"\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":429,"value":"{\n let height = 300;\n let ctx = DOM.context2d(width, height);\n const heightAmplifier = 100;\n\n const xDelta = 1;\n const yDelta = 2;\n for (let y = height; y >= 0; y -= yDelta) {\n ctx.beginPath();\n ctx.moveTo(0, y);\n for (let x = 0; x < width; x += xDelta) {\n const heightAtX = heightAt(x, y) * heightAmplifier;\n let draw = true;\n for (let n = 1; n <= 20; n++) {\n const yBelowOffset = n * yDelta;\n if (y + yBelowOffset > height) {\n break;\n }\n const belowLineHeight = heightAt(x, y + yBelowOffset) * heightAmplifier;\n if (\n heightAtX > (1 - _waterLevel) * 100 ||\n heightAtX > yBelowOffset + belowLineHeight\n ) {\n draw = false;\n break;\n }\n }\n if (draw) {\n ctx.lineTo(x, y + heightAtX);\n } else {\n ctx.moveTo(x, y + heightAtX);\n }\n }\n ctx.stroke();\n }\n return ctx.canvas;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":94,"value":"import { slider, checkbox } from \"@jashkenas/inputs\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":519,"value":"import { columns } from \"@bcardiff/observable-columns\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":4,"value":"makeNoise2D = {\n const OSN = await require('https://bundle.run/open-simplex-noise@2.2.0');\n return OSN.makeNoise2D;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":415,"value":"noise2D = makeNoise2D(seed)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"}],"files":"$W34","stdlib":"1","titling":"auto"}} 30:"$2f:body"