Skip to content

GitLab

Switch branch/tag
Find file Normal viewHistoryPermalink
edge_flip.html 18.7 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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59 
<!DOCTYPE html> <html lang="en-US"> <head> <meta charset="UTF-8"> <meta http-equiv="X-UA-Compatible" content="IE=Edge"> <title>Edge Flip Tutorial - </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>Edge Flip Tutorial</title> <meta name="generator" content="Jekyll v4.2.0" /> <meta property="og:title" content="Edge Flip Tutorial" /> <meta property="og:locale" content="en_US" /> <meta name="twitter:card" content="summary" /> <meta property="twitter:title" content="Edge Flip Tutorial" /> <script type="application/ld+json"> {"headline":"Edge Flip Tutorial","@type":"WebPage","url":"/meshedit/local/edge_flip","@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 "><a href="/meshedit/halfedge" class="nav-list-link">Halfedge Mesh</a></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/local/" class="nav-list-link">Local Operations</a><ul class="nav-list"><li class="nav-list-item active"> <a href="/meshedit/local/edge_flip" class="nav-list-link active">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"><a href="/meshedit/local/">Local Operations</a></li> <li class="breadcrumb-nav-list-item"><span>Edge Flip Tutorial</span></li> </ol> </nav> <div id="main-content" class="main-content" role="main"> <h1 id="edge-flip-tutorial"> <a href="#edge-flip-tutorial" class="anchor-heading" aria-labelledby="edge-flip-tutorial"><svg viewBox="0 0 16 16" aria-hidden="true"><use xlink:href="#svg-link"></use></svg></a> Edge Flip Tutorial </h1> <p>Here we provide a step-by-step guide to implementing a simplified version of the <em>EdgeFlip</em> operation for a pair of triangles—the final version, however, must be implemented for general polygons (i.e., any <em>n</em>-gon). The basic strategy for implementing the other local operations is quite similar to the procedure outlined below.</p> <p><strong>Note:</strong> if you’re not familiar with C++, you should definitely take a moment to learn about the <a href="http://en.cppreference.com/w/cpp/container/vector">standard library class</a> <code class="language-plaintext highlighter-rouge">std::vector</code>, especially the method <code class="language-plaintext highlighter-rouge">push_back()</code>, which will make it easy to accumulate a list of pointers as you walk around a polygon, vertex, etc.</p> <p>We now consider the case of a triangle-triangle edge flip.</p> <h3 id="phase-0-draw-a-diagram"> <a href="#phase-0-draw-a-diagram" class="anchor-heading" aria-labelledby="phase-0-draw-a-diagram"><svg viewBox="0 0 16 16" aria-hidden="true"><use xlink:href="#svg-link"></use></svg></a> PHASE 0: Draw a Diagram </h3> <p>Suppose we have a pair of triangles (a,b,c) and (c,b,d). After flipping the edge (b,c), we should now have triangles (a,d,c) and (a,b,d). A good first step for implementing any local mesh operation is to draw a diagram that clearly labels all elements affected by the operation:</p> <center><img src="edge_flip_diagram.png" /></center> <p>Here we have drawn a diagram of the region around the edge both before and after the edge operation (in this case, “flip”), labeling each type of element (halfedge, vertex, edge, and face) from zero to the number of elements. It is important to include every element affected by the operation, thinking very carefully about which elements will be affected. If elements are omitted during this phase, everything will break—even if the code written in the two phases is correct! In this example, for instance, we need to remember to include the halfedges “outside” the neighborhood, since their “twin” pointers will be affected.</p> <h3 id="phase-i-collect-elements"> <a href="#phase-i-collect-elements" class="anchor-heading" aria-labelledby="phase-i-collect-elements"><svg viewBox="0 0 16 16" aria-hidden="true"><use xlink:href="#svg-link"></use></svg></a> PHASE I: Collect elements </h3> <p>Once you’ve drawn your diagram, simply collect all the elements from the “before” picture. Give them the same names as in your diagram, so that you can debug your code by comparing with the picture.</p> <div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>// HALFEDGES
HalfedgeRef h0 = e0-&gt;halfedge();
HalfedgeRef h1 = h0-&gt;next();
HalfedgeRef h2 = h1-&gt;next();
HalfedgeRef h3 = h0-&gt;twin();
HalfedgeRef h4 = h3-&gt;next();
HalfedgeRef h5 = h4-&gt;next();
HalfedgeRef h6 = h1-&gt;twin();
HalfedgeRef h7 = h2-&gt;twin();
HalfedgeRef h8 = h4-&gt;twin();
HalfedgeRef h9 = h5-&gt;twin();

// VERTICES
VertexRef v0 = h0-&gt;vertex();
VertexRef v1 = h3-&gt;vertex();
// ...you fill in the rest!...

// EDGES
EdgeRef e1 = h5-&gt;edge();
EdgeRef e2 = h4-&gt;edge();
// ...you fill in the rest!...

// FACES
FaceRef f0 = h0-&gt;face();
// ...you fill in the rest!...
</code></pre></div></div> <h3 id="phase-ii-allocate-new-elements"> <a href="#phase-ii-allocate-new-elements" class="anchor-heading" aria-labelledby="phase-ii-allocate-new-elements"><svg viewBox="0 0 16 16" aria-hidden="true"><use xlink:href="#svg-link"></use></svg></a> PHASE II: Allocate new elements </h3> <p>If your edge operation requires new elements, now is the time to allocate them. For the edge flip, we don’t need any new elements; but suppose that for some reason we needed a new vertex v4. At this point we would allocate the new vertex via</p> <div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>VertexRef v4 = mesh.new_vertex();
</code></pre></div></div> <p>(The name used for this new vertex should correspond to the label you give it in your “after” picture.) Likewise, new edges, halfedges, and faces can be allocated via the methods <code class="language-plaintext highlighter-rouge">mesh.new_edge()</code>, <code class="language-plaintext highlighter-rouge">mesh.new_halfedge()</code>, and <code class="language-plaintext highlighter-rouge">mesh.new_face()</code>.</p> <h3 id="phase-iii-reassign-elements"> <a href="#phase-iii-reassign-elements" class="anchor-heading" aria-labelledby="phase-iii-reassign-elements"><svg viewBox="0 0 16 16" aria-hidden="true"><use xlink:href="#svg-link"></use></svg></a> PHASE III: Reassign Elements </h3> <p>Next, update the pointers for all the mesh elements that are affected by the edge operation. Be exhaustive! In other words, go ahead and specify every pointer for every element, even if it did not change. Once things are working correctly, you can always optimize by removing unnecessary assignments. But get it working correctly first! Correctness is more important than efficiency.</p> <div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>// HALFEDGES
h0-&gt;next() = h1;
h0-&gt;twin() = h3;
h0-&gt;vertex() = v2;
h0-&gt;edge() = e0;
h0-&gt;face() = f0;
h1-&gt;next() = h2;
h1-&gt;twin() = h7;
h1-&gt;vertex() = v3;
h1-&gt;edge() = e3;
h1-&gt;face() = f0;
// ...you fill in the rest!...

// ...and don't forget about the "outside" elements!...
h9-&gt;next() = h9-&gt;next(); // didn't change, but set it anyway!
h9-&gt;twin() = h4;
h9-&gt;vertex() = v1;
h9-&gt;edge() = e1;
h9-&gt;face() = h9-&gt;face(); // didn't change, but set it anyway!

// VERTICES
v0-&gt;halfedge() = h2;
v1-&gt;halfedge() = h5;
v2-&gt;halfedge() = h4;
v3-&gt;halfedge() = h3;

// EDGES
e0-&gt;halfedge() = h0; //...you fill in the rest!...

// FACES
f0-&gt;halfedge() = h0; //...you fill in the rest!...
</code></pre></div></div> <h3 id="phase-iv-delete-unused-elements"> <a href="#phase-iv-delete-unused-elements" class="anchor-heading" aria-labelledby="phase-iv-delete-unused-elements"><svg viewBox="0 0 16 16" aria-hidden="true"><use xlink:href="#svg-link"></use></svg></a> PHASE IV: Delete unused elements </h3> <p>If your edge operation eliminates elements, now is the best time to deallocate them: at this point, you can be sure that they are no longer needed. For instance, since we do not need the vertex allocated in PHASE II, we could write</p> <div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>mesh.erase(v4);
</code></pre></div></div> <p>You should be careful that this mesh element is not referenced by any other element in the mesh. But if your “before” and “after” diagrams are correct, that should not be an issue!</p> <h3 id="design-considerations"> <a href="#design-considerations" class="anchor-heading" aria-labelledby="design-considerations"><svg viewBox="0 0 16 16" aria-hidden="true"><use xlink:href="#svg-link"></use></svg></a> Design considerations </h3> <p>The basic algorithm outlined above will handle most edge flips, but you should also think carefully about possible corner-cases. You should also think about other design issues, like “how much should this operation cost?” For instance, for this simple triangle-triangle edge flip it might be reasonable to:</p> <ul> <li>Ignore requests to flip boundary edges (i.e., just return immediately if either neighboring face is a boundary loop).</li> <li>Ignore requests to perform any edge flip that would make the surface non-manifold or otherwise invalidate the mesh.</li> <li>Not add or delete any elements. Since there are the same number of mesh elements before and after the flip, you should only need to reassign pointers.</li> <li>Perform only a constant amount of work – the cost of flipping a single edge should <strong>not</strong> be proportional to the size of the mesh!</li> </ul> <p>Formally proving that your code is correct in all cases is challenging, but at least try to think about what could go wrong in degenerate cases (e.g., vertices of low degree, or very small meshes like a tetrahedron). The biggest challenge in properly implementing this type of local operation is making sure that all the pointers still point to the right place in the modified mesh, and will likely be the cause of most of your crashes! To help mitigate this, Scotty3D will automatically attempt to <code class="language-plaintext highlighter-rouge">validate</code> your mesh after each operation, and will warn you if it detects abnormalities. Note that it will still crash if you leave references to deleted mesh elements!</p> </div> </div> <div class="search-overlay"></div> </div> </body> </html>