<!DOCTYPE html><htmllang="en-US"><head><metacharset="UTF-8"><metahttp-equiv="X-UA-Compatible"content="IE=Edge"><title>Isotropic Remeshing - </title><linkrel="shortcut icon"href="/favicon.ico"type="image/x-icon"><linkrel="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><metaname="viewport"content="width=device-width, initial-scale=1"><!-- Begin Jekyll SEO tag v2.7.1 --><title>Isotropic Remeshing</title><metaname="generator"content="Jekyll v4.2.0"/><metaproperty="og:title"content="Isotropic Remeshing"/><metaproperty="og:locale"content="en_US"/><metaname="twitter:card"content="summary"/><metaproperty="twitter:title"content="Isotropic Remeshing"/><script type="application/ld+json">{"headline":"Isotropic Remeshing","@type":"WebPage","url":"/meshedit/global/remesh/","@context":"https://schema.org"}</script><!-- End Jekyll SEO tag --></head><body><svgxmlns="http://www.w3.org/2000/svg"style="display: none;"><symbolid="svg-link"viewBox="0 0 24 24"><title>Link</title><svgxmlns="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"><pathd="M10 13a5 5 0 0 0 7.54.54l3-3a5 5 0 0 0-7.07-7.07l-1.72 1.71"></path><pathd="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><symbolid="svg-search"viewBox="0 0 24 24"><title>Search</title><svgxmlns="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"><circlecx="11"cy="11"r="8"></circle><linex1="21"y1="21"x2="16.65"y2="16.65"></line></svg></symbol><symbolid="svg-menu"viewBox="0 0 24 24"><title>Menu</title><svgxmlns="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"><linex1="3"y1="12"x2="21"y2="12"></line><linex1="3"y1="6"x2="21"y2="6"></line><linex1="3"y1="18"x2="21"y2="18"></line></svg></symbol><symbolid="svg-arrow-right"viewBox="0 0 24 24"><title>Expand</title><svgxmlns="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"><polylinepoints="9 18 15 12 9 6"></polyline></svg></symbol><symbolid="svg-doc"viewBox="0 0 24 24"><title>Document</title><svgxmlns="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"><pathd="M13 2H6a2 2 0 0 0-2 2v16a2 2 0 0 0 2 2h12a2 2 0 0 0 2-2V9z"></path><polylinepoints="13 2 13 9 20 9"></polyline></svg></symbol></svg><divclass="side-bar"><divclass="site-header"><ahref="/"class="site-title lh-tight"></a><ahref="#"id="menu-button"class="site-button"><svgviewBox="0 0 24 24"class="icon"><usexlink:href="#svg-menu"></use></svg></a></div><navrole="navigation"aria-label="Main"id="site-nav"class="site-nav"><ulclass="nav-list"><liclass="nav-list-item"><ahref="/"class="nav-list-link">Home</a></li><liclass="nav-list-item"><ahref="/git/"class="nav-list-link">GitHub Setup</a></li><liclass="nav-list-item"><ahref="/build/"class="nav-list-link">Building Scotty3D</a></li><liclass="nav-list-item"><ahref="#"class="nav-list-expander"><svgviewBox="0 0 24 24"><usexlink:href="#svg-arrow-right"></use></svg></a><ahref="/guide/"class="nav-list-link">User Guide</a><ulclass="nav-list "><liclass="nav-list-item "><ahref="/guide/animate_mode/"class="nav-list-link">Animate</a></li><liclass="nav-list-item "><ahref="/guide/layout_mode/"class="nav-list-link">Layout</a></li><liclass="nav-list-item "><ahref="/guide/model_mode/"class="nav-list-link">Model</a></li><liclass="nav-list-item "><ahref="/guide/render_mode/"class="nav-list-link">Render</a></li><liclass="nav-list-item "><ahref="/guide/rigging_mode/"class="nav-list-link">Rig</a></li><liclass="nav-list-item "><ahref="/guide/simulate_mode/"class="nav-list-link">Simulate</a></li></ul></li><liclass="nav-list-item active"><ahref="#"class="nav-list-expander"><svgviewBox="0 0 24 24"><usexlink:href="#svg-arrow-right"></use></svg></a><ahref="/meshedit/"class="nav-list-link">A2: MeshEdit</a><ulclass="nav-list "><liclass="nav-list-item "><ahref="/meshedit/halfedge"class="nav-list-link">Halfedge Mesh</a></li><liclass="nav-list-item "><ahref="#"class="nav-list-expander"><svgviewBox="0 0 24 24"><usexlink:href="#svg-arrow-right"></use></svg></a><ahref="/meshedit/local/"class="nav-list-link">Local Operations</a><ulclass="nav-list"><liclass="nav-list-item "><ahref="/meshedit/local/edge_flip"class="nav-list-link">Edge Flip Tutorial</a></li><liclass="nav-list-item "><ahref="/meshedit/local/bevel/"class="nav-list-link">Bevelling</a></li></ul></li><liclass="nav-list-item active"><ahref="#"class="nav-list-expander"><svgviewBox="0 0 24 24"><usexlink:href="#svg-arrow-right"></use></svg></a><ahref="/meshedit/global/"class="nav-list-link">Global Operations</a><ulclass="nav-list"><liclass="nav-list-item "><ahref="/meshedit/global/catmull/"class="nav-list-link">Catmull-Clark Subdivision</a></li><liclass="nav-list-item active"><ahref="/meshedit/global/remesh/"class="nav-list-link active">Isotropic Remeshing</a></li><liclass="nav-list-item "><ahref="/meshedit/global/linear/"class="nav-list-link">Linear Subdivision</a></li><liclass="nav-list-item "><ahref="/meshedit/global/loop/"class="nav-list-link">Loop Subdivision</a></li><liclass="nav-list-item "><ahref="/meshedit/global/simplify/"class="nav-list-link">Simplification</a></li><liclass="nav-list-item "><ahref="/meshedit/global/triangulate/"class="nav-list-link">Triangulation</a></li></ul></li></ul></li><liclass="nav-list-item"><ahref="#"class="nav-list-expander"><svgviewBox="0 0 24 24"><usexlink:href="#svg-arrow-right"></use></svg></a><ahref="/pathtracer/"class="nav-list-link">A3: Pathtracer</a><ulclass="nav-list "><liclass="nav-list-item "><ahref="/pathtracer/camera_rays"class="nav-list-link">(Task 1) Camera Rays</a></li><liclass="nav-list-item "><ahref="#"class="nav-list-expander"><svgviewBox="0 0 24 24"><usexlink:href="#svg-arrow-right"></use></svg></a><ahref="/pathtracer/intersecting_objects"class="nav-list-link">(Task 2) Intersections</a><ulclass="nav-list"><liclass="nav-list-item "><ahref="/pathtracer/ray_triangle_intersection"class="nav-list-link">Ray Triangle Intersection</a></li><liclass="nav-list-item "><ahref="/pathtracer/ray_sphere_intersection"class="nav-list-link">Ray Sphere Intersection</a></li></ul></li><liclass="nav-list-item "><ahref="/pathtracer/bounding_volume_hierarchy"class="nav-list-link">(Task 3) BVH</a></li><liclass="nav-list-item "><ahref="/pathtracer/shadow_rays"class="nav-list-link">(Task 4) Shadow Rays</a></li><liclass="nav-list-item "><ahref="/pathtracer/path_tracing"class="nav-list-link">(Task 5) Path Tracing</a></li><liclass="nav-list-item "><ahref="#"class="nav-list-expander"><svgviewBox="0 0 24 24"><usexlink:href="#svg-arrow-right"></use></svg></a><ahref="/pathtracer/materials"class="nav-list-link">(Task 6) Materials</a><ulclass="nav-list"><liclass="nav-list-item "><ahref="/pathtracer/dielectrics_and_transmission"class="nav-list-link">Dielectrics and Transmission</a></li></ul></li><liclass="nav-list-item "><ahref="#"class="nav-list-expander"><svgviewBox="0 0 24 24"><usexlink:href="#svg-arrow-right"></use></svg></a><ahref="/pathtracer/environment_lighting"class="nav-list-link">(Task 7) Environment Lighting</a><ulclass="nav-list"><liclass="nav-list-item "><ahref="/pathtracer/importance_sampling"class="nav-list-link">Environment Light Importance Sampling</a></li></ul></li><liclass="nav-list-item "><ahref="/pathtracer/visualization_of_normals"class="nav-list-link">Visualization of normals</a></li></ul></li><liclass="nav-list-item"><ahref="#"class="nav-list-expander"><svgviewBox="0 0 24 24"><usexlink:href="#svg-arrow-right"></use></svg></a><ahref="/animation/"class="nav-list-link">A4: Animation</a><ulclass="nav-list "><liclass="nav-list-item "><ahref="/animation/splines"class="nav-list-link">Splines</a></li><liclass="nav-list-item "><ahref="/animation/skeleton_kinematics"class="nav-list-link">Skeleton Kinematics</a></li><liclass="nav-list-item "><ahref="/animation/skinning"class="nav-list-link">Skinning</a></li><liclass="nav-list-item "><ahref="/animation/particles"class="nav-list-link">Particles</a></li></ul></li></ul></nav><footerclass="site-footer"> This site uses <ahref="https://github.com/pmarsceill/just-the-docs">Just the Docs</a>, a documentation theme for Jekyll. </footer></div><divclass="main"id="top"><divid="main-header"class="main-header"><divclass="search"><divclass="search-input-wrap"><inputtype="text"id="search-input"class="search-input"tabindex="0"placeholder="Search "aria-label="Search "autocomplete="off"><labelfor="search-input"class="search-label"><svgviewBox="0 0 24 24"class="search-icon"><usexlink:href="#svg-search"></use></svg></label></div><divid="search-results"class="search-results"></div></div></div><divid="main-content-wrap"class="main-content-wrap"><navaria-label="Breadcrumb"class="breadcrumb-nav"><olclass="breadcrumb-nav-list"><liclass="breadcrumb-nav-list-item"><ahref="/meshedit/">A2: MeshEdit</a></li><liclass="breadcrumb-nav-list-item"><ahref="/meshedit/global/">Global Operations</a></li><liclass="breadcrumb-nav-list-item"><span>Isotropic Remeshing</span></li></ol></nav><divid="main-content"class="main-content"role="main"><h1id="isotropic-remeshing"><ahref="#isotropic-remeshing"class="anchor-heading"aria-labelledby="isotropic-remeshing"><svgviewBox="0 0 16 16"aria-hidden="true"><usexlink:href="#svg-link"></use></svg></a> Isotropic Remeshing </h1><p>For an in-practice example, see the <ahref="/Scotty3D/guide/model">User Guide</a>.</p><p>Scotty3D also supports remeshing, an operation that keeps the number of samples roughly the same while improving the shape of individual triangles. The isotropic remeshing algorithm tries to make the mesh as “uniform” as possible, i.e., triangles as close as possible to equilateral triangles of equal size, and vertex degrees as close as possible to 6 (note: this algorithm is for <strong>triangle meshes only</strong>). The algorithm to be implemented is based on the paper <ahref="http://graphics.uni-bielefeld.de/publications/disclaimer.php?dlurl=sgp04.pdf">Botsch and Kobbelt, “A Remeshing Approach to Multiresolution Modeling”</a> (Section 4), and can be summarized in just a few simple steps:</p><ol><li>If an edge is too long, split it.</li><li>If an edge is too short, collapse it.</li><li>If flipping an edge improves the degree of neighboring vertices, flip it.</li><li>Move vertices toward the average of their neighbors.</li></ol><p>Repeating this simple process several times typically produces a mesh with fairly uniform triangle areas, angles, and vertex degrees. However, each of the steps deserves slightly more explanation.</p><h3id="edge-splitting--collapsing"><ahref="#edge-splitting--collapsing"class="anchor-heading"aria-labelledby="edge-splitting--collapsing"><svgviewBox="0 0 16 16"aria-hidden="true"><usexlink:href="#svg-link"></use></svg></a> Edge Splitting / Collapsing </h3><p>Ultimately we want all of our triangles to be about the same size, which means we want edges to all have roughly the same length. As suggested in the paper by Botsch and Kobbelt, we will aim to keep our edges no longer than 4/3rds of the <strong>mean</strong> edge length <em>L</em> in the input mesh, and no shorter than 4/5ths of <em>L</em>. In other words, if an edge is longer than 4L/3, split it; if it is shorter than 4L/5, collapse it. We recommend performing all of the splits first, then doing all of the collapses (though as usual, you should be careful to think about when and how mesh elements are being allocated/deallocated).</p><h3id="edge-flipping"><ahref="#edge-flipping"class="anchor-heading"aria-labelledby="edge-flipping"><svgviewBox="0 0 16 16"aria-hidden="true"><usexlink:href="#svg-link"></use></svg></a> Edge Flipping </h3><p>We want to flip an edge any time it reduces the total deviation from regular degree (degree 6). In particular, let <em>a1</em>, <em>a2</em> be the degrees of an edge that we’re thinking about flipping, and let <em>b1</em>, <em>b2</em> be the degrees of the two vertices across from this edge. The total deviation in the initial configuration is <codeclass="language-plaintext highlighter-rouge">|a1-6| + |a2-6| + |b1-6| + |b2-6|</code>. You should be able to easily compute the deviation after the edge flip <strong>without actually performing the edge flip</strong>; if this number decreases, then the edge flip should be performed. We recommend flipping all edges in a single pass, after the edge collapse step.</p><h3id="vertex-averaging"><ahref="#vertex-averaging"class="anchor-heading"aria-labelledby="vertex-averaging"><svgviewBox="0 0 16 16"aria-hidden="true"><usexlink:href="#svg-link"></use></svg></a> Vertex Averaging </h3><p>Finally, we also want to optimize the geometry of the vertices. A very simple heuristic is that a mesh will have reasonably well-shaped elements if each vertex is located at the center of its neighbors. To keep your code clean and simple, we recommend using the method <codeclass="language-plaintext highlighter-rouge">Vertex::neighborhood_center()</code>, which computes the average position of the vertex’s neighbors. Note that you should not use this to immediately replace the current position: we don’t want to be taking averages of vertices that have already been averaged. Doing so can yield some bizarre behavior that depends on the order in which vertices are traversed (if you’re interested in learning more about this issue, Google around for the terms “Jacobi iterations” and “Gauss-Seidel). So, the code should (i) first compute the new positions (stored in <codeclass="language-plaintext highlighter-rouge">Vertex::new_pos</code>) for all vertices using their neighborhood centroids, and (ii) <em>then</em> update the vertices with new positions (copy <codeclass="language-plaintext highlighter-rouge">new_pos</code> to <codeclass="language-plaintext highlighter-rouge">pos</code>).</p><center><imgsrc="laplacian_smoothing.png"style="height:200px"/></center><p>How exactly should the positions be updated? One idea is to simply replace each vertex position with its centroid. We can make the algorithm slightly more stable by moving <em>gently</em> toward the centroid, rather than immediately snapping the vertex to the center. For instance, if <em>p</em> is the original vertex position and <em>c</em> is the centroid, we might compute the new vertex position as <em>q</em> = <em>p</em> + <em>w</em>(<em>c</em> - <em>p</em>) where <em>w</em> is some weighting factor between 0 and 1 (we use 1/5 in the examples below). In other words, we start out at <em>p</em> and move a little bit in the update direction <em>v</em> = <em>c</em> - <em>p</em>.</p><p>Another important issue arises if the update direction <em>v</em> has a large <em>normal</em> component, then we’ll end up pushing the surface in or out, rather than just sliding our sample points around on the surface. As a result, the shape of the surface will change much more than we’d like (try it!). To ameliorate this issue, we will move the vertex only in the <em>tangent</em> direction, which we can do by projecting out the normal component, i.e., by replacing <em>v</em> with <em>v</em> - dot(<em>N</em>,<em>v</em>)<em>N</em>, where <em>N</em> is the unit normal at the vertex. To get this normal, you will implement the method <codeclass="language-plaintext highlighter-rouge">Vertex::normal()</code>, which computes the vertex normal as the area-weighted average of the incident triangle normals. In other words, at a vertex i the normal points in the direction</p><center><imgsrc="vert_normal_eq.png"style="height:80px"/></center><p>where A_ijk is the area of triangle ijk, and N_ijk is its unit normal; this quantity can be computed directly by just taking the cross product of two of the triangle’s edge vectors (properly oriented).</p><h3id="implementation"><ahref="#implementation"class="anchor-heading"aria-labelledby="implementation"><svgviewBox="0 0 16 16"aria-hidden="true"><usexlink:href="#svg-link"></use></svg></a> Implementation </h3><p>The final implementation requires very little information beyond the description above; the basic recipe is:</p><ol><li>Compute the mean edge length <em>L</em> of the input.</li><li>Split all edges that are longer than 4L/3.</li><li>Collapse all edges that are shorter than 4L/5.</li><li>Flip all edges that decrease the total deviation from degree 6.</li><li>Compute the centroids for all the vertices.</li><li>Move each vertex in the tangent direction toward its centroid.</li></ol><p>Repeating this procedure about 5 or 6 times should yield results like the ones seen below; you may want to repeat the smoothing step 10-20 times for each “outer” iteration.</p><center><imgsrc="remesh_example.png"style="height:420px"/></center></div></div><divclass="search-overlay"></div></div></body></html>
