-
Notifications
You must be signed in to change notification settings - Fork 108
/
index.html
9899 lines (9519 loc) · 470 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-GB">
<head>
<meta charset="utf-8" />
<meta name="viewport" content="width=device-width, initial-scale=1" />
<title>A Primer on Bézier Curves</title>
<link rel="icon" href="images/favicon.png" type="image/png" />
<link rel="alternate" type="application/rss+xml" title="RSS" href="news/rss.xml" />
<!-- page styling -->
<link rel="preload" href="images/paper.png" as="image" />
<style>
:root[lang="en-GB"] {
font-family: "Helvetica Neue", Helvetica, Arial, sans-serif;
font-size: 18px;
}
</style>
<link rel="stylesheet" href="style.css" />
<!-- And a slew of SEO related meta elements, because being discoverable is important -->
<meta
name="description"
content="A detailed explanation of Bézier curves, and how to do the many things that we commonly want to do with them."
/>
<!-- opengraph information -->
<meta property="og:title" content="A Primer on Bézier Curves" />
<meta property="og:image" content="https://pomax.github.io/bezierinfo/images/og-image.png" />
<meta property="og:type" content="text" />
<meta property="og:url" content="https://pomax.github.io/bezierinfo" />
<meta
property="og:description"
content="A detailed explanation of Bézier curves, and how to do the many things that we commonly want to do with them."
/>
<meta property="og:locale" content="en-GB" />
<meta property="og:type" content="article" />
<meta property="og:published_time" content="2013-06-13T12:00:00+00:00" />
<meta property="og:updated_time" content="2024-06-19T22:12:56+00:00" />
<meta property="og:author" content="Mike 'Pomax' Kamermans" />
<meta property="og:section" content="Bézier Curves" />
<meta property="og:tag" content="Bézier Curves" />
<!-- twitter card information -->
<meta name="twitter:card" content="summary" />
<meta name="twitter:site" content="@TheRealPomax" />
<meta name="twitter:creator" content="@TheRealPomax" />
<meta name="twitter:image" content="https://pomax.github.io/bezierinfo/images/og-image.png" />
<meta name="twitter:url" content="https://pomax.github.io/bezierinfo" />
<meta
name="twitter:description"
content="A detailed explanation of Bézier curves, and how to do the many things that we commonly want to do with them."
/>
<!-- my own referral/page hit tracker, because Google knows enough -->
<script src="./js/site/referrer.js" type="module" async></script>
<!--
The part that makes interactive graphics work: an HTML5 <graphics-element> custom element.
Note that we're not defering this: we just want it to kick in as soon as possible, and
given how much HTML there is, that means this can, and thus should, kick in before the
document is done even transferring.
-->
<script src="./js/graphics-element/graphics-element.js" type="module" async></script>
<link rel="stylesheet" href="./js/graphics-element/graphics-element.css" />
<!-- make images lazy load much earlier -->
<script src="./js/site/better-lazy-loading.js" type="module" async defer></script>
</head>
<body>
<div class="dev" style="display: none;">
DEV PREVIEW ONLY
<script>
(function () {
var loc = window.location.toString();
if (loc.includes("localhost") || loc.includes("BezierInfo-2")) {
var e = document.querySelector("div.dev");
e.removeAttribute("style");
}
})();
</script>
</div>
<div class="github">
<img src="images/ribbon.png" alt="This page on GitHub" style="border: none;" usemap="#githubmap" width="200" height="149" />
<map name="githubmap">
<area shape="poly" coords="30,0, 200,0, 200,114" href="http://github.com/pomax/BezierInfo-2" alt="This page on GitHub" />
</map>
</div>
<div class="notforprint scl">
<img src="images/icons.gif" usemap="#rhtimap" title="Share this on social media" />
<map name="rhtimap">
<area
class="sclnk-rdt"
shape="rect"
coords="0, 0, 19, 15"
href="https://www.reddit.com/submit?url=https://pomax.github.io/bezierinfo&title=A Primer on Bézier Curves&text=A free, online book for when you really need to know how to do Bézier things."
alt="submit to reddit"
title="submit to reddit"
/>
<area
class="sclnk-hn"
shape="rect"
coords="0, 20, 19, 35"
href="https://news.ycombinator.com/submitlink?u=https://pomax.github.io/bezierinfo&t=A Primer on Bézier Curves"
alt="submit to hacker news"
title="submit to hacker news"
/>
<area
class="sclnk-twt"
shape="rect"
coords="0, 40, 19, 55"
href="https://twitter.com/intent/tweet?hashtags=bezier,curves,maths&original_referer=https://pomax.github.io/bezierinfo&text=Reading “A Primer on Bezier Curves” by @TheRealPomax over on https://pomax.github.io/bezierinfo"
alt="tweet your read"
title="tweet your read"
/>
</map>
</div>
<script src="./js/site/social-updater.js" async defer></script>
<header>
<h1>
A Primer on Bézier Curves<a class="rss-link" href="news/rss.xml"><img src="images/rss.png" /></a>
</h1>
<h2>A free, online book for when you really need to know how to do Bézier things.</h2>
<div>
<span>Read this in your own language:</span>
<ul class="lang-switcher">
<li><a href="./index.html">English</a> </li>
<li><a href="./ja-JP/index.html">日本語</a> <span class="localisation-progress">(24%)</span></li>
<li><a href="./zh-CN/index.html">中文</a> <span class="localisation-progress">(37%)</span></li>
<li><a href="./ru-RU/index.html">Русский</a> <span class="localisation-progress">(24%)</span></li>
<li><a href="./uk-UA/index.html">Українська</a> <span class="localisation-progress">(2%)</span></li>
<li><a href="./ko-KR/index.html">한국어</a> <span class="localisation-progress">(9%)</span></li>
</ul>
<p>
(Don't see your language listed, or want to see it reach 100%?
<a href="https://github.com/Pomax/BezierInfo-2/wiki/help-localize-the-primer-on-bezier-curves">Help translate this content!</a>)
</p>
</div>
<p>
Welcome to the Primer on Bezier Curves. This is a free website/ebook dealing with both the maths and programming aspects of Bezier Curves,
covering a wide range of topics relating to drawing and working with that curve that seems to pop up everywhere, from Photoshop paths to CSS
easing functions to Font outline descriptions.
</p>
<p>
If this is your first time here: welcome! Let me know if you were looking for anything in particular that the primer doesn't cover over on the
<a href="https://github.com/Pomax/BezierInfo-2/issues">issue tracker</a>!
</p>
<h2>Donations and sponsorship</h2>
<p>
If this is a resource that you're using for research, as work reference, or even writing your own software, please consider
<a href="https://www.paypal.com/donate/?cmd=_s-xclick&hosted_button_id=3BNHGHZAS3DP6&locale.x=en_CA">donating</a> (any amount helps) or
signing up as <a href="https://www.patreon.com/bezierinfo">a patron on Patreon</a>. I don't get paid to work on this, so if you find this site
valuable, and you'd like it to stick around for a long time to come, a lot of coffee went into writing this over the years, and a lot more
coffee will need to go into it yet: if you can spare a coffee, you'd be helping keep a resource alive and well.
</p>
<p>
Also, if you are a company and your staff uses this book as a resource, or you use it as an onboarding resource, then please: consider
sponsoring the site! I am more than happy to work with your finance department on sponsorship invoicing and recognition.
</p>
<!--
<div class="btcfh">
<div>
<h3>
Bitcoin donations:
</h3>
<p>
If you prefer to donate via Bitcoin, you can donate either directly to
<a class="btclk" href="bitcoin:3GY1HbQ2cH9V4xBLnRYdEfc42Nd1ZyjLZu?label=Primer%20on%20Bezier%20Curves">3GY1HbQ2cH9V4xBLnRYdEfc42Nd1ZyjLZu</a>
or use the QR code on the right, if that's the kind of convenience you prefer =)
</p>
</div>
<div class="btcqr">
<a href="bitcoin:3GY1HbQ2cH9V4xBLnRYdEfc42Nd1ZyjLZu?label=Primer%20on%20Bezier%20Curves">
<img src="./images/3GY1HbQ2cH9V4xBLnRYdEfc42Nd1ZyjLZu.PNG">
</a>
</div>
</div>
-->
<br style="clear: both;" />
<p>— <a href="https://mastodon.social/@TheRealPomax">Pomax</a></p>
<noscript>
<div class="note">
<header>
<h2>This site (obviously) works best with JS enabled</h2>
<h3>But it's not required.</h3>
</header>
<p>
If you're reading this text block, then you have scripts disabled: thankfully, that's perfectly fine, and this site is not going to punish
you for making smart choices around privacy and security in your browser. All the content will show just fine, you can still read the
text, navigate to sections, and see the graphics that are used to illustrate the concepts that individual sections talk about.
</p>
<p>
<strong>However</strong>, a big part of this primer's experience is the fact that all graphics are interactive, and for that to work, HTML
Custom Elements need to work, which requires Javascript to be enabled. If anything, you'll probably want to allow scripts to run just for
this site, and keep blocking everything else. Although that does mean you won't see comments, which use Disqus's comment system, and you
won't get convenient "share a link to the section you're reading right now" buttons, if that's something you like to do.
</p>
</div>
</noscript>
<nav aria-labelledby="toc">
<h1 id="toc">Table of Contents</h1>
<h4>Preamble</h4>
<ol class="preamble">
<li><a href="#preface">Preface </a></li>
<li><a href="#changelog">What's new</a></li>
</ol>
<h4>Main content</h4>
<ol>
<li><a href="#introduction">A lightning introduction</a></li>
<li><a href="#whatis">So what makes a Bézier Curve?</a></li>
<li><a href="#explanation">The mathematics of Bézier curves</a></li>
<li><a href="#control">Controlling Bézier curvatures</a></li>
<li><a href="#weightcontrol">Controlling Bézier curvatures, part 2: Rational Béziers</a></li>
<li><a href="#extended">The Bézier interval [0,1]</a></li>
<li><a href="#matrix">Bézier curvatures as matrix operations</a></li>
<li><a href="#decasteljau">de Casteljau's algorithm</a></li>
<li><a href="#flattening">Simplified drawing</a></li>
<li><a href="#splitting">Splitting curves</a></li>
<li><a href="#matrixsplit">Splitting curves using matrices</a></li>
<li><a href="#reordering">Lowering and elevating curve order</a></li>
<li><a href="#derivatives">Derivatives</a></li>
<li><a href="#pointvectors">Tangents and normals</a></li>
<li><a href="#pointvectors3d">Working with 3D normals</a></li>
<li><a href="#components">Component functions</a></li>
<li><a href="#extremities">Finding extremities: root finding</a></li>
<li><a href="#boundingbox">Bounding boxes</a></li>
<li><a href="#aligning">Aligning curves</a></li>
<li><a href="#tightbounds">Tight bounding boxes</a></li>
<li><a href="#inflections">Curve inflections</a></li>
<li><a href="#canonical">The canonical form (for cubic curves)</a></li>
<li><a href="#yforx">Finding Y, given X</a></li>
<li><a href="#arclength">Arc length</a></li>
<li><a href="#arclengthapprox">Approximated arc length</a></li>
<li><a href="#curvature">Curvature of a curve</a></li>
<li><a href="#tracing">Tracing a curve at fixed distance intervals</a></li>
<li><a href="#intersections">Intersections</a></li>
<li><a href="#curveintersection">Curve/curve intersection</a></li>
<li><a href="#abc">The projection identity</a></li>
<li><a href="#pointcurves">Creating a curve from three points</a></li>
<li><a href="#projections">Projecting a point onto a Bézier curve</a></li>
<li><a href="#circleintersection">Intersections with a circle</a></li>
<li><a href="#molding">Molding a curve</a></li>
<li><a href="#curvefitting">Curve fitting</a></li>
<li><a href="#catmullconv">Bézier curves and Catmull-Rom curves</a></li>
<li><a href="#catmullfitting">Creating a Catmull-Rom curve from three points</a></li>
<li><a href="#polybezier">Forming poly-Bézier curves</a></li>
<li><a href="#offsetting">Curve offsetting</a></li>
<li><a href="#graduatedoffset">Graduated curve offsetting</a></li>
<li><a href="#circles">Circles and quadratic Bézier curves</a></li>
<li><a href="#circles_cubic">Circular arcs and cubic Béziers</a></li>
<li><a href="#arcapproximation">Approximating Bézier curves with circular arcs</a></li>
<li><a href="#bsplines">B-Splines</a></li>
<li><a href="#comments">Comments and questions</a></li>
</ol>
</nav>
</header>
<main>
<section id="preface">
<h1>Preface</h1>
<p>
In order to draw things in 2D, we usually rely on lines, which typically get classified into two categories: straight lines, and curves. The
first of these are as easy to draw as they are easy to make a computer draw. Give a computer the first and last point in the line, and BAM!
straight line. No questions asked.
</p>
<p>
Curves, however, are a much bigger problem. While we can draw curves with ridiculous ease freehand, computers are a bit handicapped in that
they can't draw curves unless there is a mathematical function that describes how it should be drawn. In fact, they even need this for
straight lines, but the function is ridiculously easy, so we tend to ignore that as far as computers are concerned; all lines are
"functions", regardless of whether they're straight or curves. However, that does mean that we need to come up with fast-to-compute
functions that lead to nice looking curves on a computer. There are a number of these, and in this article we'll focus on a particular
function that has received quite a bit of attention and is used in pretty much anything that can draw curves: Bézier curves.
</p>
<p>
They're named after <a href="https://en.wikipedia.org/wiki/Pierre_B%C3%A9zier">Pierre Bézier</a>, who is principally responsible for making
them known to the world as a curve well-suited for design work (publishing his investigations in 1962 while working for Renault), although
he was not the first, or only one, to "invent" these type of curves. One might be tempted to say that the mathematician
<a href="https://en.wikipedia.org/wiki/Paul_de_Casteljau">Paul de Casteljau</a> was first, as he began investigating the nature of these
curves in 1959 while working at Citroën, and came up with a really elegant way of figuring out how to draw them. However, de Casteljau did
not publish his work, making the question "who was first" hard to answer in any absolute sense. Or is it? Bézier curves are, at their core,
"Bernstein polynomials", a family of mathematical functions investigated by
<a href="https://en.wikipedia.org/wiki/Sergei_Natanovich_Bernstein">Sergei Natanovich Bernstein</a>, whose publications on them date back at
least as far as 1912.
</p>
<p>
Anyway, that's mostly trivia, what you are more likely to care about is that these curves are handy: you can link up multiple Bézier curves
so that the combination looks like a single curve. If you've ever drawn Photoshop "paths" or worked with vector drawing programs like Flash,
Illustrator or Inkscape, those curves you've been drawing are Bézier curves.
</p>
<p>
But what if you need to program them yourself? What are the pitfalls? How do you draw them? What are the bounding boxes, how do you
determine intersections, how can you extrude a curve, in short: how do you do everything that you might want to do with these curves? That's
what this page is for. Prepare to be mathed!
</p>
<div class="note">
<h2>Virtually all Bézier graphics are interactive.</h2>
<p>
This page uses interactive examples, relying heavily on <a href="https://pomax.github.io/bezierjs/">Bezier.js</a>, as well as maths
formulae which are typeset into SVG using the <a href="https://ctan.org/pkg/xetex">XeLaTeX</a> typesetting system and
<a href="https://github.com/dawbarton/pdf2svg">pdf2svg</a> by <a href="https://cityinthesky.co.uk/">David Barton</a>.
</p>
<h2>This book is open source.</h2>
<p>
This book is an open source software project, and lives on two github repositories. The first is
<a href="https://github.com/pomax/bezierinfo">https://github.com/pomax/bezierinfo</a> and is the purely-for-presentation version you are
viewing right now. The other repository is <a href="https://github.com/pomax/BezierInfo-2">https://github.com/pomax/BezierInfo-2</a>,
which is the development version, housing all the code that gets turned <em>into</em> the web version, and is also where you should file
issues if you find bugs or have ideas on what to change or add to the primer.
</p>
<h2>How complicated is the maths going to be?</h2>
<p>
Most of the mathematics in this Primer are early high school maths. If you understand basic arithmetic, and you know how to read English,
you should be able to get by just fine. There will at times be <em>far</em> more complicated maths, but if you don't feel like digesting
them, you can safely skip over them by either skipping over the "detail boxes" in section or by just jumping to the end of a section with
maths that looks too involving. The end of sections typically simply list the conclusions so you can just work with those values directly.
</p>
<h2>What language is all this example code in?</h2>
<p>
There are way too many programming languages to favour one of all others, soo all the example code in this Primer uses a form of
pseudo-code that uses a syntax that's close enough to, but not actually, modern scripting languages like JS, Python, etc. That means you
won't be able to copy-paste any of it without giving it any thought, but that's intentional: if you're reading this primer, presumably you
want to <em>learn</em>, and you don't learn by copy-pasting. You learn by doing things yourself, <em>making mistakes</em>, and then fixing
those mistakes. Now, of course, I didn't intentionally add errors in the example code just to trick you into making mistakes (that would
be horrible!) but I <em>did</em> intentionally keep the code from favouring one programming language over another. Don't worry though, if
you know even a single procedural programming language, you should be able to read the examples without any difficulties.
</p>
<h2>Questions, comments:</h2>
<p>
If you have suggestions for new sections, hit up the <a href="https://github.com/pomax/BezierInfo-2/issues">Github issue tracker</a> (also
reachable from the repo linked to in the upper right). If you have questions about the material, there's currently no comment section
while I'm doing the rewrite, but you can use the issue tracker for that as well. Once the rewrite is done, I'll add a general comment
section back in, and maybe a more topical "select this section of text and hit the 'question' button to ask a question about it" system.
We'll see.
</p>
<h2>Help support the book!</h2>
<p>
If you enjoyed this book, or you simply found it useful for something you were trying to get done, and you were wondering how to let me
know you appreciated this book, you have two options: you can either head on over to the
<a href="https://www.patreon.com/bezierinfo">Patreon page</a> for this book, or if you prefer to make a one-time donation, head on over to
the <a href="https://www.paypal.com/donate/?cmd=_s-xclick&hosted_button_id=3BNHGHZAS3DP6&locale.x=en_CA">buy Pomax a coffee</a> page. This
work has grown from a small primer to a 100-plus print-page-equivalent reader on the subject of Bézier curves over the years, and a lot of
coffee went into the making of it. I don't regret a minute I spent on writing it, but I can always do with some more coffee to keep on
writing!
</p>
</div>
</section>
<section id="changelog">
<h1>What's new?</h1>
<p>
This primer is a living document, and so depending on when you last look at it, there may be new content. Click the following link to expand
this section to have a look at what got added, when, or click through to the <a href="./news">News posts</a> for more detailed updates. (<a
href="./news/rss.xml"
>RSS feed</a
>
available)
</p>
<!-- non-JS content reveals are nice -->
<label for="changelogtoggle">Toggle changes</label>
<input type="checkbox" id="changelogtoggle" />
<section>
<h2>November 2020</h2>
<ul>
<li><p>Added a section on finding curve/circle intersections</p></li>
</ul>
<h2>October 2020</h2>
<ul>
<li><p>Added the Ukranian locale! Help out in getting its localization to 100%!</p></li>
</ul>
<h2>August-September 2020</h2>
<ul>
<li>
<p>
Completely overhauled the site: the Primer is now a normal web page that works fine with JS disabled, but obviously better with JS
turned on.
</p>
</li>
</ul>
<h2>June 2020</h2>
<ul>
<li><p>Added automatic CI/CD using Github Actions</p></li>
</ul>
<h2>January 2020</h2>
<ul>
<li><p>Added reset buttons to all graphics</p></li>
<li><p>Updated to preface to correctly describe the on-page maths</p></li>
<li><p>Fixed the Catmull-Rom section because it had glaring maths errors</p></li>
</ul>
<h2>August 2019</h2>
<ul>
<li><p>Added a section on (plain) rational Bezier curves</p></li>
<li><p>Improved the Graphic component to allow for sliders</p></li>
</ul>
<h2>December 2018</h2>
<ul>
<li><p>Added a section on curvature and calculating kappa.</p></li>
<li>
<p>
Added a Patreon page! Head on over to <a href="https://www.patreon.com/bezierinfo">patreon.com/bezierinfo</a> to help support this
site!
</p>
</li>
</ul>
<h2>August 2018</h2>
<ul>
<li><p>Added a section on finding a curve's y, if all you have is the x coordinate.</p></li>
</ul>
<h2>July 2018</h2>
<ul>
<li><p>Rewrote the 3D normals section, implementing and explaining Rotation Minimising Frames.</p></li>
<li><p>Updated the section on curve order raising/lowering, showing how to get a least-squares optimized lower order curve.</p></li>
<li>
<p>(Finally) updated 'npm test' so that it automatically rebuilds when files are changed while the dev server is running.</p>
</li>
</ul>
<h2>June 2018</h2>
<ul>
<li><p>Added a section on direct curve fitting.</p></li>
<li><p>Added source links for all graphics.</p></li>
<li><p>Added this "What's new?" section.</p></li>
</ul>
<h2>April 2017</h2>
<ul>
<li><p>Added a section on 3d normals.</p></li>
<li><p>Added live-updating for the social link buttons, so they always link to the specific section you're reading.</p></li>
</ul>
<h2>February 2017</h2>
<ul>
<li><p>Finished rewriting the entire codebase for localization.</p></li>
</ul>
<h2>January 2016</h2>
<ul>
<li><p>Added a section to explain the Bezier interval.</p></li>
<li><p>Rewrote the Primer as a React application.</p></li>
</ul>
<h2>December 2015</h2>
<ul>
<li><p>Set up the split repository between BezierInfo-2 as development repository, and bezierinfo as live page.</p></li>
<li>
<p>
Removed the need for client-side LaTeX parsing entirely, so the site doesn't take a full minute or more to load all the graphics.
</p>
</li>
</ul>
<h2>May 2015</h2>
<ul>
<li><p>Switched over to pure JS rather than Processing-through-Processing.js</p></li>
<li><p>Added Cardano's algorithm for finding the roots of a cubic polynomial.</p></li>
</ul>
<h2>April 2015</h2>
<ul>
<li><p>Added a section on arc length approximations.</p></li>
</ul>
<h2>February 2015</h2>
<ul>
<li><p>Added a section on the canonical cubic Bezier form.</p></li>
</ul>
<h2>November 2014</h2>
<ul>
<li><p>Switched to HTTPS.</p></li>
</ul>
<h2>July 2014</h2>
<ul>
<li><p>Added the section on arc approximation.</p></li>
</ul>
<h2>April 2014</h2>
<ul>
<li><p>Added the section on Catmull-Rom fitting.</p></li>
</ul>
<h2>November 2013</h2>
<ul>
<li><p>Added the section on Catmull-Rom / Bezier conversion.</p></li>
<li><p>Added the section on Bezier cuves as matrices.</p></li>
</ul>
<h2>April 2013</h2>
<ul>
<li><p>Added a section on poly-Beziers.</p></li>
<li><p>Added a section on boolean shape operations.</p></li>
</ul>
<h2>March 2013</h2>
<ul>
<li><p>First drastic rewrite.</p></li>
<li><p>Added sections on circle approximations.</p></li>
<li><p>Added a section on projecting a point onto a curve.</p></li>
<li><p>Added a section on tangents and normals.</p></li>
<li><p>Added Legendre-Gauss numerical data tables.</p></li>
</ul>
<h2>October 2011</h2>
<ul>
<li>
<p>
First commit for the <a href="https://pomax.github.io/bezierinfo/">bezierinfo</a> site, based on the pre-Primer webpage that covered
the basics of Bezier curves in HTML with Processing.js examples.
</p>
</li>
</ul>
</section>
</section>
<section id="chapters">
<section id="introduction">
<h1>
<div class="nav"><a href="#toc">table of contents</a><a href="#whatis">next</a></div>
<a href="#introduction">A lightning introduction</a>
</h1>
<p>
Let's start with the good stuff: when we're talking about Bézier curves, we're talking about the things that you can see in the following
graphics. They run from some start point to some end point, with their curvature influenced by one or more "intermediate" control points.
Now, because all the graphics on this page are interactive, go manipulate those curves a bit: click-drag the points, and see how their
shape changes based on what you do.
</p>
<div class="figure">
<graphics-element title="A quadratic Bézier curve" width="275" height="275" src="./chapters/introduction/quadratic.js">
<fallback-image>
<span class="view-source">Scripts are disabled. Showing fallback image.</span>
<img width="275px" height="275px" src="./images/chapters/introduction/54e9ec0600ac436b0e6f0c6b5005cf03.png" loading="lazy" />
<label>A quadratic Bézier curve</label>
</fallback-image></graphics-element
>
<graphics-element title="A cubic Bézier curve" width="275" height="275" src="./chapters/introduction/cubic.js">
<fallback-image>
<span class="view-source">Scripts are disabled. Showing fallback image.</span>
<img width="275px" height="275px" src="./images/chapters/introduction/8d158a13e9a86969b99c64057644cbc6.png" loading="lazy" />
<label>A cubic Bézier curve</label>
</fallback-image></graphics-element
>
</div>
<p>
These curves are used a lot in computer aided design and computer aided manufacturing (CAD/CAM) applications, as well as in graphic design
programs like Adobe Illustrator and Photoshop, Inkscape, GIMP, etc. and in graphic technologies like scalable vector graphics (SVG) and
OpenType fonts (TTF/OTF). A lot of things use Bézier curves, so if you want to learn more about them... prepare to get your learn on!
</p>
</section>
<section id="whatis">
<h1>
<div class="nav"><a href="#introduction">previous</a><a href="#toc">table of contents</a><a href="#explanation">next</a></div>
<a href="#whatis">So what makes a Bézier Curve?</a>
</h1>
<p>
Playing with the points for curves may have given you a feel for how Bézier curves behave, but what <em>are</em> Bézier curves, really?
There are two ways to explain what a Bézier curve is, and they turn out to be the entirely equivalent, but one of them uses complicated
maths, and the other uses really simple maths. So... let's start with the simple explanation:
</p>
<p>
Bézier curves are the result of <a href="https://en.wikipedia.org/wiki/Linear_interpolation">linear interpolations</a>. That sounds
complicated but you've been doing linear interpolation since you were very young: any time you had to point at something between two other
things, you've been applying linear interpolation. It's simply "picking a point between two points".
</p>
<p>
If we know the distance between those two points, and we want a new point that is, say, 20% the distance away from the first point (and
thus 80% the distance away from the second point) then we can compute that really easily:
</p>
<!--
╭ p = some point ╮
│ 1 │
│ p = some other point │
│ 2 │
Given │ distance= (p - p ) │, our new point = p + distance · ratio
│ 2 1 │ 1
│ percentage │
│ ratio= ─────────── │
╰ 100 ╯
-->
<img class="LaTeX SVG" src="./images/chapters/whatis/c7f8cdd755d744412476b87230d0400d.svg" width="493px" height="103px" loading="lazy" />
<p>
So let's look at that in action: the following graphic is interactive in that you can use your up and down arrow keys to increase or
decrease the interpolation ratio, to see what happens. We start with three points, which gives us two lines. Linear interpolation over
those lines gives us two points, between which we can again perform linear interpolation, yielding a single point. And that point —and all
points we can form in this way for all ratios taken together— form our Bézier curve:
</p>
<graphics-element title="Linear Interpolation leading to Bézier curves" width="825" height="275" src="./chapters/whatis/interpolation.js">
<fallback-image>
<span class="view-source">Scripts are disabled. Showing fallback image.</span>
<img width="825px" height="275px" src="./images/chapters/whatis/524dd296e96c0fe2281fb95146f8ea65.png" loading="lazy" />
<label></label>
</fallback-image>
<input type="range" min="10" max="90" step="1" value="25" class="slide-control" />
</graphics-element>
<p>And that brings us to the complicated maths: calculus.</p>
<p>
While it doesn't look like that's what we've just done, we actually just drew a quadratic curve, in steps, rather than in a single go. One
of the fascinating parts about Bézier curves is that they can both be described in terms of polynomial functions, as well as in terms of
very simple interpolations of interpolations of [...]. That, in turn, means we can look at what these curves can do based on both "real
maths" (by examining the functions, their derivatives, and all that stuff), as well as by looking at the "mechanical" composition (which
tells us, for instance, that a curve will never extend beyond the points we used to construct it).
</p>
<p>
So let's start looking at Bézier curves a bit more in depth: their mathematical expressions, the properties we can derive from them, and
the various things we can do to, and with, Bézier curves.
</p>
</section>
<section id="explanation">
<h1>
<div class="nav"><a href="#whatis">previous</a><a href="#toc">table of contents</a><a href="#control">next</a></div>
<a href="#explanation">The mathematics of Bézier curves</a>
</h1>
<p>
Bézier curves are a form of "parametric" function. Mathematically speaking, parametric functions are cheats: a "function" is actually a
well defined term representing a mapping from any number of inputs to a <strong>single</strong> output. Numbers go in, a single number
comes out. Change the numbers that go in, and the number that comes out is still a single number.
</p>
<p>
Parametric functions cheat. They basically say "alright, well, we want multiple values coming out, so we'll just use more than one
function". An illustration: Let's say we have a function that maps some value, let's call it <i>x</i>, to some other value, using some
kind of number manipulation:
</p>
<!--
f(x) = cos (x)
-->
<img class="LaTeX SVG" src="./images/chapters/explanation/0cc876c56200446c60114c1b0eeeb2cc.svg" width="96px" height="17px" loading="lazy" />
<p>
The notation <i>f(x)</i> is the standard way to show that it's a function (by convention called <i>f</i> if we're only listing one) and
its output changes based on one variable (in this case, <i>x</i>). Change <i>x</i>, and the output for <i>f(x)</i> changes.
</p>
<p>So far, so good. Now, let's look at parametric functions, and how they cheat. Let's take the following two functions:</p>
<!--
f(a) = cos (a)
f(b) = sin (b)
-->
<img class="LaTeX SVG" src="./images/chapters/explanation/a2891980850ddbb27d308ac112d69f74.svg" width="93px" height="36px" loading="lazy" />
<p>
There's nothing really remarkable about them, they're just a sine and cosine function, but you'll notice the inputs have different names.
If we change the value for <i>a</i>, we're not going to change the output value for <i>f(b)</i>, since <i>a</i> isn't used in that
function. Parametric functions cheat by changing that. In a parametric function all the different functions share a variable, like this:
</p>
<!--
╭ f (t) = cos (t)
╡ a
│ f (t) = sin (t)
╰ b
-->
<img
class="LaTeX SVG"
src="./images/chapters/explanation/7acc94ec70f053fd10dab69d424b02a6.svg"
width="100px"
height="40px"
loading="lazy"
/>
<p>
Multiple functions, but only one variable. If we change the value for <i>t</i>, we change the outcome of both <i>f<sub>a</sub>(t)</i> and
<i>f<sub>b</sub>(t)</i>. You might wonder how that's useful, and the answer is actually pretty simple: if we change the labels
<i>f<sub>a</sub>(t)</i> and <i>f<sub>b</sub>(t)</i> with what we usually mean with them for parametric curves, things might be a lot more
obvious:
</p>
<!--
{ x = cos (t)
y = sin (t)
-->
<img class="LaTeX SVG" src="./images/chapters/explanation/6914ba615733c387251682db7a3db045.svg" width="77px" height="40px" loading="lazy" />
<p>There we go. <i>x</i>/<i>y</i> coordinates, linked through some mystery value <i>t</i>.</p>
<p>
So, parametric curves don't define a <i>y</i> coordinate in terms of an <i>x</i> coordinate, like normal functions do, but they instead
link the values to a "control" variable. If we vary the value of <i>t</i>, then with every change we get <strong>two</strong> values,
which we can use as (<i>x</i>,<i>y</i>) coordinates in a graph. The above set of functions, for instance, generates points on a circle: We
can range <i>t</i> from negative to positive infinity, and the resulting (<i>x</i>,<i>y</i>) coordinates will always lie on a circle with
radius 1 around the origin (0,0). If we plot it for <i>t</i> from 0 to 5, we get this:
</p>
<graphics-element title="A (partial) circle: x=sin(t), y=cos(t)" width="275" height="275" src="./chapters/explanation/circle.js">
<fallback-image>
<span class="view-source">Scripts are disabled. Showing fallback image.</span>
<img width="275px" height="275px" src="./images/chapters/explanation/959762e39ae32407e914a687d804ff3a.png" loading="lazy" />
<label>A (partial) circle: x=sin(t), y=cos(t)</label>
</fallback-image>
<input type="range" min="0" max="10" step="0.1" value="5" class="slide-control" />
</graphics-element>
<p>
Bézier curves are just one out of the many classes of parametric functions, and are characterised by using the same base function for all
of the output values. In the example we saw above, the <i>x</i> and <i>y</i> values were generated by different functions (one uses a
sine, the other a cosine); but Bézier curves use the "binomial polynomial" for both the <i>x</i> and <i>y</i> outputs. So what are
binomial polynomials?
</p>
<p>You may remember polynomials from high school. They're those sums that look like this:</p>
<!--
3 2
f(x) = a · x + b · x + c · x + d
-->
<img
class="LaTeX SVG"
src="./images/chapters/explanation/855a34c7f72733be6529c3fb33fa1a23.svg"
width="213px"
height="20px"
loading="lazy"
/>
<p>
If the highest order term they have is <i>x³</i>, they're called "cubic" polynomials; if it's <i>x²</i>, it's a "square" polynomial; if
it's just <i>x</i>, it's a line (and if there aren't even any terms with <i>x</i> it's not a polynomial!)
</p>
<p>
Bézier curves are polynomials of <i>t</i>, rather than <i>x</i>, with the value for <i>t</i> being fixed between 0 and 1, with
coefficients <i>a</i>, <i>b</i> etc. taking the "binomial" form, which sounds fancy but is actually a pretty simple description for mixing
values:
</p>
<!--
linear= (1-t) + t
2 2
square= (1-t) + 2 · (1-t) · t + t
3 2 2 3
cubic= (1-t) + 3 · (1-t) · t + 3 · (1-t) · t + t
-->
<img
class="LaTeX SVG"
src="./images/chapters/explanation/7f74178029422a35267fd033b392fe4c.svg"
width="367px"
height="64px"
loading="lazy"
/>
<p>
I know what you're thinking: that doesn't look too simple! But if we remove <i>t</i> and add in "times one", things suddenly look pretty
easy. Check out these binomial terms:
</p>
<!--
linear= 1 + 1
square= 1 + 2 + 1
cubic= 1 + 3 + 3 + 1
quartic= 1 + 4 + 6 + 4 + 1
-->
<img
class="LaTeX SVG"
src="./images/chapters/explanation/af40980136c291814e8970dc2a3d8e63.svg"
width="183px"
height="87px"
loading="lazy"
/>
<p>
Notice that 2 is the same as 1+1, and 3 is 2+1 and 1+2, and 6 is 3+3... As you can see, each time we go up a dimension, we simply start
and end with 1, and everything in between is just "the two numbers above it, added together", giving us a simple number sequence known as
<a href="https://en.wikipedia.org/wiki/Pascal%27s_triangle">Pascal's triangle</a>. Now <i>that's</i> easy to remember.
</p>
<p>
There's an equally simple way to figure out how the polynomial terms work: if we rename <i>(1-t)</i> to <i>a</i> and <i>t</i> to <i>b</i>,
and remove the weights for a moment, we get this:
</p>
<!--
linear= \colorblue a + \colorred b
square= \colorblue a · \colorblue a + \colorblue a · \colorred b + \colorred b · \colorred b
cubic= \colorblue a · \colorblue a · \colorblue a + \colorblue a · \colorblue a · \colorred b + \colorblue a · \colorred b · \colorred b + \co
lorred b · \colorred b · \colorred b
-->
<img
class="LaTeX SVG"
src="./images/chapters/explanation/4319b2e361960c842a4308a610a35048.svg"
width="300px"
height="60px"
loading="lazy"
/>
<p>
It's basically just a sum of "every combination of <i>a</i> and <i>b</i>", progressively replacing <i>a</i>'s with <i>b</i>'s after every
+ sign. So that's actually pretty simple too. So now you know binomial polynomials, and just for completeness I'm going to show you the
generic function for this:
</p>
<!--
__ n n-i i
Bézier(n,t) = ❯ \underset binomial term\underbrace\binomni · \ \underset polynomial term\underbrace(1-t) · t
‾‾ i=0
-->
<img
class="LaTeX SVG"
src="./images/chapters/explanation/39d33ea94e7527ed221a809ca6054174.svg"
width="289px"
height="55px"
loading="lazy"
/>
<p>
And that's the full description for Bézier curves. Σ in this function indicates that this is a series of additions (using the variable
listed below the Σ, starting at ...=<value> and ending at the value listed on top of the Σ).
</p>
<div class="howtocode">
<h3>How to implement the basis function</h3>
<p>We could naively implement the basis function as a mathematical construct, using the function as our guide, like this:</p>
<table class="code">
<tr>
<td>1</td>
<td rowspan="5">
<textarea disabled rows="5" role="doc-example">
function Bezier(n,t):
sum = 0
for(k=0; k<n; k++):
sum += n!/(k!*(n-k)!) * (1-t)^(n-k) * t^(k)
return sum</textarea
>
</td>
</tr>
<tr>
<td>2</td>
</tr>
<tr>
<td>3</td>
</tr>
<tr>
<td>4</td>
</tr>
<tr>
<td>5</td>
</tr>
</table>
<p>
I say we could, because we're not going to: the factorial function is <em>incredibly</em> expensive. And, as we can see from the above
explanation, we can actually create Pascal's triangle quite easily without it: just start at [1], then [1,1], then [1,2,1], then
[1,3,3,1], and so on, with each next row fitting 1 more number than the previous row, starting and ending with "1", with all the numbers
in between being the sum of the previous row's elements on either side "above" the one we're computing.
</p>
<p>
We can generate this as a list of lists lightning fast, and then never have to compute the binomial terms because we have a lookup
table:
</p>
<table class="code">
<tr>
<td>1</td>
<td rowspan="18">
<textarea disabled rows="18" role="doc-example">
lut = [ [1], // n=0
[1,1], // n=1
[1,2,1], // n=2
[1,3,3,1], // n=3
[1,4,6,4,1], // n=4
[1,5,10,10,5,1], // n=5
[1,6,15,20,15,6,1]] // n=6
function binomial(n,k):
while(n >= lut.length):
s = lut.length
nextRow = new array(size=s+1)
nextRow[0] = 1
for(i=1, prev=s-1; i<s; i++):
nextRow[i] = lut[prev][i-1] + lut[prev][i]
nextRow[s] = 1
lut.add(nextRow)
return lut[n][k]</textarea
>
</td>
</tr>
<tr>
<td>2</td>
</tr>
<tr>
<td>3</td>
</tr>
<tr>
<td>4</td>
</tr>
<tr>
<td>5</td>
</tr>
<tr>
<td>6</td>
</tr>
<tr>
<td>7</td>
</tr>
<tr>
<td>8</td>
</tr>
<tr>
<td>9</td>
</tr>
<tr>
<td>10</td>
</tr>
<tr>
<td>11</td>
</tr>
<tr>
<td>12</td>
</tr>
<tr>
<td>13</td>
</tr>
<tr>
<td>14</td>
</tr>
<tr>
<td>15</td>
</tr>
<tr>
<td>16</td>
</tr>
<tr>
<td>17</td>
</tr>
<tr>
<td>18</td>
</tr>
</table>
<p>
So what's going on here? First, we declare a lookup table with a size that's reasonably large enough to accommodate most lookups. Then,
we declare a function to get us the values we need, and we make sure that if an <i>n/k</i> pair is requested that isn't in the LUT yet,
we expand it first. Our basis function now looks like this:
</p>
<table class="code">
<tr>
<td>1</td>
<td rowspan="5">
<textarea disabled rows="5" role="doc-example">
function Bezier(n,t):
sum = 0
for(k=0; k<=n; k++):
sum += binomial(n,k) * (1-t)^(n-k) * t^(k)
return sum</textarea
>
</td>
</tr>
<tr>
<td>2</td>
</tr>
<tr>
<td>3</td>
</tr>
<tr>
<td>4</td>
</tr>
<tr>
<td>5</td>
</tr>
</table>
<p>
Perfect. Of course, we can optimize further. For most computer graphics purposes, we don't need arbitrary curves (although we will also
provide code for arbitrary curves in this primer); we need quadratic and cubic curves, and that means we can drastically simplify the
code:
</p>
<table class="code">
<tr>
<td>1</td>
<td rowspan="13">
<textarea disabled rows="13" role="doc-example">
function Bezier(2,t):
t2 = t * t
mt = 1-t
mt2 = mt * mt
return mt2 + 2*mt*t + t2
function Bezier(3,t):
t2 = t * t
t3 = t2 * t
mt = 1-t
mt2 = mt * mt
mt3 = mt2 * mt
return mt3 + 3*mt2*t + 3*mt*t2 + t3</textarea
>
</td>
</tr>
<tr>
<td>2</td>
</tr>
<tr>
<td>3</td>
</tr>
<tr>
<td>4</td>
</tr>
<tr>
<td>5</td>
</tr>
<tr>
<td>6</td>
</tr>
<tr>
<td>7</td>
</tr>
<tr>
<td>8</td>
</tr>
<tr>
<td>9</td>
</tr>
<tr>
<td>10</td>