{"id":451,"date":"2008-02-27T23:28:29","date_gmt":"2008-02-28T07:28:29","guid":{"rendered":"http:\/\/www.elbeno.com\/blog\/?p=451"},"modified":"2008-03-01T10:51:03","modified_gmt":"2008-03-01T18:51:03","slug":"experimenting-with-cubic-bezier-subdivision","status":"publish","type":"post","link":"https:\/\/www.elbeno.com\/blog\/?p=451","title":{"rendered":"Experimenting with (cubic) B\u00c3\u00a9zier subdivision"},"content":{"rendered":"<p>As you know, a <a href=\"http:\/\/en.wikipedia.org\/wiki\/B%C3%A9zier_curve\">B\u00c3\u00a9zier curve<\/a> (here meaning specifically a cubic B\u00c3\u00a9zier) is often used for drawing all kinds of things in vector graphics. It has the nice property that the endpoints and control points form a bounding box, and <a href=\"http:\/\/en.wikipedia.org\/wiki\/De_Casteljau's_algorithm\">deCasteljau&#8217;s algorithm<\/a> is a nice numerically stable way of evaluating the curve at a particular point. Of course, the same algorithm trivially gives the tangent to the curve at that point and from there it&#8217;s a hop and a skip to find the normal.<\/p>\n<p>All well and good so far. The problem I wanted to tackle was that of spacing points equally along the curve (and incidentally, pushing these same points out along the normal), so that I can easily modulate a pattern (e.g. sawtooth, square wave) on to an arbitrary B\u00c3\u00a9zier curve. <\/p>\n<p>But there&#8217;s a slight problem with the naive method for doing this. Recall that a B\u00c3\u00a9zier curve is in fact a parametric curve, specified by the parameter t which varies from 0 to 1 along the curve. The problem is that a linear increment of the parameter t does not correspond to a linear step along the curve length. For some curves, it&#8217;s not a bad approximation, but the more &#8220;curvy&#8221; the B\u00c3\u00a9zier, the worse the discrepancy. This picture is a clear illustration of this problem.<\/p>\n<p><a href=\"http:\/\/www.flickr.com\/photos\/88319047@N00\/2297140229\/\" title=\"bezier-subdiv-wrong by villagelinca, on Flickr\"><img loading=\"lazy\" decoding=\"async\" src=\"http:\/\/farm4.static.flickr.com\/3174\/2297140229_bf23de167d_o.png\" width=\"500\" height=\"500\" alt=\"bezier-subdiv-wrong\" \/><\/a><\/p>\n<p>The picture shows points (and points pushed along the normal) plotted on the curve, as t increments linearly from 0 to 1. As you can see, stepping along with constant increments of the parameter t gives the wrong result. These points are not equally spaced along the curve.<\/p>\n<p>So far, I have a naive &#8220;correct&#8221; solution to this problem as follows: I sample the curve at a high frequency (say 1000). Each segment between points I then treat as a straight line, and I compute the length of the curve (simply the sum of the Pythagorean distance between successive points). I can then step along the curve linearly with respect to the curve length, and recover the parameter t (to actually evaluate the curve at a given point) by a simple calculation (binary search and interpolation between nearest neighbours). The result of this approach:<\/p>\n<p><a href=\"http:\/\/www.flickr.com\/photos\/88319047@N00\/2297140227\/\" title=\"bezier-subdiv by villagelinca, on Flickr\"><img loading=\"lazy\" decoding=\"async\" src=\"http:\/\/farm4.static.flickr.com\/3040\/2297140227_6431e331c4_o.png\" width=\"500\" height=\"500\" alt=\"bezier-subdiv\" \/><\/a><\/p>\n<p>Much better.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>As you know, a B\u00c3\u00a9zier curve (here meaning specifically a cubic B\u00c3\u00a9zier) is often used for drawing all kinds of things in vector graphics. It has the nice property that the endpoints and control points form a bounding box, and deCasteljau&#8217;s algorithm is a nice numerically stable way of evaluating&#8230;<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[13,11,8],"tags":[],"class_list":["post-451","post","type-post","status-publish","format-standard","hentry","category-lisp","category-maths","category-programming"],"_links":{"self":[{"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/451","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=451"}],"version-history":[{"count":0,"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/451\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=451"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=451"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=451"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}