衝突判定の多くは、一定間隔の時刻ごとに「いま重なっているか」を調べる方式です。しかし物体が速いと、ある時刻では手前、次の時刻では向こう側にいて、どちらの時刻でも重なりが検出されません。これがすり抜け（トンネリング）です。
下図は、半径 0.15 の球がベジエ曲面（ティーポットの注ぎ口）をかすめる軌跡について、球の中心から曲面までの最短距離を時刻の関数として描いたものです。
接触している時間帯は、この例では全体の 2.7 % しかありません。評価時刻をいくら細かくしても、物体が速くなればいつでも同じ状況が再現します。刻みを細かくする方向では原理的に解決しません。
ベジエ曲面 S(u,v) の値は、必ず制御点の凸包に含まれます。したがって、ある領域について「ここには解が存在しない」ことを計算で確定できます。
衝突判定に使うときは、これを時間を含めた領域に対して適用します。すなわち「この時間帯・このパラメータ領域では接触が起こり得ない」と確定した箱だけを捨て、確定できない箱を細分していきます。捨てた箱に解が無いことは保証されているので、接触時間がどれほど短くても見落としません。
相手の形状によって、時間の扱い方に2通りの実現法があります。以下ではそれぞれを説明します。
| 相手の形状 | 時間の扱い | 条件関数 |
|---|---|---|
| 球 | 第3のパラメータ t を追加 | F(u,v,t) = |S(u,v) − C(t)|² − r²（3変数ベジエ関数） |
| 三角形・凸多面体 | スイープ体として空間に畳み込む | 掃引でできる凸多面体の各面による曲面のクリップ |
球の中心が時刻の関数 C(t) で動くとき、接触の条件は次式です。
C(t) をベジエ曲線で表せば、F は3変数のベジエ関数になります。|S − C|² は C について2次なので、t の次数は軌跡の次数の2倍です。
| 軌跡 C(t) | t の次数 | F の次数 (u×v×t) | 係数の個数 |
|---|---|---|---|
| 静止（動かない） | 0 | 6×6 | 49 |
| 線分（等速直線運動） | 1 | 6×6×2 | 147 |
| 自由落下・放物運動 | 2 | 6×6×4 | 245 |
| 一般の m 次ベジエ曲線 | m | 6×6×2m | 49(2m+1) |
係数の構成は軽い計算で済みます。F を展開すると
となり、第2項は変数分離形 f(u,v)·g(t) です。u,v と t は独立な変数なので、各因子を目的次数に上げた係数どうしの積がそのまま3変数の係数になります。第1項は (u,v) だけ、第3項は t だけの関数で、定数 −r² はバーンスタイン基底が1の分割であることから全係数に加えるだけです。
ユタティーポット（32パッチ）に対し、時刻を4000分割し各時刻で全パッチを29×29点に標本化した総当たり計算と比較しました。
| 軌跡 | 半径 | 本手法 | 総当たり | 差 | 判定ノード | 時間 |
|---|---|---|---|---|---|---|
| (−4.5, 2.6, 0) → (4.5, −0.6, 0) | 0.5 | 0.31575 | 0.31600 | 0.00025 | 4498 | 95 ms |
| (−5, 0.2, 0) → (5, 0.2, 0) | 0.3 | 0.20904 | 0.20925 | 0.00021 | 4824 | 153 ms |
| (0, 5, 0) → (0, −5, 0) 真上から | 0.4 | 0.27550 | 0.27550 | 0.00000 | 7760 | 346 ms |
| (3.2, 4, 0) → (3.2, −3, 0) 注ぎ口 | 0.15 | 0.38001 | 0.38025 | 0.00024 | 1724 | 51 ms |
| (−5, 6, 0) → (5, 6, 0) 頭上を通過 | 0.5 | 衝突なし | 衝突なし | — | 208 | 2 ms |
最後の行に注目してください。衝突しない軌跡は 208ノード・2ミリ秒で「絶対に衝突しない」と断定できます。ほとんどのパッチが最初の1回の符号チェックで消えるためで、衝突判定では圧倒的多数を占める「当たらない場合」がもっとも速いという、実用上ありがたい性質になっています。
相手が多角形の場合、時刻を変数として追加しなくても済む、より軽い方法があります。鍵は次の事実です。
剛体が並進するときのスイープ体（掃いた領域）は、厳密に凸多面体になる。
三角形と並進ベクトルのミンコフスキー和なので、側面3枚とキャップで囲まれた三角柱がスイープ体そのものです。近似でも外接でもなく、完全に一致します。
したがって次が厳密に成り立ちます。
曲面と凸多面体の交差判定は、すでに確立している「凸多面体で曲面をクリップする」処理そのものです。各面について、曲面の制御点の符号付き距離を係数とするベジエ関数を作り、全係数が同符号なら分離を確定、そうでなければ UV 範囲を収縮して反復します。時間を陽に扱うことなく、タイムステップ全体にわたる衝突の有無が判定できます。
速度がどれほど速くても、接触時間がどれほど短くても、この判定が正しければ見落としは起こりません。
「衝突したか」だけでなく「いつ衝突したか」が必要です。ここで注意すべき点があります。
正しくは、静止判定ではなくスイープ判定で時間区間を二分します。区間 [a,b] のスイープ体が曲面と交差しないなら、その時間帯に接触が無いことは保証されています。したがって次のように進めます。
常に「最初の接触を含むことが保証された区間」を保ちながら幅を半分ずつ縮められるため、接触時間がどれほど短くても取りこぼしません。新しい数式は一切必要なく、既存のスイープ判定を再帰的に呼ぶだけです。
過検出の除去 クリッピングは反復回数や誤差閾値が緩いと「交差あり」側に倒れます。見落としはしませんが過検出はするため、これをそのまま接触として採用すると、実際には当たっていない位置で停止してしまいます。そこで、区間が十分細くなった葉では反復回数を上げて再確認し、過検出と分かればその枝を捨てて後半の区間を調べ直します（バックトラック）。全区間が過検出と判明すれば接触なしとして落下を継続します。
このとき誤差閾値 tol は変えてはいけません。tol は接触の定義そのものなので、小さくすると、かすめる接触を取り逃がして貫通が深くなります。増やすのは反復回数だけにします。
薄いスイープ体の退化 区間が狭まると三角柱が薄くなり、側面を作る3点がほぼ一直線に並んで法線が数値的に定まらなくなります。厚みが誤差閾値を下回った時点で、厚み0の極限である静止三角形の判定へ切り替えることで回避します。
曲面を細かく標本化した独立の真値と比較しました（速度1.0、tol = 0.02、反復2、1/60秒ステップ）。
| 進行方向 | 真値（移動距離） | 旧方式（点サンプリング） | 本方式 |
|---|---|---|---|
| 垂直 −Y | 3.1530 | 3.1001（−0.0529） | 3.1583（+0.0053） |
| ＋X 斜め | 3.4925 | 3.4697（−0.0228） | 3.5000（+0.0075） |
| −X 斜め | 3.2405 | 3.2334（−0.0071） | 3.2500（+0.0095） |
| ＋Z 斜め | 3.4560 | 3.4057（−0.0503） | 3.4583（+0.0023） |
| −Z 斜め | 3.2580 | 3.1465（−0.1115） | 3.2667（+0.0087） |
誤差は 0.02〜0.11 から 0.002〜0.011 へと1桁改善し、すべて許容誤差 tol = 0.02 の範囲内に収まりました。符号にも意味があります。旧方式は誤差が負、すなわち接触より手前で止まっていました。過検出をそのまま接触として採用していたためです。本方式は誤差が正で、保証区間の上端を採るため確実に接触した側で止まります。物理的にはめり込み方向に倒れないほうが自然です。
1ステップの移動量を増やしていくと差は決定的になります。
| 1ステップの移動量 | 旧方式 | 本方式 | 旧の計算時間 | 本方式の計算時間 |
|---|---|---|---|---|
| 0.017 | −0.053 | +0.005 | 0.68 ms | 1.12 ms |
| 0.333 | −0.078 | +0.003 | 0.41 ms | 2.09 ms |
| 1.000 | −0.075 | +0.011 | 0.43 ms | 1.87 ms |
| 3.333 | 見落とし（すり抜け） | +0.187 | 99.7 ms | 4.5 ms |
素直に当たる方向では、スイープ体は平面が4枚あるぶん静止三角形より重く、1〜2 ms 程度かかります。一方、斜め方向では旧方式が過検出のたびに4点走査を無駄打ちして判定回数が383回に膨らんだのに対し、本方式は凸包による棄却が効いて4〜5回で決着し、19.1 ms から 6.3 ms へ短縮しました。極端な高速移動では、旧方式が 99.7 ms を費やしたうえで見落としたのに対し、本方式は 4.5 ms で検出しています。
| スイープ凸多面体 | 3変数 F(u,v,t) | |
|---|---|---|
| 対象 | 並進する多角形・凸多面体 | 球、任意の軌跡・変形・回転 |
| 追加の変数 | 不要 | 時刻 t |
| 判定に使う量 | 平面との符号付き距離（線形） | ベジエ係数（6×6×2 次など） |
| スイープ体の扱い | 厳密に凸（近似なし） | — |
| 接触時刻 | 時間方向の再帰が必要 | 求解に内蔵 |
| 多項式求解 | 不要 | 必要（ただしクリッピングで代替） |
| 計算コスト | 軽い | 重い |
多角形かつ並進という条件下では、スイープ体方式のほうが明確に優れています。既存の凸多面体クリップをそのまま使え、平面は4枚で済み、多項式求解が不要だからです。曲がった軌跡・回転・変形が必要になった時点で3変数方式へ移る、という整理が自然です。
なお回転が加わると、スイープ体は凸でなくなります。各頂点が弧を描き、弧は弦の外側に膨らむため、2つの姿勢の凸包はスイープ体の一部を取りこぼします。対処は、タイムステップ内の弧の膨らみ（サジッタ）を上から抑えて各平面を外側にオフセットするか、四元数を使って3変数の定式化に移るかのいずれかです。四元数を用いれば回転行列の成分は四元数成分の2次式になるため、有理ベジエ関数として同じ枠組みで扱えます。
最も広く使われている方式です。実装が容易で高速ですが、第1節で示したとおりすり抜けを原理的に排除できません。刻みを細かくしても、物体が速くなれば同じ状況が再現します。
現在の距離と最大速度から「この時間だけは絶対に衝突しない」安全な時間幅を求めて前進する方式です。見落としは生じませんが、距離計算を繰り返すため接触直前で歩幅が極端に小さくなり、収束が遅くなります。また曲面に対する距離計算そのものが容易ではありません。
4点が同一平面上に来る条件から、時刻の3次方程式を解く古典的な方法です。この3次式を浮動小数点で解くと、ほぼ平行・ほぼ縮退した配置や接触に近い場合に符号判定を誤り、衝突を見落とすことがあると長く指摘されてきました。布や髪のシミュレーションでは一度の見落としが自己交差を招き、破綻が伝播します。
これに対し、本稿のスイープ体方式は多項式求解を一切使いません。平面との距離という線形量と凸包の符号判定だけで済むため、数値的な壊れ方が根本的に少ない構造です。
近年 CCD の分野で主流になりつつある方式で、時間区間と空間領域の箱に対して関数値の上下限を保証つきで求め、解が無いと確定できた箱を捨てて残りを細分します。これはベジエクリッピング法の凸包による棄却とまったく同じ発想です。CCD の分野はロバスト性を追求した結果、独立に同じ原理へ到達しています。
ただし既存の包含法は区間を二分して細分するのに対し、ベジエクリッピングは制御係数から作る上下限の包絡線によって解が存在し得る範囲まで一気に収縮させます。同じ保証を保ちながら探索量が減ります。実測では、凸包クリップを無効にして単純4分割のみとした場合、輪郭線抽出における判定ノード数が 753 から 4328 へと約5.7倍に増加しました。
既存の CCD 研究は、ほぼすべて点・線分・三角形を対象としており、曲面はポリゴンに分割してから扱うのが前提です。分割を細かくすればポリゴン数が爆発し、粗くすれば実際の曲面より内側で判定することになって、めり込みや浮き、分割由来の偽の稜線による引っかかりが生じます。本稿の方法は曲面のまま扱うため、この問題が原理的に生じません。
| 手法 | すり抜け | 曲面の扱い | 特徴 |
|---|---|---|---|
| 離散時刻の重なり判定 | 生じ得る | 分割が必要 | 最も簡便・高速。速度が上がると破綻 |
| 保守的前進 | なし | 距離計算が困難 | 接触直前で歩幅が縮み収束が遅い |
| 3次方程式による CCD | 生じ得る | 分割が必要 | 退化配置で符号判定を誤る |
| 包含に基づく手法 | なし | 分割が必要 | 二分細分のため収縮が遅い |
| 本手法 | なし | 曲面のまま | 凸包性で確実に棄却。多項式求解が不要（多面体の場合） |
第1に、衝突判定を「曲面上の条件をベジエ関数の零点問題として解く」という枠組みの一事例として位置づけた点です。断面抽出、輪郭線抽出、球や二次曲面との交線と同じ解法がそのまま適用でき、条件式と次数だけが異なります。
第2に、凸包性による棄却が変数の個数に依存しないことを利用し、2変数の交線抽出と同一の実装で3変数の連続衝突検出が得られることを示した点です。テンソル積バーンスタイン基底は3変数でも非負かつ総和が1であるため、判定は完全に同じ形になります。
第3に、並進するスイープ体が厳密に凸多面体であることを利用し、時刻を変数として導入せずにタイムステップ全体の衝突有無を判定できることを示した点です。多項式求解を回避しているため、既存の三角形 CCD が抱える数値的頑健性の問題が構造的に生じません。
第4に、曲面をポリゴン分割せずに扱える点です。既存の CCD 研究の空白領域であり、CAD データ（NURBS）をそのまま VR や物理シミュレーションで扱う場面に直結します。
包含に基づく手法が近年 CCD 分野の主流になりつつあることを踏まえると、ベジエクリッピング法は1990年の時点で同じ原理を採用していたことになります。「古い手法」ではなく、現在の最良の方針を先取りしていたと位置づけられます。
ちょうど接する瞬間、条件関数は符号を変えずに0に接します。したがって「符号の変化」を頼りにする検出では接触を取り逃がします。「F の最小値が0以下になる最小の t」として扱う必要があります。
棄却が保証つきであることと、最終的に得られる時刻の精度は別問題です。捨てた箱に衝突が無いことは数学的に保証されるため見落としは生じませんが、残った箱の中で時刻を追い込む段階には近似が含まれます。また係数計算は通常の浮動小数点で行っているため、数学的には保証つきでも数値的には証明されていません。係数計算に上下丸めを入れて区間として扱えば、この点も解決できます。
現状は1接触あたり数〜百数十ミリ秒です。ゲームの衝突判定予算は1フレーム全体で数ミリ秒なので開きがあります。ただしこれは最適化の問題で、包含球の階層によるブロードフェーズ（各箱の判定は完全に独立なので SIMD・GPU 並列化に向く）で詰められる性質のものです。