(57)【特許請求の範囲】
【請求項１】
プログラムされたコンピュータによってオリジナルモデルのポリゴン数を削減するポリゴン処理方法において、
該オリジナルモデルのポリゴンの頂点を、所定の間隔で並んだ格子点上に一致させて第１のモデルを生成する第１の工程と、
第１のモデルに対して、１つのエッジを共有して隣接する２つのポリゴンの法線の成す角度が所定の値より大きい場合に、該エッジを抽出する第２の工程と、
抽出されたエッジのうち、１端を共有する２つのエッジをペアにしてペアエッジを構成し、該ペアエッジのうち一方のエッジを共有する複数のペアエッジを組み合わせてポリゴンを再構築する第３の工程と、
再構築したポリゴンの存在の可否及び該ポリゴンの法線の向きを、前記オリジナルモデルのポリゴンデータを参照して決定する第４の工程を含み、
前記第３の工程は、前記一方のエッジを共有する２つのペアエッジのうち、それぞれのペアエッジの法線の成す角度が所定の値より小さいペアエッジを組み合わせる工程を含むことを特徴とするポリゴン処理方法。
【請求項２】
請求項１において、前記第１の工程は、前記オリジナルモデルのポリゴンの頂点の座標データを、前記格子点の間隔で割った値を求め、該値の整数部分と格子点の間隔との積を前記第１のモデルの座標データとする工程を含むことを特徴とするポリゴン処理方法。
【請求項３】
請求項１において、前記第２の工程は、抽出したエッジに対して、１つの端点を共有する２つのエッジの成す角度が所定の値より大きい場合に、該端点を削除する工程を含むことを特徴とするポリゴン処理方法。
【請求項４】
請求項１において、前記オリジナルモデルは、ＮＵＲＢＳ曲線を用いて生成されたポリゴンモデルであることを特徴とするポリゴン処理方法。
【請求項５】
請求項１乃至４に記載したポリゴン処理方法により生成したポリゴンデータを記録した記録媒体。
【請求項６】
請求項１乃至４に記載したポリゴン処理方法により生成したポリゴンデータを用いたゲームプログラムを記録した記録媒体。
【請求項７】
コンピュータによってオリジナルモデルのポリゴン数を削減するためのプログラムを記録した記録媒体において、
該オリジナルモデルのポリゴンの頂点を、所定の間隔で並んだ格子点上に一致させて第１のモデルを生成する第１の工程と、
第１のモデルに対して、１つのエッジを共有して隣接する２つのポリゴンの法線の成す角度が、所定の値より大きい場合に該エッジを抽出する第２の工程と、
抽出されたエッジのうち１端を共有する２つのエッジをペアにしてペアエッジを構成し、該ペアエッジのうち一方のエッジを共有する複数のペアエッジを組み合わせてポリゴンを再構築する第３の工程と、
再構築したポリゴンの存在の可否及び該ポリゴンの法線の向きを、前記オリジナルモデルのポリゴンデータを参照して決定する第４の工程とをコンピュータに実行させ、
前記第３の工程では、前記一方のエッジを共有する２つのペアエッジのうち、それぞれのペアエッジの法線の成す角度が所定の値より小さいペアエッジを組み合わせてポリゴンを再構築することを特徴とするポリゴン処理プログラムを記録した記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、コンピュータグラッフィクスにおけるポリゴン処理方法及びポリゴン処理プログラムを記録した記録媒体に関する。
【０００２】
【従来の技術】
コンピュータグラッフィックスにおいて曲線や曲面を持つ実際のモデルを表現するのに、曲線や曲面をそのまま表現できるＮＵＲＢＳ（Ｎｏｎ−Ｕｎｉｆｏｒｍ  Ｒａｔｉｏｎａｌ  Ｂ−Ｓｐｌｉｎｅ）曲線又は曲面が利用される場合がある。しかし、曲線や曲面のデータ量は膨大なものとなるため、コンピュータグラッフィックスを利用したゲームプログラムでは、曲面を持つ実際のモデルを微小な平面（ポリゴン）で近似したモデルを使用する場合が多い。
【０００３】
一方、コンピュータグラッフィックスを利用したゲームにおいては、ゲーム内のモデル等が、遊戯者が操作するスイッチに応答して、ほぼリアルタイムに移動したり変化する必要がある。モデルの動きの速さはそのモデルの形状データ等を処理する速度で決まるため、ゲーム内のモデルの形状等のデータ量はできるだけ少ない方がよい。このため、ゲームのデザイナーは、多数のポリゴンで表現されたオリジナルモデルのポリゴン数を削減し、ゲームにおける操作のリアルタイム性を確保していた。
【０００４】
【発明が解決しようとする課題】
このように、ＮＵＲＢＳ曲線で表現されたモデルを微小なポリゴンで近似したり、実際の建築物等のモデルの平面をそのままポリゴンに変換すると、膨大な数のポリゴンが生成され、コンピュータグラッフィックスにおけるモデルのデータ量が増大する。このような膨大な数のポリゴンで形成されるモデルを、実際のモデルの形状の特徴を維持しつつ、操作のリアルタイム性を確保できるポリゴン数に削減する作業は、長い時間と労力を必要とし、ゲームのデザイナーにとって大きな負担となっていた。
【０００５】
一方、コンピュータを利用してポリゴンを減らす従来のポリゴンリダクションツールは、単純に、多数のポリゴン数のモデルを指定したポリゴン数に減少させるため、実際のモデルの形状等の特徴が維持されない場合が多く、ゲームで使用するモデルの形状データの作成に必ずしも適したものではなかった。
【０００６】
そこで本発明は、入力となるオリジナルモデルの形状の情報からポリゴンの再構築を行い、オリジナルモデルの形状の特徴を維持すると同時に、オリジナルモデルのポリゴン数の削減を行うポリゴン処理方法及びポリゴン処理プログラムを記録した記録媒体を提供することを目的とする。
【０００７】
【課題を解決するための手段】
上記の目的は、プログラムされたコンピュータによってオリジナルモデルのポリゴン数を削減するポリゴン処理方法において、該オリジナルモデルのポリゴンの頂点を、所定の間隔で並んだ格子点上に一致させて第１のモデルを生成する工程と、前記第１のモデルにおいて、１つのエッジを共有して隣接する２つのポリゴンの法線の成す角度が、所定の値より大きい場合に該エッジを抽出し、該角度が所定の値以下の場合に該エッジを削除する工程と、
前記抽出されたエッジのうち１端を共有する２つのエッジをペアにしてペアエッジを構成する工程と、該ペアエッジのうち一方のエッジを共有する複数のペアエッジを組み合わせてポリゴンを再構築する工程と、前記再構築したポリゴンの存在の可否及び該ポリゴンの法線の向きを、前記オリジナルモデルのポリゴンデータを参照して決定する工程とを含むことを特徴とするポリゴン処理方法及びそのプログラムを記録した記録媒体を提供することにより達成される。
【０００８】
本発明によれば、１つのエッジを共有して隣接する２つのポリゴンの法線の成す角度が、所定の値より大きい場合にそのエッジを抽出し、抽出されたエッジのうち１端を共有する２つのエッジをペアにしてペアエッジを構成し、更にペアエッジのうち一方のエッジを共有する複数のペアエッジを組み合わせてポリゴンを再構築するので、多数のポリゴンで構成されるオリジナルモデルが、形状の特徴を維持したまま少ないポリゴン数のモデルに変換される。
【０００９】
【発明の実施の形態】
以下、本発明の実施の形態の例について図面に従って説明する。図１は、本発明の実施の形態のポリゴン処理方法が実行されるハードウエアの構成例である。メモリ１０２内には、入力となるオリジナルモデルのポリゴンデータ、処理の過程で生成されるモデルのエッジデータ及びペアエッジデータ、本実施の形態の出力データとなるポリゴンリスト、及びポリゴン処理プログラムが格納される。
【００１０】
ＣＰＵ１００は、バス１０１を介してメモリ１０２にアクセスし、入力モデルのポリゴンデータにポリゴン処理プログラムに従った処理を実行し、入力モデルのポリゴン数を削減して出力データとなるポリゴンリストを生成する。
【００１１】
図２は本発明の実施の形態のポリゴン処理方法のフローチャートである。図２を参照してポリゴン処理方法の全体の流れについて説明する。本発明の実施の形態のポリゴン処理方法は、コンピュータにおいて実行されるので、まず、ポリゴン数を削減する対象となるオリジナルモデルのポリゴンデータをコンピュータに入力する（Ｓ１１）。
【００１２】
次に、モデルの形状を構成する上で必要性の低いポリゴンを削除するために、ポリゴンのクリーンアップ処理を行う（Ｓ１２）。この処理には、ポリゴンの頂点を予め指定した微小な格子点上に移動する処理、格子点上で一致した頂点のデータを削除する処理等が含まれる。
【００１３】
次にエッジの抽出処理を行う（Ｓ１３）。この処理は、隣接するポリゴンの法線の成す角がユーザの指定した値以上のエッジを、モデルの形状維持に必要なエッジとして抽出する処理であり、隣接するポリゴンの法線の成す角が指定した値以下のエッジは削除される。なお、このステップではエッジのみが抽出され、ポリゴンはまだ構成されていない。
【００１４】
次にポリゴンの構築処理を行う（Ｓ１４）。この処理は、抽出されたエッジのうち１つの端点を共有する２本のエッジを組み合わせてペアエッジとし、更に１本のエッジを共有する複数のペアエッジを組み合わせてポリゴンを再構築する処理である。また、この処理には、再構築したポリゴンの存在の可否、及びポリゴンの表裏を区別する法線の向きを決定する処理が含まれる。
【００１５】
次にポリゴンデータの出力を行う（Ｓ１５）。本実施の形態では、ユーザが指定するパラメータに従って、オリジナルモデルの形状の特徴を維持しつつポリゴンが削減され、ポリゴンの頂点座標データが出力される。
【００１６】
図３は、本実施の形態のポリゴン処理方法の処理の過程を示す説明図である。これにより多数のポリゴンで構成されるオリジナルモデルが、少ないポリゴンで構成されるモデルに変換される様子について説明する。
【００１７】
図３（１）はオリジナルモデルの１例である。このオリジナルモデルは三角形のポリゴンＡ、Ｂ、Ｃ等で構成されており、全ポリゴン数が例えば３０であるとする。なお、三角形ポリゴンは、頂点である３つの制御点で構成され、例えばポリゴンＡは制御点１、２、３を有し、ポリゴンＢは制御点２、４、５を有する。
【００１８】
オリジナルモデルのポリゴンデータがコンピュータに入力されると（図２のＳ１１）、次にポリゴンのクリーンアップ処理（Ｓ１２）が行われ、接近している制御点が統合され、微小なポリゴンが削除される。例えば、図３（１）の接近している制御点３、５、７は制御点３に統合され、制御点２、３、５で構成される微小なポリゴンは削除される。
【００１９】
次にエッジの抽出処理（Ｓ１３）が行われる。エッジの抽出処理は、前述のように、隣接するポリゴンの法線の成す角がユーザの指定した値以上のエッジを、モデルの形状維持に必要なエッジとして抽出する処理である。例えば、図３（１）の制御点１、８、９で構成されるポリゴンＦと制御点８、９、１０で構成されるポリゴンＧは、制御点８、９を両端とするエッジを共有している。そこで、ポリゴンＦの法線とポリゴンＧの法線との成す角がユーザの指定した値以下の場合は、制御点８、９を両端とするエッジが削除される。
【００２０】
図３（２）は、オリジナルモデルにエッジの抽出処理を行い、１２本のエッジが抽出された場合を示す。なお、この処理には、後述するように、１つの制御点を共有し、ほぼ直線状になっている２本のエッジを、１本のエッジにする処理が含まれる。従って、オリジナルモデルから、制御点１、２を両端とするエッジＥＡ、制御点２、３を両端とするエッジＥＢ等が抽出される。なお、Ｋ、Ｌ等は、エッジに隣接するポリゴンの番号である。
【００２１】
図３（３）は、抽出したエッジからポリゴンを再構築（Ｓ１４）する過程を示す図である。ポリゴンの再構築は、端点を共有する２本のエッジをペアエッジとし、複数のペアエッジを組み合わせ平面を構成する処理である。例えば、制御点４、１を両端とするエッジと制御点１、２を両端とするエッジを組み合わせてペアエッジＰＡとし、制御点１、２を両端とするエッジと制御点２、３を両端とするエッジを組み合わせてペアエッジＰＢとする。同様にペアエッジＰＣ、ＰＤを構成し、４つのペアエッジＰＡ、ＰＢ、ＰＣ、ＰＤを組み合わせて１つのポリゴンを構成する。なお、図３（２）の１２本のエッジからは、２４組のペアエッジが構成される。
【００２２】
図３（４）は、ポリゴンの構築処理によりポリゴン数６のモデルが再構築された場合を示す。このように、本実施の形態では、図３（１）に示した、多数のポリゴンで構成されるオリジナルモデルが、形状の特徴を維持したまま少ないポリゴン数のモデルに変換される。
【００２３】
図４は、本実施の形態のポリゴン処理方法で処理の対象となるモデルのポリゴンデータの構成例を示す。本実施の形態のポリゴン処理方法において、入力となるオリジナルモデルのポリゴンデータ、及び出力となるモデルのポリゴンデータは、同様の構成を有する。但し、本実施の形態のポリゴン処理方法により、オリジナルモデルの形状の特徴を維持しつつ、オリジナルモデルのポリゴン数、及び制御点の個数等のデータが削減される。なお、図４のデータ構成は、モデルを三角形ポリゴンで構成した場合を示す。
【００２４】
図４（１）のポリゴン数は、モデルを構成するポリゴンの全数であり、図３（１）のオリジナルモデルの場合は、ポリゴンＡ、Ｂ、Ｃ等の合計で例えば３０である。また、図４（２）のポリゴン毎の制御点の個数は、ポリゴンを構成する頂点の数であり、モデルを三角形ポリゴンで構成した場合は３である。
【００２５】
図４（３）のポリゴン毎の制御点の番号は、三角形ポリゴンの頂点の番号で、図３（１）のオリジナルモデルの場合は、ポリゴンＡの制御点は１、２、３であり、ポリゴンＢの制御点は２、４、５である。また、図４（４）の全制御点の個数は、モデルを構成する制御点の合計であり、図３（１）のオリジナルモデルの場合は、制御点１、２、３等の合計で例えば２５である。
【００２６】
図４（５）の制御点の座標データは、ゲーム空間に設けられたワールド座標における制御点のＸ、Ｙ、Ｚ座標で、例えば制御点１の座標データは（Ｘ１、Ｙ１、Ｚ１）であり、制御点２の座標データは（Ｘ２、Ｙ２、Ｚ２）である。また、図４（６）のポリゴン毎の法線ベクトルは、ポリゴンの制御点から求まるポリゴンの法線ベクトルで、ポリゴンの表裏の区別等に使用される。
【００２７】
図５は、モデルのエッジデータの構成例を示す。エッジデータは、必要に応じてモデルの制御点データから生成され、エッジの抽出処理等で使用される。図５（１）のエッジの本数は、モデルのエッジの総数で、図３（２）のモデルの場合は１２本である。また、図５（２）のエッジの両端点の制御点の番号は、エッジの両端の２つの制御点の番号で、図３（２）のモデルの場合は、エッジＥＡは制御点１、２を有し、エッジＥＢは制御点２、３を有する。
【００２８】
図５（３）のエッジに隣接するポリゴンの数は、通常の立体モデルの場合は２であるが、隣接するポリゴンがない場合は１であり、ポリゴンがＴ字型に接している場合は３である。また、図５（４）のエッジに隣接するポリゴンの番号は、１本のエッジを共有する２つのポリゴンの番号で、図３（２）のモデルの場合は、エッジＥＡに隣接するのはポリゴンＫ、Ｌであり、エッジＥＢに隣接するのはポリゴンＫ、Ｍである。
【００２９】
図６は、モデルのペアエッジのデータ構成を示す。ペアエッジのデータは、抽出されたエッジの制御点のデータから生成され、ポリゴンを再構築する処理で使用される。図６（１）のペアエッジの個数は、抽出されたエッジで構成可能なペアエッジの総数で、図３（２）のモデルの場合は６本のエッジで組合せ可能な数２４である。また、図６（２）のペアエッジの番号は、それぞれのペアエッジの番号で、図３（３）の場合は、ペアエッジＰＡは制御点４、１、２を有し、ペアエッジＰＢは制御点１、２、３を有する。
【００３０】
図７は、図２に示したポリゴンのクリーンアップ処理（Ｓ１２）の詳細フローチャートである。ポリゴンのクリーンアップ処理は、形状を維持する上で重要でないポリゴンを予め削除する処理で、まず、ポリゴンを構成する制御点を格子点上に移動する処理を行う（Ｓ２１）。
【００３１】
この場合、格子点の間隔は、モデルを表示する表示装置の解像度、及び削減すべきデータ量等により指定される。また、制御点を格子点上に移動するには、制御点のＸ座標、Ｙ座標、Ｚ座標それぞれの座標データを、格子間隔で割った値の整数部分と格子間隔の積を求めることにより行う。
【００３２】
次に、不要な制御点の削除を行う（Ｓ２２）。制御点を格子点上に移動することにより、オリジナルモデルにおいて接近している制御点が格子点上で一致する場合が生ずる。その場合に、一致した制御点は１つの制御点に統合し、制御点のデータ量を削減する。
【００３３】
次に、不要なポリゴンの削除を行う（Ｓ２３）。制御点が格子点上に移動することにより、ポリゴンが１本のエッジや１つの制御点に変化する場合も生じる。この場合は、そのポリゴンを削除し、ポリゴンのデータ量を削減する。
【００３４】
図８は、ポリゴンのクリーンップ処理の過程を示す説明図である。図８（１）は、図３（１）のオリジナルモデルの一部を抜き出したものであり、ポリゴンＡ、Ｂ、Ｃ、Ｄ、Ｅと制御点１、２、３、４、５、６、７を有する。また、図８（２）は、制御点３、５、７が３次元の格子内に配置されている状態を示す。制御点５、７は、格子の中間に位置しているので、前述の処理により格子点上に移動する。
【００３５】
図８（３）は、図７のステップＳ２１で制御点を点線で示す格子点上に移動した場合を示す。但し、説明の都合上、格子は２次元で示す。このように、接近している制御点３、５、７は、１つの格子点上に移動する。また、制御点３、５、７が一致したことにより、ポリゴンＤ及びポリゴンＥが削除される。
【００３６】
図８（４）は、クリーンアップ処理により不要な制御点及び不要なポリゴンが削除された状態を示す。このようにオリジナルモデルは、ポリゴンＡ、Ｂ、Ｃ、と制御点１、２、３、４、５を有するモデルとなり、データ量が削減される。
【００３７】
図９は、図２に示したエッジの抽出処理（Ｓ１３）の詳細フローチャートである。エッジの抽出処理は、隣接するポリゴンの法線の成す角がユーザの指定した値以上のエッジを、モデルの形状維持に必要なエッジとして抽出する処理である。
【００３８】
この処理では、まず、隣接するポリゴンの法線の成す角を計算する（Ｓ３１）。この場合、法線はポリゴンの制御点座標から求まり、隣接するポリゴンの成す角は、１８０度からそれぞれの法線の成す角を引くことにより求まる。
【００３９】
次に、隣接するポリゴンの法線の成す角がユーザの指定する値より大きいか否かを判断する（Ｓ３２）。ユーザが指定する値により抽出されるエッジの個数に差異を生じるので、オリジナルモデルの形状の特徴の再現性、及びポリゴンデータを削減する程度により指定値を選択する。なお、本実施の形態では、指定値の初期値は８０度である。
【００４０】
判断の結果、隣接するポリゴンの法線の成す角が指定値より大きい（Ｙｅｓ）場合は、そのエッジを抽出する（Ｓ３３）。これは、法線の成す角が指定値より大きい場合は、隣接するポリゴンの成す角が鋭く、そのエッジはオリジナルモデルの形状の特徴を維持するのに必要だからである。
【００４１】
一方、隣接するポリゴンの法線の成す角が指定値より小さい（Ｎｏ）場合は、そのエッジを削除する（Ｓ３４）。これは、法線の成す角が指定値より小さい場合は、隣接するポリゴンの成す角が鈍角であり、そのエッジを削除してもオリジナルモデルの形状の特徴を維持できるからである。
【００４２】
次に、１つの制御点を共有するエッジの成す角をエッジの両端の座標により計算し（Ｓ３５）、そのエッジの成す角が指定値より大きいか否かを判断する（Ｓ３６）。そして、エッジの成す角が指定値より小さい（Ｎｏ）場合、即ち、２つのエッジの成す角が鋭い場合は、オリジナルモデルの形状の特徴を維持するために、その制御点を抽出する（Ｓ３７）。
【００４３】
一方、エッジの成す角が指定値より大きい（Ｙｅｓ）場合、即ち、２つのエッジがほぼ直線上に並んでいる場合はその制御点を削除する（Ｓ３８）。このように、ほぼ直線上に並んだ２本のエッジを１本のエッジに置き換えて、ポリゴンを構成する制御点のデータ量を更に削減する。
【００４４】
図１０は、エッジの抽出処理の説明図である。図１０（１）は、図３（１）に示したオリジナルモデルの一部を抜き出したものである。この場合、ポリゴンＦとポリゴンＧとは、制御点８、９を両端とするエッジを共有している。この場合に、ポリゴンＦの制御点１、８、９各座標から法線ベクトルＶＦが求め、ポリゴンＧの制御点８、９、１０各座標から法線ベクトルＶＧが求める。
【００４５】
図１０（２）は、法線ベクトルＶＦと法線ベクトルＶＧとの成す角θを示す。図９のステップＳ３１からステップＳ３４で説明したように、角θが指定値より大きい場合は、ポリゴンＦとポリゴンＧとの成す角（１８０°−θ）は鋭くなり、制御点８、９を両端とするエッジが抽出される。一方、角θが指定値より小さい場合は、ポリゴンＦとポリゴンＧとの成す角（１８０°−θ）は鈍角となり、制御点８、９を両端とするエッジは削除される。
【００４６】
図１０（３）は、制御点１５、１６を両端とするエッジＥＰと制御点１６、１７を両端とするエッジＥＱとが、制御点１６を共有している場合を示す。図９のステップＳ３５からステップＳ３８で説明したように、エッジＥＰとエッジＥＱとの成す角φが指定値より大きい場合は制御点１６は削除され、角φが指定値より小さい場合は制御点１６は抽出される。
【００４７】
図１１は、図２に示したポリゴンの構築処理（Ｓ１４）の詳細なフローチャートであり、図１２はその処理の過程を示す説明図である。図１１及び図１２によりポリゴンの構築処理について説明する。
【００４８】
前述のように、モデルの形状維持に必要なものとして抽出されたエッジは、図５に示したデータ構成を有し、また、２本のエッジで構成されるペアエッジは図６に示したデータ構成を有する。
【００４９】
ポリゴンを構築するには、まず、抽出されたエッジから構成されるペアエッジのうちの任意のペアエッジを選択する（Ｓ４０）。ペアエッジは、端点を共有する２本のエッジをペアにしたもので、図１２（１）は、エッジＥＤ、ＥＡから構成されるペアエッジＰＡが選択された状態を示す。
【００５０】
また、ペアエッジＰＡが選択されると、所定のレジスタに開始制御点番号４と、解リスト｛ＰＡ｝が記憶される。開始制御点番号は、最初に選択したペアエッジの一方の制御点の番号で、ポリゴンを構成する起点となる。また、解リストは、ポリゴンを構成する候補となるペアエッジのデータリストである。
【００５１】
次に、最初に選択したペアエッジとエッジを共有する他のペアエッジを選択する（Ｓ４１）。図１２（２）は、ペアエッジＰＡのエッジＥＡを共有するペアエッジＰＢが選択された状態を示す。
【００５２】
次に、２組のペアエッジの法線の成す角を調べる（Ｓ４２）。ペアエッジの法線は、ペアエッジの３つの制御点で構成される平面の法線である。そして、ペアエッジの法線の成す角が指定値より小さいか否かを判断する（Ｓ４３）。これは、１つのペアエッジとエッジを共有する他のペアエッジが複数存在する場合に、平面としてのポリゴンを構成できるペアエッジを選択するためである。
【００５３】
そして、ペアエッジの法線の成す角が指定値より大きい場合（Ｎｏ）は、そのペアエッジは平面を構成しないとして、ステップＳ４１に戻り別のエッジを選択する。一方、ペアエッジの法線の成す角が指定値より小さい場合（Ｙｅｓ）は、そのペアエッジはポリゴンを構成する要素と成り得るので、そのペアエッジを解リストに追加する。図１２（２）のペアエッジＰＢは、ポリゴンを構成する要素と成り得るので、解リストは｛ＰＡ、ＰＢ｝となる。
【００５４】
次に、選択した他のペアエッジとエッジを共有する更に他のペアエッジを選択する（Ｓ４４）。図１２（３）では、ペアエッジＰＢのエッジＥＢを共有するペアエッジＰＣを選択した状態を示す。そして、ペアエッジＰＢとペアエッジＰＣの法線の成す角が指定値より小さい場合は、ペアエッジＰＣが解リストに追加され、解リストは｛ＰＡ、ＰＢ、ＰＣ｝となる。
【００５５】
このようにして、法線の成す角が指定値より小さいペアエッジを次々に組み合わせていく。なお、この指定値は、ユーザがどの範囲までを平面とみなすかにより指定することができる。
【００５６】
このように、ポリゴンを構成するためにエッジを共有するペアエッジを次々に選択していくと、ペアエッジの制御点が最初のペアエッジの制御点と一致する場合が生じる（Ｓ４５）。図１２（３）では、ペアエッジＰＣの制御点４が最初のペアエッジＰＡの制御点４と一致した場合を示す。なお、制御点の一致は、前述した開始制御点番号４を記憶したレジスタを参照することにより検出する。
【００５７】
このように、次々に組み合わせたペアエッジの制御点番号が開始制御点番号に一致した場合は、ポリゴンの再構成の処理に成功したことになる。一方、ペアエッジの制御点が開始制御点番号と一致しない場合は、ポリゴンの再構成の処理に失敗したことになる。
【００５８】
次に、構成されたポリゴンをオリジナルモデルと比較し、その存在の可否を調べる（Ｓ４６）。本実施の形態のポリゴン処理方法では、オリジナルモデルのエッジを抽出してポリゴンを再構成しているため、再構成したポリゴンが必ずしもオリジナルモデルを適切に表現しない場合も生じるからである。なお、この処理は、構成したポリゴンに含まれる点、例えば、中心又は重心等の座標データの近傍に、オリジナルモデルの対応点が存在するか否かにより判断する。
【００５９】
次に、存在を確認したポリゴンのデータをポリゴンリストに追加し、オリジナルモデルを参照してポリゴンの法線の向きを決定する（Ｓ４７）。ポリゴンリストは、本実施の形態のポリゴン処理方法の出力となるデータで、図４に示したデータ構成を有する。
【００６０】
次に、最初のペアエッジのエッジと最後のペアエッジのエッジから構成されるペアエッジを選択する（Ｓ４８）。図１２（４）は、最初のペアエッジＰＡのエッジＥＤと、最後のペアエッジＰＣのエッジＥＣから構成されるペアエッジＰＤを選択した状態を示す。また、この場合の解リストは｛ＰＡ、ＰＢ、ＰＣ、ＰＤ｝となる。
【００６１】
次に、ペアエッジのデータから、ポリゴンの構築処理で使用したペアエッジのデータを削除する（Ｓ４９）。即ち、図６に示したペアエッジのデータ、例えば｛ＰＡ、ＰＢ、ＰＣ、ＰＤ、ＰＥ、ＰＦ、・・・｝から、ポリゴンの再構築の処理で使用した解リスト｛ＰＡ、ＰＢ、ＰＣ、ＰＤ｝のデータを削除し、次のポリゴンを再構築する処理を行う。
【００６２】
このように本実施の形態のポリゴン処理方法では、オリジナルモデルの隣接するポリゴンの法線の成す角が指定値以上のエッジを抽出し、そのエッジからペアエッジを構成し、更にそのペアエッジを組み合わせてポリゴンを再構築する。このため、オリジナルモデルの形状の特徴を維持しつつ、モデルのデータ量を削減することができる。
【００６３】
以上、本実施の形態について具体的に説明したが、かかる実施の形態例が本発明の技術的範囲を限定するものではない。
【００６４】
【発明の効果】
以上説明した通り、本発明は、１つのエッジを共有して隣接する２つのポリゴンの法線の成す角度が、所定の値より大きい場合にそのエッジを抽出し、抽出されたエッジのうち１端を共有する２つのエッジをペアにしてペアエッジを構成し、更にペアエッジのうち一方のエッジを共有する複数のペアエッジを組み合わせてポリゴンを再構築する。従って、多数のポリゴンで構成されるオリジナルモデルを、形状の特徴を維持したまま少ないポリゴン数のモデルに変換することができる。
【図面の簡単な説明】
【図１】本発明の実施の形態のポリゴン処理方法が実行されるハードウエアの構成例である。
【図２】本発明の実施の形態のポリゴン処理方法のフローチャートである。
【図３】本発明の実施の形態のポリゴン処理方法の説明図である。
【図４】ポリゴンのデータ構成である。
【図５】エッジのデータ構成である。
【図６】ペアエッジのデータ構成である。
【図７】ポリゴンのクリーンアップ処理のフローチャートである。
【図８】ポリゴンのクリーンアップ処理の説明図である。
【図９】エッジの抽出処理のフローチャートである。
【図１０】エッジの抽出処理の説明図である。
【図１１】ポリゴンの構築処理のフローチャートである。
【図１２】ポリゴンの構築処理の説明図である。
【符号の説明】
１００  ＣＰＵ
１０１  バス
１０２  メモリ
１、２・・  制御点
Ａ、Ｂ・・  ポリゴン
ＥＡ、ＥＢ・・  エッジ
ＰＡ、ＰＢ・・  ペアエッジ
【図１】
0004182565.tif 000002
【図２】
0004182565.tif 000003
【図３】
0004182565.tif 000004
【図４】
0004182565.tif 000005
【図５】
0004182565.tif 000006
【図６】
0004182565.tif 000007
【図７】
0004182565.tif 000008
【図８】
0004182565.tif 000009
【図９】
0004182565.tif 000010
【図１０】
0004182565.tif 000011
【図１１】
0004182565.tif 000012
【図１２】
0004182565.tif 000013