2d:null 2e:["$","title",null,{"children":"Free Form Deformation | j.carson | Observable"}] 33:T7c1,md`# Free Form Deformation [Free Form Deformation](https://en.wikipedia.org/wiki/Free-form_deformation) (FFD) is an [old-timey](https://docs.google.com/viewer?url=http%3A%2F%2Ffaculty.cs.tamu.edu%2Fschaefer%2Fteaching%2F689_Fall2006%2Fp151-sederberg.pdf) technique for deforming solid models in, as the paper amusingly reiterates several times, a "free form manner". In a nut shell FFD deforms the shape of a 3D object using a grid of control points in and around the model. Each control point exerts a certain amount of "force" over the shape of the model, proportional to the force exerted by the other control points. The more control points you have, the more points you need to move to affect noticable deformation. Like a big game of (3D) tug-of-war. ### Try it out now! Below is an interactive Stanford bunny in a 3x3x3 grid of adjustable control points. Grid size (ie. number of points) affects performance and so 3x3x3 is used to keep the deformation performant. To deform the bunny select a control point (left-click-down+hold) and drag it vertically or horizontally. Release the control point to apply a deformormation to the model. The model won't change shape until the mouse is released. FFD is feasible in real-time with better optimized code. This example can serve as a starting point. Drag controls are locked to the perspective of the camera so "up" is always up from your perspective. Meaning interactions with the control points should feel natural. ### Improvements > **NOTE**: This notebook was never intended to be optimal, only functional. The deformation update is O(n) but a more accurate bound would be closer to O(n${html`*`}I${html`*`}J${html`*`}K), where I, J, and K represent the number of control points along each axis of the control grid. Potential TODO(s): * Add scene reset * Refactor FFD class to avoid costly copy of control points back and forth * Recalculate surface normals after deformation (avoid lighting artifacts)`34:T65a,core = { const renderer = new THREE.WebGLRenderer({antialias: true}); const controls = new THREE.OrbitControls(camera, renderer.domElement); const {scene, dragObjects, ffd} = sceneObject; renderer.setSize(width, height); renderer.setPixelRatio(devicePixelRatio); renderer.render(scene, camera); controls.addEventListener("change", () => renderer.render(scene, camera)); // Add drag controls to the free-form deformer's control points. var dragControls = new THREE.DragControls( dragObjects, camera, renderer.domElement ); dragControls.addEventListener( 'dragstart', function () { controls.enabled = false; }); dragControls.addEventListener( 'drag', function () { renderer.render(scene, camera); }); dragControls.addEventListener( 'dragend', function () { controls.enabled = true; let index = 0 // Woah nelly is this going to be slow. ;) FFD isn't fast so do it on dragend. for(let i = 0; i <= ffd.L; i++){ for(let j = 0; j <= ffd.M; j++){ for(let k = 0; k <= ffd.N; k++){ ffd.controlPoints[i][j][k].x = dragObjects[index].position.x; ffd.controlPoints[i][j][k].y = dragObjects[index].position.y; ffd.controlPoints[i][j][k].z = dragObjects[index].position.z; index+=1; } } } ffd.updateMesh(); renderer.render(scene, camera); } ); // Free up resources (https://observablehq.com/@observablehq/invalidation) invalidation.then(() => (controls.dispose(), renderer.dispose(), dragControls.dispose() )); return { dom: renderer.domElement } }35:T433,sceneObject = { const scene = new THREE.Scene(); scene.background = new THREE.Color(0xffffff); scene.add(model); scene.add(lights); // Create free form deformation object. const ffd = new FreeFormDeformer(2,2,2); ffd.attach(model); ffd.parameterize(); ffd.updateMesh(); let dragObjects = []; var geometry = new THREE.SphereBufferGeometry( 0.01, 16, 16 ); // Convert free form deformer's control points to visible spheres. for(let i = 0; i <= ffd.L; i++){ for(let j = 0; j <= ffd.M; j++){ for(let k = 0; k <= ffd.N; k++){ var object = new THREE.Mesh( geometry, new THREE.MeshLambertMaterial( { color: Math.random() * 0xffffff } ) ); object.position.x = ffd.controlPoints[i][j][k].x; object.position.y = ffd.controlPoints[i][j][k].y; object.position.z = ffd.controlPoints[i][j][k].z; if(i==0 && j==0 && k==0)console.log("Object:",object); scene.add(object); dragObjects.push(object); } } } return { scene, dragObjects, ffd }; }36:T225d,class FreeFormDeformer { /** c'tor * * @param dimL - Number of control points in the 'X' direction * @param dimM - Number of control points in the 'Y' direction * @param dimN - Number of control points in the 'Z' direction * * @note - Technically the axes for our control points can be arbitrary * but to keep things simple we align our controls axes S, T, U to X, * Y, and Z respectively. So why introduce an L, M, and N? That's the * nomenclature from the original paper. In 3 dimensions you have * N objects in one direction, M in another, and L in the 3rd. Yes, * it can be hard to remember. * */ constructor(dimL,dimM,dimN){ this.target = null; this.originalVertices = []; this.transformedVertices = []; this.vertexParams = []; this.S = new THREE.Vector3(0,0,0); this.T = new THREE.Vector3(0,0,0); this.U = new THREE.Vector3(0,0,0); this.L = dimL; this.M = dimM; this.N = dimN; } /** Attach free form deformer to a model. * * @param target - THREE.js mesh * @note - Assumes 'target' has only a single child containing all the geometry. */ attach(target){ this.target = target; // Keep a direct reference to the target's position array to avoid costly copies. this.transformedVertices = target.children[0].geometry.attributes.position.array; // Also retain a clean copy of the unaltered data, stored as THREE.Vector3 for(let i = 0; i < this.transformedVertices.length; i+=3){ this.originalVertices.push(new THREE.Vector3( this.transformedVertices[i], this.transformedVertices[i+1], this.transformedVertices[i+2]) ); }; } /** Calculated a bionomial coefficient (obviously) * * @param n * @param k * @note - See https://en.wikipedia.org/wiki/Binomial_coefficient */ binomialCoeff(n,k){ let total = 1.0; for(let i = 1; i <= k; i++){ total *= (n - (k - i)) / parseFloat(i); } return total; } /** Compute part of a trivariate Bernstein Polynomial * * @param n {int} - Number of control points in a given direction * @param v {int} - Current control point between 1 and 'n' * @param x {float} - One of the local coordinates of local coordinate system {s,t,u} */ bernsteinPoly(n, v, x) { return this.binomialCoeff(n,v) * Math.pow(x, parseFloat(v)) * Math.pow(parseFloat(1.0 - x), parseFloat(n - v)); } /** Parameterize the deformation by the currently attached model * */ parameterize() { if(this.target == null){ throw "Call Free Form Deformations 'attach' method before calling 'parameterize'" } let minVertex = new THREE.Vector3(Infinity,Infinity,Infinity); let maxVertex = new THREE.Vector3(-Infinity,-Infinity,-Infinity); this.originalVertices.forEach((v)=>{ maxVertex = maxVertex.max(v,maxVertex); minVertex = minVertex.min(v,minVertex); }); this.calculateSTU(maxVertex, minVertex); this.calculateTrivariateBernsteinPolynomial(minVertex); this.createControlPoints(minVertex); } /** Calculate our local coordinate system S, T, U * * @param max * @param min */ calculateSTU(max, min){ this.S = new THREE.Vector3(max.x - min.x, 0.0, 0.0); this.T = new THREE.Vector3(0.0, max.y - min.y, 0.0); this.U = new THREE.Vector3(0.0, 0.0, max.z - min.z); } /** Generate control points along S, T, U that will deform our object. * * @param origin - Origin of S, T, U */ createControlPoints(origin){ this.controlPoints = []; for(let i = 0; i <= this.L; i++){ this.controlPoints.push([]); for(let j = 0; j <= this.M; j++){ this.controlPoints[i].push([]) for(let k = 0; k <= this.N; k++){ this.controlPoints[i][j].push(this.createControlPoint(origin, i, j, k)); } } } } /** Create individual control point * * @param p0 {THREE.Vector3} - Origin of the entire S, T, U coordinate system. * @param i {int} - Control point along S * @param j {int} - Control point along T * @param k {int} - Control point along U */ createControlPoint(p0, i, j, k){ let LS = this.S.clone(); LS.multiplyScalar(i/parseFloat(this.L)); let MT = this.T.clone(); MT.multiplyScalar(j/this.M); let NU = this.U.clone(); NU.multiplyScalar(k/this.N); let cp = p0.clone().add(LS).add(MT).add(NU); return cp; } /** Precalculate the trivariate bernstein polynomial * * The coefficients created by the tribavariate bernstein poly. * only need to be calculated once. The state of the control points * has no bearing on these values (it uses them, but it doesn't alter them). * Precalculating this here will save us some CPU time down the road. * * @param p0 - Origin of the S, T, U coordinate system. */ calculateTrivariateBernsteinPolynomial(p0){ let TcU = this.T.clone(); TcU.cross(this.U); let ScU = this.S.clone(); ScU.cross(this.U); let ScT = this.S.clone(); ScT.cross(this.T); let TcUdS = TcU.dot(this.S); let ScUdT = ScU.dot(this.T); let ScTdU = ScT.dot(this.U); for (let v = 0; v < this.originalVertices.length; ++v){ let diff = this.originalVertices[v].clone().sub(p0); let tmp = {}; tmp.s = TcU.clone(); tmp.s = tmp.s.dot(diff.clone().divideScalar(TcUdS)); tmp.t = ScU.clone(); tmp.t = tmp.t.dot(diff.clone().divideScalar(ScUdT)); tmp.u = ScT.clone(); tmp.u = tmp.u.dot(diff.clone().divideScalar(ScTdU)); tmp.p = p0.clone(); tmp.p.add(this.S.clone().multiplyScalar(tmp.s)); tmp.p.add(this.T.clone().multiplyScalar(tmp.t)); tmp.p.add(this.U.clone().multiplyScalar(tmp.u)); tmp.p0 = p0.clone(); tmp.bernPolyPack = []; { // Reserve room for each bernstein polynomial pack. tmp.bernPolyPack.push([]); tmp.bernPolyPack.push([]); tmp.bernPolyPack.push([]); } { // Pre-calculate bernstein polynomial expansion. It only needs to be done once per parameterization for (let i = 0; i <= this.L; i++){ for (let j = 0; j <= this.M; j++){ for (let k = 0; k <= this.N; k++){ tmp.bernPolyPack[2].push(this.bernsteinPoly(this.N, k, tmp.u)); } tmp.bernPolyPack[1].push(this.bernsteinPoly(this.M, j, tmp.t)); } tmp.bernPolyPack[0].push(this.bernsteinPoly(this.L, i, tmp.s)); } } this.vertexParams.push(tmp); } } /** Deform vertex by the current state of the control points. * * @param r {bernsteinPoly value} - Single value from 'bernsteinPoly' containing all * data on how all the control points affect a particular vertex. */ getWorldVector3(r){ let l = this.L; let m = this.M; let n = this.N; let tS = new THREE.Vector3(0,0,0); for(let i = 0; i <= l; i++){ let tM = new THREE.Vector3(0,0,0); for(let j = 0; j <= m; j++){ let tK = new THREE.Vector3(0,0,0); for(let k = 0; k <= n; k++){ tK.add(this.controlPoints[i][j][k].clone().multiplyScalar(r.bernPolyPack[2][k])); } tM.add(tK.multiplyScalar(r.bernPolyPack[1][j])); } tS.add(tM.multiplyScalar(r.bernPolyPack[0][i])); } return tS; } /** Call to deform mesh data. * */ updateMesh(){ if(this.target == null){ throw "Call Free Form Deformations 'attach' method before calling 'updateMesh'"; } // Transform 'target's geometry by the position of 'controlPoints' this.vertexParams.forEach((vp,vpi)=>{ let p = this.getWorldVector3(vp); this.transformedVertices[vpi*3] = p.x; this.transformedVertices[vpi*3+1] = p.y; this.transformedVertices[vpi*3+2] = p.z; }); // Make sure to signal THREE.js to update this.target.children[0].geometry.attributes.position.needsUpdate = true; this.target.children[0].geometry.computeBoundingSphere(); } };37:[] 31:{"id":"27dde4be04f6ae60","slug":"free-form-deformation-work-in-progress","title":"Free Form Deformation","thumbnail":"f1ffcc51d2113fa9a2daa08ba6898cbcb1c376f5ec60662c352c77490fb324b4","access_level":"public","create_time":"$D2019-04-24T11:45:49.903Z","update_time":"$D2021-04-14T18:14:56.823Z","view_time":null,"first_public_time":"$D2019-08-23T21:34:53.400Z","has_unpublished_edits":null,"fork":false,"stars":2,"starred":false,"owner":{"type":"team","id":"7cae0ef6ff159231","login":"jerdak","name":"j.carson","avatar_url":"https://avatars-next.observableusercontent.com/c9503938960f19ac6db5d65d8d4d6a9f676805ddb8d5dfca1e6e3d1ab6c18f7c","tier":"starter_2024"},"version":374,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"bbfa6fe35a8ce00e","login":"jerdak","name":"j.carson","avatar_url":"https://avatars-next.observableusercontent.com/c9503938960f19ac6db5d65d8d4d6a9f676805ddb8d5dfca1e6e3d1ab6c18f7c","tier":null}],"members":[{"type":"individual","id":"bbfa6fe35a8ce00e","login":"jerdak","name":"j.carson","avatar_url":"https://avatars-next.observableusercontent.com/c9503938960f19ac6db5d65d8d4d6a9f676805ddb8d5dfca1e6e3d1ab6c18f7c","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":2,"collection":null,"type":"notebook","body":{"title":"Free Form Deformation","cells":[{"id":0,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":15,"value":"core.dom","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":13,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":9,"value":"height = 600","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":326,"value":"width = 800","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":12,"value":"$35","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":61,"value":"modelSelect = \"https://gist.githubusercontent.com/esperanc/adfa03fd2f4a4c1ba659182d97403bc4/raw/3547113a6c25fd3554ff6faf290edfb648720f1c/bunny.obj\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":297,"value":"function centerObjectOnOrigin(object){\n let center = new THREE.Vector3 ();\n let size = new THREE.Vector3();\n let modelbox = new THREE.Box3().setFromObject (object);\n modelbox.getCenter(center);\n modelbox.getSize(size);\n\n let positions = object.children[0].geometry.attributes.position.array;\n for(let p = 0; p < positions.length; p+=3){\n positions[p] = positions[p] - center.x;\n positions[p+1] = positions[p+1] - center.y;\n positions[p+2] = positions[p+2] - center.z;\n }\n object.children[0].geometry.attributes.position.needsUpdate = true;\n object.children[0].geometry.computeBoundingSphere();\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":53,"value":"model = new Promise ((resolve,reject) => {\n // instantiate a loader\n var loader = new THREE.OBJLoader();\n \n // load a resource\n loader.load(\n\t // resource URL\n\t modelSelect, \n \t// called when resource is loaded\n\t function ( object ) { \n // Attach the material to each mesh element of the object\n object.traverse( function ( child ) {\n\t\t\t\tif ( child.isMesh ) child.material = material;\n\t\t\t});\n \n // Some objects are a little off origin, shifting the axis of rotation in non-obvious ways.\n centerObjectOnOrigin(object);\n \n // Finally, resolve the promise\n resolve(object);\n \t},\n\t // called when loading is in progresses\n\t function ( xhr ) {\n\t\t console.log( ( xhr.loaded / xhr.total * 100 ) + '% loaded' );\n \t},\n\t // called when loading has errors\n\t function ( error ) {\n \t\tconsole.log( 'An error happened' );\n reject (\"Error\")\n\t }\n );\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":59,"value":"material = {\n //return new THREE.MeshNormalMaterial()\n return new THREE.MeshStandardMaterial ({color:\"#ff0000\", side: THREE.DoubleSide})\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":72,"value":"lights = {\n let group = new THREE.Group();\n let hlight = new THREE.HemisphereLight(0xffffff, 0x888888);\n let dlight = new THREE.DirectionalLight( 0xffffff );\n\tdlight.position.set( 1, 1, 1 ).normalize();\n let dlight2 = new THREE.DirectionalLight( 0xffffff );\n\tdlight2.position.set( -1, -1, -1 ).normalize();\n group.add( hlight, dlight, dlight2 );\n return group;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":6,"value":"camera = {\n let center = new THREE.Vector3 ();\n let size = new THREE.Vector3();\n let modelbox = new THREE.Box3().setFromObject (model);\n modelbox.getCenter(center);\n modelbox.getSize(size);\n let radius = size.length()/2;\n console.log(\"Center:\",center);\n console.log(\"radius:\",radius);\n console.log(\"size:\",size);\n \n const fov = 45;\n const aspect = width / height;\n const near = radius / 2.0;\n const far = 1000*radius;\n const camera = new THREE.PerspectiveCamera(fov, aspect, near, far);\n //model.position.set(-center.x,-center.y,-center.z)\n // Set the camera away from the the objec\n camera.position.set(0,0,radius*3);\n return camera;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":41,"value":"$36","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2,"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 await require(\"three@0.99.0/examples/js/controls/TransformControls.js\").catch(() => {});\n await require(\"three@0.99.0/examples/js/controls/DragControls.js\").catch(() => {});\n await require(\"three@0.99.0/examples/js/loaders/OBJLoader.js\").catch(() => {});\n return THREE;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":37,"value":"class Vector3P {\n constructor(){\n this.polyPack = [];\n this.p = new THREE.Vector3(0,0,0);\n this.p0 = new THREE.Vector3(0,0,0);\n \n this.s = 0.0;\n this.t = 0.0;\n this.u = 0.0;\n }\n copy(v/*: Vector3P*/){\n this.p = v.p;\n this.p0 = v.p0;\n this.s = v.s;\n this.t = v.t;\n this.u = v.u;\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W37","stdlib":"1","titling":"auto"}} 32:"$31:body"