2つのベジエ曲面の交差曲線を求める問題（Surface-Surface Intersection, SSI）は、CAD における最も基本的かつ最も難しい処理のひとつです。求めるのは次の連立方程式の解集合です。
未知数は u, v, s, t の 4 個、条件式は x, y, z 成分の 3 本なので、自由度は 4 − 3 = 1、すなわち解集合は 1 次元の曲線になります。
SSI が難所とされてきた理由は、解が点ではなく曲線であることに由来します。
本稿では、この問題を4次元の箱に対する凸包による棄却として扱う方法を示します。ベジエ曲面の凸包性により「この箱には解が存在しない」と確実に断定できるので、取りこぼしのない探索が可能になります。
(u,v) の箱と (s,t) の箱の組、すなわち部分パッチの対を 1 つのノードとして扱い、棄却・収縮・分割を繰り返します。棄却は 2 段構えです。
ベジエ曲面は制御点の凸包に含まれます。したがって、2つの部分パッチの制御点の境界箱が重ならなければ、その組み合わせでは交差が起こり得ません。比較 6 回で済む最も安い判定であり、実形状では大部分のパッチ対がこれだけで消えます。
境界箱で捨てられない場合、より強い棄却としてFAT 平面を使います。一方の曲面（B とする）の平均平面を作り、その平面からの符号付き距離の最小・最大で B を挟む平行 2 平面を構成します。曲線どうしの交点計算で使う FAT Line の曲面版です。
ここで重要な性質があります。平面からの符号付き距離は
と書けますが、これは制御点について線形です。したがって式 (1) のように、F のベジエ係数は制御点にそのまま内積を当てはめるだけで得られます。
輪郭線抽出や抜き勾配のように法線 N を含む条件では、条件式が制御点について 3 次以上になるため、積の公式で係数を組み立てる必要がありました。SSI ではこの手間が要りません。距離が線形なので、内積を 16 回計算するだけで凸包性が使える形になります。SSI が本手法と相性の良い問題である理由のひとつです。
あとは凸包性により、距離が帯 [lo, hi] に入り得ない UV 範囲を確実に削り落とせます。u を固定すると F は各 u 列の係数の凸結合になるので、列ごとの最小係数による下限のベジエ関数と、最大係数による上限のベジエ関数が F を挟みます。
A と B を入れ替えて同じ操作を行えば、両方のパラメータ範囲が縮みます。
範囲が十分縮まらない場合は分割します。このときどちらを分割するかが効率を左右します。本実装では、平均平面からのずれが大きい方（＝より曲がっている方）を優先して 4 分割します。平坦な側をいくら分割しても平面近似の精度は上がらないためです。
両方のパッチが十分平坦になったら、それぞれを 4 隅からなる平面四辺形（2 つの三角形）で近似し、三角形どうしの交線を線分として取り出します。平坦性は平均平面からの最大ずれで測るので、得られた線分が真の交差曲線から高々その値しか離れないことが保証されます。
ティーポット（32パッチ）と 1 枚の双3次パッチの交差について、許容誤差 0.02 での計測結果です。
| 曲面A | 判定ノード | 棄却 | クリップで収縮 | 末端パッチ対 | 交差線分 | 時間 |
|---|---|---|---|---|---|---|
| ティーポット（32枚） | 480 | 244 | 399 | 124 | 97 | 8 ms |
| ドーナツ（8枚） | 480 | 266 | 342 | 96 | 82 | 14 ms |
| 楕円体（8枚） | 400 | 179 | 381 | 123 | 83 | 13 ms |
クリップの ON / OFF を比較しました。
| 許容誤差 | OFF 判定ノード | ON 判定ノード | ノード比 | OFF 時間 | ON 時間 |
|---|---|---|---|---|---|
| 0.050 | 596 | 304 | 1.96 倍 | 4.5 ms | 7.4 ms |
| 0.020 | 1128 | 480 | 2.35 倍 | 2.0 ms | 6.7 ms |
| 0.005 | 2264 | 956 | 2.37 倍 | 4.2 ms | 17.0 ms |
| 0.001 | 4712 | 2024 | 2.33 倍 | 6.4 ms | 21.4 ms |
実時間でも効かせるには、(i) 距離が線形であることを活かして包絡線を作らず制御点の最小最大だけで区間を決める、(ii) 浅い深度でのみクリップを適用する、(iii) 境界箱を方向性境界箱（OBB）に変えて棄却率そのものを上げる、といった改良が考えられます。
得られるのは順序を持たない線分の集合です。末端のパッチ対ごとに独立して三角形どうしの交線を求めているため、パッチ対をまたいだ接続情報を持っていません。すなわち、交差曲線が何本の閉ループからなるか、ある線分の次にどの線分が続くか、といった位相構造は分かりません。
描画するだけならこれで十分ですが、次の用途では順序づけられた点列（ポリライン）への変換が必要です。
変換には端点を照合して線分をつなぐ後処理を入れます。ただし端点の一致を浮動小数で直接比較すると不安定なので、座標を量子化するか、分割構造からパッチ対の隣接関係を辿るほうが堅実です。より本質的には、末端で平面近似せず、パッチ境界上で 1 次元のベジエクリッピングにより厳密に交点を求めて連結する方式に変えるのが望ましく、参考文献[2]（Sederberg-Nishita の Geometric Hermite 近似）は、こうして得た交差曲線を滑らかな曲線として表現する問題を扱っています。
両曲面を格子状に細かく評価してポリゴン化し、三角形どうしの交差を総当たりで求める方式です。実装が単純で確実そうに見えますが、格子の間をすり抜ける細い交差や小さな閉ループを原理的に排除できません。精度を上げようとすると評価点数がパラメータの 2 乗、対の数はその 2 乗で増えます。
交差曲線上の 1 点を見つけ、そこから接線方向に予測子・修正子で追跡する方式です。滑らかな曲線が直接得られ、1 本を追う分には非常に高速です。
弱点は開始点の網羅性です。独立した閉ループが別の場所にあっても、そこに開始点が見つからなければ丸ごと見落とします。「開始点をどう漏れなく見つけるか」がこの方式の本質的な課題であり、結局は本稿のような領域分割による探索が必要になります。また、交差曲線が接する箇所や分岐する箇所で追跡が破綻しやすく、歩幅の制御にも経験的な調整が要ります。
終結式により変数を消去して 1 変数の代数方程式に帰着させる方式です。厳密ですが、双3次パッチ 2 枚で非常に高次の多項式となり、計算量と数値的安定性の両面から現実的ではありません。
区間演算で保証つきの上下限を求めながら領域を細分する方式で、保証がある点は本手法と同種です。ただし区間演算は過大評価が蓄積しやすく、収縮が遅くなります。ベジエ表現の凸包性は過大評価のない緊密な上下限を与えるため、この点で有利です。
| 手法 | 取りこぼし | 精度 | 特徴 |
|---|---|---|---|
| 格子評価＋マーチング | 生じ得る | 格子依存 | 単純。精度向上に伴い計算量が急増 |
| 数値追跡法 | 生じ得る | 高い | 滑らかだが開始点の網羅と分岐処理が困難 |
| 代数的手法 | なし | 厳密 | 高次となり計算量・安定性が問題 |
| 区間解析 | なし | 任意 | 過大評価により収縮が遅い |
| 本手法 | なし | 任意 | 凸包性で確実に棄却。距離が線形なので係数構成が自明 |
なお実用システムでは、本手法で交差曲線の存在する領域を漏れなく絞り込み、その中で数値追跡法により滑らかな曲線として追うという組合せが有効です。両者は競合ではなく補完関係にあります。
2曲面が接する場合、交差は点または縮退した曲線になります。距離の符号変化を頼りにする手法では検出できませんが、本手法は「境界箱が重なるか」「帯に入り得るか」という包含関係で判定しているため、接触も棄却されずに残ります。ただし末端での平面近似では線分が出ないことがあり、接触点を明示的に扱う処理が別途必要です。
棄却されなかったパッチ対でも、その内部に非常に小さな閉ループが完全に収まっている場合、平面近似では線分が出ずにループが消える可能性があります。凸包判定が保証するのは「捨てた領域に解が無いこと」であって、「残した領域で解を正しく再構成できること」ではありません。許容誤差を十分小さく取るか、末端での判定を細かくすることで対処します。
2つの平面がほぼ平行なとき、交線の方向ベクトルが数値的に定まりません。本実装では外積の大きさが閾値を下回る場合を除外しています。実用上は、重なり領域を面として扱う別処理が必要です。
SSI は、未知数 4・条件 3 の連立方程式として、(u,v,s,t) の 4 次元の箱に対する凸包による棄却の問題に還元できます。平面からの距離が制御点について線形であるため、条件関数のベジエ係数は内積を計算するだけで得られ、積の公式すら不要です。
凸包性により「この箱には交差が存在しない」ことを保証つきで断定できるので、細い交差や小さな閉ループを取りこぼしません。これは、格子評価や数値追跡といった従来法が構造的に抱えてきた弱点の解決にあたります。