(57)【特許請求の範囲】
【請求項１】
複数の３角形から構成された３角形集合を表現するデータを作成することができる３次元形状処理装置において、与えられた複数の３角形から構成された３角形集合を表現する可変長データを作成するデータ作成手段と、その可変長データ内に散在する孤立３角形に対応するデータを統合するデータ統合手段と、統合された各孤立３角形を区別する区切り情報を削除する区切り情報削除手段とを備えたことを特徴とする３次元形状処理装置。
【請求項２】
複数の３角形から構成された３角形集合を入力する入力部と、前記３角形集合を表現する可変長データを作成する可変長データ作成部と、該可変長データ内に散在する孤立３角形に対応するデータを統合する孤立３角形統合部と、を備え、複数の３角形から構成された３角形集合を表現するデータを作成する３角形集合表現用データ作成方法において、与えられた複数の３角形から構成された３角形集合を表現する可変長データを前記可変長データ作成部により作成し、その可変長データ内に散在する孤立３角形に対応するデータを前記孤立３角形統合部により統合し、統合された各孤立３角形を区別する区切り情報を削除することを特徴とする３角形集合表現用データ作成方法。
【請求項３】
請求項２記載の３角形集合表現用データ作成方法において、３角形集合表現用データを、孤立３角形でない３角形のデータを統合した結合非孤立３角形対応データと、孤立３角形のデータを統合した結合孤立３角形対応データと、前記結合非孤立３角形対応データ・結合孤立３角形対応データ間を区切る区切り情報とから構成したことを特徴とする３角形集合表現用データ作成方法。
【請求項４】
請求項２又は３に記載の３角形集合表現用データ作成方法をコンピュータが制御可能にプログラミングしたことを特徴とする３角形集合表現用データ作成プログラム。
【請求項５】
請求項４に記載の３角形集合表現用データ作成プログラムをコンピュータが読み取り可能な形式で記録したことを特徴とする記憶媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、３次元ＣＡＤ／ＣＡＭシステムなど３次元形状処理システムに係わり、特に、複数の３角形から構成された３角形集合を表現するデータを作成する３角形集合表現用データ作成方法に関する。
【０００２】
【従来の技術】
３次元ＣＡＤ／ＣＡＭシステムなど３次元形状処理システムの普及により３次元形状データの利用者層が拡大するに従って、ネットワーク環境において、高速なデータ転送など快適な操作性を求めるニーズが高まっており、その実現のために、３次元形状データのデータ量を縮小する必要性が高まっている。
現在、広く採用されている３次元形状の表現形式は、近似表現形式である３角形メッシュモデルであり、その３角形メッシュモデルでは、一般に、３角形メッシュは、図５（ａ）に示すような３角形の集合（３角形セット）として表現される。この３角形セット形式では、１個の３角形を常に３個の頂点の組で定義するので、３角形集合を表現するには３角形数の３倍の頂点データを記憶しておく必要がある。例えば、図５（ａ）の場合は、Ｖ０〜Ｖ１１の１２個の頂点によってＶ０Ｖ１Ｖ２、Ｖ３Ｖ４Ｖ５、Ｖ６Ｖ７Ｖ８、Ｖ９Ｖ１０Ｖ１１の４個の３角形が表現される。
従来、この３角形集合を表現するデータのデータ量を縮小するために、図５（ｂ）、（ｃ）に示したように、３角形メッシュ内において、隣接する３角形が稜線を共有して複数の３角形が連なる帯状の連続領域（３角形ストリップ）、または隣接する３角形が稜線を共有して複数の３角形が同一の頂点を共有しながら連なる扇状の連続領域（３角形ファン）に着目し、３角形メッシュを３角形ストリップの集合（３角形ストリップセット）または３角形ファンの集合（３角形ファンセット）として表現する方法が知られている。
【０００３】
この３角形ストリップセット形式または３角形ファンセット形式では、３角形ストリップ内または３角形ファン内において隣接する３角形どうしで頂点を共有し、前の３角形の２個の頂点と新しい１個の頂点によって次の３角形を定義するので、３角形セット形式よりも少ない頂点データで３角形集合を表現することができる。例えば、図５（ｂ）の３角形ストリップの場合は、Ｖ０〜Ｖ５の６個の頂点によってＶ０Ｖ１Ｖ２、Ｖ２Ｖ１Ｖ３、Ｖ２Ｖ３Ｖ４、Ｖ４Ｖ３Ｖ５の４個の３角形を表現することができるのである。また、図５（ｃ）の３角形ファンの場合は、Ｖ０〜Ｖ５の６個の頂点によってＶ０Ｖ１Ｖ２、Ｖ０Ｖ２Ｖ３、Ｖ０Ｖ３Ｖ４、Ｖ０Ｖ４Ｖ５の４個の３角形を表現することができる。
なお、３角形セット形式で記憶する頂点データが３角形数の３倍という固定長であるのに対し、連続領域に着目する３角形ストリップセット形式または３角形ファンセット形式では、各連続領域（各３角形ストリップまたは各３角形ファン）の長さは一般には一定しないため、記憶する頂点データは可変長となる。そのため、Silicon Graphics, Inc., Open Inventor Nodes Quick Reference, Release 2.0 に示された従来技術では、可変長データの一部として（３角形集合を表現する頂点データに加えて）、各連続領域を区別するための区切り情報（デリミタに相当するデータ）を記憶していた。
【０００４】
【発明が解決しようとする課題】
前記した３角形ストリップセット形式または３角形ファンセット形式では、各３角形ストリップまたは各３角形ファンが長いほど、より少ない頂点データで３角形集合を表現することができる。しかしながら、実用的な３次元形状を表現する３角形メッシュに対して３角形ストリップセット形式または３角形ファンセット形式を適用すると、しばしば、他の３角形と隣接しない孤立３角形１個のみから成る３角形ストリップまたは３角形ファンが生じることがある。このような孤立３角形を表現するには、前記した従来技術では、前記したように、３個の頂点データに加えてデリミタに相当する区切り情報を必要とするが、３角形セット形式では３個の頂点データのみでよい。したがって、孤立３角形が多い場合には、３角形セット形式に対する３角形ストリップセット形式または３角形ファンセット形式のデータサイズ縮小性能が損なわれてしまっていた。
本発明の目的は、このような従来技術の問題を解決することにあり、具体的には、可変長データ内の孤立３角形に対応するデータを統合して、不要なデータを削除することができる３角形集合表現用データ作成方法などを提供することにある。
【０００５】
【課題を解決するための手段】
前記の課題を解決するために、請求項１記載の発明では、複数の３角形から構成された３角形集合を表現するデータを作成することができる３次元形状処理装置において、与えられた複数の３角形から構成された３角形集合を表現する可変長データを作成するデータ作成手段と、その可変長データ内に散在する孤立３角形に対応するデータを統合するデータ統合手段と、統合された各孤立３角形を区別する区切り情報を削除する区切り情報削除手段とを備えたことを特徴とする。
また、請求項２記載の発明では、複数の３角形から構成された３角形集合を入力する入力部と、前記３角形集合を表現する可変長データを作成する可変長データ作成部と、該可変長データ内に散在する孤立３角形に対応するデータを統合する孤立３角形統合部と、を備え、複数の３角形から構成された３角形集合を表現するデータを作成する３角形集合表現用データ作成方法において、与えられた複数の３角形から構成された３角形集合を表現する可変長データを前記可変長データ作成部により作成し、その可変長データ内に散在する孤立３角形に対応するデータを前記孤立３角形統合部により統合し、統合された各孤立３角形を区別する区切り情報を削除することを特徴とする。
また、請求項３記載の発明では、請求項２記載の発明において、３角形集合表現用データを、孤立３角形でない３角形のデータを統合した結合非孤立３角形対応データと、孤立３角形のデータを統合した結合孤立３角形対応データと、前記結合非孤立３角形対応データ・結合孤立３角形対応データ間を区切る区切り情報とから構成したことを特徴とする。
また、請求項４記載の発明では、請求項２又は３に記載の３角形集合表現用データ作成方法をコンピュータが制御可能にプログラミングしたことを特徴とする。
また、請求項５記載の発明では、請求項４に記載の３角形集合表現用データ作成プログラムをコンピュータが読み取り可能な形式で記録したことを特徴とする。
【０００６】
【発明の実施の形態】
以下、図面により本発明の実施の形態を詳細に説明する。
図１は本発明の一実施例を示す３次元形状処理装置のハードウェアを示す構成ブロック図である。図示したように、この実施例の３次元形状処理装置は、プログラムに従って装置全体の制御・管理および本発明に係わる３角形集合表現用データ作成を含む３次元形状処理を実行するＣＰＵ１、そのプログラムやデータを一時的に記憶するメモリ２、前記プログラムやデータを記憶（保存）しておく外部記憶装置３、キーボード、マウス、着脱可能な記憶媒体からデータを読み込む記憶媒体駆動装置などを有して指示を与えたりデータを入力したりする入力装置４、３次元形状モデルなどを表示する表示装置５を備えている。
また、図２は、このようなハードウェアを用いて構築される、本発明の一実施例を示す３次元形状処理システム要部の構成ブロック図である。図示したように、この３次元形状処理システムは、複数の３角形から構成された３角形集合などを入力する入力部１１、その３角形集合を表現する可変長データを作成する可変長データ作成部１２、その可変長データ内に散在する孤立３角形に対応するデータを統合したりする孤立３角形統合部１３、作成された３角形集合表現用データを表示部などに出力する出力部１４、表示装置５に表示する表示データを作成したりする表示部１５などを備える。なお、この実施例では、請求項１記載のデータ作成手段は可変長データ作成部１２により実現され、データ統合手段および区切り情報削除手段は孤立３角形統合部１３により実現される。また、前記入力部１１、可変長データ作成部１２、孤立３角形統合部１３、出力部１４、および表示部１５は、図１に示したＣＰＵ１およびメモリ２などにより実現される。
【０００７】
図３に、この実施例の動作フローを示す。以下、図３に従って、この実施例の動作を説明する。
まず、複数の３角形から構成された３角形集合に係わるデータをメモリ２に読み込む（Ｓ１）。入力装置４を用いてそのデータを入力するか、予め外部記憶装置３に格納されているデータを読み込むのである。
続いて、可変長データ作成部１２が、３角形集合を表現する可変長データを作成する（Ｓ２）。可変長データが３角形ストリップセット形式であれば、例えば次のようにして作成するのである。
（１）全３角形のうち３角形ストリップの構成要素になっていない３角形の集をＵとし、Ｕに属する任意の一つの３角形を新しい３角形ストリップＳの開始３角形とする。その際、Ｕが空の場合は終了とする。
（２）開始３角形に稜線を共有して隣接する２番目の３角形をＵから選択し、さらに、その２番目の３角形に稜線を共有して隣接する３番目の３角形をＵから選択してはＳの構成要素として取り込む操作を繰り返し、Ｓを延ばす。
（３）これ以上Ｓを延ばせなくなったら、Ｓの構成要素である３角形集合を表現する頂点データの先頭に、デリミタに相当する区切り情報として頂点データの個数を付与し、３角形ストリップデータとして登録し、（１）に戻る。
【０００８】
また、可変長データが３角形ファンセット形式の場合は、例えば次のようにして作成する。
（１１）全３角形のうち３角形ファンの構成要素になっていない３角形の集合をＵとし、Ｕに属する任意の一つの３角形を新しい３角形ファンＦの開始３角形とする。その際、Ｕが空の場合は終了とする。
（１２）開始３角形から順に同一の頂点と稜線を共有しながら隣接するような３角形をＵから選択してはＦの構成要素として取り込み、Ｆを延ばす。
（１３）これ以上Ｆを延ばせなくなったら、Ｆの構成要素である３角形集合を表現する頂点データの先頭に、デリミタに相当する区切り情報として頂点データの個数を付与し、３角形ファンデータとして登録し、（１１）に戻る。
こうして、可変長データを作成した後、孤立３角形統合部１３が、可変長データ内の孤立３角形を前記頂点データの個数から判断し、その結果から孤立３角形に対応するデータを統合し、各孤立３角形を区別するためのデリミタに相当する区切り情報を削除してデータの総量を減らす（Ｓ３）。そして、出力部１４が３角形集合表現用データとして出力する（Ｓ４）。
【０００９】
次に、前記したステップＳ３について図４に従って詳細を説明する。
まず、可変長データ内の孤立３角形以外に対応するデータを抽出する（Ｓ１１）。例えば、前記ステップＳ２においてデリミタに相当するデータとして頂点データの個数を付与する場合、その値が４以上であるデータを抽出すればよい。
さらに、孤立３角形以外に対応するデータを結合し（Ｓ１２）、結合非孤立３角形対応データとする。
続いて、可変長データ内の孤立３角形に対応するデータを抽出する（Ｓ１３）。例えば、前記ステップＳ２においてデリミタに相当する区切り情報として頂点データの個数を付与する場合、その値が３であるデータを抽出すればよい。
さらに、孤立３角形に対応するデータからデリミタに相当する頂点データを削除してデータの総量を減らす（Ｓ１４）。そして、デリミタに相当する頂点データを削除した孤立３角形に対応するデータを結合する（Ｓ１５）。これにより、結合されたデータは、先頭から３個ずつの組がそれぞれ１個の孤立３角形を定義するような頂点データとなる。
続いて、結合された頂点データの先頭に、結合非孤立３角形対応データ内に含まれるいかなるデリミタに相当するデータとも異なる特殊なデリミタに相当する区切り情報（例えば負の整数値）を付与し（Ｓ１６）、結合孤立３角形対応データとする。そして、結合非孤立３角形対応データの後に結合孤立３角形対応データを結合し（Ｓ１７）、３角形集合表現用データとして出力する（Ｓ１８）。このとき、３角形集合表現用データは元の可変長データよりも総量が減っており、特定した特殊なデリミタに相当する区切り情報以降は３個ずつの組がそれぞれ１個の孤立３角形を定義するような頂点データとなっている。
【００１０】
以上、本発明の３角形集合表現用データ作成方法について説明したが、説明したような方法に従ってプログラミングしたプログラムを例えば着脱可能な記憶媒体に記憶し、その記憶媒体をこれまで本発明によった３角形集合表現用データ作成を行なえなかったパーソナルコンピュータなど情報処理装置に装着することにより、または、そのプログラムをネットワークを介してそのような情報処理装置へ転送することにより、その情報処理装置においても本発明によった３角形集合表現用データを作成することができる。
【００１１】
【発明の効果】
以上説明したように、本発明によれば、請求項１および請求項２記載の発明では、複数の３角形から構成された３角形集合を表現するデータを作成する際、与えられた複数の３角形から構成された３角形集合を表現する可変長データが作成され、その可変長データ内に散在する孤立３角形に対応するデータが統合され、統合された各孤立３角形を区別する区切り情報が削除されるので、３角形集合表現用データのデータ量を減らすことができ、したがって、例えば３角形集合表現用データをネットワークを介して転送するような場合、通信時間を短くすることができる。
また、請求項３記載の発明では、請求項２記載の発明において、３角形集合表現用データが、孤立３角形でない３角形のデータを統合した結合非孤立３角形対応データと、孤立３角形のデータを統合した結合孤立３角形対応データと、その結合非孤立３角形対応データ・結合孤立３角形対応データ間を区切る区切り情報とから構成されるので、結合孤立３角形対応データを容易に識別することができるし、各孤立３角形を区別する区切り情報が削除されていても個々の孤立３角形を容易に識別することができる。
【００１２】
また、請求項４記載の発明では、本発明の３角形集合表現用データ作成方法をコンピュータが制御可能なＯＳに従ってプログラミングすることにより、そのＯＳを備えたコンピュータであれば同じ処理方法により制御することができる。
また、請求項５記載の発明では、請求項４に記載の３角形集合表現用データ作成方法に従ってプログラミングしたプログラムが例えば着脱可能な記憶媒体に記憶されるので、その記憶媒体をこれまで請求項２乃至請求項５のいずれか１項に記載の発明によった３角形集合表現用データ作成を行なえなかったパーソナルコンピュータなど情報処理装置に装着することにより、その情報処理装置においても請求項２又は３に記載の発明の効果を得ることができる。
【図面の簡単な説明】
【図１】本発明の一実施例を示す３次元形状処理装置の構成ブロック図である。
【図２】本発明の一実施例を示す３次元形状処理システム要部の構成ブロック図である。
【図３】本発明の一実施例を示す３角形集合表現用データ作成方法の動作フロー図である。
【図４】本発明の一実施例を示す３角形集合表現用データ作成方法要部の動作フロー図である。
【図５】従来技術の一例を示す３角形集合表現用データ作成方法の説明図である。
【符号の説明】
１  ＣＰＵ、２  メモリ、３  外部記憶装置、４  入力装置、５  表示装置、１１  入力部、１２  可変長データ作成部、１３  孤立３角形統合部、１４  出力部、１５  表示部
【図１】
0004012715.tif 000002
【図２】
0004012715.tif 000003
【図３】
0004012715.tif 000004
【図４】
0004012715.tif 000005
【図５】
0004012715.tif 000006