(57)【要約】【課題】多数のポリゴンの中から処理対象となるポリゴンを効率的に特定することができる２分木構造を有するデータを生成すること。【解決手段】データ生成システム１０は、正規ポリゴン集合を分割対象ポリゴン集合として設定する第１分割対象設定部１０２と、分割対象ポリゴン集合に含まれる正規ポリゴンＲの頂点に基づいて、複数の補助分割面候補ＡＣを生成する補助分割面候補生成部１０６と、複数の補助分割面候補ＡＣのそれぞれについて、分割対象ポリゴン集合に含まれる正規ポリゴンＲとの位置関係を評価する第１評価部１０８と、第１評価部１０８の評価結果に基づいて、複数の補助分割面候補ＡＣのうち１つの補助分割面候補ＳＡＣを、分割対象ポリゴン集合を分割する分割面ＡＤとして決定する第１決定部１１２と、を含む。【選択図】図５
2011053778.tif 000002
【特許請求の範囲】
【請求項１】
複数の正規ポリゴンを含む正規ポリゴン集合から処理対象となる１つまたは複数の正規ポリゴンを特定するための２分木構造を有するデータを生成するためのプログラムであって、
前記正規ポリゴン集合を分割対象ポリゴン集合として設定する第１分割対象設定ステップと、
前記分割対象ポリゴン集合に含まれる正規ポリゴンの頂点に基づいて、複数の補助分割面候補を生成する補助分割面候補生成ステップと、
前記複数の補助分割面候補のそれぞれについて、前記分割対象ポリゴン集合に含まれる正規ポリゴンとの位置関係を評価する第１評価ステップと、
前記第１評価ステップの評価結果に基づいて、前記複数の補助分割面候補のうち１つの補助分割面候補を、前記分割対象ポリゴン集合を分割する分割面として決定する第１決定ステップと、
をコンピューターに更に実行させることを特徴とするプログラム。
【請求項２】
請求項１において、
前記複数の補助分割面候補から決定される前記分割面に、前記処理対象としないことを示す除外フラグを設定する除外フラグ設定ステップをコンピューターに更に実行させることを特徴とするプログラム。
【請求項３】
請求項１または２において、
前記補助分割面候補生成ステップでは、
前記分割対象ポリゴン集合に含まれる正規ポリゴンの頂点に基づいて前記分割対象ポリゴン集合を含む３次元領域を求め、前記３次元領域の重心に基づいて前記複数の補助分割面候補を生成することを特徴とするプログラム。
【請求項４】
請求項１〜３のいずれかにおいて、
前記補助分割面候補生成ステップでは、
前記分割対象ポリゴン集合に含まれる正規ポリゴンの頂点の代表点を求め、前記代表点に基づいて前記複数の補助分割面候補を生成することを特徴とするプログラム。
【請求項５】
請求項１〜４のいずれかにおいて、
前記第１評価ステップでは、
前記分割対象ポリゴン集合に含まれる複数の正規ポリゴンのうち、前記複数の補助分割面候補のうちの１つの補助分割面候補に含まれる正規ポリゴンの数、および前記１つの補助分割面候補と交差する正規ポリゴンの数、および前記１つの補助分割面候補の一方側に存在する正規ポリゴンの数の少なくとも１つに基づいて前記１つの補助分割面候補を評価する処理を、前記複数の補助分割面候補のそれぞれについて行うことを特徴とするプログラム。
【請求項６】
請求項１〜５のいずれかにおいて、
前記第１評価ステップの評価結果が所定条件を満たさない場合に、
前記分割対象ポリゴン集合に含まれる複数の正規ポリゴンのそれぞれを含む面である複数の正規分割面候補を生成する正規分割面候補生成ステップと、
前記複数の正規分割面候補のそれぞれについて、前記分割対象ポリゴン集合に含まれる正規ポリゴンとの位置関係を評価する第２評価ステップと、
前記第２評価ステップの評価結果に基づいて、前記第２評価ステップの評価結果に応じた１つの正規分割面候補を前記分割面として決定する第２決定ステップと、
をコンピューターに更に実行させ、
前記第１決定ステップでは、
前記第１評価ステップの評価結果が所定条件を満たす場合に、前記１つの補助分割面候補を前記分割面として決定することを特徴とするプログラム。
【請求項７】
請求項６において、
前記第１評価ステップの評価結果が前記所定条件を満たさない場合に、
前記第１評価ステップの評価結果と前記第２評価ステップの評価結果とを比較する比較ステップと、
をコンピューターに更に実行させ、
前記第２決定ステップでは、
前記比較ステップの比較結果に基づいて、前記第１評価ステップの評価結果に応じた１つの補助分割面候補または前記第２評価ステップの評価結果に応じた１つの正規分割面候補を前記分割面として決定することを特徴とするプログラム。
【請求項８】
請求項６または７において、
前記第２評価ステップでは、
前記分割対象ポリゴン集合に含まれる複数の正規ポリゴンのうち、前記複数の正規分割面候補のうちの１つの正規分割面候補に含まれる正規ポリゴンの数、および前記１つの正規分割面候補と交差する正規ポリゴンの数、および前記１つの正規分割面候補の一方側に存在する正規ポリゴンの数の少なくとも１つに基づいて前記１つの正規分割面候補を評価する処理を、前記複数の正規分割面候補のそれぞれについて行うことを特徴とするプログラム。
【請求項９】
請求項７または８において、
前記第１評価ステップでは、
前記分割対象ポリゴン集合に含まれる複数の正規ポリゴンのうち、前記複数の補助分割面候補のうちの１つの補助分割面候補に含まれる正規ポリゴンの数、および前記１つの補助分割面候補と交差する正規ポリゴンの数、および前記１つの補助分割面候補の一方側に存在する正規ポリゴンの数の少なくとも１つに基づいて前記１つの補助分割面候補について第１評価値を求める処理を、前記複数の補助分割面候補のそれぞれについて行うステップと、
前記第１評価値に基づいて、前記複数の補助分割面候補から１つの補助分割面候補を選択補助分割面候補として選択し、前記選択補助分割面候補と交差する正規ポリゴンの数および前記選択補助分割面候補の一方側に存在する正規ポリゴンの数に基づいて、前記選択補助分割面候補について第２評価値を求める処理を行うステップと、
をコンピューターに更に実行させ、
前記第１決定ステップでは、
前記第２評価値が前記所定条件を満たす場合に、前記選択補助分割面候補を前記分割面として決定し、
前記第２評価ステップでは、
前記第２評価値が前記所定条件を満たさない場合に、前記分割対象ポリゴン集合に含まれる複数の正規ポリゴンのうち、前記複数の正規分割面候補のうちの１つの正規分割面候補に含まれる正規ポリゴンの数、および前記１つの正規分割面候補と交差する正規ポリゴンの数、および前記１つの正規分割面候補の一方側に存在する正規ポリゴンの数の少なくとも１つに基づいて前記１つの正規分割面候補について第３評価値を求める処理を、前記複数の正規分割面候補のそれぞれについて行うステップと、
前記第３評価値に基づいて、前記複数の正規分割面候補から１つの正規分割面候補を選択正規分割面候補として選択し、前記選択正規分割面候補と交差する正規ポリゴンの数および前記選択正規分割面候補の一方側に存在する正規ポリゴンの数に基づいて、前記選択正規分割面候補について第４評価値を求める処理を行うステップと、
をコンピューターに更に実行させ、
前記比較ステップでは、
前記第２評価値と前記第４評価値とを比較し、
前記第２決定ステップでは、
前記比較ステップの比較結果に基づいて、前記選択補助分割面候補または前記選択正規分割面候補を前記分割面として決定することを特徴とするプログラム。
【請求項１０】
請求項１〜９のいずれかにおいて、
前記分割対象ポリゴン集合に含まれる正規ポリゴンの数が所定数以上である場合に、
前記補助分割面候補生成ステップと前記第１評価ステップと前記第１決定ステップとをコンピューターに実行させ、
前記分割対象ポリゴン集合に含まれる正規ポリゴンの数が所定数以上でない場合に、
前記分割対象ポリゴン集合に含まれる複数の正規ポリゴンのそれぞれを含む面である複数の正規分割面候補を生成する正規分割面候補生成ステップと、
前記複数の正規分割面候補のそれぞれについて、前記分割対象ポリゴン集合に含まれる正規ポリゴンとの位置関係を評価する第２評価ステップと、
前記第２評価ステップの評価結果に基づいて、前記複数の正規分割面候補のうち１つの正規分割面候補を前記分割面として決定する第２決定ステップと、
をコンピューターに更に実行させることを特徴とするプログラム。
【請求項１１】
複数の正規ポリゴンを含む正規ポリゴン集合から処理対象となる１つまたは複数の正規ポリゴンを特定するための２分木構造を有するデータを生成するためのプログラムであって、
前記正規ポリゴン集合を分割対象ポリゴン集合として設定する初期分割対象設定ステップと、
前記分割対象ポリゴン集合に含まれる複数の正規ポリゴンのそれぞれを含む面である複数の正規分割面候補を生成する正規分割面候補生成ステップと、
前記複数の正規分割面候補のそれぞれについて、前記分割対象ポリゴン集合に含まれる正規ポリゴンとの位置関係を評価する第２評価ステップと、
前記第２評価ステップの評価結果に基づいて、前記複数の正規分割面候補のうち１つの正規分割面候補を前記分割面として決定する第２決定ステップと、
をコンピューターに更に実行させることを特徴とするプログラム。
【請求項１２】
複数の正規ポリゴンを含む正規ポリゴン集合から処理対象となる１つまたは複数の正規ポリゴンを特定するための２分木構造を有するデータを生成するためのデータ生成システムであって、
前記正規ポリゴン集合を分割対象ポリゴン集合として設定する第１分割対象設定部と、
前記分割対象ポリゴン集合に含まれる正規ポリゴンの頂点に基づいて、複数の補助分割面候補を生成する補助分割面候補生成部と、
前記複数の補助分割面候補のそれぞれについて、前記分割対象ポリゴン集合に含まれる正規ポリゴンとの位置関係を評価する第１評価部と、
前記第１評価部の評価結果に基づいて、前記複数の補助分割面候補のうち１つの補助分割面候補を、前記分割対象ポリゴン集合を分割する分割面として決定する第１決定部と、
を含むことを特徴とするデータ生成システム。
【請求項１３】
複数の正規ポリゴンを含む正規ポリゴン集合から処理対象となる１つまたは複数の正規ポリゴンを特定するための２分木構造を有するデータを生成するデータ生成方法であって、
前記正規ポリゴン集合を分割対象ポリゴン集合として設定する第１分割対象設定ステップと、
前記分割対象ポリゴン集合に含まれる正規ポリゴンの頂点に基づいて、複数の補助分割面候補を生成する補助分割面候補生成ステップと、
前記複数の補助分割面候補のそれぞれについて、前記分割対象ポリゴン集合に含まれる正規ポリゴンとの位置関係を評価する第１評価ステップと、
前記第１評価ステップの評価結果に基づいて、前記複数の補助分割面候補のうち１つの補助分割面候補を、前記分割対象ポリゴン集合を分割する分割面として決定する第１決定ステップと、
を含むことを特徴とするデータ生成方法。
【請求項１４】
複数の正規ポリゴンを含む正規ポリゴン集合から処理対象となる１つまたは複数の正規ポリゴンを特定するための２分木構造を有するデータであって、
前記正規ポリゴン集合を分割対象ポリゴン集合として設定する第１分割対象設定ステップと、
前記分割対象ポリゴン集合に含まれる正規ポリゴンの頂点に基づいて、複数の補助分割面候補を生成する補助分割面候補生成ステップと、
前記複数の補助分割面候補のそれぞれについて、前記分割対象ポリゴン集合に含まれる正規ポリゴンとの位置関係を評価する第１評価ステップと、
前記第１評価ステップの評価結果に基づいて、前記複数の補助分割面候補のうち１つの補助分割面候補を、前記分割対象ポリゴン集合を分割する分割面として決定する第１決定ステップと、
を含むデータ生成方法により生成されたデータが記憶されたことを特徴とするコンピューターが読み取り可能な情報記憶媒体。
【請求項１５】
複数の正規ポリゴンを含む正規ポリゴン集合から処理対象となる１つまたは複数の正規ポリゴンを特定するための２分木構造を有するデータのデータ構造であって、
前記正規ポリゴン集合を分割対象ポリゴン集合として設定する第１分割対象設定ステップと、
前記分割対象ポリゴン集合に含まれる正規ポリゴンの頂点に基づいて、複数の補助分割面候補を生成する補助分割面候補生成ステップと、
前記複数の補助分割面候補のそれぞれについて、前記分割対象ポリゴン集合に含まれる正規ポリゴンとの位置関係を評価する第１評価ステップと、
前記第１評価ステップの評価結果に基づいて、前記複数の補助分割面候補のうち１つの補助分割面候補を、前記分割対象ポリゴン集合を分割する分割面として決定する第１決定ステップと、
を含むデータ生成方法により生成されたデータのデータ構造。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、プログラム、データ生成システム、データ生成方法、情報記憶媒体およびデータ構造に関する。
【背景技術】
【０００２】
従来から、仮想的な３次元空間であるオブジェクト空間を仮想カメラ（所与の視点）から見た画像を生成する画像生成システム（ゲームシステム）が知られており、いわゆる仮想現実を体験できるものとして人気が高い。そしてこのような画像生成システムでは、フレームが更新される毎にオブジェクト空間に配置されるオブジェクトを構成するポリゴンについて描画処理や交差判定処理（衝突判定処理、接触判定処理）を行うが、各フレームにおいて処理対象となるポリゴンは、オブジェクト空間に配置される多数のポリゴンのうち一部のポリゴンであることが多い。そこで、オブジェクト空間に配置される多数のポリゴンについて２分木構造の一種であるＢＳＰ木（Binary Space-Partitioning tree）構造を有するデータを生成し、これにより多数のポリゴンの中から処理対象となるポリゴンを効率的に特定しようとする画像生成システムが知られている（特許文献１）。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００２−２６９５８８号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかし、オブジェクト空間においてポリゴンは様々な態様で分布するため、従来の手法では、多数のポリゴンの中から処理対象となるポリゴンを効率的に特定することができない２分木構造を有するデータが生成されてしまうことがあった。
【０００５】
本発明は、このような事情に鑑みてなされたものであり、多数のポリゴンの中から処理対象となるポリゴンを効率的に特定することができる２分木構造を有するデータを生成することができるプログラム、データ生成システム、データ生成方法、情報記憶媒体およびデータ構造を提供することを目的とする。
【課題を解決するための手段】
【０００６】
（１）本発明は、
複数の正規ポリゴンを含む正規ポリゴン集合から処理対象となる１つまたは複数の正規ポリゴンを特定するための２分木構造を有するデータを生成するためのプログラムであって、
前記正規ポリゴン集合を分割対象ポリゴン集合として設定する第１分割対象設定ステップと、
前記分割対象ポリゴン集合に含まれる正規ポリゴンの頂点に基づいて、複数の補助分割面候補を生成する補助分割面候補生成ステップと、
前記複数の補助分割面候補のそれぞれについて、前記分割対象ポリゴン集合に含まれる正規ポリゴンとの位置関係を評価する第１評価ステップと、
前記第１評価ステップの評価結果に基づいて、前記複数の補助分割面候補のうち１つの補助分割面候補を、前記分割対象ポリゴン集合を分割する分割面として決定する第１決定ステップと、
をコンピューターに更に実行させることを特徴とするプログラムに関係する。
【０００７】
また本発明は、
複数の正規ポリゴンを含む正規ポリゴン集合から処理対象となる１つまたは複数の正規ポリゴンを特定するための２分木構造を有するデータを生成するためのデータ生成システムであって、
前記正規ポリゴン集合を分割対象ポリゴン集合として設定する第１分割対象設定部と、
前記分割対象ポリゴン集合に含まれる正規ポリゴンの頂点に基づいて、複数の補助分割面候補を生成する補助分割面候補生成部と、
前記複数の補助分割面候補のそれぞれについて、前記分割対象ポリゴン集合に含まれる正規ポリゴンとの位置関係を評価する第１評価部と、
前記第１評価部の評価結果に基づいて、前記複数の補助分割面候補のうち１つの補助分割面候補を、前記分割対象ポリゴン集合を分割する分割面として決定する第１決定部と、
を含むことを特徴とするデータ生成システムに関係する。
【０００８】
また本発明は、
複数の正規ポリゴンを含む正規ポリゴン集合から処理対象となる１つまたは複数の正規ポリゴンを特定するための２分木構造を有するデータを生成するデータ生成方法であって、
前記正規ポリゴン集合を分割対象ポリゴン集合として設定する第１分割対象設定ステップと、
前記分割対象ポリゴン集合に含まれる正規ポリゴンの頂点に基づいて、複数の補助分割面候補を生成する補助分割面候補生成ステップと、
前記複数の補助分割面候補のそれぞれについて、前記分割対象ポリゴン集合に含まれる正規ポリゴンとの位置関係を評価する第１評価ステップと、
前記第１評価ステップの評価結果に基づいて、前記複数の補助分割面候補のうち１つの補助分割面候補を、前記分割対象ポリゴン集合を分割する分割面として決定する第１決定ステップと、
を含むことを特徴とするデータ生成方法に関係する。
【０００９】
また本発明は、
複数の正規ポリゴンを含む正規ポリゴン集合から処理対象となる１つまたは複数の正規ポリゴンを特定するための２分木構造を有するデータであって、
前記正規ポリゴン集合を分割対象ポリゴン集合として設定する第１分割対象設定ステップと、
前記分割対象ポリゴン集合に含まれる正規ポリゴンの頂点に基づいて、複数の補助分割面候補を生成する補助分割面候補生成ステップと、
前記複数の補助分割面候補のそれぞれについて、前記分割対象ポリゴン集合に含まれる正規ポリゴンとの位置関係を評価する第１評価ステップと、
前記第１評価ステップの評価結果に基づいて、前記複数の補助分割面候補のうち１つの補助分割面候補を、前記分割対象ポリゴン集合を分割する分割面として決定する第１決定ステップと、
を含むデータ生成方法により生成されたデータが記憶されたことを特徴とするコンピューターが読み取り可能な情報記憶媒体に関係する。
【００１０】
また本発明は、
複数の正規ポリゴンを含む正規ポリゴン集合から処理対象となる１つまたは複数の正規ポリゴンを特定するための２分木構造を有するデータのデータ構造であって、
前記正規ポリゴン集合を分割対象ポリゴン集合として設定する第１分割対象設定ステップと、
前記分割対象ポリゴン集合に含まれる正規ポリゴンの頂点に基づいて、複数の補助分割面候補を生成する補助分割面候補生成ステップと、
前記複数の補助分割面候補のそれぞれについて、前記分割対象ポリゴン集合に含まれる正規ポリゴンとの位置関係を評価する第１評価ステップと、
前記第１評価ステップの評価結果に基づいて、前記複数の補助分割面候補のうち１つの補助分割面候補を、前記分割対象ポリゴン集合を分割する分割面として決定する第１決定ステップと、
を含むデータ生成方法により生成されたデータのデータ構造に関係する。
【００１１】
本発明によれば、複数の補助分割面候補のそれぞれについて正規ポリゴンとの位置関係が評価されるので、正規ポリゴンの分布に応じた補助分割面候補が分割面として決定される。これにより本発明によれば、処理対象となるポリゴンを効率的に特定することができる２分木構造を有するデータを、少ない処理負荷で生成することができる。
【００１２】
（２）また本発明は、
前記複数の補助分割面候補から決定される前記分割面に、前記処理対象としないことを示す除外フラグを設定する除外フラグ設定ステップをコンピューターに更に実行させるようにしてもよい。
【００１３】
本発明では、複数の補助分割面候補から決定される分割面に結果的に除外フラグが設定されるように除外フラグが設定されればよく、複数の補助分割面候補のそれぞれに除外フラグが設定されるようにしてもよいし、複数の補助分割面候補のうち１つの補助分割面候補に除外フラグが設定されるようにしてもよいし、複数の補助分割面候補から決定された分割面に除外フラグが設定されるようにしてもよい。
【００１４】
このようにすれば、複数の補助分割面候補から決定される分割面により分割対象ポリゴン集合を分割しても、分割面を正規ポリゴンと区別して分割面を交差判定処理などの処理対象としないようにすることができる。
【００１５】
（３）また本発明は、
前記補助分割面候補生成ステップでは、
前記分割対象ポリゴン集合に含まれる正規ポリゴンの頂点に基づいて前記分割対象ポリゴン集合を含む３次元領域を求め、前記３次元領域の重心に基づいて前記複数の補助分割面候補を生成するようにしてもよい。
【００１６】
このようにすれば、分割対象ポリゴン集合を含む３次元領域を均等に分割する補助分割面候補を生成することができる。
【００１７】
（４）また本発明は、
前記補助分割面候補生成ステップでは、
前記分割対象ポリゴン集合に含まれる正規ポリゴンの頂点の代表点を求め、前記代表点に基づいて前記複数の補助分割面候補を生成するようにしてもよい。
【００１８】
このようにすれば、分割対象ポリゴン集合に含まれる正規ポリゴンの分布の偏りに応じた補助分割面候補を生成することができる。
【００１９】
（５）また本発明は、
前記第１評価ステップでは、
前記分割対象ポリゴン集合に含まれる複数の正規ポリゴンのうち、前記複数の補助分割面候補のうちの１つの補助分割面候補に含まれる正規ポリゴンの数、および前記１つの補助分割面候補と交差する正規ポリゴンの数、および前記１つの補助分割面候補の一方側に存在する正規ポリゴンの数の少なくとも１つに基づいて前記１つの補助分割面候補を評価する処理を、前記複数の補助分割面候補のそれぞれについて行うようにしてもよい。
【００２０】
このようにすれば、分割対象ポリゴン集合を分割することによる正規ポリゴンの数の増加を可及的に抑制する補助分割面候補、あるいは分割対象ポリゴン集合を分割した２つの分割後ポリゴン集合のそれぞれに含まれる正規ポリゴンの数の偏りを可及的に抑制する補助分割面候補を分割面として決定することができる。
【００２１】
（６）また本発明は、
前記第１評価ステップの評価結果が所定条件を満たさない場合に、
前記分割対象ポリゴン集合に含まれる複数の正規ポリゴンのそれぞれを含む面である複数の正規分割面候補を生成する正規分割面候補生成ステップと、
前記複数の正規分割面候補のそれぞれについて、前記分割対象ポリゴン集合に含まれる正規ポリゴンとの位置関係を評価する第２評価ステップと、
前記第２評価ステップの評価結果に基づいて、前記第２評価ステップの評価結果に応じた１つの正規分割面候補を前記分割面として決定する第２決定ステップと、
をコンピューターに更に実行させ、
前記第１決定ステップでは、
前記第１評価ステップの評価結果が所定条件を満たす場合に、前記１つの補助分割面候補を前記分割面として決定するようにしてもよい。
【００２２】
このようにすれば、補助分割面候補が所定条件を満たさない場合には、正規分割面候補を分割面の候補とすることができる。
【００２３】
（７）また本発明は、
前記第１評価ステップの評価結果が前記所定条件を満たさない場合に、
前記第１評価ステップの評価結果と前記第２評価ステップの評価結果とを比較する比較ステップと、
をコンピューターに更に実行させ、
前記第２決定ステップでは、
前記比較ステップの比較結果に基づいて、前記第１評価ステップの評価結果に応じた１つの補助分割面候補または前記第２評価ステップの評価結果に応じた１つの正規分割面候補を前記分割面として決定するようにしてもよい。
【００２４】
このようにすれば、補助分割面候補と正規分割面候補のうち、分割面としてより有用な方を分割面として決定することができる。
【００２５】
（８）また本発明は、
前記第２評価ステップでは、
前記分割対象ポリゴン集合に含まれる複数の正規ポリゴンのうち、前記複数の正規分割面候補のうちの１つの正規分割面候補に含まれる正規ポリゴンの数、および前記１つの正規分割面候補と交差する正規ポリゴンの数、および前記１つの正規分割面候補の一方側に存在する正規ポリゴンの数の少なくとも１つに基づいて前記１つの正規分割面候補を評価する処理を、前記複数の正規分割面候補のそれぞれについて行うようにしてもよい。
【００２６】
このようにすれば、分割対象ポリゴン集合を分割することによる正規ポリゴンの数の増加を可及的に抑制する正規分割面候補、あるいは分割対象ポリゴン集合を分割した２つの分割後ポリゴン集合のそれぞれに含まれる正規ポリゴンの数の偏りを可及的に抑制する正規分割面候補を分割面として決定することができる。
【００２７】
（９）また本発明は、
前記第１評価ステップでは、
前記分割対象ポリゴン集合に含まれる複数の正規ポリゴンのうち、前記複数の補助分割面候補のうちの１つの補助分割面候補に含まれる正規ポリゴンの数、および前記１つの補助分割面候補と交差する正規ポリゴンの数、および前記１つの補助分割面候補の一方側に存在する正規ポリゴンの数の少なくとも１つに基づいて前記１つの補助分割面候補について第１評価値を求める処理を、前記複数の補助分割面候補のそれぞれについて行うステップと、
前記第１評価値に基づいて、前記複数の補助分割面候補から１つの補助分割面候補を選択補助分割面候補として選択し、前記選択補助分割面候補と交差する正規ポリゴンの数および前記選択補助分割面候補の一方側に存在する正規ポリゴンの数に基づいて、前記選択補助分割面候補について第２評価値を求める処理を行うステップと、
をコンピューターに更に実行させ、
前記第１決定ステップでは、
前記第２評価値が前記所定条件を満たす場合に、前記選択補助分割面候補を前記分割面として決定し、
前記第２評価ステップでは、
前記第２評価値が前記所定条件を満たさない場合に、前記分割対象ポリゴン集合に含まれる複数の正規ポリゴンのうち、前記複数の正規分割面候補のうちの１つの正規分割面候補に含まれる正規ポリゴンの数、および前記１つの正規分割面候補と交差する正規ポリゴンの数、および前記１つの正規分割面候補の一方側に存在する正規ポリゴンの数の少なくとも１つに基づいて前記１つの正規分割面候補について第３評価値を求める処理を、前記複数の正規分割面候補のそれぞれについて行うステップと、
前記第３評価値に基づいて、前記複数の正規分割面候補から１つの正規分割面候補を選択正規分割面候補として選択し、前記選択正規分割面候補と交差する正規ポリゴンの数および前記選択正規分割面候補の一方側に存在する正規ポリゴンの数に基づいて、前記選択正規分割面候補について第４評価値を求める処理を行うステップと、
をコンピューターに更に実行させ、
前記比較ステップでは、
前記第２評価値と前記第４評価値とを比較し、
前記第２決定ステップでは、
前記比較ステップの比較結果に基づいて、前記選択補助分割面候補または前記選択正規分割面候補を前記分割面として決定するようにしてもよい。
【００２８】
このようにすれば、選択補助分割面候補および選択正規分割面候補のうち第２評価値と第４評価値とを比較した場合に分割面としてより有用な方を、分割面として決定することができる。
【００２９】
（１０）また本発明は、
前記分割対象ポリゴン集合に含まれる正規ポリゴンの数が所定数以上である場合に、
前記補助分割面候補生成ステップと前記第１評価ステップと前記第１決定ステップとをコンピューターに実行させ、
前記分割対象ポリゴン集合に含まれる正規ポリゴンの数が所定数以上でない場合に、
前記分割対象ポリゴン集合に含まれる複数の正規ポリゴンのそれぞれを含む面である複数の正規分割面候補を生成する正規分割面候補生成ステップと、
前記複数の正規分割面候補のそれぞれについて、前記分割対象ポリゴン集合に含まれる正規ポリゴンとの位置関係を評価する第２評価ステップと、
前記第２評価ステップの評価結果に基づいて、前記複数の正規分割面候補のうち１つの正規分割面候補を前記分割面として決定する第２決定ステップと、
をコンピューターに更に実行させるようにしてもよい。
【００３０】
このようにすれば、分割対象ポリゴン集合に含まれる正規ポリゴンの数が少ない場合には、正規分割面候補から分割面を決定することができる。
【００３１】
（１１）本発明は、
複数の正規ポリゴンを含む正規ポリゴン集合から処理対象となる１つまたは複数の正規ポリゴンを特定するための２分木構造を有するデータを生成するためのプログラムであって、
前記正規ポリゴン集合を分割対象ポリゴン集合として設定する初期分割対象設定ステップと、
前記分割対象ポリゴン集合に含まれる複数の正規ポリゴンのそれぞれを含む面である複数の正規分割面候補を生成する正規分割面候補生成ステップと、
前記複数の正規分割面候補のそれぞれについて、前記分割対象ポリゴン集合に含まれる正規ポリゴンとの位置関係を評価する第２評価ステップと、
前記第２評価ステップの評価結果に基づいて、前記複数の正規分割面候補のうち１つの正規分割面候補を前記分割面として決定する第２決定ステップと、
をコンピューターに更に実行させることを特徴とするプログラムに関係する。
【００３２】
また本発明は、
複数の正規ポリゴンを含む正規ポリゴン集合から処理対象となる１つまたは複数の正規ポリゴンを特定するための２分木構造を有するデータを生成するためのデータ生成システムであって、
前記正規ポリゴン集合を分割対象ポリゴン集合として設定する初期分割対象設定部と、
前記分割対象ポリゴン集合に含まれる複数の正規ポリゴンのそれぞれを含む面である複数の正規分割面候補を生成する正規分割面候補生成部と、
前記複数の正規分割面候補のそれぞれについて、前記分割対象ポリゴン集合に含まれる正規ポリゴンとの位置関係を評価する第２評価部と、
前記第２評価部の評価結果に基づいて、前記複数の正規分割面候補のうち１つの正規分割面候補を前記分割面として決定する第２決定部と、
を含むことを特徴とするデータ生成システムに関係する。
【００３３】
また本発明は、
複数の正規ポリゴンを含む正規ポリゴン集合から処理対象となる１つまたは複数の正規ポリゴンを特定するための２分木構造を有するデータを生成するデータ生成方法であって、
前記正規ポリゴン集合を分割対象ポリゴン集合として設定する初期分割対象設定ステップと、
前記分割対象ポリゴン集合に含まれる複数の正規ポリゴンのそれぞれを含む面である複数の正規分割面候補を生成する正規分割面候補生成ステップと、
前記複数の正規分割面候補のそれぞれについて、前記分割対象ポリゴン集合に含まれる正規ポリゴンとの位置関係を評価する第２評価ステップと、
前記第２評価ステップの評価結果に基づいて、前記複数の正規分割面候補のうち１つの正規分割面候補を前記分割面として決定する第２決定ステップと、
を含むことを特徴とするデータ生成方法に関係する。
【００３４】
また本発明は、
複数の正規ポリゴンを含む正規ポリゴン集合から処理対象となる１つまたは複数の正規ポリゴンを特定するための２分木構造を有するデータであって、
前記正規ポリゴン集合を分割対象ポリゴン集合として設定する初期分割対象設定ステップと、
前記分割対象ポリゴン集合に含まれる複数の正規ポリゴンのそれぞれを含む面である複数の正規分割面候補を生成する正規分割面候補生成ステップと、
前記複数の正規分割面候補のそれぞれについて、前記分割対象ポリゴン集合に含まれる正規ポリゴンとの位置関係を評価する第２評価ステップと、
前記第２評価ステップの評価結果に基づいて、前記複数の正規分割面候補のうち１つの正規分割面候補を前記分割面として決定する第２決定ステップと、
を含むデータ生成方法により生成されたデータが記憶されたことを特徴とするコンピューターが読み取り可能な情報記憶媒体に関係する。
【００３５】
本発明によれば、複数の正規分割面候補のそれぞれについて正規ポリゴンとの位置関係が評価されるので、正規ポリゴンの分布に応じた正規分割面候補が分割面として決定される。これにより本発明によれば、処理対象となるポリゴンを効率的に特定することができる２分木構造を有するデータを生成することができる。
【図面の簡単な説明】
【００３６】
【図１】従来のデータ生成システムの手法の説明図。
【図２】従来のデータ生成システムにより生成されるデータの説明図。
【図３】本実施形態のデータ生成システムの手法の説明図。
【図４】本実施形態のデータ生成システムの手法の説明図。
【図５】本実施形態のデータ生成システムにより生成されるデータの説明図。
【図６】本実施形態のデータ生成システムの手法の説明図。
【図７】本実施形態のデータ生成システムの手法の説明図。
【図８】本実施形態のデータ生成システムの手法の説明図。
【図９】本実施形態のデータ生成システムの手法の説明図。
【図１０】本実施形態のデータ生成システムの機能ブロック図。
【図１１】本実施形態のデータ生成システムの処理の一例を示すフローチャート図。
【図１２】本実施形態のデータ生成システムの処理の一例を示すフローチャート図。
【図１３】本実施形態のデータ生成システムの処理の一例を示すフローチャート図。
【図１４】本実施形態のデータ生成システムの処理の一例を示すフローチャート図。
【図１５】本実施形態のデータ生成システムの処理の一例を示すフローチャート図。
【発明を実施するための形態】
【００３７】
以下、本実施形態について説明する。なお、以下に説明する本実施形態は、特許請求の範囲に記載された本発明の内容を不当に限定するものではない。また本実施形態で説明される構成の全てが、本発明の必須構成要件であるとは限らない。
【００３８】
１．従来の手法
まず、従来のＢＳＰ木構造を有するデータの生成手法を概説する。ＢＳＰ木構造を有するデータの生成手法では、キャラクタなどの移動体との交差判定処理（処理の一例）の対象となる多数のポリゴンが配置される空間が、第１分割面によって２つに分割されることにより、多数のポリゴンを含むポリゴン集合（分割対象ポリゴン集合の一例）が、第１分割面の一方側に配置される分割後ポリゴン集合と、第１分割面の他方側に配置される分割後ポリゴン集合とに分割される。そして、分割後ポリゴン集合を構成するポリゴンの数が予め決められた数以下とならない場合には、第１分割面の一方側の空間が第２分割面によって２つに分割されることにより、第１分割面の一方側に配置される分割後ポリゴン集合が、第２分割面の一方側に配置される分割後ポリゴン集合と、第２分割面の他方側に配置される分割後ポリゴン集合とに分割される。
【００３９】
同様にして、第１分割面の他方側に配置される分割後ポリゴン集合が、第３分割面の一方側に配置される分割後ポリゴン集合と、第３分割面の他方側に配置される分割後ポリゴン集合とに分割される。ここで分割面を跨ぐポリゴンは、分割面の一方側のポリゴンと他方側のポリゴンとに分割される。そしてこのような処理が繰り返されることにより、多数のポリゴンを含むポリゴン集合が、親子関係を有しつつポリゴン数が予め決められた数以下となる複数の分割後ポリゴン集合に再帰的に分割されたＢＳＰ木構造のデータが生成される。
【００４０】
そして、このようなＢＳＰ木構造のデータが生成されたポリゴン集合とキャラクタなどの移動体との交差判定処理を行う際には、移動体の位置が分割面の一方側か他方側かを判定しながらＢＳＰ木構造のデータを辿ることにより、移動体が存在する領域に対応する分割後ポリゴン集合を特定することができる。そして、このようにして特定した分割後ポリゴン集合に含まれるポリゴンのそれぞれについて移動体との交差判定処理を行うことにより、ポリゴン集合に含まれる全てのポリゴンについて交差判定処理を行う場合と比較して処理負荷を軽減することができる。
【００４１】
図１は、矩形のオブジェクトＯ１〜オブジェクトＯ６を構成する正規ポリゴンＲ１〜正規ポリゴンＲ２４（正規ポリゴン集合の一例）が配置された３次元空間ＳＰを、３次元空間ＳＰのＸＺ平面に投影した図である。図１では、説明を容易にするために、面を構成するポリゴンが線分により表されている。また、以下では説明を容易にするために、３次元空間ＳＰに配置される正規ポリゴンの数が２４個である場合を例に挙げて説明するが、本実施形態の手法は、３次元空間ＳＰに配置される正規ポリゴンの数がより多い場合に適用されることが多い。
【００４２】
図１の例では、まず、正規ポリゴンＲ１〜正規ポリゴンＲ２４が１回目の分割の対象となる分割対象ポリゴン集合として設定される（初期分割対象設定処理の一例）。ここで、オブジェクトＯ１を構成する正規ポリゴンＲ１を含み３次元空間ＳＰを横断する面が、３次元空間ＳＰを２つに分割する１回目の正規分割面ＲＤ１（分割面の一例）として決定されたとする。すなわち３次元空間ＳＰが正規分割面ＲＤ１により分割されたとする。
【００４３】
すると正規分割面ＲＤ１には、正規ポリゴンＲ１の向きを示す法線ベクトルが正規分割面ＲＤ１の法線ベクトルとして設定される。そして正規分割面ＲＤ１よりも図中上側の３次元空間ＳＰが、正規分割面ＲＤ１の表側（一方側の一例）とされ、正規分割面ＲＤ１よりも図中下側の３次元空間ＳＰが、正規分割面ＲＤ１の裏側（他方側の一例）とされる。
【００４４】
すると図１の例では、１回目の分割対象ポリゴン集合であった２４個の正規ポリゴンのうち、正規分割面ＲＤ１に含まれ、かつ正規分割面ＲＤ１と向きが同一の正規ポリゴンＲ１と正規ポリゴンＲ１７の２個の正規ポリゴンが、正規分割面ＲＤ１の表側の分割後ポリゴン集合として設定される。一方、正規ポリゴンＲ１と正規ポリゴンＲ１７以外の２２個の正規ポリゴンが、正規分割面ＲＤ１の裏側の分割後ポリゴン集合として設定される。
【００４５】
図２は、図１の例の３次元空間ＳＰを分割することにより生成されるＢＳＰ木構造を有するデータの一例を示す図である。図１で示したように、３次元空間ＳＰが最初に正規分割面ＲＤ１により分割されると、図２に示すように、正規分割面ＲＤ１がＢＳＰ木構造のルートとして設定される。ここで図２の例では、分割後ポリゴン集合に含まれる正規ポリゴンの数が５個以下となると、その分割後ポリゴン集合が、ＢＳＰ木構造の末端となる外部ノード（リーフ）として設定される。従って、図１で示したように正規分割面ＲＤ１の表側の分割後ポリゴン集合は、それに含まれる正規ポリゴンの数が２個であるので、図２に示すように、正規ポリゴンＲ１と正規ポリゴンＲ１７とが正規分割面ＲＤ１の表側の外部ノードとして設定される。一方、図１で示したように正規分割面ＲＤ１の裏側の分割後ポリゴン集合は、それに含まれる正規ポリゴンの数が２２個であるので、２回目の分割の対象となる分割対象ポリゴン集合として設定される（再分割対象設定処理の一例）。
【００４６】
そして図１に示すように、例えばオブジェクトＯ１を構成する正規ポリゴンＲ２を含む面が、正規分割面ＲＤ１の裏側（図中下側）の３次元空間ＳＰを２つに分割する２回目の正規分割面ＲＤ２として決定されたとする。すると図２に示すように、正規分割面ＲＤ２が正規分割面ＲＤ１の裏側の中間ノードとして設定される。
【００４７】
そして図１に示すように正規分割面ＲＤ２には、正規ポリゴンＲ２の向きを示す法線ベクトルが正規分割面ＲＤ２の法線ベクトルとして設定される。そして正規分割面ＲＤ２よりも図中左側の３次元空間ＳＰが、正規分割面ＲＤ１の裏側かつ正規分割面ＲＤ２の表側とされ、正規分割面ＲＤ２よりも図中右側の３次元空間ＳＰが、正規分割面ＲＤ１の裏側かつ正規分割面ＲＤ２の裏側とされる。
【００４８】
すると図１の例では、２回目の分割対象ポリゴン集合であった２２個の正規ポリゴンのうち、正規分割面ＲＤ２に含まれ、かつ正規分割面ＲＤ２と向きが同一の正規ポリゴンＲ２の１個の正規ポリゴンが、正規分割面ＲＤ２の表側の分割後ポリゴン集合として設定される。一方、正規ポリゴンＲ２以外の２１個の正規ポリゴンが、正規分割面ＲＤ２の裏側の分割後ポリゴン集合として設定される。
【００４９】
すると正規分割面ＲＤ２の表側の分割後ポリゴン集合は、それに含まれる正規ポリゴンの数が１個であるので、図２に示すように、正規ポリゴンＲ２が正規分割面ＲＤ２の表側の外部ノードとして設定される。一方、正規分割面ＲＤ２の裏側の分割後ポリゴン集合は、それに含まれる正規ポリゴンの数が２１個であるので、３回目の分割の対象となる分割対象ポリゴン集合として設定される（再分割対象設定処理の一例）。
【００５０】
そして図１に示すように、例えばオブジェクトＯ１を構成する正規ポリゴンＲ３を含む面が、正規分割面ＲＤ１の裏側（図中下側）であってかつ正規分割面ＲＤ２の裏側（図中右側）の３次元空間ＳＰを２つに分割する３回目の正規分割面ＲＤ３として決定されたとする。すると図２に示すように、正規分割面ＲＤ３が正規分割面ＲＤ２の裏側の中間ノードとして設定される。
【００５１】
そして図１に示すように正規分割面ＲＤ３には、正規ポリゴンＲ３の向きを示す法線ベクトルが正規分割面ＲＤ３の法線ベクトルとして設定される。そして正規分割面ＲＤ３よりも図中下側の３次元空間ＳＰが、正規分割面ＲＤ２の裏側かつ正規分割面ＲＤ３の表側とされ、正規分割面ＲＤ３よりも図中上側の３次元空間ＳＰが、正規分割面ＲＤ２の裏側かつ正規分割面ＲＤ３の裏側とされる。
【００５２】
ここで図１の例では、正規分割面ＲＤ３は、オブジェクトＯ３を構成する正規ポリゴンＲ１０および正規ポリゴンＲ１２と交差しているので、正規ポリゴンＲ１０を正規分割面ＲＤ３の表側となる正規ポリゴンＲ１０‐１と正規分割面ＲＤ３の裏側となる正規ポリゴンＲ１０‐２とに分割し、正規ポリゴンＲ１２を正規分割面ＲＤ３の表側となる正規ポリゴンＲ１２‐１と正規分割面ＲＤ３の裏側となる正規ポリゴンＲ１２‐２とに分割する。
【００５３】
すると図１の例では、３回目の分割対象ポリゴン集合であった２１個の正規ポリゴンと分割により増加した２個の正規ポリゴンの合計２３個の正規ポリゴンのうち、正規ポリゴンＲ１０‐１や正規ポリゴンＲ１２‐１、正規分割面ＲＤ３に含まれかつ正規分割面ＲＤ３と向きが同一の正規ポリゴンＲ３や正規ポリゴンＲ１９など、１７個の正規ポリゴンが、正規分割面ＲＤ３の表側の分割後ポリゴン集合として設定される。一方、これら１７個の正規ポリゴン以外の正規ポリゴンＲ１０‐２や正規ポリゴンＲ１２‐２などの６個の正規ポリゴンが、正規分割面ＲＤ３の裏側の分割後ポリゴン集合として設定される。
【００５４】
そしてこの場合には、いずれの分割後ポリゴン集合もそれに含まれる正規ポリゴンの数が５個以下でないので、いずれの分割後ポリゴン集合に含まれる正規ポリゴンも正規分割面ＲＤ３の外部ノードとして設定されない。そしてこの場合には、正規分割面ＲＤ３の表側の分割後ポリゴン集合（１７個）と裏側の分割後ポリゴン集合（６個）の双方が、分割対象ポリゴン集合として設定される。この場合には、まず正規分割面ＲＤ３の表側の分割後ポリゴン集合（１７個）が、４回目の分割の対象となる分割対象ポリゴン集合として設定される（再分割対象設定処理の一例）。
【００５５】
そして図１に示すように、例えばオブジェクトＯ３を構成する正規ポリゴンＲ１１を含む面が、正規分割面ＲＤ２の裏側（図中右側）であってかつ正規分割面ＲＤ３の表側（図中下側）の３次元空間ＳＰを２つに分割する４回目の正規分割面ＲＤ４として決定されたとする。すると図２に示すように、正規分割面ＲＤ４が正規分割面ＲＤ３の表側の中間ノードとして設定される。
【００５６】
そして正規分割面ＲＤ４には、図１に示すように正規ポリゴンＲ１１の向きを示す法線ベクトルが正規分割面ＲＤ４の法線ベクトルとして設定される。そして正規分割面ＲＤ４よりも図中下側の３次元空間ＳＰが、正規分割面ＲＤ４の表側とされ、正規分割面ＲＤ４よりも図中上側の３次元空間ＳＰが、正規分割面ＲＤ４の裏側とされる。
【００５７】
すると図１の例では、４回目の分割対象ポリゴン集合であった１７個の正規ポリゴンのうち、正規分割面ＲＤ４に含まれかつ正規分割面ＲＤ４と向きが同一の正規ポリゴンＲ１１など、１３個の正規ポリゴンが、正規分割面ＲＤ４の表側の分割後ポリゴン集合として設定される。一方、１３個の正規ポリゴン以外の正規ポリゴンＲ１０‐１や正規ポリゴンＲ１２‐１などの４個の正規ポリゴンが、正規分割面ＲＤ４の裏側の分割後ポリゴン集合として設定される。
【００５８】
すると正規分割面ＲＤ４の表側の分割後ポリゴン集合は、それに含まれる正規ポリゴンの数が１３個であるので、５回目の分割の対象となる分割対象ポリゴン集合として設定される（再分割対象設定処理の一例）。一方、正規分割面ＲＤ４の裏側の分割後ポリゴン集合は、それに含まれる正規ポリゴンの数が４個であるので、図２に示すように、正規ポリゴンＲ３、正規ポリゴンＲ１０‐１、正規ポリゴンＲ１２‐１、正規ポリゴンＲ１９の４個の正規ポリゴンが正規分割面ＲＤ４の裏側の外部ノードとして設定される。
【００５９】
このような処理を繰り返すことにより、所定の３次元空間ＳＰに配置される正規ポリゴンＲ１〜正規ポリゴンＲ２４あるいはいずれかの正規ポリゴンが分割されることにより生成された正規ポリゴンの全てが、いずれかの外部ノードの分割後ポリゴン集合として設定されると、図２に示すように、正規ポリゴンＲ１〜正規ポリゴンＲ２４についてＢＳＰ木構造を有するデータが完成される。そして、３次元空間ＳＰに存在する移動体について交差判定処理を行う際には、まずＢＳＰ木構造を有するデータのルートとして設定されている正規分割面ＲＤ１に対して移動体の位置が表側であるか裏側であるかの表裏判定が行われる。そして表裏判定の結果が表側である場合には、ルートの表側のノードが参照され、表裏判定の結果が裏側である場合には、ルートの裏側のノードが参照される。そして参照されたノードが中間ノードである場合には、中間ノードとして設定されている正規分割面ＲＤについて移動体の位置の表裏判定が行われ、参照されたノードが外部ノードである場合には、外部ノードとして設定されている分割後ポリゴン集合が交差判定処理の処理対象として特定される。
【００６０】
例えば図１に示す所定の３次元空間ＳＰの位置ＰＯにキャラクタが存在している場合には、１回目の表裏判定として、位置ＰＯが図２に示すルートである正規分割面ＲＤ１に対して表側であるか裏側であるか判定される。そして位置ＰＯは、図１に示すように正規分割面ＲＤ１に対して裏側であるので、図２に示す正規分割面ＲＤ１の裏側の中間ノードである正規分割面ＲＤ２が参照され、２回目の表裏判定として、位置ＰＯが正規分割面ＲＤ２に対して表側であるか裏側であるか判定される。そして位置ＰＯは、図１に示すように正規分割面ＲＤ２に対して裏側であるので、図２に示す正規分割面ＲＤ２の裏側の中間ノードである正規分割面ＲＤ３が参照され、３回目の表裏判定として、位置ＰＯが正規分割面ＲＤ３に対して表側であるか裏側であるか判定される。そして位置ＰＯは、図１に示すように正規分割面ＲＤ３に対して表側であるので、図２に示す正規分割面ＲＤ３の表側の中間ノードである正規分割面ＲＤ４が参照され、４回目の表裏判定として、位置ＰＯが正規分割面ＲＤ４に対して表側であるか裏側であるか判定される。
【００６１】
そして位置ＰＯは、図１に示すように正規分割面ＲＤ４に対して表側であるので、図２に示す正規分割面ＲＤ４の表側の中間ノードである正規分割面ＲＤ６が参照され、５回目の表裏判定として、位置ＰＯが正規分割面ＲＤ６に対して表側であるか裏側であるか判定される。そして位置ＰＯは、図１に示すように正規分割面ＲＤ６に対して表側であるので、図２に示す正規分割面ＲＤ６の表側の中間ノードである正規分割面ＲＤ７が参照され、６回目の表裏判定として、位置ＰＯが正規分割面ＲＤ７に対して表側であるか裏側であるか判定される。そして位置ＰＯは、図１に示すように正規分割面ＲＤ７に対して表側であるので、図２に示す正規分割面ＲＤ７の表側の外部ノードである正規ポリゴンＲ１５、正規ポリゴンＲ２１、正規ポリゴンＲ２２、正規ポリゴンＲ２３、正規ポリゴンＲ２４の５個の正規ポリゴンが、交差判定処理の処理対象として特定される。
【００６２】
このようにＢＳＰ木構造を有するデータを用いると、ポリゴン集合に含まれる全てのポリゴンについて交差判定処理を行う必要がなくなる。しかし、図２の例のＢＳＰ木構造を有するデータでは、ルートから各外部ノードまでの深さが偏っているため、図１に示す位置ＰＯについて交差判定処理の処理対象を特定するために６回の表裏判定を要しており効率的でない。これに対して、ルートから各外部ノードまでの深さの偏りが少なければ、必要となる表裏判定の回数の偏りが少なくなり効率的となる。
【００６３】
２．本実施形態の手法
次に、本実施形態のＢＳＰ木構造を有するデータの生成手法を説明する。
【００６４】
２−１．正規評価処理
本実施形態では、分割対象ポリゴン集合を分割する際には、分割対象ポリゴン集合に含まれる複数の正規ポリゴンのそれぞれを含む複数の正規分割面候補のそれぞれを評価対象として、それぞれについて正規評価値（第３評価値の一例）を求める正規評価処理を行う。そして複数の正規分割面候補のそれぞれの正規評価値を比較して１つの正規分割面を決定する。これにより本実施形態では、ルートから各外部ノードまでの深さの偏りが少ないＢＳＰ木構造を有するデータを生成するために好適な正規分割面を決定している。
【００６５】
図３は、図１と同一の３次元空間ＳＰをそのＸＺ平面に投影した図である。図３でも図１と同様に、説明を容易にするために、面を構成するポリゴンが線分により表されている。
【００６６】
図３の例では、まず、正規ポリゴンＲ１〜正規ポリゴンＲ２４の２４個の正規ポリゴンが１回目の分割の対象となる分割対象ポリゴン集合として設定される（初期分割対象設定処理の一例）。すると、２４個の正規ポリゴンのそれぞれを含む２４個の正規分割面候補ＲＣ１が１回目の評価対象として設定され、２４個の正規分割面候補ＲＣ１のそれぞれについて正規評価値を求める正規評価処理が行われる。本実施形態では、まず、図３に示す正規ポリゴンＲ１を含む正規分割面候補ＲＣ１‐１を評価対象として設定し、正規分割面候補ＲＣ１‐１について正規評価値を求める正規評価処理が行われる。
【００６７】
この正規評価処理では、まずは正規分割面候補ＲＣ１‐１を評価対象として、１回目の分割対象ポリゴン集合に含まれる正規ポリゴンのうち、正規分割面候補ＲＣ１‐１と交差する正規ポリゴンの数に基づいて交差評価成分（第１評価成分）が求められる。本実施形態では正規分割面ＲＤが正規ポリゴンと交差すると正規ポリゴンが分割されて正規ポリゴンの数が増加するので、正規分割面候補ＲＣと交差する正規ポリゴンの数が少ない方が、分割による正規ポリゴンの数の増加を抑制できる正規分割面ＲＤであると評価できるからである。
【００６８】
具体的には本実施形態では、「交差評価成分＝正規分割面候補ＲＣと交差する正規ポリゴンの数／分割対象ポリゴン集合に含まれる正規ポリゴンの総数」のようにして交差評価成分が求められ、０〜１の範囲で交差評価成分が小さいほど評価が高くなる。図３の例では正規分割面候補ＲＣ１‐１は、１回目の分割対象ポリゴン集合に含まれる正規ポリゴンのいずれとも交差していないので、正規分割面候補ＲＣ１‐１の交差評価成分＝０／２４＝０となる。
【００６９】
するとこの正規分割面候補ＲＣ１‐１を評価対象として、１回目の分割対象ポリゴン集合に含まれる正規ポリゴンのうち、正規分割面候補ＲＣ１‐１上に存在する（正規分割面候補ＲＣ１‐１に含まれる、あるいは正規分割面候補ＲＣ１‐１と平行である）正規ポリゴンの数に基づいて平行評価成分（第２評価成分）が求められる。本実施形態では正規分割面ＲＤが正規ポリゴンと交差すると正規ポリゴンが分割されて正規ポリゴンの数が増加するので、正規分割面候補ＲＣ上に存在する正規ポリゴンの数が多い方が、分割による正規ポリゴンの数の増加を抑制できる正規分割面ＲＤであると評価できる上、１つの正規分割面候補ＲＣ上に複数の正規ポリゴンが存在する場合には、１つの正規分割面候補ＲＣ上の複数の正規ポリゴンのそれぞれは同一の正規分割面ＲＤとなるので、中間ノードの増加を抑制できる正規分割面ＲＤであると評価できるからである。
【００７０】
具体的には本実施形態では、「平行評価成分＝（分割対象ポリゴン集合に含まれる正規ポリゴンの総数−正規分割面候補ＲＣ上に存在する正規ポリゴンの数）／分割対象ポリゴン集合に含まれる正規ポリゴンの総数」のようにして平行評価成分が求められ、０〜１の範囲で平行評価成分が小さいほど評価が高くなる。図３の例では、正規分割面候補ＲＣ１‐１上には正規ポリゴンＲ１と正規ポリゴンＲ１７の２個の正規ポリゴンが存在しているので、正規分割面候補ＲＣ１‐１の交差評価成分＝（２４−２）／２４＝０．９１７となる。
【００７１】
更にこの正規分割面候補ＲＣ１‐１を評価対象として、１回目の分割対象ポリゴン集合に含まれる正規ポリゴンのうち、正規分割面候補ＲＣ１‐１の表側に存在する正規ポリゴンの数と裏側に存在する正規ポリゴンの数とに基づいてバランス評価成分（第３評価成分）が求められる。本実施形態では、正規分割面候補ＲＣの表側の正規ポリゴンの数と裏側の正規ポリゴンの数との比が１：１に近い方が、ルートから各外部ノードまでの深さの偏りを抑制できる正規分割面であると評価できるからである。
【００７２】
具体的には本実施形態では、「バランス評価成分＝｜（０．５−（正規分割面候補ＲＣの表側の正規ポリゴンの数／（正規分割面候補ＲＣの表側の正規ポリゴンの数＋正規分割面候補ＲＣの裏側の正規ポリゴンの数））｜／０．５」のようにしてバランス評価成分が求められ、０〜１の範囲でバランス評価成分が小さいほど評価が高くなる。図３の例では、正規分割面候補ＲＣ１‐１の表側の正規ポリゴンの数は２個であり裏側の正規ポリゴンの数は２２個であるので、正規分割面候補ＲＣ１‐１のバランス評価成分＝｜（０．５−（２／（２＋２２））｜／０．５＝０．８３４となる。
【００７３】
そして本実施形態では、このようにして求められた交差評価成分と平行評価成分とバランス評価成分とに適切な重み付けを行って、正規分割面候補ＲＣ１‐１の正規評価値が求められる。本実施形態では、「正規評価値＝（Ａ＊交差評価成分＋Ｂ＊平行評価成分＋Ｃ＊バランス評価成分）／（Ａ＋Ｂ＋Ｃ）」のようにして正規評価値が求められ、０〜１の範囲で正規評価値が小さいほど評価が高くなる。図３の例では、正規分割面候補ＲＣ１‐１の正規評価値＝（０＋０．９１７Ｂ＋０．８３４Ｃ）／（Ａ＋Ｂ＋Ｃ）となる。ここでＡ、Ｂ、Ｃは、各評価成分に対する重み付けとなる係数であり、本実施形態では、Ａ＞Ｃ＞Ｂとなっている。
【００７４】
こうして正規分割面候補ＲＣ１‐１の正規評価値が求められると、図３に示す正規ポリゴンＲ２を含む正規分割面候補ＲＣ２‐１を評価対象として設定し、正規分割面候補ＲＣ１‐２について正規評価値を求める正規評価処理が行われる。そして、１回目の分割の対象となる分割対象ポリゴン集合として設定された正規ポリゴンＲ１〜正規ポリゴンＲ２４のそれぞれを含む正規分割面候補ＲＣ１‐１〜正規分割面候補ＲＣ１‐２４の全てについて正規評価値を求める正規評価処理が行われる。
【００７５】
なお本実施形態では、１つの正規分割面候補ＲＣ上に存在する正規ポリゴンを含む他の正規分割面候補ＲＣに関しては正規評価値が同一となるので、最初に評価対象となった正１つの規分割面候補ＲＣの正規評価値を、その正規分割面候補ＲＣ上に存在する正規ポリゴンを含む他の正規分割面候補ＲＣの正規評価値として設定する。
【００７６】
そして、正規分割面候補ＲＣ１‐１〜正規分割面候補ＲＣ１‐２４の全てについて正規評価値を求める正規評価処理が行われると、正規分割面候補ＲＣ１‐１〜正規分割面候補ＲＣ１‐２４のうち最も正規評価値が小さい、すなわち最も評価が高い正規分割面候補ＲＣ１が選択され、選択された正規分割面候補ＲＣ１が、１回目の分割の対象となる分割対象ポリゴン集合を分割する１回目の正規分割面ＲＤとして決定される。
【００７７】
図３の例では、正規評価値を求める際の重み付けが最も大きい係数Ａが設定されている交差評価成分に関して正規分割面候補ＲＣ１‐１〜正規分割面候補ＲＣ１‐２４を比較すると、正規分割面候補ＲＣ１‐１や正規分割面候補ＲＣ１‐２など数個の正規分割面候補ＲＣが、１回目の分割対象ポリゴン集合に含まれる正規ポリゴンのいずれとも交差していないので、これら数個の正規分割面候補ＲＣの交差評価成分が最も小さく評価が最も高い。
【００７８】
また、正規評価値を求める際の重み付けが次に大きい係数Ｃが設定されているバランス評価成分に関して正規分割面候補ＲＣ１‐１〜正規分割面候補ＲＣ１‐２４を比較すると、正規ポリゴンＲ５を含む正規分割面候補ＲＣ１‐５の表側の正規ポリゴンの数と裏側の正規ポリゴンの数の比が１３：１１となり、正規ポリゴンＲ１２を含む正規分割面候補ＲＣ１‐１２の表側の正規ポリゴンの数と裏側の正規ポリゴンの数の比が１２：１２＝１：１となるため、正規分割面候補ＲＣ１‐１２のバランス評価成分が最も小さく評価が最も高く、正規分割面候補ＲＣ１‐５のバランス評価成分が次に評価が高い。
【００７９】
そして、正規評価値を求める際の重み付けが次に大きい係数Ｂが設定されている平行評価成分に関してこの正規分割面候補ＲＣ１‐５と正規分割面候補ＲＣ１‐１２を比較すると、正規分割面候補ＲＣ１‐５上には正規ポリゴンＲ５の１個の正規ポリゴンが存在し、正規分割面候補ＲＣ１‐１２上には正規ポリゴンＲ１２と正規ポリゴンＲ１４の２個の正規ポリゴンが存在するので、正規分割面候補ＲＣ１‐１２の平行評価成分が最も小さく評価が最も高い。
【００８０】
従って図３の例では、１回目の分割の対象となる分割対象ポリゴン集合として設定された正規ポリゴンＲ１〜正規ポリゴンＲ２４については、正規ポリゴンＲ１２を含む正規分割面候補ＲＣ１‐１２が、図４に示すように１回目の正規分割面ＲＤ１として決定される。すると、図５に示すように、正規分割面ＲＤ１がＢＳＰ木構造のルートとして設定される。
【００８１】
そして図４に示すように、正規分割面ＲＤ１には、正規ポリゴンＲ１２の向きを示す法線ベクトルが正規分割面ＲＤ１の法線ベクトルとして設定される。そして正規分割面ＲＤ１よりも図中右側の３次元空間ＳＰが、正規分割面ＲＤ１の表側とされ、正規分割面ＲＤ１よりも図中左側の３次元空間ＳＰが、正規分割面ＲＤ１の裏側とされる。
【００８２】
すると図４の例では、１回目の分割対象ポリゴン集合であった２４個の正規ポリゴンのうち、正規分割面ＲＤ１に含まれ、かつ正規分割面ＲＤ１と向きが同一の正規ポリゴンＲ１２などの１２個の正規ポリゴンが、正規分割面ＲＤ１の表側の分割後ポリゴン集合として設定され、２回目の分割の対象となる分割対象ポリゴン集合として設定される（再分割対象設定処理の一例）。そして１２個の正規ポリゴンのそれぞれを含む１２個の正規分割面候補ＲＣ２が２回目の評価対象として設定され、１２個の正規分割面候補ＲＣ２のそれぞれについて、上述した正規評価値を求める正規評価処理が行われる。
【００８３】
図４の例では、正規ポリゴンＲ１３を含む正規分割面候補ＲＣ２‐１３と正規ポリゴンＲ１８を含む正規分割面候補ＲＣ２‐１８とが、２回目の分割対象ポリゴン集合に含まれる１２個の正規ポリゴンのいずれとも交差せず、その表側の正規ポリゴンの数と裏側の正規ポリゴンの数の比が６：６＝１：１となるが、正規分割面候補ＲＣ２‐１３上には正規ポリゴンＲ１３の１個の正規ポリゴンしか存在しないが、正規分割面候補ＲＣ２‐１８上には正規ポリゴンＲ１８と正規ポリゴンＲ２２の２個の正規ポリゴンが存在するので、正規分割面候補ＲＣ２‐１８の正規評価値が最も小さく評価が最も高い。従って、２回目の分割の対象となる分割対象ポリゴン集合として設定された１２個の正規ポリゴンについては、図４に示す正規分割面候補ＲＣ２‐１８が、図６に示すように２回目の正規分割面ＲＤ２として決定される。すると、図５に示すように、正規分割面ＲＤ２が正規分割面ＲＤ１の表側の中間ノードとして設定される。
【００８４】
すると図６の例では、正規分割面ＲＤ２よりも図中左側の３次元空間ＳＰが、正規分割面ＲＤ２の表側とされ、正規ポリゴンＲ１８などの６個の正規ポリゴンが、正規分割面ＲＤ２の表側の分割後ポリゴン集合として設定され、３回目の分割の対象となる分割対象ポリゴン集合として設定される（再分割対象設定処理の一例）。そして６個の正規ポリゴンのそれぞれを含む６個の正規分割面候補ＲＣ３が評価対象として設定され、６個の正規分割面候補ＲＣ３のそれぞれについて、上述した正規評価値を求める正規評価処理が行われる。
【００８５】
図６の例では、正規ポリゴンＲ１３を含む正規分割面候補ＲＣ３‐１３が、３回目の分割対象ポリゴン集合に含まれる６個の正規ポリゴンのいずれとも交差せず、その表側の正規ポリゴンの数と裏側の正規ポリゴンの数の比が３：３＝１：１となるので、正規評価値が最も小さく評価が最も高い。従って、３回目の分割の対象となる分割対象ポリゴン集合として設定された６個の正規ポリゴンについては、図６に示す正規分割面候補ＲＣ３‐１３が、３回目の正規分割面ＲＤ３として決定される。すると、図５に示すように、正規分割面ＲＤ３が正規分割面ＲＤ２の表側の中間ノードとして設定される。
【００８６】
すると図６の例では、正規分割面ＲＤ３よりも図中上側の３次元空間ＳＰが、正規分割面ＲＤ３の表側とされ、正規ポリゴンＲ１２と正規ポリゴンＲ１３と正規ポリゴンＲ１８の３個の正規ポリゴンが、正規分割面ＲＤ３の表側の分割後ポリゴン集合として設定される。そして、この分割後ポリゴン集合はそれに含まれる正規ポリゴンの数が５個以下であるので、図５に示すように、正規ポリゴンＲ１２と正規ポリゴンＲ１３と正規ポリゴンＲ１８とが正規分割面ＲＤ３の表側の外部ノードとして設定される。
【００８７】
更に、正規分割面ＲＤ３よりも図中下側の３次元空間ＳＰが、正規分割面ＲＤ３の裏側とされ、正規ポリゴンＲ１５と正規ポリゴンＲ１６と正規ポリゴンＲ２２の３個の正規ポリゴンが、正規分割面ＲＤ３の裏側の分割後ポリゴン集合として設定される。そして、この分割後ポリゴン集合はそれに含まれる正規ポリゴンの数が５個以下であるので、図５に示すように、正規ポリゴンＲ１５と正規ポリゴンＲ１６と正規ポリゴンＲ２２とが正規分割面ＲＤ３の裏側の外部ノードとして設定される。
【００８８】
そして図６の例では、正規分割面ＲＤ２よりも図中右側の３次元空間ＳＰについては、正規ポリゴンＲ１７などの６個の正規ポリゴンが、正規分割面ＲＤ２の裏側の分割後ポリゴン集合として設定され、４回目の分割の対象となる分割対象ポリゴン集合として設定される（分割対象設定処理の一例）。そして６個の正規ポリゴンのそれぞれを含む６個の正規分割面候補ＲＣ４のそれぞれについて、上述した正規評価値を求める正規評価処理が行われ、図６の例では、正規ポリゴンＲ１９を含む正規分割面候補ＲＣ４‐１９が、４回目の正規分割面ＲＤ４として決定される。すると、図５に示すように、正規分割面ＲＤ４が正規分割面ＲＤ２の裏側の中間ノードとして設定される。
【００８９】
すると図６の例では、正規分割面ＲＤ４よりも図中下側の３次元空間ＳＰが、正規分割面ＲＤ４の表側とされ、正規ポリゴンＲ１９と正規ポリゴンＲ２１と正規ポリゴンＲ２３と正規ポリゴンＲ２４の４個の正規ポリゴンが、正規分割面ＲＤ４の表側の分割後ポリゴン集合として設定される。すると、この分割後ポリゴン集合はそれに含まれる正規ポリゴンの数が５個以下であるので、図５に示すように、正規ポリゴンＲ１９と正規ポリゴンＲ２１と正規ポリゴンＲ２３と正規ポリゴンＲ２４とが正規分割面ＲＤ４の表側の外部ノードとして設定される。
【００９０】
更に図６の例では、正規分割面ＲＤ４よりも図中上側の３次元空間ＳＰが、正規分割面ＲＤ４の裏側とされ、正規ポリゴンＲ１７と正規ポリゴンＲ２０の２個の正規ポリゴンが、正規分割面ＲＤ４の裏側の分割後ポリゴン集合として設定される。すると、この分割後ポリゴン集合はそれに含まれる正規ポリゴンの数が５個以下であるので、図５に示すように、正規ポリゴンＲ１７と正規ポリゴンＲ２０とが正規分割面ＲＤ４の裏側の外部ノードとして設定される。
【００９１】
そして以上と同様の処理を、図６に示す正規分割面ＲＤ１よりも図中左側の３次元空間ＳＰである正規分割面ＲＤ１の裏側について行うと、正規ポリゴンＲ１１を含む正規分割面候補ＲＣ５‐１１が、５回目の正規分割面ＲＤ５として決定され、図５に示すように、正規分割面ＲＤ５が正規分割面ＲＤ１の裏側の中間ノードとして設定される。
【００９２】
更に以上と同様の処理を、図６に示す正規分割面ＲＤ５よりも図中下側の３次元空間ＳＰである正規分割面ＲＤ５の表側について行うと、正規ポリゴンＲ８を含む正規分割面候補ＲＣ６‐８が、６回目の正規分割面ＲＤ６として決定され、図５に示すように、正規分割面ＲＤ６が正規分割面ＲＤ５の表側の中間ノードとして設定される。
【００９３】
すると、正規分割面ＲＤ６の図中右側となる表側の分割後ポリゴン集合は、それに含まれる正規ポリゴンの数が５個以下であるので、図５に示すように、正規ポリゴンＲ８と正規ポリゴンＲ１１と正規ポリゴンＲ１４とが正規分割面ＲＤ６の表側の外部ノードとして設定される。一方、正規分割面ＲＤ６の図中左側となる裏側の分割後ポリゴン集合も、それに含まれる正規ポリゴンの数が５個以下であるので、図５に示すように、正規ポリゴンＲ５と正規ポリゴンＲ６と正規ポリゴンＲ７とが正規分割面ＲＤ６の裏側の外部ノードとして設定される。
【００９４】
更に以上と同様の処理を、図７に示す正規分割面ＲＤ５よりも図中上側の３次元空間ＳＰである正規分割面ＲＤ５の裏側について行うと、正規ポリゴンＲ４を含む正規分割面候補ＲＣ７‐４が、７回目の正規分割面ＲＤ７として決定され、図５に示すように、正規分割面ＲＤ７が正規分割面ＲＤ５の裏側の中間ノードとして設定される。
【００９５】
すると、正規分割面ＲＤ７の図中右側となる表側の分割後ポリゴン集合は、それに含まれる正規ポリゴンの数が５個以下であるので、図５に示すように、正規ポリゴンＲ４と正規ポリゴンＲ９と正規ポリゴンＲ１０とが正規分割面ＲＤ７の表側の外部ノードとして設定される。一方、正規分割面ＲＤ７の図中左側となる裏側の分割後ポリゴン集合も、それに含まれる正規ポリゴンの数が５個以下であるので、図５に示すように、正規ポリゴンＲ１と正規ポリゴンＲ２と正規ポリゴンＲ３とが正規分割面ＲＤ７の裏側の外部ノードとして設定される。
【００９６】
こうして本実施形態では、図５に示すように、正規ポリゴンＲ１〜正規ポリゴンＲ２４についてＢＳＰ木構造を有するデータが完成されるが、図５に示す本実施形態の手法により生成されたＢＳＰ木構造を有するデータでは、ルートから各外部ノードまでの深さの偏りが少ない。従って本実施形態の手法により生成されたＢＳＰ木構造を有するデータでは、３次元空間ＳＰに配置されるキャラクタなどについて交差判定処理の処理対象を特定するために必要となる表裏判定の回数の偏りも少なくなり、効率的に処理対象を特定することができる。
【００９７】
２−２．補助評価処理
しかし本実施形態では、上述した正規評価値を求める正規評価処理を複数の正規分割面候補ＲＣの全てについて行うので、分割対象ポリゴン集合に含まれる複数の正規ポリゴンの数が多い場合には、ＢＳＰ木構造を有するデータを生成する際の処理負荷が大きくなってしまう。そこで本実施形態では、分割対象ポリゴン集合に含まれる複数の正規ポリゴンの数が１０個（所定数の一例）以上である場合には、分割対象ポリゴン集合に含まれる正規ポリゴンの頂点に基づいて、６個の補助分割面候補を生成する補助分割面候補生成処理を行い、６個の補助分割面候補のそれぞれを評価対象として、それぞれについて補助評価値（第１評価値の一例）を求める補助評価処理を行う。そして６個の補助分割面候補から１個の補助分割面候補を決定している。
【００９８】
図７（Ａ）および図７（Ｂ）は、図１や図３などで２次元的に示した３次元空間ＳＰの斜視図である。本実施形態では、図７（Ａ）に示すように、オブジェクトＯ１〜オブジェクトＯ６を構成する正規ポリゴンＲ１〜正規ポリゴンＲ２４の２４個の正規ポリゴンが１回目の分割対象ポリゴン集合として設定されると、１回目の分割対象ポリゴン集合に含まれる正規ポリゴンの数が１０個以上となる。この場合には本実施形態では、図７（Ａ）に示すように、オブジェクトＯ１〜オブジェクトＯ６を囲むバウンディングボックスＢＢ（３次元領域の一例）が生成される。本実施形態では、オブジェクトＯ１〜オブジェクトＯ６を構成する正規ポリゴンＲ１〜正規ポリゴンＲ２４の頂点に基づいて、全ての頂点が含まれる直方体がバウンディングボックスＢＢとして生成される。すると、このバウンディングボックスＢＢの重心ＣＧを通り、３次元空間ＳＰのＸＺ平面に平行なポリゴンである補助分割面候補ＡＣ１‐１と、３次元空間ＳＰのＸＹ平面に平行なポリゴンである補助分割面候補ＡＣ１‐２と、３次元空間ＳＰのＹＺ平面に平行なポリゴンである補助分割面候補ＡＣ１‐３とが生成される。
【００９９】
更に本実施形態では、図７（Ｂ）に示すように、オブジェクトＯ１〜オブジェクトＯ６を構成する正規ポリゴンＲ１〜正規ポリゴンＲ２４の頂点に基づいて、全ての頂点の平均位置ＡＶ（代表点の一例）が求められ、この平均位置ＡＶを通り、３次元空間ＳＰのＸＺ平面に平行なポリゴンである補助分割面候補ＡＣ１‐４と、３次元空間ＳＰのＸＹ平面に平行なポリゴンである補助分割面候補ＡＣ１‐５と、３次元空間ＳＰのＹＺ平面に平行なポリゴンである補助分割面候補ＡＣ１‐６とが生成される。
【０１００】
そしてこれら補助分割面候補ＡＣ１‐１〜補助分割面候補ＡＣ１‐６のそれぞれが１回目の評価対象として設定され、６個の補助分割面候補ＡＣ１のそれぞれについて補助評価値を求める補助評価処理が行われる。従って補助評価処理では、２４個の正規分割面候補ＲＣの全てについて正規評価値を求める正規評価処理と比較して処理負荷が小さい。
【０１０１】
この補助評価処理でも、上述した正規評価処理と同様に、まず、補助分割面候補ＡＣ１‐１を評価対象として、１回目の分割対象ポリゴン集合に含まれる正規ポリゴンＲ１〜正規ポリゴンＲ２４のうち、補助分割面候補ＡＣ１‐１と交差する正規ポリゴンの数に基づいて交差評価成分（第１評価成分）が求められる。具体的には本実施形態では、「交差評価成分＝補助分割面候補ＡＣと交差する正規ポリゴンの数／分割対象ポリゴン集合に含まれる正規ポリゴンの総数」のようにして交差評価成分が求められ、０〜１の範囲で交差評価成分が小さいほど評価が高くなる。
【０１０２】
するとこの補助分割面候補ＡＣ１‐１を評価対象として、１回目の分割対象ポリゴン集合に含まれる正規ポリゴンのうち、補助分割面候補ＡＣ１‐１上に存在する正規ポリゴンの数に基づいて平行評価成分（第２評価成分）が求められる。具体的には本実施形態では、「平行評価成分＝（分割対象ポリゴン集合に含まれる正規ポリゴンの総数−補助分割面候補ＡＣ上に存在する正規ポリゴンの数）／分割対象ポリゴン集合に含まれる正規ポリゴンの総数」のようにして平行評価成分が求められ、０〜１の範囲で平行評価成分が小さいほど評価が高くなる。
【０１０３】
更にこの補助分割面候補ＡＣ１‐１を評価対象として、１回目の分割対象ポリゴン集合に含まれる正規ポリゴンのうち、補助分割面候補ＡＣ１‐１の表側に存在する正規ポリゴンの数と裏側に存在する正規ポリゴンの数とに基づいてバランス評価成分（第３評価成分）が求められる。具体的には本実施形態では、「バランス評価成分＝｜（０．５−（補助分割面候補ＡＣの表側の正規ポリゴンの数／（補助分割面候補ＡＣの表側の正規ポリゴンの数＋補助分割面候補ＡＣの裏側の正規ポリゴンの数））｜／０．５」のようにしてバランス評価成分が求められ、０〜１の範囲でバランス評価成分が小さいほど評価が高くなる。
【０１０４】
そして本実施形態では、このようにして求められた交差評価成分と平行評価成分とバランス評価成分とに適切な重み付けを行って、補助分割面候補ＡＣ１‐１の補助評価値が求められる。本実施形態では、「補助評価値＝（Ａ＊交差評価成分＋Ｂ＊平行評価成分＋Ｃ＊バランス評価成分）／（Ａ＋Ｂ＋Ｃ）」のようにして補助評価値が求められ、０〜１の範囲で補助評価値が小さいほど評価が高くなる。ここでＡ、Ｂ、Ｃは、各評価成分に対する重み付けとなる係数であり、本実施形態では、Ａ＞Ｃ＞Ｂとなっている。
【０１０５】
こうして補助分割面候補ＡＣ１‐１の補助評価値が求められると、補助分割面候補ＡＣ１‐２を評価対象として設定し、補助分割面候補ＡＣ１‐２について補助評価値を求める補助評価処理が行われる。そして、補助分割面候補ＡＣ１‐１〜補助分割面候補ＡＣ１‐６の全てについて補助評価値を求める補助評価処理が行われると、補助分割面候補ＡＣ１‐１〜補助分割面候補ＡＣ１‐６のうち最も補助評価値が小さい、すなわち最も評価が高い補助分割面候補ＡＣ１が、選択補助分割面候補ＳＡＣ１として選択される。
【０１０６】
図９（Ａ）は、図８（Ａ）で示した３次元空間ＳＰをそのＸＺ平面に投影した図であり、図９（Ｂ）は、図８（Ｂ）で示した３次元空間ＳＰをそのＸＺ平面に投影した図である。図９（Ａ）では、ＸＺ平面に平行な補助分割面候補ＡＣ１‐１が面により表されており、ＸＺ平面に垂直な補助分割面候補ＡＣ１‐２および補助分割面候補ＡＣ１‐３が線分により表されている。同様に図９（Ｂ）では、ＸＺ平面に平行な補助分割面候補ＡＣ１‐４が面により表されており、ＸＺ平面に垂直な補助分割面候補ＡＣ１‐５および補助分割面候補ＡＣ１‐６が線分により表されている。
【０１０７】
図９（Ａ）および図９（Ｂ）の例では、バウンディングボックスＢＢの重心ＣＧを通り、３次元空間ＳＰのＹＺ平面に平行な補助分割面候補ＡＣ１‐３が、交差評価成分に関しては１回目の分割対象ポリゴン集合に含まれる正規ポリゴンのいずれとも交差しておらず、バランス評価成分に関しては表側の正規ポリゴンの数と裏側の正規ポリゴンの数の比が１２：１２＝１：１となり、平行評価成分に関しては補助分割面候補ＡＣ１‐３上には正規ポリゴンＲ１２と正規ポリゴンＲ１４の２個の正規ポリゴンが存在するので、補助分割面候補ＡＣ１‐３の補助評価値が最も小さく評価が最も高い。
【０１０８】
従って図９（Ａ）および図９（Ｂ）の例では、１回目の分割の対象となる分割対象ポリゴン集合として設定された正規ポリゴンＲ１〜正規ポリゴンＲ２４については、図９（Ａ）で示した補助分割面候補ＡＣ１‐３が、補助評価処理において最も評価が高い選択補助分割面候補ＳＡＣ１として選択される。
【０１０９】
しかしこのようにして選択された選択補助分割面候補ＳＡＣ１は、補助分割面候補ＡＣ１‐１〜補助分割面候補ＡＣ１‐６の中では評価が最も高くても、補助評価処理は正規評価処理と比較すると評価対象数が少ないため、分割面として適切ではない場合がある。そこで本実施形態では、選択補助分割面候補ＳＡＣ１が分割面として適切か否かを判断するため、選択補助分割面候補ＳＡＣ１についてサイズ評価値（第２評価値の一例）を求めるサイズ評価処理が行われる。
【０１１０】
このサイズ評価処理では、選択補助分割面候補ＳＡＣ１について上述した補助評価処理で既に求められている数である、選択補助分割面候補ＳＡＣ１と交差する正規ポリゴンの数と、選択補助分割面候補ＳＡＣ１の表側に存在する正規ポリゴンの数と裏側に存在する正規ポリゴンの数とに基づいてサイズ評価値が求められる。本実施形態では、交差する正規ポリゴンの数が少ない方が、分割による正規ポリゴンの数の増加を抑制でき、生成されるＢＳＰ木構造を有するデータのサイズをより小さくすることができる補助分割面であると評価でき、表側の正規ポリゴンの数と裏側の正規ポリゴンの数との比が１：１に近い方が、ルートから各外部ノードまでの深さの偏りを抑制できる補助分割面であると評価できるからである。
【０１１１】
具体的には本実施形態では、「サイズ評価値＝（選択補助分割面候補ＳＡＣと交差する正規ポリゴンの数＊２＋選択補助分割面候補ＳＡＣの表側に存在する正規ポリゴンの数と裏側に存在する正規ポリゴンの数のうち大きい方＊２）／分割対象ポリゴン集合に含まれる正規ポリゴンの総数」のようにしてサイズ評価値が求められ、０〜１の範囲でサイズ評価値が小さいほど評価が高くなる。
【０１１２】
図９（Ａ）および図９（Ｂ）の例では、選択補助分割面候補ＳＡＣ１は図９（Ａ）の補助分割面候補ＡＣ１‐３となるので、補助分割面候補ＡＣ１‐３についてサイズ評価値を検討すると、補助分割面候補ＡＣ１‐３と交差する正規ポリゴンの数は０個であり、補助分割面候補ＡＣ１‐３の表側に存在する正規ポリゴンの数と裏側に存在する正規ポリゴンの数のうち大きい方は１２個であるので、サイズ評価値＝（０＊２＋１２＊２）／２４＝０．５となる。
【０１１３】
そして本実施形態では、この選択補助分割面候補ＳＡＣ１のサイズ評価値が１．１以下である場合に（所定条件を満たすことの一例）、選択補助分割面候補ＳＡＣ１が分割対象ポリゴン集合を分割する補助分割面として採用される。従って、図９（Ａ）に示す補助分割面候補ＡＣ１‐３は、図１０に示すように、１回目の分割対象ポリゴン集合を分割する１回目の補助分割面ＡＤ１として採用され、ＢＳＰ木構造のルートとして設定される。
【０１１４】
ここで本実施形態では、補助分割面候補ＡＣが補助分割面ＡＤとして採用された場合にはルートや中間ノードとして設定され、本実施形態により生成されたＢＳＰ木構造を有するデータが用いられる際には、補助分割面ＡＤに対する移動体の表裏判定が行われるが、補助分割面ＡＤを交差判定処理などの処理対象としないように正規ポリゴンと区別する必要がある。そこで本実施形態では、補助分割面ＡＤには、交差判定処理などの処理対象としないことを示す除外フラグを設定する。これにより本実施形態では、補助分割面ＡＤにより分割対象ポリゴン集合を分割しても、補助分割面ＡＤを正規ポリゴンと区別して補助分割面ＡＤを交差判定処理などの処理対象としないようにすることができる。なおこの除外フラグは、６個の補助分割面候補ＡＣを生成した場合に６個の補助分割面候補ＡＣのそれぞれに設定するようにしてもよいし、６個の補助分割面候補ＡＣのいずれかを補助分割面ＡＤとして採用した場合に補助分割面ＡＤに設定するようにしてもよい。
【０１１５】
こうして補助分割面候補ＡＣ１‐３が補助分割面ＡＤ１として採用されると、図１０の例では、１回目の分割対象ポリゴン集合であった２４個の正規ポリゴンのうち、補助分割面ＡＤ１に含まれ、かつ補助分割面ＡＤ１と向きが同一の正規ポリゴンＲ１２などの１２個の正規ポリゴンが、補助分割面ＡＤ１の表側の分割後ポリゴン集合として設定され、２回目の分割の対象となる分割対象ポリゴン集合として設定される（再分割対象設定処理の一例）。
【０１１６】
そして、この２回目の分割対象ポリゴン集合に含まれる複数の正規ポリゴンの数は１０個以上であるので、図９に示すように、２回目の分割対象ポリゴン集合に含まれる正規ポリゴンの頂点に基づいて、補助分割面候補ＡＣ２‐１〜補助分割面候補ＡＣ２‐６を生成する補助分割面候補生成処理を行い、６個の補助分割面候補ＡＣ２のそれぞれを評価対象として、それぞれについて補助評価値を求める補助評価処理を更に行う。そして上述したように６個の補助分割面候補ＡＣ２から１個の選択補助分割面候補ＳＡＣ２を決定する。
【０１１７】
ここで、選択補助分割面候補ＳＡＣ２のサイズ評価値が１．１よりも大きい場合には（所定条件を満たさないことの一例）、このような選択補助分割面候補ＳＡＣ２は２回目の分割対象ポリゴン集合を分割する補助分割面ＡＤ２としての採用が保留される。そしてこのような場合には、２回目の分割対象ポリゴン集合に含まれる１２個の正規ポリゴンのそれぞれを含む１２個の正規分割面候補ＲＣ２が評価対象として設定され、１２個の正規分割面候補ＲＣ２のそれぞれについて、上述した正規評価値を求める正規評価処理が行われる。
【０１１８】
そして、１２個の正規分割面候補ＲＣ２の全てについて正規評価値を求める正規評価処理が行われると、１２個の正規分割面候補ＲＣ２のうち最も正規評価値が小さい正規分割面候補ＲＣ２が、正規評価処理において最も評価が高い選択正規分割面候補ＳＲＣ２として選択される。図１０の例では、正規ポリゴンＲ１８を含む正規分割面候補ＲＣ２‐１８が、２回目の分割対象ポリゴン集合に含まれる１２個の正規ポリゴンのいずれとも交差せず、その表側の正規ポリゴンの数と裏側の正規ポリゴンの数の比が６：６＝１：１となり、その面上には正規ポリゴンＲ１８と正規ポリゴンＲ２２の２個の正規ポリゴンが存在するので、正規評価値が最も小さく評価が最も高い。従って、正規分割面候補ＲＣ２‐１８が、正規評価処理において最も評価が高い選択正規分割面候補ＳＲＣ２として選択される。
【０１１９】
すると本実施形態では、選択正規分割面候補ＳＲＣ２について、上述したサイズ評価値（第４評価値の一例）を求めるサイズ評価処理が行われる。このサイズ評価処理では、選択正規分割面候補ＳＲＣ２について正規評価処理で既に求められている数である、選択正規分割面候補ＳＲＣ２と交差する正規ポリゴンの数と、選択正規分割面候補ＳＲＣ２の表側に存在する正規ポリゴンの数と裏側に存在する正規ポリゴンの数とに基づいてサイズ評価値が求められる。
【０１２０】
具体的には本実施形態では、「サイズ評価値＝（選択正規分割面候補ＳＲＣと交差する正規ポリゴンの数＊２＋選択正規分割面候補ＳＲＣの表側に存在する正規ポリゴンの数と裏側に存在する正規ポリゴンの数のうち大きい方＊２）／分割対象ポリゴン集合に含まれる正規ポリゴンの総数」のようにしてサイズ評価値が求められ、０〜１の範囲でサイズ評価値が小さいほど評価が高くなる。
【０１２１】
図９の例では、選択正規分割面候補ＳＲＣ２は、選択正規分割面候補ＳＲＣ２と交差する正規ポリゴンの数は０個であり、選択正規分割面候補ＳＲＣ２の表側に存在する正規ポリゴンの数と裏側に存在する正規ポリゴンの数のうち大きい方は６個であるので、サイズ評価値＝（０＊２＋６＊２）／１２＝１．０となる。
【０１２２】
そして本実施形態では、選択補助分割面候補ＳＡＣ２のサイズ評価値（第２評価値の一例）と、選択正規分割面候補ＳＲＣ２のサイズ評価値（第４評価値の一例）とが比較され、サイズ評価値が小さい方が評価が高いとして、２回目の分割対象ポリゴン集合を分割する分割面として採用される。図１０の例では、選択補助分割面候補ＳＡＣ２のサイズ評価値は１．１よりも大きかったため、選択正規分割面候補ＳＲＣ２が２回目の分割対象ポリゴン集合を分割する２回目の正規分割面ＲＤ２として採用され、ＢＳＰ木構造のルートとして設定されている補助分割面ＡＤ１の表側の中間ノードとして設定される。
【０１２３】
すると図９の例では、正規分割面ＲＤ２よりも図中左側の３次元空間ＳＰが、正規分割面ＲＤ２の表側とされ、６個の正規ポリゴンが、正規分割面ＲＤ２の表側の分割後ポリゴン集合として設定され、３回目の分割の対象となる分割対象ポリゴン集合として設定される（再分割対象設定処理の一例）。そして、この３回目の分割対象ポリゴン集合はそれに含まれる正規ポリゴンの数が１０個よりも小さいので、上述した補助分割面候補生成処理や補助評価処理は行われず、分割対象ポリゴン集合に含まれる正規ポリゴンに基づいて複数の正規分割面候補ＲＣが生成され、複数の正規分割面候補ＲＣのそれぞれについて正規評価処理が行われる。
【０１２４】
こうして本実施形態では、分割対象ポリゴン集合に含まれる複数の正規ポリゴンの数が所定数以上である場合には、６つの補助分割面候補ＡＣについて補助評価処理が行われ、１つの選択補助分割面候補ＳＡＣが選択されることにより処理負荷を軽減させている。しかし、選択補助分割面候補ＳＡＣのサイズ評価値が所定条件を満たさない場合には、分割対象ポリゴン集合に含まれる複数の正規ポリゴンのそれぞれを含む複数の正規分割面候補ＲＣについて正規評価処理が行われ、１つの選択正規分割面候補ＳＲＣが選択される。そして、選択補助分割面候補ＳＡＣと選択正規分割面候補ＳＲＣのうち、サイズ評価値が小さい方が分割対象ポリゴン集合を分割する分割面として採用される。そして、分割対象ポリゴン集合に含まれる複数の正規ポリゴンの数が所定数よりも小さくなると、分割対象ポリゴン集合に含まれる複数の正規ポリゴンのそれぞれを含む複数の正規分割面候補ＲＣについて正規評価処理が行われる。
【０１２５】
３．機能ブロック
図１０は、本実施形態のＢＳＰ木構造を有するデータの生成手法を実現するデータ生成システム１０の機能ブロック図である。なお本実施形態のデータ生成システム１０は、図１０の構成要素（各部）を全て含む必要はなく、その一部を省略した構成としてもよい。
【０１２６】
操作部２０は、操作者が操作データを入力するためのものであり、その機能はキーボードやマウスなどにより実現できる。具体的には操作部２０には、本実施形態のＢＳＰ木構造を有するデータを生成する処理の対象となるオブジェクト群（オブジェクト空間）を選択する操作や、本実施形態のデータ生成処理を開始させる操作の操作データが入力される。
【０１２７】
表示部３０は、データ生成システム１０により生成された画像を出力するものであり、その機能はＣＲＴディスプレイ、液晶ディスプレイなどにより実現できる。具体的には表示部３０には、本実施形態のデータ生成処理の対象となるオブジェクトを示す画像や、本実施形態のデータ生成処理により生成されたＢＳＰ木構造を有するデータを示す画像が表示される。
【０１２８】
情報記憶媒体４０（コンピュータにより読み取り可能な媒体）は、プログラムやデータなどを格納するものであり、その機能は、メモリカード、光ディスク（ＣＤ、ＤＶＤ）、光磁気ディスク（ＭＯ）、磁気ディスク、ハードディスク、磁気テープなどにより実現できる。
【０１２９】
この情報記憶媒体４０には、処理部１００において種々の処理を行うためのプログラムやデータが記憶されている。即ち、この情報記憶媒体４０には、本実施形態の各部としてコンピュータを機能させるためのプログラム（各部の処理をコンピュータに実行させるためのプログラム）が格納されている。
【０１３０】
記憶部５０は、処理部１００や通信部６０などのワーク領域となるもので、その機能はＲＡＭやＶＲＡＭなどにより実現できる。そして、本実施形態の記憶部５０は、処理部１００のワーク領域として使用される主記憶部５１と、表示部３０に表示させる画像が描画される描画バッファ５２と、本実施形態のデータ生成処理の対象となる複数の正規ポリゴンを含む正規ポリゴン集合であるオブジェクトデータが読み込まれるオブジェクトデータ記憶部５３と、を含む。
【０１３１】
通信部６０は、外部（例えばサーバや他の携帯端末）との間で通信を行うための各種制御を行うものであり、その機能は、各種プロセッサ又は通信用の集積回路（ＡＳＩＣ）などのハードウェアや、プログラムなどにより実現できる。
【０１３２】
なお、本実施形態の各部としてコンピュータを機能させるためのプログラム（データ）は、ホスト装置（サーバ）が有する情報記憶媒体からネットワーク及び通信部６０を介して情報記憶媒体４０（記憶部５０）に配信してもよい。このようなホスト装置（サーバ）の情報記憶媒体の使用も本発明の範囲内に含めることができる。
【０１３３】
処理部１００（プロセッサ）は、操作部２０からの操作情報やプログラムなどに基づいて、データ生成処理、画像生成処理などの処理を行う。この処理部１００は、記憶部５０をワーク領域として各種処理を行い、その機能は各種プロセッサ（ＣＰＵ、ＤＳＰ等）、各種集積回路（ＩＣ、ＡＳＩＣ）などのハードウェアや、プログラムにより実現できる。
【０１３４】
特に、本実施形態の処理部１００は、第１分割対象設定部１０２、第１判定部１０４、補助分割面候補生成部１０６、第１評価部１０８、第２判定部１１０、第１決定部１１２、除外フラグ設定部１１４、正規分割面候補生成部１１６、第２評価部１１８、比較部１２０、第２決定部１２２、ノード設定部１２４、分割部１２６、第３判定部１２８、第２分割対象設定部１３０、描画部１３２を含む。なお、これらの一部を省略する構成としてもよい。
【０１３５】
第１分割対象設定部１０２は、操作部２０からの操作情報に基づいて、本実施形態のデータ生成処理の対象となる複数の正規ポリゴンを含む正規ポリゴン集合（オブジェクト）を選択する処理、データ生成の対象となる正規ポリゴン集合を読み込む処理、正規ポリゴン集合を分割対象ポリゴン集合として設定する処理を行う。具体的には第１分割対象設定部１０２は、地形オブジェクトとその地形オブジェクトに配置される建造物オブジェクトとを含む地形オブジェクト群や、建造物の内部構成オブジェクトとその内部構成オブジェクトに配置される物品オブジェクトとを含む屋内環境オブジェクト群など、５００個〜１０００個程度の正規ポリゴンを含む正規ポリゴン集合を分割対象ポリゴン集合として設定する処理を行う。
【０１３６】
第１判定部１０４は、分割対象ポリゴン集合に含まれる正規ポリゴンの数をカウントし、分割対象ポリゴン集合に含まれる正規ポリゴンの数が所定数以上であるか否かを判定する。具体的には第１判定部１０４は、分割対象ポリゴン集合に含まれる正規ポリゴンの数が５１２個以上であるか否かを判定する。
【０１３７】
補助分割面候補生成部１０６は、分割対象ポリゴン集合に含まれる正規ポリゴンの数が所定数以上である場合に、分割対象ポリゴン集合に含まれる正規ポリゴンの頂点に基づいて、複数の補助分割面候補を生成する。具体的には補助分割面候補生成部１０６は、分割対象ポリゴン集合に含まれる正規ポリゴンの頂点に基づいて分割対象ポリゴン集合を含む３次元領域を求め、３次元領域の重心に基づいて複数の補助分割面候補を生成する。また補助分割面候補生成部１０６は、分割対象ポリゴン集合に含まれる正規ポリゴンの頂点の代表点を求め、代表点に基づいて複数の補助分割面候補を生成する。ここで補助分割面候補生成部１０６は、分割対象ポリゴン集合に含まれる正規ポリゴンの頂点の平均値を代表点として求める。そして補助分割面候補生成部１０６は、複数の補助分割面候補のそれぞれに、表裏を示す法線ベクトルを設定する。
【０１３８】
第１評価部１０８は、複数の補助分割面候補のそれぞれについて、分割対象ポリゴン集合に含まれる正規ポリゴンとの位置関係を評価する。具体的には第１評価部１０８は、分割対象ポリゴン集合に含まれる複数の正規ポリゴンのうち、複数の補助分割面候補のうちの１つの補助分割面候補に含まれる正規ポリゴンの数、および１つの補助分割面候補と交差する正規ポリゴンの数、および１つの補助分割面候補の一方側に存在する正規ポリゴンの数の少なくとも１つに基づいて１つの補助分割面候補について第１評価値を求める処理を、複数の補助分割面候補のそれぞれについて行う。そして第１評価部１０８は、第１評価値に基づいて、複数の補助分割面候補から１つの補助分割面候補を選択補助分割面候補として選択する。そして第１評価部１０８は、分割対象ポリゴン集合に含まれる複数の正規ポリゴンのうち、選択補助分割面候補と交差する正規ポリゴンの数および選択補助分割面候補の一方側に存在する正規ポリゴンの数に基づいて、選択補助分割面候補について第２評価値を求める処理を行う。
【０１３９】
第２判定部１１０は、第１評価部１０８の評価結果が所定条件を満たすか否かを判定する。具体的には第２判定部１１０は、選択補助分割面候補についての第２評価値が所定値以下である場合に所定条件を満たすと判定する。
【０１４０】
第１決定部１１２は、第１評価部１０８の評価結果に基づいて、複数の補助分割面候補のうち１つの補助分割面候補を、分割対象ポリゴン集合を分割する分割面として決定する。具体的には第１決定部１１２は、選択補助分割面候補についての第２評価値が所定条件を満たす場合に、選択補助分割面候補を補助分割面として決定する。
【０１４１】
除外フラグ設定部１１４は、複数の補助分割面候補から決定される分割面に、本実施形態により生成されたＢＳＰ木構造を有するデータが用いられた場合に交差判定処理などの処理対象としないことを示す除外フラグを設定する。具体的には除外フラグ設定部１１４は、複数の補助分割面候補のそれぞれに除外フラグを設定するようにしてもよいし、選択補助分割面候補に除外フラグを設定するようにしてもよいし、選択補助分割面候補が分割面として決定されてから分割面に除外フラグを設定するようにしてもよい。
【０１４２】
正規分割面候補生成部１１６は、第１評価部１０８の評価結果が所定条件を満たさない場合に、分割対象ポリゴン集合に含まれる複数の正規ポリゴンのそれぞれを含む面である複数の正規分割面候補を生成する。具体的には正規分割面候補生成部１１６は、選択補助分割面候補についての第２評価値が所定値よりも大きい場合に、正規分割面候補として、分割対象ポリゴン集合に含まれる１つの正規ポリゴンを含み分割対象ポリゴン集合が配置される３次元空間を切断する面を、分割対象ポリゴン集合に含まれる複数の正規ポリゴンのそれぞれについて生成する。そして正規分割面候補生成部１１６は、複数の正規分割面候補のそれぞれが含む正規ポリゴンに設定されている法線ベクトルを、複数の正規分割面候補のそれぞれの表裏を示す法線ベクトルとして設定する。
【０１４３】
また正規分割面候補生成部１１６は、分割対象ポリゴン集合に含まれる正規ポリゴンの数が５１２個よりも小さい場合にも、分割対象ポリゴン集合に含まれる複数の正規ポリゴンのそれぞれを含む面である複数の正規分割面候補を生成する。
【０１４４】
第２評価部１１８は、第１評価部１０８の評価結果が所定条件を満たさない場合に、複数の正規分割面候補のそれぞれについて、分割対象ポリゴン集合に含まれる正規ポリゴンとの位置関係を評価する。具体的には第２評価部１１８は、選択補助分割面候補についての第２評価値が所定値よりも大きい場合に、分割対象ポリゴン集合に含まれる複数の正規ポリゴンのうち、複数の正規分割面候補のうちの１つの正規分割面候補に含まれる正規ポリゴンの数、および１つの正規分割面候補と交差する正規ポリゴンの数、および１つの正規分割面候補の一方側に存在する正規ポリゴンの数の少なくとも１つに基づいて１つの正規分割面候補について第３評価値を求める処理を、複数の正規分割面候補のそれぞれについて行う。そして第２評価部１１８は、第３評価値に基づいて、複数の正規分割面候補から１つの正規分割面候補を選択正規分割面候補として選択する。そして第２評価部１１８は、分割対象ポリゴン集合に含まれる複数の正規ポリゴンのうち、選択正規分割面候補と交差する正規ポリゴンの数および選択正規分割面候補の一方側に存在する正規ポリゴンの数に基づいて、前記選択正規分割面候補について第４評価値を求める処理を行う。
【０１４５】
また第２評価部１１８は、分割対象ポリゴン集合に含まれる正規ポリゴンの数が所定数よりも小さい場合に、複数の正規分割面候補のそれぞれについて、分割対象ポリゴン集合に含まれる正規ポリゴンとの位置関係を評価する。具体的には第２評価部１１８は、分割対象ポリゴン集合に含まれる正規ポリゴンの数が５１２個よりも小さい場合に、分割対象ポリゴン集合に含まれる複数の正規ポリゴンのうち、複数の正規分割面候補のうちの１つの正規分割面候補に含まれる正規ポリゴンの数、および１つの正規分割面候補と交差する正規ポリゴンの数、および１つの正規分割面候補の一方側に存在する正規ポリゴンの数の少なくとも１つに基づいて１つの正規分割面候補について第３評価値を求める処理を、複数の正規分割面候補のそれぞれについて行う。
【０１４６】
比較部１２０は、第１評価部１０８の評価結果が所定条件を満たさない場合に、第１評価部１０８の評価結果と第２評価部１１８の評価結果とを比較する。具体的には比較部１２０は、選択補助分割面候補についての第２評価値が所定値よりも大きい場合に、選択補助分割面候補についての第２評価値と選択正規分割面候補についての第４評価値とを比較する。
【０１４７】
第２決定部１２２は、第１評価部１０８の評価結果が所定条件を満たさない場合に、第２評価部１１８の評価結果に応じた１つの正規分割面候補を分割面として決定する。具体的には第２決定部１２２は、選択補助分割面候補についての第２評価値が所定値よりも大きい場合に、比較部１２０の比較結果に基づいて、選択補助分割面候補および選択正規分割面候補のうち、評価値が小さい方を分割面として決定する。
【０１４８】
また第２決定部１２２は、分割対象ポリゴン集合に含まれる正規ポリゴンの数が所定数よりも小さい場合に、第２評価部１１８の評価結果に応じた１つの正規分割面候補を分割面として決定する。具体的には第２決定部１２２は、分割対象ポリゴン集合に含まれる正規ポリゴンの数が５１２個よりも小さい場合に、第３評価値が最も小さく評価が高い選択正規分割面候補を分割面として決定する。
【０１４９】
ノード設定部１２４は、このようにして決定された分割面を２分木構造を有するデータにおけるルートあるいは中間ノードとして設定する。具体的にはノード設定部１２４は、１回目の分割対象ポリゴン集合を分割する１回目の分割面を、ＢＳＰ木構造のルートとして設定し、２回目以降の分割対象ポリゴン集合を分割する２回目以降の分割面を、ＢＳＰ木構造の中間ノードとして設定する。ここでノード設定部１２４は、親ノードとして設定された分割面の表側の分割後ポリゴン集合を分割する分割面を、親ノードの表側の子ノードとして設定し、親ノードとして設定された分割面の裏側の分割後ポリゴン集合を分割する分割面を、親ノードの裏側の子ノードとして設定する。
【０１５０】
分割部１２６は、分割対象ポリゴン集合を分割面の一方側の分割後ポリゴン集合と、分割面の他方側の分割後ポリゴン集合の２つの分割後ポリゴン集合に分割する。具体的には分割部１２６は、分割面に設定されている法線ベクトルに基づいて、分割対象ポリゴン集合に含まれる正規ポリゴンのうち、分割面よりも表側に存在する正規ポリゴンを表側の分割後ポリゴン集合として設定し、分割面よりも裏側に存在する正規ポリゴンを裏側の分割後ポリゴン集合として設定する。また分割部１２６は、分割面と交差する正規ポリゴンを表側の正規ポリゴンと裏側の正規ポリゴンとに分割して、それぞれを表側の分割後ポリゴン集合または裏側の分割後ポリゴン集合として設定する。
【０１５１】
第３判定部１２８は、２つの分割後ポリゴン集合のそれぞれに含まれる正規ポリゴンの数をカウントし、分割後ポリゴン集合に含まれる正規ポリゴンの数が予め決められた数以下であるか否かを判定する。具体的には第３判定部１２８は、分割後ポリゴン集合に含まれる正規ポリゴンの数が１２８個以下であるか否かを判定する。
【０１５２】
第２分割対象設定部１３０は、正規ポリゴンの数が予め決められた数以下でない分割後ポリゴン集合を分割対象ポリゴン集合として設定する。具体的には第２分割対象設定部１３０は、正規ポリゴンの数が１２８個以下でない分割後ポリゴン集合を、再び分割するために分割対象ポリゴン集合として設定する。
【０１５３】
一方、正規ポリゴンの数が予め決められた数以下である分割後ポリゴン集合については、ノード設定部１２４が、分割後ポリゴン集合に含まれる正規ポリゴンを外部ノードとして設定する。
【０１５４】
描画部１３２は、処理部１００で行われる種々の処理の結果に基づいて描画処理を行い、これにより画像を生成し、表示部３０に出力する。具体的には描画部１３２は、本実施形態のデータ生成処理の対象となるオブジェクトを示す画像を描画する処理や、本実施形態のデータ生成処理により生成されたＢＳＰ木構造を有するデータを示す画像を描画する処理などを行う。
【０１５５】
４．本実施形態の処理
次に、本実施形態で行われる処理の流れの一例についてフローチャートを用いて説明する。
【０１５６】
図１１は、ＢＳＰ木構造を有するデータを生成する処理の概略を示すフローチャート図である。図１１に示すように、ＢＳＰ木構造を有するデータを生成する処理では、まず、データ生成システム１０は、正規ポリゴン集合を分割対象ポリゴン集合として設定し（ステップＳ１０）、分割対象ポリゴン集合を分割する１つの分割面を決定する分割面決定処理を行う（ステップＳ１２）。するとデータ生成システム１０は、決定された分割面の識別情報を、ＢＳＰ木構造を有するデータのノードとして設定し（ステップＳ１４）、決定された分割面で、分割対象ポリゴン集合を表側の分割後ポリゴン集合と裏側の分割後ポリゴン集合とに分割する（ステップＳ１６）。そしてデータ生成システム１０は、各分割後ポリゴン集合について、それぞれに含まれる正規ポリゴンの数をカウントし（ステップＳ２０）、正規ポリゴンの数が１２８個以下である場合には（ステップＳ２２でＹ）、分割後ポリゴン集合に含まれる正規ポリゴンの識別情報を外部ノードとして設定し（ステップＳ２４）、正規ポリゴンの数が１２８個以下でない場合には（ステップＳ２２でＮ）、分割後ポリゴン集合を分割対象ポリゴン集合として設定し（ステップＳ２６）、ステップＳ１２に戻る。
【０１５７】
図１２は、図１１のステップＳ１２の分割面決定処理の詳細を示すフローチャート図である。図１２に示すように、分割面決定処理では、データ生成システム１０は、分割対象ポリゴン集合に含まれる正規ポリゴン数が５１２個以上である場合には（ステップＳ３０でＹ）、分割対象ポリゴン集合に含まれる複数の正規ポリゴンの頂点に基づいて６個の補助分割面候補を生成する補助分割面候補生成処理を行う（ステップＳ３２）。するとデータ生成システム１０は、複数の補助分割面候補のそれぞれについて補助評価処理を行い（ステップＳ３４）、最も評価が高い補助分割面候補を選択補助分割面候補として決定する（ステップＳ３６）。そしてデータ生成システム１０は、選択補助分割面候補についてサイズ評価値を求めるサイズ評価処理を行い（ステップＳ３８）、サイズ評価値が１．１以下である場合には（ステップＳ４０でＹ）、選択補助分割面候補を補助分割面として設定する（ステップＳ４２）。
【０１５８】
一方、サイズ評価値が１．１よりも大きい場合には（ステップＳ４０でＮ）、分割対象ポリゴン集合に含まれる複数の正規ポリゴンのそれぞれを含む複数の正規分割面候補を生成する正規分割面候補生成処理を行う（ステップＳ４４）。するとデータ生成システム１０は、複数の正規分割面候補のそれぞれについて正規評価処理を行い（ステップＳ４６）、最も評価が高い正規分割面候補を選択正規分割面候補として決定する（ステップＳ４８）。そしてデータ生成システム１０は、選択正規分割面候補についてサイズ評価値を求めるサイズ評価処理を行い（ステップＳ５０）、補助分割面候補と正規分割面候補のサイズ評価値を比較し（ステップＳ５２）、選択補助分割面候補と選択正規分割面候補のうちサイズ評価値が小さい方を分割面として設定する（ステップＳ５４）。
【０１５９】
また、ステップＳ３０において、分割対象ポリゴン集合に含まれる正規ポリゴン数が５１２個以上でない場合には（ステップＳ３０でＮ）、分割対象ポリゴン集合に含まれる複数の正規ポリゴンのそれぞれを含む複数の正規分割面候補を生成する正規分割面候補生成処理を行う（ステップＳ５６）。するとデータ生成システム１０は、複数の正規分割面候補のそれぞれについて正規評価処理を行い（ステップＳ５８）、最も評価が高い正規分割面候補を選択正規分割面候補として決定する（ステップＳ６０）。そしてデータ生成システム１０は、選択正規分割面候補を分割面として設定する（ステップＳ６２）。
【０１６０】
図１３は、図１２のステップＳ３２の補助分割面候補生成処理の詳細を示すフローチャート図である。図１３に示すように、補助分割面候補生成処理では、データ生成システム１０は、分割対象ポリゴン集合を含むバウンディングボックスを求め（ステップＳ７０）、バウンディングボックスの重心を通る３つの面を補助分割面候補とする（ステップＳ７２）。またデータ生成システム１０は、分割対象ポリゴン集合に含まれる正規ポリゴンの頂点の平均位置を求め（ステップＳ７４）、この平均位置を通る３つの面を補助分割面候補とする（ステップＳ７６）。
【０１６１】
図１４は、図１２のステップＳ３４の補助評価処理の詳細を示すフローチャート図である。図１４に示すように、補助評価処理では、データ生成システム１０は、図１２のステップＳ３２の補助分割面候補生成処理で生成された複数の補助分割面候補のうち、１つの補助分割面候補を評価対象として設定し（ステップＳ８０）、分割対象ポリゴン集合に含まれる正規ポリゴンのうち、評価対象と交差する正規ポリゴンの数に基づいて交差評価成分を求め（ステップＳ８２）、分割対象ポリゴン集合に含まれる正規ポリゴンのうち、評価対象と同一面上にある正規ポリゴンの数に基づいて平行評価成分を求め（ステップＳ８４）、分割対象ポリゴン集合に含まれる正規ポリゴンのうち、評価対象の一方側の正規ポリゴンの数に基づいてバランス評価成分を求める（ステップＳ８６）。そしてデータ生成システム１０は、交差評価成分と平行評価成分とバランス評価成分とに基づいて補助評価値を求める（ステップＳ８８）。そして、全ての補助分割面候補について補助評価値を求めた場合には（ステップＳ９０でＹ）、補助評価処理を終了し、未だ評価対象としていない補助分割面候補がある場合には（ステップＳ９０でＮ）、ステップＳ８０に戻る。
【０１６２】
図１５は、図１２のステップＳ４６あるいはステップＳ５８の正規評価処理の詳細を示すフローチャート図である。図１５に示すように、正規評価処理では、データ生成システム１０は、図１２のステップＳ４４あるいはステップＳ５６の正規分割面候補生成処理で生成された複数の正規分割面候補のうち、１つの正規分割面候補を評価対象として設定し（ステップＳ１００）、分割対象ポリゴン集合に含まれる正規ポリゴンのうち、評価対象と交差する正規ポリゴンの数に基づいて交差評価成分を求め（ステップＳ１０２）、分割対象ポリゴン集合に含まれる正規ポリゴンのうち、評価対象と同一面上にある正規ポリゴンの数に基づいて平行評価成分を求め（ステップＳ１０４）、分割対象ポリゴン集合に含まれる正規ポリゴンのうち、評価対象の一方側の正規ポリゴンの数に基づいてバランス評価成分を求める（ステップＳ１０６）。そしてデータ生成システム１０は、交差評価成分と平行評価成分とバランス評価成分とに基づいて正規評価値を求める（ステップＳ１０８）。そして、全ての正規分割面候補について正規評価値を求めた場合には（ステップＳ１１０でＹ）、正規評価処理を終了し、未だ評価対象としていない正規分割面候補がある場合には（ステップＳ１１０でＮ）、ステップＳ１００に戻る。
【０１６３】
５．変形例
上記実施形態で説明した手法は、一例を示したに過ぎず、上記実施形態の手法と同様の効果を奏する均等な手法を採用した場合においても本発明の範囲に含めることができる。また本発明は、上記実施形態で説明したものに限らず、種々の変形実施が可能である。そして上記実施形態の手法や、変形例として後述する各種の手法は、本発明を実現する手法として適宜組み合わせて採用することができる。
【０１６４】
例えば、上記実施形態で例に挙げた数や数式は一例を挙げたものであり、適宜異なる数や数式を用いることができる。
【０１６５】
また、上記実施形態では、分割対象ポリゴン集合に含まれる正規ポリゴンの数が所定数以上でない場合に（図１２のステップＳ３０でＮ）、複数の正規分割面候補のそれぞれについて、分割対象ポリゴン集合に含まれる正規ポリゴンとの位置関係を評価する正規評価処理（図１２のステップＳ５８）が行われる例を挙げて説明したが、分割対象ポリゴン集合に含まれる正規ポリゴンの数に関わらず、複数の正規分割面候補のそれぞれについて、分割対象ポリゴン集合に含まれる正規ポリゴンとの位置関係を評価する正規評価処理を行うようにしてもよい。すなわち図１２に示す分割面決定処理として、図１２のステップＳ５６〜ステップＳ６２までの処理を行うようにしてもよい。
【０１６６】
また、上記実施形態では、選択補助分割面候補についての第２評価値が所定値以下でない場合に（図１２のステップＳ４０でＮ）、選択正規分割面候補のサイズ評価処理（図１２のステップＳ５０）およびサイズ評価値の比較処理（図１２のステップＳ５２）を行い、選択補助分割面候補および選択正規分割面候補のうち、評価値が小さい方を分割面として決定する（図１２のステップＳ５４）例を挙げて説明したが、選択補助分割面候補についての第２評価値が所定値以下でない場合に（図１２のステップＳ４０でＮ）、選択正規分割面候補のサイズ評価処理（図１２のステップＳ５０）およびサイズ評価値の比較処理（図１２のステップＳ５２）を省略し、図１２のステップＳ５４に代えて、図１２のステップＳ４８で決定された選択正規分割面候補を分割面として決定するようにしてもよい。
【０１６７】
また、上記実施形態では、選択補助分割面候補についての第２評価値が所定値以下であるか否かを判断する（図１２のステップＳ４０）例を挙げて説明したが、選択補助分割面候補のサイズ評価処理（図１２のステップＳ３８）を省略し、図１２のステップＳ４０に代えて、図１２のステップＳ３４で求められた選択補助分割面候補についての第１評価値が所定値以下であるか否かを判断するようにしてもよい。
【符号の説明】
【０１６８】
Ｏ  オブジェクト、Ｒ  正規ポリゴン、ＲＣ  正規分割面候補、
ＳＲＣ  選択正規分割面候補、ＲＤ  正規分割面、ＡＣ  補助分割面候補、
ＳＡＣ  選択補助分割面候補、ＡＤ  補助分割面、
１０  データ生成システム、２０  操作部、３０  表示部、４０  情報記憶媒体、
５０  記憶部、６０  通信部、１００  処理部、１０２  第１分割対象設定部、
１０４  第１判定部、１０６  補助分割面候補生成部、１０８  第１評価部、
１１０  第２判定部、１１２  第１決定部、１１４  除外フラグ設定部、
１１６  正規分割面候補生成部、１１８  第２評価部、１２０  比較部、
１２２  第２決定部、１２４  ノード設定部、１２６  分割部、１２８  第３判定部、
１３０  第２分割対象設定部、１３２  描画部、
【図１】
2011053778.tif 000003
【図２】
2011053778.tif 000004
【図３】
2011053778.tif 000005
【図４】
2011053778.tif 000006
【図５】
2011053778.tif 000007
【図６】
2011053778.tif 000008
【図７】
2011053778.tif 000009
【図８】
2011053778.tif 000010
【図９】
2011053778.tif 000011
【図１０】
2011053778.tif 000012
【図１１】
2011053778.tif 000013
【図１２】
2011053778.tif 000014
【図１３】
2011053778.tif 000015
【図１４】
2011053778.tif 000016
【図１５】
2011053778.tif 000017