https://pomax.github.io/bezierinfo/ DEV PREVIEW ONLY This page on GitHub [icons] A Primer on Bezier Curves[rss] A free, online book for when you really need to know how to do Bezier things. Read this in your own language: * English * Ri Ben Yu (24%) * Zhong Wen (22%) * Russkii (24%) * Ukrayins'ka (2%) * hangugeo (7%) (Don't see your language listed, or want to see it reach 100%? Help translate this content!) 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. 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 issue tracker! Donations and sponsorship If this is a resource that you're using for research, as work reference, or even writing your own software, please consider donating (any amount helps) or signing up as a patron on Patreon. 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. 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. -- Pomax This site (obviously) works best with JS enabled But it's not required. 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. However, 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. Table of Contents Preamble 1. Preface 2. What's new Main content 1. A lightning introduction 2. So what makes a Bezier Curve? 3. The mathematics of Bezier curves 4. Controlling Bezier curvatures 5. Controlling Bezier curvatures, part 2: Rational Beziers 6. The Bezier interval [0,1] 7. Bezier curvatures as matrix operations 8. de Casteljau's algorithm 9. Simplified drawing 10. Splitting curves 11. Splitting curves using matrices 12. Lowering and elevating curve order 13. Derivatives 14. Tangents and normals 15. Working with 3D normals 16. Component functions 17. Finding extremities: root finding 18. Bounding boxes 19. Aligning curves 20. Tight bounding boxes 21. Curve inflections 22. The canonical form (for cubic curves) 23. Finding Y, given X 24. Arc length 25. Approximated arc length 26. Curvature of a curve 27. Tracing a curve at fixed distance intervals 28. Intersections 29. Curve/curve intersection 30. The projection identity 31. Creating a curve from three points 32. Projecting a point onto a Bezier curve 33. Intersections with a circle 34. Molding a curve 35. Curve fitting 36. Bezier curves and Catmull-Rom curves 37. Creating a Catmull-Rom curve from three points 38. Forming poly-Bezier curves 39. Curve offsetting 40. Graduated curve offsetting 41. Circles and quadratic Bezier curves 42. Circular arcs and cubic Beziers 43. Approximating Bezier curves with circular arcs 44. B-Splines 45. Comments and questions Preface 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. 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: Bezier curves. They're named after Pierre Bezier, 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 Paul de Casteljau was first, as he began investigating the nature of these curves in 1959 while working at Citroen, 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? Bezier curves are, at their core, "Bernstein polynomials", a family of mathematical functions investigated by Sergei Natanovich Bernstein, whose publications on them date back at least as far as 1912. Anyway, that's mostly trivia, what you are more likely to care about is that these curves are handy: you can link up multiple Bezier 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 Bezier curves. 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! Virtually all Bezier graphics are interactive. This page uses interactive examples, relying heavily on Bezier.js, as well as maths formulae which are typeset into SVG using the XeLaTeX typesetting system and pdf2svg by David Barton. This book is open source. This book is an open source software project, and lives on two github repositories. The first is https://github.com/pomax/bezierinfo and is the purely-for-presentation version you are viewing right now. The other repository is https://github.com/pomax/BezierInfo-2, which is the development version, housing all the code that gets turned into 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. How complicated is the maths going to be? 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 far 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. What language is all this example code in? 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 learn, and you don't learn by copy-pasting. You learn by doing things yourself, making mistakes, 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 did 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. Questions, comments: If you have suggestions for new sections, hit up the Github issue tracker (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. Help support the book! 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 Patreon page for this book, or if you prefer to make a one-time donation, head on over to the buy Pomax a coffee page. This work has grown from a small primer to a 100-plus print-page-equivalent reader on the subject of Bezier 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! What's new? 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 News posts for more detailed updates. (RSS feed available) Toggle changes [ ] November 2020 * Added a section on finding curve/circle intersections October 2020 * Added the Ukranian locale! Help out in getting its localization to 100%! August-September 2020 * 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. June 2020 * Added automatic CI/CD using Github Actions January 2020 * Added reset buttons to all graphics * Updated to preface to correctly describe the on-page maths * Fixed the Catmull-Rom section because it had glaring maths errors August 2019 * Added a section on (plain) rational Bezier curves * Improved the Graphic component to allow for sliders December 2018 * Added a section on curvature and calculating kappa. * Added a Patreon page! Head on over to patreon.com/bezierinfo to help support this site! August 2018 * Added a section on finding a curve's y, if all you have is the x coordinate. July 2018 * Rewrote the 3D normals section, implementing and explaining Rotation Minimising Frames. * Updated the section on curve order raising/lowering, showing how to get a least-squares optimized lower order curve. * (Finally) updated 'npm test' so that it automatically rebuilds when files are changed while the dev server is running. June 2018 * Added a section on direct curve fitting. * Added source links for all graphics. * Added this "What's new?" section. April 2017 * Added a section on 3d normals. * Added live-updating for the social link buttons, so they always link to the specific section you're reading. February 2017 * Finished rewriting the entire codebase for localization. January 2016 * Added a section to explain the Bezier interval. * Rewrote the Primer as a React application. December 2015 * Set up the split repository between BezierInfo-2 as development repository, and bezierinfo as live page. * 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. May 2015 * Switched over to pure JS rather than Processing-through-Processing.js * Added Cardano's algorithm for finding the roots of a cubic polynomial. April 2015 * Added a section on arc length approximations. February 2015 * Added a section on the canonical cubic Bezier form. November 2014 * Switched to HTTPS. July 2014 * Added the section on arc approximation. April 2014 * Added the section on Catmull-Rom fitting. November 2013 * Added the section on Catmull-Rom / Bezier conversion. * Added the section on Bezier cuves as matrices. April 2013 * Added a section on poly-Beziers. * Added a section on boolean shape operations. March 2013 * First drastic rewrite. * Added sections on circle approximations. * Added a section on projecting a point onto a curve. * Added a section on tangents and normals. * Added Legendre-Gauss numerical data tables. October 2011 * First commit for the bezierinfo site, based on the pre-Primer webpage that covered the basics of Bezier curves in HTML with Processing.js examples. table of contentsnext A lightning introduction Let's start with the good stuff: when we're talking about Bezier 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. Scripts are disabled. Showing fallback image. [54e9ec0600ac436b0e6f0c6b5005cf03] A quadratic Bezier curve Scripts are disabled. Showing fallback image. [8d158a13e9a86969b99c64057644cbc6] A cubic Bezier curve 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 Bezier curves, so if you want to learn more about them... prepare to get your learn on! previoustable of contentsnext So what makes a Bezier Curve? Playing with the points for curves may have given you a feel for how Bezier curves behave, but what are Bezier curves, really? There are two ways to explain what a Bezier 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: Bezier curves are the result of linear interpolations. 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". 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: [c7f8cdd755d744412476b87230d0400d] 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 Bezier curve: Scripts are disabled. Showing fallback image. [524dd296e96c0fe2281fb95146f8ea65] [25 ] And that brings us to the complicated maths: calculus. 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 Bezier 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). So let's start looking at Bezier 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, Bezier curves. previoustable of contentsnext The mathematics of Bezier curves Bezier 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 single 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. 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 x, to some other value, using some kind of number manipulation: [0cc876c56200] The notation f(x) is the standard way to show that it's a function (by convention called f if we're only listing one) and its output changes based on one variable (in this case, x). Change x, and the output for f(x) changes. So far, so good. Now, let's look at parametric functions, and how they cheat. Let's take the following two functions: [a2891980850d] 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 a, we're not going to change the output value for f(b), since a 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: [7acc94ec70f05] Multiple functions, but only one variable. If we change the value for t, we change the outcome of both f[a](t) and f[b](t). You might wonder how that's useful, and the answer is actually pretty simple: if we change the labels f[a](t) and f[b](t) with what we usually mean with them for parametric curves, things might be a lot more obvious: [6914ba615] There we go. x/y coordinates, linked through some mystery value t. So, parametric curves don't define a y coordinate in terms of an x coordinate, like normal functions do, but they instead link the values to a "control" variable. If we vary the value of t, then with every change we get two values, which we can use as (x,y) coordinates in a graph. The above set of functions, for instance, generates points on a circle: We can range t from negative to positive infinity, and the resulting (x,y) coordinates will always lie on a circle with radius 1 around the origin (0,0). If we plot it for t from 0 to 5, we get this: Scripts are disabled. Showing fallback image. [959762e39ae32407e914a687d804ff3a] A (partial) circle: x=sin(t), y= cos(t) [5 ] Bezier 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 x and y values were generated by different functions (one uses a sine, the other a cosine); but Bezier curves use the "binomial polynomial" for both the x and y outputs. So what are binomial polynomials? You may remember polynomials from high school. They're those sums that look like this: [855a34c7f72733be6529c3fb33fa1] If the highest order term they have is x3, they're called "cubic" polynomials; if it's x2, it's a "square" polynomial; if it's just x, it's a line (and if there aren't even any terms with x it's not a polynomial!) Bezier curves are polynomials of t, rather than x, with the value for t being fixed between 0 and 1, with coefficients a, b etc. taking the "binomial" form, which sounds fancy but is actually a pretty simple description for mixing values: [7f74178029422a35267fd033b392fe4c] I know what you're thinking: that doesn't look too simple! But if we remove t and add in "times one", things suddenly look pretty easy. Check out these binomial terms: [af40980136c291814e8970dc2] 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 Pascal's triangle. Now that's easy to remember. There's an equally simple way to figure out how the polynomial terms work: if we rename (1-t) to a and t to b, and remove the weights for a moment, we get this: [4319b2e361960c842a4308a610a35048] It's basically just a sum of "every combination of a and b", progressively replacing a's with b'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: [39d33ea94e7527ed221a809ca6054174] And that's the full description for Bezier curves. S in this function indicates that this is a series of additions (using the variable listed below the S, starting at ...= and ending at the value listed on top of the S). How to implement the basis function We could naively implement the basis function as a mathematical construct, using the function as our guide, like this: 1 [function Bezier(n,t)] 2 [ sum = 0 ] 3 [ for(k=0; k= lut.len] 11 [ s = lut.length ] 12 [ nextRow = new ar] 13 [ nextRow[0] = 1 ] 14 [ for(i=1, prev=s-] 15 [ nextRow[i] = l] 16 [ nextRow[s] = 1 ] 17 [ lut.add(nextRow)] 18 [ return lut[n][k] ] 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 n/k pair is requested that isn't in the LUT yet, we expand it first. Our basis function now looks like this: 1 [function Bezier(n,t)] 2 [ sum = 0 ] 3 [ for(k=0; k<=n; k++] 4 [ sum += binomial(] 5 [ return sum ] 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: 1 [function Bezier(2,t)] 2 [ t2 = t * t ] 3 [ mt = 1-t ] 4 [ mt2 = mt * mt ] 5 [ return mt2 + 2*mt*] 6 [ ] 7 [function Bezier(3,t)] 8 [ t2 = t * t ] 9 [ t3 = t2 * t ] 10 [ mt = 1-t ] 11 [ mt2 = mt * mt ] 12 [ mt3 = mt2 * mt ] 13 [ return mt3 + 3*mt2] And now we know how to program the basis function. Excellent. So, now we know what the basis function looks like, time to add in the magic that makes Bezier curves so special: control points. previoustable of contentsnext Controlling Bezier curvatures Bezier curves are, like all "splines", interpolation functions. This means that they take a set of points, and generate values somewhere "between" those points. (One of the consequences of this is that you'll never be able to generate a point that lies outside the outline for the control points, commonly called the "hull" for the curve. Useful information!). In fact, we can visualize how each point contributes to the value generated by the function, so we can see which points are important, where, in the curve. The following graphs show the interpolation functions for quadratic and cubic curves, with "S" being the strength of a point's contribution to the total sum of the Bezier function. Click-and-drag to see the interpolation percentages for each curve-defining point at a specific t value. Scripts are disabled. Showing fallback image. [8332e5d34b7344bbee2a2e1f4521ce46] Quadratic interpolations [0 ] Scripts are disabled. Showing fallback image. [1b8c5e574dc67bfb0afc3fb0a8727378] Cubic interpolations [0 ] Scripts are disabled. Showing fallback image. [c26d2655e8741ef7e2eeb4f6554fc7a5] 15th degree interpolations [0 ] Also shown is the interpolation function for a 15^th order Bezier function. As you can see, the start and end point contribute considerably more to the curve's shape than any other point in the control point set. If we want to change the curve, we need to change the weights of each point, effectively changing the interpolations. The way to do this is about as straightforward as possible: just multiply each point with a value that changes its strength. These values are conventionally called "weights", and we can add them to our original Bezier function: [c2f2fe0ef5d0089d9dd8e5e3999405cb] That looks complicated, but as it so happens, the "weights" are actually just the coordinate values we want our curve to have: for an n^th order curve, w[0] is our start coordinate, w[n] is our last coordinate, and everything in between is a controlling coordinate. Say we want a cubic curve that starts at (110,150), is controlled by (25,190) and (210,250) and ends at (210,30), we use this Bezier curve: [be73034ac382b54863c7a18c2932cbbc] Which gives us the curve we saw at the top of the article: Scripts are disabled. Showing fallback image. [8d158a13e9a86969b99c64057644cbc6] Our cubic Bezier curve What else can we do with Bezier curves? Quite a lot, actually. The rest of this article covers a multitude of possible operations and algorithms that we can apply, and the tasks they achieve. How to implement the weighted basis function Given that we already know how to implement basis function, adding in the control points is remarkably easy: 1 [function Bezier(n,t,] 2 [ sum = 0 ] 3 [ for(k=0; k<=n; k++] 4 [ sum += w[k] * bi] 5 [ return sum ] And now for the optimized versions: 1 [function Bezier(2,t,] 2 [ t2 = t * t ] 3 [ mt = 1-t ] 4 [ mt2 = mt * mt ] 5 [ return w[0]*mt2 + ] 6 [ ] 7 [function Bezier(3,t,] 8 [ t2 = t * t ] 9 [ t3 = t2 * t ] 10 [ mt = 1-t ] 11 [ mt2 = mt * mt ] 12 [ mt3 = mt2 * mt ] 13 [ return w[0]*mt3 + ] And now we know how to program the weighted basis function. previoustable of contentsnext Controlling Bezier curvatures, part 2: Rational Beziers We can further control Bezier curves by "rationalising" them: that is, adding a "ratio" value in addition to the weight value discussed in the previous section, thereby gaining control over "how strongly" each coordinate influences the curve. Adding these ratio values to the regular Bezier curve function is fairly easy. Where the regular function is the following: [ceac4259d2aed0767c7765d2237ca1a3] The function for rational Bezier curves has two more terms: [942e3b3cacc7f403ad95fcd4acce7d19] In this, the first new term represents an additional weight for each coordinate. For example, if our ratio values are [1, 0.5, 0.5, 1] then ratio[0] = 1, ratio[1] = 0.5, and so on, and is effectively identical as if we were just using different weight. So far, nothing too special. However, the second new term is what makes the difference: every point on the curve isn't just a "double weighted" point, it is a fraction of the "doubly weighted" value we compute by introducing that ratio. When computing points on the curve, we compute the "normal" Bezier value and then divide that by the Bezier value for the curve that only uses ratios, not weights. This does something unexpected: it turns our polynomial into something that isn't a polynomial anymore. It is now a kind of curve that is a super class of the polynomials, and can do some really cool things that Bezier curves can't do "on their own", such as perfectly describing circles (which we'll see in a later section is literally impossible using standard Bezier curves). But the best way to show what this does is to do literally that: let's look at the effect of "rationalising" our Bezier curves using an interactive graphic for a rationalised curves. The following graphic shows the Bezier curve from the previous section, "enriched" with ratio factors for each coordinate. The closer to zero we set one or more terms, the less relative influence the associated coordinate exerts on the curve (and of course the higher we set them, the more influence they have). Try to change the values and see how it affects what gets drawn: Scripts are disabled. Showing fallback image. [3d71e2b9373684eebcb0dc8563f70b18] Our rational cubic Bezier curve [1 ] [1 ] [1 ] [1 ] You can think of the ratio values as each coordinate's "gravity": the higher the gravity, the closer to that coordinate the curve will want to be. You'll also notice that if you simply increase or decrease all the ratios by the same amount, nothing changes... much like with gravity, if the relative strengths stay the same, nothing really changes. The values define each coordinate's influence relative to all other points. How to implement rational curves Extending the code of the previous section to include ratios is almost trivial: 1 [function RationalBez] 2 [ t2 = t * t ] 3 [ mt = 1-t ] 4 [ mt2 = mt * mt ] 5 [ f = [ ] 6 [ r[0] * mt2, ] 7 [ 2 * r[1] * mt * ] 8 [ r[2] * t2 ] 9 [ ] ] 10 [ basis = f[0] + f[1] 11 [ return (f[0] * w[0] 12 [ ] 13 [function RationalBez] 14 [ t2 = t * t ] 15 [ t3 = t2 * t ] 16 [ mt = 1-t ] 17 [ mt2 = mt * mt ] 18 [ mt3 = mt2 * mt ] 19 [ f = [ ] 20 [ r[0] * mt3, ] 21 [ 3 * r[1] * mt2 *] 22 [ 3 * r[2] * mt * ] 23 [ r[3] * t3 ] 24 [ ] ] 25 [ basis = f[0] + f[1] 26 [ return (f[0] * w[0] And that's all we have to do. previoustable of contentsnext The Bezier interval [0,1] Now that we know the mathematics behind Bezier curves, there's one curious thing that you may have noticed: they always run from t=0 to t=1. Why that particular interval? It all has to do with how we run from "the start" of our curve to "the end" of our curve. If we have a value that is a mixture of two other values, then the general formula for this is: [dfd6ded3f0addcf43e0a1581627a2] The obvious start and end values here need to be a=1, b=0, so that the mixed value is 100% value 1, and 0% value 2, and a=0, b=1, so that the mixed value is 0% value 1 and 100% value 2. Additionally, we don't want "a" and "b" to be independent: if they are, then we could just pick whatever values we like, and end up with a mixed value that is, for example, 100% value 1 and 100% value 2. In principle that's fine, but for Bezier curves we always want mixed values between the start and end point, so we need to make sure we can never set "a" and "b" to some values that lead to a mix value that sums to more than 100%. And that's easy: [4e0fa763b173e3a683587acf83733] With this we can guarantee that we never sum above 100%. By restricting a to values in the interval [0,1], we will always be somewhere between our two values (inclusively), and we will always sum to a 100% mix. But... what if we use this form, which is based on the assumption that we will only ever use values between 0 and 1, and instead use values outside of that interval? Do things go horribly wrong? Well... not really, but we get to "see more". In the case of Bezier curves, extending the interval simply makes our curve "keep going". Bezier curves are simply segments of some polynomial curve, so if we pick a wider interval we simply get to see more of the curve. So what do they look like? The following two graphics show you Bezier curves rendered "the usual way", as well as the curves they "lie on" if we were to extend the t values much further. As you can see, there's a lot more "shape" hidden in the rest of the curve, and we can model those parts by moving the curve points around. Scripts are disabled. Showing fallback image. [37948bde4bf0d25bde85f172bf55b9fb] Quadratic infinite interval Bezier curve Scripts are disabled. Showing fallback image. [2d17acb381ebdd28f0ff43be00d723c4] Cubic infinite interval Bezier curve In fact, there are curves used in graphics design and computer modelling that do the opposite of Bezier curves; rather than fixing the interval, and giving you freedom to choose the coordinates, they fix the coordinates, but give you freedom over the interval. A great example of this is the "Spiro" curve, which is a curve based on part of a Cornu Spiral, also known as Euler's Spiral. It's a very aesthetically pleasing curve and you'll find it in quite a few graphics packages like FontForge and Inkscape. It has even been used in font design, for example for the Inconsolata typeface. previoustable of contentsnext Bezier curvatures as matrix operations We can also represent Bezier curves as matrix operations, by expressing the Bezier formula as a polynomial basis function and a coefficients matrix, and the actual coordinates as a matrix. Let's look at what this means for the cubic curve, using P[...] to refer to coordinate values "in one or more dimensions": [9a9a55f5b0323d9ea88f82fc6be58ad3] Disregarding our actual coordinates for a moment, we have: [87cfac83cb8a4b0bee68ef006effc611] We can write this as a sum of four expressions: [cdd88611833f3b178d] And we can expand these expressions: [ec118f296511c6e9ac8727be3703a7ce] Furthermore, we can make all the 1 and 0 factors explicit: [67a5ea33d6c6558f7d954b18226f4] And that, we can view as a series of four matrix operations: [8ecff6b8a37d60385d287ea2b26876db] If we compact this into a single matrix operation, we get: [b9527f7d5a0f5d2d737eac118d69243] This kind of polynomial basis representation is generally written with the bases in increasing order, which means we need to flip our t matrix horizontally, and our big "mixing" matrix upside down: [1a64ed455c6dd2f8cacca5e5e12bdcc] And then finally, we can add in our original coordinates as a single third matrix: [b32cae2dfc47d5f36df0bc3defb7dfa8] We can perform the same trick for the quadratic curve, in which case we end up with: [1bae50fefa43210b3a6259d1984f6cbc] If we plug in a t value, and then multiply the matrices, we will get exactly the same values as when we evaluate the original polynomial function, or as when we evaluate the curve using progressive linear interpolation. So: why would we bother with matrices? Matrix representations allow us to discover things about functions that would otherwise be hard to tell. It turns out that the curves form triangular matrices, and they have a determinant equal to the product of the actual coordinates we use for our curve. It's also invertible, which means there's a ton of properties that are all satisfied. Of course, the main question is "why is this useful to us now?", and the answer to that is that it's not immediately useful, but you'll be seeing some instances where certain curve properties can be either computed via function manipulation, or via clever use of matrices, and sometimes the matrix approach can be (drastically) faster. So for now, just remember that we can represent curves this way, and let's move on. previoustable of contentsnext de Casteljau's algorithm If we want to draw Bezier curves, we can run through all values of t from 0 to 1 and then compute the weighted basis function at each value, getting the x/y values we need to plot. Unfortunately, the more complex the curve gets, the more expensive this computation becomes. Instead, we can use de Casteljau's algorithm to draw curves. This is a geometric approach to curve drawing, and it's really easy to implement. So easy, in fact, you can do it by hand with a pencil and ruler. Rather than using our calculus function to find x/y values for t, let's do this instead: * treat t as a ratio (which it is). t=0 is 0% along a line, t=1 is 100% along a line. * Take all lines between the curve's defining points. For an order n curve, that's n lines. * Place markers along each of these line, at distance t. So if t is 0.2, place the mark at 20% from the start, 80% from the end. * Now form lines between those points. This gives n-1 lines. * Place markers along each of these line at distance t. * Form lines between those points. This'll be n-2 lines. * Place markers, form lines, place markers, etc. * Repeat this until you have only one line left. The point t on that line coincides with the original curve point at t. To see this in action, move the slider for the following sketch to changes which curve point is explicitly evaluated using de Casteljau's algorithm. Scripts are disabled. Showing fallback image. [df92f529841f39decf9ad62b0967855a] Traversing a curve using de Casteljau's algorithm [0 ] How to implement de Casteljau's algorithm Let's just use the algorithm we just specified, and implement that as a function that can take a list of curve-defining points, and a t value, and draws the associated point on the curve for that t value: 1 [function drawCurvePo] 2 [ if(points.length==] 3 [ draw(points[0]) ] 4 [ else: ] 5 [ newpoints=array(] 6 [ for(i=0; iS+d1, 0,L, s,e), d1 = distance along curve to projection of c1 * c2: map(S+d2, 0,L, s,e), d2 = distance along curve to projection of c2 * ... * end: map(S+length(subcurve), 0,L, s,e) At each of the relevant points (start, end, and the projections of the control points onto the curve) we know the curve's normal, so offsetting is simply a matter of taking our original point, and moving it along the normal vector by the offset distance for each point. Doing so will give us the following result (these have with a starting width of 0, and an end width of 40 pixels, but can be controlled with your up and down arrow keys): Scripts are disabled. Showing fallback image. [8cc724d5343c65685d88c92b2d069a2a] Offsetting a quadratic Bezier curve [20 ] Scripts are disabled. Showing fallback image. [17bf62e05a1fc3387b0c210f2decff45] Offsetting a cubic Bezier curve [20 ] previoustable of contentsnext Circles and quadratic Bezier curves Circles and Bezier curves are very different beasts, and circles are infinitely easier to work with than Bezier curves. Their formula is much simpler, and they can be drawn more efficiently. But, sometimes you don't have the luxury of using circles, or ellipses, or arcs. Sometimes, all you have are Bezier curves. For instance, if you're doing font design, fonts have no concept of geometric shapes, they only know straight lines, and Bezier curves. OpenType fonts with TrueType outlines only know quadratic Bezier curves, and OpenType fonts with Type 2 outlines only know cubic Bezier curves. So how do you draw a circle, or an ellipse, or an arc? You approximate. We already know that Bezier curves cannot model all curves that we can think of, and this includes perfect circles, as well as ellipses, and their arc counterparts. However, we can certainly approximate them to a degree that is visually acceptable. Quadratic and cubic curves offer us different curvature control, so in order to approximate a circle we will first need to figure out what the error is if we try to approximate arcs of increasing degree with quadratic and cubic curves, and where the coordinates even lie. Since arcs are mid-point-symmetrical, we need the control points to set up a symmetrical curve. For quadratic curves this means that the control point will be somewhere on a line that intersects the baseline at a right angle. And we don't get any choice on where that will be, since the derivatives at the start and end point have to line up, so our control point will lie at the intersection of the tangents at the start and end point. First, let's try to fit the quadratic curve onto a circular arc. In the following sketch you can move the mouse around over a unit circle, to see how well, or poorly, a quadratic curve can approximate the arc from (1,0) to where your mouse cursor is: Scripts are disabled. Showing fallback image. [08ca09aacb271735e063e7e8d941a195] [-0.7854 ] As you can see, things go horribly wrong quite quickly; even trying to approximate a quarter circle using a quadratic curve is a bad idea. An eighth of a turns might look okay, but how okay is okay? Let's apply some maths and find out. What we're interested in is how far off our on-curve coordinates are with respect to a circular arc, given a specific start and end angle. We'll be looking at how much space there is between the circular arc, and the quadratic curve's midpoint. We start out with our start and end point, and for convenience we will place them on a unit circle (a circle around 0,0 with radius 1), at some angle ph: [7ab3da0922477af4cc09f58] What we want to find is the intersection of the tangents, so we want a point C such that: [d4bfb47b623c968e3231566c9705c6c4] i.e. we want a point that lies on the vertical line through S (at some distance a from S) and also lies on the tangent line through E (at some distance b from E). Solving this gives us: [8237af1396bb567d70c8b5e4dd7f81] First we solve for b: [1829e42ea956ee4df0e45d9ac5334ef7] which yields: [06369b0033831] which we can then substitute in the expression for a: [5a23f3bc298c85540c6dd18e304d922] A quick check shows that plugging these values for a and b into the expressions for C[x] and C[y] give the same x/y coordinates for both "a away from A" and "b away from B", so let's continue: now that we know the coordinate values for C, we know where our on-curve point T for t=0.5 (or angle ph/2) is, because we can just evaluate the Bezier polynomial, and we know where the circle arc's actual point P is for angle ph/2: [8b4e1d0a62380ed011f27c645] We compute T, observing that if t=0.5, the polynomial values (1-t)2, 2(1-t)t, and t2 are 0.25, 0.5, and 0.25 respectively: [a04bd1558a76e60b8ca6e1fe4fa38c00] Which, worked out for the x and y components, gives: [986ae9104e0bc52e95689ae7ae4504db] And the distance between these two is the standard Euclidean distance: [942c90bc8311e49d94059b3127fc78d5] So, what does this distance function look like when we plot it for a number of ranges for the angle ph, such as a half circle, quarter circle and eighth circle? [arc-q-pi] plotted [arc-q-pi2] plotted for [arc-q-pi4] plotted for for 0 <= ph <= p: 0 <= ph <= 1/2p: 0 <= ph <= 1/4p: We now see why the eighth circle arc looks decent, but the quarter circle arc doesn't: an error of roughly 0.06 at t=0.5 means we're 6% off the mark... we will already be off by one pixel on a circle with pixel radius 17. Any decent sized quarter circle arc, say with radius 100px, will be way off if approximated by a quadratic curve! For the eighth circle arc, however, the error is only roughly 0.003, or 0.3%, which explains why it looks so close to the actual eighth circle arc. In fact, if we want a truly tiny error, like 0.001, we'll have to contend with an angle of (rounded) 0.593667, which equates to roughly 34 degrees. We'd need 11 quadratic curves to form a full circle with that precision! (technically, 10 and ten seventeenth, but we can't do partial curves, so we have to round up). That's a whole lot of curves just to get a shape that can be drawn using a simple function! In fact, let's flip the function around, so that if we plug in the precision error, labelled e, we get back the maximum angle for that precision: [f9d15462df31186feef8c3d53c0f6163] And frankly, things are starting to look a bit ridiculous at this point, we're doing way more maths than we've ever done, but thankfully this is as far as we need the maths to take us: If we plug in the precisions 0.1, 0.01, 0.001 and 0.0001 we get the radians values 1.748, 1.038, 0.594 and 0.3356; in degrees, that means we can cover roughly 100 degrees (requiring four curves), 59.5 degrees (requiring six curves), 34 degrees (requiring 11 curves), and 19.2 degrees (requiring a whopping nineteen curves). The bottom line? Quadratic curves are kind of lousy if you want circular (or elliptical, which are circles that have been squashed in one dimension) curves. We can do better, even if it's just by raising the order of our curve once. So let's try the same thing for cubic curves. previoustable of contentsnext Circular arcs and cubic Beziers Let's look at approximating circles and circular arcs using cubic Beziers. How much better is that? Scripts are disabled. Showing fallback image. [891d50a946936c9701adc855de12623d] [1.4 ] At cursory glance, a fair bit better, but let's find out how much better by looking at how to construct the Bezier curve. A construction diagram for a cubic approximation of a circular arc The start and end points are trivial, but the mid point requires a bit of work, but it's mostly basic trigonometry once we know the angle th for our circular arc: if we scale our circular arc to a unit circle, we can always start our arc, with radius 1, at (1,0) and then given our arc angle th, we also know that the circular arc has length th (because unit circles are nice that way). We also know our end point, because that's just (cos(th), sin(th)), and so the challenge is to figure out what control points we need in order for the curve at t =0.5 to exactly touch the circular arc at the angle th/2: So let's again formally describe this: [9054528132317434ae2c0be27572] Only P[3] isn't quite straight-forward here, and its description is based on the fact that the triangle (origin, P[4], P[3]) is a right angled triangle, with the distance between the origin and P[4] being 1 (because we're working with a unit circle), and the distance between P[4] and P[3] being k, so that we can represent P[3] as "The point P[4] plus the vector from the origin to P[4] but then rotated a quarter circle, counter-clockwise, and scaled by k". With that, we can determine the y-coordinates for A, B, e[1], and e [2], after which we have all the information we need to determine what the value of k is. We can find these values by using (no surprise here) linear interpolation between known points, as A is midway between P[2] and P[3], e[1] is between A and "midway between P [1] and P[2]" (which is "half height" P[2]), and so forth: [e0d46f5fd4bf01e72f23495757f64448] Which now gives us two identities for B, because in addition to determining B through linear interpolation, we also know that B's y coordinate is just sin(th/2): we started this exercise by saying we were going to approximate the circular arc using a Bezier curve that had its midpoint, which is point B, touching the unit circle at the arc's half-angle, by definition making B the point at (cos(th/2), sin (th/2)). This means we can equate the two identities we now have for B[y] and solve for k. Deriving k Solving for k is fairly straight forward, but it's a fair few steps, and if you just the immediate result: using a tool like Wolfram Alpha is definitely the way to go. That said, let's get going: [cb6686f1aff26d9f47ed4c695109fd5f] And finally, we can take further advantage of several trigonometric identities to drastically simplify our formula for k: [f65f4e30a9f7a08c5c0092a1a3853922] And we're done. So, the distance of our control points to the start/end points can be expressed as a number that we get from an almost trivial expression involving the circular arc's angle: [f47561c3870425499e3] Which means that for any circular arc with angle th and radius r, our Bezier approximation based on three points of incidence is: [d880c4a1b3d7b651b054b008e952b493] Which also gives us the commonly found value of 0.55228 for quarter circles, based on them having an angle of half p: [acbde4be3cde3838b99b0ffc933f1f89] And thus giving us the following Bezier coordinates for a quarter circle of radius r: [ad4d512cb92280ac88af5313] So, how accurate is this? Unlike for the quadratic curve, we can't use t=0.5 as our reference point because by its very nature it's one of the three points that are actually guaranteed to be on the circular arc itself. Instead, we need a different t value that will give us the maximum deflection - there are two possible choices (as our curve is still strictly "overshoots" the circular arc, and it's symmetrical) but rather than trying to use calculus to find the perfect t value--which we could! the maths is perfectly reasonable as long as we get to use computers--we can also just perform a binary search for the biggest deflection and not bother with all this maths stuff. So let's do that instead: we can run a maximum deflection check that just runs through t from 0 to 1 at some coarse interval, finds a t value that has "the highest deflection of the bunch", then reruns the same check with a much smaller interval around that t value, repeating as many times as necessary to get us an arbitrarily precise value of t: 1 [getMostWrongT(radius] 2 [ if end-start < eps] 3 [ return (start+en] 4 [ worst_t = 0 ] 5 [ max = 0 ] 6 [ stepsize = (end-st] 7 [ for t=start to end] 8 [ p = bezier.get(t] 9 [ diff = p.magnitu] 10 [ if diff > max: ] 11 [ worst_t = t ] 12 [ max = diff ] 13 [ return getMostWron] Plus, how often do you get to write a function with that name? Using this code, we find that our t values are approximately 0.211325 and 0.788675, so let's pick the lower of the two and see what the maximum deflection is across our domain of angles, with the original quadratic error show in green (rocketing off to infinity first, and then coming back down as we approach 2p) [image-20210417173811587] [image-20210417174019035] [image-20210417174100036] error plotted for 0 <= ph <= error plotted for 0 <= ph <= error plotted for 0 <= ph <= 2p p 1/2p That last image is probably not quite clear enough: the cubic approximation of a quarter circle is so incredibly much better that we can't even really see it at the same scale of our quadratic curve. Let's scale the y-axis a little, and try that again: [image-2021] Yeah... the error of a cubic approximation for a quarter circle turns out to be two orders of magnitude better. At approximately 0.00027 (or: just shy of being 2.7 pixels off for a circle with a radius of 10,000 pixels) the increase in precision over quadratic curves is quite spectacular - certainly good enough that no one in their right mind should ever use quadratic curves. So that's it, kappa is 4/3 * tan(th/4) , we're done! ...or are we? Can we do better? Technically: yes, we can. But I'm going to prefix this section with "we can, and we should investigate that possibility, but let me warn you up front that the result is only better if we're going to hard-code the values". We're about to get into the weeds and the standard three-points-of-incidence value is so good already that for most applications, trying to do better won't make any sense at all. So with that said: what we calculated above is an upper bound for a best fit Bezier curve for a circular arc: anywhere we don't touch the circular arc in our approximation, we've "overshot" the arc. What if we dropped our value for k just a little, so that the curve starts out as an over-estimation, but then crosses the circular arc, yielding an region of underestimation, and then crosses the circular arc again, with another region of overestimation. This might give us a lower overall error, so let's see what we can do. First, let's express the total error (given circular arc angle th, and some k) using standard calculus notation: [85c3dc0187f786b37f5fa5a7cc74d642] This says that the error function for a given angle and value of k is equal to the "infinite" sum of differences between our curve and the circular arc, as we run t from 0 to 1, using an infinitely small step size. between subsequent t values. Now, since we want to find the minimal error, that means we want to know where along this function things go from "error is getting progressively less" to "error is increasing again", which means we want to know where its derivative is zero, which as mathematical expression looks like: [a7dc2e51b90e89ec62e4a328d2b2] And here we have the most direct application of the Fundamental Theorem of Calculus: the derivative and integral are each other's inverse operations, so they cancel out, leaving us with our original function: [b996b7c1af4c9187004af7d04b37] And now we just solve for that... oh wait. We've seen this before. In order to solve this, we'd end up needing to solve this: [610a69d8be] And both of those terms on the left of the equal sign are 6^th degree polynomials, which means--as we've covered in the section on arc lengths--there is no symbolic solution for this equasion. Instead, we'll have to use a numerical approach to find the solutions here, so... to the computer! Iterating on a solution By which I really mean "to the binary search algorithm", because we're dealing with a reasonably well behaved function: depending on the value for k , we're either going to end up with a Bezier curve that's on average "not at distance r from the arc's center", "exactly distance r from the arc's center", or "more than distance r from the arc's center", so we can just binary search our way to the most accurate value for c that gets us that middle case. First our setup, where we determine our upper and lower bounds, before entering our binary search: 1 [findBest(radius, ang] 2 [ lowerBound = 0 ] 3 [ upperBound = 4.0/3] 4 [ return binarySearc] And then the binary search algorithm, which can be found in pretty much any CS textbook, as well as more online articles, tutorials, and blog posts than you can ever read in a life time: 1 [binarySearch(radius,] 2 [ value = (upperBoun] 3 [ ] 4 [ if (upperBound - l] 5 [ ] 6 [ // recompute the c] 7 [ d = (points[3].y <] 8 [ points[1] = new Po] 9 [ points[2] = new Po] 10 [ points[3].x + d ] 11 [ points[3].y - d ] 12 [ ) ] 13 [ ] 14 [ if radialError(rad] 15 [ // our bezier cu] 16 [ return binarySea] 17 [ else: ] 18 [ // our bezier cu] 19 [ return binarySea] Using the following radialError function, which samples the curve's approximation of the circular arc over several points (although the first and last point will never contribute anything, so we skip them): 1 [radialError(radius, ] 2 [ err = 0 ] 3 [ steps = 5.0 ] 4 [ for (int i=1; i s] 5 [ let numerator = ] 6 [ let denominator ] 7 [ let alpha = nume] 8 [ let v[i] = alpha] 9 [ } ] 10 [} ] (A nice bit of behaviour in this code is that we work the interpolation "backwards", starting at i=s at each level of the interpolation, and we stop when i = s - order + level, so we always end up with a value for i such that those v[i-1] don't try to use an array index that doesn't exist) Open vs. closed paths Much like poly-Beziers, B-Splines can be either open, running from the first point to the last point, or closed, where the first and last point are the same coordinate. However, because B-Splines are an interpolation of curves, not just points, we can't simply make the first and last point the same, we need to link as many points as are necessary to form "a curve" that the spline performs interpolation with. As such, for an order d B-Spline, we need to make the first and last d points the same. This is of course hardly more work than before (simply append points.splice(0,d) to points) but it's important to remember that you need more than just a single point. Of course if we want to manipulate these kind of curves we need to make sure to mark them as "closed" so that we know the coordinate for points[0] and points[n-k] etc. don't just happen to have the same x/y values, but really are the same coordinate, so that manipulating one will equally manipulate the other, but programming generally makes this really easy by storing references to points, rather than copies (or other linked values such as coordinate weights, discussed in the NURBS section) rather than separate coordinate objects. Manipulating the curve through the knot vector The most important thing to understand when it comes to B-Splines is that they work because of the concept of a knot vector. As mentioned above, knots represent "where individual control points start/stop influencing the curve", but we never looked at the values that go in the knot vector. If you look back at the N() and a() functions, you see that interpolations are based on intervals in the knot vector, rather than the actual values in the knot vector, and we can exploit this to do some pretty interesting things with clever manipulation of the knot vector. Specifically there are four things we can do that are worth looking at: 1. we can use a uniform knot vector, with equally spaced intervals, 2. we can use a non-uniform knot vector, without enforcing equally spaced intervals, 3. we can collapse sequential knots to the same value, locally lowering curve complexity using "null" intervals, and 4. we can form a special case non-uniform vector, by combining (1) and (3) to for a vector with collapsed start and end knots, with a uniform vector in between. Uniform B-Splines The most straightforward type of B-Spline is the uniform spline. In a uniform spline, the knots are distributed uniformly over the entire curve interval. For instance, if we have a knot vector of length twelve, then a uniform knot vector would be [0,1,2,3,...,9,10,11]. Or [4,5,6,...,13,14,15], which defines the same intervals, or even [0,2,3,...,18,20,22], which also defines the same intervals, just scaled by a constant factor, which becomes normalised during interpolation and so does not contribute to the curvature. Scripts are disabled. Showing fallback image. [48a30189e74658737b3a8b28bb816f8a] This is an important point: the intervals that the knot vector defines are relative intervals, so it doesn't matter if every interval is size 1, or size 100 - the relative differences between the intervals is what shapes any particular curve. The problem with uniform knot vectors is that, as we need order control points before we have any curve with which we can perform interpolation, the curve does not "start" at the first point, nor "ends" at the last point. Instead there are "gaps". We can get rid of these, by being clever about how we apply the following uniformity-breaking approach instead... Reducing local curve complexity by collapsing intervals Collapsing knot intervals, by making two or more consecutive knots have the same value, allows us to reduce the curve complexity in the sections that are affected by the knots involved. This can have drastic effects: for every interval collapse, the curve order goes down, and curve continuity goes down, to the point where collapsing order knots creates a situation where all continuity is lost and the curve "kinks". Scripts are disabled. Showing fallback image. [ceaef2fbee05a58aa11835925403b4cd] Open-Uniform B-Splines By combining knot interval collapsing at the start and end of the curve, with uniform knots in between, we can overcome the problem of the curve not starting and ending where we'd kind of like it to: For any curve of degree D with control points N, we can define a knot vector of length N+D+1 in which the values 0 ... D+1 are the same, the values D+1 ... N+1 follow the "uniform" pattern, and the values N+1 ... N+D+1 are the same again. For example, a cubic B-Spline with 7 control points can have a knot vector [0,0,0,0,1,2,3,4,4,4,4], or it might have the "identical" knot vector [0,0,0,0,2,4,6,8,8,8,8], etc. Again, it is the relative differences that determine the curve shape. Scripts are disabled. Showing fallback image. [0215dc106e4ad51afe043c0176a595f6] Non-uniform B-Splines This is essentially the "free form" version of a B-Spline, and also the least interesting to look at, as without any specific reason to pick specific knot intervals, there is nothing particularly interesting going on. There is one constraint to the knot vector, other than that any value knots[k+1] should be greater than or equal to knots[k]. One last thing: Rational B-Splines While it is true that this section on B-Splines is running quite long already, there is one more thing we need to talk about, and that's "Rational" splines, where the rationality applies to the "ratio", or relative weights, of the control points themselves. By introducing a ratio vector with weights to apply to each control point, we greatly increase our influence over the final curve shape: the more weight a control point carries, the closer to that point the spline curve will lie, a bit like turning up the gravity of a control point, just like for rational Bezier curves. Scripts are disabled. Showing fallback image. [0d9c2186423466a32bb8fbd187409f82] Of course this brings us to the final topic that any text on B-Splines must touch on before calling it a day: the NURBS, or Non-Uniform Rational B-Spline (NURBS is not a plural, the capital S actually just stands for "spline", but a lot of people mistakenly treat it as if it is, so now you know better). NURBS is an important type of curve in computer-facilitated design, used a lot in 3D modelling (typically as NURBS surfaces) as well as in arbitrary-precision 2D design due to the level of control a NURBS curve offers designers. While a true non-uniform rational B-Spline would be hard to work with, when we talk about NURBS we typically mean the Open-Uniform Rational B-Spline, or OURBS, but that doesn't roll off the tongue nearly as nicely, and so remember that when people talk about NURBS, they typically mean open-uniform, which has the useful property of starting the curve at the first control point, and ending it at the last. Extending our implementation to cover rational splines The algorithm for working with Rational B-Splines is virtually identical to the regular algorithm, and the extension to work in the control point weights is fairly simple: we extend each control point from a point in its original number of dimensions (2D, 3D, etc.) to one dimension higher, scaling the original dimensions by the control point's weight, and then assigning that weight as its value for the extended dimension. For example, a 2D point (x,y) with weight w becomes a 3D point (w * x, w * y, w). We then run the same algorithm as before, which will automatically perform weight interpolation in addition to regular coordinate interpolation, because all we've done is pretended we have coordinates in a higher dimension. The algorithm doesn't really care about how many dimensions it needs to interpolate. In order to recover our "real" curve point, we take the final result of the point generation algorithm, and "unweigh" it: we take the final point's derived weight w' and divide all the regular coordinate dimensions by it, then throw away the weight information. Based on our previous example, we take the final 3D point (x', y', w'), which we then turn back into a 2D point by computing (x'/w', y'/ w'). And that's it, we're done! previoustable of contents Comments and questions First off, 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 Patreon page for this book, or if you prefer to make a one-time donation, head on over to the buy Pomax a coffee page. This work has grown from a small primer to a 70-plus print-page-equivalent reader on the subject of Bezier 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. With that said, on to the comments! --------------------------------------------------------------------- This article is (c) 2011-2020 to me, Mike "Pomax" Kamermans, but the text, code, and images are almost no rights reserved. Go do something cool with it!