ここでは、適当に覚え書き等を。


交点判定-Bezier Clipping法

西田先生が開発した、ベジェ曲線と直線、ベジェ曲線とベジェ曲線との交点を高速に求める手法。

http://nis-lab.is.s.u-tokyo.ac.jp/~nis/cdrom/nishita.pdf

<以下、やねうらおによるメモ>

まず、直線とベジェ曲線の交点:

ベジェは凸包(the convex full of the curve)なので、3次のベジェなら、制御点0,1,2,3で四角形書いたら、その四角形の内側に居てます。0,3はベジェ曲線上の点。

そこで直線とベジェの交点なら、この論文のFig1のa.みたく直線0-2(制御点0と2を結んだもの)と直線1-3の直線(この場合x軸)との交点を求めて、それをt.min , t.maxとして、もっかいこの区間に対して同じことを繰り返していけば、どんどん四角形が小さくなって最終的には収束するだろうってのが基本的な考えかたです。凸包版のnewton法ですね。

ベジェ曲線とベジェ曲線の交点場合:

片方のベジェ曲線をfat line(太った線=太さのある直線)だとみなして、直線とベジェ曲線との交点を求めることを考えます。そうすれば、さっきと同じ原理で四角形が小さくなります。ベジェ曲線Q,Pがあるとすれば、QをPを直線とみなしてクリップするのと、PをQを直線とみなしてクリップするのとを交互に繰り返します。

別に交互に繰り返さなくても収束するんだけど、交互にしたほうが早く収束するのでこうする。(図描いてみれば直感的に明らか)

原理はそんだけです。fat lineとみなすんで、まあ嘘の交点判定になってたり、多少の誤差がついてたりするのはご愛敬。