(57)【要約】
2003001457.tif 000125で表せるアフィン変換を行う情報処理装置において、アフィン変換の行列Ａにλ（≠０）をかけた行列2003001457.tif 000126を予めメモリ部に記憶しておく。アフィン変換により、座標（ｘ，ｙ，ｚ）ｔを座標（ｘ’，ｙ’，ｚ’）ｔに変換する演算処理を行う場合、メモリ部からＡ’と行列（ｔ１，ｔ２，ｔ３）ｔとを読み出し、2003001457.tif 000127を演算して、座標（ｘ’，ｙ’，ｚ’）ｔを求める。
2003001457.tif 000002
【特許請求の範囲】
【請求項１】
座標値が整数に限定され、座標（ｘ，ｙ，ｚ）ｔを、
2003001457.tif 000096
で表現されるアフィン変換により、座標（ｘ’，ｙ’，ｚ’）ｔに変換処理を行う３次元画像の描画を行う情報処理装置であって、
アフィン変換の行列
2003001457.tif 000097
にλ（≠０）をかけた行列
2003001457.tif 000098
と、行列（ｔ１，ｔ２，ｔ３）ｔと、形状データとが格納されたメモリと、
前記形状データの座標（ｘ，ｙ，ｚ）ｔを、行列Ａ及び行列（ｔ１，ｔ２，ｔ３）ｔとのアフィン変換により、座標（ｘ’，ｙ’，ｚ’）ｔに変換する際、前記メモリより、行列Ａ’と、行列（ｔ１，ｔ２，ｔ３）ｔとを読み出し、
2003001457.tif 000099
を演算して、座標（ｘ’，ｙ’，ｚ’）ｔを演算する演算手段と
を有することを特徴とする情報処理装置。
【請求項２】
前記λを２ｎ（ｎ＞１）に限定し、
前記演算手段は、
2003001457.tif 000100
の除算演算を、ｎ桁右シフトすることにより演算する手段であることを特徴とする請求項１に記載の情報処理装置。
【請求項３】
前記演算手段は、各被除数に定数λ／２を加えた後、ｎ桁右シフトすることにより演算する手段であることを特徴とする請求項２に記載の情報処理装置。
【請求項４】
予めλ（≠０）をかけた二つ以上のパラメータを合成する合成手段を有することを特徴とする請求項１から請求項３のいずれかに記載の情報処理装置。
【請求項５】
2003001457.tif 000101
変化量に関連付けられて格納されたメモリと、
ｙ座標に対するｘ座標の変化量、
2003001457.tif 000102
を演算する際、
前記ｙ座標の変化量に対応するμを前記メモリより読み出して乗算により、
2003001457.tif 000103
を演算し、
算出されたΔｘ’を、ｎ桁右シフトすることにより、Δｘを演算する演算手段とを更に有することを特徴とする請求項１から請求項４のいずれかに記載の情報処理装置。
【請求項６】
座標値が整数に限定され、座標（ｘ，ｙ，ｚ）ｔを、
2003001457.tif 000104
で表現されるアフィン変換により、座標（ｘ’，ｙ’，ｚ’）ｔに変換処理を行う３次元画像の描画処理方法であって、
形状データの座標（ｘ，ｙ，ｚ）ｔを、行列Ａ及び行列（ｔ１，ｔ２，ｔ３）ｔとのアフィン変換により、座標（ｘ’，ｙ’，ｚ’）ｔに変換する際、メモリに記憶されている、行列Ａにλ（≠０）をかけたパラメータＡ’
2003001457.tif 000105
と、行列（ｔ１，ｔ２，ｔ３）ｔとを読み出すステップと、
前記読み出した行列Ａ’と、行列（ｔ１，ｔ２，ｔ３）ｔとに基づいて、
2003001457.tif 000106
を演算して、座標（ｘ’，ｙ’，ｚ’）ｔを演算するステップと
を有することを特徴とする描画処理方法。
【請求項７】
前記λを２ｎ（ｎ＞１）に限定し、
前記演算するステップは、
2003001457.tif 000107
の除算演算を、ｎ桁右シフトすることにより、座標（ｘ’，ｙ’，ｚ’）ｔを演算するステップであることを特徴とする請求項６に記載の描画処理方法。
【請求項８】
前記ｎ桁右シフトする前に、各被除数に定数λ／２を加算するステップを更に有することを特徴とする請求項７に記載の描画処理方法。
【請求項９】
予めλ（≠０）をかけた二つ以上のパラメータを合成するステップを更に有することを特徴とする請求項６から請求項８のいずれかに記載の描画処理方法。
【請求項１０】
ｙ座標に対するｘ座標の変化量、
2003001457.tif 000108
を演算する際、
2003001457.tif 000109
に対応して記憶されているメモリから、前記演算するｙ座標の変化量に対応する定数μを読み出すステップと、
前記読み出した定数μに基づいて、
2003001457.tif 000110
を演算するステップと、
算出されたΔｘ’を、ｎ桁右シフトすることにより、Δｘを演算するステップと
を更に有することを特徴とする請求項６から請求項９のいずれかに記載の描画処理方法。
【請求項１１】
座標値が整数に限定され、座標（ｘ，ｙ，ｚ）ｔを、
2003001457.tif 000111
で表現されるアフィン変換により、座標（ｘ’，ｙ’，ｚ’）ｔに変換処理を、情報処理装置に行わせるプログラムであって、
形状データの座標（ｘ，ｙ，ｚ）ｔを、行列Ａ及び行列（ｔ１，ｔ２，ｔ３）ｔとのアフィン変換により、座標（ｘ’，ｙ’，ｚ’）ｔに変換する際、メモリに記憶されている、行列Ａにλ（≠０）をかけたパラメータＡ’
2003001457.tif 000112
と、行列（ｔ１，ｔ２，ｔ３）ｔとを読み出すステップと、
前記読み出した行列Ａ’と、行列（ｔ１，ｔ２，ｔ３）ｔとに基づいて、
2003001457.tif 000113
を演算して、座標（ｘ’，ｙ’，ｚ’）ｔを演算するステップと
を有することを特徴とするプログラム。
【請求項１２】
前記プログラムは、
前記λを２ｎ（ｎ＞１）に限定されている場合において、
前記演算するステップは、情報処理装置に、
2003001457.tif 000114
の除算演算を、ｎ桁右シフトすることにより、座標（ｘ’，ｙ’，ｚ’）ｔを演算させるステップであることを特徴とする請求項１１に記載のプログラム。
【請求項１３】
情報処理装置に、前記ｎ桁右シフトする前に、各被除数に定数λ／２を加算させるステップを更に有することを特徴とする請求項１２に記載のプログラム。
【請求項１４】
情報処理装置に、予めλ（≠０）をかけた二つ以上のパラメータを合成させるステップを更に有することを特徴とする請求項１１から請求項１３のいずれかに記載のプログラム。
【請求項１５】
情報処理装置に、
ｙ座標に対するｘ座標の変化量、
2003001457.tif 000115
を演算する際、
2003001457.tif 000116
に対応して記憶されているメモリから、前記演算するｙ座標の変化量に対応する定数μを読み出させるステップと、
前記読み出した定数μに基づいて、
2003001457.tif 000117
を演算させるステップと、
算出されたΔｘ’を、ｎ桁右シフトすることにより、Δｘを演算させるステップと
を更に有することを特徴とする請求項１１から請求項１４のいずれかに記載のプログラム。
【請求項１６】
座標値が整数に限定され、座標（ｘ，ｙ，ｚ）ｔを、
2003001457.tif 000118
で表現されるアフィン変換により、座標（ｘ’，ｙ’，ｚ’）ｔに変換処理を、情報処理装置に行わせるプログラムが格納された記録媒体であって、
前記プログラムは、
形状データの座標（ｘ，ｙ，ｚ）ｔを、行列Ａ及び行列（ｔ１，ｔ２，ｔ３）ｔとのアフィン変換により、座標（ｘ’，ｙ’，ｚ’）ｔに変換する際、メモリに記憶されている、行列Ａにλ（≠０）をかけたパラメータＡ’
2003001457.tif 000119
と、行列（ｔ１，ｔ２，ｔ３）ｔとを読み出すステップと、
前記読み出した行列Ａ’と、行列（ｔ１，ｔ２，ｔ３）ｔとに基づいて、
2003001457.tif 000120
を演算して、座標（ｘ’，ｙ’，ｚ’）ｔを演算するステップと
を有することを特徴とするプログラムが格納された記録媒体。
【請求項１７】
前記プログラムは、
前記λを２ｎ（ｎ＞１）に限定されている場合において、
前記演算するステップは、情報処理装置に、
2003001457.tif 000121
の除算演算を、ｎ桁右シフトすることにより、座標（ｘ’，ｙ’，ｚ’）ｔを演算させるステップであることを特徴とする請求項１６に記載のプログラムが格納された記録媒体。
【請求項１８】
前記プログラムは、情報処理装置に、前記ｎ桁右シフトする前に、各被除数に定数λ／２を加算させるステップを更に有することを特徴とする請求項１７に記載のプログラムが格納された記録媒体。
【請求項１９】
前記プログラムは、情報処理装置に、予めλ（≠０）をかけた二つ以上のパラメータを合成させるステップを更に有することを特徴とする請求項１６から請求項１８のいずれかに記載のプログラムが格納された記録媒体。
【請求項２０】
前記プログラムは、情報処理装置に、
ｙ座標に対するｘ座標の変化量、
2003001457.tif 000122
を演算する際、
2003001457.tif 000123
に対応して記憶されているメモリから、前記演算するｙ座標の変化量に対応する定数μを読み出させるステップと、
前記読み出した定数μに基づいて、
2003001457.tif 000124
を演算させるステップと、
算出されたΔｘ’を、ｎ桁右シフトすることにより、Δｘを演算させるステップと
を更に有することを特徴とする請求項１６から請求項１９のいずれかに記載のプログラムが格納された記録媒体。
【発明の詳細な説明】
技術分野
本発明は３次元画像の描画の技術に関し、特に３次元画像の描画の処理時に行われるジオメトリ演算や除算の処理を軽減し、ＦＰＵ（浮動小数点演算ユニット）を持たない情報処理装置や、ＣＰＵの処理能力が低い情報処理装置であっても３次元グラフィクの描画を可能とする技術に関する。
背景技術
３次元グラフィクを描画する場合、情報処理端末は、
（１）３次元の物体をずらしたりする座標変換演算（Ｔｒａｎｓｆｏｒｍａｔｉｏｎ）、
（２）物体に光源（例えば太陽など）から光が当たっていると考えて、日向になっている部分と日陰になっている部分とを計算する光源計算処理（Ｌｉｇｈｔｉｎｇ）
（３）物体をドットと呼ばれるカラムに分割する処理（ラスタライズ）
（４）そのカラムにテクスチャー（模様）を張り込んでいく（テクスチャーマッピング）
等の処理を行う。
通常、情報処理装置本体のＣＰＵは、（１）と（２）とのいわゆるジオメトリ演算という作業を担当し、ＣＰＵのＦＰＵ（浮動小数点演算ユニット）を利用して処理している。
更に、（３）と（４）とのいわゆるラスタライズの処理は、通常、３Ｄグラフィックスアクセラレータが行っている。
しかしながら、（１）と（２）とのいわゆるジオメトリ演算という作業はＣＰＵのＦＰＵ（浮動小数点演算ユニット）を利用して行なわれていが、ＦＰＵはジオメトリ演算だけでなく、浮動小数点一般を計算するために設計されているほか、ＣＰＵは他の処理も行ったりしており、必ずしも３次元のグラフィクを描画する処理に適したものではない。
そこで、そのジオメトリ演算をグラフィックスチップで行えるように設計した（つまりジオメトリエンジンを内蔵）３Ｄグラフィックスアクセラレータも登場しており、ＣＰＵの負荷率を下げる工夫がされているほか、何よりもジオメトリ演算の性能をＣＰＵで行う場合に比べて大幅に向上させることが可能、つまり３Ｄの描画性能を向上させることを可能としている。
しかしながら、３Ｄグラフィックスアクセラレータは高価なのものであり、全ての情報処理装置が備えている訳ではない。
更に、情報処理装置の中には、例えば携帯電話や、ＰＤＡ（Ｐｅｒｓｏｎａｌ  Ｄｉｇｉｔａｌ（Ｄａｔａ）Ａｓｓｉｓｔａｎｔｓ）のように３Ｄグラフィックスアクセラレータどころか、ＦＰＵ（浮動小数点演算ユニット）も備えていないものもある。
このような情報処理装置では、一般にＣＰＵの能力も低く、３Ｄグラフィックスは無理とされていた。
更に、除算処理は乗算処理に比べてたいへん低速であり、高速に演算処理を行う為には、除算をなるべく減らすことが好ましい。
そこで、本発明は、３次元グラフィクの描画の処理時に行われるジオメトリ演算において、整数演算処理を行うことによって、ＦＰＵ（浮動小数点演算ユニット）を持たない情報処理装置であっても３次元グラフィクの描画を可能とする技術を提供することを目的としている。
また、本発明は、ラスタライズ処理の際、除算を行わずラスタライズ処理を行うことによって、処理能力が低いＣＰＵを持つ情報処理装置であっても、３次元グラフィクの描画を高速に可能とする技術を提供することを目的としている。
発明の開示
上記目的を達成する第１の発明は、座標値が整数に限定され、座標（ｘ，ｙ，ｚ）ｔを、
2003001457.tif 000003
で表現されるアフィン変換により、座標（ｘ’，ｙ’，ｚ’）ｔに変換処理を行う３次元画像の描画を行う情報処理装置であって、
アフィン変換の行列
2003001457.tif 000004
にλ（≠０）をかけた行列
2003001457.tif 000005
と、行列（ｔ１，ｔ２，ｔ３）ｔと、形状データとが格納されたメモリと、
前記形状データの座標（ｘ，ｙ，ｚ）ｔを、行列Ａ及び行列（ｔ１，ｔ２，ｔ３）ｔとのアフィン変換により、座標（ｘ’，ｙ’，ｚ’）ｔに変換する際、前記メモリより、行列Ａ’と、行列（ｔ１，ｔ２，ｔ３）ｔとを読み出し、
2003001457.tif 000006
を演算して、座標（ｘ’，ｙ’，ｚ’）ｔを演算する演算手段と
を有することを特徴とする。
上記目的を達成する第２の発明は、上記第１の発明において、前記λを２ｎ（ｎ＞１）に限定し、
前記演算手段は、
2003001457.tif 000007
の除算演算を、ｎ桁右シフトすることにより演算する手段であることを特徴とする。
上記目的を達成する第３の発明は、上記第２の発明において、前記演算手段は、各被除数に定数λ／２を加えた後、ｎ桁右シフトすることにより演算する手段であることを特徴とする。
上記目的を達成する第４の発明は、上記第１、２、３の発明において、予めλ（≠０）をかけた二つ以上のパラメータを合成する合成手段を有することを特徴とする。
上記目的を達成する第２の発明は、上記第１、２、３，４の発明に
2003001457.tif 000008
の変化量をインデックスとして格納されたメモリと、
ｙ座標に対するｘ座標の変化量、
2003001457.tif 000009
を演算する際、
前記ｙ座標の変化量に対応するμを前記メモリより読み出して乗算により、
2003001457.tif 000010
を演算し、
算出されたΔｘ’を、ｎ桁右シフトすることにより、Δｘを演算する演算手段とを更に有することを特徴とする。
上記目的を達成する第６の発明は、座標値が整数に限定され、座標（ｘ，ｙ，ｚ）ｔを、
2003001457.tif 000011
で表現されるアフィン変換により、座標（ｘ’，ｙ’，ｚ’）ｔに変換処理を行う３次元画像の描画処理方法であって、
形状データの座標（ｘ，ｙ，ｚ）ｔを、行列Ａ及び行列（ｔ１，ｔ２，ｔ３）ｔとのアフィン変換により、座標（ｘ’，ｙ’，ｚ’）ｔに変換する際、メモリに記憶されている、行列Ａにλ（≠０）をかけたパラメータＡ’
2003001457.tif 000012
と、行列（ｔ１，ｔ２，ｔ３）ｔとを読み出すステップと、
前記読み出した行列Ａ’と、行列（ｔ１，ｔ２，ｔ３）ｔとに基づいて、
2003001457.tif 000013
を演算して、座標（ｘ’，ｙ’，ｚ’）ｔを演算するステップと
を有することを特徴とする。
上記目的を達成する第７の発明は、上記第６の発明において、前記λを２ｎ（ｎ＞１）に限定し、
前記演算するステップは、
2003001457.tif 000014
の除算演算を、ｎ桁右シフトすることにより、座標（ｘ’，ｙ’，ｚ’）ｔを演算するステップであることを特徴とする。
上記目的を達成する第８の発明は、上記第７の発明において、前記ｎ桁右シフトする前に、各被除数に定数λ／２を加算するステップを更に有することを特徴とする。
上記目的を達成する第９の発明は、上記第６、７、８の発明において、予めλ（≠０）をかけた二つ以上のパラメータを合成するステップを更に有することを特徴とする。
上記目的を達成する第９の発明は、上記第６、７、８、９の発明において、ｙ座標に対するｘ座標の変化量、
2003001457.tif 000015
を演算する際、
2003001457.tif 000016
に対応して記憶されているメモリから、前記演算するｙ座標の変化量に対応する定数μを読み出すステップと、
前記読み出した定数μに基づいて、
2003001457.tif 000017
を演算するステップと、
算出されたΔｘ’を、ｎ桁右シフトすることにより、Δｘを演算するステップと
を更に有することを特徴とする。
上記目的を達成する第１１の発明は、座標値が整数に限定され、座標（ｘ，ｙ，ｚ）ｔを、
2003001457.tif 000018
で表現されるアフィン変換により、座標（ｘ’，ｙ’，ｚ’）ｔに変換処理を、情報処理装置に行わせるプログラムであって、
形状データの座標（ｘ，ｙ，ｚ）ｔを、行列Ａ及び行列（ｔ１，ｔ２，ｔ３）ｔとのアフィン変換により、座標（ｘ’，ｙ’，ｚ’）ｔに変換する際、メモリに記憶されている、行列Ａにλ（≠０）をかけたパラメータＡ’
2003001457.tif 000019
と、行列（ｔ１，ｔ２，ｔ３）ｔとを読み出すステップと、
前記読み出した行列Ａ’と、行列（ｔ１，ｔ２，ｔ３）ｔとに基づいて、
2003001457.tif 000020
を演算して、座標（ｘ’，ｙ’，ｚ’）ｔを演算するステップと
を有することを特徴とするプログラムである。
上記目的を達成する第１２の発明は、上記第１１の発明において、前記プログラムは、
前記λを２ｎ（ｎ＞１）に限定されている場合において、
前記演算するステップは、情報処理装置に、
2003001457.tif 000021
の除算演算を、ｎ桁右シフトすることにより、座標（ｘ’，ｙ’，ｚ’）ｔを演算させるステップであることを特徴とするプログラムである。
上記目的を達成する第１３の発明は、上記第１２の発明において、情報処理装置に、前記ｎ桁右シフトする前に、各被除数に定数λ／２を加算させるステップを更に有することを特徴とするプログラムである。
上記目的を達成する第１４の発明は、上記第１１、１２、１３の発明において、情報処理装置に、予めλ（≠０）をかけた二つ以上のパラメータを合成させるステップを更に有することを特徴とする。
上記目的を達成する第１５の発明は、上記第１１、１２、１３、１４の発明において、情報処理装置に、
ｙ座標に対するｘ座標の変化量、
2003001457.tif 000022
を演算する際、
2003001457.tif 000023
に対応して記憶されているメモリから、前記演算するｙ座標の変化量に対応する定数μを読み出させるステップと、
前記読み出した定数μに基づいて、
2003001457.tif 000024
を演算させるステップと、
算出されたΔｘ’を、ｎ桁右シフトすることにより、Δｘを演算させるステップと
を更に有することを特徴とするプログラムである。
上記目的を達成する第１６の発明は、座標値が整数に限定され、座標（ｘ，ｙ，ｚ）ｔを、
2003001457.tif 000025
で表現されるアフィン変換により、座標（ｘ’，ｙ’，ｚ’）ｔに変換処理を、情報処理装置に行わせるプログラムが格納された記録媒体であって、
前記プログラムは、
形状データの座標（ｘ，ｙ，ｚ）ｔを、行列Ａ及び行列（ｔ１，ｔ２，ｔ３）ｔとのアフィン変換により、座標（ｘ’，ｙ’，ｚ’）ｔに変換する際、メモリに記憶されている、行列Ａにλ（≠０）をかけたパラメータＡ’
2003001457.tif 000026
と、行列（ｔ１，ｔ２，ｔ３）ｔとを読み出すステップと、
前記読み出した行列Ａ’と、行列（ｔ１，ｔ２，ｔ３）ｔとに基づいて、
2003001457.tif 000027
を演算して、座標（ｘ’，ｙ’，ｚ’）ｔを演算するステップと
を有することを特徴とするプログラムが格納された記録媒体である。
上記目的を達成する第１７の発明は、上記第１６の発明において、前記プログラムは、
前記λを２ｎ（ｎ＞１）に限定されている場合において、
前記演算するステップは、情報処理装置に、
2003001457.tif 000028
の除算演算を、ｎ桁右シフトすることにより、座標（ｘ’，ｙ’，ｚ’）ｔを演算させるステップであることを特徴とするプログラムが格納された記録媒体である。
上記目的を達成する第１８の発明は、上記第１７の発明において、前記プログラムは、情報処理装置に、前記ｎ桁右シフトする前に、各被除数に定数λ／２を加算させるステップを更に有することを特徴とするプログラムが格納された記録媒体である。
上記目的を達成する第１９の発明は、上記第１６、１７、１８の発明において、前記プログラムは、情報処理装置に、予めλ（≠０）をかけた二つ以上のパラメータを合成させるステップを更に有することを特徴とするプログラムが格納された記録媒体である。
上記目的を達成する第２０の発明は、上記第１６、１７、１８、１９の発明において、前記プログラムは、情報処理装置に、
ｙ座標に対するｘ座標の変化量、
2003001457.tif 000029
を演算する際、
2003001457.tif 000030
に対応して記憶されているメモリから、前記演算するｙ座標の変化量に対応する定数μを読み出させるステップと、
前記読み出した定数μに基づいて、
2003001457.tif 000031
を演算させるステップと、
算出されたΔｘ’を、ｎ桁右シフトすることにより、Δｘを演算させるステップと
を更に有することを特徴とするプログラムが格納された記録媒体である。
発明を実施するための最良の形態
本発明の実施するための最良の形態を説明する。
まず、本発明の特徴である情報処理装置を用いた整数によるジオメトリ演算と、除算を使用しない三角形ラスタライズとについて説明する。
＜整数によるジオメトリ演算＞
１．アフィン変換による座標変換
座標（ｘ，ｙ，ｚ）ｔから座標（ｘ’，ｙ’，ｚ’）ｔへのアフィン変換を、
2003001457.tif 000032
2003001457.tif 000033
の形で表すとき、Ｃ言語的な数値演算で、ｘ’，ｙ’，ｚ’を求める場合、
2003001457.tif 000034
のようになる。但し、全ての数値型が無限の範囲と精度とをもっているものとする。
有限範囲の整数で座標計算する場合、計算精度と演算のオーバーフローとが問題となる。
オーバーフローに関しては、扱う座標の範囲を制限すれば、問題とならないが、計算精度は絶対値の小さい実数を整数に丸めるときに（小数を含む数値などで、必要とする右端の位（または桁）より一つ下の位（または桁）の値を四捨五入等して、数値を短縮すること。四捨五入以外にも切り上げや切り捨てなどの場合もありうる。）、相対誤差が大きくなる。特に、行列Ａの成分は絶対値が１以下の場合が非常に多く、その数値を整数に丸めた場合は期待する結果から大きくずれてしまう。
そこで、行列Ａの成分を整数に丸めるとき、相対誤差をなるべく少なくするために、予めλ（≠０）を行列Ａの成分に掛けておく。
2003001457.tif 000035
この行列Ａ’で座標変換するときに
2003001457.tif 000036
のように計算する。
Ｃ言語的な数値演算で、ｘ’，ｙ’，ｚ’を求める場合、
2003001457.tif 000037
のようになる。但し、すべての数値型は整数である。
このような計算でも、整数計算となり、浮動小数点演算を行う必要はないが、高速化のために実行時の整数除算を避けるためλを２ｎ（ｎ＞１）に限定し、λ’＝ｌｏｇ２λとして、
2003001457.tif 000038
のように算術右シフトで除算とほぼ同じ演算を行う。
また、算術右シフトを整数除算として利用する場合、丸めは−∞方向になるので、
2003001457.tif 000039
のように算術右シフトを行う前に定数λ／２を加えて誤差を修正する。
具体的な例で説明すると、例えば、座標（１１１，２２２，３３３）ｔの点をアフィン変換する場合を考える。
上記の式２の行列Ａ及びｔ（ｔ１，ｔ２，ｔ３）ｔを、
2003001457.tif 000040
とすると、
実数で計算した場合の式２の結果は、
2003001457.tif 000041
となる。
ここで、上述した如く、本発明のアフィン変換を用いると、λ＝４０９６（２１２）とした場合、行列Ａ’は、
2003001457.tif 000042
となる。
この行列Ａ’と、行列ｔ（ｔ１，ｔ２，ｔ３）ｔとを使ったアフィン変換を、Ｃ言語の式で表すと、
2003001457.tif 000043
となる。
この計算結果は、（９９１，５７９，１３１６）ｔとなり、上記の実数の演算結果とほぼ同じ結果となる。
情報処理装置の実際処理では、行列Ａにλを乗算した行列Ａ’と、行列ｔ（ｔ１，ｔ２，ｔ３）ｔとが、情報処理装置のメモリにパラメータとして格納されており、アフィン変換による座標変換をする際に、該当する行列Ａに対応する行列Ａ’と、行列ｔ（ｔ１，ｔ２，ｔ３）ｔとをメモリから読み出し、読み出した行列Ａ’基づいて、各要素毎に演算が行われる。そして、その結果に定数λ／２を加えたものを、定数λ’回右シフトを行い、その結果に行列ｔ（ｔ１，ｔ２，ｔ３）ｔを加えて、座標を算出する。
２．アフィン変換の合成
２つのアフィン変換ｆ，ｇ（変換パラメータ）をそれぞれ、
2003001457.tif 000044
2003001457.tif 000045
2003001457.tif 000046
2003001457.tif 000047
である。Ａ’＝λＡ、Ｂ’＝λβのとき、
2003001457.tif 000048
である。
2003001457.tif 000049
2003001457.tif 000050
とすると、式８は、
2003001457.tif 000051
となる。
この式１１の右辺と式４の右辺は同じ形である。
2003001457.tif 000052
2003001457.tif 000053
2003001457.tif 000054
として、Ｃ言語的な数値演算でＭとｔとの成分を求める場合、
2003001457.tif 000055
となる。λを２ｎ（ｎ＞１）に限定し、λ’＝ｌｏｇ２λとして全ての整数型を整数で計算するようにすると、
2003001457.tif 000056
となる。
この方法により、事前にλを掛けたアフィン変換同士の合成ができる。
具体的な例で説明すると、例えば、
2003001457.tif 000057
とし、λ＝４０９６とすると、
2003001457.tif 000058
となる。
λＡとλＢとの要素を最近整数値に丸めた行列は、
2003001457.tif 000059
2003001457.tif 000060
である。
従って、上述した数式により、行列Ｍと行列ｔとを求めると、
2003001457.tif 000061
となる。
このように、上記の如く計算した
2003001457.tif 000062
と、ほぼ同様な値を得ることができる。
＜除算を使用しない三角形ラスタライズ＞
直線上のｘ座標の変化量を求める場合、２次元平面上の点Ｐ１の座標を（ｘ１，ｙ１）、点Ｐ２の座標を（ｘ２，ｙ２）とする。ｙ１≠ｙ２のとき、Ｐ１とＰ２とをとおる直線のｙ座標に対するｘ座標の変化量は、
2003001457.tif 000063
である。
Δｘ’＝λΔｘとし、Δｘ’をＣ言語的な数値演算で求める場合、
2003001457.tif 000064
のようになる。
2003001457.tif 000065
としたときは
2003001457.tif 000066
のように乗算の形式になる。
整数のみで計算する場合、｜λ｜が十分に大きく｜ｙ２−ｙ１｜がある程度小さければ、丸めによる相対誤差が小さくなる。
そこで、λを定数にして、ｙ座標の範囲を制限すれば、μは予め用意された少ない配列から得ることができる。すなわち、μを｜ｙ２−ｙ１｜に対応させて、情報処理装置のメモリに予め格納しておく。そして、｜ｙ２−ｙ１｜をインデックスとして、μを読み出して、
2003001457.tif 000067
を計算すれば、乗算だけでほぼΔｘと同じ値のΔｘ’を求めることができる。
また、λを２ｎ（ｎ＞１）に制限すれば、算術右シフトによって、Δｘを算出することができる。
よって、除算を一切使わずにｘ座標の変化量が求まる。
また、テクスチャー座標も同じ理由により、除算は必要ない。
具体的な例として、λ＝６５５３６として、座標（１０，２０）の始点Ｐ１と座標（８５，１２０）の始点Ｐ２との線分の例を説明する。
この線分のｙ座標に対するｘ座標の変化量は、
2003001457.tif 000068
となり、Δｘ’＝λｘ＝４９１５２．０となる。
Δｘ’を整数のみで除算を使用しないで計算する場合、上述したように１２０−２０＝１００をインデックスとして、対応するμをメモリから読み出してくる。
この場合、
2003001457.tif 000069
とすると、
2003001457.tif 000070
となり、除算を使用したΔｘ’＝λｘ＝４９１５２．０とほぼ同じ値を得ることができる。
次に、上述の方法を携帯端末等に用いた場合について説明する。
図１は携帯端末のブロック図である。
図１中、１は３次元グラフィクを表示するディスプレイであり、２はＦＰＵ（浮動小数点演算ユニット）を持たないＣＰＵ等で構成された演算手段である制御部、３はプログラムやデータが格納されたメモリ部である。
尚、メモリ部３には、変換パラメータ（上述した行列Ａ’と、行列ｔ（ｔ１，ｔ２，ｔ３）ｔ）が格納された変換パラメータテーブル４と、上述した｜ｙ２−ｙ１｜をインデックスとしてμが格納された逆数テーブル５とが格納されている。
以下の本説明の３次元グラフィクの描画では、物体をすべて多角形の平面の組み合わせで表現する。そして、その多角形のことをポリゴンと呼ぶ。３次元空間にある物体（ポリゴン）は、Ｘ，Ｙ，Ｚの３つの座標値を持っており、この座標を動かすことで、物体の位置や向きを変更することができる。さらに、３次元座標で表現されるものを、最終的に２次元のスクリーンに表示させる為、スクリーン座標系への変換が行われる。
このような、一連の座標変換、透視変換、光源計算などの処理（演算）は、ジオメトリ演算と呼ばれる。そして、計算によって変換されたポリゴンは、最終的にフレームバッファに書き込まれ、描画が行われる。
通常、ジオメトリ演算という処理はＣＰＵのＦＰＵ（浮動小数点演算ユニット）を利用して行なわれていが、ＦＰＵはジオメトリ演算だけでなく、浮動小数点一般を計算するために設計されている。更に、携帯電話に代表される携帯端末の機器では、高価になるという理由で、ＦＰＵ（浮動小数点演算ユニット）を持たないものも多い。
そこで、携帯端末のようなＦＰＵ（浮動小数点演算ユニット）を持たないＣＰＵの情報処理装置でも、ジオメトリ演算を可能とする為、本発明では制御部３が整数によるジオメトリ演算を行う。
また、物体をドットに分割するラスタライズについても、３Ｄグラフィックスアクセラレータのない携帯端末では、処理負荷が増大する。
そこで、本発明では、処理負荷を軽減する為に、制御部３が除算を使用しないで三角形をラスタライズする。
次に、制御部３が行う、上述した演算を用いた３次元グラフィクの描画動作を説明する。
図２は３次元グラフィクの基本的な描画動作を示すフローチャートである。
まず、描画先の仮想フレームバッファの情報を設定する（Ｓｔｅｐ  １００）。
次に、モデルオブジェクトに、メモリ部３から幾何学的座標データである形状データを読み込む（Ｓｔｅｐ  １０１）。
ここで読み込まれる形状データは、頂点座標列、ポリゴン列及びセグメント列の情報が含まれる。また、セグメントのデータには、基本姿勢用の変換パラメータ、所属頂点群及び親セグメントのＩＤ（識別情報）を含む。
尚、読み出される変換パラメータは、基本の行列Ａにλ（２ｎ（ｎ＞１））を乗算した行列Ａ’と行列ｔ（ｔ１，ｔ２，ｔ３）ｔとであり、行列Ａ’と行列ｔ（ｔ１，ｔ２，ｔ３）ｔとは、変換パラメータテーブル４から読み出される。
続いて、形状データに対応するテクスチャーデータ、例えば質感等のデータを読み込む（Ｓｔｅｐ  １０２）。
そして、モデル座標系から視点座標系への変換パラメータを設定し（Ｓｔｅｐ  １０３）、視点座標系からスクリーン座標系への変換パラメータを設定する（Ｓｔｅｐ  １０４）。
仮想フレームバッファに２次元の背景を描画する（Ｓｔｅｐ  １０５）。
仮想フレームバッファにモデルオブジェクトを描画する（Ｓｔｅｐ  １０６）。
最後に、仮想フレームバッファの内容を実際の画面に表示する（Ｓｔｅｐ  １０７）。
そして、Ｓｔｅｐ  １０３からＳｔｅｐ  １０７を繰り返すことによって３次元グラフィクが描画されることになる。
続いて、本発明の特徴である演算が用いられるモデルオブジェクトを制御部３が描画するＳｔｅｐ  １０６について、更に詳細に説明する。
図３はモデルオブジェクトを描画のステップであるＳｔｅｐ  １０６の動作を更に詳細に示すフローチャートである。
まず、モデルの頂点座標をローカル座標系からスクリーン座標系に変換する（Ｓｔｅｐ  ２００）。
ここで、モデルの構造について説明する。通常、モデルは内部に複数のセグメントを持ち，各セグメントは複数の頂点を持っている。それらの頂点はセグメント座標系での座標値を持っている。セグメントは複数の子セグメントを持つことができ，セグメントに含まれる頂点の座標を親セグメント座標系に変換するための変換パラメータを持つ。最上位のセグメントが持つ変換パラメータは，そのセグメントが含む頂点の座標をモデル座標系に変換するための値になる。また、基本姿勢用の変換パラメータの情報も有する。
そこで、セグメント座標系での座標値を持つモデルの頂点座標をローカル座標系からスクリーン座標系に変換するため、まず、セグメント座標系からモデル座標系への変換を行う。
セグメント座標系からモデル座標系への変換パラメータの算出は，上述した整数によるジオメトリ演算によるアフィン変換の合成により行われる。
親セグメントを持つセグメントの場合は，セグメントが持つ変換パラメータｆと、親セグメントのセグメント座標系からモデル座標系への変換パラメータｇとを合成して，セグメント座標系からモデル座標
2003001457.tif 000071
この合成に際し、上述したアフィン変換の合成の手法が用いられる。
尚、親セグメントを持たないセグメントの場合は、セグメントが持つ変換パラメータｆとすると、セグメント座標系からモデル座標系への変換パラメータは、ｈ＝ｆになる。
続いて、モデル座標系からスクリーン座標系への変換について、説明する。
モデル座標系からスクリーン座標系への変換パラメータも同じ方法で計算する。
モデル座標系から視点座標系への変換パラメータをｐとし，視点座標系からスクリーン座標系への変換パラメータをｑとすると，モデル
2003001457.tif 000072
最後に、上述の如く算出された、セグメント座標系からモデル座標系への変換パラメータｈと、モデル座標系からスクリーン座標系への変換パラメータｒとに基づいて、セグメント座標系からスクリーン座標系への変換パラメータｓを算出する。
セグメント座標系からスクリーン座標系への変換パラメータｓは、
2003001457.tif 000073
必要があるが、ｒは１体のモデルの計算では１度しか計算する必要がない。
このように算出された変換パラメータｓを使ってセグメント座標系の頂点座標をスクリーン座標系の座標に変換する。
座標変換の演算は、上述した整数によるジオメトリ演算のアフィン変換により座標変換により行う。
すなわち、セグメント座標系の頂点座標（ｘ，ｙ，ｚ）ｔを、変換パラメータｓを使ってスクリーン座標系の座標（ｘ’，ｙ’，ｚ’）ｔに変換する。
続いて、スクリーン空間で裏面のポリゴンを処理対象から外す（Ｓｔｅｐ  ２０１）。
処理対象のポリゴンを視点座標系のＺ値（奥行き）でソートする（Ｓｔｅｐ  ２０２）。
最後に、スクリーン座標で仮想フレームバッファにポリゴンを描画する（Ｓｔｅｐ  ２０３）。
本ステップを更に詳細に説明すると、まず、ここでは描画領域に三角形が表示される可能性をチェックする。三角形が完全に描画領域の外にある場合は以降の描画処理をスキップする。
そして、三角形を走査するための数値を事前に計算する。この計算は、主に三角形の稜線座標やテクスチャー座標などの変化量を計算する。この変化量は、上述した除算を使用しない三角形ラスタライズの演算により行われる。
三角形の走査は，加算やビットシフトなどの単純操作を繰り返し、仮想フレームバッファにピクセル値を書き込む。
具体的な演算の方法としては、直線上のｘ座標の変化量を求める場合、２次元平面上の点Ｐ１の座標を（ｘ１，ｙ１）、点Ｐ２の座標を（ｘ２，ｙ２）とする。ｙ１≠ｙ２のとき、Ｐ１とＰ２とをとおる直線のｙ座標に対するｘ座標の変化量は、上述した通り、
2003001457.tif 000074
である。
Δｘ’＝λΔｘとし、Δｘ’をＣ言語的な数値演算で求める場合、
2003001457.tif 000075
のようになる。
2003001457.tif 000076
としたときは
2003001457.tif 000077
のように乗算の形式になる。
整数のみで計算する場合、｜λ｜が十分に大きく｜ｙ２−ｙ１｜がある程度小さければ、丸めによる相対誤差が小さくなる。
そこで、λを定数にして、ｙ座標の範囲を制限すれば、μは少ない配列から得ることができる。
そこで、｜ｙ２−ｙ１｜をインデックスとしたμの値を、メモリ部３の逆数テーブル５に予め格納しておく。そして、｜ｙ２−ｙ１｜に対応するμを逆数テーブル５から読み出し、このμと（ｘ２−ｘ１）とを除算することにより、Δｘ’を算出する。
そして、処理の高速化のため、Δｘ’で必要な演算を行っていき、仮想フレームバッファにピクセル値を書き込む際にλで除算する。
また、除算の段階で、λを２ｎ（ｎ＞１）としてあれば、算術右シフトによって、Δｘを算出することができ、除算を使わずにｘ座標の変化量が求まることが可能となる。
尚、テクスチャー座標も同様な処理が可能である。
次に、本発明の実際の具体例として、制御部３で実行されるＣ言語で記載されたプログラムを説明する。
まず、整数によるジオメトリ演算のプログラムを以下に記す。
以下は、メモリに記憶されている、変換パラメータ、すなわち行列Ａ’と行列（ｔ１，ｔ２，ｔ３）ｔの例である。
2003001457.tif 000078
2003001457.tif 000079
ここで、ｐｕｂｌｉｃ  ｉｎｔ  ｍ００からｐｕｂｌｉｃ  ｉｎｔ  ｍ２３は、コメントにあるようにアフィン変換の行列Ａ’と、行列（ｔ１，ｔ２，ｔ３）ｔの各要素に相当する。また、λ＝４０９６である。
次に、座標変換について以下に示す。
2003001457.tif 000080
2003001457.tif 000081
ここで、＠ｐａｒａｍ  ｓｒｃは上記の式２で示される座標（ｘ，ｙ，ｚ）ｔに相当し、＠ｐａｒａｍ  ｄｓｔは上記の式２で示される座標（ｘ’，ｙ’，ｚ’）ｔに相当する。
次に、アフィン変換の合成について以下に示す。
2003001457.tif 000082
2003001457.tif 000083
次に、ポリゴン描画について示す。
2003001457.tif 000084
2003001457.tif 000085
2003001457.tif 000086
尚、上記テーブルは、上述したμの値の逆数テーブル５に相当するものであるが、メモリの記憶容量節約の観点から、μ−１としてある。そして、｜ｙ２−ｙ１｜の大きさの順に並んでいる。
2003001457.tif 000087
2003001457.tif 000088
2003001457.tif 000089
2003001457.tif 000090
2003001457.tif 000091
2003001457.tif 000092
2003001457.tif 000093
2003001457.tif 000094
2003001457.tif 000095
以上が、本発明を実施する為のプログラムの一例である。
産業上の利用可能性
本発明は、３次元画像の描画の演算処理の際、整数の範囲で演算処理が行えるので、携帯電話や、ＰＤＡ（Ｐｅｒｓｏｎａｌ  Ｄｉｇｉｔａｌ（Ｄａｔａ）Ａｓｓｉｓｔａｎｔｓ）のようにＦＰＵ（浮動小数点演算ユニット）も備えていないものであっても、３次元画像が扱える。
また、演算処理の際、処理負荷の高い除算を行わないようにしているので、ＣＰＵの能力が低い情報処理装置であっても、スムーズな描画処理が行える。
【図面の簡単な説明】
図１は携帯端末のブロック図であり、図２は３次元グラフィクの基本的な描画動作を示すフローチャートであり、図３はモデルオブジェクトを描画のステップであるＳｔｅｐ  １０６の動作を更に詳細に示すフローチャートである。
【図１】
2003001457.tif 000128
【図２】
2003001457.tif 000129
【図３】
2003001457.tif 000130
【国際調査報告】
2003001457.tif 000131
2003001457.tif 000132
2003001457.tif 000133
2003001457.tif 000134