Geometric Modeling

5 ECTS; Winter Term; Dr. Roberto Grosso

Reiter

Description

The lecture covers methods for modeling three-dimensional curves and free-form surfaces. Typical areas of application are computer-aided design (CAD, e.g. in automobile or aircraft construction), the reconstruction of surfaces from sensor data or the construction of smooth interpolated surfaces.

Course Content

The course Geometric Modeling consists of the following learning units

Polynomial Curves
Bézier Curves
B-Splines
Rational Curves
Geometric and Parametric Continuity
Tensor Product Surfaces
Subdivision Surfaces
Application: keyframe animation (optional)

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

Materials

Lecture Notes (PDF), see link in section Learning Units.
StudOn: section Learning units
List of recommended books
- Hoschek, Lasser: Grundlagen der Geometrischen Datenverarbeitung
- Farin: Kurven und Flächen im Computer Aided Geometric Design
- de Boor: A Practical Guide to Splines
- Bartels, Beatty, Barsky: Splines for Use in Computer Graphics and Geometric Modeling
- Abramowski, Müller: Geometrisches Modellieren

Examination

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

Geometric Modeling

{ getResources: function() { const url1 = 'https://www.studon.fau.de/file4834389_download.html'//"https://www.studon.fau.de/file4329481_download.html" // toroidal tetrahedron const url2 = 'https://www.studon.fau.de/file4834388_download.html'//"https://www.studon.fau.de/file4329480_download.html" // cube const url3 = 'https://www.studon.fau.de/file4834391_download.html'//"https://www.studon.fau.de/file4329479_download.html" // cube with bnd const url4 = 'https://www.studon.fau.de/file4834390_download.html'//"https://www.studon.fau.de/file4329482_download.html" // pawn return [ {name:"TETRAHEDRON", uri: url1, type:"json"}, {name:"CUBE", uri: url2, type:"json"}, {name:"CUBE_BND", uri: url3, type:"json"}, {name:"PAWN", uri: url4, type:"json"} ] }, setupDOM: function(canvasElement, outputElement, scope) { canvasElement.find('.row').css('display','block'); canvasElement.css("border", 'none') canvasElement.css("background", 'rgba(255, 255, 255, 0)') scope.find("#allow_run_button").css('display','none') }, init(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('Catmull-Clark Subdivision') divNode.appendChild(divText) canvasElement.append(divNode) // data const toroidalTetrahedron = this.TETRAHEDRON, cube1 = this.CUBE, cube2 = this.CUBE_BND, pawn = this.PAWN const width = canvasElement.width() const height = canvasElement.height() - 25 // 25px for title canvasElement.width(width) canvasElement.height(height) 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.2, 1.5, 6.5 ) // 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,-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_Subdivision').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.5, 0 ); controls.update(); // process geometries const g = new THREE.Group() const scaleFactors = [0.9,1.6,1.6,5] const meshes = [toroidalTetrahedron, cube1, cube2, pawn] for (let index = 0; index < meshes.length; index++) { let m = heMeshFromQuadIndexedFaceSet(meshes[index]) m = translate(m) m = scale(m, scaleFactors[index]) const n = 4 let x0 = -4 const dx = 2 * Math.abs(x0) / (n-1) const mGroup = new THREE.Group() for (let i = 0; i < n; i++) { // compute vertex and face buffers, and wireframe and bounding box const sm = heTesselation(m) // compute surface mesh const mGeometry = new THREE.BufferGeometry() mGeometry.setIndex(sm.faces) mGeometry.setAttribute('position', new THREE.Float32BufferAttribute(sm.vertices, 3).onUpload(disposeArray)) mGeometry.computeVertexNormals() mGeometry.normalizeNormals() 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 sMesh = new THREE.Mesh( mGeometry, mMaterial ) sMesh.rotation.x = -Math.PI / 2 // wireframe const wGeometry = new THREE.BufferGeometry().setFromPoints(sm.edges) const wMaterial = new THREE.LineBasicMaterial({ color: 0x040701, linewidth: 1 }) const wireframe = new THREE.LineSegments( wGeometry, wMaterial ) wireframe.rotation.x = -Math.PI / 2 // bounding box const bGeometry = new THREE.BufferGeometry().setFromPoints(sm.bbox) const bMaterial = new THREE.LineBasicMaterial( { color: 0xb008b, linewidth: 1}) const bbox = new THREE.LineSegments( bGeometry, bMaterial ) bbox.rotation.x = -Math.PI / 2 // position objects sMesh.translateX(x0) wireframe.translateX(x0) bbox.translateX(x0) // add mGroup.add(sMesh) mGroup.add(wireframe) mGroup.add(bbox) // set object to invisible sMesh.material.visible = false sMesh.castShadow = true sMesh.receiveShadow = false wireframe.material.visible = false bbox.material.visible = false wireframe.castShadow = false wireframe.receiveShadow = false bbox.castShadow = false bbox.receiveShadow = false // compute subdivision if (i < n-1) { m = quadSubdivision(m) catmullClark(m) } // position next subdivision surface x0 += dx } g.add(mGroup) } // loop over models g.children[0].children.forEach( (e,index) => { e.material.visible = true if (index%3 === 0) { e.castShadow = true e.receiveShadow = false } }) //g.children[0].children[0].material.visivle = true // add geometry to scene scene.add(g) // 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: { tetra: true, cube1: false, cube2: false, pawn: false }, rendering: { wireframe: true, flatShading: true, bbox: 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%3 === 0) m.material.visible = flag[index] else if (i%3 === 1) m.material.visible = guiProps.rendering.wireframe else if (i%3 === 2) m.material.visible = guiProps.rendering.bbox }) } }) } const tBox = folderModel.add(guiProps.model, 'tetra') .name('toroidal tetrahedron') .listen() .onChange( v => setModel(g, guiProps, 'tetra', v) ) const cBox1 = folderModel.add(guiProps.model, 'cube1') .name('cube 1') .listen() .onChange( v => setModel(g,guiProps,'cube1', v) ) const cBox2 = folderModel.add(guiProps.model, 'cube2') .name('cube 2') .listen() .onChange( v => setModel(g,guiProps,'cube2',v)) const pBox = folderModel.add(guiProps.model, 'pawn') .name('pawn') .listen() .onChange( v => setModel(g, guiProps, 'pawn', v)) const w = folderRendering.add(guiProps.rendering, 'wireframe').listen().onChange( v => { let mIndex = -1 if (guiProps.model.tetra === true) mIndex = 0 else if (guiProps.model.cube1 === true) mIndex = 1 else if (guiProps.model.cube2 === true) mIndex = 2 else if (guiProps.model.pawn === true) mIndex = 3 if (mIndex !== -1) { g.children[mIndex].children.forEach( (c,index) => { if (index%3 === 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%3 === 0) { m.material.needsUpdate = true m.material.flatShading = v } })) }) const b = folderRendering.add(guiProps.rendering, 'bbox').name('bounding box') .listen().onChange( v => { let mIndex = -1 if (guiProps.model.tetra === true) mIndex = 0 else if (guiProps.model.cube1 === true) mIndex = 1 else if (guiProps.model.cube2 === true) mIndex = 2 else if (guiProps.model.pawn === true) mIndex = 3 if (mIndex !== -1) { g.children[mIndex].children.forEach( (c,index) => { if (index%3 === 2) { c.material.needsUpdate = true c.material.visible = 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') // 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() //////////////////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////////////////// // create vertex and index buffers, and set of points to // render edges. Es edge should be only once in the data function heTesselation(heMesh) { const mesh = {} const vBuff = [] const iBuff = [] const edges = [] const bBox = [] heMesh.vertices.forEach( v => { vBuff.push(v.v[0],v.v[1],v.v[2]) }) heMesh.faces.forEach( f => { // collect vertices const h0 = f.he const h1 = heMesh.halfedges[h0].next const h2 = heMesh.halfedges[h1].next const h3 = heMesh.halfedges[h2].next const v0 = heMesh.halfedges[h0].origin const v1 = heMesh.halfedges[h1].origin const v2 = heMesh.halfedges[h2].origin const v3 = heMesh.halfedges[h3].origin iBuff.push(v0,v1,v2,v0,v2,v3) }) // wireframe heMesh.edges.forEach( e => { const v0 = heMesh.vertices[e.v0] const v1 = heMesh.vertices[e.v1] edges.push(new THREE.Vector3(v0.v[0], v0.v[1], v0.v[2])) edges.push(new THREE.Vector3(v1.v[0], v1.v[1], v1.v[2])) }) // bounding box const {bbox} = heMesh for (let i = 0; i < bbox.length; i += 3) { bBox.push(new THREE.Vector3(bbox[i], bbox[i+1], bbox[i+2])) } mesh.vertices = vBuff mesh.faces = iBuff mesh.edges = edges mesh.bbox = bBox return mesh } // subdivision of quad mesh using halfedge data structure /////////////////////////////////////////////////////////////////////////////// function quadSubdivision(heMesh) { const mesh = {} // copy mesh const halfedges = [] const edges = [] const heFaces = [] const heVertices = [] heMesh.vertices.forEach ( v => { const nv = {index: v.index, he: -1, v: [v.v[0], v.v[1], v.v[2]], type: 'vertex'} heVertices.push(nv) }) // subdivision: face wise const vmap = new Map() heMesh.faces.forEach( f => { // collect const h0 = f.he const h1 = heMesh.halfedges[h0].next const h2 = heMesh.halfedges[h1].next const h3 = heMesh.halfedges[h2].next const v0 = heMesh.halfedges[h0].origin const v1 = heMesh.halfedges[h1].origin const v2 = heMesh.halfedges[h2].origin const v3 = heMesh.halfedges[h3].origin const p0 = heVertices[v0].v const p1 = heVertices[v1].v const p2 = heVertices[v2].v const p3 = heVertices[v3].v // create new vertices const p4 = [ // face vertex 1/4 * (p0[0] + p1[0] + p2[0] + p3[0]), 1/4 * (p0[1] + p1[1] + p2[1] + p3[1]), 1/4 * (p0[2] + p1[2] + p2[2] + p3[2]) ] const p5 = [ // edge 0 1/2 * (p0[0] + p1[0]), 1/2 * (p0[1] + p1[1]), 1/2 * (p0[2] + p1[2]) ] const p6 = [ // edge 1 1/2 * (p1[0] + p2[0]), 1/2 * (p1[1] + p2[1]), 1/2 * (p1[2] + p2[2]) ] const p7 = [ // edge 2 1/2 * (p2[0] + p3[0]), 1/2 * (p2[1] + p3[1]), 1/2 * (p2[2] + p3[2]) ] const p8 = [ // edge 3 1/2 * (p3[0] + p0[0]), 1/2 * (p3[1] + p0[1]), 1/2 * (p3[2] + p0[2]) ] // add vertices to list const id = heVertices.length const fv = {index: id, v: p4, type: 'face'} heVertices.push(fv) // check if vertex was already created by neighbor let id0 = -1 let ev0 = null let key = cantor(v0,v1) let val = vmap.get(key) if (val === undefined) { // vertex does not exists id0 = heVertices.length ev0 = { index: id0, v: p5, type: 'edge' } heVertices.push(ev0) vmap.set(key, ev0) } else { ev0 = val id0 = ev0.index } let id1 = -1 let ev1 = null key = cantor(v1, v2) val = vmap.get(key) if (val === undefined) { id1 = heVertices.length ev1 = {index: id1, v: p6, type: 'edge'} heVertices.push(ev1) vmap.set(key,ev1) } else { ev1 = val id1 = ev1.index } let id2 = -1 let ev2 = null key = cantor(v2, v3) val = vmap.get(key) if (val === undefined) { id2 = heVertices.length ev2 = {index: id2, v: p7, type: 'edge'} heVertices.push(ev2) vmap.set(key,ev2) } else { ev2 = val id2 = ev2.index } let id3 = -1 let ev3 = null key = cantor(v3, v0) val = vmap.get(key) if (val === undefined) { id3 = heVertices.length ev3 = {index: id3, v: p8, type: 'edge'} heVertices.push(ev3) vmap.set(key,ev3) } else { ev3 = val id3 = ev3.index } // create halfedges // current size of arrays const fid = heFaces.length const eid = halfedges.length // faces const f0 = {id: fid, he: -1} const f1 = {id: fid+1, he: -1} const f2 = {id: fid+2, he: -1} const f3 = {id: fid+3, he: -1} heFaces.push(f0, f1, f2, f3) // edges const h4 = {id: eid, face: f0.id, origin: v0, twin: -1 } const h5 = {id: eid+1, face: f0.id, origin: id0, twin: -1 } const h6 = {id: eid+2, face: f0.id, origin: id, twin: -1 } const h7 = {id: eid+3, face: f0.id, origin: id3, twin: -1 } const h8 = {id: eid+4, face: f1.id, origin: id0, twin: -1 } const h9 = {id: eid+5, face: f1.id, origin: v1, twin: -1 } const h10 = {id: eid+6, face: f1.id, origin: id1, twin: -1 } const h11 = {id: eid+7, face: f1.id, origin: id, twin: -1 } const h12 = {id: eid+8, face: f2.id, origin: id, twin: -1 } const h13 = {id: eid+9, face: f2.id, origin: id1, twin: -1 } const h14 = {id: eid+10, face: f2.id, origin: v2, twin: -1 } const h15 = {id: eid+11, face: f2.id, origin: id2, twin: -1 } const h16 = {id: eid+12, face: f3.id, origin: id3, twin: -1 } const h17 = {id: eid+13, face: f3.id, origin: id, twin: -1 } const h18 = {id: eid+14, face: f3.id, origin: id2, twin: -1 } const h19 = {id: eid+15, face: f3.id, origin: v3, twin: -1 } h4.next = h5.id h5.next = h6.id h6.next = h7.id h7.next = h4.id h8.next = h9.id h9.next = h10.id h10.next = h11.id h11.next = h8.id h12.next = h13.id h13.next = h14.id h14.next = h15.id h15.next = h12.id h16.next = h17.id h17.next = h18.id h18.next = h19.id h19.next = h16.id // add edges to list halfedges.push(h4, h5, h6, h7) halfedges.push(h8, h9, h10, h11) halfedges.push(h12, h13, h14, h15) halfedges.push(h16, h17, h18, h19) // set halfedge of faces f0.he = h4.id f1.he = h8.id f2.he = h12.id f3.he = h16.id // set halfedge of vertex heVertices[v0].he = h4.id heVertices[v1].he = h9.id heVertices[v2].he = h14.id heVertices[v3].he = h19.id ev0.he = h8.id ev1.he = h13.id ev2.he = h18.id ev3.he = h7.id fv.he = h6.id }) // mark first every vertex as inner vertex heVertices.forEach ( v => v.bnd = false) // connect twins and find boundary vertices const eMap = new Map() for (let e of halfedges) { const h0 = e.id const h1 = halfedges[h0].next const v0 = halfedges[h0].origin const v1 = halfedges[h1].origin const key = cantor(v0, v1) let value = eMap.get(key) if (value === undefined) eMap.set(key, {he0: e.id, he1: -1}) else value.he1 = e.id } for (const [key, value] of eMap) { const e0 = value.he0 const e1 = value.he1 if (e1 < 0) { halfedges[e0].twin = e1 const next = halfedges[e0].next const origin = halfedges[e0].origin edges.push({v0: origin, v1: halfedges[next].origin}) heVertices[origin].bnd = true heVertices[origin].he = e0 } else { halfedges[e0].twin = e1 halfedges[e1].twin = e0 edges.push({v0: halfedges[e0].origin, v1: halfedges[e1].origin}) } } // construct halfedge mesh mesh.vertices = heVertices mesh.faces = heFaces mesh.halfedges = halfedges mesh.edges = edges mesh.bbox = heMesh.bbox return mesh } // compute one ring, consider boundaries function oneRing(v, vertices, halfedges) { const neigh = [] const h0 = vertices[v.index].he let hn = h0 let h3 = -1 do { const h1 = halfedges[hn].next neigh.push(vertices[halfedges[h1].origin]) const h2 = halfedges[h1].next neigh.push(vertices[halfedges[h2].origin]) h3 = halfedges[h2].next hn = halfedges[h3].twin } while(hn != h0 && hn !== -1) if (hn === -1) { neigh.push(vertices[halfedges[h3].origin]) } return neigh } /////////////////////////////////////////////////////////////////////////////// // Catmull-Clark smoothing /////////////////////////////////////////////////////////////////////////////// function catmullClark(mesh) { const iVertices = [] const {vertices, halfedges} = mesh vertices.forEach( v => { const nv = [v.v[0], v.v[1], v.v[2]] iVertices.push(nv) }) // three pass: // 1. pass: faces vertices vertices.forEach( (v, index, vArray) => { if (v.bnd === false) { if (v.type === 'edge') { const neigh = oneRing(v, vArray, halfedges) // reposition vertex const p = [0,0,0] neigh.forEach( nv => { if (nv.type === 'face') { p[0] += iVertices[nv.index][0] p[1] += iVertices[nv.index][1] p[2] += iVertices[nv.index][2] } }) v.v[0] = (iVertices[v.index][0] + p[0] / 2) / 2 v.v[1] = (iVertices[v.index][1] + p[1] / 2) / 2 v.v[2] = (iVertices[v.index][2] + p[2] / 2) / 2 } if (v.type === 'vertex') { const neigh = oneRing(v, vertices, halfedges) const F = [0,0,0] const E = [0,0,0] let valence = 0 neigh.forEach( nv => { if (nv.type === 'face') { valence++ F[0] += iVertices[nv.index][0] F[1] += iVertices[nv.index][1] F[2] += iVertices[nv.index][2] } else if (nv.type === 'edge') { E[0] += iVertices[nv.index][0] E[1] += iVertices[nv.index][1] E[2] += iVertices[nv.index][2] } }) F[0] /= valence F[1] /= valence F[2] /= valence E[0] /= valence E[1] /= valence E[2] /= valence v.v[0] = (F[0] + 2*E[0] + (valence-3)*iVertices[v.index][0]) / valence v.v[1] = (F[1] + 2*E[1] + (valence-3)*iVertices[v.index][1]) / valence v.v[2] = (F[2] + 2*E[2] + (valence-3)*iVertices[v.index][2]) / valence } else { if (v.type === 'vertex') { const neigh = oneRing(v, vertices, halfedges) const v0 = neigh[0] const v1 = neigh[neigh.length-1] v.v[0] = 1/4 * (iVertices[v0][0] + iVertices[v1][0]) + 3/4 * iVertices[v.index][0] v.v[1] = 1/4 * (iVertices[v0][1] + iVertices[v1][1]) + 3/4 * iVertices[v.index][1] v.v[2] = 1/4 * (iVertices[v0][2] + iVertices[v1][2]) + 3/4 * iVertices[v.index][2] } } } // inner vertex else { // boundary vertex if (v.type === 'vertex') { const neigh = oneRing(v, vertices, halfedges) const v0 = neigh[0] const v1 = neigh.at(-1) const p = [0,0,0] p[0] = 1/2 * v.v[0] + 1/4 * (v0.v[0] + v1.v[0]) p[1] = 1/2 * v.v[1] + 1/4 * (v0.v[1] + v1.v[1]) p[2] = 1/2 * v.v[2] + 1/4 * (v0.v[2] + v1.v[2]) vertices[v.index].v = p } } }) } // compute the boundring box from max and min coordinates function boundingBox(xMin,xMax,yMin,yMax,zMin,zMax) { const bbox = [] bbox.push(xMin,yMin,zMin,xMax,yMin,zMin) // edge 0 bbox.push(xMax,yMin,zMin,xMax,yMax,zMin) // edge 1 bbox.push(xMax,yMax,zMin,xMin,yMax,zMin) // edge 2 bbox.push(xMin,yMax,zMin,xMin,yMin,zMin) // edge 3 bbox.push(xMin,yMin,zMax,xMax,yMin,zMax) // edge 4 bbox.push(xMax,yMin,zMax,xMax,yMax,zMax) // edge 5 bbox.push(xMax,yMax,zMax,xMin,yMax,zMax) // edge 6 bbox.push(xMin,yMax,zMax,xMin,yMin,zMax) // edge 7 bbox.push(xMin,yMin,zMin,xMin,yMin,zMax) // edge 8 bbox.push(xMax,yMin,zMin,xMax,yMin,zMax) // edge 9 bbox.push(xMax,yMax,zMin,xMax,yMax,zMax) // edge 10 bbox.push(xMin,yMax,zMin,xMin,yMax,zMax) // edge 11 return bbox } // computes a halfedge data structure out of // an indexed face set function heMeshFromQuadIndexedFaceSet(quadMesh) { const heMesh = {} const halfedges = [] const edges = [] const heFaces = [] const heVertices = [] // create vertices and c let xMin = Number.MAX_VALUE let xMax = -Number.MAX_VALUE let yMin = Number.MAX_VALUE let yMax = -Number.MAX_VALUE let zMin = Number.MAX_VALUE let zMax = -Number.MAX_VALUE quadMesh.vertices.forEach( (v,index) => { xMin = Math.min(xMin,v[0]) xMax = Math.max(xMax,v[0]) yMin = Math.min(yMin,v[1]) yMax = Math.max(yMax,v[1]) zMin = Math.min(zMin,v[2]) zMax = Math.max(zMax,v[2]) heVertices.push({index: index, he: -1, v: v}) }) const map = new Map() quadMesh.faces.forEach( (f,index) => { const v0 = f[0] - 1 const v1 = f[1] - 1 const v2 = f[2] - 1 const v3 = f[3] - 1 const he0 = {id: 4*index, face: index, origin: v0, twin: -1} const he1 = {id: 4*index + 1, face: index, origin: v1, twin: -1} const he2 = {id: 4*index + 2, face: index, origin: v2, twin: -1} const he3 = {id: 4*index + 3, face: index, origin: v3, twin: -1} const hf = {id: index, he: 4*index} // connect heVertices[v0].he = he0.id heVertices[v1].he = he1.id heVertices[v2].he = he2.id heVertices[v3].he = he3.id he0.next = he1.id he1.next = he2.id he2.next = he3.id he3.next = he0.id // collect heFaces.push(hf) halfedges.push(he0, he1, he2, he3) }) // boundary vertices heVertices.forEach ( v => v.bnd = false) // neighborhood const eMap = new Map() for (let e of halfedges) { const h0 = e.id const h1 = e.next const v0 = e.origin const v1 = halfedges[h1].origin const key = cantor(v0, v1) let value = eMap.get(key) if (value === undefined) eMap.set(key, {he0: e.id, he1: -1}) else value.he1 = e.id } for (const [key, value] of eMap) { const e0 = value.he0 const e1 = value.he1 if (e1 < 0) { halfedges[e0].twin = e1 const next = halfedges[e0].next const origin = halfedges[e0].origin edges.push({v0: origin, v1: halfedges[next].origin}) // mark vertices as boundary vertices heVertices[origin].bnd = true // set start edge for iteration heVertices[origin].he = e0 } else { halfedges[e0].twin = e1 halfedges[e1].twin = e0 edges.push({v0: halfedges[e0].origin, v1: halfedges[e1].origin}) } } // compute mesh heMesh.vertices = heVertices heMesh.faces = heFaces heMesh.halfedges = halfedges heMesh.edges = edges heMesh.bbox = boundingBox(xMin,xMax,yMin,yMax,zMin,zMax) return heMesh } // compute center of mesh function computeCenter(mesh) { const c = [0,0,0] const n = mesh.vertices.length mesh.vertices.forEach( v => { c[0] += v.v[0] c[1] += v.v[1] c[2] += v.v[2] }) c[0] /= n c[1] /= n c[2] /= n return c } // remove array from memory after upload on GPU function disposeArray() { this.array = null; } // construct a unique key out of two integers using Cantor's map function cantor(k1, k2) { if (k1 > k2) { return (k1+k2)*(k1+k2+1)/2 + k2 } else { return (k1+k2)*(k1+k2+1)/2 + k1 } } // translate center of mesh to origin function translate(mesh) { let x = 0 let y = 0 let z = 0 mesh.vertices.forEach( v => { x += v.v[0] y += v.v[1] z += v.v[2] }) x /= mesh.vertices.length y /= mesh.vertices.length z /= mesh.vertices.length mesh.vertices.forEach( v => { v.v[0] -= x v.v[1] -= y v.v[2] -= z }) // compute bounding box for (let i = 0; i < mesh.bbox.length; i += 3) { mesh.bbox[i] -= x mesh.bbox[i+1] -= y mesh.bbox[i+2] -= z } return mesh } // uniform scaling by factor s function scale(mesh, s) { mesh.vertices.forEach( v => { v.v[0] *= s v.v[1] *= s v.v[2] *= s }) mesh.bbox.forEach( (v,index,arr) => { arr[index] *= s }) return mesh } }, update: function(txt, json, canvasElement, outputElement) { } }

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

Geometric Modeling