{"id":616,"date":"2014-09-03T11:54:28","date_gmt":"2014-09-03T18:54:28","guid":{"rendered":"http:\/\/www.imaginary-institute.com\/blog\/?p=616"},"modified":"2017-06-28T20:25:46","modified_gmt":"2017-06-29T03:25:46","slug":"efficiently-finding-points-on-catmull-rom-and-bezier-curves","status":"publish","type":"post","link":"https:\/\/www.imaginary-institute.com\/blog\/2014\/09\/03\/efficiently-finding-points-on-catmull-rom-and-bezier-curves\/","title":{"rendered":"Efficiently Finding Points on Catmull-Rom and Bezier Curves"},"content":{"rendered":"

In my AU library, I offer some utilities related to curves. Although Processing offers functions for finding points on curves, I needed to write my own implementation that was fast and efficient. Here’s an easy, elegant way to compute points on Catmull-Rom and Bezier curves, along with a discussion of an idea for making it faster. <\/p>\n

The most convenient way to generate points on these curves is to use a matrix form, as nicely summarized by Tom Duff’s memo<\/a>. Suppose we have a curve with knot values k0, k1, k2, and k3. Form them into row vector, which I’ll call k<\/strong>. We’ll be using this in column form, so I’ll use this vector in its transposed form, written kT<\/sup><\/strong>. Now we want to find a point at the parameter value t<\/em> along the curve. Form a row vector as [t<\/em>3<\/sup> t<\/em>2<\/sup> t<\/em> 1], which I’ll call t<\/strong>.<\/p>\n

 <\/p>\n

\"ATo find the value of the curve at t<\/em>, we need only one more thing: a 4-by-4 matrix, which I’ll call M<\/strong>. This matrix sits between the two vectors as in the tableau above. Multiplied together, these three elements give us the scalar t M kT<\/sup><\/strong>, which is the value of the curve of matrix type M<\/strong>, with knot data k<\/strong>, at time t<\/em>. Each particular kind of curve has its own characteristic matrix M<\/strong> that combines t<\/strong> with k<\/strong> in the just the right way.<\/p>\n

 <\/p>\n

\"Cardinal

Cardinal Spline Matrix<\/p><\/div>\n

\"Catmull-Rom

Catmull-Rom Matrix<\/p><\/div>\n

The interesting thing is that we can use this form for both Bezier curves and all the cardinal splines. The cardinal splines take a single parameter, which Duff calls c<\/em>. When c<\/em>=0 we get straight lines from knot to knot, and when c<\/em>=.5 we get Catmull-Rom curves. Values of c<\/em> between those values blend between the polygon and Catmull-Rom forms. Values of c<\/em> outside that range produce very squiggly curves.<\/p>\n

A nice derivation of the matrix form of the Bezier curve is described by Ken Joy here<\/a> (note that Joy writes his t<\/strong> vector in the opposite order that I’ve written it, so I’ve flipped his matrix to make it match our notation).<\/p>\n

\"Bezier

Bezier Matrix<\/p><\/div>\n

To evaluate a 1D curve at t<\/em>, we just put our knot values into k<\/strong>, build t<\/strong>, and evaluate t M kT<\/sup><\/strong>. Because these curves are independent along each axis, we can blend as many values as we like for each value of t<\/em> just by changing k<\/strong>. For example, to evaluate a 2D curve, with knot values for X and Y, we only need fill up k<\/strong> with the X values, and find t M kT<\/sup><\/strong>. To find the Y value, just put the Y values into k<\/strong> and find t M kT<\/sup><\/strong> again. We can attach other data to each knot, such as stroke thickness or rainfall that day, and interpolate it as well.<\/p>\n

This suggests saving some time by computing t M<\/strong> just once for a given value of t<\/em>, and then applying it to each different set of k<\/strong>.<\/p>\n

But wait, why not pre-compute t M<\/strong> for all time? Then for any given value of t<\/em>, we find the two closest pre-computed vectors, linearly interpolate them, and then apply them to k<\/strong>. For example, save a static table tMtable[1000][4]<\/code>, loaded with the 4-element vector t M<\/strong> for 1000 choices of t<\/em>. When a value of t<\/em> arrives, find the two indices that bracket it, which I’ll call i0<\/code> and i1<\/code>. We’ll say that b<\/code> is a float from 0 to 1 across that interval, telling us where t<\/em> lands. Then we can find the value of t M<\/strong>, which I’ll save in a 4-element vector tM<\/code>:<\/p>\n

for (int i=0; i<4; i++) tM[i] = lerp(tMtable[i0,i], tMtable[i1,i], b);\r\n<\/pre>\n
Great, now we have tM<\/code> holding t M<\/strong>, and we can find the spline value by just dotting it with the vector k<\/strong> holding our knot data:<\/p>\n
float val = 0;\r\nfor (int i=0; i<4; i++) val += tM[i] * k[i];\r\n<\/pre>\n
I like this idea, but is it worth it? Writing out the full evaluation of t M kT<\/sup><\/strong>, we’d need 20 multiplies and 5 adds. In this lookup table form, we’d need a total of 8 multiplies and 12 adds (and that’s leaving out the overhead of the loops, and finding the values of i0<\/code>, i1<\/code>, and b<\/code>). Unfortunately, this doesn’t seem at all worth it. Finding t M<\/strong> just isn’t that expensive.<\/p>\n
I think it’s always worth looking at these kinds of time\/space tradeoffs, because they often return impressive benefits. But it’s important to look at them closely, so we don’t waste time implementing “optimizations” that aren’t optimizing anything!<\/p>\n","protected":false},"excerpt":{"rendered":"
In my AU library, I offer some utilities related to curves. Although Processing offers functions for finding points on curves, I needed to write my own implementation that was fast and efficient. Here’s an easy, elegant way to compute points on Catmull-Rom and Bezier curves, along with a discussion of an idea for making it […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[1],"tags":[],"class_list":["post-616","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.imaginary-institute.com\/blog\/wp-json\/wp\/v2\/posts\/616","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.imaginary-institute.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.imaginary-institute.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.imaginary-institute.com\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.imaginary-institute.com\/blog\/wp-json\/wp\/v2\/comments?post=616"}],"version-history":[{"count":51,"href":"https:\/\/www.imaginary-institute.com\/blog\/wp-json\/wp\/v2\/posts\/616\/revisions"}],"predecessor-version":[{"id":1277,"href":"https:\/\/www.imaginary-institute.com\/blog\/wp-json\/wp\/v2\/posts\/616\/revisions\/1277"}],"wp:attachment":[{"href":"https:\/\/www.imaginary-institute.com\/blog\/wp-json\/wp\/v2\/media?parent=616"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.imaginary-institute.com\/blog\/wp-json\/wp\/v2\/categories?post=616"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.imaginary-institute.com\/blog\/wp-json\/wp\/v2\/tags?post=616"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}