Skip to content

GitLab

Switch branch/tag
Find file Normal viewHistoryPermalink
halfedge.html 23.6 KB
Newer Older
allai5's avatar
add data and site info    
allai5 committed
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33 
<!DOCTYPE html> <html lang="en-US"> <head> <meta charset="UTF-8"> <meta http-equiv="X-UA-Compatible" content="IE=Edge"> <title>Halfedge Mesh - </title> <link rel="shortcut icon" href="/favicon.ico" type="image/x-icon"> <link rel="stylesheet" href="/assets/css/just-the-docs-default.css"> <script type="text/javascript" src="/assets/js/vendor/lunr.min.js"></script> <script type="text/javascript" src="/assets/js/just-the-docs.js"></script> <meta name="viewport" content="width=device-width, initial-scale=1"> <!-- Begin Jekyll SEO tag v2.7.1 --> <title>Halfedge Mesh</title> <meta name="generator" content="Jekyll v4.2.0" /> <meta property="og:title" content="Halfedge Mesh" /> <meta property="og:locale" content="en_US" /> <meta name="twitter:card" content="summary" /> <meta property="twitter:title" content="Halfedge Mesh" /> <script type="application/ld+json"> {"headline":"Halfedge Mesh","@type":"WebPage","url":"/meshedit/halfedge","@context":"https://schema.org"}</script> <!-- End Jekyll SEO tag --> </head> <body> <svg xmlns="http://www.w3.org/2000/svg" style="display: none;"> <symbol id="svg-link" viewBox="0 0 24 24"> <title>Link</title> <svg xmlns="http://www.w3.org/2000/svg" width="24" height="24" viewBox="0 0 24 24" fill="none" stroke="currentColor" stroke-width="2" stroke-linecap="round" stroke-linejoin="round" class="feather feather-link"> <path d="M10 13a5 5 0 0 0 7.54.54l3-3a5 5 0 0 0-7.07-7.07l-1.72 1.71"></path><path d="M14 11a5 5 0 0 0-7.54-.54l-3 3a5 5 0 0 0 7.07 7.07l1.71-1.71"></path> </svg> </symbol> <symbol id="svg-search" viewBox="0 0 24 24"> <title>Search</title> <svg xmlns="http://www.w3.org/2000/svg" width="24" height="24" viewBox="0 0 24 24" fill="none" stroke="currentColor" stroke-width="2" stroke-linecap="round" stroke-linejoin="round" class="feather feather-search"> <circle cx="11" cy="11" r="8"></circle><line x1="21" y1="21" x2="16.65" y2="16.65"></line> </svg> </symbol> <symbol id="svg-menu" viewBox="0 0 24 24"> <title>Menu</title> <svg xmlns="http://www.w3.org/2000/svg" width="24" height="24" viewBox="0 0 24 24" fill="none" stroke="currentColor" stroke-width="2" stroke-linecap="round" stroke-linejoin="round" class="feather feather-menu"> <line x1="3" y1="12" x2="21" y2="12"></line><line x1="3" y1="6" x2="21" y2="6"></line><line x1="3" y1="18" x2="21" y2="18"></line> </svg> </symbol> <symbol id="svg-arrow-right" viewBox="0 0 24 24"> <title>Expand</title> <svg xmlns="http://www.w3.org/2000/svg" width="24" height="24" viewBox="0 0 24 24" fill="none" stroke="currentColor" stroke-width="2" stroke-linecap="round" stroke-linejoin="round" class="feather feather-chevron-right"> <polyline points="9 18 15 12 9 6"></polyline> </svg> </symbol> <symbol id="svg-doc" viewBox="0 0 24 24"> <title>Document</title> <svg xmlns="http://www.w3.org/2000/svg" width="24" height="24" viewBox="0 0 24 24" fill="none" stroke="currentColor" stroke-width="2" stroke-linecap="round" stroke-linejoin="round" class="feather feather-file"> <path d="M13 2H6a2 2 0 0 0-2 2v16a2 2 0 0 0 2 2h12a2 2 0 0 0 2-2V9z"></path><polyline points="13 2 13 9 20 9"></polyline> </svg> </symbol> </svg> <div class="side-bar"> <div class="site-header"> <a href="/" class="site-title lh-tight"> </a> <a href="#" id="menu-button" class="site-button"> <svg viewBox="0 0 24 24" class="icon"><use xlink:href="#svg-menu"></use></svg> </a> </div> <nav role="navigation" aria-label="Main" id="site-nav" class="site-nav"> <ul class="nav-list"><li class="nav-list-item"><a href="/" class="nav-list-link">Home</a></li><li class="nav-list-item"><a href="/git/" class="nav-list-link">GitHub Setup</a></li><li class="nav-list-item"><a href="/build/" class="nav-list-link">Building Scotty3D</a></li><li class="nav-list-item"><a href="#" class="nav-list-expander"><svg viewBox="0 0 24 24"><use xlink:href="#svg-arrow-right"></use></svg></a><a href="/guide/" class="nav-list-link">User Guide</a><ul class="nav-list "><li class="nav-list-item "><a href="/guide/animate_mode/" class="nav-list-link">Animate</a></li><li class="nav-list-item "><a href="/guide/layout_mode/" class="nav-list-link">Layout</a></li><li class="nav-list-item "><a href="/guide/model_mode/" class="nav-list-link">Model</a></li><li class="nav-list-item "><a href="/guide/render_mode/" class="nav-list-link">Render</a></li><li class="nav-list-item "><a href="/guide/rigging_mode/" class="nav-list-link">Rig</a></li><li class="nav-list-item "><a href="/guide/simulate_mode/" class="nav-list-link">Simulate</a></li></ul></li><li class="nav-list-item active"><a href="#" class="nav-list-expander"><svg viewBox="0 0 24 24"><use xlink:href="#svg-arrow-right"></use></svg></a><a href="/meshedit/" class="nav-list-link">A2: MeshEdit</a><ul class="nav-list "><li class="nav-list-item active"><a href="/meshedit/halfedge" class="nav-list-link active">Halfedge Mesh</a></li><li class="nav-list-item "><a href="#" class="nav-list-expander"><svg viewBox="0 0 24 24"><use xlink:href="#svg-arrow-right"></use></svg></a><a href="/meshedit/local/" class="nav-list-link">Local Operations</a><ul class="nav-list"><li class="nav-list-item "> <a href="/meshedit/local/edge_flip" class="nav-list-link">Edge Flip Tutorial</a> </li><li class="nav-list-item "> <a href="/meshedit/local/bevel/" class="nav-list-link">Bevelling</a> </li></ul></li><li class="nav-list-item "><a href="#" class="nav-list-expander"><svg viewBox="0 0 24 24"><use xlink:href="#svg-arrow-right"></use></svg></a><a href="/meshedit/global/" class="nav-list-link">Global Operations</a><ul class="nav-list"><li class="nav-list-item "> <a href="/meshedit/global/catmull/" class="nav-list-link">Catmull-Clark Subdivision</a> </li><li class="nav-list-item "> <a href="/meshedit/global/remesh/" class="nav-list-link">Isotropic Remeshing</a> </li><li class="nav-list-item "> <a href="/meshedit/global/linear/" class="nav-list-link">Linear Subdivision</a> </li><li class="nav-list-item "> <a href="/meshedit/global/loop/" class="nav-list-link">Loop Subdivision</a> </li><li class="nav-list-item "> <a href="/meshedit/global/simplify/" class="nav-list-link">Simplification</a> </li><li class="nav-list-item "> <a href="/meshedit/global/triangulate/" class="nav-list-link">Triangulation</a> </li></ul></li></ul></li><li class="nav-list-item"><a href="#" class="nav-list-expander"><svg viewBox="0 0 24 24"><use xlink:href="#svg-arrow-right"></use></svg></a><a href="/pathtracer/" class="nav-list-link">A3: Pathtracer</a><ul class="nav-list "><li class="nav-list-item "><a href="/pathtracer/camera_rays" class="nav-list-link">(Task 1) Camera Rays</a></li><li class="nav-list-item "><a href="#" class="nav-list-expander"><svg viewBox="0 0 24 24"><use xlink:href="#svg-arrow-right"></use></svg></a><a href="/pathtracer/intersecting_objects" class="nav-list-link">(Task 2) Intersections</a><ul class="nav-list"><li class="nav-list-item "> <a href="/pathtracer/ray_triangle_intersection" class="nav-list-link">Ray Triangle Intersection</a> </li><li class="nav-list-item "> <a href="/pathtracer/ray_sphere_intersection" class="nav-list-link">Ray Sphere Intersection</a> </li></ul></li><li class="nav-list-item "><a href="/pathtracer/bounding_volume_hierarchy" class="nav-list-link">(Task 3) BVH</a></li><li class="nav-list-item "><a href="/pathtracer/shadow_rays" class="nav-list-link">(Task 4) Shadow Rays</a></li><li class="nav-list-item "><a href="/pathtracer/path_tracing" class="nav-list-link">(Task 5) Path Tracing</a></li><li class="nav-list-item "><a href="#" class="nav-list-expander"><svg viewBox="0 0 24 24"><use xlink:href="#svg-arrow-right"></use></svg></a><a href="/pathtracer/materials" class="nav-list-link">(Task 6) Materials</a><ul class="nav-list"><li class="nav-list-item "> <a href="/pathtracer/dielectrics_and_transmission" class="nav-list-link">Dielectrics and Transmission</a> </li></ul></li><li class="nav-list-item "><a href="#" class="nav-list-expander"><svg viewBox="0 0 24 24"><use xlink:href="#svg-arrow-right"></use></svg></a><a href="/pathtracer/environment_lighting" class="nav-list-link">(Task 7) Environment Lighting</a><ul class="nav-list"><li class="nav-list-item "> <a href="/pathtracer/importance_sampling" class="nav-list-link">Environment Light Importance Sampling</a> </li></ul></li><li class="nav-list-item "><a href="/pathtracer/visualization_of_normals" class="nav-list-link">Visualization of normals</a></li></ul></li><li class="nav-list-item"><a href="#" class="nav-list-expander"><svg viewBox="0 0 24 24"><use xlink:href="#svg-arrow-right"></use></svg></a><a href="/animation/" class="nav-list-link">A4: Animation</a><ul class="nav-list "><li class="nav-list-item "><a href="/animation/splines" class="nav-list-link">Splines</a></li><li class="nav-list-item "><a href="/animation/skeleton_kinematics" class="nav-list-link">Skeleton Kinematics</a></li><li class="nav-list-item "><a href="/animation/skinning" class="nav-list-link">Skinning</a></li><li class="nav-list-item "><a href="/animation/particles" class="nav-list-link">Particles</a></li></ul></li></ul> </nav> <footer class="site-footer"> This site uses <a href="https://github.com/pmarsceill/just-the-docs">Just the Docs</a>, a documentation theme for Jekyll. </footer> </div> <div class="main" id="top"> <div id="main-header" class="main-header"> <div class="search"> <div class="search-input-wrap"> <input type="text" id="search-input" class="search-input" tabindex="0" placeholder="Search " aria-label="Search " autocomplete="off"> <label for="search-input" class="search-label"><svg viewBox="0 0 24 24" class="search-icon"><use xlink:href="#svg-search"></use></svg></label> </div> <div id="search-results" class="search-results"></div> </div> </div> <div id="main-content-wrap" class="main-content-wrap"> <nav aria-label="Breadcrumb" class="breadcrumb-nav"> <ol class="breadcrumb-nav-list"> <li class="breadcrumb-nav-list-item"><a href="/meshedit/">A2: MeshEdit</a></li> <li class="breadcrumb-nav-list-item"><span>Halfedge Mesh</span></li> </ol> </nav> <div id="main-content" class="main-content" role="main"> <h1 id="halfedge-mesh"> <a href="#halfedge-mesh" class="anchor-heading" aria-labelledby="halfedge-mesh"><svg viewBox="0 0 16 16" aria-hidden="true"><use xlink:href="#svg-link"></use></svg></a> Halfedge Mesh </h1> <h2 id="geometric-data-structures"> <a href="#geometric-data-structures" class="anchor-heading" aria-labelledby="geometric-data-structures"><svg viewBox="0 0 16 16" aria-hidden="true"><use xlink:href="#svg-link"></use></svg></a> Geometric Data Structures </h2> <p>Scotty3D uses a variety of geometric data structures, depending on the task. Some operations (e.g., ray tracing) use a simple list of triangles that can be compactly encoded and efficiently cached. For more sophisticated geometric tasks like mesh editing and sampling, a simple triangle list is no longer sufficient (or leads to unnecessarily poor asymptotic performance). Most actions in MeshEdit mode therefore use a topological data structure called a <em>halfedge mesh</em> (also known as a <em>doubly-connected</em> edge list), which provides a good tradeoff between simplicity and sophistication.</p> <h3 id="the-halfedge-data-structure"> <a href="#the-halfedge-data-structure" class="anchor-heading" aria-labelledby="the-halfedge-data-structure"><svg viewBox="0 0 16 16" aria-hidden="true"><use xlink:href="#svg-link"></use></svg></a> The Halfedge Data Structure </h3> <p>The basic idea behind the halfedge data structure is that, in addition to the usual vertices, edges, and faces that make up a polygonal mesh, we also have an entity called a <em>halfedge</em> that acts like “glue” connecting the different elements. It is this glue that allow us to easily “navigate” the mesh, i.e., easily access mesh elements adjacent to a given element.</p> <center><img src="halfedge_pointers.png" style="height:240px" /></center> <p>In particular, there are two halfedges associated with each edge (see picture above). For an edge connecting two vertices i and j, one of its halfedges points from i to j; the other one points from j to i. In other words, we say that the two halfedges are <em>oppositely oriented</em>. On of the halfedges is associated with the face to the “left” of the edge; the other is associated with the face to the “right.” Each halfedge knows about the opposite halfedge, which we call its <em>twin</em>. It also knows about the <em>next</em> halfedge around its face, as well as its associated edge, face, and vertex.</p> <p>In contrast, the standard mesh elements (vertices, edges, and faces) know only about <em>one</em> of their halfedges. In particular:</p> <ul> <li>a vertex knows about one of its “outgoing” halfedges,</li> <li>an edge knows about one of its two halfedges, and</li> <li>a face knows about one of the many halfedges circulating around its interior.</li> </ul> <p>In summary, we have the following relationships:</p> <div class="table-wrapper"><table> <thead> <tr> <th>Mesh Element</th> <th>Pointers</th> </tr> </thead> <tbody> <tr> <td>Vertex</td> <td>halfedge (just one)</td> </tr> <tr> <td>Edge</td> <td>halfedge (just one)</td> </tr> <tr> <td>Face</td> <td>halfedge (just one)</td> </tr> <tr> <td>Halfedge</td> <td>next, twin, vertex, edge, face</td> </tr> </tbody> </table></div> <p>This list emphasizes that it is really the <strong>halfedges</strong> that connect everything up. An easy example is if we want to visit all the vertices of a given face. We can start at the face’s halfedge, and follow the “next” pointer until we’re back at the beginning. A more interesting example is visiting all the vertices adjacent to a given vertex v. We can start by getting its outgoing halfedge, then its twin, then its next halfedge; this final halfedge will also point out of vertex v, but it will point <strong>toward</strong> a different vertex than the first halfedge. By repeating this process, we can visit all the neighboring vertices:</p> <center><img src="vertex_traversal.png" style="height:360px" /></center> <p>In some sense, a halfedge mesh is kind of like a supercharged linked list. For instance, the halfedges around a given face (connected by <code class="language-plaintext highlighter-rouge">next</code> pointers) form a sort of “cyclic” linked list, where the tail points back to the head.</p> <p>A nice consequence of the halfedge representation is that any valid halfedge mesh <strong>must</strong> be manifold and orientable. Scotty3D will therefore only produce manifold, oriented meshes as output (and will complain if the input does not satisfy these criteria).</p> <h3 id="the-halfedge_mesh-class"> <a href="#the-halfedge_mesh-class" class="anchor-heading" aria-labelledby="the-halfedge_mesh-class"><svg viewBox="0 0 16 16" aria-hidden="true"><use xlink:href="#svg-link"></use></svg></a> The <code class="language-plaintext highlighter-rouge">Halfedge_Mesh</code> Class </h3> <p>The Scotty3D skeleton code already provides a fairly sophisticated implementation of the half edge data structure, in the <code class="language-plaintext highlighter-rouge">Halfedge_Mesh</code> class (see <code class="language-plaintext highlighter-rouge">geometry/halfedge.h</code> and <code class="language-plaintext highlighter-rouge">geometry/halfedge.cpp</code>). Although the detailed implementation may appear a bit complicated, the basic interface is not much different from the abstract description given above. For instance, suppose we have a face f and want to print out the positions of all its vertices. We would write a routine like this:</p> <div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>void printVertexPositions(FaceRef f) {
  HalfEdgeRef h = f-&gt;halfedge(); // get the first halfedge of the face
  do {
    VertexRef v = h-&gt;vertex();   // get the vertex of the current halfedge
    cout &lt;&lt; v-&gt;pos &lt;&lt; endl;      // print the vertex position
    h = h-&gt;next();               // move to the next halfedge around the face
  } while (h != f-&gt;halfedge());  // keep going until we're back at the beginning
}
</code></pre></div></div> <p>Notice that we refer to a face as a <code class="language-plaintext highlighter-rouge">FaceRef</code> rather than just a <code class="language-plaintext highlighter-rouge">Face</code>. You can think of a <code class="language-plaintext highlighter-rouge">Ref</code> as a kind of <em>pointer</em>. Note that members of an iterator are accessed with an arrow <code class="language-plaintext highlighter-rouge">-&gt;</code> rather than a dot <code class="language-plaintext highlighter-rouge">.</code>, just as with pointers. (A more in-depth explanation of some of these details can be found in the inline documentation.) Similarly, to print out the positions of all the neighbors of a given vertex we could write a routine like this:</p> <div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>void printNeighborPositions(VertexRef v) {
  HalfEdgeRef h = v-&gt;halfedge();    // get one of the outgoing halfedges of the vertex
  do {
    HalfEdgeRef h_twin = h-&gt;twin();   // get the vertex of the current halfedge
    VertexRef vN = h_twin-&gt;vertex();  // vertex is 'source' of the half edge.
                                      // so h-&gt;vertex() is v,
                                      // whereas h_twin-&gt;vertex() is the neighbor vertex.
    cout &lt;&lt; vN-&gt;pos &lt;&lt; endl;          // print the vertex position
    h = h_twin-&gt;next();               // move to the next outgoing halfedge of the vertex.
  } while(h != v-&gt;halfedge());        // keep going until we're back at the beginning
}
</code></pre></div></div> <p>To iterate over <strong>all</strong> the vertices in a halfedge mesh, we could write a loop like this:</p> <div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>for(VertexRef v = mesh.vertices_begin(); v != mesh.vertices_end(); v++) {
  printNeighborPositions(v); // do something interesting here
}
</code></pre></div></div> <p>Internally, the lists of vertices, edges, faces, and halfedges are stored as <strong>linked lists</strong>, which allows us to easily add or delete elements to our mesh. For instance, to add a new vertex we can write</p> <div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>VertexRef v = mesh.new_vertex();
</code></pre></div></div> <p>Likewise, to delete a vertex we can write</p> <div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>mesh.erase(v);
</code></pre></div></div> <p>Note, however, that one should be <strong>very, very careful</strong> when adding or deleting mesh elements. New mesh elements must be properly linked to the mesh – for instance, this new vertex must be pointed to one of its associated halfedges by writing something like</p> <div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>v-&gt;halfedge() = h;
</code></pre></div></div> <p>Likewise, if we delete a mesh element, we must be certain that no existing elements still point to it; the halfedge data structure does not take care of these relationships for you automatically. In fact, that is exactly the point of this assignment: to get some practice directly manipulating the halfedge data structure. Being able to perform these low-level manipulations will enable you to write useful and interesting mesh code far beyond the basic operations in this assignment. The <code class="language-plaintext highlighter-rouge">Halfedge_Mesh</code> class provides a helper function called <code class="language-plaintext highlighter-rouge">validate</code> that checks whether the mesh iterators are valid. You might find it worthwhile calling this function to debug your implementation (please note that <code class="language-plaintext highlighter-rouge">validate</code> only checks that your mesh is valid - passing it does not imply that your specific operation is correct).</p> <p>Finally, the <strong>boundary</strong> of the surface (e.g., the ankles and waist of a pair of pants) requires special care in our halfedge implementation. At first glance, it would seem that the routine <code class="language-plaintext highlighter-rouge">printNeighborPositions()</code> above might break if the vertex <code class="language-plaintext highlighter-rouge">v</code> is on the boundary, because at some point we worry that we have no <code class="language-plaintext highlighter-rouge">twin()</code> element to visit. Fortunately, our implementation has been designed to avoid this kind of catastrophe. In particular, rather than having an actual hole in the mesh, we create a “virtual” boundary face whose edges are all the edges of the boundary loop. This way, we can iterate over boundary elements just like any other mesh element. If we ever need to check whether an element is on the boundary, we have the methods.</p> <div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>Vertex::on_boundary()
Edge::on_boundary()
Face::is_boundary()
Halfedge::is_boundary()
</code></pre></div></div> <p>These methods return true if and only if the element is contained in the domain boundary. Additionally, we store an explicit list of boundary faces, which we can iterate over like any other type of mesh element:</p> <div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>for(FaceRef b = mesh.boundaries_begin(); b != mesh.boundaries_end(); b++) {
  // do something interesting with this boundary loop
}
</code></pre></div></div> <p>These virtual faces are not stored in the usual face list, i.e., they will not show up when iterating over faces. The figure below should help to further explain the behavior of <code class="language-plaintext highlighter-rouge">Halfedge_Mesh</code> for surfaces with boundary:</p> <center><img src="boundary_conventions.png" style="height:360px" /></center> <p>Dark blue regions indicate interior faces, whereas light blue regions indicate virtual boundary faces. Note that for vertices and edges, <code class="language-plaintext highlighter-rouge">on_boundary()</code> will return true if the element is attached to a boundary face, but <code class="language-plaintext highlighter-rouge">is_boundary()</code> for halfedges is only true if the halfedge is ‘inside’ the boundary face. For example, in the figure above the region <code class="language-plaintext highlighter-rouge">b</code> is a virtual boundary face, which means that vertex <code class="language-plaintext highlighter-rouge">v'</code>, edge <code class="language-plaintext highlighter-rouge">e'</code>, and halfedge <code class="language-plaintext highlighter-rouge">h'</code> are all part of the boundary; their methods will return true. In contrast, vertex <code class="language-plaintext highlighter-rouge">v</code>, edge <code class="language-plaintext highlighter-rouge">e</code>, face <code class="language-plaintext highlighter-rouge">f</code>, and halfedge <code class="language-plaintext highlighter-rouge">h</code> are not part of the boundary, and their methods will return false. Notice also that the boundary face b is a polygon with 12 edges.</p> <p><em>Note:</em> <em>the edge degree and face degree of a boundary vertex is not the same!</em> Notice, for instance, that vertex <code class="language-plaintext highlighter-rouge">v'</code> is contained in three edges but only two interior faces. By convention, <code class="language-plaintext highlighter-rouge">Vertex::degree()</code> returns the face degree, not the edge degree. The edge degree can be computed by finding the face degree, and adding 1 if the vertex is a boundary vertex.</p> <p>Please refer to the inline comments (e.g. of <code class="language-plaintext highlighter-rouge">geometry/halfedge.h</code>) for further details about the <code class="language-plaintext highlighter-rouge">Halfedge_Mesh</code> data structure.</p> </div> </div> <div class="search-overlay"></div> </div> </body> </html>