芸術科学会論文誌 Vol. 20, No. 4, pp. 204-209 (2021)

有理ベジエ曲面と球やメタボールの干渉計算
西田友是 1)（正会員）
1) プロメテックＣＧリサーチ／デジタルハリウッド大学

An Intersection Test between Rational Bezier Surfaces andSpheres/Metaballs
Tomoyuki NISHITA1) (Member)

1) Prometic CG Research / Digital Hollywood University
nishita@shudo-u.ac.jp

アブストラクト
本稿では有理ベジエ曲線（曲面）と球（楕円体あるいはメタボール）の最短距離（クリアランスあるいはギャップ）および交差を計算する方法を提案し、曲面部品の組立・編集や動的シーンでの衝突検出に有効な方法について論じる。さらに、球のみではなく応用として多角形メッシュの包含球の干渉についても提案する。提案法は高次ベジエ関数で判定でき、すべての解法は統合的に Bezier Clipping（ベジエ・クリッピング）法を適用でき、線形計算のみで実現できる特徴がある。なお、Bezier Clipping 法はレイトレーシングにおいて、有理ベジエ曲線と視線の交点を線形計算の収束計算を用いて算出する方法である。

Abstract
This paper presents intersection test and detection of the minimum distance between rationalsurfaces/curves and spheres (ellipsoids or Metaballs). We discuss an effective method of
arranging/editing parts with curved surfaces. The proposed method is applicable tometaballs/bounding spheres for triangle (or polygonal) meshes of curved surfaces not only for spheres.
We proposes the decision function for the intersection test. The functions are defined by high order
Bezier functions, then we apply the Bezier Clipping method for solving the functions. The BezierClipping method has been developed for solving the intersection points between viewing ray andrational Bezier surfaces. The proposed method has the feature using only the liner calculation eventhough simultaneous system including high-order polynomial equations.

キーワード：有理ベジエ曲線, メタボール, 包含球 ベジエ・クリッピング法, 曲線・曲面と球との最短距離

204芸術科学会論文誌 Vol. 20, No. 4, pp. 204-209 (2021)
1. はじめにCAD,CG,アニメーションなどの分野において、曲面の交差、変形などの曲面処理の研究が多くなされている。本稿では有理ベジエ曲線（曲面）と球（包含球、メタボール）の最短距離（クリアランスあるいはギャップ）あるいは交差を計算する方法を提案し、曲面部品の組立・編集や動的シーンでの衝突検出に有効な方法について論じる。特に円錐曲面も表現できる有理曲線・曲面に適用できる方法である。
一般に、球は陰関数表現で、ベジエ曲面はパラメトリック表現されており、異なる表現形式の曲線・曲面間の交差計算は困難とされている。これを線形計算のみの収束計算で効率的に行う方法を提案する。曲面は多角形メッシュで近似表現されることが多い。本稿では曲面を多角形化しないで球との最短距離を検出する。また多角形メッシュの場合、包含球（楕円体も含む）を利用する交差テストがなされる。多角形メッシュでの近似曲面（包含球利用）と曲面表現のままの物体との干渉計算法も提案する。加えて CG でよく利用されるメタボール曲面と有理曲線・曲面との最短点・交差についても論じる。

2. 基本的な考え方
2.1 曲面間の干渉問題
本稿では有理ベジエ曲線・曲面と球（楕円体）やメタボールの最短距離計算法および交差計算を論じる。部品の組み立てや衝突判定の際は、部品間の隙間での作業スペースがあるかも無視できない。よって交差判定のみでなく物体間の最短距離(ギャップ、クリアランス)に重点をおく。
本稿では、曲面としての対象は有理ベジェ曲面を考える、これは，殆どの曲面はベジェ曲面に変換できることから十分な仮定である。ベジェ曲線・曲面の場合の干渉テストには制御点の凸包がよく利用される。この際、どのように細分割するかが重要となる。提案法はこの分割区間を最適予測し、効率よく収束解を得る方法である。曲面体間の間隙が十分かの判定には、静的に球と曲面が交差するかというのみでなく、動的にある軌跡に沿って動く球が曲面間を通過できるかも重要となる。この軌跡は直線のみでなく円弧や放物線などの有理ベジエ曲線が有効である。勿論発射された球の衝突判定に使う軌跡にも放物線は有効である。すなわち、有理ベジエ曲線と曲面間の最短距離計算も必要であ る 。 さ ら に 、 近 年 で は レ イ ・ マ ー チ ン グ 法 （ raymarching）によるレンダリングも行われる。この方法は視線（レイ）上を球が移動し、サンプリング点から物体への最短距離を利用して、レイ上を進む距離を決める方法である。この際にも直線上の点と曲面の最短距離が必要となる。
曲面は多角形メッシュで近似表現されることが多い。各多角形の交差は包含箱や包含球が利用される。包含箱の場合、構成する6面と曲面との交差判定（ミニマックステスト）が利用される。包含球の場合は包含球の中心からの距離のみで判定できる。したがって、曲線・曲面と包含球の交差判定が利用される。提案法は、簡易テストに加え最短距離や交点計算が可能な関数（ベジエ関数）を提案し、解は線形計算のみの収束計算で得られる。
2.2 曲線・曲面間の隙間計算の関連研究
曲面との交差の計算法は数多くあるが、間隔を計算する従来法はあまり多くない。曲面同士の交差に関しては多数なので略し、ここでは最短距離問題を論じる。ただ、著者は205

レイトレーシング法とし曲面と直線（レイと呼ばれる）との交差判定[1]、2 曲線の交差計算法[2]を発表している。
これらを発展したのが本稿である。一方、交差問題でなく最短距離検出方法としては、点と曲線の距離計算があり、古くは西田らの方法[3]や Oha らの方法[4]がある。前者では、曲線上の接線との内積で最近点を判定し円を利用し判定領域を削減している。曲線同士の最短距離に関し、2009年に Chen ら[5]が発表した。また 2011 年 Chang らは、曲線と曲面に対応できる方法を提案した[6]. これらの方法は曲線を 2 分割し、最短点の領域を探索する方法である。これらの方法は、2分探索法であるから、ケースにもよるがこの論文[5]の計算例では曲線間計算に 10－5 精度で 2 桁以上の分割数を要している。
提案法は解の存在領域を予測して分割するので効率よく 1 桁の分割数で収束する。また、平面と曲面の距離に関しては 2017 年に著者らが発表し [13]、同様に曲面間の距離の計算は最近発表した[14]。本稿はこれ等の方法を発展させたものである。
2.3 メタボール
メタボールは陰数表現で、ベジエ曲線はパラメトリック表現である。両社の表現形式が異なるのでこれらの交差判定や最短距離計算は困難とされている。メタボールは、RBF（Radial Basis Function: 放射基底関数）の一種である。
最初Blinn[13]がブロブとよばれる複数の球の融合体の描画法を提案し、その後大阪大学によりメタボールが発表された[14]。前者は密度分布が指数関数で表現されており無限遠点まで密度は存在する欠点がある。後者はいくつかの区分2次式で表現されているので、区間ごとに関数を切り替えるようで境界面を解析的には計算できず、2分法で解くようである。ただ、ボールの密度が連続多項式表現されていると、解法が見いだせるので、著者は6次ベジエ関数で密度を表現し、解析的に表面を解けるようにした[6]。
本稿ではこのベジエ関数の密度分布を採用する。
2.3
Bezier Clipping法および基本関数
本論文で採用するBezier Clipping法は、当初曲面のレイトレーシングのために開発され[1]、次の特徴がある。
①高次多項式や有理関数に適用できる。②ロバストである。
③ニュートン法のように初期値を推測する必要がなく、すべての解が取得できる。④解（交差）がないことを制御点の符号で素早くテストできる。⑤高次Bezier関数でも線形計算の繰返しで解ける。Bezier Clipping法は、交点などの解を得る関数（ベジエ曲線で表現）の解を得るのに区間ニュートン法的に区間の収束計算をする。ベジエ曲線の凸包と軸との交差区間で、関数をクリップし、この関数の凸包から交差区間を抽出する。この関数は直線に近づき解の存在区間は急速に収束する。交差区間が減少しない際は関数を2分割し、各区間で収束計算する。この方法によりすべての解が抽出できる。ここで、判定関数をクリップする方法と元の曲線（あるいは曲面）をクリップする方法が組合される。
また、Bezier Clipping法は次のものに応用されている。
多項式の解、曲線と線分との交点、直線と曲面との交差、曲線と点との最短点の抽出などに加え、隠線消去、メタボール、照明計算など広範囲である[5-14]。
本稿の目標は、パラメトリック曲面であるベジエ曲面（2 つのパラメータ）と陰関数である球やメタボールを対象とした最短距離および交差計算である。点と曲線間の距離計算が基本であるが、説明の都合上 2 次元の曲線を例に述べる。まず,制御点 Pk(xk, yk)をもつ n 次有理ベジェ曲線

芸術科学会論文誌 Vol. 20, No. 4, pp. 204-209 (2021)（パラメータｔ）を考える。

（2n-1）次のベジエ関数なので、これらの関数を加算すると、一"∑"!#$ "! #! $! (&)P(t) = ∑"(1)"!#$ "! $! (&)

ここで、𝐵!" (𝑡)はバーシュタイン多項式で、wk は重み係数である。球と曲線が交差するのは両者の距離が球の半径より小さい場合である。汎用化するため、点が線分上を移動する例を考える。したがって、球の中心点𝑄と曲線Pとの距離が参照できる。本稿で利用する基本的な距離計算の関数を説明する。曲線上の点P(𝑡)、線分（単位法線𝐧）上の点𝑄、線分からの距離関数f、曲線 P への投影関数q、および 2 点PQ 間の距離の 2 乗距離関数𝐷を考える。基本的にはベクトルの内積の形式であるが、実際に適用する際はすべてベジエ関数に変換される。
𝑓(t) = 𝐧 · (P(𝑡) − 𝑄)(2)(3)
𝑓# (t) = 𝐧 · P# (t)𝐷(𝑡) = /P(𝑡)－𝑄0 · /P(𝑡)－𝑄0(4)(5)q(t) = P# (t) · (P(t) − Q)
曲線上の点P(x(t), y(t))の(x, y)座標は式（１）の有理ベジエ関数で定義されているものとする。点Ｐの(x, y)座標にベジエ曲線の式を代入すると、これらの４式ともパラメータｔに関するバーシュタイン多項式（有理の場合は分数形式）となる。ここで、式(2)の距離は線分Q1Q2の単位法線ベクトル とベクトルQPの内積に相当する（あるいは2ベクトルの外積の大きさに相当）。式(3)はその微分である。微分が0になる点が線分からの最短距離（または最大）である。式(4)はベクトルQPの内積で表現されているが、2点間の距離の2乗に相当する。また、式(5)は点Pの接線とベクトルPQの内積が0になる点である（これは接線に投影した長さに相当）。
これらの式は、n 次有理ベジエ曲線（あるいは曲面）に対し、後述のように、それぞれｎ、2n-1, 2n 、3n-1 次の多項式である（非有理ならｎ、n-1, 2n,2n-1 次と簡単）。曲線を細分割により直線近似された場合、最近点は、式(2)の微分すなわち式(3)で解けるので n-1 次である（有理の場合は 2n-1）。なお、3 次元空間の場合、式(2)は平面とその法線で、式(5)は曲面 P(u,v)の u,v 方向の接線から算出できる。

3. ベジエ曲線と線分の距離・交差
本稿では交点のみでなく最小距離にも重点をおく。簡単のため
2 次元平面において、有理曲線と直線との距離の最小・最大値の検出法を説明する。距離が 0 のときが交点である。制御点
𝑃! (𝑥!, 𝑦! )をもつ n 次有理ベジェ曲線は前述の式(1)で表せる。
直線と点 P(x, y)の（符号付き）距離はf(x, y) = ax + by + cである。ただし、(a, b)は線分の単位法線ベクトル𝐧のｘ、ｙ成分である（a 2+b 2=1）。したがって、式(1)の P の x,y 座
標x(t), y(t)を式(2)の関数 f に代入すると、下記のように曲線との距離は有理ベジェ関数となる。
∑"" ( $ " (&))(&)

𝑓(t) = ∑"!#$ " !(&)! $!"(&)= *(&)!#$!

つのベジエ関数となる。ここで𝑓 + が 0 になるかは分子𝑑(𝑡)で判定できる。すなわち、極値（最短点あるいは最大となる点）は距離関数の微分（式(7)の分子で 2n-1 次の関数）が 0 の点として算出できる。
3次元空間の場合、平面と点との距離はF(x, y, z) =ax+by+cz+dとなるだけで、制御点の距離計算後は式(1),(2)は同じ計算手順となる。ここで、(a, b, c)は平面の単位法線ベクトルである。n次曲線の場合、微分した距離関数は非有理なら(n-1)
次、有理なら(2n-1)次のベジェ関数の解を求めることになる。この距離とは符号付き距離である。
曲線間の交差判定に、ファットライン（厚みのある曲線；曲線を包含する長方形）が提案されている[2]。曲線と円（球）の場合にも適用し、ファットラインからの距離が円の半径より長いなら交差しないことがわかる。この距離は前述のf(x, y)で計算でき,これは1次式で簡単に判定できる。ただ、ファットラインと円が重なる場合でも交差しないケースもあり、処理は複雑である。この場合、次節の判定を行う。

４. 円・球と曲線との交差判定（包含球テスト）
球（または円）と曲面（曲線）の交差判定は CAD や CG でよく利用されている。これは式(3)を利用すれば簡単に適用できる。円や球でも有理曲面の場合でも、2n 次の有理ベジエ関数であり、この関数が解をもつかで交差判定ができる。
中心（）および半径 R の円とｎ次有理ベジエ曲線（パラメータｔ）の場合、式(4)を修正した関数𝑒(𝑡, 𝑅) = D(𝑡)-𝑅, を利用する。

𝑒(𝑡, 𝑅) = D(𝑡)-𝑅! =((∑$"%& 𝑤" (𝑥" − 𝑥# )𝐵"$ (𝑡))! +(∑$"%& 𝑤" (𝑦" −$𝑦# )𝐵" (𝑡))! -𝑅! (∑$"%& 𝑤# 𝐵"$ (𝑡))! )/(∑$"%& 𝑤# 𝐵"$ (𝑡))!
(8)
整理すると,",𝑒(𝑡, 𝑅) = ∑,"(9)!01 𝑑! 𝐵! (𝑡)⁄𝑔 (𝑡)ただし、𝑑! = 𝑎! − 𝑏! 𝑅は関数 e の制御点（2n+1 個）で半径の関数。 𝑒(𝑡, 𝑅) > 0は交差(分子の制御点の符号で判定)しない条件である。この関数は一般に下に凸の関数（概形は下に凸の放物線状）で、この関数は制御多角形の凸包内部に存在する。
この関数の制御点が負でないなら、必ず交差しない。こうした制御点の符号のみの簡易テストが利用できる。分子が 0 になる t を計算する。この関数は 2n 次のベジエ関数なので、次のようにBezier Clipping 法で求まる。この関数の制御多角形の凸包で解の存在区間が分かる。この区間は制御多角形と軸との交点で求まる。解の存在区間の最小最大値でこの関数（曲線）をクリップする。交点は一般に複数点または 0 である。解の収束が少ない
場合この曲線を 2 分割すると、それぞれの曲線が軸と交点に収(6)!

なお、𝑓! = 𝑎𝑥! + 𝑏𝑥! + 𝑐である。次に𝑓(t)を微分する.

𝑓 + (𝑡) =)& (-)-)% (-)*% (&)=)+(&)*(&),*+(&))(&)*% (&)=2𝑛−1∑2𝑛−1(𝑡)𝑘=0 𝑔𝑘 𝐵𝑘

𝑔2 (𝑡)$%!
ただし、𝑑!(t) = n ∑"&'(𝑤"＋１ 𝑓"#! − 𝑤" 𝑓" )𝐵"$ (𝑡) ∑$"&' 𝑤" 𝐵"$ (𝑡)

(7)

𝑄!
t=0

"""
𝑑, (t) = n ∑"/.
!01 (𝑤!-. − 𝑤! )𝐵! (𝑡) ∑!01 𝑤! 𝑓! 𝐵! (𝑡)𝑄(𝑄)

図１ 円と曲線の交差判定関数である。両者とも 2 つのベジエ関数の積で、乗算後𝑑. , 𝑑, ともに

206

t=1

芸術科学会論文誌 Vol. 20, No. 4, pp. 204-209 (2021)
束し、複数の交差パラメータが算出できる。手順を整理すると、①関数 e の制御点に負がないなら交差しない。②円が交差する曲線の範囲（関数 e の制御多角形が軸と交差する区間）でクリップされ、短い曲線を得る。③曲線を 2 分し各区間において収束計算で交点を得る。図 1 に円と有理曲線の交差判定を示す。図の左上の位置関係の際の 6 次関数を示す。関数(曲線)（青曲線）の制御多角形（図中赤線）とｔ軸の交差区間を求めると、必ず解はその区間の曲線上にあるので、 関数をクリップし、 図中のＰ１Ｐ２間の曲線が得られる。円との交差なので解は 2 つあるとうこともあり、このクリップされた関数を 2 分割し、区間Ｐ１Ｐ３を得る。
この曲線はほぼ直線なので、この制御多角形のｔ軸との交差区間（微小幅）で再分割すると解（図中ｔ軸上の×）に収束する。同様にＰ３Ｐ２間の解も収束計算で求まる。円が交差しない場合には、最短点を求める。これは式(8)を微分した関数が 0 になる点を求める。提案法は楕円にも簡単に求まる。楕円は各軸の長さが異なるが、この比率を重み係数（式(8)の𝑤" (𝑦" − 𝑦# )の項）に乗じるのみで、同じ関数が楕円に利用できる。球や楕円体と空間曲線の場合は、式（8）でｘ、ｙ成分に加えてｚ成分𝑤" (𝑧" − 𝑧# )を含めば良い。曲面の場合、2 つのパラメータで下記のように定義される。

𝑃(𝑢, 𝑣) =∑"(#$""∑"*#$ "(,* #(,* $( (/)$* (0)""""∑(#$ ∑*#$ "(,* $( (/)$* (0)(10)

また式(8)は下記となる。
,",",",,𝑒(𝑢, 𝑣, 𝑅) = ∑,"201 ∑301 𝑑2,3 𝐵2 (𝑢) 𝐵3 (𝑣)⁄𝑔 (𝑢)𝑔 (𝑣) (11)交差しない場合、最短点が必要な際は球の中心𝑄と曲面の等パラメータ曲線の接線を利用し、下記を解く。
45(7,8)· (𝑃(𝑢, 𝑣) − 𝑄) = 0(12)· (𝑃(𝑢, 𝑣) − 𝑄) = 0

(13)

47
4:(7,8)48

式(12)で𝑢の範囲を抽出し、曲面の𝑢成分をクリップし、分割後の曲面に対して式(13)を用いて𝑣の範囲を抽出し曲面の𝑣成分を分割する。この操作を微小平面になるまで繰り返す。曲面と球との交点が必要な際は、曲面の幾つかの等パラメータ曲線との交点列を計算する。
次に球（円）自身の交差判定でなく、包含球としての利用を説明する。曲面が多角形メッシュを用いて表現されることが多い。
その場合、多角形同士の干渉テストが必要となる。一つの曲面が NxN 枚の三角形で表現されていると、同様な分解能の多角形メッシュとは N8 回もの干渉テストが必要になる。できるだけ一方の曲面は多角形近似せず、制御点（ｎ次曲面なら(n+1)x(n+1)点）のみを利用した判定が効率がよい。多角形（三角形）の包含球の交差判定を考える。これは式(8),(10)の制御点の符号で判定できる。あくまで包含球テストなので、包含球と曲面・曲線との交点計算までは必要なく、交差の有無のみの判定で充分である。
包含テストで交差の可能性が分かるが、この際曲線あるいは曲面は球と重なる領域に分割されている。この小さくなった曲線と多角形の各辺との交差判定を行う。これらの辺は線分な
図 2 ボール内の密度分布
ので式(2)の関数で交点（距離に関し 6 次ベジエ関数）（距離が 0 の点）が計算できる。

5. メタボールと曲線の干渉
メタボールはいくつかの密度球の集合で構成され、合成された密度がある閾値となる面(等値面)で表現される。各球の密度は中心座標と中心からの距離 r で定義される。本稿では距離ｒに関し 6 次のベジエ関数[6]で表現するものを採用した（r の 2 乗に関しては３次のベジエ関数）。以下 2次元の場合で説明する。N 個のボールで、各ボール中心の密度 qi (本稿では 1), 閾値 T(一般に T＝0.5)とすると、ボール表面は下記の陰関数で表現される。
f(x, y) = ∑((14)'%& 𝑞' 𝑓' (r) − T=0
有効半径 R とすると、密度は R 内のみで定義される。また、𝑟 # =(𝑟/𝑅), に関して密度は下記の 3 次ベジエ関数である。中心（𝑥2 , 𝑦2 ）のボールに対して点Ｐ(x,y)での密度𝑓(𝑥, 𝑦)は、点 P とボール中心との距離の 2 乗比𝑟 # を用いて定義される。
𝑟 ) = (r/R)! = ((x − x' )! + (y − y' )! )⁄𝑅!
(15)
f' (𝑟 ) ) = ∑*"%& 𝑑" 𝐵"* (𝑟 ) )(16)!
<
ここで制御点kでの座標は(; , 𝑑! ) , 𝑑! = Q1, ,= , 0,0Sである。ボールが１つなら、𝑟 # ＝0.25すなわちｒ＝0.5Rが解になる。すなわ
ち、0.5Rの円と曲線の交点として求まる。これは、前節の曲面と円との交差関数が利用できる。曲線上（ｎ次ベジエ関数）のパラメータtで𝑟 # は決まり（2n次ベジエ関数、𝑟 # で密度（3次ベジエ関数）が決まる。曲線上のボールが一つの領域は円となり簡単である。2つのボールを考えると、まず一つのボールに切り取られる曲線Pの区間を抽出し、次にもう一つの円で曲線をクリップする（図４中のP2,P3の区間）。２つのボールと曲線の交差区間内での解を求めるが、2つのボールの交差区間は短いので直線近似できる。フラット（直線近似）でないなら細分割する。直線と円が交差する場合、交差区間のパラメータsとすると（s = 0, s = 1で交差：図中のP1P3）
f' (𝑠) = ∑+"%& 𝑑" 𝐵"+ (𝑠)(17)
ここで𝑑! = {0,0,16a, /27, (8𝑎 + 5) a, /45, 16a, /27, 0,0}, な
お D は 直 線 と 円 の 交 差 判 別 式 で 、 交 差 区 間 長 は 2 √𝐷で、a=D/R2 である。円内のどのような線分も円をよぎる直線の一部であり、密度は6次関数である。すなわち、この式(17)の関数を交差区間でクリップした6次関数である。すなわち、tの2n次関数で解ける。曲線とボール１の交点とボール2の交点を抽出し、それらの交差区間の両点の間の曲線を、直等値面

図 3 複数メタボールと曲線の交差区間 P2P3207

芸術科学会論文誌 Vol. 20, No. 4, pp. 204-209 (2021)
有理曲面と曲面との最短距離、三角形メッシュ（120 個の三角形メッシュで構成される半球状曲面）と曲面の交差を示す。図 7 は、球と有理曲面・曲線の交差・最短距離である。図８は、メタボー
ルと有理曲面との交差・最短距離である。左図のメタボールはレイトーシングで表示している。右 2 列の図ではマーチンキューブ法を用いて多角形化しているが、曲面との交点は多角形としてではなく陰関数表現のまま等パラメータ曲線の交点列として検出した。図９は、球と曲面の衝突アニメーションの例である。球の軌跡がドット列で表示される。球の発射角、速度、高さがインタラクティブに指定でき、これらの図は発射角度と初速度を変えた例である。

𝑃,
𝑃;
𝑃,
𝑃.

図 4 ボール重なり区間の密度分布線近似して直線上の密度分布を得る。普通は中央が凸になる分布で解は2つあるので、2分割して直線近似すると、各々の区間に解が求まる。図3は、ボールが重なっている区間の直線上の密度の計算をする。ボール１の直線状の分布を重なり区間（図中区間B）でクリップし、同様にボール2の密度分布も重なり区間でクリップし、両者を加算する。

図 7 球と有理曲面・曲線の交差・最短距離

図5点と５次有理曲線の最短点、円（楕円）と３次有理曲線の交差、メタボールと３次有理曲線との交差・最近点

図 8 メタボールと有理曲面との交差・最短距離
図 6 三角形の包含球と曲面の交差、4 つの 2 次有理曲面と曲面との最短距離、3 角形メッシュと曲面の交差

6. 計算例
基本的には携帯端末など種々のプラットホームで動作できるように、JavaScript で開発した（近年は WEB 上で動作する CADシステムも注目されている）。WEB 上のブラウザー上で動作でき、マウスを用いて、有理曲線.曲面の制御点列、それらの重み係数と円の中心を指定するインタラクティブなシステムとした。
図 5-９に提案法の計算結果を示す．図 5 は左上から、点と５次有理曲線の最短点、円（楕円）と３次有理曲線の交差、メタボールと３次有理曲線との交差・最近点である。左上の図の下部のように制御点の重みをインタラクティブに変更できる。ここで、最短点の計算の際は 3 分割で収束、円との交差は 1 交点当たり 4 分割程度であった。図 6 は、三角形の包含球（緑点を端点とする有理曲線上を包含球は移動）と曲面の交差、4 つの 2 次208

図 9 落下球と曲面との衝突判定（黒点は軌跡；発射角度と初速度による差）

芸術科学会論文誌 Vol. 20, No. 4, pp. 204-209 (2021)
7. まとめ
本稿では、有理ベジェ曲面・曲線と球・円の交差およびギャップ（最短距離）を計算する関数を提案し、この関数がベジエ関数であることを利用し、Bezier Clipping 法を用い、線形計算のみで計算できる方法について提案した。
n 次ベジェ曲面（あるいは曲線）と円の干渉について整理すると、判定関数の次数は n 次曲線なら、2n 次、2n-1 次のベジエ関数である。またメタボールの密度分関数がベジエ関数で表現できるものを採用した。これによりすべての判定関数はベジエ関数で表現される。したがって、各種の判定に統合的に Bezier Clipping 法が適用できる。曲面の場合や複数曲線間の処理の場合、変数が複数となり、かつ高次多項式の連立方程式を解くようであるが、幾何学的性質を用いた線形計算のみで実現できる特徴がある。分割処理を多用するが、有理曲線の分割も線形計算のみでできる。
従来法の多くの最短距離計算には曲線・曲面を再帰的に２分割する、2分探索法が用いられており、複数解を得るには相当の分割数が必要とされるが、提案法は1桁の程度の分割数で解が得られる効率的な方法である。
計算例のように、この提案法は形状設計のCADにおいて物体間の干渉や間隙（ギャップあるいはクリアランス）の検出や、ゲームなどの衝突判定に有効である。

2008-4[11] T. Nishita, K. Kaneda, E. Nakamae, “A Scanline
Algorithm for Displaying Trimmed Surfaces byusing Bezier Clipping,” The Visual Computer,
Vol.7, No.5, pp.269-279, 1991-9.
[12] 西田，松田，高栄，「曲線上の最短点検出を利用した自由形状変形法」，画像電子学会誌，Vol.27，
No.4，pp.287-297.
[13] 西田,出本,「曲面と多角形との最短距離検出法」
Visual Computing / グラフィクスと CAD 合同シンポジウム,１１，2017-6.
[14] 西田,「分割法を用いた有理ベジエ曲線・曲面の間隙計算」Visual Computing / グラフィクスと CAD 合同シンポジウム,36，2021-10.
[15] J.F. Blinn. “ A generalization of algebraic
surface drawing.”ACM Trans.Graphics,1(3):235256, 1982.
[16] H. Nishimura, M. Hirai, T. Kawai, I. Shirakawa,and K. Omura. “Object modeling by distributionfunction and a method of image generation.”
Journal of papers given by at the Electronics
Communication Conference, J68-D(4):718-275, 1985.

西田

友是

参考文献
[1] T. Nishita, T. Sederberg, M. Kakimoto, "Ray
Tracing Trimmed Rational Surface Patches,"Computer Graphics, Vol.24, No.4, pp.337-345,
1990-8.
[2] T. Sederberg, T. Nishita, "Curve Intersection
using Bezier Clipping," CAD, Vol.22, No.9,pp.337-345, 1990-11.
[3] Y- T. Oha, Y-J Kim, J. Leeb, M-S. Kim, G. Elber, ”
Efficient point-projection to freeform curves andsurfaces,” GACD, 192-205、2010[4] X.Chen, et al.” Computing the minimum distance
between two Bézier curves”、 J. of Computationaland Applied Mathematics 229, 294-301,2009[5] J-W,Chang,et “Computation of the minimum
fdistance between two Bezier curves/surface,”
Computers & Graphics,Vol. 35, Issue 3, pp.677684, 2011[6] T. Nishita, E. Nakamae, "A Method for Displaying
Metaballs by using Bezier Clipping," ComputerGraphics Forum, Vol.13, No.3, pp.271-280, 19949.
[7] T. Nishita, S. Takita, E. Nakamae, “Hidden Curve
Elimination of Trimmed Surfaces Using Bezier
Clipping,” Computer Graphics International 92,pp.595-619, 1992-6.
[8] T. Nishita, K. Kaneda, E. Nakamae, “High-Quality
Rendering of Parametric Surfaces by Using aRobust Scanline Algorithm,” Computer Graphics
International 90, pp.493-506, 1990-6.
[9] T. Nishita, K. Kaneda, E. Nakamae, “A Scanline
Algorithm for Displaying Trimmed Surfaces byusing Bezier Clipping,” The Visual Computer,
Vol.7, No.5, pp.269-279, 1991-9.
[10] Y. Kanamori, Z. Szego,T. Nishita, "GPU-based
Fast Ray Casting for a Large Number ofMetaballs," Computer Graphics Forum (Proc.
EUROGRAPHICS 2008), Vol.27, ISSUE 2, pp.351-360,

209

1971年, 広島大学工学部卒業.1973年,同大学大学院工学研究科修了, 同年, マツダ (株) に入社.1979年, 福山大学工学部講師,1984 年同助教授,1990年同教授.1998年, 東京大学理学部教授. 1999年同大学大学院新領域創成科学研究科教授,2013年より広島修道大学教授、2020年よりデジタルハリウッド大学卓越教授、2013年よりプロメテックCGリサーチ（当初UEIリサーチ）所長、現在に至る. 2005年，ACM
SIGGRAPH より Steven A.Coons 賞を，2008年紫綬褒章．
2020年船井業績賞受賞、2021年画像電子学会よりアレクサーベイン賞を受賞。コンピュータグラフィックスの研究に従事.学会誌 IEEE TVCG, TheVisualComputer のエディター
を歴任. 工学博士. 情報処理学会, 電子情報通信学会, 画像電子学会、ACM,IEEE各会員．