-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathindex.html
4421 lines (3560 loc) · 195 KB
/
index.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<!DOCTYPE html>
<html lang="en" xmlns:p="http://www.w3.org/1999/html">
<head>
<meta charset="utf-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=edge"/>
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<!--
Query parameters:
?TODO - show TODOs
?diagrams=hide - hide diagrams (for faster loading)
"edit" link: http://localhost/alpenglow/?TODO&diagrams=hide#WGSL
-->
<title>Alpenglow Plan & Documentation</title>
<link rel="shortcut icon" type="image/x-icon" href="../scenery/assets/logo-v1.svg">
<link rel="stylesheet" href="../sherpa/lib/bootstrap-2.2.2.css">
<link rel="stylesheet" href="../sherpa/lib/bootstrap-responsive-2.2.2.css">
<script>
window.MathJax = {
tex: {
inlineMath: [ [ '$', '$' ], [ '\\(', '\\)' ] ]
},
autoload: {
cases: [ [], [ 'numcases', 'subnumcases' ] ]
}
};
</script>
<script id="MathJax-script" async src="../sherpa/mathjax/tex-chtml.js"></script>
<script>
window.phet = window.phet || {};
window.pendingDiagrams = [];
window.addDiagram = ( id, callback ) => {
window.pendingDiagrams.push( { id: id, callback: callback } );
};
</script>
<!-- Before loading other things (that might error), create hooks to report errors/loads for continuous testing -->
<script src="../chipper/js/browser/sim-tests/pageload-connector.js"></script>
<!-- jQuery and LoDash are dependencies -->
<script src="../sherpa/lib/jquery-2.1.0.min.js"></script>
<script src="../sherpa/lib/lodash-4.17.4.min.js"></script>
<!-- For the styling -->
<script src="../sherpa/lib/bootstrap-2.2.2.js"></script>
<link rel="stylesheet" href="../sherpa/lib/codemirror-5.52.2.min.css">
<link rel="stylesheet" href="../sherpa/lib/codemirror-5.52.2.monokai.min.css">
<script src="../sherpa/lib/codemirror-5.52.2.min.js"></script>
<script src="../sherpa/lib/codemirror-5.52.2.javascript.min.js"></script>
<script src="./doc/citations.js"></script>
<link rel="stylesheet" href="./doc/doc.css">
<script src="./doc/todo.js"></script>
<script>
// Loads a synchronously-executed asynchronously-downloaded script tag, with optional data-main parameter.
// See http://www.html5rocks.com/en/tutorials/speed/script-loading/ for more about script loading. It helps to
// load all of the scripts with this method, so they are treated the same (and placed in the correct execution
// order).
const loadURL = ( preloadURL, type = 'text/javascript', async = false ) => {
const script = document.createElement( 'script' );
script.type = type;
script.src = preloadURL;
script.async = async;
script.setAttribute( 'crossorigin', 'use-credentials' );
document.head.appendChild( script );
};
window.usePhetLib = true;
loadURL( '../scenery/doc/extractFunctionJS.js' );
loadURL( './doc/teapotObj.js' );
loadURL( './doc/load-citations.js' );
if ( window.usePhetLib ) {
loadURL( './doc/lib/phet-lib.min.js' ); // TODO: consider using plain alpenglow (smaller)?
}
else {
loadURL( '../assert/js/assert.js' );
loadURL( '../sherpa/lib/linebreak-1.1.0.js' );
loadURL( '../sherpa/lib/flatqueue-1.2.1.js' );
loadURL( '../sherpa/lib/paper-js-0.12.17.js' );
loadURL( '../sherpa/lib/he-1.1.1.js' );
loadURL( '../sherpa/lib/TextEncoderLite-3c9f6f0.js' );
loadURL( '../sherpa/lib/base64-js-1.2.0.js' );
}
loadURL( './doc/index.js', 'module' );
loadURL( './doc/load-mermaid.js', 'module' );
</script>
</head>
<body>
<div class="row-fluid">
<div class="span2"></div>
<div class="span8">
<div class="give-max-width">
<div class="page-header" style="text-align: center;">
<h1>Alpenglow Plan & Documentation</h1>
</div>
</div>
</div>
<div class="span2"></div>
</div>
<div class="nav-container hidden-phone">
<div class="nav-root">
<ul class="nav nav-list nav-main">
<li>
<a href="#overview">Overview</a>
<ul class="nav nav-list">
<li><a href="#overview-mainChallenges">Main Challenges</a></li>
<li><a href="#overview-relatedWork">Related Work</a></li>
<li><a href="#overview-contributions">Contributions</a></li>
<li><a href="#overview-impact">Desired Impact</a></li>
</ul>
</li>
<li>
<a href="#concepts">Concepts</a>
<ul class="nav nav-list">
<li><a href="#polygonalFaces">Polygonal Faces</a></li>
<li><a href="#clipping">Clipping</a></li>
<li><a href="#booleanOperations">Boolean Operations</a></li>
<li>
<a href="#antialiasing">Anti-Aliasing</a>
<ul class="nav nav-list">
<li><a href="#antialiasing-integrals">Integrals</a></li>
<li><a href="#antialiasing-filters">Filters</a></li>
<li><a href="#antialiasing-examples">Examples</a></li>
</ul>
</li>
<li>
<a href="#color-and-blending">Color & Blending</a>
</li>
<li>
<a href="#renderProgram">RenderProgram</a>
<ul class="nav nav-list">
<li><a href="#RenderColor">RenderColor</a></li>
<li><a href="#RenderPathBoolean">RenderPathBoolean</a></li>
<li><a href="#RenderStack">RenderStack</a></li>
<li><a href="#RenderLinearBlend">RenderLinearBlend</a></li>
<li><a href="#RenderLinearGradient">RenderLinearGradient</a></li>
<li><a href="#RenderRadialBlend">RenderRadialBlend</a></li>
<li><a href="#RenderRadialGradient">RenderRadialGradient</a></li>
<li><a href="#RenderBlendCompose">RenderBlendCompose</a></li>
<li><a href="#renderProgram-simplification">Simplification</a></li>
<li><a href="#renderProgram-execution">Execution</a></li>
</ul>
</li>
<li>
<a href="#WGSL">WGSL</a>
<ul class="nav nav-list">
<li><a href="#WGSL-templating">Templating</a></li>
<li><a href="#WGSL-types">Types</a></li>
<li><a href="#WGSL-linking">Linking</a></li>
<li><a href="#WGSL-recording">Recording</a></li>
<li><a href="#WGSL-logging">Logging</a></li>
<li><a href="#WGSL-testing">Testing</a></li>
<li><a href="#WGSL-algorithms">Algorithms</a></li>
<li><a href="#WGSL-reduce">Reduce</a></li>
<li><a href="#WGSL-scan">Scan</a></li>
<li><a href="#WGSL-radixSort">Radix Sort</a></li>
<li><a href="#WGSL-mergeSort">Merge Sort</a></li>
<li><a href="#WGSL-stackMonoid">Stack Monoid</a></li>
<li><a href="#WGSL-memory">Memory</a></li>
<li><a href="#WGSL-rationals">Rationals</a></li>
<li><a href="#WGSL-profiling">Profiling</a></li>
<li><a href="#WGSL-unitTesting">Unit Testing</a></li>
<li><a href="#WGSL-knownBugs">Known Bugs</a></li>
<li><a href="#WGSL-notes">Notes</a></li>
<li><a href="#WGSL-newLanguage">New Language</a></li>
<li><a href="#WGSL-overlap">Overlap</a></li>
<li><a href="#WGSL-documentation">Documentation</a></li>
<li><a href="#WGSL-deprecated">Deprecated</a></li>
</ul>
</li>
<li><a href="#asyncSimulation">Async Simulation</a></li>
<li><a href="#depthSort">Depth Sort</a></li>
<li><a href="#vectorCanvas">Vector Canvas</a></li>
</ul>
</li>
<li>
<a href="#stages">Stages</a>
<ul class="nav nav-list">
<li><a href="#stage-transforms">Transforms</a></li>
<li><a href="#stage-subdivision">Subdivision</a></li>
<li><a href="#stage-bounds">Bounds</a></li>
<li><a href="#stage-tiling">Tiling</a></li>
<li><a href="#stage-integerTransform">Integer Transform</a></li>
<li><a href="#stage-hilbertSort">Hilbert Sort</a></li>
<li><a href="#stage-intersection">Intersection</a></li>
<li><a href="#stage-split">Split</a></li>
<li><a href="#stage-edgeSort">Edge Sort</a></li>
<li><a href="#stage-filterConnect">Filter & Connect</a></li>
<li><a href="#stage-boundaryTrace">Boundary Trace</a></li>
<li><a href="#stage-faceHoles">Face Holes</a></li>
<li><a href="#stage-windingMaps">Winding Maps</a></li>
<li><a href="#stage-renderProgramSimplification">RenderProgram Simplification</a></li>
<li><a href="#stage-renderableFaceCreation">RenderableFace Creation</a></li>
<li><a href="#stage-splitPrograms">Split Programs</a></li>
<li><a href="#stage-rasterize">Rasterize</a></li>
</ul>
</li>
<li><a href="#references">References</a></li>
</ul>
</div>
</div>
<div class="row-fluid">
<div class="span2"></div>
<div class="span8">
<div class="give-max-width">
<h2 id="overview">Overview</h2>
<p>
Alpenglow is an experimental rasterizer that takes a scene description and efficiently produces a corresponding
high-quality image.
</p>
<p>
The goal is to have:
</p>
<ul>
<li>
A high-performance WebGPU rasterizer (<span class="text-info">in progress</span>)
</li>
<li>
A software reference implementation (<span class="text-success">implemented</span>)
</li>
<li>
A potential WebGL 2 fallback (<span class="text-error">not started</span>)
</li>
</ul>
<p>
<strong>
Please contact the author (Jonathan Olson, [email protected]) for any questions or comments, no matter how small!
</strong>
</p>
<p class="TODO">
Improve rasterization docs below
</p>
<p class="TODO">
Get the scan-based rasterization also working - we are being VERY LIMITED by coarse face limit, since we can't
dispatch 65536 or more workgroups (and we have one workgroup per coarse face).
</p>
<p class="TODO">
Consider keeping CAG in CPU, sweep-line or Vatti (Kite) like algorithms for intersection (rather than what we do now).
We could potentially do CAG "deltas" if not much changes, for scenes with some animated but most is static.
Or consider stateful CAG on GPU?
</p>
<p class="TODO">
CPU CAG would also enable better "vector canvas" approach. Progressive, where each frame has added edges and removed edges.
</p>
<p class="TODO">
Get non-crashing on phones -
Prioritize demos lazily (either when they are close to the scrolled viewport) or on other threads (web workers).
</p>
<p class="TODO">
Run rendering in web worker thread?
</p>
<p class="TODO">
Remove duplication of render-program logic (that was confusing) - how to do this with potential workgroup variables?
</p>
<p class="TODO">
Fix logging so we don't have to patch in forwarding of local/global/workgroup IDs through everything.
Can we set these things as a var<private>? That should solve all of it, but would need a different naming.
Can this be consistently done? Any easy way? Add a WGSLString that goes at start of main(), has a module dependency
that adds the var-privates?
</p>
<p class="TODO">
Lazy paints with IntersectionObserver API.
See <a href="https://macarthur.me/posts/animate-canvas-in-a-worker/">Animate Canvas in a Worker</a> or
<a href="https://webgpu.github.io/webgpu-samples/?sample=worker">Web Worker WebGPU</a>.
<code>canvas.transferControlToOffscreen()</code> and messaging it to worker seems to work.
</p>
<p class="TODO">
Add TODO levels here, so we can flag critical/important ones. Also, make them searchable?
</p>
<p class="TODO">
Sub-pixel rendering! Do separate regions for each color channel. Get Loupe for screen inspection.
Experiment more with text and readability, see how small we can get text to still be readable!
Animated moving siemens stars would help identify the type of subpixel! Animate a bunch of options, see
which looks the cleanest without jitter.
</p>
<p class="TODO">
Implement SVG full compatibility?
</p>
<p class="TODO">
Get font changes done with Scenery vello branch, so we can include code improvements and get RenderFromNode working
better. Also allows showing Vello stuff in demos (will need to see if we can port over the multi branch work).
Merge multi-work. Remove auto-feature-detect for now, so it doesn't ping shaders on main?
</p>
<p class="TODO">
Improve styling, see <a href="https://getbootstrap.com/2.3.2/scaffolding.html">Old Bootstrap docs</a>.
</p>
<p class="TODO">
Add "(your browser)" on SVG/Canvas demo labels?
</p>
<p class="TODO">
Stream out tiles one-by-one (as CPU is ready for it)? We could CAG one tile at a time, and push out the rasterization.
Have the CPU and GPU working at the same time! Compatible with web workers even also?
</p>
<p class="TODO">
Consider "analytic extension" of the border region, so that manual "extension" not needed for use with filters.
</p>
<p class="TODO">
Why did phong rendering break? It was working?
</p>
<h3 id="overview-mainChallenges">Main Challenges</h3>
<p>
We are trying to solve the following problems:
</p>
<ol>
<li>
Need a high-quality and high-performance way to display vector graphics (in the browser,
and natively). In particular, we would like to avoid <a href="#overview-conflation">conflation artifacts</a>,
<a href="#overview-aliasingGamma">anti-aliasing/gamma-blending issues</a>, and
<a href="#overview-gradients">gradient aliasing issues</a>
without having to resort to expensive techniques like multisampling. We'd also prefer to
<a href="#overview-color">support wide gamut display</a>, and have finer-grained control over image
<a href="#overview-upsampling">upsampling</a> and <a href="#overview-downsampling">downsampling</a>.
</li>
<li>
WebGPU/WGSL is missing a library with reusable generic parallel computation primitives (e.g. reduce/scan/sort),
and doesn't have the abstractions built-in to easily support this.
</li>
<li>
Improving the processing of vector graphics primitives to efficiently solve the occlusion/overlapping problem.
</li>
</ol>
<h4 id="overview-conflation">Conflation Artifacts</h4>
<p>
Many common approaches run into conflation artifacts (from
<span class="citation" data-citation-id="KilgardBolz2012"></span>, see
<a href="https://computergraphics.stackexchange.com/questions/1824/what-is-illustrators-vector-rasterization-process">description</a>,
<a href="https://github.com/linebender/vello/issues/49">discussion</a>, and
<a href="https://w3.impa.br/~diego/projects/GanEtAl14/sample.html?contour">examples</a>). These are graphical
glitches that occur when coverage is conflated with opacity, and happens in many common approaches (especially
with compositing). The source is treating the cases "a red path at 50% opacity fully covers the area" and
"a fully-opaque red path covers 50% of the area" as equivalent in later stages, and cases where multiple paths
precisely join along a curve may incorrectly show the background in those pixels.
</p>
<div class="row-fluid">
<div class="span4 example">
<div id="conflation-canvas"><div class="example placeholder" style="width: 128px; height: 128px;"></div></div>
Conflation artifacts (Canvas)
</div>
<div class="span4 example">
<div id="conflation-svg"><div class="example placeholder" style="width: 128px; height: 128px;"></div></div>
Conflation artifacts (SVG)
</div>
<div class="span4 example">
<div id="conflation-default"><div class="example placeholder" style="width: 128px; height: 128px;"></div></div>
No artifacts (Alpenglow CPU)
</div>
</div>
<p>
We are able to solve this problem by using a different approach based on polygonal boolean operations, where
we can get a list of polygonal faces where each input path is either fully contained or fully
excluded in each face. We can then use high-performance approaches to rasterize each face independently, then
accumulate while avoiding multisampling and conflation artifacts. Often these faces will be of constant color,
which can very efficiently be displayed (we skip the per-pixel blending with the completely-occluded background
contents).
</p>
<h4 id="overview-aliasingGamma">Aliasing & Gamma-Incorrect Blending</h4>
<p>
Aliasing is the low-frequency pattern that spuriously appears when we are displaying high-frequency content
in a lower-resolution way. In general, we want to reduce these low-frequency patterns without overly introducing
blurring. Basic anti-aliasing can help "smooth" things like the jagged edges of lines (e.g. with text), but
some approaches aren't general enough to help with other types of aliasing.
</p>
<p>
To be correct, blending should be done in the correct color spaces. Many applications choose to blend in
non-linear color spaces (e.g. sRGB), which can cause blended colors to look incorrect (usually darker).
For more information, see
<a href="https://blog.johnnovak.net/2016/09/21/what-every-coder-should-know-about-gamma/">this reference</a>.
</p>
<div class="row-fluid" style="margin-bottom: 15px;">
<div class="span2"></div>
<div class="span4 example">
<div id="checkerboard-canvas"><div class="example placeholder" style="width: 128px; height: 64px;"></div></div>
Canvas
</div>
<div class="span4 example">
<div id="checkerboard-svg"><div class="example placeholder" style="width: 128px; height: 64px;"></div></div>
SVG
</div>
<div class="span2"></div>
</div>
<div class="row-fluid" style="margin-bottom: 15px;">
<div class="span4 example">
<div id="checkerboard-box"><div class="example placeholder" style="width: 128px; height: 64px;"></div></div>
Alpenglow CPU (Box Filter)
</div>
<div class="span4 example">
<div id="checkerboard-bilinear"><div class="example placeholder" style="width: 128px; height: 64px;"></div></div>
Alpenglow CPU (Bilinear Filter)
</div>
<div class="span4 example">
<div id="checkerboard-mitchell-netravali"><div class="example placeholder" style="width: 128px; height: 64px;"></div></div>
Alpenglow CPU (Mitchell-Netravali Filter)
</div>
</div>
<p>
For instance, the above checkerboards (with 3d perspective) have smooth transitions from low to high frequency.
Note the pattern should blur to a light gray as it fades in the distance. Visible patterns are a sign of aliasing,
and darkening of the pattern is a sign of gamma-incorrect blending.
</p>
<h4 id="overview-gradients">Gradient Aliasing & Precision</h4>
<div class="row-fluid" style="margin-bottom: 15px;">
<div class="span2"></div>
<div class="span4 example">
<div id="gradients-canvas"><div class="example placeholder" style="width: 128px; height: 128px;"></div></div>
Canvas
</div>
<div class="span4 example">
<div id="gradients-svg"><div class="example placeholder" style="width: 128px; height: 128px;"></div></div>
SVG
</div>
<div class="span2"></div>
</div>
<div class="row-fluid" style="margin-bottom: 15px;">
<div class="span4 example">
<div id="gradients-box"><div class="example placeholder" style="width: 128px; height: 128px;"></div></div>
Alpenglow CPU (Box Filter)
</div>
<div class="span4 example">
<div id="gradients-bilinear"><div class="example placeholder" style="width: 128px; height: 128px;"></div></div>
Alpenglow CPU (Bilinear Filter)
</div>
<div class="span4 example">
<div id="gradients-mitchell-netravali"><div class="example placeholder" style="width: 128px; height: 128px;"></div></div>
Alpenglow CPU (Mitchell-Netravali Filter)
</div>
</div>
<p>
Gradients with color stops close together (e.g. when zoomed out in a user interface) can also create many aliasing patterns.
Alpenglow is able to compute exact analytic gradient contributions (based on the exact pixel coverage), and with
filtering added is able to produce high-quality gradients.
</p>
<div class="row-fluid" style="margin-bottom: 15px;">
<div class="span4 example">
<div id="gradientPrecision-canvas"><div class="example placeholder" style="width: 128px; height: 128px;"></div></div>
Canvas
</div>
<div class="span4 example">
<div id="gradientPrecision-svg"><div class="example placeholder" style="width: 128px; height: 128px;"></div></div>
SVG
</div>
<div class="span4 example">
<div id="gradientPrecision-box"><div class="example placeholder" style="width: 128px; height: 128px;"></div></div>
Alpenglow CPU (Box Filter)
</div>
</div>
<p>
Many gradient implementations also have issues with gradients when zoomed in, and may drop or distort gradients
in the above cases. Gradient bands should get thinner and thinner until they look like lines.
</p>
<h4 id="overview-color">Color Spaces and Wide-Gamut Support</h4>
<p>
While gamma is critical, blending in the correct color space is also important. Blending in sRGB does not produce
perceptually uniform colors. Colors should be converted to/from a color space meant for this purpose when
perceptual gradients are required. <a href="https://bottosson.github.io/posts/oklab/">Oklab</a> is great for this,
and while not yet supported in Canvas/SVG, it can be
<a href="https://developer.mozilla.org/en-US/docs/Web/CSS/color_value/oklab">used in CSS</a>.
</p>
<div class="row-fluid" style="margin-bottom: 15px;">
<div class="span6 example">
<div id="redGreenGradients-example"><div class="example placeholder" style="width: 256px; height: 96px;"></div></div>
Oklab, linear sRGB, and sRGB (top to bottom). Note the green bias in linear sRGB and darkening in sRGB. Oklab is perceptually uniform.
</div>
<div class="span6 example">
<div id="blueWhiteGradients-example"><div class="example placeholder" style="width: 256px; height: 96px;"></div></div>
Oklab, linear sRGB, and sRGB (top to bottom). Note the hue shift toward purple in the blue-white gradient for sRGB varieties. Oklab is perceptually uniform, without a hue shift.
</div>
</div>
<p>
However, when we use other color spaces like Oklab, even blends from colors inside the sRGB gamut can produce
out-of-gamut colors. To compensate for this, we will need to use gamut mapping:
</p>
<div class="row-fluid" style="margin-bottom: 15px;">
<div class="span2"></div>
<div class="span4 example">
<div id="sRGBGamutMap-example"><div class="example placeholder" style="width: 206px; height: 180px;"></div></div>
sRGB triangle with (relative colorimetric) gamut mapping
</div>
<div class="span4 example">
<div id="sRGBNoGamutMap-example"><div class="example placeholder" style="width: 206px; height: 180px;"></div></div>
sRGB triangle without gamut mapping (gray to white shows how far outside of gamut the colors are)
</div>
<div class="span2"></div>
</div>
<p>
Additionally, many monitors are now capable of displaying a wider gamut of colors than sRGB. Chrome and Safari
support the extended colors inside the <a href="https://en.wikipedia.org/wiki/DCI-P3">Display P3</a> color space.
As seen, this can be helpful even if most elements are in sRGB, however it can also be impactful to use the
bolder colors in the extended gamut. Many GPU rasterization solutions do not yet support this.
</p>
<div class="row-fluid" style="margin-bottom: 15px;" id="display-p3-container">
<div class="span2"></div>
<div class="span4 example">
<div id="displayP3GamutMap-example"><div class="example placeholder" style="width: 206px; height: 180px;"></div></div>
Display P3 triangle
</div>
<div class="span4 example">
<div id="displayP3Comparison-example"><div class="example placeholder" style="width: 206px; height: 180px;"></div></div>
sRGB (top), Display P3 (middle) and Display P3 gamut mapped to sRGB (bottom).
</div>
<div class="span2"></div>
</div>
<script>
if ( !window.matchMedia( '(color-gamut: p3)' ).matches ) {
document.querySelector( '#display-p3-container' ).style.display = 'none';
}
</script>
<p>
Hopefully soon, we will have a convenient interface to show high dynamic range (HDR) content, but Alpenglow will be able
to support it when it is available.
</p>
<h4 id="overview-upsampling">Image Upsampling</h4>
<div class="row-fluid" style="margin-bottom: 15px;">
<div class="span2"></div>
<div class="span4 example">
<div id="upsampling-canvas"><div class="example placeholder" style="width: 128px; height: 128px;"></div></div>
Canvas
</div>
<div class="span4 example">
<div id="upsampling-svg"><div class="example placeholder" style="width: 128px; height: 128px;"></div></div>
SVG
</div>
<div class="span2"></div>
</div>
<div class="row-fluid" style="margin-bottom: 15px;">
<div class="span2"></div>
<div class="span4 example">
<div id="upsampling-analytic-box"><div class="example placeholder" style="width: 128px; height: 128px;"></div></div>
Alpenglow CPU Analytic Box Filter
</div>
<div class="span4 example">
<div id="upsampling-mitchell-netravali"><div class="example placeholder" style="width: 128px; height: 128px;"></div></div>
Alpenglow CPU Mitchell-Netravali Filter
</div>
<div class="span2"></div>
</div>
<p>
Most Canvas/SVG implementations do not support upsampling with the Mitchell-Netravali ("cubic") filter, and will
blend in a gamma-incorrect way. Additionally, we are able to represent images with exact analytic filters, so
that a box filter upsampling will have nicely anti-aliased edges.
</p>
<h4 id="overview-downsampling">Image Downsampling</h4>
<div class="row-fluid" style="margin-bottom: 15px;">
<div class="span2"></div>
<div class="span4 example">
<div id="downsampling-canvas"><div class="example placeholder" style="width: 128px; height: 128px;"></div></div>
Canvas
</div>
<div class="span4 example">
<div id="downsampling-svg"><div class="example placeholder" style="width: 128px; height: 128px;"></div></div>
SVG
</div>
<div class="span2"></div>
</div>
<div class="row-fluid" style="margin-bottom: 15px;">
<div class="span4 example">
<div id="downsampling-analytic-box"><div class="example placeholder" style="width: 128px; height: 128px;"></div></div>
Alpenglow CPU (Analytic Box Filter)
</div>
<div class="span4 example">
<div id="downsampling-analytic-bilinear"><div class="example placeholder" style="width: 128px; height: 128px;"></div></div>
Alpenglow CPU (Analytic Bilinear Filter)
</div>
<div class="span4 example">
<div id="downsampling-analytic-mitchell-netravali"><div class="example placeholder" style="width: 128px; height: 128px;"></div></div>
Alpenglow CPU (Analytic Mitchell-Netravali Filter)
</div>
</div>
<p>
Image downsampling is also prone to both aliasing arifacts and gamma-incorrect blending. Many Canvas implementations
will quickly sample an image, leading to serious ringing patterns on these example images. There are many cases
where we will want to use a higher-quality downsampling algorithm, and we can compute an exact analytic filtered
result.
</p>
<p>
It is recommended to see the <a href="./doc/downscale.png">image</a> at full (1:1) size, to see how the above methods
scale the image down.
</p>
<h3 id="overview-relatedWork">Related Work</h3>
<h4>GPU Vector Graphics</h4>
<p>
<a href="https://github.com/linebender/vello">Vello</a> is the most similar project, and we've tested integration
of it <a href="https://github.com/phetsims/scenery/tree/vello">into Scenery</a>. It's the main inspiration for
this project, and we plan to use many components from it. However, it was tricky getting it to work on the web
(compiling it for WASM creates a bundle in excess of 5MB), and thus required rewriting the Rust code into TypeScript.
At the time it didn't have support for avoiding conflation artifacts, and now (as of writing) it is using a more
expensive multisampling approach to reduce the effects of conflation. Additionally, it runs into gamma blending
problems, and doesn't support additional color spaces currently. The approach we are using is different enough
that it unfortunately can't be integrated into Vello.
</p>
<p>
Other libraries that target the GPU for similar rendering include
<a href="https://github.com/servo/pathfinder">Pathfinder</a> (discontinued),
<a href="https://github.com/google/forma">Forma</a> (not under active development),
<a href="https://fuchsia.googlesource.com/fuchsia/+/refs/heads/master/src/graphics/lib/compute/spinel/">Spinel</a>,
and <a href="https://github.com/flutter/engine/tree/main/impeller">Flutter's Impeller</a>
</p>
<p>
Additionally, browsers have some built-in support for GPU-accelerated vector graphics, most notably with
<a href="https://developer.mozilla.org/en-US/docs/Web/API/Canvas_API">Canvas</a> and
<a href="https://developer.mozilla.org/en-US/docs/Web/SVG">SVG</a>. These approaches have decent performance,
but performance can be improved with the WebGPU/WebGL solutions above. Additionally, they run into the
conflation/gamma/aliasing artifacts previously described (in order to improve their performance).
</p>
<h4>Anti-Aliased Vector Graphics</h4>
<p>
For filtering-based analytic rasterization, we've explored other recent approaches, including
<span class="citation" data-citation-id="doi:10.1080/2151237X.2005.10129191"></span>,
<span class="citation" data-citation-id="doi:10.1080/2151237X.2005.10129189"></span>,
<span class="citation" data-citation-id="10.1111:cgf.12070"></span>, which could also be included/implemented.
</p>
<p>
For the general GPU processing, relevant literature is in
<span class="citation" data-citation-id="10.1145/1409060.1409088"></span>,
<span class="citation" data-citation-id="10.1145/2018323.2018337"></span>, and
<span class="citation" data-citation-id="10.1145/2661229.2661274"></span> are particularly promising, as the
inspiring approaches behind Vello.
<span class="citation" data-citation-id="GPUpathtracingSA16"></span> could also be explored.
</p>
<p>
Especially for text, many approaches look to be patent/license encumbered, most notably the Loop-Blinn approach
<span class="citation" data-citation-id="loop2005resolution"></span> (with <a href="https://developer.nvidia.com/gpugems/gpugems3/part-iv-image-effects/chapter-25-rendering-vector-art-gpu">notes</a>).
The <a href="https://sluglibrary.com/">Slug</a> library seems like the go-to solution for games, backed by
<span class="citation" data-citation-id="Lengyel2017FontRendering"></span>.
Signed distance fields like in
<span class="citation" data-citation-id="10.1145/1281500.1281665"></span> and
<span class="citation" data-citation-id="MCDF"></span> lose too much accuracy for our purposes,
however there are examples of <a href="https://www.shadertoy.com/view/4sKyzW">exact Cubic beziers</a> with SDFs
which can <a href="https://www.shadertoy.com/view/4sySDK">render text</a>. There are also a few approaches using
circular window approaches:
<a href="https://wdobbie.com/post/gpu-text-rendering-with-vector-textures/">A</a> and
<a href="https://gasiulis.name/vector-graphics-on-gpu/">B</a>.
</p>
<h4>WebGPU</h4>
<p>
High quality libraries for the CUDA interface to GPUs exist, and this work is inspired by
<a href="https://github.com/NVIDIA/cccl">Thrust</a> <span class="citation" data-citation-id="BELL2012359"></span>
and <a href="https://github.com/moderngpu/moderngpu/wiki">moderngpu</a>
<span class="citation" data-citation-id="Baxter:2016:M2"></span>. They serve as prime examples of useful patterns,
but can't target WebGPU. In addition, many algorithms rely in forward progress or workgroup communication that
WebGPU doesn't offer (in an effort for portability), so we will need to explore new approaches.
</p>
<p>
There are also good shader generation systems, but which don't target WebGPU. Notably
<a href="https://github.com/shader-slang/slang">Slang</a>
<span class="citation" data-citation-id="10.1145/3197517.3201380"></span>
<span class="citation" data-citation-id="bangaru2023slangd"></span>.
</p>
<p>
<a href="https://usegpu.live/">Use.GPU</a> takes a novel approach with WebGPU, but focuses on rendering instead of
the compute primitives.
</p>
<h3 id="overview-contributions">Contributions</h3>
<p>
Current contributions:
</p>
<ul>
<li>
New approach to solving 2D occlusion/overlapping with computational geometry at the start of the rasterization
process. Based on our previous work for PhET's <a href="https://github.com/phetsims/kite">computational geometry library</a>,
we are able to compute the overlap for many general regions at the same time (but using line segments with
rational values for exact intersections and robustness).
</li>
<li>
New approach to anti-aliasing with filters (evaluating arbitrary polynomial integrals over polygons, based on
Green's Theorem). It's efficient (allows bilinear filtering with minimal performance burden), and compatible
with other future segment types (quadratic/cubic Bezier curves, elliptical arcs, etc.).
This also allows <a href="#antialiasing-examples">computing exact blurs</a>.
</li>
<li>
New approach to <a href="#depthSort">3D graphics (using the above)</a>, where we compute (exact vector)
occlusion and some perspective-corrected exact integrals (for barycentric-based coordinates on triangular meshes).
</li>
<li>
New approach to recursive clipping of polygons, particularly with the ability to handle degenerate cases
in a compact fashion on a GPU.
</li>
<li>
Initial work for generating WGSL for high-performance computational primitives in generic form (reduce,
prefix sum, radix sort, merge sort, stream compaction, etc.).
</li>
<li>
New approach to <a href="#asyncSimulation">simulating the WebGPU execution model</a> with TypeScript async/await
patterns (for evaluation of race conditions, uniformity, indeterminate behavior, etc.).
</li>
</ul>
<p>
Planned contributions:
</p>
<ul>
<li>
High-performance WebGPU implementation of the Alpenglow strategy, including the preceding stages (for
transformation, conversion to line segments, etc.)
</li>
<li>
Library for generic parallel computation primitives (using code generation/templating with WGSL, or potentially
extending WGSL to a new language with templating support).
</li>
<li>
Full integration of Alpenglow WebGPU into <a href="https://github.com/phetsims/scenery">Scenery</a> (as a renderer) and
PhET simulations.
</li>
<li>
Further exploration of 3D rasterization using this approach, including general (exact!) perspective-corrected
integrals across triangles when displayed.
</li>
<li>
Canvas API replacement that supports a fully vector-based description of the current Canvas state (same
drawing commands, but can be resized/queried and has an underling vector representation). Should be able to do
this in a high-performance way where we will have the quality of Alpenglow. Drawing over parts of the Canvas
will "merge" vector regions into one where appropriate, so we can have a finite-memory representation of the
state after an arbitrary number of drawing commands.
</li>
<li>
Static SVG to Alpenglow converter, which will transform SVG files into Alpenglow render programs for display.
</li>
<li>
Extension of the Alpenglow approach to additional curve types (hopefully in a robust way). Intersections for
quadratic/cubic Bezier curves and elliptical arcs present some robustness problems. I would like to investigate
rationally-based curves with rational sections (looking into
<span class="citation" data-citation-id="Wildberger2005"></span>) to see if we can extend the robust approach.
</li>
</ul>
<h3 id="overview-impact">Desired Impact</h3>
<p>
Ideally, Alpenglow would be able to replace the usage of Canvas/SVG (and some WebGL) for the purpose of displaying
interactive graphics and UI, both in <a href="https://phet.colorado.edu/">PhET Interactive Simulations</a> and in other projects.
Canvas API integration could be a drop-in replacement for existing Canvas usage, with higher-quality output.
</p>
<p>
In addition, since the target is to rely on WebGPU, it would be possible to run the same code in native applications
(using <a href="https://dawn.googlesource.com/dawn">Dawn</a> or <a href="https://wgpu.rs/">WGPU</a>),
or possibly at the OS level. This could be potentially useful for rendering native UIs, or anything that needs
scale-independent high-quality graphics.
</p>
<p>
It would also allow <a href="https://github.com/phetsims/scenery">Scenery</a> to be a higher-performance solution
for interactive graphics and user interfaces on the web, especially in an accessibility-compatible way.
</p>
<h2 id="concepts">Concepts</h2>
<h3 id="polygonalFaces">Polygonal Faces</h3>
<p>
Polygonal faces are used pervasively throughout Alpenglow. In general, our data structures are designed to support
<a href="https://en.wikipedia.org/wiki/Polygon_with_holes">polygons with holes</a>, and more generally, the
primitive is a "list of polygons". An example is the following diagram, which can be stored in different ways:
</p>
<div class="example">
<div id="polygonal-face-example"><div class="example placeholder" style="width: 256px; height: 256px;"></div></div>
</div>
<p>
All of the storage representations below conform to the <code>ClippableFace</code> interface in the software
implementation.
</p>
<h4>Polygonal Form</h4>
<p>
It can be represented in the polygonal form as three (directed) lists of vertices (with a <a href="https://en.wikipedia.org/wiki/Nonzero-rule">nonzero winding rule</a>):
</p>
<p>
(0, 0),
(10, 0),
(10, 2),
(2, 10),
(0, 10)
<br>
(2, 2),
(2, 7),
(7, 2)
<br>
(9, 9),
(6, 9),
(9, 6)
</p>
<p>
where there is a line (edge) between each consecutive pair of vertices, and the last vertex is connected to the
first vertex. This is compact, however the order is critical. This can cause certain operations (e.g. circular
clipping, some tracing) to be slower than other methods. This is handled by <code>PolygonalFace</code> in the
software implementation.
</p>
<h4>Edge Form</h4>
<p>
For much of Alpenglow's needs, things work better if we consider the list of edges itself (with start/end vertices):
</p>
<p>
(0, 0) => (10, 0),
(10, 0) => (10, 2),
(10, 2) => (2, 10),
(2, 10) => (0, 10),
(0, 10) => (0, 0)
(2, 2) => (2, 7),
(2, 7) => (7, 2),
(7, 2) => (2, 2)
(9, 9) => (6, 9),
(6, 9) => (9, 6),
(9, 6) => (9, 9)
</p>
<p>
Now, for most critical operations, order doesn't matter, and each edge can be considered in isolation.
We won't need to sort things during/after operations, but also certain operations might need to generate more
edges that get canceled out (whereas with polygonal data, we could detect it and simplify in higher-performance
ways). This form is handled by <code>EdgedFace</code> in the software implementation.
</p>
<h4>Degenerate Edges</h4>
<p>
Additionally, we can actually construct this with an equivalent single (degenerate) polygon. Since we only care
about the filled area, it turns out that edges that "reverse" over each other won't contribute to the filled area,
so we can double-back. Thus the following diagram:
</p>
<div class="example">
<div id="polygonal-face-canceling"><div class="example placeholder" style="width: 256px; height: 256px;"></div></div>
</div>
<p>
can be constructed with an equivalent area with the following polygon:
</p>
<p>
(0, 0),
(10, 0),
(10, 2),
(7, 2),
(2, 2),
(2, 7),
(6, 9),
(9, 6),
(9, 9),
(6, 9),
(2, 7),
(7, 2),
(10, 2),
(2, 10),
(0, 10)
</p>
<h4>Edge-Clipped Form</h4>
<p>
It turns out, for computational complexity of future clipping operations (see below), it is very helpful to NOT
directly store the edges that go along the full edge of the clipping rectangle (e.g. the 0,0 to 10,10 region in
the diagram). Instead, those edges will be counted. Due to the property above of degenerate edges, these counts
can be added together to add the contribution of these "clipped" edges.
</p>
<p>
The diagram below shows the edge orientations that get positive (+1) counts. Reversed edges will get negative (-1)
counts:
</p>
<div class="example">
<div id="polygonal-face-edge-clips"><div class="example placeholder" style="width: 256px; height: 256px;"></div></div>
</div>
<p>
Thus the edge-clipped version (for the 0,0 to 10,10 bounds) will have the following edges and counts:
</p>
<div class="example">
<div id="polygonal-face-edge-clipped"><div class="example placeholder" style="width: 256px; height: 256px;"></div></div>
</div>
<p>
(10, 0) => (10, 2),
(10, 2) => (2, 10),
(2, 10) => (0, 10),
(2, 2) => (2, 7),
(2, 7) => (7, 2),
(7, 2) => (2, 2)
(9, 9) => (6, 9),
(6, 9) => (9, 6),
(9, 6) => (9, 9)
</p>
<p>
This is handled by the <code>EdgedClippedFace</code> in the software implementation.
</p>
<p class="TODO">
Create "Bounds Pyramid" immutable data structure. It's a binary tree, leaves are edges. Each level stores the
bounding box. PIP-tests are VERY accelerated on this. Clipping also potentially will be (if a node is fully within
one side of a binary clip, we can just INCLUDE that node). Thus we will have a linked list way of describing how
the nodes connect (so we can reuse parts of the source within the result). At a certain point, this will be less
beneficial, but high-up it might be very helpful? Test PIP and clipping with this. (each section has bounds and
children). Linked list so we can store "sequences" immutably, that don't get changed.
</p>