Skip to content

GitLab

Switch branch/tag
Find file Normal viewHistoryPermalink
index.html 19.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 
<!DOCTYPE html> <html lang="en-US"> <head> <meta charset="UTF-8"> <meta http-equiv="X-UA-Compatible" content="IE=Edge"> <title>Loop Subdivision - </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>Loop Subdivision</title> <meta name="generator" content="Jekyll v4.2.0" /> <meta property="og:title" content="Loop Subdivision" /> <meta property="og:locale" content="en_US" /> <meta name="twitter:card" content="summary" /> <meta property="twitter:title" content="Loop Subdivision" /> <script type="application/ld+json"> {"headline":"Loop Subdivision","@type":"WebPage","url":"/meshedit/global/loop/","@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 "><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 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/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 active"> <a href="/meshedit/global/loop/" class="nav-list-link active">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/global/">Global Operations</a></li> <li class="breadcrumb-nav-list-item"><span>Loop Subdivision</span></li> </ol> </nav> <div id="main-content" class="main-content" role="main"> <h1 id="loop-subdivision"> <a href="#loop-subdivision" class="anchor-heading" aria-labelledby="loop-subdivision"><svg viewBox="0 0 16 16" aria-hidden="true"><use xlink:href="#svg-link"></use></svg></a> Loop Subdivision </h1> <p>For an in-practice example, see the <a href="/Scotty3D/guide/model">User Guide</a>.</p> <p>Loop subdivision (named after <a href="http://charlesloop.com/">Charles Loop</a>) is a standard approximating subdivision scheme for triangle meshes. At a high level, it consists of two basic steps:</p> <ol> <li>Split each triangle into four by connecting edge midpoints (sometimes called “4-1 subdivision”).</li> <li>Update vertex positions as a particular weighted average of neighboring positions.</li> </ol> <p>The 4-1 subdivision looks like this:</p> <p><img src="loop_41.png" alt="4-1 Subdivision" /></p> <p>And the following picture illustrates the weighted average:</p> <p><img src="loop_weights.png" alt="Loop subdivision weights" /></p> <p>In words, the new position of an old vertex is (1 - nu) times the old position + u times the sum of the positions of all of its neighbors. The new position for a newly created vertex v that splits Edge AB and is flanked by opposite vertices C and D across the two faces connected to AB in the original mesh will be 3/8 * (A + B) + 1/8 * (C + D). If we repeatedly apply these two steps, we will converge to a fairly smooth approximation of our original mesh.</p> <p>We will implement Loop subdivision as the <code class="language-plaintext highlighter-rouge">Halfedge_Mesh::loop_subdivide()</code> method. In contrast to linear and Catmull-Clark subdivision, Loop subdivision <strong>must</strong> be implemented using the local mesh operations described above (simply because it provides an alternative perspective on subdivision implementation, which can be useful in different scenarios). In particular, 4-1 subdivision can be achieved by applying the following strategy:</p> <ol> <li>Split every edge of the mesh <em>in any order whatsoever</em>.</li> <li>Flip any new edge that touches a new vertex and an old vertex.</li> </ol> <p>The following pictures (courtesy Denis Zorin) illustrate this idea:</p> <p><img src="loop_flipping.png" alt="Subdivision via flipping" /></p> <p>Notice that only blue (and not black) edges are flipped in this procedure; as described above, edges in the split mesh should be flipped if and only if they touch both an original vertex <em>and</em> a new vertex (i.e., a midpoint of an original edge).</p> <p>When working with dynamic mesh data structures (like a halfedge mesh), one must think <strong>very carefully</strong> about the order in which mesh elements are processed—it is quite easy to delete an element at one point in the code, then try to access it later (typically resulting in a crash!). For instance, suppose we write a loop like this:</p> <div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>// iterate over all edges in the mesh
for (EdgeRef e = mesh.edges_begin(); e != mesh.edges_end(); e++) {
  if (some condition is met) {
    mesh.split_edge(e);
  }
}
</code></pre></div></div> <p>Although this routine looks straightforward, it can very easily crash! The reason is fairly subtle: we are iterating over edges in the mesh by incrementing the iterator <code class="language-plaintext highlighter-rouge">e</code> (via the expression <code class="language-plaintext highlighter-rouge">e++</code>). But since <code class="language-plaintext highlighter-rouge">split_edge()</code> is allowed to create and delete mesh elements, it might deallocate the edge pointed to by <code class="language-plaintext highlighter-rouge">e</code> before we increment it! To be safe, one should instead write a loop like this:</p> <div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>// iterate over all edges in the mesh
int n = mesh.n_edges();
EdgeRef e = mesh.edges_begin();
for (int i = 0; i &lt; n; i++) {

  // get the next edge NOW!
  EdgeRef nextEdge = e;
  nextEdge++;

  // now, even if splitting the edge deletes it...
  if (some condition is met) {
    mesh.split_edge(e);
  }

  // ...we still have a valid reference to the next edge.
  e = nextEdge;
}
</code></pre></div></div> <p>Note that this loop is just a representative example, the implementer must consider which elements might be affected by a local mesh operation when writing such loops. We recommend ensuring that your atomic edge operations provide certain guarantees. For instance, if the implementation of <code class="language-plaintext highlighter-rouge">Halfedge_Mesh::flip_edge()</code> guarantees that no edges will be created or destroyed (as it should), then you can safely do edge flips inside a loop without worrying about these kinds of side effects.</p> <p>For Loop subdivision, there are some additional data members that will make it easy to keep track of the data needed to update the connectivity and vertex positions. In particular:</p> <ul> <li><code class="language-plaintext highlighter-rouge">Vertex::new_pos</code> can be used as temporary storage for the new position (computed via the weighted average above). Note that one should <em>not</em> change the value of <code class="language-plaintext highlighter-rouge">Vertex::pos</code> until <em>all</em> the new vertex positions have been computed – otherwise, subsequent computation will take averages of values that have already been averaged!</li> <li>Likewise, <code class="language-plaintext highlighter-rouge">Edge::new_pos</code> can be used to store the position of the vertices that will ultimately be inserted at edge midpoints. Again, these values should be computed from the original values (before subdivision), and applied to the new vertices only at the very end. The <code class="language-plaintext highlighter-rouge">Edge::new_pos</code> value will be used for the position of the vertex that will appear along the old edge after the edge is split. We precompute the position of the new vertex before splitting the edges and allocating the new vertices because it is easier to traverse the simpler original mesh to find the positions for the weighted average that determines the positions of the new vertices.</li> <li><code class="language-plaintext highlighter-rouge">Vertex::is_new</code> can be used to flag whether a vertex was part of the original mesh, or is a vertex newly inserted by subdivision (at an edge midpoint).</li> <li><code class="language-plaintext highlighter-rouge">Edge::is_new</code> likewise flags whether an edge is a piece of an edge in the original mesh, or is an entirely new edge created during the subdivision step.</li> </ul> <p>Given this setup, we strongly suggest that it will be easiest to implement subdivision according to the following “recipe” (though the implementer is of course welcome to try doing things a different way!). The basic strategy is to <em>first</em> compute the new vertex positions (storing the results in the <code class="language-plaintext highlighter-rouge">new_pos</code> members of both vertices and edges), and only <em>then</em> update the connectivity. Doing it this way will be much easier, since traversal of the original (coarse) connectivity is much simpler than traversing the new (fine) connectivity. In more detail:</p> <ol> <li>Mark all vertices as belonging to the original mesh by setting <code class="language-plaintext highlighter-rouge">Vertex::is_new</code> to <code class="language-plaintext highlighter-rouge">false</code> for all vertices in the mesh.</li> <li>Compute updated positions for all vertices in the original mesh using the vertex subdivision rule, and store them in <code class="language-plaintext highlighter-rouge">Vertex::new_pos</code>.</li> <li>Compute new positions associated with the vertices that will be inserted at edge midpoints, and store them in <code class="language-plaintext highlighter-rouge">Edge::new_pos</code>.</li> <li>Split every edge in the mesh, being careful about how the loop is written. In particular, you should make sure to iterate only over edges of the original mesh. Otherwise, the loop will keep splitting edges that you just created!</li> <li>Flip any new edge that connects an old and new vertex.</li> <li>Finally, copy the new vertex positions (<code class="language-plaintext highlighter-rouge">Vertex::new_pos</code>) into the usual vertex positions (<code class="language-plaintext highlighter-rouge">Vertex::pos</code>).</li> </ol> <p>It may be useful to ensure <code class="language-plaintext highlighter-rouge">Halfedge_Mesh::split_edge()</code> will now return an iterator to the newly inserted vertex, and particularly that the halfedge of this vertex will point along the edge of the original mesh. This iterator is useful because it can be used to (i) flag the vertex returned by the split operation as a new vertex, and (ii) flag each outgoing edge as either being new or part of the original mesh. (In other words, Step 3 is a great time to set the members <code class="language-plaintext highlighter-rouge">is_new</code> for vertices and edges created by the split. It is also a good time to copy the <code class="language-plaintext highlighter-rouge">new_pos</code> field from the edge being split into the <code class="language-plaintext highlighter-rouge">new_pos</code> field of the newly inserted vertex.)</p> <p>We recommend implementing this algorithm in stages, e.g., <em>first</em> see if you can correctly update the connectivity, <em>then</em> worry about getting the vertex positions right. Some examples below illustrate the correct behavior of the algorithm.</p> <p>This subdivision rule <strong>is not</strong> required to support meshes with boundary, unless the implementer wishes to go above and beyond.</p> </div> </div> <div class="search-overlay"></div> </div> </body> </html>