31:Ta27,class HilbertCurve { constructor(dimension) { this.dimension = dimension; this.maxM = Math.floor(8 * 8 / dimension); this.maxAxisSize = 1 << this.maxM; } log2(value) { let result = 0; while ((value >>= 1) != 0) { result += 1; } return result; } rol(x, d) { const c = d % this.dimension >= 0 ? d % this.dimension : d % this.dimension + this.dimension; return (x << c | x >>> (this.dimension - c)) & ((1 << this.dimension) - 1); } ror(x, d) { const c = d % this.dimension >= 0 ? d % this.dimension : d % this.dimension + this.dimension; return (x >>> c | x << (this.dimension - c)) & ((1 << this.dimension) - 1); } bit(x, i) { return x >>> i & 1; } gc(i) { return i ^ (i >>> 1); } e(i) { return i == 0 ? 0 : this.gc(((i - 1) >>> 1) << 1); } inverseGc(gc) { let i = gc; let j = 1; while (j < this.dimension) { i ^= gc >>> j; j += 1; } return i; } g(i) { return this.log2(this.gc(i) ^ this.gc(i + 1)); } d(i) { if (i == 0) { return 0; } else if (i % 2 == 0) { return this.g(i - 1) % this.dimension; } else { return this.g(i) % this.dimension; } } t(e, d, b) { return this.ror(b ^ e, d + 1); } inverseT(e, d, b) { return this.t(this.ror(e, d + 1), this.dimension - d - 2, b); } indexAt(m, p) { // FIXME: check m let h = 0; let ve = 0; let vd = 0; for (let i = m - 1; i > -1; i--) { let s = 0; for (let j = 0; j < this.dimension; j++) { s += this.bit(p[j], i) << j; } let l = this.t(ve, vd, s); let w = this.inverseGc(l); ve ^= (this.rol(this.e(w), vd + 1)); vd = (vd + this.d(w) + 1) % this.dimension; h = (h << this.dimension) | w; } return h; } indexAt(p) { let m = this.maxM; return this.indexAt(m, p); } _pointAt(m, h) { // FIXME: check m let ve = 0; let vd = 0; var p = []; for (let i = 0; i < this.dimension; i++) { p.push(0.0); } for (let i = m - 1; i > -1; i--) { let w = 0; for (let j = 0; j < this.dimension; j++) { w += this.bit(h, i* this.dimension + j) << j; } let l = this.inverseT(ve, vd, this.gc(w)); for (let j = 0; j < this.dimension; j++) { p[j] += this.bit(l, j) << i; } ve ^= this.rol(this.e(w), vd + 1); vd = (vd + this.d(w) + 1) % this.dimension; } return p; } pointAt(h) { let m = this.maxM; return this._pointAt(m, h); } }32:[] 2f:{"title":"Hilbert-Curve","cells":[{"id":0,"value":"md`# Hilbert-Curve`","pinned":false,"hidden":false,"mode":"ojs"},{"id":200,"value":"viewof dimension = radio({\n options: [\n { label: '2D', value: 2 },\n { label: '3D', value: 3 },\n ],\n value: 2,\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":119,"value":"viewof m = slider({\n min: 1, \n max: 6, \n step: 1, \n value: 4,\n title: 'm',\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":185,"value":"viewof t = slider({\n min: 0,\n max: 1,\n step: 0.0001,\n precision: 4,\n value: 1,\n title: 't',\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":75,"value":"{\n while(scene.children.length > 0){ \n scene.remove(scene.children[0]); \n }\n \n let points = [];\n \n const s = 1 << m;\n const size = 10.0;\n const scale = size / (s - 1);\n \n let n = Math.pow(s, hilbert.dimension);\n \n for (let i = 0; i < Math.round(n * t); i++) {\n let [x, y, z] = hilbert._pointAt(m, i);\n points.push(new THREE.Vector3(x, y, z).multiplyScalar(scale));\n }\n \n var geometry = new THREE.BufferGeometry().setFromPoints(points);\n \n let material = new THREE.LineBasicMaterial({\n color: 'red',\n });\n \n scene.add(new THREE.Line(geometry, material)\n .translateX(-size / 2)\n .translateY(-size / 2)\n .translateZ(dimension == 2 ? 0 : -size / 2));\n \n renderer.render(scene, camera);\n \n return renderer.domElement;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":193,"value":"md`---`","pinned":false,"hidden":false,"mode":"ojs"},{"id":17,"value":"hilbert = new HilbertCurve(dimension);","pinned":false,"hidden":false,"mode":"ojs"},{"id":9,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":73,"value":"renderer = {\n let renderer = new THREE.WebGLRenderer({antialias: true});\n \n const controls = new THREE.OrbitControls(camera, renderer.domElement);\n invalidation.then(() => (controls.dispose(), renderer.dispose()));\n renderer.setSize(width, height);\n renderer.setPixelRatio(devicePixelRatio);\n \n controls.addEventListener(\"change\", () => renderer.render(scene, camera));\n renderer.render(scene, camera);\n \n return renderer;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":71,"value":"scene = {\n const scene = new THREE.Scene();\n scene.background = new THREE.Color(0xffffff);\n \n return scene;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":69,"value":"camera = {\n let fov = 45;\n let aspect = width / height;\n let near = 0.1;\n let far = 1000;\n \n let camera = new THREE.PerspectiveCamera(fov, aspect, near, far);\n camera.position.set(20, 20, -20)\n camera.lookAt(new THREE.Vector3(0, 0, 0));\n \n return camera;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":67,"value":"height = 600;","pinned":false,"hidden":false,"mode":"ojs"},{"id":65,"value":"THREE = {\n const THREE = window.THREE = await require(\"three@0.99.0/build/three.min.js\");\n await require(\"three@0.99.0/examples/js/controls/OrbitControls.js\").catch(() => {});\n return window.THREE;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":109,"value":"import {radio, slider} from \"@jashkenas/inputs\"","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W32","stdlib":"1","titling":"auto"}