三次元図形演算プログラム、ダイナミックリンクライブラリ及び景観検討装置
【課題】 複数の三次元図形の相貫関係に基づき各三次元図形の合成画面を生成する図形演算において、データ量の増大を抑制しつつ、精度の高い図形演算を行うことのできる三次元図形演算プログラム、ダイナミックリンクライブラリ及び三次元図形演算プログラムを実行して景観の検討を行う景観検討装置を提供する。
【解決手段】 三次元図形演算プログラムは、各三次元図形を多面体に表現する第１ステップと、多面体に表現された、一の三次元図形を構成するすべての面に関する、他の三次元図形を構成するすべての面の相貫関係を分析する第２ステップと、この相貫関係の分析結果に基づき、一の三次元図形を構成する各面において、他の三次元図形と重なり合い裏側となる部分を除去する第３ステップと、除去されなかった部分を有する面からなる三次元図形同士を合成して表示する第４ステップと、をコンピュータに実行させる。
【解決手段】 三次元図形演算プログラムは、各三次元図形を多面体に表現する第１ステップと、多面体に表現された、一の三次元図形を構成するすべての面に関する、他の三次元図形を構成するすべての面の相貫関係を分析する第２ステップと、この相貫関係の分析結果に基づき、一の三次元図形を構成する各面において、他の三次元図形と重なり合い裏側となる部分を除去する第３ステップと、除去されなかった部分を有する面からなる三次元図形同士を合成して表示する第４ステップと、をコンピュータに実行させる。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、三次元空間における複数の三次元図形の相貫関係を分析して各三次元図形の合成表示を行う三次元図形演算プログラム、ダイナミックリンクライブラリ及び景観検討装置に関し、特に三次元図形演算プログラムを用いて地形や構造物の合成画面を生成・表示し、景観のシミュレーションや検討を行う技術に係るものである。
【背景技術】
【０００２】
従来、建設事業においては、ビルや路面などの構造物を三次元データとして用意しておき、背景写真や地形の三次元データと合成することにより、建設計画案の内容を三次元空間において立体的に確認することのできる景観シミュレーションシステムが知られている。このシステムでは、景観検討に用いる合成画面を作成する過程で、三次元空間における地形と構造物との間の重なり合い（相貫関係）を分析し、相互に重なり合う部分を除去した上で、それぞれの合成を行っている。すなわち、既存地形などの地物の一部の切欠き処理を行い、この切欠き処理が施された部分に、新たに追加される土木建築施設などを合成することにより、景観検討用の合成画面を表示している。
【０００３】
初期の景観シミュレーションシステムにおいては、地形と構造物（とりわけ法面）との相貫関係に基づく図形演算を、描画処理の陰線消去に使用するデプス・バッファを用いて実行していた。すなわち、地形及び構造物の平面図を、表示画面の解像度に対応したメッシュに分割した上で、各格子点に関して地形と構造物のどちらが上にあるかを判定し、この判定結果で得られる地形と構造物との交差部を抽出する。そして、この交差図形（水平面上に投影された二次元の閉多角形）に基づいて、削除されるべき地形の範囲と、そこに充填されるべき法面の形状を求めて、これらを合成していた。
【０００４】
しかし、この方法で取得される地形と構造物との交差部の形状は、画面サイズによって規定されるデプス・バッファの解像度に制約され、直線部分に関しても単純な直線形ではなく、折れ線として取得される。このため、データが不必要に大きくなるにもかかわらず、演算結果の精度が低く、地形と構造物との間に隙間が生じたり、境界付近の地形及び構造物の表面を構成する多角形の平面性が失われるなどの問題があった。また、遠景として長大法面などの検討に使用することはできても、路上を走行する車両乗員などの近接する視点位置からの景観画像の質には限界があった。
【０００５】
この問題を解決する手法として、三角形分割による三次元図形演算法が提案されている（非特許文献１参照）。この手法によれば、三次元データで表現される地形や構造物を、多面体に近似した形状（ポリゴン）として表現し、その表面を構成する複雑な多角形をあらかじめ三角形に分割しておく。そして、地形と構造物との交差部において、それぞれの三角形同士の切欠き処理を行うことにより、処理の場合分けが単純化され、厳密な座標計算を行うことが可能となっている。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】「建築研究資料Ｎｏ．９６ 成熟都市シミュレータ Ｖｅｒ１．０＋ 景観シミュレータ Ｖｅｒ２．０５ 実務マニュアル」 建設省建築研究所 ２０００年７月
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、前述の三角形分割による図形演算では、単純な三角形同士の切欠き処理であっても、処理結果は複雑な形状となり、次の処理に先立ってさらに三角形分割が要求される。そのため、処理が進行するにしたがって、地形が複雑に細分化していき、データ量が肥大してしまうという問題があった。また、地形が複雑に細分化されるために、演算の成功率も低く、精度の良い演算方法とはいえないものとなっていた。
【０００８】
この発明は、かかる課題を解決するためになされたものであり、複数の三次元図形の相貫関係に基づき各三次元図形の合成画面を生成する図形演算において、データ量の増大を抑制しつつ、精度の高い図形演算を行うことのできる三次元図形演算プログラム、ダイナミックリンクライブラリ及び三次元図形演算プログラムを実行して景観の検討を行う景観検討装置を提供することを目的とする。
【課題を解決するための手段】
【０００９】
前記の目的を達成するために、請求項１に記載の発明は、三次元空間における複数の三次元図形の相貫関係を分析し、相互に重なり合う部分を除去して各三次元図形を合成表示する三次元図形演算プログラムであって、前記各三次元図形を、面の集合である多面体に近似した形状に表現する第１ステップと、前記第１ステップにおいて多面体に近似した形状に表現された各三次元図形において、一の三次元図形を構成するすべての面に関する、他の三次元図形を構成するすべての面の相貫関係を分析する第２ステップと、前記第２ステップにおける面同士の相貫関係の分析結果に基づき、一の三次元図形を構成する各面において、他の三次元図形と重なり合い裏側となる部分を除去する第３ステップと、前記第３ステップにおいて除去されなかった部分を有する面からなる三次元図形同士を合成して表示する第４ステップと、をコンピュータに実行させることを特徴とする。
【００１０】
請求項２に記載の発明は、請求項１に記載の三次元図形演算プログラムにおいて、前記第２ステップにおける面同士の相貫関係の分析は、一の三次元図形を構成する各面と、他の三次元図形を構成する各面との切欠き状態に基づいて行われ、一の面による切欠きが、他の面の辺または頂点から始まり、かつ他の面の内部で終わる場合の処理を行う切込みステップと、一の面による切欠きが、他の面の内部から始まり、かつ他の面の辺または頂点で終わる場合の処理を行う切抜けステップと、一の面による切欠きが、他の面の内部から始まり、かつ他の面の内部で終わる場合の処理を行う切入れステップと、一の面による切欠きにより、他の面が複数の断片に分割される場合に、分割後の複数の各断片の分割面に関する表裏を確定する切分けステップと、をさらに有することを特徴とする。
【００１１】
請求項３に記載の発明は、請求項２に記載の三次元図形演算プログラムにおいて、前記第１ステップにおいて多面体に近似した形状に表現された三次元図形の各面のうち、面内部に穴を有する面について、前記穴を構成するいずれかの頂点と、この穴を有する面を構成するいずれかの頂点とを仮想線で接続するサブステップをさらに有することを特徴とする。
【００１２】
請求項４に記載の発明は、請求項２または３に記載の三次元図形演算プログラムにおいて、前記切入れステップにおいて、面内部に面積のない線状の切れ目が生じた面について、前記切れ目の一端と、この切れ目が生じた面を構成するいずれかの頂点とを仮想線で接続するサブステップをさらに有することを特徴とする。
【００１３】
請求項５に記載の発明は、請求項３または４に記載の三次元図形演算プログラムにおいて、前記仮想線を有する面について、前記第２ステップにおいて他の面による新たな切欠きが生じた場合、この新たな切欠きの発生状況に応じて、前記仮想線の削除もしくは接続先の変更を行うサブステップをさらに有することを特徴とする。
【００１４】
請求項６に記載の発明は、請求項３ないし５のいずれかに記載の三次元図形演算プログラムにおいて、前記第４ステップにおける合成表示に際し、前記仮想線を非表示に設定可能であることを特徴とする。
【００１５】
請求項７に記載の発明は、請求項１ないし６のいずれかに記載の三次元図形演算プログラムにおいて、前記第１ステップにおいて多面体に近似した形状に表現された三次元図形の各面が、前記第２ステップ以降の処理を適用する対象として正常であるか異常であるかを判定し、異常と判定された面に対して修正を行うサブステップをさらに有することを特徴とする。
【００１６】
請求項８に記載の発明は、請求項１ないし７のいずれかに記載の三次元図形演算プログラムにおいて、前記第２ステップにおける面同士の相貫関係の分析の結果、分析エラーとなった面の組み合わせをエラーログとして記録手段に記録するサブステップをさらに有することを特徴とする。
【００１７】
請求項９に記載の発明は、メモリ上にロードして実行されるダイナミックリンクライブラリであって、請求項１ないし８のいずれかに記載の三次元図形演算プログラムを含んでいることを特徴とする。
【００１８】
請求項１０に記載の発明は、地形又は構造物の三次元データを解析し、三次元空間における前記地形又は構造物の合成画面を表示して景観のシミュレーション及び検討を行う景観検討装置であって、前記地形又は構造物の三次元データを入力する入力手段と、前記入力された三次元データを記録する記録手段と、請求項１ないし８のいずれかに記載の三次元図形演算プログラムを記憶する記憶手段と、前記記憶手段に記憶された三次元図形演算プログラムを実行して、前記地形又は構造物の三次元データに基づき前記合成画面を生成する制御手段と、前記生成された合成画面を表示する表示手段と、を備えたことを特徴とする。
【００１９】
請求項１１に記載の発明は、請求項１０に記載の景観検討装置において、前記地形又は構造物の撮像データを取得する撮像手段と、該撮像手段により取得された撮像データを受信するための通信インタフェースと、をさらに備えたことを特徴とする。
【発明の効果】
【００２０】
この発明は、前記のようであって、請求項１に記載の発明によれば、三次元空間における複数の三次元図形の相貫関係の分析を、各三次元図形を構成する面同士の相貫関係の分析に還元することができる。これにより、三次元図形同士の図形演算が単純化され、データ量の増大を抑制しつつ、精度の高い図形演算を行うことができる。
【００２１】
請求項２に記載の発明によれば、請求項１に記載の三次元図形演算プログラムにおける面同士の相貫関係の分析が、切欠きの発生状況に応じて４つの処理ステップに場合分けされる。これにより、切欠きの発生状況に応じた適切な処理ステップが選択され、面同士の相貫関係の分析を正確に行うことができる。
【００２２】
請求項３に記載の発明によれば、多面体を構成する面のうち、その内部に穴を有する面に対して、仮想線を適用することにより、これらの面を準正常な面として取り扱うことができる。これにより、内部に穴を有する面であっても、図形分割することなく、通常の面と同様に、面同士の相貫関係の分析を行うことができる。
【００２３】
請求項４に記載の発明によれば、面同士の相貫関係の分析において、内部に面積のない線状の切れ目が生じた面に対して、仮想線を適用することにより、これらの面を準正常な面として取り扱うことができる。これにより、内部に面積のない線状の切れ目が生じた面であっても、図形分割することなく、通常の面と同様に、面同士の相貫関係の分析を行うことができる。
【００２４】
請求項５に記載の発明によれば、仮想線を有する準正常な面において、新たな切欠きが発生した場合に、その新たな切欠きの発生状況に応じて、仮想線の削除や接続先の変更が行われる。これにより、仮想線は、準正常な面において常に適切に適用されることとなり、連続的な面同士の分析においても正確に分析を行うことができる。
【００２５】
請求項６に記載の発明によれば、図形演算の結果を表示する際に、仮想線を非表示に設定することができる。これにより、ノイズの少ない表示画面を得ることができ、図形演算後の図形の形状を分かりやすく表示することができる。
【００２６】
請求項７に記載の発明によれば、面同士の相貫関係の分析に先立って、分析対象となる面のうち異常が検出された面に対して、適宜修正が施される。これにより、面の異常性に起因する分析エラーが発生する割合を低減させることができる。
【００２７】
請求項８に記載の発明によれば、面同士の相貫関係の分析において、分析エラーとなった面の組み合わせがエラーログとして記録される。これにより、相貫関係の分析における分析エラーの発生箇所を容易に特定することができ、この点でプログラムの保守性が向上する。
【００２８】
請求項９に記載の発明によれば、三次元図形演算プログラムをダイナミックリンクライブラリとして提供することにより、他のプログラムに影響を与えることなく独立して修正や更新を行うことができ、この点でも保守性が向上する。また、この三次元図形演算プログラムで実現される三次元図形演算機能を、独立した機能として提供することが可能となり、その応用範囲を拡大することができる。
【００２９】
請求項１０に記載の発明によれば、前記請求項１ないし８のいずれかに記載の作用効果を、景観検討装置においても奏することができる。これにより、三次元空間における地形又は構造物の合成画面を表示する際に、その境界部分において余計な隙間がなく、滑らかに合成された画面を表示することができる。
【００３０】
請求項１１に記載の発明によれば、カメラなどの撮像手段によって撮像された地形又は構造物の撮像データを、撮像手段から受信することができる。これにより、入力手段によって入力された三次元データのみならず、撮像手段によって撮像されたデータからでも、景観の検討を行うことができる。
【図面の簡単な説明】
【００３１】
【図１】この発明の一実施の形態に係る景観検討装置の構成例を示すブロック図である。
【図２】同上の三次元図形演算プログラムにより実行される図形演算の全体処理を示すフローチャートである。
【図３】同上の穴あき面に仮想線を適用した例を示す説明図である。
【図４】同上の三次元図形演算プログラムにより実行される面同士の相貫関係の分析の全体処理を示すフローチャートである。
【図５】同上の面Ｆ２による面Ｆ１の切欠き処理を示すフローチャートである。
【図６Ａ】同上の「切込み」の概要を示す説明図である。
【図６Ｂ】同上の「切込み」における頂点追加の例を示す説明図である。
【図７】同上の切込み処理の流れを示すフローチャートである。
【図８】同上の「切抜け」の概要を示す説明図である。
【図９】同上の切抜け処理の流れを示すフローチャートである。
【図１０Ａ】同上の「切入れ」の概要を示す説明図である。
【図１０Ｂ】同上の「切入れ」における仮想線の適用例を示す説明図である。
【図１１】同上の切入れ処理の流れを示すフローチャートである。
【図１２Ａ】同上の「切分け」の概要を示す説明図である。
【図１２Ｂ】同上の「切分け」における頂点追加の例を示す説明図である。
【図１３】同上の切分け処理の流れを示すフローチャートである。
【図１４Ａ】同上の切分けの発生状況に応じた仮想線の削除又は通常の辺への変更の様子を示す説明図である。
【図１４Ｂ】同上の切分けの発生状況に応じた仮想線の削除又は通常の辺への変更の様子を示す説明図である。
【図１５Ａ】同上の切欠きの発生状況に応じた仮想線の接続先の変更の様子を示す説明図である。
【図１５Ｂ】同上の切欠きの発生状況に応じた仮想線の接続先の変更の様子を示す説明図である。
【図１６】同上の景観検討装置により表示される地形及び構造物の合成画面の例を示す説明図である。
【発明を実施するための形態】
【００３２】
この発明の一実施の形態に係る三次元図形演算プログラムでは、三次元空間における複数の三次元図形の相貫関係を分析する際に、まず、各三次元図形を多面体に近似した形状（ポリゴン）として表現する。そして、一の三次元図形を構成するすべての面と、他の三次元図形を構成するすべての面との間で、順次相貫関係を分析する。この面同士の相貫関係の分析は、面と面との間で発生する切欠き状態に基づいて行われ、この切欠き状態に応じた所定の切欠き処理が行われる。このように、複数の三次元図形における相貫関係の分析を、面同士の切欠き処理の繰り返しに還元することで、処理を単純化している。
【００３３】
また、各三次元図形を多面体として表現した際に、その内部に穴を有する面が生じた場合に、この面に対して仮想線を適用することにより、これらの面を「準正常な面」として取り扱い、通常の面と同様に切欠き処理を適用することを可能としている。また、この仮想線は、面同士の切欠き処理の過程で、その内部に線状の切れ目が生じた面に対しても適用され、これらの面も同様に「準正常な面」として取り扱っている。
以下、図面を参照しながら、三次元図形演算プログラムの具体的な処理内容について説明する。ここでは、この三次元図形演算プログラムを実行して、地形又は構造物の合成画面を表示し、景観の検討を行う景観検討装置を例に挙げて説明する。
【００３４】
図１において、１は景観検討装置で、この景観検討装置１は、三次元データとして予め用意されたビルや路面などの構造物と、同様に用意された背景写真や地形と、の合成画面を表示して、三次元空間における合成の様子を立体的に確認することを主な基本機能としている。また、この合成画面を表示するために必要となる様々な編集画面を提供する機能も、併せて備えている。
【００３５】
景観検討装置１は、一般的なパーソナルコンピュータＰＣを有している。すなわち、このＰＣは、装置全体の制御や図形演算を行う制御手段（ＣＰＵ：Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓ Ｕｎｉｔ）２、制御手段２の処理データなどを一時記憶する書き換え可能なＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）３、固定データなどを記憶するＲＯＭ（Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）４、図形演算結果のデータなどを記録するハードディスクドライブ装置などの記録手段５、各種データの入力や指示を行うキーボードやマウスなどの入力手段６、図形演算結果を表示するディスプレイなどの表示手段７、ネットワーク接続に使用する通信インタフェース８、などの通常のコンピュータのハードウェア資源を備えている。そして、これらの各ハードウェア資源と、三次元図形演算プログラムをはじめとするソフトウェアとの協働により、景観検討装置１の基本機能が実現される。
【００３６】
また、この景観検討装置１は、景観検討の対象となる地形や構造物を撮像する撮像手段９を備えていてもよい。この撮像手段９は、例えばデジタルカメラなどで構成され、この撮像手段９により取得された地形や構造物の撮像データを用いて、景観の検討を行うこともできる。
【００３７】
この撮像手段９により取得された撮像データは、景観検討装置１に通信インタフェース８を経由して送信することができる。このように、撮像手段９から入力される撮像データとしては、例えば地形や構造物を立体的に見るために、複数の異なるカメラの視点位置から撮像したステレオ写真や、通常の方法で撮像した単眼写真などが挙げられる。このように入力されたステレオ写真などの撮像データは、三次元図形演算プログラムの入力となる三次元データに変換され、この三次元データを用いて、図形演算が行われる。
【００３８】
この他、入力データとして三次元図形演算プログラムに入力される三次元データとしては、過去にＣＡＤ（Ｃｏｍｐｕｔｅｒ Ａｉｄｅｄ Ｄｅｓｉｇｎ）やＧＩＳ（Ｇｅｏｇｒａｐｈｉｃ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｙｓｔｅｍ）で作成された三次元データを、図形演算に適したデータ形式に変換したものや、過去に作成された紙図面を基に、オペレータが入力手段６を用いて三次元データとして作成したものを用いてもよい。これらの方法により作成した三次元データや、撮像手段９による撮像データから生成した三次元データは、ハードディスクドライブ装置などの記録手段５に記録される。
【００３９】
このように、三次元図形演算プログラムの入力となる三次元データが用意された後、オペレータにより、マウスなどの入力手段６が操作され、図形演算の開始が指示される。この指示を受けると、制御手段２は、予めＲＯＭ４に記憶されている三次元図形演算プログラムを読み出し、これを実行して図形演算を開始する。なお、この三次元図形演算プログラムは、ＣＤ−ＲＯＭなどの外部記録媒体からインストールされ、ハードディスクドライブ装置などの記録手段５に記録されていてもよい。以下、制御手段２が実行する図形演算について、図２ないし図１５を用いて詳細に説明する。
【００４０】
＜全体の流れ＞
図２は、制御手段２が実行する図形演算の全体の流れを示すフローチャートである。はじめに、このフローチャートに基づき図形演算の全体の流れを説明し、次に、各ステップにおける具体的な処理内容について説明する。
【００４１】
図形演算は、図２に示すように、大きく４つの処理ステップで構成される。各ステップの処理の概要を以下に示す。
（ステップ０１）入力された地形や構造物などの三次元データを基に、各三次元図形を多面体に近似した形状（ポリゴン）に表現する。
（ステップ０２）ステップ０１において、多面体に近似した形状に表現された各三次元図形において、一の三次元図形を構成するすべての面に関する、他の三次元図形を構成するすべての面の相貫関係を分析する。
（ステップ０３）ステップ０２における各面同士の相貫関係の分析結果に基づき、各面において他の三次元図形と重なり合い裏側となる部分を除去する。
（ステップ０４）ステップ０３において、除去されなかった部分を有する面で構成される三次元図形同士を合成し、合成画面を表示する。
以下、これら各ステップについて、詳細に説明する。
【００４２】
＜ステップ０１：多面体に近似する＞
まず、制御手段２は、オペレータにより指示されて図形演算の対象となった構造物などの図形の三次元データを、記録手段５から読み出す。そして、読み出した三次元データに基づき、各三次元図形を多面体に近似した形状（ポリゴン）として表現する。そして、このように表現された各三次元図形を構成する各面において、その内部に穴を有する面（以下、穴あき面と称する）が生じた場合に、この穴あき面に対して仮想線を適用する。
【００４３】
この仮想線は、前述の穴あき面のように、内部に穴を有する面であっても、穴のない通常の面と同様に取り扱うことを可能にするもので、例えばビルの外壁や、既に図形演算が施されている地形など、内部に穴のある三次元図形であっても、通常の三次元図形と同様に取り扱うことができる。
【００４４】
具体的な仮想線の適用例を図３に示す。この例では、内部に穴１１を有する穴あき面１０において、この穴１１を構成するいずれかの頂点と、穴あき面１０を構成するいずれかの頂点（ここでは頂点１２）とを、仮想線Ｋで接続する。このように、穴１１と頂点１２とを仮想線Ｋで接続することにより、穴あき面１０を従来の三角形分割のように図形分割することなく、ステップ０２以降の処理で用いることができる。なお、この仮想線Ｋの具体的な作用については、後述のステップ０２において説明する。
【００４５】
制御手段２は、このように多面体として表現された三次元図形のすべての面に関するデータを、ＲＡＭ３に記憶する。また、これらのデータは、ハードディスクドライブ装置などの記録手段５に記録してもよい。
【００４６】
＜ステップ０２：面同士の相貫関係の分析＞
次に、制御手段２は、ステップ０１において多面体として表現された各三次元図形において、一の三次元図形を構成するすべての面に関する、他の三次元図形を構成するすべての面の相貫関係を分析する。このステップ０２は、図４のフローチャートに示すサブステップ１１〜１７で構成されている。なお、ここでは、説明を簡単にするために、２つの三次元図形Ｇ１、Ｇ２を例として、図４のフローチャートに基づき各サブステップについて説明する。
【００４７】
まず、２つの三次元図形Ｇ１、Ｇ２において、図形Ｇ１を構成するすべての面に関し、図形Ｇ２の内部に含まれる部分を考える。このような部分は、図形Ｇ２と重なり合ってＧ２の裏側となる部分であり、取り除かれるべき部分となる。そこで、図形Ｇ１を構成するすべての面に関して、図形Ｇ２の内部に含まれる部分を取り除くことを、「Ｇ２でＧ１を切り取る」と呼ぶ。
【００４８】
このように、Ｇ２でＧ１を切り取る場合、Ｇ１を構成する各々の面は、相互に影響を受けることなく、互いに独立してＧ２に切り取られる。すなわち、Ｇ１を構成する１つの面Ｆ１について、Ｇ２の内部に含まれる部分が切り取られるとき、Ｇ１を構成するＦ１以外の面に対しては、同様の切り取りにおいて影響を与えない。そこで、Ｇ１を構成する１つの面Ｆ１から、Ｇ２に含まれる部分を切り取ることを、「Ｇ２でＦ１を切り取る」と呼ぶ。そこで、まず、図形Ｇ１から１つの面Ｆ１を取り出す（サブステップ１１）。
【００４９】
このように取り出した面Ｆ１をＧ２で切り取るためには、Ｇ２を構成するすべての面で、面Ｆ１を切り取る必要がある。そこで、次に、図形Ｇ２から１つの面Ｆ２を取り出す（サブステップ１２）。
このように取り出した面Ｆ２により、面Ｆ１を切り取ることを、「Ｆ２でＦ１を切り取る」と呼ぶ。また、その際に行われる処理を「Ｆ２によるＦ１の切欠き処理」と呼ぶ（サブステップ１３）。以下、この面Ｆ２による面Ｆ１の切欠き処理について説明する。
【００５０】
＜サブステップ１３：面Ｆ２による面Ｆ１の切欠き処理＞
この切欠き処理を行うサブステップ１３は、さらに図５のフローチャートに示すサブステップ２１〜３８で構成されている。この各サブステップの処理について、図５のフローチャートに基づき説明する。
【００５１】
まず、面Ｆ１及び面Ｆ２が、切欠き処理を適用する対象として正常であるか異常であるかを判定する（サブステップ２１）。すなわち、切欠き処理を適用しようとする面は、必ずしも現実に存在しうる幾何学的な形状の面であるとは限らない。例えば、頂点が２以下しかない頂点不足の面や、ある辺と次の辺が一直線上にある面などである。このような面は、切欠き処理を行うには不適切な面となる。
そこで、処理に先立って、対象となる面を診断し、異常であると判定された場合には、可能な限り修正を行ってから処理を行う。なお、このような診断及び修正は、切欠き処理を施す前の面に限らず、切欠き処理を行った結果として得られる面に対しても行うことができる。
【００５２】
次に、面Ｆ１と面Ｆ２が同一平面であるか否かを確認する（サブステップ２２）。同一平面であれば、従来の二次元図形演算処理を行う（サブステップ２３）。同一平面でなければ、サブステップ２４へ進む。
【００５３】
次に、面Ｆ１に関する面Ｆ２の各頂点の高さを求める。そして、面Ｆ２のすべての頂点が、面Ｆ１の上または下にあるか否かを確認する（サブステップ２４）。もし、面Ｆ２のすべての頂点が面Ｆ１よりも上または下にあれば、この二つの面は接触しないと判定して（サブステップ２６）、サブステップ１３を終了する。それ以外の場合は、サブステップ２５へ進む。
【００５４】
次に、面Ｆ２に関する面Ｆ１の各頂点の高さを求める。そして、面Ｆ１のすべての頂点が、面Ｆ２の上または下にあるか否かを確認する（サブステップ２５）。もし、面Ｆ１のすべての頂点が面Ｆ２よりも上または下にあれば、この二つの面は接触しないと判定して（サブステップ２６）、サブステップ１３を終了する。それ以外の場合は、サブステップ２７へ進む。
【００５５】
次に、面Ｆ１と面Ｆ２の交線となる直線（交差線）を求める（サブステップ２７）。そして、この交差線と、面Ｆ１及び面Ｆ２のすべての辺との交点を求め、この交点のリストを作成する（サブステップ２８）。このリストにおいては、各交点を、交差線に沿った１次元座標値に基づいて並び替えておく。このとき、面Ｆ１が仮想線を含む場合は、この仮想線と交差線との交点も同様にリスト化する。
【００５６】
次に、前述のリストに基づいて、面Ｆ２による面Ｆ１の切欠きの開始点及び終了点を求める（サブステップ２９）。具体的には、前述の交差線上において、仮想線以外の交点によって区切られた各区間を、１次元座標値が若い順に評価する。その結果、面Ｆ１に含まれ、かつ面Ｆ２にも含まれるすべての区間が、実際に切欠きが行われる区間となる。すなわち、これらの各区間の開始点及び終了点が、それぞれの切欠きの開始点及び終了点となる。なお、仮想線による交点は、当該区間の属性としてリスト化しておく。
【００５７】
次に、サブステップ２９において求めた切欠きの開始点及び終了点に基づき、切欠き処理の場合分けを行う。すなわち、面Ｆ２による面Ｆ１の切欠き処理は、面Ｆ１における切欠きの開始点及び終了点の位置に応じて、「切込み」「切抜け」「切入れ」「切分け」の４パターンに場合分けされる。そこで、面Ｆ２による面Ｆ１の切欠きが、このいずれのパターンに該当するかを順次確認していく。
【００５８】
まず、当該切欠きが「切込み」であるか否かを確認する（サブステップ３０）。「切込み」は、切欠きが面Ｆ１の辺または頂点から始まり、かつ面Ｆ１の内部で終わる状態である。当該切欠きがこの「切込み」に該当する場合は、サブステップ３１に進み、切込み処理を行う。該当しない場合は、サブステップ３２に進む。
【００５９】
次に、当該切欠きが「切抜け」であるか否かを確認する（サブステップ３２）。「切抜け」は、切欠きが面Ｆ１の内部から始まり、かつ面Ｆ１の辺または頂点で終わる状態である。当該切欠きがこの「切抜け」に該当する場合は、サブステップ３３に進み、切抜け処理を行う。該当しない場合は、サブステップ３４に進む。
【００６０】
次に、当該切欠きが「切入れ」であるか否かを確認する（サブステップ３４）。「切入れ」は、切欠きが面Ｆ１の内部から始まり、かつ内部で終わる状態である。当該切欠きがこの「切入れ」に該当する場合は、サブステップ３５に進み、切入れ処理を行う。該当しない場合は、サブステップ３６に進む。
【００６１】
次に、当該切欠きが「切分け」であるか否かを確認する（サブステップ３６）。「切分け」は、切欠きの開始点及び終了点が、いずれも面Ｆ１の辺または頂点と一致する状態である。当該切欠きがこの「切分け」に該当する場合は、サブステップ３７に進み、切分け処理を行う。該当しない場合は、サブステップ３８に進む。
【００６２】
当該切欠きが、前述した４パターンのいずれにも該当しない場合には、切断方法不明を通知するエラーメッセージを出力し（サブステップ３８）、サブステップ１３を終了する。続いて、前述の４パターンの具体的な処理について、それぞれ説明する。
【００６３】
＜サブステップ３１：切込み処理＞
まず、切込み処理について、図６及び図７を用いて説明する。図６Ａは、この切込み処理が行われる具体例を示している。図６Ａに示すように、「切込み」においては、切欠きの開始点Ｓが面Ｆ１の辺または頂点と一致し、かつ終了点Ｅが面Ｆ１の内部に位置している。この場合は、結果として面Ｆ１が面Ｆ２の表と裏にまたがることとなり、面Ｆ１の図形Ｇ２に関する内外判定は未詳となる。
【００６４】
切込み処理を行うサブステップ３１は、図７のフローチャートに示すように、サブステップ４１〜４４から構成されている。まず、サブステップ４１において、切欠きの開始点Ｓの妥当性を検査する。具体的には、この開始点Ｓが、過去に作成された切込みの開始点である場合、この開始点Ｓに２つの辺または頂点が重畳することとなる。このような場合には、今回の切込みが面Ｆ１の内側となるような辺または頂点を選択する。
【００６５】
次に、面Ｆ１の辺上における切欠きの開始点Ｓの位置に応じて、面Ｆ１に所定の数の頂点を追加する（サブステップ４２）。
具体的には、切欠きの開始点Ｓが、面Ｆ１の辺上の頂点と一致するか、あるいは頂点以外の箇所（以下、辺の中間点と呼ぶ）にあるかにより、面Ｆ１に追加する頂点の数を決定する。例えば、図６Ｂに示すように、切欠きの開始点Ｓが、辺Ｌの中間点にある場合には、面Ｆ１に対して３頂点（Ｍ２１、Ｍ２２、Ｍ２３）を追加する。一方、切欠きの開始点Ｓが、辺Ｌの既存の頂点のいずれか（例えばＭ２）と一致する場合には、切欠き後もこの頂点Ｍ２を利用できるので、２頂点を追加することとなる。この結果、面Ｆ１の内部には、面積のない線状の切れ目が生じる。
【００６６】
次に、切欠きの開始点Ｓ及び終了点Ｅの間を通過する仮想線があるか否かを確認する（サブステップ４３）。このような仮想線がある場合はサブステップ４４へ進み、その仮想線の接続先を変更する。ない場合は、サブステップ３１を終了する。なお、この両ステップ４３，４４における仮想線の接続先の変更については、前述した４パターンの切欠きに共通して行われるので、後述する切分け処理において詳しく説明する。
【００６７】
＜サブステップ３３：切抜け処理＞
次に、切抜け処理について、図８及び図９を用いて説明する。図８は、この切抜け処理が行われる具体例を示している。図８に示すように、「切抜け」においては、切欠きの開始点Ｓが面Ｆ１の内部に位置し、かつ終了点Ｅが面Ｆ１の辺または頂点と一致している。この場合も、前述の切込み処理と同様に、面Ｆ１が面Ｆ２の表と裏にまたがることとなり、面Ｆ１の図形Ｇ２に関する内外判定は未詳となる。
【００６８】
切抜け処理を行うサブステップ３３は、図９のフローチャートに示すように、サブステップ５１〜５４から構成されている。まず、サブステップ５１において、切欠きの終了点Ｅの妥当性を検査する。具体的には、この終了点Ｅが、過去に作成された切抜けの終了点である場合、この終了点Ｅに２つの辺または頂点が重畳することとなる。このような場合には、今回の切抜けが面Ｆ１の内側となるような辺または頂点を選択する。
【００６９】
次に、面Ｆ１の辺上における切欠きの終了点Ｅの位置に応じて、面Ｆ１に所定の数の頂点を追加する（サブステップ５２）。
具体的には、切欠きの終了点Ｅが、面Ｆ１の辺上の頂点と一致するか、あるいは辺の中間点にあるかにより、面Ｆ１に追加する頂点の数を決定する。この頂点追加の処理は、前述の切込み処理におけるサブステップ４２とほぼ同様であり、終了点Ｅが辺の中間点にあれば３頂点を、辺の頂点と一致すれば２頂点を追加する。この場合にも、面Ｆ１の内部には、面積のない線状の切れ目が生じることとなる。
【００７０】
次に、切欠きの開始点Ｓ及び終了点Ｅの間を通過する仮想線があるか否かを確認する（サブステップ５３）。このような仮想線がある場合はサブステップ５４へ進み、その仮想線の接続先を変更する。ない場合は、サブステップ３３を終了する。この両ステップ５３，５４における仮想線の接続先の変更についても、後述する切分け処理において詳しく説明する。
【００７１】
＜サブステップ３５：切入れ処理＞
次に、切入れ処理について、図１０及び図１１を用いて説明する。図１０は、この切入れ処理が行われる具体例を示している。図１０Ａに示すように、「切入れ」においては、切欠きの開始点Ｓ及び終了点Ｅが、いずれも面Ｆ１の内部に位置している。この場合も、前述の切込み処理などと同様に、面Ｆ１が面Ｆ２の表と裏にまたがることとなり、面Ｆ１の図形Ｇ２に関する内外判定は未詳となる。そして、このように切入れが生じた面Ｆ１に対し、前述した仮想線が適用される。
【００７２】
切入れ処理を行うサブステップ３５は、図１１のフローチャートに示すように、サブステップ６１〜６４から構成されている。まず、サブステップ６１において、面Ｆ１を構成するすべての頂点と、切欠きの開始点Ｓ及び終了点Ｅに関して、仮想線により接続される点として最適な位置を検討し、選択する。次に、選択された面Ｆ１の頂点と、切欠きの開始点Ｓ及び終了点Ｅのいずれかとを、仮想線Ｋで接続する（サブステップ６２）。この場合の例を、図１０Ｂに示す。
【００７３】
図１０Ｂに示すように、面Ｆ１の内部に切欠きの開始点Ｓ及び終了点Ｅが位置しているとき、面Ｆ１の既存の頂点Ｍ２と、切欠きの開始点Ｓとを、仮想線Ｋで接続する。また、この仮想線Ｋを適用する際に、面Ｆ１に対して５頂点（Ｍ２１、Ｍ２２、Ｍ２３、Ｍ２４、Ｍ２５）を追加する。
【００７４】
仮想線Ｋは、この面Ｆ１のように、その内部の一部分だけに線状の切れ目が入ったような不完全な状態の面であっても、準正常な面として通常の面と同様に取り扱うことを可能にしている。すなわち、仮想線Ｋにより、面Ｆ１の内部に独立した状態で生成される線状の切れ目が、面Ｆ１の既存の頂点と接続されて、面Ｆ１の辺Ｌへ橋渡しされる。これにより、この線状の切れ目は、面Ｆ１のデータ構造を表現する頂点の集合に取り込まれる形で表現することができる。なお、このような仮想線Ｋによる作用は、ステップ０１で述べた「穴あき面」においても同様に発揮され、かかる「穴あき面」も準正常な面として取り扱うことができる。
【００７５】
次に、切欠きの開始点Ｓ及び終了点Ｅの間を通過する仮想線があるか否かを確認する（サブステップ６３）。このような仮想線がある場合はサブステップ６４へ進み、その仮想線の接続先を変更する。ない場合は、サブステップ３５を終了する。この両ステップ６３，６４における仮想線の接続先の変更についても、後述する切分け処理において詳しく説明する。
【００７６】
＜サブステップ３７：切分け処理＞
次に、切分け処理について、図１２及び図１３を用いて説明する。図１２は、この切分け処理が行われる具体例を示している。図１２Ａに示すように、「切分け」においては、切欠きの開始点Ｓ及び終了点Ｅが、いずれも面Ｆ１の辺または頂点と一致している。この場合は、面Ｆ１が面Ｆ２によって分割され、分割された面Ｆ１の２つの断片が、面Ｆ２に関して表となるか裏となるかが確定する。
【００７７】
切分け処理を行うサブステップ３７は、図１３のフローチャートに示すように、サブステップ７１〜７９で構成されている。まず、サブステップ７１において、切欠きの開始点Ｓ及び終了点Ｅの妥当性を検査する。具体的には、この開始点Ｓ及び終了点Ｅが、過去に作成された切欠きの開始点、終了点、またはその中間の辺上である場合、この各点Ｓ、Ｅに２つの辺または頂点が重畳することとなる。このような場合には、開始点Ｓ及び終了点Ｅによる切分けが、面Ｆ１の内側となるような辺または頂点を選択する。
【００７８】
次に、切欠きの開始点Ｓ及び終了点Ｅが、いずれも面Ｆ１の頂点と一致するか否かを確認する（サブステップ７２）。一致する場合にはサブステップ７３へ進み、一致しない場合にはサブステップ７５へ進む。
【００７９】
次に、開始点Ｓ及び終了点Ｅによって生じる切欠きの区間が、面Ｆ１に適用された仮想線と一致するか否かを確認する（サブステップ７３）。一致する場合はサブステップ７４へ進み、一致しない場合はサブステップ７５へ進む。この場合の例を、図１４を用いて説明する。
【００８０】
図１４Ａに示すように、面Ｆ１は、その内部に穴Ｐ１、Ｐ２、Ｐ３、Ｐ４を有する穴あき面である。また、この面Ｆ１には仮想線Ｋ１、Ｋ２、Ｋ３、Ｋ４が適用され、これらの仮想線により、それぞれの穴Ｐ１〜Ｐ４が、面Ｆ１のいずれかの頂点または他の穴と接続されている。
ここで、穴Ｐ２と穴Ｐ３との間の部分で新たに発生した切欠きＲ１の区間は、穴Ｐ２と穴Ｐ３とを接続している仮想線Ｋ３と一致する。このような場合に、図１４Ｂに示すように、既存の仮想線Ｋ３を通常の辺Ｌ１に変換する（サブステップ７４）。この変換を行った後、サブステップ３７を終了する。
【００８１】
次に、切分けの開始点Ｓ及び終了点Ｅが、それぞれ異なる穴の辺上であるか否かを確認する（サブステップ７５）。異なる穴の辺上である場合にはサブステップ７６へ進み、そうでない場合にはサブステップ７７へ進む。
【００８２】
例えば、図１４Ａ及びＢに示すように、新たに発生した切欠きＲ２の開始点Ｓ及び終了点Ｅは、それぞれ異なる穴Ｐ２、Ｐ４の辺上に位置している。このとき、新たな切欠きＲ２によって、不要となる仮想線を削除する。
具体的には、穴Ｐ２は、仮想線Ｋ２によって面Ｆ１の頂点Ｍ２と接続され、さらに仮想線Ｋ３によって穴Ｐ３と接続されている。また、穴Ｐ３は、仮想線Ｋ４によって穴Ｐ４と接続されている。このとき、仮想線Ｋ２ないしＫ４の階層関係は、面Ｆ１の外周から数えてＫ２、Ｋ３、Ｋ４の順に定義することができる。
【００８３】
この場合において、新たに発生した切欠きＲ２により、穴Ｐ２と穴Ｐ４とは、新たに生成される辺Ｌ２で接続されることになる。そこで、この新たに生成される辺Ｌ２によって不要となる仮想線、すなわち、穴Ｐ２とＰ４とにそれぞれ対応する仮想線Ｋ２とＫ４のうち、より下位にある仮想線Ｋ４を削除する（サブステップ７６）。また、より上位にある仮想線Ｋ２を削除することなく温存する。
【００８４】
なお、別の切欠きＲ３は、穴Ｐ１と面Ｆ１の外周との間で発生している。この場合にも、前述の場合と同様に、穴Ｐ１に関して、仮想線Ｋ１を削除する。
【００８５】
次に、面Ｆ１の辺上における切欠きの開始点Ｓ及び終了点Ｅの位置に応じて、分割後の各断片に所定の数の頂点を追加する（サブステップ７７）。
具体的には、切欠きの開始点Ｓ及び終了点Ｅが、面Ｆ１の辺上の頂点と一致するか、あるいは辺の中間点にあるかにより、分割後の各断片に追加する頂点の数を決定する。例えば、図１２Ｂに示すように、切欠きの開始点Ｓが面Ｆ１の辺Ｌの中間点に位置し、かつ終了点Ｅが面Ｆ１の頂点Ｍ６と一致する場合には、分割後の断片Ｆ１１に対して２頂点（Ｍ２１、Ｍ２２）を追加するとともに、分割後の他の断片Ｆ１２に対して１頂点（Ｍ６１）を追加する。また、切欠きの開始点Ｓ及び終了点Ｅがともに面Ｆ１の頂点のいずれかと一致する場合は、分割後のそれぞれの断片Ｆ１１、Ｆ１２に対して１頂点を追加する。
【００８６】
この結果、分割により発生した断片Ｆ１１及びＦ１２は、面Ｆ２に関して表となるか裏となるかが確定する。そこで、それぞれの断片Ｆ１１及びＦ１２に対して、面Ｆ２に関する表裏を示すフラグを付加する。この場合は、図１４Ａ，Ｂに示すように、面Ｆ１の上部で新たな切欠きＲ４が発生し、その切欠きＲ４の上側と下側で別の断片に分割される。分割後のそれぞれの断片は、面Ｆ２に関する表裏が確定し、その旨を示すフラグが付される。
【００８７】
なお、このようにフラグが付されても、面Ｆ２に続く図形Ｇ２の次の面による切欠きにより、さらに分割されるような場合には、このフラグは変更される場合がある。また、次の面による切欠きにより、前述した切入れなどの線状の切れ目が発生するのみで、分割が発生しない場合には、一度確定した表裏のフラグを取り消し、再び未確定とする。
【００８８】
次に、切欠きの開始点Ｓ及び終了点Ｅの間を通過する仮想線があるか否かを確認する（サブステップ７８）。このような仮想線がある場合はサブステップ７９へ進み、その仮想線の接続先を変更する。ない場合は、サブステップ３７を終了する。
【００８９】
この場合の具体例を図１５に示す。図１５Ａに示すように、面Ｆ１では、その内部に新たな切分けが発生し、その開始点Ｓ１及び終了点Ｅ１の間を、既存の仮想線Ｋが通過している。このような場合に、仮想線Ｋの接続先を変更し、図１５Ｂに示すように、切分けの区間と交差しない仮想線Ｋ’とする（サブステップ７９）。この変更の後、サブステップ３７を終了する。
【００９０】
なお、このような仮想線の接続先の変更は、前述した切込み、切抜け、切入れの各処理においても同様に行われる。すなわち、図１５Ａに示す新たな切込みの開始点Ｓ２及び終了点Ｅ２、切抜けの開始点Ｓ３及び終了点Ｅ３、切入れの開始点Ｓ４及び終了点Ｅ４のそれぞれの間を通過する仮想線Ｋがある場合には、図１５Ｂに示すように、仮想線Ｋの接続先の変更を行い、それぞれの区間と交差しない仮想線Ｋ’とする。
【００９１】
次に、再び図４に戻り、サブステップ１４以降の処理について説明する。まず、図形Ｇ２のすべての面について、面Ｆ１及びこれから生成されたすべての断片の切欠き処理が終了したか否かを確認する（サブステップ１４）。すべての面について終了していなければ、Ｇ２から次の面を取り出してこれを面Ｆ２とし（サブステップ１５）、サブステップ１３へ戻り、すべての面について終了するまで、サブステップ１３、１４を繰り返す。終了していれば、サブステップ１６へ進む。
【００９２】
続いて、図形Ｇ１のすべての面について、Ｇ２による切欠き処理が終了したか否かを確認する（サブステップ１６）。すべての面について終了していなければ、Ｇ１から次の面を取り出してこれを面Ｆ１とし（サブステップ１７）、サブステップ１２へ戻り、すべての面について終了するまで、サブステップ１２ないし１６を繰り返す。終了していれば、ステップ０２を終了する。
【００９３】
以上のように、図形Ｇ２で図形Ｇ１を切り取る処理は、面Ｆ２による面Ｆ１及びこれから生成されたすべての断片の切欠き処理の繰り返しに還元される。すなわち、図形Ｇ１及びＧ２における相貫関係の分析は、それぞれの図形を構成する面同士の相貫関係の分析に還元される。
【００９４】
なお、面Ｆ１に対して、図形Ｇ２のすべての面による切欠き処理を行った結果、面Ｆ１の図形Ｇ２に対する表裏が確定していない場合には、補足的な処理を行って表裏を判定してもよい。例えば、面Ｆ１に関して、図形Ｇ２のすべての面が同じ側（面Ｆ１の上または下）にある場合には、面Ｆ１は図形Ｇ２の表（外側）にあると判定し、面Ｆ１が、図形Ｇ２のすべての面に関して下側にある場合には、面Ｆ１は図形Ｇ２の裏（内側）にあると判定するようにしてもよい。
【００９５】
＜ステップ０３：裏側となる部分の除去＞
再び図２に戻り、ステップ０２以降の処理について説明する。ステップ０３において、制御手段２は、図形Ｇ１において、図形Ｇ２の裏側となる部分を除去する。
この除去は、前述したサブステップ７７において、面Ｆ１の各断片に付された、表裏を示すフラグに基づいて行われる。すなわち、図形Ｇ１を構成するすべての面において、裏を示すフラグが付されている断片を一括して除去する。これにより、図形Ｇ１において、図形Ｇ２と合成したときに、図形Ｇ２の裏側となって表示されない部分が除去される。
【００９６】
＜ステップ０４：図形Ｇ１、Ｇ２の合成表示＞
次に、制御手段２は、ステップ０３において、除去されずに残った部分を有する面で構成された図形Ｇ１と、図形Ｇ２とを合成して、その結果をディスプレイなどの表示手段７に表示し、ユーザに提示する。
【００９７】
この表示例を図１６に示す。ここでは、図形Ｇ１としての地形Ｘと、図形Ｇ２としての構造物Ｙとの合成画面を表示した例を示している。この例では、地形Ｘと構造物Ｙとの合成画面が精度良く表示されており、特に地形Ｘと法面ｙ１との接合部分には余分な隙間を生じることなく、必要かつ十分な線分のみで表示されている。
【００９８】
なお、表示された図形Ｇ１及びＧ２において、前述の仮想線が適用された面が含まれている場合であっても、図形の表面の質感などを表示するテクスチャ表示や、明暗のコントラストを表示するシェーディング表示に際しては、仮想線を含まない通常の図形と同様に表示することができる。
【００９９】
また、このように図形Ｇ１及びＧ２が仮想線を含んでいる場合に、この仮想線を非表示として、表示手段７に表示させないように設定してもよい。例えば、仮想線を含む図形をワイヤーフレーム（線形状）で表示する際に、この仮想線を非表示とすることにより、ノイズが少ない表示画面を得ることができる。これにより、従来の三角形分割の場合と比較して、図形演算後の図形の形状を分かりやすく表示することができる。
【０１００】
以上のように、この発明の三次元図形演算プログラムによれば、図形Ｇ２で図形Ｇ１を切り取る処理を、面Ｆ２による面Ｆ１の切欠き処理の繰り返しに還元することができる。これにより、複雑な三次元図形演算を単純化でき、データ量の増大を抑制しつつ、精度の高い図形演算を行うことができる。
【０１０１】
また、仮想線を適用することにより、面の内部に穴を有する穴あき面や、面同士の切欠き処理において、その一部だけに線状の切れ目が入ったような不完全な状態の面を、準正常な面として取り扱うことが可能になる。これにより、これら不完全な状態の面を、従来のように図形分割することなく表現することができ、通常の面と同様に、面同士の切欠き処理を行うことができる。
【０１０２】
さらに、このように、面同士の切欠き処理において、準正常な面を取り扱うことにより、バッファやスタックなどの特別なデータ構造が不要となる。これにより、処理が単純化され、データ量の増大も抑制される。
また、準正常な面において新たな切欠きが発生した場合に、その新たな切欠きの発生状況に応じて、仮想線の削除や接続先の変更が行われる。これにより、仮想線は、準正常な面において常に適切に適用されることとなり、連続的な面同士の切欠き処理においても、正確に処理を行うことができる。
【０１０３】
なお、サブステップ１３における面Ｆ２による面Ｆ１及びこれから生成されたすべての断片の切欠き処理において、エラーが発生した場合に、このエラーとなった２つの面又は面と断片の組み合わせをエラーログとして、ハードディスクドライブ装置などの記録手段５に記録してもよい。
【０１０４】
すなわち、図形演算のエラーは、ほとんどの場合、面Ｆ２による面Ｆ１及びこれから生成されたすべての断片の切欠き処理の過程で発生する。このとき、エラーが発生した面Ｆ１又は断片と面Ｆ２のデータを、エラーログとして記録しておくことにより、図形演算終了後において、エラーが発生した面の所在を、処理対象の図形Ｇ１及びＧ２から容易に探し出すことができる。また、発生したエラーが、三次元図形演算プログラムの不完全性に起因するものである場合、このエラーログを用いて、プログラムの修正やテストを行うことができ、この点でプログラムの保守性を向上させることができる。
【０１０５】
また、この発明の三次元図形演算プログラムは、メモリ上にロードして実行されるダイナミックリンクライブラリ（ＤＬＬ）としても提供することができる。このように、この発明の三次元図形演算プログラムをダイナミックリンクライブラリとして提供することにより、他のプログラムに影響を与えることなく独立して修正や更新を行うことができ、この点でも保守性が向上する。
【０１０６】
また、このように、三次元図形演算プログラムをダイナミックリンクライブラリとして独立させることにより、この三次元図形演算プログラムで実現される三次元図形演算機能を、独立した機能として提供することが可能となる。これにより、かかる三次元図形演算機能の適用範囲は、本実施形態に係る景観検討装置のような、景観の検討を目的とするものに限定されることなく、他の様々な装置にも応用することができる。この場合において、かかるダイナミックリンクライブラリは、社内ネットワークやインターネットなどを経由して、ネットワーク上の各コンピュータに提供されるようにしてもよい。
【符号の説明】
【０１０７】
１ 景観検討装置
２ 制御手段（ＣＰＵ）
３ 記憶手段（ＲＡＭ）
４ 記憶手段（ＲＯＭ）
５ 記録手段
６ 入力手段
７ 表示手段
８ 通信インタフェース
９ 撮像手段
１０ 穴あき面
１１ 穴
１２ 頂点
Ｋ 仮想線
Ｓ 切欠きの開始点
Ｅ 切欠きの終了点
【技術分野】
【０００１】
この発明は、三次元空間における複数の三次元図形の相貫関係を分析して各三次元図形の合成表示を行う三次元図形演算プログラム、ダイナミックリンクライブラリ及び景観検討装置に関し、特に三次元図形演算プログラムを用いて地形や構造物の合成画面を生成・表示し、景観のシミュレーションや検討を行う技術に係るものである。
【背景技術】
【０００２】
従来、建設事業においては、ビルや路面などの構造物を三次元データとして用意しておき、背景写真や地形の三次元データと合成することにより、建設計画案の内容を三次元空間において立体的に確認することのできる景観シミュレーションシステムが知られている。このシステムでは、景観検討に用いる合成画面を作成する過程で、三次元空間における地形と構造物との間の重なり合い（相貫関係）を分析し、相互に重なり合う部分を除去した上で、それぞれの合成を行っている。すなわち、既存地形などの地物の一部の切欠き処理を行い、この切欠き処理が施された部分に、新たに追加される土木建築施設などを合成することにより、景観検討用の合成画面を表示している。
【０００３】
初期の景観シミュレーションシステムにおいては、地形と構造物（とりわけ法面）との相貫関係に基づく図形演算を、描画処理の陰線消去に使用するデプス・バッファを用いて実行していた。すなわち、地形及び構造物の平面図を、表示画面の解像度に対応したメッシュに分割した上で、各格子点に関して地形と構造物のどちらが上にあるかを判定し、この判定結果で得られる地形と構造物との交差部を抽出する。そして、この交差図形（水平面上に投影された二次元の閉多角形）に基づいて、削除されるべき地形の範囲と、そこに充填されるべき法面の形状を求めて、これらを合成していた。
【０００４】
しかし、この方法で取得される地形と構造物との交差部の形状は、画面サイズによって規定されるデプス・バッファの解像度に制約され、直線部分に関しても単純な直線形ではなく、折れ線として取得される。このため、データが不必要に大きくなるにもかかわらず、演算結果の精度が低く、地形と構造物との間に隙間が生じたり、境界付近の地形及び構造物の表面を構成する多角形の平面性が失われるなどの問題があった。また、遠景として長大法面などの検討に使用することはできても、路上を走行する車両乗員などの近接する視点位置からの景観画像の質には限界があった。
【０００５】
この問題を解決する手法として、三角形分割による三次元図形演算法が提案されている（非特許文献１参照）。この手法によれば、三次元データで表現される地形や構造物を、多面体に近似した形状（ポリゴン）として表現し、その表面を構成する複雑な多角形をあらかじめ三角形に分割しておく。そして、地形と構造物との交差部において、それぞれの三角形同士の切欠き処理を行うことにより、処理の場合分けが単純化され、厳密な座標計算を行うことが可能となっている。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】「建築研究資料Ｎｏ．９６ 成熟都市シミュレータ Ｖｅｒ１．０＋ 景観シミュレータ Ｖｅｒ２．０５ 実務マニュアル」 建設省建築研究所 ２０００年７月
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、前述の三角形分割による図形演算では、単純な三角形同士の切欠き処理であっても、処理結果は複雑な形状となり、次の処理に先立ってさらに三角形分割が要求される。そのため、処理が進行するにしたがって、地形が複雑に細分化していき、データ量が肥大してしまうという問題があった。また、地形が複雑に細分化されるために、演算の成功率も低く、精度の良い演算方法とはいえないものとなっていた。
【０００８】
この発明は、かかる課題を解決するためになされたものであり、複数の三次元図形の相貫関係に基づき各三次元図形の合成画面を生成する図形演算において、データ量の増大を抑制しつつ、精度の高い図形演算を行うことのできる三次元図形演算プログラム、ダイナミックリンクライブラリ及び三次元図形演算プログラムを実行して景観の検討を行う景観検討装置を提供することを目的とする。
【課題を解決するための手段】
【０００９】
前記の目的を達成するために、請求項１に記載の発明は、三次元空間における複数の三次元図形の相貫関係を分析し、相互に重なり合う部分を除去して各三次元図形を合成表示する三次元図形演算プログラムであって、前記各三次元図形を、面の集合である多面体に近似した形状に表現する第１ステップと、前記第１ステップにおいて多面体に近似した形状に表現された各三次元図形において、一の三次元図形を構成するすべての面に関する、他の三次元図形を構成するすべての面の相貫関係を分析する第２ステップと、前記第２ステップにおける面同士の相貫関係の分析結果に基づき、一の三次元図形を構成する各面において、他の三次元図形と重なり合い裏側となる部分を除去する第３ステップと、前記第３ステップにおいて除去されなかった部分を有する面からなる三次元図形同士を合成して表示する第４ステップと、をコンピュータに実行させることを特徴とする。
【００１０】
請求項２に記載の発明は、請求項１に記載の三次元図形演算プログラムにおいて、前記第２ステップにおける面同士の相貫関係の分析は、一の三次元図形を構成する各面と、他の三次元図形を構成する各面との切欠き状態に基づいて行われ、一の面による切欠きが、他の面の辺または頂点から始まり、かつ他の面の内部で終わる場合の処理を行う切込みステップと、一の面による切欠きが、他の面の内部から始まり、かつ他の面の辺または頂点で終わる場合の処理を行う切抜けステップと、一の面による切欠きが、他の面の内部から始まり、かつ他の面の内部で終わる場合の処理を行う切入れステップと、一の面による切欠きにより、他の面が複数の断片に分割される場合に、分割後の複数の各断片の分割面に関する表裏を確定する切分けステップと、をさらに有することを特徴とする。
【００１１】
請求項３に記載の発明は、請求項２に記載の三次元図形演算プログラムにおいて、前記第１ステップにおいて多面体に近似した形状に表現された三次元図形の各面のうち、面内部に穴を有する面について、前記穴を構成するいずれかの頂点と、この穴を有する面を構成するいずれかの頂点とを仮想線で接続するサブステップをさらに有することを特徴とする。
【００１２】
請求項４に記載の発明は、請求項２または３に記載の三次元図形演算プログラムにおいて、前記切入れステップにおいて、面内部に面積のない線状の切れ目が生じた面について、前記切れ目の一端と、この切れ目が生じた面を構成するいずれかの頂点とを仮想線で接続するサブステップをさらに有することを特徴とする。
【００１３】
請求項５に記載の発明は、請求項３または４に記載の三次元図形演算プログラムにおいて、前記仮想線を有する面について、前記第２ステップにおいて他の面による新たな切欠きが生じた場合、この新たな切欠きの発生状況に応じて、前記仮想線の削除もしくは接続先の変更を行うサブステップをさらに有することを特徴とする。
【００１４】
請求項６に記載の発明は、請求項３ないし５のいずれかに記載の三次元図形演算プログラムにおいて、前記第４ステップにおける合成表示に際し、前記仮想線を非表示に設定可能であることを特徴とする。
【００１５】
請求項７に記載の発明は、請求項１ないし６のいずれかに記載の三次元図形演算プログラムにおいて、前記第１ステップにおいて多面体に近似した形状に表現された三次元図形の各面が、前記第２ステップ以降の処理を適用する対象として正常であるか異常であるかを判定し、異常と判定された面に対して修正を行うサブステップをさらに有することを特徴とする。
【００１６】
請求項８に記載の発明は、請求項１ないし７のいずれかに記載の三次元図形演算プログラムにおいて、前記第２ステップにおける面同士の相貫関係の分析の結果、分析エラーとなった面の組み合わせをエラーログとして記録手段に記録するサブステップをさらに有することを特徴とする。
【００１７】
請求項９に記載の発明は、メモリ上にロードして実行されるダイナミックリンクライブラリであって、請求項１ないし８のいずれかに記載の三次元図形演算プログラムを含んでいることを特徴とする。
【００１８】
請求項１０に記載の発明は、地形又は構造物の三次元データを解析し、三次元空間における前記地形又は構造物の合成画面を表示して景観のシミュレーション及び検討を行う景観検討装置であって、前記地形又は構造物の三次元データを入力する入力手段と、前記入力された三次元データを記録する記録手段と、請求項１ないし８のいずれかに記載の三次元図形演算プログラムを記憶する記憶手段と、前記記憶手段に記憶された三次元図形演算プログラムを実行して、前記地形又は構造物の三次元データに基づき前記合成画面を生成する制御手段と、前記生成された合成画面を表示する表示手段と、を備えたことを特徴とする。
【００１９】
請求項１１に記載の発明は、請求項１０に記載の景観検討装置において、前記地形又は構造物の撮像データを取得する撮像手段と、該撮像手段により取得された撮像データを受信するための通信インタフェースと、をさらに備えたことを特徴とする。
【発明の効果】
【００２０】
この発明は、前記のようであって、請求項１に記載の発明によれば、三次元空間における複数の三次元図形の相貫関係の分析を、各三次元図形を構成する面同士の相貫関係の分析に還元することができる。これにより、三次元図形同士の図形演算が単純化され、データ量の増大を抑制しつつ、精度の高い図形演算を行うことができる。
【００２１】
請求項２に記載の発明によれば、請求項１に記載の三次元図形演算プログラムにおける面同士の相貫関係の分析が、切欠きの発生状況に応じて４つの処理ステップに場合分けされる。これにより、切欠きの発生状況に応じた適切な処理ステップが選択され、面同士の相貫関係の分析を正確に行うことができる。
【００２２】
請求項３に記載の発明によれば、多面体を構成する面のうち、その内部に穴を有する面に対して、仮想線を適用することにより、これらの面を準正常な面として取り扱うことができる。これにより、内部に穴を有する面であっても、図形分割することなく、通常の面と同様に、面同士の相貫関係の分析を行うことができる。
【００２３】
請求項４に記載の発明によれば、面同士の相貫関係の分析において、内部に面積のない線状の切れ目が生じた面に対して、仮想線を適用することにより、これらの面を準正常な面として取り扱うことができる。これにより、内部に面積のない線状の切れ目が生じた面であっても、図形分割することなく、通常の面と同様に、面同士の相貫関係の分析を行うことができる。
【００２４】
請求項５に記載の発明によれば、仮想線を有する準正常な面において、新たな切欠きが発生した場合に、その新たな切欠きの発生状況に応じて、仮想線の削除や接続先の変更が行われる。これにより、仮想線は、準正常な面において常に適切に適用されることとなり、連続的な面同士の分析においても正確に分析を行うことができる。
【００２５】
請求項６に記載の発明によれば、図形演算の結果を表示する際に、仮想線を非表示に設定することができる。これにより、ノイズの少ない表示画面を得ることができ、図形演算後の図形の形状を分かりやすく表示することができる。
【００２６】
請求項７に記載の発明によれば、面同士の相貫関係の分析に先立って、分析対象となる面のうち異常が検出された面に対して、適宜修正が施される。これにより、面の異常性に起因する分析エラーが発生する割合を低減させることができる。
【００２７】
請求項８に記載の発明によれば、面同士の相貫関係の分析において、分析エラーとなった面の組み合わせがエラーログとして記録される。これにより、相貫関係の分析における分析エラーの発生箇所を容易に特定することができ、この点でプログラムの保守性が向上する。
【００２８】
請求項９に記載の発明によれば、三次元図形演算プログラムをダイナミックリンクライブラリとして提供することにより、他のプログラムに影響を与えることなく独立して修正や更新を行うことができ、この点でも保守性が向上する。また、この三次元図形演算プログラムで実現される三次元図形演算機能を、独立した機能として提供することが可能となり、その応用範囲を拡大することができる。
【００２９】
請求項１０に記載の発明によれば、前記請求項１ないし８のいずれかに記載の作用効果を、景観検討装置においても奏することができる。これにより、三次元空間における地形又は構造物の合成画面を表示する際に、その境界部分において余計な隙間がなく、滑らかに合成された画面を表示することができる。
【００３０】
請求項１１に記載の発明によれば、カメラなどの撮像手段によって撮像された地形又は構造物の撮像データを、撮像手段から受信することができる。これにより、入力手段によって入力された三次元データのみならず、撮像手段によって撮像されたデータからでも、景観の検討を行うことができる。
【図面の簡単な説明】
【００３１】
【図１】この発明の一実施の形態に係る景観検討装置の構成例を示すブロック図である。
【図２】同上の三次元図形演算プログラムにより実行される図形演算の全体処理を示すフローチャートである。
【図３】同上の穴あき面に仮想線を適用した例を示す説明図である。
【図４】同上の三次元図形演算プログラムにより実行される面同士の相貫関係の分析の全体処理を示すフローチャートである。
【図５】同上の面Ｆ２による面Ｆ１の切欠き処理を示すフローチャートである。
【図６Ａ】同上の「切込み」の概要を示す説明図である。
【図６Ｂ】同上の「切込み」における頂点追加の例を示す説明図である。
【図７】同上の切込み処理の流れを示すフローチャートである。
【図８】同上の「切抜け」の概要を示す説明図である。
【図９】同上の切抜け処理の流れを示すフローチャートである。
【図１０Ａ】同上の「切入れ」の概要を示す説明図である。
【図１０Ｂ】同上の「切入れ」における仮想線の適用例を示す説明図である。
【図１１】同上の切入れ処理の流れを示すフローチャートである。
【図１２Ａ】同上の「切分け」の概要を示す説明図である。
【図１２Ｂ】同上の「切分け」における頂点追加の例を示す説明図である。
【図１３】同上の切分け処理の流れを示すフローチャートである。
【図１４Ａ】同上の切分けの発生状況に応じた仮想線の削除又は通常の辺への変更の様子を示す説明図である。
【図１４Ｂ】同上の切分けの発生状況に応じた仮想線の削除又は通常の辺への変更の様子を示す説明図である。
【図１５Ａ】同上の切欠きの発生状況に応じた仮想線の接続先の変更の様子を示す説明図である。
【図１５Ｂ】同上の切欠きの発生状況に応じた仮想線の接続先の変更の様子を示す説明図である。
【図１６】同上の景観検討装置により表示される地形及び構造物の合成画面の例を示す説明図である。
【発明を実施するための形態】
【００３２】
この発明の一実施の形態に係る三次元図形演算プログラムでは、三次元空間における複数の三次元図形の相貫関係を分析する際に、まず、各三次元図形を多面体に近似した形状（ポリゴン）として表現する。そして、一の三次元図形を構成するすべての面と、他の三次元図形を構成するすべての面との間で、順次相貫関係を分析する。この面同士の相貫関係の分析は、面と面との間で発生する切欠き状態に基づいて行われ、この切欠き状態に応じた所定の切欠き処理が行われる。このように、複数の三次元図形における相貫関係の分析を、面同士の切欠き処理の繰り返しに還元することで、処理を単純化している。
【００３３】
また、各三次元図形を多面体として表現した際に、その内部に穴を有する面が生じた場合に、この面に対して仮想線を適用することにより、これらの面を「準正常な面」として取り扱い、通常の面と同様に切欠き処理を適用することを可能としている。また、この仮想線は、面同士の切欠き処理の過程で、その内部に線状の切れ目が生じた面に対しても適用され、これらの面も同様に「準正常な面」として取り扱っている。
以下、図面を参照しながら、三次元図形演算プログラムの具体的な処理内容について説明する。ここでは、この三次元図形演算プログラムを実行して、地形又は構造物の合成画面を表示し、景観の検討を行う景観検討装置を例に挙げて説明する。
【００３４】
図１において、１は景観検討装置で、この景観検討装置１は、三次元データとして予め用意されたビルや路面などの構造物と、同様に用意された背景写真や地形と、の合成画面を表示して、三次元空間における合成の様子を立体的に確認することを主な基本機能としている。また、この合成画面を表示するために必要となる様々な編集画面を提供する機能も、併せて備えている。
【００３５】
景観検討装置１は、一般的なパーソナルコンピュータＰＣを有している。すなわち、このＰＣは、装置全体の制御や図形演算を行う制御手段（ＣＰＵ：Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓ Ｕｎｉｔ）２、制御手段２の処理データなどを一時記憶する書き換え可能なＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）３、固定データなどを記憶するＲＯＭ（Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）４、図形演算結果のデータなどを記録するハードディスクドライブ装置などの記録手段５、各種データの入力や指示を行うキーボードやマウスなどの入力手段６、図形演算結果を表示するディスプレイなどの表示手段７、ネットワーク接続に使用する通信インタフェース８、などの通常のコンピュータのハードウェア資源を備えている。そして、これらの各ハードウェア資源と、三次元図形演算プログラムをはじめとするソフトウェアとの協働により、景観検討装置１の基本機能が実現される。
【００３６】
また、この景観検討装置１は、景観検討の対象となる地形や構造物を撮像する撮像手段９を備えていてもよい。この撮像手段９は、例えばデジタルカメラなどで構成され、この撮像手段９により取得された地形や構造物の撮像データを用いて、景観の検討を行うこともできる。
【００３７】
この撮像手段９により取得された撮像データは、景観検討装置１に通信インタフェース８を経由して送信することができる。このように、撮像手段９から入力される撮像データとしては、例えば地形や構造物を立体的に見るために、複数の異なるカメラの視点位置から撮像したステレオ写真や、通常の方法で撮像した単眼写真などが挙げられる。このように入力されたステレオ写真などの撮像データは、三次元図形演算プログラムの入力となる三次元データに変換され、この三次元データを用いて、図形演算が行われる。
【００３８】
この他、入力データとして三次元図形演算プログラムに入力される三次元データとしては、過去にＣＡＤ（Ｃｏｍｐｕｔｅｒ Ａｉｄｅｄ Ｄｅｓｉｇｎ）やＧＩＳ（Ｇｅｏｇｒａｐｈｉｃ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｙｓｔｅｍ）で作成された三次元データを、図形演算に適したデータ形式に変換したものや、過去に作成された紙図面を基に、オペレータが入力手段６を用いて三次元データとして作成したものを用いてもよい。これらの方法により作成した三次元データや、撮像手段９による撮像データから生成した三次元データは、ハードディスクドライブ装置などの記録手段５に記録される。
【００３９】
このように、三次元図形演算プログラムの入力となる三次元データが用意された後、オペレータにより、マウスなどの入力手段６が操作され、図形演算の開始が指示される。この指示を受けると、制御手段２は、予めＲＯＭ４に記憶されている三次元図形演算プログラムを読み出し、これを実行して図形演算を開始する。なお、この三次元図形演算プログラムは、ＣＤ−ＲＯＭなどの外部記録媒体からインストールされ、ハードディスクドライブ装置などの記録手段５に記録されていてもよい。以下、制御手段２が実行する図形演算について、図２ないし図１５を用いて詳細に説明する。
【００４０】
＜全体の流れ＞
図２は、制御手段２が実行する図形演算の全体の流れを示すフローチャートである。はじめに、このフローチャートに基づき図形演算の全体の流れを説明し、次に、各ステップにおける具体的な処理内容について説明する。
【００４１】
図形演算は、図２に示すように、大きく４つの処理ステップで構成される。各ステップの処理の概要を以下に示す。
（ステップ０１）入力された地形や構造物などの三次元データを基に、各三次元図形を多面体に近似した形状（ポリゴン）に表現する。
（ステップ０２）ステップ０１において、多面体に近似した形状に表現された各三次元図形において、一の三次元図形を構成するすべての面に関する、他の三次元図形を構成するすべての面の相貫関係を分析する。
（ステップ０３）ステップ０２における各面同士の相貫関係の分析結果に基づき、各面において他の三次元図形と重なり合い裏側となる部分を除去する。
（ステップ０４）ステップ０３において、除去されなかった部分を有する面で構成される三次元図形同士を合成し、合成画面を表示する。
以下、これら各ステップについて、詳細に説明する。
【００４２】
＜ステップ０１：多面体に近似する＞
まず、制御手段２は、オペレータにより指示されて図形演算の対象となった構造物などの図形の三次元データを、記録手段５から読み出す。そして、読み出した三次元データに基づき、各三次元図形を多面体に近似した形状（ポリゴン）として表現する。そして、このように表現された各三次元図形を構成する各面において、その内部に穴を有する面（以下、穴あき面と称する）が生じた場合に、この穴あき面に対して仮想線を適用する。
【００４３】
この仮想線は、前述の穴あき面のように、内部に穴を有する面であっても、穴のない通常の面と同様に取り扱うことを可能にするもので、例えばビルの外壁や、既に図形演算が施されている地形など、内部に穴のある三次元図形であっても、通常の三次元図形と同様に取り扱うことができる。
【００４４】
具体的な仮想線の適用例を図３に示す。この例では、内部に穴１１を有する穴あき面１０において、この穴１１を構成するいずれかの頂点と、穴あき面１０を構成するいずれかの頂点（ここでは頂点１２）とを、仮想線Ｋで接続する。このように、穴１１と頂点１２とを仮想線Ｋで接続することにより、穴あき面１０を従来の三角形分割のように図形分割することなく、ステップ０２以降の処理で用いることができる。なお、この仮想線Ｋの具体的な作用については、後述のステップ０２において説明する。
【００４５】
制御手段２は、このように多面体として表現された三次元図形のすべての面に関するデータを、ＲＡＭ３に記憶する。また、これらのデータは、ハードディスクドライブ装置などの記録手段５に記録してもよい。
【００４６】
＜ステップ０２：面同士の相貫関係の分析＞
次に、制御手段２は、ステップ０１において多面体として表現された各三次元図形において、一の三次元図形を構成するすべての面に関する、他の三次元図形を構成するすべての面の相貫関係を分析する。このステップ０２は、図４のフローチャートに示すサブステップ１１〜１７で構成されている。なお、ここでは、説明を簡単にするために、２つの三次元図形Ｇ１、Ｇ２を例として、図４のフローチャートに基づき各サブステップについて説明する。
【００４７】
まず、２つの三次元図形Ｇ１、Ｇ２において、図形Ｇ１を構成するすべての面に関し、図形Ｇ２の内部に含まれる部分を考える。このような部分は、図形Ｇ２と重なり合ってＧ２の裏側となる部分であり、取り除かれるべき部分となる。そこで、図形Ｇ１を構成するすべての面に関して、図形Ｇ２の内部に含まれる部分を取り除くことを、「Ｇ２でＧ１を切り取る」と呼ぶ。
【００４８】
このように、Ｇ２でＧ１を切り取る場合、Ｇ１を構成する各々の面は、相互に影響を受けることなく、互いに独立してＧ２に切り取られる。すなわち、Ｇ１を構成する１つの面Ｆ１について、Ｇ２の内部に含まれる部分が切り取られるとき、Ｇ１を構成するＦ１以外の面に対しては、同様の切り取りにおいて影響を与えない。そこで、Ｇ１を構成する１つの面Ｆ１から、Ｇ２に含まれる部分を切り取ることを、「Ｇ２でＦ１を切り取る」と呼ぶ。そこで、まず、図形Ｇ１から１つの面Ｆ１を取り出す（サブステップ１１）。
【００４９】
このように取り出した面Ｆ１をＧ２で切り取るためには、Ｇ２を構成するすべての面で、面Ｆ１を切り取る必要がある。そこで、次に、図形Ｇ２から１つの面Ｆ２を取り出す（サブステップ１２）。
このように取り出した面Ｆ２により、面Ｆ１を切り取ることを、「Ｆ２でＦ１を切り取る」と呼ぶ。また、その際に行われる処理を「Ｆ２によるＦ１の切欠き処理」と呼ぶ（サブステップ１３）。以下、この面Ｆ２による面Ｆ１の切欠き処理について説明する。
【００５０】
＜サブステップ１３：面Ｆ２による面Ｆ１の切欠き処理＞
この切欠き処理を行うサブステップ１３は、さらに図５のフローチャートに示すサブステップ２１〜３８で構成されている。この各サブステップの処理について、図５のフローチャートに基づき説明する。
【００５１】
まず、面Ｆ１及び面Ｆ２が、切欠き処理を適用する対象として正常であるか異常であるかを判定する（サブステップ２１）。すなわち、切欠き処理を適用しようとする面は、必ずしも現実に存在しうる幾何学的な形状の面であるとは限らない。例えば、頂点が２以下しかない頂点不足の面や、ある辺と次の辺が一直線上にある面などである。このような面は、切欠き処理を行うには不適切な面となる。
そこで、処理に先立って、対象となる面を診断し、異常であると判定された場合には、可能な限り修正を行ってから処理を行う。なお、このような診断及び修正は、切欠き処理を施す前の面に限らず、切欠き処理を行った結果として得られる面に対しても行うことができる。
【００５２】
次に、面Ｆ１と面Ｆ２が同一平面であるか否かを確認する（サブステップ２２）。同一平面であれば、従来の二次元図形演算処理を行う（サブステップ２３）。同一平面でなければ、サブステップ２４へ進む。
【００５３】
次に、面Ｆ１に関する面Ｆ２の各頂点の高さを求める。そして、面Ｆ２のすべての頂点が、面Ｆ１の上または下にあるか否かを確認する（サブステップ２４）。もし、面Ｆ２のすべての頂点が面Ｆ１よりも上または下にあれば、この二つの面は接触しないと判定して（サブステップ２６）、サブステップ１３を終了する。それ以外の場合は、サブステップ２５へ進む。
【００５４】
次に、面Ｆ２に関する面Ｆ１の各頂点の高さを求める。そして、面Ｆ１のすべての頂点が、面Ｆ２の上または下にあるか否かを確認する（サブステップ２５）。もし、面Ｆ１のすべての頂点が面Ｆ２よりも上または下にあれば、この二つの面は接触しないと判定して（サブステップ２６）、サブステップ１３を終了する。それ以外の場合は、サブステップ２７へ進む。
【００５５】
次に、面Ｆ１と面Ｆ２の交線となる直線（交差線）を求める（サブステップ２７）。そして、この交差線と、面Ｆ１及び面Ｆ２のすべての辺との交点を求め、この交点のリストを作成する（サブステップ２８）。このリストにおいては、各交点を、交差線に沿った１次元座標値に基づいて並び替えておく。このとき、面Ｆ１が仮想線を含む場合は、この仮想線と交差線との交点も同様にリスト化する。
【００５６】
次に、前述のリストに基づいて、面Ｆ２による面Ｆ１の切欠きの開始点及び終了点を求める（サブステップ２９）。具体的には、前述の交差線上において、仮想線以外の交点によって区切られた各区間を、１次元座標値が若い順に評価する。その結果、面Ｆ１に含まれ、かつ面Ｆ２にも含まれるすべての区間が、実際に切欠きが行われる区間となる。すなわち、これらの各区間の開始点及び終了点が、それぞれの切欠きの開始点及び終了点となる。なお、仮想線による交点は、当該区間の属性としてリスト化しておく。
【００５７】
次に、サブステップ２９において求めた切欠きの開始点及び終了点に基づき、切欠き処理の場合分けを行う。すなわち、面Ｆ２による面Ｆ１の切欠き処理は、面Ｆ１における切欠きの開始点及び終了点の位置に応じて、「切込み」「切抜け」「切入れ」「切分け」の４パターンに場合分けされる。そこで、面Ｆ２による面Ｆ１の切欠きが、このいずれのパターンに該当するかを順次確認していく。
【００５８】
まず、当該切欠きが「切込み」であるか否かを確認する（サブステップ３０）。「切込み」は、切欠きが面Ｆ１の辺または頂点から始まり、かつ面Ｆ１の内部で終わる状態である。当該切欠きがこの「切込み」に該当する場合は、サブステップ３１に進み、切込み処理を行う。該当しない場合は、サブステップ３２に進む。
【００５９】
次に、当該切欠きが「切抜け」であるか否かを確認する（サブステップ３２）。「切抜け」は、切欠きが面Ｆ１の内部から始まり、かつ面Ｆ１の辺または頂点で終わる状態である。当該切欠きがこの「切抜け」に該当する場合は、サブステップ３３に進み、切抜け処理を行う。該当しない場合は、サブステップ３４に進む。
【００６０】
次に、当該切欠きが「切入れ」であるか否かを確認する（サブステップ３４）。「切入れ」は、切欠きが面Ｆ１の内部から始まり、かつ内部で終わる状態である。当該切欠きがこの「切入れ」に該当する場合は、サブステップ３５に進み、切入れ処理を行う。該当しない場合は、サブステップ３６に進む。
【００６１】
次に、当該切欠きが「切分け」であるか否かを確認する（サブステップ３６）。「切分け」は、切欠きの開始点及び終了点が、いずれも面Ｆ１の辺または頂点と一致する状態である。当該切欠きがこの「切分け」に該当する場合は、サブステップ３７に進み、切分け処理を行う。該当しない場合は、サブステップ３８に進む。
【００６２】
当該切欠きが、前述した４パターンのいずれにも該当しない場合には、切断方法不明を通知するエラーメッセージを出力し（サブステップ３８）、サブステップ１３を終了する。続いて、前述の４パターンの具体的な処理について、それぞれ説明する。
【００６３】
＜サブステップ３１：切込み処理＞
まず、切込み処理について、図６及び図７を用いて説明する。図６Ａは、この切込み処理が行われる具体例を示している。図６Ａに示すように、「切込み」においては、切欠きの開始点Ｓが面Ｆ１の辺または頂点と一致し、かつ終了点Ｅが面Ｆ１の内部に位置している。この場合は、結果として面Ｆ１が面Ｆ２の表と裏にまたがることとなり、面Ｆ１の図形Ｇ２に関する内外判定は未詳となる。
【００６４】
切込み処理を行うサブステップ３１は、図７のフローチャートに示すように、サブステップ４１〜４４から構成されている。まず、サブステップ４１において、切欠きの開始点Ｓの妥当性を検査する。具体的には、この開始点Ｓが、過去に作成された切込みの開始点である場合、この開始点Ｓに２つの辺または頂点が重畳することとなる。このような場合には、今回の切込みが面Ｆ１の内側となるような辺または頂点を選択する。
【００６５】
次に、面Ｆ１の辺上における切欠きの開始点Ｓの位置に応じて、面Ｆ１に所定の数の頂点を追加する（サブステップ４２）。
具体的には、切欠きの開始点Ｓが、面Ｆ１の辺上の頂点と一致するか、あるいは頂点以外の箇所（以下、辺の中間点と呼ぶ）にあるかにより、面Ｆ１に追加する頂点の数を決定する。例えば、図６Ｂに示すように、切欠きの開始点Ｓが、辺Ｌの中間点にある場合には、面Ｆ１に対して３頂点（Ｍ２１、Ｍ２２、Ｍ２３）を追加する。一方、切欠きの開始点Ｓが、辺Ｌの既存の頂点のいずれか（例えばＭ２）と一致する場合には、切欠き後もこの頂点Ｍ２を利用できるので、２頂点を追加することとなる。この結果、面Ｆ１の内部には、面積のない線状の切れ目が生じる。
【００６６】
次に、切欠きの開始点Ｓ及び終了点Ｅの間を通過する仮想線があるか否かを確認する（サブステップ４３）。このような仮想線がある場合はサブステップ４４へ進み、その仮想線の接続先を変更する。ない場合は、サブステップ３１を終了する。なお、この両ステップ４３，４４における仮想線の接続先の変更については、前述した４パターンの切欠きに共通して行われるので、後述する切分け処理において詳しく説明する。
【００６７】
＜サブステップ３３：切抜け処理＞
次に、切抜け処理について、図８及び図９を用いて説明する。図８は、この切抜け処理が行われる具体例を示している。図８に示すように、「切抜け」においては、切欠きの開始点Ｓが面Ｆ１の内部に位置し、かつ終了点Ｅが面Ｆ１の辺または頂点と一致している。この場合も、前述の切込み処理と同様に、面Ｆ１が面Ｆ２の表と裏にまたがることとなり、面Ｆ１の図形Ｇ２に関する内外判定は未詳となる。
【００６８】
切抜け処理を行うサブステップ３３は、図９のフローチャートに示すように、サブステップ５１〜５４から構成されている。まず、サブステップ５１において、切欠きの終了点Ｅの妥当性を検査する。具体的には、この終了点Ｅが、過去に作成された切抜けの終了点である場合、この終了点Ｅに２つの辺または頂点が重畳することとなる。このような場合には、今回の切抜けが面Ｆ１の内側となるような辺または頂点を選択する。
【００６９】
次に、面Ｆ１の辺上における切欠きの終了点Ｅの位置に応じて、面Ｆ１に所定の数の頂点を追加する（サブステップ５２）。
具体的には、切欠きの終了点Ｅが、面Ｆ１の辺上の頂点と一致するか、あるいは辺の中間点にあるかにより、面Ｆ１に追加する頂点の数を決定する。この頂点追加の処理は、前述の切込み処理におけるサブステップ４２とほぼ同様であり、終了点Ｅが辺の中間点にあれば３頂点を、辺の頂点と一致すれば２頂点を追加する。この場合にも、面Ｆ１の内部には、面積のない線状の切れ目が生じることとなる。
【００７０】
次に、切欠きの開始点Ｓ及び終了点Ｅの間を通過する仮想線があるか否かを確認する（サブステップ５３）。このような仮想線がある場合はサブステップ５４へ進み、その仮想線の接続先を変更する。ない場合は、サブステップ３３を終了する。この両ステップ５３，５４における仮想線の接続先の変更についても、後述する切分け処理において詳しく説明する。
【００７１】
＜サブステップ３５：切入れ処理＞
次に、切入れ処理について、図１０及び図１１を用いて説明する。図１０は、この切入れ処理が行われる具体例を示している。図１０Ａに示すように、「切入れ」においては、切欠きの開始点Ｓ及び終了点Ｅが、いずれも面Ｆ１の内部に位置している。この場合も、前述の切込み処理などと同様に、面Ｆ１が面Ｆ２の表と裏にまたがることとなり、面Ｆ１の図形Ｇ２に関する内外判定は未詳となる。そして、このように切入れが生じた面Ｆ１に対し、前述した仮想線が適用される。
【００７２】
切入れ処理を行うサブステップ３５は、図１１のフローチャートに示すように、サブステップ６１〜６４から構成されている。まず、サブステップ６１において、面Ｆ１を構成するすべての頂点と、切欠きの開始点Ｓ及び終了点Ｅに関して、仮想線により接続される点として最適な位置を検討し、選択する。次に、選択された面Ｆ１の頂点と、切欠きの開始点Ｓ及び終了点Ｅのいずれかとを、仮想線Ｋで接続する（サブステップ６２）。この場合の例を、図１０Ｂに示す。
【００７３】
図１０Ｂに示すように、面Ｆ１の内部に切欠きの開始点Ｓ及び終了点Ｅが位置しているとき、面Ｆ１の既存の頂点Ｍ２と、切欠きの開始点Ｓとを、仮想線Ｋで接続する。また、この仮想線Ｋを適用する際に、面Ｆ１に対して５頂点（Ｍ２１、Ｍ２２、Ｍ２３、Ｍ２４、Ｍ２５）を追加する。
【００７４】
仮想線Ｋは、この面Ｆ１のように、その内部の一部分だけに線状の切れ目が入ったような不完全な状態の面であっても、準正常な面として通常の面と同様に取り扱うことを可能にしている。すなわち、仮想線Ｋにより、面Ｆ１の内部に独立した状態で生成される線状の切れ目が、面Ｆ１の既存の頂点と接続されて、面Ｆ１の辺Ｌへ橋渡しされる。これにより、この線状の切れ目は、面Ｆ１のデータ構造を表現する頂点の集合に取り込まれる形で表現することができる。なお、このような仮想線Ｋによる作用は、ステップ０１で述べた「穴あき面」においても同様に発揮され、かかる「穴あき面」も準正常な面として取り扱うことができる。
【００７５】
次に、切欠きの開始点Ｓ及び終了点Ｅの間を通過する仮想線があるか否かを確認する（サブステップ６３）。このような仮想線がある場合はサブステップ６４へ進み、その仮想線の接続先を変更する。ない場合は、サブステップ３５を終了する。この両ステップ６３，６４における仮想線の接続先の変更についても、後述する切分け処理において詳しく説明する。
【００７６】
＜サブステップ３７：切分け処理＞
次に、切分け処理について、図１２及び図１３を用いて説明する。図１２は、この切分け処理が行われる具体例を示している。図１２Ａに示すように、「切分け」においては、切欠きの開始点Ｓ及び終了点Ｅが、いずれも面Ｆ１の辺または頂点と一致している。この場合は、面Ｆ１が面Ｆ２によって分割され、分割された面Ｆ１の２つの断片が、面Ｆ２に関して表となるか裏となるかが確定する。
【００７７】
切分け処理を行うサブステップ３７は、図１３のフローチャートに示すように、サブステップ７１〜７９で構成されている。まず、サブステップ７１において、切欠きの開始点Ｓ及び終了点Ｅの妥当性を検査する。具体的には、この開始点Ｓ及び終了点Ｅが、過去に作成された切欠きの開始点、終了点、またはその中間の辺上である場合、この各点Ｓ、Ｅに２つの辺または頂点が重畳することとなる。このような場合には、開始点Ｓ及び終了点Ｅによる切分けが、面Ｆ１の内側となるような辺または頂点を選択する。
【００７８】
次に、切欠きの開始点Ｓ及び終了点Ｅが、いずれも面Ｆ１の頂点と一致するか否かを確認する（サブステップ７２）。一致する場合にはサブステップ７３へ進み、一致しない場合にはサブステップ７５へ進む。
【００７９】
次に、開始点Ｓ及び終了点Ｅによって生じる切欠きの区間が、面Ｆ１に適用された仮想線と一致するか否かを確認する（サブステップ７３）。一致する場合はサブステップ７４へ進み、一致しない場合はサブステップ７５へ進む。この場合の例を、図１４を用いて説明する。
【００８０】
図１４Ａに示すように、面Ｆ１は、その内部に穴Ｐ１、Ｐ２、Ｐ３、Ｐ４を有する穴あき面である。また、この面Ｆ１には仮想線Ｋ１、Ｋ２、Ｋ３、Ｋ４が適用され、これらの仮想線により、それぞれの穴Ｐ１〜Ｐ４が、面Ｆ１のいずれかの頂点または他の穴と接続されている。
ここで、穴Ｐ２と穴Ｐ３との間の部分で新たに発生した切欠きＲ１の区間は、穴Ｐ２と穴Ｐ３とを接続している仮想線Ｋ３と一致する。このような場合に、図１４Ｂに示すように、既存の仮想線Ｋ３を通常の辺Ｌ１に変換する（サブステップ７４）。この変換を行った後、サブステップ３７を終了する。
【００８１】
次に、切分けの開始点Ｓ及び終了点Ｅが、それぞれ異なる穴の辺上であるか否かを確認する（サブステップ７５）。異なる穴の辺上である場合にはサブステップ７６へ進み、そうでない場合にはサブステップ７７へ進む。
【００８２】
例えば、図１４Ａ及びＢに示すように、新たに発生した切欠きＲ２の開始点Ｓ及び終了点Ｅは、それぞれ異なる穴Ｐ２、Ｐ４の辺上に位置している。このとき、新たな切欠きＲ２によって、不要となる仮想線を削除する。
具体的には、穴Ｐ２は、仮想線Ｋ２によって面Ｆ１の頂点Ｍ２と接続され、さらに仮想線Ｋ３によって穴Ｐ３と接続されている。また、穴Ｐ３は、仮想線Ｋ４によって穴Ｐ４と接続されている。このとき、仮想線Ｋ２ないしＫ４の階層関係は、面Ｆ１の外周から数えてＫ２、Ｋ３、Ｋ４の順に定義することができる。
【００８３】
この場合において、新たに発生した切欠きＲ２により、穴Ｐ２と穴Ｐ４とは、新たに生成される辺Ｌ２で接続されることになる。そこで、この新たに生成される辺Ｌ２によって不要となる仮想線、すなわち、穴Ｐ２とＰ４とにそれぞれ対応する仮想線Ｋ２とＫ４のうち、より下位にある仮想線Ｋ４を削除する（サブステップ７６）。また、より上位にある仮想線Ｋ２を削除することなく温存する。
【００８４】
なお、別の切欠きＲ３は、穴Ｐ１と面Ｆ１の外周との間で発生している。この場合にも、前述の場合と同様に、穴Ｐ１に関して、仮想線Ｋ１を削除する。
【００８５】
次に、面Ｆ１の辺上における切欠きの開始点Ｓ及び終了点Ｅの位置に応じて、分割後の各断片に所定の数の頂点を追加する（サブステップ７７）。
具体的には、切欠きの開始点Ｓ及び終了点Ｅが、面Ｆ１の辺上の頂点と一致するか、あるいは辺の中間点にあるかにより、分割後の各断片に追加する頂点の数を決定する。例えば、図１２Ｂに示すように、切欠きの開始点Ｓが面Ｆ１の辺Ｌの中間点に位置し、かつ終了点Ｅが面Ｆ１の頂点Ｍ６と一致する場合には、分割後の断片Ｆ１１に対して２頂点（Ｍ２１、Ｍ２２）を追加するとともに、分割後の他の断片Ｆ１２に対して１頂点（Ｍ６１）を追加する。また、切欠きの開始点Ｓ及び終了点Ｅがともに面Ｆ１の頂点のいずれかと一致する場合は、分割後のそれぞれの断片Ｆ１１、Ｆ１２に対して１頂点を追加する。
【００８６】
この結果、分割により発生した断片Ｆ１１及びＦ１２は、面Ｆ２に関して表となるか裏となるかが確定する。そこで、それぞれの断片Ｆ１１及びＦ１２に対して、面Ｆ２に関する表裏を示すフラグを付加する。この場合は、図１４Ａ，Ｂに示すように、面Ｆ１の上部で新たな切欠きＲ４が発生し、その切欠きＲ４の上側と下側で別の断片に分割される。分割後のそれぞれの断片は、面Ｆ２に関する表裏が確定し、その旨を示すフラグが付される。
【００８７】
なお、このようにフラグが付されても、面Ｆ２に続く図形Ｇ２の次の面による切欠きにより、さらに分割されるような場合には、このフラグは変更される場合がある。また、次の面による切欠きにより、前述した切入れなどの線状の切れ目が発生するのみで、分割が発生しない場合には、一度確定した表裏のフラグを取り消し、再び未確定とする。
【００８８】
次に、切欠きの開始点Ｓ及び終了点Ｅの間を通過する仮想線があるか否かを確認する（サブステップ７８）。このような仮想線がある場合はサブステップ７９へ進み、その仮想線の接続先を変更する。ない場合は、サブステップ３７を終了する。
【００８９】
この場合の具体例を図１５に示す。図１５Ａに示すように、面Ｆ１では、その内部に新たな切分けが発生し、その開始点Ｓ１及び終了点Ｅ１の間を、既存の仮想線Ｋが通過している。このような場合に、仮想線Ｋの接続先を変更し、図１５Ｂに示すように、切分けの区間と交差しない仮想線Ｋ’とする（サブステップ７９）。この変更の後、サブステップ３７を終了する。
【００９０】
なお、このような仮想線の接続先の変更は、前述した切込み、切抜け、切入れの各処理においても同様に行われる。すなわち、図１５Ａに示す新たな切込みの開始点Ｓ２及び終了点Ｅ２、切抜けの開始点Ｓ３及び終了点Ｅ３、切入れの開始点Ｓ４及び終了点Ｅ４のそれぞれの間を通過する仮想線Ｋがある場合には、図１５Ｂに示すように、仮想線Ｋの接続先の変更を行い、それぞれの区間と交差しない仮想線Ｋ’とする。
【００９１】
次に、再び図４に戻り、サブステップ１４以降の処理について説明する。まず、図形Ｇ２のすべての面について、面Ｆ１及びこれから生成されたすべての断片の切欠き処理が終了したか否かを確認する（サブステップ１４）。すべての面について終了していなければ、Ｇ２から次の面を取り出してこれを面Ｆ２とし（サブステップ１５）、サブステップ１３へ戻り、すべての面について終了するまで、サブステップ１３、１４を繰り返す。終了していれば、サブステップ１６へ進む。
【００９２】
続いて、図形Ｇ１のすべての面について、Ｇ２による切欠き処理が終了したか否かを確認する（サブステップ１６）。すべての面について終了していなければ、Ｇ１から次の面を取り出してこれを面Ｆ１とし（サブステップ１７）、サブステップ１２へ戻り、すべての面について終了するまで、サブステップ１２ないし１６を繰り返す。終了していれば、ステップ０２を終了する。
【００９３】
以上のように、図形Ｇ２で図形Ｇ１を切り取る処理は、面Ｆ２による面Ｆ１及びこれから生成されたすべての断片の切欠き処理の繰り返しに還元される。すなわち、図形Ｇ１及びＧ２における相貫関係の分析は、それぞれの図形を構成する面同士の相貫関係の分析に還元される。
【００９４】
なお、面Ｆ１に対して、図形Ｇ２のすべての面による切欠き処理を行った結果、面Ｆ１の図形Ｇ２に対する表裏が確定していない場合には、補足的な処理を行って表裏を判定してもよい。例えば、面Ｆ１に関して、図形Ｇ２のすべての面が同じ側（面Ｆ１の上または下）にある場合には、面Ｆ１は図形Ｇ２の表（外側）にあると判定し、面Ｆ１が、図形Ｇ２のすべての面に関して下側にある場合には、面Ｆ１は図形Ｇ２の裏（内側）にあると判定するようにしてもよい。
【００９５】
＜ステップ０３：裏側となる部分の除去＞
再び図２に戻り、ステップ０２以降の処理について説明する。ステップ０３において、制御手段２は、図形Ｇ１において、図形Ｇ２の裏側となる部分を除去する。
この除去は、前述したサブステップ７７において、面Ｆ１の各断片に付された、表裏を示すフラグに基づいて行われる。すなわち、図形Ｇ１を構成するすべての面において、裏を示すフラグが付されている断片を一括して除去する。これにより、図形Ｇ１において、図形Ｇ２と合成したときに、図形Ｇ２の裏側となって表示されない部分が除去される。
【００９６】
＜ステップ０４：図形Ｇ１、Ｇ２の合成表示＞
次に、制御手段２は、ステップ０３において、除去されずに残った部分を有する面で構成された図形Ｇ１と、図形Ｇ２とを合成して、その結果をディスプレイなどの表示手段７に表示し、ユーザに提示する。
【００９７】
この表示例を図１６に示す。ここでは、図形Ｇ１としての地形Ｘと、図形Ｇ２としての構造物Ｙとの合成画面を表示した例を示している。この例では、地形Ｘと構造物Ｙとの合成画面が精度良く表示されており、特に地形Ｘと法面ｙ１との接合部分には余分な隙間を生じることなく、必要かつ十分な線分のみで表示されている。
【００９８】
なお、表示された図形Ｇ１及びＧ２において、前述の仮想線が適用された面が含まれている場合であっても、図形の表面の質感などを表示するテクスチャ表示や、明暗のコントラストを表示するシェーディング表示に際しては、仮想線を含まない通常の図形と同様に表示することができる。
【００９９】
また、このように図形Ｇ１及びＧ２が仮想線を含んでいる場合に、この仮想線を非表示として、表示手段７に表示させないように設定してもよい。例えば、仮想線を含む図形をワイヤーフレーム（線形状）で表示する際に、この仮想線を非表示とすることにより、ノイズが少ない表示画面を得ることができる。これにより、従来の三角形分割の場合と比較して、図形演算後の図形の形状を分かりやすく表示することができる。
【０１００】
以上のように、この発明の三次元図形演算プログラムによれば、図形Ｇ２で図形Ｇ１を切り取る処理を、面Ｆ２による面Ｆ１の切欠き処理の繰り返しに還元することができる。これにより、複雑な三次元図形演算を単純化でき、データ量の増大を抑制しつつ、精度の高い図形演算を行うことができる。
【０１０１】
また、仮想線を適用することにより、面の内部に穴を有する穴あき面や、面同士の切欠き処理において、その一部だけに線状の切れ目が入ったような不完全な状態の面を、準正常な面として取り扱うことが可能になる。これにより、これら不完全な状態の面を、従来のように図形分割することなく表現することができ、通常の面と同様に、面同士の切欠き処理を行うことができる。
【０１０２】
さらに、このように、面同士の切欠き処理において、準正常な面を取り扱うことにより、バッファやスタックなどの特別なデータ構造が不要となる。これにより、処理が単純化され、データ量の増大も抑制される。
また、準正常な面において新たな切欠きが発生した場合に、その新たな切欠きの発生状況に応じて、仮想線の削除や接続先の変更が行われる。これにより、仮想線は、準正常な面において常に適切に適用されることとなり、連続的な面同士の切欠き処理においても、正確に処理を行うことができる。
【０１０３】
なお、サブステップ１３における面Ｆ２による面Ｆ１及びこれから生成されたすべての断片の切欠き処理において、エラーが発生した場合に、このエラーとなった２つの面又は面と断片の組み合わせをエラーログとして、ハードディスクドライブ装置などの記録手段５に記録してもよい。
【０１０４】
すなわち、図形演算のエラーは、ほとんどの場合、面Ｆ２による面Ｆ１及びこれから生成されたすべての断片の切欠き処理の過程で発生する。このとき、エラーが発生した面Ｆ１又は断片と面Ｆ２のデータを、エラーログとして記録しておくことにより、図形演算終了後において、エラーが発生した面の所在を、処理対象の図形Ｇ１及びＧ２から容易に探し出すことができる。また、発生したエラーが、三次元図形演算プログラムの不完全性に起因するものである場合、このエラーログを用いて、プログラムの修正やテストを行うことができ、この点でプログラムの保守性を向上させることができる。
【０１０５】
また、この発明の三次元図形演算プログラムは、メモリ上にロードして実行されるダイナミックリンクライブラリ（ＤＬＬ）としても提供することができる。このように、この発明の三次元図形演算プログラムをダイナミックリンクライブラリとして提供することにより、他のプログラムに影響を与えることなく独立して修正や更新を行うことができ、この点でも保守性が向上する。
【０１０６】
また、このように、三次元図形演算プログラムをダイナミックリンクライブラリとして独立させることにより、この三次元図形演算プログラムで実現される三次元図形演算機能を、独立した機能として提供することが可能となる。これにより、かかる三次元図形演算機能の適用範囲は、本実施形態に係る景観検討装置のような、景観の検討を目的とするものに限定されることなく、他の様々な装置にも応用することができる。この場合において、かかるダイナミックリンクライブラリは、社内ネットワークやインターネットなどを経由して、ネットワーク上の各コンピュータに提供されるようにしてもよい。
【符号の説明】
【０１０７】
１ 景観検討装置
２ 制御手段（ＣＰＵ）
３ 記憶手段（ＲＡＭ）
４ 記憶手段（ＲＯＭ）
５ 記録手段
６ 入力手段
７ 表示手段
８ 通信インタフェース
９ 撮像手段
１０ 穴あき面
１１ 穴
１２ 頂点
Ｋ 仮想線
Ｓ 切欠きの開始点
Ｅ 切欠きの終了点
【特許請求の範囲】
【請求項１】
三次元空間における複数の三次元図形の相貫関係を分析し、相互に重なり合う部分を除去して各三次元図形を合成表示する三次元図形演算プログラムであって、
前記各三次元図形を、面の集合である多面体に近似した形状に表現する第１ステップと、
前記第１ステップにおいて多面体に近似した形状に表現された各三次元図形において、一の三次元図形を構成するすべての面に関する、他の三次元図形を構成するすべての面の相貫関係を分析する第２ステップと、
前記第２ステップにおける面同士の相貫関係の分析結果に基づき、一の三次元図形を構成する各面において、他の三次元図形と重なり合い裏側となる部分を除去する第３ステップと、
前記第３ステップにおいて除去されなかった部分を有する面からなる三次元図形同士を合成して表示する第４ステップと、
をコンピュータに実行させることを特徴とする三次元図形演算プログラム。
【請求項２】
前記第２ステップにおける面同士の相貫関係の分析は、一の三次元図形を構成する各面と、他の三次元図形を構成する各面との切欠き状態に基づいて行われ、
一の面による切欠きが、他の面の辺または頂点から始まり、かつ他の面の内部で終わる場合の処理を行う切込みステップと、
一の面による切欠きが、他の面の内部から始まり、かつ他の面の辺または頂点で終わる場合の処理を行う切抜けステップと、
一の面による切欠きが、他の面の内部から始まり、かつ他の面の内部で終わる場合の処理を行う切入れステップと、
一の面による切欠きにより、他の面が複数の断片に分割される場合に、分割後の複数の各断片の分割面に関する表裏を確定する切分けステップと、
をさらに有することを特徴とする請求項１記載の三次元図形演算プログラム。
【請求項３】
前記第１ステップにおいて多面体に近似した形状に表現された三次元図形の各面のうち、面内部に穴を有する面について、前記穴を構成するいずれかの頂点と、この穴を有する面を構成するいずれかの頂点とを仮想線で接続するサブステップをさらに有する
ことを特徴とする請求項２記載の三次元図形演算プログラム。
【請求項４】
前記切入れステップにおいて、面内部に面積のない線状の切れ目が生じた面について、前記切れ目の一端と、この切れ目が生じた面を構成するいずれかの頂点とを仮想線で接続するサブステップをさらに有する
ことを特徴とする請求項２または３に記載の三次元図形演算プログラム。
【請求項５】
前記仮想線を有する面について、前記第２ステップにおいて他の面による新たな切欠きが生じた場合、この新たな切欠きの発生状況に応じて、前記仮想線の削除もしくは接続先の変更を行うサブステップをさらに有する
ことを特徴とする請求項３または４に記載の三次元図形演算プログラム。
【請求項６】
前記第４ステップにおける合成表示に際し、前記仮想線を非表示に設定可能であることを特徴とする請求項３ないし５のいずれかに記載の三次元図形演算プログラム。
【請求項７】
前記第１ステップにおいて多面体に近似した形状に表現された三次元図形の各面が、前記第２ステップ以降の処理を適用する対象として正常であるか異常であるかを判定し、異常と判定された面に対して修正を行うサブステップをさらに有する
ことを特徴とする請求項１ないし６のいずれかに記載の三次元図形演算プログラム。
【請求項８】
前記第２ステップにおける面同士の相貫関係の分析の結果、分析エラーとなった面の組み合わせをエラーログとして記録手段に記録するサブステップをさらに有する
ことを特徴とする請求項１ないし７のいずれかに記載の三次元図形演算プログラム。
【請求項９】
メモリ上にロードして実行されるダイナミックリンクライブラリであって、請求項１ないし８のいずれかに記載の三次元図形演算プログラムを含んでいることを特徴とするダイナミックリンクライブラリ。
【請求項１０】
地形又は構造物の三次元データを解析し、三次元空間における前記地形又は構造物の合成画面を表示して景観のシミュレーション及び検討を行う景観検討装置であって、
前記地形又は構造物の三次元データを入力する入力手段と、
前記入力された三次元データを記録する記録手段と、
請求項１ないし８のいずれかに記載の三次元図形演算プログラムを記憶する記憶手段と、
前記記憶手段に記憶された三次元図形演算プログラムを実行して、前記地形又は構造物の三次元データに基づき前記合成画面を生成する制御手段と、
前記生成された合成画面を表示する表示手段と、
を備えたことを特徴とする景観検討装置。
【請求項１１】
前記地形又は構造物の撮像データを取得する撮像手段と、
該撮像手段により取得された撮像データを受信するための通信インタフェースと、をさらに備えたことを特徴とする請求項１０に記載の景観検討装置。
【請求項１】
三次元空間における複数の三次元図形の相貫関係を分析し、相互に重なり合う部分を除去して各三次元図形を合成表示する三次元図形演算プログラムであって、
前記各三次元図形を、面の集合である多面体に近似した形状に表現する第１ステップと、
前記第１ステップにおいて多面体に近似した形状に表現された各三次元図形において、一の三次元図形を構成するすべての面に関する、他の三次元図形を構成するすべての面の相貫関係を分析する第２ステップと、
前記第２ステップにおける面同士の相貫関係の分析結果に基づき、一の三次元図形を構成する各面において、他の三次元図形と重なり合い裏側となる部分を除去する第３ステップと、
前記第３ステップにおいて除去されなかった部分を有する面からなる三次元図形同士を合成して表示する第４ステップと、
をコンピュータに実行させることを特徴とする三次元図形演算プログラム。
【請求項２】
前記第２ステップにおける面同士の相貫関係の分析は、一の三次元図形を構成する各面と、他の三次元図形を構成する各面との切欠き状態に基づいて行われ、
一の面による切欠きが、他の面の辺または頂点から始まり、かつ他の面の内部で終わる場合の処理を行う切込みステップと、
一の面による切欠きが、他の面の内部から始まり、かつ他の面の辺または頂点で終わる場合の処理を行う切抜けステップと、
一の面による切欠きが、他の面の内部から始まり、かつ他の面の内部で終わる場合の処理を行う切入れステップと、
一の面による切欠きにより、他の面が複数の断片に分割される場合に、分割後の複数の各断片の分割面に関する表裏を確定する切分けステップと、
をさらに有することを特徴とする請求項１記載の三次元図形演算プログラム。
【請求項３】
前記第１ステップにおいて多面体に近似した形状に表現された三次元図形の各面のうち、面内部に穴を有する面について、前記穴を構成するいずれかの頂点と、この穴を有する面を構成するいずれかの頂点とを仮想線で接続するサブステップをさらに有する
ことを特徴とする請求項２記載の三次元図形演算プログラム。
【請求項４】
前記切入れステップにおいて、面内部に面積のない線状の切れ目が生じた面について、前記切れ目の一端と、この切れ目が生じた面を構成するいずれかの頂点とを仮想線で接続するサブステップをさらに有する
ことを特徴とする請求項２または３に記載の三次元図形演算プログラム。
【請求項５】
前記仮想線を有する面について、前記第２ステップにおいて他の面による新たな切欠きが生じた場合、この新たな切欠きの発生状況に応じて、前記仮想線の削除もしくは接続先の変更を行うサブステップをさらに有する
ことを特徴とする請求項３または４に記載の三次元図形演算プログラム。
【請求項６】
前記第４ステップにおける合成表示に際し、前記仮想線を非表示に設定可能であることを特徴とする請求項３ないし５のいずれかに記載の三次元図形演算プログラム。
【請求項７】
前記第１ステップにおいて多面体に近似した形状に表現された三次元図形の各面が、前記第２ステップ以降の処理を適用する対象として正常であるか異常であるかを判定し、異常と判定された面に対して修正を行うサブステップをさらに有する
ことを特徴とする請求項１ないし６のいずれかに記載の三次元図形演算プログラム。
【請求項８】
前記第２ステップにおける面同士の相貫関係の分析の結果、分析エラーとなった面の組み合わせをエラーログとして記録手段に記録するサブステップをさらに有する
ことを特徴とする請求項１ないし７のいずれかに記載の三次元図形演算プログラム。
【請求項９】
メモリ上にロードして実行されるダイナミックリンクライブラリであって、請求項１ないし８のいずれかに記載の三次元図形演算プログラムを含んでいることを特徴とするダイナミックリンクライブラリ。
【請求項１０】
地形又は構造物の三次元データを解析し、三次元空間における前記地形又は構造物の合成画面を表示して景観のシミュレーション及び検討を行う景観検討装置であって、
前記地形又は構造物の三次元データを入力する入力手段と、
前記入力された三次元データを記録する記録手段と、
請求項１ないし８のいずれかに記載の三次元図形演算プログラムを記憶する記憶手段と、
前記記憶手段に記憶された三次元図形演算プログラムを実行して、前記地形又は構造物の三次元データに基づき前記合成画面を生成する制御手段と、
前記生成された合成画面を表示する表示手段と、
を備えたことを特徴とする景観検討装置。
【請求項１１】
前記地形又は構造物の撮像データを取得する撮像手段と、
該撮像手段により取得された撮像データを受信するための通信インタフェースと、をさらに備えたことを特徴とする請求項１０に記載の景観検討装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６Ａ】
【図６Ｂ】
【図７】
【図８】
【図９】
【図１０Ａ】
【図１０Ｂ】
【図１１】
【図１２Ａ】
【図１２Ｂ】
【図１３】
【図１４Ａ】
【図１４Ｂ】
【図１５Ａ】
【図１５Ｂ】
【図１６】
【図２】
【図３】
【図４】
【図５】
【図６Ａ】
【図６Ｂ】
【図７】
【図８】
【図９】
【図１０Ａ】
【図１０Ｂ】
【図１１】
【図１２Ａ】
【図１２Ｂ】
【図１３】
【図１４Ａ】
【図１４Ｂ】
【図１５Ａ】
【図１５Ｂ】
【図１６】
【公開番号】特開２０１２−１９０２１３（Ｐ２０１２−１９０２１３Ａ）
【公開日】平成２４年１０月４日（２０１２．１０．４）
【国際特許分類】
【出願番号】特願２０１１−５２４６６（Ｐ２０１１−５２４６６）
【出願日】平成２３年３月１０日（２０１１．３．１０）
【出願人】（５０１１９８０３９）国土交通省国土技術政策総合研究所長 (23)
【Ｆターム（参考）】
【公開日】平成２４年１０月４日（２０１２．１０．４）
【国際特許分類】
【出願日】平成２３年３月１０日（２０１１．３．１０）
【出願人】（５０１１９８０３９）国土交通省国土技術政策総合研究所長 (23)
【Ｆターム（参考）】
[ Back to top ]