subdivision-interactive.html (80799B)
1 <!DOCTYPE html> 2 <html lang="en"> 3 <head> 4 <meta charset="utf-8"> 5 <meta name="viewport" content="width=device-width, initial-scale=1"> 6 <title>Subdivision Surfaces — from the refinement equation</title> 7 <link rel="preconnect" href="https://fonts.googleapis.com"> 8 <link rel="preconnect" href="https://fonts.gstatic.com" crossorigin> 9 <link href="https://fonts.googleapis.com/css2?family=IBM+Plex+Sans+Condensed:wght@600;700&family=IBM+Plex+Sans:wght@400;500;600&family=IBM+Plex+Mono:wght@400;500;600&display=swap" rel="stylesheet"> 10 <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.16.9/katex.min.css"> 11 <style> 12 :root{ 13 --ground:#10151a; --panel:#171e25; --panel2:#1d262e; 14 --chalk:#e8e6df; --dim:#9aa5ad; --cage:#6b7c8c; 15 --face:#f2b04a; --edge:#4fd6c4; --vert:#e86a92; 16 --rule:rgba(107,124,140,.22); 17 --mono:"IBM Plex Mono",ui-monospace,monospace; 18 --sans:"IBM Plex Sans",system-ui,sans-serif; 19 --cond:"IBM Plex Sans Condensed","IBM Plex Sans",system-ui,sans-serif; 20 } 21 *{box-sizing:border-box} 22 html{-webkit-text-size-adjust:100%} 23 body{margin:0;background:var(--ground);color:var(--chalk);font-family:var(--sans); 24 font-size:16.5px;line-height:1.65;-webkit-font-smoothing:antialiased} 25 canvas{display:block;max-width:100%} 26 .wrap{max-width:1080px;margin:0 auto;padding:0 22px 110px} 27 .col{max-width:66ch} 28 h1,h2,h3{font-family:var(--cond);font-weight:700;letter-spacing:-.015em;line-height:1.08;margin:0} 29 h2{font-size:clamp(1.5rem,4.4vw,2.15rem);margin:0 0 .5rem} 30 h4{font-family:var(--mono);font-size:.72rem;font-weight:600;letter-spacing:.14em; 31 text-transform:uppercase;color:var(--dim);margin:2rem 0 .6rem} 32 p{margin:0 0 1rem} ul,ol{margin:0 0 1rem;padding-left:1.25rem} li{margin-bottom:.4rem} 33 strong{font-weight:600;color:#fff} em{color:var(--chalk)} 34 code{font-family:var(--mono);font-size:.87em;background:rgba(107,124,140,.16); 35 padding:.12em .38em;border-radius:3px} 36 .hero{padding:clamp(52px,9vw,92px) 0 12px} 37 .eyebrow{font-family:var(--mono);font-size:.7rem;letter-spacing:.2em;text-transform:uppercase; 38 color:var(--cage);margin-bottom:1.4rem} 39 .hero h1{font-size:clamp(2.35rem,8vw,4.5rem);letter-spacing:-.03em;margin-bottom:1.1rem} 40 .hero h1 .thin{display:block;font-weight:600;color:var(--dim);font-size:.44em; 41 letter-spacing:-.01em;margin-top:.55rem} 42 .lede{font-size:clamp(1.02rem,2.4vw,1.2rem);color:var(--dim);max-width:56ch} 43 .lede b{color:var(--chalk);font-weight:500} 44 .legend{position:sticky;top:0;z-index:50;background:rgba(16,21,26,.94); 45 backdrop-filter:blur(10px);border-bottom:1px solid var(--rule);padding:9px 0;margin:52px 0 0} 46 .legend-in{max-width:1080px;margin:0 auto;padding:0 22px;display:flex;gap:16px; 47 flex-wrap:wrap;align-items:center;font-family:var(--mono);font-size:.7rem} 48 .key{display:flex;align-items:center;gap:6px;color:var(--dim);white-space:nowrap} 49 .dot{width:9px;height:9px;border-radius:50%;flex:none} 50 .dot.f{background:var(--face)}.dot.e{background:var(--edge)} 51 .dot.v{background:var(--vert)}.dot.c{background:var(--cage)} 52 section{padding:62px 0 0} 53 .snum{font-family:var(--mono);font-size:.7rem;letter-spacing:.18em;color:var(--cage); 54 display:block;margin-bottom:.85rem} 55 .snum b{color:var(--edge);font-weight:500} 56 .deriv{border-left:2px solid var(--rule);padding:2px 0 2px 20px;margin:1.5rem 0} 57 .deriv.f{border-color:rgba(242,176,74,.55)} 58 .deriv.e{border-color:rgba(79,214,196,.55)} 59 .deriv.v{border-color:rgba(232,106,146,.55)} 60 .deriv h5{font-family:var(--mono);font-size:.7rem;letter-spacing:.13em;text-transform:uppercase; 61 color:var(--dim);margin:0 0 .55rem;font-weight:500} 62 .deriv p:last-child{margin-bottom:0} 63 .note{background:var(--panel);border:1px solid var(--rule);border-radius:5px; 64 padding:16px 18px;margin:1.5rem 0;font-size:.94rem} 65 .note h5{font-family:var(--mono);font-size:.7rem;letter-spacing:.13em;text-transform:uppercase; 66 color:var(--edge);margin:0 0 .5rem;font-weight:600} 67 .note p:last-child{margin-bottom:0} 68 figure{margin:2.2rem 0;background:var(--panel);border:1px solid var(--rule); 69 border-radius:6px;overflow:hidden} 70 .figbar{display:flex;gap:14px;align-items:center;flex-wrap:wrap;padding:10px 14px; 71 border-bottom:1px solid var(--rule);background:var(--panel2)} 72 .ftitle{font-family:var(--mono);font-size:.7rem;letter-spacing:.11em;text-transform:uppercase; 73 color:var(--dim);margin-right:auto} 74 figure canvas{width:100%;height:auto;touch-action:none;cursor:grab;background:#0d1216} 75 figure canvas:active{cursor:grabbing} 76 figcaption{padding:12px 16px 14px;font-size:.85rem;color:var(--dim); 77 border-top:1px solid var(--rule);line-height:1.6} 78 figcaption b{color:var(--chalk);font-weight:500} 79 .readout{font-family:var(--mono);font-size:.73rem;color:var(--dim);padding:9px 14px; 80 border-top:1px solid var(--rule);min-height:34px;line-height:1.55} 81 .readout b{color:var(--chalk);font-weight:500} 82 .ctl{display:flex;align-items:center;gap:7px;font-family:var(--mono);font-size:.71rem;color:var(--dim)} 83 input[type=range]{-webkit-appearance:none;appearance:none;background:transparent; 84 width:104px;height:18px;margin:0;cursor:pointer} 85 input[type=range]::-webkit-slider-runnable-track{height:2px;background:var(--rule)} 86 input[type=range]::-webkit-slider-thumb{-webkit-appearance:none;width:12px;height:12px; 87 border-radius:50%;background:var(--chalk);margin-top:-5px;border:none} 88 input[type=range]::-moz-range-track{height:2px;background:var(--rule)} 89 input[type=range]::-moz-range-thumb{width:12px;height:12px;border-radius:50%; 90 background:var(--chalk);border:none} 91 input[type=range]:focus-visible{outline:2px solid var(--edge);outline-offset:3px} 92 .seg{display:inline-flex;border:1px solid var(--rule);border-radius:4px;overflow:hidden} 93 .seg button{font-family:var(--mono);font-size:.69rem;background:transparent;color:var(--dim); 94 border:0;padding:5px 9px;cursor:pointer;border-right:1px solid var(--rule)} 95 .seg button:last-child{border-right:0} 96 .seg button[aria-pressed=true]{background:var(--chalk);color:#0d1216;font-weight:600} 97 .seg button:focus-visible{outline:2px solid var(--edge);outline-offset:-2px} 98 .btn{font-family:var(--mono);font-size:.69rem;background:transparent;color:var(--dim); 99 border:1px solid var(--rule);border-radius:4px;padding:5px 10px;cursor:pointer} 100 .btn:hover{color:var(--chalk);border-color:var(--cage)} 101 .btn:focus-visible{outline:2px solid var(--edge);outline-offset:2px} 102 .val{color:var(--chalk);min-width:1.6em;display:inline-block} 103 label.chk{display:inline-flex;align-items:center;gap:5px;cursor:pointer} 104 input[type=checkbox]{accent-color:var(--edge);width:13px;height:13px;margin:0} 105 .stencils{display:flex;gap:22px;flex-wrap:wrap;margin:1.6rem 0} 106 .sten{font-family:var(--mono);font-size:.72rem} 107 .sten .lab{color:var(--dim);letter-spacing:.1em;text-transform:uppercase; 108 font-size:.66rem;margin-bottom:7px} 109 .sten .grid{display:inline-grid;gap:2px;background:var(--rule);padding:2px;border-radius:3px} 110 .sten .cell{background:var(--panel2);width:38px;height:30px;display:flex; 111 align-items:center;justify-content:center;color:var(--chalk)} 112 .sten.fS .cell.hi{background:rgba(242,176,74,.2);color:var(--face)} 113 .sten.eS .cell.hi{background:rgba(79,214,196,.2);color:var(--edge)} 114 .sten.vS .cell.hi{background:rgba(232,106,146,.2);color:var(--vert)} 115 .tbl{width:100%;overflow-x:auto;margin:1.7rem 0;-webkit-overflow-scrolling:touch} 116 table{border-collapse:collapse;font-size:.86rem;min-width:520px;width:100%} 117 th,td{text-align:left;padding:9px 13px 9px 0;border-bottom:1px solid var(--rule); 118 vertical-align:top} 119 th{font-family:var(--mono);font-size:.67rem;letter-spacing:.1em;text-transform:uppercase; 120 color:var(--dim);font-weight:500;white-space:nowrap} 121 td code{background:none;padding:0} 122 pre{font-family:var(--mono);font-size:.79rem;background:var(--panel); 123 border:1px solid var(--rule);border-radius:5px;padding:14px 16px;overflow-x:auto; 124 line-height:1.7;color:var(--chalk)} 125 hr{border:0;border-top:1px solid var(--rule);margin:58px 0 0} 126 .end{font-family:var(--mono);font-size:.76rem;color:var(--cage);line-height:1.9;padding-top:46px} 127 .katex{font-size:1.03em} 128 .katex-display{margin:1.15rem 0;overflow-x:auto;overflow-y:hidden;padding:2px 0} 129 @media (max-width:640px){ 130 body{font-size:16px} 131 .wrap{padding:0 16px 80px} 132 .legend-in{padding:0 16px;gap:11px;font-size:.66rem} 133 .deriv{padding-left:14px} 134 .sten .cell{width:33px;height:27px} 135 .figbar{gap:10px;padding:9px 11px} 136 input[type=range]{width:84px} 137 } 138 @media (prefers-reduced-motion:reduce){*{animation-duration:.01ms!important;transition-duration:.01ms!important}} 139 </style> 140 </head> 141 <body> 142 <div class="wrap"> 143 144 <header class="hero"> 145 <div class="eyebrow">Refinement operators on meshes</div> 146 <h1>Subdivision<br>Surfaces 147 <span class="thin">Every mask below is a B-spline in disguise.</span></h1> 148 <p class="lede">Drag the white points. A <b>control polygon</b> is hit repeatedly by one 149 linear operator; in the limit it becomes a curve you never wrote an equation for. Everything 150 else here is that same idea applied to meshes.</p> 151 </header> 152 153 <figure> 154 <div class="figbar"> 155 <span class="ftitle">Fig 1 — refinement, live</span> 156 <div class="seg" id="f1scheme"> 157 <button data-s="chaikin" aria-pressed="true">Chaikin · quadratic</button> 158 <button data-s="cubic" aria-pressed="false">Cubic B-spline</button></div> 159 <span class="ctl">level <input type="range" id="f1lvl" min="0" max="6" value="2"> 160 <b class="val" id="f1lvlv">2</b></span> 161 <label class="chk ctl"><input type="checkbox" id="f1limit" checked> limit</label> 162 </div> 163 <canvas id="f1"></canvas> 164 <div class="readout" id="f1out"></div> 165 <figcaption>Drag the white points — one finger works on a phone. <b>Chaikin</b> discards the 166 old vertices and puts two new points on every edge (a <em>dual</em> scheme). <b>Cubic</b> 167 keeps them and relaxes them (<em>primal</em>). At level 6 the polygon has already become the 168 curve.</figcaption> 169 </figure> 170 171 <div class="legend"><div class="legend-in"> 172 <span class="key" style="letter-spacing:.13em">COLOUR KEY</span> 173 <span class="key"><i class="dot c"></i>control cage, level k</span> 174 <span class="key"><i class="dot f"></i>face point</span> 175 <span class="key"><i class="dot e"></i>edge point</span> 176 <span class="key"><i class="dot v"></i>vertex point</span> 177 </div></div> 178 179 <section><div class="col"> 180 <span class="snum"><b>00</b> · VOCABULARY & THE COUNTING ARGUMENT</span> 181 <h2>Why irregular vertices are unavoidable</h2> 182 <p>A polygon mesh \(M=(V,E,F)\) carries two independent kinds of information, and subdivision 183 treats them separately:</p> 184 <ul> 185 <li><strong>Topology</strong> — which vertices join to which. Purely combinatorial.</li> 186 <li><strong>Geometry</strong> — the map \(V\to\mathbb{R}^3\) of positions. Purely numerical.</li> 187 </ul> 188 <p>Each step applies a <em>topological rule</em> (split faces) then a <em>geometric rule</em> 189 (average positions). Keeping them apart is what lets the method work on arbitrary shapes.</p> 190 <h4>Definitions</h4> 191 <div class="tbl"><table> 192 <tr><th>Term</th><th>Meaning</th></tr> 193 <tr><td><strong>Valence</strong> \(n(v)\)</td><td>number of edges incident to \(v\)</td></tr> 194 <tr><td><strong>\(k\)-ring</strong> of \(v\)</td><td>vertices at graph distance \(\le k\)</td></tr> 195 <tr><td><strong>Manifold</strong></td><td>every edge has 1 or 2 faces; every vertex's faces form one fan</td></tr> 196 <tr><td><strong>Regular vertex</strong></td><td>quad mesh: \(n=4\). Triangle mesh: \(n=6\)</td></tr> 197 <tr><td><strong>Extraordinary vertex</strong> (EV)</td><td>any vertex that is not regular</td></tr> 198 <tr><td><strong>Regular region</strong></td><td>submesh with no EV — locally a \(\mathbb{Z}^2\) grid</td></tr> 199 </table></div> 200 <div class="deriv"> 201 <h5>Derivation — the Euler obstruction</h5> 202 <p>For a closed orientable mesh, \(V-E+F=2-2g\). Suppose a closed quad mesh had <em>every</em> 203 vertex of valence 4. Each face has 4 edges, each edge shared by 2 faces, so \(4F=2E\Rightarrow 204 F=E/2\). Each vertex has 4 edge-ends, each edge has 2 ends, so \(4V=2E\Rightarrow V=E/2\). 205 Then</p> 206 \[\frac{E}{2}-E+\frac{E}{2}=0=2-2g\;\Longrightarrow\;g=1\] 207 <p>So <strong>only a torus admits an all-regular closed quad mesh.</strong> A sphere, a car 208 body, a wing fairing — every one <em>must</em> contain extraordinary vertices.</p> 209 </div> 210 <p>This drives everything below. Tensor-product B-splines need a global rectangular domain and 211 therefore cannot cover a closed surface. Subdivision throws away the global domain and keeps 212 only the <em>local</em> averaging rule — after which the whole literature is one question: 213 <em>what happens at the EVs?</em></p> 214 </div> 215 216 <figure> 217 <div class="figbar"> 218 <span class="ftitle">Fig 2 — valence, and where the EVs sit</span> 219 <div class="seg" id="f2shape"> 220 <button data-s="cube" aria-pressed="true">Cube</button> 221 <button data-s="torus" aria-pressed="false">Torus</button> 222 <button data-s="lshape" aria-pressed="false">L-block</button></div> 223 </div> 224 <canvas id="f2"></canvas> 225 <div class="readout" id="f2out"></div> 226 <figcaption>Drag to rotate. Vertices coloured by valence: 227 <b style="color:#6b7c8c">grey = 4, regular</b>; 228 <b style="color:#e86a92">rose = extraordinary</b>. The cube's 8 corners are all valence 3 — 229 every one an EV. The torus is the single shape that gets away with none.</figcaption> 230 </figure> 231 </section> 232 233 <hr> 234 235 <section><div class="col"> 236 <span class="snum"><b>01</b> · WHERE THE MASKS COME FROM</span> 237 <h2>The refinement equation</h2> 238 <p>Subdivision is read <em>backwards</em> out of B-spline theory, so we need that first — 239 briefly, and only the part that matters.</p> 240 <h4>Bases</h4> 241 <p>Bernstein: \(B_i^n(t)=\binom{n}{i}t^i(1-t)^{n-i}\), giving 242 \(\mathbf{C}(t)=\sum_i\mathbf{P}_iB_i^n(t)\). Since \(B_i^n\ge0\) and \(\sum_iB_i^n\equiv1\) — 243 a <strong>partition of unity</strong> — affine invariance and the convex-hull property come 244 free. Every mask below satisfies that pair.</p> 245 <p>B-splines replace Bernstein with Cox–de Boor on a knot vector:</p> 246 \[N_{i,p}(t)=\frac{t-t_i}{t_{i+p}-t_i}N_{i,p-1}(t)+\frac{t_{i+p+1}-t}{t_{i+p+1}-t_{i+1}}N_{i+1,p-1}(t)\] 247 <p><strong>Uniform</strong> means \(t_i=i\); then every basis function is an integer translate of 248 one <strong>cardinal B-spline</strong>, a repeated box convolution:</p> 249 \[N_p=\underbrace{\chi_{[0,1]}*\cdots*\chi_{[0,1]}}_{p+1\ \text{factors}},\qquad 250 \operatorname{supp}N_p=[0,p+1],\qquad N_p\in C^{p-1}\] 251 <div class="deriv e"> 252 <h5>Derivation — the two-scale relation</h5> 253 <p>Cardinal B-splines are <strong>refinable</strong>. In Fourier, 254 \(\widehat{N_p}(\omega)=\big(\tfrac{1-e^{-i\omega}}{i\omega}\big)^{p+1}\), so halving the 255 frequency gives \(\widehat{N_p}(\omega)=a(e^{-i\omega/2})\widehat{N_p}(\omega/2)\) with 256 \(a(z)=(1+z)^{p+1}/2^{p}\). Transforming back:</p> 257 \[\boxed{\;N_p(t)=\frac{1}{2^{p}}\sum_{k=0}^{p+1}\binom{p+1}{k}N_p(2t-k)\;}\] 258 <p>Call \(a_k=2^{-p}\binom{p+1}{k}\) the <strong>mask</strong> and \(a(z)=\sum_ka_kz^k\) the 259 <strong>symbol</strong>. This is the whole trick: <em>the same curve, on a knot grid twice as 260 fine, has different but computable control points.</em> Refinement replaces evaluation.</p> 261 </div> 262 <div class="deriv"> 263 <h5>Derivation — mask to operator</h5> 264 \[\boxed{\;\mathbf{p}^{k+1}_i=\sum_j a_{\,i-2j}\,\mathbf{p}^k_j\;}\] 265 <p>The \(-2j\) encodes the scale change. Splitting by the parity of \(i\) gives two 266 independent <strong>stencils</strong>:</p> 267 \[\text{even (vertex):}\ \mathbf{p}^{k+1}_{2i}=\sum_j a_{2j}\mathbf{p}^k_{i-j} 268 \qquad \text{odd (edge):}\ \mathbf{p}^{k+1}_{2i+1}=\sum_j a_{2j+1}\mathbf{p}^k_{i-j}\] 269 <p><strong>Convergence:</strong> \(a(1)=2\) and \(a(-1)=0\) — equivalently the even 270 coefficients sum to 1 <em>and</em> the odd ones sum to 1. Each stencil is separately a 271 partition of unity, so affine invariance and convex-hull containment hold at <em>every</em> 272 level, not just in the limit.</p> 273 </div> 274 </div> 275 276 <figure> 277 <div class="figbar"> 278 <span class="ftitle">Fig 3 — symbol, mask, stencils</span> 279 <span class="ctl">degree p <input type="range" id="f3p" min="1" max="5" value="3"> 280 <b class="val" id="f3pv">3</b></span> 281 </div> 282 <canvas id="f3"></canvas> 283 <div class="readout" id="f3out"></div> 284 <figcaption>Left: \(N_p\) in white, drawn as the sum of its own half-scale copies weighted by 285 the mask (<b style="color:#e86a92">even k</b>, <b style="color:#4fd6c4">odd k</b>) — that is 286 the two-scale relation, plotted. Right: the mask split by parity. Degree 2 is Chaikin; 287 degree 3 is split-and-smooth, which becomes Catmull–Clark.</figcaption> 288 </figure> 289 290 <div class="col"> 291 <div class="deriv e"> 292 <h5>Degree 2 — Chaikin, 1974</h5> 293 <p>\(a(z)=\tfrac14(1+z)^3\), mask \(\tfrac14[1,3,3,1]\). Parity split:</p> 294 \[\mathbf{q}_i=\tfrac34\mathbf{p}_i+\tfrac14\mathbf{p}_{i+1},\qquad 295 \mathbf{r}_i=\tfrac14\mathbf{p}_i+\tfrac34\mathbf{p}_{i+1}\] 296 <p>Two new points per edge at \(\tfrac14,\tfrac34\); old vertices <em>discarded</em>. Chaikin 297 invented it as pure <strong>corner cutting</strong>, no spline in mind — Riesenfeld later 298 proved the limit is the uniform quadratic B-spline. The idea traces to de Rham in the 299 1940s.</p> 300 </div> 301 <div class="deriv v"> 302 <h5>Degree 3 — split and smooth</h5> 303 <p>\(a(z)=\tfrac18(1+z)^4\), mask \(\tfrac18[1,4,6,4,1]\). Parity split:</p> 304 \[\text{odd}=\tfrac18[4,4]=[\tfrac12,\tfrac12],\qquad 305 \text{even}=\tfrac18[1,6,1]=[\tfrac18,\tfrac34,\tfrac18]\] 306 <p>As an algorithm: <strong>insert every edge midpoint, then relax every old vertex by 307 \(\tfrac18,\tfrac34,\tfrac18\)</strong>. That relaxation weight is the direct ancestor of every 308 surface vertex rule on this page.</p> 309 </div> 310 <div class="note"><h5>Lane–Riesenfeld, 1980</h5> 311 <p>The general degree-\(p\) scheme is one midpoint-doubling pass then \(p\) passes of pairwise 312 averaging — convolving with \(\tfrac12[1,1]\) raises the degree by one each time. \(O(p)\) per 313 point and trivially vectorised.</p></div> 314 <h4>Primal vs dual — a distinction that persists</h4> 315 <div class="tbl"><table> 316 <tr><th></th><th>Old vertices</th><th>New mesh sits</th><th>Curve</th><th>Surface</th></tr> 317 <tr><td><strong>Dual</strong></td><td>discarded</td><td>in the <em>faces</em></td><td>Chaikin</td><td>Doo–Sabin</td></tr> 318 <tr><td><strong>Primal</strong></td><td>retained, moved</td><td>on <em>vertices + edges</em></td><td>cubic</td><td>Catmull–Clark, Loop</td></tr> 319 </table></div> 320 <div class="deriv"> 321 <h5>Derivation — smoothness of the limit</h5> 322 <p>Given \(a(1)=2,a(-1)=0\) we factor \(a(z)=\tfrac{1+z}{2}a_{[1]}(z)\); then \(a_{[1]}\) is the 323 symbol acting on forward differences \(\Delta\mathbf{p}_i=\mathbf{p}_{i+1}-\mathbf{p}_i\). 324 <strong>Dyn–Gregory–Levin:</strong> if the difference scheme is contractive, 325 \(\|S_{a_{[1]}}^{L}\|_\infty<1\) for some \(L\), then \(S_a\) converges to a \(C^0\) limit; 326 recursing on divided differences gives \(C^1,C^2,\dots\) For \(a(z)=(1+z)^{p+1}/2^p\) this 327 returns <strong>\(C^{p-1}\)</strong>. Cubic \(\Rightarrow C^2\). Hold on to that number.</p> 328 </div> 329 <h4>Tensor product, and exactly where it breaks</h4> 330 \[\mathbf{S}(u,v)=\sum_{i=0}^{3}\sum_{j=0}^{3}\mathbf{P}_{ij}N_3(u-i)N_3(v-j)\] 331 <p>Masks tensor too — the bicubic surface masks are outer products of \(\tfrac18[1,4,6,4,1]\) 332 with itself:</p> 333 <div class="stencils"> 334 <div class="sten vS"><div class="lab">vertex 1/64</div><div class="grid"> 335 <div class="cell">1</div><div class="cell">6</div><div class="cell">1</div> 336 <div class="cell">6</div><div class="cell hi">36</div><div class="cell">6</div> 337 <div class="cell">1</div><div class="cell">6</div><div class="cell">1</div></div></div> 338 <div class="sten eS"><div class="lab">edge 1/16</div><div class="grid"> 339 <div class="cell">1</div><div class="cell">1</div> 340 <div class="cell hi">6</div><div class="cell hi">6</div> 341 <div class="cell">1</div><div class="cell">1</div></div></div> 342 <div class="sten fS"><div class="lab">face 1/4</div><div class="grid"> 343 <div class="cell hi">1</div><div class="cell hi">1</div> 344 <div class="cell hi">1</div><div class="cell hi">1</div></div></div> 345 </div> 346 <p>Here is the problem in one sentence. <strong>Tensor product requires a rectangular parameter 347 domain</strong> — the mesh must be combinatorially \(\mathbb{Z}^2\). By §00 no closed surface 348 except a torus admits that. Trimming, \(G^1\) patch stitching, singular polar caps: all the 349 familiar NURBS pain.</p> 350 <p>But look at the masks again — they are <em>local</em>, reading only a 1-ring. So stop asking 351 for a global grid. Generalise the mask to arbitrary valence and apply it everywhere. That is 352 the content of the next three sections.</p> 353 </div></section> 354 355 <hr> 356 357 <section><div class="col"> 358 <span class="snum"><b>02</b> · LIFTING CHAIKIN — DOO–SABIN, 1978</span> 359 <h2>The dual scheme on surfaces</h2> 360 <div class="deriv f"><h5>Topological rule</h5> 361 <p>One new point per face-corner. Then three families of new faces: an <strong>F-face</strong> 362 per old face, an <strong>E-face</strong> per old edge (4 points), and a <strong>V-face</strong> 363 per old vertex \(v\) — an \(n(v)\)-gon. Old vertices vanish.</p></div> 364 <div class="deriv"><h5>Geometric rule</h5> 365 <p>For an \(n\)-gon, the new point at corner \(i\) is 366 \(\mathbf{p}'_i=\sum_j\alpha_{ij}\mathbf{p}_j\) with</p> 367 \[\alpha_{ii}=\frac{n+5}{4n},\qquad 368 \alpha_{ij}=\frac{3+2\cos\!\big(\tfrac{2\pi(i-j)}{n}\big)}{4n}\quad(i\ne j)\] 369 <p><strong>Check \(n=4\):</strong> \(\alpha_{ii}=9/16\); adjacent \(=3/16\); opposite 370 \(=1/16\) — exactly \(\tfrac14[3,1]\otimes\tfrac14[3,1]=\tfrac1{16}[9,3,3,1]\), the 371 biquadratic mask. ✓</p></div> 372 <p>All faces become quads; the limit is biquadratic B-spline on regular regions, \(C^1\) at 373 EVs. The \(\cos(2\pi k/n)\) is not decoration — it is the discrete Fourier basis on the 374 \(n\)-cycle, the first hint that EV analysis will be spectral. §05 makes that explicit.</p> 375 </div></section> 376 377 <hr> 378 379 <section><div class="col"> 380 <span class="snum"><b>03</b> · LIFTING CUBIC — CATMULL–CLARK, 1978</span> 381 <h2>Three passes, and one very useful accident</h2> 382 <p>Catmull and Clark were graduate students at Utah. Doo and Sabin, in Europe, pointed out that 383 the arbitrary-topology extension applied to the cubic case too; Catmull and Clark wrote it in 384 the form everyone now uses. It is the industry standard — Pixar, OpenSubdiv, Maya, Blender.</p> 385 <div class="deriv f"><h5>Pass 1 — face points</h5> 386 \[\boxed{\;\mathbf{f}=\frac{1}{m}\sum_{i=1}^{m}\mathbf{v}_i\;}\]</div> 387 <div class="deriv e"><h5>Pass 2 — edge points</h5> 388 <p>Endpoints \(\mathbf{v}_1,\mathbf{v}_2\) and the two <em>new</em> face points:</p> 389 \[\boxed{\;\mathbf{e}=\tfrac14(\mathbf{v}_1+\mathbf{v}_2+\mathbf{f}_1+\mathbf{f}_2)\;}\]</div> 390 <div class="deriv v"><h5>Pass 3 — vertex points</h5> 391 <p>\(Q\) = average of incident new face points, \(R\) = average of incident edge 392 <em>midpoints</em>:</p> 393 \[\boxed{\;\mathbf{v}'=\frac{Q+2R+(n-3)\mathbf{v}}{n}\;}\] 394 <p>Equivalently, and cheaper:</p> 395 \[\mathbf{v}'=\frac{n-2}{n}\mathbf{v}+\frac{1}{n^2}\sum_i\mathbf{e}_i+\frac{1}{n^2}\sum_i\mathbf{f}_i\]</div> 396 <p>Then reconnect: every new face is 397 <span style="color:#f2b04a">face point</span> → <span style="color:#4fd6c4">edge point</span> 398 → <span style="color:#e86a92">vertex point</span> → <span style="color:#4fd6c4">edge 399 point</span>. All output faces are quads. The chain \(\mathbf{f}\to\mathbf{e}\to\mathbf{v}'\) is 400 why it is three passes and not one.</p> 401 </div> 402 403 <figure> 404 <div class="figbar"> 405 <span class="ftitle">Fig 4 — the three passes, with masks</span> 406 <div class="seg" id="f4pass"> 407 <button data-p="0" aria-pressed="true">cage</button> 408 <button data-p="1" aria-pressed="false">+ face</button> 409 <button data-p="2" aria-pressed="false">+ edge</button> 410 <button data-p="3" aria-pressed="false">+ vertex</button> 411 <button data-p="4" aria-pressed="false">reconnect</button></div> 412 <button class="btn" id="f4reset">reset cage</button> 413 </div> 414 <canvas id="f4"></canvas> 415 <div class="readout" id="f4out">Step through the passes, then tap or hover any coloured point to see the stencil that produced it.</div> 416 <figcaption>A planar cage with a <b style="color:#e86a92">valence-5 vertex</b> at the centre. 417 <b>Hover or tap a coloured point</b> — the contributing cage points light up with their 418 weights and dashed lines to the result. White points are draggable.</figcaption> 419 </figure> 420 421 <div class="col"> 422 <div class="deriv"> 423 <h5>Derivation — why this <em>is</em> bicubic, not an approximation of it</h5> 424 <p>Set \(n=4\) in a regular grid. Each incident face point is 425 \(\mathbf{f}_i=\tfrac14(\mathbf{v}+\mathbf{e}_a+\mathbf{e}_b+\mathbf{d})\); summing over four 426 faces (each edge-neighbour appears twice, each diagonal once):</p> 427 \[Q=\tfrac1{16}\Big(4\mathbf{v}+2\textstyle\sum\mathbf{e}+\sum\mathbf{d}\Big),\qquad 428 R=\tfrac12\mathbf{v}+\tfrac18\textstyle\sum\mathbf{e}\] 429 <p>Substituting into \(\mathbf{v}'=\tfrac14[Q+2R+\mathbf{v}]\):</p> 430 \[\mathbf{v}'=\tfrac{9}{16}\mathbf{v}+\tfrac{3}{32}\textstyle\sum\mathbf{e}+\tfrac{1}{64}\sum\mathbf{d}\] 431 <p>Against the bicubic mask \(\tfrac1{64}[1,6,1;6,36,6;1,6,1]\): centre \(36/64=9/16\) ✓, 432 edge-neighbour \(6/64=3/32\) ✓, diagonal \(1/64\) ✓. So <strong>on regular regions 433 Catmull–Clark <em>is</em> the bicubic uniform B-spline, exactly.</strong> The generalisation 434 only ever acts near an EV.</p> 435 </div> 436 <h4>The valence bookkeeping — the structurally important part</h4> 437 <div class="tbl"><table> 438 <tr><th>New vertex</th><th>Valence</th></tr> 439 <tr><td><span style="color:#f2b04a">face point</span> of an \(m\)-gon</td><td>\(m\)</td></tr> 440 <tr><td><span style="color:#4fd6c4">edge point</span></td><td><strong>always 4</strong></td></tr> 441 <tr><td><span style="color:#e86a92">vertex point</span> from \(\mathbf{v}\)</td><td>\(n(\mathbf{v})\) — <strong>preserved</strong></td></tr> 442 </table></div> 443 <ol> 444 <li>After one step <strong>all faces are quads</strong>, so from step 2 on all face points have valence 4.</li> 445 <li>The EV set is <strong>frozen after step 1</strong>. No new EVs are ever created.</li> 446 <li>Each step halves edge lengths, so <strong>EVs become progressively isolated</strong>.</li> 447 </ol> 448 <p>Point 3 is the payoff. Once EVs are more than two rings apart, every remaining region has a 449 \(4\times4\) net in rectangular topology — a genuine bicubic patch.</p> 450 <div class="note"><h5>The limit surface</h5> 451 <p>Catmull–Clark converges to a surface that is <strong>piecewise bicubic and \(C^2\) 452 everywhere, except at finitely many isolated points where it is \(C^1\)</strong>. Those points 453 are exactly the EVs of the original cage, and there are never more of them than you started 454 with.</p></div> 455 </div> 456 457 <figure> 458 <div class="figbar"> 459 <span class="ftitle">Fig 5 — Catmull–Clark in 3D</span> 460 <div class="seg" id="f5shape"> 461 <button data-s="cube" aria-pressed="true">Cube</button> 462 <button data-s="lshape" aria-pressed="false">L-block</button> 463 <button data-s="pent" aria-pressed="false">Pentagon prism</button> 464 <button data-s="tet" aria-pressed="false">Tetrahedron</button></div> 465 <span class="ctl">level <input type="range" id="f5lvl" min="0" max="4" value="0"> 466 <b class="val" id="f5lvlv">0</b></span> 467 <label class="chk ctl"><input type="checkbox" id="f5ev" checked> mark EVs</label> 468 <label class="chk ctl"><input type="checkbox" id="f5cage"> show cage</label> 469 </div> 470 <canvas id="f5"></canvas> 471 <div class="readout" id="f5out"></div> 472 <figcaption>Drag to rotate. Watch the EV count: it jumps once at level 1 and then 473 <b>never changes again</b>, exactly as the bookkeeping predicts. The surface also pulls 474 inward — see the shrinkage note in §04.</figcaption> 475 </figure> 476 </section> 477 478 <hr> 479 480 <section><div class="col"> 481 <span class="snum"><b>04</b> · TRIANGLES — LOOP, 1987</span> 482 <h2>Where 5/8 and 3/8 come from</h2> 483 <p>Charles Loop's Utah master's thesis. Triangles only, regular valence 6, topologically the 484 1-to-4 split.</p> 485 <div class="deriv e"><h5>Edge (odd) rule</h5> 486 <p>\(\mathbf{v}_3,\mathbf{v}_4\) are the opposite vertices of the two adjacent triangles:</p> 487 \[\boxed{\;\mathbf{e}=\tfrac38(\mathbf{v}_1+\mathbf{v}_2)+\tfrac18(\mathbf{v}_3+\mathbf{v}_4)\;}\]</div> 488 <div class="deriv v"><h5>Vertex (even) rule</h5> 489 \[\boxed{\;\mathbf{v}'=(1-n\beta)\mathbf{v}+\beta\sum_{i=1}^{n}\mathbf{v}_i\;}\qquad 490 \beta(n)=\frac{1}{n}\left[\frac58-\left(\frac38+\frac14\cos\frac{2\pi}{n}\right)^{\!2}\right]\] 491 <p>Warren's substitute: \(\beta=\tfrac{3}{8n}\) for \(n>3\), \(\beta=\tfrac{3}{16}\) for 492 \(n=3\). <strong>Checks.</strong> At \(n=6\): 493 \(\tfrac16[\tfrac58-(\tfrac12)^2]=\tfrac1{16}\), and \(\tfrac{3}{48}=\tfrac1{16}\) ✓. At 494 \(n=3\): \(\tfrac13[\tfrac58-\tfrac1{16}]=\tfrac{3}{16}\) ✓. They agree at \(n=3,6\) and differ 495 elsewhere — at \(n=4\), \(31/256\) versus \(3/32\).</p></div> 496 <p>The limit is the <strong>quartic box spline</strong> on regular regions — \(C^2\) there, 497 \(C^1\) at EVs.</p> 498 <h4>Approximating vs interpolating — "why does it shrink?"</h4> 499 <p>Every mask above is non-negative and sums to 1, so each new point lies in the convex hull of 500 its stencil, and the limit surface lies in the convex hull of the cage. It pulls 501 <em>inward</em>, most visibly at sharp corners and in concave regions. These are 502 <strong>approximating</strong> schemes: control points are not on the surface.</p> 503 <p><strong>Interpolating</strong> schemes — the 4-point rule, Butterfly — fix the old points and 504 use negative weights:</p> 505 \[\mathbf{p}^{k+1}_{2i+1}=-\tfrac1{16}\mathbf{p}_{i-1}+\tfrac9{16}\mathbf{p}_i 506 +\tfrac9{16}\mathbf{p}_{i+1}-\tfrac1{16}\mathbf{p}_{i+2}\] 507 <p>The negative weights buy interpolation but lose the convex-hull property, with worse fairness 508 and less stable behaviour. Production accepts the shrinkage.</p> 509 </div> 510 511 <figure> 512 <div class="figbar"> 513 <span class="ftitle">Fig 6 — Loop, and the shrinkage</span> 514 <div class="seg" id="f6shape"> 515 <button data-s="tet" aria-pressed="true">Tetrahedron</button> 516 <button data-s="icosa" aria-pressed="false">Icosahedron</button> 517 <button data-s="octa" aria-pressed="false">Octahedron</button></div> 518 <span class="ctl">level <input type="range" id="f6lvl" min="0" max="4" value="0"> 519 <b class="val" id="f6lvlv">0</b></span> 520 <label class="chk ctl"><input type="checkbox" id="f6cage" checked> show cage</label> 521 </div> 522 <canvas id="f6"></canvas> 523 <div class="readout" id="f6out"></div> 524 <figcaption>The dashed grey wireframe is the level-0 cage. The shaded surface sits strictly 525 <em>inside</em> it — the convex-hull property made visible, and the reason approximating 526 schemes never interpolate their control points.</figcaption> 527 </figure> 528 529 <div class="col"> 530 <h4>The three schemes side by side</h4> 531 <div class="tbl"><table> 532 <tr><th></th><th>Doo–Sabin</th><th>Catmull–Clark</th><th>Loop</th></tr> 533 <tr><td>Primal / dual</td><td>dual</td><td>primal</td><td>primal</td></tr> 534 <tr><td>Input faces</td><td>any</td><td>any</td><td>triangles only</td></tr> 535 <tr><td>Output faces</td><td>quads</td><td>quads</td><td>triangles</td></tr> 536 <tr><td>Regular limit</td><td>biquadratic</td><td><strong>bicubic B-spline</strong></td><td>quartic box spline</td></tr> 537 <tr><td>Continuity</td><td>\(C^1\)</td><td>\(C^2\), \(C^1\) at EV</td><td>\(C^2\), \(C^1\) at EV</td></tr> 538 <tr><td>Regular valence</td><td>4</td><td>4</td><td>6</td></tr> 539 </table></div> 540 <p>Catmull–Clark won industrially for the \(C^2\) and, more importantly, for the clean 541 bicubic-patch correspondence that makes §06 possible.</p> 542 </div></section> 543 544 <hr> 545 546 <section><div class="col"> 547 <span class="snum"><b>05</b> · WHAT HAPPENS AT AN EV</span> 548 <h2>The local subdivision matrix</h2> 549 <p>This is the part the lecture defers to "next quarter". It is the mathematical core, and it is 550 entirely linear algebra.</p> 551 <div class="deriv"><h5>Setup</h5> 552 <p>Near an EV of valence \(n\), subdivision is a linear map on a finite neighbourhood. Collect 553 the 1-ring control points — centre, \(n\) edge-neighbours, \(n\) face-diagonals — into 554 \(\mathbf{P}^k\in\mathbb{R}^{2n+1}\) per coordinate:</p> 555 \[\boxed{\;\mathbf{P}^{k+1}=A\mathbf{P}^{k}\;}\qquad\Longrightarrow\qquad\mathbf{P}^{k}=A^{k}\mathbf{P}^{0}\] 556 <p>\(A\) is the <strong>local subdivision matrix</strong>. Everything about the surface at the EV 557 is in its spectrum.</p></div> 558 <div class="deriv"><h5>(a) \(\lambda_0=1\) always</h5> 559 <p>Every row of \(A\) sums to 1 — partition of unity again — so \(A\mathbf{1}=\mathbf{1}\). That 560 is affine invariance. Convergence forces \(|\lambda_1|<1\).</p></div> 561 <div class="deriv"><h5>(b) Limit position — jump straight to the surface</h5> 562 <p>With right eigenvectors \(\mathbf{x}_i\) and left eigenvectors \(\boldsymbol{\ell}_i\), 563 \(A^k\to\mathbf{x}_0\boldsymbol{\ell}_0^{\top}\), so 564 \(\mathbf{v}^{\infty}=\boldsymbol{\ell}_0^{\top}\mathbf{P}^0\). For Catmull–Clark 565 (Halstead–Kass–DeRose 1993) this is the <strong>limit-point mask</strong></p> 566 \[\boxed{\;\mathbf{v}^{\infty}=\frac{n^{2}\mathbf{v}+4\sum_i\mathbf{e}_i+\sum_i\mathbf{f}_i}{n(n+5)}\;}\] 567 <p><strong>Check \(n=4\):</strong> \(\tfrac1{36}(16\mathbf{v}+4\sum\mathbf{e}+\sum\mathbf{f})\), 568 matching \(\tfrac16[1,4,1]\otimes\tfrac16[1,4,1]\) ✓. One dot product and you are on the 569 surface — no iteration.</p></div> 570 <div class="deriv"><h5>(c) Tangent plane from the subdominant pair</h5> 571 <p>Expanding \(\mathbf{P}^0=\sum_ic_i\mathbf{x}_i\),</p> 572 \[\mathbf{P}^k=c_0\mathbf{x}_0+\lambda_1^kc_1\mathbf{x}_1+\lambda_2^kc_2\mathbf{x}_2+O(|\lambda_3|^k)\] 573 <p>so the <strong>tangent plane is spanned by \(\boldsymbol{\ell}_1^{\top}\mathbf{P}^0\) and 574 \(\boldsymbol{\ell}_2^{\top}\mathbf{P}^0\)</strong> — the two tangent masks; the normal is their 575 cross product. Exact normals at an EV, no differencing.</p></div> 576 <div class="deriv"><h5>(d) The \(C^1\) conditions</h5> 577 <p><em>Necessary:</em> \(1>\lambda_1=\lambda_2>|\lambda_3|\), \(\lambda_1\) real with a 578 two-dimensional eigenspace. <em>Sufficient</em> (Reif 1995): the <strong>characteristic 579 map</strong> \(\Phi:\mathbb{R}^2\to\mathbb{R}^2\) built from 580 \(\boldsymbol{\ell}_1,\boldsymbol{\ell}_2\) must be regular and injective — a finite check per 581 valence, tabulated numerically once. For Catmull–Clark, with \(c=\cos(2\pi/n)\):</p> 582 \[\lambda(n)=\tfrac{1}{16}\left(c+5+\sqrt{(c+9)(c+1)}\right)\] 583 <p>At \(n=4\): \(\tfrac1{16}(5+3)=\tfrac12\) ✓ — the bicubic contraction rate. At \(n=3\): 584 \(\approx0.4101\).</p></div> 585 </div> 586 587 <figure> 588 <div class="figbar"> 589 <span class="ftitle">Fig 7 — subdominant eigenvalue vs valence</span> 590 <span class="ctl">valence n <input type="range" id="f7n" min="3" max="12" value="4"> 591 <b class="val" id="f7nv">4</b></span> 592 </div> 593 <canvas id="f7"></canvas> 594 <div class="readout" id="f7out"></div> 595 <figcaption>\(\lambda(n)\) drifts away from the regular value \(\tfrac12\) in both directions. 596 Since \(\lambda\) sets the contraction rate, and \(C^2\) needs a specific relation between 597 \(\lambda^2\) and the next eigenvalue group, <b>high-valence vertices genuinely degrade the 598 surface</b>. "Keep valences near 4" is a statement about eigenvalues, not taste.</figcaption> 599 </figure> 600 601 <div class="col"> 602 <div class="note"><h5>Curvature — where Catmull–Clark actually fails</h5> 603 <p>\(C^2\) at an EV needs conditions relating \(\lambda_1^2\) to the next eigenvalue group, and 604 Catmull–Clark generically <strong>fails</strong> them: curvature there is unbounded or zero. 605 Tuned schemes (Sabin; Prautzsch–Umlauf; Karčiauskas–Peters) fix it at some other cost. For aero 606 surfaces this is not academic — curvature-discontinuous points show up in reflection lines and 607 pressure-gradient artefacts.</p></div> 608 <h4>Exact evaluation — Stam, 1998</h4> 609 <ol> 610 <li>Map \((u,v)\) into a dyadic annulus — find the \(k\) after which it lies in a regular 611 sub-patch.</li> 612 <li>Apply \(A^k=X\Lambda^kX^{-1}\), so \(\Lambda^k\) is just scalar powers. \(O(1)\) in 613 \(k\).</li> 614 <li>Evaluate the resulting bicubic patch directly.</li> 615 </ol> 616 <p><strong>Exact positions and exact first and second derivatives at arbitrary \((u,v)\), in 617 closed form.</strong> This is what turns a subdivision surface from a refinement process into 618 an honest parametric surface.</p> 619 </div></section> 620 621 <hr> 622 623 <section><div class="col"> 624 <span class="snum"><b>06</b> · BACK TO PATCHES</span> 625 <h2>B-spline to Bézier, and the 2008 shortcut</h2> 626 <div class="deriv"><h5>Uniform bicubic B-spline → Bézier</h5> 627 \[M=\frac16\begin{bmatrix}1&4&1&0\\0&4&2&0\\0&2&4&0\\0&1&4&1\end{bmatrix},\qquad B=MPM^{\!\top}\] 628 <p>\(B\) is the Bézier net of the identical patch. Every regular Catmull–Clark region converts 629 to a bicubic Bézier patch <em>exactly</em> — which is how subdivision surfaces enter GPU 630 tessellation and interoperate with NURBS CAD.</p></div> 631 <div class="note"><h5>Loop & Schaefer, TOG 2008</h5> 632 <p>For EV-adjacent patches, drop exact evaluation: one bicubic patch for position plus two 633 separately-constructed tangent fields for normals. \(C^0\) in position with small controlled 634 error, but \(G^1\) in the normal field — so it <em>looks</em> right. Uniform patch 635 representation, no eigen-machinery, no branching. This is what OpenSubdiv's feature-adaptive GPU 636 path is built on, and the construction to reach for if you want closed-form 637 \(\partial\mathbf{S}/\partial u\) across a whole surface.</p></div> 638 </div></section> 639 640 <hr> 641 642 <section><div class="col"> 643 <span class="snum"><b>07</b> · THE DATA STRUCTURE FROM HELL</span> 644 <h2>Half-edges, and two permutations</h2> 645 <p>The three passes need these in \(O(1)\) or \(O(\text{valence})\):</p> 646 <div class="tbl"><table> 647 <tr><th>Query</th><th>Needed by</th></tr> 648 <tr><td>face → its vertices, in order</td><td><span style="color:#f2b04a">face points</span></td></tr> 649 <tr><td><strong>edge → its two incident faces</strong></td><td><span style="color:#4fd6c4">edge points</span></td></tr> 650 <tr><td><strong>vertex → its ordered 1-ring</strong></td><td><span style="color:#e86a92">vertex points</span></td></tr> 651 </table></div> 652 <p>An indexed face list gives you the first and neither of the others without a full scan. Hence 653 the nickname.</p> 654 <p>The "split edge" is what is now called the <strong>half-edge</strong> (also <em>dart</em>, or 655 <em>directed edge</em>). Split every undirected edge into two opposite directed halves:</p> 656 <pre>struct HalfEdge { 657 origin: VertexId, <span style="color:#9aa5ad">// vertex it emanates from</span> 658 twin: HalfEdgeId, <span style="color:#9aa5ad">// the opposite half-edge</span> 659 next: HalfEdgeId, <span style="color:#9aa5ad">// next half-edge round this face (CCW)</span> 660 face: FaceId, <span style="color:#9aa5ad">// the face on its left</span> 661 }</pre> 662 <p>Each vertex stores one outgoing half-edge; each face stores one of its half-edges.</p> 663 <div class="deriv"><h5>The algebraic view — a combinatorial map</h5> 664 <p>Two permutations on the set \(H\) of half-edges, \(|H|=2E\): the twin map \(\alpha\), an 665 <strong>involution</strong> with \(\alpha^2=\mathrm{id}\) and no fixed points; and the next map 666 \(\nu\). The entire topology is their orbits:</p> 667 \[\text{faces}=\text{orbits of }\nu,\qquad\text{vertices}=\text{orbits of }\nu\circ\alpha, 668 \qquad\text{edges}=\text{orbits of }\alpha\] 669 <p>and \(V-E+F=2-2g\) recovers the genus. Two permutations; that is the whole structure.</p></div> 670 </div> 671 672 <figure> 673 <div class="figbar"> 674 <span class="ftitle">Fig 8 — traversal</span> 675 <div class="seg" id="f8mode"> 676 <button data-m="face" aria-pressed="true">face loop · ν</button> 677 <button data-m="ring" aria-pressed="false">1-ring · ν∘α</button> 678 <button data-m="twin" aria-pressed="false">twins · α</button></div> 679 <button class="btn" id="f8step">step</button> 680 <button class="btn" id="f8play">auto</button> 681 </div> 682 <canvas id="f8"></canvas> 683 <div class="readout" id="f8out"></div> 684 <figcaption>Each undirected edge is two opposed arrows. <b>Face loop</b> follows 685 <code>next</code> until it closes. <b>1-ring</b> alternates <code>twin</code> then 686 <code>next</code> — the "alternate twin and next" move, at \(O(\text{valence})\).</figcaption> 687 </figure> 688 689 <div class="col"> 690 <h4>Invariants</h4> 691 \[\alpha(\alpha(h))=h,\quad \nu\text{-orbits}=\text{faces},\quad 692 \mathrm{face}(\nu(h))=\mathrm{face}(h),\quad \mathrm{origin}(\alpha(h))=\mathrm{origin}(\nu(h))\] 693 <p>Every traversal assumes all four. During construction they are <em>transiently violated</em> — 694 which is exactly the segfault complaint. Not a soft warning: a half-built half-edge mesh either 695 loops forever or dereferences garbage.</p> 696 <p><strong>Restrictions.</strong> Manifold only — an edge with three faces has no well-defined 697 twin. Boundaries need a null-face sentinel or a virtual boundary loop; the latter keeps the 698 invariants total, and is what I would use.</p> 699 <div class="note"><h5>Rust, specifically</h5> 700 <p>Do not model this with references. The pointer graph is cyclic, so <code>&</code> / 701 <code>&mut</code> is unrepresentable without <code>Rc<RefCell<_>></code> — which 702 costs runtime borrow panics, cache locality, and <code>Send</code>.</p> 703 <p><strong>Use an arena with integer handles:</strong> <code>Vec<HalfEdge></code> plus 704 <code>u32</code> indices. Contiguous, cache-friendly, trivially <code>Send + Sync</code>. Then 705 refinement is a pure <code>Mesh -> Mesh</code>, the hierarchy is a 706 <code>Vec<Mesh></code>, and each level parallelises directly with rayon since all three 707 passes are read-only on level \(k\) and write-only to level \(k{+}1\).</p> 708 <p>Two refinements worth taking: store half-edges in pairs so <code>twin(h) = h ^ 1</code> 709 (saves a field and an indirection), and use a slotmap with generational indices if you need 710 handles stable under edge collapse. Alternatives: <em>directed edges</em> 711 (Campagna–Kobbelt–Seidel 1998) for triangle-only meshes at roughly half the memory; 712 <em>quad-edge</em> if you want the dual for free.</p></div> 713 </div></section> 714 715 <hr> 716 717 <section><div class="col"> 718 <span class="snum"><b>08</b> · A DIFFERENT ANIMAL</span> 719 <h2>The geodesic sphere</h2> 720 <p>Do not conflate this with the above. The problem is: how do you tessellate a sphere? Not with 721 patches — a UV sphere degenerates at the poles and pinches textures; rational patches 722 distort.</p> 723 <ol> 724 <li>Start with a regular <strong>icosahedron</strong>: \(V{=}12,E{=}30,F{=}20\), every vertex 725 valence 5. Euler: \(12-30+20=2\) ✓. The closed triangle mesh with the most uniform possible 726 vertex distribution.</li> 727 <li><strong>1-to-4 split</strong> each triangle — the same topological operation as Loop.</li> 728 <li><strong>Project</strong> radially: \(\mathbf{p}\mapsto r\mathbf{p}/\|\mathbf{p}\|\).</li> 729 <li>Repeat. After \(k\) steps, \(F=20\cdot4^k\) and \(V=10\cdot4^k+2\).</li> 730 </ol> 731 <div class="note"><h5>The distinction that matters</h5> 732 <p>Radial projection is <strong>interpolating</strong> and exact against the analytic sphere at 733 every level. Running <strong>Loop</strong> on the same icosahedron is 734 <strong>approximating</strong>: it shrinks inward and converges to a smooth blob that is 735 <em>not</em> a sphere. Same combinatorial split, completely different geometry. Toggle below and 736 watch the radius readout.</p></div> 737 </div> 738 739 <figure> 740 <div class="figbar"> 741 <span class="ftitle">Fig 9 — project vs subdivide</span> 742 <div class="seg" id="f9mode"> 743 <button data-m="project" aria-pressed="true">radial project</button> 744 <button data-m="loop" aria-pressed="false">Loop subdivide</button></div> 745 <span class="ctl">level <input type="range" id="f9lvl" min="0" max="4" value="2"> 746 <b class="val" id="f9lvlv">2</b></span> 747 </div> 748 <canvas id="f9"></canvas> 749 <div class="readout" id="f9out"></div> 750 <figcaption>Same 1-to-4 split in both cases. <b>Radial project</b> holds 751 \(\|\mathbf{p}\|=1\) exactly. <b>Loop</b> lets the radius collapse — the min/max readout shows 752 it drifting well below 1 and staying non-constant.</figcaption> 753 </figure> 754 </section> 755 756 <hr> 757 758 <section><div class="col"> 759 <span class="snum"><b>09</b> · DIFFERENTIATING THROUGH IT</span> 760 <h2>What is smooth in the parameters, and what is not</h2> 761 <div class="deriv"><h5>Positions are linear in the control points</h5> 762 \[\mathbf{S}^{\infty}=L\,A^{k}\,\mathbf{P}^{0}\qquad\Longrightarrow\qquad 763 \frac{\partial\mathbf{S}^{\infty}}{\partial\mathbf{P}^{0}}=L\,A^{k}\] 764 <p>with \(L\) the limit/evaluation operator. This Jacobian is <strong>exact, sparse and 765 constant</strong> — no approximation, no finite differencing. Autodiff through \(k\) rounds is 766 \(k\) sparse matmuls with a known transpose; reverse mode is cheap, and you can regenerate the 767 sparsity pattern rather than store it.</p></div> 768 <p><strong>Surface derivatives</strong> come from §05 (Stam, exact) or §06 (Loop–Schaefer, 769 closed-form per patch). Either gives differentiable normals — what you need for pressure 770 integration or any normal-dependent objective.</p> 771 <div class="note"><h5>The non-differentiable boundary is topology</h5> 772 <p>Valence, connectivity and the EV set are discrete. You can freely optimise vertex positions 773 with gradients; you cannot differentiate through an edge collapse, a valence change or a 774 remesh. Same wall as differentiable iso-surface extraction: the geometry is smooth in the 775 parameters, the combinatorics is not. Standard practice — fix the cage topology, optimise 776 positions only, treat remeshing as a discrete outer step.</p></div> 777 <p><strong>Sharp features.</strong> Production Catmull–Clark adds a per-edge crease sharpness 778 \(\sigma\in[0,\infty)\), blending between the smooth rule and the piecewise-linear rule. 779 Semi-sharp creases are \(C^0\) along the crease, and \(\sigma\) is a <em>continuous</em> 780 parameter — so it is differentiable, useful if you ever want to optimise feature-line strength 781 directly.</p> 782 </div></section> 783 784 <div class="col end"> 785 <div style="color:#9aa5ad;letter-spacing:.14em">READING ORDER</div> 786 <div style="margin-top:12px"> 787 1 Joy, <em>On-Line Geometric Modeling Notes</em> — Subdivision Curves → Surfaces → Doo-Sabin → Catmull-Clark → Loop<br> 788 2 Zorin & Schröder, <em>Subdivision for Modeling and Animation</em>, SIGGRAPH '99 — Ch. 4 for schemes, analysis chapter for §05<br> 789 3 Stam 1998, <em>Exact Evaluation of Catmull-Clark Subdivision Surfaces at Arbitrary Parameter Values</em><br> 790 4 Loop & Schaefer 2008, TOG 27(1) — the one for your purposes<br> 791 5 Reif 1995 — the \(C^1\) sufficiency proof<br> 792 6 Peters & Reif, <em>Subdivision Surfaces</em>, Springer 2008 — the monograph 793 </div> 794 </div> 795 796 </div> 797 798 <script src="https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.16.9/katex.min.js"></script> 799 <script src="https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.16.9/contrib/auto-render.min.js"></script> 800 <script> 801 const C={ground:'#0d1216',chalk:'#e8e6df',dim:'#9aa5ad',cage:'#6b7c8c', 802 face:'#f2b04a',edge:'#4fd6c4',vert:'#e86a92'}; 803 const REDUCED=matchMedia('(prefers-reduced-motion: reduce)').matches; 804 805 function setup(cv,ar){ 806 cv._ar=ar; const ctx=cv.getContext('2d'); 807 function fit(){ 808 const r=cv.getBoundingClientRect(), dpr=Math.min(devicePixelRatio||1,2); 809 const w=Math.max(1,r.width), h=w*ar; 810 cv.width=Math.round(w*dpr); cv.height=Math.round(h*dpr); 811 cv.style.height=h+'px'; ctx.setTransform(dpr,0,0,dpr,0,0); 812 return {w,h}; 813 } 814 return {ctx,fit}; 815 } 816 function seg(id,cb){ 817 const el=document.getElementById(id); 818 el.addEventListener('click',e=>{ 819 const b=e.target.closest('button'); if(!b)return; 820 [...el.querySelectorAll('button')].forEach(x=>x.setAttribute('aria-pressed',x===b)); 821 cb(b.dataset); 822 }); 823 } 824 function slider(id,vid,cb){ 825 const s=document.getElementById(id), v=document.getElementById(vid); 826 s.addEventListener('input',()=>{v.textContent=s.value; cb(+s.value);}); 827 } 828 const V={ 829 add:(a,b)=>[a[0]+b[0],a[1]+b[1],(a[2]||0)+(b[2]||0)], 830 sub:(a,b)=>[a[0]-b[0],a[1]-b[1],(a[2]||0)-(b[2]||0)], 831 mul:(a,s)=>[a[0]*s,a[1]*s,(a[2]||0)*s], 832 cross:(a,b)=>[a[1]*b[2]-a[2]*b[1],a[2]*b[0]-a[0]*b[2],a[0]*b[1]-a[1]*b[0]], 833 dot:(a,b)=>a[0]*b[0]+a[1]*b[1]+a[2]*b[2], 834 len:a=>Math.hypot(a[0],a[1],a[2]||0), 835 norm:a=>{const l=V.len(a)||1;return [a[0]/l,a[1]/l,(a[2]||0)/l];}, 836 avg:ps=>V.mul(ps.reduce((a,p)=>V.add(a,p),[0,0,0]),1/ps.length) 837 }; 838 function edgeTable(faces){ 839 const m=new Map(); 840 faces.forEach((f,fi)=>{for(let i=0;i<f.length;i++){ 841 const a=f[i],b=f[(i+1)%f.length],lo=Math.min(a,b),hi=Math.max(a,b),k=lo+','+hi; 842 if(!m.has(k))m.set(k,{a:lo,b:hi,faces:[]}); 843 m.get(k).faces.push(fi);}}); 844 return m; 845 } 846 function valences(verts,faces){ 847 const val=new Array(verts.length).fill(0); 848 edgeTable(faces).forEach(e=>{val[e.a]++;val[e.b]++;}); 849 return val; 850 } 851 852 /* ---------- FIG 1 ---------- */ 853 (function(){ 854 const cv=document.getElementById('f1'),{ctx,fit}=setup(cv,.49); 855 const out=document.getElementById('f1out'); 856 let scheme='chaikin',lvl=2,limit=true,drag=-1,W=900,H=440; 857 let P=[[.10,.72],[.22,.20],[.44,.80],[.60,.22],[.78,.70],[.92,.32]]; 858 function refine(p){ 859 const n=p.length,o=[]; 860 if(scheme==='chaikin'){ 861 for(let i=0;i<n-1;i++){const a=p[i],b=p[i+1]; 862 o.push([.75*a[0]+.25*b[0],.75*a[1]+.25*b[1]]); 863 o.push([.25*a[0]+.75*b[0],.25*a[1]+.75*b[1]]);} 864 }else{ 865 o.push(p[0]); 866 for(let i=0;i<n-1;i++){const a=p[i],b=p[i+1]; 867 o.push([(a[0]+b[0])/2,(a[1]+b[1])/2]); 868 if(i<n-2){const c=p[i+2]; 869 o.push([(a[0]+6*b[0]+c[0])/8,(a[1]+6*b[1]+c[1])/8]);}} 870 o.push(p[n-1]); 871 } 872 return o; 873 } 874 const chain=k=>{let p=P;for(let i=0;i<k;i++)p=refine(p);return p;}; 875 const X=p=>p[0]*W,Y=p=>p[1]*H; 876 function poly(pts,col,lw,dash){ 877 ctx.save();ctx.strokeStyle=col;ctx.lineWidth=lw;ctx.setLineDash(dash||[]); 878 ctx.lineJoin='round';ctx.beginPath(); 879 pts.forEach((p,i)=>i?ctx.lineTo(X(p),Y(p)):ctx.moveTo(X(p),Y(p))); 880 ctx.stroke();ctx.restore(); 881 } 882 function draw(){ 883 const d=fit();W=d.w;H=d.h;ctx.clearRect(0,0,W,H); 884 ctx.strokeStyle='rgba(107,124,140,.08)';ctx.lineWidth=1; 885 for(let i=1;i<10;i++){ctx.beginPath();ctx.moveTo(W*i/10,0);ctx.lineTo(W*i/10,H);ctx.stroke();} 886 for(let i=1;i<5;i++){ctx.beginPath();ctx.moveTo(0,H*i/5);ctx.lineTo(W,H*i/5);ctx.stroke();} 887 if(limit)poly(chain(7),'rgba(232,230,223,.28)',3.4); 888 poly(P,C.cage,1.4,[4,4]); 889 const cur=chain(lvl),col=scheme==='chaikin'?C.edge:C.vert; 890 poly(cur,col,2.2); 891 if(lvl<=4){ctx.fillStyle=col;cur.forEach(p=>{ctx.beginPath();ctx.arc(X(p),Y(p),2.7,0,7);ctx.fill();});} 892 P.forEach((p,i)=>{ctx.beginPath();ctx.arc(X(p),Y(p),i===drag?8:6.4,0,7); 893 ctx.fillStyle=C.chalk;ctx.fill();ctx.lineWidth=2;ctx.strokeStyle=C.ground;ctx.stroke();}); 894 out.innerHTML='mask <b>'+(scheme==='chaikin'?'¼[1,3,3,1]':'⅛[1,4,6,4,1]')+'</b> · ' 895 +(scheme==='chaikin'?'dual — old vertices discarded':'primal — old vertices retained') 896 +' · level <b>'+lvl+'</b>: '+P.length+' → <b>'+cur.length+'</b> points · limit is the uniform <b>' 897 +(scheme==='chaikin'?'quadratic':'cubic')+'</b> B-spline, <b>C' 898 +(scheme==='chaikin'?'¹':'²')+'</b>'; 899 } 900 const pos=e=>{const r=cv.getBoundingClientRect(); 901 return [(e.clientX-r.left)/r.width,(e.clientY-r.top)/(r.width*.49)];}; 902 cv.addEventListener('pointerdown',e=>{const m=pos(e);let b=-1,bd=9; 903 P.forEach((p,i)=>{const d=Math.hypot(p[0]-m[0],(p[1]-m[1])*.5);if(d<bd){bd=d;b=i;}}); 904 if(bd<.05){drag=b;cv.setPointerCapture(e.pointerId);draw();}}); 905 cv.addEventListener('pointermove',e=>{if(drag<0)return;const m=pos(e); 906 P[drag]=[Math.max(.03,Math.min(.97,m[0])),Math.max(.05,Math.min(.95,m[1]))];draw();}); 907 cv.addEventListener('pointerup',()=>{drag=-1;draw();}); 908 seg('f1scheme',d=>{scheme=d.s;draw();}); 909 slider('f1lvl','f1lvlv',v=>{lvl=v;draw();}); 910 document.getElementById('f1limit').onchange=e=>{limit=e.target.checked;draw();}; 911 new ResizeObserver(draw).observe(cv);draw(); 912 })(); 913 914 /* ---------- 3D engine ---------- */ 915 function make3D(id,ar){ 916 const cv=document.getElementById(id),{ctx,fit}=setup(cv,ar); 917 let yaw=.6,pitch=-.42,dn=false,lx=0,ly=0,spin=!REDUCED,W=900,H=400,model=null,o={}; 918 function rot(p){let[x,y,z]=p; 919 let c=Math.cos(yaw),s=Math.sin(yaw);[x,z]=[x*c-z*s,x*s+z*c]; 920 c=Math.cos(pitch);s=Math.sin(pitch);[y,z]=[y*c-z*s,y*s+z*c];return[x,y,z];} 921 function pj(p,sc,cx,cy){const d=4.4,k=d*sc/(d-p[2]);return[cx+p[0]*k,cy-p[1]*k,p[2]];} 922 function render(){ 923 const d=fit();W=d.w;H=d.h;ctx.clearRect(0,0,W,H);if(!model)return; 924 const cx=W/2,cy=H/2,sc=Math.min(W,H)*.40; 925 const RV=model.verts.map(rot),PV=RV.map(p=>pj(p,sc,cx,cy)); 926 const L=V.norm([.4,.75,1]),tint=o.tint||[112,158,172]; 927 model.faces.map((f,fi)=>({f,z:f.reduce((a,i)=>a+RV[i][2],0)/f.length})) 928 .sort((a,b)=>a.z-b.z).forEach(t=>{ 929 const f=t.f,a=RV[f[0]],b=RV[f[1]],c=RV[f[2]]; 930 const nr=V.norm(V.cross(V.sub(b,a),V.sub(c,a))); 931 if(nr[2]<-.02)return; 932 const sh=.11+.66*Math.pow(Math.max(0,V.dot(nr,L)),.85); 933 ctx.beginPath(); 934 f.forEach((i,k)=>{const p=PV[i];k?ctx.lineTo(p[0],p[1]):ctx.moveTo(p[0],p[1]);}); 935 ctx.closePath(); 936 ctx.fillStyle='rgb('+Math.round(tint[0]*sh)+','+Math.round(tint[1]*sh)+','+Math.round(tint[2]*sh)+')'; 937 ctx.fill();ctx.strokeStyle='rgba(232,230,223,.13)';ctx.lineWidth=.8;ctx.stroke();}); 938 if(o.cage){ 939 const cg=o.cage.verts.map(p=>pj(rot(p),sc,cx,cy)); 940 ctx.save();ctx.strokeStyle='rgba(107,124,140,.6)';ctx.lineWidth=1.1;ctx.setLineDash([3,3]); 941 o.cage.faces.forEach(f=>{ctx.beginPath(); 942 f.forEach((i,k)=>{const p=cg[i];k?ctx.lineTo(p[0],p[1]):ctx.moveTo(p[0],p[1]);}); 943 ctx.closePath();ctx.stroke();}); 944 ctx.restore(); 945 } 946 if(o.marks)o.marks.forEach(m=>{const p=PV[m.i]; 947 if(!p||RV[m.i][2]<-.55)return; 948 ctx.beginPath();ctx.arc(p[0],p[1],m.r||4.2,0,7);ctx.fillStyle=m.c;ctx.fill();}); 949 } 950 cv.addEventListener('pointerdown',e=>{dn=true;spin=false;lx=e.clientX;ly=e.clientY; 951 cv.setPointerCapture(e.pointerId);}); 952 cv.addEventListener('pointermove',e=>{if(!dn)return; 953 yaw+=(e.clientX-lx)*.008;pitch+=(e.clientY-ly)*.008; 954 pitch=Math.max(-1.35,Math.min(1.35,pitch));lx=e.clientX;ly=e.clientY;render();}); 955 cv.addEventListener('pointerup',()=>{dn=false;}); 956 new ResizeObserver(render).observe(cv); 957 if(!REDUCED)(function l(){if(spin){yaw+=.0032;render();}requestAnimationFrame(l);})(); 958 return {set:(m,op)=>{model=m;o=op||{};render();}}; 959 } 960 961 /* ---------- base meshes ---------- */ 962 const cubeMesh=()=>({verts:[[-1,-1,-1],[1,-1,-1],[1,1,-1],[-1,1,-1],[-1,-1,1],[1,-1,1],[1,1,1],[-1,1,1]] 963 .map(p=>V.mul(p,.72)),faces:[[0,3,2,1],[4,5,6,7],[0,1,5,4],[2,3,7,6],[1,2,6,5],[0,4,7,3]]}); 964 function lshapeMesh(){ 965 const s=.52,v=[[0,0,0],[2,0,0],[2,1,0],[1,1,0],[1,2,0],[0,2,0], 966 [0,0,1],[2,0,1],[2,1,1],[1,1,1],[1,2,1],[0,2,1]] 967 .map(p=>V.mul([p[0]-1,p[1]-1,p[2]-.5],s)); 968 return {verts:v,faces:[[0,5,4,3],[3,2,1,0],[6,7,8,9],[9,10,11,6], 969 [0,1,7,6],[1,2,8,7],[2,3,9,8],[3,4,10,9],[4,5,11,10],[5,0,6,11]]}; 970 } 971 function pentPrism(){ 972 const v=[],f=[],n=5,r=.72,h=.6; 973 for(let i=0;i<n;i++){const a=i/n*Math.PI*2; 974 v.push([r*Math.cos(a),-h,r*Math.sin(a)]);v.push([r*Math.cos(a),h,r*Math.sin(a)]);} 975 const bot=[],top=[]; 976 for(let i=0;i<n;i++){bot.push(2*i);top.push(2*(n-1-i)+1);} 977 f.push(bot.slice().reverse());f.push(top.slice().reverse()); 978 for(let i=0;i<n;i++){const j=(i+1)%n;f.push([2*i,2*j,2*j+1,2*i+1]);} 979 return {verts:v,faces:f}; 980 } 981 const tetraMesh=()=>({verts:[[1,1,1],[-1,-1,1],[-1,1,-1],[1,-1,-1]].map(p=>V.mul(V.norm(p),.92)), 982 faces:[[0,1,2],[0,3,1],[0,2,3],[1,3,2]]}); 983 const octaMesh=()=>({verts:[[1,0,0],[-1,0,0],[0,1,0],[0,-1,0],[0,0,1],[0,0,-1]].map(p=>V.mul(p,.88)), 984 faces:[[0,2,4],[2,1,4],[1,3,4],[3,0,4],[2,0,5],[1,2,5],[3,1,5],[0,3,5]]}); 985 function icosaMesh(r){ 986 r=r||.86;const t=(1+Math.sqrt(5))/2,v=[]; 987 [[-1,t,0],[1,t,0],[-1,-t,0],[1,-t,0],[0,-1,t],[0,1,t],[0,-1,-t],[0,1,-t], 988 [t,0,-1],[t,0,1],[-t,0,-1],[-t,0,1]].forEach(p=>v.push(V.mul(V.norm(p),r))); 989 return {verts:v,faces:[[0,11,5],[0,5,1],[0,1,7],[0,7,10],[0,10,11],[1,5,9],[5,11,4], 990 [11,10,2],[10,7,6],[7,1,8],[3,9,4],[3,4,2],[3,2,6],[3,6,8],[3,8,9], 991 [4,9,5],[2,4,11],[6,2,10],[8,6,7],[9,8,1]]}; 992 } 993 function torusMesh(){ 994 const R=.66,r=.27,nu=12,nv=8,v=[],f=[]; 995 for(let i=0;i<nu;i++)for(let j=0;j<nv;j++){ 996 const a=i/nu*Math.PI*2,b=j/nv*Math.PI*2; 997 v.push([(R+r*Math.cos(b))*Math.cos(a),r*Math.sin(b),(R+r*Math.cos(b))*Math.sin(a)]);} 998 const id=(i,j)=>(((i%nu)+nu)%nu)*nv+(((j%nv)+nv)%nv); 999 for(let i=0;i<nu;i++)for(let j=0;j<nv;j++) 1000 f.push([id(i,j),id(i+1,j),id(i+1,j+1),id(i,j+1)]); 1001 return {verts:v,faces:f}; 1002 } 1003 1004 /* ---------- Catmull–Clark ---------- */ 1005 function catmullClark(mesh){ 1006 const {verts,faces}=mesh; 1007 const fp=faces.map(f=>V.avg(f.map(i=>verts[i]))); 1008 const et=edgeTable(faces),keys=[...et.keys()]; 1009 const eI=new Map(keys.map((k,i)=>[k,i])); 1010 const ep=keys.map(k=>{const e=et.get(k); 1011 return e.faces.length===2 1012 ? V.mul(V.add(V.add(verts[e.a],verts[e.b]),V.add(fp[e.faces[0]],fp[e.faces[1]])),.25) 1013 : V.mul(V.add(verts[e.a],verts[e.b]),.5);}); 1014 const vf=verts.map(()=>[]),ve=verts.map(()=>[]); 1015 faces.forEach((f,fi)=>f.forEach(i=>vf[i].push(fi))); 1016 keys.forEach((k,i)=>{const e=et.get(k);ve[e.a].push(i);ve[e.b].push(i);}); 1017 const nv=verts.map((v,i)=>{ 1018 const n=ve[i].length;if(!n||!vf[i].length)return v; 1019 const F=V.avg(vf[i].map(fi=>fp[fi])); 1020 const R=V.avg(ve[i].map(ei=>{const e=et.get(keys[ei]); 1021 return V.mul(V.add(verts[e.a],verts[e.b]),.5);})); 1022 return V.add(V.add(V.mul(F,1/n),V.mul(R,2/n)),V.mul(v,(n-3)/n));}); 1023 const oF=verts.length,oE=verts.length+faces.length; 1024 const outV=[...nv,...fp,...ep],outF=[]; 1025 faces.forEach((f,fi)=>{const m=f.length; 1026 for(let i=0;i<m;i++){ 1027 const vi=f[i],pv=f[(i-1+m)%m],nx=f[(i+1)%m]; 1028 const e1=eI.get(Math.min(vi,nx)+','+Math.max(vi,nx)); 1029 const e0=eI.get(Math.min(pv,vi)+','+Math.max(pv,vi)); 1030 outF.push([vi,oE+e1,oF+fi,oE+e0]);}}); 1031 return {verts:outV,faces:outF}; 1032 } 1033 1034 /* ---------- Loop ---------- */ 1035 function loopSub(mesh){ 1036 const {verts,faces}=mesh; 1037 const et=edgeTable(faces),keys=[...et.keys()]; 1038 const eI=new Map(keys.map((k,i)=>[k,i])); 1039 const opp=keys.map(()=>[]); 1040 faces.forEach(f=>{for(let i=0;i<3;i++){ 1041 const a=f[i],b=f[(i+1)%3],c=f[(i+2)%3]; 1042 opp[eI.get(Math.min(a,b)+','+Math.max(a,b))].push(c);}}); 1043 const ep=keys.map((k,i)=>{const e=et.get(k),o=opp[i]; 1044 return o.length===2 1045 ? V.add(V.mul(V.add(verts[e.a],verts[e.b]),3/8),V.mul(V.add(verts[o[0]],verts[o[1]]),1/8)) 1046 : V.mul(V.add(verts[e.a],verts[e.b]),.5);}); 1047 const ring=verts.map(()=>new Set()); 1048 et.forEach(e=>{ring[e.a].add(e.b);ring[e.b].add(e.a);}); 1049 const nv=verts.map((v,i)=>{ 1050 const nb=[...ring[i]],n=nb.length;if(!n)return v; 1051 const c=Math.cos(2*Math.PI/n); 1052 const beta=(5/8-Math.pow(3/8+c/4,2))/n; 1053 const s=nb.reduce((a,j)=>V.add(a,verts[j]),[0,0,0]); 1054 return V.add(V.mul(v,1-n*beta),V.mul(s,beta));}); 1055 const oE=verts.length,outV=[...nv,...ep],outF=[]; 1056 faces.forEach(f=>{const[a,b,c]=f; 1057 const ab=oE+eI.get(Math.min(a,b)+','+Math.max(a,b)); 1058 const bc=oE+eI.get(Math.min(b,c)+','+Math.max(b,c)); 1059 const ca=oE+eI.get(Math.min(c,a)+','+Math.max(c,a)); 1060 outF.push([a,ab,ca],[b,bc,ab],[c,ca,bc],[ab,bc,ca]);}); 1061 return {verts:outV,faces:outF}; 1062 } 1063 function splitProject(mesh,r){ 1064 const {verts,faces}=mesh; 1065 const et=edgeTable(faces),keys=[...et.keys()]; 1066 const eI=new Map(keys.map((k,i)=>[k,i])); 1067 const ep=keys.map(k=>{const e=et.get(k); 1068 return V.mul(V.norm(V.mul(V.add(verts[e.a],verts[e.b]),.5)),r);}); 1069 const oE=verts.length,outV=[...verts,...ep],outF=[]; 1070 faces.forEach(f=>{const[a,b,c]=f; 1071 const ab=oE+eI.get(Math.min(a,b)+','+Math.max(a,b)); 1072 const bc=oE+eI.get(Math.min(b,c)+','+Math.max(b,c)); 1073 const ca=oE+eI.get(Math.min(c,a)+','+Math.max(c,a)); 1074 outF.push([a,ab,ca],[b,bc,ab],[c,ca,bc],[ab,bc,ca]);}); 1075 return {verts:outV,faces:outF}; 1076 } 1077 1078 /* ---------- FIG 2 ---------- */ 1079 (function(){ 1080 const R=make3D('f2',.44),out=document.getElementById('f2out'); 1081 const build={cube:cubeMesh,torus:torusMesh,lshape:lshapeMesh}; 1082 let shape='cube'; 1083 function go(){ 1084 const m=build[shape](),val=valences(m.verts,m.faces); 1085 const marks=val.map((n,i)=>({i,c:n===4?C.cage:C.vert,r:n===4?3.4:5.2})); 1086 const ev=val.filter(n=>n!==4).length; 1087 const E=[...edgeTable(m.faces).keys()].length; 1088 const chi=m.verts.length-E+m.faces.length; 1089 R.set(m,{marks,tint:[104,150,164]}); 1090 out.innerHTML='V=<b>'+m.verts.length+'</b> E=<b>'+E+'</b> F=<b>'+m.faces.length 1091 +'</b> · χ = V−E+F = <b>'+chi+'</b> → genus <b>'+(2-chi)/2 1092 +'</b> · extraordinary vertices: <b style="color:'+(ev?C.vert:C.edge)+'">'+ev+'</b>' 1093 +(ev===0?' — only the torus gets away with this':''); 1094 } 1095 seg('f2shape',d=>{shape=d.s;go();});go(); 1096 })(); 1097 1098 /* ---------- FIG 3 ---------- */ 1099 (function(){ 1100 const cv=document.getElementById('f3'),{ctx,fit}=setup(cv,.333); 1101 const out=document.getElementById('f3out');let p=3,W=900,H=300; 1102 function N(i,k,x){ 1103 if(k===0)return (x>=i&&x<i+1)?1:0; 1104 return (x-i)/k*N(i,k-1,x)+(i+k+1-x)/k*N(i+1,k-1,x); 1105 } 1106 const bs=(d,t)=>N(0,d,t); 1107 function binom(n,k){let r=1;for(let i=0;i<k;i++)r=r*(n-i)/(i+1);return r;} 1108 function draw(){ 1109 const d=fit();W=d.w;H=d.h;ctx.clearRect(0,0,W,H); 1110 const mask=[];for(let k=0;k<=p+1;k++)mask.push(binom(p+1,k)/Math.pow(2,p)); 1111 const pad=30,lw=W*.55,lh=H-2*pad-14,x0=pad,y0=pad; 1112 const sup=p+1,span=sup*1.35; 1113 const px=t=>x0+t/span*lw, maxN=bs(p,sup/2)||1, py=v=>y0+lh-v/(maxN*1.14)*lh; 1114 ctx.strokeStyle='rgba(107,124,140,.25)';ctx.lineWidth=1; 1115 ctx.beginPath();ctx.moveTo(x0,y0+lh);ctx.lineTo(x0+lw,y0+lh);ctx.stroke(); 1116 mask.forEach((a,k)=>{ctx.beginPath();let st=true; 1117 for(let t=0;t<=span;t+=.01){const v=a*bs(p,2*t-k); 1118 if(v<=0&&st)continue;const Xc=px(t),Yc=py(v); 1119 st?(ctx.moveTo(Xc,Yc),st=false):ctx.lineTo(Xc,Yc);} 1120 ctx.strokeStyle=k%2===0?'rgba(232,106,146,.6)':'rgba(79,214,196,.6)'; 1121 ctx.lineWidth=1.4;ctx.stroke();}); 1122 ctx.beginPath(); 1123 for(let t=0;t<=span;t+=.006){const v=bs(p,t); 1124 t===0?ctx.moveTo(px(t),py(v)):ctx.lineTo(px(t),py(v));} 1125 ctx.strokeStyle=C.chalk;ctx.lineWidth=2.5;ctx.stroke(); 1126 ctx.font='500 11px "IBM Plex Mono",monospace'; 1127 ctx.fillStyle=C.chalk;ctx.fillText('N'+p+' = Σ of the copies below',x0+6,y0+12); 1128 ctx.fillStyle='rgba(232,106,146,.95)';ctx.fillText('even k',x0+6,y0+29); 1129 ctx.fillStyle='rgba(79,214,196,.95)';ctx.fillText('odd k',x0+62,y0+29); 1130 const rx=W*.63,rw=W-rx-pad,mx=Math.max(...mask); 1131 const bw=Math.min(28,rw/(mask.length+.8)); 1132 mask.forEach((a,k)=>{ 1133 const h=a/mx*(lh-24),Xc=rx+k*(bw+4),Yc=y0+lh-h; 1134 ctx.fillStyle=k%2===0?'rgba(232,106,146,.8)':'rgba(79,214,196,.8)'; 1135 ctx.fillRect(Xc,Yc,bw,h); 1136 ctx.fillStyle=C.dim;ctx.font='500 9px "IBM Plex Mono",monospace'; 1137 ctx.fillText(Math.round(a*Math.pow(2,p)),Xc+bw/2-3,Yc-5); 1138 ctx.fillText('a'+k,Xc+bw/2-6,y0+lh+13);}); 1139 ctx.strokeStyle='rgba(107,124,140,.25)'; 1140 ctx.beginPath();ctx.moveTo(rx-4,y0+lh);ctx.lineTo(rx+rw,y0+lh);ctx.stroke(); 1141 const ev=mask.filter((_,k)=>k%2===0).reduce((a,b)=>a+b,0); 1142 const od=mask.filter((_,k)=>k%2===1).reduce((a,b)=>a+b,0); 1143 const fr=mask.map(a=>Math.round(a*Math.pow(2,p))); 1144 out.innerHTML='a(z) = (1+z)<sup>'+(p+1)+'</sup>/2<sup>'+p+'</sup> · mask <b>1/' 1145 +Math.pow(2,p)+'·['+fr.join(',')+']</b> · Σeven = <b>'+ev.toFixed(3) 1146 +'</b>, Σodd = <b>'+od.toFixed(3)+'</b> (both must be 1) · limit <b>C' 1147 +(p-1)+'</b>'+(p===2?' ← Chaikin':p===3?' ← split & smooth → Catmull–Clark':''); 1148 } 1149 slider('f3p','f3pv',v=>{p=v;draw();}); 1150 new ResizeObserver(draw).observe(cv);draw(); 1151 })(); 1152 1153 /* ---------- FIG 4 ---------- */ 1154 (function(){ 1155 const cv=document.getElementById('f4'),{ctx,fit}=setup(cv,.60); 1156 const out=document.getElementById('f4out'); 1157 let pass=0,W=900,H=540,drag=-1,hov=null; 1158 function baseCage(){ 1159 const cx=.5,cy=.5,R=.135,verts=[[cx,cy]]; 1160 for(let i=0;i<5;i++){const a=-Math.PI/2+i*2*Math.PI/5; 1161 verts.push([cx+R*1.45*Math.cos(a),cy+R*Math.sin(a)]);} 1162 for(let i=0;i<5;i++){const a=-Math.PI/2+(i+.5)*2*Math.PI/5; 1163 verts.push([cx+R*2.5*1.45*Math.cos(a),cy+R*2.5*Math.sin(a)]);} 1164 const faces=[]; 1165 for(let i=0;i<5;i++){const j=(i+1)%5;faces.push([0,1+i,6+i,1+j]);} 1166 return {verts,faces}; 1167 } 1168 let cage=baseCage(); 1169 function compute(){ 1170 const {verts,faces}=cage; 1171 const fp=faces.map(f=>{const s=f.reduce((a,i)=>[a[0]+verts[i][0],a[1]+verts[i][1]],[0,0]); 1172 return [s[0]/f.length,s[1]/f.length];}); 1173 const et=edgeTable(faces),keys=[...et.keys()]; 1174 const ep=keys.map(k=>{const e=et.get(k); 1175 if(e.faces.length===2)return [(verts[e.a][0]+verts[e.b][0]+fp[e.faces[0]][0]+fp[e.faces[1]][0])/4, 1176 (verts[e.a][1]+verts[e.b][1]+fp[e.faces[0]][1]+fp[e.faces[1]][1])/4]; 1177 return [(verts[e.a][0]+verts[e.b][0])/2,(verts[e.a][1]+verts[e.b][1])/2];}); 1178 const vf=verts.map(()=>[]),ve=verts.map(()=>[]); 1179 faces.forEach((f,fi)=>f.forEach(i=>vf[i].push(fi))); 1180 keys.forEach((k,i)=>{const e=et.get(k);ve[e.a].push(i);ve[e.b].push(i);}); 1181 const vp=verts.map((v,i)=>{ 1182 const n=ve[i].length;if(!n||!vf[i].length)return v.slice(); 1183 const F=vf[i].reduce((a,fi)=>[a[0]+fp[fi][0],a[1]+fp[fi][1]],[0,0]).map(x=>x/vf[i].length); 1184 const Rr=ve[i].reduce((a,ei)=>{const e=et.get(keys[ei]); 1185 return [a[0]+(verts[e.a][0]+verts[e.b][0])/2,a[1]+(verts[e.a][1]+verts[e.b][1])/2];},[0,0]) 1186 .map(x=>x/ve[i].length); 1187 return [(F[0]+2*Rr[0]+(n-3)*v[0])/n,(F[1]+2*Rr[1]+(n-3)*v[1])/n];}); 1188 return {fp,ep,vp,keys,et,vf,ve}; 1189 } 1190 const X=p=>p[0]*W,Y=p=>p[1]*H; 1191 function draw(){ 1192 const d=fit();W=d.w;H=d.h;ctx.clearRect(0,0,W,H); 1193 const {fp,ep,vp,keys,et,vf,ve}=compute(),{verts,faces}=cage; 1194 ctx.strokeStyle='rgba(107,124,140,.5)';ctx.lineWidth=1.3; 1195 et.forEach(e=>{ctx.beginPath();ctx.moveTo(X(verts[e.a]),Y(verts[e.a])); 1196 ctx.lineTo(X(verts[e.b]),Y(verts[e.b]));ctx.stroke();}); 1197 if(pass>=4){ 1198 faces.forEach((f,fi)=>{const m=f.length; 1199 for(let i=0;i<m;i++){ 1200 const vi=f[i],pv=f[(i-1+m)%m],nx=f[(i+1)%m]; 1201 const e1=keys.indexOf(Math.min(vi,nx)+','+Math.max(vi,nx)); 1202 const e0=keys.indexOf(Math.min(pv,vi)+','+Math.max(pv,vi)); 1203 const q=[vp[vi],ep[e1],fp[fi],ep[e0]]; 1204 ctx.beginPath();q.forEach((p,k)=>k?ctx.lineTo(X(p),Y(p)):ctx.moveTo(X(p),Y(p))); 1205 ctx.closePath();ctx.fillStyle='rgba(232,230,223,.05)';ctx.fill(); 1206 ctx.strokeStyle='rgba(232,230,223,.45)';ctx.lineWidth=1.1;ctx.stroke();}}); 1207 } 1208 if(hov){ 1209 let cs=[],tgt,col; 1210 if(hov.t==='f'){col=C.face;tgt=fp[hov.i]; 1211 cs=faces[hov.i].map(i=>({p:verts[i],w:'1/'+faces[hov.i].length}));} 1212 if(hov.t==='e'){col=C.edge;tgt=ep[hov.i];const e=et.get(keys[hov.i]); 1213 cs=[{p:verts[e.a],w:'¼'},{p:verts[e.b],w:'¼'}]; 1214 e.faces.forEach(fi=>cs.push({p:fp[fi],w:'¼'}));} 1215 if(hov.t==='v'){col=C.vert;tgt=vp[hov.i]; 1216 cs=[{p:verts[hov.i],w:'(n−2)/n'}]; 1217 vf[hov.i].forEach(fi=>cs.push({p:fp[fi],w:'1/n²'})); 1218 ve[hov.i].forEach(ei=>{const e=et.get(keys[ei]); 1219 cs.push({p:verts[e.a===hov.i?e.b:e.a],w:'1/n²'});});} 1220 ctx.save();ctx.font='600 10px "IBM Plex Mono",monospace'; 1221 cs.forEach(c=>{ 1222 ctx.globalAlpha=.45;ctx.strokeStyle=col;ctx.lineWidth=1.4;ctx.setLineDash([3,3]); 1223 ctx.beginPath();ctx.moveTo(X(c.p),Y(c.p));ctx.lineTo(X(tgt),Y(tgt));ctx.stroke(); 1224 ctx.setLineDash([]);ctx.globalAlpha=1; 1225 ctx.beginPath();ctx.arc(X(c.p),Y(c.p),9,0,7);ctx.lineWidth=2;ctx.stroke(); 1226 ctx.fillStyle=col;ctx.fillText(c.w,X(c.p)+12,Y(c.p)-9);}); 1227 ctx.restore(); 1228 } 1229 const dot=(p,c,r)=>{ctx.beginPath();ctx.arc(X(p),Y(p),r,0,7);ctx.fillStyle=c;ctx.fill();}; 1230 if(pass>=1)fp.forEach((p,i)=>dot(p,C.face,hov&&hov.t==='f'&&hov.i===i?7:4.8)); 1231 if(pass>=2)ep.forEach((p,i)=>dot(p,C.edge,hov&&hov.t==='e'&&hov.i===i?7:4.3)); 1232 if(pass>=3)vp.forEach((p,i)=>{if(vf[i].length)dot(p,C.vert,hov&&hov.t==='v'&&hov.i===i?7:4.8);}); 1233 verts.forEach((p,i)=>{ctx.beginPath();ctx.arc(X(p),Y(p),i===drag?6.6:5.2,0,7); 1234 ctx.fillStyle='rgba(232,230,223,.92)';ctx.fill(); 1235 ctx.lineWidth=1.6;ctx.strokeStyle=C.ground;ctx.stroke();}); 1236 if(!hov){ 1237 const L=['cage only — 11 points, 5 quads, one valence-5 centre', 1238 'face points: <b style="color:'+C.face+'">f = (1/m)·Σvᵢ</b> — one per face', 1239 'edge points: <b style="color:'+C.edge+'">e = ¼(v₁+v₂+f₁+f₂)</b> — needs pass 1, so this is pass 2', 1240 'vertex points: <b style="color:'+C.vert+'">v′ = (Q+2R+(n−3)v)/n</b> — needs both, so pass 3', 1241 'reconnect: each quad is <b style="color:'+C.vert+'">v′</b> → <b style="color:'+C.edge+'">e</b> → <b style="color:'+C.face+'">f</b> → <b style="color:'+C.edge+'">e</b>']; 1242 out.innerHTML=L[pass]+(pass>0?' · hover or tap a coloured point for its stencil':''); 1243 } 1244 } 1245 const pos=e=>{const r=cv.getBoundingClientRect(); 1246 return [(e.clientX-r.left)/r.width,(e.clientY-r.top)/(r.width*.60)];}; 1247 function pick(m){ 1248 const {fp,ep,vp,vf}=compute(),c=[]; 1249 if(pass>=1)fp.forEach((p,i)=>c.push({t:'f',i,p})); 1250 if(pass>=2)ep.forEach((p,i)=>c.push({t:'e',i,p})); 1251 if(pass>=3)vp.forEach((p,i)=>{if(vf[i].length)c.push({t:'v',i,p});}); 1252 let b=null,bd=9; 1253 c.forEach(x=>{const d=Math.hypot(x.p[0]-m[0],(x.p[1]-m[1])*.6);if(d<bd){bd=d;b=x;}}); 1254 return bd<.024?b:null; 1255 } 1256 function mask(h){ 1257 const {ve,et,keys}=compute(); 1258 if(h.t==='f'){const m=cage.faces[h.i].length; 1259 out.innerHTML='<b style="color:'+C.face+'">face point</b> of a '+m+'-gon · f = (1/'+m 1260 +')·Σvᵢ · new valence <b>'+m+'</b>' 1261 +(m!==4?' → <b style="color:'+C.vert+'">becomes an EV</b>':' → regular');} 1262 if(h.t==='e'){const e=et.get(keys[h.i]); 1263 out.innerHTML='<b style="color:'+C.edge+'">edge point</b> · ' 1264 +(e.faces.length<2?'boundary → ½(v₁+v₂)':'e = ¼(v₁ + v₂ + f₁ + f₂)') 1265 +' · new valence <b>4 always</b> → never an EV';} 1266 if(h.t==='v'){const n=ve[h.i].length; 1267 out.innerHTML='<b style="color:'+C.vert+'">vertex point</b>, n = <b>'+n 1268 +'</b> · v′ = (n−2)/n·v + (1/n²)Σeᵢ + (1/n²)Σfᵢ · centre weight <b>' 1269 +((n-2)/n).toFixed(3)+'</b> · valence <b>preserved</b>' 1270 +(n!==4?' → <b style="color:'+C.vert+'">stays an EV forever</b>':'');} 1271 } 1272 cv.addEventListener('pointerdown',e=>{ 1273 const m=pos(e),h=pick(m); 1274 if(h){hov=h;drag=-1;mask(h);draw();return;} 1275 let b=-1,bd=9; 1276 cage.verts.forEach((p,i)=>{const d=Math.hypot(p[0]-m[0],(p[1]-m[1])*.6);if(d<bd){bd=d;b=i;}}); 1277 if(bd<.03){drag=b;hov=null;cv.setPointerCapture(e.pointerId);draw();}}); 1278 cv.addEventListener('pointermove',e=>{ 1279 const m=pos(e); 1280 if(drag>=0){cage.verts[drag]=[Math.max(.03,Math.min(.97,m[0])), 1281 Math.max(.04,Math.min(.96,m[1]))];draw();return;} 1282 if(e.pointerType==='mouse'){const h=pick(m); 1283 const ch=(h&&!hov)||(!h&&hov)||(h&&hov&&(h.t!==hov.t||h.i!==hov.i)); 1284 if(ch){hov=h;if(h)mask(h);draw();}}}); 1285 cv.addEventListener('pointerup',()=>{drag=-1;}); 1286 cv.addEventListener('pointerleave',()=>{if(hov){hov=null;draw();}}); 1287 seg('f4pass',d=>{pass=+d.p;hov=null;draw();}); 1288 document.getElementById('f4reset').onclick=()=>{cage=baseCage();hov=null;draw();}; 1289 new ResizeObserver(draw).observe(cv);draw(); 1290 })(); 1291 1292 /* ---------- FIG 5 ---------- */ 1293 (function(){ 1294 const R=make3D('f5',.522),out=document.getElementById('f5out'); 1295 const build={cube:cubeMesh,lshape:lshapeMesh,pent:pentPrism,tet:tetraMesh}; 1296 let shape='cube',lvl=0,mk=true,cg=false; 1297 function go(){ 1298 const base=build[shape]();let m=base; 1299 for(let i=0;i<lvl;i++)m=catmullClark(m); 1300 const val=valences(m.verts,m.faces); 1301 const ev=val.map((n,i)=>n!==4?i:-1).filter(i=>i>=0); 1302 R.set(m,{marks:mk?ev.map(i=>({i,c:C.vert,r:4.4})):null,cage:cg?base:null,tint:[112,158,172]}); 1303 const E=[...edgeTable(m.faces).keys()].length; 1304 out.innerHTML='level <b>'+lvl+'</b> · V=<b>'+m.verts.length+'</b> E=<b>'+E 1305 +'</b> F=<b>'+m.faces.length+'</b> · extraordinary vertices <b style="color:'+C.vert+'">' 1306 +ev.length+'</b>'+(lvl>=1?' — frozen from level 1 on':' — about to freeze') 1307 +' · all quads: <b>'+(m.faces.every(f=>f.length===4)?'yes':'no')+'</b>'; 1308 } 1309 seg('f5shape',d=>{shape=d.s;go();}); 1310 slider('f5lvl','f5lvlv',v=>{lvl=v;go();}); 1311 document.getElementById('f5ev').onchange=e=>{mk=e.target.checked;go();}; 1312 document.getElementById('f5cage').onchange=e=>{cg=e.target.checked;go();}; 1313 go(); 1314 })(); 1315 1316 /* ---------- FIG 6 ---------- */ 1317 (function(){ 1318 const R=make3D('f6',.50),out=document.getElementById('f6out'); 1319 const build={tet:tetraMesh,icosa:()=>icosaMesh(.86),octa:octaMesh}; 1320 let shape='tet',lvl=0,cg=true; 1321 function go(){ 1322 const base=build[shape]();let m=base; 1323 for(let i=0;i<lvl;i++)m=loopSub(m); 1324 const val=valences(m.verts,m.faces),ev=val.filter(n=>n!==6).length; 1325 const rB=Math.max(...base.verts.map(V.len)),rN=Math.max(...m.verts.map(V.len)); 1326 R.set(m,{cage:cg?base:null,tint:[150,140,175]}); 1327 out.innerHTML='level <b>'+lvl+'</b> · V=<b>'+m.verts.length+'</b> F=<b>'+m.faces.length 1328 +'</b> · irregular (n≠6) <b style="color:'+C.vert+'">'+ev+'</b> · max radius <b>' 1329 +rN.toFixed(3)+'</b> vs cage <b>'+rB.toFixed(3)+'</b> → shrunk to <b>' 1330 +(100*rN/rB).toFixed(1)+'%</b> (convex hull property)'; 1331 } 1332 seg('f6shape',d=>{shape=d.s;go();}); 1333 slider('f6lvl','f6lvlv',v=>{lvl=v;go();}); 1334 document.getElementById('f6cage').onchange=e=>{cg=e.target.checked;go();}; 1335 go(); 1336 })(); 1337 1338 /* ---------- FIG 7 ---------- */ 1339 (function(){ 1340 const cv=document.getElementById('f7'),{ctx,fit}=setup(cv,.366); 1341 const out=document.getElementById('f7out');let n=4,W=900,H=330; 1342 const lam=k=>{const c=Math.cos(2*Math.PI/k);return (c+5+Math.sqrt((c+9)*(c+1)))/16;}; 1343 function draw(){ 1344 const d=fit();W=d.w;H=d.h;ctx.clearRect(0,0,W,H); 1345 const pl=52,pr=22,pt=24,pb=38,gw=W-pl-pr,gh=H-pt-pb; 1346 const n0=3,n1=12,y0=.35,y1=.62; 1347 const px=k=>pl+(k-n0)/(n1-n0)*gw, py=v=>pt+gh-(v-y0)/(y1-y0)*gh; 1348 ctx.font='500 10px "IBM Plex Mono",monospace'; 1349 for(let v=.35;v<=.621;v+=.05){ 1350 ctx.strokeStyle='rgba(107,124,140,.13)';ctx.lineWidth=1; 1351 ctx.beginPath();ctx.moveTo(pl,py(v));ctx.lineTo(pl+gw,py(v));ctx.stroke(); 1352 ctx.fillStyle=C.dim;ctx.fillText(v.toFixed(2),12,py(v)+3);} 1353 ctx.strokeStyle='rgba(79,214,196,.55)';ctx.lineWidth=1.4;ctx.setLineDash([5,4]); 1354 ctx.beginPath();ctx.moveTo(pl,py(.5));ctx.lineTo(pl+gw,py(.5));ctx.stroke(); 1355 ctx.setLineDash([]);ctx.fillStyle=C.edge; 1356 ctx.fillText('λ = ½ regular, n = 4',pl+8,py(.5)-7); 1357 ctx.beginPath(); 1358 for(let k=n0;k<=n1;k+=.02){k===n0?ctx.moveTo(px(k),py(lam(k))):ctx.lineTo(px(k),py(lam(k)));} 1359 ctx.strokeStyle=C.chalk;ctx.lineWidth=2.2;ctx.stroke(); 1360 for(let k=n0;k<=n1;k++){ 1361 ctx.beginPath();ctx.arc(px(k),py(lam(k)),k===n?7:3.6,0,7); 1362 ctx.fillStyle=k===n?C.vert:(k===4?C.edge:'rgba(232,230,223,.55)');ctx.fill(); 1363 ctx.fillStyle=C.dim;ctx.fillText(k,px(k)-3,pt+gh+16);} 1364 ctx.fillText('valence n',pl+gw/2-22,pt+gh+31); 1365 const l=lam(n); 1366 out.innerHTML='n = <b>'+n+'</b> · λ = <b>'+l.toFixed(5)+'</b> · deviation from ½ <b style="color:' 1367 +(Math.abs(l-.5)<1e-9?C.edge:C.vert)+'">'+(l>=.5?'+':'')+(l-.5).toFixed(5) 1368 +'</b> · contraction per level ≈ <b>'+(l*100).toFixed(1)+'%</b>' 1369 +(n===4?' — exactly the bicubic rate':n===3?' — fastest contraction, flattest limit' 1370 :' — slower contraction, curvature degrades'); 1371 } 1372 slider('f7n','f7nv',v=>{n=v;draw();}); 1373 new ResizeObserver(draw).observe(cv);draw(); 1374 })(); 1375 1376 /* ---------- FIG 8 ---------- */ 1377 (function(){ 1378 const cv=document.getElementById('f8'),{ctx,fit}=setup(cv,.467); 1379 const out=document.getElementById('f8out'); 1380 let W=900,H=420,mode='face',k=0,timer=null; 1381 const P=[[.24,.22],[.50,.17],[.76,.24],[.20,.50],[.50,.50],[.80,.50], 1382 [.24,.80],[.50,.85],[.76,.78]]; 1383 const F=[[0,3,4,1],[1,4,5,2],[3,6,7,4],[4,7,8,5]]; 1384 const HE=[],hm=new Map(); 1385 F.forEach((f,fi)=>{const s=HE.length; 1386 f.forEach((v,i)=>{HE.push({o:v,d:f[(i+1)%f.length],face:fi,next:s+((i+1)%f.length),twin:-1}); 1387 hm.set(v+'>'+f[(i+1)%f.length],HE.length-1);});}); 1388 HE.forEach(h=>{const t=hm.get(h.d+'>'+h.o);h.twin=t===undefined?-1:t;}); 1389 const vOut=new Map();HE.forEach((h,i)=>{if(!vOut.has(h.o))vOut.set(h.o,i);}); 1390 const X=p=>p[0]*W,Y=p=>p[1]*H; 1391 const sFace=()=>{const s=0,o=[s];let h=HE[s].next;while(h!==s){o.push(h);h=HE[h].next;}return o;}; 1392 const sRing=()=>{const s=vOut.get(4),o=[s];let h=s; 1393 for(let i=0;i<10;i++){const t=HE[h].twin;if(t<0)break;h=HE[t].next;if(h===s)break;o.push(h);} 1394 return o;}; 1395 const sTwin=()=>{const o=[];HE.forEach((h,i)=>{if(h.twin>i)o.push(i);});return o;}; 1396 function arrow(a,b,col,lw){ 1397 const dx=b[0]-a[0],dy=b[1]-a[1],L=Math.hypot(dx,dy),ux=dx/L,uy=dy/L; 1398 const ox=-uy*.012,oy=ux*.012,s=.19; 1399 const A=[a[0]+ux*L*s+ox,a[1]+uy*L*s+oy],B=[b[0]-ux*L*s+ox,b[1]-uy*L*s+oy]; 1400 ctx.strokeStyle=col;ctx.lineWidth=lw;ctx.lineCap='round'; 1401 ctx.beginPath();ctx.moveTo(X(A),Y(A));ctx.lineTo(X(B),Y(B));ctx.stroke(); 1402 const hx=X(B),hy=Y(B),an=Math.atan2(Y(B)-Y(A),X(B)-X(A)),s2=8; 1403 ctx.beginPath();ctx.moveTo(hx,hy); 1404 ctx.lineTo(hx-s2*Math.cos(an-.42),hy-s2*Math.sin(an-.42)); 1405 ctx.lineTo(hx-s2*Math.cos(an+.42),hy-s2*Math.sin(an+.42)); 1406 ctx.closePath();ctx.fillStyle=col;ctx.fill(); 1407 } 1408 function draw(){ 1409 const d=fit();W=d.w;H=d.h;ctx.clearRect(0,0,W,H); 1410 F.forEach(f=>{ctx.beginPath(); 1411 f.forEach((i,j)=>{const p=P[i];j?ctx.lineTo(X(p),Y(p)):ctx.moveTo(X(p),Y(p));}); 1412 ctx.closePath();ctx.fillStyle='rgba(107,124,140,.07)';ctx.fill();}); 1413 const sq=mode==='face'?sFace():mode==='ring'?sRing():sTwin(); 1414 const cur=sq[k%sq.length]; 1415 const col=mode==='face'?C.face:mode==='ring'?C.vert:C.edge; 1416 HE.forEach(h=>arrow(P[h.o],P[h.d],'rgba(107,124,140,.32)',1.2)); 1417 sq.slice(0,(k%sq.length)+1).forEach(i=>arrow(P[HE[i].o],P[HE[i].d],col,2.4)); 1418 const h=HE[cur];arrow(P[h.o],P[h.d],'#fff',3.2); 1419 if(mode==='twin'&&h.twin>=0){const t=HE[h.twin];arrow(P[t.o],P[t.d],C.edge,3.2);} 1420 P.forEach((p,i)=>{const c=mode==='ring'&&i===4; 1421 ctx.beginPath();ctx.arc(X(p),Y(p),c?7:5.4,0,7); 1422 ctx.fillStyle=c?C.vert:'rgba(232,230,223,.9)';ctx.fill(); 1423 ctx.lineWidth=1.6;ctx.strokeStyle=C.ground;ctx.stroke(); 1424 ctx.font='500 10px "IBM Plex Mono",monospace';ctx.fillStyle=C.dim; 1425 ctx.fillText('v'+i,X(p)+9,Y(p)-8);}); 1426 out.innerHTML=(mode==='face' 1427 ?'<b>ν orbit</b> = face '+h.face+' · h = '+cur+', next = '+h.next 1428 :mode==='ring' 1429 ?'<b>ν∘α orbit</b> = 1-ring of v4 · h = '+cur+', twin = '+h.twin+', then next' 1430 :'<b>α involution</b> · h = '+cur+' ⟷ twin = '+h.twin) 1431 +' · step <b>'+((k%sq.length)+1)+'/'+sq.length+'</b> · |H| = 2E = <b>'+HE.length+'</b>'; 1432 } 1433 seg('f8mode',d=>{mode=d.m;k=0;draw();}); 1434 document.getElementById('f8step').onclick=()=>{k++;draw();}; 1435 document.getElementById('f8play').onclick=e=>{ 1436 if(timer){clearInterval(timer);timer=null;e.target.textContent='auto';return;} 1437 e.target.textContent='stop';timer=setInterval(()=>{k++;draw();},620);}; 1438 new ResizeObserver(draw).observe(cv);draw(); 1439 })(); 1440 1441 /* ---------- FIG 9 ---------- */ 1442 (function(){ 1443 const R=make3D('f9',.50),out=document.getElementById('f9out'); 1444 let mode='project',lvl=2; 1445 function go(){ 1446 let m=icosaMesh(1); 1447 for(let i=0;i<lvl;i++)m=mode==='project'?splitProject(m,1):loopSub(m); 1448 const rs=m.verts.map(V.len),rmin=Math.min(...rs),rmax=Math.max(...rs); 1449 R.set({verts:m.verts.map(p=>V.mul(p,.86)),faces:m.faces}, 1450 {tint:mode==='project'?[110,170,180]:[172,140,160]}); 1451 out.innerHTML='level <b>'+lvl+'</b> · V=<b>'+m.verts.length+'</b> F=<b>'+m.faces.length 1452 +'</b> (= 20·4<sup>'+lvl+'</sup>) · radius min <b>'+rmin.toFixed(4)+'</b> max <b>' 1453 +rmax.toFixed(4)+'</b> · '+(mode==='project' 1454 ?'<b style="color:'+C.edge+'">exactly on the sphere — interpolating</b>' 1455 :'<b style="color:'+C.vert+'">not a sphere — approximating, radius down to ' 1456 +(rmin*100).toFixed(1)+'%</b>'); 1457 } 1458 seg('f9mode',d=>{mode=d.m;go();}); 1459 slider('f9lvl','f9lvlv',v=>{lvl=v;go();}); 1460 go(); 1461 })(); 1462 1463 /* ---------- math ---------- */ 1464 function typeset(){ 1465 if(!window.renderMathInElement)return; 1466 renderMathInElement(document.body,{ 1467 delimiters:[{left:'\\[',right:'\\]',display:true},{left:'\\(',right:'\\)',display:false}], 1468 throwOnError:false,ignoredTags:['script','noscript','style','textarea','pre','code'] 1469 }); 1470 } 1471 if(document.readyState==='complete')typeset(); 1472 else addEventListener('load',typeset); 1473 </script> 1474 </body> 1475 </html>