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