2b:null 2c:["$","title",null,{"children":"Boustrophedon curves | Benjamin Schmidt | Observable"}] 31:T59b,md`# Boustrophedon curves As Job van der Zwan says, the [Hilbert curve gets all the glory](https://observablehq.com/@jobleonard/a-simple-algorithm-to-generate-h-curves?collection=@jobleonard/space-filling-curves) when it comes to space filling curves, but other ways of turning one dimension into two have other uses. Hilbert and the H-Curve van der Zwan describes both have especially nice properties, but there are times that the way they wind can be confusing, since often we want to represent a linear ordering. The simplest curves--z-curves, or "quadtree order"--on the other hand, do not guarantee that neighbors in 1-dimensional space will be close in two-dimensional space. A compromise is what I think of as "boustrophedon curves," which includes the first space-filling curve to be discovered, the Peano curve. Every pair of neighboring points are next to each other, but rows and columns are filled in linear order rather than through the more elaborate fractals of a Hilbert curve. There are many different different metrics for assessing the quality of curves, but Peano curves can be quite effective [according to this article](https://arxiv.org/abs/0806.4787) at minimizing the size of bounding boxes. Those authors also note that distending the Peano curve from a square to a rectangle with aspect ratio \`sqrt(3)\` improves locality properties, so I've adopted a similar strategy for the various alterations here. `32:T4cb,md`# Parameters Aside from the number of points, the most important parameter is the number of moves before turning. The simplest case is the [Peano curve](https://en.wikipedia.org/wiki/Peano_curve), composed of units of 3. But Peano is from a general family that can be useful for data visualization that balances between keeping adjacent items together and the intuitive simplicity of moving only in unidirectional straight lines. Although I only show curves with a single turn-ordering in this notebook, it's also possible to intermix any set of odd numbers to fill rectangles (rather than squares). Below are the first few thousand points from a canvas layout where the smallest grouping is 11 points, then 7, 5, 3, and 3. One interesting feature of this mixing is that for any given number of points, it is possible to build a curve where the rectangle Because of imprecisions in floating point arithmetic, some of the numbers above may have minor or major problems. On my Mac, 3 and 7 are broken, while 5 and 9 work--I'm curious if your experience is different. Probably the shader code could be improved to use more ints and fewer floats, although full integer modulo, necessary here, is not possible in webgl 1.0. `33:Ta55,md`# Libraries and other space-filling curves This problem--placing one-dimensional flows into higher-dimensional spaces--happens all the time to people as they encounter logically one-dimensional things in places where it's convenient to wrap into two dimensions. Probably the most obvious example is the flow of text in a book; rather than reading a single long strip of paper, books arrange words in a hierarchy of lines and pages. Text sort of resembles a Z-curve but with more than two letters per line. Z curves are convenient, but less optimal in conserving locality because you periodically sweep back to the beginning of a line. But he earliest forms of writing *did* use a flipped orientation known as [boustrephedon](https://en.wikipedia.org/wiki/Boustrophedon). (See image below). Only as literacy increased to the point where reading became automatic did left-to-right (or right-to-left) because automatic. And these patterns are in certain ways superior--eye movement while reading would be minimized if books were printed on a giant leaf of paper in a Hilbert curve or something. I think of these as Boustrephedon curves because they mediate between the locality-conserving properties of the Hilbert and H-curves and the linear simplicity of S-curves and Z-curves. What's interesting about them is that they tend to occur in the real world. A more complex example than books is the arrangement of library books on shelves, because they include multiple levels of hierarchy: 1. Several books are arranged on each shelf, left to right; 2. Several shelves are arranged into a single bookshelf, top to bottom. In a single shelf, libraries in the English-speaking world generally use left-to-right and top-to-bottom arrangement; but at all larger scales, they use a boustrephedon-like arrangement that resembles. 3. Several bookshelves are arranged into a row; this can be *either* left to right or right to left. 4. Groups of rows are arranged into larger areas; 5. Groups of areas make up a floor of a library; 6. Several floors may make up a single bookstack; 7. Several bookstacks make up a building; 6. In the largest libraries, it may take several buildings to hold the full collection. ## In Regl. The function in regl here only implements the simplest curves possible here, where every rank is the same shape. The vertex shader lays out each number inside an enclosing square from small to large. Some bookkeeping keeps track of when elements of the curve need to be flipped. In certain cases the use of floats rather than integers causes big jumps--probably it would be improved by using ints instead of floats. `34:T5da,grid2 = glsl` /* Here is a GLSL function that calculates MOD accurately with (float) parameters that should be integers: */ // https://stackoverflow.com/questions/33908644/get-accurate-integer-modulo-in-webgl-shader float modI(float a,float b) { float m=a-floor((a+0.5)/b)*b; return floor(m+0.5); } float reposition(float ix, float i, float base, float flip_this, inout float flip_other) { // FML floating point numbers... is why I need 0.5 here. Sometimes it won't be high enough. float rank_in_layer = floor((ix + .5) / (pow(base, i))); if (rank_in_layer == 0.) {return 0.;} float position_on_axis = floor(i / 2.); float position = modI(rank_in_layer, base); float width_of_each = pow(base + u_separation, position_on_axis); if (flip_this == -1.) { position = base - position - 1.; } if (u_boust == 1. && modI(position, 2.) == 1.) { flip_other *= -1.; } return position * width_of_each; } vec2 grid2(float ix, float max_ix) { float x = 0.; float y = 0.; float flip_y = 1.; float flip_x = 1.; for (float i = 17.0; i >= 0.; i -= 1.) { if (modI(i, 2.) == 1.) { x += reposition(ix, i, u_base, flip_y, flip_x); } else { y += reposition(ix, i, u_base, flip_x, flip_y); } } vec2 xy = vec2(x, y) / sqrt(max_ix) / 3.4; return positioner(xy) * vec2(1., -1.); } `35:[{"id":"dfde37d8b3a3174fd9e6d06452fb010c83a8b7a4147d8787a5d3674e9ff59e97a00dc6b15ced3e87d61d29616158540e8d95b0dc18fd977bb341aeb85722480b","href":"https://static.observableusercontent.com/files/dfde37d8b3a3174fd9e6d06452fb010c83a8b7a4147d8787a5d3674e9ff59e97a00dc6b15ced3e87d61d29616158540e8d95b0dc18fd977bb341aeb85722480b","name":"image.png","type":"image/png","lastModified":1614910777621.563,"size":50533}] 2f:{"id":"bca016147e3d6932","slug":"boustrophedon-curves","title":"Boustrophedon curves","thumbnail":null,"access_level":"public","create_time":"$D2021-03-04T17:59:19.866Z","update_time":"$D2021-03-19T21:21:14.135Z","view_time":null,"first_public_time":"$D2021-03-05T15:02:25.654Z","fork":false,"stars":7,"starred":false,"owner":{"type":"team","id":"18bbeceb36c8f564","login":"bmschmidt","name":"Benjamin Schmidt","avatar_url":"https://avatars-next.observableusercontent.com/addc2adb5ec95cc72a64820e4a08488bad5d48d95a895eef85a45b136ed66792","tier":"starter_2024"},"version":863,"publish_version":863,"role":null,"authored":false,"authors":[{"type":"individual","id":"33354ca265b21f01","login":"bmschmidt","name":"Benjamin Schmidt","avatar_url":"https://avatars-next.observableusercontent.com/addc2adb5ec95cc72a64820e4a08488bad5d48d95a895eef85a45b136ed66792","tier":null}],"members":[{"type":"individual","id":"33354ca265b21f01","login":"bmschmidt","name":"Benjamin Schmidt","avatar_url":"https://avatars-next.observableusercontent.com/addc2adb5ec95cc72a64820e4a08488bad5d48d95a895eef85a45b136ed66792","tier":null,"role":"editor"}],"comments":[{"id":"62fe91996113297a","reply_to_id":null,"content":"This is soooo satisfying to watch","create_time":"$D2021-03-06T17:34:42.152Z","update_time":null,"resolved":true,"user":{"type":"individual","id":"d36034ddfb454bdd","login":"jobleonard","name":"Job van der Zwan","avatar_url":"https://avatars-next.observableusercontent.com/808373580aa09723ceabb9cb31d01ea6db287280b59eaa63618e259f5d28dd71","tier":null}},{"id":"1201637c51840f39","reply_to_id":"62fe91996113297a","content":"Although the times the floating point math messes up confuse me all the more...\n\nRegarding your H-curves--I guess that original code you cited, opaque as it is, can produce [x, y] coordinates for an H-curve that might run in webgl? GLSL doesn't support recursion, or--best as I can see--any other form of dynamic looping where the number of loops is set before the program executes. Which makes it a tricky language to program these in.","create_time":"$D2021-03-07T15:13:45.014Z","update_time":null,"resolved":true,"user":{"type":"individual","id":"33354ca265b21f01","login":"bmschmidt","name":"Benjamin Schmidt","avatar_url":"https://avatars-next.observableusercontent.com/addc2adb5ec95cc72a64820e4a08488bad5d48d95a895eef85a45b136ed66792","tier":null}},{"id":"e696f0599ab7cb98","reply_to_id":"62fe91996113297a","content":"I believe it's just an inlined set of iterations, honestly. The paper it was part of describes a recursive tiling algorithm, it would surprise me if they had a code implementation that did not have recursion (or inlined recursion) without also describing that","create_time":"$D2021-03-08T10:58:18.479Z","update_time":null,"resolved":true,"user":{"type":"individual","id":"d36034ddfb454bdd","login":"jobleonard","name":"Job van der Zwan","avatar_url":"https://avatars-next.observableusercontent.com/808373580aa09723ceabb9cb31d01ea6db287280b59eaa63618e259f5d28dd71","tier":null}},{"id":"f253a754f5337956","reply_to_id":"62fe91996113297a","content":"Oh yeah, looking at the code all the y coordinate and x coordinate functions do call themselves when i > 36 or something. Hmm. I do think the flipping strategy in the Hilbert fork of this notebook could probably be adapted for the square H curve in some way.","create_time":"$D2021-03-12T18:01:29.918Z","update_time":null,"resolved":true,"user":{"type":"individual","id":"33354ca265b21f01","login":"bmschmidt","name":"Benjamin Schmidt","avatar_url":"https://avatars-next.observableusercontent.com/addc2adb5ec95cc72a64820e4a08488bad5d48d95a895eef85a45b136ed66792","tier":null}},{"id":"67ee1202bbbb6565","reply_to_id":"62fe91996113297a","content":"I just realized: my implementation effectively produces a vector field - a Uint8Array representing the grid and for every point in space it says to which neighbor the curve will step. You could try using that as a uniform input - so generate the tiling on the CPU just once, feed the output to webgl, do something with a shader to interpret that vector field. Could that work?","create_time":"$D2021-03-15T10:36:37.685Z","update_time":null,"resolved":true,"user":{"type":"individual","id":"d36034ddfb454bdd","login":"jobleonard","name":"Job van der Zwan","avatar_url":"https://avatars-next.observableusercontent.com/808373580aa09723ceabb9cb31d01ea6db287280b59eaa63618e259f5d28dd71","tier":null}},{"id":"b83a810ea8cc7144","reply_to_id":"62fe91996113297a","content":"I've been thinking about another strategy for implementing the H curve that I think ought to work, but I simply have trouble tracking the rotations. Here's a notebook that explains the idea in canvas--the webgl code just produces a tangle of spaghetti at the moment. Basically the idea is that if you fill out only half the square, the H-curve neatly subdivides into a set of L shapes. https://observablehq.com/d/cf69b572eb172e6e. \n\nHalf the points are flipped only in 1d, and only the other half have a full 2d range of motion.\n\nI suspect there's an implication in there for what a 3d H-curve would look like as well, though I can't quite see it.","create_time":"$D2021-03-15T17:00:23.848Z","update_time":null,"resolved":true,"user":{"type":"individual","id":"33354ca265b21f01","login":"bmschmidt","name":"Benjamin Schmidt","avatar_url":"https://avatars-next.observableusercontent.com/addc2adb5ec95cc72a64820e4a08488bad5d48d95a895eef85a45b136ed66792","tier":null}},{"id":"ede2a44b321afb53","reply_to_id":"62fe91996113297a","content":"> I simply have trouble tracking the rotations. \n\nOof, I feel you. I basically was stuck with implementing the curve until I came up with the method that I used because of the necessary rotations. The approch that you're working on is a lot closer to the method in the original paper actually!","create_time":"$D2021-03-15T17:07:37.659Z","update_time":null,"resolved":true,"user":{"type":"individual","id":"d36034ddfb454bdd","login":"jobleonard","name":"Job van der Zwan","avatar_url":"https://avatars-next.observableusercontent.com/808373580aa09723ceabb9cb31d01ea6db287280b59eaa63618e259f5d28dd71","tier":null}},{"id":"29757adf8d5349fe","reply_to_id":"62fe91996113297a","content":"OK, got it! https://observablehq.com/@bmschmidt/webgl-h-curve Not that I entirely understand how. My impression of that code from the original is that they lay out many more points than they need to, probably both for performance but also maybe to avoid some of the low level description of what's going on in that shape.","create_time":"$D2021-03-19T16:36:06.565Z","update_time":null,"resolved":true,"user":{"type":"individual","id":"33354ca265b21f01","login":"bmschmidt","name":"Benjamin Schmidt","avatar_url":"https://avatars-next.observableusercontent.com/addc2adb5ec95cc72a64820e4a08488bad5d48d95a895eef85a45b136ed66792","tier":null}}],"custom_thumbnail":false,"trashed":false,"subscribed":null,"forks":2,"collection":{"id":"a4842740b17d6109","slug":"space-filling-curves-in-webgl","title":"Space filling curves in WebGL","owner":{"id":"18bbeceb36c8f564","login":"bmschmidt","name":"Benjamin Schmidt"}},"type":"notebook","body":{"title":"Boustrophedon curves","cells":[{"id":0,"value":"$31","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":10,"value":"viewof regl = {\n let div = DOM.canvas(width * .75, width * .75 / Math.sqrt(ordinality));\n let regl = wrapREGL(div);\n div.value = regl;\n return div;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":20,"value":"canvas = {\n // This actual canvas is shunted to regl to use as the colorscale texture, which is kinda nifty.\n // const width = 512\n const canvas = DOM.canvas(width, 20)\n const ctx = canvas.getContext(\"2d\")\n for (let i = 0; i < width; i++) {\n ctx.fillStyle = d3.interpolateSinebow(i/width)\n\n ctx.fillRect(i, 0, 1, 20) \n }\n return canvas\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":772,"value":"{\n if (animate.length) {\n set(viewof n_points_log, 5 * (2 + Math.sin(now/3000)))\n yield md`${d3.format(\",\")(n_points)} points`\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":753,"value":"viewof primitive = Radio([\"points\", \"line strip\"],{value: \"line strip\", label: \"WebGL Primitive\"})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":783,"value":"viewof animate = Checkbox([\"Animate?\"], {value: [\"Animate?\"]})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":260,"value":"viewof n_points_log = Range([0, Math.log(8_000_000)], {label: \"Number of points (log)\", value: Math.log(15627 * 5 * 7.3)})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":591,"value":"viewof padding = Range([-.1, 2], {step: .05, value: .25, label: \"Padding between cell groups\"})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":558,"value":"viewof ordinality = Radio([3, 5, 7, 9, 11], {value: 5, label: md`**Moves before turn** (only odd numbers allow turns?)`, step: 1})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":576,"value":"viewof order = Radio([\"Boustrephedon\", \"Z-order\"], {label: md`**Edge strategy** Snake back and forth, or snap back a row?`, value: \"Boustrephedon\"})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":724,"value":"$32","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":728,"value":"FileAttachment(\"image.png\").image()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":710,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":613,"value":"html`

Example of Boustropheon writing from Wikipedia

$\"Boustrophedon.svg\"$
By User:Zeimusu, CC BY-SA 3.0, Link

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":471,"value":"n_points = Math.floor(Math.exp(n_points_log))","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":620,"value":"md`# WebGL implementation.\n\nThis implementation is a little ad-hoc; I just hard code in that there will be 17 loops, because 3**17 seems like more points than anyone could reasonably lay out.\n\nAlthough this particular code assumed that all blocks are the same size, a language that facilitates indexing arrays can have different baskets of sizes.\n\n`","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":703,"value":"3**17","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":136,"value":"$34","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":51,"value":"vertex_shader = glsl`\n precision highp float;\n\n attribute float ix;\n\n uniform float u_time;\n uniform float u_boust;\n uniform float u_max_ix;\n uniform float tick;\n uniform sampler2D u_color_buffer;\n uniform float u_separation;\n uniform float u_base;\n varying vec4 fill;\n\n vec2 positioner(vec2 fracts) {\n return 1.95 * vec2(fracts.x - .5, fracts.y - .5);\n }\n\n ${grid2.value}\n\n void main() {\n vec2 pos = grid2(ix, u_max_ix);\n gl_Position = vec4(pos.x, pos.y, 0., 1.);\n gl_PointSize = 2.;\n\n float prop_through = ix / u_max_ix;\n float offset = -fract(u_time / 5.);\n fill = texture2D(u_color_buffer, vec2(fract(offset + ix/u_max_ix), 0.5));\n }\n `","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":12,"value":"aspect_ratio = 1","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":512,"value":"3 * 5 * 5 * 5","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":516,"value":"{\n const numbers = []\n const fives = 0;\n const threes = 0;\n const sevens = 0;\n for (let i of d3.range(10)) {\n const i_ = 3 ** i\n for (let j of d3.range(8)) {\n const j_ = 5 ** j\n for (let k of d3.range(6)) {\n const k_ = 7 ** k\n numbers.push([i_ * j_ * k_, [i, j, k]])\n }\n }\n }\n numbers.sort((a, b) => a[0] - b[0])\n return numbers\n}\n ","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":83,"value":"{\n const tick = regl.frame(({time}) => {\n // clear contents of the drawing buffer\n regl.clear({\n color: [0, 0, 0, 0],\n depth: 1\n })\n drawPoints({})\n // draw a triangle using the command defined above\n })\n invalidation.then(() => tick.cancel())\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":58,"value":"fragment_shader = glsl`\n precision mediump float;\n varying vec4 fill;\n\n void main() {\n gl_FragColor = fill;\n }\n `","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":73,"value":"","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2,"value":"drawPoints = {\n const regl_params = {\n depth: { enable: false },\n stencil: { enable: false },\n blend: {\n enable: true,\n func: {\n srcRGB: 'one',\n srcAlpha: 'one',\n dstRGB: 'one minus src alpha',\n dstAlpha: 'one minus src alpha',\n },\n },\n frag: fragment_shader.value,\n vert: vertex_shader.value,\n attributes: {\n ix: {\n buffer: points,\n stride: 4,\n offset: 0\n },\n },\n uniforms: {\n tick: ({ tick }) => tick,\n u_max_ix: n_points,\n u_boust: order == \"Boustrephedon\" ? 1 : 0,\n u_time: regl.context(\"time\"),\n u_aspect_ratio: aspect_ratio,\n u_color_buffer: colorscheme,\n u_separation: padding,\n u_base: ordinality,\n },\n // specify the number of points to draw\n count: n_points - 1,\n\n // specify that each vertex is a point (not part of a mesh)\n primitive\n }\n\n return regl(regl_params)\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":34,"value":"md`# Create a colorscheme`","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":44,"value":"load_time = Date.now()","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":41,"value":"points = regl.buffer(vals)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":543,"value":"vals = {\n return d3.range(0, 8000000)\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":16,"value":"colorscheme = regl.texture(canvas)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":5,"value":"wrapREGL = require('regl')","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":7,"value":"import { glsl } from \"@stwind/glsl-chunk-tag\";","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":17,"value":"d3 = require(\"d3@v6\")","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":463,"value":"import {Button, Checkbox, Toggle, Radio, Range, Select, Text, Textarea, Search, Table} from \"@observablehq/inputs\"\n","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":770,"value":"import { set } from \"@observablehq/synchronized-inputs\"","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"}],"files":"$W35","stdlib":"1","titling":"auto"}} 30:"$2f:body"