技術

Canvasでベジェ曲線

HTMLのCanvasにベジェ曲線を描くアルゴリズムを実装してみました。
CanvasをJavaScriptで操作した事がある方はオイオイと思われるかもしれません。なぜならCanvasのコンテキストオブジェクトにはbezierCurveTo()っていう3次ベジェ曲線を描くメソッドすでにあるからです(しかも速い)w

しかし実装する過程で色々得るものがありましたのでよしとします。

まず最初に実装した、3次ベジェ曲線を特に工夫なく描画してみるですが、詳しくはソースを見ていただければと思いますが、Wikipediaに載ってたアルゴリズムほぼそのままで実装しました。

このシンプルなアルゴリズムであの複雑な式で表されるベジェ曲線を描けるなんて!とちょっと感動してしまいました。

で次に3次からn次に拡張すべく、n次ベジェ曲線を特に工夫なく描画してみるを実装してみました。再帰を使えば簡単にn次に拡張できることに気づいてここでもちょっと感動しました。

でベジェ曲線について調べてたら、2次ベジェ曲線を整数の加減算とビットシフトだけで高速に描く方法を見つけまして、それを3次に拡張しJavaScriptで実装してみたのが、3次ベジェ曲線を整数の加減算とビットシフトのみで描画してみるになります。

これはさすがに苦労しました。(といっても掛かったのは数時間程度)

まず学がないので元の記事で説明されてる事の意味が分からないw

色々参考にしながら、紙に鉛筆で数式を色々書いて「数学的にベジェ曲線とは何哉?」からはじめまして、やっと元の記事の意味を理解できました。

理解できた後は、どうすれば3次に拡張できるか?ってのはすぐ分かったんですが、やたらと記号や項数が多い式を色々変形して幾つかの式を求める必要があって心が折れそうになったんですが、Maximaという数式処理システムに出会いましてかなり助けられました。

Mac用のバイナリはこちら。wxMaximaを使ってます。

昔からMaximaという名前は知ってたのですが、難しそうというのと必要性が理解できなかったのとで敬遠してましたが、それを激しく後悔するくらい強力で便利なソフトです。

例えば、((N-i)^3*P0 + 3*i*(N-i)^2*P1 + 3*i^2*(N-i)*P2 + i^3*P3)/N^3という式があったとして、この式のi = i + 1の場合からi = iの場合を引いて簡単化する。なんてのを、紙と鉛筆でやってたらとても大変だし途中でミスしそうですが、Maximaを使えば一発です。

具体的には関数を使って、

iB3(i):=((N-i)^3*P0 + 3*i*(N-i)^2*P1 + 3*i^2*(N-i)*P2 + i^3*P3)/N^3;

ratsimp(iB3(i+1)-iB3(i));

とやるだけです。ホント便利です。また紙に書くときのような形で数式を表示してくれるのでとても見やすいです。

次にこれを3次からn次に拡張しようと思ったのですが、数式をn個求めなきゃいけない(数式を求めるアルゴリズムを考えなきゃいけない)のと、分解能(128とか1024とか)のn乗とかの数値を扱うのでビット演算を使う以上、整数のビット数が足りなくなるため放置中です。

n次の場合の数式を求めるアルゴリズムはできそうな気がするので、ビット数のところは無限ビット整数が扱えるPythonを使うととりあえずは作れそうな気はします。

最後に、今回実装した2種の3次ベジェ曲線描画アルゴリズムとCanvasのbezierCurveTo()の速度を比較するため、3次ベジェ曲線ベンチを作りました。

MacのFirefoxでしかテストしてませんが、bezierCurveTo()がやはり一番速いですw

何も考えずに実装したものと、整数の加減算とビットシフトのみで実装したものを比べると後者のほうが断然速いです。

ですが、微妙に線がガタガタになりますw

分解能は2^7 = 128にしてますのでもっと上げれば滑らかになるとは思いますが、ビット数の制限上3次の場合はこれ以上は無理っぽいです。

最初に実装したものは遅いですが、今回実装したように容易にn次に拡張できるのでどこかで使えるかもしれません。(ないかなー)

結論。

bezierCurveTo()を使いましょうw

コメントを残す

メールアドレスが公開されることはありません。



※画像をクリックして別の画像を表示

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください