NURBS曲線のベジエ分解と線分交差判定(ベジエクリッピング法)

制御点が6点以上の3次NURBS曲線(クランプ一様ノットベクトル)を、 Boehmのノット挿入アルゴリズム(各内部ノットの重複度を次数 p=3 まで引き上げる)によって 複数の有理ベジエ曲線(セグメント)に厳密分解します。各セグメントは4個の制御点と重みを持つ3次有理ベジエです。 線分(黒い実線・端点はドラッグ可能な青四角)とNURBS曲線の交差は、各セグメントごとに 「制御点から線分を含む直線への符号付き距離」を表す3次のスカラー・ベジエ関数 Num(t) を作り、 その根をベジエクリッピング法(制御多角形の凸包と y=0 の交差でtの区間を反復的に絞り込む二分法)で求め、 得られた t での曲線上の点が実際に線分の範囲内(媒介変数 s∈[0,1])にあるかどうかで判定しています。 下部のタブでセグメントを選ぶと、右側にそのセグメントの Num(t) と制御点の凸包が表示されます。 制御点(オレンジの丸)はドラッグで移動、ダブルクリックで重み w を編集できます。

NURBS曲線(ベジエ分解済み)と線分
NURBS曲線(全体)
選択中セグメントの曲線/ベジエ制御多角形
NURBS制御点 Pi(元の制御多角形は破線)
線分端点 A, B
線分と曲線の交点(有効な交差)
セグメント境界(ノット位置)
選択セグメントの距離関数 Num(t)(3次)と凸包
Num(t) の曲線
制御点の凸包
根(s∈[0,1] =有効な交差)
根(線分の外=直線とは交わるが線分外)
計算中...
次数 p = 3(3次NURBS)/ 制御点は6〜10点の範囲で調整できます