Skip to content

GitLab

Switch branch/tag
Find file Normal viewHistoryPermalink
index.html 17.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 
<!DOCTYPE html> <html lang="en-US"> <head> <meta charset="UTF-8"> <meta http-equiv="X-UA-Compatible" content="IE=Edge"> <title>Linear 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>Linear Subdivision</title> <meta name="generator" content="Jekyll v4.2.0" /> <meta property="og:title" content="Linear Subdivision" /> <meta property="og:locale" content="en_US" /> <meta name="twitter:card" content="summary" /> <meta property="twitter:title" content="Linear Subdivision" /> <script type="application/ld+json"> {"headline":"Linear Subdivision","@type":"WebPage","url":"/meshedit/global/linear/","@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 active"> <a href="/meshedit/global/linear/" class="nav-list-link active">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/global/">Global Operations</a></li> <li class="breadcrumb-nav-list-item"><span>Linear Subdivision</span></li> </ol> </nav> <div id="main-content" class="main-content" role="main"> <h1 id="linear-subdivision"> <a href="#linear-subdivision" class="anchor-heading" aria-labelledby="linear-subdivision"><svg viewBox="0 0 16 16" aria-hidden="true"><use xlink:href="#svg-link"></use></svg></a> Linear Subdivision </h1> <p>For an in-practice example, see the <a href="/Scotty3D/guide/model">User Guide</a>.</p> <p>Unlike most other global remeshing operations, linear (and Catmull-Clark) subdivision will proceed by completely replacing the original halfedge mesh with a new one. The high-level procedure is:</p> <ol> <li>Generate a list of vertex positions for the new mesh.</li> <li>Generate a list of polygons for the new mesh, as a list of indices into the new vertex list (a la “polygon soup”).</li> <li>Using these two lists, rebuild the halfedge connectivity from scratch.</li> </ol> <p>Given these lists, <code class="language-plaintext highlighter-rouge">Halfedge_Mesh::from_poly</code> will take care of allocating halfedges, setting up <code class="language-plaintext highlighter-rouge">next</code> and <code class="language-plaintext highlighter-rouge">twin</code> pointers, etc., based on the list of polygons generated in step 2—this routine is already implemented in the Scotty3D skeleton code.</p> <p>Both linear and Catmull-Clark subdivision schemes will handle general <em>n</em>-gons (i.e., polygons with <em>n</em> sides) rather than, say, quads only or triangles only. Each <em>n</em>-gon (including but not limited to quadrilaterals) will be split into <em>n</em> quadrilaterals according to the following template:</p> <center><img src="subdivide_quad.png" style="height:220px" /></center> <p>The high-level procedure is outlined in greater detail in <code class="language-plaintext highlighter-rouge">student/meshedit.cpp</code>.</p> <h3 id="vertex-positions"> <a href="#vertex-positions" class="anchor-heading" aria-labelledby="vertex-positions"><svg viewBox="0 0 16 16" aria-hidden="true"><use xlink:href="#svg-link"></use></svg></a> Vertex Positions </h3> <p>For global linear or Catmull-Clark subdivision, the strategy for assigning new vertex positions may at first appear a bit strange: in addition to updating positions at vertices, we will also calculate vertex positions associated with the <em>edges</em> and <em>faces</em> of the original mesh. Storing new vertex positions on edges and faces will make it extremely convenient to generate the polygons in our new mesh, since we can still use the halfedge data structure to decide which four positions get connected up to form a quadrilateral. In particular, each quad in the new mesh will consist of:</p> <ul> <li>one new vertex associated with a face from the original mesh,</li> <li>two new vertices associated with edges from the original mesh, and</li> <li>one vertex from the original mesh.</li> </ul> <p>For linear subdivision, the rules for computing new vertex positions are very simple:</p> <ul> <li>New vertices at original faces are assigned the average coordinates of all corners of that face (i.e., the arithmetic mean).</li> <li>New vertices at original edges are assigned the average coordinates of the two edge endpoints.</li> <li>New vertices at original vertices are assigned the same coordinates as in the original mesh.</li> </ul> <p>These values should be assigned to the members <code class="language-plaintext highlighter-rouge">Face::new_pos</code>, <code class="language-plaintext highlighter-rouge">Edge::new_pos</code>, and <code class="language-plaintext highlighter-rouge">Vertex::new_pos</code>, respectively. For instance, <code class="language-plaintext highlighter-rouge">f-&gt;new_pos = Vec3( x, y, z );</code> will assign the coordinates (x,y,z) to the new vertex associated with face <code class="language-plaintext highlighter-rouge">f</code>. The general strategy for assigning these new positions is to iterate over all vertices, then all edges, then all faces, assigning appropriate values to <code class="language-plaintext highlighter-rouge">new_pos</code>. <strong>Note:</strong> you <em>must</em> copy the original vertex position <code class="language-plaintext highlighter-rouge">Vertex::pos</code> to the new vertex position <code class="language-plaintext highlighter-rouge">Vertex::new_pos</code>; these values will not be used automatically.</p> <p>This step should be implemented in the method <code class="language-plaintext highlighter-rouge">Halfedge_Mesh::linear_subdivide_positions</code> in <code class="language-plaintext highlighter-rouge">student/meshedit.cpp</code>.</p> <p>Steps 2 and 3 are already implemented by <code class="language-plaintext highlighter-rouge">Halfedge_Mesh::subdivide</code> in <code class="language-plaintext highlighter-rouge">geometry/halfedge.cpp</code>. For your understanding, an explanation of how these are implemented is provided below:</p> <h3 id="polygons"> <a href="#polygons" class="anchor-heading" aria-labelledby="polygons"><svg viewBox="0 0 16 16" aria-hidden="true"><use xlink:href="#svg-link"></use></svg></a> Polygons </h3> <p>Recall that in linear and Catmull-Clark subdivision <em>all polygons are subdivided simultaneously</em>. In other words, if we focus on the whole mesh (rather than a single polygon), then we are globally</p> <ul> <li>creating one new vertex for each edge,</li> <li>creating one new vertex for each face, and</li> <li>keeping all the vertices of the original mesh.</li> </ul> <p>These vertices are then connected up to form quadrilaterals (<em>n</em> quadrilaterals for each <em>n</em>-gon in the input mesh). Rather than directly modifying the halfedge connectivity, these new quads will be collected in a much simpler mesh data structure: a list of polygons. Note that with this subdivision scheme, <em>every</em> polygon in the output mesh will be a quadrilateral, even if the input contains triangles, pentagons, etc.</p> <p>In Scotty3D, a list of polygons can be declared as</p> <div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>std::vector&lt;std::vector&lt;Index&gt;&gt; quads;
</code></pre></div></div> <p>where <code class="language-plaintext highlighter-rouge">std::vector</code> is a <a href="http://en.cppreference.com/w/cpp/container/vector">class from the C++ standard template library</a>, representing a dynamically-sized array. An <code class="language-plaintext highlighter-rouge">Index</code> is just another name for a <code class="language-plaintext highlighter-rouge">size_t</code>, which is the standard C++ type for integers that specify an element of an array. Polygons can be created by allocating a list of appropriate size, then specifying the indices of each vertex in the polygon. For example:</p> <div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>std::vector&lt;Index&gt; quad( 4 ); // allocate an array with four elements
// Build a quad with vertices specified by integers (a,b,c,d), starting at zero.
// These indices should correspond to the indices computing when assigning vertex
// positions, as described above.
quad[0] = a;
quad[1] = b;
quad[2] = c;
quad[3] = d;
</code></pre></div></div> <p>Once a quad has been created, it can be added to the list of quads by using the method <code class="language-plaintext highlighter-rouge">vector::push_back</code>, which appends an item to a vector:</p> <div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>std::vector&lt;std::vector&lt;Index&gt;&gt; newPolygons;
newPolygons.push_back( quad );
</code></pre></div></div> <p>The full array of new polygons will then be passed to the method <code class="language-plaintext highlighter-rouge">Halfedge_Mesh::from_poly</code>, together with the new vertex positions.</p> </div> </div> <div class="search-overlay"></div> </div> </body> </html>