28:null 29:["$","title",null,{"children":"Quad Closest Point | Thomas Oberbichler | Observable"}] 2e:Tca1,{ const scene = three.scene scene.clear() const n = 10 const us = d3.ticks(0, 1, n) const vs = d3.ticks(0, 1, n) { const geometry = new THREE.Geometry() for (const [u, v] of d3.cross(us, vs)) { const xyz = quad(u, v) geometry.vertices.push(new THREE.Vector3(xyz.x, xyz.z, xyz.y)) } for (let i = 0; i < 10; i++) { for (let j = 0; j < 10; j++) { const a = i + j + j * n const b = a + 1 const c = 1 + i + j + n + j * n const d = c + 1 geometry.faces.push(new THREE.Face3(a, b, c)) geometry.faces.push(new THREE.Face3(d, c, b)) } } geometry.computeVertexNormals() const material = new THREE.MeshPhongMaterial({ color: colors.gray, emissive: colors.black, transparent: true, opacity: 0.5, side: THREE.DoubleSide, }) three.scene.add(new THREE.Mesh(geometry, material)) } { const geometryU0 = new THREE.Geometry() const geometryU1 = new THREE.Geometry() const geometryV0 = new THREE.Geometry() const geometryV1 = new THREE.Geometry() for (const v of vs) { const u0 = quad(0, v) geometryV0.vertices.push(new THREE.Vector3(u0.x, u0.z, u0.y)) const u1 = quad(1, v) geometryV1.vertices.push(new THREE.Vector3(u1.x, u1.z, u1.y)) } for (const u of us) { const v0 = quad(u, 0) geometryV0.vertices.push(new THREE.Vector3(v0.x, v0.z, v0.y)) const v1 = quad(u, 1) geometryV1.vertices.push(new THREE.Vector3(v1.x, v1.z, v1.y)) } const material = new THREE.LineBasicMaterial({ color: colors.black, }) three.scene.add(new THREE.Line(geometryU0, material)) three.scene.add(new THREE.Line(geometryU1, material)) three.scene.add(new THREE.Line(geometryV0, material)) three.scene.add(new THREE.Line(geometryV1, material)) } { const min = new THREE.Vector3(range.xmin, range.zmin, range.ymin) const max = new THREE.Vector3(range.xmax, range.zmax, range.ymax) const box = new THREE.Box3(min, max) const helper = new THREE.Box3Helper(box, 0x000000) scene.add(helper) } const spotLight = new THREE.SpotLight(0xffffff) spotLight.position.set(-0, 30, 60) spotLight.castShadow = true spotLight.intensity = 0.6 scene.add(spotLight) const solution = new THREE.Group() three.scene.add(solution) const pointMaterial = new THREE.PointCloudMaterial({ color: colors.red, size: 6, sizeAttenuation: false, }) const lineMaterial = new THREE.LineBasicMaterial({ color: colors.red, }) while (true) { solution.clear() for (const particle of particles) { const sample = particle const cp = closestPoint(quad, sample) const geometry = new THREE.BufferGeometry().setFromPoints([ new THREE.Vector3(sample.x, sample.z, sample.y), new THREE.Vector3(cp.x, cp.z, cp.y), ]) solution.add(new THREE.PointCloud(geometry, pointMaterial)) solution.add(new THREE.Line(geometry, lineMaterial)) particle.update() } three.render() yield three.renderer.domElement await Promises.delay(20) } }2f:T44b,class Particle { constructor (x, y, z, vx, vy, vz) { this.x = x this.y = y this.z = z this.vx = vx this.vy = vy this.vz = vz } static random (v) { function rnd (min, max) { return min + Math.random() * (max - min) } const x = rnd(range.xmin, range.xmax) const y = rnd(range.ymin, range.ymax) const z = rnd(range.zmin, range.zmax) const vx = rnd(-v, v) const vy = rnd(-v, v) const vz = rnd(-v, v) return new Particle(x, y, z, vx, vy, vz) } update (direction='xyz') { if (direction.includes('x')) { this.x += this.vx } if (direction.includes('y')) { this.y += this.vy } if (direction.includes('z')) { this.z += this.vz } if (this.x < range.xmin) { this.vx *= -1 } if (this.y < range.ymin) { this.vy *= -1 } if (this.z < range.zmin) { this.vz *= -1 } if (this.x > range.xmax) { this.vx *= -1 } if (this.y > range.ymax) { this.vy *= -1 } if (this.z > range.zmax) { this.vz *= -1 } } }30:[] 2c:{"id":"098df62ca979c21c","slug":"quad-closest-point","title":"Quad Closest Point","thumbnail":"3ada6f3e43769ee32e2b8676502ca7dba4bf697c928a39558b7c2f63cc9c8c48","access_level":"public","create_time":"$D2021-02-16T08:14:05.860Z","update_time":"$D2021-02-16T23:10:43.110Z","view_time":null,"first_public_time":"$D2021-02-16T16:09:21.751Z","has_unpublished_edits":null,"fork":false,"stars":3,"starred":false,"owner":{"type":"team","id":"63ea0ba327c02e72","login":"oberbichler","name":"Thomas Oberbichler","avatar_url":"https://avatars-next.observableusercontent.com/265b4716883baf8f5978e349384c2921f054e6d4c37507f37a41a09745720cbe","tier":"starter_2024"},"version":413,"publish_version":413,"role":null,"authored":false,"authors":[{"type":"individual","id":"c69ce5b2b338318d","login":"oberbichler","name":"Thomas Oberbichler","avatar_url":"https://avatars-next.observableusercontent.com/265b4716883baf8f5978e349384c2921f054e6d4c37507f37a41a09745720cbe","tier":null}],"members":[{"type":"individual","id":"c69ce5b2b338318d","login":"oberbichler","name":"Thomas Oberbichler","avatar_url":"https://avatars-next.observableusercontent.com/265b4716883baf8f5978e349384c2921f054e6d4c37507f37a41a09745720cbe","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":1,"collection":null,"type":"notebook","body":{"title":"Quad Closest Point","cells":[{"id":0,"value":"md`# Quad Closest Point`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":255,"value":"$2e","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":90,"value":"md`---`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":6,"value":"a = {\n const particle = Particle.random(0.1)\n Object.assign(particle, {x: -2, y: -2, z: -1})\n return particle\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":10,"value":"b = {\n const particle = Particle.random(0.1)\n Object.assign(particle, {x: 1, y: -1, z: 1})\n return particle\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":11,"value":"c = {\n const particle = Particle.random(0.1)\n Object.assign(particle, {x: -3, y: 4, z: 2})\n return particle\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":13,"value":"d = {\n const particle = Particle.random(0.1)\n Object.assign(particle, {x: 2, y: 2, z: 0})\n return particle\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2,"value":"createQuad = (a, b, c, d) => {\n const s = ({x: b.x + c.x - d.x, y: b.y + c.y - d.y, z: b.z + c.z - d.z})\n \n const quad = (u, v) => {\n const q = (u - 1) * (v - 1)\n\n const x = a.x * q + c.x * v + u * (b.x - s.x * v)\n const y = a.y * q + c.y * v + u * (b.y - s.y * v)\n const z = a.z * q + c.z * v + u * (b.z - s.z * v)\n\n return {x, y, z}\n }\n \n quad.d = (u, v) => {\n const q0 = u - 1\n const q1 = v - 1\n \n return [\n [b.x + a.x * q1 - s.x * v, c.x + a.x * q0 - s.x * u],\n [b.y + a.y * q1 - s.y * v, c.y + a.y * q0 - s.y * u],\n [b.z + a.z * q1 - s.z * v, c.z + a.z * q0 - s.z * u],\n ]\n }\n \n return quad\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":86,"value":"quad = createQuad(a, b, c, d)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":180,"value":"closestPoint = (quad, sample) => {\n const cpABCD = quadClosestPoint(quad, sample)\n \n if (0 <= cpABCD.u && cpABCD.u <= 1 && 0 <= cpABCD.v && cpABCD.v <= 1) {\n const pt = cpABCD.point\n pt.iterations = cpABCD.iterations\n return pt\n }\n \n const cpAB = lineSegmentClosestPoint(sample, a, b)\n const cpBD = lineSegmentClosestPoint(sample, b, d)\n const cpCD = lineSegmentClosestPoint(sample, c, d)\n const cpAC = lineSegmentClosestPoint(sample, a, c)\n \n const cp = d3.least([cpAB, cpBD, cpCD, cpAC], result => result.distance)\n console.log(cp)\n console.log([cpAB, cpBD, cpCD, cpAC].map(result => result.distance))\n \n return cp.point\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":33,"value":"quadClosestPoint = (quad, sample) => {\n let u = 0.5\n let v = 0.5\n \n let i = 0\n \n for (; i < 100; i++) {\n const p = quad(u, v)\n const j = quad.d(u, v)\n\n const g = [p.x - sample.x, p.y - sample.y, p.z - sample.z]\n\n const r = [\n j[0][0] * g[0] + j[1][0] * g[1] + j[2][0] * g[2],\n j[0][1] * g[0] + j[1][1] * g[1] + j[2][1] * g[2],\n ]\n \n if (r[0]**2 + r[1]**2 < 1e-6) {\n break\n }\n\n const k = [\n j[0][0]**2 + j[1][0]**2 + j[2][0]**2 + 0.1,\n j[0][0] * j[0][1] + j[1][0] * j[1][1] + j[2][0] * j[2][1],\n j[0][1]**2 + j[1][1]**2 + j[2][1]**2 + 0.1,\n ]\n\n const delta = linearSolve(k, r) \n \n u -= delta[0]\n v -= delta[1]\n }\n \n const point = quad(u, v)\n \n return {u, v, point, distance: distance(point, sample), iterations: i}\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":199,"value":"sub = (a, b) => {\n return {\n x: a.x - b.x,\n y: a.y - b.y,\n z: a.z - b.z,\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":203,"value":"squaredNorm = (v) => {\n return v.x**2 + v.y**2 + v.z**2\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":184,"value":"distance = (a, b) => {\n return squaredNorm(sub(a, b))**0.5\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":45,"value":"linearSolve = ([dxx, dxy, dyy], [dx, dy]) => {\n const det = dxx * dyy - dxy**2\n\n const vx = (dyy * dx - dxy * dy) / det\n const vy = (dxx * dy - dxy * dx) / det\n \n return [vx, vy]\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":176,"value":"lineSegmentClosestPoint = (sample, lineA, lineB) => {\n const v = sub(lineB, lineA)\n const l2 = v.x**2 + v.y**2 + v.z**2\n\n if (l2 < 1e-14) {\n return {t: 0, point: lineA, distance: distance(lineA, sample)}\n }\n\n const o = lineA\n const r = {x: v.x / l2, y: v.y / l2, z: v.z / l2}\n const t = sample.y * r.y - o.z * r.z + sample.z * r.z - o.x * r.x + sample.x * r.x - o.y * r.y\n\n if (t < 0) {\n return {t: 0, point: lineA, distance: distance(lineA, sample)}\n }\n\n if (t > 1) {\n return {t: 1, point: lineB, distance: distance(lineB, sample)}\n }\n\n const point = {\n x: lineA.x + t * v.x,\n y: lineA.y + t * v.y,\n z: lineA.z + t * v.z,\n }\n\n return {t, point, distance: distance(point, sample)};\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":240,"value":"range = ({\n xmin: -4,\n xmax: 4,\n ymin: -4,\n ymax: 4,\n zmin: -4,\n zmax: 4,\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":98,"value":"height = 600","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":249,"value":"particles = d3.range(1, 21).map(i => Particle.random(0.01 * i))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":246,"value":"$2f","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":93,"value":"three = {\n // setup renderer\n \n const renderer = new THREE.WebGLRenderer({antialias: true})\n renderer.shadowMapEnabled = true\n \n // setup camera\n \n const fov = 45\n const aspect = width / height\n const near = 0.1\n const far = 1000\n \n const 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 // setup scene\n \n const scene = new THREE.Scene()\n scene.background = new THREE.Color(0xffffff)\n \n // setup orbit controls\n \n function render () {\n renderer.render(scene, camera)\n }\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', render)\n\n return {\n renderer,\n camera,\n controls,\n scene,\n render,\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":329,"value":"md`---`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":95,"value":"THREE = {\n const THREE = window.THREE = await require(\"three@0.124/build/three.min.js\");\n await require(\"three@0.124/examples/js/controls/OrbitControls.js\").catch(() => {});\n await require(\"three@0.124/examples/js/renderers/CSS2DRenderer.js\").catch(() => {});\n return THREE;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":102,"value":"import {colors} from '@oberbichler/colors'","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":100,"value":"d3 = require('d3@6')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W30","stdlib":"1","titling":"auto"}} 2d:"$2c:body"