(57)【特許請求の範囲】
【請求項１】
入力されたポリゴンの頂点データに基づいて、頂点、辺および面の接続情報に関する接続データを生成する初期接続データ生成部と、
前記接続データに基づいて新たな接続データを生成する新規接続データ生成部と、
前記頂点データおよび前記接続データに基づいて新たな頂点データを生成する新規頂点データ生成部と、
同一の頂点に関する前記新たな接続データを合成するデータ合成部と、
前記初期接続データ生成部および前記新規接続データ生成部で生成された接続データと、前記データ合成部で合成された接続データと、を格納する接続データ格納部と、
入力された頂点データと前記新規頂点データ生成部で生成された頂点データとを格納する頂点データ格納部と、を備え、
前記新規接続データ生成部は、前記接続データ格納部に格納された接続データに基づいて、繰り返し前記新たな接続データを生成し、
前記新規頂点データ生成部は、前記接続データ格納部に格納された接続データと前記頂点データ格納部に格納された頂点データとに基づいて、繰り返し前記新たな頂点データを生成することを特徴とするポリゴンデータ生成装置。
【請求項２】
前記接続データ格納部は、
前記初期接続データ生成部で生成された接続データを少なくとも格納する第１接続データ格納部と、
前記新規接続データ生成部で生成された新たな接続データを格納する第２接続データ格納部と、を有し、
前記データ合成部は、前記第２接続データ格納部に格納されている接続データに基づいて合成処理を行い、合成後の接続データを前記第１接続データ格納部に格納することを特徴とする請求項１に記載のポリゴンデータ生成装置。
【請求項３】
前記頂点データの一部を構成する頂点座標を格納するとともに、これら格納された頂点座標と、入力された前記頂点データの中に含まれる頂点座標とが一致するか否かを判別する連想メモリを備え、
前記初期接続データ生成部は、前記連想メモリで一致すると判別されると、該当する頂点に関する接続データを前記接続データ格納部から読み出して、読み出した接続データに新たな接続情報を追加して前記接続データ格納部に格納し、前記連想メモリで一致しないと判別されると、入力された頂点に関する接続データを生成して前記接続データ格納部に格納することを特徴とする請求項１に記載のポリゴンデータ生成装置。
【請求項４】
前記初期接続データ生成部は、新たに入力された頂点データに関する接続情報を接続データに追加する際、ポリゴンを構成する各頂点データが時計回りまたは反時計回りのどちらに入力されたかを示す情報と、その頂点が奇数番目または偶数番目のどちらに入力されたかを示す情報と、に基づいて、接続データのどこに接続情報を追加するかを設定することを特徴とする請求項１に記載のポリゴンデータ生成装置。
【請求項５】
前記初期接続データ生成部は、新たに頂点データが入力されると、着目している頂点の接続データの先頭または最後尾に、新たに入力された頂点データに対応する接続情報を追加することを特徴とする請求項１に記載のポリゴンデータ生成装置。
【請求項６】
前記初期接続データ生成部は、新たに頂点データが入力されると、その二つ前と一つ前に入力された各頂点データに対応する接続データにそれぞれ、新たに入力された頂点データに対応する接続情報を追加することを特徴とする請求項１に記載のポリゴンデータ生成装置。
【請求項７】
前記初期接続データ生成部は、新たに頂点データが入力されると、その二つ前と一つ前に入力された各頂点データに対応する接続データのうち、いずれか一方の接続データの先頭に新たに入力された頂点データに対応する接続情報を追加し、他方の接続データの最後尾に新たに入力された頂点データに対応する接続情報を追加することを特徴とする請求項６に記載のポリゴンデータ生成装置。
【請求項８】
前記頂点データは、頂点の座標と、頂点の法線ベクトルと、頂点のテクセル座標とを含み、
前記接続データは、頂点を含む辺の数と、頂点を含む面の数と、頂点を含む辺の番号および該辺の他方の端点の番号と、頂点を含む面の番号と、該面の対角線上にある頂点の番号または他の頂点を挟んで隣り合う頂点の番号とを含むことを特徴とする請求項１に記載のポリゴンデータ生成装置。
【請求項９】
前記新規接続データ生成部は、新規に生成される頂点の番号、辺の番号および面の番号として、互いに重複しない固有かつ連続的な番号を割り振ることを特徴とする請求項１に記載のポリゴンデータ生成装置。
【請求項１０】
前記新規頂点データ生成部は、入力された前記頂点データが三角形を組み合わせたデータ構造のポリゴンの場合には、新規に生成される面の番号として、新規生成前の面の番号の３倍の番号、（３倍＋１）の番号、および（３倍＋２）の番号を割り振ることを特徴とする請求項９に記載のポリゴンデータ生成装置。
【請求項１１】
前記新規頂点データ生成部は、入力された前記頂点データが四角形を組み合わせたデータ構造のポリゴンの場合には、新規に生成される面の番号として、新規生成前の面の番号の４倍の番号、（４倍＋１）の番号、（４倍＋２）、および（４倍＋３）の番号を割り振ることを特徴とする請求項９に記載のポリゴンデータ生成装置。
【請求項１２】
前記新規接続データ生成部は、新規生成前の頂点に関する接続データ、新規生成前の辺を分割して生成された頂点に関する接続データ、および新規生成前の面を分割して生成された頂点に関する接続データの順に、前記接続データ格納部に格納することを特徴とする請求項１に記載のポリゴンデータ生成装置。
【請求項１３】
初期ポリゴンの頂点データを出力する初期頂点データ出力装置と、
前記初期頂点データ出力装置から出力された頂点データに基づいて、前記初期ポリゴンの新たな頂点データおよび接続データを生成するポリゴンデータ生成装置と、
前記ポリゴンデータ生成装置で生成された頂点データおよび接続データに基づいて描画処理を行う描画処理装置と、を備え、
前記ポリゴンデータ生成装置は、
入力されたポリゴンの頂点データに基づいて、頂点、辺および面の接続情報に関する接続データを生成する初期接続データ生成部と、
前記接続データに基づいて新たな接続データを生成する新規接続データ生成部と、
前記頂点データおよび前記接続データに基づいて新たな頂点データを生成する新規頂点データ生成部と、
同一の頂点に関する前記新たな接続データを合成するデータ合成部と、
前記初期接続データ生成部および前記新規接続データ生成部で生成された接続データと、前記データ合成部で合成された接続データと、を格納する接続データ格納部と、
入力された頂点データと前記新規頂点データ生成部で生成された頂点データとを格納する頂点データ格納部と、を備え、
前記新規接続データ生成部は、前記接続データ格納部に格納された接続データと前記頂点データ格納部に格納された頂点データとに基づいて、繰り返し前記新たな接続データを生成することを特徴とする描画システム。
【請求項１４】
前記新規接続データ生成部、前記頂点データ生成部および前記データ合成部の各処理を行う演算処理部を有することを特徴とする請求項１３に記載の描画システム。
【請求項１５】
前記頂点データの一部を構成する頂点座標を格納するとともに、これら格納された頂点座標と、入力された前記頂点データの中に含まれる頂点座標とが一致するか否かを判別する連想メモリを備え、
前記初期接続データ生成部は、前記連想メモリで一致すると判別されると、該当する頂点に関する接続データを前記接続データ格納部から読み出して、読み出した接続データに新たな接続情報を追加して前記接続データ格納部に格納し、前記連想メモリで一致しないと判別されると、入力された頂点に関する接続データを生成して前記接続データ格納部に格納することを特徴とする請求項１３に記載の描画システム。
【請求項１６】
前記初期接続データ生成部は、新たに入力された頂点データに関する接続情報を接続データに追加する際、ポリゴンを構成する各頂点データが時計回りまたは反時計回りのどちらに入力されたかを示す情報と、その頂点が奇数番目または偶数番目のどちらに入力されたかを示す情報と、に基づいて、接続データのどこに接続情報を追加するかを設定することを特徴とする請求項１３に記載の描画システム。
【請求項１７】
前記初期接続データ生成部は、新たに頂点データが入力されると、着目している頂点の接続データの先頭または最後尾に、新たに入力された頂点データに対応する接続情報を追加することを特徴とする請求項１３に記載の描画システム。
【請求項１８】
前記初期接続データ生成部は、新たに頂点データが入力されると、その二つ前と一つ前に入力された各頂点データに対応する接続データにそれぞれ、新たに入力された頂点データに対応する接続情報を追加することを特徴とする請求項１３に記載の描画システム。
【請求項１９】
前記新規接続データ生成部は、新規生成前の頂点に関する接続データ、新規生成前の辺を分割して生成された頂点に関する接続データ、および新規生成前の面を分割して生成された頂点に関する接続データの順に、前記接続データ格納部に格納することを特徴とする請求項１３に記載の描画システム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、三次元オブジェクトをポリゴン（多角形）の集合体として描画するためのポリゴンデータの生成を行うポリゴンデータ生成装置、描画システムおよびポリゴンデータ生成方法に関する。
【０００２】
【従来の技術】
三次元グラフィックスを実現するためには、ＣＰＵとグラフィック制御チップ（以下、ＧＰＵ）が共同して処理を行う。三次元オブジェクトは、ポリゴンの集合体として描画を行うのが一般的であり、曲面の滑らかなオブジェクトを表示するには、オブジェクトを多数のポリゴンに分割する必要がある。
【０００３】
【発明が解決しようとする課題】
しかしながら、オブジェクトを多数のポリゴンに分割すると、ＣＰＵとＧＰＵとの間でやり取りされるデータ量が増えるため、曲面の滑らかさはＣＰＵとＧＰＵとの間のバスバンド幅により制限されてしまう。
【０００４】
一方、多面体をどんどん細かく細分割していくことで、三次元オブジェクトの曲面を滑らかにする細分割曲面(subdivision surface)処理が提案されている。
【０００５】
細分割曲面処理をソフトウェアで実装する場合、複雑で大量のリスト処理をＣＰＵが行うことになるため、ＣＰＵの処理負担が大きく、性能向上が図れないという問題がある。
【０００６】
本発明は、このような点に鑑みてなされたものであり、その目的は、曲面の滑らかな三次元オブジェクトを高速に描画できるポリゴンデータ生成装置、描画システムおよびポリゴンデータ生成方法を提供することにある。
【０００７】
【課題を解決するための手段】
上述した課題を解決するために、本発明に係るポリゴンデータ生成装置は、入力されたポリゴンの頂点データに基づいて、頂点、辺および面の接続情報に関する接続データを生成する初期接続データ生成部と、前記接続データに基づいて新たな接続データを生成する新規接続データ生成部と、前記頂点データおよび前記接続データに基づいて新たな頂点データを生成する新規頂点データ生成部と、同一の頂点に関する前記新たな接続データを合成するデータ合成部と、前記初期接続データ生成部および前記新規接続データ生成部で生成された接続データと、前記データ合成部で合成された接続データと、を格納する接続データ格納部と、入力された頂点データと前記新規頂点データ生成部で生成された頂点データとを格納する頂点データ格納部と、を備え、前記新規接続データ生成部は、前記接続データ格納部に格納された接続データに基づいて、繰り返し前記新たな接続データを生成し、前記新規頂点データ生成部は、前記接続データ格納部に格納された接続データと前記頂点データ格納部に格納された頂点データとに基づいて、繰り返し前記新たな頂点データを生成する。
【０００８】
また、本発明に係る描画システムは、初期ポリゴンの頂点データを出力する初期頂点データ出力装置と、前記初期頂点データ出力装置から出力された頂点データに基づいて、前記初期ポリゴンの新たな頂点データおよび接続データを生成するポリゴンデータ生成装置と、前記ポリゴンデータ生成装置で生成された頂点データおよび接続データに基づいて描画処理を行う描画処理装置と、を備え、前記ポリゴンデータ生成装置は、入力されたポリゴンの頂点データに基づいて、頂点、辺および面の接続情報に関する接続データを生成する初期接続データ生成部と、前記接続データに基づいて新たな接続データを生成する新規接続データ生成部と、前記頂点データおよび前記接続データに基づいて新たな頂点データを生成する新規頂点データ生成部と、同一の頂点に関する前記新たな接続データを合成するデータ合成部と、前記初期接続データ生成部および前記新規接続データ生成部で生成された接続データと、前記データ合成部で合成された接続データと、を格納する接続データ格納部と、入力された頂点データと前記新規頂点データ生成部で生成された頂点データとを格納する頂点データ格納部と、を備え、前記新規接続データ生成部は、前記接続データ格納部に格納された接続データと前記頂点データ格納部に格納された頂点データとに基づいて、繰り返し前記新たな接続データを生成する。
【０００９】
【発明の実施の形態】
以下、本発明に係るについて、図面を参照しながら具体的に説明する。
【００１０】
以下、本発明に係るポリゴンデータ生成装置、描画システムおよびポリゴンデータ生成方法 の一実施形態について、図面を参照しながら具体的に説明する。
【００１１】
図１は本発明に係るポリゴンデータ生成装置の一実施形態のブロック図である。図１のポリゴンデータ生成装置には、ポリゴンの頂点データが時計回りまたは反時計回りの順に入力される。以下では、反時計回りに入力される例について説明するが、時計回りに入力される場合も同様の処理が行われる。
【００１２】
図１のポリゴンデータ生成装置は、入力されたポリゴンの頂点データに基づいて後述する接続データを生成する初期接続データ生成部１と、生成された接続データを格納する第１接続データ格納部２と、入力された頂点データを格納する第１頂点データ格納部３と、後述する細分割曲面処理を行って新たな接続データを生成する新規接続データ生成部４と、元の接続データに基づいて新たな頂点データを生成する新規頂点データ生成部５と、生成された新たな接続データを格納する第２接続データ格納部６と、生成された新たな頂点データを格納する第２頂点データ格納部７と、同一頂点に関する複数の接続データを合成するデータ合成部８とを備えている。
【００１３】
図２は本実施形態に係るポリゴンデータ生成装置の全体的な処理動作を示すフローチャートである。
【００１４】
まず、初期接続データ生成部１は、入力されたラフな初期ポリゴンの頂点データに基づいて接続データを生成する（ステップＳ１）。生成された接続データは第１接続データ格納部２に格納され、入力された頂点データは第１頂点データ格納部３に格納される（ステップＳ２）。
【００１５】
続いて、新規頂点データ生成部４と新規頂点データ生成部５は、第１接続データ格納部２に格納されている接続データと第１頂点データ格納部３に格納されている頂点データとに基づいて、後述する細分割曲面処理を行って新たな接続データと頂点データを生成する（ステップＳ３）。新たに生成された接続データは第２接続データ格納部６に格納され、新たに生成された頂点データは第２頂点データ格納部７に格納される（ステップＳ４）。
【００１６】
続いて、データ合成部８は、同一の頂点に関する接続データ同士を合成する（ステップＳ５）。合成された接続データは第１接続データ格納部２に格納され、第２頂点データ格納部７に格納されている頂点データは第１頂点データ格納部３に格納される（ステップＳ６）。
【００１７】
上述したステップＳ３〜Ｓ６の処理は、ポリゴンの曲面が十分に細かく細分割されるまで繰り返される（ステップＳ７）。
【００１８】
具体例として、図３のポリゴンの細分割処理について説明する。なお、図３ではポリゴンを構成する各面が四角形の例を示しているが、面の形状は三角形でもよい。
【００１９】
図１のポリゴンデータ生成装置には、図３のポリゴンの頂点データが反時計回りの順に入力される。初期接続データ生成部１は、ポリゴンの頂点、辺および面に図３のように固有かつ連続的な番号を割り振って接続データを生成する。図３では、頂点の番号をｖ１〜ｖ８、辺の番号をｅ０〜ｅ３、面の番号をｆ０〜ｆ３としている。
【００２０】
初期接続データ生成部１に入力される頂点データは、頂点座標、頂点の法線ベクトル、および頂点のテクセル座標などからなる。ここで、頂点の法線ベクトルとは、その頂点とその近傍の頂点とから成る曲面のうちその頂点を含む微小平面の法線ベクトルを示し、頂点のテクセル座標とは、テクスチャ・マッピングを行う場合の座標位置を示している。
【００２１】
また、初期接続データ生成部１が生成する接続データは、図４（ａ）に示すように、頂点を含む辺の数と、頂点を含む面の数と、頂点を含む辺の番号および当該辺の他方の端点の番号と、頂点を含む面の番号および当該面の対角線上にある頂点の番号または他の頂点を挟んで隣り合う頂点の番号と、などからなる。
【００２２】
なお、本明細書では、頂点を符号"ｖ"、辺を符号"ｅ"、面を符号"ｆ"で表す。例えば、図３のポリゴンの頂点ｖ０に関する頂点データが初期接続データ生成部１に入力されると、図４（ａ）に示すような接続データが生成される。頂点を含む辺の数は４、頂点を含む面の数は４、頂点を含む辺の番号および当該辺の他方の端点の番号は(e1,v3),(e2、v5),(e3,v7),(e0,v1)、頂点を含む面の番号および当該面の対角線上にある頂点の番号あるいは他の頂点を挟んで隣り合う頂点の番号は(f1,v4),(f2,v6),(f3,v8),(f0,v2)である。
【００２３】
以後の説明では、簡略化のため、接続データを図４（ｂ）のように、（頂点を含む辺の数、頂点を含む面の数、接続データが他にあるかどうかを示す識別子）と、（辺の番号、辺のもう一方の端点の番号）と、（面の番号、面の対角線上にある頂点あるいは二つ隣の頂点の番号）とで表す。
【００２４】
「接続データが他にあるかどうかを示す識別子には、接続データが他にないことを示す"false"と、接続データが他にあることを示す"true"の２種類がある。
【００２５】
例えば、図４（ａ）を図４（ｂ）の形式で表すと、図４（ｃ）のようになる。
【００２６】
図５は初期接続データ生成部１の処理動作を示すフローチャートであり、三角形の頂点データが入力された場合の処理動作を示している。まず、入力された頂点データと同一の頂点データが過去に入力されたか否かを判定する（ステップＳ１１）。ここでは、第１頂点データ格納部３を検索して、同一の頂点データが存在するか否かを調べる。
【００２７】
この結果、同一の頂点データが第１頂点データ格納部３に格納されていなければ、この頂点に新たな番号を付けて初期接続データ生成部１のエントリーに追加しておく（ステップＳ１２）。ここで、エントリーに追加とは、新たな接続データとして登録することを意味する。
【００２８】
一方、すでに同一の頂点データが第１頂点データ格納部３に格納されていれば、対応する接続データを第１接続データ格納部２から読み出しておく。
【００２９】
続いて、入力された頂点と以前に入力された二つの頂点とで構成される三角形の接続情報を各頂点の接続データに追加する（ステップＳ１３）。
【００３０】
例えば、図６のように、頂点ｖ０，ｖ１がすでに入力されていて、ここに頂点ｖ２の頂点データが新たに入力されたとする。図６では、頂点番号をｖ０，ｖ１，ｖ２、辺番号をｅ０，ｅ１，ｅ２、面番号をｆ０としている。
【００３１】
この場合、頂点ｖ０，ｖ１の接続データに頂点ｖ２との接続情報が追加される。このとき、頂点ｖ２が奇数番目に入力されたデータであるとすると、その一つ前に入力された頂点、すなわち偶数番目に入力された頂点ｖ１の接続データには、図７に示すように直前に登録された辺情報(e0,v0)の直前に頂点ｖ２との接続情報(e2,v2)(-f0,don't care)が追加される。また、二つ前に入力された頂点、すなわち奇数番目に入力された頂点ｖ０の接続データには、図８に示すように直前に登録された辺情報(e0,v1)(-f0,don't care)の直後に頂点ｖ２との接続情報(e1,v2)が追加される。一方、新たに追加された頂点ｖ２の接続データは図９のようになる。
【００３２】
なお、図７〜図９において、面番号の前の符号はその面が三角形なのか四角形なのかを示しており、例えば三角形の場合はマイナス符号、四角形の場合はプラス符号になる。また、"don't care"とは、面の対角の頂点がないことを意味している。
【００３３】
その後、図１０（ａ）に示すように頂点ｖ３の頂点データが新たに入力されたとする。このとき、頂点ｖ１の接続データには、図１１に示すようにデータの先頭に頂点ｖ３との接続情報が追加される。また、頂点ｖ２の接続データには、図１２（ａ）に示すようにデータの最後尾に頂点ｖ３との接続情報が追加され、頂点ｖ３の接続データは図１３のようになる。
【００３４】
例えば、図１０（ｂ）に示すように、頂点ｖ３以外に頂点ｖ４が存在したとすると、この場合の頂点ｖ２の接続データは、図１２（ｂ）のようになる。この場合、面ｆ１の対角線上に頂点ｖ３が存在するため、"don't care"にはならず、(f1,v3)になる。
【００３５】
再び図５に戻って、初期接続データ生成部１の処理動作を説明する。上述した図５のステップＳ１１において、同一の頂点に関する頂点データが入力されたと判定された場合は、反時計回りの頂点データが入力されたか否かを判断し（ステップＳ１４）、反時計回りでなければ、奇数番目の頂点データか否かを判断し（ステップＳ１５）、反時計回りであれば、奇数番目の頂点データか否かを判断する（ステップＳ１６）。
【００３６】
ステップＳ１５で奇数番目でないと判断されるか、あるいはステップＳ１６で奇数番目と判断されると、二つ前に入力された頂点の接続データ中の先頭行の辺と追加しようとする辺が等しいか否かを判断する（ステップＳ１７）。
【００３７】
等しくないと判断されると、接続データに辺情報と面情報を追加し（ステップＳ１８）、等しいと判断されると、面情報だけを接続データに追加し、着目している頂点の周囲が連続したポリゴンで囲まれたと判断する（ステップＳ１９）。
【００３８】
ステップＳ１８またはＳ１９の処理が終了すると、次に、一つ前に入力された頂点の接続データ中の最終行の辺と追加しようとする辺が等しいか否かを判断する（ステップＳ２０）。
【００３９】
等しくないと判断されると、接続データに辺情報と面情報を追加し（ステップＳ２１）、等しいと判断されると、面情報だけを接続データに追加し、着目している頂点の周囲が連続したポリゴンで囲まれたと判断する（ステップＳ２２）。
この場合、これ以上新たに情報を追加することがないため、その頂点に対応する接続データが初期接続データ生成部１のエントリから削除される。
【００４０】
一方、ステップＳ１５で奇数番目と判断されるか、あるいはステップＳ１６で奇数番目でないと判断されると、二つ前に入力された頂点の接続データ中の最終行の辺と追加しようとする辺が等しいか否かを判断する（ステップＳ２３）。
【００４１】
等しくないと判断されると、接続データに辺情報と面情報が追加され（ステップＳ２４）、等しいと判断されると、面情報だけが接続データに追加され、着目している頂点の周囲が連続したポリゴンで囲まれたと判断する（ステップＳ２５）。
【００４２】
ステップＳ２４またはＳ２５の処理が終了すると、次に、一つ前に入力された頂点の接続データ中の先頭行の辺と追加しようとする辺が等しいか否かを判断する（ステップＳ２６）。
【００４３】
等しくないと判断されると、接続データに辺情報と面情報を追加し（ステップＳ２７）、等しいと判断されると、面情報だけを接続データに追加し、着目している頂点の周囲が連続したポリゴンで囲まれたと判断する（ステップＳ２８）。
【００４４】
次に、初期接続データ生成部１が図１４のポリゴンの接続データを生成する例について説明する。
【００４５】
例えば、図１４に示すように、頂点ｖ１〜ｖ７の頂点データがすでに入力され、このときの頂点ｖ３の接続データが図１５で表され、頂点ｖ５，ｖ７の接続データがそれぞれ図１６（ａ）、図１６（ｂ）で表されているとする。
【００４６】
また、すでに入力された頂点データのうち、２つ前に頂点ｖ３の頂点データが入力され、１つ前に頂点ｖ７の頂点データが入力され、次に頂点ｖ５の頂点データが入力されたとする。
【００４７】
この場合、図１７に示すように、頂点ｖ３，ｖ７の接続データに、辺e13と面ｆ６に関する情報が追加される。具体的には、頂点ｖ３，ｖ５から成る辺ｅ７はすでに存在するため、頂点ｖ３の接続データには図１８に示すように面ｆ６の情報のみが追加され、頂点ｖ５とｖ７の各接続データにはそれぞれ図１９（ａ）、図１９（ｂ）に示すように辺ｅ13，面ｆ６の情報が追加される。
【００４８】
また、ポリゴンの種類によっては、図２０に示すように接続データが複数に分かれてしまう場合がある。図２０の場合、頂点ｖ３については、頂点ｖ０，ｖ１，ｖ２，ｖ４，ｖ５からなる図２１（ａ）に示す接続データと、頂点ｖ６，ｖ７，ｖ８，ｖ９からなる図２１（ｂ）に示す接続データとが生成される。同一の頂点について複数の接続データが他に存在する場合は、図２１（ａ）に示すように接続データ中に"true"識別子が記述される。
【００４９】
以上の処理により、図１の初期接続データ生成部１ですべての接続データが生成されると、図１の新規接続データ生成部４、新規頂点データ生成部５およびデータ合成部８は、第１接続データ格納部２に格納された接続データと第１頂点データ格納部３に格納された頂点データに基づいて細分割曲面(subdivision surface)処理を行う。
【００５０】
図２２は細分割曲面処理の一手法であるcatmull-clark法の処理手順を示すフローチャートであり、図２のステップＳ３〜Ｓ６の処理手順を詳細に説明したものである。
【００５１】
まず、新規接続データ生成部４は、着目している頂点ｖと、その頂点ｖが属する面の対角の点Ｆiと、辺の端点ｅiとに基づいて、新たに生成する面の番号と辺の番号とを計算し、新規接続データを生成する（ステップＳ３１）。
【００５２】
続いて、新規頂点データ生成部５は着目している頂点ｖと、面の対角の点Ｆiと、辺の端点ｅiとに基づいて、（１）式に従って面の重心を計算する（ステップＳ３２）。以下では、面の重心を面ポイントと呼ぶ。
【００５３】
【数１】
0003702244.tif 000002
新規頂点データ生成部５は、頂点ｖの周りのすべての面ポイントを計算するまで、ステップＳ３２の処理を繰り返す（ステップＳ３３）。
【００５４】
面ポイントの計算が終了すると、新規頂点データ生成部５は、着目している頂点ｖと、辺の両側の面の重心ｆi-1，ｆiと、辺の端点ｅiとに基づいて、（２）式に従って辺ポイントを計算する（ステップＳ３４）。
【００５５】
【数２】
0003702244.tif 000003
ここで、辺ポイントとは、辺を分割する頂点であり、例えば図２３では、辺ポイントを二重丸で示している。例えば、図２３の辺ポイントep1は、分割しようとしている辺の両端点ｖ，ｅ２と、面ｆ１の重心と、面ｆ２の重心とで囲まれる面の重心を表している。生成された辺ポイントは、元の頂点と周囲の面の重心とで新たな面を形成する。
【００５６】
新規頂点データ生成部５は、頂点ｖに関してすべての辺ポイントが求まるまで、ステップＳ３４の処理を繰り返す（ステップＳ３５）。
【００５７】
続いて、新規頂点データ生成部５は、元の頂点の座標を（３）式に従ってずらす（ステップＳ３６）。
【００５８】
【数３】
0003702244.tif 000004
新規頂点データ生成部５は、上述したステップ３１〜３６の処理を、元からあるすべての頂点について行い、各頂点ごとに、上述した面ポイントと辺ポイントを計算する（ステップＳ３７）。
【００５９】
続いて、データ合成部８は、ステップＳ３１〜Ｓ３７で生成された面ポイントと辺ポイントに対応する新規接続データを合成する（ステップＳ３８）。すなわち、同一の面ポイントや辺ポイントに対応する接続データをまとめる処理を行う。
【００６０】
合成後の新規接続データは第１接続データ格納部２に格納され、新規頂点データは第１頂点データ格納部３に格納される（ステップＳ３９）。
【００６１】
以上の処理が元の頂点、新たに生成された面ポイントおよび辺ポイントのそれぞれについて、繰り返し行われる（ステップＳ４０）。これにより、入力された初期ポリゴンを十分に細分割することができる。
【００６２】
図２４は新規頂点データ生成部５で生成された面ポイントと辺ポイントを格納する第２頂点データ格納部７のテーブル構成を示す図である。図示のように、第２頂点データ格納部７は、初期ポリゴンの頂点の座標データを（３）式の計算により変更した座標データ０〜ｖn-1、辺ポイントの座標データｖn〜ｖn+en-1および面ポイントの座標データｖn+en〜ｖn+en+fn-1の順に格納する。座標データ０〜ｖn-1は元のポリゴンの頂点０〜ｖn-1に対応づけられ、座標データｖn〜ｖn+en-1は元のポリゴンの辺０〜ｅn-1に対応付けられ、座標データｖn+en〜ｖn+en+fn-1は元のポリゴンの面０〜ｆn-1に対応づけられている。
【００６３】
ところで、図２２に示した細分割曲面処理を行うと、新たな頂点、辺および面が生成されるが、これらの新たに生成された頂点、辺および面を一意に特定できるようにするため、本実施形態では、頂点、辺および面に固有の番号を割り当てている。
【００６４】
頂点については、図２４で示したように各頂点を並べて通し番号をふり、その番号を割り当てる。
【００６５】
辺については、図２５（ａ）に示す元の辺を２分割して生成される図２５（ｂ）に示す辺には、元の辺番号と、元の辺番号に元の辺の総数を加えた番号を割り振る。例えば、元の辺番号がｅ０、元の辺の総数がｅｎだったとすると、この辺を２分割して生成される辺の番号はｅ０と(e0+en)になる。
【００６６】
また、面内に生成される頂点を示す面ポイントの周りに生成される面には、図２６（ａ）に示すように面が四角形のときは、図２６（ｂ）に示すように元の面の番号の４倍、４倍＋１、４倍＋２および４倍＋３の番号が反時計回りに割り振られる。図２６（ｃ）に示すように面が三角形のときは、図２６（ｄ）に示すように元の面の番号の３倍、３倍＋１および３倍＋２の番号が反時計回りに割り振られる。この番号は、面ポイントから辺ポイントへの各辺の番号にも利用される。
【００６７】
上述したように、本実施形態では、入力された少数の頂点データに基づいて頂点ごとに独立な接続データを生成して細分割曲面処理を行い、新たな頂点データと接続データを生成するという手順を繰り返すため、入力される頂点データの数が少なくても曲面の滑らかなポリゴンを描画でき、従来に比べて描画速度を高速化できる。
【００６８】
図２７は本実施形態のポリゴンデータ生成装置を備えた描画システムの一実装形態を示す図である。図２７の描画システムは、ＣＰＵ１１およびＧＰＵ１２を備えている。ＧＰＵ１２は、図１と同様の処理動作を行うポリゴンデータ生成装置１３と、描画コントローラ１４とを有する。
【００６９】
ポリゴンデータ生成装置１３は、初期接続データ生成部１と、細分割曲面処理部１６と、頂点データメモリ１７と、接続データメモリ１８とを有する。
【００７０】
細分割曲面処理部１６は、図１の新規接続データ生成部４および新規頂点データ生成部５と同様の処理動作を行う。頂点データメモリ１７は、図１の第１頂点データ格納部３と第２頂点データ格納部７に対応する。接続データメモリ１８は、図１の第１接続データ格納部２と第２接続データ格納部６に対応する。
【００７１】
初期接続データ生成部１、細分割曲面処理部１６、頂点データメモリ１７、接続データメモリ１８および描画コントローラ１４は、内部バス１９に接続される。ＣＰＵ１１とＧＰＵ１２は共通のバス２０に接続されている。
【００７２】
図２７のポリゴンデータ生成装置１３は、ＣＰＵ１１から送られてきた初期ポリゴンの頂点データに基づいて新たな頂点データと接続データを生成する。描画コントローラ１４は、ポリゴンデータ生成装置１３で生成された頂点データと接続データに基づいて描画処理を行う。
【００７３】
図２８は図２７のＧＰＵ１２を一つのチップにまとめたＬＳＩのレイアウト図である。図２８のＬＳＩは、連想メモリ（ＣＡＭ）２１と、情報変換部２２と、ポリゴンデータ格納部２３と、細分割曲面処理部１６とを有する。ＣＡＭ２１には、すでに入力された頂点座標の下位ｎビットが格納されている。ＣＡＭ２１は、これらのｎビットデータと、外部から入力された頂点座標の下位ｎビットとを比較して、同じ頂点データが存在するか否かを判別する。
【００７４】
情報変換部２２は、図１の初期接続データ生成部１と同様に、入力された頂点データから接続データを生成し、生成されたデータと入力された頂点データをポリゴンデータ格納部２３に格納する。ポリゴンデータ格納部２３は、図２７の頂点データメモリ１７と接続データメモリ１８を統合したものである。
【００７５】
細分割曲面処理部１６は、図１の新規接続データ生成部４および新規頂点データ生成部５と同様に、細分割曲面処理を行って新たな頂点データと接続データを生成し、生成したデータをポリゴンデータ格納部２３に格納する。
【００７６】
図２８のＬＳＩは、外部から頂点データが入力されると、ＣＡＭ２１のエントリを検索し、同じ頂点データがすでに存在すれば、その頂点の番号と接続データを読み出し、同じ頂点データが存在しなければ、その頂点に新たな番号をつけて、ＣＡＭ２１のエントリに追加する。
【００７７】
また、図２８のＬＳＩは、外部から入力された頂点データに基づいて、その頂点の頂点データと接続データをポリゴンデータ格納部２３に格納する。このとき、面には常に新たな番号を割り振り、辺にはすでに入力された頂点の場合には過去に割り振られた番号を使用し、新たに入力された頂点の場合には新たな番号を割り振る。
【００７８】
このような処理を繰り返していき、対象とする頂点の周囲が連続したポリゴンで囲まれたと判断されると、その頂点に対応する接続データはＣＡＭ２１のエントリから削除される。
【００７９】
例えば、図２９（ａ）に示すポリゴン列の頂点データが図２８のＬＳＩに入力された後に、図２９（ｂ）に示すポリゴン列の頂点データが入力される場合について説明する。なお、図２９（ａ）の頂点ｖ２，ｖ４，ｖ６，ｖ８はそれぞれ図２９（ｂ）の頂点ｖ１０，ｖ１２，ｖ１４，ｖ１６と同じである。
【００８０】
まず、図２８の情報変換部２２は、図２９（ａ）のポリゴン列からできる辺と面に辺番号と面番号を割り振り、頂点ｖ１〜ｖ８に関して頂点データと接続データを生成する。これらの頂点はいずれも初めて入力される頂点なので、ＣＡＭ２１に全頂点の座標を登録する。
【００８１】
次に、図２９（ｂ）のポリゴン列の頂点データが入力されると、頂点ｖ１，ｖ１２，ｖ１４，ｖ１６についてはすでに頂点データが入力されているため、ポリゴンデータ格納部２３から該当する接続データを読み出して接続情報の追加を行う。それ以外の頂点は初めての頂点なので、ＣＡＭ２１に頂点座標を登録する。
【００８２】
一方、例えば、図３０（ａ）に示すポリゴンファンの頂点データが図２８のＬＳＩに入力された後に、図３０（ｂ）に示すポリゴンファンの頂点データが入力される場合について説明する。なお、図３０（ａ）の頂点ｖ３，ｖ４はそれぞれ図３０（ｂ）の頂点ｖ１４，ｖ１３と同じである。
【００８３】
図２８の情報変換部２２はまず図３０（ａ）のポリゴンファンからできる辺と面に辺番号と面番号を割り振り、頂点ｖ１〜ｖ７に関して頂点データと接続データを生成する。これらの頂点はいずれも初めて入力される頂点なので、ＣＡＭ２１に全頂点の座標を登録する。
【００８４】
次に、図３０（ｂ）のポリゴン列の頂点データが入力されると、頂点ｖ１３，ｖ１４についてはポリゴンデータ格納部２３から該当する接続データを読み出して接続情報の追加を行う。それ以外の頂点は初めての頂点なので、ＣＡＭ２１に頂点座標を登録する。
【００８５】
図１では、第１接続データ格納部２と第２接続データ格納部６に分けて接続データを格納する例を説明したが、これら格納部２，６を一つにまとめてもよい。同様に、第１頂点データ格納部３と第２頂点データ格納部７を一つにまとめてもよい。
【００８６】
上述した実施形態で説明したポリゴンデータ生成装置は、ハードウェアで構成してもよいし、ソフトウェアで構成してもよい。ソフトウェアで構成する場合には、ポリゴンデータ生成装置の機能を実現するプログラムをフロッピーディスクやＣＤ−ＲＯＭ等の記録媒体に収納し、コンピュータに読み込ませて実行させてもよい。記録媒体は、磁気ディスクや光ディスク等の携帯可能なものに限定されず、ハードディスク装置やメモリなどの固定型の記録媒体でもよい。
【００８７】
また、ポリゴンデータ生成装置の機能を実現するプログラムを、インターネット等の通信回線（無線通信も含む）を介して頒布してもよい。さらに、同プログラムを暗号化したり、変調をかけたり、圧縮した状態で、インターネット等の有線回線や無線回線を介して、あるいは記録媒体に収納して頒布してもよい。
【００８８】
【発明の効果】
以上詳細に説明したように、本発明によれば、入力された頂点データに基づいて頂点ごとに独立な接続データを生成して細分割曲面処理を行って新たな頂点データと接続データを生成した後、再度細分割曲面処理を行うという手順を繰り返すため、曲面の滑らかなポリゴンを高速に描画できる。
【図面の簡単な説明】
【図１】本発明に係るポリゴンデータ生成装置の一実施形態のブロック図。
【図２】図２は本実施形態に係るポリゴンデータ生成装置の全体的な処理動作を示すフローチャート。
【図３】図３はポリゴンの一例を示す図。
【図４】図４（ａ），図４（ｂ），図４（ｃ）は接続データの一例を示す図。
【図５】図５はデータベース生成部の処理動作を示すフローチャート。
【図６】図６は頂点ｖ０〜ｖ２の頂点情報を示す図。
【図７】図７は頂点ｖ１の接続データを示す図。
【図８】図８は頂点ｖ０の接続データを示す図。
【図９】図９は頂点ｖ２の接続データを示す図。
【図１０】図１０（ａ），図１０（ｂ）は頂点ｖ０〜ｖ３の頂点情報を示す図。
【図１１】図１１は頂点ｖ３との接続情報を追加した場合の頂点ｖ１の接続データを示す図。
【図１２】図１２（ａ），図１２（ｂ）は頂点ｖ３との接続情報を追加した場合の頂点ｖ２の接続データを示す図。
【図１３】図１３は頂点ｖ３との接続情報を追加した場合の頂点ｖ３の接続データを示す図。
【図１４】図１４は頂点ｖ１〜ｖ７をもつポリゴンの接続関係を示す図。
【図１５】図１５は頂点ｖ３の接続データを示す図。
【図１６】図１６（ａ），図１６（ｂ）は頂点ｖ５とｖ７の接続データを示す図。
【図１７】図１７は図１３に辺ｅ13に関する接続情報を追加した図。
【図１８】図１８は頂点ｖ３の接続データを示す図。
【図１９】図１９（ａ），図１９（ｂ）は頂点ｖ５とｖ７の接続データを示す図。
【図２０】図２０は頂点情報が複数に分かれるポリゴンの例を示す図。
【図２１】図２１（ａ），図２１（ｂ）は図２０の頂点ｖ３の接続データを示す図。
【図２２】図２２は細分割曲面処理の処理手順を示すフローチャート。
【図２３】図２３は辺ポイントを説明する図。
【図２４】図２４は新規接続データ生成部で生成される接続データの一例を示す図。
【図２５】図２５（ａ），図２５（ｂ）は辺を分割した場合の辺番号の付け方を説明する図。
【図２６】図２６（ａ），図２６（ｂ），図２６（ｃ），図２６（ｄ）は面を分割した場合の面番号の付け方を説明する図。
【図２７】図２７は図１のポリゴンデータ生成装置の実装形態の一例を示す図。
【図２８】図２８は図２７の構成を一つのチップにまとめたＬＳＩのレイアウト図。
【図２９】図２９はポリゴン列の一例を示す図。
【図３０】図３０はポリゴンファンの一例を示す図。
【符号の説明】
１  初期接続データ生成部
２  第１接続データ格納部
３  第１頂点データ格納部
４  新規接続データ生成部
５  新規頂点データ生成部
６  第２接続データ格納部
７  第２頂点データ格納部
８  データ合成部
【図１】
0003702244.tif 000005
【図２】
0003702244.tif 000006
【図３】
0003702244.tif 000007
【図４】
0003702244.tif 000008
【図５】
0003702244.tif 000009
【図６】
0003702244.tif 000010
【図７】
0003702244.tif 000011
【図８】
0003702244.tif 000012
【図９】
0003702244.tif 000013
【図１０】
0003702244.tif 000014
【図１１】
0003702244.tif 000015
【図１２】
0003702244.tif 000016
【図１３】
0003702244.tif 000017
【図１４】
0003702244.tif 000018
【図１５】
0003702244.tif 000019
【図１６】
0003702244.tif 000020
【図１７】
0003702244.tif 000021
【図１８】
0003702244.tif 000022
【図１９】
0003702244.tif 000023
【図２０】
0003702244.tif 000024
【図２１】
0003702244.tif 000025
【図２２】
0003702244.tif 000026
【図２３】
0003702244.tif 000027
【図２４】
0003702244.tif 000028
【図２５】
0003702244.tif 000029
【図２６】
0003702244.tif 000030
【図２７】
0003702244.tif 000031
【図２８】
0003702244.tif 000032
【図２９】
0003702244.tif 000033
【図３０】
0003702244.tif 000034