(57)【特許請求の範囲】
【請求項１】
記憶手段に記憶されている３次元上領域の境界を形成している所定の稜線上において、その端点から長さに関する幾何的許容誤差に比べ十分離れた基準点を算出手段により算出する算出工程と、
該基準点を通り、当該基準点から前記幾何的許容誤差以内の距離に前記稜線と交点を持たないような面を設定手段により設定する設定工程と、
前記設定手段で設定された面と前記領域の面で交差する曲線を求める曲線工程と、
前記曲線工程で求めた交差曲線の前記基準点における、前記幾何的許容誤差に比べ十分小さい２本の接線ベクトルを求める接線ベクトル工程と、
前記接線ベクトル工程で求めた接線ベクトルのどちらが領域の外側に向かっているかを判定手段により判定して、外側に向かっている方を領域外方向ベクトルとする外ベクトル工程と、
前記基準点と前記領域外ベクトルで特定されたベクトルの終点から、前記領域がのっている面に垂線を下ろし、当該垂線に対する交点を前記領域外の点として前記記憶手段に記憶する記憶工程と
を備えることを特徴とする３次元上領域における領域内外の点の抽出方法。
【請求項２】
記憶手段に記憶されている３次元上領域の境界を形成している所定の稜線上において、その端点から長さに関する幾何的許容誤差に比べ十分離れた基準点を算出する算出手段と、
該基準点を通り、当該基準点から前記幾何的許容誤差以内の距離に前記稜線と交点を持たないような面を設定する設定手段と、
前記設定手段で設定された面と前記領域の面で交差する曲線を求める曲線手段と、
前記曲線手段で求めた交差曲線の前記基準点における、前記幾何的許容誤差に比べ十分小さい２本の接線ベクトルを求める接線ベクトル手段と、
前記接線ベクトル手段で求めた接線ベクトルのどちらが領域の外側に向かっているかを判定して、外側に向かっている方を領域外方向ベクトルとする外ベクトル手段と、
前記基準点と前記領域外ベクトルで特定されたベクトルの終点から、前記領域がのっている面に垂線を下ろし、当該垂線に対する交点を前記領域外の点として前記記憶手段に記憶する記憶制御手段と
を備えることを特徴とする３次元上領域における領域内外の点の抽出装置。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は、ＣＡＤ等の図形処理装置に適応する、３次元上領域における領域内外の点の抽出方法及び装置、及び、同一曲線上の点の並び順判定方法及び装置に関するものである。
【０００２】
【従来の技術】
２次元の領域における領域外の点の算出法としては、図６のようにｘｙ平面で考えた場合、ｘ値またはｙ値が領域の大きさに対して十分大きい座標を持つ点を考えれば、実用的に領域外の点を得られる。
【０００３】
また２次元の場合、乱数を使ってｘ値及びｙ値を算出し、その点が領域内にあるか領域外にあるかを判定し、領域外にあればその点を領域外の点とし、領域内にある場合、再び乱数を使って任意の点を求め領域外と判定されるまで、繰り返し行うという方法が知られている。
【０００４】
３次元の場合も図７のように領域が乗っている面が平面や円筒面、円錐面等、ある方向に関して、始終点が無限遠点となるような曲線が面上に存在するような面である場合は、その様な曲線上にある、領域を代表する点から十分離れた点を算出することによって領域外の点を得る方法が知られている。
【０００５】
【発明が解決しようとする課題】
従来ＣＡＤ等で計算機を使って、３次元上の領域外の点を求める場合、例えば領域の乗っている面が球のように閉じた曲面の場合、領域から十分離れた点が領域ののっている面に存在しないので、領域から十分離れた点を領域外の点とする手法は使えないという問題点がある。
【０００６】
また、領域ののっている面が円筒面や円錐面等、ある方向に関して、始終点が無限遠点となるような曲線が面上に存在する場合でも、内外判定等、領域ののっている面上の円や楕円等の閉曲線上にのっている領域外の点を求める必要がある時、領域から十分離れた点を領域外の点とする手法は使えないという問題点がある。
【０００７】
また、一般にある曲線上の点の並び順を判定する場合、これまではその曲線の幾何的特徴に基づいて判定しており、あらゆる曲線に対して適応することは難しかった。
【０００８】
【課題を解決するための手段】
及び
【作用】
本第１の発明は、かかる問題点に鑑みなされたものであり、領域の乗っている面の種類に依存せず、その領域外の点を求めることを可能ならしめる方法及び装置を提供しようとするものである。
【０００９】
この課題を解決するため、例えば、本発明の３次元上領域における内外の点の抽出方法は、以下の工程を備える。すなわち、
記憶手段に記憶されている３次元上領域の境界を形成している所定の稜線上において、その端点から長さに関する幾何的許容誤差に比べ十分離れた基準点を算出手段により算出する算出工程と、
該基準点を通り、当該基準点から前記幾何的許容誤差以内の距離に前記稜線と交点を持たないような面を設定手段により設定する設定工程と、
前記設定手段で設定された面と前記領域の面で交差する曲線を求める曲線工程と、
前記曲線工程で求めた交差曲線の前記基準点における、前記幾何的許容誤差に比べ十分小さい２本の接線ベクトルを求める接線ベクトル工程と、
前記接線ベクトル工程で求めた接線ベクトルのどちらが領域の外側に向かっているかを判定手段により判定して、外側に向かっている方を領域外方向ベクトルとする外ベクトル工程と、
前記基準点と前記領域外ベクトルで特定されたベクトルの終点から、前記領域がのっている面に垂線を下ろし、当該垂線に対する交点を前記領域外の点として前記記憶手段に記憶する記憶工程とを備える。
【００１２】
【実施例】
以下、添付図面に従って本発明に係る実施例を詳細に説明する。
【００１３】
図１は、本発明の実施例の動作の流れを説明するフローチャートである。
【００１４】
図２は、本発明の利用する図形処理装置のブロック図であり、バス１（制御線、データ、アドレス及び制御バスを含む）には、中央処理装置（以下、ＣＰＵ）２、リード・オンリ・メモリ（以下、ＲＯＭ）３、ランダム・アクセス・メモリ（以下、ＲＡＭ）４、入力インターフエース５を介して入力装置６、ＣＲＴインターフエース７を介してＣＲＴ８、外部記憶装置インターフエース９を介して、磁気ディスク、磁気テープ等の外部記憶装置１０が接続されている。
【００１５】
ＣＰＵ２は、ＲＯＭ３に記憶されたプログラムに応じ、ＲＡＭ４を一時記憶装置として種々の処理及び制御、例えば図形入力制御、図形表示、ピック処理、隠面処理、内外判定等を行う。
【００１６】
入力装置６はキーボード、タブレット、マウス等であり、図形データの入力を行うが、この図形データはホスト・コンピュータから受けてもよい。ＣＲＴ８は必要に応じて複数のビット・マップ・プレーン等を含んでおり図形や各種メニュー等を表示する。
【００１７】
次に図１及び図３，４，５を参照して本発明の好適な実施例を説明するが、以下に述べる処理及び判断はＣＰＵ２がＲＯＭ３のプログラムに従って行うものである。
【００１８】
＜領域の定義＞
本実施例では、図３のような平面及び円筒面、円錐面、球等の２次曲面及びトーラス、Ｂｅｚｉｅｒ曲面、ＮＵＲＢＳ（Non Uniformed Rational B-spline ）曲面等の自由曲面等の幾何形状を持つ面上にあり、線分及び円弧、楕円弧、放物線、双曲線等の２次曲線、Ｂｅｚｉｅｒ曲線、ＮＵＲＢＳ（Non Uniformed Rational B-spline ）曲線等の幾何形状を持つ稜線からなる境界線によって囲まれた領域内に、ある空間上の点がその領域内にあるかどうかを判定するものである。尚、ここで言う稜線とは、領域の境界を特定するエッジ部位を意味する。
【００１９】
ここで図４のように境界は稜線の集合で構成され、更にそれぞれの稜線は外周ループと内周ループよりなる。外周ループは領域の最外周を表現するループで、内周ループは領域における「穴」を表現するループである。外周ループは、反時計周りを正方向とし、内周ループは時計周りを正方向とし、その順番に稜線が並んでいるものとする。換言すれば、稜線上をループをそれぞれ正方向に進んでいったとき、その左側に領域の実体があるものとする。
【００２０】
以下に図１の本実施例の流れを示すフローチャートのステップＳ１〜Ｓ１３の順番に従って３次元領域における領域外の点の算出処理の説明を行う。
【００２１】
＜Ｓ１：３次元領域の境界Ｂの任意の稜線Ｅ０を取り出す＞
対象となる３次元上の領域のデータ（予め、入力装置６より入力されているものとする）を外部記憶装置１０またはＲＡＭ４から取り出し、境界Ｂを構成する稜線の中から任意、例えば着目しているループを構成している最初の稜線Ｅ０を選択する。この稜線Ｅ０の長さの幾何的許容誤差をεとしたとき、２εより大きいかどうかを中央処理装置で判定し、２εより大きいものを取り出し、ＲＡＭ４に格納する（図５参照）。尚、２εより小さい稜線に対しては、その長さが十分小さく無視できるものとして以下の処理を省略する。また、εの２倍の値を考慮したのは、以下に説明するように、その稜線Ｅ0の中央点を基準にするからであり、それを中心とした場合に両側の線部分の幾何学的許容誤差をそれぞれεにできるからでもある。
【００２２】
＜Ｓ２：稜線Ｅ０上の中点Ｐ０を算出＞
稜線Ｅ０のデータを外部記憶装置１０またはＲＡＭ４から取り出し、稜線Ｅ０上の中点Ｐ０をＣＰＵ２により算出して、ＲＡＭ４に格納する（図５参照）。
【００２３】
＜Ｓ３：点Ｐ０を通る切断面の算出＞
ここでは、切断面として平面を考える。ＲＡＭ４から取り出した点Ｐ０のデータ、予め固定した任意の１点と、ＣＰＵ２により発生した乱数を使って求めた一点が同一直線に並んでいるかどうかをＣＰＵ２により判定し、並んでいなかったら、それら３点で平面が特定できるので、その３点を通る平面を切断面としてＲＡＭ４に格納する。また、平面が特定できなかった場合、すなわち、同一直線に並んでいると判定されたら、並ばなくなるまで、ＣＰＵ２により発生した乱数を使って点を求める。ここで乱数を使い切断面を求めることによって点Ｐ０とε以内にＥ０と交点を持つような切断面が求まる確率が低くなる。点Ｐ０とε以内にＥ０と交点を持つと正しく領域外の点が求まらないことがある。
【００２４】
＜Ｓ４：切断面と領域の乗っている面Ｓとの交線Ｃの算出＞
上記求めた切断平面と領域の乗っている面ＳをＲＡＭ４から取り出し、その交線ＣをＣＰＵ２により算出する。
【００２５】
＜Ｓ５：点Ｐ０における面Ｓの法線ベクトルｎ０を算出＞
点Ｐ０及び面ＳのデータをＲＡＭ４より取り出し、点Ｐ０における領域の乗っている面Ｓ法線ベクトルｎ０をＣＰＵ２により算出して、それをＲＡＭ４に格納する（図５参照）。
【００２６】
＜Ｓ６：点Ｐ０における稜線Ｅ０の接線ベクトルＴＥ１，ＴＥ２の算出＞
点Ｐ０及び稜線Ｅ０のデータを外部記憶装置１０またはＲＡＭ４より取り出し、点Ｐ０における稜線Ｅ０の接線の単位方向ベクトルＴＥ１，ＴＥ２をＣＰＵ２により算出し、ＲＡＭ４に格納する。尚、この時点では、ＴＥ１、ＴＥ２のいずれが領域外を向いているのか特定できていない。
【００２７】
＜Ｓ７：ＴＥ１，ＴＥ２のうち境界の回り向きと同方向のものをＴＥとする＞上記求めた接線ベクトルＴＥ１，ＴＥ２のデータをＲＡＭ４より取り出し、どちらが境界の回り向きと同一方向かをＣＰＵ２により判定し、同一のものをＴＥとしＲＡＭ４に格納する（図５参照）。
【００２８】
＜Ｓ８：点Ｐ０における曲線Ｃの接線ベクトルＴＣ１，ＴＣ２を算出＞
上記ステップＳ４で求めた曲線ＣのデータをＲＡＭ４より取り出し、点Ｐ０における接線の方向ベクトルで、大きさが幾何的許容誤差εより十分に小さいベクトルをＣＰＵ２により算出し、ＴＣ１，ＴＣ２としてＲＡＭ４に格納する（図５参照）。
【００２９】
＜Ｓ９：ＴＣ１とＴＥの外積ｎ１及びＴＣ２とＴＥの外積ｎ２の算出＞
ＴＣ１，ＴＣ２，ＴＥのデータをＲＡＭ４より取り出し、
ｎ１＝ＴＣ１×ＴＥ                            …  （１）
ｎ２＝ＴＣ２×ＴＥ                            …  （２）
よりＴＣ１とＴＥの外積ｎ１、及びＴＣ２とＴＥ２の外積ｎ２をＣＰＵ２によって算出し、それをＲＡＭ４に格納する。
【００３０】
＜Ｓ１０：ｎ０とｎ１のなす各θ１及びｎ０とｎ２のなす角θ２の算出＞
ｎ０，ｎ１，ｎ２のデータをＲＡＭ４より取り出し、
θ１＝（ｎ０とｎ１のなす角）（０≦θ１≦π）    （３）
θ２＝（ｎ０とｎ２のなす角）（０≦θ２≦π）    （４）
としてθ１，θ２をＣＰＵ２により算出し、ＲＡＭ４に格納する。
【００３１】
＜Ｓ１１：θi(i=1,2)< π/2のときＴＣ＝ＴＣi とする＞
θ１，θ２のデータをＲＡＭ４より取り出すと、θ１，θ２のいずれかがπ／２より小さくなり、他方がπ／２より大きくなるはずなのでその判定をＣＰＵ２により行う。θｉ（ｉ＝１，２）＜π／２のときＴＣ＝ＴＣｉとして、ＲＡＭ４に格納する。すなわち、これによってベクトルＴＣが領域の外に向かうものとして特定できたことになる。
【００３２】
＜Ｓ１２：Ｐｏｕｔ０＝Ｐ０＋ＴＣ＞
Ｐ０，ＴＣのデータをＲＡＭ４より取り出し、Ｐｏｕｔ０＝Ｐ０＋ＴＣをＣＰＵ２により算出し、ＲＡＭ４に格納する（図５参照）。
【００３３】
＜Ｓ１３：Ｐｏｕｔ０から交線Ｃにおろした垂線の足を領域外の点とする＞
上記Ｓ１２で求めたＰｏｕｔ０及び上記Ｓ４で求めた交線Ｃのデータをランダムアクセスメモリから取り出し、Ｐｏｕｔ０から曲線（交線）Ｃにおろした垂線の足をＣＰＵにより求め、これを領域外の点としてＲＡＭ４または外部記憶装置１０に格納する（図５参照）。
【００３４】
以上のようにすることで、例えば領域の乗っている面が球のような面であっても、一義的に、領域外の点を得ることが可能になる。つまり、任意の種類の面にのり、任意の種類の境界に囲まれた、３次元以上領域における領域外の点を求めることにより、３次元領域における内外判定等の、３次元の図形処理を許容誤差の範囲で安定的に行うことができるという効果がある。
【００３５】
また、上記実施例では、領域外の点を求める例を示したが、領域内の点を求める場合にも適応できることは言うまでもない。
【００３６】
尚、上記実施例において、点Ｐ０からε以内の距離にＥ０と交点を持たない、着目している領域の同一面上にある曲線Ｃを求める方法として、Ｐ０と与点と乱数を使って発生された点を通る平面と領域の乗っている面との交線として求めるのではなく、Ｐ０と固定点と適当なばらつきのある予め準備された複数の点のうちの１個から平面を作り、求めた交線が点Ｐ０からε以内の距離にＥ０と交点を持っていたら別の点を使って平面を生成して、交線を求めるという方法でもよい。この場合、処理効率は若干落ちるが確実性の高い点Ｐ０からε以内の距離にＥ０と交点を持たない交線を求める方法によって、領域外の１点の算出を行えるようになる。
【００３７】
また、上記実施例において、３次元上領域の境界上の任意の稜線Ｅ０上の、端点から長さに関する幾何的許容誤差εに比べ十分離れた任意の点Ｐ０を算出するステップ点Ｐ０を求めるのに、稜線Ｅ０上の中点を取るのではなく、領域外の内外判定等のように、特定の交線上の点をＰ０とする必要がある場合は、その特定の交線とＥ０の交点をＰ０として端点との距離がεより大きいかをチェックする方法で領域外の１点の算出を行える。
【００３８】
＜第２の実施例の説明＞
次に、第２の実施例を説明する。
【００３９】
一般に、同一曲線上の点の並び順を認識する手法としては、いくつかある。例えば直線上の場合には、ある基準点からの距離により点の並びを識別できる。また、円上の場合には、その円の中心と結ぶ線分と基準線（基準点と円の中心を結ぶ線分）との角度に基づいて、点の並びを識別できる。
【００４０】
しかしながら、点の並び順を識別、もしくは認識する手法は、その曲線（直線も含む）毎の個別の幾何的特徴にたよっていたので、汎用性がないという問題点がある。
【００４１】
本第２の実施例では、かかる問題点を一掃しようとする。
【００４２】
以下、図８〜図１１に基づいて説明する。尚、装置構成としては、上記第１の実施例における図２と同じとし、その詳細は省略する。但し、ＲＯＭ３には図８のフローチャートに基づくプログラムが格納されることになる。
【００４３】
＜Ｓ２１：与えられた曲線をパラメトリック＞
２次元または３次元の空間における曲線のデータを外部記憶装置１０或いはＲＡＭ４から取り出し、ＣＰＵ２によりパラメトリック表現に変換する。そして、変換した結果をＲＡＭ４に格納する。但し、パラメータが曲線Ｃの進む方向に従って単調に増減するようなパラメトリック表現に変換する必要がある（図９〜図１１の→方向を参照）。パラメトリックの例としては、次のようになろう。
【００４４】
（１）直線の場合
Ｐ＝Ｐ０＋ｔＶ（−∝≦ｔ≦∝）
ここで、Ｐ０：直線上の任意の一点
Ｖ  ：直線の方向ベクトル
ｔ  ：パラメータ
である。
【００４５】
（２）円の場合
Ｐ＝Ｃ＋ｒ（ｕ・ｃｏｓ（ｔ）＋ｖ・ｓｉｎ（ｔ））  （０≦ｔ≦２π）
ここで、Ｃ  ：円の中心
ｒ  ：円の半径
ｕ  ：基準ベクトル１（円と同じ平面上の単位ベクトル）
ｖ  ：基準ベクトル２（円と同じ平面上の単位ベクトル）
但し、ｕ・ｖ＝０、  ｜ｕ｜＝｜ｖ｜＝１
ｔ  ：パラメータ
である。
【００４６】
（３）楕円の場合
Ｐ＝Ｃ＋ａ・ｃｏｓ（ｔ）＋ｂ・ｓｉｎ（ｔ）  （０≦ｔ≦２π）
ここで、Ｃ  ：楕円の中心
ａ  ：長軸ベクトル
ｂ  ：短軸ベクトル
但し、ａ・ｂ＝０
ｔ  ：パラメータ
である。
【００４７】
尚、ここでは３種類の曲線について示したが、種類はこれに限るものではない。要は、曲線をパラメトリック表現することにその意味があるからである。
【００４８】
＜Ｓ２２：曲線上の各点のパラメトリック値を算出＞
上記パラメトリック表現をもとに、曲線上の各点の座標値を外部記憶装置１０またはＲＡＭ４から取り出し、ＣＰＵ２により上記パラメトリック表現におけるパラメトリック値を求め、元の点と対応づけてＲＡＭ４に格納する。
【００４９】
例えば、直線の場合、
ｔ＝（Ｐ−Ｐ０）・Ｖ／（Ｖ・Ｖ）
となる。
【００５０】
円の場合、
ｃｏｓ（ｔ）＝（（Ｐ−Ｃ）・ｕ）／ｒ
ｓｉｎ（ｔ）＝（（Ｐ−Ｃ）・ｕ）／ｒ
ここで、０≦ｔ≦２πの範囲なのでパラメータが一意に決まる。
【００５１】
楕円の場合、
ｃｏｓ（ｔ）＝（（Ｐ−Ｃ）・ａ）／｜ａ｜＾２
ｓｉｎ（ｔ）＝（（Ｐ−Ｃ）・ｂ）／｜ｂ｜＾２
ここで、０≦ｔ≦２πの範囲なので、パラメータが一意に決まる。また、｜ｘ｜はｘの絶対値を、ｘ＾ｙはｘのｙ乗を示している。
【００５２】
＜Ｓ２３：パラメトリック値をソート＞
上記ステップＳ２２で求めたパラメータをＲＡＭ４より取り出し、パラメータとそれに対応する点を算出し、その算出した点をＣＰＵ２によりクイックソート、バブルソート等を使用してソートし、ソートした結果をＲＡＭ４に格納する。尚、ソートの手法には、様々なものがあって、これ以外のものを採用しても良いのは勿論である。
【００５３】
＜Ｓ２４：パラメトリック値でソートされた順番によって点をソート＞
上記ステップＳ２３でソートされたパラメータの順番とパラメータとの点の対応をＲＡＭ４より取り出し、参照して、ＣＰＵ２により点の順番を認識する。
【００５４】
以上説明したように本第２の実施例によれば、同一曲線上の点の並びを認識することにより、ＣＡＤ等における領域内外判定等の幾何学処理等を、汎用的にしかも簡単に行うことが可能になる。
【００５５】
尚、上述した第１、第２の実施例では、１つの装置に適応した例を説明したが、本発明は複数の機器から構成されるシステムに適用しても良い。また、本発明は、システム或は装置にプログラムを供給することによって達成される場合にも適用できることはいうまでもない。
【００５６】
【発明の効果】
以上説明したように本発明によれば、領域の乗っている面の種類に依存せず、その領域外の点を求めることが可能になる。
【００５７】
また、他の第２の発明によれば、与えられた曲線上の点の並びを、その曲線を表現している関数から、パラメトリック表現という共通な表現に変換し、曲線の幾何的表現に依存せず、一意にその曲線上の点の並び順を判定することが可能になる。
【００５８】
【図面の簡単な説明】
【図１】本発明の好適な一実施例を示す流れ図である。
【図２】本発明を利用する図形処理装置のブロック図である。
【図３】本実施例で扱う、領域の構成を示す図である。
【図４】外周ループと内周ループを説明する図である。
【図５】領域外の点を求める方法を示す図である。
【図６】ｘｙ平面での領域外の点を求める従来の方法を説明する図である。
【図７】３次元の領域において、領域から十分離れた点を選ぶことにより領域外の点が算出できる場合を示す図である。
【図８】第２の実施例における処理手順を示すフローチャートである。
【図９】第２の実施例における直線のパラメータの増減方向と点の並び順の関係を示す図である。
【図１０】第２の実施例における円のパラメータの増減方向と点の並び順の関係を示す図である。
【図１１】第２の実施例における楕円のパラメータの増減方向と点の並び順の関係を示す図である。
【符号の説明】
１  バス
２  中央演算処理装置（ＣＰＵ）
３  リードオンリーメモリ（ＲＯＭ）
４  ランダムアクセスメモリ（ＲＡＭ）
５  入力インターフェース
６  入力装置
７  ＣＲＴインターフェース
８  ＣＲＴ装置
９  外部記憶装置インターフェース
１０  外部記憶装置
【図１】
0003679436.tif 000002
【図２】
0003679436.tif 000003
【図３】
0003679436.tif 000004
【図４】
0003679436.tif 000005
【図５】
0003679436.tif 000006
【図６】
0003679436.tif 000007
【図７】
0003679436.tif 000008
【図８】
0003679436.tif 000009
【図９】
0003679436.tif 000010
【図１０】
0003679436.tif 000011
【図１１】
0003679436.tif 000012