スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

ベジエ曲線と点との距離

ベジェ曲線から点までの距離はどうしたらいい?という質問にStack Overflowだかどこだかでこれとかいいんじゃない?と返されていたのを見かけたので実験。

Using method

ベジェ曲線と点との距離を求めるには色々方法が考えられてきたけれど、点と曲線の距離
f(t)=sqrt((Bx(t)-x)2+(By(t)-y)2) (Bx,Byはベジェ曲線の関数)
を微分した
f'(t)=g(t)=0
を数値的に解くのが一番速そうだねという内容。
というわけで区間での刈り込みをする。
  1. スツルムの定理で解の分離
  2. 区間(ai,bi)に解が1つならそこがf(t)の極小か調べる。
    g(t)=f'(t)なので、区間の両側の符号 (g(ai), g(bi)) を調べればわかる。
    符号の組み合わせは(+,-), (+,+), (-,-), (-,+) の4通り。
    (+,+), (-,-)は極値ではないので除外。
    (+,-)は上に凸、つまり極小ではないのでこれも除外。
    従って下に凸な(-,+)の時だけ解く。
    なお全体が上に凸だった場合は左右端のどちらかが最小距離になる。
  3. まずは二分法で区間を狭める
  4. 適当に狭めたらニュートン法で解を求める
で、やってみたのが上のもの。
プルダウンの内容は
  • Brute Force : 単純に曲線上の点をたくさん取ってそこからの距離を求めて一番近いものを使う
  • Simple Newton : 少ない分割数のBrute Forceで求めた点をニュートン法で精度を上げる
  • Imploved Method : 先の手法
単純なニュートン法だと一部間違った解に収束しているのがわかる。
でも今回の実装ではこの手法はあまり速くない。どこか間違っているかも。

で、本当はシェーダーでできると良いと思ってたんだけど、スツルム列の計算に精度が必要と書いてある通り、単精度のシェーダーではぽつぽつとアーティファクトの点ができたりする。
こういう妙なカーブが無いという前提ならさほど問題は無いようではあるけれど、もうすこし考えたほうがいいかもねという結論に。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

c5h12

Author:c5h12
なにやらいろいろ

最新記事
最新コメント
最新トラックバック
月別アーカイブ
カテゴリ
検索フォーム
RSSリンクの表示
リンク
ブロとも申請フォーム

この人とブロともになる

QRコード
QR
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。