図形処理装置

【課題】図形ブーリアン演算の演算誤差の発生を抑制して、３次元形状オブジェクトの見える部分を構成しているポリゴンの形状を正確に抽出することができる図形処理装置を得ることを目的とする。
【解決手段】ポリゴン形状出力部７が、遮蔽判定処理部６によりポリゴンの面が輪郭形状により遮蔽されていないと判定された場合、そのポリゴンの形状を出力し、遮蔽判定処理部６によりポリゴンの面の一部が輪郭形状により遮蔽されていると判定された場合、そのポリゴンの面と輪郭形状間で図形ブーリアン演算を実施することで、その輪郭形状に遮蔽されている面が除かれているポリゴンを生成して、そのポリゴンの形状を出力する。

【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、３次元空間内の視点から複数のポリゴンで構成されている３次元形状のオブジェクトを見たときに、そのオブジェクトの見える部分を構成しているポリゴンの形状を抽出する図形処理装置に関するものである。
【背景技術】
【０００２】
複数のポリゴンで構成されている３次元形状のオブジェクトを描画する一般的な図形処理装置には、３次元空間内の視点（例えば、ユーザにより指定された位置）から３次元形状のオブジェクトを見たときに、そのオブジェクトの見える部分を構成しているポリゴンの形状を抽出する処理を実施する機能が備えられている。
このようなポリゴンの形状抽出処理では、３次元形状のオブジェクトを構成しているポリゴンが、例えば、ポリゴンＡとポリゴンＢである場合、ポリゴンＡとポリゴンＢの遮蔽関係を判定する必要がある。
【０００３】
視点から３次元形状のオブジェクトを見たときに、ポリゴンＡがポリゴンＢに完全に遮蔽されている場合、そのオブジェクトの見える部分を構成しているポリゴンはポリゴンＢだけであり、ポリゴンＡは該当しない。
一方、ポリゴンＢがポリゴンＡに完全に遮蔽されている場合、そのオブジェクトの見える部分を構成しているポリゴンはポリゴンＡだけであり、ポリゴンＢは該当しない。
【０００４】
視点から３次元形状のオブジェクトを見たときに、ポリゴンＡの一部がポリゴンＢに遮蔽されている場合、ポリゴンＢに遮蔽されていない部分のポリゴンＡの形状を算出する必要がある。
一方、ポリゴンＢの一部がポリゴンＡに遮蔽されている場合、ポリゴンＡに遮蔽されていない部分のポリゴンＢの形状を算出する必要がある。
例えば、ポリゴンＢに遮蔽されていない部分のポリゴンＡの形状の算出には、図形ブーリアン演算（ポリゴンＡ−ポリゴンＢ）などを利用することができる。
【０００５】
ここでは、３次元形状のオブジェクトがポリゴンＡとポリゴンＢから構成されている場合について示したが、３次元形状のオブジェクトがＮ個のポリゴンから構成されている場合、ポリゴン間の遮蔽関係を判定する処理をＮ×（Ｎ−１）回実施して、一部遮蔽していることが判明すれば、図形ブーリアン演算を実施して、遮蔽されていない部分のポリゴンの形状を算出する必要がある。
以下、ポリゴンの一部が他のポリゴンに遮蔽されている場合に、他のポリゴンに遮蔽されていない部分のポリゴンの形状を算出する処理の具体例を説明する。
【０００６】
図１０はポリゴンＣ１，Ｃ２，Ｃ３，Ｃ４によって一部が遮蔽されているポリゴンＡの抽出処理を示す説明図である。
この場合、ポリゴンＡとポリゴンＣ１間で図形ブーリアン演算を実施し、その演算結果（ポリゴンＣ１に遮蔽されていない部分のポリゴンＡ）とポリゴンＣ２間で図形ブーリアン演算を実施する。
また、その演算結果（ポリゴンＣ１，Ｃ２に遮蔽されていない部分のポリゴンＡ）とポリゴンＣ３間で図形ブーリアン演算を実施し、その演算結果（ポリゴンＣ１，Ｃ２，Ｃ３に遮蔽されていない部分のポリゴンＡ）とポリゴンＣ４間で図形ブーリアン演算を実施する。
これにより、ポリゴンＣ１，Ｃ２，Ｃ３，Ｃ４に遮蔽されていない部分のポリゴンＡが生成される。
このように、前の図形ブーリアン演算の演算結果が、次の図形ブーリアン演算に用いられる。
【０００７】
この演算の過程で、ポリゴンとポリゴンの図形ブーリアン演算を実施した結果、非常に小さな形状や極端に細長い形状のポリゴン（他のポリゴンに遮蔽されていない部分のポリゴン）が生成される場合がある。
このとき、非常に小さな形状や極端に細長い形状のポリゴンと、他のポリゴンとの間で図形ブーリアン演算を実施する場合、演算誤差によって、正しい形状のポリゴンを生成することができない場合がある。
例えば、ポリゴンの頂点データは、浮動小数点で表現されることが多いが、微少ポリゴンや極端に細長いポリゴン（例えば、ポリゴンの頂点間が非常に小さい場合など）が図形ブーリアン演算の対象になると、情報落ちなどの誤差が発生して、幾何学的な状態が崩れる場合がある。
【０００８】
具体的には、例えば、図１１に示すように、非常に細長い三角形Ｂが三角形Ａにより遮蔽されている場合、点線の丸で囲まれている２つの部分が図形ブーリアン演算（三角形Ｂ−三角形Ａ）により求まる。
しかし、頂点１，頂点２，頂点３で構成される三角形Ｃにおいて、頂点１と頂点２の位置が非常に接近している場合、頂点１及び頂点２を算出する過程の計算で、浮動小数点演算の誤差が発生する。例えば、Ａｘ＋Ｂｙにおいて、Ａ，Ｂの値が大きく、ｘ，ｙが非常に小さい値の場合に誤差が発生する。
【０００９】
この演算誤差によって、三角形Ｃの頂点１と頂点２の位置が逆転するような演算結果になると、三角形Ｃの形状が崩壊する。
この場合、本来、頂点１，頂点２，頂点３が反時計回りになる形状が、演算誤差によって、時計回りの形状になる。
このような現象によって、ポリゴンの表裏の関係や、ポリゴンの内部・外部の判定を間違うことになる。
【００１０】
なお、以下の特許文献１には、複数のポリゴン間で共有する辺を削除することで、３次元形状オブジェクトの輪郭形状を抽出する技術が開示されているが、浮動小数点演算の誤差の発生を抑制する技術については開示されていない。
【先行技術文献】
【特許文献】
【００１１】
【特許文献１】特開平６−２６６８１９号公報（段落番号［０００６］から［００１１］、図１）
【発明の概要】
【発明が解決しようとする課題】
【００１２】
従来の図形処理装置は以上のように構成されているので、３次元形状のオブジェクトを構成しているポリゴン単位で、図形ブーリアン演算を繰り返し実施する場合、その図形ブーリアン演算の途中で、微少ポリゴンや極端に細長いポリゴンが生成されて、そのポリゴンが次の図形ブーリアン演算の対象になると、演算誤差が発生して、３次元形状のオブジェクトの見える部分を構成しているポリゴンの形状を正確に抽出することができなくなる課題があった。
【００１３】
この発明は上記のような課題を解決するためになされたもので、図形ブーリアン演算の演算誤差の発生を抑制して、３次元形状のオブジェクトの見える部分を構成しているポリゴンの形状を正確に抽出することができる図形処理装置を得ることを目的とする。
【課題を解決するための手段】
【００１４】
この発明に係る図形処理装置は、３次元空間内の視点から、複数のポリゴンで構成されている３次元形状のオブジェクトを見たときに、そのオブジェクトの表面を構成している１以上のポリゴンを抽出する表面ポリゴン抽出手段と、表面ポリゴン抽出手段により抽出された１以上のポリゴンを２次元平面上に投影変換する投影変換手段と、投影変換手段により２次元平面上に投影変換された１以上のポリゴンが構成しているオブジェクトの表面の中で、連続している表面をオブジェクトの輪郭形状として抽出する輪郭形状抽出手段と、表面ポリゴン抽出手段により抽出されたポリゴン毎に、当該ポリゴンの面が輪郭形状抽出手段により抽出された輪郭形状に遮蔽されているか否かを判定する遮蔽判定手段とを設け、ポリゴン形状出力手段が、遮蔽判定手段によりポリゴンの面が輪郭形状により遮蔽されていないと判定された場合、そのポリゴンの形状を出力し、遮蔽判定手段によりポリゴンの面の一部が輪郭形状により遮蔽されていると判定された場合、そのポリゴンの面と輪郭形状間で図形ブーリアン演算を実施することで、その輪郭形状に遮蔽されている面が除かれているポリゴンを生成して、そのポリゴンの形状を出力するようにしたものである。
【発明の効果】
【００１５】
この発明によれば、３次元空間内の視点から、複数のポリゴンで構成されている３次元形状のオブジェクトを見たときに、そのオブジェクトの表面を構成している１以上のポリゴンを抽出する表面ポリゴン抽出手段と、表面ポリゴン抽出手段により抽出された１以上のポリゴンを２次元平面上に投影変換する投影変換手段と、投影変換手段により２次元平面上に投影変換された１以上のポリゴンが構成しているオブジェクトの表面の中で、連続している表面をオブジェクトの輪郭形状として抽出する輪郭形状抽出手段と、表面ポリゴン抽出手段により抽出されたポリゴン毎に、当該ポリゴンの面が輪郭形状抽出手段により抽出された輪郭形状に遮蔽されているか否かを判定する遮蔽判定手段とを設け、ポリゴン形状出力手段が、遮蔽判定手段によりポリゴンの面が輪郭形状により遮蔽されていないと判定された場合、そのポリゴンの形状を出力し、遮蔽判定手段によりポリゴンの面の一部が輪郭形状により遮蔽されていると判定された場合、そのポリゴンの面と輪郭形状間で図形ブーリアン演算を実施することで、その輪郭形状に遮蔽されている面が除かれているポリゴンを生成して、そのポリゴンの形状を出力するように構成したので、図形ブーリアン演算の演算誤差の発生を抑制して、３次元形状のオブジェクトの見える部分を構成しているポリゴンの形状を正確に抽出することができる効果がある。
【図面の簡単な説明】
【００１６】
【図１】この発明の実施の形態１による図形処理装置を示す構成図である。
【図２】この発明の実施の形態１による図形処理装置を構成しているコンピュータを示す構成図である。
【図３】この発明の実施の形態１による図形処理装置の処理内容を示すフローチャートである。
【図４】複数のポリゴンで構成されている３次元形状のオブジェクトの一例を示す説明図である。
【図５】ポリゴンを平行投影変換することで、ポリゴンが２次元平面上に投影変換された例を示す説明図である。
【図６】ポリゴン形状出力部７から出力されるポリゴンの形状を示す説明図である。
【図７】オブジェクトの輪郭形状の抽出例を示す説明図である。
【図８】この発明の実施の形態３による図形処理装置を示す構成図である。
【図９】オブジェクトの輪郭形状の抽出例を示す説明図である。
【図１０】ポリゴンＣ１，Ｃ２，Ｃ３，Ｃ４によって一部が遮蔽されているポリゴンＡの抽出処理を示す説明図である。
【図１１】図形ブーリアン演算により求まる三角形の一例を示す説明図である。
【発明を実施するための形態】
【００１７】
実施の形態１．
図１はこの発明の実施の形態１による図形処理装置を示す構成図である。
図１において、視点受付部１は例えばキーボードやマウスなどのマンマシンインタフェース等から構成されており、複数のポリゴンで構成されている３次元形状のオブジェクトを見る３次元空間内の視点の位置を受け付ける処理を実施する。
データ記憶部２は３次元形状のオブジェクトを構成している複数のポリゴンのデータを記憶しているメモリである。
【００１８】
表面ポリゴン抽出部３は視点受付部１により位置が受け付けられた３次元空間内の視点から、３次元形状のオブジェクトを見たときに、そのオブジェクトの表面を構成している１以上のポリゴンを抽出する処理を実施する。なお、表面ポリゴン抽出部３は表面ポリゴン抽出手段を構成している。
投影変換処理部４は表面ポリゴン抽出部３により抽出された１以上のポリゴンを２次元平面上に投影変換する処理を実施する。なお、投影変換処理部４は投影変換手段を構成している。
【００１９】
輪郭形状抽出部５は投影変換処理部４により２次元平面上に投影変換された１以上のポリゴンが構成しているオブジェクトの表面の中で、連続している表面をオブジェクトの輪郭形状として抽出する処理を実施する。なお、輪郭形状抽出部５は輪郭形状抽出手段を構成している。
遮蔽判定処理部６は表面ポリゴン抽出部３により抽出されたポリゴン毎に、当該ポリゴンの面が輪郭形状抽出部５により抽出された輪郭形状に遮蔽されているか否かを判定する処理を実施する。なお、遮蔽判定処理部６は遮蔽判定手段を構成している。
【００２０】
ポリゴン形状出力部７は遮蔽判定処理部６によりポリゴンの面が輪郭形状により遮蔽されていないと判定された場合、そのポリゴンの形状を出力し、遮蔽判定処理部６によりポリゴンの面の一部が輪郭形状により遮蔽されていると判定された場合、そのポリゴンの面と輪郭形状間で図形ブーリアン演算を実施することで、その輪郭形状に遮蔽されている面が除かれているポリゴンを生成して、そのポリゴンの形状を出力する処理を実施する。なお、ポリゴン形状出力部７はポリゴン形状出力手段を構成している。
【００２１】
図１の例では、図形処理装置の構成要素である視点受付部１、データ記憶部２、表面ポリゴン抽出部３、投影変換処理部４、輪郭形状抽出部５、遮蔽判定処理部６及びポリゴン形状出力部７のそれぞれが専用のハードウェア（例えば、ＣＰＵを実装している半導体集積回路、あるいは、ワンチップマイコンなど）で構成されているものを想定しているが、図形処理装置がコンピュータで構成される場合、視点受付部１、データ記憶部２、表面ポリゴン抽出部３、投影変換処理部４、輪郭形状抽出部５、遮蔽判定処理部６及びポリゴン形状出力部７の処理内容を記述しているプログラムをコンピュータのメモリに格納し、当該コンピュータのＣＰＵが当該メモリに格納されているプログラムを実行するようにしてもよい。
【００２２】
図２はこの発明の実施の形態１による図形処理装置を構成しているコンピュータを示す構成図である。
図２において、アプリケーションメモリ１１はコンピュータに内蔵されているＲＡＭやハードディスクなどの記録媒体であり、図形処理装置の構成要素である視点受付部１、データ記憶部２、表面ポリゴン抽出部３、投影変換処理部４、輪郭形状抽出部５、遮蔽判定処理部６及びポリゴン形状出力部７の処理内容を記述しているプログラムであるアプリケーションを格納している。
システムメモリ１２は演算プロセッサ１３に実行される命令コードや、３次元形状のオブジェクトを構成している複数のポリゴンのデータなどを保持しているＲＡＭやハードディスクなどの記録媒体である。
【００２３】
演算プロセッサ１３は例えばＣＰＵなどから構成されており、システムメモリ１２に保持されている命令コードを参照しながら、アプリケーションメモリ１１に格納されているアプリケーションを実行する。
なお、演算プロセッサ１３には、ＯＳなどが実装されており、このＯＳ上で、アプリケーションメモリ１１に格納されているアプリケーションやタスクが動作することで、３次元形状オブジェクトの見える部分を構成しているポリゴンだけを正確に抽出する処理を実施する。
図３はこの発明の実施の形態１による図形処理装置の処理内容を示すフローチャートである。
【００２４】
次に動作について説明する。
ここでは、説明の便宜上、複数のポリゴンで構成されている３次元形状のオブジェクトが、図４に示すように、頂点Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ，Ｇ，Ｈ，Ｉ，Ｊ，Ｋを有する物体Ａであるものとする。
この３次元形状のオブジェクトは、ＸＺ平面における断面が図４のような形状を有している。
この３次元形状のオブジェクトのＹ軸は図４の奥行き方向であり、図４の○印の位置が視点であるとすると、その視点から３次元形状のオブジェクトを見た場合、図４の太線で表されている面が見える面になり、細線で表されている面が見えない面になる。
【００２５】
視点受付部１は、３次元形状のオブジェクトを見る視点の位置を受け付けて、その視点の位置を示す位置情報を表面ポリゴン抽出部３に出力する。
表面ポリゴン抽出部３は、視点受付部１から位置情報を受けると、データ記憶部２により記憶されている３次元形状のオブジェクトを構成している複数のポリゴンのデータを取得する。
表面ポリゴン抽出部３は、視点受付部１から出力された位置情報が示す視点の位置から、３次元形状のオブジェクトを見たときに、そのオブジェクトの表面を構成している１以上のポリゴンを抽出する（ステップＳＴ１）。
【００２６】
表面を構成しているポリゴンの抽出方法としては、次のような方法を用いることができる。
ポリゴン面の法線が定義されている場合は（例えば、法線ベクトルが、Ｘ軸を起点にして、Ｚ軸に平行な方向である場合）、他の面にぶつかることなく、法線ベクトルがあたる面は３次元形状のオブジェクトの表面であり、他の面にぶつかってから、法線ベクトルがあたる面は３次元形状のオブジェクトの裏面であると判断すれば、３次元形状のオブジェクトの表面を構成しているポリゴンを抽出することができる。
一方、ポリゴン面の法線が定義されていない場合は、３次元形状のオブジェクトの形成時に決められた頂点の並び順と表裏の関係を考慮して、３次元形状のオブジェクトの面が表面であるか否かを判定すれば、３次元形状のオブジェクトの表面を構成しているポリゴンを抽出することができる。
【００２７】
図４の例では、頂点Ｆ−頂点Ｇ、頂点Ｈ−頂点Ｉ、頂点Ｊ−頂点Ｋ、頂点Ｋ−頂点Ａの間のポリゴンの面が３次元形状のオブジェクトの裏面と判定されて削除され、他の頂点間のポリゴンの面が３次元形状のオブジェクトの表面として抽出される。
即ち、頂点Ａ−頂点Ｂ−頂点Ｃ−頂点Ｄ−頂点Ｅ−頂点Ｆ、頂点Ｇ−頂点Ｈ、頂点Ｉ−頂点Ｊの間のポリゴンの面が３次元形状のオブジェクトの表面として抽出される。
【００２８】
投影変換処理部４は、表面ポリゴン抽出部３が３次元形状のオブジェクトの表面を構成している１以上のポリゴンを抽出すると、それらのポリゴンを２次元平面上に投影変換する（ステップＳＴ２）。
ポリゴンを２次元平面上に投影変換する方法としては、一般的に、ポリゴンを平行投影変換する方法や、ポリゴンを透視投影変換する方法などが考えられる。
ポリゴンを平行投影変換する場合、ポリゴンデータの奥行き情報を切り捨てる作業を実施することになる。例えば、図４に示す視点からＺ軸方向を見る場合において、Ｚ軸と垂直な面への投影であれば、Ｚ座標の情報を切り捨てることになる。
一方、ポリゴンを透視投影変換する場合、ポリゴンのＸ座標及びＹ座標をＺ座標で割り算することで変換することができる。
【００２９】
ここで、図５はポリゴンを平行投影変換することで、ポリゴンが２次元平面上に投影変換された例を示す説明図である。
ポリゴンが平行投影変換されている場合、ポリゴンデータの奥行き情報がなくなっているが、図５の例では、仮想的に奥行きの順番で並べられている。
【００３０】
輪郭形状抽出部５は、投影変換処理部４が１以上のポリゴンを２次元平面上に投影変換すると、それらのポリゴンが構成しているオブジェクトの表面の中で、連続している表面をオブジェクトの輪郭形状として抽出する（ステップＳＴ３）。
例えば、投影変換処理部４により投影変換された１以上のポリゴンの面が、頂点Ａ−頂点Ｂ−頂点Ｃ−頂点Ｄ−頂点Ｅ−頂点Ｆの間のポリゴンの面であれば、最初に、頂点Ａ−頂点Ｂのポリゴンと、頂点Ｂの位置の辺を共有している隣接のポリゴンである頂点Ｂ−頂点Ｃのポリゴンを調べることで、頂点Ａ−頂点Ｂ−頂点Ｃからなる面は、連続している表面であると認識する。
次に、頂点Ｂ−頂点Ｃのポリゴンと、頂点Ｃの位置の辺を共有している隣接のポリゴンである頂点Ｃ−頂点Ｄのポリゴンを調べることで、頂点Ａ−頂点Ｂ−頂点Ｃ−頂点Ｄからなる面は、連続している表面であると認識する。
次に、頂点Ｃ−頂点Ｄのポリゴンと、頂点Ｄの位置の辺を共有している隣接のポリゴンである頂点Ｄ−頂点Ｅのポリゴンを調べることで、頂点Ａ−頂点Ｂ−頂点Ｃ−頂点Ｄ−頂点Ｅからなる面は、連続している表面であると認識する。
最後に、頂点Ｄ−頂点Ｅのポリゴンと、頂点Ｅの位置の辺を共有している隣接のポリゴンである頂点Ｅ−頂点Ｆのポリゴンを調べることで、頂点Ａ−頂点Ｂ−頂点Ｃ−頂点Ｄ−頂点Ｅ−頂点Ｆからなる面は、連続している表面であると認識する。
これにより、図５の例では、頂点Ａ−頂点Ｂ−頂点Ｃ−頂点Ｄ−頂点Ｅ−頂点Ｆからなる面を輪郭形状（１）として抽出する。
【００３１】
投影変換処理部４により投影変換されたポリゴンの面が、頂点Ｇ−頂点Ｈの間のポリゴンの面であれば、頂点Ｇ−頂点Ｈのポリゴンと、頂点Ｈの位置の辺を共有している３次元形状のオブジェクトの表面であるポリゴンがなく（頂点Ｈ−頂点Ｉのポリゴンは、頂点Ｈの位置の辺を共有しているが、３次元形状のオブジェクトの裏面であるため除外される）、また、頂点Ｇ−頂点Ｈのポリゴンと、頂点Ｇの位置の辺を共有している３次元形状のオブジェクトの表面であるポリゴンがないので（頂点Ｆ−頂点Ｇのポリゴンは、頂点Ｇの位置の辺を共有しているが、３次元形状のオブジェクトの裏面であるため除外される）、図５の例では、頂点Ｇ−頂点Ｈからなる面を輪郭形状（２）として抽出する。
【００３２】
投影変換処理部４により投影変換されたポリゴンの面が、頂点Ｉ−頂点Ｊの間のポリゴンの面であれば、頂点Ｉ−頂点Ｊのポリゴンと、頂点Ｉの位置の辺を共有しているオブジェクトの表面であるポリゴンがなく（頂点Ｈ−頂点Ｉのポリゴンは、頂点Ｉの位置の辺を共有しているが、オブジェクトの裏面であるため除外される）、また、頂点Ｉ−頂点Ｊのポリゴンと、頂点Ｊの位置の辺を共有しているオブジェクトの表面であるポリゴンがないので（頂点Ｋ−頂点Ｊのポリゴンは、頂点Ｊの位置の辺を共有しているが、オブジェクトの裏面であるため除外される）、図５の例では、頂点Ｉ−頂点Ｊからなる面を輪郭形状（３）として抽出する。
【００３３】
遮蔽判定処理部６は、輪郭形状抽出部５がオブジェクトの輪郭形状（１）（２）（３）を抽出すると、表面ポリゴン抽出部３により抽出されたポリゴン毎に、当該ポリゴンの面と輪郭形状抽出部５により抽出された輪郭形状（１）（２）（３）間の遮蔽関係を検証する（ステップＳＴ４）。
遮蔽判定処理部６は、当該ポリゴンの面と輪郭形状（１）（２）（３）間の遮蔽関係を検証することで、当該ポリゴンの面の一部が輪郭形状（１）（２）（３）に遮蔽されているか、当該ポリゴンの面が輪郭形状（１）（２）（３）に遮蔽されていないか（または、当該ポリゴンの面が輪郭形状（１）（２）（３）と同一面であるのか）、当該ポリゴンの面が輪郭形状（１）（２）（３）に完全に遮蔽されているかを判別する（ステップＳＴ５，ＳＴ６）。
【００３４】
具体的には、以下の通りである
最初に、遮蔽判定処理部６は、オブジェクトの表面を構成しているポリゴンの中で、頂点Ａ−頂点Ｂのポリゴンの面と、輪郭形状（１）の間の遮蔽関係を検証する（ステップＳＴ４）。
頂点Ａ−頂点Ｂのポリゴンの面と輪郭形状（１）は同一面であるため、頂点Ａ−頂点Ｂのポリゴンの面が輪郭形状（１）に遮蔽されていないと判別され（ステップＳＴ５，ＳＴ６）、遮蔽関係の検証対象が輪郭形状（２）に変更される（ステップＳＴ８，ＳＴ９）。
【００３５】
これにより、遮蔽判定処理部６は、頂点Ａ−頂点Ｂのポリゴンの面と、輪郭形状（２）の間の遮蔽関係を検証する（ステップＳＴ４）。
輪郭形状（２）は頂点Ａ−頂点Ｂのポリゴンの面の奥側に存在しているため、頂点Ａ−頂点Ｂのポリゴンの面は、輪郭形状（２）に遮蔽されていないと判別され（ステップＳＴ５，ＳＴ６）、遮蔽関係の検証対象が輪郭形状（３）に変更される（ステップＳＴ８，ＳＴ９）。
これにより、遮蔽判定処理部６は、頂点Ａ−頂点Ｂのポリゴンの面と、輪郭形状（３）の間の遮蔽関係を検証する（ステップＳＴ４）。
輪郭形状（３）は頂点Ａ−頂点Ｂのポリゴンの面の奥側に存在しているため、頂点Ａ−頂点Ｂのポリゴンの面は、輪郭形状（３）に遮蔽されていないと判別される（ステップＳＴ５，ＳＴ６）。
【００３６】
図５の例では、この段階で、全ての輪郭形状が遮蔽関係の検証対象にされているので（ステップＳＴ８，ＳＴ９）、頂点Ａ−頂点Ｂのポリゴンの面に対する遮蔽関係の検証処理を終了する。
以上より、遮蔽判定処理部６によって、頂点Ａ−頂点Ｂのポリゴンの面が、輪郭形状（１）（２）（３）に遮蔽されていないと判別されているので、ポリゴン形状出力部７が、頂点Ａ−頂点Ｂのポリゴンの形状を出力する（ステップＳＴ１０）。
【００３７】
次に、遮蔽判定処理部６は、オブジェクトの表面を構成しているポリゴンの中で、頂点Ｂ−頂点Ｃのポリゴンの面を遮蔽関係の検証対象に選択し（ステップＳＴ１１，ＳＴ１２）、頂点Ｂ−頂点Ｃのポリゴンの面と、輪郭形状（１）の間の遮蔽関係を検証する（ステップＳＴ４）。
頂点Ｂ−頂点Ｃのポリゴンの面と輪郭形状（１）は同一面であるため、頂点Ｂ−頂点Ｃのポリゴンの面が輪郭形状（１）に遮蔽されていないと判別され（ステップＳＴ５，ＳＴ６）、遮蔽関係の検証対象が輪郭形状（２）に変更される（ステップＳＴ８，ＳＴ９）。
【００３８】
これにより、遮蔽判定処理部６は、頂点Ｂ−頂点Ｃのポリゴンの面と、輪郭形状（２）の間の遮蔽関係を検証する（ステップＳＴ４）。
輪郭形状（２）は頂点Ｂ−頂点Ｃのポリゴンの面の奥側に存在しているため、頂点Ｂ−頂点Ｃのポリゴンの面は、輪郭形状（２）に遮蔽されていないと判別され（ステップＳＴ５，ＳＴ６）、遮蔽関係の検証対象が輪郭形状（３）に変更される（ステップＳＴ８，ＳＴ９）。
これにより、遮蔽判定処理部６は、頂点Ｂ−頂点Ｃのポリゴンの面と、輪郭形状（３）の間の遮蔽関係を検証する（ステップＳＴ４）。
輪郭形状（３）は頂点Ｂ−頂点Ｃのポリゴンの面の奥側に存在しているため、頂点Ｂ−頂点Ｃのポリゴンの面は、輪郭形状（３）に遮蔽されていないと判別される（ステップＳＴ５，ＳＴ６）。
【００３９】
図５の例では、この段階で、全ての輪郭形状が遮蔽関係の検証対象にされているので（ステップＳＴ８，ＳＴ９）、頂点Ｂ−頂点Ｃのポリゴンの面に対する遮蔽関係の検証処理を終了する。
以上より、遮蔽判定処理部６によって、頂点Ｂ−頂点Ｃのポリゴンの面が、輪郭形状（１）（２）（３）に遮蔽されていないと判別されているので、ポリゴン形状出力部７が、頂点Ｂ−頂点Ｃのポリゴンの形状を出力する（ステップＳＴ１０）。
【００４０】
３次元形状オブジェクトの表面を構成しているポリゴンの中で、頂点Ｃ−頂点Ｄのポリゴンの面、頂点Ｄ−頂点Ｅのポリゴンの面、頂点Ｅ−頂点Ｆのポリゴンの面についても、頂点Ａ−頂点Ｂのポリゴンの面や、頂点Ｂ−頂点Ｃのポリゴンの面と同様に検証される。
頂点Ｃ−頂点Ｄのポリゴンの面、頂点Ｄ−頂点Ｅのポリゴンの面、頂点Ｅ−頂点Ｆのポリゴンの面についても、輪郭形状（１）（２）（３）によって遮蔽されていないと判別されるので、ポリゴン形状出力部７が、頂点Ｃ−頂点Ｄのポリゴンの形状、頂点Ｄ−頂点Ｅのポリゴンの形状、頂点Ｅ−頂点Ｆのポリゴンの形状を出力する（ステップＳＴ１０）。
【００４１】
次に、遮蔽判定処理部６は、３次元形状オブジェクトの表面を構成しているポリゴンの中で、頂点Ｇ−頂点Ｈのポリゴンの面を遮蔽関係の検証対象に選択し（ステップＳＴ１１，ＳＴ１２）、頂点Ｇ−頂点Ｈのポリゴンの面と、輪郭形状（１）の間の遮蔽関係を検証する（ステップＳＴ４）。
輪郭形状（１）は頂点Ｇ−頂点Ｈのポリゴンの面の手前側に存在しており、頂点Ｇ−頂点Ｈのポリゴンの面の一部が輪郭形状（１）に遮蔽されていると判別される（ステップＳＴ５）。
【００４２】
ポリゴン形状出力部７は、遮蔽判定処理部６により頂点Ｇ−頂点Ｈのポリゴンの面の一部が輪郭形状（１）に遮蔽されていると判別されると、頂点Ｇ−頂点Ｈのポリゴンの面と輪郭形状（１）の間で図形ブーリアン演算を実施することで、その輪郭形状（１）に遮蔽されている面が除かれているポリゴンを生成する（ステップＳＴ７）。
即ち、ポリゴン形状出力部７は、図形ブーリアン演算として、頂点Ｇ−頂点Ｈのポリゴンの面と輪郭形状（１）の間の差分演算を実施することで、図６に示すように、新たな頂点ＧＨを算出して、頂点ＧＨ−頂点Ｈのポリゴンを生成する。
図形ブーリアン演算の演算方法としては、既存のブーリアン演算方法を適用することができる。例えば、「ＧｅｎｅｒａｌＰｏｌｙｇｏｎＣｌｉｐｐｅｒ（ＧＰＣ）」と呼ばれるライブラリなどを使用することができる。
【００４３】
ポリゴン形状出力部７は、頂点ＧＨ−頂点Ｈのポリゴンを生成すると、そのポリゴンの形状を出力する（ステップＳＴ１０）。
ただし、最終的には、頂点ＧＨ−頂点Ｈのポリゴンから３次元形状のオブジェクトを生成するため、新たに算出した頂点ＧＨの奥行き情報を計算する必要がある。
新たに算出した頂点ＧＨは、頂点Ｇ−頂点Ｈのポリゴンの上に存在しているため、ポリゴン形状出力部７は、頂点Ｇ−頂点Ｈのポリゴンの３次元空間の平面方程式を用いて、頂点ＧＨにおける３次元空間内の奥行き情報を計算し、３次元空間のデータに復元する。
【００４４】
なお、遮蔽判定処理部６は、上記のようにして、頂点Ｇ−頂点Ｈのポリゴンの面と輪郭形状（１）の間で遮蔽関係を検証すると、遮蔽関係の検証対象を輪郭形状（２）に変更して（ステップＳＴ８，ＳＴ９）、頂点Ｇ−頂点Ｈのポリゴンの面と輪郭形状（２）の間で遮蔽関係を検証する。
このとき、輪郭形状（２）は、頂点Ｇ−頂点Ｈのポリゴンの面の一部を遮蔽しているが、頂点ＧＨ−頂点Ｈのポリゴンの面は、輪郭形状（２）に遮蔽されていないので、ポリゴン形状出力部７による図形ブーリアン演算は行われない。
【００４５】
また、遮蔽判定処理部６は、遮蔽関係の検証対象を輪郭形状（３）に変更して（ステップＳＴ８，ＳＴ９）、頂点Ｇ−頂点Ｈのポリゴンの面と輪郭形状（３）の間で遮蔽関係を検証する。
このとき、輪郭形状（３）は、頂点Ｇ−頂点Ｈのポリゴンの面と同一面であるため、ポリゴン形状出力部７による図形ブーリアン演算は行われない。
したがって、頂点Ｇ−頂点Ｈのポリゴンの面が遮蔽関係の検証対象である場合、ポリゴン形状出力部７から出力されるポリゴンの形状は、頂点ＧＨ−頂点Ｈのポリゴンの形状のみとなる。
【００４６】
次に、遮蔽判定処理部６は、３次元形状オブジェクトの表面を構成しているポリゴンの中で、頂点Ｉ−頂点Ｊのポリゴンの面を遮蔽関係の検証対象に選択し（ステップＳＴ１１，ＳＴ１２）、頂点Ｉ−頂点Ｊのポリゴンの面と、輪郭形状（１）の間の遮蔽関係を検証する（ステップＳＴ４）。
輪郭形状（１）は頂点Ｉ−頂点Ｊのポリゴンの面の手前側に存在しており、頂点Ｉ−頂点Ｊのポリゴンの面の一部が輪郭形状（１）に遮蔽されていると判別される（ステップＳＴ５）。
【００４７】
ポリゴン形状出力部７は、遮蔽判定処理部６により頂点Ｉ−頂点Ｊのポリゴンの面の一部が輪郭形状（１）に遮蔽されていると判別されると、頂点Ｉ−頂点Ｊのポリゴンの面と輪郭形状（１）の間で図形ブーリアン演算を実施することで、その輪郭形状（１）に遮蔽されている面が除かれているポリゴンを生成する（ステップＳＴ７）。
即ち、ポリゴン形状出力部７は、図形ブーリアン演算として、頂点Ｉ−頂点Ｊのポリゴンの面と輪郭形状（１）の間の差分演算を実施することで、図６に示すように、新たな頂点ＩＪを算出して、頂点Ｉ−頂点ＩＪのポリゴンを生成する。
【００４８】
ポリゴン形状出力部７は、頂点Ｉ−頂点ＩＪのポリゴンを生成すると、そのポリゴンの形状を出力する（ステップＳＴ１０）。
ただし、最終的には、頂点Ｉ−頂点ＩＪのポリゴンから３次元形状のオブジェクトを生成するため、新たに算出した頂点ＩＪの奥行き情報を計算する必要がある。
新たに算出した頂点ＩＪは、頂点Ｉ−頂点Ｊのポリゴンの上に存在しているため、ポリゴン形状出力部７は、頂点Ｉ−頂点Ｊのポリゴンの３次元空間の平面方程式を用いて、頂点ＩＪにおける３次元空間内の奥行き情報を計算し、３次元空間のデータに復元する。
【００４９】
なお、遮蔽判定処理部６は、上記のようにして、頂点Ｉ−頂点Ｊのポリゴンの面と輪郭形状（１）の間で遮蔽関係を検証すると、遮蔽関係の検証対象を輪郭形状（２）に変更して（ステップＳＴ８，ＳＴ９）、頂点Ｉ−頂点Ｊのポリゴンの面と輪郭形状（２）の間で遮蔽関係を検証する。
このとき、輪郭形状（２）は、頂点Ｉ−頂点Ｊのポリゴンの面と同一面であるため、ポリゴン形状出力部７による図形ブーリアン演算は行われない。
【００５０】
また、遮蔽判定処理部６は、遮蔽関係の検証対象を輪郭形状（３）に変更して（ステップＳＴ８，ＳＴ９）、頂点Ｉ−頂点Ｊのポリゴンの面と輪郭形状（３）の間で遮蔽関係を検証する。
このとき、輪郭形状（３）は、頂点Ｉ−頂点Ｊのポリゴンの面の奥側に存在しており、頂点Ｉ−頂点Ｊのポリゴンの面を遮蔽していないので、ポリゴン形状出力部７による図形ブーリアン演算は行われない。
したがって、頂点Ｉ−頂点Ｊのポリゴンの面が遮蔽関係の検証対象である場合、ポリゴン形状出力部７から出力されるポリゴンの形状は、頂点Ｉ−頂点ＩＪのポリゴンの形状のみとなる。
【００５１】
これにより、ポリゴン形状出力部７から出力されるポリゴンの形状は下記の通りとなり、一連の処理を終了する（ステップＳＴ１２）。
頂点Ａ−頂点Ｂのポリゴンの形状
↓
頂点Ｂ−頂点Ｃのポリゴンの形状
↓
頂点Ｃ−頂点Ｄのポリゴンの形状
↓
頂点Ｄ−頂点Ｅのポリゴンの形状
↓
頂点Ｅ−頂点Ｆのポリゴンの形状
↓
頂点ＧＨ−頂点Ｈのポリゴンの形状
↓
頂点Ｉ−頂点ＩＪのポリゴンの形状
【００５２】
以上で明らかなように、この実施の形態１によれば、３次元空間内の視点から、複数のポリゴンで構成されている３次元形状のオブジェクトを見たときに、そのオブジェクトの表面を構成している１以上のポリゴンを抽出する表面ポリゴン抽出部３と、表面ポリゴン抽出部３により抽出された１以上のポリゴンを２次元平面上に投影変換する投影変換処理部４と、投影変換処理部４により２次元平面上に投影変換された１以上のポリゴンが構成しているオブジェクトの表面の中で、連続している表面をオブジェクトの輪郭形状として抽出する輪郭形状抽出部５と、表面ポリゴン抽出部３により抽出されたポリゴン毎に、当該ポリゴンの面が輪郭形状抽出部５により抽出された輪郭形状に遮蔽されているか否かを判定する遮蔽判定処理部６とを設け、ポリゴン形状出力部７が、遮蔽判定処理部６によりポリゴンの面が輪郭形状により遮蔽されていないと判定された場合、そのポリゴンの形状を出力し、遮蔽判定処理部６によりポリゴンの面の一部が輪郭形状により遮蔽されていると判定された場合、そのポリゴンの面と輪郭形状間で図形ブーリアン演算を実施することで、その輪郭形状に遮蔽されている面が除かれているポリゴンを生成して、そのポリゴンの形状を出力するように構成したので、図形ブーリアン演算の演算誤差の発生を抑制して、３次元形状のオブジェクトの見える部分を構成しているポリゴンの形状を正確に抽出することができる効果を奏する。
【００５３】
即ち、この実施の形態１によれば、遮蔽関係の検証対象が、ポリゴンの面×ポリゴンの面ではなく、ポリゴンの面×輪郭形状としているので、遮蔽判定処理部６によりポリゴンの面が輪郭形状により遮蔽されていないと判定された場合、図形ブーリアン演算を実施する必要がない。このため、図形ブーリアン演算を実施する回数を大幅に削減することができるので、図形ブーリアン演算の演算誤差の発生を抑制して、３次元形状のオブジェクトの見える部分を構成しているポリゴンの形状を正確に抽出することができる。
【００５４】
実施の形態２．
上記実施の形態１では、輪郭形状抽出部５が１以上のポリゴンが構成しているオブジェクトの表面の中で、連続している表面をオブジェクトの輪郭形状として抽出するものについて示したが、輪郭形状抽出部５が投影変換処理部４により２次元平面上に投影変換された１以上のポリゴンの中で、他のポリゴンと辺を共有しているポリゴンが存在する場合、その辺を削除する処理を順次繰り返すことで、オブジェクトの輪郭形状を抽出するようにしてもよい。
具体的には、以下の通りである。
【００５５】
図７はオブジェクトの輪郭形状の抽出例を示す説明図である。
輪郭形状抽出部５は、投影変換処理部４が１以上のポリゴンを２次元平面上に投影変換すると、２次元平面上に投影変換された１以上のポリゴンの中で、他のポリゴンと辺を共有しているポリゴンを検索し、２つのポリゴンが共有している辺を削除して、新たなポリゴンを生成する。
図７の例では、ポリゴン（１）とポリゴン（２）が１つの辺を共有しており、ポリゴン（１）とポリゴン（２）が共有している辺を削除して、新たなポリゴン（１２）を生成している。
【００５６】
輪郭形状抽出部５は、新たなポリゴンを生成すると、更に、他のポリゴンと辺を共有しているポリゴンを検索し、２つのポリゴンが共有している辺を削除して、新たなポリゴンを生成する。
新たなポリゴンを生成する処理は、２つのポリゴンが共有している辺がなくなるまで繰り返し実施する。
２つのポリゴンが共有している辺がなくなると、残っているポリゴンの輪郭形状が、オブジェクトの輪郭形状となる。
【００５７】
実施の形態３．
図８はこの発明の実施の形態３による図形処理装置を示す構成図であり、図において、図１と同一符号は同一又は相当部分を示すので説明を省略する。
輪郭形状抽出部８は３次元形状のオブジェクトが閉ループで覆われている場合、そのオブジェクトの表面と裏面が共有している辺を検索し、表面と裏面が共有している辺の中で、頂点で結合されている辺を輪郭形状として抽出する処理を実施する。なお、輪郭形状抽出部８は輪郭形状抽出手段を構成している。
【００５８】
図８の例では、図形処理装置の構成要素である視点受付部１、データ記憶部２、表面ポリゴン抽出部３、遮蔽判定処理部６、ポリゴン形状出力部７及び輪郭形状抽出部８のそれぞれが専用のハードウェア（例えば、ＣＰＵを実装している半導体集積回路、あるいは、ワンチップマイコンなど）で構成されているものを想定しているが、図形処理装置がコンピュータで構成される場合、視点受付部１、データ記憶部２、表面ポリゴン抽出部３、遮蔽判定処理部６、ポリゴン形状出力部７及び輪郭形状抽出部８の処理内容を記述しているプログラムをコンピュータのメモリに格納し、当該コンピュータのＣＰＵが当該メモリに格納されているプログラムを実行するようにしてもよい。
【００５９】
次に動作について説明する。
上記実施の形態１では、輪郭形状抽出部５が１以上のポリゴンが構成しているオブジェクトの表面の中で、連続している表面をオブジェクトの輪郭形状として抽出するものについて示したが、３次元形状のオブジェクトが閉ループで覆われている場合、輪郭形状抽出部８が、３次元形状のオブジェクトの表面と裏面が共有している辺を検索し、表面と裏面が共有している辺の中で、頂点で結合されている辺を輪郭形状として抽出するようにしてもよい。
具体的には、以下の通りである。
【００６０】
図９はオブジェクトの輪郭形状の抽出例を示す説明図である。
図９では、３次元形状のオブジェクトが閉ループで覆われている物体形状として、３次元形状のオブジェクトが立方体である例を示している。
３次元形状のオブジェクトが閉ループで覆われている物体形状である場合、３次元形状のオブジェクトの全ての面は結合されており、３次元形状のオブジェクトの輪郭形状は表面と裏面の境界部分になる。
【００６１】
図９の例では、ポリゴン（１）、ポリゴン（２）及びポリゴン（３）は、３次元形状のオブジェクトの表面となる。
一方、ポリゴン（４）（ポリゴン（２）の反対側のポリゴン）、ポリゴン（５）（ポリゴン（３）の反対側のポリゴン）及びポリゴン（６）（ポリゴン（１）の反対側のポリゴン）は、３次元形状のオブジェクトの裏面となる。
【００６２】
まず、輪郭形状抽出部８は、３次元形状のオブジェクトの裏面であるポリゴン（４）が、辺を共有しているポリゴン（１）、ポリゴン（３）、ポリゴン（５）及びポリゴン（６）を検索し、ポリゴン（１）、ポリゴン（３）、ポリゴン（５）及びポリゴン（６）の中で、３次元形状のオブジェクトの表面であるポリゴンを判別する。この場合、ポリゴン（１）とポリゴン（３）がオブジェクトの表面である。
輪郭形状抽出部８は、ポリゴン（１）とポリゴン（３）が３次元形状のオブジェクトの表面であると判別すると、ポリゴン（４）とポリゴン（１）が共有する辺（１）が、３次元形状のオブジェクトの輪郭形状を形成している辺であると認識する。
また、ポリゴン（４）とポリゴン（３）が共有する辺（２）が、３次元形状のオブジェクトの輪郭形状を形成している辺であると認識する。
【００６３】
次に、輪郭形状抽出部８は、３次元形状のオブジェクトの裏面であるポリゴン（５）が、辺を共有しているポリゴン（１）、ポリゴン（２）、ポリゴン（４）及びポリゴン（６）を検索し、ポリゴン（１）、ポリゴン（２）、ポリゴン（４）及びポリゴン（６）の中で、３次元形状のオブジェクトの表面であるポリゴンを判別する。この場合、ポリゴン（１）とポリゴン（２）がオブジェクトの表面である。
輪郭形状抽出部８は、ポリゴン（１）とポリゴン（２）が３次元形状のオブジェクトの表面であると判別すると、ポリゴン（５）とポリゴン（１）が共有する辺（３）が、３次元形状のオブジェクトの輪郭形状を形成している辺であると認識する。
また、ポリゴン（５）とポリゴン（２）が共有する辺（４）が、３次元形状のオブジェクトの輪郭形状を形成している辺であると認識する。
【００６４】
次に、輪郭形状抽出部８は、３次元形状のオブジェクトの裏面であるポリゴン（６）が、辺を共有しているポリゴン（２）、ポリゴン（３）、ポリゴン（４）及びポリゴン（５）を検索し、ポリゴン（２）、ポリゴン（３）、ポリゴン（４）及びポリゴン（５）の中で、３次元形状のオブジェクトの表面であるポリゴンを判別する。この場合、ポリゴン（２）とポリゴン（３）がオブジェクトの表面である。
輪郭形状抽出部８は、ポリゴン（２）とポリゴン（３）が３次元形状のオブジェクトの表面であると判別すると、ポリゴン（６）とポリゴン（２）が共有する辺（５）が、３次元形状のオブジェクトの輪郭形状を形成している辺であると認識する。
また、ポリゴン（６）とポリゴン（３）が共有する辺（６）が、３次元形状のオブジェクトの輪郭形状を形成している辺であると認識する。
以上より、輪郭形状抽出部８は、辺（１）、辺（２）、辺（３）、辺（４）、辺（５）、辺（６）を３次元形状オブジェクトの輪郭形状として抽出する。
【符号の説明】
【００６５】
１視点受付部、２データ記憶部、３表面ポリゴン抽出部（表面ポリゴン抽出手段）、４投影変換処理部（投影変換手段）、５，８輪郭形状抽出部（輪郭形状抽出手段）、６遮蔽判定処理部（遮蔽判定手段）、７ポリゴン形状出力部（ポリゴン形状出力手段）、１１アプリケーションメモリ、１２システムメモリ、１３演算プロセッサ。

【特許請求の範囲】
【請求項１】
３次元空間内の視点から、複数のポリゴンで構成されている３次元形状のオブジェクトを見たときに、上記オブジェクトの表面を構成している１以上のポリゴンを抽出する表面ポリゴン抽出手段と、上記表面ポリゴン抽出手段により抽出された１以上のポリゴンを２次元平面上に投影変換する投影変換手段と、上記投影変換手段により２次元平面上に投影変換された１以上のポリゴンが構成しているオブジェクトの表面の中で、連続している表面を上記オブジェクトの輪郭形状として抽出する輪郭形状抽出手段と、上記表面ポリゴン抽出手段により抽出されたポリゴン毎に、当該ポリゴンの面が上記輪郭形状抽出手段により抽出された輪郭形状に遮蔽されているか否かを判定する遮蔽判定手段と、上記遮蔽判定手段によりポリゴンの面が輪郭形状により遮蔽されていないと判定された場合、上記ポリゴンの形状を出力し、上記遮蔽判定手段によりポリゴンの面の一部が輪郭形状により遮蔽されていると判定された場合、上記ポリゴンの面と上記輪郭形状間で図形ブーリアン演算を実施することで、上記輪郭形状に遮蔽されている面が除かれているポリゴンを生成して、上記ポリゴンの形状を出力するポリゴン形状出力手段とを備えた図形処理装置。
【請求項２】
輪郭形状抽出手段は、投影変換手段により２次元平面上に投影変換された１以上のポリゴンの中で、他のポリゴンと辺を共有しているポリゴンが存在する場合、上記辺を削除する処理を順次繰り返すことで、オブジェクトの輪郭形状を抽出することを特徴とする請求項１記載の図形処理装置。
【請求項３】
３次元空間内の視点から、複数のポリゴンで構成されている３次元形状のオブジェクトを見たときに、上記オブジェクトの表面を構成している１以上のポリゴンを抽出する表面ポリゴン抽出手段と、上記オブジェクトが閉ループで覆われている場合、上記オブジェクトの表面と裏面が共有している辺を検索し、表面と裏面が共有している辺の中で、頂点で結合されている辺を輪郭形状として抽出する輪郭形状抽出手段と、上記表面ポリゴン抽出手段により抽出されたポリゴン毎に、当該ポリゴンの面が上記輪郭形状抽出手段により抽出された輪郭形状に遮蔽されているか否かを判定する遮蔽判定手段と、上記遮蔽判定手段によりポリゴンの面が輪郭形状により遮蔽されていないと判定された場合、上記ポリゴンの形状を出力し、上記遮蔽判定手段によりポリゴンの面の一部が輪郭形状により遮蔽されていると判定された場合、上記ポリゴンの面と上記輪郭形状間で図形ブーリアン演算を実施することで、上記輪郭形状に遮蔽されている面が除かれているポリゴンを生成して、上記ポリゴンの形状を出力するポリゴン形状出力手段とを備えた図形処理装置。

【図１】