トリム曲線と平面の交点を求める
距離関数とベジエクリッピング

ベジエ曲面スライサー（トリム対応版）では、スライス面とトリム曲線の交点に球を置いています。この交点は曲面を細かく刻んで探しているのではなく、1変数の多項式の根として求めています。その仕組みである距離関数とベジエクリッピングを、動かしながら解説します。

曲線の次数

双3次曲面の上に3次のトリム曲線 (u(t), v(t)) をのせると、3次元曲線 C(t) は t の18次のベジエ曲線になります（制御点は19個）。近似はせず、この18次曲線を厳密に組み立てています。

距離関数

平面 n·p = d までの符号付き距離 g(t) も18次のベジエ曲線で、その制御係数は「各制御点 Q_k から平面までの距離」そのものです。

根の探索

g(t) = 0 の解を、1次元のベジエクリッピングで求めます。仕上げにニュートン法を数回だけ使います。

得られるもの

根 t* から (u,v) を求め、曲面上の3次元点 p = S(u,v) を計算します。この点が球の中心です。

求めたいもの

曲面は4×4の制御点 P_ij を持つ双3次ベジエ曲面 S(u,v) です。トリム曲線は、パッチのUV空間に描いた3次ベジエ曲線 (u(t), v(t))（t ∈ [0,1]）です。円は4本の3次ベジエ弧の閉ループで、円弧の制御点距離には κ = 0.5522847498307936 を使います。

トリム曲線を曲面に写した3次元曲線が C(t) = S(u(t), v(t)) です。スライス面は単位法線 n と定数 d を使って n·p = d と書けます。求めるのは、

のすべてです。トリム曲線は弧ごとに別のベジエ曲線なので、この問題を弧ごとに解きます（1つの円で4弧）。

全体の流れ

1. 形状を作るとき（1回だけ）
   各弧について、18次曲線の制御点 Q₀…Q₁₈ を厳密に組み立てます（次数の章）。円の大きさを変えたときは作り直します。
2. スライス面の向きが変わるたび
   19個の内積 n·Q_k を計算し、最小値と最大値を控えます。
3. 平面ごとの範囲判定
   d が [最小, 最大] の外なら、その弧は平面と交わりません。ここで終了です。
4. 距離関数の根探索
   g_k = n·Q_k − d を係数とする18次ベジエ曲線に、1次元ベジエクリッピングを適用して根 t* を求めます（クリッピングの章）。
5. 3次元点の復元
   (u,v) = (u(t*), v(t*)) を求め、p = S(u,v) を球の中心にします。弧の継ぎ目で同じ点が二重に見つかった場合は、距離 10⁻⁶ 未満のものを1つにまとめます。

距離関数：3次元の交点問題を1変数の根探索にする

単位法線 n の平面 n·p = d に対して、点 p の符号付き距離は n·p − d です（平面の表側なら正、裏側なら負）。曲線上の点の距離を t の関数として書いたものが距離関数です。

曲線が平面を貫く点では距離が0になるので、交点は g(t) = 0 の根です。ここまでは当然ですが、ベジエ曲線の場合はもう一段よいことが起きます。

制御係数は制御点の距離そのもの

ベジエ曲線 C(t) = Σ Q_k B_k(t) に、線形写像 p ↦ n·p − d を施すと、写像後の曲線は「制御点を同じ写像で移した曲線」になります。ベジエ基底の総和が常に1なので、定数項 −d も各係数に配ることができるからです。

つまり g(t) は、制御点が (k/n, g_k) のスカラー値ベジエ曲線です。3次元曲線と平面の交差判定は、「グラフ (t, g) が t 軸を横切る位置を探す」問題に置き換わります。ベジエ曲線の性質がそのまま使えます。

• 凸包性：曲線は制御点の凸包の内側にあります。係数 g_k がすべて同符号なら、根はありません。
• 変動減少性：根の数は、係数列 g₀, g₁, … の符号変化の回数を超えません。

左の青い曲線の制御点（色付きの丸）をドラッグしてみてください。左の破線が「各制御点から直線への符号付き距離」で、右のグラフで同じ色の点の高さになっています。右のグラフの曲線が横軸（赤）と交わる t が、左の金色の交点に対応します。すべての制御点が直線の同じ側に寄ると、右の制御多角形も横軸の片側に寄り、交点が消えます。

18次の曲線を厳密に組み立てる

ここが、次数を正しく数えるうえでいちばん大事な部分です。C(t) = S(u(t), v(t)) を、t のベジエ曲線として書き直します。

手順1：基底関数に3次曲線を代入する

3次のベジエ基底は B_i³(u) = C(3,i) uⁱ (1−u)³⁻ⁱ で、u について3次です。ここに3次のトリム曲線 u(t) を代入すると、u(t)ⁱ が 3i 次、(1−u(t))³⁻ⁱ が 3(3−i) 次になり、掛け合わせると次数は足し算で 3i + 3(3−i) = 9 次になります。i がどれでも9次です。v 側の B_j³(v(t)) も同じく9次です。

手順2：u 側と v 側を掛ける

曲面の各項は B_i(u(t)) · B_j(v(t)) という積です。9次と9次の積なので、次数は 9 + 9 = 18 になります。

手順3：制御点で線形結合する

16個の積 W_ij(t) = B_i(u(t)) B_j(v(t)) に制御点 P_ij を掛けて足すだけなので、次数は増えません。

18次のベジエ曲線の制御点は 18 + 1 = 19 個です。Q_k は、W_ij を18次のベジエ基底で展開したときの k 番目の係数を重みにして、P_ij を足し合わせたものです（x, y, z 座標ごとに同じ計算）。

一般に、u 方向 m 次・v 方向 n 次の曲面に d 次のトリム曲線を代入すると、合成曲線の次数は (m + n)d になります。実装では m = n = d = 3 なので 6 × 3 = 18 です。

ベジエ基底の積の公式

手順1〜2の掛け算は、ベジエ基底のまま計算できます。次の公式を使うと、係数配列同士の畳み込みで済みます。

次数 m と n の2つの多項式の積は次数 m + n になる、という当たり前の事実が、そのまま添字の足し算 a + b に現れています。実装の bernMul はこの公式そのものです。

「厳密」であるということ

ここまでの計算は恒等式の変形だけで、標本点から曲線をあてはめたり、低い次数で近似したりする処理を含みません。組み立てた18次曲線が曲面の直接評価 S(u(t), v(t)) と一致することは、ランダムな点で確かめています（最大誤差 7.0 × 10⁻¹⁶、丸め誤差の範囲。詳しくは検証の章）。したがって、交点の位置に近似による誤差は入りません。

ベジエクリッピング：18次の根をすべて見つける

距離関数 g(t) は係数 g₀…g₁₈ の18次ベジエ曲線です。次数が高いので、公式で根を求めることはできません。また、ニュートン法だけでは初期値しだいで根を取りこぼします。そこでベジエ曲線の凸包性を使い、「根の入っている可能性のある区間」を確実に絞り込んでいきます。

1. 制御多角形を描く
   点 (k/n, g_k) を結びます。曲線は、これらの点の凸包の内側にあります。
2. 凸包と t 軸の交わりを求める
   凸包が t 軸（g = 0）と交わらなければ、この区間に根はありません。交わるなら、その交わりの区間 [t_min, t_max] の外に根はありません。
3. 区間を切り出す
   de Casteljau 法で [t_min, t_max] の部分曲線を取り出し、[0,1] に再パラメータ化します（形は変わらず、拡大して見るのと同じです）。
4. 縮まらなければ二分する
   絞り込みで区間が25%以下にしか縮まなかったときは（残りが75%を超える場合）、区間を半分に分けて左右を別々に処理します。複数の根が近くにあるときに、それぞれを分離するためです。
5. 収束したら根とする
   区間の幅が 10⁻⁹ 未満になったら、その中央を根とします。最後にニュートン法を最大4回かけて、機械精度まで仕上げます。

実行前（0ステップ目）は、制御点を上下にドラッグして g の形を変えられます。ステップを進めるたびに、下の帯グラフで「除外された範囲（赤）」が広がり、「処理待ちの範囲（青）」が根の周りに絞られていきます。切り出した部分曲線はほぼ直線に近づき、凸包が細くなるので、根のまわりの区間は急速に縮みます。単根では、誤差が二乗のペースで減る2次収束になります。

実装の細部

凸包と t 軸の交わりの求め方

凸包そのものは作りません。符号の異なる2つの制御点を結ぶ線分がどれも凸包の内側にあることを使い、そのすべての組について線分が t 軸を横切る t 座標を計算して、最小値と最大値を取ります。これが凸包と t 軸の交わりの両端になります。18次では制御点19個の組は最大171通りで、計算は軽いです。係数がちょうど0の制御点は、その位置自体を候補に入れます。

精度を保つための工夫

• 範囲判定を先に行う：19個の n·Q_k の最小値と最大値を控えておき、d がその外にある弧は根探索を行いません。曲面のスライス面が大半の弧と交わらない場面では、これだけで計算の大部分が省けます。
• 収束閾値は 10⁻⁹：これより小さくすると、端点の係数が丸め誤差に埋もれて、区間が縮みきらないうちに探索が終わることがありました。閾値を 10⁻¹³ から 10⁻⁹ に緩め、その後にニュートン法で精度を上げる構成にしたところ、t = 1 のすぐ手前（4 × 10⁻⁷）にある根の取りこぼしが解消しました。
• ニュートン法は仕上げだけ：導関数のベジエ係数は n(g_k+1 − g_k) です。更新量が 10⁻⁶ を超えるときは、別の根へ飛んだと見なして採用しません。
• 暴走を防ぐ上限：再帰は 6000 回、深さは 90 まで。恒等的に 0 の多項式（曲線が平面の上に載っている）は、孤立した根がないので空の結果にします。

スライス線とトリム境界をつなぐ

球の位置は上の方法で厳密に決まりますが、画面のスライス線（赤い線）は、ベジエクリッピングで絞り込んだ小さなパッチの中をマーチングスクエア法で線分にしたものです。線分の端をトリム境界にきちんとつなぐため、次の処理をしています。

• UV矩形の枝刈り：再帰の各段階でUV矩形を持ち回り、矩形がトリムの穴に完全に含まれるなら、その枝を打ち切ります（円は凸なので、矩形の4隅がすべて円の内側なら矩形全体が内側です）。矩形が穴の外接矩形と重ならないなら、内外判定を省略します。
• 境界での線分の切断：線分の一端が穴の中、もう一端が外にあるときは、二分法で境界との交点を求めて切ります。
• 球へのスナップ：切った端点の近くに、距離関数から求めた交点があれば、端点をその位置に合わせます。こうして、スライス線の端が球の中心にぴったり届きます。

つまり球は距離関数の根から、線は格子から作られますが、根のほうが正確なので、線の端を根に合わせる形で整合させています。

検証

制限と注意点

• 弧ごとに独立：1つの円は4本の弧から成るので、弧の継ぎ目では同じ点が2回見つかることがあります。3次元距離が 10⁻⁶ 未満の点を1つにまとめています。
• 曲線が平面上にある場合：g が恒等的に0なら、根は無数にあります。実装は根なしとして扱い、球を置きません。
• トリムは円のみ：現在の実装で生成するトリムは円（4弧の閉ループ）だけです。根探索そのものは、任意の3次ベジエ弧に対してそのまま使えます。

式のまとめ