(57)【特許請求の範囲】
【請求項１】
コンピュータを、
三次元曲線モデルを、相互に異なる方向を向いた複数の仮想平面に夫々投影する投影手段，
前記各仮想平面において、投影された曲線に含まれる自己交差を夫々検出する平面上自己交差検出手段，及び、
前記平面上自己交差検出手段により、全ての仮想平面に投影された曲線に含まれる自己交差が検出された場合であって、且つ、前記各仮想平面において自己交差が検出された位置が同じ場合には、前記三次元曲線モデルに自己交差があると判定する判定手段
として機能させる三次元曲線モデルにおける自己交差の検出プログラム。
【請求項２】
前記投影手段は、前記三次元モデルを、複数の点列によって区切られた複数の直線状の線分からなる折れ線として、前記複数の仮想平面に夫々投影し、
前記平面上自己交差検出手段は、各仮想平面において、投影された折れ線上の点列を順に辿ったならば各仮想平面に設定された二つの座標軸上の値の変化が同じ区間において夫々単調とならない場合に、投影された曲線に自己交差が検出できたとする
ことを特徴とする請求項１記載の三次元曲線モデルにおける自己交差の検出プログラム。
【請求項３】
前記平面上自己交差検出手段は、各仮想平面において、投影された折れ線上の点列を順に辿ったならば各仮想平面に設定された二つの座標軸上の値の変化が同じ区間において夫々単調とならない場合であり、且つ、何れか一方の座標軸上において、値の変化が単調でない区間の両外側に近接して値を有する二点を選択し、前記折れ線における前記選択された二点間に存する各線分間の交点を求め、何れか２つの線分間に交点が算出できた場合にのみ、投影された曲線に自己交差が検出できたとする
ことを特徴とする請求項２記載の三次元曲線モデルにおける自己交差の検出プログラム。
【請求項４】
前記平面上自己交差検出手段は、更に、交点が算出できた二つの線分を特定し、
前記判定手段は、前記平面上自己交差検出手段により、全ての仮想平面に投影された曲線に含まれる自己交差が検出された場合であり、且つ、前記平面上自己交差検出手段により各仮想平面について特定された前記交点が算出できた二つの線分が一致する場合にのみ
、前記三次元曲線モデルに自己交差があると判定する
ことを特徴とする請求項３記載の三次元曲線モデルにおける自己交差の検出プログラム。
【請求項５】
コンピュータにより、三次元曲線モデルを、相互に異なる方向を向いた複数の仮想平面に夫々投影し、
前記各仮想平面において、投影された曲線に含まれる自己交差を夫々検出し、
全ての仮想平面に投影された曲線に含まれる自己交差が検出された場合であって、且つ、前記各仮想平面において自己交差が検出された位置が同じ場合には、前記三次元曲線モデルに自己交差があると判定する
ことを特徴とする三次元曲線モデルにおける自己交差の検出方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、三次元曲線モデルにおける自己交差の検出プログラム及び自己交差の検出方法に関する。
【背景技術】
【０００２】
機械製品や装置に組み込まれているワイヤ、ハーネス、ケーブル等の線状柔軟物を設計する際には、線状柔軟物に繋がれている機械部品の動作を当該線状柔軟物が阻害したり他の部品に干渉せぬ様、線状柔軟物の適性な長さ及び配線経路を決定する必要がある。そのため、三次元的な曲線をモデリングするソフトウェアを三次元ＣＡＤシステム上で動作させることにより、仮想空間内に線状柔軟物の三次元曲線モデルを作成し、当該仮想空間において線状柔軟物の動きをシミュレーションする方法が、従来提案されている。
【０００３】
上述したソフトウェアは、設計対象である線状柔軟物の始点と終点の位置及び接続方向，線状柔軟物の長さ、線状柔軟物の断面の半径，等の条件が入力されると、これらの各条件を満たすとともに力学法則をも満足する三次元曲線を自動生成する。
【０００４】
ただし、上述したソフトウェアは、入力された条件が不適切ないし不自然であると、現実にはありえない自己交差を含む形状を呈する三次元曲線モデルを生成してしまうことがある。ここに、自己交差とは、同一曲線の或る一部と他の一部とが空間中の同一座標にて交差することをいう。即ち、線状柔軟物は、パラメータ如何に拘わらず、現実的には螺旋状にループした形状しかとりえないにも関わらず、上述したソフトウェアは、自己交差に因る閉ループを含む形状を作成してしまう場合がある。後者の形状を有する三次元曲線モデルは、現実には存在しな形状を呈するものであるので、線状柔軟物の動きをシミュレーションする目的の為には不適当である。そこで、生成された三次元曲線中の自己交差を高速に検出することが、求められる。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】国際公開2004/825522号
【特許文献２】特開平9-292873号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
三次元曲線中の自己交差を検出するためには、三次元曲線を、複数（Ｎ＋１個）の点列と各点同士の間を夫々結ぶＮ本の線分とからなる折れ線に近似し、全線分から選ばれる二本の線分の全組合せに対して、交点（即ち、共通座標）の有無を調べることが考えられる。この場合、座標系において２本の線分を夫々示す連立方程式が解を有せば、交点が存在すると判定される。
【０００７】
しかしながら、かかる方法による場合、各線分の組み毎に交差の有無判定を行う計算（以下、「交差判定計算」という）の回数は、最大でＮ×Ｎ回となってしまう。
【０００８】
そこで、本案は、三次元曲線モデルにおける自己交差の検出のための計算量を削減することを課題とする。
【課題を解決するための手段】
【０００９】
提案された手段によると、三次元曲線モデルを、相互に異なる方向を向いた複数の仮想平面に夫々投影する。そして、各仮想平面において、投影された曲線に含まれる自己交差を夫々検出し、全ての仮想平面に投影された曲線に含まれる自己交差が検出された場合に、三次元曲線モデルに自己交差があると判定する。
【発明の効果】
【００１０】
三次元曲線モデルにおける自己交差の検出のための計算量を削減することができる。
【図面の簡単な説明】
【００１１】
【図１】コンピュータのハードウェア構成を示すブロック図
【図２】三次元曲線モデル生成プログラムを示すフローチャート
【図３】図２のＳ００３にて実行される曲線の自己交差検出処理サブルーチンを示すフローチャート
【図４】図３のＳ１０２にて実行される平面上曲線の自己交差検出処理サブルーチンを示すフローチャート
【図５】図３のＳ１０４にて実行される平面上曲線の自己交差検出処理サブルーチンを示すフローチャート
【図６】三次元曲線モデル例を示す図
【図７】折れ線に近似された三次元曲線を示す図
【図８】三次元曲線の２つの平面への投影を表す図
【図９】Ｘ軸方向における選択区間の意義を示すグラフ
【図１０】Ｙ軸方向における選択区間の意義を示すグラフ
【図１１】修正後の三次元曲線モデル例を示す図
【発明を実施するための形態】
【００１２】
以下、図面に基づいて、本案の実施の形態を説明する。
＜コンピュータ＞
図１は、三次元曲線モデル生成プログラムがインストールされているコンピュータ１のハードウェア構成図である。
【００１３】
図１に示すように、コンピュータ１は、相互にバスＢによって接続されたＣＰＵ１０，ＲＡＭ１１，入力装置１２，ディスプレイ１３及びハードディスク１５を有する一般的なコンピュータである。
【００１４】
ＣＰＵ１０は、ハードディスク１５からプログラムを読み出し、プログラムに従った処理を実行する処理装置である。
【００１５】
ＲＡＭ１１は、ＣＰＵ１０が上記処理をする際に作業領域を展開する主記憶装置である。
【００１６】
入力装置１２は、ＣＰＵ１０に対して各種コマンド又はデータを入力するためのキーボード及びポインティングデバイスである。
【００１７】
ディスプレイ１３は、ＣＰＵ１０による処理結果を表示するための表示装置である。
【００１８】
ハードディスク１５は、各種プログラム及び各種データを格納する固体記憶媒体である。このハードディスク１５が格納している各種プログラムには、三次元曲線モデルの自己交差検出プログラムを実施したモジュールである三次元曲線モデル生成プログラム１６を含む三次元ＣＡＤプログラムが、含まれている。
【００１９】
なお、三次元曲線モデル生成プログラム１６を格納する記録媒体は、ハードディスク１５に限定されず、コンピュータその他の機械、装置（以下、コンピュータ等）が読み取り可能な記録媒体を用いることができる。そして、コンピュータ等に、この記録媒体のプログラムを読み込ませて実行させることにより、その機能を提供させることができる。ここで、コンピュータ等が読み取り可能な記録媒体とは、データやプログラム等の情報を電気的、磁気的、光学的、機械的、または化学的作用によって蓄積し、コンピュータ等から読み取ることができる記録媒体をいう。このような記録媒体のうちコンピュータ等から取り外し可能なものとしては、例えばフレキシブルディスク、光磁気ディスク、ＣＤ−ＲＯＭ、ＣＤ−Ｒ／Ｗ、ＤＶＤ、ブルーレイディスク、ＤＡＴ、８ｍｍテープ、フラッシュメモリなどのメモリカード等がある。また、コンピュータ等に固定された記録媒体としてハードディスクやＲＯＭ（リードオンリーメモリ）等がある。
＜三次元曲線モデル生成プログラム＞
図２のフローチャートは、三次元ＣＡＤプログラムによる処理のうち、三次元曲線モデル生成プログラム１６による処理を示す。なお、図２〜図５に示すフローチャートは、線状柔軟物の一例であるハーネスの三次元モデルを生成するものとして記述されているが、当該プログラム１６により他の線状柔軟物の三次元モデルを生成できることは、勿論である。
【００２０】
図２に示す処理は、ＣＡＤプログラムを実行しているＣＰＵ１０に対して、オペレータが入力装置１２を通じて所定のコマンドを入力することにより、スタートする。
【００２１】
スタート後最初のＳ００１では、ＣＰＵ１０は、ハーネス形状に関する条件を入力する。図２においては、ハーネス形状に関する条件として、ハーネスの始点及び終点の位置，始点及び終点におけるハーネスの接続方向，ハーネスの長さ、ハーネスの断面の半径が例示されているが、更に、ハーネスの剛性，単位体積当たりの重量等が入力されても良い。ハーネス形状に関する条件は、予め操作者が入力装置１２を操作することによってハードディスク１５に格納されていたものであっても良いし、ＣＰＵ１０がディスプレイ１３上に表示する入力画面上に操作者によって書き込まれたものであって良い。
【００２２】
次のＳ００２では、ＣＰＵ１０は、Ｓ００１にて入力された条件を満たす直線形状を有するハーネス形状の三次元モデルを算出する。
【００２３】
次のＳ００３では、ＣＰＵ１０は、Ｓ００２にて生成したハーネス形状の三次元モデルにおける自己交差の検出を実行する。なお、ＣＰＵ１０は、Ｓ００２にて算出した三次元モデルを、図６に示すように、太さを有しない三次元曲線に変換し、かかる三次元曲線をＳ００３での自己交差検出処理に用いる。
【００２４】
図３は、Ｓ００３にて実行される自己交差検出処理サブルーチンを示すフローチャートである。このサブルーチンに入って最初のＳ１０１では、ＣＰＵ１０は、図７に示すように、上記三次元曲線上に、当該三次元曲線をＮ個の線分に等分する所定個数（Ｎ＋１個）の点列（pi={Xi,Yi,Zi}:i=0,1,2,…,N）を生成することにより、当該三次元曲線を折れ線に近似する。なお、点列の始点p0及び終点pNは、夫々、三次元曲線の始点上及び終点上に生成される。
【００２５】
次のＳ１０２では、ＣＰＵ１０は、Ｓ１０１にて生成した点列（折れ線）を、第１の平面に投影した上で（投影手段に相当）、当該第１の平面上に投影した点列を結ぶ折れ線が自己交差を有するかを検出する処理を実行する（平面上交差検出手段に相当）。なお、第１の平面及び後述する第２の平面は、互いに異なる方向を向いた面であれば、夫々、如何なる方向を向いた面であっても良い。例えば、点列の始点p0，終点pN及び任意の中間点pkを含む面であっても良い。但し、処理を簡単にするため、以下においては、第１の平面を
Ｘ−Ｙ平面と平行な面とし、第２の平面をＹ−Ｚ平面と平行な面として、説明を行う。
【００２６】
図４は、Ｓ１０２にて実行される平面上曲線の自己交差検出処理サブルーチンを示すフローチャートである。このサブルーチンに入って最初のＳ２０１では、ＣＰＵ１０は、Ｓ１０１にて生成した点列を、図８に示すように、Ｘ−Ｙ平面上の点列（pi={Xi,Yi}:i=0,1,2,…,N）に変換する。即ち、ＣＰＵ１０は、点列を構成する各点の座標値からＺ座標の
値を削除することにより、点列（折れ線）を、Ｘ−Ｙ平面に投影する。
【００２７】
次のＳ２０２では、ＣＰＵ１０は、Ｓ１０１にて変換された点列（pi={Xi,Yi}:i=0,1,2,…,N）を構成する各点PiのＸ座標の値Xiを、サフィックスｉの値順に読み込むことによ
り、点列におけるＸ座標の値Xiが単調増加又は単調減少となってないｉの区間を検出する。具体的には、ＣＰＵ１０は、点列の始点p0におけるＸ座標の値X0に比して二番目の点p1におけるＸ座標の値X1が増加している場合には、一つ前の点Pi-1におけるＸ座標の値Xi-1よりもＸ座標の値Xiが減少している点Piが連なるｉの区間を検出する。また、ＣＰＵ１０は、点列の始点p0におけるＸ座標の値X0に比して二番目の点p1におけるＸ座標の値X1が減少している場合には、一つ前の点Pi-1におけるＸ座標の値Xi-1よりもＸ座標の値Xiが増加している点Pi-1が連なるｉの区間を検出する。例えば、図９に示す例では、点列の始点p0におけるＸ座標の値X0に比して二番目の点p1におけるＸ座標の値X1が増加しているので、点P2から点P6までの区間が、単調増加でないｉの区間として検出される。
【００２８】
次のＳ２０３では、ＣＰＵ１０は、Ｓ２０２において単調増加又は単調減少でない区間が検出されたか否かを、チェックする。そして、変化が単調でない区間が検出されなかった場合には、ＣＰＵ１０は、Ｓ２１１において、戻り値を“交差なし”として、当該サブルーチンを終了して、処理を図３のルーチンに戻す。
【００２９】
これに対して、Ｓ２０２にて単調増加又は単調減少でない区間が検出された場合には、ＣＰＵ１０は、処理をＳ２０４へ進める。
【００３０】
Ｓ２０４では、ＣＰＵ１０は、Ｓ２０２において検出された単調でない区間に属する一連の点piについてのＸ座標の値Xiのうち、最小値Xmin及び最大値Xmaxを求める。そして、ＣＰＵ１０は、Ｘ座標の値XiがXmin以上Xmax以下である領域の両外側に近接する各点によって囲まれたｉの区間［i_xs,i_xe］を選択する。図９の例では、点p6についてのＸ座標
の値X6がXminであり、点p2についてのＸ座標の値X2がXm axであるから、X6以上X2以下で
ある領域の両外側に近接する点p1及び点p7によって囲まれたｉの区間［1,7］が選択され
る。
【００３１】
次のＳ２０５では、ＣＰＵ１０は、Ｓ２０４にて選択したｉの区間［i_xs,i_xe］に属
する各点piのＹ座標の値Yiを、サフィックスｉの値順に読み込むことにより、点列（pi_xs〜pi_xe）におけるＹ座標の値Yiが単調増加又は単調減少となっていないｉの区間を検出する。具体的には、ＣＰＵ１０は、Ｓ２０２と同様の手法により、単調増加又は単調減少でないｉの区間を検出する。例えば、図１０に示す例では、既に点p1から点p7までのｉの区間［1,7］が選択されているので、当該区間［1,7］のうち点p4から点p7までの区間が、単調増加でないｉの区間として検出される。
【００３２】
次のＳ２０６では、ＣＰＵ１０は、Ｓ２０５において単調増加又は単調減少でない区間が検出されたか否かを、チェックする。そして、単調でない区間が検出されなかった場合には、ＣＰＵ１０は、Ｓ２１１において、戻り値を“交差なし”として、当該サブルーチンを終了して、処理を図３のルーチンに戻す。
【００３３】
これに対して、Ｓ２０５にて単調増加又は単調減少でない区間が検出されたとＳ２０６
にて判定した場合には、ＣＰＵ１０は、処理をＳ２０７へ進める。即ち、ＣＰＵ１０は、Ｓ２０２，Ｓ２０３，Ｓ２０５，Ｓ２０６を経ることで、投影された折れ線上の点列を順に辿ったならば各仮想平面に設定された二つの座標軸上の値の変化が同じ区間において夫々単調とならない場合に限り、自己交差を検出できることとなる。
【００３４】
Ｓ２０７では、ＣＰＵ１０は、Ｓ２０５において検出された単調でない区間に属する一連の点piについてのＹ座標の値Yiのうち、最小値Ymin及び最大値Ymaxを求める。そして、ＣＰＵ１０は、点列（pi_xs〜pi_xe）のうち、Ｙ座標の値YiがYmin以上Ymax以下である領域の両外側に近接する各点によって囲まれたｉの区間［i_ys,i_ye］を選択する。図１０
の例では、点p7についてのＹ座標の値Y7がYminであり、点p4についてのＹ座標の値Y4がYmaxであるから、点p1から点p7までの区間のうち、y7以上y4以下である領域の両外側に近接する点はない。そこで、点p4及び点p7によって囲まれた区間［1,7］そのものが選択され
る。
【００３５】
次のＳ２０８では、サフィックスｉが区間［i_ys,i_ye］に属する一連の点pi_ys〜pi_yeを繋ぐ折れ線を構成する全線分から選ばれる二本の線分の全組合せに対して、交差（即
ち、共通座標）の計算を試みる。即ち、ＣＰＵ１０は、Ｘ−Ｙ座標系において２本の線分を夫々示す連立方程式の解の算出を、試みる。  
【００３６】
次のＳ２０９では、ＣＰＵ１０は、Ｓ２０８での計算の結果、何れの線分の組合わせについて解（即ち、交差の座標）が算出されたか否かに基づいて、Ｘ−Ｙ平面上において自己交差があるかどうかをチェックする。そして、Ｘ−Ｙ平面上において自己交差がないと判断した場合には、ＣＰＵ１０は、Ｓ２１１において、戻り値を“交差なし”として、当該サブルーチンを終了して、処理を図３のルーチンに戻す。
【００３７】
これに対して、Ｘ−Ｙ平面上において自己交差があるとＳ２０９にて判断した場合には、ＣＰＵ１０は、処理をＳ２１０へ進める。即ち、ＣＰＵ１０は、Ｓ２０４及びＳ２０７を経ることで、何れか一方の座標軸上において、値の変化が単調でない区間の両外側に夫々値を有する二点を選択しする。そして、ＣＰＵ１０は、Ｓ２０８及びＳ２０９を経ることで、前記折れ線における前記選択された二点間に存する各線分間の交点を求め、何れか２つの線分間に交点が算出できた場合に限り、自己交差を検出できることとなる。
【００３８】
Ｓ２１０では、ＣＰＵ１０は、“交差あり”及び解が算出された二本の線分を夫々区切る４つの点piを戻り値として、当該サブルーチンを終了して、処理を図３に戻す。
【００３９】
処理が戻された図３では、ＣＰＵ１０は、Ｓ１０２の次のＳ１０３において、Ｓ１０２の処理からの戻り値が“交差あり”であったか“交差なし”であったかを、チェックする。そして、戻り値が“交差なし”であった場合には、ＣＰＵ１０は、Ｓ１０８において、戻り値を“交差なし”として、当該サブルーチンを終了して、処理を図２のメインルーチンに戻す。
【００４０】
これに対して、戻り値が“交差あり”であった場合には、ＣＰＵ１０は、処理をＳ１０４へ進める。Ｓ１０４では、ＣＰＵ１０は、Ｓ１０１にて生成した点列を、第２の平面（Ｙ−Ｚ平面）に投影した上で（投影手段に相当）、当該第２の平面上に投影した点列を結ぶ折れ線が自己交差を有するかを検出する処理を実行する（平面上自己交差検出手段に相当）。図５は、Ｓ１０４にて実行される平面上曲線の自己交差検出処理サブルーチンを示すフローチャートである。図５のフローチャートは、図４のフローチャートと比較して、点列が投影される平面がＹ−Ｚ平面であるので、処理の対象となる座標の値が、Ｙ座標の値とＺ座標の値である点においてのみ相違する。例えば、図４のＳ２０１に相当する図５のＳ３０１では、Ｓ１０１にて生成された点列を構成する各点の座標値からＸ座標の値が
削除されることにより、点列（pi={Xi,Yi,Zi}:i=0,1,2,…,N）がＹ−Ｚ平面に投影される。その他の点において、図５は、図４と同じなので、その説明を省略する。
【００４１】
次のＳ１０５では、ＣＰＵ１０は、Ｓ１０４の処理からの戻り値が“交差あり”であったか“交差なし”であったかを、チェックする。そして、戻り値が“交差なし”であった場合には、ＣＰＵ１０は、Ｓ１０８において、戻り値を“交差なし”として、当該サブルーチンを終了して、処理を図２のメインルーチンに戻す。
【００４２】
これに対して、戻り値が“交差あり”であった場合には、ＣＰＵ１０は、処理をＳ１０６へ進める。Ｓ１０６では、ＣＰＵ１０は、Ｓ１０２（Ｓ２１０）における戻り値に含まれる４つの点piとＳ１０４（Ｓ３１０）における戻り値に含まれる４つの点piとが一致しているかどうかを判定する。即ち、ＣＰＵ１０は、当該判定結果に基づいて、第１の平面（Ｘ−Ｙ平面）に投影された曲線の交点の位置と第２の平面（Ｙ−Ｚ平面）に投影された曲線の交点の位置とが同じであるか否かを、チェックする。そして、両平面に夫々投影された曲線の交点の位置が同じでなければ、ＣＰＵ１０は、Ｓ１０８において、戻り値を“交差なし”として、当該サブルーチンを終了して、処理を図２のメインルーチンに戻す。
【００４３】
これに対して、両平面に夫々投影された曲線の交点の位置が同じであれば、ＣＰＵ１０は、Ｓ１０７において、戻り値を“交差あり”として、当該サブルーチンを終了して、処理を図２のメインルーチンに戻す。以上に説明したＳ１０３，Ｓ１０５，Ｓ１０６〜Ｓ１０７が、全ての仮想平面に投影された曲線に含まれる自己交差が検出された場合に、前記三次元曲線モデルに自己交差があると判定する判定手段に相当する。
【００４４】
処理が戻されたメインルーチンでは、ＣＰＵ１０は、Ｓ００３の次のＳ００４において、Ｓ００３の処理からの戻り値が“交差あり”であったか“交差なし”であったかを、チェックする。そして、戻り値が“交差なし”であった場合には、ＣＰＵ１０は、三次元曲線モデル生成プログラム１６による処理を終了する。
【００４５】
これに対して、戻り値が“交差あり”であったとＳ００４にて判断した場合には、ＣＰＵ１０は、処理をＳ００５へ進める。Ｓ００５では、ＣＰＵ１０は、Ｓ００１にて入力された条件を調整することにより、調整後の条件を満たす直線形状を有するハーネス形状の三次元モデルを算出する。Ｓ００５の完了後、ＣＰＵ１０は、三次元曲線モデル生成プログラム１６による処理を終了する。
＜作用＞
以上に説明した本実施形態によれば、ハーネスの三次元曲線モデルが、第１の面及び第２の面に夫々投影されるとともに、各面に投影された二次元曲線について、夫々自己交差が検出される（Ｓ１０２，Ｓ１０４）。
【００４６】
各面に投影された二次元曲線に対する自己交差の検出では、一方の座標軸上において、単調でない区間が検出されると（Ｓ２０２，Ｓ２０３）、当該軸上において当該単調でない区間の両外側に近接する点によって区切られる区間が、選択される（Ｓ２０４）。その結果、一方の軸上において単調でない区間に重なる区間の全体が、選択される。
【００４７】
しかし、選択された区間は、ループを形成している可能性もあるが、単に蛇行をしている可能性もある。
【００４８】
そこで、当該選択された区間について、他方の軸上においても単調でない区間があるか否かが検出される（Ｓ２０５，Ｓ２０６）。他方の軸においても単調でない区間があれば、単純な蛇行に過ぎない場合を排除されるからである。そして、他方の軸上においても単調でない区間が検出された場合には、更に、当該軸上において当該単調でない区間の両外
側に近接する点によって区切られる区間が、選択される（Ｓ２０７）。
【００４９】
但し、以上の処理によっても、選択された区間が単に渦巻き状になっているに過ぎない可能性も残される。そこで、念のため、当該区間を構成する各線分について、交差の計算がなされる（Ｓ２０８）。この場合、従来技術と異なり二次元上での計算となるので計算が単純化されるとともに、予め計算をすべき区間が区切られているので、計算量が大幅に減少することになる。なお、三次元曲線モデルを生成するプログラムの特性上、渦巻き状の形状が形成される可能性が低いのであれば、Ｓ２０７〜Ｓ２０８は省略可能である。
【００５０】
以上の処理の結果、一方の面のみにおいて自己交差が検出された場合には、三次元曲線モデルが螺旋を描いているに過ぎないと判断されるので、交差がないと最終判断される（Ｓ１０８）。
【００５１】
これに対して、両面において自己交差が検出された場合であっても、各面において自己交差が検出された位置（即ち、交差している線分）が異なる場合には、やはり、三次元曲線モデルが螺旋を描いているに過ぎないと判断される（Ｓ１０６：Ｎｏ）。よって、その場合も、交差がないと最終判断される（Ｓ１０８）。
【００５２】
これに対して、両面において夫々自己交差が検出され、且つ、各面において自己交差が検出された位置が同じ場合には、三次元曲線モデルが螺旋を描いていると判断される（Ｓ１０６：Ｙｅｓ）。よって、その場合には、交差があると最終判断される（Ｓ１０８）。
【００５３】
以上説明したように、本実施形態によると、交差計算の計算量が従来と比して大幅に減少するという利点がある。
【符号の説明】
【００５４】
１    コンピュータ
１０    ＣＰＵ
１２    入力装置
１５    ハードディスク
１６    三次元曲線モデル生成プログラム
【図１】
0005407695.tif 000002
【図２】
0005407695.tif 000003
【図３】
0005407695.tif 000004
【図４】
0005407695.tif 000005
【図５】
0005407695.tif 000006
【図６】
0005407695.tif 000007
【図７】
0005407695.tif 000008
【図８】
0005407695.tif 000009
【図９】
0005407695.tif 000010
【図１０】
0005407695.tif 000011
【図１１】
0005407695.tif 000012