ベジエクリッピング法（Bezier Clipping）の有効性

研究の起源：ベジエクリッピング法は、1990年にベジエ曲面とレイ（視線）の交点計算のために開発された手法[1]です。以来、CG・CAD における交差判定や最近点探索の基礎技術として広く応用されています。

基本的な考え方：線・点・平面から、ベジエ曲線／曲面への距離関数を定義します。この距離関数はベジエ関数になるため、

・距離関数＝０となる点　→ 交点, ・距離関数の微分＝０となる点　→ 最近点

という統一的な枠組みで、多項式の求解から曲面同士の交差まで、あらゆる問題を「ベジエ関数の零点を求める問題」に帰着できます。ベジエ関数は制御点の凸包性を持つため、解の存在範囲を確実に絞り込みながら反復でき、初期値に依存せず・解の取りこぼしがなく・高速に収束する点が最大の利点です。この方法はヘルミート曲線、NURBSなど多様なパラメトリック曲線に対応できます。多様な曲線もあり50余りのプログラムを生成ＡＩを活用し開発し、解説文を作成してます。注：論文発表前のものについてのデモプログラムは追加予定と表示してます。

統一性	交点・最近点・極値・最短距離を、すべて「ベジエ関数の零点／微分の零点」として同一のアルゴリズムで扱える。
頑健性	凸包性により解の存在区間を保証しながら区間を狭めるため、ニュートン法のように初期値によって発散したり解を見落としたりしない。
高速性	反復ごとにパラメータ区間が大きく縮小し、２次に近い収束を示す。
汎用性	多項式の求解、NURBS、三角形メッシュ、凸多面体によるクリップなど、２次元から３次元まで同じ原理で拡張できる。

１．多項式の解、曲線処理、距離関数

ｎ次多項式の解法多項式はベジエ関数に変換できるので、ベジエ関数が０となる点が解となる。実演画像解説
多項式から Bezier 関数への変換べき級数（power form）表現をベルンシュタイン基底（ベジエ形式）へ変換する。実演画像
ｎ次ベジエ曲線の極値の検出ｎ次多ベジエ曲線の微分が (n-1) 次のベジエ関数になることを利用し、その零点として極値を求める。実演画像
ｎ次ベジエ曲線の変曲点の検出ｎ次ベジエ曲線C(t)の場合、C′(t) × C″(t) = 0が変曲点で、これは(2n−3)次のベジエ関数となる。これをBezierCliping法で解く実演画像
ｎ次ベジエ曲線の曲率の極値検出ｎ次ベジエ曲線C(t)の場合、κ(t) = (x′y″−y′x″)/(x′²+y′²)^{3/2} が曲率で、これは κ′=0 は分子 N(t) = σ′w − (3/2)σw′、次数 4n−6 のベジエ関数ベジエ関数となる。これをBezierCliping法で解く実演画像解説
ベジエ曲線の弧長パラメータ化ｎ次ベジエ曲線C(t)の場合、弧長　w(t) = |C′(t)|² の次数が 2(n−1) のベジエ関数となる。これをBezierCliping法で解く実演画像解説
ｎ次ベジエ曲線の自己交差の検出ｎ次ベジエ曲線の自己交差をFATLine法で検出実演画像
ｎ次ベジエ曲線のオフセット曲線とトリミングｎ次ベジエ曲線、判定で使う距離関数 E(u) = (C(u)−P)・C'(u)は次数 2n−1 のベジエ関数で、これをベジエクリッピング法で解を求める実演画像解説
面から曲面への距離関数ｎ次曲面ならｎ次のベジエ関数（曲面になる。実演画像
点から曲面への距離関数ｎ次曲面なら2ｎ次のベジエ関数（曲面）になる。実演画像

２．２次元平面の幾何

線分とベジエ曲線の交点線分からｎ次ベジエ曲線への距離関数はｎ次ベジエ関数であるので、それが０となる点が交点。実演画像 1
線分と有理ベジエ曲線の最短点・交点線分からｎ次ベジエ曲線への距離関数の微分はn-1次ベジエ関数であるので、それが０となる点が最短・交点。実演画像
線分とベジエ曲線の最近点・交点線分から曲線への距離関数を求め、距離関数が０が交点。交点がないなら距離関数の微分は (n-1) 次のベジエ関数になるので、それが０となる点が最近点。実演画像、画像
線分と有理ベジエ曲線の交点（最短点）線分から有理曲線への距離関数(分子はn次）を求め、距離関数の微分は (2n-1) 次のベジエ関数になるので、それが０となる点が最近点。実演画像
線分とヘルミート曲線の交点（最短点）ヘルミート曲線はベジエ曲線に変換できる。線分から曲線への距離関数を求め、距離関数はn次のベジエ関数で、それが０となる点が交点、距離関数の微分は(n-1)次のベジエ関数になるので、それが０となる点が最近点。実演画像
線分とBスプライン曲線の交点（最短点） Bスプライン曲線は幾つかのベジエ曲線に変換できる。線分から曲線への距離関数を求め、距離関数はn次のベジエ関数で、それが０となる点が交点、距離関数の微分は(n-1)次のベジエ関数になるので、それが０となる点が最近点。実演画像
点とベジエ曲線の最短距離点と曲線との距離は 2n 次のベジエ関数で、その微分は (2n-1) 次のベジエ関数になることを利用する。実演リンクは順次追加予定
点と有理ベジエ曲線の最短距離点と曲線との距離は 2n 次の有理ベジエ関数で、その微分の分子は (３n-1) 次のベジエ関数になることを利用する。実演画像、
点からベジエ曲線の接線点と曲線C(t)との接線は（C(t)−P) × C'(t) = 0 、これは(2n−1)次のベジエ関数になることを利用する。実演画像
ベジエ曲線同士の交点（FAT Line）曲線を包含する２つの平行線を FAT Line と称する。一方の FAT Line で他方の曲線をクリップする操作を反復すると交点に収束する。FAT Line（線分）からの距離関数はｎ次ベジエ関数であるのを解く実演画像
ヘルミート曲線同士の交点（FAT Line）ヘルミート曲線はベジエ曲線に変換できる。曲線を包含する２つの平行線を FAT Line と称する。一方の FAT Line で他方の曲線をクリップする操作を反復すると交点に収束する。FAT Line（線分）からの距離関数はｎ次ベジエ関数であるのを解く実演画像
ベジエ関数とベジエ関数の乗算ｎ次ベジエ関数とｍ次ベジエ関数の乗算は（n+m)次のベジエ関数実演画像
ベジエ曲線と円の交差曲線と点と距離から円との交差判定実演画像
ベジエ曲線とベジエ曲線の最近点両曲線間の距離関数を用い、その偏微分が０となる点を求める。実演リンクは順次追加予定
有理ベジエ曲線と有理ベジエ曲線の最近点両曲線間の距離関数を用い、その微分（3n-1次ベジエ関数）が０となる点を求める。実演画像
NURBS 曲線と線分の交差 NURBS を有理ベジエ曲線分に分解したうえで、各曲線の距離関数（n次ベジエ関数）に同じクリッピング操作を適用する。実演画像 1
NURBS 曲線同士の交差有理ベジエ形式に変換して FAT Line による反復クリップを行う。実演リンクは順次追加予定
三角形（凸多角形）でベジエ曲線をクリップ各辺での曲線クリップにより多角形内の曲線を抽出でき、交差判定に応用できる。実演画像
視野ウインドウでベジエ曲線をクリップウインドウ各辺での曲線クリップにより視野内の曲線を抽出でき、交差判定に応用できる。実演画像
円とベジエ曲線の衝突判定円の包含箱（進行方向に傾いた）の事前処理。各辺での曲線クリップにより包含箱内の曲線を抽出でき、衝突判定に応用できる。ｎ次の距離関数の解法のみ実演画像

３．３次元空間の幾何

点とベジエ曲面との最短点点とｎ次曲面の距離は 2n×2n 次ベジエ関数なので、U の微分と V の微分がともに０になる点が最小距離を与える。実演画像
線分とベジエ曲面の交差線分は２平面の交線なので、１平面に交差する領域でクリップし、もう一方の面でクリップする。これを反復すると交点に収束する（1990年のレイと曲面の交点計算そのもの）。実演画像、
平面とベジエ曲線の交点・最近点ｎ次曲線と平面からの距離関数はｎ次 Bezier 関数であるので、この関数が０になるのが交点。交点がないなら、微分した (n-1) 次のベジエ関数が０となる点を求める。実演画像、
平面（３角形）とベジエ曲面の最近点曲面と平面からの距離関数は n×n 次 Bezier 関数 H となるので、∂H/∂u ＝０かつ ∂H/∂v ＝０になる点を求める。実演画像、
ベジエ曲面のスライス断面（等高線）切断平面を単位法線 n とオフセット d で表すと、曲面上の点 p の平面からの符号付き距離は f(p) = n·p − d　、平面からの距離関数は n×n 次 Bezier関数となる。実演画像、解説
トリムドベジエ曲面のスライス断面曲面の一部をベジエ曲線で切り込むトリムド曲面：切断平面を単位法線n とオフセットd で表すと、曲面上の点pの平面からの符号付き距離は f(p)= n·p−d、平面からの距離関数はn×n次Bezier関数となる。トリムド曲線と平面の距離関数は18次Bezier関数となる。実演画像、解説
ベジエ曲面の輪郭（シルエット）検出面が視線に対して真横を向く点、すなわち f(u,v) = ( S(u,v) − E ) · N(u,v) = 0 が輪郭線の条件です、関数は 2n-1ｘ2n-1次Bezier関数となる。実演画像、解説
ベジエ曲面のuv検出(レイとの交点) ｽクリーンのｘｙ座標から曲面のUV座標を計算（逆変換）、すなわち P(x,y)=f(u,v) ：２面を含む線分がレイで、２面で曲面を交互にクリップすると交点が得られる。距離関数は nｘn次Bezier関数となる。全画面のraycastingも可能実演画像、解説
ベジエ曲面と球との交差線検出球が曲面との最短距離（2乗）が半径の2乗、すなわち f(u,v) = |( S(u,v) − C)|ーｒ2 = 0 が条件です、交点計算関数は 2nｘ2n次Bezier関数となる。実演画像、 1
ベジエ曲面どうしの交差線検出曲面どうしの交差、すなわち S₁(u,v) = S₂(s,t) が条件です、交点計算関数は２組のnｘn次Bezier関数となる。実演画像、 1
有理ベジエ曲面とNURBSの交差線検出 NURBS(楕円体、ドーナツ、円柱、壺)は有理ベジエ曲面に分割できます。有理曲面どうしの交差、すなわち S₁(u,v) = S₂(s,t) が条件です、交点計算関数は２組のnｘn次有理Bezier関数となる。実演画像、 1
NURBSの包含箱・包含球の抽出および曲面の交差線検出 NURBS(楕円体、ドーナツ、円柱、壺)は有理ベジエ曲面に分割できます。NURBSの包含箱・包含球の抽出し、それを利用した交差判定、すなわち S₁(u,v) = S₂(s,t) が条件です、交点計算関数は２組のnｘn次有理Bezier関数となる。包含箱・包含球検出と交差判定ともにベジエクリッピング法が適用実演画像、 1
球・三角形とNURBS曲面への衝突検出 NURBSは有理ﾍﾞｼﾞｴ曲面に分割できます。有理曲面どうしの交差、すなわち S₁(u,v) = S₂(s,t) が条件です、交点計算関数は２組のnｘn次有理Bezier関数となる。球の境界箱、三角形の包含5面体でクリップ実演画像、 1、
金型のパーティングライン／アンダーカット検出金型の抜き操作：F=(D·N)²−sin²α(N·N) の零集合をベジエクリッピング法で抽出 — 見落とせば金型が成立しないため、取りこぼしの無さが決定的に効く実演画像、
曲線と曲面の最近点曲面と曲線上の点からの距離関数は n×n 次 Bezier関数となるので、∂H/∂u ＝０かつ ∂H/∂v ＝０になる点を求める。実演リンクは順次追加予定
有理曲線と有理曲面の最近点・交点曲面と曲線上の点からの距離関数（分数の形式）は n×n 次 Bezier関数となるので、∂H/∂u ＝０かつ ∂H/∂v ＝０になる点を求める。g(t), q_u(u), q_v(v) のベジエ係数を計算し(3n-1次)、その凸包（制御多角形）とゼロ交差区間から区間を絞り込みます実演画像、 1
凸多面体で曲面をクリップ処理で交差領域抽出凸多面体の各面での曲面クリップにより多面体と交差曲面を抽出できる。実演画像
三角形メッシュと曲面の交差各三角形を厚み０の三角柱（５面体）と考え、５面で曲面をクリップし、内部に曲面が残らなければ交差しないと判定できる。実演画像 1
曲面の包含球の計算制御点の凸包性を利用して曲面を包含する球を求め、交差判定の前処理（枝刈り）に用いる。実演リンクは順次追加予定
レイマーチング法による曲面のレンダリング視線上のサンプリング点から曲面への距離を利用し球に接する曲面の最小の球の半径を抽出し、サンプル点の進む距離を判定。実演リンクは順次追加予定
レイマーチング法による球の融合したメタボール視線上のサンプリング点から曲面への距離を利用し球に接する曲面の最小の球の半径を抽出し、サンプル点の進む距離を判定。実演画像
球と曲面の衝突点から曲面への距離を利用し球と交差する曲面を判定。実演リンクは順次追加予定。 1

4．応用例（論文発表済）

曲面の隠線消去、走査線単位の曲面レンダリング、曲面のラジオシティ法、毛筆のNPR表示、メタボール、GPUを利用した多数メタボール、曲面のモーフイング、オフセット曲面の表示、三角形メッシュ形状と曲面の交差、三角形メッシュ形状と曲面の最近点検出

参考URL

参考文献

T. Nishita, T. W. Sederberg, M. Kakimoto, "Ray tracing trimmed rational surface patches," ACM SIGGRAPH Computer Graphics, 1990.
T. W. Sederberg, T. Nishita, "Curve intersection using Bezier clipping," Computer-Aided Design, Elsevier, 1990.
T. Nishita, K. Kaneda, E. Nakamae, "A scanline algorithm for displaying trimmed surfaces by using Bézier clipping," The Visual Computer, Springer, 1991.
T. W. Sederberg, T. Nishita, "Geometric hermite approximation of surface patch intersection curves," Computer Aided Geometric Design, Elsevier, 1991.
T. Nishita, S. Takita, E. Nakamae, "Hidden curve elimination of trimmed surfaces using Bezier clipping," Visual Computing, Springer, 1992.
T. Nishita, S. Takita, E. Nakamae, "A shading model of parallel cylindrical light sources," Visual Computing, Springer, 1992.
T. Nishita, S. Takita, E. Nakamae, "A display algorithm of brush strokes using Bezier functions," Communicating with Virtual Worlds, Springer, 1993.
T. Nishita, E. Nakamae, "A new radiosity approach using area sampling for parametric patches," Computer Graphics Forum, Wiley, 1993.
T. Nishita, E. Nakamae, "A method for displaying metaballs by using Bezier clipping," Computer Graphics Forum, 1994.
K. Kaneda, Y. Zuyama, H. Yamashita, "Animation of water droplet flow on curved surfaces," Proc. Pacific Graphics, 1996.
T. Nishita, H. Iwasaki, Y. Dobashi, "A modeling and rendering method for snow by using metaballs," Computer Graphics Forum, Wiley, 1997.
T. Nishita, "Applications of Bezier clipping method and their java applets," Proceedings of SCCG, Budmerice, 1998.
T. Nishita, H. Johan, "A scan line algorithm for rendering curved tubular objects," Computer Graphics and Applications, IEEE, 1999.
Y. Kanamori, Z. Szego, T. Nishita, "GPU-based Fast Ray Casting for a Large Number of Metaballs," Computer Graphics Forum, Wiley, 2008.
西田友是, 「Bezier Clipping およびその計算機支援設計への応用」, 福山大学工学部紀要, Vol.13, 1991, pp.45-57.
西田友是, 「自由曲面を忠実に実現するレンダリング手法」, 日経CG, 1991, pp.158-173.

ベジエクリッピングに関する最近の関連論文・発表資料はこちら