Symbol Kategorie

Geometry Processing

5 ECTS; Summer Term; Dr. Roberto Grosso

Reiter

Description

This course introduces some aspects of discrete geometry processing. The focus is on the generation, processing (smoothing, deformation), and analysis of triangular meshes as well as surface reconstruction from point clouds. The following topics are covered in the course:

Course Content

  • Delaunay triangulation and Voronoi diagrams
  • Registration of points clouds
  • Surface mesh reconstruction
  • Mesh smoothing, and simplification
  • Mesh parametrization
  • Deformation of triangle meshes

Educational objectives and skills

At the end of this course students are able to
  • understand and explain the meaning of the terms polynomial curves, Bézier curves and B-Splines
  • classify and illustrate the different evaluation and subdivision methods for Bezier curves and B-Splines
  • describe and establish the properties of Bézier, B-Splines, and rational Bézier B-Splines curves
  • understand and explain tensor product surfaces and describe evaluation algorithms
  • explain polygonal surfaces and subdivision algorithms and depict their properties and differences
  • get used to common data structures to represent polygonal surfaces
  • understand and describe surface subdivision techniques
  • understand and explain interpolation methods applied to keyframe animations
  • implement the algorithms discussed in this course in any common programming language such as JavaScript

Examination

  • e-Prüfung (electronic exam within the StudOn-Exam platfrom)
  • 90 min
  • theory, exercises and programming exercises

Literature and References

Literature

  • Polygon Mesh Processing (Mario Botsch et al.)
  • Numerical Geometry of Non-Rigid Shapes (Alexander M. Bronstein et al.)

Conferences

  • SIGGRAPH
  • Eurographics Symposium on Geometry Processing

Geometry Processing

{ getResources: function() { const url1 = 'https://www.studon.fau.de/file4839480_download.html' const url2 = 'https://www.studon.fau.de/file4839481_download.html' return [ { name: 'bunny', uri: url1, type: 'text'}, { name: 'fertility', uri: url2, type: 'text'} ] }, setupDOM: function(canvasElement, outputElement, scope) { canvasElement.css('border', 'none') scope.find("#allow_run_button").css('display','none') }, init: function(canvasElement, outputElement, scope, runner) { $('.row').css('display','block'); // add a title const divNode = document.createElement('div') divNode.style.top = '20px' divNode.style.width = '100%' divNode.style.textAlign = 'left' divNode.style.leftMargin = '10px' divNode.style.zIndex = '100' divNode.style.display = 'absolute' const divText = document.createTextNode('Mesh reduction by means of halfedge collapse') divNode.appendChild(divText) canvasElement.append(divNode) // rendering const width = canvasElement.width() const height = canvasElement.height() - 25 // 25px for title const scene = new THREE.Scene() scene.background = new THREE.Color( 0xF0F8FF ) const camera = new THREE.PerspectiveCamera(45, width / height, 0.11, 1000) camera.position.set( 0.0, 1.5, 4.6 ) // add a ground plane to improve perspective view const planeGeometry = new THREE.PlaneGeometry( 30, 30, 10, 10) const planeMaterial = new THREE.MeshLambertMaterial({ color: 0xa0adaf, side: THREE.DoubleSide }) const ground = new THREE.Mesh(planeGeometry, planeMaterial ) //node.ltGeometry.push(planeGeometry) //node.ltMaterial.push(planeMaterial) ground.rotation.x = - Math.PI / 2; ground.position.set(0,-1.2,0) ground.castShadow = false ground.receiveShadow = true; scene.add(ground) // Light sources const light1 = new THREE.PointLight( 0xffffff, 1, 100, 1.5 ) light1.position.set( 0 , 4 , 8 ) light1.castShadow = true light1.shadow.camera.near = 0.5; light1.shadow.camera.far = 500; light1.shadow.mapSize.width = 1024; light1.shadow.mapSize.height = 1024; const light2 = new THREE.DirectionalLight( 0x333333, 1, 100, 1.5 ) light2.position.set( 0, 4, -4 ) const aLight = new THREE.AmbientLight( 0x606060 ) scene.add(light1) scene.add(light2) scene.add(aLight) const renderer = new THREE.WebGLRenderer({antialias: true}) renderer.setPixelRatio(window.devicePixelRatio) renderer.setSize(width, height) renderer.shadowMap.enabled = true renderer.shadowMap.type = THREE.PCFSoftShadowMap renderer.domElement.classList.add('renderer_Teaser_Subdivision') canvasElement.append(renderer.domElement) canvasElement.find('.renderer_Teaser_MeshReduction').css('border', 'solid #b11226') //canvasElement.get(0).children[1].style.border = 'solid #b11226' // controls: camera const controls = new THREE.OrbitControls( camera, renderer.domElement ) controls.minDistance = 0.1 controls.maxDistance = 80 controls.target.set( 0, 0.1, 0 ) controls.update() // border canvasElement.get(0).children[1].style.border = 'solid #b11226' canvasElement.data('scene', scene) canvasElement.data('camera', camera) canvasElement.data('light1', light1) canvasElement.data('light2', light2) canvasElement.data('aLight', aLight) canvasElement.data('renderer', renderer) canvasElement.data('controls', controls) // run runner() }, addArgumentsTo: function(args) { args.bunny = this.bunny args.fertility = this.fertility }, reset(canvasElement) {}, update: function(txt, json, canvasElement, outputElement) { const node = canvasElement.get(0) const scene = canvasElement.data('scene') const camera = canvasElement.data('camera') const light1 = canvasElement.data('light1') const light2 = canvasElement.data('light2') const aLight = canvasElement.data('aLight') const renderer = canvasElement.data('renderer') const controls = canvasElement.data('controls') // geometries const g = new THREE.Group() g.name = 'both meshes' const meshes = [ json.fertility, json.bunny ] for (let index = 0; index < meshes.length; index++) { const m = meshes[index] const n = m.length let x0 = -3 const dx = 2 * Math.abs(x0) / (n-1) const mGroup = new THREE.Group() if (index === 0) mGroup.name = "mesh: fertitlity" else mGroup.name = "mesh: bunny" for (let i = 0; i < n; i++) { const { iBuff, vBuff } = m[i] // Material const mMaterial = new THREE.MeshPhongMaterial({ color: 0x049ef4, flatShading: true, side: THREE.DoubleSide, polygonOffset: true, polygonOffsetFactor: 1, // positive value pushes polygon further away polygonOffsetUnits: 1 }) const wMaterial = new THREE.MeshBasicMaterial({ color: 0x040701, wireframe: true }) // compute surface mesh const mGeometry = new THREE.BufferGeometry() mGeometry.setIndex(iBuff) mGeometry.setAttribute('position', new THREE.Float32BufferAttribute(vBuff, 3).onUpload(disposeArray)) mGeometry.computeVertexNormals() mGeometry.normalizeNormals() const mMesh = new THREE.Mesh( mGeometry, mMaterial ) // wireframe const wMesh = new THREE.Mesh( mGeometry, wMaterial ) // position objects mMesh.translateX(x0) wMesh.translateX(x0) // add mGroup.add(mMesh) mGroup.add(wMesh) // set object to invisible mMesh.material.visible = false mMesh.castShadow = true mMesh.receiveShadow = false wMesh.material.visible = false wMesh.castShadow = false wMesh.receiveShadow = false // position next subdivision surface x0 += dx } g.add(mGroup) } // loop over models g.children[0].children.forEach( (c,index) => { if (index%2 === 0) c.material.visible = true }) // add geometry to scene scene.add(g) // GUI // GUI const gui = new lil.GUI({autoPlace: false}) gui.close() canvasElement.append(gui.domElement) const folderModel = gui.addFolder('Model') const folderRendering = gui.addFolder('Rendering') const guiProps = { model: { fertility: true, bunny: false }, rendering: { wireframe: false, flatShading: true, rotation: true, camera: function() { controls.reset() } } } const setModel = (grp, guiProps, objKey, v) => { if (v) { for (const [key,value] of Object.entries(guiProps.model)) guiProps.model[key] = !v } guiProps.model[objKey] = v const flag = [] for (const [key,value] of Object.entries(guiProps.model)) { flag.push(value) } grp.children.forEach( (c, index) => { const {children} = c if (!flag[index]) { children.forEach( m => m.material.visible = false) } else { children.forEach( (m,i) => { if (i%2 === 0) m.material.visible = flag[index] else if (i%1 === 1) m.material.visible = guiProps.rendering.wireframe }) } }) } const fBox = folderModel.add(guiProps.model, 'fertility') .name('fertility') .listen() .onChange( v => setModel(g, guiProps, 'fertility', v) ) const bBox = folderModel.add(guiProps.model, 'bunny') .name('bunny') .listen() .onChange( v => setModel(g,guiProps,'bunny', v) ) const w = folderRendering.add(guiProps.rendering, 'wireframe').listen().onChange( v => { let mIndex = -1 if (guiProps.model.fertility === true) mIndex = 0 else if (guiProps.model.bunny === true) mIndex = 1 if (mIndex !== -1) { g.children[mIndex].children.forEach( (c,index) => { if (index%2 === 1) { c.material.visible = v } }) } }) const f = folderRendering.add(guiProps.rendering,'flatShading') .listen().name('flat shading').listen().onChange( v => { g.children.forEach( c => c.children.forEach( (m, index) => { if (index%2 === 0) { m.material.needsUpdate = true m.material.flatShading = v } })) }) const r = folderRendering.add(guiProps.rendering, 'rotation').name('rotation').listen().onChange( v => rotationFlag = v) const c = folderRendering.add(guiProps.rendering, 'camera').name('reset camera') // set z-index for all gui elements //scope.find('.lil-gui').children().css('z-index', '100') $('.lil-gui').children().css('z-index', '100') // render loop let rotationFlag = true // animation const q = new THREE.Quaternion() function animate(time) { requestAnimationFrame( animate ); if (rotationFlag) { q.setFromAxisAngle( new THREE.Vector3(0,1,0), 0.005) g.children.forEach( c => c.children.forEach( e => { e.applyQuaternion(q) })) } render() } function render() { renderer.render( scene, camera ) } animate() // remove array from memory after upload on GPU function disposeArray() { this.array = null; } } }let nrC = [Infinity, 6000, 3000, 1000] const t0 = performance.now() const bunny = [] for (let level = 0; level < nrC.length; level++) { const buffers = draw(args.bunny, nrC[level]) const { iBuff, vBuff } = buffers bunny.push({ level: level, iBuff: iBuff, vBuff: vBuff }) } const fertility = [] for (let level = 0; level < nrC.length; level++) { const buffers = draw(args.fertility, nrC[level]) const { iBuff, vBuff } = buffers fertility.push({ level: level, iBuff: iBuff, vBuff: vBuff }) } console.log(JSON.stringify( { bunny: bunny, fertility: fertility } )) function decimation(heMesh, heap, minHeapSize) { const { vertices, faces, halfedges } = heMesh // Initialize // compute quadric matrix initQuadricError(heMesh) // one 4x4 matrix for each vertex // compute error of halfedge collapse const heCosts = [] halfedges.forEach((e, i, a) => { const ecCost = quadricError(e,heMesh) const ec = { element: e, index: e.index, value: ecCost } heap.push( ec ) heCosts.push(ec) }) heMesh.heCosts = heCosts const nr_e = heCosts.length const thresA = 0.7 const thresQ = 0.3 const maxDeg = 17 while (heap.size() > minHeapSize) { halfedgeCollapse(heMesh, heap, thresA, thresQ, maxDeg) } } // decimation function halfedgeCollapse(heMesh, heap, thresA, thresQ, maxDeg) { const heObject = heap.pop() if(!feasibilityCheck(heObject.element, heMesh, thresA, thresQ, maxDeg)) { return false } const { vertices, halfedges, faces } = heMesh // collect edges const he1 = heObject.element.index const he2 = halfedges[he1].next const he3 = halfedges[he2].next const he4 = halfedges[he2].twin const he5 = halfedges[he3].twin const he6 = halfedges[he1].twin const he7 = halfedges[he6].next const he8 = halfedges[he7].next const he9 = halfedges[he7].twin const he10 = halfedges[he8].twin // faces const f1 = halfedges[he1].face const f2 = halfedges[he6].face // vertices const v1 = halfedges[he1].origin const v2 = halfedges[he2].origin const v3 = halfedges[he3].origin const v4 = halfedges[he8].origin // collect edges that have to be recomputed const { inedges } = inEdges(vertices[v1], heMesh) // collect edges which origin changes const { outedges } = outEdges(vertices[v1], heMesh) // reconnect halfedges[he4].twin = he5 halfedges[he5].twin = he4 halfedges[he9].twin = he10 halfedges[he10].twin = he9 // set vertex halfedge vertices[v2].he = he5 vertices[v3].he = he4 vertices[v4].he = he9 // mark deleted vertices[v1].deleted = true faces[f1].deleted = true faces[f2].deleted = true halfedges[he1].deleted = true halfedges[he2].deleted = true halfedges[he3].deleted = true halfedges[he6].deleted = true halfedges[he7].deleted = true halfedges[he8].deleted = true // reconnect outgoing edges outedges.forEach ( e => { if (!e.deleted) e.origin = v2 }) // update priority queue const { heCosts } = heMesh heap.remove(heCosts[he2]) heap.remove(heCosts[he3]) heap.remove(heCosts[he6]) heap.remove(heCosts[he7]) heap.remove(heCosts[he8]) inedges.forEach( e => { if (!e.deleted) { const ecCost = quadricError(e,heMesh) const cost = heCosts[e.index] cost.value = ecCost heap.update(cost) } }) outedges.forEach( e => { if (!e.deleted) { const ecCost = quadricError(e,heMesh) const cost = heCosts[e.index] cost.value = ecCost heap.update(cost) } }) // update degree of vertices const deg1 = vertices[v1].degree const deg2 = vertices[v2].degree const deg3 = vertices[v3].degree const deg4 = vertices[v4].degree vertices[v2].degree = deg1+deg2 - 4 vertices[v3].degree = deg3 - 1 vertices[v4].degree = deg4 - 1 return true } function feasibilityCheck(e,heMesh, thresA, thresQ, maxDeg) { const {vertices, halfedges, faces} = heMesh const h1 = e.index const h2 = halfedges[h1].next const v1 = halfedges[h1].origin const v2 = halfedges[h2].origin // check valence const deg1 = vertices[v1].degree if (deg1 < 3) return false //if (deg1 === 3) return true // check degree of v2 const deg2 = vertices[v2].degree const deg2r = deg2+deg1-4 if (deg2 < 3 || deg2r < 3 || deg2r > maxDeg) return false const h3 = halfedges[h2].next const h6 = halfedges[h1].twin const h7 = halfedges[h6].next const h9 = halfedges[h7].twin // collect vertices const v3 = halfedges[h3].origin const v4 = halfedges[h9].origin const deg3 = vertices[v3].degree const deg4 = vertices[v4].degree if (deg3 < 4 || deg4 < 4) return false // check element quality const {onering, openFan } = oneRing(vertices[v1], heMesh) const nr_v = onering.length for (let i = 0; i < nr_v; i++) { const vi = onering[i] const vj = onering[(i+1)%nr_v] if (vi.index === v2 || vj.index === v2) continue const n1 = faceNormal(vertices[v1],vi, vj) const n2 = faceNormal(vertices[v2],vi, vj) if (dot(n1,n2) < thresA) { return false } const vk = onering[(i+2)%nr_v] if (vk.index === v2) continue const n3 = faceNormal(vertices[v2],vi, vj) const n4 = faceNormal(vertices[v2],vj, vk) if (dot(n3,n4) < thresA) { return false } // check element quality const q = quality(vertices[v2], vi, vj) if (q < thresQ) { return false } } return true } function initQuadricError(heMesh) { const { vertices, halfedges, faces } = heMesh const quadrics = [] vertices.forEach( v0 => { const { outedges, openFan } = outEdges(v0, heMesh) const fn_ = [] outedges.forEach( e => { fn_.push(e.face) }) quadrics.push(fn_) }) heMesh.quadrics = quadrics } function quadricError(e, heMesh) { const { vertices, halfedges, fNormals, quadrics } = heMesh const i0 = e.origin const i1 = halfedges[e.next].origin const fn_ = quadrics[i0] let cost = 0 const v0 = vertices[i0] const v1 = vertices[i1] const p = {x: v1.x - v0.x, y: v1.y - v0.y, z: v1.z - v0.z} fn_.forEach( f => { const n = fNormals[f] const d = dot(p,n) cost += d * d }) return cost } //============================================================================================== function draw(text, minHeapSize) { // find out which file format let flagOFF = false if (text.substring(0, 3).toUpperCase() === 'OFF') { flagOFF = true } let ifs = null if (flagOFF) { ifs = readOFF(text) } else { ifs = readObj(text) } const flag = true let buffers = null let bnd = null // Halfedge computations const heMesh = heMeshFromIndexedFaceSet(ifs) // mark elements as not deleted heMesh.vertices.forEach( v => { v.deleted = false }) heMesh.halfedges.forEach( e => { e.deleted = false }) heMesh.faces.forEach( f => { f.deleted = false }) //heVertexNormals(heMesh) heTransform(heMesh) bnd = findBoundary(heMesh) if (bnd.length > 0) { console.log(`the mesh has ${bnd.length} boundary edges`) return } //const nr_elements = countElements(heMesh) // smooth mesh const l = 0.8331 umbrella(heMesh, l) // arrays const {vertices, halfedges, faces} = heMesh // compute vertex degree let maxDeg = 0 let minDeg = Infinity vertices.forEach( v => { const deg = degree(v, heMesh) v.degree = deg maxDeg = Math.max(maxDeg, deg) minDeg = Math.min(minDeg, deg) }) //console.log(`maxDeg: ${maxDeg}, minDeg: ${minDeg}`) // compute face quality let minQ = Infinity let maxQ = 0 const fn_ = [] faces.forEach( (f,index) => { const h0 = f.he const h1 = halfedges[h0].next const h2 = halfedges[h1].next const q = quality( vertices[halfedges[h0].origin], vertices[halfedges[h1].origin], vertices[halfedges[h2].origin] ) f.quality = q minQ = Math.min(minQ, q) maxQ = Math.max(maxQ, q) // face normal const n = faceNormal(vertices[halfedges[h0].origin], vertices[halfedges[h1].origin], vertices[halfedges[h2].origin] ) fn_.push(n) }) heMesh.fNormals = fn_ //console.log(`minQ: ${minQ}, maxQ: ${maxQ}`) // decimation function cost(d) { return d.value } //const heap = binaryHeapFactory(cost) const heap = binaryHeapMapFactory(cost) if (minHeapSize !== Infinity) decimation(heMesh, heap, minHeapSize) // render clear(heMesh) heMesh.vertices.forEach( v => { if (v.deleted) console.log(`deleted vertex`) }) heMesh.halfedges.forEach( e => { if (e.deleted) console.log(`deleted edge`) }) heMesh.faces.forEach( f => { if (f.deleted) console.log(`deleted face`) }) heVertexNormals(heMesh) buffers = heRenderBuffers(heMesh) return buffers } /////////////////////////////////////////////////////////////////////////////////////////////////// // Helper functions /////////////////////////////////////////////////////////////////////////////////////////////////// function faceNormal(v0,v1,v2) { const n = normal(v0,v1,v2) return normalize(n) } function normal(v0, v1, v2) { const e0 = { x: v1.x - v0.x, y: v1.y - v0.y, z: v1.z - v0.z } const e1 = { x: v2.x - v0.x, y: v2.y - v0.y, z: v2.z - v0.z } return cross(e0, e1) } function normalize(n) { const s = Math.sqrt(n.x ** 2 + n.y ** 2 + n.z ** 2) n.x /= s n.y /= s n.z /= s return n } function dot(n1, n2) { return n1.x * n2.x + n1.y * n2.y + n1.z * n2.z } function cross(v1, v2) { return { x: v1.y * v2.z - v1.z * v2.y, y: v1.z * v2.x - v1.x * v2.z, z: v1.x * v2.y - v1.y * v2.x } } function norm(n) { return Math.sqrt( n.x * n.x + n.y * n.y + n.z * n.z) } function norm2(n) { return ( n.x * n.x + n.y * n.y + n.z * n.z) } function clear(heMesh) { const nv = [] const ne = [] const nf = [] const vm_ = [] const em_ = [] const fm_ = [] const { vertices, halfedges, faces } = heMesh let vc = 0 vertices.forEach( (v, index) => { vm_.push({c: index, n: -1 }) if (!v.deleted) { nv.push(v) vm_[v.index].n = vc vc++ } }) let ec = 0 halfedges.forEach( (e,index) => { em_.push({c: index, n: -1}) if (!e.deleted) { ne.push(e) em_[e.index].n = ec ec++ } }) let fc = 0 faces.forEach( (f,index) => { fm_.push({c: index, n: -1}) if (!f.deleted) { nf.push(f) fm_[f.index].n = fc fc++ } }) // map elements nv.forEach( (v, index) => { v.index = index v.he = em_[v.he].n }) nf.forEach( (f, index) => { f.index = index f.he = em_[f.he].n }) ne.forEach( (e, index) => { e.index = index e.origin = vm_[e.origin].n e.face = fm_[e.face].n if (e.twin !== -1) { e.twin = em_[e.twin].n } e.next = em_[e.next].n }) heMesh.vertices = nv heMesh.faces = nf heMesh.halfedges = ne } /////////////////////////////////////////////////////////////////////////////////////////////////// // Here is the halfedge stuff /////////////////////////////////////////////////////////////////////////////////////////////////// function heMeshFromIndexedFaceSet({ vertices, faces }) { const halfedges = [] const heVertices = [] const heFaces = [] // assume the mesh is tris only vertices.forEach((v, index) => heVertices.push({ index, he: -1, x: v.x, y: v.y, z: v.z, bnd: false })) faces.forEach((f, index) => { const e0 = index * 3 const e1 = index * 3 + 1 const e2 = index * 3 + 2 const he0 = { index: e0, origin: f.v0, face: index, next: e1, twin: -1 } const he1 = { index: e1, origin: f.v1, face: index, next: e2, twin: -1 } const he2 = { index: e2, origin: f.v2, face: index, next: e0, twin: -1 } heVertices[he0.origin].he = e0 heVertices[he1.origin].he = e1 heVertices[he2.origin].he = e2 halfedges.push(he0, he1, he2) const face = { index: index, he: e0 } heFaces.push(face) }) // connectivity const key0 = (k1, k2) => { if (k1 > k2) { return (k1 + k2) * (k1 + k2 + 1) / 2 + k2 } else { return (k1 + k2) * (k1 + k2 + 1) / 2 + k1 } } const key1 = (k1, k2) => { if (k1 > k2) { return (BigInt(k1) << 32n) | BigInt(k2) } else { return (BigInt(k2) << 32n) | BigInt(k1) } } const key2 = (k1, k2) => { if (k1 > k2) { return k1 + '_' + k2 } else { return k2 + '_' + k1 } } const m_ = new Map() for (let i = 0; i < halfedges.length; i++) { const e = halfedges[i] const v0 = e.origin const v1 = halfedges[e.next].origin const key = key0(v0, v1) const element = m_.get(key) if (element === undefined) { m_.set(key, { he0: e.index, he1: -1 }) } else { element.he1 = e.index } } m_.forEach(value => { const e0 = value.he0 const e1 = value.he1 //if (e0 !== -1) halfedges[e0].twin = e1 halfedges[e0].twin = e1 if (e1 !== -1) halfedges[e1].twin = e0 }) // set he at boundary vertices, mark boundary vertices let cnt = 0 halfedges.forEach(e => { if (e.twin === -1) { heVertices[e.origin].he = e.index heVertices[e.origin].bnd = true cnt++ } }) if (cnt > 0) { console.log(`nr. of boundary vertices: ${cnt}`) } return { halfedges, vertices: heVertices, faces: heFaces } } function quality(v0,v1,v2) { const e1 = {x: v1.x - v0.x, y: v1.y - v0.y, z: v1.z - v0.z} const e2 = {x: v2.x - v1.x, y: v2.y - v1.y, z: v2.z - v1.z} const e3 = {x: v2.x - v0.x, y: v2.y - v0.y, z: v2.z - v0.z} const area = norm(cross(e1,e3)) const l1 = norm2(e1) const l2 = norm2(e2) const l3 = norm2(e3) if (l1 !== 0 && l2 !== 0 && l3 !== 0) { return 2 * Math.sqrt(3) * area / (l1+l2+l3) } else { return 0 } } function degree(v, mesh) { const { vertices, halfedges } = mesh let deg = 0 const h0 = vertices[v.index].he let hn = h0 let h1 = -1 let h2 = -1 do { h1 = halfedges[hn].next deg++ h2 = halfedges[h1].next hn = halfedges[h2].twin } while (hn !== h0 && hn !== -1) if (hn === -1) { deg++ } return deg } function oneRing(vertex, mesh) { const { vertices, halfedges } = mesh const onering = [] const h0 = vertices[vertex.index].he let hn = h0 let h1 = -1 let h2 = -1 let openFan = false do { h1 = halfedges[hn].next onering.push(vertices[halfedges[h1].origin]) h2 = halfedges[h1].next hn = halfedges[h2].twin } while (hn !== h0 && hn !== -1) if (hn === -1) { openFan = true onering.push(vertices[halfedges[h2].origin]) } return { onering, openFan } } function inEdges( vertex, mesh ) { const { vertices, halfedges } = mesh const inedges = [] const h0 = vertices[vertex.index].he let hn = h0 let h1 = -1 let h2 = -1 let openFan = false do { h1 = halfedges[hn].next h2 = halfedges[h1].next inedges.push(halfedges[h2]) hn = halfedges[h2].twin } while (hn !== h0 && hn !== -1) if (hn === -1) { openFan = true } return { inedges, openFan } } function outEdges( vertex, mesh ) { const { vertices, halfedges } = mesh const outedges = [] const h0 = vertices[vertex.index].he let hn = h0 let h1 = -1 let h2 = -1 let openFan = false do { outedges.push(halfedges[hn]) h1 = halfedges[hn].next h2 = halfedges[h1].next hn = halfedges[h2].twin } while (hn !== h0 && hn !== -1) if (hn === -1) { openFan = true } return { outedges, openFan } } function countElements({ vertices, faces, halfedges }) { //const nr_v = vertices.length //const nr_f = faces.length let nr_v = 0 vertices.forEach( v => { if(!v.deleted) nr_v++ }) let nr_f = 0 faces.forEach( f => { if (!f.deleted) nr_f++ }) const key = (k1, k2) => { if (k1 > k2) { return (BigInt(k1) << 32n) | BigInt(k2) } else { return (BigInt(k2) << 32n) | BigInt(k1) } } const s_ = new Set() halfedges.forEach(e => { if (!e.deleted) { const t = e.twin const v0 = e.origin const v1 = halfedges[t].origin const k = key(v0, v1) s_.add(k) } }) const nr_e = s_.size //console.log(`nr_v: ${nr_v}, nr_f: ${nr_f}, nr_e: ${nr_e}`) return { nr_v, nr_f, nr_e } } function findBoundary(heMesh) { const { vertices, faces, halfedges } = heMesh const bnd = [] halfedges.forEach(e => { if (e.twin === -1) { const v0 = e.origin const v1 = halfedges[e.next].origin bnd.push([vertices[v0], vertices[v1]]) } }) return bnd } function heVertexNormals(heMesh) { function cross(v1, v2) { return { x: v1.y * v2.z - v1.z * v2.y, y: v1.z * v2.x - v1.x * v2.z, z: v1.x * v2.y - v1.y * v2.x } } function normalize(n) { const s = Math.sqrt(n.x ** 2 + n.y ** 2 + n.z ** 2) n.x /= s n.y /= s n.z /= s } function normal(v0, v1, v2) { const e0 = { x: v1.x - v0.x, y: v1.y - v0.y, z: v1.z - v0.z } const e1 = { x: v2.x - v0.x, y: v2.y - v0.y, z: v2.z - v0.z } return cross(e0, e1) } const { vertices, halfedges } = heMesh const normals = [] vertices.forEach(v => { const n = [0, 0, 0] const { openFan, onering } = oneRing(v, heMesh) if (openFan) { for (let i = 1; i < onering.length; i++) { const v1 = onering[i - 1] const v2 = onering[i] const fn = normal(v, v1, v2) n[0] += fn.x n[1] += fn.y n[2] += fn.z } } else { for (let i = 0; i < onering.length; i++) { const v1 = onering[i] const v2 = onering[(i + 1) % onering.length] const fn = normal(v, v1, v2) n[0] += fn.x n[1] += fn.y n[2] += fn.z } } normalize(n) normals.push({ x: n[0], y: n[1], z: n[2] }) }) heMesh.normals = normals } function transformVertices(vertices) { const pos = [0, 0, 0] vertices.forEach(v => { pos[0] += v.x pos[1] += v.y pos[2] += v.z }) pos[0] /= vertices.length pos[1] /= vertices.length pos[2] /= vertices.length for (let i = 0; i < vertices.length; i++) { vertices[i].x -= pos[0] vertices[i].y -= pos[1] vertices[i].z -= pos[2] } } function scaleVertices(vertices) { const vals = [] vals.push(Math.abs(vertices.reduce(function (a, b) { return Math.max(a, b.x) }, -Infinity))) vals.push(Math.abs(vertices.reduce(function (a, b) { return Math.min(a, b.x) }, Infinity))) vals.push(Math.abs(vertices.reduce(function (a, b) { return Math.max(a, b.y) }, -Infinity))) vals.push(Math.abs(vertices.reduce(function (a, b) { return Math.min(a, b.y) }, Infinity))) vals.push(Math.abs(vertices.reduce(function (a, b) { return Math.max(a, b.z) }, -Infinity))) vals.push(Math.abs(vertices.reduce(function (a, b) { return Math.min(a, b.z) }, Infinity))) const s = Math.max(...vals) for (let i = 0; i < vertices.length; i++) { vertices[i].x /= s vertices[i].y /= s vertices[i].z /= s } //debugger } function heTransform({ vertices }) { transformVertices(vertices) scaleVertices(vertices) } function umbrella(heMesh) { const { vertices } = heMesh const nv = [] vertices.forEach((v, index) => { if (!v.bnd) { const p = { index: index, x: 0, y: 0, z: 0 } const { onering, openFlag } = oneRing(v, heMesh) if (!openFlag) { onering.forEach(n => { p.x += (n.x - v.x) p.y += (n.y - v.y) p.z += (n.z - v.z) }) const nr_v = onering.length p.x /= nr_v p.y /= nr_v p.z /= nr_v } else { p.x = v.x p.y = v.y p.z = v.z } nv.push(p) } }) // copy back const t = 0.9 nv.forEach(v => { if (!v.bnd) { vertices[v.index].x = vertices[v.index].x + t * v.x vertices[v.index].y = vertices[v.index].y + t * v.y vertices[v.index].z = vertices[v.index].z + t * v.z } }) } function taubin(heMesh, w) { const { vertices } = heMesh const nv = [] vertices.forEach((v, index) => { const p = { index: index, x: 0, y: 0, z: 0 } const { onering, openFlag } = oneRing(v, heMesh) if (!openFlag) { onering.forEach(n => { p.x += (n.x - v.x) p.y += (n.y - v.y) p.z += (n.z - v.z) }) const nr_v = onering.length p.x /= nr_v p.y /= nr_v p.z /= nr_v } else { p.x = v.x p.y = v.y p.z = v.z } nv.push(p) }) // copy back nv.forEach((v, index) => { vertices[index].x = vertices[index].x + w * v.x vertices[index].y = vertices[index].y + w * v.y vertices[index].z = vertices[index].z + w * v.z }) } //////////////////////////////////////////////////////////////////////////////////////////////////////////// // RENDERING //////////////////////////////////////////////////////////////////////////////////////////////////////////// function heRenderBuffers(heMesh) { const { vertices, normals, faces, halfedges } = heMesh const vBuff = [] const nBuff = [] const iBuff = [] const cBuff = [] const grey = 0.7 const alpha = 0.05 const bndColor = [102 / 255, 1, 51 / 255] let nr_v = 0 vertices.forEach(v => { vBuff.push(v.x, v.y, v.z) const r = grey + alpha * (2 * Math.random() - 1) const g = grey + alpha * (2 * Math.random() - 1) const b = grey + alpha * (2 * Math.random() - 1) cBuff.push(r, g, b) nr_v++ }) normals.forEach(n => nBuff.push(n.x, n.y, n.z)) let nr_f = 0 faces.forEach(f => { // collect vertices const h0 = f.he const h1 = halfedges[h0].next const h2 = halfedges[h1].next const v1 = halfedges[h0].origin const v2 = halfedges[h1].origin const v0 = halfedges[h2].origin iBuff.push(v0, v1, v2) nr_f++ }) return { vBuff, nBuff, cBuff, iBuff, nr_v, nr_f } } function readOFF(text) { const lines = text.split(/\r?\n/) let pos = 1 while (true) { const strs = lines[pos].split(/\s+/) if (strs[0] !== '#') break else pos++ } const [nrVertices, nrFaces] = lines[pos].split(/\s+/).map( e => +e ) pos++ const vertices = [] const faces = [] for (let i = 0; i < nrVertices; i++) { const v = lines[pos++].split(/\s+/).map( e => +e ) vertices.push( {index: i, x: v[0], y: v[1], z: v[2]} ) } for (let i = 0; i < nrFaces; i++) { const face = lines[pos++].split(/\s+/).map( e => +e ) if (face[0] === 3) { faces.push( { index: i, v0: face[1], v1: face[2], v2: face[3] } ) } else if (face[0] === 4) { faces.push( { index: i, v0: face[1], v1: face[2], v2: face[3], v3: face[4] } ) } } //console.log(faces) return { vertices, faces } } function readObj(text) { const vertices = [] const faces = [] text.split(/\r?\n/).forEach( line => { const entries = line.split(/\s+/) if (entries[0] === 'v') { const vertex = entries.slice(1).map(e => +e) const index = vertices.length vertices.push({ index: index, x: vertex[0], y: vertex[1], z: vertex[2] }) } else if (entries[0] === 'f') { let f = null if (entries[entries.length-1] === '') { f = entries.slice(1,entries.length-1) } else { f = entries.slice(1) } let indices = [] f.forEach( e => { indices.push( +e.split('/')[0] - 1) }) const index = faces.length if (indices.length === 3) { faces.push( {index: index, v0: indices[0], v1: indices[1], v2: indices[2] } ) } else if (indices.length === 4) { faces.push( {index: index, v0: indices[0], v1: indices[1], v2: indices[2] } ) faces.push( {index: index+1, v0: indices[0], v1: indices[2], v2: indices[3] } ) } } }) return { vertices, faces } } function binaryHeapFactory(scoreFunction) { const content = [] return { print() { content.forEach((e, index) => { console.log(`pos: ${index}, value: ${scoreFunction(e)}`) }) }, push(element) { // Add the new element to the end of the array. content.push(element) // Allow it to bubble up. this.bubbleUp(content.length - 1) }, peek() { return content[0] }, element(i) { return content[i] }, pop() { // Store the first element so we can return it later. const result = content[0] // Get the element at the end of the array. const end = content.pop() // If there are any elements left, put the end element at the // start, and let it sink down. if (content.length > 0) { content[0] = end this.sinkDown(0) } return result }, remove: function (node) { const length = content.length // To remove a value, we must search through the array to find // it. let result = null for (let i = 0; i < length; i++) { if (content[i] != node) continue result = node // When it is found, the process seen in 'pop' is repeated // to fill up the hole. const end = content.pop() // If the element we popped was the one we needed to remove, // we're done. if (i == length - 1) break // Otherwise, we replace the removed element with the popped // one, and allow it to float up or sink down as appropriate. content[i] = end this.bubbleUp(i) this.sinkDown(i) break } return result }, update(node) { this.remove(node) this.push(node) }, size: function () { return content.length }, bubbleUp(n) { // Fetch the element that has to be moved. const element = content[n] const score = scoreFunction(element) // When at 0, an element can not go up any further. while (n > 0) { // Compute the parent element's index, and fetch it. const parentN = Math.floor((n + 1) / 2) - 1 const parent = content[parentN] // If the parent has a lesser score, things are in order and we // are done. if (score < scoreFunction(parent)) { // Otherwise, swap the parent with the current element and continue. content[parentN] = element content[n] = parent n = parentN } else { break } } }, sinkDown: function (n) { // Look up the target element and its score. const length = content.length const element = content[n] const elemScore = scoreFunction(element) while (true) { // Compute the indices of the child elements. const child2N = (n + 1) * 2 const child1N = child2N - 1 let child1Score = null //let child2Score = null // This is used to store the new position of the element, if any. let swap = null // If the first child exists (is inside the array)... if (child1N < length) { // Look it up and compute its score. child1Score = scoreFunction(content[child1N]) // If the score is less than our element's, we need to swap. if (child1Score < elemScore) { swap = child1N } } // Do the same checks for the other child. if (child2N < length) { const child2Score = scoreFunction(content[child2N]) if (child2Score < (swap == null ? elemScore : child1Score)) { swap = child2N } } // No need to swap further, we are done. if (swap != null) { // Otherwise, swap and continue. content[n] = content[swap] content[swap] = element n = swap } else { break } } } } } // factory function binaryHeapFactory() function binaryHeapMapFactory(scoreFunction) { const content = [] const map = new Map() return { print() { content.forEach((e, index) => { const el = map.get(e.value) console.log(`pos: ${index}, value: ${scoreFunction(e.value)}, map index: ${el.index}`) }) }, push(element) { // Add the new element to the end of the array. const el = {value: element, index: content.length} content.push(el) map.set(element, el) // Allow it to bubble up. this.bubbleUp(content.length - 1) }, peek() { return content[0].value }, element(i) { return content[i].value }, pop() { // Store the first element so we can return it later. const result = content[0] // Get the element at the end of the array. const end = content.pop() map.delete(result.value) // If there are any elements left, put the end element at the // start, and let it sink down. if (content.length > 0) { content[0] = end content[0].index = 0 this.sinkDown(0) } return result.value }, remove: function (node) { if (content.length === 0) return null // To remove a value, we must search through the array to find // it. let result = null const el = map.get(node) if (el !== undefined) { if (map.delete(node)) { result = node if (el.index === content.length - 1) { content.pop() } else { const end = content.pop() if (content.length > 0) { const index = el.index content[index] = end content[index].index = index this.bubbleUp(index) this.sinkDown(index) } } } else { console.log('cannot delete node') } } return result }, update: function(node) { this.remove(node) this.push(node) }, size: function () { return content.length }, bubbleUp(n) { // Fetch the element that has to be moved. const element = content[n] if (element === undefined) debugger const score = scoreFunction(element.value) // When at 0, an element can not go up any further. while (n > 0) { // Compute the parent element's index, and fetch it. const parentN = Math.floor((n + 1) / 2) - 1 const parent = content[parentN] // If the parent has a lesser score, things are in order and we // are done. if (score < scoreFunction(parent.value)) { // Otherwise, swap the parent with the current element and continue. content[parentN] = element content[n] = parent content[n].index = n content[parentN].index = parentN n = parentN } else { break } } }, sinkDown: function (n) { // Look up the target element and its score. const length = content.length const element = content[n] const elemScore = scoreFunction(element.value) while (true) { // Compute the indices of the child elements. const child2N = (n + 1) * 2 const child1N = child2N - 1 let child1Score = null //let child2Score = null // This is used to store the new position of the element, if any. let swap = null // If the first child exists (is inside the array)... if (child1N < length) { // Look it up and compute its score. child1Score = scoreFunction(content[child1N].value) // If the score is less than our element's, we need to swap. if (child1Score < elemScore) { swap = child1N } } // Do the same checks for the other child. if (child2N < length) { const child2Score = scoreFunction(content[child2N].value) if (child2Score < (swap == null ? elemScore : child1Score)) { swap = child2N } } // No need to swap further, we are done. if (swap != null) { // Otherwise, swap and continue. content[n] = content[swap] content[swap] = element content[n].index = n content[swap].index = swap n = swap } else { break } } } } } // factory function binaryHeapMap()
Remark: Programming skills are a prerequisite for this course.
Requirements: It is recommended to have passed the following modules before taking this course:
  • Algorithmik kontinuierlicher Systeme, Module-No. 93000
  • Computer Graphics, Module-No. 43821

StudOn-Course

Geometry Processing