100 m/sで衝突判定される Stanford Armadillo
spatial-temporal optimizationによるSDF-SDF CCDの概要。出典: R. G. Nielsen, K. Erleben, “Alternating Spatial-Temporal Optimization for Continuous Collision Detection of Signed Distance Fields”, Figure 1, Computer Graphics Forum, e70570 (2026).
今回のStanford Armadillo
Stanford Armadilloは、複雑な形状同士が高速で接近したとき、最初に接触する時刻をSDFから高速に求められるかを評価するベンチマークに使われています。論文のモデルは345,944三角形で、Stanford 3D Scanning Repositoryのvrip reconstructionと一致します。
形状を幅1 mにスケーリングしてSigned Distance Fieldへ変換し、表面上の特徴的な位置から388個の開始点を選びます。2,000組のrandomized pairについて、一方を静止させ、もう一方を100 m/sで接近させます。角速度は0です。
平均実行時間は0.203 ms、ground truthとのTime of Impact差の平均は9.53e-5でした。345,944枚の三角形を直接追いかける代わりに、388個の疎な開始点から接触候補を探しています。
今回の扱い：SDFへ変換され、ランダム姿勢から100 m/sで接近する2,000組のCCDベンチマークに使われる
状態：無傷
論文の内容
高速運動では離散判定だけでは足りない
Discrete Collision Detectionではframe間を飛び越えるtunnelingが起こる場合があります。Continuous Collision Detectionでは時間区間の中で最初に接触するTime of Impactを求めます。
この研究はtriangle-triangle testを繰り返すのではなく、二つのSigned Distance Fieldへdistanceとgradientを問い合わせながら、3次元位置と時刻を同時に最適化します。
表面上を滑るように探索する
探索点が元の表面から離れないよう、一方のSDFのzero level setへprojectionします。もう一方のgradientもtangent planeへprojectして、表面上の空間移動を構成します。
時間方向は形状間距離と相対速度からstepを決め、接触から遠ければ大きく、近づけば小さく進みます。
Sparse starting points
全表面を密にsampleせず、表面上の局所極値を中心に開始点を作ります。明確な極値がない領域ではisosurfaceと交差するvoxelから補助点を追加し、近すぎる点を削除します。
このsamplingは高速化に有効ですが、全collisionを必ず検出するformal guaranteeはありません。少数の開始点とcoverageにはtrade-offがあります。
Conservative advancementとearly exit
bounding sphereとlinear/angular velocityから、接触可能になる最も早い時刻をconservativeに推定します。
さらに最も早く接触しそうな開始点を先に処理してbest TOIを得ます。他の候補が既にbest TOIより遅ければ探索を中止できます。論文ではearly exitだけでruntimeがおよそ半分になり、複数の最適化を組み合わせると平均約3倍のspeedupが得られています。
数値評価
複雑な評価形状では388 starting pointsで2,000 pairを処理し、平均iteration 1.87、平均runtime 0.203 msでした。
別の1,500 triangle形状では43 starting points、0.040 msです。さらに700万triangle超の形状でもruntimeは0.277 msで、元meshのtriangle数よりSDF query数とstarting points数が支配的であることが示されています。
benchmarkはAMD Ryzen 7735HSの1 coreで実行され、broad phaseは含みません。
制約
regular-grid SDFのgradientはfinite differenceなのでdiscretization errorがあります。論文では実用上のaccuracyはおおむね1e-5程度と整理しています。
またsparse samplingとgradient optimizationに基づくため、no-false-negativeを数学的に保証するCCDではありません。real-time用途寄りの実用的近似として位置付けられています。
論文情報
Alternating Spatial-Temporal Optimization for Continuous Collision Detection of Signed Distance Fields
Rasmus Gabelgaard Nielsen, Kenny Erleben
- Published: 2026年8月12日
- Journal: Computer Graphics Forum
- DOI: https://doi.org/10.1111/cgf.70570
- 分野: Collision Detection / Physical Simulation / Geometry Processing
- 使用モデル: Stanford Armadillo
- 使用箇所: Section 4.1、Tables 2・4
- triangle数: 345,944
- pairs: 2,000
- linear velocity: 100 m/s
- angular velocity: 0
- starting points: 388
- average runtime: 0.203 ms
- average iterations: 1.87
- mean ΔTOI: 9.53e-5
- 用途: SDF-SDF CCDのaccuracy・runtime評価