JPH07160906A - 座標変換装置及び座標変換方法 - Google Patents

Abstract

(57)【要約】 （修正有） 【構成】 テクスチャマッピングのための座標変換にお
いて、複数の多項式の除算を、加減算だけの逐次解法に
より計算する。最初にステップＳ３で初期値計算した
後、ステップＳ４で誤差評価しながらステップＳ５で補
正して誤差が所定範囲になるまで補正を繰り返し、ステ
ップＳ８で値を更新してステップＳ４に戻ることによ
り、変換前座標から変換後座標を逐次的に求める。 【効果】 除算を使わずに加減算だけで座標変換が行
え、ハードウェア規模を小さくでき、演算を高速化で
き、また、変換座標に歪みが生じない。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、コンピュータグラフィ
ックのテクスチャマッピング等において座標を変換する
ために用いられる座標変換装置及び座標変換方法に関す
る。

【０００２】

【従来の技術】グラフィックコンピュータ、特殊効果装
置、ビデオゲーム等のコンピュータを用いた映像機器に
おいて、いわゆるテクスチャマッピングの手法を用いて
画像を生成することがある。このテクスチャマッピング
とは、スクリーン座標上のいわゆるポリゴンに絵や柄等
のテクスチャ画像を張り付けることで質の高い出力画像
を生成する技術のことであり、ポリゴンとは、コンピュ
ータグラフィックス（いわゆるＣＧ）において図形を表
すときの基本単位として用いられる多角形平面のことで
ある。またスクリーン座標とは、視野座標ともいい、３
次元の世界を１点を中心にして、２次元平面に投影した
場合のその面内の座標のことである。

【０００３】図４は、従来のテクスチャマッピングの手
法の流れを示すフローチャートであり、図４は、スクリ
ーン座標上のテクスチャを張り付ける前のポリゴンとテ
クスチャ座標上のテクスチャとの関係を示す図である。

【０００４】この図４の最初のステップＳ１０１におい
ては、スクリーン座標上のポリゴンとテクスチャ座標上
の画像との座標変換係数を求めている。すなわち図５に
おいて、（Ａ）のスクリーン座標上の４点（ｘ₀ ，
ｙ₀ ）、（ｘ₁ ，ｙ₁ ）、（ｘ₂，ｙ₂ ）、（ｘ₃ ，ｙ
₃ ）が、（Ｂ）のテクスチャ座標上の４点（ｕ₀ ，
ｖ₀ ）、（ｕ₁ ，ｖ₁ ）、（ｕ₂ ，ｖ₂ ）、（ｕ₃ ，ｖ
₃ ）に対応するとするとき、次の式が成立する。

【０００５】

【数１】

【０００６】

【数２】

【０００７】これらの各式中のＡが座標変換係数とな
る。ここで、（４８）式、（４９）式は例えば、George
Wolberg, "DIGITAL IMAGE WARPING", IEEE Computer S
ocietyPress, Sections 3.4 - 3.4.2 の文献等に記載
されているものである。従って、スクリーン座標をテク
スチャ座標に変換する座標変換式は、

【０００８】

【数３】

【０００９】ここで図６は、座標変換式を用いること
で、（Ａ）のスクリーン座標の点ｐが、（Ｂ）のテクス
チャ座標の点ｑの位置に座標変換される様子を示してい
る。

【００１０】次に、図４のステップＳ１０２において
は、スクリーン座標上のポリゴンを現実のスクリーンに
描画する。通常の場合、描画先はラスタスキャンタイプ
のディスプレイ装置のスクリーン面となるので、ラスタ
スキャンの走査線単位に画像を分割し、描画する。そこ
で、ポリゴンをスクリーン座標上の走査線単位に分割し
て、その走査線上の開始点と終了点とを決定する。例え
ば、図７は、第ｎ番目の走査線における開始点Ｐ_S と終
了点Ｐ_E とを示している。

【００１１】ステップＳ１０３〜Ｓ１０７においては、
図８に示すように、走査線上の開始点から終了点までを
１画素毎に座標変換をして、テクスチャ座標上の対応点
の画素値を書き込み、補間してゆき、次のステップＳ１
０８において、ポリゴン内の全ての走査線について上記
ステップＳ１０２からステップＳ１０７までの処理を繰
り返す。テクスチャマッピングが完了したときのスクリ
ーン座標の状態を図９の（Ａ）に示す。なお、図９の
（Ｂ）はテクスチャ座標を示す。

【００１２】上記ステップＳ１０３〜Ｓ１０７における
座標変換式は、上記ステップＳ１０１の座標変換式（１
３）のように、（多項式）／（多項式）となる。計算方
法は、大きく２つに分けられる。

【００１３】一つは、（多項式）／（多項式）の比を求
めるために、実際に除算を行う方法である。もう一つ
は、座標変換式を、ｕ＝ａ₃ ｘ³ ＋ａ₂ ｘ² ＋ａ₁ ｘ＋
ａ₀ のような近似多項式に置き換えて、除算を回避する
方法である。図４には、前者の例が示されている。

【００１４】すなわち、図４のステップＳ１０３におい
ては、上記開始点Ｐ_S を、補間する画素点の初期値と
し、次のステップＳ１０４に進んで、座標変換式の除数
と被除数となる多項式の値を計算する。さらに次のステ
ップＳ１０５では、被除数を除数で除算して、その解を
座標変換値とし、ステップＳ１０６では、テクスチャ座
標での画素値をポリゴン内の画素点に書き込む。ステッ
プＳ１０７により、このような補間を上記終了点まで繰
り返す。

【００１５】これに対して、上記近似多項式に置き換え
る方法の例を図１０に示す。この方法は、例えば上記文
献 George Wolberg,"DIGITAL IMAGE WARPING" の Secti
ons7.2.6 - 7.2.7 等に開示されているものである。

【００１６】図１０において、上記図４の各ステップと
対応するステップには同じ指示符号を付して説明を省略
する。この図１０の例では、図４の各ステップＳ１０３
〜Ｓ１０７の代わりに、ステップＳ１１３〜Ｓ１１６の
処理を行っている。

【００１７】すなわち、ステップＳ１１３では、上記開
始点Ｐ_S を、補間する画素点の初期値とする。座標変換
係数と開始点Ｐ_S と終了点Ｐ_E から近似多項式の各項の
係数を予め計算して記憶しておく。次のステップＳ１１
４では、近似多項式の値を計算してその値を座標変換値
とし、ステップＳ１１５では、テクスチャ座標での画素
値をポリゴン内の画素点に書き込む。さらに、ステップ
Ｓ１１６により、このような補間を上記終了点まで繰り
返す。

【００１８】

【発明が解決しようとする課題】ところで、上記図４に
示すように、計算式通りに除算を行う場合には、正しい
計算結果が得られる。しかし、欠点として、加減算に比
べて除算は手順が複雑であり、計算に時間がかかる。ま
た、集積回路等にハードウェア化するとき、高速なハー
ドウェア除算器が回路全体に対して占める面積は、加減
算器に比べてかなり大きくなる。

【００１９】また、上記図１０に示すように、除算を行
う代わりに近似多項式を用いて近似解を得る方法では、
計算を加減算だけで行うので計算が速い。また、加減算
器だけで構成できるので、ハードウェアを小さくするこ
とができる。しかしながら、近似演算を行っているた
め、得られる結果に誤差や歪が生じる。

【００２０】本発明は、このような実情に鑑みてなされ
たものであり、小規模のハードウェアで正しい計算結果
が得られるような座標変換装置及び座標変換方法を提供
することを目的とする。

【００２１】

【課題を解決するための手段】本発明に係る座標変換装
置は、上述した課題を解決するために、変換前座標を変
数とする複数の多項式の比により変換後座標を得る座標
変換に等価な座標変換を行う座標変換装置において、上
記変換後座標を記憶する変換後座標記憶手段と、上記変
換後座標の誤差評価値を記憶する誤差評価値記憶手段
と、上記誤差評価値が許容範囲にあることを判定する誤
差判定手段と、上記変換前座標に基づいて上記変換後座
標記憶手段及び上記誤差評価値記憶手段の各初期値を設
定する初期値設定手段と、上記誤差判定手段からの出力
に応じて上記変換後座標記憶手段及び上記誤差評価値記
憶手段の各内容を更新する更新手段とを有し、上記変換
前座標から上記変換後座標を逐次的に求めることを特徴
としている。

【００２２】ここで、上記更新手段は、複数の入力を選
択して演算を行う選択演算部を複数有し、少なくとも上
記変換後座標記憶手段及び上記誤差評価値記憶手段の各
値を並列に更新して高速化することが好ましい。

【００２３】また、本発明に係る座標変換方法は、上述
の課題を解決するために、変換前座標を変数とする複数
の多項式の比により変換後座標を得る座標変換方法にお
いて、変換前の任意の第ｋ番の座標点の座標成分の関数
である多項式をそれぞれＮ_k及びＤ_k として変換後座標
の一成分をこれらの多項式の比をＮ_k ／Ｄ_k により求め
るものとし、上記Ｎ_k ／Ｄ_k の除算を整数除算として計
算した結果の商を上記第ｋ番の座標点の変換後の座標点
の一座標成分Ｑ_k 、剰余をＲ_k 、すなわち、 Ｎ_k ＝Ｄ_k ×Ｑ_k ＋Ｒ_k ・・・ （１） とし、変換前の次の第ｋ＋１番の座標点に対して上記座
標変換を行った除算結果の商をＱ_k+1 、剰余をＲ_k+1 、
すなわち、 Ｎ_k+1 ＝Ｄ_k+1 ×Ｑ_k+1 ＋Ｒ_k+1 ・・・ （２） とするとき、被除数の差分Ｎ_k+1 −Ｎ_k をΔＮ、除数の
差分Ｄ_k+1 −Ｄ_k をΔＤとして、上記（１）式を書き換
えて、 Ｎ_k ＋ΔＮ＝（Ｄ_k ＋ΔＤ）×Ｑ_k ＋Ｒ_k ＋ΔＮ−ΔＤ×Ｑ_k Ｎ_k+1 ＝Ｄ_k+1 ×Ｑ_k+1 ＋Ｒ_k ＋ΔＮ−ΔＤ×Ｑ_k ・・・ （３） とし、上記（２）式と（３）式とを比較して、 Ｑ_k+1 ＝Ｑ_k ＋（Ｒ_k ＋ΔＮ−ΔＤ×Ｑ_k ）／Ｄ_k+1 ・・・ （４） Ｒ_k+1 ＝（Ｒ_k ＋ΔＮ−ΔＤ×Ｑ_k ）mod Ｄ_k+1 ・・・ （５） が成立することを利用して、上記変換後の座標点の一座
標成分Ｑ_k が既知であるときの次の変換後座標の一成分
Ｑ_k+1 を、Ｎ_k+1 ／Ｄ_k+1 を計算する代わりに上記
（４）式に置き換えて求める工程と、上記（４）式中の
除算を加減算に置き換えて計算する工程と、を有するこ
とを特徴としている。

【００２４】ここで、上記変換後座標の一成分Ｑ
_k+1 を、既知の変換後座標成分Ｑ_k を用いて上記（４）
式及び（５）式により求める際に、上記変換後座標の計
算誤差許容範囲である定数ΔＱを設定し、計算により上
記被除数差分値ΔＮ、除数差分値ΔＤを求める第１の計
算工程（初期値計算工程の一部）と、次の第ｋ＋１番の
変換前座標点に対応する除数値Ｄ_k+1 、Ｎ_k+1 ／Ｄ_k+1
を整数除算として計算したときの剰余である誤差評価値
Ｒ_k+1 、及び変換後座標の一成分Ｑ_k+1 を、 Ｄ_k+1 ＝Ｄ_k ＋ΔＤ ・・・ （６） Ｒ_k+1 ＝Ｒ_k ＋ΔＮ−ΔＤ×Ｑ_k ・・・ （７） Ｑ_k+1 ＝Ｑ_k ・・・ （８） の各式を計算することにより求める第２の計算工程（除
数値、誤差評価値の更新工程）と、求められたＲ_k+1 の
値が０より小の条件（Ｒ_k+1 ＜０）を満たすとき、 Ｒ_k+1 ←Ｒ_k+1 ＋｜Ｄ_k+1 ｜×ΔＱ ・・・ （９） Ｑ_k+1 ←Ｑ_k+1 ＋ΔＱ ・・・ （１０） の各式（ただし、←は代入を表す。）により補正を行う
第１の補正工程と、求められたＲ_k+1 の値が上記Ｄ_k+1
の値以上の条件（Ｄ_k+1 ≦Ｒ_k+1 ）を満たすとき、 Ｒ_k+1 ←Ｒ_k+1 −｜Ｄ_k+1 ｜×ΔＱ ・・・ （１１） Ｑ_k+1 ←Ｑ_k+1 ＋ΔＱ ・・・ （１２） の各式により補正を行う第２の補正工程と、求められた
Ｒ_k+1 の値が０以上かつ上記Ｄ_k+1 の値より小の条件
（０≦Ｒ_k+1＜Ｄ_k+1 ）を満たすか否かを判別し、この
条件を満足しないとき上記第１の補正工程又は上記第２
の補正工程を繰り返し、この条件を満足するときのＱ
_k+1 を最終的な目的とする座標変換結果とする誤差評価
工程とを含むことが好ましい。

【００２５】また、上記変換後座標の一成分Ｑ_k+1 を、
既知の変換後座標成分Ｑ_k を用いて上記（４）式及び
（５）式により求める際に、上記変換後座標の計算誤差
許容範囲である定数ΔＱを設定し、計算により上記被除
数差分値ΔＮ、除数差分値ΔＤを求め、複合差分値Ｃ_k
を、 Ｃ_k ＝ΔＤ×Ｑ_k ・・・ （１３） により求める第１の計算工程（初期値計算工程の一部）
と、Ｄ_k+1 、Ｒ_k+1 、Ｑ_k+1 、及びＣ_k+1 を、 Ｄ_k+1 ＝Ｄ_k ＋ΔＤ ・・・ （１４） Ｒ_k+1 ＝Ｒ_k ＋ΔＮ−Ｃ_k ・・・ （１５） Ｑ_k+1 ＝Ｑ_k ・・・ （１６） Ｃ_k+1 ＝Ｃ_k ・・・ （１７） の各式を計算することにより求める第２の計算工程（除
数値、誤差評価値の更新工程）と、求められたＲ_k+1 の
値が０より小の条件（Ｒ_k+1 ＜０）を満たすとき、 Ｒ_k+1 ←Ｒ_k+1 ＋｜Ｄ_k+1 ｜×ΔＱ ・・・ （１８） Ｑ_k+1 ←Ｑ_k+1 ＋ΔＱ ・・・ （１９） Ｃ_k+1 ←Ｃ_k ＋ΔＤ×ΔＱ ・・・ （２０） の各式（ただし、←は代入を表す。）により補正を行う
第１の補正工程と、求められたＲ_k+1 の値が上記Ｄ_k+1
の値以上の条件（Ｄ_k+1 ≦Ｒ_k+1 ）を満たすとき、 Ｒ_k+1 ←Ｒ_k+1 −｜Ｄ_k+1 ｜×ΔＱ ・・・ （２１） Ｑ_k+1 ←Ｑ_k+1 ＋ΔＱ ・・・ （２２） Ｃ_k+1 ←Ｃ_k ＋ΔＤ×ΔＱ ・・・ （２３） の各式により補正を行う第２の補正工程と、求められた
Ｒ_k+1 の値が０以上かつ上記Ｄ_k+1 の値より小の条件
（０≦Ｒ_k+1＜Ｄ_k+1 ）を満たすか否かを判別し、この
条件を満たさないとき上記第１の補正工程又は上記第２
の補正工程を繰り返し、この条件を満たすときのＱ_k+1
を最終的な座標変換結果とする誤差評価工程とを含むこ
とが好ましい。

【００２６】また、上記変換後座標の一成分Ｑ_k+1 を、
既知の変換後座標成分Ｑ_k を用いて上記（４）式及び
（５）式により求める際に、上記変換後座標の計算誤差
許容範囲である定数ΔＱを設定し、計算により上記被除
数差分値ΔＮ、除数差分値ΔＤを求め、複合差分値Ｃ_k
を、 Ｃ_k ＝ΔＤ×Ｑ_k −ΔＮ ・・・ （２４） により求める第１の計算工程（初期値計算工程の一部）
と、Ｄ_k+1 、Ｒ_k+1 、Ｑ_k+1 、及びＣ_k+1 を、 Ｄ_k+1 ＝Ｄ_k ＋ΔＤ ・・・ （２５） Ｒ_k+1 ＝Ｒ_k −Ｃ_k ・・・ （２６） Ｑ_k+1 ＝Ｑ_k ・・・ （２７） Ｃ_k+1 ＝Ｃ_k ・・・ （２８） の各式を計算することにより求める第２の計算工程（除
数値、誤差評価値の更新工程）と、求められたＲ_k+1 の
値が０より小の条件（Ｒ_k+1 ＜０）を満たすとき、 Ｒ_k+1 ←Ｒ_k+1 ＋｜Ｄ_k+1 ｜×ΔＱ ・・・ （２９） Ｑ_k+1 ←Ｑ_k+1 ＋ΔＱ ・・・ （３０） Ｃ_k+1 ←Ｃ_k ＋ΔＤ×ΔＱ ・・・ （３１） の各式（ただし、←は代入を表す。）により補正を行う
第１の補正工程と、求められたＲ_k+1 の値が上記Ｄ_k+1
の値以上の条件（Ｄ_k+1 ≦Ｒ_k+1 ）を満たすとき、 Ｒ_k+1 ←Ｒ_k+1 −｜Ｄ_k+1 ｜×ΔＱ ・・・ （３２） Ｑ_k+1 ←Ｑ_k+1 ＋ΔＱ ・・・ （３３） Ｃ_k+1 ←Ｃ_k ＋ΔＤ×ΔＱ ・・・ （３４） の各式により補正を行う第２の補正工程と、求められた
Ｒ_k+1 の値が０以上かつ上記Ｄ_k+1 の値より小の条件
（０≦Ｒ_k+1＜Ｄ_k+1 ）を満たすか否かを判別し、この
条件を満たさないとき上記第１の補正工程又は上記第２
の補正工程を繰り返し、この条件を満たすときのＱ_k+1
を最終的な座標変換結果とする誤差評価工程とを含むこ
とが好ましい。

【００２７】さらに、上記変換後座標の一成分Ｑ
_k+1 を、既知の変換後座標成分Ｑ_k を用いて上記（４）
式及び（５）式により求める際に、上記変換後座標の計
算誤差許容範囲である定数ΔＱを設定し、計算により上
記被除数差分値ΔＮ、除数差分値ΔＤを求め、複合差分
値Ｃ_k 、除数値Ｄ_k 及び除数差分値ΔＤを、 Ｃ_k ＝ΔＤ×Ｑ_k −ΔＮ ・・・ （３５） Ｄ_k ←Ｄ_k ×ΔＱ ・・・ （３６） ΔＤ←ΔＤ×ΔＱ ・・・ （３７） の各式（ただし、←は代入を表す。）により求める第１
の計算工程（初期値計算工程の一部）と、Ｄ_k+1 、Ｒ
_k+1 、Ｑ_k+1 、及びＣ_k+1 を、 Ｄ_k+1 ＝Ｄ_k ＋ΔＤ ・・・ （３８） Ｒ_k+1 ＝Ｒ_k −Ｃ_k ・・・ （３９） Ｑ_k+1 ＝Ｑ_k ・・・ （４０） Ｃ_k+1 ＝Ｃ_k ・・・ （４１） の各式を計算することにより求める第２の計算工程（除
数値、誤差評価値の更新工程）と、求められたＲ_k+1 の
値が０より小の条件（Ｒ_k+1 ＜０）を満たすとき、 Ｒ_k+1 ←Ｒ_k+1 ＋｜Ｄ_k+1 ｜ ・・・ （４２） Ｑ_k+1 ←Ｑ_k+1 ＋ΔＱ ・・・ （４３） Ｃ_k+1 ←Ｃ_k ＋ΔＤ ・・・ （４４） の各式により補正を行う第１の補正工程と、求められた
Ｒ_k+1 の値が上記Ｄ_k+1 の値以上の条件（Ｄ_k+1 ≦Ｒ
_k+1 ）を満たすとき、 Ｒ_k+1 ←Ｒ_k+1 −｜Ｄ_k+1 ｜ ・・・ （４５） Ｑ_k+1 ←Ｑ_k+1 ＋ΔＱ ・・・ （４６） Ｃ_k+1 ←Ｃ_k ＋ΔＤ ・・・ （４７） の各式により補正を行う第２の補正工程と、求められた
Ｒ_k+1 の値が０以上かつ上記Ｄ_k+1 の値より小の条件
（０≦Ｒ_k+1＜Ｄ_k+1 ）を満たすか否かを判別し、この
条件を満たさないとき上記第１の補正工程又は上記第２
の補正工程を繰り返し、この条件を満たすときのＱ_k+1
を最終的な座標変換結果とする誤差評価工程とを含むこ
とが好ましい。

【００２８】ところで、上記第１の計算工程を１回行っ
た後、上記第２の計算工程、上記第１又は第２の補正工
程、及び上記誤差評価工程を繰り返し、一連の座標に対
して座標変換を行うことが好ましい。また、上記変換後
座標の計算誤差許容範囲である定数ΔＱを１とすること
が挙げられる。

【００２９】

【作用】変換前座標を変数とする複数の多項式を除算し
て変換後座標を得る際に、除算を使わずに加減算だけを
行って、除算を行った場合と同様な正確な結果を得るこ
とができ、ハードウェアの規模を小さくすることができ
る。

【００３０】

【実施例】以下、図面を参照しながら、本発明の一実施
例について説明する。図１は、本発明に係る座標変換装
置の一実施例の概略構成を示すブロック図であり、図２
は、該実施例の動作を説明するためのフローチャートで
ある。

【００３１】この図１は、変換前座標を変数とする複数
の多項式の比により変換後座標を得る座標変換に等価な
座標変換を行う座標変換装置の一例を示しており、上記
変換後座標を記憶する変換後座標値メモリ４、上記変換
後座標の誤差評価値を記憶する誤差評価値メモリ２と、
上記誤差評価値が許容範囲にあることを判定する誤差範
囲検出部５と、上記変換座標に基づいて変換後座標値メ
モリ４及び誤差評価値メモリ２の各初期値を設定する初
期値設定部６と、誤差範囲検出部５からの出力に応じて
変換後座標値メモリ４及び誤差評価値メモリ２の各内容
を更新する更新部７とを有し、上記変換前座標から上記
変換後座標を逐次的に求めている。

【００３２】上記更新部７は、複数の入力を選択して演
算を行う複数の選択加算部２４、２５、２６、２７を有
し、例えば選択加算部２７及び２４は変換後座標値メモ
リ４及び誤差評価値メモリ１の各値を並列に更新するた
め高速化が図られる。なお、図１の他の構成について
は、次の図２のフローチャートを用いた動作説明と共に
説明する。

【００３３】図２は、この図１に示す座標変換装置の動
作を説明するためのフローチャートであり、この図２の
最初のステップＳ１においてはスクリーン座標上のポリ
ゴンとテクスチャ座標上の画像との座標変換係数を求め
る。

【００３４】すなわち、前述した図５において、スクリ
ーン座標上の４点（ｘ₀ ，ｙ₀ ）、（ｘ₁ ，ｙ₁ ）、
（ｘ₂ ，ｙ₂ ）、（ｘ₃ ，ｙ₃ ）が、テクスチャ座標上
の４点（ｕ₀ ，ｖ₀ ）、（ｕ₁ ，ｖ₁ ）、（ｕ₂ ，
ｖ₂ ）、（ｕ₃ ，ｖ₃ ）に対応するとするとき、前記
（４８）式、（４９）式が成立する。すなわち、

【００３５】

【数４】

【００３６】

【数５】

【００３７】この場合の（４８）式、（４９）式のＡが
座標変換係数となる。従って、スクリーン座標をテクス
チャ座標に変換する座標変換式は、前記（５０）式とな
る。すなわち、

【００３８】

【数６】

【００３９】次に、図２のステップＳ２においては、ス
クリーン座標上のポリゴンを現実のスクリーンに描画す
る。通常の場合、描画先はラスタスキャンタイプのディ
スプレイ装置のスクリーン面となるので、ラスタスキャ
ンの走査線単位に画像を分割し、描画する。そこで、ポ
リゴンをスクリーン座標上の走査線単位に分割して、そ
の走査線上の開始点と終了点とを決定する。なお、この
ような水平の走査線単位に画像を分割する以外に、垂直
軸（Ｙ軸）あるいは任意の傾きを持った直線に平行な直
線単位に画像を分割し、その直線上で処理を行うように
してもよい。

【００４０】図２のステップＳ３〜ステップＳ８におい
ては、上記走査線（あるいは任意の直線）上の開始点か
ら終了点までを１画素毎に座標変換をして、テクスチャ
座標上の対応点の画素値を書き込み、前記図８に示すよ
うに補間してゆく。これを、ステップＳ９において、ポ
リゴン内の全ての走査線について繰り返す。

【００４１】上記ステップＳ３〜ステップＳ８での内挿
（補間）時における座標変換式は、上記（５０）式に示
すように、変換前座標であるスクリーン座標の各成分
ｘ，ｙを変数とする多項式の比、すなわち（多項式）／
（多項式）にて表される。ここで、上記ポリゴン内の任
意の走査線（あるいは直線）上の第ｋ番の座標点の座標
値を（ｘ_k ，ｙ_k ）と表し、この座標値（ｘ_k ，ｙ_k ）
についての分子、分母の各多項式（の計算結果）をそれ
ぞれＮ_k 、Ｄ_k と表し、上記座標変換式としてのＮ_k ／
Ｄ_k を整数除算したときの商をＱ_k 、剰余をＲ_k とする
とき、 Ｎ_k ／Ｄ_k ＝Ｑ_k …Ｒ_k ・・・ （５１） この分数式は、スクリーン座標上の上記第ｋ番の座標値
（ｘ_k ，ｙ_k ）に対応するテクスチャ座標上の座標値を
（ｕ_k ，ｖ_k ）と表すときに、上記（５０）式により変
換後座標の成分ｕ_k 又はｖ_k を求める式に相当し、これ
らの座標成分ｕ_k又はｖ_k を整数値で表したものが上記
商Ｑ_k に相当する。

【００４２】この（５１）式の分数式を加法と乗法とで
表すと、前記（１）式、すなわち Ｎ_k ＝Ｄ_k ×Ｑ_k ＋Ｒ_k ・・・ （１） となる。また、スクリーン座標上の上記第ｋ番の次の座
標点である第ｋ＋１番の座標点の座標値を（ｘ_k+1 ，ｙ
_k+1 ）と表し、この第ｋ＋１番の座標点の座標値につい
ての分子、分母の各多項式（の計算結果）をそれぞれＮ
_k+1 、Ｄ_k+1 と表し、上記座標変換式としてのＮ_k+1 ／
Ｄ_k+1 を整数除算したときの商をＱ_k+1 、剰余をＲ_k+1
とするときには前記（２）式、すなわち、 Ｎ_k+1 ＝Ｄ_k+1 ×Ｑ_k+1 ＋Ｒ_k+1 ・・・ （２） が成立する。ここで、被除数差分値ΔＮ、除数差分値Δ
Ｄを、それぞれ ΔＮ＝Ｎ_k+1 −Ｎ_k ・・・ （５２） ΔＤ＝Ｄ_k+1 −Ｄ_k ・・・ （５３） とする。

【００４３】これらの被除数差分値ΔＮ、除数差分値Δ
Ｄを用いて上記（１）式を書き換えることにより、前記
（３）式、すなわち、 Ｎ_k+1 ＝Ｄ_k+1 ×Ｑ_k+1 ＋Ｒ_k ＋ΔＮ−ΔＤ×Ｑ_k ・・・ （３） とする。本実施例においては、上記（２）式と（３）式
とを比較して得られる前記（４）式及び（５）式、すな
わち、 Ｑ_k+1 ＝Ｑ_k ＋（Ｒ_k ＋ΔＮ−ΔＤ×Ｑ_k ）／Ｄ_k+1 ・・・ （４） Ｒ_k+1 ＝（Ｒ_k ＋ΔＮ−ΔＤ×Ｑ_k ）mod Ｄ_k+1 ・・・ （５） が成立することを利用して、上記変換後の座標点の一座
標成分Ｑ_k が既知であるときの次の変換後座標の一成分
Ｑ_k+1 を、Ｎ_k+1 ／Ｄ_k+1 を計算する代わりに上記
（４）式に置き換えて求めており、この（４）式中の除
算を加減算に置き換えて計算している。また、変換後座
標の計算精度あるいは誤差許容範囲であるΔＱを予め設
定しておく。

【００４４】ここで具体例として、Ｄ_k ＝７、Ｑ_k ＝
６、Ｒ_k ＝１９、ΔＮ＝４１、ΔＤ＝４、ΔＱ＝１と
し、以下の説明中でこれらの値を用いて実際の計算例を
示す。

【００４５】ステップＳ３の初期値計算工程において
は、図１の変換前座標値８から初期値設定部６に送られ
る変換前座標の上記開始点と上記座標変換係数とに基づ
いて、この開始点における変換後座標の一成分Ｑ_k 、上
記剰余である誤差評価値Ｒ_k 、複合差分値Ｃ_k 、除数値
Ｄ_k を予め計算して、上記図１の変換後座標値メモリ
４、誤差評価値メモリ１、複合差分値メモリ２、及び除
数値メモリ３にそれぞれ記憶しておく。ここで、複合差
分値Ｃ_k は、 Ｃ_k ＝Ｑ_k ×ΔＤ ・・・ （５４） である。また、定数の被除数差分値ΔＮ及び除数差分値
ΔＤを上記（５２）式、（５３）式により計算し、上記
変換後座標の誤差許容範囲であるΔＱを設定して、上記
図１のメモリ２０〜２３に記憶しておく。

【００４６】例えば、上記（５４）式に上記具体的の数
値の例を当てはめると、Ｃ_k ＝６×４＝２４、となる。
また、上記メモリ２０には０とΔＮが格納され、メモリ
２１、２２、及び２３には、順次、ΔＤと０、０とΔ
Ｄ、及びΔＱと０がそれぞれ格納されている。

【００４７】図２のステップＳ４においては、上記図１
の誤差範囲検出部５で、誤差評価値メモリ１からの誤差
評価値（Ｒ_k ）が適正か否かを判定して誤差検出結果を
出力し、更新部７及び出力制御部１０に送る。更新部７
は、この誤差検出結果に従って処理を分岐する。誤差評
価値メモリ１からの誤差評価値（Ｒ_k ）が適正とされる
範囲は０以上Ｄ_k 未満、すなわち、０≦Ｒ_k ＜Ｄ_k であ
り、この条件を満たしている場合、ステップＳ６に進
む。この条件を満たしていないときには、ステップＳ５
に進む。

【００４８】ステップＳ５においては、上記図１の変換
後座標値メモリ４からの変換後座標値Ｑ_k 、誤差評価値
メモリ１からの誤差評価値Ｒ_k 、複合差分値メモリ２か
らの複合差分値Ｃ_k を、更新部７にて更新（この場合は
補正）し、再びステップＳ４に戻る。

【００４９】このステップＳ５での更新（補正）内容を
式で表すと、もし、Ｒ_k ＜０となる場合には、 Ｒ_k ←Ｒ_k ＋｜Ｄ_k ｜ ・・・ （５５） Ｑ_k ←Ｑ_k ＋ΔＱ ・・・ （５６） Ｃ_k ←Ｃ_k ＋ΔＤ ・・・ （５７） に従って、Ｒ_k 、Ｑ_k 、及びＣ_k を補正する。

【００５０】また、もし、Ｒ_k ≧Ｄ_k の場合には、 Ｒ_k ←Ｒ_k −｜Ｄ_k ｜ ・・・ （５８） Ｑ_k ←Ｑ_k ＋ΔＱ ・・・ （５９） Ｃ_k ←Ｃ_k ＋ΔＤ ・・・ （６０） に従って、Ｒ_k 、Ｑ_k 、及びＣ_k を補正する。

【００５１】ここで上記具体的な数値の例をとって説明
すると、Ｒ_k （＝１９）≧Ｄ_k （＝７）であることよ
り、上記（５８）式〜（６０）式による補正を行う。 Ｒ_k ＝１９−７＝１２ Ｑ_k ＝６＋１＝７ Ｃ_k ＝２４＋４＝２８ この１回の補正では、まだＲ_k （＝１２）≧Ｄ_k （＝
７）であるので、もう１回補正する。

【００５２】Ｒ_k ＝１２−７＝５ Ｑ_k ＝７＋１＝８ Ｃ_k ＝２８＋４＝３２ このように、２回の補正で、０≦Ｒ_k （＝５）＜Ｄ
_k （＝７）の条件を満たすようになり、有効なＱ_k の値
（＝８）が求められる。

【００５３】次に、ステップＳ６では、変換後座標値メ
モリ４から取り出され、出力制御部１０を介して得られ
た変換後座標値９に対応する上記テクスチャ座標上の画
素値を、上記スクリーン座標上のポリゴン内の画素に書
き込む。上記具体的な数値の例としては、上述したよう
に、Ｑ_k ＝８が変換後座標（の一成分）となり、これ
が、テクスチャ座標の各成分ｕ，ｖについて求められ
て、座標（ｕ_k ，ｖ_k ）上の画素値がスクリーン座標
（ｘ_k ，ｙ_k ）の画素に書き込まれることは勿論であ
る。

【００５４】次のステップＳ７においては、変換前座標
（上記スクリーン座標）の終了点、すなわち１つの走査
線上のポリゴン内の終了点まで補間したか（座標変換処
理したか）を判断する。ＮＯのときはステップＳ８に進
み、ＹＥＳのときはステップＳ９に進む。

【００５５】ステップＳ８においては、図１の更新部７
が除数値Ｄ_k と誤差評価値Ｒ_k とを更新する。これは、
例えば前述した（１４）式〜（１７）式、すなわち、 Ｄ_k+1 ＝Ｄ_k ＋ΔＤ ・・・ （１４） Ｒ_k+1 ＝Ｒ_k ＋ΔＮ−Ｃ_k ・・・ （１５） Ｑ_k+1 ＝Ｑ_k ・・・ （１６） Ｃ_k+1 ＝Ｃ_k ・・・ （１７） に対応する。

【００５６】上記具体的な数値の例では、 Ｄ_k+1 ＝７＋４＝１１ Ｒ_k+1 ＝５＋４１−３２＝１４ Ｑ_k+1 ＝８ Ｃ_k+1 ＝３２ となる。

【００５７】以上のようなステップＳ５での補正（更
新）処理やステップＳ８での更新処理は、図１の更新部
７で行われる。すなわち、図１の誤差範囲検出部５から
の誤差検出結果出力は、更新部７の選択加算部２４〜２
７の各制御端子に供給されて、これらの選択加算部２４
〜２７での選択加算動作を制御するようになっている。
選択加算部２４には、誤差評価値メモリ１からの誤差評
価値Ｒ_k 、メモリ２０からの被除数差分値ΔＮ（０とΔ
Ｎ）、除数値メモリ２２からの除数値Ｄ_k 、及び複合差
分値メモリ２からの複合差分値Ｃ_k （減算入力−Ｃ_k ）
がそれぞれ供給されており、上記誤差検出結果に応じ
て、上記（１５）式と、上記（５５）式又は（５８）式
の演算を行う。選択加算部２５には、複合差分値メモリ
２からの複合差分値Ｃ_k 、及びメモリ２１からの除数差
分値ΔＤ（ΔＤと０）がそれぞれ供給されており、上記
誤差検出結果に応じて、上記（５７）式又は（６０）式
の演算を行う。選択加算部２６には、除数値メモリ３か
らの除数値Ｄ_k 、及びメモリ２２からの除数差分値ΔＤ
（０とΔＤ）がそれぞれ供給されており、上記誤差検出
結果に応じて、上記（１４）式の演算を行う。また、選
択加算部２７には、変換後座標値メモリ４からの変換後
座標値（の一成分）Ｑ_k 、及びメモリ２３からの変換後
座標の誤差許容範囲であるΔＱ（ΔＱと０）がそれぞれ
供給されており、上記誤差検出結果に応じて、上記（５
６）式又は（６０）式の演算を行う。この場合、選択加
算部２４〜２７は、メモリからの出力を選択して加算
し、０を加算するときは加算をしなかった（入力をその
まま出力する）ことに相当する。この０加算の代わり
に、誤差範囲検出部５からの出力を加算イネーブル信号
として用いるようにしてもよい。さらに、誤差範囲検出
部５からの誤差検出結果出力は、出力制御部１０の制御
端子にも送られている。この出力制御部１０は、変換後
座標値メモリ４から送られる変換後座標値（の一成分）
Ｑ_k を、上記条件０≦Ｒ_k＜Ｄ_k が成り立つときに、最
終的な変換後座標値９として出力する。

【００５８】ところで、上記初期値計算ステップＳ３に
おいて、上記走査線上のポリゴンの開始点で上記座標変
換式Ｎ_k ／Ｄ_k を実際に計算して変換後座標成分Ｑ_k を
求めた直後においては、誤差評価ステップＳ４ではＯＫ
（上記条件を満たす）と判別され、ステップＳ６に進ん
で、変換後座標値Ｑ_k に対応するテクスチャ座標上の画
素値をポリゴン内の画素位置に書き込む。次のステップ
Ｓ７では、同じ走査線上のポリゴンの終了点まで補間に
よる座標変換処理が行われたか否かを判断している。Ｎ
Ｏ（上記終了点にまで達していない）と判別されたとき
には、ステップＳ８に進み、変換前座標（上記スクリー
ン座標）における次の第ｋ＋１番の座標点についての除
数値Ｄ_k+1 、誤差評価値Ｒ_k+1 等に更新する。この更新
後に、上記ステップＳ４に進む。

【００５９】従って、初期値計算直後の処理以外は、ス
テップＳ８での更新後にステップＳ４の誤差評価工程に
移行すると見ることができ、既知の変換後座標成分Ｑ_k
を用いて、上記変換後座標成分Ｑ_k+1 を上記（４）式及
び（５）式により求める、と考えるときの各ステップＳ
８及びＳ５での計算式が、上記（１４）式〜（１７）式
及び前記（１８）式〜（２３）式である。このような考
え方をとるときの補間処理の要部のフローチャートを図
３に示す。

【００６０】この図３においては、初期値計算あるいは
上述した補間処理によって変換前座標（上記スクリーン
座標）の第ｋ番の座標点に対応する変換後座標の一成分
Ｑ_kが既に求められていることを前提とし、この既知の
Ｑ_k を用いて、先ずステップＳ８において、上記（１
４）式〜（１７）式の計算を行い、次の第ｋ＋１番の座
標点についての除数値Ｄ_k+1 、誤差評価値Ｒ_k+1 、変換
後座標値Ｑ_k+1 、及び複合差分値Ｃ_k+1 を求める（更新
する）。

【００６１】次に、この誤差評価値Ｒ_k+1 について上記
図２のステップＳ４に相当する誤差評価を行うわけであ
るが、この図３の例では、先ずステップＳ４ａにおい
て、求められた誤差評価値Ｒ_k+1 が、０以上かつ上記Ｄ
_k+1 の値より小（０≦Ｒ_k+1 ＜Ｄ_k+1 ）の条件を満たす
か否かを判別している。このステップＳ４ａでＹＥＳと
判別されたときには、上記図２のステップＳ６等を介し
て、補間が終了しない限りステップＳ８に進む。ステッ
プＳ４ａでＮＯと判別されたときには、ステップＳ４ｂ
で、Ｒ_k+1 ＜０か、又は否（Ｄ_k+1 ≦Ｒ_k+1 ）かを判別
され、ＹＥＳのときにはステップＳ５ａの第１の補正工
程に進み、ＮＯのときにはステップＳ５ｂの第２の補正
工程に進む。

【００６２】ステップＳ５ａの第１の補正工程では、前
記（１８）式〜（２０）式、すなわち、 Ｒ_k+1 ←Ｒ_k+1 ＋｜Ｄ_k+1 ｜×ΔＱ ・・・ （１８） Ｑ_k+1 ←Ｑ_k+1 ＋ΔＱ ・・・ （１９） Ｃ_k+1 ←Ｃ_k ＋ΔＤ×ΔＱ ・・・ （２０） の各式（ただし、←は代入を表す。）を計算することで
補正を行う。また、ステップＳ５ｂの第２の補正工程で
は、前記（２１）式〜（２３）式、すなわち、 Ｒ_k+1 ←Ｒ_k+1 −｜Ｄ_k+1 ｜×ΔＱ ・・・ （２１） Ｑ_k+1 ←Ｑ_k+1 ＋ΔＱ ・・・ （２２） Ｃ_k+1 ←Ｃ_k ＋ΔＤ×ΔＱ ・・・ （２３） の各式の計算を行って補正する。

【００６３】このようなステップＳ５ａ又はステップＳ
５ｂによる第１又は第２の補正を行った後、再び誤差評
価工程（図３ではステップＳ４ａ）に進み、上記０≦Ｒ
_k+1＜Ｄ_k+1 の条件を満たすようになるまで上記第１又
は第２の補正を繰り返す。

【００６４】以上のような装置及び方法を用いることに
より、除算を行った場合と同じ計算式通りの正確な計算
結果が得られると共に、除算を使わずに加減算だけで座
標変換が実現できる。

【００６５】なお、上記複合差分値Ｃ_k を用いずに座標
変換処理（補間処理）を実行するようにしてもよく、こ
の場合の更新工程では前記（６）式〜（８）式の計算を
行うようにし、上記第１の補正工程では前記（９）式及
び（１０）式の計算を、上記第２の補正工程では前記
（１１）式及び（１２）式の計算をそれぞれ行うように
すればよい。

【００６６】ところで、上記複合差分値Ｃ_k に上記被除
数差分値ΔＮを含ませる（−ΔＮを加える）ことによ
り、図１のメモリ２０を省略することができる。これ
は、Ｃ_kの代わりにＣ_k −ΔＮを用いることに相当し、
上記初期値計算の際に、複合差分値Ｃ_k を、前記（２
４）式、すなわち、 Ｃ_k ＝ΔＤ×Ｑ_k −ΔＮ ・・・ （２４） により求めるようにすればよい。また誤差評価値Ｒ_k の
更新の際には、前記（２６）式、すなわち、 Ｒ_k+1 ＝Ｒ_k −Ｃ_k ・・・ （２６） により求めるようにすればよい。

【００６７】このとき、上記ステップＳ８の更新時には
前記（２５）式〜（２８）式の計算を行い、上記ステッ
プＳ５ａでの第１の補正時には上記（１８）式〜（２
０）式と同様な前記（２９）式〜（３１）式の計算を行
い、上記ステップＳ５ｂでの第２の補正時には上記（２
１）式〜（２３）式と同様な前記（３２）式〜（３４）
式の計算を行うようにすればよい。なお上記更新時の前
記（２５）式、（２７）式及び（２８）式は、上記（１
４）式、（１６）式及び（１７）式とそれぞれ同様なも
のである。

【００６８】このようにすると、ΔＮが複合差分値Ｃ_k
に吸収されるので、図１中のΔＮ記憶用のメモリ２０が
不要となる。

【００６９】次に、さらに他の例として、初期値計算工
程において、複合差分値Ｃ_k を上記（２４）式と同様な
前記（３５）式で計算すると共に、除数値Ｄ_k 及び除数
差分値ΔＤとして、前記（３６）式及び（３７）式、す
なわち、 Ｄ_k ←Ｄ_k ×ΔＱ ・・・ （３６） ΔＤ←ΔＤ×ΔＱ ・・・ （３７） を計算することにより予めΔＱを乗算した値を用いるよ
うにし、補正時の計算を簡略化させてもよい。

【００７０】すなわち、このときの上記第１の補正工程
では、前記（４２）式〜（４４）式、すなわち、 Ｒ_k+1 ←Ｒ_k+1 ＋｜Ｄ_k+1 ｜ ・・・ （４２） Ｑ_k+1 ←Ｑ_k+1 ＋ΔＱ ・・・ （４３） Ｃ_k+1 ←Ｃ_k ＋ΔＤ ・・・ （４４） の各式を計算し、上記第２の補正工程では、前記（４
５）式〜（４７）式、すなわち、 Ｒ_k+1 ←Ｒ_k+1 −｜Ｄ_k+1 ｜ ・・・ （４５） Ｑ_k+1 ←Ｑ_k+1 ＋ΔＱ ・・・ （４６） Ｃ_k+1 ←Ｃ_k ＋ΔＤ ・・・ （４７） の各式を計算するようにすればよい。これらの式で、
（４３）式、（４６）式は上記（１９）式、（２２）式
とそれぞれ同様である。また、上記更新工程において
は、上述した（２５）式〜（２８）式と同様な前記（３
８）式〜（４１）式を用いて計算を行えばよい。

【００７１】なお、本発明は上記実施例のみに限定され
るものではなく、例えば、スクリーン座標のポリゴンを
Ｘ軸（水平軸）に平行な複数の走査線にて分割し、この
走査線に沿ってポリゴン内の画素の座標変換処理（補間
処理）を行っているが、Ｙ軸（垂直軸）に平行な複数の
直線、あるいは任意の傾きを持った互いに平行な複数の
直線によってポリゴンを分割して、この直線に沿って処
理を行うようにしてもよい。また、１つの画素の座標変
換結果を求めた後に、次の処理を行う対象画素として
は、隣接した画素である必要はなく、任意の一定間隔の
画素毎に処理を行うようにしてもよい。

【００７２】

【発明の効果】以上説明したように、本発明に係る座標
変換装置によれば、変換前座標を変数とする複数の多項
式の比により変換後座標を得る座標変換に等価な座標変
換を行う座標変換装置において、上記変換後座標を変換
後座標記憶手段に記憶し、上記変換後座標の誤差評価値
を誤差評価値記憶手段に記憶し、上記誤差評価値が許容
範囲にあること誤差判定手段にて判定し、初期値設定手
段により上記変換前座標に基づいて上記変換後座標記憶
手段及び上記誤差評価値記憶手段の各初期値を設定し、
更新手段により上記誤差判定手段からの出力に応じて上
記変換後座標記憶手段及び上記誤差評価値記憶手段の各
内容を更新して、上記変換前座標から上記変換後座標を
逐次的に求めているため、加減算だけの逐次解法によ
り、比較的小規模なハードウェア量で、正確な結果を高
速に得ることができる。

【００７３】また、本発明に係る座標変換方法によれ
ば、変換前座標を変数とする複数の多項式の比、例えば
Ｎ_k ／Ｄ_k により変換後座標を得る際に、このＮ_k ／Ｄ
_k の除算を整数除算として計算した結果の商を上記第ｋ
番の座標点の変換後の座標点の一座標成分Ｑ_k 、剰余を
Ｒ_k 、すなわち、 Ｎ_k ＝Ｄ_k ×Ｑ_k ＋Ｒ_k ・・・ （１） とし、次の座標点に対して上記座標変換を行った除算結
果の商をＱ_k+1 、剰余をＲ_k+1 、すなわち、 Ｎ_k+1 ＝Ｄ_k+1 ×Ｑ_k+1 ＋Ｒ_k+1 ・・・ （２） とするとき、被除数の差分Ｎ_k+1 −Ｎ_k をΔＮ、除数の
差分Ｄ_k+1 −Ｄ_k をΔＤとして、上記（１）式を書き換
えて、 Ｎ_k ＋ΔＮ＝（Ｄ_k ＋ΔＤ）×Ｑ_k ＋Ｒ_k ＋ΔＮ−ΔＤ×Ｑ_k Ｎ_k+1 ＝Ｄ_k+1 ×Ｑ_k+1 ＋Ｒ_k ＋ΔＮ−ΔＤ×Ｑ_k ・・・ （３） とし、上記（２）式と（３）式とを比較して、 Ｑ_k+1 ＝Ｑ_k ＋（Ｒ_k ＋ΔＮ−ΔＤ×Ｑ_k ）／Ｄ_k+1 ・・・ （４） Ｒ_k+1 ＝（Ｒ_k ＋ΔＮ−ΔＤ×Ｑ_k ）mod Ｄ_k+1 ・・・ （５） が成立することを利用して、上記変換後の座標点の一座
標成分Ｑ_k が既知であるときの次の変換後座標の一成分
Ｑ_k+1 を、Ｎ_k+1 ／Ｄ_k+1 を計算する代わりに上記
（４）式に置き換えて求め、上記（４）式中の除算を加
減算に置き換えて計算しているため、従来の除算を行う
場合に比べてハードウェアの規模を小さく、演算を高速
化でき、また、変換過程を加減算のみで行うにもかかわ
らず、座標変換に歪みが生じないような高精度演算を実
現できる。

【００７４】この場合の具体的な演算手順の一例として
は、上記変換後座標の一成分Ｑ_k+1を、既知の変換後座
標成分Ｑ_k を用いて上記（４）式及び（５）式により求
める際に、上記変換後座標の計算誤差許容範囲である定
数ΔＱを設定し、計算により上記被除数差分値ΔＮ、除
数差分値ΔＤを求め、複合差分値Ｃ_k を、 Ｃ_k ＝ΔＤ×Ｑ_k ・・・ （１３） により求め、Ｄ_k+1 、Ｒ_k+1 、Ｑ_k+1 、及びＣ_k+1 を、 Ｄ_k+1 ＝Ｄ_k ＋ΔＤ ・・・ （１４） Ｒ_k+1 ＝Ｒ_k ＋ΔＮ−Ｃ_k ・・・ （１５） Ｑ_k+1 ＝Ｑ_k ・・・ （１６） Ｃ_k+1 ＝Ｃ_k ・・・ （１７） の各式を計算することにより求め、求められたＲ_k+1 の
値が０より小の条件（Ｒ_k+1 ＜０）を満たすとき、 Ｒ_k+1 ←Ｒ_k+1 ＋｜Ｄ_k+1 ｜×ΔＱ ・・・ （１８） Ｑ_k+1 ←Ｑ_k+1 ＋ΔＱ ・・・ （１９） Ｃ_k+1 ←Ｃ_k ＋ΔＤ×ΔＱ ・・・ （２０） の各式（ただし、←は代入を表す。）により補正を行
い、求められたＲ_k+1 の値が上記Ｄ_k+1 の値以上の条件
（Ｄ_k+1 ≦Ｒ_k+1 ）を満たすとき、 Ｒ_k+1 ←Ｒ_k+1 −｜Ｄ_k+1 ｜×ΔＱ ・・・ （２１） Ｑ_k+1 ←Ｑ_k+1 ＋ΔＱ ・・・ （２２） Ｃ_k+1 ←Ｃ_k ＋ΔＤ×ΔＱ ・・・ （２３） の各式により補正を行い、求められたＲ_k+1 の値が０以
上かつ上記Ｄ_k+1 の値より小の条件（０≦Ｒ_k+1＜Ｄ
_k+1 ）を満たすか否かを判別し、この条件を満たさない
とき上記第１の補正工程又は上記第２の補正工程を繰り
返し、この条件を満たすときのＱ_k+1 を最終的な座標変
換結果とすることが挙げられ、これによって、加減算の
みを用いた座標変換処理（補間処理）が実現できる。

【図面の簡単な説明】

【図１】本発明の座標変換装置の一実施例の概略構成を
示すブロック回路図である。

【図２】本発明に係る座標変換方法の一実施例の概略的
な動作を説明するためのフローチャートである。

【図３】座標変換方法の一実施例の要部動作の例を示す
フローチャートである。

【図４】従来の座標変換処理の一例の動作を説明するた
めのフローチャートである。

【図５】スクリーン座標上のテクスチャを張り付ける前
のポリゴンと、テクスチャ座標上のテクスチャを示す図
である。

【図６】スクリーン座標とテクスチャ座標との対応関係
を網線により示して座標変換を説明するための図であ
る。

【図７】スクリーン座標のポリゴンを複数の走査線に分
割したときの第ｎ番目の走査線上の開始点と終了点とを
示す図である。

【図８】スクリーン座標の走査線上の各画素についての
内挿補間処理を説明するための図である。

【図９】テクスチャマッピングが完了した状態でのスク
リーン座標とテクスチャ座標とを示す図である。

【図１０】従来の座標変換処理の他の例の動作を説明す
るためのフローチャートである。

【符号の説明】

１・・・・・誤差評価値メモリ ２・・・・・複合差分値メモリ ３・・・・・除数値メモリ ４・・・・・変換後座標値メモリ ５・・・・・誤差範囲検出部 ６・・・・・初期値設定部 ７・・・・・更新部 １０・・・・・出力制御部 ２０、２１、２２、２３・・・・・メモリ ２４、２５、２６、２７・・・・・選択加算部

Claims (9)

【特許請求の範囲】
1. 【請求項１】 変換前座標を変数とする複数の多項式の
   比により変換後座標を得る座標変換に等価な座標変換を
   行う座標変換装置において、 上記変換後座標を記憶する変換後座標記憶手段と、 上記変換後座標の誤差評価値を記憶する誤差評価値記憶
   手段と、 上記誤差評価値が許容範囲にあることを判定する誤差判
   定手段と、 上記変換前座標に基づいて上記変換後座標記憶手段及び
   上記誤差評価値記憶手段の各初期値を設定する初期値設
   定手段と、 上記誤差判定手段からの出力に応じて上記変換後座標記
   憶手段及び上記誤差評価値記憶手段の各内容を更新する
   更新手段とを有し、上記変換前座標から上記変換後座標
   を逐次的に求めることを特徴とする座標変換装置。
2. 【請求項２】 上記更新手段は、複数の入力を選択して
   演算を行う選択演算部を複数有し、 上記変換後座標記憶手段と上記誤差評価値記憶手段の値
   を並列に更新して高速化することを特徴とする請求項１
   記載の座標変換装置。
3. 【請求項３】 変換前座標を変数とする複数の多項式の
   比により変換後座標を得る座標変換方法において、 変換前の任意の第ｋ番の座標点の座標成分の関数である
   多項式をそれぞれＮ_k及びＤ_k として変換後座標の一成
   分をこれらの多項式の比をＮ_k ／Ｄ_k により求めるもの
   とし、 上記Ｎ_k ／Ｄ_k の除算を整数除算として計算した結果の
   商を上記第ｋ番の座標点の変換後の座標点の一座標成分
   Ｑ_k 、剰余をＲ_k 、すなわち、 Ｎ_k ＝Ｄ_k ×Ｑ_k ＋Ｒ_k ・・・ （１） とし、変換前の次の第ｋ＋１番の座標点に対して上記座
   標変換を行った除算結果の商をＱ_k+1 、剰余をＲ_k+1 、
   すなわち、 Ｎ_k+1 ＝Ｄ_k+1 ×Ｑ_k+1 ＋Ｒ_k+1 ・・・ （２） とするとき、被除数の差分Ｎ_k+1 −Ｎ_k をΔＮ、除数の
   差分Ｄ_k+1 −Ｄ_k をΔＤとして、上記（１）式を書き換
   えて、 Ｎ_k ＋ΔＮ＝（Ｄ_k ＋ΔＤ）×Ｑ_k ＋Ｒ_k ＋ΔＮ−ΔＤ×Ｑ_k Ｎ_k+1 ＝Ｄ_k+1 ×Ｑ_k+1 ＋Ｒ_k ＋ΔＮ−ΔＤ×Ｑ_k ・・・ （３） とし、上記（２）式と（３）式とを比較して、 Ｑ_k+1 ＝Ｑ_k ＋（Ｒ_k ＋ΔＮ−ΔＤ×Ｑ_k ）／Ｄ_k+1 ・・・ （４） Ｒ_k+1 ＝（Ｒ_k ＋ΔＮ−ΔＤ×Ｑ_k ）mod Ｄ_k+1 ・・・ （５） が成立することを利用して、上記変換後の座標点の一座
   標成分Ｑ_k が既知であるときの次の変換後座標の一成分
   Ｑ_k+1 を、Ｎ_k+1 ／Ｄ_k+1 を計算する代わりに上記
   （４）式に置き換えて求める工程と、 上記（４）式中の除算を加減算に置き換えて計算する工
   程と、を有することを特徴とする座標変換方法。
4. 【請求項４】 上記変換後座標の一成分Ｑ_k+1 を、既知
   の変換後座標成分Ｑ_kを用いて上記（４）式及び（５）
   式により求める際に、 上記変換後座標の計算誤差許容範囲である定数ΔＱを設
   定し、計算により上記被除数差分値ΔＮ、除数差分値Δ
   Ｄを求める第１の計算工程と、 Ｄ_k+1 、Ｒ_k+1 、及びＱ_k+1 を、 Ｄ_k+1 ＝Ｄ_k ＋ΔＤ ・・・ （６） Ｒ_k+1 ＝Ｒ_k ＋ΔＮ−ΔＤ×Ｑ_k ・・・ （７） Ｑ_k+1 ＝Ｑ_k ・・・ （８） の各式を計算することにより求める第２の計算工程と、 求められたＲ_k+1 の値が０より小の条件（Ｒ_k+1 ＜０）
   を満たすとき、 Ｒ_k+1 ←Ｒ_k+1 ＋｜Ｄ_k+1 ｜×ΔＱ ・・・ （９） Ｑ_k+1 ←Ｑ_k+1 ＋ΔＱ ・・・ （１０） の各式（ただし、←は代入を表す。）により補正を行う
   第１の補正工程と、 求められたＲ_k+1 の値が上記Ｄ_k+1 の値以上の条件（Ｄ
   _k+1 ≦Ｒ_k+1 ）を満たすとき、 Ｒ_k+1 ←Ｒ_k+1 −｜Ｄ_k+1 ｜×ΔＱ ・・・ （１１） Ｑ_k+1 ←Ｑ_k+1 ＋ΔＱ ・・・ （１２） の各式により補正を行う第２の補正工程と、 求められたＲ_k+1 の値が０以上かつ上記Ｄ_k+1 の値より
   小の条件（０≦Ｒ_k+1＜Ｄ_k+1 ）を満たすか否かを判別
   し、この条件を満足しないとき上記第１の補正工程又は
   上記第２の補正工程を繰り返し、この条件を満足すると
   きのＱ_k+1 を最終的な座標変換結果とする誤差評価工程
   とを有することを特徴とする請求項３記載の座標変換方
   法。
5. 【請求項５】 上記変換後座標の一成分Ｑ_k+1 を、既知
   の変換後座標成分Ｑ_kを用いて上記（４）式及び（５）
   式により求める際に、 上記変換後座標の計算誤差許容範囲である定数ΔＱを設
   定し、計算により上記被除数差分値ΔＮ、除数差分値Δ
   Ｄを求め、複合差分値Ｃ_k を、 Ｃ_k ＝ΔＤ×Ｑ_k ・・・ （１３） により求める第１の計算工程と、 Ｄ_k+1 、Ｒ_k+1 、Ｑ_k+1 、及びＣ_k+1 を、 Ｄ_k+1 ＝Ｄ_k ＋ΔＤ ・・・ （１４） Ｒ_k+1 ＝Ｒ_k ＋ΔＮ−Ｃ_k ・・・ （１５） Ｑ_k+1 ＝Ｑ_k ・・・ （１６） Ｃ_k+1 ＝Ｃ_k ・・・ （１７） の各式を計算することにより求める第２の計算工程と、 求められたＲ_k+1 の値が０より小の条件（Ｒ_k+1 ＜０）
   を満たすとき、 Ｒ_k+1 ←Ｒ_k+1 ＋｜Ｄ_k+1 ｜×ΔＱ ・・・ （１８） Ｑ_k+1 ←Ｑ_k+1 ＋ΔＱ ・・・ （１９） Ｃ_k+1 ←Ｃ_k ＋ΔＤ×ΔＱ ・・・ （２０） の各式（ただし、←は代入を表す。）により補正を行う
   第１の補正工程と、 求められたＲ_k+1 の値が上記Ｄ_k+1 の値以上の条件（Ｄ
   _k+1 ≦Ｒ_k+1 ）を満たすとき、 Ｒ_k+1 ←Ｒ_k+1 −｜Ｄ_k+1 ｜×ΔＱ ・・・ （２１） Ｑ_k+1 ←Ｑ_k+1 ＋ΔＱ ・・・ （２２） Ｃ_k+1 ←Ｃ_k ＋ΔＤ×ΔＱ ・・・ （２３） の各式により補正を行う第２の補正工程と、 求められたＲ_k+1 の値が０以上かつ上記Ｄ_k+1 の値より
   小の条件（０≦Ｒ_k+1＜Ｄ_k+1 ）を満たすか否かを判別
   し、この条件を満たさないとき上記第１の補正工程又は
   上記第２の補正工程を繰り返し、この条件を満たすとき
   のＱ_k+1 を最終的な座標変換結果とする誤差評価工程と
   を有することを特徴とする請求項３記載の座標変換方
   法。
6. 【請求項６】 上記変換後座標の一成分Ｑ_k+1 を、既知
   の変換後座標成分Ｑ_kを用いて上記（４）式及び（５）
   式により求める際に、 上記変換後座標の計算誤差許容範囲である定数ΔＱを設
   定し、計算により上記被除数差分値ΔＮ、除数差分値Δ
   Ｄを求め、複合差分値Ｃ_k を、 Ｃ_k ＝ΔＤ×Ｑ_k −ΔＮ ・・・ （２４） により求める第１の計算工程と、 Ｄ_k+1 、Ｒ_k+1 、Ｑ_k+1 、及びＣ_k+1 を、 Ｄ_k+1 ＝Ｄ_k ＋ΔＤ ・・・ （２５） Ｒ_k+1 ＝Ｒ_k −Ｃ_k ・・・ （２６） Ｑ_k+1 ＝Ｑ_k ・・・ （２７） Ｃ_k+1 ＝Ｃ_k ・・・ （２８） の各式を計算することにより求める第２の計算工程と、 求められたＲ_k+1 の値が０より小の条件（Ｒ_k+1 ＜０）
   を満たすとき、 Ｒ_k+1 ←Ｒ_k+1 ＋｜Ｄ_k+1 ｜×ΔＱ ・・・ （２９） Ｑ_k+1 ←Ｑ_k+1 ＋ΔＱ ・・・ （３０） Ｃ_k+1 ←Ｃ_k ＋ΔＤ×ΔＱ ・・・ （３１） の各式（ただし、←は代入を表す。）により補正を行う
   第１の補正工程と、 求められたＲ_k+1 の値が上記Ｄ_k+1 の値以上の条件（Ｄ
   _k+1 ≦Ｒ_k+1 ）を満たすとき、 Ｒ_k+1 ←Ｒ_k+1 −｜Ｄ_k+1 ｜×ΔＱ ・・・ （３２） Ｑ_k+1 ←Ｑ_k+1 ＋ΔＱ ・・・ （３３） Ｃ_k+1 ←Ｃ_k ＋ΔＤ×ΔＱ ・・・ （３４） の各式により補正を行う第２の補正工程と、 求められたＲ_k+1 の値が０以上かつ上記Ｄ_k+1 の値より
   小の条件（０≦Ｒ_k+1＜Ｄ_k+1 ）を満たすか否かを判別
   し、この条件を満たさないとき上記第１の補正工程又は
   上記第２の補正工程を繰り返し、この条件を満たすとき
   のＱ_k+1 を最終的な座標変換結果とする誤差評価工程と
   を有することを特徴とする請求項３記載の座標変換方
   法。
7. 【請求項７】 上記変換後座標の一成分Ｑ_k+1 を、既知
   の変換後座標成分Ｑ_kを用いて上記（４）式及び（５）
   式により求める際に、 上記変換後座標の計算誤差許容範囲である定数ΔＱを設
   定し、計算により上記被除数差分値ΔＮ、除数差分値Δ
   Ｄを求め、複合差分値Ｃ_k 、除数値Ｄ_k 及び除数差分値
   ΔＤを、 Ｃ_k ＝ΔＤ×Ｑ_k −ΔＮ ・・・ （３５） Ｄ_k ←Ｄ_k ×ΔＱ ・・・ （３６） ΔＤ←ΔＤ×ΔＱ ・・・ （３７） の各式（ただし、←は代入を表す。）により求める第１
   の計算工程と、 Ｄ_k+1 、Ｒ_k+1 、Ｑ_k+1 、及びＣ_k+1 を、 Ｄ_k+1 ＝Ｄ_k ＋ΔＤ ・・・ （３８） Ｒ_k+1 ＝Ｒ_k −Ｃ_k ・・・ （３９） Ｑ_k+1 ＝Ｑ_k ・・・ （４０） Ｃ_k+1 ＝Ｃ_k ・・・ （４１） の各式を計算することにより求める第２の計算工程と、 求められたＲ_k+1 の値が０より小の条件（Ｒ_k+1 ＜０）
   を満たすとき、 Ｒ_k+1 ←Ｒ_k+1 ＋｜Ｄ_k+1 ｜ ・・・ （４２） Ｑ_k+1 ←Ｑ_k+1 ＋ΔＱ ・・・ （４３） Ｃ_k+1 ←Ｃ_k ＋ΔＤ ・・・ （４４） の各式により補正を行う第１の補正工程と、 求められたＲ_k+1 の値が上記Ｄ_k+1 の値以上の条件（Ｄ
   _k+1 ≦Ｒ_k+1 ）を満たすとき、 Ｒ_k+1 ←Ｒ_k+1 −｜Ｄ_k+1 ｜ ・・・ （４５） Ｑ_k+1 ←Ｑ_k+1 ＋ΔＱ ・・・ （４６） Ｃ_k+1 ←Ｃ_k ＋ΔＤ ・・・ （４７） の各式により補正を行う第２の補正工程と、 求められたＲ_k+1 の値が０以上かつ上記Ｄ_k+1 の値より
   小の条件（０≦Ｒ_k+1＜Ｄ_k+1 ）を満たすか否かを判別
   し、この条件を満たさないとき上記第１の補正工程又は
   上記第２の補正工程を繰り返し、この条件を満たすとき
   のＱ_k+1 を最終的な座標変換結果とする誤差評価工程と
   を有することを特徴とする請求項３記載の座標変換方
   法。
8. 【請求項８】 上記第１の計算工程を１回行った後、上
   記第２の計算工程、上記第１又は第２の補正工程、及び
   上記誤差評価工程を繰り返し、一連の座標に対して座標
   変換を行うことを特徴とする請求項４乃至７記載の座標
   変換方法。
9. 【請求項９】 上記変換後座標の計算誤差許容範囲であ
   る定数ΔＱを１とすることを特徴とする請求項４乃至７
   記載の座標変換方法。