Index

joshstock.in / master

Source for serving and static templating/compiling of https://joshstock.in.

Download | Refs | Commit Log | Files | README | LICENSE

Latest Commit

{#}TimeHashSubjectAuthor#(+)(-)GPG?
20322 Apr 2024 12:21fe619bdUpdate article - disambiguityJosh Stockin121G

Blob @ joshstock.in / site / content / blog / opengl-fractal-explorer.md

text/plain53270 bytesdownload raw
1---
2type: article
3identifier: opengl-fractal-explorer
4title: GPU-Accelerated Fractal Explorer
5description: Using OpenGL's compute shaders to dispatch fractal computation to the GPU and render in realtime.
6datestring: 2023-12-07
7banner_image: /static/images/mandelbrot.png
8links:
9 Source Code: https://github.com/JoshuaS3/zydeco/tree/fractal
10 The Mandelbrot Set: https://en.wikipedia.org/wiki/Mandelbrot_set
11 IEEE 754: https://en.wikipedia.org/wiki/IEEE_754
12 OpenGL Compute Shaders: https://www.khronos.org/opengl/wiki/Compute_Shader
13 Adam7 Algorithm: https://en.wikipedia.org/wiki/Adam7_algorithm
14 OpenGL Memory Model: https://www.khronos.org/opengl/wiki/Memory_Model
15---
16
17<style>
18svg {
19 display: block;
20 margin: 0 auto;
21 color: var(--text-color);
22 transform: scale(0.9);
23}
24</style>
25
26I've been toying around for a while with an idea for a procedural world
27generation + simulation project as an experiment in C++ and graphics
28programming to teach myself more about computer science and rendering
29techniques. Part of this is, of course, setting up the infrastructure for input
30handling, world logic, debug menus, and rendering. When writing the initial
31code, I used the Mandelbrot set for testing. This led me down a rabbit hole of
32improving my rendering techniques for this application, as well as trying out
33different fractals, ultimately culminating in this GPU-accelerated fractal
34explorer (transform, zoom, pan) with progressive refine:
35
36<iframe style="max-width:720px;max-height:405px;display:block;margin:0 auto 1em auto" src="https://www.youtube-nocookie.com/embed/Zqfeut60Qbc" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" allowfullscreen></iframe>
37<figcaption style="text-align:center">Video compression doesn't allow for demonstration of the progressive refine element very well; this is explained in detail later here.</figcaption>
38
39**Outline**
401. [Fractal Sets](#fractal-sets)
41 1. [The Mandelbrot Set](#the-mandelbrot-set)
42 2. [The Tricorn Set](#the-tricorn-set)
43 3. [The Burning Ship Fractal](#the-burning-ship-fractal)
442. [Notes on Fractal Computation](#notes-on-fractal-computation)
45 1. [Divergence](#divergence)
46 2. [Iteration Count](#iteration-count)
47 3. [Floating-Point Precision](#floating-point-precision)
483. [Rendering on the GPU](#rendering-on-the-gpu)
49 1. [Using a Fragment Shader](#using-a-fragment-shader)
50 2. [Using a Compute Shader](#using-a-compute-shader)
51 3. [Progressive Refine](#progressive-refine)
52
53# Fractal Sets
54
55## The Mandelbrot Set
56
57The [Mandelbrot set](https://en.wikipedia.org/wiki/Mandelbrot_set) is defined
58to be the set of all numbers *c* in the complex plane for which the following
59sequence (what I call a "z-transform" here — not related to the signal
60processing Z-transform) *does not* diverge to infinity:
61
62<svg xmlns="http://www.w3.org/2000/svg" width="158.472px" height="67.572px" viewBox="0 -1494.5 5837.2 2488.9" xmlns:xlink="http://www.w3.org/1999/xlink" aria-hidden="true" style=""><defs><path id="MJX-26-TEX-I-1D467" d="M347 338Q337 338 294 349T231 360Q211 360 197 356T174 346T162 335T155 324L153 320Q150 317 138 317Q117 317 117 325Q117 330 120 339Q133 378 163 406T229 440Q241 442 246 442Q271 442 291 425T329 392T367 375Q389 375 411 408T434 441Q435 442 449 442H462Q468 436 468 434Q468 430 463 420T449 399T432 377T418 358L411 349Q368 298 275 214T160 106L148 94L163 93Q185 93 227 82T290 71Q328 71 360 90T402 140Q406 149 409 151T424 153Q443 153 443 143Q443 138 442 134Q425 72 376 31T278 -11Q252 -11 232 6T193 40T155 57Q111 57 76 -3Q70 -11 59 -11H54H41Q35 -5 35 -2Q35 13 93 84Q132 129 225 214T340 322Q352 338 347 338Z"></path><path id="MJX-26-TEX-N-30" d="M96 585Q152 666 249 666Q297 666 345 640T423 548Q460 465 460 320Q460 165 417 83Q397 41 362 16T301 -15T250 -22Q224 -22 198 -16T137 16T82 83Q39 165 39 320Q39 494 96 585ZM321 597Q291 629 250 629Q208 629 178 597Q153 571 145 525T137 333Q137 175 145 125T181 46Q209 16 250 16Q290 16 318 46Q347 76 354 130T362 333Q362 478 354 524T321 597Z"></path><path id="MJX-26-TEX-N-3D" d="M56 347Q56 360 70 367H707Q722 359 722 347Q722 336 708 328L390 327H72Q56 332 56 347ZM56 153Q56 168 72 173H708Q722 163 722 153Q722 140 707 133H70Q56 140 56 153Z"></path><path id="MJX-26-TEX-I-1D450" d="M34 159Q34 268 120 355T306 442Q362 442 394 418T427 355Q427 326 408 306T360 285Q341 285 330 295T319 325T330 359T352 380T366 386H367Q367 388 361 392T340 400T306 404Q276 404 249 390Q228 381 206 359Q162 315 142 235T121 119Q121 73 147 50Q169 26 205 26H209Q321 26 394 111Q403 121 406 121Q410 121 419 112T429 98T420 83T391 55T346 25T282 0T202 -11Q127 -11 81 37T34 159Z"></path><path id="MJX-26-TEX-I-1D45B" d="M21 287Q22 293 24 303T36 341T56 388T89 425T135 442Q171 442 195 424T225 390T231 369Q231 367 232 367L243 378Q304 442 382 442Q436 442 469 415T503 336T465 179T427 52Q427 26 444 26Q450 26 453 27Q482 32 505 65T540 145Q542 153 560 153Q580 153 580 145Q580 144 576 130Q568 101 554 73T508 17T439 -10Q392 -10 371 17T350 73Q350 92 386 193T423 345Q423 404 379 404H374Q288 404 229 303L222 291L189 157Q156 26 151 16Q138 -11 108 -11Q95 -11 87 -5T76 7T74 17Q74 30 112 180T152 343Q153 348 153 366Q153 405 129 405Q91 405 66 305Q60 285 60 284Q58 278 41 278H27Q21 284 21 287Z"></path><path id="MJX-26-TEX-N-32" d="M109 429Q82 429 66 447T50 491Q50 562 103 614T235 666Q326 666 387 610T449 465Q449 422 429 383T381 315T301 241Q265 210 201 149L142 93L218 92Q375 92 385 97Q392 99 409 186V189H449V186Q448 183 436 95T421 3V0H50V19V31Q50 38 56 46T86 81Q115 113 136 137Q145 147 170 174T204 211T233 244T261 278T284 308T305 340T320 369T333 401T340 431T343 464Q343 527 309 573T212 619Q179 619 154 602T119 569T109 550Q109 549 114 549Q132 549 151 535T170 489Q170 464 154 447T109 429Z"></path><path id="MJX-26-TEX-N-2212" d="M84 237T84 250T98 270H679Q694 262 694 250T679 230H98Q84 237 84 250Z"></path><path id="MJX-26-TEX-N-31" d="M213 578L200 573Q186 568 160 563T102 556H83V602H102Q149 604 189 617T245 641T273 663Q275 666 285 666Q294 666 302 660V361L303 61Q310 54 315 52T339 48T401 46H427V0H416Q395 3 257 3Q121 3 100 0H88V46H114Q136 46 152 46T177 47T193 50T201 52T207 57T213 61V578Z"></path><path id="MJX-26-TEX-N-2B" d="M56 237T56 250T70 270H369V420L370 570Q380 583 389 583Q402 583 409 568V270H707Q722 262 722 250T707 230H409V-68Q401 -82 391 -82H389H387Q375 -82 369 -68V230H70Q56 237 56 250Z"></path></defs><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="scale(1,-1)"><g data-mml-node="math"><g data-mml-node="mtable"><g data-mml-node="mtr" transform="translate(0,744.5)"><g data-mml-node="mtd" transform="translate(70.7,0)"><g data-mml-node="msub"><g data-mml-node="mi"><use data-c="1D467" xlink:href="#MJX-26-TEX-I-1D467"></use></g><g data-mml-node="mn" transform="translate(498,-150) scale(0.707)"><use data-c="30" xlink:href="#MJX-26-TEX-N-30"></use></g></g></g><g data-mml-node="mtd" transform="translate(972.3,0)"><g data-mml-node="mi"></g><g data-mml-node="mo" transform="translate(277.8,0)"><use data-c="3D" xlink:href="#MJX-26-TEX-N-3D"></use></g><g data-mml-node="mi" transform="translate(1333.6,0)"><use data-c="1D450" xlink:href="#MJX-26-TEX-I-1D450"></use></g></g></g><g data-mml-node="mtr" transform="translate(0,-689.5)"><g data-mml-node="mtd"><g data-mml-node="msub"><g data-mml-node="mi"><use data-c="1D467" xlink:href="#MJX-26-TEX-I-1D467"></use></g><g data-mml-node="mi" transform="translate(498,-150) scale(0.707)"><use data-c="1D45B" xlink:href="#MJX-26-TEX-I-1D45B"></use></g></g></g><g data-mml-node="mtd" transform="translate(972.3,0)"><g data-mml-node="mi"></g><g data-mml-node="mo" transform="translate(277.8,0)"><use data-c="3D" xlink:href="#MJX-26-TEX-N-3D"></use></g><g data-mml-node="msubsup" transform="translate(1333.6,0)"><g data-mml-node="mi"><use data-c="1D467" xlink:href="#MJX-26-TEX-I-1D467"></use></g><g data-mml-node="mn" transform="translate(498,413) scale(0.707)"><use data-c="32" xlink:href="#MJX-26-TEX-N-32"></use></g><g data-mml-node="TeXAtom" transform="translate(498,-247) scale(0.707)" data-mjx-texclass="ORD"><g data-mml-node="mi"><use data-c="1D45B" xlink:href="#MJX-26-TEX-I-1D45B"></use></g><g data-mml-node="mo" transform="translate(600,0)"><use data-c="2212" xlink:href="#MJX-26-TEX-N-2212"></use></g><g data-mml-node="mn" transform="translate(1378,0)"><use data-c="31" xlink:href="#MJX-26-TEX-N-31"></use></g></g></g><g data-mml-node="mo" transform="translate(3431.7,0)"><use data-c="2B" xlink:href="#MJX-26-TEX-N-2B"></use></g><g data-mml-node="mi" transform="translate(4431.9,0)"><use data-c="1D450" xlink:href="#MJX-26-TEX-I-1D450"></use></g></g></g></g></g></g></svg>
63
64Note that the z-*squared* term is squaring a complex number, given by the
65following:
66
67<svg xmlns="http://www.w3.org/2000/svg" width="267.096px" height="66.084px" viewBox="0 -1467 9838.1 2433.9" xmlns:xlink="http://www.w3.org/1999/xlink" aria-hidden="true" style=""><defs><path id="MJX-44-TEX-I-1D450" d="M34 159Q34 268 120 355T306 442Q362 442 394 418T427 355Q427 326 408 306T360 285Q341 285 330 295T319 325T330 359T352 380T366 386H367Q367 388 361 392T340 400T306 404Q276 404 249 390Q228 381 206 359Q162 315 142 235T121 119Q121 73 147 50Q169 26 205 26H209Q321 26 394 111Q403 121 406 121Q410 121 419 112T429 98T420 83T391 55T346 25T282 0T202 -11Q127 -11 81 37T34 159Z"></path><path id="MJX-44-TEX-N-3D" d="M56 347Q56 360 70 367H707Q722 359 722 347Q722 336 708 328L390 327H72Q56 332 56 347ZM56 153Q56 168 72 173H708Q722 163 722 153Q722 140 707 133H70Q56 140 56 153Z"></path><path id="MJX-44-TEX-I-1D44E" d="M33 157Q33 258 109 349T280 441Q331 441 370 392Q386 422 416 422Q429 422 439 414T449 394Q449 381 412 234T374 68Q374 43 381 35T402 26Q411 27 422 35Q443 55 463 131Q469 151 473 152Q475 153 483 153H487Q506 153 506 144Q506 138 501 117T481 63T449 13Q436 0 417 -8Q409 -10 393 -10Q359 -10 336 5T306 36L300 51Q299 52 296 50Q294 48 292 46Q233 -10 172 -10Q117 -10 75 30T33 157ZM351 328Q351 334 346 350T323 385T277 405Q242 405 210 374T160 293Q131 214 119 129Q119 126 119 118T118 106Q118 61 136 44T179 26Q217 26 254 59T298 110Q300 114 325 217T351 328Z"></path><path id="MJX-44-TEX-N-2B" d="M56 237T56 250T70 270H369V420L370 570Q380 583 389 583Q402 583 409 568V270H707Q722 262 722 250T707 230H409V-68Q401 -82 391 -82H389H387Q375 -82 369 -68V230H70Q56 237 56 250Z"></path><path id="MJX-44-TEX-I-1D44F" d="M73 647Q73 657 77 670T89 683Q90 683 161 688T234 694Q246 694 246 685T212 542Q204 508 195 472T180 418L176 399Q176 396 182 402Q231 442 283 442Q345 442 383 396T422 280Q422 169 343 79T173 -11Q123 -11 82 27T40 150V159Q40 180 48 217T97 414Q147 611 147 623T109 637Q104 637 101 637H96Q86 637 83 637T76 640T73 647ZM336 325V331Q336 405 275 405Q258 405 240 397T207 376T181 352T163 330L157 322L136 236Q114 150 114 114Q114 66 138 42Q154 26 178 26Q211 26 245 58Q270 81 285 114T318 219Q336 291 336 325Z"></path><path id="MJX-44-TEX-I-1D456" d="M184 600Q184 624 203 642T247 661Q265 661 277 649T290 619Q290 596 270 577T226 557Q211 557 198 567T184 600ZM21 287Q21 295 30 318T54 369T98 420T158 442Q197 442 223 419T250 357Q250 340 236 301T196 196T154 83Q149 61 149 51Q149 26 166 26Q175 26 185 29T208 43T235 78T260 137Q263 149 265 151T282 153Q302 153 302 143Q302 135 293 112T268 61T223 11T161 -11Q129 -11 102 10T74 74Q74 91 79 106T122 220Q160 321 166 341T173 380Q173 404 156 404H154Q124 404 99 371T61 287Q60 286 59 284T58 281T56 279T53 278T49 278T41 278H27Q21 284 21 287Z"></path><path id="MJX-44-TEX-N-32" d="M109 429Q82 429 66 447T50 491Q50 562 103 614T235 666Q326 666 387 610T449 465Q449 422 429 383T381 315T301 241Q265 210 201 149L142 93L218 92Q375 92 385 97Q392 99 409 186V189H449V186Q448 183 436 95T421 3V0H50V19V31Q50 38 56 46T86 81Q115 113 136 137Q145 147 170 174T204 211T233 244T261 278T284 308T305 340T320 369T333 401T340 431T343 464Q343 527 309 573T212 619Q179 619 154 602T119 569T109 550Q109 549 114 549Q132 549 151 535T170 489Q170 464 154 447T109 429Z"></path><path id="MJX-44-TEX-N-28" d="M94 250Q94 319 104 381T127 488T164 576T202 643T244 695T277 729T302 750H315H319Q333 750 333 741Q333 738 316 720T275 667T226 581T184 443T167 250T184 58T225 -81T274 -167T316 -220T333 -241Q333 -250 318 -250H315H302L274 -226Q180 -141 137 -14T94 250Z"></path><path id="MJX-44-TEX-N-2212" d="M84 237T84 250T98 270H679Q694 262 694 250T679 230H98Q84 237 84 250Z"></path><path id="MJX-44-TEX-N-29" d="M60 749L64 750Q69 750 74 750H86L114 726Q208 641 251 514T294 250Q294 182 284 119T261 12T224 -76T186 -143T145 -194T113 -227T90 -246Q87 -249 86 -250H74Q66 -250 63 -250T58 -247T55 -238Q56 -237 66 -225Q221 -64 221 250T66 725Q56 737 55 738Q55 746 60 749Z"></path></defs><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="scale(1,-1)"><g data-mml-node="math"><g data-mml-node="mtable"><g data-mml-node="mtr" transform="translate(0,717)"><g data-mml-node="mtd" transform="translate(436.6,0)"><g data-mml-node="mi"><use data-c="1D450" xlink:href="#MJX-44-TEX-I-1D450"></use></g></g><g data-mml-node="mtd" transform="translate(869.6,0)"><g data-mml-node="mi"></g><g data-mml-node="mo" transform="translate(277.8,0)"><use data-c="3D" xlink:href="#MJX-44-TEX-N-3D"></use></g><g data-mml-node="mi" transform="translate(1333.6,0)"><use data-c="1D44E" xlink:href="#MJX-44-TEX-I-1D44E"></use></g><g data-mml-node="mo" transform="translate(2084.8,0)"><use data-c="2B" xlink:href="#MJX-44-TEX-N-2B"></use></g><g data-mml-node="mi" transform="translate(3085,0)"><use data-c="1D44F" xlink:href="#MJX-44-TEX-I-1D44F"></use></g><g data-mml-node="mi" transform="translate(3514,0)"><use data-c="1D456" xlink:href="#MJX-44-TEX-I-1D456"></use></g></g></g><g data-mml-node="mtr" transform="translate(0,-717)"><g data-mml-node="mtd"><g data-mml-node="msup"><g data-mml-node="mi"><use data-c="1D450" xlink:href="#MJX-44-TEX-I-1D450"></use></g><g data-mml-node="mn" transform="translate(466,413) scale(0.707)"><use data-c="32" xlink:href="#MJX-44-TEX-N-32"></use></g></g></g><g data-mml-node="mtd" transform="translate(869.6,0)"><g data-mml-node="mi"></g><g data-mml-node="mo" transform="translate(277.8,0)"><use data-c="3D" xlink:href="#MJX-44-TEX-N-3D"></use></g><g data-mml-node="mo" transform="translate(1333.6,0)"><use data-c="28" xlink:href="#MJX-44-TEX-N-28"></use></g><g data-mml-node="msup" transform="translate(1722.6,0)"><g data-mml-node="mi"><use data-c="1D44E" xlink:href="#MJX-44-TEX-I-1D44E"></use></g><g data-mml-node="mn" transform="translate(562,413) scale(0.707)"><use data-c="32" xlink:href="#MJX-44-TEX-N-32"></use></g></g><g data-mml-node="mo" transform="translate(2910.3,0)"><use data-c="2212" xlink:href="#MJX-44-TEX-N-2212"></use></g><g data-mml-node="msup" transform="translate(3910.6,0)"><g data-mml-node="mi"><use data-c="1D44F" xlink:href="#MJX-44-TEX-I-1D44F"></use></g><g data-mml-node="mn" transform="translate(462,413) scale(0.707)"><use data-c="32" xlink:href="#MJX-44-TEX-N-32"></use></g></g><g data-mml-node="mo" transform="translate(4776.1,0)"><use data-c="29" xlink:href="#MJX-44-TEX-N-29"></use></g><g data-mml-node="mo" transform="translate(5387.3,0)"><use data-c="2B" xlink:href="#MJX-44-TEX-N-2B"></use></g><g data-mml-node="mo" transform="translate(6387.6,0)"><use data-c="28" xlink:href="#MJX-44-TEX-N-28"></use></g><g data-mml-node="mn" transform="translate(6776.6,0)"><use data-c="32" xlink:href="#MJX-44-TEX-N-32"></use></g><g data-mml-node="mi" transform="translate(7276.6,0)"><use data-c="1D44E" xlink:href="#MJX-44-TEX-I-1D44E"></use></g><g data-mml-node="mi" transform="translate(7805.6,0)"><use data-c="1D44F" xlink:href="#MJX-44-TEX-I-1D44F"></use></g><g data-mml-node="mo" transform="translate(8234.6,0)"><use data-c="29" xlink:href="#MJX-44-TEX-N-29"></use></g><g data-mml-node="mi" transform="translate(8623.6,0)"><use data-c="1D456" xlink:href="#MJX-44-TEX-I-1D456"></use></g></g></g></g></g></g></svg>
68
69where *a* is the real term and *b* is the imaginary term.
70
71When rendering, we take the real axis to be *x* and the imaginary axis to be
72*y*. Points (numbers) in the set are colored black, and points not in the set
73are colored with a brightness corresponding to the number of iterations
74required until divergence.
75
76The above unassuming sequence and rules of complex algebra result in perhaps
77the most popular fractal shape, which exhibits infinite complexity at the
78boundary of the set and yields new patterns—including copies and variations of
79the set itself!—wherever you zoom in, forever.
80
81<figure class="full">
82 <img width="700px" src="/static/images/mandelbrot.png">
83</figure>
84
85Needless to say, I've been pretty fascinated by it. This isn't the only
86fractal set though. You can generate more interesting shapes and
87patterns by simply modifying the original sequence, or just coming up with
88something new. You can also add an additional parameter to play around with,
89transforming fractals. I don't get very scientific with it. You can see this
90used in the video to transform between fractals. Most random variants however
91are relatively boring in that they 1. don't produce more than one or two
92patterns, 2. produce patterns that are just the Mandelbrot set (this by itself
93is an interesting pattern of emergence), or 3. devolve into noise when zooming
94in most places. There are a couple exceptions of note:
95
96## The Tricorn Set
97
98The Tricorn set is a variant of the Mandelbrot set that uses the *conjugate* of
99z, which inverts the sign of the imaginary term.
100
101<svg xmlns="http://www.w3.org/2000/svg" width="158.472px" height="67.572px" viewBox="0 -1494.5 5837.2 2488.9" xmlns:xlink="http://www.w3.org/1999/xlink" aria-hidden="true" style=""><defs><path id="MJX-68-TEX-I-1D467" d="M347 338Q337 338 294 349T231 360Q211 360 197 356T174 346T162 335T155 324L153 320Q150 317 138 317Q117 317 117 325Q117 330 120 339Q133 378 163 406T229 440Q241 442 246 442Q271 442 291 425T329 392T367 375Q389 375 411 408T434 441Q435 442 449 442H462Q468 436 468 434Q468 430 463 420T449 399T432 377T418 358L411 349Q368 298 275 214T160 106L148 94L163 93Q185 93 227 82T290 71Q328 71 360 90T402 140Q406 149 409 151T424 153Q443 153 443 143Q443 138 442 134Q425 72 376 31T278 -11Q252 -11 232 6T193 40T155 57Q111 57 76 -3Q70 -11 59 -11H54H41Q35 -5 35 -2Q35 13 93 84Q132 129 225 214T340 322Q352 338 347 338Z"></path><path id="MJX-68-TEX-N-30" d="M96 585Q152 666 249 666Q297 666 345 640T423 548Q460 465 460 320Q460 165 417 83Q397 41 362 16T301 -15T250 -22Q224 -22 198 -16T137 16T82 83Q39 165 39 320Q39 494 96 585ZM321 597Q291 629 250 629Q208 629 178 597Q153 571 145 525T137 333Q137 175 145 125T181 46Q209 16 250 16Q290 16 318 46Q347 76 354 130T362 333Q362 478 354 524T321 597Z"></path><path id="MJX-68-TEX-N-3D" d="M56 347Q56 360 70 367H707Q722 359 722 347Q722 336 708 328L390 327H72Q56 332 56 347ZM56 153Q56 168 72 173H708Q722 163 722 153Q722 140 707 133H70Q56 140 56 153Z"></path><path id="MJX-68-TEX-I-1D450" d="M34 159Q34 268 120 355T306 442Q362 442 394 418T427 355Q427 326 408 306T360 285Q341 285 330 295T319 325T330 359T352 380T366 386H367Q367 388 361 392T340 400T306 404Q276 404 249 390Q228 381 206 359Q162 315 142 235T121 119Q121 73 147 50Q169 26 205 26H209Q321 26 394 111Q403 121 406 121Q410 121 419 112T429 98T420 83T391 55T346 25T282 0T202 -11Q127 -11 81 37T34 159Z"></path><path id="MJX-68-TEX-I-1D45B" d="M21 287Q22 293 24 303T36 341T56 388T89 425T135 442Q171 442 195 424T225 390T231 369Q231 367 232 367L243 378Q304 442 382 442Q436 442 469 415T503 336T465 179T427 52Q427 26 444 26Q450 26 453 27Q482 32 505 65T540 145Q542 153 560 153Q580 153 580 145Q580 144 576 130Q568 101 554 73T508 17T439 -10Q392 -10 371 17T350 73Q350 92 386 193T423 345Q423 404 379 404H374Q288 404 229 303L222 291L189 157Q156 26 151 16Q138 -11 108 -11Q95 -11 87 -5T76 7T74 17Q74 30 112 180T152 343Q153 348 153 366Q153 405 129 405Q91 405 66 305Q60 285 60 284Q58 278 41 278H27Q21 284 21 287Z"></path><path id="MJX-68-TEX-N-AF" d="M69 544V590H430V544H69Z"></path><path id="MJX-68-TEX-N-32" d="M109 429Q82 429 66 447T50 491Q50 562 103 614T235 666Q326 666 387 610T449 465Q449 422 429 383T381 315T301 241Q265 210 201 149L142 93L218 92Q375 92 385 97Q392 99 409 186V189H449V186Q448 183 436 95T421 3V0H50V19V31Q50 38 56 46T86 81Q115 113 136 137Q145 147 170 174T204 211T233 244T261 278T284 308T305 340T320 369T333 401T340 431T343 464Q343 527 309 573T212 619Q179 619 154 602T119 569T109 550Q109 549 114 549Q132 549 151 535T170 489Q170 464 154 447T109 429Z"></path><path id="MJX-68-TEX-N-2212" d="M84 237T84 250T98 270H679Q694 262 694 250T679 230H98Q84 237 84 250Z"></path><path id="MJX-68-TEX-N-31" d="M213 578L200 573Q186 568 160 563T102 556H83V602H102Q149 604 189 617T245 641T273 663Q275 666 285 666Q294 666 302 660V361L303 61Q310 54 315 52T339 48T401 46H427V0H416Q395 3 257 3Q121 3 100 0H88V46H114Q136 46 152 46T177 47T193 50T201 52T207 57T213 61V578Z"></path><path id="MJX-68-TEX-N-2B" d="M56 237T56 250T70 270H369V420L370 570Q380 583 389 583Q402 583 409 568V270H707Q722 262 722 250T707 230H409V-68Q401 -82 391 -82H389H387Q375 -82 369 -68V230H70Q56 237 56 250Z"></path></defs><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="scale(1,-1)"><g data-mml-node="math"><g data-mml-node="mtable"><g data-mml-node="mtr" transform="translate(0,744.5)"><g data-mml-node="mtd" transform="translate(70.7,0)"><g data-mml-node="msub"><g data-mml-node="mi"><use data-c="1D467" xlink:href="#MJX-68-TEX-I-1D467"></use></g><g data-mml-node="mn" transform="translate(498,-150) scale(0.707)"><use data-c="30" xlink:href="#MJX-68-TEX-N-30"></use></g></g></g><g data-mml-node="mtd" transform="translate(972.3,0)"><g data-mml-node="mi"></g><g data-mml-node="mo" transform="translate(277.8,0)"><use data-c="3D" xlink:href="#MJX-68-TEX-N-3D"></use></g><g data-mml-node="mi" transform="translate(1333.6,0)"><use data-c="1D450" xlink:href="#MJX-68-TEX-I-1D450"></use></g></g></g><g data-mml-node="mtr" transform="translate(0,-689.5)"><g data-mml-node="mtd"><g data-mml-node="msub"><g data-mml-node="mi"><use data-c="1D467" xlink:href="#MJX-68-TEX-I-1D467"></use></g><g data-mml-node="mi" transform="translate(498,-150) scale(0.707)"><use data-c="1D45B" xlink:href="#MJX-68-TEX-I-1D45B"></use></g></g></g><g data-mml-node="mtd" transform="translate(972.3,0)"><g data-mml-node="mi"></g><g data-mml-node="mo" transform="translate(277.8,0)"><use data-c="3D" xlink:href="#MJX-68-TEX-N-3D"></use></g><g data-mml-node="msubsup" transform="translate(1333.6,0)"><g data-mml-node="TeXAtom" data-mjx-texclass="ORD"><g data-mml-node="mover"><g data-mml-node="mi"><use data-c="1D467" xlink:href="#MJX-68-TEX-I-1D467"></use></g><g data-mml-node="mo" transform="translate(288.1,3) translate(-250 0)"><use data-c="AF" xlink:href="#MJX-68-TEX-N-AF"></use></g></g></g><g data-mml-node="mn" transform="translate(498,413) scale(0.707)"><use data-c="32" xlink:href="#MJX-68-TEX-N-32"></use></g><g data-mml-node="TeXAtom" transform="translate(498,-247) scale(0.707)" data-mjx-texclass="ORD"><g data-mml-node="mi"><use data-c="1D45B" xlink:href="#MJX-68-TEX-I-1D45B"></use></g><g data-mml-node="mo" transform="translate(600,0)"><use data-c="2212" xlink:href="#MJX-68-TEX-N-2212"></use></g><g data-mml-node="mn" transform="translate(1378,0)"><use data-c="31" xlink:href="#MJX-68-TEX-N-31"></use></g></g></g><g data-mml-node="mo" transform="translate(3431.7,0)"><use data-c="2B" xlink:href="#MJX-68-TEX-N-2B"></use></g><g data-mml-node="mi" transform="translate(4431.9,0)"><use data-c="1D450" xlink:href="#MJX-68-TEX-I-1D450"></use></g></g></g></g></g></g></svg>
102
103<figure class="full">
104 <img width="700px" src="/static/images/tricorn.png">
105</figure>
106
107## The Burning Ship Fractal
108
109A more well-known variant of the Mandelbrot set is the Burning Ship fractal,
110which takes the *absolute value* of z before squaring it.
111
112<svg xmlns="http://www.w3.org/2000/svg" width="185.424px" height="66.084px" viewBox="0 -1467 6829.8 2433.9" xmlns:xlink="http://www.w3.org/1999/xlink" aria-hidden="true" style=""><defs><path id="MJX-73-TEX-I-1D467" d="M347 338Q337 338 294 349T231 360Q211 360 197 356T174 346T162 335T155 324L153 320Q150 317 138 317Q117 317 117 325Q117 330 120 339Q133 378 163 406T229 440Q241 442 246 442Q271 442 291 425T329 392T367 375Q389 375 411 408T434 441Q435 442 449 442H462Q468 436 468 434Q468 430 463 420T449 399T432 377T418 358L411 349Q368 298 275 214T160 106L148 94L163 93Q185 93 227 82T290 71Q328 71 360 90T402 140Q406 149 409 151T424 153Q443 153 443 143Q443 138 442 134Q425 72 376 31T278 -11Q252 -11 232 6T193 40T155 57Q111 57 76 -3Q70 -11 59 -11H54H41Q35 -5 35 -2Q35 13 93 84Q132 129 225 214T340 322Q352 338 347 338Z"></path><path id="MJX-73-TEX-N-30" d="M96 585Q152 666 249 666Q297 666 345 640T423 548Q460 465 460 320Q460 165 417 83Q397 41 362 16T301 -15T250 -22Q224 -22 198 -16T137 16T82 83Q39 165 39 320Q39 494 96 585ZM321 597Q291 629 250 629Q208 629 178 597Q153 571 145 525T137 333Q137 175 145 125T181 46Q209 16 250 16Q290 16 318 46Q347 76 354 130T362 333Q362 478 354 524T321 597Z"></path><path id="MJX-73-TEX-N-3D" d="M56 347Q56 360 70 367H707Q722 359 722 347Q722 336 708 328L390 327H72Q56 332 56 347ZM56 153Q56 168 72 173H708Q722 163 722 153Q722 140 707 133H70Q56 140 56 153Z"></path><path id="MJX-73-TEX-I-1D450" d="M34 159Q34 268 120 355T306 442Q362 442 394 418T427 355Q427 326 408 306T360 285Q341 285 330 295T319 325T330 359T352 380T366 386H367Q367 388 361 392T340 400T306 404Q276 404 249 390Q228 381 206 359Q162 315 142 235T121 119Q121 73 147 50Q169 26 205 26H209Q321 26 394 111Q403 121 406 121Q410 121 419 112T429 98T420 83T391 55T346 25T282 0T202 -11Q127 -11 81 37T34 159Z"></path><path id="MJX-73-TEX-I-1D45B" d="M21 287Q22 293 24 303T36 341T56 388T89 425T135 442Q171 442 195 424T225 390T231 369Q231 367 232 367L243 378Q304 442 382 442Q436 442 469 415T503 336T465 179T427 52Q427 26 444 26Q450 26 453 27Q482 32 505 65T540 145Q542 153 560 153Q580 153 580 145Q580 144 576 130Q568 101 554 73T508 17T439 -10Q392 -10 371 17T350 73Q350 92 386 193T423 345Q423 404 379 404H374Q288 404 229 303L222 291L189 157Q156 26 151 16Q138 -11 108 -11Q95 -11 87 -5T76 7T74 17Q74 30 112 180T152 343Q153 348 153 366Q153 405 129 405Q91 405 66 305Q60 285 60 284Q58 278 41 278H27Q21 284 21 287Z"></path><path id="MJX-73-TEX-N-7C" d="M139 -249H137Q125 -249 119 -235V251L120 737Q130 750 139 750Q152 750 159 735V-235Q151 -249 141 -249H139Z"></path><path id="MJX-73-TEX-N-2212" d="M84 237T84 250T98 270H679Q694 262 694 250T679 230H98Q84 237 84 250Z"></path><path id="MJX-73-TEX-N-31" d="M213 578L200 573Q186 568 160 563T102 556H83V602H102Q149 604 189 617T245 641T273 663Q275 666 285 666Q294 666 302 660V361L303 61Q310 54 315 52T339 48T401 46H427V0H416Q395 3 257 3Q121 3 100 0H88V46H114Q136 46 152 46T177 47T193 50T201 52T207 57T213 61V578Z"></path><path id="MJX-73-TEX-N-32" d="M109 429Q82 429 66 447T50 491Q50 562 103 614T235 666Q326 666 387 610T449 465Q449 422 429 383T381 315T301 241Q265 210 201 149L142 93L218 92Q375 92 385 97Q392 99 409 186V189H449V186Q448 183 436 95T421 3V0H50V19V31Q50 38 56 46T86 81Q115 113 136 137Q145 147 170 174T204 211T233 244T261 278T284 308T305 340T320 369T333 401T340 431T343 464Q343 527 309 573T212 619Q179 619 154 602T119 569T109 550Q109 549 114 549Q132 549 151 535T170 489Q170 464 154 447T109 429Z"></path><path id="MJX-73-TEX-N-2B" d="M56 237T56 250T70 270H369V420L370 570Q380 583 389 583Q402 583 409 568V270H707Q722 262 722 250T707 230H409V-68Q401 -82 391 -82H389H387Q375 -82 369 -68V230H70Q56 237 56 250Z"></path></defs><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="scale(1,-1)"><g data-mml-node="math"><g data-mml-node="mtable"><g data-mml-node="mtr" transform="translate(0,717)"><g data-mml-node="mtd" transform="translate(70.7,0)"><g data-mml-node="msub"><g data-mml-node="mi"><use data-c="1D467" xlink:href="#MJX-73-TEX-I-1D467"></use></g><g data-mml-node="mn" transform="translate(498,-150) scale(0.707)"><use data-c="30" xlink:href="#MJX-73-TEX-N-30"></use></g></g></g><g data-mml-node="mtd" transform="translate(972.3,0)"><g data-mml-node="mi"></g><g data-mml-node="mo" transform="translate(277.8,0)"><use data-c="3D" xlink:href="#MJX-73-TEX-N-3D"></use></g><g data-mml-node="mi" transform="translate(1333.6,0)"><use data-c="1D450" xlink:href="#MJX-73-TEX-I-1D450"></use></g></g></g><g data-mml-node="mtr" transform="translate(0,-717)"><g data-mml-node="mtd"><g data-mml-node="msub"><g data-mml-node="mi"><use data-c="1D467" xlink:href="#MJX-73-TEX-I-1D467"></use></g><g data-mml-node="mi" transform="translate(498,-150) scale(0.707)"><use data-c="1D45B" xlink:href="#MJX-73-TEX-I-1D45B"></use></g></g></g><g data-mml-node="mtd" transform="translate(972.3,0)"><g data-mml-node="mi"></g><g data-mml-node="mo" transform="translate(277.8,0)"><use data-c="3D" xlink:href="#MJX-73-TEX-N-3D"></use></g><g data-mml-node="TeXAtom" data-mjx-texclass="ORD" transform="translate(1333.6,0)"><g data-mml-node="mo" transform="translate(0 -0.5)"><use data-c="7C" xlink:href="#MJX-73-TEX-N-7C"></use></g></g><g data-mml-node="msub" transform="translate(1611.6,0)"><g data-mml-node="mi"><use data-c="1D467" xlink:href="#MJX-73-TEX-I-1D467"></use></g><g data-mml-node="TeXAtom" transform="translate(498,-150) scale(0.707)" data-mjx-texclass="ORD"><g data-mml-node="mi"><use data-c="1D45B" xlink:href="#MJX-73-TEX-I-1D45B"></use></g><g data-mml-node="mo" transform="translate(600,0)"><use data-c="2212" xlink:href="#MJX-73-TEX-N-2212"></use></g><g data-mml-node="mn" transform="translate(1378,0)"><use data-c="31" xlink:href="#MJX-73-TEX-N-31"></use></g></g></g><g data-mml-node="msup" transform="translate(3487.5,0)"><g data-mml-node="TeXAtom" data-mjx-texclass="ORD"><g data-mml-node="mo" transform="translate(0 -0.5)"><use data-c="7C" xlink:href="#MJX-73-TEX-N-7C"></use></g></g><g data-mml-node="mn" transform="translate(311,413) scale(0.707)"><use data-c="32" xlink:href="#MJX-73-TEX-N-32"></use></g></g><g data-mml-node="mo" transform="translate(4424.3,0)"><use data-c="2B" xlink:href="#MJX-73-TEX-N-2B"></use></g><g data-mml-node="mi" transform="translate(5424.5,0)"><use data-c="1D450" xlink:href="#MJX-73-TEX-I-1D450"></use></g></g></g></g></g></g></svg>
113
114<figure class="full">
115 <img width="700px" src="/static/images/burning_ship1.png">
116</figure>
117
118The most interesting part about this one is actually the figure to the left,
119which is what the fractal is named after.
120
121<figure class="full">
122 <img width="700px" src="/static/images/burning_ship2.png">
123</figure>
124
125
126# Notes on Fractal Computation
127
128I want to talk about some details of computing and rendering fractals. As you
129would expect, for a full quality render you will need to compute iterations for
130every pixel in the image. **<i>This is very computationally expensive.</i>**
131Even more troublesome is having to calculate this for *every frame* when
132panning around and zooming in if you're writing a realtime explorer.
133
134## Divergence
135
136Let's first define what is meant by "diverge" when iterating over a
137z-transform. Mathematically, this means the point is unbounded, or transforms
138off to infinity. We can discard a point from the set long before infinity
139though—in fact, for the three fractals mentioned above, any complex number with
140a distance from the origin *greater than 2* will diverge during a z-transform.
141Storing the square of this—to prevent having to compute square roots when
142applying the Pythagorean theorem—in a `discard_threshold_squared` constant or
143parameter, we can speed things up by stopping before unneeded iterations in our
144compute code:
145
146```c
147const int discard_threshold_squared = 4;
148```
149
150```c
151// [inside z-transform loop]
152if ((a*a + b*b) > discard_threshold_squared)
153{
154 // [store current iteration count for purpose of
155 // coloring, indicating point is not in set]
156 break;
157}
158```
159
160Points in the set will not exit the sequence early. An implication of this is
161that *the more points in the set the frame contains, the longer the frame will
162take to render.*
163
164## Iteration Count
165
166We also need to define a maximum iteration count, the number of iterations it
167takes to confidently say "this point does not diverge." This makes for another
168design consideration, though. Note in the screenshots above how points closer
169to the set are brighter; this means it takes more iterations for those points
170to diverge. From this, it should follow that **<i>increasing the maximum number
171of iterations will lead to greater detail at the bounds of the set</i>**. If we
172set the iteration count too low, we get undetailed renders like the following
173(compare to previous screenshot).
174
175<figure class="full">
176 <img width="700px" src="/static/images/burning_ship3.png">
177</figure>
178
179Not only that, but zooming in only makes the boundary seem coarser. To
180compensate for this, I define my maximum iteration count to be a function of
181zoom level, where `n0` is a "base" iteration count parameter and `s` is the
182scale (decreases when zooming in).
183
184<svg xmlns="http://www.w3.org/2000/svg" width="258.972px" height="55.332px" viewBox="0 -1269 9538.8 2038" xmlns:xlink="http://www.w3.org/1999/xlink" aria-hidden="true" style=""><defs><path id="MJX-125-TEX-I-1D45B" d="M21 287Q22 293 24 303T36 341T56 388T89 425T135 442Q171 442 195 424T225 390T231 369Q231 367 232 367L243 378Q304 442 382 442Q436 442 469 415T503 336T465 179T427 52Q427 26 444 26Q450 26 453 27Q482 32 505 65T540 145Q542 153 560 153Q580 153 580 145Q580 144 576 130Q568 101 554 73T508 17T439 -10Q392 -10 371 17T350 73Q350 92 386 193T423 345Q423 404 379 404H374Q288 404 229 303L222 291L189 157Q156 26 151 16Q138 -11 108 -11Q95 -11 87 -5T76 7T74 17Q74 30 112 180T152 343Q153 348 153 366Q153 405 129 405Q91 405 66 305Q60 285 60 284Q58 278 41 278H27Q21 284 21 287Z"></path><path id="MJX-125-TEX-N-28" d="M94 250Q94 319 104 381T127 488T164 576T202 643T244 695T277 729T302 750H315H319Q333 750 333 741Q333 738 316 720T275 667T226 581T184 443T167 250T184 58T225 -81T274 -167T316 -220T333 -241Q333 -250 318 -250H315H302L274 -226Q180 -141 137 -14T94 250Z"></path><path id="MJX-125-TEX-I-1D460" d="M131 289Q131 321 147 354T203 415T300 442Q362 442 390 415T419 355Q419 323 402 308T364 292Q351 292 340 300T328 326Q328 342 337 354T354 372T367 378Q368 378 368 379Q368 382 361 388T336 399T297 405Q249 405 227 379T204 326Q204 301 223 291T278 274T330 259Q396 230 396 163Q396 135 385 107T352 51T289 7T195 -10Q118 -10 86 19T53 87Q53 126 74 143T118 160Q133 160 146 151T160 120Q160 94 142 76T111 58Q109 57 108 57T107 55Q108 52 115 47T146 34T201 27Q237 27 263 38T301 66T318 97T323 122Q323 150 302 164T254 181T195 196T148 231Q131 256 131 289Z"></path><path id="MJX-125-TEX-N-29" d="M60 749L64 750Q69 750 74 750H86L114 726Q208 641 251 514T294 250Q294 182 284 119T261 12T224 -76T186 -143T145 -194T113 -227T90 -246Q87 -249 86 -250H74Q66 -250 63 -250T58 -247T55 -238Q56 -237 66 -225Q221 -64 221 250T66 725Q56 737 55 738Q55 746 60 749Z"></path><path id="MJX-125-TEX-N-3D" d="M56 347Q56 360 70 367H707Q722 359 722 347Q722 336 708 328L390 327H72Q56 332 56 347ZM56 153Q56 168 72 173H708Q722 163 722 153Q722 140 707 133H70Q56 140 56 153Z"></path><path id="MJX-125-TEX-N-30" d="M96 585Q152 666 249 666Q297 666 345 640T423 548Q460 465 460 320Q460 165 417 83Q397 41 362 16T301 -15T250 -22Q224 -22 198 -16T137 16T82 83Q39 165 39 320Q39 494 96 585ZM321 597Q291 629 250 629Q208 629 178 597Q153 571 145 525T137 333Q137 175 145 125T181 46Q209 16 250 16Q290 16 318 46Q347 76 354 130T362 333Q362 478 354 524T321 597Z"></path><path id="MJX-125-TEX-N-6C" d="M42 46H56Q95 46 103 60V68Q103 77 103 91T103 124T104 167T104 217T104 272T104 329Q104 366 104 407T104 482T104 542T103 586T103 603Q100 622 89 628T44 637H26V660Q26 683 28 683L38 684Q48 685 67 686T104 688Q121 689 141 690T171 693T182 694H185V379Q185 62 186 60Q190 52 198 49Q219 46 247 46H263V0H255L232 1Q209 2 183 2T145 3T107 3T57 1L34 0H26V46H42Z"></path><path id="MJX-125-TEX-N-6F" d="M28 214Q28 309 93 378T250 448Q340 448 405 380T471 215Q471 120 407 55T250 -10Q153 -10 91 57T28 214ZM250 30Q372 30 372 193V225V250Q372 272 371 288T364 326T348 362T317 390T268 410Q263 411 252 411Q222 411 195 399Q152 377 139 338T126 246V226Q126 130 145 91Q177 30 250 30Z"></path><path id="MJX-125-TEX-N-67" d="M329 409Q373 453 429 453Q459 453 472 434T485 396Q485 382 476 371T449 360Q416 360 412 390Q410 404 415 411Q415 412 416 414V415Q388 412 363 393Q355 388 355 386Q355 385 359 381T368 369T379 351T388 325T392 292Q392 230 343 187T222 143Q172 143 123 171Q112 153 112 133Q112 98 138 81Q147 75 155 75T227 73Q311 72 335 67Q396 58 431 26Q470 -13 470 -72Q470 -139 392 -175Q332 -206 250 -206Q167 -206 107 -175Q29 -140 29 -75Q29 -39 50 -15T92 18L103 24Q67 55 67 108Q67 155 96 193Q52 237 52 292Q52 355 102 398T223 442Q274 442 318 416L329 409ZM299 343Q294 371 273 387T221 404Q192 404 171 388T145 343Q142 326 142 292Q142 248 149 227T179 192Q196 182 222 182Q244 182 260 189T283 207T294 227T299 242Q302 258 302 292T299 343ZM403 -75Q403 -50 389 -34T348 -11T299 -2T245 0H218Q151 0 138 -6Q118 -15 107 -34T95 -74Q95 -84 101 -97T122 -127T170 -155T250 -167Q319 -167 361 -139T403 -75Z"></path><path id="MJX-125-TEX-N-32" d="M109 429Q82 429 66 447T50 491Q50 562 103 614T235 666Q326 666 387 610T449 465Q449 422 429 383T381 315T301 241Q265 210 201 149L142 93L218 92Q375 92 385 97Q392 99 409 186V189H449V186Q448 183 436 95T421 3V0H50V19V31Q50 38 56 46T86 81Q115 113 136 137Q145 147 170 174T204 211T233 244T261 278T284 308T305 340T320 369T333 401T340 431T343 464Q343 527 309 573T212 619Q179 619 154 602T119 569T109 550Q109 549 114 549Q132 549 151 535T170 489Q170 464 154 447T109 429Z"></path><path id="MJX-125-TEX-N-2061" d=""></path><path id="MJX-125-TEX-N-2B" d="M56 237T56 250T70 270H369V420L370 570Q380 583 389 583Q402 583 409 568V270H707Q722 262 722 250T707 230H409V-68Q401 -82 391 -82H389H387Q375 -82 369 -68V230H70Q56 237 56 250Z"></path><path id="MJX-125-TEX-N-31" d="M213 578L200 573Q186 568 160 563T102 556H83V602H102Q149 604 189 617T245 641T273 663Q275 666 285 666Q294 666 302 660V361L303 61Q310 54 315 52T339 48T401 46H427V0H416Q395 3 257 3Q121 3 100 0H88V46H114Q136 46 152 46T177 47T193 50T201 52T207 57T213 61V578Z"></path></defs><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="scale(1,-1)"><g data-mml-node="math"><g data-mml-node="mtable"><g data-mml-node="mtr" transform="translate(0,-73)"><g data-mml-node="mtd"><g data-mml-node="mi"><use data-c="1D45B" xlink:href="#MJX-125-TEX-I-1D45B"></use></g><g data-mml-node="mo" transform="translate(600,0)"><use data-c="28" xlink:href="#MJX-125-TEX-N-28"></use></g><g data-mml-node="mi" transform="translate(989,0)"><use data-c="1D460" xlink:href="#MJX-125-TEX-I-1D460"></use></g><g data-mml-node="mo" transform="translate(1458,0)"><use data-c="29" xlink:href="#MJX-125-TEX-N-29"></use></g><g data-mml-node="mo" transform="translate(2124.8,0)"><use data-c="3D" xlink:href="#MJX-125-TEX-N-3D"></use></g><g data-mml-node="msub" transform="translate(3180.6,0)"><g data-mml-node="mi"><use data-c="1D45B" xlink:href="#MJX-125-TEX-I-1D45B"></use></g><g data-mml-node="mn" transform="translate(633,-150) scale(0.707)"><use data-c="30" xlink:href="#MJX-125-TEX-N-30"></use></g></g><g data-mml-node="msub" transform="translate(4383.8,0)"><g data-mml-node="mi"><use data-c="6C" xlink:href="#MJX-125-TEX-N-6C"></use><use data-c="6F" xlink:href="#MJX-125-TEX-N-6F" transform="translate(278,0)"></use><use data-c="67" xlink:href="#MJX-125-TEX-N-67" transform="translate(778,0)"></use></g><g data-mml-node="mn" transform="translate(1311,-241.4) scale(0.707)"><use data-c="32" xlink:href="#MJX-125-TEX-N-32"></use></g></g><g data-mml-node="mo" transform="translate(6098.3,0)"><use data-c="2061" xlink:href="#MJX-125-TEX-N-2061"></use></g><g data-mml-node="mo" transform="translate(6098.3,0)"><use data-c="28" xlink:href="#MJX-125-TEX-N-28"></use></g><g data-mml-node="mn" transform="translate(6487.3,0)"><use data-c="32" xlink:href="#MJX-125-TEX-N-32"></use></g><g data-mml-node="mo" transform="translate(7209.6,0)"><use data-c="2B" xlink:href="#MJX-125-TEX-N-2B"></use></g><g data-mml-node="mfrac" transform="translate(8209.8,0)"><g data-mml-node="mn" transform="translate(220,676)"><use data-c="31" xlink:href="#MJX-125-TEX-N-31"></use></g><g data-mml-node="mi" transform="translate(235.5,-686)"><use data-c="1D460" xlink:href="#MJX-125-TEX-I-1D460"></use></g><rect width="700" height="60" x="120" y="220"></rect></g><g data-mml-node="mo" transform="translate(9149.8,0)"><use data-c="29" xlink:href="#MJX-125-TEX-N-29"></use></g></g></g></g></g></g></svg>
185
186This largely fixes the coarseness of the shape when zooming in, but poses a new
187issue. At a certain point when zooming in, the iteration count will become so
188large that framerate begins to drop. In the [Rendering on the
189GPU](#rendering-on-the-gpu) section I detail a rendering method called
190*interlacing* (or *progressive refine*) that lets us split up the work of a
191render across multiple frames.
192
193## Floating-Point Precision
194
195The primary limitation with a realtime fractal renderer like this is computer
196hardware architecture. For most applications, computers store decimal numbers
197according to standard [IEEE 754](https://en.wikipedia.org/wiki/IEEE_754) (or
198variants thereof), which, in essence, represent decimal numbers in scientific
199notation form, comprising a significand ("mantissa") and an exponent. On
200modern CPUs and GPUs, there are floating-point arithmetic units (FPUs) built
201into hardware that make computation with floating-point types significantly
202faster than it would be with a software-only implementation. FPUs nowadays come
203in sizes of 16 bits (half-width/FP16), 32 bits (single-width/FP32), 64 bits
204(double-width/FP64), and 128 bits (quad-width/FP128). As you might be able to
205guess, more bits means larger values means greater precision.
206
207This pertains to computing fractals because the points needed on the complex
208plane are decimals, not integers. **<i>Zooming into one point—effectively
209increasing the number of decimal places encoded by each pixel's location—only
210increases the precision required in computing.</i>**
211
212Limiting ourselves to hardware floating-point implementations caps our
213precision at FP128. In reality, if we're running this on the GPU, we're capped
214to FP64, since most GPU architectures don't support FP128. (OpenGL's shader
215language doesn't even provide a quad-width type, e.g. `long double`. Even for
216CPU architectures, hardware support for FP128 is
217[iffy](https://en.wikipedia.org/wiki/Quadruple-precision_floating-point_format#Hardware_support).)
218Also, since graphics applications generally don't need more than 32 bits of
219floating-point precision, GPUs tend to have only 32-bit wide FPUs, with a slow
220processing path for FP64 (about 1/64 the speed of FP32 according to some
221benchmarks). Despite this, GPUs have significantly more floating-point
222execution units than CPUs, so we're *still* running faster on the GPU.
223
224With 64-bit precision on the GPU, we can zoom in by a factor of about 14 times
225before we hit our precision limit.
226
227<figure class="full">
228 <img width="700px" src="/static/images/fractal_precision.png">
229</figure>
230
231This isn't ideal but it's the best I could come up with (or cared to,
232considering this was not a planned project) for a realtime renderer. Fractal
233dive renderers use high-level CPU software implementations for
234*arbitrary-precision* floating-point computation, like
235[BigFloat](https://github.com/nicowilliams/bigfloat), but this would be
236disastrously slow for a realtime application (and be incompatible with GPU
237acceleration).
238
239# Rendering on the GPU
240
241## Using a Fragment Shader
242
243The 10,000-foot view of the basic OpenGL rendering pipeline for an object is as
244follows:
245
2461. You give the graphics card mesh data and some arbitrary program-defined
247 render settings
2482. A vertex shader interprets this mesh data as primitive shapes, e.g.
249 triangles, and applies perspective transformations to scale, rotate, and
250 position them relative to the screen or "camera"
2513. A fragment shader uses the geometry of the primitive plus the given
252 arbitrary render settings (including textures) to fill in the colors of
253 fragments (pixels, basically) within the primitive
2544. The graphics card does some linear algebra magic to combine the computed
255 data for all objects into a rendered scene, the framebuffer
256
257<figcaption>This is the explain-like-I'm-five version. If you actually know
258OpenGL you know this is so insanely simplified it could just be called "wrong,"
259but it's a good enough overview for the purposes of this writeup.</figcaption>
260
261Knowing my CPU would be too slow for realtime rendering, rather than doing
262fractal computation on the CPU and loading the result into a texture to be
263displayed by the GPU, my initial attempt used an OpenGL fragment shader to do
264computation directly on the GPU. It seemed like a good idea; given two
265triangles filling the entire screen, the fragment shader is executed for every
266pixel of the frame and outputs a color for that pixel. However, there were some
267drawbacks:
268
2691. Everything was redrawn every frame, even if the user hadn't moved,
270 unnecessarily consuming GPU resources
2712. This was extraordinarily slow at high iteration counts (high zoom)
2723. Iterative refine—either splitting iterations across frames or breaking the
273 frame up into chunks—wasn't feasible (or wouldn't be efficient/elegant
274 enough)
275
276Clearly, a different strategy was needed.
277
278## Using a Compute Shader
279
280The [compute shader](https://www.khronos.org/opengl/wiki/Compute_Shader) is
281OpenGL's interface for general purpose GPU (GPGPU) programming—analogous to
282NVIDIA's CUDA, which lets you use a GPU for arbitrary floating-point-intensive
283computation. Unlike CUDA however, compute shaders provide cross-platform
284support (including integrated GPUs) and integrate with the rest of the graphics
285library, for things like accessing textures. Perfect!!
286
287As they're meant to be used for GPGPU programming, compute shaders aren't built
288into the core OpenGL rendering pipeline. They must be explicitly invoked
289(dispatched) by the application, separate of the rendering sequence. This is
290actually great for our renderer because being able to control when computes
291happen means we can have them run only when they're actually needed (when the
292user pans, zooms, or transforms).
293
294```cpp
295// inside application C++ "world logic"
296// once we determine we need to recompute after some user input, we can do it like this:
297
298// bind texture/image to save computed data in
299m_pTexture->BindAsImage();
300
301// upload arbitrary data/settings (x/y position, zoom level, screen size, iteration count)
302m_pComputeShaderUniformUploader->UploadUniforms(program);
303
304// do compute across the width and height of the screen split up into 32x32 pixel chunks
305glDispatchCompute((m_windowWidth+31)/32, (m_windowHeight+31)/32, 1);
306```
307
308The compute shader looks like this:
309
310```glsl
311#version 460 core
312
313// define the size of the local working group to be 32x32x1
314// main() runs every time for each pixel in the 32x32 region
315layout (local_size_x = 32, local_size_y = 32, local_size_z = 1) in;
316
317// arbitrary data/settings ("uniforms") uploaded by the application
318layout(r32f, binding = 0) uniform image2D texture0;
319uniform ivec2 screen_size;
320uniform dvec2 offset; // indicates x/y position within the fractal
321uniform double scale; // decreases when zooming in
322uniform float discard_threshold_squared;
323uniform int max_iteration_count;
324
325void main()
326{
327 // 1. convert screen pixel location to world/graph space
328 // 2. run z-transform
329 // 3. store iteration count into texture
330}
331```
332
333Splitting up the screen into 32x32 chunks is pretty arbitrary. GPUs are very
334heavily designed for parallelism, so, generally, splitting work up into chunks
335means things will get done more quickly, but there is an upper limit to this.
336In my experimentation, 32x32 chunks seemed to work best for whatever reason.
337
338The only data we're storing in the texture during computes is a single number
339per pixel: the number of iterations it takes for the pixel's corresponding
340point to diverge. The same texture is then fed into the fragment shader during the
341rendering stage, which reads these values and spits out colors to the screen
342accordingly. `-1` can be used to indicate a point that doesn't diverge (in the
343set, colored black).
344
345<figcaption>Note the texture is declared in the computer shader as having
346format <code>r32f</code>; this indicates a single channel <code>r</code> with
347type FP32, though <code>r32i</code> would work just as well here. See
348possible formats in OpenGL documentation for <a
349href="https://registry.khronos.org/OpenGL-Refpages/gl4/html/glTexImage2D.xhtml">glTexImage2D</a>.
350Texture creation is managed by the application.</figcaption>
351
352This is great and all, but it doesn't really solve the issue with high
353iteration counts slowing things down. When zooming in a lot, the application
354becomes so slow that doing anything has a more-than-noticeable input latency
355(see this in the video around 0:15). This is where we implement a method for
356*progressive refine*.
357
358## Progressive Refine
359
360Progressive refine is the act of taking an intensive piece of work and breaking
361it down into multiple chunks *over time*. This is commonly done in dedicated
362renderers when you want a preview of a render that will take a while, or in
363networking when loading images over a slow connection; it quickly gives you an
364image at, for example, 1/64 full quality, then not-so-quickly an image at 1/32,
365then 1/16, and so on, with each step taking longer on average than the
366previous. Inspired by a friend's [use of the Bayer matrix for this
367purpose](https://jbaker.graphics/writings/bayer.html), I used a similar
368**<i>interlacing pattern</i>** defined by the **<i>[Adam7
369algorithm](https://en.wikipedia.org/wiki/Adam7_algorithm)</i>**, which splits
370work in an 8x8 grid across seven steps:
371
372```glsl
373const int ADAM7_MATRIX[8][8] = {
374 {1, 6, 4, 6, 2, 6, 4, 6},
375 {7, 7, 7, 7, 7, 7, 7, 7},
376 {5, 6, 5, 6, 5, 6, 5, 6},
377 {7, 7, 7, 7, 7, 7, 7, 7},
378 {3, 6, 4, 6, 3, 6, 4, 6},
379 {7, 7, 7, 7, 7, 7, 7, 7},
380 {5, 6, 5, 6, 5, 6, 5, 6},
381 {7, 7, 7, 7, 7, 7, 7, 7},
382};
383```
384
385<figcaption>For this pattern of interlacing, the 1st and 2nd steps actually
386always take the same amount of time because they do the same amount of work.
387Every step after that, though, takes twice as long as the
388previous.</figcaption>
389
390Incorporating this into the fractal renderer, what we can do is pass some
391number to the compute shader which indicates which step we're on, [1-7]. The
392compute shader then indexes the above matrix at the pixel's position, compares
393that value to the instructed interlace step, and only computes if the values
394are equal.
395
396```glsl
397uniform int interlace_step;
398```
399
400```glsl
401// [in main()]
402
403// 32x32 work group size means we'll have 16 internal 8x8 grids for interlacing.
404// Check where the current pixel is within whichever 8x8 grid it falls in:
405int relative_pixel_grid_pos_x = gl_LocalInvocationID.x % 8;
406int relative_pixel_grid_pos_y = gl_LocalInvocationID.y % 8;
407
408bool do_compute = (ADAM7_MATRIX[relative_pixel_grid_pos_y][relative_pixel_grid_pos_x] == interlace_step);
409if (do_compute)
410{
411 // z-transform
412}
413```
414
415For each pixel, the routine then stores either the new computed value or, if
416nothing was computed, does nothing. Correspondingly, the fragment shader must
417be updated for this behavior as well. Following step 1, most elements in the
418texture will still be empty; to prevent the screen from displaying mostly
419uncomputed pixels (undefined behavior?), we should check whether a pixel has
420been computed before trying to use it, and use the nearest computed pixel if
421the first hasn't been.
422
423The resulting behavior is this:
424
425<figure class="full">
426 <img width="700px" src="/static/images/fractal_refine.gif">
427</figure>
428
429Now, when zooming in at high iteration count, the first compute step is only
430doing 1/64 (~1.56%) of the computations it normally would, keeping things
431within the span of a single frame, i.e. preventing framerate drops. This is
432great for user actions, where zooming and panning happen for as long as the
433mouse input lasts—potentially hundreds of frames.
434
435Suppose, though, that a single step takes longer than a frame to compute. Well,
436that's no worry either since *compute shaders act independent of the rendering
437pipeline*, so rendering is not being held up by a compute shader still running.
438Furthermore, to prevent compute dispatches from overlapping, you can make use
439of asynchronous OpenGL interfaces like [fences and memory
440barriers](https://www.khronos.org/opengl/wiki/Memory_Model) to prevent
441dispatching a new compute for the next step until the previous has finished,
442framerate unaffected.
443
444My implementation can actually take the idea of progressive refine a step
445further, allowing the point's z-transform itself to be distributed across
446computes, resulting in *multiple* interlacing passes. It does this by storing
447another two elements per pixel in the texture, the real and imaginary
448components of the z-transform output, for it to pick up with on the start of
449the next compute. This poses the same precision issues as before, however,
450considering OpenGL textures only allow you to store elements up to FP32
451precision, so it doesn't work very well at high zoom levels. We can work around
452this by using a separate texture with four elements per pixel: two 32-bit
453elements for the real component, and two more 32-bit elements for the imaginary
454component. See
455[floatBitsToInt](https://registry.khronos.org/OpenGL-Refpages/gl4/html/floatBitsToInt.xhtml)
456and related GLSL functions for a way you might accomplish this.
457
458