2b:null 2c:["$","title",null,{"children":"Mesh Data Structures & Traversal | Tim Henning | Observable"}] 31:T509,md`# Mesh Data Structures & Traversal Two common mesh data structures are face-vertex lists and the half-edge data structure. Each has its own advantages and disadvantages. In the first part, I'll discuss each data structure, and compare them. In the second part, I'll explain and demonstrate mesh traversal algorithms. ## Face-Vertex Lists The FV mesh data structure is extremely simple and intuitive. It typically consists of an ordered array of vertices, and a list of faces. Each face is a list of the indices of the vertices that form its boundary. In this data structure, edges are implicit in the sequence of verts around the face. One of the largest advantages of this data structure is how easy it is to populate. In addition, it makes no assumptions about the structure of the data, which can be an advantage or a disadvantage. In some cases this is desirable, and can support arbitrary arrangements of polygons. However, it encodes very little information about the structure of the mesh, which makes traversals and mesh modification without another data structure slow. For static meshes that don't need computations done regarding connectivity, the FV mesh is an excellent structure. For example, \`Three.js\` (the library I use for visualizations), uses this structure. `32:T718,md` ## Half-Edge Data Structure The half-edge data structure, or Doubly-Connected Edge List (DCEL), encodes much more information than the FV mesh. Unlike the FV mesh, a DCEL makes a very important strong assumption about the mesh: the mesh must be manifold. For a mesh to be manifold, two conditions must hold. First, the adjacent faces around a vert must be able to be ordered so that their vertices (other than the common vertex) form a simple chain. Second, each edge must be shared by no more than two faces. While these conditions may seem restrictive, they are a necessary (but not sufficient) condition for a mesh that represents the boundary of a volume. A DCEL consists of a list of vertices, halfedges and vertices. Each vertex stores its position and one outgoing halfedge. Each halfedge stores the origin vertex, and the end vertex. In addition, the halfedge stores pointers to its previous, next, and twin halfedges. The twin is the halfedge along the same edge, but pointing in the opposite direction. The next halfedge is the next halfedge forward around the adjacent face. The previous halfedge is the halfedge moving backwards around the adjacent face. Faces can also be stored in the halfedge data structure but are optional, as they can be inferred by following half edges around a face. If they are to be stored, a face has a pointer to an arbitrary halfedge on its boundary, and each halfedge has a pointer to its adjacent face. Because the halfedges around a face form an order, orientation of a face can be inferred. Strictly speaking, the data structure only needs to store the origin, next, and twin for each halfedge, but the pointers to the end vertex and previous halfedge are stored for convenience. They can be obtained fairly easily by traversing the halfedge data structure. `33:T601,html` `34:T761,HalfEdgeMesh = { function HalfEdgeMesh(){ this.verts = []; this.edges = {}; this.geom = null; // Store the original geometry too } HalfEdgeMesh.prototype.addVert = function(point){ this.verts.push(new Vertex(point)); } HalfEdgeMesh.prototype.addHalfEdge = function(head,tail){ if(!([head,tail] in this.edges)){ // To store halfedges, we use the head and tail as a key to reference the halfedge object. var E = new HalfEdge(this.verts[head],this.verts[tail]); this.edges[[head,tail]] = E; return E; } } HalfEdgeMesh.prototype.populateFromThreeGeom = function(geom){ this.geom = geom; for(var V in geom.vertices){ //Populate the vertices. Three.js uses index-based vert references, so we will too. this.addVert(geom.vertices[V]); } for(var faceIndex in geom.faces){ var F = geom.faces[faceIndex]; // Each face is a tri, so we know what the vert pairs are for each face. var vertPairs = [[F.a,F.b],[F.b,F.c],[F.c,F.a]]; for(var i = 0; i<3; i++){ var E=vertPairs[i]; // Create our half edges var newEdge = this.addHalfEdge(E[0],E[1]); newEdge.face = F; // If the source vert doesn't have a half-edge yet, populate it. if(this.verts[E[0]].halfedge == null){ this.verts[E[0]].halfedge = newEdge; } } for(var i=0; i<3; i++){ var E = vertPairs[i] // We know the next from the order around our tri, so populate that this.edges[E].next = this.edges[vertPairs[(i+1) % 3]]; // Look for the halfedge going the opposite direction to populate the twin. if([E[1],E[0]] in this.edges){ this.edges[E].twin = this.edges[[E[1],E[0]]]; this.edges[[E[1],E[0]]].twin = this.edges[E]; } } } } return HalfEdgeMesh }35:T4b1,scene = { const scene = new THREE.Scene(); scene.background = new THREE.Color(0xFFFFFF); var obj = new THREE.IcosahedronGeometry(1); var material = new THREE.MeshBasicMaterial( {vertexColors:THREE.FaceColors} ); var wirematerial = new THREE.MeshBasicMaterial( {color:0x000000, wireframe: true, transparent:true}); for(var F in obj.faces){ obj.faces[F].color = new THREE.Color(0xbbd3f9); } var cube = new THREE.Mesh(obj, material); var objwiremesh = new THREE.Mesh(obj,wirematerial); scene.add( objwiremesh ); scene.add( cube ); var hem = new HalfEdgeMesh(); hem.populateFromThreeGeom(obj); sceneObjects["hem"] = hem; sceneObjects["currentEdge"] = hem.edges[[0,1]]; var dir = sceneObjects["currentEdge"].tail.point.clone(); dir.sub(sceneObjects["currentEdge"].head.point); var length = dir.length(); dir.normalize(); var origin = sceneObjects["currentEdge"].head.point; var CEArrow = new THREE.ArrowHelper(dir, origin, length, 0x000000); sceneObjects["CEArrow"] = CEArrow; scene.add( CEArrow); sceneObjects.currentEdge.face.color= new THREE.Color(0x77a3ea); sceneObjects.hem.geom.elementsNeedUpdate = true; return scene; }36:[] 2f:{"id":"deb61103fb7c1e7f","slug":"mesh-data-structures-traversal","title":"Mesh Data Structures & Traversal","thumbnail":"8c5634e84880f69c9e1402bfa46fd06921ab5a2d70af006c6e612878f7eb60e1","access_level":"public","create_time":"$D2018-09-16T16:58:36.068Z","update_time":"$D2018-12-08T00:18:24.412Z","view_time":null,"first_public_time":"$D2018-12-07T03:16:08.788Z","fork":false,"stars":9,"starred":false,"owner":{"type":"team","id":"87a3845f24186372","login":"2talltim","name":"Tim Henning","avatar_url":"https://avatars-next.observableusercontent.com/8964efd53fa9def0b85fc46a61a9e09e500d3b7eb2d4da34deb9cc6cc524e398","tier":"starter_2024"},"version":320,"publish_version":320,"role":null,"authored":false,"authors":[{"type":"individual","id":"8ed5bea0fbd58bf6","login":"2talltim","name":"Tim Henning","avatar_url":"https://avatars-next.observableusercontent.com/8964efd53fa9def0b85fc46a61a9e09e500d3b7eb2d4da34deb9cc6cc524e398","tier":null}],"members":[{"type":"individual","id":"8ed5bea0fbd58bf6","login":"2talltim","name":"Tim Henning","avatar_url":"https://avatars-next.observableusercontent.com/8964efd53fa9def0b85fc46a61a9e09e500d3b7eb2d4da34deb9cc6cc524e398","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":10,"collection":null,"type":"notebook","body":{"title":"Mesh Data Structures & Traversal","cells":[{"id":0,"value":"$31","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":129,"value":"$32","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":13,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":118,"value":"md`\nBecause \\`Three.js\\` uses an FV data structure, we must create our own DCEL data type. The code is shown at the bottom. In the visualization below, click the next and twin buttons to step through the generated halfedge data structure.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":318,"value":"md`\n## Traversals\n\nThe nature of the halfedge data structure is such that traversing the mesh is the same as traversing a graph data structure of its edges. Click and drag on the object below to orbit around. The highlighted face is the currently active face. Click on the buttons to traverse the halfedge data structure.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":174,"value":"viz = {\n const renderer = new THREE.WebGLRenderer({antialias:true});\n const controls = new THREE.OrbitControls(camera,renderer.domElement);\n renderer.setSize(width,height);\n renderer.setPixelRatio(devicePixelRatio);\n invalidation.then(() => (controls.dispose(), renderer.dispose()));\n controls.addEventListener(\"change\", () => renderer.render(scene, camera));\n while (true){\n update();\n renderer.render(scene, camera);\n yield renderer.domElement;\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":213,"value":"viewof nextBTN = button({value: \"Next\"})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":260,"value":"viewof twinBTN = button({value: \"Twin\"})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":126,"value":"function HalfEdge(tail,head){\n this.head = head; //Integer index in vertex list\n this.tail = tail; //Integer index in vertex list\n this.next = null;\n this.twin = null;\n this.face = null;\n //Here, the next and twin values will be populated as the mesh is created.\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":142,"value":"function Vertex(point){\n this.point = point; // Coordinate position\n this.halfedge = null;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":147,"value":"$34","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":189,"value":"sceneObjects = ({})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":176,"value":"update = {\n var clock = new THREE.Clock();\n return function update(){\n var delta = clock.getDelta();\n //do something\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":178,"value":"camera = {\n const fov = 30;\n const aspect = width / height;\n const near = 1;\n const far = 1000;\n const camera = new THREE.PerspectiveCamera(fov, aspect, near, far);\n camera.position.set(0, 4, 4)\n camera.lookAt(new THREE.Vector3(0, 0, 0));\n return camera;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":180,"value":"height = 500","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":221,"value":"{\n nextBTN;\n sceneObjects.currentEdge = sceneObjects.currentEdge.next;\n updateArrow();\n sceneObjects.hem.geom.elementsNeedUpdate = true;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":262,"value":"{\n twinBTN;\n sceneObjects.currentEdge.face.color= new THREE.Color(0xbbd3f9);\n sceneObjects.currentEdge = sceneObjects.currentEdge.twin;\n sceneObjects.currentEdge.face.color= new THREE.Color(0x77a3ea);\n sceneObjects.hem.geom.elementsNeedUpdate = true;\n updateArrow();\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":267,"value":"updateArrow = function(){\n var tail = sceneObjects[\"currentEdge\"].tail.point.clone();\n tail.multiplyScalar(1.1);\n var head = sceneObjects[\"currentEdge\"].head.point.clone();\n head.multiplyScalar(1.1);\n var dir = head.clone();\n dir.sub(tail);\n var length = dir.length();\n dir.normalize();\n var origin = tail;\n sceneObjects[\"CEArrow\"].setDirection( dir );\n sceneObjects[\"CEArrow\"].setLength(length);\n sceneObjects[\"CEArrow\"].position.set( origin.x, origin.y, origin.z);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":167,"value":"$35","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":163,"value":"THREE = {\n const THREE = window.THREE = await require(\"three@0.96/build/three.min.js\");\n await require(\"three@0.96/examples/js/controls/OrbitControls.js\").catch(() => {});\n return THREE;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":227,"value":"import {button} from \"@jashkenas/inputs\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W36","stdlib":"1","titling":"auto"}} 30:"$2f:body"