-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathcs488.html
More file actions
1232 lines (1232 loc) · 76.3 KB
/
cs488.html
File metadata and controls
1232 lines (1232 loc) · 76.3 KB
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 xmlns="http://www.w3.org/1999/xhtml" lang="" xml:lang="">
<head>
<meta charset="utf-8" />
<meta name="generator" content="pandoc" />
<meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=yes" />
<title>cs488</title>
<style type="text/css">
code{white-space: pre-wrap;}
span.smallcaps{font-variant: small-caps;}
span.underline{text-decoration: underline;}
div.column{display: inline-block; vertical-align: top; width: 50%;}
</style>
<style type="text/css">
a.sourceLine { display: inline-block; line-height: 1.25; }
a.sourceLine { pointer-events: none; color: inherit; text-decoration: inherit; }
a.sourceLine:empty { height: 1.2em; }
.sourceCode { overflow: visible; }
code.sourceCode { white-space: pre; position: relative; }
div.sourceCode { margin: 1em 0; }
pre.sourceCode { margin: 0; }
@media screen {
div.sourceCode { overflow: auto; }
}
@media print {
code.sourceCode { white-space: pre-wrap; }
a.sourceLine { text-indent: -1em; padding-left: 1em; }
}
pre.numberSource a.sourceLine
{ position: relative; left: -4em; }
pre.numberSource a.sourceLine::before
{ content: attr(title);
position: relative; left: -1em; text-align: right; vertical-align: baseline;
border: none; pointer-events: all; display: inline-block;
-webkit-touch-callout: none; -webkit-user-select: none;
-khtml-user-select: none; -moz-user-select: none;
-ms-user-select: none; user-select: none;
padding: 0 4px; width: 4em;
color: #aaaaaa;
}
pre.numberSource { margin-left: 3em; border-left: 1px solid #aaaaaa; padding-left: 4px; }
div.sourceCode
{ }
@media screen {
a.sourceLine::before { text-decoration: underline; }
}
code span.al { color: #ff0000; font-weight: bold; } /* Alert */
code span.an { color: #60a0b0; font-weight: bold; font-style: italic; } /* Annotation */
code span.at { color: #7d9029; } /* Attribute */
code span.bn { color: #40a070; } /* BaseN */
code span.bu { } /* BuiltIn */
code span.cf { color: #007020; font-weight: bold; } /* ControlFlow */
code span.ch { color: #4070a0; } /* Char */
code span.cn { color: #880000; } /* Constant */
code span.co { color: #60a0b0; font-style: italic; } /* Comment */
code span.cv { color: #60a0b0; font-weight: bold; font-style: italic; } /* CommentVar */
code span.do { color: #ba2121; font-style: italic; } /* Documentation */
code span.dt { color: #902000; } /* DataType */
code span.dv { color: #40a070; } /* DecVal */
code span.er { color: #ff0000; font-weight: bold; } /* Error */
code span.ex { } /* Extension */
code span.fl { color: #40a070; } /* Float */
code span.fu { color: #06287e; } /* Function */
code span.im { } /* Import */
code span.in { color: #60a0b0; font-weight: bold; font-style: italic; } /* Information */
code span.kw { color: #007020; font-weight: bold; } /* Keyword */
code span.op { color: #666666; } /* Operator */
code span.ot { color: #007020; } /* Other */
code span.pp { color: #bc7a00; } /* Preprocessor */
code span.sc { color: #4070a0; } /* SpecialChar */
code span.ss { color: #bb6688; } /* SpecialString */
code span.st { color: #4070a0; } /* String */
code span.va { color: #19177c; } /* Variable */
code span.vs { color: #4070a0; } /* VerbatimString */
code span.wa { color: #60a0b0; font-weight: bold; font-style: italic; } /* Warning */
</style>
<link rel="stylesheet" href="../pandoc.css" />
<script src="https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.9.0/katex.min.js"></script>
<script>document.addEventListener("DOMContentLoaded", function () {
var mathElements = document.getElementsByClassName("math");
for (var i = 0; i < mathElements.length; i++) {
var texText = mathElements[i].firstChild;
if (mathElements[i].tagName == "SPAN") { katex.render(texText.data, mathElements[i], { displayMode: mathElements[i].classList.contains("display"), throwOnError: false } );
}}});</script>
<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.9.0/katex.min.css" />
<!--[if lt IE 9]>
<script src="//cdnjs.cloudflare.com/ajax/libs/html5shiv/3.7.3/html5shiv-printshiv.min.js"></script>
<![endif]-->
</head>
<body>
<h1 id="cs-488-exam-review">CS 488 (Exam Review)</h1>
<blockquote>
<p>No shader questions, probably no coding questions. Set of <a href="https://www.student.cs.uwaterloo.ca/~cs488/Fall2019/q.pdf">Sample Exam Questions</a>, likely that a few appear on the exam. Questions that have not showed up on an exam in a long time are less likely to be asked.</p>
</blockquote>
<ol start="2" type="1">
<li>History (Nothing).</li>
<li>Devices (Nothing).</li>
<li>Device Interfaces (Nothing).</li>
<li><a href="#geometries"><strong>Geometries</strong></a> (Won’t be tested in depth).</li>
<li><a href="#affine-geometries-transformations"><strong>Affine Geometries & Transformations</strong></a>.</li>
<li><a href="#windows-viewports-ndc"><strong>Windows, Viewports, NDC</strong></a>.</li>
<li><a href="#line-clipping"><strong>Line Clipping</strong></a>.</li>
<li><a href="#projections"><strong>Projections</strong></a>.</li>
<li>A2 (Nothing).</li>
<li><a href="#polygons"><strong>Polygons</strong></a>.
<ul>
<li>At least clipping, scan conversion (concept).</li>
</ul></li>
<li><a href="#hidden-surface-removal"><strong>Hidden Surface Removal</strong></a>.
<ul>
<li>Backface Culling, Painter’s Algorithm, Warnock, Z-Buffer.</li>
</ul></li>
<li><a href="#hierarchical-models-transformations"><strong>Hierarchical Models & Transformations</strong></a>.</li>
<li><a href="#rotations-about-arbitrary-axis"><strong>Rotations About Arbitrary Axis</strong></a>.
<ul>
<li>Focused on Euler vs. Trackball.</li>
</ul></li>
<li>Picking (Nothing)</li>
<li><a href="#colour"><strong>Colour</strong> (Minor things)</a>.</li>
<li><a href="#lighting"><strong>Lighting</strong></a>.
<ul>
<li>Diffuse, Specular.</li>
</ul></li>
<li><a href="#shading"><strong>Shading</strong></a>.
<ul>
<li>Flat, Gouraud, Phong.</li>
</ul></li>
<li>Graphics Hardware (Nothing).</li>
<li>++ <a href="#ray-tracing"><strong>Ray Tracing</strong></a> ++
<ul>
<li>Around 30% of the exam.</li>
<li>Shadows, CSG, Texture / Bump Mapping.</li>
</ul></li>
<li><a href="#aliasing"><strong>Aliasing</strong></a>.</li>
<li><a href="#bidirectional-ray-tracing"><strong>Bidirectional Tracing</strong> (Not tested in depth)</a>.</li>
<li><a href="#radiosity"><strong>Radiosity</strong> (Not tested in depth)</a>.</li>
<li><a href="#photon-mapping"><strong>Photon Mapping</strong> (Not tested in depth)</a>.</li>
<li><a href="#25"><strong>Shadows, Projective, Shadow Maps, Volumes</strong> (Not tested in depth)</a>.</li>
<li><a href="#modelling-stuff"><strong>Modelling Stuff</strong> (Short answers only if anything)</a>.</li>
<li>Polyhedral Data Structures (Nothing).</li>
<li><a href="#splines-de-casteljaus-algorithm"><strong>Splines, De Casteljau’s Algorithm</strong> (Lightly tested)</a>.
<ul>
<li>Know De Casteljau’s.</li>
</ul></li>
<li><a href="#non-photorealistic-rendering"><strong>Non-Photorealistic Rendering</strong> (Very lightly tested)</a>.</li>
<li>Volume Rendering (Nothing).</li>
<li><a href="#animation"><strong>Animation</strong> (Might be short questions)</a>.</li>
<li>Computational Geometry (Nothing).</li>
</ol>
<h2 id="geometries">Geometries</h2>
<h3 id="vector-spaces">Vector Spaces</h3>
<blockquote>
<p>Set of vectors <span class="math inline">V</span> with two operations.</p>
</blockquote>
<ol type="1">
<li><strong>Addition</strong>: <span class="math inline">u + v \in V</span>.</li>
<li><strong>Scalar Multiplication</strong>: <span class="math inline">\alpha v \in V</span>, where <span class="math inline">\alpha</span> is a member of some field <span class="math inline">\mathbb{F}</span>.</li>
</ol>
<p><strong>Axioms</strong>.</p>
<ul>
<li><strong>Addition Commutes</strong>: <span class="math inline">u + v = v + u</span>.</li>
<li><strong>Addition Associates</strong>: <span class="math inline">(u + v) + w = u + (v + w)</span>.</li>
<li><strong>Scalar Multiplication Distributes</strong>: <span class="math inline">\alpha(u + v) = \alpha u + \alpha v</span>.</li>
<li><strong>Unique Zero Elements</strong>: <span class="math inline">0 + u = u</span>.</li>
<li><strong>Field Unit Element</strong>: <span class="math inline">1 u = u</span>.</li>
</ul>
<h3 id="span">Span</h3>
<p>Suppose <span class="math inline">B = \{v_1, v_2, ..., v_n\}</span>. <span class="math inline">B</span> <strong>spans</strong> <span class="math inline">V</span> if and only if any <span class="math inline">v \in V</span> can be written as <span class="math inline">v = \sum_{i=1}^n \alpha_i v_i</span> (<strong>linear combination</strong> of the vectors in <span class="math inline">B</span>).</p>
<ul>
<li>Any minimal spanning set is a basis. All bases are the same size.</li>
<li>The number of vectors in any basis is the <strong>dimension</strong>.</li>
</ul>
<h3 id="affine-spaces">Affine Spaces</h3>
<blockquote>
<p>Now we use a set of points <span class="math inline">P</span> in addition to the set of vectors <span class="math inline">V</span>.</p>
</blockquote>
<ul>
<li>Points can be combined with vectors to make new points. <span class="math inline">P + v \to Q</span>, with <span class="math inline">P, Q \in P</span> and <span class="math inline">v \in V</span>.</li>
<li>Basis now requires an affine extension. <strong>Frame</strong> is a vector basis plus a point <span class="math inline">O</span> (<strong>origin</strong>), with the same dimension as the basis.</li>
</ul>
<p><strong>Inner Product Spaces</strong>: Binary operator which is commutative, associative, scalar multiplication distributes, <span class="math inline">u \cdot u \ge 0</span> if and only if <span class="math inline">u = 0</span>.</p>
<h3 id="euclidean-spaces">Euclidean Spaces</h3>
<p><strong>Metric Space</strong>: Space with a <strong>distance metric</strong> <span class="math inline">d(P, Q)</span> defined. Requires distance be non-negative, zero if and only if the points are identical, commutative, and satisfy triangle inequality.</p>
<p><strong>Euclidean Space</strong>: Metric space based on a dot (inner) product, <span class="math inline">d^2(P, Q) = (P - Q) \cdot (P - Q)</span>.</p>
<ul>
<li><strong>Norm</strong>: <span class="math inline">|u| = \sqrt{u \cdot u}</span>.</li>
<li><strong>Angle</strong>: <span class="math inline">cos(\angle u v) = \frac{u \cdot v}{|u||v|}</span>.</li>
<li><strong>Perpendicularity</strong>: <span class="math inline">u \cdot v = 0 \Rightarrow u \perp v</span>. Perpendicularity is not an affine concept.</li>
</ul>
<h3 id="cartesian-space">Cartesian Space</h3>
<p>An Euclidean Space with a standard <strong>orthonormal frame</strong> <span class="math inline">(i, j, k, O)</span>.</p>
<ul>
<li><strong>Orthogonal</strong>: <span class="math inline">i \cdot j = j \cdot k = k \cdot i = 0</span>.</li>
<li><strong>Normal</strong>: <span class="math inline">|i| = |j| = |k| = 1</span>.</li>
</ul>
<blockquote>
<p>For notation, we specify the <strong>Standard Frame</strong> <span class="math inline">F_s = (i, j, k, O)</span>.</p>
</blockquote>
<p>Since points and vectors are different objects with different operations and behave differently under transformations how do we handle them?</p>
<p><strong>Coordinates</strong>: We use an <em>extra coordinate</em>.</p>
<ul>
<li><span class="math inline">v = (v_x, v_y, v_z, 0)</span>.</li>
<li><span class="math inline">P = (p_x, p_y, p_z, 1)</span>.</li>
</ul>
<h3 id="why-do-we-need-affine-spaces">Why Do We Need Affine Spaces?</h3>
<ul>
<li>No metric, but we can add a metric to vector space.</li>
<li>We want to represent objects efficiently, and we want to be able to translate, rotate, scale our objects in their representation. This is difficult to do with vectors.
<ul>
<li>For example, suppose we represent a position by the sum of two vectors. We cannot naively apply a translation to both vectors to translate the position.</li>
</ul></li>
</ul>
<h2 id="affine-geometries-transformations">Affine Geometries & Transformations</h2>
<h3 id="linear-combinations">Linear Combinations</h3>
<ul>
<li>Vector-Vector addition.</li>
<li><span class="math inline">T(u + v) = T(u) + T(v)</span>. T(u) = T(u).</li>
<li>Point-Vector addition.</li>
</ul>
<h3 id="affine-combinations">Affine Combinations</h3>
<ul>
<li><strong>Point Subtraction</strong>: <span class="math inline">Q - P = v \in V</span> such that <span class="math inline">Q = P + v</span>, for <span class="math inline">P, Q \in P</span>. So <span class="math inline">\sum a_i P_i</span> is a vector if and only if <span class="math inline">\sum a_i = 0</span>.</li>
<li><strong>Point Blending</strong>: <span class="math inline">Q = (1 - \alpha)Q_1 + \alpha Q_2</span> such that <span class="math inline">Q = Q_1 + \alpha(Q_2 - Q_1) \in P</span>. So <span class="math inline">\sum a_i P_i</span> is a point if and only if <span class="math inline">\sum a_i = 1</span>.
<ul>
<li><span class="math inline">\frac{|Q - Q_1|}{|Q - Q_2|} = \frac{1 - \alpha}{\alpha}</span>.</li>
</ul></li>
<li>So when combining points, the result is a point if the coefficients sum to <span class="math inline">1</span>, and the result is a vector if the coefficients sum to <span class="math inline">0</span>.</li>
</ul>
<h3 id="affine-transformations">Affine Transformations</h3>
<p>Let <span class="math inline">T: A_1 \to A_2</span>, where <span class="math inline">A_1, A_2</span> are affine spaces.</p>
<ul>
<li><span class="math inline">T</span> maps vectors to vectors and points to points.</li>
<li><span class="math inline">T</span> is a linear trasformation on the vectors.</li>
<li><span class="math inline">T(P + u) = T(P) + T(u)</span>, where <span class="math inline">P \in P</span>, <span class="math inline">v \in V</span>.</li>
</ul>
<p>Then <span class="math inline">T</span> is an affine transformation. Preserves affine combinations on the points.</p>
<p>Suppose <span class="math inline">T</span> is only defined on <span class="math inline">P</span>. Then <span class="math inline">T(v) = T(Q) - T(R)</span>, where <span class="math inline">v = Q - R</span>.</p>
<h3 id="mapping-through-an-affine-transformation">Mapping Through an Affine Transformation</h3>
<p>Let <span class="math inline">A, B</span> be affine spaces, with <span class="math inline">T: A \to B</span> be an affine transformation. Let <span class="math inline">F_A = (v_1, v_2, O_v)</span> be a frame for <span class="math inline">A</span>, let <span class="math inline">F_B = (w_1, w_2, O_w)</span> be a frame for <span class="math inline">B</span>. Let<span class="math inline">P</span> be a point in <span class="math inline">A</span> whose <em>coordinates</em> relative to <span class="math inline">F_A = (p_1, p_2, 1)</span>. What are the coordinates <span class="math inline">(p_1^\prime, p_2^\prime, 1)</span> of <span class="math inline">T(P)</span> relative to frame <span class="math inline">F_B</span>?</p>
<p><span class="math inline">\begin{aligned} T(P) &= T(p_1 v_1 + p_2 v_2 + O_v) \\ &= p_1T(v_1) + p_2 T(v_2) + T(O_v) \\ \end{aligned}</span></p>
<h3 id="geometric-transformations">Geometric Transformations</h3>
<ul>
<li><strong>Rotation</strong>: <span class="math inline">\begin{bmatrix}\cos(\theta) & -\sin(\theta) & 0 \\ \sin(\theta) & \cos(\theta) & 0\\ 0 & 0 & 1\end{bmatrix}</span>.</li>
<li><strong>Shear</strong>: <span class="math inline">\begin{bmatrix}1 & \beta & 0 \\ \alpha & 1 & 0\\ 0 & 0 & 1\end{bmatrix}</span>.</li>
<li>Translation is a shear in the next dimension.</li>
</ul>
<h3 id="change-of-basis">Change of Basis</h3>
<p>Suppose we want to change coordinates relative to <span class="math inline">F_1</span> to coordinates relative to <span class="math inline">F_2</span>. We know that <span class="math inline">P = [x, y, 1]^T</span> relative to <span class="math inline">F_1 = (w_1, w_2, O_w)</span>. Solve <span class="math inline">F_1 = F_2 M_{1, 2}</span>.</p>
<ul>
<li>When <span class="math inline">F_2</span> is orthonormal, <span class="math inline">f_{i,j} = w_j \cdot v_i</span>, <span class="math inline">f_{i,3} = (O_w - O_v) \cdot v_i</span>.</li>
<li>Points “mapped” by a change of basis do not change, they are just represented in a different frame.</li>
<li>To fully specify a transformation, we need a matrix, a domain space, a range space, and a coordinate frame in each space.</li>
</ul>
<h3 id="world-and-viewing-frames">World and Viewing Frames</h3>
<ul>
<li>Standard frame is the <strong>world frame</strong>.</li>
<li>Viewer may be anywhere and looking anywhere. Specified as <span class="math inline">z, y</span> with <span class="math inline">z</span> as the <strong>view direction</strong> and <span class="math inline">z</span> is the <strong>up vector</strong>.</li>
<li>We change basis from the world frame to the viewers frame.</li>
</ul>
<p>After we are in viewing coordinates, we place a clipping box around the scene relative to the viewing frame.</p>
<ul>
<li>The screen is 2D, so an <strong>orthographic projection</strong> is made by removing the z-coordinate.</li>
</ul>
<h3 id="transforming-normals">Transforming Normals</h3>
<ul>
<li>Consider a non-uniform scale of a circle and the effect on the normal vector. The normal vector will be scaled as well which is incorrect.</li>
<li>This is because normal vectors are <strong>not</strong> the difference in points.
<ul>
<li>But tangent vectors <strong>are</strong>, and normals are vectors perpendicular to all tangents at a point.</li>
<li>We can prove we should transform normals by the inverse transpose of the linear part of the transformation (upper 3 x 3 submatrix).</li>
<li>This is only an issue if there is a non-uniform scale or a shear transformation.</li>
</ul></li>
</ul>
<h2 id="windows-viewports-ndc">Windows, Viewports, NDC</h2>
<ul>
<li><strong>Window</strong>: Rectangular area of interest in the scene.</li>
<li><strong>Viewport</strong>: Rectangular region on device.</li>
</ul>
<p>Window to Viewport mapping is simple a scale based on the ratios and an offset based on their positions.</p>
<ul>
<li>When the ratios between the heights and lengths of the two regions are not the same, the image will be distorted.</li>
</ul>
<h3 id="normalized-device-coordinates">Normalized Device Coordinates</h3>
<p>We want to specify the viewport in a generalized way so that it works on all plaforms / devices. So we use <strong>Normalized Device Coordinates</strong> as an intermediate coordinate system.</p>
<h2 id="line-clipping">Line Clipping</h2>
<p><strong>Clipping</strong> is removing points outside a region of interest.</p>
<ul>
<li><strong>Point clipping</strong>: Points are either entirely inside the region or not.</li>
<li><strong>Line clipping</strong>: Halfspaces can be combined to bound a convex region.
<ul>
<li>Liang-Barsky algorithm efficiently clips line segments to a halfspace.</li>
<li>When a line segment is parially inside and partially outside a halfspace, we generate a new line to represent the part inside.</li>
</ul></li>
</ul>
<div class="sourceCode" id="cb1"><pre class="sourceCode python"><code class="sourceCode python"><a class="sourceLine" id="cb1-1" title="1"><span class="cf">for</span> P, n <span class="kw">in</span> edges: <span class="co"># Halfspaces</span></a>
<a class="sourceLine" id="cb1-2" title="2"> wecA <span class="op">=</span> dot(A <span class="op">-</span> P, n)</a>
<a class="sourceLine" id="cb1-3" title="3"> wecB <span class="op">=</span> dot(B <span class="op">-</span> P, n)</a>
<a class="sourceLine" id="cb1-4" title="4"></a>
<a class="sourceLine" id="cb1-5" title="5"> <span class="cf">if</span> wecA <span class="op"><</span> <span class="dv">0</span> <span class="kw">and</span> wecB <span class="op"><</span> <span class="dv">0</span>:</a>
<a class="sourceLine" id="cb1-6" title="6"> reject <span class="co"># Outside</span></a>
<a class="sourceLine" id="cb1-7" title="7"> <span class="cf">if</span> wecA <span class="op">>=</span> <span class="dv">0</span> <span class="kw">and</span> wecB <span class="op">>=</span> <span class="dv">0</span>:</a>
<a class="sourceLine" id="cb1-8" title="8"> <span class="bu">next</span> <span class="co"># Inside</span></a>
<a class="sourceLine" id="cb1-9" title="9"></a>
<a class="sourceLine" id="cb1-10" title="10"> t <span class="op">=</span> wecA <span class="op">/</span> (wecA <span class="op">-</span> wecB)</a>
<a class="sourceLine" id="cb1-11" title="11"></a>
<a class="sourceLine" id="cb1-12" title="12"> <span class="cf">if</span> wecA <span class="op"><</span> <span class="dv">0</span>:</a>
<a class="sourceLine" id="cb1-13" title="13"> A <span class="op">=</span> A <span class="op">+</span> t <span class="op">*</span> (B <span class="op">-</span> A)</a>
<a class="sourceLine" id="cb1-14" title="14"> <span class="cf">else</span>:</a>
<a class="sourceLine" id="cb1-15" title="15"> B <span class="op">=</span> A <span class="op">+</span> t <span class="op">*</span> (B <span class="op">-</span> A)</a></code></pre></div>
<h2 id="projections">Projections</h2>
<h3 id="perspective-projection">Perspective Projection</h3>
<ul>
<li>Identify all points with a line through the eyepoint.</li>
<li>Take intersection with viewing plane as projection.</li>
<li>This is <strong>not</strong> an affine transformation, but a perspective projection.</li>
<li>Angles and distances are not preserved, but they are not preserved under affine transformations.</li>
<li>Ratios of distances are not preserved, affine combinations are not preserved.</li>
<li>Straight lines are mapped to straight lines.</li>
<li><em>Cross</em> ratios are preserved. <span class="math inline">\frac{|AC| / |CD}{|AB| / |BC|}</span>.</li>
<li>Compared to affine transformations, they require 1 extra point or vector <span class="math inline">(n + 2)</span> to define a projection map in <span class="math inline">n</span> dimensional space.</li>
</ul>
<h3 id="perspective-map">Perspective Map</h3>
<blockquote>
<p>For projection plane <span class="math inline">z = d</span>.</p>
</blockquote>
<ul>
<li>By similar triangles, <span class="math inline">P = \left(\frac{xd}{z}, \frac{yd}{z}, d\right)</span></li>
<li>We need to know what is in front, which is impossible because the map loses <span class="math inline">z</span> information.</li>
<li><span class="math inline">\begin{bmatrix}1 & 0 & 0 & 0 \\0 & 1 & 0 & 0\\0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix}\begin{bmatrix}x \\y\\z\\1\end{bmatrix} = \begin{bmatrix}x\\y\\z+1\\z\end{bmatrix}</span> maps <span class="math inline">x, y</span> to <span class="math inline">\frac{x}{z}, \frac{y}{z}</span>, and maps <span class="math inline">z</span> to <span class="math inline">1 + \frac{1}{z}</span>. So we retain depth information.</li>
<li><span class="math inline">\begin{bmatrix}1 & 0 & 0 & 0 \\0 & 1 & 0 & 0\\0 & 0 & \frac{f+n}{f-n} & \frac{-2fn}{f-n} \\ 0 & 0 & 1 & 0 \end{bmatrix}\begin{bmatrix}x \\y\\z\\1\end{bmatrix} = \begin{bmatrix}x\\y\\\frac{z(f + n) - 2fn}{f - n}\\z\end{bmatrix}</span> is used for mapping the near and far clipping planes to <span class="math inline">[-1, 1]</span>.</li>
<li>When fov-y is given, we need to include this in the matrix as <span class="math inline">\cot(\theta / 2)</span>.</li>
</ul>
<h3 id="d-clipping">3D Clipping</h3>
<ul>
<li>We should clip the near plane <strong>before</strong> projection to avoid divide by 0.</li>
<li>Clipping to other planes <em>could</em> be done before projection but it is easier to clip after projection because we will have a cube instead of the truncated viewing pyramid.</li>
</ul>
<h2 id="polygons">Polygons</h2>
<blockquote>
<p>Area primitive.</p>
</blockquote>
<ul>
<li>Simple polygon is planar set of ordered points, no holes, no crossing.</li>
<li>Convention is to have points ordered in counter-clockwise order, so we have a defined interior and exterior.</li>
<li>Affine transformations may introduce degeneracies. Orthographic projection may project entire polygon to a line segment.</li>
</ul>
<h3 id="polygon-clipping">Polygon Clipping</h3>
<ul>
<li>Window must be a convex polygon. Polygon to be clipped does not need to be convex.</li>
<li>Given a polygon represented as <span class="math inline">v_1,..., v_n</span>, we process all polygon edges in succession against a window edge, <span class="math inline">w_1, ..., w_n</span>. Repeat for every window edge.</li>
</ul>
<p><strong>Algorithm</strong>: Four cases to consider.</p>
<ol type="1">
<li>Polygon edge is entirely inside the window edge.</li>
<li>Polygon edge crosses window edge going out.
<ul>
<li>Intersection point <span class="math inline">i</span> is the next vertex of the resulting polygon.</li>
</ul></li>
<li>Polygon edge is entirely outside the window edge.
<ul>
<li>No output.</li>
</ul></li>
<li>Polygon edge crosses window going in.
<ul>
<li>Intersection point <span class="math inline">i</span> and <span class="math inline">p</span> are the next two vertices of the resulting polygon.</li>
</ul></li>
</ol>
<h3 id="polygon-scan-conversion">Polygon Scan Conversion</h3>
<ul>
<li>Complicated in general, we look at scan conversion of triangle.</li>
<li>Split triangle with horizonal line at middle <span class="math inline">y</span> value, so we have an axis-aligned edge.</li>
<li>Scan convert the triangle by calculating slopes and iterating over every horizontal line (floating point algorithm).</li>
</ul>
<h2 id="hidden-surface-removal">Hidden Surface Removal</h2>
<blockquote>
<p>When we have a lot of polygons, we want to draw only those visible to the viewer.</p>
</blockquote>
<h3 id="backface-culling">Backface Culling</h3>
<ul>
<li>Remove all <em>backfacing</em> polygons. Polygons are backfacing if their normal is facing away from the viewer. So cull the polygon if <span class="math inline">N \cdot V > 0</span>.</li>
<li>Not a complete solution (used in conjuction with more complete algorithm), but easy to integrate into hardware and usually improves performance by a factor of 2.</li>
</ul>
<h3 id="painters-algorithm">Painter’s Algorithm</h3>
<ul>
<li>Sort polygons on farthest <span class="math inline">z</span>.</li>
<li>Resolve ambiguities where <span class="math inline">z</span>’s overlap.</li>
<li>Scan convert from largest <span class="math inline">z</span> to smallest <span class="math inline">z</span>.</li>
<li>Some cases are simple but others are not. <span class="math inline">\Omega(n^2)</span> algorithm.</li>
</ul>
<h3 id="warnocks-algorithm">Warnock’s Algorithm</h3>
<blockquote>
<p>Divide and conquer algorithm.</p>
</blockquote>
<ul>
<li>Draw the polygon-list if it is simple in the viewport, otherwise split the viewport vertically and horizontally then recursively draw.</li>
<li>Simple means there is no more than one polygon in the viewport, or that the viewport is only 1 pixel in size (shade pixel based on closest polygon).</li>
<li><span class="math inline">O(pn)</span>, where <span class="math inline">p, n</span> are the number of pixels and polygons.</li>
</ul>
<h3 id="z-buffer-algorithm">Z-Buffer Algorithm</h3>
<ul>
<li>Perspective transformatoin maps polygons to polygons.</li>
<li>Scan convert while also stepping in <span class="math inline">z</span>.</li>
<li>In addition to framebuffer, have a depth buffer (<span class="math inline">z</span> buffer) to write <span class="math inline">z</span> values.</li>
<li>Update colour in framebuffer if the <span class="math inline">z</span> value is less than current.</li>
<li><span class="math inline">O(p_c + n)</span>, where <span class="math inline">p_c, n</span> are the number of scan converted pixels and polygons.</li>
<li>Easy to implement (hardware too), online algorithm.</li>
<li>Doubles memory requirements (memory is cheap).</li>
<li>Scale / device dependent.</li>
</ul>
<h2 id="hierarchical-models-transformations">Hierarchical Models & Transformations</h2>
<blockquote>
<p>How do we model complex objects and scenes?</p>
</blockquote>
<ul>
<li>Define basic 3D primitives in some nice way in their own space.</li>
<li>Use transformations to put primitives together.</li>
<li>Use hierarchy of spaces to build complex models (DAG).
<ul>
<li>DFS of the DAG, using a <strong>matrix stack</strong>.</li>
<li>Primitives occur at leaf nodes, transformations occur at internal nodes.</li>
</ul></li>
</ul>
<h2 id="rotations-about-arbitrary-axis">Rotations About Arbitrary Axis</h2>
<blockquote>
<p>Rotation given by <span class="math inline">a = (x, y, z)</span> and <span class="math inline">\theta</span>. Map <span class="math inline">a</span> onto one of the canonical axes, rotate by <span class="math inline">\theta</span>, then map back.</p>
</blockquote>
<ol type="1">
<li>Pick closest axis to <span class="math inline">a</span>. Assume we chose the <span class="math inline">x</span>-axis.</li>
<li>Project <span class="math inline">a</span> onto <span class="math inline">b</span> in the <span class="math inline">xz</span> plane.</li>
<li>Compute <span class="math inline">\cos(\phi) = \frac{x}{\sqrt{x^2 + z^2}}</span>, <span class="math inline">\sin(\phi) = \frac{z}{\sqrt{x^2+z^2}}</span>.</li>
<li>Create <span class="math inline">R(-\phi)</span>.</li>
<li>Rotate <span class="math inline">a</span> onto the <span class="math inline">xy</span> plane using <span class="math inline">R(-\phi)</span>. <span class="math inline">c = R_y(-\theta)a</span>.</li>
<li>Compute <span class="math inline">\cos(\gamma)</span>, <span class="math inline">\sin(\gamma)</span>, where <span class="math inline">\gamma</span> is the angle of <span class="math inline">c</span> with the <span class="math inline">x</span> axis.</li>
<li>Use <span class="math inline">\cos(\gamma)</span> and <span class="math inline">\sin(\gamma)</span> to create <span class="math inline">R_z(-\gamma)</span>.</li>
<li>Rotate <span class="math inline">c</span> onto the <span class="math inline">x</span>-axis using <span class="math inline">R_z(-\gamma)</span>.</li>
<li>Rotate around the <span class="math inline">x</span>-axis by <span class="math inline">\theta</span>, <span class="math inline">R_x(\theta)</span>.</li>
<li>Reverse <span class="math inline">z</span>-axis rotation.</li>
<li>Reverse <span class="math inline">y</span>-axis rotation.</li>
</ol>
<p>So the overall transformation is <span class="math inline">R(\theta, a) = R_y(\phi)R_z(\gamma)R_x(\theta)R_z(-\gamma)R_y(-\phi)</span>.</p>
<h3 id="d-rotation-user-interfaces">3D Rotation User Interfaces</h3>
<ul>
<li><strong>Virtual Sphere</strong>: Given two sequential samples of mouse position <span class="math inline">S, T</span>, map <span class="math inline">S</span> to point on sphere, map <span class="math inline">ST</span> to tangential velocity. Use to rotate. When <span class="math inline">S</span> is outside of the sphere we do <span class="math inline">z</span>-axis rotation.</li>
<li><strong>Arcball</strong>: Rather than using <span class="math inline">T</span> as tangent, map <span class="math inline">T</span> to point on the sphere as well and rotate the ball so that <span class="math inline">S</span> moves to <span class="math inline">T</span>.</li>
</ul>
<h2 id="colour">Colour</h2>
<ul>
<li>Light sources emit intensity <span class="math inline">I(\lambda)</span>, assigns intensity to each wavelength of light.</li>
<li>Humans perceive <span class="math inline">I(\lambda)</span> as colour. Normal human retina has three types of colour receptors which respond most strongly to short, medium, or long wavelengths.</li>
</ul>
<h3 id="tri-stimulus-colour-theory">Tri-Stimulus Colour Theory</h3>
<ul>
<li>Model visual system as linear map, from wavelength to three dimensional vector space.</li>
</ul>
<h3 id="colour-systems">Colour Systems</h3>
<ul>
<li>RGB (Red, Green, Blue) Additive.</li>
<li>CMY (Cyan, Magenta, Yellow) Subtractive. Complement of RGB.</li>
<li>HSV (Hue, Saturation, Value). Cone shaped colour space.</li>
<li>CIE XYZ. More complete colour space.</li>
<li>YIQ. Backwards compatible with black-and-white TV.</li>
</ul>
<h2 id="lighting">Lighting</h2>
<blockquote>
<p>Given a point on the surface visible through a pixel, what colour should we assign it?</p>
</blockquote>
<ul>
<li>Want to smoothly shade objects in the scene.</li>
<li>Shading done quickly (interactive speeds).</li>
</ul>
<p><strong>Initial Assumptions</strong></p>
<ul>
<li>Linearity of reflection.</li>
<li>Energy conservation.</li>
<li>Full spectrum of light is representable by three floats (RGB).</li>
</ul>
<h3 id="lambertian-reflection">Lambertian Reflection</h3>
<blockquote>
<p>Assume that incoming light is partially absorbed, then the remainder of energy is propogated equally in all directions.</p>
</blockquote>
<ul>
<li>Approximates matte materials.</li>
<li><span class="math inline">L_{out}(v) = \rho(v, l)E_{in}(l)</span>. We assumed that outgoing radiance is equal in all directions so <span class="math inline">\rho</span> is a constant.</li>
<li><span class="math inline">L_{out}(v) = k_d E_{in}(l) = k_d L_{in}(l) l \cdot n</span>. For the complete environment we take the integral over all possible directions. Taken as the sum over all light sources in practice.</li>
</ul>
<h3 id="attenuation">Attenuation</h3>
<ul>
<li>No attenuation for directional lights, because the energy goes not spread out.</li>
<li>For point light sources, <span class="math inline">L_{in}(l) \propto \frac{1}{r^2}</span>, where <span class="math inline">r</span> is the distance from light to <span class="math inline">P</span>.
<ul>
<li>Too harsh in practice because real lighting is from area sources, multiply reflections in environment.</li>
<li>We use <span class="math inline">L_{in}(l) = \frac{I}{c_1 + c_2r + c_3r^2}</span>. We do not attenuate light from <span class="math inline">P</span> to the screen.</li>
</ul></li>
</ul>
<h3 id="ambient-light">Ambient Light</h3>
<ul>
<li>Lambertian only models direct illumination.</li>
<li>Ambient illumination is a simple approximation to global illumination.</li>
<li>Assume everything gets uniform illumination in addition to direct illumination. <span class="math inline">L_{out}(v) = k_a I_a + \sum_i \rho(v, l_i) I_i \frac{l_i \cdot n}{c_1 + c_2 r_i + c_3 r_i^2}</span>.</li>
</ul>
<h3 id="specular-reflection">Specular Reflection</h3>
<ul>
<li>Lambertian models matte but not shiny.</li>
<li>Shiny surfaces have highlights.</li>
<li>Phong Bui-Tuong developed empirical model. <span class="math inline">L_{out}(v) = k_a I_a + k_d (l \cdot n) I_d + k_s (r \cdot v)^p I_s</span>. Classic <strong>Phong lighting model</strong>.
<ul>
<li>Vector <span class="math inline">r</span> is <span class="math inline">l</span> reflected by the surface. <span class="math inline">r = -l + 2(l \cdot n)n</span>.</li>
<li>Exponent <span class="math inline">p</span> controls sharpness of highlight. Small <span class="math inline">p</span> gives wide highlight, large <span class="math inline">p</span> gives narrow highlight.</li>
</ul></li>
<li>Blinn introduced variation, <strong>Blinn-Phong lighting model</strong>. <span class="math inline">L_{out} k_a I_a + k_d(l \cdot n) I_d + k_s (h \cdot n)^p I_s</span>, with <span class="math inline">h = \frac{v + l}{|v + l|}</span> measuring deviation from the ideal mirror configuration.</li>
</ul>
<h2 id="shading">Shading</h2>
<ul>
<li>We have lighting calculation for a point, so we need surface normals at every point.</li>
<li>Surface is often polygonal.</li>
</ul>
<h3 id="flat-shading">Flat Shading</h3>
<ul>
<li>Shade entire polygon one colour.</li>
<li>Surface will look faceted. This is acceptable if it really is a polygonal model, not good if it is an approximation of a curved surface.</li>
</ul>
<h3 id="gouraud-shading">Gouraud Shading</h3>
<ul>
<li>Interpolate colours across a polygon from the vertices.</li>
<li>Lighting calculation only performed at vertices.</li>
<li>Well-defined for triangles. Extends to convex polygons but better to just convert to triangles.
<ul>
<li>We could slice convex polygon horizontally then interpolate colours along each scanline. This will not produce consistent shading after rotations.</li>
<li>Triangluation is expensive and it will be visible to the viewer.</li>
</ul></li>
</ul>
<h3 id="phong-shading">Phong Shading</h3>
<ul>
<li>Interpolate lighting model parameters instead of colours.</li>
<li><strong>Normal</strong> is specified at every vertex of a polygon, interpolated using the Gouraud technique.</li>
<li>Simulated with programmable vertex and fragment shaders on modern graphics hardware.</li>
</ul>
<h2 id="ray-tracing">Ray Tracing</h2>
<ul>
<li>Want more realistic images with shadows and reflections.</li>
</ul>
<div class="sourceCode" id="cb2"><pre class="sourceCode python"><code class="sourceCode python"><a class="sourceLine" id="cb2-1" title="1"><span class="cf">for</span> pixel <span class="kw">in</span> pixels:</a>
<a class="sourceLine" id="cb2-2" title="2"> ray <span class="op">=</span> (eye, pixel <span class="op">-</span> eye)</a>
<a class="sourceLine" id="cb2-3" title="3"> Intersect(Scene, ray)</a></code></pre></div>
<ul>
<li><strong>Setting</strong>: eyepoint, virtual screen (array of virtual pixels).</li>
<li><strong>Ray</strong>: Half-line determined by eyepoint and a point associated with a chosen pixel.</li>
<li><strong>Interpretations</strong>: Ray is a path of photons that reach the eye.</li>
</ul>
<h3 id="intersection-computations">Intersection Computations</h3>
<ul>
<li>Express ray in parametric form <span class="math inline">E + t(P - E)</span>, <span class="math inline">t > 0</span>.</li>
<li><strong>Direct Implicit Form</strong>: Express object as <span class="math inline">f(Q) = 0</span> when <span class="math inline">Q</span> is a surface point, intersection equation is solving for <span class="math inline">t</span> such that <span class="math inline">f(E + t(P - E)) = 0</span>.</li>
<li><strong>Procedural Implicit Form</strong>: <span class="math inline">f</span> is defined procedurally.</li>
</ul>
<h4 id="quadratic-surfaces.">Quadratic Surfaces.</h4>
<ul>
<li><strong>Ellipsoid</strong>: <span class="math inline">\frac{x^2}{a^2} + \frac{y^2}{b^2} + \frac{z^2}{c^2} = 1</span>.</li>
<li><strong>Elliptic Paraboloid</strong>: <span class="math inline">\frac{x^2}{p^2} + \frac{y^2}{q^2} = 1</span>.</li>
<li><strong>Hyperboloid of One Sheet</strong>: <span class="math inline">\frac{x^2}{a^2} + \frac{y^2}{b^2} - \frac{z^2}{c^2} = 1</span>.</li>
<li><strong>Elliptic Cone</strong>: <span class="math inline">\frac{x^2}{p^2} + \frac{y^2}{q^2} - \frac{z^2}{r^2} = 0</span>.</li>
<li><strong>Elliptic Cylinder</strong>: <span class="math inline">\frac{x^2}{p^2} + \frac{y^2}{q^2} = 1</span>.</li>
<li>Instead of solving generally, we can solve for simpler versions then just scale results (intersections in model space).</li>
</ul>
<h3 id="shading-1">Shading</h3>
<ul>
<li>At closest intersection point, perform Phong shading.</li>
<li>Before adding contribution from a light, cast a ray to the light. If the ray hits an object before the light, then don’t shade. This gives <strong>shadows</strong>.</li>
</ul>
<h3 id="reflections">Reflections</h3>
<ul>
<li>Cast ray in the mirror direction.</li>
<li>Add colour coming from this ray to the shade of the initial ray.</li>
</ul>
<h3 id="recursive-ray-tracing">Recursive Ray Tracing</h3>
<ul>
<li>Eye-screen ray is the <em>primary</em> ray.</li>
<li>Generate secondary rays for light sources, reflections, refractions, and recurse.</li>
<li>Accumulate averaged information for primary ray.</li>
</ul>
<h3 id="ray-casting">Ray Casting</h3>
<ul>
<li>Stop before generating secondary rays.</li>
</ul>
<h3 id="surface-normals">Surface Normals</h3>
<ul>
<li>Illumination models require surface normal vectors at intersection points.</li>
<li>Normals to polygons are provided by planar normal or cross product of adjacent edges.</li>
<li>Normals to any implicit surface use calculus.</li>
</ul>
<h4 id="normal-transformations">Normal Transformations</h4>
<blockquote>
<p>How do affine transformations affect surface normals?</p>
</blockquote>
<ul>
<li>Recall from <a href="#affine-geometries-transformations">Affine Geometrics & Transformations</a> that normals are transformed by the inverse transpose of the upper 3 x 3 portion of the transformation matrix.</li>
</ul>
<h3 id="modeling-and-csg">Modeling and CSG</h3>
<ul>
<li>Hierarchical modeling works for ray tracer too.</li>
<li>In <em>Constructive Solid Geometry</em> all primitives are solids.</li>
<li>New type of internal node in DAG, boolean operations (Intersection, Union, Difference).
<ul>
<li>Complete ray intersect object with every primitive, then perform boolean operations on the set of resulting line segments.</li>
<li>Segments must be transformed on the way back up the DAG similar to how the ray is transformed.</li>
</ul></li>
</ul>
<h3 id="texture-mapping">Texture Mapping</h3>
<blockquote>
<p>Adding detail by increasing model complexity is costly. When the detail is surface detail, we can use texture mapping.</p>
</blockquote>
<ul>
<li>Scan a photo of the detail and paste it onto objects.</li>
<li>Associate texture with polygon.</li>
<li>Map pixel onto polygon then into texture map.</li>
<li>Use weighted average of covered texture to compute colour.</li>
</ul>
<h3 id="bump-mapping">Bump Mapping</h3>
<ul>
<li>Textures will still appear smooth (no shadows).</li>
<li>We perturb the normal, use for lighting calculation.</li>
</ul>
<h3 id="solid-textures">Solid Textures</h3>
<ul>
<li>Hard to texture map onto curved surfaces.</li>
<li>Use a 3D texture instead. Usually procedural.</li>
</ul>
<h3 id="bounding-boxes-spatial-subdivision">Bounding Boxes, Spatial Subdivision</h3>
<ul>
<li>Ray tracing is slow, often because of ray intersect object.</li>
<li>Improvements come in two forms; reduce the cost of ray intersect object or intersect the ray with fewer objects.</li>
<li><strong>Bounding Boxes</strong>: Place bounding box around complicated geometry. Only compute ray intersect object if the ray intersects the bounding box. Cheap to compute if the box is axis-aligned.</li>
</ul>
<h3 id="spatial-subdivision">Spatial Subdivision</h3>
<ul>
<li>Divide space into subregions.</li>
<li>When tracing ray, only interesect with objects in sub-regions the ray passes through.</li>
<li>Useful when there are a lot of small objects in the scene.</li>
</ul>
<h2 id="aliasing">Aliasing</h2>
<ul>
<li>Images sample a continuous function. When the samples are spaced too far apart, don’t get a true representation of the scene.
<ul>
<li>Stairsteps.</li>
<li>Moire Patterns.</li>
<li>Loss of small objects.</li>
</ul></li>
</ul>
<h3 id="nyquist-limit">Nyquist Limit</h3>
<ul>
<li>Sampling rate which is twice the highest frequency.</li>
<li>Avoids aliasing.</li>
<li>Doesn’t work for man made objects because they have distinct edges with infinite frequency.</li>
</ul>
<h3 id="area-sampling">Area Sampling</h3>
<ul>
<li>Instead of sampling, we could integrate.</li>
</ul>
<h3 id="weighted-sampling">Weighted Sampling</h3>
<ul>
<li>Unweighted is just <span class="math inline">I = \int_{x \in Box} I_x dI</span>.</li>
<li>Weighted gives different weights depending on position in the pixel. For example, positions closer to the center of the pixel may be weighted higher than positions near the edge.</li>
</ul>
<h3 id="anti-aliasing-in-ray-tracing">Anti-aliasing in Ray Tracing</h3>
<ul>
<li>Integration not possible, instead we point sample the image.</li>
<li><strong>Super Sampling</strong>: Take more samples and weight with filter. Sampling pattern should not be regular or we will still get aliasing.</li>
<li><strong>Stochastic Sampling</strong>: Jitter samples.</li>
</ul>
<h2 id="bidirectional-tracing">Bidirectional Tracing</h2>
<blockquote>
<p>Some effects such as caustics require tracing lights from light back to eye.</p>
</blockquote>
<h3 id="radiosity">Radiosity</h3>
<ul>
<li>Model diffuse interaction of light only in steady state.</li>
<li>Discretize scene into polygons and assume polygons emit constant light over surface.</li>
<li>Determine interaction between pairs of polygons.</li>
<li>Solve a large linear system which is expensive but the result is reusable.</li>
</ul>
<h3 id="distribution-ray-tracing">Distribution Ray Tracing</h3>
<ul>
<li>Ray trace, but at every reflection cast multiple rays based on a distribution function that represents reflection properties.</li>
<li>Distribution over reflected direction gives soft reflections, over light area gives soft shadows, over aperature gives depth of field, over time gives motion blur.</li>
<li>Can handle caustics in theory but needs a lot of rays.</li>
</ul>
<h3 id="bidirectional-path-tracing">Bidirectional Path Tracing</h3>
<blockquote>
<p>Trace paths from eye and from light and connect them. Trace paths (single reflected ray).</p>
</blockquote>
<ul>
<li>Reflect with distribution function.</li>
<li>Lots of rays, low error, high noise.</li>
<li>Less expensive than distribution ray tracing.</li>
</ul>
<h3 id="photon-maps">Photon Maps</h3>
<ul>
<li>Cast rays from lights, create a <em>photon map</em> wherever light hits.</li>
<li>Use standard ray casting to determine lighting.
<ul>
<li>Density estimation to convert photon map to intensity.</li>
</ul></li>
<li>Fast, easy to program, high noise.</li>
</ul>
<h3 id="metropolis-algorithm">Metropolis Algorithm</h3>
<ul>
<li>Take one path from light to eye, perturb the <em>path</em> and see if it still reaches the eye.</li>
</ul>
<h2 id="radiosity-1">Radiosity</h2>
<ul>
<li>Ambient term approximates diffuse interaction of light, want to find a better model.</li>
<li>Discretize environment and find interactions between pairs of pieces.</li>
<li>After lighting interactions computed once, multiple views can be rendered easily.
<ul>
<li>No mirror or specular reflectoins.</li>
</ul></li>
</ul>
<p><strong>Radiance</strong>: Total energy flux comes from flux at each wavelength <span class="math inline">L(x, \theta, \phi) = \int_{\lambda_{min}}^{\lambda_{max}} L(x, \theta, \phi, \lambda)d\lambda</span>.</p>
<p><strong>Radiosity</strong>: Total power leaving a surface point per unit area <span class="math inline">\int_0^{\frac{\pi}{2}}\int_0^{2\pi} L(x, \theta, \phi) \cos(\theta) \sin(\theta) d\phi d\theta</span>.</p>
<h3 id="bidirectional-reflectance-distribution-function">Bidirectional Reflectance Distribution Function</h3>
<ul>
<li>Surface property at a point, relates energy in to energy out.</li>
</ul>
<h3 id="simple-energy-balance-hemisphere-based">Simple Energy Balance (Hemisphere Based)</h3>
<ul>
<li>General energy balance equation is a long triple integral equation over the hemisphere above the point based on the BRDF, radiance, radiance emitted from surfaces from a given point, and the incident radiance impinging on a given point.</li>
<li>Series of assumptions are made to get a simpler approximation.
<ul>
<li>All wavelengths act independently.</li>
<li>All surfaces are pure Lambertian.</li>
</ul></li>
</ul>
<p><span class="math display">B(x) = E(x) + p_d(x) \int_{\Omega} L^i(x) \cos(\theta^i_x) d \omega</span></p>
<p>In general we have <span class="math inline">L^i(x, \theta^i_x, \phi^i_x) = L^o(y, \theta^o_y, \phi^o_u)</span> for some <span class="math inline">y</span>. In other words, the radiance comes from some incident radiance. So we simplify with <span class="math inline">\theta^i_x = \theta_{xy}</span>, <span class="math inline">\theta^o_y = \theta_{yz}</span> and <span class="math inline">L^i(x) = \frac{B(y)}{\pi}</span>.</p>
<ul>
<li><strong>Visibility</strong>: We use <span class="math inline">H(x, y)</span> as an indicator variable with <span class="math inline">H(x, y) = 1</span> if <span class="math inline">y</span> is visible from <span class="math inline">x</span>.</li>
<li><strong>Area</strong>: Convert <span class="math inline">d\omega</span> to surface area <span class="math inline">d\omega = \frac{\cos(\theta_{yx})}{||x - y||^2} dA(y)</span>.</li>
</ul>
<p><span class="math display">B(x) = E(x) + p_d(x) \int_{y \in S} B(y) \frac{\cos(\theta_{xy})\cos(\theta_{yx})}{\pi ||x - y||^2} H(x, y) dA(y)</span></p>
<h3 id="piecewise-constant-approximation">Piecewise Constant Approximation</h3>
<ul>
<li>We approximate this integral by breaking into a summation over patches.</li>
<li>Assume constant radiosity on each patch.</li>
</ul>
<p><span class="math display">B(x) \approx E(x) + p_d(x) \sum_j B_j \int_{y \in P_j}\frac{\cos(\theta_{xy})\cos(\theta_{yx})}{\pi ||x - y||^2} H(x, y) dA(y)</span></p>
<ul>
<li>Solve with per-patch average density. So <span class="math inline">p_d(x) \approx p_i</span> for <span class="math inline">x \in P_i</span>, <span class="math inline">B_i \approx \frac{1}{A_i} \int_{x \in P_i} B(x)d A(x)</span>, <span class="math inline">E_i \approx \frac{1}{A_i} \int_{x \in P_i} E(x) dA(x)</span>.</li>
</ul>
<p><span class="math display"> B_i = E_i + p_i \sum_j B_j \frac{1}{A_i} \int_{x \in P_i} \int_{y \in P_j} \frac{\cos(\theta_{i})\cos(\theta_{j})}{\pi ||x - y||^2} H(i, j) dA_j dA_i</span></p>
<ul>
<li><strong>Form Factor</strong>: <span class="math inline">F_{ij} = \frac{1}{A_i} \int_{x \in P_i} \int_{y \in P_j} \frac{\cos(\theta_{i})\cos(\theta_{j})}{\pi ||x - y||^2} H(i, j) dA_j dA_i</span>. By symmetry, <span class="math inline">A_i F_{ij} = A_j F_{ji}</span>.</li>
</ul>
<p>So given all of the form factors, we have linear equations <span class="math inline">B_i = E_i + p_i \sum_j F_{ij} B_j</span>, <span class="math inline">B_i = E_i + p_i \sum_j F_{ji} \frac{A_j}{A_i} B_j</span>.</p>
<h4 id="matrix-form">Matrix Form</h4>
<ul>
<li>Equations are <span class="math inline">B_i - p_i \sum_{1 \le j \le n} B_j F_{ij} = E_i</span>. <span class="math inline">B_i's</span> are the only unknowns, solve 3 times to get <span class="math inline">RGB</span> values of <span class="math inline">B_i</span>.</li>
</ul>
<h3 id="calculating-form-factors">Calculating Form Factors</h3>
<ul>
<li>Differential form factor is <span class="math inline">ddF_{di,d_j} = \frac{\cos(\theta_i)\cos(\theta_j)}{\pi r^2} H_{i,j} dA_j dA_i</span>.</li>
<li>Form factor from <span class="math inline">A_i</span> to <span class="math inline">A_j</span> is an area average over the integral over <span class="math inline">A_i</span>. <span class="math inline">F_{i,j} = \frac{1}{A_i} \int_{A_i} \int_{A_j} \frac{\cos(\theta_i)\cos(\theta_j)}{\pi r^2} H_{i,j} dA_j dA_i</span>.
<ul>
<li>We approximate this integral though ray tracing, hemi-sphere, hemi-cube.</li>
<li>Lots of <span class="math inline">F_{i,j}</span> may be zero, so we have sparse matrix.</li>
</ul></li>
</ul>
<h4 id="hemi-sphere-form-factors">Hemi-sphere Form Factors</h4>
<ul>
<li>Place hemisphere around patch <span class="math inline">i</span> and project patch <span class="math inline">j</span> onto it.</li>
<li>Still non-trivial to project onto hemisphere.</li>
</ul>
<h4 id="hemi-cube-form-factors">Hemi-cube Form Factors</h4>
<ul>
<li>Project onto a hemi-cube.</li>
<li>Subdivide faces into smaller squares.</li>
</ul>
<h4 id="delta-form-factors">Delta Form Factors</h4>
<ul>
<li>Every hemi-cube cell <span class="math inline">P</span> has pre-computed delta form factor <span class="math inline">\Delta F_P = \frac{\cos(\theta_i)\cos(\theta_P)}{\pi r^2} \Delta A_P</span>. Approximate <span class="math inline">d F_{dj, i}</span> by summing delta form factors.</li>
</ul>
<h3 id="progressive-refinement">Progressive Refinement</h3>
<ul>
<li>Continuously choose a patch and shoot its radiosity to all other patches.</li>
</ul>
<div class="sourceCode" id="cb3"><pre class="sourceCode python"><code class="sourceCode python"><a class="sourceLine" id="cb3-1" title="1"><span class="kw">def</span> shoot(i):</a>
<a class="sourceLine" id="cb3-2" title="2"> For <span class="bu">all</span> j, calculate F_ji</a>
<a class="sourceLine" id="cb3-3" title="3"> For every j:</a>
<a class="sourceLine" id="cb3-4" title="4"> d_rad <span class="op">=</span> pj <span class="op">*</span> dB_i <span class="op">*</span> F_ji <span class="op">*</span> A_i <span class="op">/</span> A_j</a>
<a class="sourceLine" id="cb3-5" title="5"> dB_j <span class="op">+=</span> d_rad</a>
<a class="sourceLine" id="cb3-6" title="6"> Bj <span class="op">+=</span> d_rad</a>
<a class="sourceLine" id="cb3-7" title="7"> dB_i <span class="op">=</span> <span class="dv">0</span></a>
<a class="sourceLine" id="cb3-8" title="8"></a>
<a class="sourceLine" id="cb3-9" title="9"><span class="cf">while</span> unshot <span class="op">></span> EPS:</a>
<a class="sourceLine" id="cb3-10" title="10"> Choose patch i <span class="cf">with</span> highest d_B</a>
<a class="sourceLine" id="cb3-11" title="11"> shoot(i)</a></code></pre></div>
<ul>
<li>Able to stop and look at partial results.</li>
</ul>
<h3 id="meshing-in-radiosity">Meshing in Radiosity</h3>
<h4 id="adaptive-subdivision">Adaptive Subdivision</h4>
<ul>
<li>Make initial meshing guess.</li>
<li>Point sample a patch.</li>
<li>Radiosity has <span class="math inline">O(n^2)</span> runtime but subdivision increases <span class="math inline">n</span>.</li>
<li>We could shoot from big patches and receive at small patches.</li>
</ul>
<h3 id="stochastic-methods">Stochastic Methods</h3>
<ul>
<li>Rather than computing form factor, estimate by <em>sampling</em>.</li>
<li>Cast <span class="math inline">N_i</span> rays cosine-distributed from patch <span class="math inline">i</span>. Let <span class="math inline">N_{ij}</span> be the number of particles that reach patch <span class="math inline">j</span>. Then <span class="math inline">\frac{N_{ij}}{N_i} \approx F_{ij}</span>.</li>
<li>Let <span class="math inline">\Delta P_i^{(j)}</span> be unshot radiosity. Select source patch randomly based on unshot radiosity, select patch <span class="math inline">j</span> by casting stochastic rays.</li>
<li>Much faster than form factor methods but lots of noise.</li>
</ul>
<h2 id="photon-mapping">Photon Mapping</h2>
<ul>
<li>Trace rays from lights, bounce off shiny surfaces.</li>
<li>Store lights hitting diffuse surfaces, use stored light to achieve global illumination effects.</li>
</ul>
<ol type="1">
<li>Emit photons.</li>
<li>Trace photons, store in data structure.</li>
<li>Estimate irradiance with <span class="math inline">k</span> nearest neighbour search.</li>
<li>Ray trace, using estimated irradiance.</li>
</ol>
<h2 id="shadows-projective-shadow-maps-volumes">Shadows, Projective, Shadow Maps, Volumes</h2>
<ul>
<li>Shadows are important to help viewer locate objects.</li>
</ul>
<h3 id="projective-shadows">Projective Shadows</h3>
<blockquote>
<p>For drawing shadows on a plane.</p>
</blockquote>
<ul>
<li>After drawing scene, draw ray from light through corners of polygon and intersect with plane.</li>
<li>Draw projected polygon as a dark colour with alpha blending.</li>
<li>Fast and simple but only works for shadows on a plane.</li>
</ul>
<h3 id="shadow-maps">Shadow Maps</h3>
<ul>
<li>Render scene from <strong>light</strong>’s view and store the <span class="math inline">z</span>-map.</li>
<li>Render from eye’s viewpoint. For a point <span class="math inline">P</span> that the eye sees, convert to light’s frame and look up distance to light using shadow map. When distance is equal, the object is <em>unblocked</em>, so do lighting calculation. When distance is not equal, it is in shadow.</li>
<li>No need to rerender shadow maps every frame if light and objects are not moving.</li>
<li>Works best with directional and spot lights.</li>
</ul>
<h3 id="shadow-volumes">Shadow Volumes</h3>
<ul>
<li>Use stencil buffer to determine where shadows are. Stencil buffer stores per pixel data.</li>
<li>For every point <span class="math inline">P</span> on surface, consider shadow planes cast by silhouette edges. Count front facing shadow planes as <span class="math inline">+1</span>, rear facing plane as <span class="math inline">-1</span>. Take the sum of shadow planes, if it is positive then the object is in shadow.</li>
</ul>
<ol type="1">
<li>Draw scene normally.</li>
<li>Draw in stencil buffer, front facing shadow polygons using previous depth buffer. Increment stencil buffer on draws.</li>
<li>Draw in stencil buffer, backfacing polygons. Decrement stencil buffer on draws.</li>
<li>Redraw scene with light off, but only update pixels with exact depth match and non-zero stencil value.</li>
</ol>
<h2 id="modelling-stuff">Modelling Stuff</h2>
<h3 id="fractal-mountains">Fractal Mountains</h3>
<ul>
<li>Start with triangle, refine and adjust vertices. At every step of refinement, adjust height of vertices. Use scaled random numbers to adjust height.</li>
</ul>
<h3 id="l-system-plants">L-system Plants</h3>
<ul>
<li>Model as CFG.</li>
</ul>
<h3 id="buildings">Buildings</h3>
<ul>
<li>Model as CFG.</li>
</ul>
<h3 id="partical-systems">Partical Systems</h3>
<ul>
<li>Aim for overall effects by having many simple particles.</li>
<li>At each time step based on state, update attributes of particles, delete old particles, create new particles, display current state of all particles.</li>
</ul>
<h2 id="splines-de-casteljaus-algorithm">Splines, De Casteljau’s Algorithm</h2>
<ul>
<li><strong>Linear blend</strong>: Line segment from an affine combination of the points.</li>
<li><strong>Quadratic blend</strong>: Quadratic segment from an affine combination of line segments.
<ul>
<li><span class="math inline">\begin{aligned}P_0^1(t) &= (1 - t)P_0 + tP_1 \\ P_1^1(t) &= (1 - t)P_1 + tP_2 \\ P_0^2(t) &= (1 - t)P_0^1(t) + tP_1^1(t)\end{aligned}</span></li>
</ul></li>
<li><strong>Cubic blend</strong>: Cubic segment from affine combination of quadratic segments.</li>
</ul>
<h3 id="de-casteljau-algorithm">de Casteljau Algorithm</h3>
<blockquote>
<p>Geometric view.</p>
</blockquote>
<ul>
<li>Join <span class="math inline">P_i</span> by line segments.</li>
<li>Join the <span class="math inline">t: (1 - t)</span> points of those line segments by line segments.</li>
<li>Repeat as necessary.</li>
<li><span class="math inline">t: (1-t)</span> point on the final line segment is a point on the curve, final line segment is tangent to the curve at <span class="math inline">t</span>.</li>
</ul>
<h4 id="expanding-terms-basic-polynomials">Expanding Terms (Basic Polynomials)</h4>
<ul>
<li><span class="math inline">P^n_0(t) = \sum_{i=0}^n P_i B^n_i(t)</span>, where <span class="math inline">B^n_i(t) = \frac{n!}{(n-i)!i!}(1 - t)^{n-i}t^i = {n \choose i}(1 - t)^{n-i}t^i</span>.</li>
<li>Bernstein polynomials of degree <span class="math inline">n</span> form a basis for the space of all degree-<span class="math inline">n</span> polynomials.</li>
</ul>
<h3 id="bernstein-polynomials">Bernstein Polynomials</h3>
<ul>
<li><span class="math inline">\sum_{i=0}^n B_i^n(t) = 1</span></li>
<li><span class="math inline">B_i^n (t) \ge 0</span>, for <span class="math inline">t \in [0, 1]</span>.</li>
</ul>
<h3 id="bezier-splines">Bezier Splines</h3>
<ul>
<li>Degree <span class="math inline">n</span> (order <span class="math inline">n + 1</span>) <strong>Bezier curve segment</strong> is <span class="math inline">P(t) = \sum_{i=0}^n P_i B^n_i(t)</span>.</li>
<li><span class="math inline">P_i</span> are the <span class="math inline">k</span>-dimensional <strong>control points</strong>.</li>
<li><span class="math inline">P(t)</span> is a convex combination of the <span class="math inline">P_i</span> for <span class="math inline">t \in [0, 1]</span>.</li>
<li>So <span class="math inline">P(t)</span> lies within the <strong>convex hull</strong> of <span class="math inline">P_i</span>.</li>
<li>Since the Bezier curve is an affine combination of its control points, any affine transformation of a curve is the curve of the transformed control points.</li>
</ul>
<h4 id="interpolation">Interpolation</h4>
<ul>
<li><span class="math inline">B^n_0(0) = 1</span>, <span class="math inline">B^n_n(1) = 1</span>, so <span class="math inline">B_i^n(0) = 0</span> if <span class="math inline">i \neq 0</span>, <span class="math inline">B_i^n(1) = 0</span>, if <span class="math inline">i \neq n</span>.</li>
<li><span class="math inline">P(0) = P_0</span>, <span class="math inline">P(1) = P_n</span>.</li>
</ul>
<h4 id="derivatives">Derivatives</h4>
<p><span class="math inline">\frac{d}{dt} B_i^n(t) = n(B^{n-1}_{t-1}(t) - B_i^{n-1}(t))</span>, so <span class="math inline">P^\prime(t) = n(P_1 - P_0)</span>, <span class="math inline">P^\prime(1) = n(P_n - P_{n-1})</span>.</p>
<h4 id="smoothly-joined-segments-c1">Smoothly Joined Segments (<span class="math inline">C^1</span>)</h4>
<ul>
<li>Let <span class="math inline">P_{n-1}, P_n</span> be the last two control points of one segment. Let <span class="math inline">Q_0, Q_1</span> be the nest two control points of the next sequence.</li>
<li><span class="math inline">P_n = Q_0</span>.</li>
<li><span class="math inline">P_n - P_{n-1} = Q_1 - Q_0</span>.</li>
</ul>
<h4 id="smoothly-joined-segments-c1-1">Smoothly Joined Segments (<span class="math inline">C^1</span>)</h4>
<ul>
<li><span class="math inline">P_n = Q_0</span>.</li>
<li><span class="math inline">P_n - P_{n-1} = \beta(Q_1 - Q_0)</span>, for some <span class="math inline">\beta > 0</span>.</li>
</ul>
<h4 id="c2-continuity"><span class="math inline">C^2</span> Continuity</h4>
<ul>
<li><span class="math inline">C^0: P_n = Q_0</span>.</li>
<li><span class="math inline">C^1: P_n - P_{n-1} = Q_1 - Q_0</span>.</li>
<li><span class="math inline">C^2: (P_n - P_{n-1}) - (P_{n-1} - P_{n-2}) = (Q_2 - Q_1) - (Q_1 - Q_0)</span>.</li>
</ul>
<h3 id="recurrence-subdivision">Recurrence, Subdivision</h3>
<ul>
<li>Since <span class="math inline">B^n_i(t) = (1 - t)B_i^{n-1} + t B_{i-1}^{n-1}(t)</span>,</li>
</ul>
<p><span class="math display">\begin{aligned}
P(t) &= P_0^n(t) \\
P_i^k(t) &= (1 - t)P^{k-1}_i(t) + tP_{i+1}^{k-1} \\
P^0_i(t) &= P_i
\end{aligned}</span> Use to evaluate point at <span class="math inline">t</span>, subdivide into two new curves.</p>
<h3 id="spline-continuity">Spline Continuity</h3>
<ul>
<li><strong>Weierstrass Approximation Theorem</strong>: We can approximate any <span class="math inline">C^0</span> curve to any tolerance with polynomials, but may require a high degree.</li>
<li>High degree are non-local, expensive to evaluate, and slow to converge.</li>
</ul>
<h3 id="piecewise-polynomials">Piecewise Polynomials</h3>
<ul>
<li>Instead of one high degree polynomial, piece together lots of low degree polynomials.</li>
<li>Issue is continuity between pieces.</li>
</ul>
<h4 id="c0-piecewise-cubic-bezier"><span class="math inline">C^0</span> Piecewise Cubic Bezier</h4>
<ul>
<li>Use last control point of one segment to be first control point of the next segment, so the curves will meet at the endpoints.</li>
</ul>
<h4 id="c1-piecewise-cubic-bezier"><span class="math inline">C^1</span> Piecewise Cubic Bezier</h4>
<blockquote>
<p>We also need <span class="math inline">P_3 - P_2 = Q_1 - Q_0</span>.</p>
</blockquote>
<ul>
<li><strong>Cubic Hermite Interpolation</strong>: Given points <span class="math inline">P_0, ... P_N</span> and vectors <span class="math inline">v_0, ..., v_N</span>, we want to find a piecewise <span class="math inline">C^1</span> cubic polynomial such that <span class="math inline">P(i) = P_i</span>, <span class="math inline">P^\prime(i) = v_i</span>.
<ul>
<li>Create one cubic Bezier segment per interval.</li>
</ul></li>
</ul>
<p><span class="math display">\begin{aligned}
P_{i,0} &= P_i \\
P_{i,1} &= P_i + \frac{v_i}{3} \\
P_{i,2} &= P_{i+1} - \frac{v_{i + 1}}{3} \\
P_{i,3} &= P_{i+1}
\end{aligned}</span></p>
<ul>
<li><strong>Catmull-Rom Splines</strong>: Annoying to give derivatives, we want to just specify points.
<ul>
<li>Make up derivatives, <span class="math inline">v^i = \frac{P_{i+1} - P_{i-1}}{2}</span>.</li>
</ul></li>
</ul>
<h4 id="c2-piecewise-cubic-bezier"><span class="math inline">C^2</span> Piecewise Cubic Bezier</h4>
<ul>
<li><span class="math inline">A-frame</span> construction gives <span class="math inline">C^2</span> constraints on Bezier segments.</li>
<li>Hard to place points, so user places four control pounts, program places next tree.</li>
</ul>
<h3 id="tensor-product-patches">Tensor Product Patches</h3>
<ul>
<li><strong>Control polgon</strong> is polygonal mesh with vertices <span class="math inline">P_{i,j}</span>.</li>
<li><strong>Patch blending functions</strong> are the products of curve basis functions. <span class="math inline">P(s, t) = \sum_{i=0}^n\sum_{j=0}^n P_{i,j} B^n_{i,j}(s, t)</span>, where <span class="math inline">B^n_{i,j}(s, t) = B^n_i(s) B^n_j(t)</span>.</li>
</ul>
<h4 id="smoothly-joined-patches">Smoothly Joined Patches</h4>
<ul>
<li>Ensure that <span class="math inline">P_{i,n} - P_{i, n-1} = \beta (Q_{i,1} - Q_{i,0})</span>.</li>
</ul>
<h4 id="rendering">Rendering</h4>
<ul>
<li>Divide up into polygons by stepping over <span class="math inline">s, t \in [0, 1]</span> with some small <span class="math inline">\delta</span>.</li>
<li>Join up sides and diagonals to produce triangular mesh.</li>
<li>Alternatively, subdivide and render control polygon.</li>
</ul>
<h4 id="tensor-product-b-splines">Tensor Product B-splines</h4>