(57)【要約】【課題】  物体形状モデルに対する内外判定値の場の計算を高速に行う内外判定方法、及びそのプログラムを提供する。【解決手段】  本発明は、CSG( Constructive Solid Geometry )形式で記述された物体形状データを入力する入力工程と、格子を任意の軸に平行な直線の集合で表現する直線集合の作成工程と、直線とCSGモデルとの内外判定値の区間をRay  Castingによって作成する区間作成工程と、求められた各直線上の内外判定値の区間から直線上のノードの内外判定値を求めることにより内外判定値の場を作成する工程からなることを特徴とする内外判定方法。【選択図】  図２
2007102629.tif 000002
【特許請求の範囲】
【請求項１】
CSG( Constructive Solid Geometry )形式で記述された物体形状データを入力する形状入力工程と、格子を任意の軸に平行な直線の集合で表現する直線集合の作成工程と、直線とCSGモデルとの内外判定値の区間をRay Castingによって作成する区間作成工程と、求められた各直線上の内外判定値の区間から直線上のノードの内外判定値を求めることにより内外判定値の場を作成する工程からなることを特徴とする内外判定方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、界面などの境界や物体形状を扱う数値解析やCG( Computer Graphics )で使用される3次元形状モデルとの内外判定に関する。
【背景技術】
【０００２】
近年、流体解析などの界面を扱う数値解析手法では、計算機の急速な進歩に伴い、古くから知られていた直交格子法が大規模計算に適した手法として再注目されている。
【０００３】
直交格子はその性質上、格子の自由度の大きい非構造格子に比べ形状の扱いが困難であって、直交格子による物体形状を扱う数値シミュレーションを行うためには、何らかの手段によりこれを克服しなければならない。例えば非特許文献1に開示されているカットセル法では、格子と形状表面との交点を元に、形状表面の離散化を行う。この時、形状表面は2次元であれば格子上の交点を結んだ区分線形で表現され、3次元であれば同様に格子状の交点からなる3角形の集合として表現され、物体は次のようなラベルをつけられたセル（格子によって仕切られた空間。2次元であれば正方形、3次元であれば直方体）によって格子上に表現される。
【０００４】
・内部セル  （物体の内部のみを表すセル）
・カットセル（物体表面がセルを切断し、物体の内側、外側が同居するセル）
・外部セル  （物体の外部のみを表すセル）
また非特許文献2に開示されているレベルセット法によると、物体形状は直交格子上の符号付距離の場として表現される。
【０００５】
このような直交格子上へ物体形状を埋め込む技術は、近年の3D-CADの普及による複雑かつ精密なモデルを解析対象とする産業上の機会、要求の増加に伴い、より高速な手法が望まれている。
【０００６】
直交格子上で物体形状を表現するための最も単純な方法の一つであって、かつ先に述べたいずれの手法においても基礎となる方法は、全ての格子点に対し物体形状との位置関係を調べ、予め定めた位置関係を表す値（以降、内外判定値と呼ぶ）によって判定結果を表現し、格子上に内外判定値の場を作成することである。
2007102629.tif 000003
【０００７】
2次半空間による物体形状表現は、複雑な形状を複数の2次半空間の集合演算を用いて表現する。図1に2次元空間上での半空間の集合演算による形状表現の例を示す。図1では陰関数f1( p )によって定義される半空間の組S1 = ｛φ1, γ1 ｝ と、f2( p )によって定義される半空間の組S2 = ｛φ2, γ2 ｝ と、f3( p )によって定義される半空間の組S3 = ｛φ3, γ3 ｝ の集合演算 S1 ∩ S2 ∩ S3 により3角形が作成されている。ここで半空間の組Si間の積集合演算∩はSi∩Sj = ｛ φi∩φj ，γi∪γj ｝，和集合演算∪はSi∪Sj = ｛ φi∪φj ，γi∩γj ｝ を行うものとする。 3角形の両半空間の組をS4 = S1∩S2∩S3 = ｛φ4，γ4｝とすればφ4，γ4はそれぞれ3角形の内部、外部を表す領域
2007102629.tif 000004
γ4 = ｛ p | f1( p )  > 0 または f2( p ) > 0 または f3( p ) > 0 ｝
である。従って任意の座標pと該3角形との内外判定は、個々の半空間での2値の内外判定値と、2値の論理演算により行う事ができる。また平面から構成される多角形と任意の点との内外判定は、非特許文献3に開示されている凸多角形法、交点計算法、角度総和法、三角形法等により行う事もできる。
【０００８】
2次半空間もしくは2次半空間によって構成される物体を、物体形状を構成する際の原始立体(プリミティブ)とし、該プリミティブの集合演算によって物体形状をモデリングする手法はCSG( Constructive Solid Geometry )として知られ、CG( Computer Graphics )、3D-CAD( 3-Dimensional Computer Aided Design )等で広く使用されるモデリング手法である。以下ではCSGに基づいて記述された物体モデルをCSGモデルと呼称する。
【０００９】
次に2次半空間をプリミティブとして持つCSGモデルと解析空間との内外判定値の場を求める方法について述べる。
【００１０】
内外判定値の場を直交格子の結節点（ノード）上に定義する場合、各ノードをpiとし、N個からなるノード全体の集合をP = ｛ p1, … ，pN ｝とし、CSGモデルの内部領域をΦとし、内側を表す内外判定値を1とし、外側を表す内外判定値を0とし、上記の内外判定法により各ノードの内外判定値を返す内外判定関数g( p )を次のように定義する。
【００１１】
【数１】
2007102629.tif 000005
【００１２】
内外判定値の場は、ノード集合Pに含まれる全てのノードpに対する（式1）の内外判定から求める事ができる。
【非特許文献１】J.J. Quirk，An alternative to unstructured grids for computing gas dynamic flows around arbitrarily complex two-dimensional bodies，Comput. Fluids， 23(1)，pp.125142，1994.
【非特許文献２】J.A. Sethian，Fast Marching Methods，SIAM Review, 41，2，pp.199-235，1999.
【非特許文献３】日本図学会，CGハンドブック―Computer graphics，森北出版，1989．
【非特許文献４】Scott  D. Roth，Ray Casting for  MODELING  Solids，COMPUTER  GRAPHICS  AND  PROCESSING，Vo. 18，pp．109−114，1982.
【発明の開示】
【発明が解決しようとする課題】
【００１３】
先に述べた（式1）による内外判定法は、計算が容易であるという利点がある。しかしながら格子上の全てのノードに対し内外判定を行い内外判定値の場を求める際の計算オーダーは、格子の一軸あたりの分割数をnとし、次元数をdとし、総ノード数ndに比例するO(nd)である。このため（式1）による内外判定法は膨大な数のノードを扱う大規模シミュレーションには適した方法ではなく、高速な内外判定方法が課題となる。
【課題を解決するための手段】
【００１４】
本発明は、CSG( Constructive Solid Geometry )形式で記述された物体形状データを入力する形状入力工程と、格子を任意の軸に平行な直線の集合で表現する直線集合の作成工程と、直線とCSGモデルとの内外判定値の区間を前述の非特許文献4に開示されるRay Castingを用いて作成する区間作成工程と、求められた各直線上の内外判定値の区間から直線上のノードの内外判定値を求めることにより内外判定値の場を作成する工程を設ける。
【発明の効果】
【００１５】
本発明による結果、CSGモデルに対する内外判定値の場の計算について、O(ｎd-1)の高速な計算を可能にする。
【発明を実施するための最良の形態】
【００１６】
本発明の実施例の構成図を図2に示す。図2中、201はCPU、202は表示装置、203は入力装置、204は1次記憶装置、205は2次記憶装置、206は通信装置、207はバスラインである。本発明における工程は、プログラムとして予め2次記憶装置205に格納されており、入力装置203、或いは通信装置206等からのコマンド入力によって、1次記憶装置にロードされ、実行されるものである。
【００１７】
図3は、本発明によって実施される処理の流れである。
【００１８】
301は形状入力工程である。301では物体形状データを入力し、入力したCSGモデルΩを計算機上にCSG木として表現する。CSG木とは、木の各ノードに集合演算子を持ち、各リーフにはプリミティブを持つ2分木である．図4に4つのプリミティブφ1，φ2，φ3，φ4による集合演算φ1∩φ2∪φ3∪φ4によりCSGモデルが記述される場合のCSG木の例を示す。
【００１９】
プリミティブφiは2次半空間
2007102629.tif 000006
である。ここでpは実数の座標p = ｛ ( x，y，ｚ)，p  Ｒ3｝であり、q( p )は係数パラメータa, b, c, d, e, f, g, h及び定数iを用いた次式の2次関数である。
【００２０】
（式3）  q( x, y, z ) =
a x2 + b y2 + c z2 + d xy + e xz + d yz + f x + g y + h z + i
該プリミティブφiは（式3）の係数パラメータの値によって入力データ中に記述される。CSGモデルΩは該記述形式により定義されたk個の半空間の集合Φ＝｛φ1,…,φk ｝による集合演算式Ω = φ1∩φ2∪φ3−φ4 ・・・ φkとして入力データ内に記述される。
【００２１】
302は格子を表現する任意の一つの軸に平行な直線liの集合L = ｛ l1, l2, …, lN ｝ を作成する直線集合の作成工程である。ここでNは直線の個数を表し、例えば各軸をn等分する等間隔格子の場合、2次元ではN = n，3次元ではN = n2となる。
【００２２】
該工程では、あらかじめ格子を規定する情報が与えられる。例えば直交格子の場合、x軸方向の格子の最大値xmax、最小値xmin、分割数nx、y軸方向の格子の最大値ymax、最小値ymin、分割数ny、z軸方向の格子の最大値zmax、最小値zmin、分割数nzである。該規定情報は301により入力されてもよいし、あらかじめ定めていてもよい。該規定情報により直線liを次のように定義する。例えば解析空間が2次元である場合に、任意の軸としてx軸を選択する場合の直線liは
【００２３】
【数２】
2007102629.tif 000007
である。ただしtは任意の実数、Δy = ( ymax - ymin ) / yn,  i = 0, …, nyである。解析空間が3次元である場合に，任意の軸としてｚ軸を選択する場合の直線lijは
【００２４】
【数３】
2007102629.tif 000008
である。ただしΔx = ( xmax  xmin ) / nx，j = 0, …, nxである。図5にそれぞれ2次元、3次元の格子から作成される直線集合Lの例を示す。
【００２５】
303は302で作成された直線liと301により入力されたCSGモデルとのRay  Castingを行い区間を作成する工程である。
【００２６】
まず直線liとプリミティブφiとのRay Castingについて述べる。直線liとプリミティブφiとの Ray Castingは、プリミティブとliとの交点から、直線liがプリミティブ内部を通過する区間、通過しない区間を作成する。以降ではliがプリミティブを通過する区間を内側区間T、通過しない区間を外側区間Fと呼ぶ。また求められた区間は、例えば次のような情報を有する構造体またはオブジェクトとして、プログラム上で表現される。
【００２７】
区間の下限値lower
区間の上限値upper
下限値での閉開情報
上限値での閉開情報
ポインタ
内側、外側のそれぞれの区間が複数存在する場合には、ポインタに次の区間を指すアドレスを代入する。図6に直線liとプリミティブφiとの内側、外側区間の例を示す。図6ではa, bが直線とプリミティブとの交点を示し、該交点a, bにより作成されたそれぞれの区間［x min,a］,[a,b],[b,x max]を表す構造体(オブジェクト)F1,T1,F2を示している。また、図6では外側区間が2つ(F1とF2)存在しているため、F1のポインタにはF2を指すアドレスが代入される。また、以降では内側、外側の区間をまとめて内外区間と呼ぶ。
【００２８】
次に内外区間に対する集合演算について述べる。例えば上記の内外区間の作成方法によってプリミティブφ1と直線l1との内外区間A、プリミティブφ2と直線l1との内外区間Bが作成される。内外区間A, Bの集合演算は、例えば区間の交差などを利用して行う。図7に2つの内外区間A, Bの積集合演算∩、和集合演算∪、差集合演算−による演算結果の例を示す。
【００２９】
直線集合LとCSG木表現されたCSGモデルとの内外区間は、次の再帰的な手順で作成される。
【００３０】
１．ルートノードを選択する。
【００３１】
２．ノードは左右の子ノードを呼び出す。
【００３２】
３．呼び出された子ノードがリーフであれば、直線集合Lの全ての直線と該リーフ上のプリミティブとの内外区間を計算し、親ノードへ返す。
【００３３】
４．呼び出された子ノードがリーフでなければ2を繰り返す。
【００３４】
５．左右の子ノードから返ってきた内外区間について、該ノード上の集合演算子による集合演算を行う。
【００３５】
６．現在のノードがルートノードであれば終了し、それ以外であれば親ノードへ5で求めた内外区間を返す。
【００３６】
304は内外判定値の場の計算工程である。303の工程により、直線集合Lに対応した内外区間群が得られる。工程304では、該内外区間群から、直線li上のノードpの内外判定値を求める。例えば直線li上のノードpが内側区間に含まれていれば内外判定値1を与え、外側区間に含まれていれば内外判定値0を与えることにより計算する。直線li上のノードpの内外判定値の計算をLの全ての直線liについて行い、内外判定値の場を得る。
【００３７】
本発明による実施例を示す。入力には、図8にCG画像として示したCSG形式に基づく物体形状データを使用する。図9に（式1）と、本発明による内外判定値の場の計算時間のグラフをそれぞれ示す。図9では、横軸が一軸あたりの格子の分割数、縦軸が計算時間であり、両軸ともに常用対数のスケールである。また計算にはC＋＋言語，Celeron 1.40GHz, 256MbyteのLinux PCを使用した。図9より、（式1）による計算オーダーがほぼO(nｄ) 、本発明による計算オーダーがほぼO(nd-1)であることが分かる。また、図10に本発明によって計算された。ノード数を1003として計算した時の内外判定値の場の等値面（ 等値 = 1 ）を示す。
【００３８】
（産業上の利用可能性）
本発明は、CG( Computer Graphics )や数値解析で使用される物体形状モデルとの内外判定に有効な方法である。
【図面の簡単な説明】
【００３９】
【図１】CSGモデルの例である。
【図２】本発明の実施例の構成図である。
【図３】本発明の処理の流れ図である。
【図４】CSG木の例である。
【図５】格子から作成される直線集合の例である。
【図６】Ray Castingによる区間作成の例である。
【図７】区間の集合演算の例である。
【図８】実施例に使用したCSGモデルである。
【図９】本発明の計算速度を示すグラフである。
【図１０】本発明により計算した内外判定値の場の等値面である。
【図１】
2007102629.tif 000009
【図２】
2007102629.tif 000010
【図３】
2007102629.tif 000011
【図４】
2007102629.tif 000012
【図５】
2007102629.tif 000013
【図６】
2007102629.tif 000014
【図７】
2007102629.tif 000015
【図８】
2007102629.tif 000016
【図９】
2007102629.tif 000017
【図１０】
2007102629.tif 000018