(57)【要約】【課題】複数の要素で構成されるオブジェクト間の最短距離を取得するための処理時間を短縮する。【解決手段】オブジェクトを構成する複数の要素の幾何学的連続性を有する配列順の配列に対して、幾何学的連続性を有さない読出順に基づいて対象要素を決定し、対象要素の位置情報を読み出し、対象要素と所定点との距離を簡易判定し、簡易判定距離Ｄrghが最短距離Ｄminを超えている場合には次の対象要素に対する簡易判定を行い、簡易判定距離Ｄrghが最短距離Ｄmin以下である場合には、対象要素の位置情報に基づいて対象要素と所定点との距離を詳細判定し要素距離Ｄobjに設定し、要素距離Ｄobjが最短距離Ｄminを超えている場合には次の対象要素に対する簡易判定を実行し、要素距離Ｄobjが最短距離Ｄmin以下である場合には、要素距離Ｄobjを最短距離Ｄminに代入し、全ての要素が対象要素になったと判断されるまで以上の処理を実行する。【選択図】図９
2008021329.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータグラフィックス処理において、複数の要素で構成されるオブジェクトと所定点との最短距離を取得するためのオブジェクト間の最短距離取得方法であって、
Ａ）最短距離Ｄminを初期値に設定する段階と、
Ｂ）前記オブジェクトを構成する複数の要素の幾何学的連続性を有する配列順の配列に対して、幾何学的連続性を有さない読出順に基づいて対象要素を決定し、前記対象要素の位置情報を読み出す段階と、
Ｃ）前記対象要素の位置情報に基づいて、対象要素と所定点との距離を簡易判定して、簡易判定距離Ｄrghに設定する段階と、
Ｄ）前記簡易判定距離Ｄrghと最短距離Ｄminとを比較し、簡易判定距離Ｄrghが最短距離Ｄminを超えている場合にはＢ段階に移行し、簡易判定距離Ｄrghが最短距離Ｄmin以下である場合には、対象要素の位置情報に基づいて対象要素と所定点との距離を詳細判定し要素距離Ｄobjに設定する段階と、
Ｅ）前記要素距離Ｄobjと最短距離Ｄminとを比較し、要素距離Ｄobjが最短距離Ｄminを超えている場合にはＢ段階に移行し、要素距離Ｄobjが最短距離Ｄmin以下である場合には、要素距離Ｄobjを最短距離Ｄminに代入する段階と、
Ｆ）前記オブジェクトを構成する複数の要素のうち対象要素になっていないものがある場合にはＢ段階に移行し、全ての要素が対象要素になったと判断される場合には処理を終了する段階と、
を含むオブジェクト間の最短距離取得方法。
【請求項２】
前記Ｂ段階は、
前記オブジェクトを構成する要素数Ｎの要素の幾何学的な連続性を考慮した所定配列順（１〜Ｎ）に対して、所定数ａおきに対象要素となるような読出順を処理順テーブルとして記憶し、前記処理順テーブルを参照することにより対象要素を決定して前記対象要素の位置情報を読み出すことを特徴とする、請求項１に記載のオブジェクト間の最短距離取得方法。
【請求項３】
コンピュータのグラフィックス処理において、複数の要素で構成される第１オブジェクトおよび第２オブジェクトの最短距離を取得するためのオブジェクト間の最短距離取得方法であって、
Ａ）最短距離Ｄminを初期値に設定する段階と、
Ｂ）前記第１オブジェクトを構成する所定要素数の要素の幾何学的な連続性を考慮した所定配列順に対して、所定数おきに対象要素となるような読出順を第１処理順テーブルとして記憶し、前記第１処理順テーブルを参照することにより第１対象要素を決定して前記第１対象要素の位置情報を読み出す段階と、
Ｃ）前記第２オブジェクトを構成する所定要素数の要素の幾何学的な連続性を考慮した所定配列順に対して、所定数おきに対象要素となるような読出順を第２処理テーブルとして記憶し、前記第２処理順テーブルを参照することにより第２対象要素を決定して前記第２対象要素の位置情報を読み出す段階と、
Ｄ）前記第１対象要素および第２対象要素の位置情報に基づいて、第１対象要素と第２対象要素の距離を簡易判定して、簡易判定距離Ｄrghに設定する段階と、
Ｅ）前記簡易判定距離Ｄrghと最短距離Ｄminとを比較し、簡易判定距離Ｄrghが最短距離Ｄminを超えている場合にはＣ段階に移行し、簡易判定距離Ｄrghが最短距離Ｄmin以下である場合には、前記第１対象要素と第２対象要素の位置情報に基づいて第１対象要素と第２対象要素の距離を詳細判定し要素距離Ｄobjに設定する段階と、
Ｆ）前記要素距離Ｄobjと最短距離Ｄminとを比較し、要素距離Ｄobjが最短距離Ｄminを超えている場合にはＣ段階に移行し、要素距離Ｄobjが最短距離Ｄmin以下である場合には、要素距離Ｄobjを最短距離Ｄminに代入する段階と、
Ｇ）前記第２オブジェクトを構成する複数の要素のうち第２対象要素になっていないものがある場合にはＣ段階に移行し、全ての要素が第２対象要素になったと判断される場合にはＨ段階に移行する段階と、
Ｈ）前記第１オブジェクトを構成する複数の要素のうち第１対象要素になっていないものがある場合にはＢ段階に移行し、全ての要素が第１対象要素になったと判断される場合には処理を終了する段階と、
を含むオブジェクト間の最短距離取得方法。
【請求項４】
複数の要素で構成されるオブジェクトと所定点との最短距離を取得するためのオブジェクト間の最短距離取得方法をコンピュータに行わせるプログラムであって、
Ａ）最短距離Ｄminを初期値に設定する段階と、
Ｂ）前記オブジェクトを構成する複数の要素の幾何学的連続性を有する配列順の配列に対して、幾何学的連続性を有さない読出順に基づいて対象要素を決定し、前記対象要素の位置情報を読み出す段階と、
Ｃ）前記対象要素の位置情報に基づいて、対象要素と所定点との距離を簡易判定して、簡易判定距離Ｄrghに設定する段階と、
Ｄ）前記簡易判定距離Ｄrghと最短距離Ｄminとを比較し、簡易判定距離Ｄrghが最短距離Ｄminを超えている場合にはＢ段階に移行し、簡易判定距離Ｄrghが最短距離Ｄmin以下である場合には、対象要素の位置情報に基づいて対象要素と所定点との距離を詳細判定し要素距離Ｄobjに設定する段階と、
Ｅ）前記要素距離Ｄobjと最短距離Ｄminとを比較し、要素距離Ｄobjが最短距離Ｄminを超えている場合にはＢ段階に移行し、要素距離Ｄobjが最短距離Ｄmin以下である場合には、要素距離Ｄobjを最短距離Ｄminに代入する段階と、
Ｆ）前記オブジェクトを構成する複数の要素のうち対象要素になっていないものがある場合にはＢ段階に移行し、全ての要素が対象要素になったと判断される場合には処理を終了する段階と、
を含むオブジェクト間の最短距離取得方法をコンピュータに実行させるためのプログラム。
【請求項５】
複数の要素で構成される第１オブジェクトおよび第２オブジェクトの最短距離を取得するためのオブジェクト間の最短距離取得方法をコンピュータに行わせるプログラムであって、
Ａ）最短距離Ｄminを初期値に設定する段階と、
Ｂ）前記第１オブジェクトを構成する所定要素数の要素の幾何学的な連続性を考慮した所定配列順に対して、所定数おきに対象要素となるような読出順を第１処理順テーブルとして記憶し、前記第１処理順テーブルを参照することにより第１対象要素を決定して前記第１対象要素の位置情報を読み出す段階と、
Ｃ）前記第２オブジェクトを構成する所定要素数の要素の幾何学的な連続性を考慮した所定配列順に対して、所定数おきに対象要素となるような読出順を第２処理テーブルとして記憶し、前記第２処理順テーブルを参照することにより第２対象要素を決定して前記第２対象要素の位置情報を読み出す段階と、
Ｄ）前記第１対象要素および第２対象要素の位置情報に基づいて、第１対象要素と第２対象要素の距離を簡易判定して、簡易判定距離Ｄrghに設定する段階と、
Ｅ）前記簡易判定距離Ｄrghと最短距離Ｄminとを比較し、簡易判定距離Ｄrghが最短距離Ｄminを超えている場合にはＣ段階に移行し、簡易判定距離Ｄrghが最短距離Ｄmin以下である場合には、前記第１対象要素と第２対象要素の位置情報に基づいて第１対象要素と第２対象要素の距離を詳細判定し要素距離Ｄobjに設定する段階と、
Ｆ）前記要素距離Ｄobjと最短距離Ｄminとを比較し、要素距離Ｄobjが最短距離Ｄminを超えている場合にはＣ段階に移行し、要素距離Ｄobjが最短距離Ｄmin以下である場合には、要素距離Ｄobjを最短距離Ｄminに代入する段階と、
Ｇ）前記第２オブジェクトを構成する複数の要素のうち第２対象要素になっていないものがある場合にはＣ段階に移行し、全ての要素が第２対象要素になったと判断される場合にはＨ段階に移行する段階と、
Ｈ）前記第１オブジェクトを構成する複数の要素のうち第１対象要素になっていないものがある場合にはＢ段階に移行し、全ての要素が第１対象要素になったと判断される場合には処理を終了する段階と、
を含むオブジェクト間の最短距離取得方法をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、CAD/CAMやCGなどのコンピュータ技術計算に関するものであり、特に、複数の要素で構成されるオブジェクトと所定点との最短距離を取得するためのオブジェクト間の最短距離取得方法に関する。
【背景技術】
【０００２】
CAD/CAMやコンピュータグラフィックスでは、独立した複数のオブジェクトより構成されており、各オブジェクトの衝突や接触などの相互作用を決定して表現する必要がある。特に、CAD/CAMにより製品のデザインを設計する場合、各部品同士または製造工具との干渉状態を認識するために、オブジェクト間の最短距離を算出する必要がある。
各オブジェクトのフェースが所定の数式で表現されているような場合には、この数式を解析してオブジェクト間の最短距離を算出するように構成することができる。
【０００３】
また、各オブジェクトを多面体（polyhedron）と想定し、この多面体を構成する簡易形状要素に分解し、各要素の位置情報に基づいて最短距離を求めるように構成することができる。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
各オブジェクトのフェースを表現している数式を解析して最短距離を求める場合には、収束演算などを用いる必要があるために、演算に多大な時間を要するという問題を内包している。
各オブジェクトを簡易形状要素に分解する場合には、多面体を構成する三角形ポリゴンの位置情報に基づいて、各オブジェクトを構成するポリゴンの最短距離を逐次的に求めることが行われる。
【０００５】
三角形ポリゴンは、要素の境界を示すエッジ（edge）、エッジの端部対を構成する頂点（vertex）、要素の面を表すフェース（face）で構成されている。この三角形ポリゴンは、幾何学的に連続性がある状態で分割され、その要素データはその連続性に基づく順で整列されていることが一般的である。
通常、このようなポリゴンデータをその整列順で読み出して最短距離の算出を行っているため、その処理に多大な時間を要する。
【０００６】
本発明では、複数の要素で構成されるオブジェクト間の最短距離を取得するための処理時間を短縮することを目的とする。
【課題を解決するための手段】
【０００７】
本発明に係るオブジェクト間の最短距離取得方法は、コンピュータグラフィックス処理において、複数の要素で構成されるオブジェクトと所定点との最短距離を取得するためのオブジェクト間の最短距離取得方法であって、Ａ）最短距離Ｄminを初期値に設定する段階と、Ｂ）オブジェクトを構成する複数の要素の幾何学的連続性を有する配列順の配列に対して、幾何学的連続性を有さない読出順に基づいて対象要素を決定し、対象要素の位置情報を読み出す段階と、Ｃ）対象要素の位置情報に基づいて、対象要素と所定点との距離を簡易判定して、簡易判定距離Ｄrghに設定する段階と、Ｄ）簡易判定距離Ｄrghと最短距離Ｄminとを比較し、簡易判定距離Ｄrghが最短距離Ｄminを超えている場合にはＢ段階に移行し、簡易判定距離Ｄrghが最短距離Ｄmin以下である場合には、対象要素の位置情報に基づいて対象要素と所定点との距離を詳細判定し要素距離Ｄobjに設定する段階と、Ｅ）要素距離Ｄobjと最短距離Ｄminとを比較し、要素距離Ｄobjが最短距離Ｄminを超えている場合にはＢ段階に移行し、要素距離Ｄobjが最短距離Ｄmin以下である場合には、要素距離Ｄobjを最短距離Ｄminに代入する段階と、Ｆ）オブジェクトを構成する複数の要素のうち対象要素になっていないものがある場合にはＢ段階に移行し、全ての要素が対象要素になったと判断される場合には処理を終了する段階とを含む。
【０００８】
ここで、Ｂ段階は、オブジェクトを構成する要素数Ｎの要素の幾何学的な連続性を考慮した所定配列順（１〜Ｎ）に対して、所定数ａおきに対象要素となるような読出順を処理順テーブルとして記憶し、処理順テーブルを参照することにより対象要素を決定して対象要素の位置情報を読み出すように構成できる。
また、本発明の他の観点に係るオブジェクト間の最短距離取得方法は、コンピュータのグラフィックス処理において、複数の要素で構成される第１オブジェクトおよび第２オブジェクトの最短距離を取得するためのオブジェクト間の最短距離取得方法であって、Ａ）最短距離Ｄminを初期値に設定する段階と、Ｂ）第１オブジェクトを構成する所定要素数の要素の幾何学的な連続性を考慮した所定配列順に対して、所定数おきに対象要素となるような読出順を第１処理順テーブルとして記憶し、第１処理順テーブルを参照することにより第１対象要素を決定して第１対象要素の位置情報を読み出す段階と、Ｃ）第２オブジェクトを構成する所定要素数の要素の幾何学的な連続性を考慮した所定配列順に対して、所定数おきに対象要素となるような読出順を第２処理テーブルとして記憶し、第２処理順テーブルを参照することにより第２対象要素を決定して第２対象要素の位置情報を読み出す段階と、Ｄ）第１対象要素および第２対象要素の位置情報に基づいて、第１対象要素と第２対象要素の距離を簡易判定して、簡易判定距離Ｄrghに設定する段階と、Ｅ）簡易判定距離Ｄrghと最短距離Ｄminとを比較し、簡易判定距離Ｄrghが最短距離Ｄminを超えている場合にはＣ段階に移行し、簡易判定距離Ｄrghが最短距離Ｄmin以下である場合には、第１対象要素と第２対象要素の位置情報に基づいて第１対象要素と第２対象要素の距離を詳細判定し要素距離Ｄobjに設定する段階と、Ｆ）要素距離Ｄobjと最短距離Ｄminとを比較し、要素距離Ｄobjが最短距離Ｄminを超えている場合にはＣ段階に移行し、要素距離Ｄobjが最短距離Ｄmin以下である場合には、要素距離Ｄobjを最短距離Ｄminに代入する段階と、Ｇ）第２オブジェクトを構成する複数の要素のうち第２対象要素になっていないものがある場合にはＣ段階に移行し、全ての要素が第２対象要素になったと判断される場合にはＨ段階に移行する段階と、Ｈ）第１オブジェクトを構成する複数の要素のうち第１対象要素になっていないものがある場合にはＢ段階に移行し、全ての要素が第１対象要素になったと判断される場合には処理を終了する段階とを含む。
【０００９】
また、本発明に係るプログラムは、複数の要素で構成されるオブジェクトと所定点との最短距離を取得するためのオブジェクト間の最短距離取得方法をコンピュータに行わせるプログラムであって、Ａ）最短距離Ｄminを初期値に設定する段階と、Ｂ）オブジェクトを構成する複数の要素の幾何学的連続性を有する配列順の配列に対して、幾何学的連続性を有さない読出順に基づいて対象要素を決定し、対象要素の位置情報を読み出す段階と、Ｃ）対象要素の位置情報に基づいて、対象要素と所定点との距離を簡易判定して、簡易判定距離Ｄrghに設定する段階と、Ｄ）簡易判定距離Ｄrghと最短距離Ｄminとを比較し、簡易判定距離Ｄrghが最短距離Ｄminを超えている場合にはＢ段階に移行し、簡易判定距離Ｄrghが最短距離Ｄmin以下である場合には、対象要素の位置情報に基づいて対象要素と所定点との距離を詳細判定し要素距離Ｄobjに設定する段階と、Ｅ）要素距離Ｄobjと最短距離Ｄminとを比較し、要素距離Ｄobjが最短距離Ｄminを超えている場合にはＢ段階に移行し、要素距離Ｄobjが最短距離Ｄmin以下である場合には、要素距離Ｄobjを最短距離Ｄminに代入する段階と、Ｆ）オブジェクトを構成する複数の要素のうち対象要素になっていないものがある場合にはＢ段階に移行し、全ての要素が対象要素になったと判断される場合には処理を終了する段階とを含むオブジェクト間の最短距離取得方法をコンピュータに実行させるためのプログラムである。
【００１０】
さらに、本発明の他の観点によるプログラムは、複数の要素で構成される第１オブジェクトおよび第２オブジェクトの最短距離を取得するためのオブジェクト間の最短距離取得方法をコンピュータに行わせるプログラムであって、Ａ）最短距離Ｄminを初期値に設定する段階と、Ｂ）第１オブジェクトを構成する所定要素数の要素の幾何学的な連続性を考慮した所定配列順に対して、所定数おきに対象要素となるような読出順を第１処理順テーブルとして記憶し、第１処理順テーブルを参照することにより第１対象要素を決定して第１対象要素の位置情報を読み出す段階と、Ｃ）第２オブジェクトを構成する所定要素数の要素の幾何学的な連続性を考慮した所定配列順に対して、所定数おきに対象要素となるような読出順を第２処理テーブルとして記憶し、第２処理順テーブルを参照することにより第２対象要素を決定して第２対象要素の位置情報を読み出す段階と、Ｄ）第１対象要素および第２対象要素の位置情報に基づいて、第１対象要素と第２対象要素の距離を簡易判定して、簡易判定距離Ｄrghに設定する段階と、Ｅ）簡易判定距離Ｄrghと最短距離Ｄminとを比較し、簡易判定距離Ｄrghが最短距離Ｄminを超えている場合にはＣ段階に移行し、簡易判定距離Ｄrghが最短距離Ｄmin以下である場合には、第１対象要素と第２対象要素の位置情報に基づいて第１対象要素と第２対象要素の距離を詳細判定し要素距離Ｄobjに設定する段階と、Ｆ）要素距離Ｄobjと最短距離Ｄminとを比較し、要素距離Ｄobjが最短距離Ｄminを超えている場合にはＣ段階に移行し、要素距離Ｄobjが最短距離Ｄmin以下である場合には、要素距離Ｄobjを最短距離Ｄminに代入する段階と、Ｇ）第２オブジェクトを構成する複数の要素のうち第２対象要素になっていないものがある場合にはＣ段階に移行し、全ての要素が第２対象要素になったと判断される場合にはＨ段階に移行する段階と、Ｈ）第１オブジェクトを構成する複数の要素のうち第１対象要素になっていないものがある場合にはＢ段階に移行し、全ての要素が第１対象要素になったと判断される場合には処理を終了する段階とを含むオブジェクト間の最短距離取得方法をコンピュータに実行させるためのプログラムである。
【発明の効果】
【００１１】
本発明によれば、オブジェクト間の最短距離を取得する際に、詳細な距離測定の処理回数を減少することができ、最短距離の取得処理を高速に行うことを可能とする。
【発明を実施するための最良の形態】
【００１２】
本発明に係るオブジェクト間の最短距離取得方法は、CAD/CAMやCGなどのグラフィックス処理を行うコンピュータのアプリケーションの一部として搭載されるものであり、その１実施形態を以下に説明する。
図１に示すように、第１オブジェクト１０と第２オブジェクト２０の最短距離を取得する場合について考える。
【００１３】
図示した第１オブジェクト１０および第２オブジェクト２０は、それぞれポリゴン平面が連続した多面体で構成されている。第１オブジェクト１０は、三角形ポリゴンでなる第１要素１０１、第２要素１０２、第３要素１０３・・・を備えており、同様にして、第２オブジェクト２０も三角形ポリゴンである第１要素２０１、第２要素２０２、第３要素２０３・・・で構成されているものとする。
【００１４】
第１オブジェクト１０の第１要素１０１、第２要素１０２、第３要素１０３・・・の位置情報は、幾何学的な連続性を考慮して所定の配列順で整列されており、たとえば、図１の最も左下に位置する第１要素１０１から隣接する要素が順次整列するようにデータ配列が構成される。また、同様に第２オブジェクト２０の第１要素２０１、第２要素２０２、第３要素２０３・・・の位置情報も幾何学的な連続性を考慮して所定の配列順で整列されており、たとえば、図１の最も右上に位置する第１要素２０１から隣接する要素が順次整列するようにデータ配列が構成される。
【００１５】
このような第１オブジェクト１０と第２オブジェクト２０の最短距離を取得するためには、たとえば、第２オブジェクト２０の第１要素２０１から第１オブジェクト１０までの距離を第１オブジェクト１０の各要素の配列順に算出していき、最短となるものをオブジェクト間の暫定的な最短距離とする。さらに、第２オブジェクト２０の次の要素である第２要素２０２から第２オブジェクト１０までの距離を第１オブジェクト１０の各要素の配列順に算出していき、暫定的な最短距離よりも小さい値のものがあれば逐次データの更新を行う。
【００１６】
このようにして第２オブジェクト２０の最終要素まで処理を実行し、得られた最短距離を第１オブジェクト１０と第２オブジェクト２０との最短距離とする。
ここで、説明を簡略化するために、所定点とオブジェクトとの最短距離を求める場合について考察する。
図２に示すように、第１オブジェクト１０は、図１と同様に、第１要素１０１、第２要素１０２、第３要素１０３・・・で構成されており、第２オブジェクト上の所定点２１から第１オブジェクト１０までの最短距離を取得する場合を考える。
【００１７】
このような所定点２１から第１オブジェクト１０までの最短距離取得方法の従来例を図３のフローチャートに示す。
ステップＳ１１では、最短距離Ｄminを所定の最大値に設定する。ここでは、計算に用いる変数の桁数に対応した最大値を既定値として設定することができ、たとえば、1.0E+38とすることができる。
【００１８】
ステップＳ１２では、所定点２１から現在対象となっている第ｉ番目の要素１００（ｉ）までの簡易判定距離Ｄrghを取得する。
第１オブジェクト１０の第ｉ要素１００（ｉ）が、図４に示すように、３つの頂点V1（x1,y2,z3），V2（x2,y2,z2），V3（x3,y3,z3）を備える場合、最大領域座標Vmax（xmax,ymax,zmax）および最小領域座標Vmin（xmin,ymin,zmin）と所定点２１との距離を算出し、いずれか小さいものを簡易判定距離Ｄrghとする。
【００１９】
ステップＳ１３では、簡易判定距離Ｄrghが最短距離Ｄminを超えているか否かを判別する。簡易判定距離Ｄrghが最短距離Ｄminを超えていると判断した場合にはステップＳ１２に移行し、簡易判定距離Ｄrghが最短距離Ｄmin以下であると判断した場合にはステップＳ１４に移行する。
ステップＳ１４では、所定点２１と第ｉ要素１００（ｉ）との詳細な距離を算出して、所定点２１と第ｉ要素１００（ｉ）との要素距離Ｄobjを取得する。ここで、所定点２１と第ｉ要素１００（ｉ）との距離を取得する方法は、種々提案されている方法を用いて処理するものであり、ここではその詳細については言及しない。
【００２０】
ステップＳ１５では、要素距離Ｄobjが最短距離Ｄminより小さいか否かを判別する。要素距離Ｄobjが最短距離Ｄminより小さいと判断した場合にはステップＳ１６に移行し、要素距離Ｄobjが最短距離Ｄobj以上であると判断した場合にはステップＳ１２に移行する。
ステップＳ１６では、要素距離Ｄobjの値を最短距離Ｄminに代入して、最短距離Ｄminのデータを更新する。
【００２１】
ステップＳ１７では、第１オブジェクト１０の全ての要素について処理を実行したか否かを判断する。第１オブジェクト１０の要素のうち処理が実行されていない要素があると判断した場合には、変数ｉをインクリメントして次の要素について同様の処理を実行する。
このように、第１オブジェクト１０の各要素の配列順に処理を実行した場合には、全ての要素について詳細な距離算出の処理を実行しなければならない場合が生じる。
【００２２】
たとえば、図５に示すように、第１オブジェクト１０の各要素のうち筆頭に配列されている第１要素１０１までの距離が最短であるような場合には、詳細な距離測定は、最初の第１要素１０１についてのみ処理することだけでよい。
しかしながら、図６に示すように、第１オブジェクト１０の各要素のうち筆頭に配列されている第１要素１０１までの距離が最大であり、各要素の距離が配列順に順次短くなるような場合には、全ての要素について詳細な距離測定を行う必要がある。
【００２３】
また、図７に示すように、第５要素１０５までの距離が最短となる場合と、図８に示すように、第１０要素１１０までの距離が最短となる場合とでは、詳細な距離測定の処理回数が異なってくる。
このような従来の逐次距離取得により図５〜図８の各モデルについて最短距離の取得を行った場合の処理回数を表１に示す。
【００２４】
【表１】
2008021329.tif 000003
【００２５】
このような逐次距離取得の方法における詳細な距離測定の処理回数の平均値は、第１オブジェクト１０の要素数をＮとした場合、(N/2)*K1で表すことができる。ここで、K1は、第１オブジェクト１０の形状のタイプや形状の複雑さに応じて決定される係数である。
本発明に係るオブジェクト間の最短距離取得方法のフローチャートを図９に示す。
ステップＳ２１では、最短距離Ｄminを既定の最大値に設定する。前述と同様にして、計算に用いる変数の桁数に対応した最大値を既定値として設定することができ、たとえば、1.0E+38とすることができる。
【００２６】
ステップＳ２２では、第１オブジェクト１０のうちの各要素について、処理順を決定するための処理順テーブルNoTblを作成する。処理順テーブルNoTblの作成は、たとえば、第１オブジェクト１０の各要素の配列順に対して２以上の所定数おきに処理を行うように処理順テーブルNoTblを設定することが可能であり、また、第１オブジェクト１０の各要素（１〜Ｎ）の配列順に対して第１要素、第Ｎ要素、第N/2要素、第N/4要素、第3N/4要素・・・のように２分割位置を順次処理するように処理順テーブルNoTblを設定することができる。
【００２７】
ステップＳ２３では、処理順テーブルNoTblを参照して処理を実行する要素番号no＝NoTbl（ｉ）を取得する。
ステップＳ２４では、所定点２１と現在対象となっている第no要素の簡易判定距離Ｄrghを取得する。前述と同様にして、図４の最大領域座標Vmax（xmax,ymax,zmax）および最小領域座標Vmin（xmin,ymin,zmin）と所定点２１との距離を算出し、いずれか小さいものを簡易判定距離Ｄrghとすることができる。
【００２８】
ステップＳ２５では、簡易判定距離Ｄrghが最短距離Ｄminを超えているか否かを判別する。簡易判定距離Ｄrghが最短距離Ｄminを超えていると判断した場合にはステップＳ２３に移行し、簡易判定距離Ｄrghが最短距離Ｄmin以下であると判断した場合にはステップＳ２６に移行する。
ステップＳ２６では、所定点２１と第no要素１００（no）との詳細な距離を算出して、所定点２１と第no要素１００（no）との要素距離Ｄobjを取得する。
【００２９】
ステップＳ２７では、要素距離Ｄobjが最短距離Ｄminより小さいか否かを判別する。要素距離Ｄobjが最短距離Ｄminより小さいと判断した場合にはステップＳ２８に移行し、要素距離Ｄobjが最短距離Ｄobj以上であると判断した場合にはステップＳ２３に移行する。
ステップＳ２８では、要素距離Ｄobjの値を最短距離Ｄminに代入して、最短距離Ｄminのデータを更新する。
【００３０】
ステップＳ２９では、第１オブジェクト１０の全ての要素について処理を実行したか否かを判断する。第１オブジェクト１０の要素のうち処理が実行されていない要素があると判断した場合には、変数ｉをインクリメントして次の要素について同様の処理を実行する。
処理順テーブルNoTblは、第１オブジェクト１０の各要素の配列順に対して所定数おきに処理を実行するように設定することができる。たとえば、図５〜図８に示すような第１要素１０１〜第１５要素１１５が配列される第１オブジェクト１０に対して５つおきに処理を実行する場合、図１０に示すような処理順テーブルNoTblを設定することができる。この場合、第１要素１０１から初めて５つおきに要素を並べていき、次に５つ先の要素が最終要素を超えるような場合には第２要素１０２に戻ってそこから５つおきに要素を配列している。
【００３１】
５つおきに処理順テーブルNoTblを設定した場合に、図５〜図８のモデルを実行した場合のそれぞれの処理回数を表２に示す。
【００３２】
【表２】
2008021329.tif 000004
【００３３】
このような所定数おきに処理順テーブルNoTblを設定した場合における詳細な距離測定の処理回数は、第１オブジェクト１０の要素数をＮとし所定数をＭとした場合、その最大値が（N/M+M)*K2で表すことができる。ここで、K2は、第１オブジェクト１０の形状のタイプや形状の複雑さに応じて決定される係数である。
このように、所定数おきに処理順テーブルNoTblを設定し、この処理順テーブルNoTblに沿って処理を実行することにより、詳細な距離測定の処理回数を減らすことが可能となり、処理の高速化を図ることができる。
【００３４】
処理順テーブルNoTblは、第１オブジェクト１０の各要素の配列順に対して、第１要素、第Ｎ要素、第(1+N)/2要素・・・の順で、２分割毎に設定することが可能である。
たとえば、図５〜図８に示すような第１要素１０１〜第１５要素１１５が配列される第１オブジェクト１０に対して、第１要素１０１、第１５要素１１５（Ｎ）を処理した後、第８要素１０８（(1+N)/2）の処理を実行し、さらに、第４要素１０４（(1+N)/4）、第１２要素（3(1+N)/4）の処理を実行し、その後の処理は元々の配列順に処理を行うように設定することができる。
【００３５】
このような２分割順と逐次処理を組み合わせた処理順テーブルNoTblを設定した場合に、図５〜図８のモデルを実行した場合のそれぞれの処理回数を表３に示す。
【００３６】
【表３】
2008021329.tif 000005
【００３７】
２分割順を含む処理順テーブルNoTblの作成方法について、図１２〜図１５に基づいて説明する。
処理順テーブルNoTblに含まれる各要素のデータは、リンクリスト構造を使用して記述される。処理順テーブルNoTblを構成する各データ格納部３００（１）〜３００（Ｎ）は、それぞれＩＤ格納部３０１とNEXTポインタ３０２とを備えている。ＩＤ格納部３０１には、第１オブジェクト１０の要素番号が格納され、NEXTポインタ３０２には次に処理を実行する要素のデータアドレスが格納される。最終のデータ格納部３００（Ｎ）のNEXTポインタ３０２（Ｎ）には"END"が格納される。
【００３８】
第１オブジェクト１０の要素数Ｎが１７の場合について考察する。まず、図１３に示すように、第１オブジェクト１０の第１要素（最初）と第１７要素（最終）のデータを設定し、第１要素のNEXTポインタ３０２に第１７要素のデータアドレスを格納し、第１７要素のNEXTポインタに"END"を格納する。このことにより、処理順テーブルNoTblに、第１要素、第１７要素の処理順がセットされる。
【００３９】
次に、第１要素および第１７要素の中間に位置する第９要素のデータを挿入する。ここでは、第１要素のNEXTポインタ３０２を第９要素のデータアドレスに更新し、第９要素のNEXTポインタ３０２には第１７要素のデータアドレスを格納する。このことにより、図１４に示すように、処理順テーブルNoTblに、第１要素、第９要素、第１７要素の処理順がセットされる。
【００４０】
さらに、各要素間の中間に位置する要素のデータを挿入する。ここでは、第１要素と第９要素の間に第５要素を挿入し、第９要素と第１７要素との間に第１３要素を挿入する。各要素のNEXTポインタ３０２を更新することにより、図１５に示すような各要素の処理順が処理順テーブルNoTblにセットされる。
このようにして、隣り合う要素の要素番号の差が１になるまで、データの挿入を繰り返すことで、処理順テーブルNoTblを設定することができる。このときの各要素の決定順を表４に示す。
【００４１】
【表４】
2008021329.tif 000006
【００４２】
このようにして決定された処理順テーブルNoTblを用いて最短距離の取得処理を実行した場合の詳細な距離測定の処理回数を表５に示す。
【００４３】
【表５】
2008021329.tif 000007
【００４４】
ここでは、処理順テーブルNoTblの処理順を横軸に示し、所定点２１（検査点）から最も近い要素が第２要素、第４要素、第６要素、第８要素、第１０要素、第１２要素、第１４要素、第１６要素のそれぞれについて詳細な距離測定の回数を算出している。ただし、所定点２１に最も近い要素が第２要素、第４要素であるものについて次に近い要素が第３要素である場合、所定点２１に最も近い要素が第６要素、第８要素であるものについて次に近い要素が第７要素である場合、所定点２１に最も近い要素が第１０要素、第１２要素であるものについて次に近い要素が第１１要素である場合、所定点２１に最も近い要素が第１４要素、第１６要素であるものについて次に近い要素が第１５要素である場合について考察している。
【００４５】
このように、処理順テーブルNoTblが２分割順のみで構成され逐次順を含まない場合の距離計算回数の最大値は、（log2N＋２〜３）*K3で表すことができる。ここで、K3は、第１オブジェクト１０の形状のタイプや形状の複雑さに応じて決定される係数である
以上のようにして、所定点２１と第１オブジェクト１０との最短距離を算出することにより、従来の逐次詳細な距離測定の処理を実行する場合に比して、処理時間を大幅に短縮することが可能となる。
【００４６】
第２オブジェクト２０を構成する複数の要素２０１，２０２，２０３・・・のそれぞれについて、同様の方法を用いて第１オブジェクト１０までの最短距離を求めることにより、第１オブジェクト１０と第２オブジェクト２０との間の最短距離を取得することが可能であり、この場合にも処理時間を大幅に短縮することが可能となる。
このような第１オブジェクト１０と第２オブジェクト２０との最短距離を取得する方法について、図１６のフローチャートに基づいて説明する。
【００４７】
ステップＳ３１では、最短距離Ｄminを既定の最大値に設定する。前述と同様にして、計算に用いる変数の桁数に対応した最大値を既定値として設定することができ、たとえば、1.0E+38とすることができる。
ステップＳ３２では、第１オブジェクト１０のうちの各要素について処理順を決定するための処理順テーブルNoTbl1および第２オブジェクトのうちの各要素について処理順を決定するための処理順テーブルNoTbl2を作成する。処理順テーブルNoTbl1，NoTbl2の作成は、前述の処理順テーブルNoTblと同様に設定することができる。
【００４８】
ステップＳ３３では、処理順テーブルNoTbl1，NoTbl2を参照して処理を実行する要素番号no1＝NoTbl1（i1），no2＝NoTbl2（i2）を取得する。
ステップＳ３４では、第１オブジェクト１０および第２オブジェクト２０のそれぞれ現在対象となっている要素番号no1および要素番号no2の簡易判定距離Ｄrghを取得する。前述と同様にして、各要素の最大領域座標Vmax（xmax,ymax,zmax）および最小領域座標Vmin（xmin,ymin,zmin）に基づいて簡易判定距離Ｄrghを算出する。
【００４９】
ステップＳ３５では、簡易判定距離Ｄrghが最短距離Ｄminを超えているか否かを判別する。簡易判定距離Ｄrghが最短距離Ｄminを超えていると判断した場合にはステップＳ３３に移行し、簡易判定距離Ｄrghが最短距離Ｄmin以下であると判断した場合にはステップＳ３６に移行する。
ステップＳ３６では、第１オブジェクト１０の第no1要素１００（no1）と第２オブジェクト２０の第no2要素２００（no2）の詳細な距離を算出して、第no1要素１００（no1）と第no2要素２００（no2）との要素距離Ｄobjを取得する。
【００５０】
ステップＳ３７では、要素距離Ｄobjが最短距離Ｄminより小さいか否かを判別する。要素距離Ｄobjが最短距離Ｄminより小さいと判断した場合にはステップＳ３８に移行し、要素距離Ｄobjが最短距離Ｄobj以上であると判断した場合にはステップＳ３３に移行する。
ステップＳ３８では、要素距離Ｄobjの値を最短距離Ｄminに代入して、最短距離Ｄminのデータを更新する。
【００５１】
ステップＳ３９では、第２オブジェクト２０の全ての要素について処理を実行したか否かを判断する。第２オブジェクト２０の要素のうち処理が実行されていない要素があると判断した場合には、変数i2をインクリメントして次の要素について同様の処理を実行する。また、第２オブジェクト２０の要素の全てについて処理を実行したと判断した場合にはステップＳ４０に移行する。
【００５２】
ステップＳ４０では、第１オブジェクト１０の全ての要素について処理を実行した否かを判断する。第１オブジェクト１０の要素のうち処理が実行されていない要素があると判断した場合には、変数i1をインクリメントするとともに変数i2を初期値に設定し、次の要素について同様の処理を実行する。第１オブジェクト１０の全ての要素について処理が完了したと判断した場合には、この処理ルーチンを終了し、現在の最短距離Ｄminの値を第１オブジェクト１０と第２オブジェクト２０の最短距離として出力する。
【産業上の利用可能性】
【００５３】
本発明によれば、オブジェクト間の最短距離を取得する際に、詳細な距離測定の処理回数を減少することができ、最短距離の取得処理を高速に行うことを可能とし、特に、コンピュータグラフィックス処理において、複数の要素で構成されるオブジェクトと所定点との最短距離または複数のオブジェクト間の最短距離を取得するために利用することができる。
【図面の簡単な説明】
【００５４】
【図１】本発明に係るオブジェクト間の最短距離取得方法が採用されるモデルの例を示す説明図。
【図２】本発明に係るオブジェクト間の最短距離取得方法が採用されるモデルの例を示す説明図。
【図３】従来手法のフローチャート。
【図４】簡易判定処理の説明図。
【図５】本発明に係るオブジェクト間の最短距離取得方法が採用されるモデルの例を示す説明図。
【図６】本発明に係るオブジェクト間の最短距離取得方法が採用されるモデルの例を示す説明図。
【図７】本発明に係るオブジェクト間の最短距離取得方法が採用されるモデルの例を示す説明図。
【図８】本発明に係るオブジェクト間の最短距離取得方法が採用されるモデルの例を示す説明図。
【図９】本発明の１実施形態によるフローチャート。
【図１０】処理順テーブルの一例を示す説明図。
【図１１】処理順テーブルの一例を示す説明図。
【図１２】リンクリスト構造の説明図。
【図１３】２分割順による処理順テーブルの作成過程を示す説明図。
【図１４】２分割順による処理順テーブルの作成過程を示す説明図。
【図１５】２分割順による処理順テーブルの作成過程を示す説明図。
【図１６】ポリゴン間の最短距離を取得する方法のフローチャート。
【図１】
2008021329.tif 000008
【図２】
2008021329.tif 000009
【図３】
2008021329.tif 000010
【図４】
2008021329.tif 000011
【図５】
2008021329.tif 000012
【図６】
2008021329.tif 000013
【図７】
2008021329.tif 000014
【図８】
2008021329.tif 000015
【図９】
2008021329.tif 000016
【図１０】
2008021329.tif 000017
【図１１】
2008021329.tif 000018
【図１２】
2008021329.tif 000019
【図１３】
2008021329.tif 000020
【図１４】
2008021329.tif 000021
【図１５】
2008021329.tif 000022
【図１６】
2008021329.tif 000023