TOP > 国内特許検索 > 3次元幾何データの無矛盾化方法及びそのシステム > 明細書

明細書 :3次元幾何データの無矛盾化方法及びそのシステム

発行国 日本国特許庁(JP)
公報種別 特許公報(B2)
特許番号 特許第3950976号 (P3950976)
公開番号 特開2005-196684 (P2005-196684A)
登録日 平成19年5月11日(2007.5.11)
発行日 平成19年8月1日(2007.8.1)
公開日 平成17年7月21日(2005.7.21)
発明の名称または考案の名称 3次元幾何データの無矛盾化方法及びそのシステム
国際特許分類 G06F  17/50        (2006.01)
FI G06F 17/50 626C
請求項の数または発明の数 12
全頁数 23
出願番号 特願2004-004690 (P2004-004690)
出願日 平成16年1月9日(2004.1.9)
審査請求日 平成16年1月9日(2004.1.9)
特許権者または実用新案権者 【識別番号】301022471
【氏名又は名称】独立行政法人情報通信研究機構
発明者または考案者 【氏名】荒川 佳樹
個別代理人の代理人 【識別番号】100085338、【弁理士】、【氏名又は名称】赤澤 一博
【識別番号】100118245、【弁理士】、【氏名又は名称】井上 敬子
審査官 【審査官】加舎 理紅子
参考文献・文献 特開平01-286081(JP,A)
特開平06-124324(JP,A)
荒川佳樹 他,超3角形BRepにおける無誤差完全4次元処理を用いた形状演算アルゴリズム,情報処理学会論文誌,1999年 9月15日,第40巻,第9号,p.3471-3482
調査した分野 G06F 17/50
G06T 11/20
G06T 17/10
特許請求の範囲 【請求項1】
3次元幾何データに対して演算処理を行い、前記演算処理過程で生成及び処理された幾何データを記憶する3次元幾何データ処理システムにおいて、処理される3次元幾何データにおける幾何矛盾を検出しかつ除去する方法であって、
3次元幾何図形の表面データである境界面データを、3角形面データまたは3角形の3つの頂点が同一直線上となるゼロ3角形データにより構成し処理する3角形/ゼロ3角形データ処理ステップと、
前記3角形/ゼロ3角形データ処理ステップで処理された3次元幾何データの数値を必要精度に応じて任意に切り捨てる数値データ切り捨て処理ステップと、
前記数値データ切り捨て処理ステップにより、発生する幾何矛盾を検出し除去する幾何無矛盾化処理ステップと、
を有し、
前記幾何無矛盾化処理ステップが、縮退3角形面を検出し除去する縮退3角形面の検出除去処理ステップ、重なり3角形面を検出し除去する面の重なり検出除去処理ステップ、および矛盾立体を検出し除去する矛盾立体の検出除去処理ステップを含むものであることを特徴とする3次元幾何データの無矛盾化方法。
【請求項2】
縮退3角形面の検出除去処理ステップが、2頂点が同一点となるいびつな3角形、3頂点が同一点となるいびつな3角形、および3頂点が同一直線上となるいびつな3角形を検出し除去するものであることを特徴とする請求項1記載の3次元幾何データの無矛盾化方法。
【請求項3】
面の重なり検出除去処理ステップが、組にした3角形面データの同一平面判定および面の向き判定の判定結果に基づき、3角形面が重なっていると判定された3角形面に対してその重なりを除去するようにした処理であることを特徴とする請求項1または2記載の3次元幾何データの無矛盾化方法。
【請求項4】
矛盾立体の検出除去処理ステップが、
同じ立体を構成する面同士が交差している立体を検出し除去するものであることを特徴とする請求項1乃至3いずれか記載の3次元幾何データの無矛盾化方法。
【請求項5】
矛盾立体の検出除去処理ステップが、
自己干渉立体の分離処理を行うステップ、立体の最上位3角形面の探索処理を行うステップ、立体の最近傍上位立体の探索処理を行うステップ、最近傍上位立体順に立体データのソーティングを行うステップ、面の向きによる立体の消去処理を行うステップからなることを特徴とする請求項1乃至4いずれか記載の3次元幾何データの無矛盾化方法。
【請求項6】
前記各ステップにおいて、
4次元同次座標系処理と可変長ビットの演算を用いて無誤差演算を行うことを特徴とする請求項1乃至5いすれか記載の3次元幾何データの無矛盾化方法。
【請求項7】
3次元幾何データに対して演算処理を行い、前記演算処理過程で生成及び処理された幾何データを記憶する3次元幾何データ処理システムであって、
3次元幾何図形の表面データである境界面データを、3角形面データまたは3角形の3つの頂点が同一直線上となるゼロ3角形データにより構成し処理する3角形/ゼロ3角形データ処理部と、
前記3角形/ゼロ3角形データ処理で処理された3次元幾何データの数値を必要精度に応じて任意に切り捨てる数値データ切り捨て処理部と、
前記数値データ切り捨て処理部により、発生する幾何矛盾を検出し除去する幾何無矛盾化処理部と、
を有し、
前記幾何無矛盾化処理部が、縮退3角形面を検出し除去する縮退3角形処理部、重なり3角形面を検出し除去する重なり3角形処理部、および矛盾立体を検出し除去する矛盾立体処理部を含むものであることを特徴とする3次元幾何データの無矛盾化システム。
【請求項8】
縮退3角形処理部が、2頂点が同一点となるいびつな3角形、3頂点が同一点となるいびつな3角形、および3頂点が同一直線上となるいびつな3角形を検出し除去するものであることを特徴とする請求項7記載の3次元幾何データの無矛盾化システム。
【請求項9】
重なり3角形処理部が、組にした3角形面データの同一平面判定および面の向き判定の判定結果に基づき、3角形面が重なっていると判定された3角形面に対してその重なりを除去する処理をすることを特徴とする請求項7または8記載の3次元幾何データの無矛盾化システム。
【請求項10】
矛盾立体処理部が、
同じ立体を構成する面同士が交差している立体を検出し除去する処理を行うことを特徴とする請求項7乃至9いずれか記載の3次元幾何データの無矛盾化システム。
【請求項11】
矛盾立体処理部が、
自己干渉立体の分離処理と、立体の最上位3角形面の探索処理と、立体の最近傍上位立体の探索処理と、最近傍上位立体順に立体データのソーティングを行う処理と、面の向きによる立体の消去処理とを行うように構成していることを特徴とする請求項7乃至10いずれか記載の3次元幾何データの無矛盾化システム。
【請求項12】
前記各処理部において、
4次元同次座標系処理と可変長ビットの演算を用いて無誤差演算を行うことを特徴とする請求項7乃至11いすれか記載の3次元幾何データの無矛盾化システム。
発明の詳細な説明 【技術分野】
【0001】
本発明は、3次元幾何データの演算処理方法及びそのシステムに関する。
【背景技術】
【0002】
従来技術では、幾何演算は浮動小数点演算を用いて行うのが一般的である。浮動小数点演算では数値の丸め(切り捨て)が行われるために演算誤差が発生する。そして、このような浮動小数点演算が繰り返されると、誤差が蓄積していく。
【0003】
このような演算誤差のために、浮動小数点演算をベースとした幾何演算処理(図形処理)では、処理が破綻し処理系に暴走(バグ)が生じるという問題点があった。このような処理系の暴走へのこれまでの対処方法は、それぞれの破綻に対応した例外処理ルーチン(アドホック的)を作成することにより対応していた。そして、このような例外処理ルーチンはかなりの量となり、また次第に増加していく。すなわち、根本的に処理系の破綻を回避することが出来なかった。
【0004】
この幾何処理の破綻の問題を解決する1つの方法を提案した。この提案では、以下に示す3つの特徴を有し、これにより無誤差形状演算を実現している。そして、計算誤差をまったくなくすことにより、計算誤差から生じる幾何演算の破綻を回避している(例えば特許文献1参照)。
(1)超3角形(ゼロ3角形)幾何データ処理
(2)4次元同次座標系幾何処理
(3)可変長ビットの整数演算

【特許文献1】特許第3151710号
【発明の開示】
【発明が解決しようとする課題】
【0005】
通常の3角形面データ処理およびゼロ3角形を含む超3角形データ処理は、多角形面データ処理と比較して、より単純なデータ構造及び処理アルゴリズムとなるので、その処理系の高信頼性を確保することが容易である。
【0006】
しかしながら、通常の3角形面データ処理および超3角形データ処理でも、誤差による破綻は免れない。この幾何演算の誤差による破綻の問題を根本的に解決するために、特許第3151710号では、ゼロ3角形幾何データ処理および4次元同次座標系幾何処理等を用いて、数値(座標値)の桁数が、ある一定の上限値以上に増大しない効率的な無誤算形状演算方法を実現している。
【0007】
しかし、この特許では、1回限りの形状演算をある上限以下の桁数で効率よく行う方式を提供している。複数回の形状演算を実行すると、やはり桁数が増大していく。この無誤差演算に伴う桁数の増大は数理的に原理的なもので不可避である。
【0008】
このような桁数の増大を回避する現実的かつ実用的な方法は、必要精度に応じて数値(座標値)を切り捨てることである。しかしながら、幾何処理において、このような方法を取ると、幾何矛盾が発生する。
【0009】
本発明は、このような課題に着目してなされたものであって、主たる目的は、上述のような幾何矛盾を検出しかつ除去する汎用的かつ効率的な方法およびその方法を利用したシステムを提供することにある。例えば、3次元幾何データの形状演算において、形状演算を何回も実行しても、演算に破綻が生じない、かつ処理を効率的、高速に実行することが可能な3次元幾何データの演算方法、すなわち幾何無矛盾化処理方法およびその方法を利用したシステムを提供することにある。
【課題を解決するための手段】
【0010】
すなわち、本発明の3次元幾何データの無矛盾化方法は、3次元幾何データに対して演算処理を行い、これらの処理過程で生成及び処理された幾何データを記憶する3次元幾何データ処理システムにおいて、、以下により構成される方法を有することを特徴とする。
(1)3次元幾何図形の表面データである境界面データを、3角形面データまたは3角形の3つの頂点が同一直線上となるゼロ3角形データにより構成し処理する。特に、ゼロ3角形データ形式を用いた幾何処理により、不必要な数値桁数の増大および不必要なデータ量の増大を抑制する。
(2)3次元幾何データを構成する頂点データの座標値データ等を必要精度に応じて切り捨てを行い、数値桁数の増大に対処する。
(3)前記座標値データ等の切り捨て処理により、発生する幾何矛盾を検出し除去する。この処理は、縮退3角形面の検出除去処理、面の重なり検出除去処理および矛盾立体の検出除去処理から構成される。
(4)上記のすべての処理を、4次元同次座標系幾何処理と可変長ビット演算により無誤差演算で行う。4次元同次座標系幾何処理を用いることにより、割り算を排除し、すべての演算を無誤差で行うことができる。
例えば、1÷3のように割り算があると循環小数(無限の桁数)となり、有限の桁数(ビット長)で表現することが出来なくなり、無誤算演算が出来なくなる。これに対して、割り算が必要でない4次元同次座標系幾何処理では、扱う数値が全て有限桁数の有理数であるとすれば、その演算結果も有限桁数の有理数となる。無限桁数の循環小数等になることはない。
【発明の効果】
【0011】
以上に説明したように本発明の3次元幾何データの無矛盾化方法およびその方法を利用したシステムによれば、3次元幾何図形の表面データである境界面データを、3角形面データまたは3角形の3つの頂点が同一直線上となるゼロ3角形データにより構成し処理し、特に、ゼロ3角形データ形式を用いた幾何処理により、不必要な数値桁数の増大および不必要なデータ量の増大を抑制することができ、また、3次元幾何データを構成する頂点データの座標値データ等を必要精度に応じて切り捨てを行い、数値桁数の増大に対処することができ、さらに、座標値データ等の切り捨て処理により、発生する幾何矛盾を検出し除去することができるので、効果的に、3次元幾何データにおける幾何矛盾を検出し除去することができる。すなわち、無矛盾な誤りのない3次元幾何データを生成することができる。
【発明を実施するための最良の形態】
【0012】
以下、本発明の一実施形態を、図面を参照して説明するが、まず始めに、簡単に従来の3次元幾何処理、および、本発明で用いる4次元同時座標幾何演算について説明をしておく。
【0013】
従来の3次元幾何処理は、3次元のユークリッド座標系(X、Y、Z)を用いて行われてきた。そして、この座標系を用いた幾何演算では、割り算が通常発生する。本発明では、次元を1次元上げた4次元の同次座標系(X、Y、Z、w)を用いて幾何処理を行う。このような4次元処理を幾何演算に用いることにより、全ての演算は加減算とかけ算のみで済み、割り算は必要でなくなる。
【0014】
従って、本発明では、頂点データは、この4次元同次座標(X、Y、Z、w)を用いて表現される。また、本発明では、座標値X、Y、Z、wは、全て可変長ビットの整数表現となる。すなわち、図3(4)に示すように、数値は、そのビット長と、符号(+、-)と、整数表現された数値とから構成される。以下、本発明では、特に断らない限り、座標系は4次元同次座標系での実施である。
<4次元同次座標幾何演算>
以下、本実施形態で用いる4次元同次座標幾何演算に関して説明する。なお、特に説明なきもので、太文字のものはベクトル、行列を表すものとする。
(1)2点から線の生成
2点V0=(X0、Y0、Z0、w0)及びV1=(X1、Y1、Z1、w1)を通る直線L01は次式(数1)で与えられる。ただし、V0、V1、L01はベクトル、行列を表している。
【0015】
【数1】
JP0003950976B2_000002t.gif
ここで、P01等は、下式(数2)で与えられる。
【0016】
【数2】
JP0003950976B2_000003t.gif
(2)3点から面の生成(平面係数の算出)
3点V0=(X0、Y0、Z0、w0)、V1=(X1、Y1、Z1、w1)、V2=(X2、Y2、Z2、w2)を通る面F012は、次式(数3)で与えられる。ただし、V0、V1、V2、F012はベクトル、行列を表している。
【0017】
【数3】
JP0003950976B2_000004t.gif
ここで、A012等は、下式(数4)で与えられる。
【0018】
【数4】
JP0003950976B2_000005t.gif
(3)線と面の交点計算
2点Va=(Xa、Ya、Za、wa)およびVb=(Xb、Yb、Zb、wb)を通る直線と、面F012との交点Vは、次式(数5)で与えられる。ただし、Va、Vb、F012はベクトル、行列を表している。
【0019】
【数5】
JP0003950976B2_000006t.gif
ここで、Sa012等は、下式(数6)で与えられる。
【0020】
【数6】
JP0003950976B2_000007t.gif
(4)2点の一致判定
2点V0=(X0、Y0、Z0、w0)とV1=(X1、Y1、Z1、w1)の一致判定は、前記2点を通る直線L01において以下(数7)となることである。ただし、V0、V1、L01はベクトル、行列を表している。
【0021】
【数7】
JP0003950976B2_000008t.gif
(5)2面の一致判定
下式(数8)で表される2つの平面f0とf1との一致判定は,点と面の双対性により,式(数7)と同じ形式となる。
【0022】
【数8】
JP0003950976B2_000009t.gif
(6)点の面に対する位置判定
点V=(X、Y、Z、w)が,平面F012に対してどの位置にあるかの判定は次式(数9)で与えられる。ただし、V、F012はベクトル、行列を表している。
【0023】
【数9】
JP0003950976B2_000010t.gif
式(数9)において、sの符号+、0、-に対応して、点は、面の正側、面上、面の負側となる。
(7)2線分の向き判定
2線分L01とL23が同一直線である時には、両者の向きの判定は、次式(数10)で与えられる。ただし、L01、L23はベクトル、行列を表している。
【0024】
【数10】
JP0003950976B2_000011t.gif
上記の式(数10)において、両者の向きは、sが正の時は同じ方向、負の時は逆向きとなる。
(8)2面の向き判定
2面F012とF345が同一平面である時には、両者の向きの判定は次式(数11)で与えられる。ただし、F012、F345はベクトル、行列を表している。
【0025】
【数11】
JP0003950976B2_000012t.gif
上記の(7)の場合と同様に、両者の向きは、sが正の時は同じ方向、負の時は逆向きとなる。
<超3角形幾何データ>
本発明では、ゼロ3角形を用いた図形処理方式(超3角形幾何処理方式)を提案している。次に、本発明の特徴であるゼロ3角形幾何とそのデータ構造に関して説明する。
【0026】
従来の3次元形状表現(境界面表現)においては、図2(2)に示すように多角形面表現が用いられてきた。以下、多角形面を単に多角形と呼称する。 図2において、(3)は(2)の多角形表現を通常の3角形面表現とした斜視図である。以下、3角形面を単に3角形と呼称する。
【0027】
これに対して、本発明の実施例で例示する超3角形表現は、(4)のようになる。すなわち、図2(4)において、頂点C、D、G、及びHは同一直線上にある。そして、3角形CDH、DGHは頂点が同一直線上となり面積がゼロとなる。これらの3角形をゼロ3角形と呼称している。ゼロ3角形は3角形が完全につぶれた「線形の3角形」とみなすことができる。
【0028】
また、3つの頂点が同一直線上にない通常の3角形を実3角形と呼称している。そして、これらの実3角形とゼロ3角形とを組み合わせた幾何表現形式を拡張された表現形式ということで超3角形幾何表現と呼称している。
【0029】
図2(4)と(3)の3角形の数を比較すると、超3角形表現では4個(ゼロ3角形は2個)、通常3角形表現では6個となる。ゼロ3角形を用いることにより、より少ない実3角形(通常3角形)で面分を表現することが可能となる。このような特徴により、超3角形処理では、3角形幾何の表現性とその処理性が飛躍的に増大する。
【0030】
本発明のデータ構造は、図3に示すように、(1)立体データ、(2)実3角形データ、(3)ゼロ3角形データ、(4)頂点データ、そして(5)交線データから構成される。
【0031】
立体データは、実3角形データおよびゼロ3角形データの集合体である。従って、これらのデータへのポインタで構成される。ここで、ポインタとは、記憶装置(メモリ)上において、該当データが格納されている番地(アドレス)を示すデータである。
【0032】
実3角形データ及びゼロ3角形データは、データ構造上は全く同じ形式となり、3角形の3つの頂点データへのポインタ(v0、v1、v2)と、3つの隣接する実3角形データ或いはゼロ3角形データへのポインタ(t0、t1、t2)とから構成される。また、頂点データは、4次元同次座標形式(X、Y、Z、w)で格納される。座標値は、可変長ビットの整数表現となる。すなわち、ビット長、符号(+、-)および数値(ビット列)から構成される。
【0033】
交線データは、交線の始点及び終点となる頂点データへのポインタ(v0、v1)と、交線を挟んで隣接する2つの3角形データへのポインタ(t0、t1)とから構成される。
<システム構成>
以下、本発明の一実施形態を、図面を参照して説明する。
【0034】
本発明の3次元幾何データの無矛盾化システムたる3次元幾何データ処理システムSSは、図18に示すように、CPU101、メモリ102、外部記憶装置103、マウスやキーボードなどの入力手段104、ディスプレイなどの出力手段105、外部機器06と通信するための外部機器インタフェース106を主な構成要素とする。
【0035】
そして、前記外部記憶装置103やメモリ102に記憶する所定のプログラムを作動させることにより、前記CPU101や周辺機器を作動させ、該3次元幾何データ処理システムSSが、3次元幾何データ処理部01,幾何データ記憶部02,4次元同次座標系幾何処理部(プリュッカー座標演算器)03,可変長ビット整数演算器04、外部機器インターフェース部05等としての機能を発揮するようにしている。
【0036】
以下、各部を説明する。
【0037】
3次元幾何データ処理部01は、3角形/ゼロ3角形データ処理部07、数値データ切り捨て処理部08、幾何無矛盾化処理部09としての機能を発揮するものである。
【0038】
より具体的には、3角形/ゼロ3角形データ処理部07は、外部機器インタフェース106により入力された3次元形状データを通常の3角形データ、あるいは超3角形データに変換するものである。
【0039】
数値データ切り捨て処理部08は、頂点データ等の数値データを、必要精度に応じて切り捨てる処理を行うものである。
【0040】
幾何無矛盾化処理部09は、前記数値データ切り捨て処理部08において、数値データの切り捨てにより発生する幾何矛盾をなくす処理を行うものである。なお、本実施形態では、この幾何無矛盾化処理部09が、縮退3角形処理部10、重なり3角形処理部11、矛盾立体処理部12としての機能を発揮するように構成している。
【0041】
幾何データ記憶部02は、前記外部記憶装置103およびメモリ102の少なくともいずれか一方の所定領域に形成されるものであって、本実施形態では、さらに、立体データ記憶部13、実3角形データ記憶部14、ゼロ3角形データ記憶部15、頂点データ記憶部16、交線データ記憶部17からなるように構成している。
【0042】
より具体的には、立体データ記憶部13、実3角形データ記憶部14、ゼロ3角形データ記憶部15、頂点データ記憶部16、交線データ記憶部17は、前記3次元幾何データ処理部01で生成された超3角形データを構成する、立体データ、実3角形データ、ゼロ3角形データ、頂点データおよび交線データを、それぞれ、記憶するものである。
【0043】
4次元同次座標系幾何処理部03は、全ての幾何演算を4次元同次座標系に基づいて行うものである。即ち、プリュッカー座標演算が行われる。
【0044】
可変長ビット整数演算器04は、加算器、減算器および乗算器としての機能を有するものである。そして、加算、減算及び乗算が可変長ビットの整数演算を用いて、無誤差で行うようにしている。なお、この可変長ビット整数演算器04においては、除算器としての機能がないのが特徴である。
【0045】
外部機器インターフェース部05は、前記3次元幾何データ処理部で処理された演算結果などを外部機器06に対して出力する機能と、前記外部機器06からのデータを受け付け前記3次元幾何データ処理部01に対して出力する機能とを有するものであって、前記外部機器インターフェース106等を利用して構成している。
【0046】
次に、本実施形態の3次元幾何データ処理システムSSの動作についてフロー図などを用いて説明する。
【0047】
特に、本実施形態の根幹をなす幾何無矛盾化処理部09における幾何無矛盾化処理について詳細に説明する。頂点データの下位桁の数値の切り捨てを行うと、次の3つの幾何矛盾が発生する可能性がある。
(1) 縮退3角形(いびつな3角形)
(2) 面の重なり(3角形の重なり)
(3) 矛盾立体(立体の自己干渉等)
ここで、このような幾何矛盾を検出し除去する処理を「無矛盾化処理」と呼ぶことにする。この無矛盾化処理の全体フローチャートは図4に示すようになる。
【0048】
すなわち、[a]縮退3角形の検出除去処理(ステップ400)、[b]重なり3角形の検出除去処理(ステップ401)、[c]矛盾立体の検出除去処理(ステップ402)の順で幾何無矛盾化処理が行われる。
【0049】
なお、[c]矛盾立体の検出除去処理はさらに、[c1]自己干渉立体の分離処理(ステップ403)、[c2]立体の最上位3角形の探索処理(ステップ404)、[c3]立体の最近傍上位立体の探索処理(ステップ405)、[c4]最近傍上位立体順に立体データのソーティング(ステップ406)、[c5]面の向きによる立体の消去処理(ステップ407)の順で行われる。
【0050】
以下、幾何矛盾化処理部09における各処理[a]、[b]、[c1]~[c5]について説明する。
【0051】
[a]縮退3角形の検出除去処理
頂点データの下位桁の数値の切り捨てを行うと、立体を構成する3角形面において、図5(1)~(3)に示すように、以下の3つの「いびつな」3角形が発生する可能性がある。このようないびつな3角形を「縮退3角形」と呼ぶ。
(1) 2頂点が同一点となる3角形
(2) 3頂点が同一点となる3角形
(3) 3頂点が同一直線上となる3角形(ゼロ3角形)
縮退3角形の検出とその除去処理について、図6のフローチャートを用いて説明する。まず、3角形データ(実3角形データおよびゼロ3角形データ)を幾何データ記憶部02から順次取り出し、その頂点データv0、v1、v2を頂点データ記憶部16から順次読み込む(ステップ600)。その3つの頂点データv0、v1、v2に関して同一点判定処理を行う。v0=v1となる場合は(ステップ601)、辺v0v1を挟んで隣接する2つの3角形データ(図5(4)の例ではt0とt1)を消去する。これに伴い、図5(4)に示すように、消去される3角形t0、t1を取り囲む4つの周辺3角形t2、t3、t4、t5の隣接接続情報を変更する。図5(4)では、t0とt1の消去に伴い、t2とt3、およびt4とt5が隣接するようになる。また、v1を頂点に持つすべての3角形データの頂点v1をv0とする。図5(4)では、v1を頂点に持つ3角形面t3、t5、t6の頂点v1をv0に変更する。そして、頂点データv1を消去する(ステップ602)。v0=v2、v1=v2となる場合も同様の処理を行う(ステップ603~606)。以上の処理が、(1)2頂点が同一点となる場合、および(2)3頂点が同一点となる場合の縮退3角形データの検出消去処理である。
【0052】
次に、同一頂点を持たない3角形データに対して、その3つの頂点データv0、v1、v2の同一直線判定処理を行う(ステップ607)。これらの3つの頂点が同一直線上となる場合は、この3角形データをゼロ3角形データとして、ゼロ3角形データ記憶部15に保存する(ステップ608)。同一直線上とならない場合は、通常3角形であるので、実3角形データ記憶部14に書き込む(ステップ609)。以上の処理をすべての3角形データに関して行う。
【0053】
このように、ゼロ3角形幾何処理を行っているので、3角形の3つの頂点が同一直線上となる場合は、このゼロ3角形を特段消去する必要も、例外処理する必要もない。
【0054】
[b]重なり3角形の検出除去処理
幾何矛盾の1つとして、図8(8)に示すように、3角形面が重なり「面のしわ」となる場合がある。図8(8)では、形状の断面図を示しており、頂点A、B、C、D、Eは同一平面上にある。そして、3角形面tiとtjが重なっている。このように面が重なる時は、図8(8)に矢印として示すように、面の向きは必ず逆となる。
【0055】
このような重なり3角形データの検出除去処理について、図7のフローチャートを用いて説明する。まず、同一平面上となり、かつ面の向きが逆となる2つの3角形データのペアを探索する。このために、2つの実3角形データti、tjを幾何データ記憶部02から順次読み出し、同一平面判定および面の向き判定を行う(ステップ701~703)。
【0056】
両者が同一平面かつ面の向きが逆となる場合が、重なり面処理の対象となる。同一平面とならない場合または向きが同じとなる場合は次の実3角形データのペアに処理を進める。
【0057】
両者が同一平面かつ面の向きが逆となる場合は、両者tiとtjが重なるかどうかの判定を行う(ステップ704)。重ならない場合は次の実3角形データのペアに処理を進める。
【0058】
両者が重なる場合は、一方の3角形の頂点により他方の3角形を分割する(ステップ705)。この時のパターンは図8(1)~(4)に示すように4通りある。図8では3角形ABCが頂点Dにより分割される。そして、図8(1)と(2)のパターンの場合のみが分割処理の対象となる。本実施形態では、不必要な分割をなくすために「ゼロ3角形分割」を行う(図8(2)の場合)。ここでは、3角形ADCがゼロ3角形となる。
【0059】
次に、この分割された3角形が他方の分割される前の3角形の内部にあるかどうかの判定処理を順次行う(ステップ706)。判定される3角形の3つの頂点すべてが、もう一方の3角形の内部(辺上を含む)となる場合は、前者の3角形は後者の内部となる(含まれる)。そして、内部となる場合は、この3角形データを消去する(ステップ708)。
【0060】
また、判定される3角形の3つの頂点が、他方の内部および外部の両方となる場合(またがる場合)は、「3角形の位相変形」を行い(ステップ707)、判定される3角形が他方の内部あるいは外部のどちらかになるようにする。
【0061】
図8(5)の例では、分割される前の3角形として、ABCとDEFが重なっている。これらが互いに他を分割しあうと、3角形ABCは、図8(6)のように分割される。ここで、3角形CDEとCFDは、3角形DEFに対して、内部となる部分と外部となる部分の両方がある。そこで、この2つの3角形が構成する4角形CFDEにおいて、その対角線となる辺CDをEFと付け替え、新たな3角形DEFとCFEを生成する(図8(7))。これが3角形の位相変形である。これを繰り返すことにより最終的に、3角形は他方の3角形の内部か外部かのどちらか一方となり、内部および外部の両方に「またがる」場合は存在しなくなる。
【0062】
分割された3角形が、他方の分割される前の3角形の外部となる場合は、次の分割された3角形データに処理を進める。以上の処理を、すべての分割された3角形データに関して行う。
【0063】
最後に、消去された3角形に隣接する3角形データを相互に接続する処理(接続情報の更新処理)を行う(ステップ710)。以上の処理を、同一平面上かつ面の向きが逆となる実3角形データのすべてのペアにおいて行う。これにより、すべての重なり3角形(面のしわ)を消去することができる。
【0064】
[c]矛盾立体の検出除去処理
[c1]自己干渉立体の分離処理
自己干渉立体とは、図10(1)、(2)に示すように、同じ立体を構成する面(3角形面)どうしが交差している立体である。自己干渉立体の分離処理では、図10(3)、(4)に示すように、この交差している面(3角形面)をその交線において分割し、1つの閉じた面(立体)とする処理である。
【0065】
図10では、立体の断面図を示している。灰色領域が形状の内部である。図10(1)では、立体の一部で表裏が逆転している。矛盾立体が発生している。そこで、図10(2)に示すように、この部分を切り離す処理が分離処理となる。また、図10(3)では、立体の内部にある穴が外部にはみ出している。そこで、図10(4)に示すように、このはみ出し部分を分離する。
【0066】
自己干渉立体の分離処理の流れを、図9のフローチャートを用いて説明する。2つの実3角形データti、tjを順次幾何データ記憶部02から取り出し、両者の交差判定処理を行う(ステップ901~903)。交差する場合は、両方の3角形ti、tjの共通交線skを求めて、この共通交線において両者を分割する(ステップ904)。
【0067】
図10(5)の例では、交線ABにおいて、3角形tiとtjが交差している。この時、共通交線skはCDとなる。本実施形態では、重なり3角形検出除去処理において説明したように、不必要な分割をなくすために、「ゼロ3角形分割」を行う。ここでの分割パターンは、図10(6)に示すように2通りとなる。共通交線CDにおいて、その端点C側は3角形の辺上となり、ゼロ3角形分割が行われ、3角形ECGはゼロ3角形となる。もう一方の端点Dは、3角形面内となり、通常の分割が行われる。
【0068】
そして、この分割処理において、共通交線と一致する3角形の辺が存在しない場合は、重なり3角形検出除去処理において説明した位相変形を行い、共通交線と一致する3角形の辺を生成する。以上の処理をすべての実3角形データのペアに関して繰り返す。
【0069】
次に、この交線skを挟んで隣接する3角形の隣接情報を、図11、12に示すように変更する(ステップ907~909)。この処理をすべての交線データskに関して行う。これにより、自己干渉立体を分離することができる。
【0070】
図11、12は、自己干渉立体の分離処理において求めた共通交線sk近傍の面の交差パターンを示している。これらは立体の断面図であり、黒点は共通交線を示している。また、ハッチングがある側が立体の内部である。
【0071】
図11(1)では、面(3角形面)taとtbが完全に交差している。この場合は当然両者の面の接続関係を、共通交線において、切り替える。図11(2)の場合は、両者の面が形状の内側(内部)において接している場合である。この場合も、接続関係を切り替える。図11(3)の場合は、両者の面が形状の外側(外部)において接している場合である。この場合は、接続関係は切り替えずそのままとする。図11(4)は、両者の面が接し、かつ面の向きが同じとなる場合である。この場合も、接続関係は切り替えない。
【0072】
図12(1)、(2)は、面(3角形面)taとtbにおいて、同一平面となる部分がある場合である。このような場合は、taがtbに対して内部となる場合のみ、接続関係を切り替える。従って、図12(1)の場合のみ、切り替える。図12(2)の場合は、taがtbに対して外部となるので、接続関係は切り替えない。ここでは、内部となる場合を切り替えるとしたが、この基準をまったく逆にして、外部となる場合を切り替えるとしても何ら問題はない。
【0073】
また、図12(1)、(2)では、同一平面となる部分の面の向きが同じとなる場合を図示しているが、もちろん、面の向きが逆となる場合も存在する。しかし、このような場合は、「重なり3角形の検出除去処理」(同一平面かつ面の向きが逆)において、検出除去処理されるので、ここでは、対象外となる。
【0074】
[c2]最上位3角形の探索処理
最上位3角形とは、1つの立体(1つの閉じた境界面)において、その立体を構成する3角形の中で、Z座標値が最大となる頂点を持ち、かつ上面が存在しない3角形である。4次元同次座標系において、頂点Va=(Xa、Ya、Za、wa)のZ座標値がVb=(Xb、Yb、Zb、wb)より大きいとは以下の式(数12)が成り立つことである。
【0075】
【数12】
JP0003950976B2_000013t.gif
また、3角形F012が3角形F345に対して(Z座標軸に関して)上面となるとは、この2つの3角形F012とF345がZ座標軸方向からみて重なり、かつ3角形F012の3つの頂点V0=(X0、Y0、Z0、w0)、V1=(X1、Y1、Z1、w1)、V2=(X2、Y2、Z2、w2)において、以下の式(数13)が成り立つことである。ただし、3角形F012とF345は交差しないとする。
【0076】
【数13】
JP0003950976B2_000014t.gif

ここで、s0等は、下式(数14)で与えられる。
【0077】
【数14】
JP0003950976B2_000015t.gif

さらに、2つの3角形が、Z座標軸方向からみて、重なるかどうかの判定処理に関して説明する。4次元同次座標系(X、Y、Z、w)において、Z座標を無視した3次元同次座標系(X、Y、w)を想定する。この座標系における3角形の重なり判定処理に帰着することができる。この処理は、3角形の頂点と、方向を持った辺との位置関係判定処理(領域判定処理)に帰着する。
【0078】
最上位3角形を求める処理を、図13のフローチャートを用いて説明する。まず最上位頂点Vmaxに適当な初期値(例えば存在する頂点データ)を代入する(ステップ1300)。次に、処理対象となる1つの立体を構成する実3角形データを幾何データ記憶部02から順次読み出し、さらにその実3角形を構成する3つの頂点データv0i、v1i、v2iを幾何データ記憶部02から読み出し比較し、Z座標値が最大となる頂点データVを求める(ステップ1301)。
【0079】
次に、この頂点データVと最上位頂点データVmaxのZ座標値を比較する(ステップ1302)。Vが大きい場合は、Vmax=Vとする(ステップ1303)。以上の処理を、処理対象立体のすべての実3角形データに関して行う。以上の処理により、処理対象立体において、Z座標値が最大となる最上位頂点Vmaxが求まる。
【0080】
次に、最上位3角形Tmaxと基準3角形Tbaseに適当な初期値を代入する。例えば処理対象立体おいて、最上位頂点Vmaxを頂点に持つ適当な実3角形データを両者に代入する(ステップ1305)。そして、処理対象立体において、この最上位頂点Vmaxを頂点に持つ実3角形データtiを順次幾何データ記憶部02から取り出す(ステップ1306、1307)。
【0081】
次に、この3角形tiとTbaseがZ座標軸方向からみて重なるかどうかの判定を行う(ステップ1308)。重なる場合は、この3角形tiとTmaxがZ座標軸方向からみて重なるかどうかの判定を行う(ステップ1309)。重なる場合は、tiとTmaxの位置関係をチェックする(ステップ1310)。tiがTmaxの上面となる場合(Tmax<ti)はTmax=tiとする(ステップ1311)。以上の処理をすべての実3角形データtiに関して行う。これにより、最上位3角形Tmaxが求まる。
【0082】
[c3]最近傍上位立体を求める処理
ある立体biの最近傍上位立体bnearとは、以下の条件を満たす立体のことである(図15参照)。すなわち、最近傍上位立体とは、ある立体(1つの閉じた境界面)に、Z座標軸正方向に最も近い立体のことである。
(1)立体biの最上位頂点Vmax=(Xmax、Ymax、Zmax、wmax)にZ座標軸 と平行に正方向に立てた半直線と交差あるいは接する立体。
(2)この交点あるいは接点をVnear=(Xnear、Ynear、Znear、wnear)とすると 、Vnearは頂点Vmax=(Xmax、Ymax、Zmax、wmax)に最近傍となる立体。 ここで、Vnearを最近傍上位点と呼ぶことにする。
(3)Z座標軸方向から見て、立体biの最上位3角形Tmaxと重なる上面Tnea rを持つ立体。
(4)上記上面Tnearが複数個ある場合は、その中で最も下面となる面を持つ立体 。ここで、下面とは、3角形t2が3角形t3の上面となる場合、逆にt3はt2に 対して下面となる(図15参照)。また、この最も下面となる面Tnearを最近傍 上位3角形と呼ぶことにする。
【0083】
図15の例では、立体の断面図を示している。ここでは、立体biの最上位頂点はVmax=v0、最上位3角形はTmax=t1である。立体b(j+1)は、半直線Lと接し、かつ最近傍頂点v1を持つが、Tmaxと重なる面が存在しない。そこで、立体b(j+1)は、立体biの最近傍上位立体ではない。
【0084】
一方、立体bjは、半直線Lと接し、かつ(立体b(j+1)は対象外となるので)最近傍上位点(頂点)v2を持ち、かつ最上位3角形Tmaxと重なる面t3が存在する。そこで、立体bjが、立体biの最近傍上位立体となる。ここで、最上位3角形Tmaxと重なる面はt2とt3の2つが存在するが、両者を比較すると、t3がt2の下面となるので、t3が最近傍上位3角形Tnearとなる。
【0085】
最近傍上位立体を求める処理に関して、図14のフローチャートを用いて説明する。ここでは、立体biの最近傍上位立体bnearを求める。まず、立体biの最上位頂点Vmaxを通るZ座標軸と平行な直線Lを求める。そして、最近傍上位頂点Vnear等を初期設定する(ステップ1400)。例えば、Vnearには、Z座標値に適当な大きな値、X、Y、w座標値にVmaxと同じ値を代入しておけばよい。また、NULLは「値なし」(該当データなし)を意味する。
【0086】
次に、立体biとは異なる他の立体bjの実3角形データtjkを幾何データ記憶部02から順次読み込む(ステップ1402)。そして、このtjkと直線Lとの交点Vsが存在するかどうかを判定し、存在する場合はVsを求める(ステップ1403)。
【0087】
交点Vsが存在する場合は、VmaxとVsのZ座標値を比較する(ステップ1404)。VsのZ座標値がVmaxのZ座標値より小さい場合(Vs<Vmax)は、次の実3角形データに処理を移す。逆に、Vmax<=Vsとなる場合は、この3角形tjkとTmaxがZ座標軸方向からみて重なるかどうかの判定(ステップ1405)、および頂点データを比較して、tjkがTmaxの上面となるかどうか(Tmax<=tjk)の判定処理を行う(ステップ1406)。
【0088】
tjkとTmaxがZ座標軸方向からみて重なり、かつtjkがTmaxの上面となる場合(Tmax<=tjk)は、VsとVnearを比較する(ステップ1407)。Vnear<Vsとなる場合は、次の実3角形データに処理を移す。Vs<Vnearとなる場合はステップ1410に処理を進める。
【0089】
Vs=Vnearとなる場合は、3角形tjkとTnearがZ座標軸方向からみて重なるかどうかの判定(ステップ1408)、および頂点データを比較して、tjkがTnearの下面となるかどうか(tjk<=Tnear)の判定処理を行う(ステップ1409)。
【0090】
tjkとTnearがZ座標軸方向からみて重なり、かつtjkがTnearの下面となる場合(tjk<=Tnear)は、Vnear=Vs、Tnear=tjk、bnear=bjとする(ステップ1410)。
【0091】
以上の処理を、立体bi以外のすべての実3角形データに関して行う。以上の処理により、立体biの最近傍上位立体bnear、最近傍上位頂点Vnear、最近傍上位3角形Tnearが求まる。
【0092】
[c4]最近傍上位立体順に立体データのソーティング
最近傍上位立体順に立体データbiをソーティング処理するとは、立体データ(幾何データの集合体(実3角形データまたはゼロ3角形データの集合体))biとbj(i<j)において、biの最近傍上位立体bnearがbjとなる場合は、両者のデータの順番を入れ替えることである。すなわち、ここではbiがbjよりもデータの先頭にある(i<j)ので、biとbjのデータ順を入れ替え、bjがbiよりもデータの先頭となるようにする。
【0093】
この処理により、ある立体biの最近傍上位立体データbnearは、必ず立体データbiよりも上位となる(先頭となる)。図15の例では、立体データの順番は上位から、b(j+2)、bj、b(j+1)、biの順番となる。
【0094】
[c5]面の向きによる立体の消去処理
面の向きによる立体の消去処理とは、ある立体の面の表裏が最近傍上位立体との関係で矛盾する場合は、この矛盾する立体データの消去を行う処理である。
【0095】
図17を用いて、面の向きと矛盾立体との関係を説明する。図17は立体の断面図を表している。また、ハッチングのある側が立体(形状)の内部、ない側が立体の外部を表現している。言い換えれば、矢印の向きが立体の内部を表している。
【0096】
図17(1)および(2)の場合は、立体Aにおいて、最近傍上位立体がない場合である。このような場合は、立体Aの最上位面(最上位3角形)のZ軸方向の向きを用いて判定を行う。図17では、立体Aにおける矢印はすべて、立体Aの最上位3角形(面)のZ軸方向の向きを表している。
【0097】
図17(1)では、立体Aの最上位3角形のZ軸方向の向きはマイナスとなっている。このような場合は、立体Aは矛盾立体ではないので、消去されない。一方、図17(2)では、立体Aの最上位3角形のZ軸方向の向きはプラスとなっている。このような場合は、立体Aは矛盾立体となる(空間全体に立体の内部が広がっている)ので、消去される。
【0098】
図17(3)~(6)の場合は、立体Aの最近傍上位立体が存在する場合である。ここでは、立体Bが立体Aの最近傍上位立体となる。また、立体Bにおける矢印はすべて、立体Aに対する最近傍上位3角形(面)のZ軸方向の向きを表している。
【0099】
図17(3)~(6)の場合は、立体Aの最上位3角形と、立体Aに対する(立体Bに属する)最近傍上位3角形のZ軸方向の向きの組み合わせをチェックする。図17(3)と(6)に示すように、両者のZ軸方向の向きが逆となる場合は、立体Aは立体Bに対して「無矛盾立体」となる。そこで、このような場合は、立体Aは消去されない。
【0100】
一方、図17(4)と(5)の場合は、両者のZ軸方向の向きが同じとなる。このような場合は、立体Aは立体Bに対して「矛盾立体」となる。そこで、このような場合は、立体Aは消去される。
【0101】
次に、面の向きによる立体の消去処理に関して、図16のフローチャートを用いて説明する。ここでは、立体データbiの幾何矛盾チェックを、データ順に(データの先頭から)行う。まず、初期処理として、すべての立体データの消去フラグをすべてOFFとする(ステップ1600)。ここで、OFFは消去しない(無矛盾立体である)を意味する。そして、立体b=biとする(ステップ1601)。次に、立体bの最近傍上位立体bnearが存在するかをチェックする(ステップ1602)。
【0102】
存在しない場合は、立体biの最上位3角形TmaxのZ座標軸方向の向きをチェックする(ステップ1603)。正の場合は幾何矛盾となるので、立体データbiの消去フラグをON(消去を意味する)とする(ステップ1607)。負の場合は幾何矛盾とならないので、立体データbiの消去フラグをOFFのままとする。ここでの処理は、図17(1)と(2)の場合に対応している。
【0103】
立体bの最近傍上位立体bnearが存在する場合は、bnearの消去フラグがONかOFFかのチェックを行う(ステップ1604)。消去フラグがONの場合は、この最近傍上位立体bnearは矛盾立体であり消去されるので、b=bnearとし(ステップ1605)、さらに上位の消去フラグがOFFとなっている無矛盾立体である最近傍上位立体を探す。
【0104】
消去フラグがOFFとなっている最近傍上位立体bnearが存在する場合は、このbnearの最近傍上位3角形Tnearと、立体biの最上位3角形TmaxのZ座標軸方向の向きの組み合わせをチェックする(ステップ1606)。TnearとTmaxのZ座標軸方向の面の向きの組み合わせが同じとなる場合は(図17(4)と(5)の場合)、立体biは矛盾立体となるので、立体biの消去フラグをONとする(ステップ1607)。面の向きの組み合わせが逆となる場合は(図17(3)と(6)の場合)、立体biは矛盾しないので、消去フラグはOFFのままとする。そして、次の立体に処理を移す。以上の処理を、すべての立体データに関して行うことにより、すべての立体の幾何矛盾チェックが完了し、その結果として、消去フラグの値(ONまたはOFF)が確定する。
【0105】
最後に、消去フラグがONとなっているすべての立体データを幾何データ記憶部02から消去する(ステップ1609)。これにより、すべての矛盾立体が消去され、無矛盾立体だけが保存される。
【0106】
以上に詳述したように、本実施形態の3次元幾何データ処理システムSSによれば、3次元幾何図形の表面データである境界面データを、3角形面データまたは3角形の3つの頂点が同一直線上となるゼロ3角形データにより構成し処理する3角形/ゼロ3角形データ処理部07と、前記3次元幾何データの数値を必要精度に応じて任意に切り捨てる数値データ切り捨て処理部08と、前記数値データ切り捨て処理部08により、発生する幾何矛盾を検出し除去する幾何無矛盾化処理部09とを具備しているので、3次元幾何図形の表面データである境界面データを、3角形面データまたは3角形の3つの頂点が同一直線上となるゼロ3角形データにより構成し処理し、特に、ゼロ3角形データ形式を用いた幾何処理により、不必要な桁数の増大および不必要なデータ量の増大を抑制することができ、また、3次元幾何データを構成する頂点データの座標値データ等を必要精度に応じて切り捨てを行い、数値桁数の増大に対処することができ、さらに、座標値データ等の切り捨て処理により、発生する幾何矛盾を検出し除去することができるので、効果的に、3次元幾何データにおける幾何矛盾を検出し除去することができる。すなわち、無矛盾な誤りのない3次元幾何データを生成することができる。
【0107】
また、前記幾何無矛盾化処理部09が、縮退3角形を検出し除去する縮退3角形処理部10、重なり3角形を検出し除去する重なり3角形処理部11、および自己干渉立体等を検出し除去する矛盾立体処理部12を含むようにしているので、幾何学的な矛盾にすべて対応することができる。
【0108】
特に、縮退3角形処理部10によって、2頂点が同一点となるいびつな3角形、3頂点が同一点となるいびつな3角形、および3頂点が同一直線上となるいびつな3角形を、検出し除去することが確実にできる。
【0109】
また、重なり3角形処理部11によって、3角形面が重なっていると判定された3角形に対してその重なりを除去することを確実に行える。
【0110】
また、矛盾立体処理部12が、自己干渉立体の分離処理と、立体の最上位3角形の探索処理と、立体の最近傍上位立体の探索処理と、最近傍上位立体順に立体データのソーティングを行う処理と、面の向きによる立体の消去処理とを行うように構成しているので、立体に矛盾のあるものを、確実に除去することができる。
【0111】
加えて、各処理部において、4次元同次座標系処理と可変長ビットの演算を用いて無誤差演算を行うようにしているので、演算を何回実行してもその演算に破綻が生じず、システムを安定して作動させることができる。
【0112】
なお、本発明は、以上に詳述した実施形態に限られるものではない。
【0113】
例えば、本実施形態では、3次元幾何データ処理システムSSを、スタンドアローン型で動作させているが、インターネット等の通信回線網を介して接続される端末装置およびサーバ装置からなるものとしてもよい。
【0114】
その他、各部の具体的構成についても上記実施形態に限られるものではなく、本発明の趣旨を逸脱しない範囲で種々変形が可能である。
【図面の簡単な説明】
【0115】
【図1】本発明の一実施形態における3次元幾何データの無矛盾化処理システムの機能構成図。
【図2】同実施形態における従来と本発明の形状表現法の違いを示す図。
【図3】同実施形態におけるデータ構造を示す図。
【図4】同実施形態における幾何無矛盾化処理の全体フローを示す図。
【図5】同実施形態における縮退3角形およびその除去処理に関する説明図。
【図6】同実施形態における縮退3角形の検出除去処理のフローチャート。
【図7】同実施形態における重なり3角形の検出除去処理のフローチャート。
【図8】同実施形態における重なり3角形の検出除去処理に関する説明図。
【図9】同実施形態における自己干渉立体の分離処理のフローチャート。
【図10】同実施形態における自己干渉立体の分離処理に関する説明図。
【図11】同実施形態における自己干渉立体の面の交差パターンに関する説明図。
【図12】同実施形態における自己干渉立体の面の交差パターンに関する説明図。
【図13】同実施形態における立体の最上位3角形探索処理のフローチャート。
【図14】同実施形態における最近傍上位立体探索処理のフローチャート。
【図15】同実施形態における最近傍上位立体に関する説明図。
【図16】同実施形態における幾何矛盾立体の消去処理のフローチャート。
【図17】同実施形態における幾何矛盾立体に関する説明図。
【図18】同実施形態における3次元幾何データの無矛盾化処理システムの機器構成図。
【符号の説明】
【0116】
SS・・・3次元幾何データの無矛盾化システム(3次元幾何データ処理システム)
07・・・3角形/ゼロ3角形データ処理部
08・・・数値データ切り捨て処理部
09・・・幾何無矛盾化処理部
10・・・縮退3角形処理部
11・・・重なり3角形処理部
12・・・矛盾立体処理部
図面
【図1】
0
【図2】
1
【図3】
2
【図4】
3
【図5】
4
【図6】
5
【図7】
6
【図8】
7
【図9】
8
【図10】
9
【図11】
10
【図12】
11
【図13】
12
【図14】
13
【図15】
14
【図16】
15
【図17】
16
【図18】
17