(57)【特許請求の範囲】
【請求項１】
階層球体モデル保持部（１）に保持されている階層球体モデルの、所定の半径以下の球体のうち、最も上位の階層の球体をレンダリング球として指定するとともに、各レンダリング球に対応してレンダリングモデルを割り当てておき、レンダリング球がクリップ領域の内部か外部かを判定して、レンダリング球がクリップ領域の外部である場合に該当するレンダリングモデルをクリップすることを特徴とする高速レンダリング方法。
【請求項２】
モデル化の対象となる物体の表面を、メッシュ分割するとともに、メッシュ分割された各メッシュの全ての辺の長さを予め設定した最下位階層の球の直径以下に設定し、メッシュ分割により発生し、メッシュデータ保持部（４４）により保持した各節点を中心として最下位階層の球体を生成し、次いで、全節点に基づいて定まる立方体領域を含む最小の球体を生成して最上位階層の球体とし、その後、最上位階層の球体の中心を通る平面で全節点を２分割し、分割された各区分に属する全節点に基づいて定まる立方体領域を含む最小の球体を生成して、分割前の階層の次の階層の球体とし、その後、全節点の２分割処理および各区分に属する全節点に基づいて定まる立方体領域を含む最小の球体を生成して次の球体とする処理を、分割後の節点数が１になるまで反復することにより階層球体モデルを作成する請求項１に記載の高速レンダリング方法。
【請求項３】
視点位置保持部（１１）に保持されている視点位置を基準として、視線方向ベクトル保持部（１２）に保持されている視線方向ベクトルおよび視野角保持部（１３）に保持されている視野角により視野が規定されている状態において、視点から、レンダリング球中心保持部（１３ａ）に保持されているレンダリング球の中心に向かうベクトルと、このベクトルを中心としてレンダリング球の広がりを規定する角度とを算出し、両ベクトルのなす角が視野角とレンダリング球の広がりを規定する角度との和よりも大きいことを条件として該当するレンダリング球を除去する請求項１または請求項２に記載の高速レンダリング方法。
【請求項４】
視野内に少なくとも一部が含まれるレンダリング球について、このレンダリング球に含まれるポリゴンをそれぞれの法線ベクトルの向きに基づいて複数のグループに区分し、各区分に属するポリゴンの法線の集合体を円錐で近似し、視点から、レンダリング球中心保持部（２１）に保持されているレンダリング球の中心に向かうベクトルを中心としてレンダリング球の広がりを規定する第１広がり角度を算出するとともに、ポリゴンの法線の集合体を近似する円錐の中心軸を規定する中心軸ベクトルおよびこの円錐の第２広がり角度を算出し、視点からレンダリング球の中心に向かうベクトルと中心軸ベクトルとのなす角が両広がり角度の和以下であることを条件として、該当する区分に属するポリゴンを描画の対象として選択する請求項１から請求項３の何れかに記載の高速レンダリング方法。
【請求項５】
各レンダリングモデルに対応するポリゴンについて、視点からレンダリング球の中心に向かうベクトルの大きさに対応させて、予め描画精度が異なる複数のポリゴンを生成してＬＯＤモデル保持部（３１）に保持しておき、上記ベクトルの実際の大きさに基づいて該当する描画精度のポリゴンを描画する請求項１から請求項４の何れかに記載の高速レンダリング方法。
【請求項６】
階層球体モデルの、所定の半径以下の球体のうち、最も上位の階層の球体をレンダリング球として指定するレンダリング球指定手段（２）と、各レンダリング球に対応してレンダリングモデルを割り当てるレンダリングモデル割り当て手段（３）と、レンダリング球がクリップ領域の内部か外部かを判定する内外判定手段（５）と、レンダリング球がクリップ領域の外部であることを示す内外判定手段（５）の判定結果に応答して該当するレンダリングモデルをクリップするクリップ手段（６）とを有することを特徴とする高速レンダリング装置。
【請求項７】
モデル化の対象となる物体の表面を、メッシュ分割するとともに、メッシュ分割された各メッシュの全ての辺の長さを予め設定した最下位階層の球の直径以下に設定するメッシュ分割手段（４３）と、メッシュ分割により発生した各節点を中心として最下位階層の球体を生成する最下位階層球体生成手段（４９）と、全節点に基づいて定まる立方体領域を含む最小の球体を生成して最上位階層の球体とする最上位階層球体生成手段（４５）と、処理時点での最上位階層の球体の中心を通る平面で全節点を２分割する分割手段（４６）と、分割された各区分に属する全節点に基づいて定まる立方体領域を含む最小の球体を生成して、分割前の階層の次の階層の球体とする中間階層球体生成手段（４８）と、分割手段（４６）による処理および中間階層球体生成手段（４８）による処理を、分割後の節点数が１になるまで反復させる反復制御手段とをさらに有している請求項６に記載の高速レンダリング装置。
【請求項８】
視野を規定すべく、視点位置を基準として設定された視線方向ベクトルおよび視野角を保持する保持手段（１２）（１３）と、視点からレンダリング球の中心に向かうベクトルと、このベクトルを中心としてレンダリング球の広がりを規定する角度とを算出する算出手段（１５）（１６）と、両ベクトルのなす角が視野角とレンダリング球の広がりを規定する角度との和よりも大きいか否かを判定する第１大小判定手段（１８）と、両ベクトルのなす角が視野角とレンダリング球の広がりを規定する角度との和よりも大きいことを示す第１大小判定手段（１８）の判定結果に応答して該当するレンダリング球を除去するレンダリング球除去手段（１９）とをさらに有している請求項６または請求項７に記載の高速レンダリング装置。
【請求項９】
視野内に少なくとも一部が含まれるレンダリング球について、このレンダリング球に含まれるポリゴンをそれぞれの法線ベクトルの向きに基づいて複数のグループに区分する区分手段と、各区分に属するポリゴンの法線の集合体を円錐で近似する近似手段と、視点からレンダリング球の中心に向かうベクトルを中心としてレンダリング球の広がりを規定する第１広がり角度を算出する第１算出手段（２４）と、ポリゴンの法線の集合体を近似する円錐の中心軸を規定する中心軸ベクトルおよびこの円錐の第２広がり角度を算出する第２算出手段（２５）（２６）（２７）と、視点からレンダリング球の中心に向かうベクトルと中心軸ベクトルとのなす角が両広がり角度の和以下であるか否かを判定する第２大小判定手段（２９）と、視点からレンダリング球の中心に向かうベクトルと中心軸ベクトルとのなす角が両広がり角度の和以下であることを示す第２大小判定手段の判定結果に応答して該当する区分に属するポリゴンを描画の対象として選択する選択手段（３０）とをさらに有している請求項６から請求項８の何れかに記載の高速レンダリング装置。
【請求項１０】
各レンダリングモデルに対応するポリゴンについて、視点からレンダリング球の中心に向かうベクトルの大きさに対応させて、予め描画精度が異なる複数のポリゴンを生成しておくポリゴン生成手段（３１）と、上記ベクトルの実際の大きさに基づいて該当する描画精度のポリゴンを描画する描画手段（３２）（３３）（３４）（３５）とをさらに有している請求項６から請求項９の何れかに記載の高速レンダリング装置。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
この発明は高速レンダリング方法およびその装置に関し、さらに詳細にいえば、視覚効果を低下させることなく３次元モデルの描画時間を減少させるための高速レンダリング方法およびその装置に関する。この方法およびその装置は、景観シミュレーション、人工現実感などの分野に好適に適用可能である。
【０００２】
【従来の技術】
近年、コンピュータグラフィックス（以下、ＣＧと略称する）技術を応用した景観シミュレーション、サイエンティフィックビジュアライゼーションなどの研究が盛んに行われているとともに、ウォークスルー、フライトシミュレータなどの人工現実感の研究も盛んに行われている。ここで、前者は主として静止画を対象とするのに対して、後者は動画を対象としている。したがって、後者に適用されるＣＧ技術として一般的に描画の高速性が強く要求される。ただし、前者においても、特に景観シミュレーションなどのように膨大なデータ量を有する場合があるので、やはり描画の高速性が要求される。また、何れの場合においても、視覚効果を低下させることなく高速性を達成することが要求される。
【０００３】
この要求を達成するための方法として、従来から、次の３つの方法が提案されている。
（１）  空間分割により立体をグルーピングしておき、グループごとに視野に対する内外判定を行い、視野内であると判定されたグループのみを描画対象とすることにより、該当する３次元モデルの描画を高速化する方法（「広域３次元オブジェクト管理システム」、玉田隆史、中村泰明、ＴＥＣＨＮＩＣＡＬ  ＲＥＰＯＲＴ  ＯＦ  ＩＥＩＣＥ  ＨＣ９３−１１（１９９３−０５）、社団法人  電子情報通信学会）
（２）  形状の段階的簡略化表現を行う方法、例えば、視点からの距離が小さい場合には形状をそのまま表示し、視点からの距離が大きい場合には形状を簡略化して表示することにより、該当する３次元モデル全体としての描画を高速化する方法（“Ａｄａｐｔｉｖｅ  Ｄｉｓｐｌａｙ  Ａｌｇｏｒｉｔｈｍ  ｆｏｒ  Ｉｎｔｅｒａｃｔｉｖｅ  Ｆｒｍｅ  Ｒａｔｅｓ  Ｄｕｒｉｎｇ  Ｖｉｓｕａｌｉｚａｔｉｏｎ  ｏｆ  Ｃｏｍｐｌｅｘ  Ｖｉｒｔｕａｌ  Ｅｎｖｉｒｏｎｍｅｎｔｓ”，Ｔｈｏｍａｓ  Ａ．  Ｆｕｎｋｈｏｕｓｅｒ  ａｎｄ  Ｃａｒｌｏ  Ｈ．  外１，  ＣＯＭＰＵＴＥＲ  ＧＲＡＰＨＩＣＳ  Ｐｒｏｃｅｅｄｉｎｇｓ，  Ａｎｎｕａｌ  Ｃｏｎｆｅｒｅｎｃｅ  Ｓｅｒｉｅｓ，  １９９３）、および
【０００４】
【外１】
0003724006.tif 000002
【０００５】
（３）  視線の向きによる面のグルーピングを行い、グループごとに視点から見えるか否かの判定を行い、見えると判定されたグループのみを描画対象とすることにより、該当する３次元モデルの描画を高速化する方法（「リアルタイム景観シミュレータのための形状のグルーピングと多重表現に基づく描画時間の短縮」、北嶋克寛、遊佐洋子、電子情報通信学会論文誌Ｄ−ＩＩ  Ｖｏｌ．Ｊ７７−Ｄ−ＩＩ  Ｎｏ．２  ｐｐ．３１１−３２０  １９９４年２月）
【０００６】
【発明が解決しようとする課題】
しかし、上記従来の方法は、全て視点と描画物体との位置関係により描画するポリゴンを選出する方法であり、しかも立方体領域、オクトトリーなどの多面体表現を用いて位置関係を計算するのであるから、計算コストがかかるという不都合がある。そして、計算コストがかかることに起因して、描画ポリゴンの選出の所要時間が長くなり、ひいては描画所要時間が長くなってしまう。
【０００７】
【発明の目的】
この発明は上記の問題点に鑑みてなされたものであり、描画ポリゴンの選出所要時間を大幅に短縮することができる高速レンダリング方法およびその装置を提供することを目的としている。
【０００８】
【課題を解決するための手段】
請求項１の高速レンダリング方法は、階層球体モデル保持部（１）に保持されている階層球体モデルの、所定の半径以下の球体のうち、最も上位の階層の球体をレンダリング球として指定するとともに、各レンダリング球に対応してレンダリングモデルを割り当てておき、レンダリング球がクリップ領域の内部か外部かを判定して、レンダリング球がクリップ領域の外部である場合に該当するレンダリングモデルをクリップする方法である。
【０００９】
請求項２の高速レンダリング方法は、モデル化の対象となる物体の表面を、メッシュ分割するとともに、メッシュ分割された各メッシュの全ての辺の長さを予め設定した最下位階層の球の直径以下に設定し、メッシュ分割により発生し、メッシュデータ保持部（４４）により保持した各節点を中心として最下位階層の球体を生成し、次いで、全節点に基づいて定まる立方体領域を含む最小の球体を生成して最上位階層の球体とし、その後、最上位階層の球体の中心を通る平面で全節点を２分割し、分割された各区分に属する全節点に基づいて定まる立方体領域を含む最小の球体を生成して、分割前の階層の次の階層の球体とし、その後、全節点の２分割処理および各区分に属する全節点に基づいて定まる立方体領域を含む最小の球体を生成して次の球体とする処理を、分割後の節点数が１になるまで反復することにより階層球体モデルを作成する方法である。
【００１０】
請求項３の高速レンダリング方法は、視点位置保持部（１１）に保持されている視点位置を基準として、視線方向ベクトル保持部（１２）に保持されている視線方向ベクトルおよび視野角保持部（１３）に保持されている視野角により視野が規定されている状態において、視点から、レンダリング球中心保持部（１３ａ）に保持されているレンダリング球の中心に向かうベクトルと、このベクトルを中心としてレンダリング球の広がりを規定する角度とを算出し、両ベクトルのなす角が視野角とレンダリング球の広がりを規定する角度との和よりも大きいことを条件として該当するレンダリング球を除去する方法である。
【００１１】
請求項４の高速レンダリング方法は、視野内に少なくとも一部が含まれるレンダリング球について、このレンダリング球に含まれるポリゴンをそれぞれの法線ベクトルの向きに基づいて複数のグループに区分し、各区分に属するポリゴンの法線の集合体を円錐で近似し、視点から、レンダリング球中心保持部（２１）に保持されているレンダリング球の中心に向かうベクトルを中心としてレンダリング球の広がりを規定する第１広がり角度を算出するとともに、ポリゴンの法線の集合体を近似する円錐の中心軸を規定する中心軸ベクトルおよびこの円錐の第２広がり角度を算出し、視点からレンダリング球の中心に向かうベクトルと中心軸ベクトルとのなす角が両広がり角度の和以下であることを条件として、該当する区分に属するポリゴンを描画の対象として選択する方法である。
【００１２】
請求項５の高速レンダリング方法は、各レンダリングモデルに対応するポリゴンについて、視点からレンダリング球の中心に向かうベクトルの大きさに対応させて、予め描画精度が異なる複数のポリゴンを生成してＬＯＤモデル保持部（３１）に保持しておき、上記ベクトルの実際の大きさに基づいて該当する描画精度のポリゴンを描画する方法である。
請求項６の高速レンダリング装置は、階層球体モデルの、所定の半径以下の球体のうち、最も上位の階層の球体をレンダリング球として指定するレンダリング球指定手段と、各レンダリング球に対応してレンダリングモデルを割り当てるレンダリングモデル割り当て手段と、レンダリング球がクリップ領域の内部か外部かを判定する内外判定手段と、レンダリング球がクリップ領域の外部であることを示す内外判定手段の判定結果に応答して該当するレンダリングモデルをクリップするクリップ手段とを有している。
【００１３】
請求項７の高速レンダリング装置は、モデル化の対象となる物体の表面を、メッシュ分割するとともに、メッシュ分割された各メッシュの全ての辺の長さを予め設定した最下位階層の球の直径以下に設定するメッシュ分割手段と、メッシュ分割により発生した各節点を中心として最下位階層の球体を生成する最下位階層球体生成手段と、全節点に基づいて定まる立方体領域を含む最小の球体を生成して最上位階層の球体とする最上位階層球体生成手段と、処理時点での最上位階層の球体の中心を通る平面で全節点を２分割する分割手段と、分割された各区分に属する全節点に基づいて定まる立方体領域を含む最小の球体を生成して、分割前の階層の次の階層の球体とする中間階層球体生成手段と、分割手段による処理および中間階層球体生成手段による処理を、分割後の節点数が１になるまで反復させる反復制御手段とをさらに有している。
【００１４】
請求項８の高速レンダリング装置は、視野を規定すべく、視点位置を基準として設定された視線方向ベクトルおよび視野角を保持する保持手段と、視点からレンダリング球の中心に向かうベクトルと、このベクトルを中心としてレンダリング球の広がりを規定する角度とを算出する算出手段と、両ベクトルのなす角が視野角とレンダリング球の広がりを規定する角度との和よりも大きいか否かを判定する第１大小判定手段と、両ベクトルのなす角が視野角とレンダリング球の広がりを規定する角度との和よりも大きいことを示す第１大小判定手段の判定結果に応答して該当するレンダリング球を除去するレンダリング球除去手段とをさらに有している。
【００１５】
請求項９の高速レンダリング装置は、視野内に少なくとも一部が含まれるレンダリング球について、このレンダリング球に含まれるポリゴンをそれぞれの法線ベクトルの向きに基づいて複数のグループに区分する区分手段と、各区分に属するポリゴンの法線の集合体を円錐で近似する近似手段と、視点からレンダリング球の中心に向かうベクトルを中心としてレンダリング球の広がりを規定する第１広がり角度を算出する第１算出手段と、ポリゴンの法線の集合体を近似する円錐の中心軸を規定する中心軸ベクトルおよびこの円錐の第２広がり角度を算出する第２算出手段と、視点からレンダリング球の中心に向かうベクトルと中心軸ベクトルとのなす角が両広がり角度の和以下であるか否かを判定する第２大小判定手段と、視点からレンダリング球の中心に向かうベクトルと中心軸ベクトルとのなす角が両広がり角度の和以下であることを示す第２大小判定手段の判定結果に応答して該当する区分に属するポリゴンを描画の対象として選択する選択手段とをさらに有している。
【００１６】
請求項１０の高速レンダリング装置は、各レンダリングモデルに対応するポリゴンについて、視点からレンダリング球の中心に向かうベクトルの大きさに対応させて、予め描画精度が異なる複数のポリゴンを生成しておくポリゴン生成手段と、上記ベクトルの実際の大きさに基づいて該当する描画精度のポリゴンを描画する描画手段とをさらに有している。
【００１７】
【作用】
請求項１の高速レンダリング方法であれば、階層球体モデル保持部（１）に保持されている階層球体モデルの、所定の半径以下の球体のうち、最も上位の階層の球体をレンダリング球として指定するとともに、各レンダリング球に対応してレンダリングモデルを割り当てておき、レンダリング球がクリップ領域の内部か外部かを判定して、レンダリング球がクリップ領域の外部である場合に該当するレンダリングモデルをクリップするのであるから、多面性表現を用いた位置関係の計算が不要になり、レンダリング球を用いた干渉計算を行うことによりレンダリングモデルのクリップを高速に達成でき、ひいてはレンダリングを高速化することができる。
【００１８】
請求項２の高速レンダリング方法であれば、モデル化の対象となる物体の表面を、メッシュ分割するとともに、メッシュ分割された各メッシュの全ての辺の長さを予め設定した最下位階層の球の直径以下に設定し、メッシュ分割により発生し、メッシュデータ保持部（４４）により保持した各節点を中心として最下位階層の球体を生成し、次いで、全節点に基づいて定まる立方体領域を含む最小の球体を生成して最上位階層の球体とし、その後、直前の階層の球体の中心を通る平面で全節点を２分割し、分割された各区分に属する全節点に基づいて定まる立方体領域を含む最小の球体を生成して、分割前の階層の次の階層の球体とし、その後、全節点の２分割処理および各区分に属する全節点に基づいて定まる立方体領域を含む最小の球体を生成して次の階層の球体とする処理を、分割後の節点数が１になるまで反復することにより階層球体モデルを作成するのであるから、物体に内包される球体はもともと生成されず、処理の複雑化を伴なうことなく、生成される球体の数を減少させることができ、このように生成された階層球体モデルに基づいて請求項１と同様の作用を達成することができる。
【００１９】
請求項３の高速レンダリング方法であれば、視点位置保持部（１１）に保持されている視点位置を基準として、視線方向ベクトル保持部（１２）に保持されている視線方向ベクトルおよび視野角保持部（１３）に保持されている視野角により視野が規定されている状態において、視点から、レンダリング球中心保持部（１３ａ）に保持されているレンダリング球の中心に向かうベクトルと、このベクトルを中心としてレンダリング球の広がりを規定する角度とを算出し、両ベクトルのなす角が視野角とレンダリング球の広がりを規定する角度との和よりも大きいことを条件として該当するレンダリング球を除去するのであるから、多面性表現を用いた位置関係の計算が不要になり、描画に不要なレンダリング球の除去を円錐対円錐の高速な干渉チェックにより簡単にすることができ、ひいては描画ポリゴンの検出を高速に達成することができる。
【００２０】
請求項４の高速レンダリング方法であれば、視野内に少なくとも一部が含まれるレンダリング球について、このレンダリング球に含まれるポリゴンをそれぞれの法線ベクトルの向きに基づいて複数のグループに区分し、各区分に属するポリゴンの法線の集合体を円錐で近似し、視点から、レンダリング球中心保持部（２１）に保持されているレンダリング球の中心に向かうベクトルを中心としてレンダリング球の広がりを規定する第１広がり角度を算出するとともに、ポリゴンの法線の集合体を近似する円錐の中心軸を規定する中心軸ベクトルおよびこの円錐の第２広がり角度を算出し、視点からレンダリング球の中心に向かうベクトルと中心軸ベクトルとのなす角が両広がり角度の和以下であることを条件として、該当する区分に属するポリゴンを描画の対象として選択するのであるから、多面体表現を用いた位置関係の計算が不要になり、レンダリング球内のポリゴンのうち、描画の対象となるポリゴンの選択を高速に達成でき、ひいてはレンダリングを高速化することができる。
【００２１】
請求項５の高速レンダリング方法であれば、各レンダリングモデルに対応するポリゴンについて、視点からレンダリング球の中心に向かうベクトルの大きさに対応させて、予め描画精度が異なる複数のポリゴンを生成してＬＯＤモデル保持部（３１）に保持しておき、上記ベクトルの実際の大きさに基づいて該当する描画精度のポリゴンを描画するのであるから、一部のポリゴンについて描画精度が低いポリゴンを採用することにより描画を高速化でき、ひいてはレンダリングを高速化することができる。
【００２２】
請求項６の高速レンダリング装置であれば、階層球体モデルの、所定の半径以下の球体のうち、最も上位の階層の球体をレンダリング球指定手段によりレンダリング球として指定し、レンダリングモデル割り当て手段により、各レンダリング球に対応してレンダリングモデルを割り当てる。そして、内外判定手段により、レンダリング球がクリップ領域の内部か外部かを判定し、レンダリング球がクリップ領域の外部であることを示す内外判定手段の判定結果に応答してクリップ手段により該当するレンダリングモデルをクリップする。したがって、多面体表現を用いた位置関係の計算が不要になり、レンダリング球を用いた干渉計算を行うことによりレンダレングモデルのクリップを高速に達成でき、ひいてはレンダリングを高速化することができる。
【００２３】
請求項７の高速レンダリング装置であれば、モデル化の対象となる物体の表面を、メッシュ分割するとともに、メッシュ分割された各メッシュの全ての辺の長さを予め設定した最下位階層の球の直径以下に設定するメッシュ分割手段と、メッシュ分割により発生した各節点を中心として最下位階層の球体を生成する最下位階層球体生成手段と、全節点に基づいて定まる立方体領域を含む最小の球体を生成して最上位階層の球体とする最上位階層球体生成手段と、処理時点での最上位階層の球体の中心を通る平面で全節点を２分割する分割手段と、分割された各区分に属する全節点に基づいて定まる立方体領域を含む最小の球体を生成して、分割前の階層の次の階層の球体とする中間階層球体生成手段と、分割手段による処理および中間階層球体生成手段による処理を、分割後の節点数が１になるまで反復させる反復制御手段とをさらに有しているのであるから、物体に内包される球体はもともと生成されず、処理の複雑化を伴うことなく、生成される球体の数を減少させることができ、このように生成された階層球体モデルに基づいて請求項６と同様の作用を達成することができる。
【００２４】
請求項８の高速レンダリング装置であれば、視野を規定すべく、視点位置を基準として設定された視線方向ベクトルおよび視野角を保持する保持手段と、視点からレンダリング球の中心に向かうベクトルと、このベクトルを中心としてレンダリング球の広がりを規定する角度とを算出する算出手段と、両ベクトルのなす角が視野角とレンダリング球の広がりを規定する角度との和よりも大きいか否かを判定する第１大小判定手段と、両ベクトルのなす角が視野角とレンダリング球の広がりを規定する角度との和よりも大きいことを示す第１大小判定手段の判定結果に応答して該当するレンダリング球を除去するレンダリング球除去手段とをさらに有しているのであるから、多面体表現を用いた位置関係の計算が不要になり、描画に不要なレンダリング球の除去を円錐対円錐の高速な干渉チェックにより簡単にすることができ、ひいては描画ポリゴンの検出を高速に達成することができる。
【００２５】
請求項９の高速レンダリング装置であれば、視野内に少なくとも一部が含まれるレンダリング球について、このレンダリング球に含まれるポリゴンをそれぞれの法線ベクトルの向きに基づいて複数のグループに区分する区分手段と、各区分に属するポリゴンの法線の集合体を円錐で近似する近似手段と、視点からレンダリング球の中心に向かうベクトルを中心としてレンダリング球の広がりを規定する第１広がり角度を算出する第１算出手段と、ポリゴンの法線の集合体を近似する円錐の中心軸を規定する中心軸ベクトルおよびこの円錐の第２広がり角度を算出する第２算出手段と、視点からレンダリング球の中心に向かうベクトルと中心軸ベクトルとのなす角が両広がり角度の和以下であるか否かを判定する第２大小判定手段と、視点からレンダリング球の中心に向かうベクトルと中心軸ベクトルとのなす角が両広がり角度の和以下であることを示す第２大小判定手段の判定結果に応答して該当する区分に属するポリゴンを描画の対象として選択する選択手段とをさらに有しているのであるから、多面体表現を用いた位置関係の計算が不要になり、レンダリング球内のポリゴンのうち、描画の対象となるポリゴンの選択を高速に達成でき、ひいてはレンダリングを高速化することができる。
【００２６】
請求項１０の高速レンダリング装置であれば、各レンダリングモデルに対応するポリゴンについて、視点からレンダリング球の中心に向かうベクトルの大きさに対応させて、予め描画精度が異なる複数のポリゴンを生成しておくポリゴン生成手段と、上記ベクトルの実際の大きさに基づいて該当する描画精度のポリゴンを描画する描画手段とをさらに有しているのであるから、一部のポリゴンについて描画精度が低いポリゴンを採用することにより描画を高速化でき、ひいてはレンダリングを高速化することができる。
【００２７】
【実施例】
以下、実施例を示す添付図面によってこの発明を詳細に説明する。
図１は階層球体モデルとレンダリングモデルとの関係を示す概略図である。
図において、階層球体モデルを構成する各階層の球体をサイズが異なる楕円で示している。また、この階層球体モデルは、最上位階層の球体から順に分割処理を行うことにより作成されるのであるが、この場合に、予め指定した値以下の半径の球体Ｓ１，Ｓ２，Ｓ３が生成された場合に、この球体Ｓ１，Ｓ２，Ｓ３をレンダリング球に設定し、それぞれレンダリングモデルＬ１，Ｌ２，Ｌ３と対応付ける。ただし、予め指定した値以下の半径の球体のうち、最も上位階層の球体のみをレンダリング球に設定する。したがって、レンダリング球よりも下位の階層の球体はレンダリング球ではない。また、レンダリング球の半径が最下位階層の球体の半径よりも十分に大きくなるように、上記値を指定する。さらに、レンダリングモデルＬ１，Ｌ２，Ｌ３は、対応するレンダリング球に包含されるポリゴンなどの形状情報を含むモデルである。
【００２８】
上述のようにレンダリング球とレンダリングモデルとの対応付けを行った場合に、レンダリング球とレンダリングモデルとが１対１で対応しない場合がある。このような場合は、図２に示すように、レンダリングモデルを１対１対応部分Ｌ１´，Ｌ２´と多対１対応部分Ｌ１２´とに分離し、新たなレンダリングモデルを生成する。図２の場合に対応する元のレンダリングモデルＬ１，Ｌ２と新たなレンダリングモデルＬ１´，Ｌ２´，Ｌ１２´との関係は、図３に示すとおりである。
【００２９】
したがって、このようにレンダリング球を設定するとともに、各レンダリング球に対してレンダリングモデルを対応付けておけば、各レンダリング球がクリップ領域の内部か外部かの判定を行い、クリップ領域の外部であると判定されたレンダリング球のみをクリップすることにより、レンダリングモデルのクリップ処理を簡単に達成することができる。
【００３０】
上記レンダリングモデルのクリップ処理は、例えば、図４のフローチャートに示すように、ステップＳＰ１においてレンダリング球を設定し、ステップＳＰ２において各レンダリング球にレンダリングモデルを対応付けし、ステップＳＰ３において、各レンダリング球について、設定されたクリップ領域の内部か外部かの判定を行い、レンダリング球がクリップ領域の外部であると判定された場合には、ステップＳＰ４において、該当するレンダリング球をクリップし、ステップＳＰ５において全てのレンダリング球に対する処理が行われたか否かを判定し、処理が行われていないレンダリング球が存在している場合には、再びステップＳＰ３の処理を行う。逆に、ステップＳＰ５において全てのレンダリング球に対する処理が行われたと判定された場合には、そのまま一連の処理を終了する。また、ステップＳＰ３においてレンダリング球がクリップ領域の内部であると判定された場合には、再びステップＳＰ３の処理を行う。
【００３１】
したがって、階層球体モデルのうち、レンダリング球として設定された球体のみに基づいてクリップ領域に対する内外判定を行い、クリップ領域の外部であると判定されたレンダリング球に対応するレンダリングモデルのクリップ処理を行うことができ、レンダリングモデルをクリップするための処理を著しく簡単化できる。この結果、レンダリングを高速化することができる。
【００３２】
ただし、クリップされなかったレンダリング球であっても、レンダリングモデルを構成する全てのポリゴンなどがクリップ領域の内部であるとは限らない。したがって、この場合には、例えば、クリップされなかったレンダリング球に対応するレンダリングモデルを構成するポリゴンなどについてクリップ処理を行うことが可能であるが、後述する、法線ベクトルによるグルーピング方法を採用することが好ましい。
【００３３】
図５は円錐で近似された視野とレンダリング球との関係を示す概略図である。
図において、視点位置がＯ＝（Ｘ０，Ｙ０，Ｚ０）、視線方向ベクトルがＶ１＝（Ｘ１，Ｙ１，Ｚ１）、視野角がθ１、レンダリング球の中心がＣ＝（Ｘｃ，Ｙｃ，Ｚｃ）、レンダリング球の半径がｒ、視点を始点としレンダリング球の中心を終点とするレンダリング球ベクトルがＶ２＝（Ｘ２，Ｙ２，Ｚ２）、両ベクトルのなす角がφにそれぞれ設定されている。
【００３４】
この場合には、レンダリング球の広がりを示す角度が数１になる。また、上記角φは数２になる。
【００３５】
【数１】
0003724006.tif 000003
【００３６】
【数２】
0003724006.tif 000004
【００３７】
したがって、角φと、角度θ１，θ２の和との大小を判定し、φ≦θ１＋θ２の場合にレンダリング球が視野内であり、φ＞θ１＋θ２の場合にレンダリング球が視野外であると判定する。
この判定は、レンダリング球の全てについて行ってもよいが、好ましくは、最上位階層の球体から順にレンダリング球まで上記の判定を行い、視野外であると判定された上位球体から発生したレンダリング球について上記の判定を省略することが好ましい。そして、以上の判定の結果、視野外にあると判定されたレンダリング球を除去し、視野内にあると判定されたレンダリング球に対応するレンダリングモデルのポリゴンのみを描画の対象とすることにより、レンダリングの高速化を達成することができる。
【００３８】
以上には、視野を円錐で近似した場合について説明したが、視野（ビューボリューム）を表示管面に合せて四角錐台領域として規定した状態において、四角錐台領域の４つの側面のそれぞれと球体の中心との距離を計算し、距離と球体の半径との大小を判定することにより視野の内部か外部かを判定するようにしてもよい。
【００３９】
上記の処理において視野内であると判定されたレンダリングモデルのポリゴンなどを表示するに当って、以下の方法を適用することにより、表示の高速化を達成することができる。
この方法は、視野内のレンダリングモデルのポリゴンなどを法線ベクトルに応じて切り代えるため、予めレンダリング球内のポリゴンなどを法線ベクトルに基づいていくつかのグループに分割し、各グループの法線ベクトルを円錐で近似しておく（図６、図７参照）。
【００４０】
図６は描画されないポリゴンなどの法線ベクトルの範囲を円錐で近似した状態を示す概略図である。なお、ここでＶ２，θ２は図５のそれらと同じである。
この場合に、上記円錐の広がり角度θ３は、θ３＝（π／２）−θ２である。
図７は２つの円錐（１つは図６の円錐と同じ円錐）を示している。図において、新たに付加された円錐の中心ベクトル（円錐の頂点を始点とし、円錐の底面の中心に向かうベクトル）をＶ３＝（Ｘ３，Ｙ３，Ｚ３）、この円錐の広がり角度をα、両ベクトルＶ２，Ｖ３のなす角をβでそれぞれ示している。
【００４１】
この場合には、角βが、数３になる。
【００４２】
【数３】
0003724006.tif 000005
【００４３】
したがって、角θ３と、角度α，βの和との大小を判定し、θ３≦α＋βの場合に、該当する円錐の範囲に対応する法線ベクトルを有するポリゴンなどを描画の対象とし、θ３＞α＋βの場合に、該当する円錐の範囲に対応する法線ベクトルを有するポリゴンなどを描画の対象としない。この処理を採用することにより、視野内にあるレンダリング球内のポリゴンなどのうち、描画の対象とすべきポリゴンなどの抽出を高速に達成することができる。
【００４４】
さらに、表示対象となるポリゴンなどをレベル・オブ・ディテイル（以下、ＬＯＤと略称する）表示（“Ａｄａｐｔｉｖｅ  Ｄｉｓｐｌａｙ  Ａｌｇｏｒｉｔｈｍ  ｆｏｒ  Ｉｎｔｅｒａｃｔｉｖｅ  Ｆｒｍｅ  Ｒａｔｅｓ  ＤｕｒｉｎｇＶｉｓｕａｌｉｚａｔｉｏｎ  ｏｆ  Ｃｏｍｐｌｅｘ  Ｖｉｒｔｕａｌ  Ｅｎｖｉｒｏｎｍｅｎｔｓ”，Ｔｈｏｍａｓ  Ａ．  Ｆｕｎｋｈｏｕｓｅｒ  ａｎｄＣａｒｌｏ  Ｈ．  外１，  ＣＯＭＰＵＴＥＲ  ＧＲＡＰＨＩＣＳ  Ｐｒｏｃｅｅｄｉｎｇｓ，  Ａｎｎｕａｌ  Ｃｏｎｆｅｒｅｎｃｅ  Ｓｅｒｉｅｓ，  １９９３参照）することにより、表示対象となる全てのポリゴンなどの描画および表示の所要時間を短縮することができる。
【００４５】
具体的には、図８に示すように、各レンダリングモデルに対応するポリゴンなどの複数ＬＯＤモデル（ＬＯＤ階層が異なる複数のＬＯＤモデルであり、ＬＤ０，ＬＤ１，ＬＤ２がＬＯＤ階層を示している）を予め作成しておき、図９に示すように、レンダリング球ベクトルＶ２の長さからレンダリング球の半径ｒを減算した値（原点からレンダリング球までの最小距離）の大小に応じて何れかのＬＯＤ階層を選択し、または表示を省略するようにしている。なお、何れのＬＯＤ階層を選択するかを示す閾値は、経験則などに基づいて予め設定しておく。
【００４６】
したがって、この場合には、始点から離れたポリゴンなどを簡略化して表示することができ、レンダリングモデルのより一層の高速表示を達成することができる。
図１０、図１１は階層球体モデル作成方法の一例を説明するフローチャートである。
【００４７】
図１０のフローチャートにおいては、ステップＳＰ１において最下位階層の球体の直径を設定し、ステップＳＰ２においてＤｅｌａｕｎａｙ三角分割法など、従来公知の方法により処理対象となる物体の表面をメッシュ分割し、メッシュ分割により発生した節点群を記憶し、ステップＳＰ３において図１１のフローチャートの処理（球体モデル作成処理）を行い、そのまま一連の処理を終了する。なお、ステップＳＰ２におけるメッシュ分割は、各メッシュの各辺の長さが最下位階層の球体の半径以下になるように設定される。
【００４８】
図１１のフローチャートにおいては、ステップＳＰ１において複数個の節点が存在しているか否かを判定する。そして、節点の数が複数であると判定された場合には、ステップＳＰ２において、該当する全ての節点を基に立方体領域（全節点を含む直方体または立方体）を発生し、立方体領域を内包する最小半径の球体を生成し（図１２中（Ａ）参照）、ステップＳＰ３において、分割により節点群が発生したか否か（即ち、該当する節点群が後述する分割処理により発生させられたものであるか否か）を判定する。そして、節点群が分割により発生したのではないと判定された場合には、ステップＳＰ４において、ステップＳＰ２で生成された最小球を最上位階層の球体として保存する。逆に、節点群が分割により発生したと判定された場合には、ステップＳＰ５において、ステップＳＰ２で生成された最小球を、先に行われた図１１のフローチャートの処理のステップＳＰ４またはステップＳＰ５において保存された最小球の下位の階層の球体として保存する。
【００４９】
ステップＳＰ４またはステップＳＰ５の処理が行われた後は、ステップＳＰ６において、直前に保存された最小球の中心を通り、かつ立方体領域の長手方向を法線とする平面で全節点を２分割し（図１２中（Ｂ）参照）、ステップＳＰ７において、分割された一方の節点群に対して図１１のフローチャートの処理を行い、ステップＳＰ８において、分割された残余の節点群に対して図１１のフローチャートの処理を行い、そのまま元の処理に戻る。
【００５０】
上記ステップＳＰ１において節点の数が１つであると判定された場合には、ステップＳＰ９において、分割により節点群が発生したか否か（即ち、該当する節点群が後述する分割処理により発生させられたものであるか否か）を判定する。そして、節点群が分割により発生したのではないと判定された場合には、ステップＳＰ１０において、最下位階層の球体を、その中心を節点と一致させた状態で保存する。逆に、節点群が分割により発生したと判定された場合には、ステップＳＰ１１において、最下位階層の球体を、その中心を節点と一致させた状態で、かつ先に行われた図１１のフローチャートの処理のステップＳＰ４またはステップＳＰ５において保存された最小球の下位の階層の球体として保存する。ステップＳＰ１０またはステップＳＰ１１の処理が行なわれた後は、そのまま元の処理に戻る。
【００５１】
したがって、最下位階層の球体は、図１３中（Ａ）に示すように物体の表面のメッシュ分割が行われた場合において、例えば、物体の表面の１辺に対して図１３中（Ｂ）に示すように配置される。したがって、最下位階層の球体により表現される物体形状の誤差は最下位階層の球体の半径以下になる。
また、最下位階層以外の階層の球体は、その上位の階層の球体の中心を通り、かつ立方体領域の長手方向を法線とする平面で節点群を２分割し、各区分に属する全ての節点に基づいて定まる立方体領域を含む最小半径の球体として生成されるのであるから、球体の生成処理を簡単化できる。
さらに、物体表面のみを対象として球体を生成するのであるから、物体に内包される球体はもともと生成されない。したがって、無駄な球体を削除する処理が不要であり、しかも無駄な球体が生成されないので、球体の数を少なくすることができる。
【００５２】
なお、階層の数は、最下位階層の球体の直径および対象となる物体のサイズ、形状により自動的に定まる。
ただし、図１１のフローチャートにおいて、全ての節点に基づいて定まる立方体領域を含む最小半径の球体を生成する処理に代えて、全ての節点を含む最小半径の球体を生成する処理を採用することが好ましく、球体内における物体占有率を高めることができる。
【００５３】
また、図１１のフローチャートにおいて、立方体領域の長手方向を法線とする平面に代えて、全節点の最大分散方向を法線とする平面を採用することが好ましく、分割された各節点群を含む球体内における物体占有率が大なる確率を大きくすることができる。
【００５４】
【実施例２】
図１４はこの発明の高速レンダリング装置の一実施例を示すブロック図である。ただし、このブロック図には、レンダリングモデルのクリップ処理を行う部分のみを示している。したがって、他の処理を行う部分については、従来公知の装置または以下に説明する装置を採用することになる。
【００５５】
この装置は、階層球体モデル（階層ごとの球の中心座標値、半径など）を保持する階層球体モデル保持部１と、階層球体モデルを構成する全ての階層の球体の中から、所定の値以下の半径を有する球体であって、かつ最も上位の階層の球体を抽出してレンダリング球に設定するレンダリング球設定部２（レンダリング球指定手段）と、設定された各レンダリング球に対してレンダリングモデルを対応付けるレンダリングモデル対応付け部３（レンダリングモデル割り当て手段）と、クリップ領域を規定するデータを保持するクリップ領域保持部４と、各レンダリング球がクリップ領域の内部か外部かを判定する内外判定部５と、クリップ領域の外部であると判定されたレンダリング球に対応するレンダリングモデルをクリップするクリップ処理部６とを有している。なお、構成各部の動作は図４のフローチャートの該当するステップの処理と同様であるから詳細な説明は省略してある。もちろん、これら構成各部は、ハードウェアで構成されてもよいが、図４に示す処理を行うプログラムが組み込まれたコンピュータで構成することが好ましい。
【００５６】
したがって、階層球体モデルのうち、レンダリング球として設定された球体のみに基づいてクリップ領域に対する内外判定を行い、クリップ領域の外部であると判定されたレンダリング球に対応するレンダリングモデルのクリップ処理を行うことができ、レンダリングモデルをクリップするための処理を著しく簡単化できる。この結果、レンダリングを高速化することができる。
【００５７】
ただし、レンダリングモデル対応付け部３としては、レンダリング球とレンダリングモデルとが１対１に対応しない場合に、オペレータの指示などに基づいてレンダリングモデルを１対１対応部分と多対１対応部分とに分離して新たなレンダリングモデルを作成し、新たなレンダリングモデルに基づいて対応付けを行うものであることが好ましい。
【００５８】
図１５は、視野が円錐で近似されている場合に、レンダリング球が視野の内部か外部かを判定する処理を行なう装置の構成を示すブロック図である。
この装置は、視点位置Ｏ＝（Ｘ０，Ｙ０，Ｚ０）を保持する視点位置保持部１１と、視線方向ベクトルＶ１＝（Ｘ１，Ｙ１，Ｚ１）を保持する視線方向ベクトル保持部１２と、視野角θ１を保持する視野角保持部１３と、レンダリング球の中心Ｃ＝（Ｘｃ，Ｙｃ，Ｚｃ）を保持するレンダリング球中心保持部１３ａと、レンダリング球の半径ｒを保持する半径保持部１４と、視点を始点としレンダリング球の中心を終点とするレンダリング球ベクトルＶ２＝（Ｘ２，Ｙ２，Ｚ２）を算出するレンダリング球ベクトル算出部１５と、数１に基づいてレンダリング球の広がり角度θ２を算出する広がり角度算出部１６と、数２に基づいて両ベクトルのなす角φを算出するベクトル角度算出部１７と、角度φと、角度θ１，θ２の和との大小を判定する大小判定部１８と、φ≦θ１＋θ２の場合にレンダリング球が視野内であり、φ＞θ１＋θ２の場合にレンダリング球が視野外であると判定して該当するレンダリング球を除去する内外判定部１９とを有している。なお、以上の各構成部分による処理は、全てのレンダリング球について反復的に行われる。
【００５９】
したがって、全てのレンダリング球について角度φ、θ２の算出処理、角度φと角度θ１，θ２の和との大小判定を行うことにより、レンダリング球が視野内であるか視野外であるかの判定を行うことができる。ただし、最上位階層の球体から順にレンダリング球まで内外判定を行い、視野外であると判定された上位球体から発生したレンダリング球について上記の判定を省略することが好ましい。この場合には、レンダリング球についての各保持部、各算出部、各判定部による処理を、レンダリング球よりも上位の階層の球体に対して行うようにすればよい。そして、以上の判定の結果、視野外にあると判定されたレンダリング球を除去し、視野内にあると判定されたレンダリング球に対応するレンダリングモデルのポリゴンのみを描画の対象とすることにより、レンダリングの高速化を達成することができる。
【００６０】
図１６はレンダリング球に包含されるポリゴンなどを法線ベクトルに基づいてグルーピングした場合に、各グループのポリゴンなどが描画対象であるか否かを判定するための装置の構成を示すブロック図である。なお、このブロック図においては、グルーピングを行うための処理部、グルーピングされた各区分に属する法線ベクトルの集合体を円錐で近似する処理部を図示していない。これらの処理部は、例えば、オペレータの設定入力値に基づいて必要な処理を行うものであってもよく、この場合には、例えば、設定入力値に円錐の広がり角度、円錐の中心軸を規定する中心軸ベクトルなどが含まれることになる。
【００６１】
この装置は、レンダリング球の中心Ｃ＝（Ｘｃ，Ｙｃ，Ｚｃ）を保持するレンダリング球中心保持部２１と、レンダリング球の半径ｒを保持する半径保持部２２と、視点を始点としレンダリング球の中心を終点とするレンダリング球ベクトルＶ２＝（Ｘ２，Ｙ２，Ｚ２）を算出するレンダリング球ベクトル算出部２３と、数１に基づいてレンダリング球の広がり角度θ２を算出する第１広がり角度算出部２４と、（π／２−θ２）の演算を行って描画されないポリゴンなどの法線ベクトルの範囲を近似する円錐の広がり角度θ３を算出する第２広がり角度算出部２５と、何れかのグループのポリゴンなどの法線ベクトルの範囲を規定する円錐の中心ベクトルＶ３＝（Ｘ３，Ｙ３，Ｚ３）を保持する中心ベクトル保持部２６と、この円錐の広がり角度αを保持する第３広がり角度保持部２７と、数３に基づいて両ベクトルのなす角βを算出するベクトル角度算出部２８と、角度θ３と、角度α，βの和との大小を判定する大小判定部２９と、θ３≦α＋βの場合に対応するポリゴンなどが描画対象であり、θ３＞α＋βの場合に対応するポリゴンなどが描画対象でないと判定する描画判定部３０とを有している。なお、以上の各構成部分による処理は、全ての円錐について反復的に行われる。
【００６２】
したがって、グルーピングされた各グループのポリゴンなどが描画対象であるか否かを簡単かつ高速に判定することができ、ひいてはレンダリングを高速化することができる。
図１７はレンダリングモデルを構成するポリゴンなどをＬＯＤ表示するための装置を示すブロック図である。この装置には、複数のＬＯＤモデルを作成する処理部が示されていないが、この処理部としては、従来公知の装置を採用することができる。
【００６３】
この装置は、各レンダリングモデルごとに、対応するポリゴンについて予め作成されている複数のＬＯＤモデルを保持するＬＯＤモデル保持部３１と、レンダリング球ベクトルＶ２の長さからレンダリング球の半径を減算した値を得る距離算出部３２と、算出された距離と予め設定されている１または２以上の閾値との大小を判定する大小判定部３３と、大小判定部３３による大小判定結果に応答してＬＯＤモデル保持部から該当するＬＯＤ階層のＬＯＤモデルを選択するＬＯＤモデル選択部３４と、選択されたＬＯＤモデルに基づく表示を行う表示部３５とを有している。
【００６４】
したがって、ポリゴンなどの表示に当って、簡略化されたＬＯＤモデルを選択することにより、レンダリングモデルの表示を高速化することができる。レンダリングモデルでは、遠景に多数のポリゴンなどが含まれており、これらを簡略化表示できるのであるから、著しい高速化を達成することができる。
図１８は階層構造球体モデル作成装置の一例を示すブロック図である。
【００６５】
この階層構造球体モデル作成装置は、対象物体の形状データを保持する形状データ保持部４１と、最下位階層の球体の直径の設定値を保持する直径保持部４２と、対象物体の形状データおよび最下位階層の球体の直径を入力として、従来公知の方法により対象物体の表面をメッシュ分割し、各メッシュの各辺の長さを上記直径以下に設定するメッシュ分割部４３と、メッシュ分割により得られた節点群を保持する（例えば、各節点の座標値などを保持する）メッシュデータ保持部４４と、全ての節点に基づいて定まる立方体領域を含む最小の球体を生成し、最上位階層の球体として割当てる最上位階層球体生成部４５と、最も新たに生成され、かつ未処理の球体に含まれる節点の数が複数であることを条件として、この節点群を、この球体の中心を通り、かつ立方体領域の長手方向を法線とする平面で２分割する分割部４６と、分割部４６により分割された各区分に属する節点の数が複数か否かを判定する節点数判定部４７と、節点数が複数であることを条件として、分割部４６により分割された各区分に属する全ての節点に基づいて定まる立方体領域を含む最小の球体を生成し、次の階層の球体として割当てる中間階層球体生成部４８と、節点数が１であることを条件として、該当する節点と中心とを一致させた状態で最下位階層球体を配置する最下位階層球体配置部４９とを有している。
【００６６】
なお、構成各部の作用は図１０、図１１のフローチャートの該当するステップの処理と同様であるから、詳細な説明を省略する。もちろん、これら構成各部は、ハードウェアで構成されてもよいが、図１０、図１１に示す処理を行うプログラムが組み込まれたコンピュータで構成することが好ましい。また、節点数が１になるまで分割部４６による分割処理、中間階層球体生成部４８の処理を反復させる制御部は図示を省略してある。また、２分割された各節点群を保持する保持部も図示を省略してある。
【００６７】
【発明の効果】
請求項１の発明は、多面体表現を用いた位置関係の計算が不要になり、レンダリング球を用いた干渉計算を行うことによりレンダレングモデルのクリップを高速に達成でき、ひいてはレンダリングを高速化することができるという特有の効果を奏する。
【００６８】
請求項２の発明は、物体に内包される球体はもともと生成されず、処理の複雑化を伴なうことなく、生成される球体の数を減少させることができ、このように生成された階層球体モデルに基づいて請求項１と同様の効果を奏する。
請求項３の発明は、多面体表現を用いた位置関係の計算が不要になり、描画に不要なレンダリング球の除去を円錐対円錐の高速な干渉チェックにより簡単にすることができ、ひいては描画ポリゴンの検出を高速に達成することができるという特有の効果を奏する。
【００６９】
請求項４の発明は、多面体表現を用いた位置関係の計算が不要になり、レンダリング球内のポリゴンのうち、描画の対象となるポリゴンの選択を高速に達成でき、ひいてはレンダリングを高速化することができるという特有の効果を奏する。
請求項５の発明は、一部のポリゴンについて描画精度が低いポリゴンを採用することにより描画を高速化でき、ひいてはレンダリングを高速化することができるという特有の効果を奏する。
【００７０】
請求項６の発明は、多面体表現を用いた位置関係の計算が不要になり、レンダリング球を用いた干渉計算を行うことによりレンダリングモデルのクリップを高速に達成でき、ひいてはレンダリングを高速化することができるという特有の効果を奏する。
請求項７の発明は、物体に内包される球体はもともと生成されず、処理の複雑化を伴うことなく、生成される球体の数を減少させることができ、このように生成された階層球体モデルに基づいて請求項６と同様の効果を奏する。
【００７１】
請求項８の発明は、多面体表現を用いた位置関係の計算が不要になり、描画に不要なレンダリング球の除去を円錐対円錐の高速な干渉チェックにより簡単にすることができ、ひいては描画ポリゴンの検出を高速に達成することができるという特有の効果を奏する。
請求項９の発明は、多面体表現を用いた位置関係の計算が不要になり、レンダリング球内のポリゴンのうち、描画の対象となるポリゴンの選択を高速に達成でき、ひいてはレンダリングを高速化することができるという特有の効果を奏する。
【００７２】
請求項１０の発明は、一部のポリゴンについて描画精度が低いポリゴンを採用することにより描画を高速化でき、ひいてはレンダリングを高速化することができるという特有の効果を奏する。
【図面の簡単な説明】
【図１】階層球体モデルとレンダリングモデルとの関係を示す概略図である。
【図２】レンダリング球とレンダリングモデルとが１対１で対応しない場合に、レンダリングモデルを１対１対応部分と多対１対応部分とに分離した状態を説明する概略図である。
【図３】１対１対応部分と多対１対応部分とに分離した状態におけるレンダリングモデルを示す概略図である。
【図４】高速レンダリング方法のうち、レンダリングモデルのクリップ処理を説明するフローチャートである。
【図５】円錐で近似された視野とレンダリング球との関係を示す概略図である。
【図６】描画されないポリゴンなどの法線ベクトルの範囲を円錐で近似した状態を示す概略図である。
【図７】ポリゴンなどの法線ベクトルの範囲を近似する２つの円錐の関係を示す概略図である。
【図８】各レンダリングモデルに対応するポリゴンなどの複数ＬＯＤモデルを示す概略図である。
【図９】ＬＯＤ階層と、レンダリング球ベクトルの長さからレンダリング球の半径を減算した値との関係を示す図である。
【図１０】階層球体モデル作成方法の一例の一部を説明するフローチャートである。
【図１１】階層球体モデル作成方法の一例の残部を説明するフローチャートである。
【図１２】立方体領域を含む最小半径の球体の生成処理、および全節点の２分割処理を説明する概略図である。
【図１３】物体表面のメッシュ分割、および最下位階層の球体の配置を説明する概略図である。
【図１４】この発明の高速レンダリング装置の一実施例を示すブロック図である。
【図１５】レンダリング球が円錐で近似された視野の内部か外部かを判定する装置の構成を示すブロック図である。
【図１６】レンダリング球に包含されるポリゴンなどを法線ベクトルに基づいてグルーピングした場合に、各グループのポリゴンなどが描画対象であるか否かを判定するための装置の構成を示すブロック図である。
【図１７】レンダリングモデルを構成するポリゴンなどをＬＯＤ表示するための装置を示すブロック図である。
【図１８】階層球体モデル作成装置の一例を示すブロック図である。
【符号の説明】
２  レンダリング球設定部    ３  レンダリングモデル対応付け部
５  内外判定部    ６  クリップ処理部
１２  視線方向ベクトル保持部    １３  視野角保持部
１５  レンダリング球ベクトル算出部    １６  広がり角度算出部
１８  大小判定部    １９  内外判定部
２４  第１広がり角度算出部    ２５  第２広がり角度算出部
２６  中心ベクトル保持部    ２７  第３広がり角度保持部
２９  大小判定部    ３０  描画判定部
３１  ＬＯＤモデル保持部    ３２  距離算出部
３３  大小判定部    ３４  ＬＯＤモデル選択部
３５  表示部    ４３  メッシュ分割部
４５  最上位階層球体生成部    ４６  分割部
４８  中間階層球体生成部    ４９  最下位階層球体生成部
【図１】
0003724006.tif 000006
【図２】
0003724006.tif 000007
【図３】
0003724006.tif 000008
【図４】
0003724006.tif 000009
【図５】
0003724006.tif 000010
【図６】
0003724006.tif 000011
【図７】
0003724006.tif 000012
【図８】
0003724006.tif 000013
【図９】
0003724006.tif 000014
【図１０】
0003724006.tif 000015
【図１１】
0003724006.tif 000016
【図１２】
0003724006.tif 000017
【図１３】
0003724006.tif 000018
【図１４】
0003724006.tif 000019
【図１５】
0003724006.tif 000020
【図１６】
0003724006.tif 000021
【図１７】
0003724006.tif 000022
【図１８】
0003724006.tif 000023