(57)【特許請求の範囲】
【請求項１】
三次元のオブジェクトの形状に近似する、基本となる多面体の頂点を決定する基本頂点決定手段と、前記基本となる多面体よりも前記オブジェクトに対する近似の度合いの高い多面体の頂点を、近似の度合いにより階層的に決定する詳細頂点決定手段と、前記詳細頂点決定手段により、階層的に決定された多面体の頂点の位置の情報として、当該多面体よりも近似の度合いの低い多面体の所定の複数の頂点に基づいて定められる座標系における座標を算出する詳細頂点座標算出手段とを備えることを特徴とする階層化ポリゴンデータ生成装置。
【請求項２】
前記基本頂点決定手段は、操作者の指定により基本となる多面体の頂点を決定する請求項１に記載の階層化ポリゴンデータ生成装置。
【請求項３】
三次元のオブジェクトを仮想的に複数の面で切断した断面において、それぞれの断面に近似する多角形の頂点を、当該三次元のオブジェクトの形状に近似する、基本となる多面体の頂点として決定する基本頂点決定手段と、前記基本となる多面体よりも前記オブジェクトに対する近似の度合いの高い多面体の頂点を、近似の度合いにより階層的に決定する詳細頂点決定手段と、前記詳細頂点決定手段により、階層的に決定された多面体の頂点の位置の情報として、当該多面体よりも近似の度合いの低い多面体の所定の複数の頂点に基づいて定められる相対座標を算出する詳細頂点座標算出手段とを備えることを特徴とする階層化ポリゴンデータ生成装置。
【請求項４】
前記それぞれの断面に近似する多角形は、当該三次元のオブジェクトの形状モデリングにより得られたオリジナルポリゴンデータにより表される線分と、前記仮想的にオブジェクトを切断する面との交わる点を代表点とし、当該代表点同士を接続して生成した第２の多角形において、前記第２の多角形の辺の長さの和を四等分する四つの点を頂点とする四角形である請求項３に記載の階層化ポリゴンデータ生成装置。
【請求項５】
前記詳細頂点決定手段は、前記断面に近似する多角形よりも当該断面に対する近似の度合いを高くするように頂点を増加させた多角形の、当該増加させた頂点を、増加させた頂点の数により階層的に詳細頂点として決定する請求項３に記載の階層化ポリゴンデータ生成装置。
【請求項６】
前記詳細頂点決定手段は、前記四角形の各辺の長さと、各辺の両端の間の前記第２の多角形の辺の長さの和との差を算出する近似度算出手段と、前記近似度算出手段により算出された差と、予め決められた一定値とを比較する比較手段と、前記比較手段により、差が一定値以上であると判定された場合には、当該辺の両端の間の前記第２の多角形の辺の長さの和を二等分する点を、より近似の度合いの高い多角形の頂点として決定し、差が一定値より小さいと判定された場合には、より近似の度合いの高い多角形の頂点を決定しない階層化頂点決定手段とを備え、前記近似度算出手段は、前記階層化頂点決定手段により、より近似の度合いの高い多角形の頂点が決定された場合には、決定された多角形において、新たに生成された各辺についてさらに前記差を算出し、前記階層化頂点決定手段が、より近似の度合いの高い多角形の頂点を決定しなくなるまで再帰的に処理を行う請求項４に記載の階層化ポリゴンデータ生成装置。
【請求項７】
前記詳細頂点決定手段は、前記基本となる多面体の各面の面積と、前記三次元オブジェクト上において、当該基本となる多面体の各面の頂点間を結ぶ線分により区切られた範囲の面積との差を算出する近似度算出手段と、前記近似度算出手段により算出された差と、予め決められた一定値とを比較する比較手段と、前記比較手段により、差が一定値以上であると判定された場合には、当該面より、三次元オブジェクトの表面に近いところに新たな頂点を決定し、差が一定値より小さいと判定された場合には、新たな頂点を決定しない階層化頂点決定手段とを備え、前記近似度算出手段は、前記階層化頂点決定手段により、新たな頂点が決定された場合には、当該面と、新たな頂点とから構成される多面体についてさらに前記面積の差を算出し、前記階層化頂点決定手段が、新たな頂点を決定しなくなるまで再帰的に処理を行う請求項１に記載の階層化ポリゴンデータ生成装置。
【請求項８】
前記階層化頂点決定手段は、多面体の、対応する面の重心からの法線と、当該三次元のオブジェクトの形状モデリングにより得られたオリジナルポリゴンデータにより表される面とが交わる点を新たな頂点として決定する請求項７に記載の階層化ポリゴンデータ生成装置。
【請求項９】
三次元のオブジェクトの形状に近似する、基本となる多面体の頂点を決定する基本頂点決定ステップと、前記基本となる多面体よりも前記オブジェクトに対する近似の度合いの高い多面体の頂点を、近似の度合いにより階層的に決定する詳細頂点決定ステップと、階層的に決定された多面体の頂点の位置の情報として、当該多面体よりも近似の度合いの低い多面体の所定の複数の頂点に基づいて定められる座標系における座標を算出する詳細頂点座標算出ステップとを有し、前記詳細頂点決定ステップ及び前記詳細頂点座標算出ステップを、前記近似の度合いが所定の近似度以上となるまで実行することを特徴とする階層化ポリゴンデータ生成方法。
【請求項１０】
前記近似の度合いを、前記詳細頂点決定ステップにおいて決定された頂点と、前記詳細頂点座標算出ステップにおいて座標系の決定に用いる所定の複数の頂点により構成される多面体の面の面積と、当該オブジェクトの形状モデリングにより得られたオリジナルポリゴンデータにより表される面のうち、当該多面体の面と対応する部分の面積との差と、予め定められた一定の値とを比較することにより判定する請求項９に記載の階層化ポリゴンデータ生成方法。
【請求項１１】
三次元のオブジェクトの形状に近似する、基本となる多面体の頂点を決定する基本頂点決定ステップと、前記基本となる多面体よりも前記オブジェクトに対する近似の度合いの高い多面体の頂点を、近似の度合いにより階層的に決定する詳細頂点決定ステップと、階層的に決定された多面体の頂点の位置の情報として、当該多面体よりも近似の度合いの低い多面体の所定の複数の頂点に基づいて定められる座標系における座標を算出する詳細頂点座標算出ステップとを有し、前記詳細頂点決定ステップ及び前記詳細頂点座標算出ステップを、前記近似の度合いが所定の近似度以上となるまで実行するプログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項１２】
三次元ポリゴンデータを表示する際の表示ポリゴン数を決定する表示ポリゴン数決定手段と、前記表示ポリゴン数決定手段により決定された表示ポリゴン数に従って、請求項１から８のいずれかに記載の階層化ポリゴンデータ生成装置により生成された階層化ポリゴンデータから、三次元ポリゴンデータを復元する復元手段を備えることを特徴とする三次元リアルタイム映像生成装置。
【請求項１３】
前記復元手段は、前記表示ポリゴン数決定手段により決定された表示ポリゴン数に従って、オブジェクトを表示するための三次元ポリゴンデータを構成する頂点を決定することにより三次元ポリゴンデータを復元する請求項１２に記載の三次元リアルタイム映像生成装置。
【請求項１４】
前記三次元リアルタイム映像生成装置はさらに、前記基本となる多面体の頂点の位置を変更する基本頂点変更手段を有し、前記復元手段は、前記基本頂点変更手段により、前記基本となる多面体の頂点の位置が変更された場合に、当該頂点に基づいて定められる座標系における座標で位置が表される詳細頂点の絶対座標を、変更後の頂点の位置に基づいて算出する請求項１２または１３に記載の三次元リアルタイム映像生成装置。
【請求項１５】
前記三次元リアルタイム映像生成装置はさらに、階層化ポリゴンデータに、表示タイミングに関する情報を付加して複数記憶するアニメーションデータ記憶手段と、前記アニメーションデータ記憶手段に記憶された階層化ポリゴンデータから、前記復元手段により復元された三次元ポリゴンデータを、前記表示タイミングに関する情報に従って表示させるアニメーション表示制御手段とを備える請求項１２から１４のいずれかに記載の三次元リアルタイム映像生成装置。
【請求項１６】
前記表示ポリゴン数決定手段は、前記アニメーションデータ記憶手段に記憶されている複数の階層化ポリゴンデータと、前記表示タイミングに関する情報から、三次元ポリゴンデータを連続的に表示した際のオブジェクトの移動速度を算出する移動速度算出手段を有し、前記移動速度算出手段により算出された移動速度に基づいて、表示ポリゴン数を決定する請求項１５に記載の三次元リアルタイム映像生成装置。
【請求項１７】
前記表示ポリゴン数決定手段は、前記階層化ポリゴンデータから、当該オブジェクトの表示位置の画面からの奥行きを表すＺ値を取得するＺ値取得手段を有し、前記Ｚ値取得手段が取得した奥行きに基づいて、表示ポリゴン数を決定する請求項１５又は１６に記載の三次元リアルタイム映像生成装置。
【請求項１８】
前記表示ポリゴン数決定手段は、オブジェクトを表示するシステムの環境に関する情報に基づいて表示ポリゴン数を決定する請求項１５から１７のいずれかに記載の三次元リアルタイム映像生成装置。
【請求項１９】
三次元ポリゴンデータを表示する際の表示ポリゴン数を決定する表示ポリゴン数決定ステップと、前記表示ポリゴン数決定ステップにおいて決定された表示ポリゴン数に従って、請求項１から８のいずれかに記載の階層化ポリゴンデータ生成装置により生成された階層化ポリゴンデータから、三次元ポリゴンデータを復元する復元ステップとを有することを特徴とする三次元リアルタイム映像生成方法。
【請求項２０】
三次元ポリゴンデータを表示する際の表示ポリゴン数を決定する表示ポリゴン数決定ステップと、前記表示ポリゴン数決定ステップにおいて決定された表示ポリゴン数に従って、請求項１から８のいずれかに記載の階層化ポリゴンデータ生成装置により生成された階層化ポリゴンデータから、三次元ポリゴンデータを復元する復元ステップとを有し、当該復元ステップにおいては、前記表示ポリゴン数決定ステップで決定された表示ポリゴン数に従って、オブジェクトを表示するための三次元ポリゴンデータを構成する頂点を決定することにより、三次元ポリゴンデータを復元する処理を行うプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、階層化ポリゴンデータ生成装置及び方法及び当該階層化ポリゴンデータを用いる三次元リアルタイム映像生成装置及び方法に関する。
【０００２】
【従来の技術】
近年、コンピュータグラフィックス（以下、「ＣＧ」という。）の分野において、三次元（以下、「３Ｄ」という。）で表示するための様々な３Ｄ専用ボード（以下、単に「ボード」という。）や専用機が市販されている。その中でもWindows 95（登録商標）やWindows NT（登録商標）の普及に伴い、パーソナルコンピュータ（以下、「ＰＣ」という。）に内蔵するためのボードが安価に入手できるようになり、また、ゲーム専用機も安価で発売されている。
【０００３】
このような状況の中で、ほとんどのボードやゲーム専用機はポリゴンを使用して内部データを保持し、並びに表示しているが、ポリゴンを使用するボードは高性能なものから性能の低いものまで様々である。例えば、高性能なボードでは、１０，０００ポリゴンを使用して美しく表示対象の３Ｄ物体（以下、「オブジェクト」という。）の表示ができるのに対し、性能の低いボードでは、５００ポリゴン程度の使用でオブジェクトの表示を行う必要がある。
【０００４】
従来、アニメーションの作成者（以下、「アニメータ」という。）がMicrosoft社製のSoftImage （登録商標）等のアニメーション作成ツールを使用して、リアルタイム表示が可能なアニメーションを作成すると、通常３０，０００ポリゴン以上のポリゴン数が必要であった。
【０００５】
しかしながら、現在のＰＣで表示を行う場合、多くとも２，０００ポリゴン程度にポリゴン数をおさえなければリアルタイムに表示を行うことはできない。また、複数のオブジェクトを同時に表示するような場合には、複数のオブジェクトのトータルで２，０００ポリゴン程度におさえる必要がある。
【０００６】
複数のオブジェクトを表示する場合に、個々のオブジェクトの表示に使用するポリゴンデータを削減する目的で、予め、解像度の違うポリゴンデータを複数セット用意しておき、表示の際の動作の内容等に基づいて表示するポリゴンデータの解像度を変更して表示する技術が、特開平７−８５３０７号公報に開示されている。
【０００７】
この方法によれば、オブジェクトの表示に際して、オブジェクトの動作等に基き、使用するポリゴン数を減少させることが可能であるため、画面に複数のオブジェクトを表示したい場合などには有効である。
【０００８】
【発明が解決しようとする課題】
ところで、一般にアニメーションを記憶領域に格納する際に、アニメーションをポリゴンの状態で格納しておくと、１本のアニメーションを格納しておくだけで巨大な記憶領域を必要とするという問題がある。上記従来の技術では、予め、複数の解像度に対応したポリゴンデータを用意しておく必要があるため、ポリゴンデータの記憶に必要な記憶領域としては、依然として膨大な量が必要とされるという問題点を有していた。
【０００９】
また、上記従来の技術では、性能が異なる機械に対して、同一のポリゴンデータを汎用的に使用することができず、機械の性能に応じた数だけアニメーションを用意する必要があるため、膨大な記憶領域が必要となるだけでなく、アニメータの工数も膨大になるという問題点もあった。
【００１０】
本発明は、上記問題点に鑑み、オブジェクトの表示にあたって、ポリゴンデータの記憶領域を節約することが可能な階層化ポリゴンデータ生成装置及び方法、及び当該階層化ポリゴンデータを用いることによりアニメータの工数を削減することができる３Ｄリアルタイム映像生成装置及び方法、さらに各方法を実現するプログラムを記録した記録媒体、及び階層化ポリゴンデータを記録した記録媒体を提供することを目的とする。
【００１１】
【課題を解決するための手段】
前記目的を達成するため、本発明の階層化ポリゴンデータ生成装置は、三次元のオブジェクトの形状に近似する、基本となる多面体の頂点を決定する基本頂点決定手段と、前記基本となる多面体よりも前記オブジェクトに対する近似の度合いの高い多面体の頂点を、近似の度合いにより階層的に決定する詳細頂点決定手段と、前記詳細頂点決定手段により、階層的に決定された多面体の頂点の位置の情報として、当該多面体よりも近似の度合いの低い多面体の所定の複数の頂点に基づいて定められる座標系における座標を算出する詳細頂点座標算出手段とを備えることを特徴とする。
【００１２】
前記基本頂点決定手段は、操作者の指定により基本となる多面体の頂点を決定することができる。
【００１３】
また、本発明の階層化ポリゴンデータ生成装置は、三次元のオブジェクトを仮想的に複数の面で切断した断面において、それぞれの断面に近似する多角形の頂点を、当該三次元のオブジェクトの形状に近似する、基本となる多面体の頂点として決定する基本頂点決定手段と、前記基本となる多面体よりも前記オブジェクトに対する近似の度合いの高い多面体の頂点を、近似の度合いにより階層的に決定する詳細頂点決定手段と、前記詳細頂点決定手段により、階層的に決定された多面体の頂点の位置の情報として、当該多面体よりも近似の度合いの低い多面体の所定の複数の頂点に基づいて定められる座標系における座標を算出する詳細頂点座標算出手段とを備えることを特徴とする。
【００１４】
ここで、前記それぞれの断面に近似する多角形は、当該三次元のオブジェクトの形状モデリングにより得られたオリジナルポリゴンデータにより表される線分と、前記仮想的にオブジェクトを切断する面との交わる点を代表点とし、当該代表点同士を接続して生成した第２の多角形において、前記第２の多角形の辺の長さの和を四等分する四つの点を頂点とする四角形であることが好ましい。
【００１５】
また、前記詳細頂点決定手段は、前記断面に近似する多角形よりも当該断面に対する近似の度合いを高くするように頂点を増加させた多角形の、当該増加させた頂点を、増加させた頂点の数により階層的に詳細頂点として決定することが好ましい。詳細頂点の位置の情報を簡略化した形式で保持することが可能となるからである。
【００１６】
また、前記詳細頂点決定手段は、前記四角形の各辺の長さと、各辺の両端の間の前記第２の多角形の辺の長さの和との差を算出する近似度算出手段と、前記近似度算出手段により算出された差と、予め決められた一定値とを比較する比較手段と、前記比較手段により、差が一定値以上であると判定された場合には、当該辺の両端の間の前記第２の多角形の辺の長さの和を二等分する点を、より近似の度合いの高い多角形の頂点として決定し、差が一定値より小さいと判定された場合には、より近似の度合いの高い多角形の頂点を決定しない階層化頂点決定手段とを備え、前記近似度算出手段は、前記階層化頂点決定手段により、より近似の度合いの高い多角形の頂点が決定された場合には、決定された多角形において、新たに生成された各辺についてさらに前記差を算出し、前記階層化頂点決定手段が、より近似の度合いの高い多角形の頂点を決定しなくなるまで再帰的に処理を行うことが好ましい。このような処理により詳細頂点を決定しておけば、表示に利用したい三次元ポリゴン数に応じて、適切に三次元ポリゴンデータの復元を行うことが可能となるからである。
【００１７】
また、前記詳細頂点決定手段は、前記基本となる多面体の各面の面積と、前記三次元オブジェクト上において、当該基本となる多面体の各面の頂点間を結ぶ線分により区切られた範囲の面積との差を算出する近似度算出手段と、前記近似度算出手段により算出された差と、予め決められた一定値とを比較する比較手段と、前記比較手段により、差が一定値以上であると判定された場合には、当該面より、三次元オブジェクトの表面に近いところに新たな頂点を決定し、差が一定値より小さいと判定された場合には、新たな頂点を決定しない階層化頂点決定手段とを備え、前記近似度算出手段は、前記階層化頂点決定手段により、新たな頂点が決定された場合には、当該面と、新たな頂点とから構成される多面体についてさらに前記面積の差を算出し、前記階層化頂点決定手段が、新たな頂点を決定しなくなるまで再帰的に処理を行うことが好ましい。このような処理によっても、表示に利用したい三次元ポリゴン数に応じて、適切に三次元ポリゴンデータの復元を行うことが可能となる。
【００１８】
ここで、前記階層化頂点決定手段は、多面体の、対応する面の重心からの法線と、当該三次元のオブジェクトの形状モデリングにより得られたオリジナルポリゴンデータにより表される面とが交わる点を新たな頂点として決定することが好ましい。三次元ポリゴンデータの復元に適切な頂点を得ることができるからである。
【００１９】
また、本発明の階層化ポリゴンデータ生成方法は、三次元のオブジェクトの形状に近似する、基本となる多面体の頂点を決定する基本頂点決定ステップと、前記基本となる多面体よりも前記オブジェクトに対する近似の度合いの高い多面体の頂点を、近似の度合いにより階層的に決定する詳細頂点決定ステップと、階層的に決定された多面体の頂点の位置の情報として、当該多面体よりも近似の度合いの低い多面体の所定の複数の頂点に基づいて定められる座標系における座標を算出する詳細頂点座標算出ステップとを有し、前記詳細頂点決定ステップ及び前記詳細頂点座標算出ステップを、前記近似の度合いが所定の近似度以上となるまで実行することを特徴とする。
【００２０】
前記近似の度合いを、前記詳細頂点決定ステップにおいて決定された頂点と、前記詳細頂点座標算出ステップにおいて座標系の決定に用いる所定の複数の頂点により構成される多面体の面の面積と、当該オブジェクトの形状モデリングにより得られたオリジナルポリゴンデータにより表される面のうち、当該多面体の面と対応する部分の面積との差と、予め定められた一定の値とを比較することにより判定することが好ましい。表示に利用することができる表示ポリゴン数に応じて、適切に三次元ポリゴンデータの復元を行うことが可能となるからである。
【００２１】
また、本発明の記録媒体は、三次元のオブジェクトの形状に近似する、基本となる多面体の頂点を決定する基本頂点決定ステップと、前記基本となる多面体よりも前記オブジェクトに対する近似の度合いの高い多面体の頂点を、近似の度合いにより階層的に決定する詳細頂点決定ステップと、階層的に決定された多面体の頂点の位置の情報として、当該多面体よりも近似の度合いの低い多面体の所定の複数の頂点に基づいて定められる座標系における座標を算出する詳細頂点座標算出ステップとを有し、前記詳細頂点決定ステップ及び前記詳細頂点座標算出ステップを、前記近似の度合いが所定の近似度以上となるまで実行するプログラムを記録したコンピュータ読み取り可能な記録媒体である。
【００２２】
また、本発明の三次元リアルタイム映像生成装置は、三次元ポリゴンデータを表示する際の表示ポリゴン数を決定する表示ポリゴン数決定手段と、前記表示ポリゴン数決定手段により決定された表示ポリゴン数に従って、本発明のいずれかの階層化ポリゴンデータ生成装置により生成された階層化ポリゴンデータから、三次元ポリゴンデータを復元する復元手段を備えることを特徴とする。ここで、階層化ポリゴンデータとは、本発明の階層化ポリゴンデータ生成装置により生成された情報をいい、基本頂点に関する情報、詳細頂点に関する情報を含む。
【００２３】
前記復元手段は、前記表示ポリゴン数決定手段により決定された表示ポリゴン数に従って、オブジェクトを表示するための三次元ポリゴンデータを構成する頂点を決定することにより三次元ポリゴンデータを復元することが好ましい。本発明の階層化ポリゴンデータを利用すれば、容易に三次元ポリゴンデータを復元することができるからである。
【００２４】
また、前記三次元リアルタイム映像生成装置はさらに、前記基本となる多面体の頂点の位置を変更する基本頂点変更手段を有し、前記復元手段は、前記基本頂点変更手段により、前記基本となる多面体の頂点の位置が変更された場合に、当該頂点に基づいて定められる座標系における座標で位置が表される詳細頂点の絶対座標を、変更後の頂点の位置に基づいて算出することが好ましい。基本となる多面体の頂点の位置を変更した後に、詳細頂点を順次追加していくことにより、容易にオブジェクトの移動、形状の変更等が行えるからである。
【００２５】
また、前記三次元リアルタイム映像生成装置はさらに、階層化ポリゴンデータに、表示タイミングに関する情報を付加して複数記憶するアニメーションデータ記憶手段と、前記アニメーションデータ記憶手段に記憶された階層化ポリゴンデータから、前記復元手段により復元された三次元ポリゴンデータを、前記表示タイミングに関する情報に従って表示させるアニメーション表示制御手段とを備えることもできる。前述のように、オブジェクトの移動、形状の変更等をおこなった複数のポリゴンデータを所定のタイミングで連続的に表示することにより、アニメーションとすることができるが、本発明の装置を用いると、オブジェクトの移動、形状の変更等を容易に行うことができるため、アニメータの工数を削減することができる。
【００２６】
また、前記表示ポリゴン数決定手段は、前記アニメーションデータ記憶手段に記憶されている複数の階層化ポリゴンデータと、前記表示タイミングに関する情報から、三次元ポリゴンデータを連続的に表示した際のオブジェクトの移動速度を算出する移動速度算出手段を有し、前記移動速度算出手段により算出された移動速度に基づいて、表示ポリゴン数を決定することが好ましい。移動速度が速い場合には、ポリゴン数を落としても違和感のないアニメーションとすることができるため、表示するオブジェクトのポリゴン数を削減することにより、より多くのオブジェクトを表示することもできるからである。
【００２７】
また、前記表示ポリゴン数決定手段は、前記階層化ポリゴンデータから、当該オブジェクトの表示位置の画面からの奥行きを表すＺ値を取得するＺ値取得手段を有し、前記Ｚ値取得手段が取得した奥行きに基づいて、表示ポリゴン数を決定することが好ましい。画面からの奥行きが遠い場合は、ポリゴン数を落としても違和感なくオブジェクトの表示ができるため、表示するオブジェクトのポリゴン数を削減することにより、より多くのオブジェクトを表示することもできるからである。
【００２８】
また、前記表示ポリゴン数決定手段は、オブジェクトを表示するシステムの環境に関する情報に基づいて表示ポリゴン数を決定することが好ましい。例えば、ＣＰＵの処理能力、メモリの搭載量等のシステム環境によって、適切な表示ポリゴン数は異なってくるからである。
【００２９】
また、本発明の三次元リアルタイム映像生成方法は、三次元ポリゴンデータを表示する際の表示ポリゴン数を決定する表示ポリゴン数決定ステップと、前記表示ポリゴン数決定ステップにおいて決定された表示ポリゴン数に従って、本発明の階層化ポリゴンデータ生成装置により生成された階層化ポリゴンデータから、三次元ポリゴンデータを復元する復元ステップとを有することを特徴とする。
【００３０】
また、本発明の記録媒体は、三次元ポリゴンデータを表示する際の表示ポリゴン数を決定する表示ポリゴン数決定ステップと、前記表示ポリゴン数決定ステップにおいて決定された表示ポリゴン数に従って、本発明の階層化ポリゴンデータ生成装置により生成された階層化ポリゴンデータから、三次元ポリゴンデータを復元する復元ステップとを有し、当該復元ステップにおいては、前記表示ポリゴン数決定ステップで決定された表示ポリゴン数に従って、オブジェクトを表示するための三次元ポリゴンデータを構成する頂点を決定することにより、三次元ポリゴンデータを復元する処理を行うプログラムを記録したコンピュータ読み取り可能な記録媒体である。
【００３１】
さらに、本発明の記録媒体は、指定された表示ポリゴン数に応じて、三次元のオブジェクトを表す三次元ポリゴンデータを復元することができる階層化ポリゴンデータであって、当該三次元のオブジェクトの形状に近似する、基本となる多面体の頂点に関する情報と、前記指定された表示ポリゴン数に応じて、前記基本となる多面体の頂点に、順次頂点を追加することにより、より当該三次元のオブジェクトに対する近似の度合いの高い多面体を生成するが可能な複数の詳細頂点の情報とからなり、当該詳細頂点の情報は、当該詳細頂点を含まない多面体の、所定の複数の頂点に基づいて定められる座標系における座標の情報であることを特徴とする階層化ポリゴンデータを記録したコンピュータ読み取り可能な記録媒体である。階層化ポリゴンデータの生成と、三次元リアルタイム映像の生成とを、別のコンピュータで実行させる場合に特に有効である。
【００３２】
【発明の実施の形態】
以下、本発明の実施の形態について、図面を参照しながら説明する。
【００３３】
図１は、本発明の階層化ポリゴンデータ生成装置及び３Ｄリアルタイム映像生成装置の構成の一例を示す機能ブロック図である。本実施の形態では、一つの装置で階層化ポリゴンデータ生成処理及び３Ｄリアルタイム映像生成処理の両方を実現できるようにしているが（以下、本実施の形態の装置を、単に「３Ｄリアルタイム映像生成装置」という。）、後述の如く、階層化ポリゴンデータ生成処理と、３Ｄリアルタイム映像生成処理とを、別の装置で実行するようにすることも可能である。
【００３４】
図１に示されるように、本実施の形態の３Ｄリアルタイム映像生成装置は、入力部１０１、制御部１０２、出力部１０３、オリジナルポリゴンデータ格納部１０４、代表点データ格納部１０５、階層化ポリゴンデータ格納部１０６を備える。
【００３５】
入力部１０１は、ユーザがポリゴンデータの編集等の入力を行うために使用される。入力部１０１としては、具体的には、キーボード、マウス等の入力装置を用いることができる。
【００３６】
制御部１０２は、本実施の形態の３Ｄリアルタイム映像生成装置全体の制御を行う。制御部１０２は、ハードウェア的には、ＣＰＵや、入出力装置とのＩ／Ｏインターフェース部分が対応する部分である。制御部１０２において、プログラムが動作することにより本発明に係る階層化ポリゴンデータ生成処理及び３Ｄリアルタイム映像生成処理が実現される。制御部１０２は、機能的には、代表点変換部１０２１、ポリゴン階層化部１０２２、入力受付部１０２３、基本ポリゴンデータ編集部１０２４、表示ポリゴン数算出部１０２５、マージ処理部１０２６、３Ｄ情報表示部１０２７を有している。
【００３７】
本実施の形態の３Ｄリアルタイム映像生成装置においては、主として代表点変換部１０２１及びポリゴン階層化部１０２２において３Ｄポリゴンデータ生成処理が実行され、その他の部分で３Ｄリアルタイム映像生成処理が実行される。即ち、オリジナルポリゴンデータ格納部１０４に格納されているオリジナルポリゴンデータから、階層化ポリゴンデータ格納部１０６に格納される階層化ポリゴンデータを生成するまでの階層化ポリゴンデータ生成処理を行う部分と、他の部分とを別の装置に分けることにより、前述の如く、階層化ポリゴンデータ生成処理と、３Ｄリアルタイム映像生成処理とを、別の装置で実行するようにすることができる。制御部１０２の各部の詳細な処理内容については後述する。
【００３８】
出力部１０３には、３Ｄリアルタイム映像等が表示出力される。出力部１０３としては、例えば、ディスプレイ装置等の出力装置を用いることができる。
【００３９】
オリジナルポリゴンデータ格納部１０４には、オリジナルポリゴンデータが格納される。ここで、オリジナルポリゴンデータのデータ構造等について説明する。
【００４０】
図２は、本実施の形態のオリジナルポリゴンデータのデータ構造の一例を示す図である。同図に示されるように、本実施の形態のオリジナルポリゴンデータ２０は、現実のオブジェクトからモデリングされた三角形ポリゴンの頂点（vertex・以下、下付け文字「V」で表す。）の座標（XV, YV, ZV）を、それぞれの頂点 の識別子IDVとともに保持する頂点データ２０１、三角形ポリゴンの面（face・ 以下、下付け文字「F」で表す。）を構成する三つの頂点の識別子（IDV）のセットを、それぞれの面の識別子IDFとともに保持する三角形ポリゴンデータ２０２ から構成され、オブジェクト（object・以下、下付け文字「O」で表す。）の識 別子IDO２０３がオブジェクトごとに付与されて格納されている。なお、本実施 の形態では三角形ポリゴンを用いたが、四角形等、他の多角形のポリゴンを使用することもことも可能である。
【００４１】
代表点データ格納部１０５には、オリジナルポリゴンデータ２０から変換された代表点データが格納される。代表点データのデータ構造等、詳細については後述する。
【００４２】
階層化ポリゴンデータ格納部１０６には、代表点データから、ポリゴン階層化部１０２２によって階層化された階層化ポリゴンデータが格納される。階層化ポリゴンデータは、階層の最も上層にあたる、最も荒いポリゴンデータ（以下、「基本ポリゴンデータ」という。）１０６１と、上記基本ポリゴンデータに頂点を追加していくことにより、基本ポリゴンデータより下層にあたる、より面の細かいポリゴンデータを生成することができるようなデータ（以下、「詳細ポリゴンデータ」という。）１０６２とが格納される。ポリゴン階層化処理の詳細、及び当該処理により生成される基本ポリゴンデータ１０６１と詳細ポリゴンデータ１０６２とを含む階層化ポリゴンデータのデータ構造等については、後に詳細に説明する。
【００４３】
次に、制御部１０２の各部の処理内容について説明する。
【００４４】
代表点変換部１０２１は、オリジナルポリゴンデータ２０を代表点データに変換する処理を行う。代表点変換処理の詳細については後述する。
【００４５】
ポリゴン階層化部１０２２は、代表点データから階層化ポリゴンデータを生成する。
【００４６】
入力受付部１０２３は、入力部１０１から入力された基本ポリゴンデータ１０６１の編集指示入力等を受け付ける。基本ポリゴンデータ１０６１の編集処理の詳細については後述する。
【００４７】
基本ポリゴンデータ編集部１０２４は、入力受付部１０２３が受け付けた入力に従い、基本ポリゴンデータ１０６１の編集を行う。基本ポリゴンデータ編集部１０２４としては、具体的には、既存のポリゴン編集ソフトウェア等を用いることができる。なお、編集された基本ポリゴンデータは、編集前の基本ポリゴンデータとは別に保存することもできる。
【００４８】
表示ポリゴン数算出部１０２５は、オブジェクトを出力部１０３に出力する際の表示ポリゴン数を算出する。ここで、「表示ポリゴン数」とは、階層化ポリゴンデータにおいて、基本ポリゴンデータ１０６１に対し、どの程度の階層まで詳細ポリゴンデータ１０６２を計算する処理を行うかを表す値をいう。表示ポリゴン数の算出方法の詳細については後述する。
【００４９】
マージ処理部１０２６は、表示ポリゴン数算出部１０２５により算出された表示ポリゴン数に基づいて、基本ポリゴンデータ１０６１に、詳細ポリゴンデータ１０６２を計算する処理（以下、「マージ処理」という。）を行い、出力部１０３に出力すべきオブジェクトの３Ｄポリゴンデータを復元する。
【００５０】
３Ｄ情報表示部１０２７は、マージ処理部１０２６により復元された３Ｄポリゴンデータを受け取り、出力部１０３にオブジェクトを表示させる。３Ｄ情報表示部１０２７には、特に図示はしていないが、本実施の形態の３Ｄリアルタイム映像生成処理において生成される３Ｄポリゴンデータを用いてオブジェクトを出力部１０３に表示させるためのツールが格納される。このツールとしては、既存のソフトウェアを利用することが可能である。本実施の形態では、Microsoft 社製のSoftImage（登録商標）というソフトウェアを用いたが、具体的には、３Ｄ ポリゴンデータとして、ポリゴンの頂点のデータと、複数の頂点により構成される面のデータを得ることによりオブジェクトの３Ｄ表示を行うことができるものであれば、他のソフトウェアを使用することも可能である。
【００５１】
以上のように構成された本実施の形態の３Ｄリアルタイム映像生成装置について、以下、種々の実施の形態と、それぞれの実施の形態における制御部１０２の処理内容等について詳細に説明する。
（実施の形態１）
まず、本発明の第１の実施の形態について説明する。本実施の形態では、本発明に係る階層化ポリゴンデータ生成の第１の方法、即ち、オリジナルポリゴンデータ２０から階層化ポリゴンデータを生成する第１の方法について、詳細に説明する。
【００５２】
まず、本実施の形態の方法を用いてオリジナルポリゴンデータ２０から階層化ポリゴンデータを生成する概念について説明する。
【００５３】
図３は、本実施の形態の方法によるオリジナルポリゴンデータ２０の階層化方法について説明するための、オブジェクトの一例を示す図である。同図の例では、形状モデリングにより既にオリジナルポリゴンデータが取得されたオブジェクト４０１、及び説明のための座標軸を記載している。尚、同図では、オリジナルポリゴンデータを表す三角形の表示は一部省略している。本実施の形態のポリゴン階層化方法では、まず、オブジェクト４０１を、例えばｚ軸に垂直なｘｙ平面４０２を用い、当該ｘｙ平面４０２のｚ座標を連続的に変化させながら、仮想的にオブジェクトを切断し、それぞれの断面４０３の外周上の座標を求めることにより、オリジナルポリゴンデータ２０を代表点データとする。ここで、本実施の形態では、ｘｙ平面で切断する場合について説明するが、ｙｚ平面や、ｚｘ平面を用いて切断しても構わない。
【００５４】
以下、オブジェクト４０１をｚ座標がＺ1であるｘｙ平面４０２で仮想的に切 断した断面４０３を例として、基本ポリゴンデータ１０６１及び詳細ポリゴンデータ１０６２の算出までの処理の概念について説明する。
【００５５】
図４は、断面４０３の近傍に存在するオリジナルポリゴンデータ２０から、代表点データへの変換を行う場合の処理について説明するための図である。同図の領域４０４の部分に示されるように、断面４０３の近傍には、オリジナルポリゴンデータにより表される面の中で断面４０３と交差する面が多数存在する。同図に示された領域４０４の部分を拡大した図を図５に示す。
【００５６】
オリジナルポリゴンデータ２０により表される三角形ポリゴンの中で、断面４０３と交差する三角形４０５の頂点Ａ、Ｂ、Ｃの座標が、それぞれ(Xa,Ya,Za)、(Xb,Yb,Zb)、(Xc,Yc,Zc) であるとすると、当該座標から、頂点Ａと頂点Ｂとの間、及び頂点Ａと頂点Ｃとの間の線分ＡＢ及び線分ＡＣの上において、ｚ座標がＺ1である点の座標を算出することができる。線分ＡＢ上でｚ座標がＺ1である点をＰ、線分ＡＣ上でｚ座標がＺ1である点をＱとすると、Ｐ点の座標（Xp,Yp,Zp ）、及びＱ点の座標（Xq,Yq,Zq）は、具体的には、以下の式により容易に求めることができる。
【００５７】
Xp＝Xa×（Z1−Zb）／（Za−Zb）
Yp＝Ya×（Z1−Zb）／（Za−Zb）
Zp＝Z1
Xq＝Xa×（Z1−Zc）／（Za−Zc）
Yq＝Ya×（Z1−Zc）／（Za−Zc）
Zq＝Z1
このように算出された点を、以下、「代表点」という。
【００５８】
オリジナルポリゴンデータにより表される三角形のうち、断面４０３と交差する全ての三角形について、上記の処理を行うことにより、断面４０３の代表点の座標を算出することができる。図６は、断面４０３について全ての代表点を算出した結果の一例を示す図である。同図において黒い四角形で示されているのが代表点であるとする。
【００５９】
以上のように算出された代表点の座標を用いて、以下、ポリゴン階層化処理を行う。図７は、ポリゴン階層化処理における外周及び開始点について説明するための図である。同図に示されるように、代表点の間の線分をとり外周４０６を形成した後、外周４０６上で開始点Ｓを決定する。開始点Ｓとしては、外周４０６上の任意の点を選択することができるが、本実施の形態では、もっともｘ軸に近い代表点を開始点Ｓとしている。図７において、×で示された点が開始点Ｓである。
【００６０】
ここで、前述の処理により、代表点の座標が算出されているので、外周４０６の一周の長さを算出することができる。従って、開始点Ｓを起点とした場合に、外周４０６の一周の長さの中間にあたる点、即ち、中点の座標を求めることができる。図８は、中点を求めた結果の一例を示す図である。同図に示されるＭ1が 中点であるとする。上記中点の定義から、外周４０６上における開始点Ｓから中点Ｍ1までの長さは、上側、下側のどちらの経路をとった場合も等しい。即ち、 同図においてＬ01とＬ01′は等しい。
【００６１】
次に、開始点Ｓから中点Ｍ1までの線分の長さｌ01と、上記のＬ01とを比較す る。両者の差の絶対値（｜Ｌ01−ｌ01｜）が、所定の値εを下回っていれば、その後のポリゴン階層化処理は行う必要はない。
【００６２】
一方、両者の差の絶対値がε以上である場合には、さらに開始点Ｓと中点Ｍ1 との中点にあたる点を求める。図９は、開始点Ｓと中点Ｍ1との間の中点を示す 図である。同図に示されるＭ2が、開始点Ｓと中点Ｍ1との間の中点であるとする。上記中点の定義から、外周４０６上における開始点Ｓから中点Ｍ2までの長さ Ｌ02は、外周４０６上における中点Ｍ1から中点Ｍ2までの長さＬ12に等しい。
【００６３】
なお、中点としては、Ｍ2の他にＭ2′も求められるが、以後の説明では、Ｍ2を例として説明する。以下に説明する処理は、中点としてＭ2′を用いた場合についても行う。
【００６４】
図９において、開始点Ｓと中点Ｍ2との間の外周４０６上の長さをＬ02、線分 ＳＭ2の長さをｌ02とする。また同様に中点Ｍ1と中点Ｍ2との間の外周４０６上 の長さをＬ12、線分Ｍ1Ｍ2の長さをｌ12とする。
【００６５】
前述した内容より、Ｌ02はＬ12と等しいが、ｌ02とｌ12とは異なる。ここで、先の処理と同様にＬ02とｌ02、Ｌ12とｌ12との差をそれぞれ求める。即ち、Ｌ02とｌ02との差の絶対値（｜Ｌ02−ｌ02｜）、及びＬ12とｌ12との差の絶対値（｜Ｌ12−ｌ12｜）が、それぞれ一定値εを下回っているか否かを判定する。一定値εを下回っていれば、それ以上中点を求める必要はないと判定する。しかし、両者の差の絶対値がε以上であった場合には、開始点と中点との間、あるいは中点同士の間で、さらに中点を求め同様の処理を行う。このような処理を行うことにより、形状が複雑である部分については深く、単純な形状の部分については浅く、階層化された頂点データを得ることができる。以上の処理は、中点Ｍ2′を経 由する側でも同様に行う。図１０は、中点Ｍ1と中点Ｍ2との間に、さらに中点Ｍ3 を求めた場合について説明するための図である。同図の例では、Ｌ02とｌ02との差の絶対値（｜Ｌ02−ｌ02｜）が一定値εを下回っていたために、開始点Ｓと中点Ｍ2との間には、もはや新たな中点を求める必要が無くなっていたが、Ｌ12 と ｌ12との差の絶対値（｜Ｌ12−ｌ12｜）が一定値ε以上であったため、中点 Ｍ1 と中点Ｍ2との間に、さらに中点Ｍ3を求めたものである。
【００６６】
その後さらに上述と同様の処理を行い、最終的には、全ての中点の間において、外周４０６上の長さＬと、中点の間の線分の長さｌとが一定値εを下回るまで再帰的に処理を行うことにより、階層化された頂点データを得る。図１０の例であれば、Ｌ13とｌ13との差の絶対値（｜Ｌ13−ｌ13｜）は一定値εを下回っているため、中点Ｍ1と中点Ｍ3との間には、もはや新たな中点を求める必要はないが、Ｌ23とｌ23との差の絶対値（｜Ｌ23−ｌ23｜）は一定値ε以上であるため、中点Ｍ2と中点Ｍ3との間に、さらに中点Ｍ4が求められることとなる。
【００６７】
以上のような処理により得られた開始点Ｓ及び中点Ｍ1、Ｍ2、Ｍ3・・が階層 化ポリゴンデータにおける頂点データとなる。最初に得られた開始点Ｓ及び中点Ｍ1、Ｍ2（及びＭ2′）が基本ポリゴンデータ１０６１となり、その後に得られた中点Ｍ3以降は、基本ポリゴンデータ１０６１に順次追加していくことにより、 よりポリゴン数が多い場合に対処するための詳細ポリゴンデータ１０６２となる。
【００６８】
ここで、詳細ポリゴンデータ１０６２となる頂点の位置の情報としての、相対的な座標の算出処理について説明する。基本ポリゴンデータ１０６１は、画面への表示ポリゴン数が最も少ない場合に表示に用いられるポリゴンデータであるので、原点に対する絶対座標の形式で保持することが可能である。しかし、詳細ポリゴンデータ１０６２は、基本ポリゴンデータが、例えば基本ポリゴンデータ編集部１０２４により編集された場合等でも、順次追加していくことで、３Ｄポリゴンデータを復元することができるようなデータである必要があるため、絶対座標の形式では保持することができない。
【００６９】
従って、本実施の形態では、例えば、中点Ｍ3については、中点Ｍ1及び中点Ｍ2から見た場合の相対的な座標に変換して保持しておく必要がある。
【００７０】
図１１は、中点Ｍ3の相対的な座標について説明するための図である。中点Ｍ1及びＭ2を含むｘｙ平面における原点Ｏから中点Ｍ1及びＭ2までのベクトルをそ れぞれベクトルｍ1及びベクトルｍ2とすると、原点から中点Ｍ3までのベクトル ｍ3は、適切な実数ａ及びｂを選択することにより、(ａｍ1＋ｂｍ2)で表すこと ができる。従って、中点Ｍ3を表すデータとして、ベクトルｍ1及びベクトルｍ2 の情報と実数ａ及びｂの値とを保存しておくことによって、中点Ｍ1及びＭ2が変形等の処理により移動した場合であっても、相対的に適切な位置に中点Ｍ3を復 元することができる。
【００７１】
以上のような処理により、ｚ座標がＺ1である断面４０３について、階層化さ れた頂点データを得ることができる。この処理をｚ座標を変化させて行うことにより、オブジェクト４０１についての階層化された頂点データを得ることができる。
【００７２】
ただし、階層化された頂点データを、さらに階層化ポリゴンデータとするためには、適切な頂点をとって階層ごとに三角形を形成するようにしなければならない。一般的な３Ｄ表示ソフトウェアにオブジェクトを表示させるためには、ポリゴンを構成する頂点に関するデータの他、ポリゴンが表す面についてのデータを渡す必要がある場合が多いからである。
【００７３】
従って、本実施の形態の方法により得られた、階層化された頂点データを階層化ポリゴンデータとするために、各階層ごとに得られた頂点データについて、三角形ポリゴンを形成する頂点をグループ化する処理を行うことが必要である。具体的には、ｚ座標が一段階異なる二つの断面の間において、基本頂点データの座標を順次比較することにより、基本ポリゴンデータを構成する三角形の頂点をグループ化することが可能である。詳細頂点データを得る際に、その階層の深さを保持しておき、ここで、各階層ごとに詳細頂点のグループ化を行うことにより、詳細ポリゴンデータを構成する三角形の頂点の組み合わせを得ることができる。
【００７４】
図１２は、以上のような処理によって得られた階層化ポリゴンデータのデータ構造の一例を示す図である。以下、同図に示される階層化ポリゴンデータのデータ構造について詳細に説明する。
【００７５】
階層化ポリゴンデータ３０は、ステップ数データ３０１、頂点ステップデータ３０２、面ステップデータ３０３、基本ポリゴン頂点データ３０４、詳細ポリゴン頂点データ３０５、面データ３０６から構成され、オブジェクトごとにオブジェクト識別子３０７が付与されている。
【００７６】
ここで、「ステップ」とは、基本ポリゴンデータに対して詳細ポリゴンデータを順次追加していく処理のステップを意味する。即ち、ステップ数が大きいほど、ポリゴン数が多いことになる。
【００７７】
ステップ数データ３０１は、あるオブジェクトについての最大のステップ数、及び最大のステップ数の処理が行われた場合の頂点の数Ｖtと面の数Ｆtとを含んでいる。
【００７８】
頂点ステップデータ３０２としては、ステップ番号ごとの頂点の数が保持されている。本実施の形態の階層化ポリゴンデータでは、基本ポリゴンデータにはステップ番号０が対応する。頂点ステップデータ３０２においてステップ番号０に対応する頂点数が基本ポリゴンデータの頂点数である。ステップ番号０から、ステップ番号１、ステップ番号２とステップ番号が増加するに従って頂点数が増加していく。最終的には、ステップ数データ３０１として保持されている、最大のステップ番号に対応する頂点の数までのデータが頂点ステップデータ３０２として保持されている。最大のステップ数に対応する頂点の数はステップ数データ３０１として保持されているＶtに一致する。中間のステップ番号では、保持され ている数に頂点数が合致するまで、後述する詳細ポリゴン頂点データ３０５により表される頂点を追加していく。
【００７９】
本実施の形態の階層化ポリゴンデータを利用する場合には、表示ポリゴン数算出部１０２５において、表示ポリゴン数に対応するステップ番号を指定する。マージ処理部１０２６では、指定されたステップ数に従って、必要な階層化ポリゴンデータを取得し、ポリゴンデータを復元した後、３Ｄ情報表示部１０２７に渡すこととなる。
【００８０】
基本ポリゴン頂点データ３０４としては、基本ポリゴンデータを構成する頂点の絶対座標が、頂点ごとの識別子とともに格納されている。基本ポリゴン頂点データ３０４のデータ数は、頂点ステップデータ３０２に含まれているステップ番号０における頂点数に一致する。
【００８１】
詳細ポリゴン頂点データ３０５には、先に説明した中点Ｍ3等、詳細頂点とし て得られた頂点の相対座標が格納されるのであるが、その他のどの頂点を基準とした相対座標であるかを示すために、当該基準となる頂点の識別子が格納されている。本実施の形態の階層化ポリゴンデータでは、ｚ座標については、基準となる頂点と同じ座標を使用することが可能であるので、基準となる頂点は二つ保持しておけばよい。即ち、本実施の形態の例であれば、ｘｙ平面上における原点から当該二つの頂点へのベクトルの和により当該詳細頂点座標を決定する際の、先に説明した適切な実数ａ及びｂを保持しておけばよい。
【００８２】
ポリゴン面データ３０６としては、基本ポリゴン頂点データ、詳細ポリゴン頂点データを用いて、一定の階層の深さの三角形ポリゴンを構成した場合に、各三角形ポリゴンを構成する各頂点の識別子の組み合わせが格納される。組み合わせには、ポリゴンにより表される三角形の面の識別子IDFが付与される。
【００８３】
次に、以上に説明したポリゴンデータの階層化の概念に基づき、本実施の形態の３Ｄリアルタイム映像生成装置において、ポリゴンデータの階層化を行う際の、制御部１０２の処理内容について説明する。
【００８４】
図１３は、ポリゴン階層化処理を行う際の制御部１０２の処理内容を示すフローチャートである。同図に示される処理は、主として代表点変換部１０２１及びポリゴン階層化部１０２２によって行われる。
【００８５】
まず、代表点変換部１０２１が、ポリゴンの階層化処理を行うべきオブジェクトを選択し、オリジナルポリゴンデータ格納部１０４から、当該オブジェクトのオリジナルポリゴンデータを取得する（Ｓ１３０１）。
【００８６】
次に代表点変換部１０２１は、前述の如く、断面を得るための断面の座標を設定する（Ｓ１３０２）。ここでの座標はｚ座標に限られることなく任意の設定が可能である。
【００８７】
次に代表点変換部１０２１は、代表点算出処理を行う（Ｓ１３０３）。代表点算出方法の詳細については既に説明したので、ここでの説明は省略する。算出された代表点データは、代表点データ格納部１０５に格納される。
【００８８】
次に、ポリゴン階層化部１０２２により、ポリゴン階層化処理が行われる。まず、ポリゴン階層化部１０２２は、代表点データが得られた断面について、開始点（Ｓ１３０４）、及び第１の中点Ｍ1（Ｓ１３０５）の座標を算出する。
【００８９】
ここで、まず、開始点と中点Ｍ1とについて外周の長さＬと、線分の長さｌと の差を算出する（Ｓ１３０６）。長さの差が一定値εを下回っている場合（Ｓ１３０６：Ｙｅｓ）には、その後のポリゴン階層化ループには入らず、次の断面の処理へと進む。
【００９０】
長さの差が一定値εを下回っていない場合（Ｓ１３０６：Ｎｏ）には、ポリゴン階層化ループへと進む（Ｓ１３０７）。即ち、開始点と中点、又は中点同士の中点を算出し（Ｓ１３０８）、算出された中点の相対座標を階層化ポリゴンデータ格納部１０６に格納した上で（Ｓ１３０９）、当該中点について、外周の長さＬと線分の長さｌとの差と、一定値εとの比較を行う（Ｓ１３１０）。
【００９１】
全ての中点について、線分の長さｌと、対応する外周の長さＬとの差が一定値εを下回るまで、再帰的に処理を行うことにより、詳細ポリゴンデータの頂点データとなるべき相対座標を得る。
【００９２】
なお、一定値εの具体的な値については、オブジェクトの形状やマシン性能等の種々の条件によって異なるが、それぞれの環境に適した値を、予め任意に設定することが可能である。
【００９３】
一つの断面について、以上の処理を終了すると、次の断面についての処理に進み（Ｓ１３１１：Ｎｏ）、全ての断面について処理を終了すると、階層ごとにポリゴンを構成する三角形を構成する頂点の組み合わせを求めることにより、階層ごとに多面体を構成していく（Ｓ１３１２）。ここで、ポリゴン面データ３０６が得られる。さらに、必要な全てのオブジェクトについて処理を行うことにより（Ｓ１３１３：Ｎｏ）、最終的に必要な階層化ポリゴンデータを得ることができる。
【００９４】
得られた階層化ポリゴンデータは、先に説明したように、画面への表示ポリゴン数に応じて、基本ポリゴンデータに対して階層的に詳細ポリゴンデータを追加していくことにより、適切なポリゴン数の３Ｄポリゴンデータを復元することができる構造となっている。
【００９５】
以上に説明したように、上記のようなポリゴンデータの階層化方法を用いて生成された階層化ポリゴンデータを用いることにより、画面に表示できるポリゴン数が種々異なる場合であっても、どのようなポリゴン数にも対応できるような形式をとることができ、かつ、ポリゴンデータの記憶領域を節約することが可能となる。
（実施の形態２）
次に、本発明の第２の実施の形態について説明する。
【００９６】
本実施の形態では、本発明に係る第２の階層化ポリゴンデータ生成方法、即ち、オリジナルポリゴンデータ２０を階層化する第２の方法について説明する。
【００９７】
本実施の形態においても、まず階層化方法の概念について詳細に説明する。
【００９８】
図１４は、本実施の形態における階層化方法の概念について説明するためのオブジェクトの一例を示す図である。
【００９９】
本実施の形態では、図１４に示すように、オブジェクト１４０１に内接する四面体１４０２を仮想的に作成する。最初の四面体１４０２の頂点の座標が基本ポリゴンデータの頂点データとなる。最初の四面体１４０２の頂点の座標は、３Ｄ情報編集ツールを用いてユーザが指定することも可能であるが、自動的に計算することもできる。
【０１００】
次に、本実施の形態では、前記四面体１４０２と一つの面を共有する、新たな四面体を作成することによりポリゴンデータの階層化を行う。四面体の一つの面１４０３を底面とした四面体を作成する際の処理の様子の一例を図１５に示す。同図に示されるように、本実施の形態では、まず、四面体の一つの面１４０３の重心Ｇの座標を算出する。その後、重心Ｇから垂線を延ばし、当該垂線がオブジェクト１４０１の表面とあたる点をＤとすると、当該Ｄを頂点とした新たな四面体を作成することができる。新たな四面体１４０４を作成した様子を図１６に示す。
【０１０１】
第１の実施の形態では、外周上の長さＬと線分の長さｌとの差を、一定値εと比較したが、本実施の形態では、例えば、四面体の頂点をオブジェクト１４０１上での最短距離で区切った場合の、当該区切られた部分のオブジェクトの表面積と、対応する四面体の面の面積との差を、一定値とを比較することにより、どこまで階層化するかを判定する。
【０１０２】
即ち、例えば図１６において、もとの四面体の一つの面１４０３の頂点をＴ、Ｕ、Ｗとすると、新たに作成された四面体の頂点Ｄとの間において、ＴＤ間、ＤＵ間及びＴＵ間のオブジェクト１４０１の表面上における最短距離を求めることができる。それらで画された範囲のオブジェクト１４０１上における表面積と三角形ＴＤＵの面積との差を算出し、当該表面積と面積との差が所定の値を下回っていれば、三角形ＴＤＵを含む新たな四面体を作成する必要はないと判定する。所定の値を下回っていなければ、さらに三角形ＴＤＵの重心を算出し、前述と同様の処理により新たな四面体を作成する。
【０１０３】
以上の処理を、全ての面について所定の値を下回るまで、再帰的に繰り返して行うことにより階層化ポリゴンデータを得ることができる。本実施の形態の階層化ポリゴンデータは、新たに作成された四面体の頂点Ｄの座標については、元の四面体の面を構成する頂点Ｔ、Ｄ、Ｕを用いて定めた座標系における相対座標の形式で保持される。即ち、頂点Ｔから頂点Ｄへのベクトル、及び頂点Ｔから頂点Ｕへのベクトル、及び両者の外積により定められる座標系における相対座標上における座標として保持される。
【０１０４】
図１７は、新たな頂点の相対座標について詳細に説明するための図である。同図において、V11が頂点Ｔ、V12が頂点Ｗ、V13が頂点Ｕであり、V111が新たな頂 点Ｄであるとする。V11からV12までのベクトルをベクトルP1、V11からV13までのベクトルをベクトルP2とすると、ベクトルP1及びベクトルP2の外積として、ベクトルP3を得ることができる。
【０１０５】
ベクトルP1、P2、P3を用いて、V11を原点とする座標系における新たな頂点V111の相対座標を表すことができる。即ち、適切な実数ｌ、ｍ、ｎを選択すること により、V111＝ｌ111P1＋ｍ111P2＋ｎ111P3で表すことができる。
【０１０６】
図１８は、本実施の形態の階層化ポリゴンデータのデータ構造の一例を示す。第１の実施の形態で説明したものとは、詳細ポリゴン頂点データ３０５の内容が異なっている。基準となる頂点の識別子を三つ保持する必要があるためである。即ち、三つの頂点のうち最初に表された頂点から、その他の二つの頂点へのそれぞれのベクトルと、両者の外積とにより構成される３次元座標上における相対座標が格納される。即ち、上述の式で得られたｌ111、ｍ111、ｎ111をデータとし て保持する。
【０１０７】
以上のような処理により得られた基本ポリゴンデータ及び詳細ポリゴンデータも、第１の実施の形態と同様に、画面への表示ポリゴン数に応じて、基本ポリゴンデータに対して階層的に詳細ポリゴンデータを追加していくことにより、適切なポリゴン数の３Ｄポリゴンデータを復元することができるようになっている。即ち、上述の如く、新たに作成された頂点の座標が、元の四面体の一つの面に対する相対座標の形式で保持されているため、基本ポリゴンデータ１０６１の編集等がなされた場合でも、適切な３Ｄポリゴンデータを復元することができるからである。
【０１０８】
以上のような概念に基づいて、ポリゴンデータの階層化を行う場合の制御部１０２の処理内容について、以下に説明する。
【０１０９】
図１９は、本実施の形態の方法を用いてポリゴンデータの階層化を行う際の制御部１０２の処理内容を示すフローチャートである。
【０１１０】
まず、処理対象となるオブジェクトを選択し（Ｓ１９０１）、選択されたオブジェクトについて、図１５に示したような基本となる四面体の座標を決定する（Ｓ１９０２）。ここで、座標を決定する方法としては、制御部１０２が自動的に決定するようにすることも可能であるが、ユーザに指定させるようにしてもよい。
【０１１１】
次に、前述の方法に従って、四面体の各面の面積と、対応するオブジェクトの表面積との差を順次求め、予め定められた一定値と比較する（Ｓ１９０３）。四面体の全ての面について、差が一定値を下回っていれば（Ｓ１９０３：Ｙｅｓ）、それ以上ポリゴン階層化処理を行う必要はないので、次のオブジェクトを選択する。
【０１１２】
面積の差が一定値を下回っていない面があれば（Ｓ１９０３：Ｎｏ）、上述の概念に従って、ポリゴンの階層化処理を行う（Ｓ１９０４）。具体的には、当該面先の差が一定値を下回っていない面について、重心の座標を算出し（Ｓ１９０５）、法線ベクトルを求めた後（Ｓ１９０６）、新たな頂点の相対座標を詳細ポリゴンデータとして格納する（Ｓ１９０７）。
【０１１３】
以上の処理を、処理すべき全てのオブジェクトについて終了すれば（Ｓ１９０８：Ｙｅｓ）、ポリゴン階層化処理を終了する。
【０１１４】
以上に説明したようなポリゴンデータの階層化方法を用いて生成された階層化ポリゴンデータを用いることによっても、画面に表示できるポリゴン数が種々異なる場合において、どのようなポリゴン数にも対応できるような形式をとることができ、かつ、ポリゴンデータの記憶領域を節約することが可能となる。
（実施の形態３）
次に、本発明の第３の実施の形態について説明する。
【０１１５】
本実施の形態では、本発明に係る３Ｄリアルタイム映像生成装置における、表示ポリゴン数の管理方法について説明する。
【０１１６】
実施の形態１及び実施の形態２で説明したように、本発明に係る方法で得られた階層化ポリゴンデータを用いることにより、容易に所望の荒さのポリゴンデータを得ることができるが、ポリゴンデータを表示する際の表示ポリゴン数をいかにして決定するかが問題となる。表示環境に応じて、表示ポリゴン数を決定することができれば、それをパラメータとして付与し、基本ポリゴンデータに対して詳細ポリゴンデータを追加する処理を行うことにより所望の荒さのポリゴンデータを生成することができる。
【０１１７】
図２０は、本実施の形態の３Ｄリアルタイム映像生成装置において、表示ポリゴン数を算出する際の制御部１０２の処理内容を示すフローチャートである。なお、この処理は、階層化ポリゴンデータ等に基づいて、表示ポリゴン数算出部１０２５が行う。
【０１１８】
同図２０に示されるように、本実施の形態の３Ｄリアルタイム映像生成装置では、マシーンの機能、オブジェクトの表示位置の画面からの奥行き（以下、「Ｚ値」という。）、及びオブジェクトの動作スピードにより、表示するオブジェクトのポリゴン数を管理する。
【０１１９】
同図について詳細に説明する前に、本発明の３Ｄリアルタイム映像生成装置におけるポリゴン数管理の概念について説明する。
【０１２０】
まず、Ｚ値によるポリゴン数の管理について説明する。
【０１２１】
表示すべきオブジェクトが手前に存在する場合には、ポリゴン数を上げて表示しなければ、ポリゴンの形状がはっきりとわかってしまう。逆にオブジェクトが遠くに存在する場合には、表示する画像が小さくなるため、表示するポリゴン数を減らしても、見た目にはわからない。即ち、オブジェクトのＺ値に基づいて表示すべきポリゴン数を、先に説明したポリゴンデータの階層構造を用いて動的に変化させ、ＣＰＵやボードの処理すべき内容を最小限に押さえることが可能となる。
【０１２２】
図２１から図２５にポリゴン数を変化させた場合のオブジェクトの表示の様子の例を示す。図２１は１０，０００ポリゴン、図２２は、２，０００ポリゴン、図２３は、４００ポリゴン、図２４は、２２０ポリゴン、図２５は、２００ポリゴンである。同図に示されるように、ポリゴン数を減らしていくに従って、本実施の形態で用いている三角形ポリゴンの形状がはっきりわかるようになっている。図２６から図３０までは、図２１から図２５までのオブジェクトと同一のオブジェクトを上から見た様子を表したものである。
【０１２３】
図３１は、オブジェクトを縮小して表示したものであるが、これを見ると、Ｚ値が大きいオブジェクト（ａにいく程Ｚ値が大きい）の場合には、少ないポリゴン数でも違和感を感じさせることなく表示することができることがわかる。
【０１２４】
なお、本発明の３Ｄリアルタイム映像生成装置は、ポリゴンデータを階層的に保持しているため、カメラ方向から見えないポリゴン層を算出することもできる。このため、３Ｄ映像生成装置において一般的に行う必要のある、カメラから見えない部分のポリゴンを表示しないようにする処理も、ポリゴンデータを再帰的に展開する時点で判断することができる。
【０１２５】
また、一般的に、ポリゴン数が少ない場合には、オブジェクトの輪郭が目立つようになるが、カメラ方向とオブジェクトの法線との関係を使用することで輪郭部分にポリゴン数が多く、手前にはポリゴン数を少なくすることで、少ないポリゴン数でも品質の高い画像を生成することもできる。
【０１２６】
次に、オブジェクトの速度に基づいた表示ポリゴン数の管理について説明する。
【０１２７】
オブジェクトのアクション動作が大きい場合には、表示すべきポリゴン数を減らしても違和感を感じさせることなくオブジェクトの表示を行うことができる。例えば図３２に示されるような場合において、同図に示されるようなオブジェクトが高速で移動する場合であれば、移動の中間においてはポリゴン数を減らして表示しても、見た目に違和感を感じさせることはない。
【０１２８】
従って、アニメーションを表示する際に、フレームごとのオブジェクトの位置を管理しておき、オブジェクトの移動速度を算出することにより、表示ポリゴン数を減らすことが可能である。このオブジェクトの位置の管理は、オブジェクト全体で管理することもできるし、オブジェクトの部分に対して適用することもできる。例えば、人間が動作する場合において、腕だけを高速で動作させるような場合には、腕の部分の速度ベクトルを別個に管理することにより、当該腕部分のみのポリゴン数を減らすことができる。
【０１２９】
最後に、コンピュータの機能、性能等に基づくポリゴン数管理について説明する。例えば、高性能なボードを搭載したコンピュータであれば、１０，０００ポリゴンでオブジェクトをリアルタイムに表示できるのに対し、より性能の低いボードを用いた場合には、５００ポリゴンでオブジェクトの表示を行う必要がある場合もある。これら、最高表示可能ポリゴン数を決定するには、他にメモリの搭載量等も考慮する必要がある。
【０１３０】
以上のような概念に基づいた、表示ポリゴン数算出処理の詳細について、以下に説明する。図２０のフローチャートに戻って、本実施の形態における制御部１０２の処理内容について説明する。
【０１３１】
制御部１０２は、まず、マシンデータを取得する（Ｓ２００１）。マシンデータとは、コンピュータの機能、性能等に関する情報をいう。この値は、オブジェクトごとに変更する必要がなく、最初に一度取得しておけば十分である。
【０１３２】
マシンデータの取得方法には、種々の方法が考えられるが、例えば、パラメータの値としてユーザが付与する方法がある。
【０１３３】
その後、各オブジェクトごとに、まずＺ値を取得し（Ｓ２００２）、さらに、階層化ポリゴンデータ格納部１０６に格納されている、フレームごとのオブジェクトの重心の位置情報を取得して（Ｓ２００３）、フレームごとのオブジェクトの移動距離、即ち、オブジェクトの移動速度を算出したうえ（Ｓ２００４）、表示ポリゴン数を決定する（Ｓ２００５）。表示ポリゴン数としては、先に説明した、階層化ポリゴンデータにおけるステップ番号の形式でマージ処理部１０２６に渡すため、本実施の形態の表示ポリゴン数算出部１０２５は、具体的に利用可能なポリゴン数と、ステップ番号との対応関係を示すテーブルを保持している。これは、常にテーブルとして保持する必要はなく、例えば、最大の値に対する割合の形式でマージ処理部１０２６に渡すようにすることもできる。ステップＳ２００２からＳ２００５までの処理は、処理が終了するまで（Ｓ２００６）、オブジェクトごとに行う。
【０１３４】
以上に説明したように、本実施の形態の３Ｄリアルタイム映像生成装置を用いることにより、種々の表示環境に適応させた、適切な表示ポリゴン数により、オブジェクトの表示を行うことが可能となる。
（実施の形態４）
次に、本発明の第４の実施の形態について説明する。
【０１３５】
本実施の形態では、階層化されたポリゴンデータを用いて、動的にオブジェクトを変形して表示する方法について説明する。
【０１３６】
まず、階層化されたポリゴンデータを用いて、オブジェクトを変形する方法の概念について説明する。実施の形態１及び２において説明したように、本発明により生成された階層化ポリゴンデータは、あるオブジェクトをもっとも少ないポリゴン数で表現した場合の基本ポリゴンデータ１０６１と、その基本ポリゴンデータ１０６１により表されるオブジェクトの形状を、オリジナルポリゴンデータにより表される形状に近づけていくとした場合に、当該基本ポリゴンデータ１０６１に対して、階層的に追加していくべき多面体の頂点を表す詳細ポリゴンデータ１０６２の二つをふくんでいる。
【０１３７】
ここで、詳細ポリゴンデータ１０６２は、前述の如く相対座標で座標データを持っているので、例えば、基本ポリゴンデータ１０６１を基本ポリゴンデータ編集部１０２４を介して変形し、変形後の基本ポリゴンデータ１０６１に、詳細ポリゴンデータ１０６２を順次追加していくことによりオブジェクト全体の変形を行うことができる。
【０１３８】
まず、本実施の形態では、オブジェクトの平行移動について説明する。本発明に係る階層化ポリゴンデータの生成方法を用いて、階層化ポリゴンデータを求めたオブジェクトの一例を図３３に示す。このオブジェクトを、基本ポリゴンデータ１０６１のみを用いて表示すると、図３４に示すように、例えばオブジェクトの左足部分が三角形と荒いものとなる。
【０１３９】
その後、入力部１０１として備えられたマウス等の入力手段を用い、荒いオブジェクトを、例えば左右に平行移動する。オブジェクト全体を右に平行移動した後の様子を図３５に示す。同図の例では、画面の横軸に対して、オブジェクトを１０％平行移動している。編集後の基本ポリゴンデータは、内部的には、絶対座標の形式で、編集前の基本ポリゴンデータとは別に、階層化ポリゴンデータ格納部１０６に格納される。その後、マージ処理部１０２６が、詳細ポリゴンデータ１０６２を追加することにより、図３６に示すようにオブジェクト全体を平行移動することができる。なお、図３７から図４０までに示した例は、図３３から図３６に示したオブジェクトを上から見た場合について、同様の処理を行った例である。
【０１４０】
なお、本実施の形態では、二つの形状の間をダイレクトに平行移動したが、本実施の形態の例で示した二つの位置の中間の位置に移動したオブジェクトも作成し、一定時間ごとに表示することにより、徐々に移動しているアニメーションを作成することもできる。具体的には、基本ポリゴンデータ編集部１０２４を介して、オブジェクトの表示タイミングに関する情報をアニメーションを構成するそれぞれの階層化ポリゴンデータに付加しておき、当該情報で指定されたタイミングにてオブジェクトの表示を行うように、マージ処理部１０２６及び３Ｄ情報表示部１０２７が処理を行うことにより、アニメーションを表示させることが可能である。
【０１４１】
以上に説明したように、本実施の形態の３Ｄリアルタイム映像生成装置を用いることにより、オブジェクトの編集作業が容易となる。これにより、例えば、オブジェクトを徐々に変化させた画像を複数生成し、一定時間ごとに連続して表示することによるアニメーションを生成するような場合に、アニメータの作業工数を削減することが可能となる。さらに、本発明の階層化ポリゴンデータを用いれば、詳細ポリゴンデータの追加の際の計算量は、Ｏ(n)ですむ、即ち問題の複雑 度がｎ倍に増えても計算量がｎ倍で抑えられるため、コンピュータによる処理を高速に行うことも可能となる。
（実施の形態５）
次に、本発明の第５の実施の形態について説明する。
【０１４２】
本実施の形態では、オブジェクトの一部を変形する場合について説明する。
【０１４３】
本発明に係る階層化ポリゴンデータの生成方法を用いて、階層化ポリゴンデータを求めたオブジェクトの一例を図４１に示す。このオブジェクトを、基本ポリゴンデータ１０６１のみを用いて表示すると、図４２に示すように、例えばオブジェクトの左足部分が三角形と荒いものとなる。
【０１４４】
次に、このオブジェクトの左足部分のポリゴンの頂点位置を、第４の実施の形態の同様の方法で変更する。図４３は、変更により変形されたポリゴンの形状を示す図である。
【０１４５】
その後、マージ処理部１０２６が、詳細ポリゴンデータ１０６２を追加することにより、図４４に示すようにオブジェクトの左足部分のみ足を持ち上げている形状を作成することができる。同図に示されるように、本発明の方法では、ポリゴン全体において、ポリゴンの亀裂、歪み等の不具合は発生しないことも確認できる。なお、図４５から図４８までに示した例は、図４１から図４４に示したのと同じオブジェクトを左下から見た場合について、同様の処理を行った場合の例である。
【０１４６】
なお、本実施の形態では、二つの形状の間をダイレクトに変形したが、本実施の形態の例で示した二つの形状の中間の形状も作成し、一定時間ごとに表示することにより、第４の実施の形態と同様に、左足を徐々に持ち上げているアニメーションを作成することもできる。
【０１４７】
以上に説明したように、本実施の形態の３Ｄリアルタイム映像生成装置を用いることによっても、オブジェクトの編集が容易となる。これにより、例えば、オブジェクトを徐々に変化させた映像を生成し、一定時間ごとに連続して表示することによるアニメーションを生成するような場合に、アニメータの作業工数を削減することが可能となる。さらに、本発明の階層化ポリゴンデータを用いれば、詳細ポリゴンデータの追加の際の計算量は、Ｏ(n)ですむ、即ち問題の複雑度がｎ倍に増えても計算量がｎ倍で抑えられるため、コンピュータによる処理を高速に行うことも可能となる。
（実施の形態６）
次に、本発明の第６の実施の形態について説明する。
【０１４８】
本実施の形態では、オブジェクトの全体を変形する場合について説明する。
【０１４９】
本発明に係る階層化ポリゴンデータの生成方法を用いて、階層化ポリゴンデータを求めたオブジェクトの一例を図４９に示す。このオブジェクトを、基本ポリゴンデータ１０６１のみを用いて表示すると、図５０に示すように、例えばオブジェクトの左足部分が三角形と荒いものとなる。
【０１５０】
次に、この左足のポリゴンの頂点位置を、基本ポリゴンデータ編集部１０２４を介して変更する。変更によりポリゴンの形状が変化した様子を図５１に示す。
その後、第４の実施の形態と同様の処理を行うことにより、図５２に示すようにオブジェクトの左足部分が膨らんだ形状を作成することができる。なお、図５３から図５６までに示した例は、図４９から図５２に示した例と同一のオブジェクトを上から見た場合について、同様の処理を行った場合の例である。
【０１５１】
なお、本実施の形態では、二つの形状の間をダイレクトに変形したが、本実施の形態の例で示した二つの形状の中間のオブジェクトも複数作成しておき、一定時間ごとに表示していくことにより、第４の実施の形態と同様に、左足が徐々に膨れていくアニメーションを作成することもできる。
【０１５２】
以上に説明したように、本実施の形態の３Ｄリアルタイム映像生成装置を用いることによっても、オブジェクトの編集が容易となる。これにより、例えば、オブジェクトを徐々に変化させた映像を生成し、一定時間ごとに連続して表示することによるアニメーションを生成するような場合に、アニメータの作業工数を削減することが可能となる。さらに、本発明の階層化ポリゴンデータを用いれば、詳細ポリゴンデータの追加の際の計算量は、Ｏ(n)ですむ、即ち問題の複雑度がｎ倍に増えても計算量がｎ倍で抑えられるため、コンピュータによる処理を高速に行うことも可能となる。
【０１５３】
なお、本実施の形態では、階層化ポリゴンデータの生成方法として、三次元オブジェクトを仮想的に切断する方法と、四面体を階層的にオブジェクトの形状に近付けていく方法について説明したが、階層的に詳細頂点を求め、求められた詳細頂点の位置に関する情報を相対座標の形式で保持するようにすれば本発明の効果を得ることができる。そのような方法は、他にも種々考えられる。
【０１５４】
本発明である３Ｄポリゴンデータ生成装置及び３Ｄリアルタイム映像生成装置を実現するプログラムを記憶した記録媒体は、図５７に示す記録媒体の例に示すように、ＣＤ−ＲＯＭやフロッピーディスク等の可搬型記録媒体だけでなく、通信回線の先に備えられた他の記憶装置や、コンピュータのハードディスクやＲＡＭ等の記録媒体のいずれでもよく、プログラム実行時には、プログラムはローディングされ、主メモリ上で実行される。
【０１５５】
また、本発明である３Ｄポリゴンデータ生成装置または方法により生成された階層化ポリゴンデータを記録した記録媒体も、図５７に示す記録媒体の例に示すように、ＣＤ−ＲＯＭやフロッピーディスク等の可搬型記録媒体だけでなく、通信回線の先に備えられた他の記憶装置や、コンピュータのハードディスクやＲＡＭ等の記録媒体のいずれでもよく、例えば本発明である３Ｄリアルタイム映像生成装置を利用する際に、コンピュータにより読みとられる。
【０１５６】
【発明の効果】
以上に説明したように、本発明に係る階層化ポリゴンデータ生成装置及び方法を用いることにより、種々の表示ポリゴン数に対応することが可能となるため、性能の異なる機械でも汎用的に利用できる３Ｄポリゴンデータを生成することができ、また、詳細ポリゴンデータを階層的に生成するため、３Ｄポリゴンデータを格納する記憶領域を節約することができるという効果がある。
【０１５７】
また、本発明において生成された階層化ポリゴンデータを用いれば、コンピュータの処理量を軽減することができ、高速に処理を行うことができるという効果もある。
【０１５８】
さらに、本発明に係る３Ｄリアルタイム映像生成装置及び方法を用いることにより、オブジェクトの編集が容易となり、アニメータの工数を削減することができるという効果がある。
【図面の簡単な説明】
【図１】  本発明の一実施の形態に係る３Ｄリアルタイム映像生成装置の構成を示す機能ブロック図である。
【図２】  オリジナルポリゴンデータのデータ構造の一例を示す図である。
【図３】  第１の実施の形態のオブジェクトの階層化方法について説明するための、オブジェクトの一例を示す図である。
【図４】  断面４０３の近傍に存在するオリジナルポリゴンデータから、代表点データへの変換を行う場合の処理について説明するための図である。
【図５】  領域４０４の部分を拡大した図である。
【図６】  断面４０３について全ての代表点を算出した結果の一例を示す図である。
【図７】  外周及び開始点について説明するための図である。
【図８】  中点について説明するための図である。
【図９】  開始点Ｓと中点Ｍ1との間の中点を示す図である。
【図１０】  中点Ｍ1と中点Ｍ2との間に、さらに中点Ｍ3を求めた場合について説明するための図である。
【図１１】  中点Ｍ3の相対的な座標について説明するための図である。
【図１２】  第１の実施の形態における階層化ポリゴンデータのデータ構造の一例を示す図である。
【図１３】  本発明の第１の実施の形態においてポリゴンデータの階層化を行う際の制御部の処理内容を示すフローチャートである。
【図１４】  オブジェクトに内接する四面体の一例を示す図である。
【図１５】  四面体の一つの面を底面とした四面体を作成する際の処理の様子の一例を示す図である。
【図１６】  新たな四面体を作成した様子を示す図である。
【図１７】  新たな頂点の相対座標について説明するための図である。
【図１８】  第２の実施の形態における階層化ポリゴンデータのデータ構造の一例を示す図である。
【図１９】  本発明の第２の実施の形態においてポリゴンデータの階層化を行う際の制御部の処理内容を示すフローチャートである。
【図２０】  表示ポリゴン数の制御を行う際の制御部の処理内容を示すフローチャートである。
【図２１】  オブジェクトの一例を１０，０００ポリゴンで表示した場合を示す図である。
【図２２】  図２１と同一のオブジェクトを２，０００ポリゴンで表示した場合を示す図である。
【図２３】  図２１と同一のオブジェクトを４００ポリゴンで表示した場合を示す図である。
【図２４】  図２１と同一のオブジェクトを２２０ポリゴンで表示した場合を示す図である。
【図２５】  図２１と同一のオブジェクトを２００ポリゴンで表示した場合を示す図である。
【図２６】  図２１と同一のオブジェクトを上から見た様子を表す図である。
【図２７】  図２２と同一のオブジェクトを上から見た様子を表す図である。
【図２８】  図２３と同一のオブジェクトを上から見た様子を表す図である。
【図２９】  図２４と同一のオブジェクトを上から見た様子を表す図である。
【図３０】  図２５と同一のオブジェクトを上から見た様子を表す図である。
【図３１】  オブジェクトを縮小して表示した様子を表す図である。
【図３２】  表示速度による表示ポリゴン数管理について説明するための図である。
【図３３】  オブジェクトの平行移動について説明するための図である。
【図３４】  オブジェクトの平行移動について説明するための図である。
【図３５】  オブジェクトの平行移動について説明するための図である。
【図３６】  オブジェクトの平行移動について説明するための図である。
【図３７】  オブジェクトの平行移動について説明するための図である。
【図３８】  オブジェクトの平行移動について説明するための図である。
【図３９】  オブジェクトの平行移動について説明するための図である。
【図４０】  オブジェクトの平行移動について説明するための図である。
【図４１】  オブジェクトの一部変形について説明するための図である。
【図４２】  オブジェクトの一部変形について説明するための図である。
【図４３】  オブジェクトの一部変形について説明するための図である。
【図４４】  オブジェクトの一部変形について説明するための図である。
【図４５】  オブジェクトの一部変形について説明するための図である。
【図４６】  オブジェクトの一部変形について説明するための図である。
【図４７】  オブジェクトの一部変形について説明するための図である。
【図４８】  オブジェクトの一部変形について説明するための図である。
【図４９】  オブジェクト全体の変形について説明するための図である。
【図５０】  オブジェクト全体の変形について説明するための図である。
【図５１】  オブジェクト全体の変形について説明するための図である。
【図５２】  オブジェクト全体の変形について説明するための図である。
【図５３】  オブジェクト全体の変形について説明するための図である。
【図５４】  オブジェクト全体の変形について説明するための図である。
【図５５】  オブジェクト全体の変形について説明するための図である。
【図５６】  オブジェクト全体の変形について説明するための図である。
【図５７】  記録媒体の例を示す図である。
【符号の説明】
１０１          入力部
１０２          制御部
１０２１        代表点変換部
１０２２        ポリゴン階層化部
１０２３        入力受付部
１０２４        基本ポリゴンデータ編集部
１０２５        表示ポリゴン数算出部
１０２６        マージ処理部
１０２７        ３Ｄ情報表示部
１０３          出力部
１０４          オリジナルポリゴンデータ格納部
１０５          代表点データ格納部
１０６          階層化ポリゴンデータ格納部
１０６１        基本ポリゴンデータ
１０６２        詳細ポリゴンデータ
２０            オリジナルポリゴンデータ
２０１          頂点データ
２０２          三角形ポリゴンデータ
２０３          オブジェクト識別子
３０            階層化ポリゴンデータ
３０１          ステップ数データ
３０２          頂点ステップデータ
３０３          面ステップデータ
３０４          基本ポリゴン頂点データ
３０５          詳細ポリゴン頂点データ
３０６          ポリゴン面データ
３０７          オブジェクト識別子
４０１          オブジェクト
４０２          ｘｙ平面
４０３          断面
４０４          領域
４０５          三角形ポリゴン
４０６          外周
１４０１        オブジェクト
１４０２        四面体
１４０３        面
１４０４        新たな四面体
５７１          回線先の記憶装置
５７２          ＣＤ−ＲＯＭやフロッピーディスク等の可搬型記録媒体
５７２−１      ＣＤ−ＲＯＭ
５７２−２      フロッピーディスク
５７３          コンピュータ
５７４          コンピュータ上のＲＡＭ／ハードディスク等の記録媒体
【図１】
0003654616.tif 000002
【図２】
0003654616.tif 000003
【図３】
0003654616.tif 000004
【図４】
0003654616.tif 000005
【図５】
0003654616.tif 000006
【図６】
0003654616.tif 000007
【図７】
0003654616.tif 000008
【図８】
0003654616.tif 000009
【図９】
0003654616.tif 000010
【図１０】
0003654616.tif 000011
【図１１】
0003654616.tif 000012
【図１２】
0003654616.tif 000013
【図１３】
0003654616.tif 000014
【図１４】
0003654616.tif 000015
【図１５】
0003654616.tif 000016
【図１６】
0003654616.tif 000017
【図１７】
0003654616.tif 000018
【図１８】
0003654616.tif 000019
【図１９】
0003654616.tif 000020
【図２０】
0003654616.tif 000021
【図２１】
0003654616.tif 000022
【図２２】
0003654616.tif 000023
【図２３】
0003654616.tif 000024
【図２４】
0003654616.tif 000025
【図２５】
0003654616.tif 000026
【図２６】
0003654616.tif 000027
【図２７】
0003654616.tif 000028
【図２８】
0003654616.tif 000029
【図２９】
0003654616.tif 000030
【図３０】
0003654616.tif 000031
【図３１】
0003654616.tif 000032
【図３２】
0003654616.tif 000033
【図３３】
0003654616.tif 000034
【図３４】
0003654616.tif 000035
【図３５】
0003654616.tif 000036
【図３６】
0003654616.tif 000037
【図３７】
0003654616.tif 000038
【図３８】
0003654616.tif 000039
【図３９】
0003654616.tif 000040
【図４０】
0003654616.tif 000041
【図４１】
0003654616.tif 000042
【図４２】
0003654616.tif 000043
【図４３】
0003654616.tif 000044
【図４４】
0003654616.tif 000045
【図４５】
0003654616.tif 000046
【図４６】
0003654616.tif 000047
【図４７】
0003654616.tif 000048
【図４８】
0003654616.tif 000049
【図４９】
0003654616.tif 000050
【図５０】
0003654616.tif 000051
【図５１】
0003654616.tif 000052
【図５２】
0003654616.tif 000053
【図５３】
0003654616.tif 000054
【図５４】
0003654616.tif 000055
【図５５】
0003654616.tif 000056
【図５６】
0003654616.tif 000057
【図５７】
0003654616.tif 000058