(57)【要約】【課題】  格子状データでないテーブルデータに対して高速に４面体補間処理を行う。【解決手段】  ４面体補間を行うべく読み込んだデータの存在範囲を、補間前テーブルに格納されているデータのある特定の範囲内に指定し、指定された範囲内で読み込んだデータを４面体補間する。【選択図】  図４
2006119883.tif 000002
【特許請求の範囲】
【請求項１】
データ入力部、各軸最大値・最小値算出部、読み込みデータ存在範囲算出部、四面体補間部、テーブル作成部、補間前テーブル、補間後テーブル、各軸最大値・最小値記憶部からなり、
前記読み込みデータ存在範囲算出部は、四面体補間を行うべく読み込んだデータの存在範囲を、前記補間前テーブルに格納されているデータのある特定の範囲内に指定し、
前記四面体補間部は、前記読み込みデータ存在範囲算出部において、指定された範囲内で四面体補間を行うべく読み込んだデータを四面体補間することを特徴とする四面体補間装置。
【請求項２】
データ入力工程、各軸最大値・最小値算出工程、読み込みデータ存在範囲算出工程、四面体補間工程、テーブル作成工程、補間前テーブル、補間後テーブル、各軸最大値・最小値記憶工程からなり、
前記読み込みデータ存在範囲算出工程は、四面体補間を行うべく読み込んだデータの存在範囲を、前記補間前テーブルに格納されているデータのある特定の範囲内に指定し、
前記四面体補間工程は、前記読み込みデータ存在範囲算出工程において指定された範囲内で、四面体補間を行うべく読み込んだデータを四面体補間することを特徴とする四面体補間方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、補間前のテーブルデータが格子状データでないとき、高速に四面体補間を行う方法に関する。
【背景技術】
【０００２】
四面体補間を行う際に、補間前のテーブルデータが図２のように格子状になっている場合、補間を行うべき点のデータが補間前のテーブルで形成される空間内の、どの位置にくるのかが瞬時に分かる。したがって、高速に処理することが出来る。
【０００３】
一方、補間前のテーブルデータが図３のように格子状になっていない場合、補間を行うべき点のデータが補間前のテーブルで形成される空間内の、その位置にくるかが瞬時には分からず、総当りで四面体内部か、外部かを調べる必要があり、高速に処理できなかった。
【特許文献１】特公昭５８−１６１８０号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
以上のことを鑑みて本発明では、補間を行いたいデータの値から、テーブルデータの値の範囲をある程度指定することで、四面体補間を行う際に補間前のテーブルデータが格子状データでないときでも、総当りで四面体内部か、外部かを判定すること無く、高速に四面体補間処理を行える装置、および方法を提供することを目的とする。
【課題を解決するための手段】
【０００５】
上記目的を達成するために本発明は、データ入力部、各軸最大値・最小値算出部、読み込みデータ存在範囲算出部、四面体補間部、テーブル作成部、補間前テーブル、補間後テーブル、各軸最大値・最小値記憶部からなり、前記読み込みデータ存在範囲算出部は、四面体補間を行うべく読み込んだデータの存在範囲を、前記補間前テーブルに格納されているデータのある特定の範囲内に指定し、前記四面体補間部は、前記読み込みデータ存在範囲算出部において、指定された範囲内で四面体補間を行うべく読み込んだデータを四面体補間することを特徴とする。
【発明の効果】
【０００６】
本発明によれば、四面体補間を行う際に、補間前のテーブルデータが格子状となっていなくても、総当りで四面体内部か外部かを調べることなく、高速に補間を行うことが出来る。
【発明を実施するための最良の形態】
【０００７】
（実施例１）
＜構成＞
図１に装置の構成を示す。
【０００８】
この装置は、データ入力部１、各軸最大値・最小値算出部２、読み込みデータ存在範囲算出部３、四面体補間部４、テーブル作成部５、補間前テーブル６、補間後テーブル７、各軸最大値・最小値記憶部８、データ出力部９から構成される。
【０００９】
＜説明＞
データ入力部１は、四面体補間を行いたいデータを読み込む。
【００１０】
各軸最大値・最小値算出部２は、補間前テーブル６に格納されているテーブルデータをもとに、各軸の最大値・最小値を求める。結果を各軸最大値・最小値記憶部８に格納する。
【００１１】
読み込みデータ存在範囲算出部３は、先に求めた各軸の最大値、最小値から、データ入力部１から読み込んだデータの存在範囲を求める。
【００１２】
四面体補間部４は、先に求めた存在範囲内で、四面体補間を行う。四面体補間が出来ない場合もある。
【００１３】
テーブル作成部５は、補間前データ、および補間後データを補間前テーブル６および補間後テーブル７にそれぞれ格納する。
【００１４】
補間前テーブル６は、補間前テーブルデータを格納する。データ事態は、ＤＡＴＡ［ｘ３］［ｙ３］［ｚ３］という形式で、各データｘ値、ｙ値、ｚ値を持っている。以下、ｘ値をＤＡＴＡ［ｘ３］［ｙ３］［ｚ３］．ｘとしめす。また、ｘ３、ｙ３、ｚ３は、各々０以上８以下の整数である。
【００１５】
補間後テーブル７は、補間後テーブルデータを格納する。
【００１６】
各軸最大値・最小値記憶部８は、各軸最大値・最小値算出部２で算出したデータを格納する。
【００１７】
データ出力部９は、四面体補間を行った後のデータを出力する。
【００１８】
以下、発明の実施の形態を、具体例を用いて詳細に説明する。
【００１９】
＜本実施例における装置の動作の説明＞
図４に装置の動作について示す。
【００２０】
ステップＳ１１において、データ入力部１から、補間前の点のデータＰｏｉｎｔを読み込む。Ｐｏｉｎｔは、ｘ、ｙ、ｚの３つの値を持っている。以下、Ｐｏｉｎｔ．ｘ、Ｐｏｉｎｔ．ｙ、Ｐｏｉｎｔ．ｚと記述する。
【００２１】
ステップＳ１２において、各軸最大値・最小値算出部２において、補間前テーブル６内のデータから各軸の最大値・最小値を求める。結果を各軸最大値・最小値記憶部８に格納する。各軸最大値・最小値算出部２の動作の詳細を図５〜６に示す。
【００２２】
ステップＳ１３において、読み込みデータ存在範囲算出部３において、データ入力部１から読み込んだデータの存在範囲を求める。読み込みデータ存在範囲算出部３の動作の詳細を図７〜８に示す。
【００２３】
ステップＳ１４において、四面体補間部４において、先に求めた範囲内で四面体補間を行う。四面体補間部４の動作の詳細を図９に示す。
【００２４】
ステップＳ１５において、データ出力部５において、補間後の点のデータＰｏｉｎｔ’を出力する。
【００２５】
＜各軸最大値・最小値記憶部８の動作＞
図５〜６は各軸最大値・最小値記憶部８の動作を詳細に示したものである。
【００２６】
ステップＳ２１において、各軸最大値・最小値記憶部８に格納されているＭａｘＸ［ｘ］、ＭｉｎＸ［ｘ］、ＭａｘＹ［ｙ］、ＭｉｎＹ［ｙ］、ＭａｘＺ［ｚ］、ＭｉｎＺ［ｚ］を初期化する。ｘ、ｙ、ｚはそれぞれ０から８までの整数であるとする。
【００２７】
ステップＳ２２において、補間前テーブル６から、ＤＡＴＡ［ｘ３］［ｙ３］［ｚ３］を読み込む。ｘ３、ｙ３、ｚ３はそれぞれ０から８までの整数であるとする。つまり、このテーブルには合計９×９×９＝７２９個のデータが存在する。
【００２８】
ステップＳ２３において、各軸最大値・最小値記憶部８に格納されているＭｉｎＸ［ｘ］、ＭａｘＸ［ｘ］を更新する。動作の詳細を図６に示す。
【００２９】
ステップＳ２４において、各軸最大値・最小値記憶部８に格納されているＭｉｎＹ［ｙ］、ＭａｘＹ［ｙ］を更新する。動作の詳細は図６においてＭａｎＸ［ｘ］をＭａｘＹ［ｙ］に、ＭｉｎＸ［ｘ］をＭｉｎＹ［ｙ］に、ＤＡＴＡ［ｘ３］［ｙ３］［ｚ３］．ｘをＤＡＴＡ［ｘ３］［ｙ３］［ｚ３］．ｙにそれぞれ変更したものと同じである。
【００３０】
ステップＳ２５において、各軸最大値・最小値記憶部８に格納されているＭｉｎＺ［ｚ］、ＭａｘＺ［ｚ］を更新する。動作の詳細は図６においてＭａｘＸ［ｘ］をＭａｘＺ［ｚ］に、ＭｉｎＸ［ｘ］をＭｉｎＺ［ｚ］に、ＤＡＴＡ［ｘ３］［ｙ３］［ｚ３］．ｘをＤＡＴＡ［ｘ３］［ｙ３］［ｚ３］．ｚにそれぞれ変更したものと同じである。
【００３１】
ステップＳ２６において、全データ終了したかを調べる。もし全データ終了していれば、処理終了。まだデータが残っていれば、ステップＳ２１に戻る。
【００３２】
次に図６について詳細に説明する。
【００３３】
ステップＳ３１において、ＭａｘＸ［ｘ］と、補間前テーブルのデータのｘ値ＤＡＴＡ［ｘ３］［ｘｙ］［ｚ３］．ｘを比較する。ＭａｘＸ［ｘ］＜ＤＡＴＡ［ｘ３］［ｙ３］［ｚ３］．ｘのときは、ステップＳ３２に進む。それ以外の時は、ステップＳ３３に進む。
【００３４】
ステップＳ３２において、ＭａｘＸ［ｘ］にＤＡＴＡ［ｘ３］［ｙ３］［ｚ３］．ｘを代入する。
【００３５】
ステップＳ３３において、ＭｉｎＸ［ｘ］と、補間前テーブルのデータのｘ値ＤＡＴＡ［ｘ３］［ｙ３］［ｚ３］．ｘを比較する。ＭｉｎＸ［ｘ］＞ＤＡＴＡ［ｘ３］［ｙ３］［ｚ３］．ｘのときは、ステップＳ３４に進む。それ以外の時は、処理終了。
【００３６】
ステップＳ３４において、ＭｉｎＸ［ｘ］にＤＡＴＡ［ｘ３］［ｙ３］［ｚ３］．ｘを代入する。
【００３７】
＜読み込みデータ存在範囲算出部３での動作の詳細＞
図７〜８に読み込みデータ存在範囲算出部３での動作の詳細を示す。
【００３８】
ステップＳ４１において、ｘ軸方向の存在範囲の下限ｘ１と上限ｘ２を求める。動作の詳細を図８に示す。
【００３９】
ステップＳ４２において、ｙ軸方向の存在範囲の下限ｙ１と上限ｙ２を求める。動作の詳細は、図８において、Ｐｏｉｎｔ．ｘをＰｏｉｎｔ．ｙに、ｘ１をｙ１に、ｘ２をｙ２に、ＭｉｎＸをＭｉｎＹに、ＭａｘＸをＭａｘＹにそれぞれ変更したものである。
【００４０】
ステップＳ４３において、ｚ軸方向の存在範囲の下限ｚ１と上限ｚ２を求める。動作の詳細は、図８において、Ｐｏｉｎｔ．ｘをＰｏｉｎｔ．ｚに、ｘ１をｚ１に、ｘ２をｚ２に、ＭｉｎＸをＭｉｎＺに、ＭａｘＸをＭａｘＺにそれぞれ変更したものである。
【００４１】
次に図８について詳細に説明する。
【００４２】
ステップＳ５１において、カウンタｃｎｔｘを０で初期化する。
【００４３】
ステップＳ５２において、読み込んだデータのｘ値、Ｐｏｉｎｔ．ｘが、
ＭｉｎＸ［ｃｎｔｘ］＜＝Ｐｏｉｎｔ．ｘ＜＝ＭａｘＸ［ｃｎｔｘ＋１］
範囲に入っているかどうかを調べる。上記範囲に入っていれば、ステップＳ５６に進む。範囲外なら、ステップＳ５３に進む。
【００４４】
ステップＳ５３において、ｃｎｔｘをインクリメントする。
【００４５】
ステップＳ５４において、ｃｎｔｘ＜８を満たすか調べる。ｃｎｔｘ＜８なら、ステップＳ５２に戻る。それ以外なら、ステップＳ５５に進む。
【００４６】
ステップＳ５５において、ｘ軸方向の下限値ｘ１、上限値ｘ２ともに８を代入して処理終了。
【００４７】
ステップＳ５６において、ｘ軸方向の下限値ｘ１にｃｎｔｘを代入する。
【００４８】
ステップＳ５７において、ｃｎｔｘをインクリメントする。
【００４９】
ステップＳ５８において、読み込んだデータのｘ値、Ｐｏｉｎｔ．ｘが、
ＭｉｎＸ［ｃｎｔｘ］＜＝Ｐｏｉｎｔ．ｘ＜＝ＭａｘＸ［ｃｎｔｘ＋１］
範囲に入っているかどうかを調べる。上記範囲に入っていれば、ステップＳ５９に進む。範囲外なら、ステップＳ６２に進む。
【００５０】
ステップＳ５９において、ｃｎｔｘをインクリメントする。
【００５１】
ステップＳ６０において、ｃｎｔｘ＜８を満たすか調べる。ｃｎｔｘ＜８なら、ステップＳ５８に戻る。それ以外なら、ステップＳ６１に進む。
【００５２】
ステップＳ６１において、ｘ軸方向の上限値ｘ２に８を代入して、処理終了。
【００５３】
ステップＳ６２において、ｘ軸方向の上限値ｘ２にｃｎｔｘを代入して、処理終了。
【００５４】
ステップＳ５１からステップＳ６２までの処理は、ｙ軸方向、ｚ軸方向についても同じである。
【００５５】
＜四面体補間部４での動作＞
図９に四面体補間部４での動作の詳細を示す。
【００５６】
ステップＳ７１において、ｘ軸方向のカウンタｃｎｔｘをｘ１で初期化する。ｘ１は、先に求めた値である。
【００５７】
ステップＳ７２において、ｙ軸方向のカウンタｃｎｔｙをｙ１で初期化する。ｙ１は、先に求めた値である。
【００５８】
ステップＳ７３において、ｚ軸方向のカウンタｃｎｔｚをｚ１で初期化する。ｚ１は、先に求めた値である。
【００５９】
ステップＳ７４において、立方体を作成する。立方体は、以下の８点で作成される。
【００６０】
DATA[cntx][cnty][cntz]、DATA[cntx+1][cnty][cntz]、
DATA[cntx][cnty+1][cntz]、DATA[cntx+1][cnty+1][cntz]
DATA[cntx][cnty][cntz+1]、DATA[cntx+1][cnty][cntz+1]、
DATA[cntx][cnty+1][cntz+1]、DATA[cntx+1][cnty+1][cntz+1]
ステップＳ７５において、読み込んだデータが作成した立方体の内部かどうかを判定する。もし、内部なら、ステップＳ７９に進む。外部なら、ステップＳ７６に進む。
【００６１】
ステップＳ７６において、ｃｎｔｚをインクリメントした後、ｚ２と大小を比較する。ｚ２のほうが大きければ、ステップＳ７４に戻る。それ以外のときは、ステップＳ７７に進む。
【００６２】
ステップＳ７７において、ｃｎｔｙをインリメントした後、ｙ２と大小を比較する。Ｙ２のほうが大きければ、ステップＳ７３に戻る。それ以外のときは、ステップＳ７８に進む。
【００６３】
ステップＳ７８において、ｃｎｔｘをインクリメントした後、ｘ２と大小を比較する。Ｘ２のほうが大きければ、ステップＳ７２に戻る。それ以外のときは、処理終了。
【００６４】
ステップＳ７９において、四面体補間を行う。
【００６５】
（他の実施の形態）
本実施例では、テーブル、および読み込みデータともに３次元である場合の説明を行ったが、３次元に限らず、４次元、５次元、それ以上の次元数でも実施可能なことは言うまでもない。
【００６６】
また、各軸のテーブルの格子点の数は９点で行っていたが、９点に限らず実施可能であることは言うまでもない。さらに、各軸で格子点数が異なっても良いことは言うまでもない。
【００６７】
なお、本発明は、複数の機器（例えばホストコンピュータ、インタフェイス機器、リーダ、プリンタなど）から構成されるシステムに適用しても、一つの機器からなる装置（例えば、複写機、ファクシミリ装置など）に適用しても良い。
【００６８】
また、本発明の目的は前述した実施形態の機能を実現するソフトウェアのプログラムコードを記録した記憶媒体を、システムあるいは装置に供給し、そのシステムあるいは装置のコンピュータ（またはＣＰＵまたはＭＰＵ）が記憶媒体に格納されたプログラムコードを読み出し実行することによっても達成されることは言うまでもない。
【００６９】
この場合、記憶媒体から読み出されたプログラムコード自体が前述した実施形態の機能を実現することになり、そのプログラムコードを記憶した記憶媒体は本発明を構成することになる。
【００７０】
プログラムコードを供給するための記憶媒体としては、例えば、フロッピー（登録商標）ディスク、ハードディスク、光ディスク、光磁気ディスク、ＣＤ−ＲＯＭ、ＣＤ−Ｒ、磁気テープ、不揮発性のメモリカード、ＲＯＭなどを用いることが出来る。
【００７１】
また、コンピュータが読み出したプログラムを実行することにより、前述した実施形態の機能が実現されるだけでなく、そのプログラムコードの指示に基づき、コンピュータ上で稼動しているＯＳ（オペレーティングシステム）などが実際の処理の一部を行い、その処理によって前述した実施形態の機能が実現される場合も含まれることは言うまでもない。
【００７２】
さらに、記憶媒体から読み出されたプログラムコードが、コンピュータに挿入された機能拡張ボードやコンピュータに接続された機能拡張ユニットに備わるメモリに書き込まれた後、そのプログラムコードの指示に基づき、その機能拡張ボードや機能拡張ユニットに備わるＣＰＵなどが実際の処理の一部または全部を行い、その処理によって前述した実施形態の機能が実現される場合も含まれることは言うまでもない。
【図面の簡単な説明】
【００７３】
【図１】装置の構成を示す図である。
【図２】格子状になっているテーブルデータを示す図である。
【図３】格子状になっていないテーブルデータを示す図である。
【図４】装置の動作を説明するフローチャートである。
【図５】各軸最大値・最小値記憶部の動作を説明するフローチャートである。
【図６】各軸最大値・最小値記憶部の動作を説明するフローチャートである。
【図７】読み込みデータ存在範囲算出部の動作を説明するフローチャートである。
【図８】読み込みデータ存在範囲算出部の動作を説明するフローチャートである。
【図９】四面体補間部の動作を説明するフローチャートである。
【図１】
2006119883.tif 000003
【図２】
2006119883.tif 000004
【図３】
2006119883.tif 000005
【図４】
2006119883.tif 000006
【図５】
2006119883.tif 000007
【図６】
2006119883.tif 000008
【図７】
2006119883.tif 000009
【図８】
2006119883.tif 000010
【図９】
2006119883.tif 000011