JP3018151B2 - ３次元図形データの演算処理方法及びその装置 - Google Patents

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、３次元図形データ
の演算処理方法及びその装置に関する。

【０００２】

【従来の技術】３次元図形データの処理において、これ
までに実用化され広く使われている方法は、多角形面デ
ータを用いる処理方法である。多角形面データ処理で
は、例えば図19の(a)に示すような３次元図形30を表現
しかつ処理するために、図19の(b)に示すように複数の
多角形面を用いて図形３０を表現する。そしてこれらの
多角形面の多角形面データに基づいて、３次元図形の形
状演算処理が行われる。

【０００３】

【発明が解決しようとする課題】このような多角形面デ
ータ処理では様々な形状の多角形面を表現しかつ処理す
ることが必要となる。従って図20に示すように、多角形
面データ（e₀, e₁ --- e_n）のデータ長が辺データや頂
点データなど他のデータのデータ長に比べて長くなる。
すなわちデータ構造が可変長となり計算機処理効率が悪
くなる。また、任意な形状の多角形面の処理において
は、穴や凹多角形面等の処理が必要となるため処理方式
が複雑になる。例えば、図19の(b)の面31には穴が存在
する。このような場合は、仮想切断線32を用いて面31を
１つの凹多角形面にする処理が行われる。そして更に、
この凹多角形面31を４個の凸多角形面３２Ａに分割する
処理が行われる。このような処理は、多くの穴や複雑な
凹多角形面が存在する場合は非常に複雑な処理となり、
その演算処理量も多くなる。結果として、多角形面デー
タ処理はその処理系も大規模なものとなり、高い信頼性
が得られにくく、処理速度も遅いといった問題点があっ
た。

【０００４】一方、図2の(a)のように、多角形面データ
の代わりに三角形面データのみを用いると、そのデータ
構造および処理は必然的に単純になる。多角形面データ
処理において問題となった凹多角形面や穴の処理は不要
となる。しかし、三角形面データの数が増加するので形
状演算の処理過程でデータ量の大幅な増大を招き処理効
率が悪くなる。結果として処理速度も遅くなる。従っ
て、三角形面データのみを用いる図形処理方法はこれま
でに実用化されていない。

【０００５】本発明は、３次元図形の形状演算処理にお
いて、三角形面データを用いる処理の優れた特徴である
単純な処理および単純なデータ構造を損なうことなく、
三角形面データを用いる高効率かつ高速な処理方法及び
処理装置を提供することを目的とするものである。

【０００６】

【課題を解決するための手段】上記課題を解決するため
に、本発明では三角形面データ処理に「３点線分デー
タ」と称するデータ形式、および「交線データ」を用い
る。３点線分は、両端点（２点）で定義される通常の線
分に対して、両端点の他に線分上に、隣接する三角形面
の頂点を共有しているもう１つの点を有する線分として
定義される。

【０００７】この３点線分は３つの点のデータを有する
３点線分データによって表現される。３点線分データを
用いて三角形面データ処理を行うことにより、不必要な
三角形分割が抑制されるので、三角形面データ量の増大
を抑制することができる。

【０００８】また、交線データは三角形相互の交差分割
情報を保持する。これにより交線において接する三角形
を探索する処理等が不要となるので、三角形面間の接続
処理等が効率化される。このように、３点線分データお
よび交線データを併用して形状演算を行うことにより、
データ量および演算量の増大を抑制することができる。
従って本発明の形状演算処理方式は高効率かつ高速な処
理が実現できる。さらに、上記の方式と、画像・図形処
理においてよく用いられる空間分割法とを融合し、分割
された部分空間外の三角形面データ、および新たに生成
されたものを含むすべての３点線分データを分割処理の
対象外とすることにより、さらに高効率かつ高速な形状
演算方式を実現している。

【０００９】

【発明の実施の形態】本発明の３次元データの演算処理
装置は、対話表示部から入力された３次元図形の図形デ
ータを、図形入力処理部によりデータ変換処理を行い、
データ演算処理部において前記３次元図形の形状演算処
理を行い、図形出力処理部において前記３次元図形の表
示図形データを生成して、対話表示部に表示するととも
に、これらの処理過程で生成されかつ処理された図形デ
ータをデータ記憶部に記憶させる３次元図形データ処理
システムにおいて、入力された３次元図形の表面である
境界面のデータから、各境界面を三角形面に分割して三
角形面データを生成するとともに、隣接する三角形面の
境界に、境界上の線分の両端点と線分上にある前記隣接
する三角形面の１つの頂点から構成される３点線分を介
在させる。そして三角形面データおよびこの３点線分を
表す３点線分データを生成する図形入力処理部と、前記
三角形面及び前記３点線分によって境界面が構成される
複数の３次元図形の形状演算を前記三角形面データ及び
前記３点線分データを用いて行うデータ演算処理部とを
有する。

【００１０】また、入力された３次元図形の表面である
境界面のデータから、各境界面を三角形面に分割して三
角形面データを生成しデータ記憶部に記憶させるととも
に、隣接する三角形面の境界に、境界上の線分の両端点
と線分上にある前記隣接する三角形面の１つの頂点から
構成される３点線分を介在させる。そしてこの３点線分
を表す３点線分データを生成し前記データ記憶部に記憶
させる図形入力処理部を有し、前記三角形面データおよ
び前記３点線分データとによって境界面が構成される２
つの３次元図形において、前記２つの３次元図形が共に
存在する共通空間を求め、この共通空間内に存在する両
図形の三角形面データを前記データ記憶部からそれぞれ
取り出す第１の処理部を有する。取り出された図形の三
角形面データ間において交差判定を順次行い、交わる場
合は両者の交線を求めて、その交線に基づいて、三角形
面を、三角形面とそれに隣接する三角形面の境界に介在
する３点線分との集合体に分割し、前記交線を表す交線
データ、前記三角形面を表す三角形面データ、及び前記
３点線分を表す３点線分データを生成し、これらのデー
タを前記データ記憶部に記憶する第２の処理部を有す
る。さらに前記各三角形面データ及び３点線分データに
おいて、他方の図形に包含されているかどうかの内外判
定を行い、その結果に応じて三角形面データ及び３点線
分データを前記データ記憶部から消去する第３の処理部
と、交線において隣接する両図形の三角形面データ及び
３点線分データを、３点線分データを用いて接続する第
４の処理部と、三角形面データまたは３点線分データと
これに隣接する三角形面または３点線分が形成する図形
が三角形面あるいは３点線分を形成する場合は、三角形
面データ及び３点線分データの統合を行第５の処理部と
を有する。さらに三角形面データ及び３点線分データに
より境界面が構成される３次元図形の隠線処理及び隠面
処理を、三角形面データ及び３点線分データを用いて行
い表示図形データを生成する図形出力処理部とを有し、
上記の処理ステップにおいて、生成されかつ処理される
三角形面データ、３点線分データ、交線データ、および
頂点データをすべて固定長データ構造の形式でそれぞれ
記憶する、三角形面データの記憶部と、３点線分データ
の記憶部と、交線データの記憶部と、頂点データの記憶
部とを備えている。

【００１１】さらに、前記三角形面データ及び前記３点
線分データによって境界面が構成される２つの３次元図
形において、前記２つの３次元図形が共に存在する共通
空間を求め、この共通空間内に存在する両図形の三角形
面データを前記データ記憶部から取り出す第１の処理部
と、前記共通空間をさらに細分し部分空間を生成し、前
記取り出された両図形の三角形面データから、前記部分
空間に一部または全部が含まれる三角形面データ群をそ
れぞれ取り出す第６の処理部と、この取り出された両図
形の三角形面データ間において交差判定を順次行い、交
差する場合は両者の交線を求めて、その交線に基づい
て、三角形面を、三角形面と、それに隣接する三角形面
との境界に介在する３点線分との集合体に分割し、前記
交線を表す交線データ、前記三角形面を表す三角形面デ
ータ、及び３点線分を表す３点線分データを生成し、こ
れらのデータを前記データ記憶部に記憶する第２の処理
部とを備えている。

【００１２】本発明の３次元図形データ演算処理方法
は、対話表示部から入力された３次元図形の図形データ
のデータ変換処理及び前記３次元図形の形状演算処理を
行い、前記３次元図形の表示図形データを生成して、対
話表示部に表示するとともに、これらの処理過程で生成
されかつ処理された図形データをデータ記憶部に記憶さ
せる３次元図形データ処理システムにおいて、入力され
た３次元図形の表面である境界面のデータから、各境界
面を三角形面に分割して三角形面データを生成するとと
もに、隣接する三角形面の境界に、境界上の線分の両端
点と前記線分上にある前記隣接する三角形面の１つの頂
点から構成される３点線分を介在させる。そして、この
３点線分を表す３点線分データを生成し、前記三角形面
及び前記３点線分によって境界面が構成される複数の３
次元図形の形状演算を前記三角形面データ及び前記３点
線分データを用いて行う。

【００１３】また、入力された３次元図形の表面である
境界面のデータから、各境界面を三角形面に分割して三
角形面データを生成するとともに、隣接する三角形面の
境界に、境界上の線分の両端点と線分上にある前記隣接
する三角形面の１つの頂点から構成される３点線分を介
在させ、この３点線分を表す３点線分データを生成す
る。そして前記三角形面及び前記３点線分によって境界
面が構成される２つの３次元図形において、前記２つの
３次元図形が共に存在する共通空間を求め、この共通空
間内に存在する両図形の三角形面データ間において交差
判定を順次行い、交差する場合は両者の交線を求めて、
その交線に基づいて、三角形面を、三角形面とそれに隣
接する三角形面との境界に介在する３点線分との集合体
に分割し、前記交線を表す交線データ、前記三角形面を
表す三角形面データ、及び前記３点線分を表す３点線分
データを生成する。次に前記各三角形面データ及び３点
線分データにおいて、図形に包含されているかどうかの
内外判定を行い、その結果に応じて三角形面データ及び
３点線分データを消去し、交線において隣接する両図形
の三角形面データ及び３点線分データを、３点線分デー
タを用いて接続する。さらに三角形面データまたは３点
線分データとこれに隣接する三角形面または３点線分と
が形成する図形が三角形面あるいは３点線分を形成する
場合は、三角形面データ及び３点線分データの統合を行
なう。そして三形面データ及び３点線分データにより境
界面が構成される３次元図形の隠線処理及び隠面処理
を、三角形面データ及び３点線分データを用いて行い表
示図形データを生成する。上記の処理において、生成及
び処理される三角形面データ、３点線分データ、交線デ
ータ、および頂点データをすべて固定長データ構造の形
式で記憶させる。

【００１４】さらに、前記三角形面データ及び前記３点
線分データによって境界面が構成される２つの３次元図
形において、前記２つの３次元図形が共に存在する共通
空間を求め、この共通空間内に存在する両図形の三角形
面データを取り出すとともに、前記共通空間をさらに細
分して部分空間を生成し、前記取り出された両図形の三
角形面データから、前記部分空間に一部または全部が含
まれる三角形面データ群をそれぞれ取り出す。この取り
出された両図形の三角形面データ間において交差判定を
順次行い、交差する場合は両者の交線を求める。そして
その交線に基づいて、三角形面を、三角形面と、それに
隣接する三角形面との境界に介在する３点線分との集合
体に分割し、前記交線を表す交線データ、前記三角形面
を表す三角形面データ、及び３点線分を表す３点線分デ
ータを生成する。

【００１５】［実施例］まず、本発明の根幹をなす「３
点線分データ」のデータ構造について説明する。図4の
(d)に示す斜線部で示した三角形L₁は３つの頂点V₁, V₃,
V₆を有している、また隣接する斜線部で示した三角形L
₂は３つの頂点 V₆, V₃, V₄を有している。本発明の実施
例の参照図において、前記の三角形L₁、L₂のような斜線
を施した三角形は仮想上の三角形を表している。この仮
想上の三角形は、その３つの頂点が同一直線上となる。
すなわち、両端点以外にその直線上にもう１点を持つ線
分となる。この線分を「３点線分」と称する。仮想上の
三角形L₁、L₂において、点V₁, V₆, V₄, V₃はすべて同一
直線上にあるが、３点線分上の各点を分かりやすくする
ためにずらして図示した結果仮想上の三角形が形成され
ている。以後仮想上の三角形L₁、L₂で表される線分を単
に３点線分L₁、L₂と呼ぶことにする。

【００１６】３点線分は三角形が完全につぶれた「線形
の三角形」とみなすことができる。そこで、３点線分は
３点を持つと共に同一直線上に３線分（仮想上の三角形
では３つの辺となる）を持つ。例えば、図4(d)に示す３
点線分L₁は、３点V₁, V₃, V₆を持ち、かつ３線分（辺）
V₁V₃, V₁V₆, V₃V₆を持つ。３点線分は３点のデータを含
む「３点線分データ」によって表される。以後、三角形
の面を三角形面と呼び、３点線分データを用いた三角形
面のデータ処理を「３点線分データ処理」と呼ぶ。また
従来の通常の三角形面に基づくデータ処理を「通常三角
形面データ処理」と呼ぶことにする。

【００１７】３点線分データ処理のデータ構造は、図3
の(a)に示すように、三角形面データ、３点線分デー
タ、交線データおよび頂点データから構成される。三角
形面データおよび３点線分データはデータ構造上は全く
同じ形式となり、３つの頂点データへのポインタ(v₀, v
₁, v₂)、３つの隣接する三角形面データあるいは３点線
分データへのポインタ(t₀, t₁, t₂)から構成される。こ
こで、ポインタとは、記憶装置（メモリ）上においてそ
のデータが格納されている番地（アドレス）を示すデー
タである。

【００１８】交線データは、両端点（頂点）データへの
ポインタ(v₀, v₁)、交線を挟んで隣接する２つの三角形
面データあるいは３点線分データへのポインタ(t₀,
t₁)、重なり合う交線データへのポインタsから構成され
る。頂点データは、頂点の座標値(x, y, z)から構成さ
れる。このように、本実施例のすべてのデータは、固定
長の１次元リスト構造という最も単純で電子計算機によ
る効率的処理に最も適合したデータ形式となる。

【００１９】《３点線分データのデータ形式》図4の例
を用いて、３点線分データ形式を具体的に説明する。図
4の(a)の多角形面50を、最小の個数の三角形面を用いて
表現すると、図4の(b)のように２つの三角形面T₁とT₂で
表現することができる。しかし、これでは三角形面T₁と
T₂の接続関係（頂点V₁, V₆, V₄, V₃）をデータ上に簡単
に表現できない。そこで従来の方法では図4の(c)のよう
に、隣接する三角形面は必ずその２頂点を共有するかた
ちで表現される。すなわち面50は三角形面T₁, T₂, T₃及
びT₄で表現される。このような表現形式をとることによ
り、隣接する三角形面は必ず辺を挟んで１対１に対応す
る。この方法により、図4の(c)の場合の三角形面データ
および頂点データは図3の(b)に示すようになる。非常に
単純な固定長データ構造で複数の三角形面の間の接続情
報を保持することができる。しかしながら、この方法で
は、三角形面データ（三角形面）の数が増えてしまい、
結果として処理効率が悪くなる。図4の多角形面50の場
合では、図4の(b)の２個から図4の(c)の４個と倍増して
しまう。

【００２０】本実施例の特徴は、三角形面データの数を
最小にしたままで、三角形面の接続関係を「固定長デー
タ形式」で表現できる「３点線分データ形式」を用いる
点にある。図4の(b)のように分割した場合には、図4の
(d)に示すように、三角形面T₁とT₂の間に２つの３点線
分L₁とL₂を挿入して両三角形面T₁とT₂間に介在させる。
その結果すべての三角形面T₁,T₂および３点線分L₁,L₂は
必ず２頂点を共有するかたちで互いに隣接する。３点線
分を介在させる図形の表現を「３点線分表現」と呼ぶこ
とにする。

【００２１】３点線分処理のデータ形式の１例を図3の
(c)に示す。図3の(c)に示すように、３点線分L₁,L₂のデ
ータを用いることにより、三角形面データの数は三角形
面T₁,T₂に対応する２個のデータとなる。従ってデータ
の数を最少に保ちつつ三角形面の結合情報を固定長のデ
ータ形式で保持できる。例えば、図4の(d)において、三
角形面T₁に隣接する三角形面を探索する場合、図3の(c)
に示すように、三角形面T₁→３点線分L₁→３点線分L₂→
三角形面T₂の順序でそれぞれのデータをたどることによ
り、三角形面T₁に隣接する三角形面T₂を求めることがで
きる。この３点線分データ処理方式では、図4の(e)に示
すような辺V₁V₃を挟んで隣接する三角形面が１対１に対
応しない場合などの種々のケースに対しても、三角形面
の結合情報を固定長データ形式で保持することができ
る。

【００２２】例えば、従来の技術の項で挙げた図19の
(a)の図形30を３点線分表現で表すと、図2の(a)のよう
になる。図2の(b)は通常三角形面で表現したものであ
る。両図の比較から明らかなように図3の(a)の３点線分
表現の方が図3の(b)の通常三角形面表現よりもはるかに
少ない数の三角形面のデータで図形を表現しかつ処理で
きることが分かる。以上のように３点線分データを用い
ると、三角形面データの数を最少に保ちつつ、各三角形
面の隣接情報を保持することができる。また、３点線分
データは固定長のデータ形式となるので処理効率が非常
によい。このことが本実施例の重要な特徴である。

【００２３】［３点線分データの処理］次に、図５を参
照して３点線分データを用いた処理の利点について、３
点線分データを用いない通常三角形面処理の場合と対比
しつつ詳細に説明する。図5の(a)の例では、多角形の面
50が２つの三角形面T₁,T₂と２つの３点線分L₁,L₂を用い
て表現されている。面50は４本の交線51, 52, 53及び54
において他の面（三角形面）と交わっており、交線51,
52, 53, 54の順に面50の三角形面分割が行われるものと
する。

【００２４】３本の交線51, 52, 53による３点線分を用
いた三角形面分割の結果をそれぞれ図5の(b),(c),(d)に
示す。まず、交線51による分割について詳細に説明す
る。図5の(a)において、交線51を下方に延長して３点線
分L₂と交差させる。その結果、図5の(b)に示すように三
角形面T₂は３個の三角形面T₄, T₅, T₆に分割され、３点
線分L₃を介して３点線分L₂に接続される。次に交線52に
よって分割すると、図5の(c)に示すように、三角形面T₄
は３個の三角形面T₇, T₈, T₉に分割され、３点線分L₄を
介して三角形面T₅に接続される。最後に、三角形面T₁を
交線53により分割すると、図5の(d)に示すように、三角
形面T₁は三角形面T₁₀, T₁₁, T₁₂に分割される。その結
果面50は８個の三角形面T₅, T₆, T₇, T₈, T₉, T₁₀,
T₁₁, T₁₂に分割される。

【００２５】一方、図5の(a)の面50を三角形面のみで表
現すると図5の(e)に示すようになる。次に図5の(e)の各
三角形面を交線51、52、53について三角形面のみを用いて
分割すると図5の(f)に示すようになる。図5の(d)と(f)
のそれぞれの分割結果を比較すると、三角形面の総数
は、図5の(d)の３点線分処理では8個であるのに対し
て、図5の(f)の通常三角形面処理では18個となってい
る。両者にこのような差が生じるのは、３点線分処理で
は、隣接する三角形面間に介在する３点線分により周辺
の三角形面への三角形面分割の波及を防ぐことができる
からであり、結果として三角形面の分割数により新たに
生成される三角形面の数を大幅に減らすことができる。

【００２６】形状演算などにおいて、三角形面を分割す
る処理は全体の処理量のかなりの部分を占める。図5の
(d)に示す３点線分表現において面50と交線54との交差
判定をする場合、３点線分処理では８個の三角形面との
交差判定のみをすればよい。これに対して、図5の(f)の
三角形面のみの表現における処理では、18個のすべての
三角形面との交差判定が必要となる。さらに、分割処理
が行われる三角形面は、図5の(d)の３点線分処理ではた
った１個であるのに対し、図5の(f)の通常三角形面処理
では４個となる。そして、通常、形状演算ではこれらの
処理が繰り返されるために、両者のデータ量および演算
量の差は指数関数的に大幅に増大する。

【００２７】上記のように、３点線分処理は、従来の三
角形面処理の利点である固定長データ構造および処理の
単純性を維持しつつ、データ量及び演算量が多いという
従来の処理の欠点を解消することができる。従って３点
線分処理方式は、従来の方法である通常三角形面処理お
よび多角形面処理に比べて、高効率かつ高速な処理が実
現できる。

【００２８】《第１実施例》本発明の第１実施例につい
て図1ないし図14を参照して詳細に説明する。本発明の
３次元データの演算処理装置は、図1に示すように、図
形入力処理部02、データ演算処理部としての三角形面デ
ータ処理部03及び図形出力処理部04から成る中央処理装
置100、対話表示部01、およびデータ記憶部としてのデ
ータ記憶装置05を備えている。対話表示部01は、例えば
グラフィックディスプレイ、キーボード、マウスなどか
ら構成され、マン・マシンインターフェイスおよび３次
元図形の入力と図形の表示を行う。

【００２９】図形入力処理部02では、図形データ作成装
置としての対話表示部01により入力された立方体、直方
体、円柱、円錐、球などの３次元基本図形（以下、プリ
ミティブと呼ぶ）データに基づいて、３次元基本図形の
境界面（表面）が三角形面に分割され、三角形面データ
と３点線分データに変換される。そして、生成された三
角形面データ、３点線分データおよびその頂点の座標を
表す頂点データは、それぞれ三角形面データ記憶部11、
３点線分データ記憶部12おおよび頂点データ記憶部14に
保存される。また、図形入力処理部02では、３次元図形
のプリミティブによる入力定義以外の方法も用いられ
る。例えば、三角形面および３点線分で構成された２次
元断面図形を基にして、平行移動（スイープ）あるいは
回転することにより３次元図形を生成し、これにより生
成された三角形面データ、３点線分データおよび頂点デ
ータがそれぞれの記憶部11,12,14に記憶される。

【００３０】三角形面データ処理部03では、三角形面デ
ータおよび３点線分データで表現された３次元図形の形
状演算、すなわち形状和（足し算）、形状差（引き算）
および形状積（重なる部分を求めること）が「３点線分
データ」を用いて行われる。

【００３１】図形出力処理部04では、三角形面データ処
理部03において生成されかつ演算された三角形面データ
および３点線分データで構成された３次元図形の隠線あ
るいは隠面処理がなされ、表示図形及び画像が生成され
る。そして、この生成された表示図形及び画像は、対話
表示部01のグラフィックディスプレイ(CRT) に表示され
る。

【００３２】また、データ記憶部05は、三角形面データ
記憶部11、３点線分データ記憶部12、交線データ記憶部
13および頂点データ記憶部14から構成される。これらの
記憶部に記憶されるデータはすべて、固定長の非常に単
純な構造であるので高効率かつ高速に記憶されかつ処理
される。

【００３３】次に、第１実施例の根幹をなす三角形面デ
ータ処理部03およびデータ記憶部05について詳細に説明
する。三角形面データ処理部03では形状演算処理が行わ
れる。まず、本発明の形状演算処理方式の概要を図17を
用いて説明する。ここでは、図17の(a)に示すように３
次元図形である形状αと形状βの形状和をとる場合を想
定する。本実施例では、形状αおよび形状βなどの３次
元図形はすべて、三角形面データおよび３点線分データ
を用いて構成される。

【００３４】まず、図17の(b)に示すように、形状αと
形状βが共に存在する共通空間Ｑ（直方体空間）を求め
る。この共通空間Ｑが存在しない場合は以後のすべての
処理は行われず終了となる。共通空間Qが存在する場合
には、この共通空間に含まれる形状αおよび形状βの三
角形面データが第１の処理部としての共通空間処理部06
で処理されてそれぞれ三角形面データ記憶部11から順次
取り出される。

【００３５】次に、図17の(c)に示すように、互いに交
差する面の分割処理が行われる。すなわち、上記の共通
空間処理により取り出された形状αおよび形状βの三角
形面データ間において、交差判定が順次行なわれる。そ
して、両者が交わる場合はその交線を生成し、その交線
においてそれぞれの三角形面が第２の処理部としての分
割処理部07により三角形面と３点線分に分割される。三
角形面の分割において３点線分を用いることにより、新
たに生成される三角形面（三角形面データ）の数が抑制
される。

【００３６】次に、図17の(d)に示すように、第３の処
理部としての消去処理部08により他の形状の内部となる
三角形面データおよび３点線分データが消去される。

【００３７】さらに、図17の(e)に示すように、形状α
および形状βの面を交線において接続する（境界面接続
処理）。すなわち、交線において接する形状αと形状β
の三角形面あるいは３点線分の対が３点線分を用いて第
４の処理部としての接続処理部09により接続される。３
点線分を用いることにより、この接続処理は単純化かつ
効率化される。

【００３８】最後に、図17の(f)に示すように、三角形
面および３点線分の統合を行う。図17の(f)の面190のよ
うに三角形面分割が行われた面は、必要以上の数の三角
形面および３点線分から面が構成されている。そこで、
図17の(f)の面191に示すように、第５の処理部としての
統合処理部10により三角形面および３点線分の統合処理
を行い、三角形面データおよび３点線分データの数を最
少にする処理を行う。なお、この処理は必ずしも行う必
要はない。以上が形状和の演算処理の概要である。

【００３９】以下に、３次元図形である形状αと形状β
の形状和をとる場合すなわち交差処理を詳細に説明す
る。形状αの１つの三角形面ABCと形状βの１つの三角
形面DEFとの交差処理パターンは、図6の(a),(b),(c)に
示す３通りとなる。

【００４０】すなわち、 (a) 交線56が三角形面ABCの２辺と交わる。 (b) 交線56が三角形面ABCの１辺および頂点と交わる。 (c) 交線56が三角形面ABCの１辺と一致する。

【００４１】図6の(a)では、形状αの三角形面ABCと形
状βの三角形面DEFが交線56で交わっている。この場
合、図6の(a'), (a'')に示すように三角形面が分割さ
れ、同時に形状α側の交線GHと形状β側の交線IJが生成
される。そして、この両交線GH,IJは重なり合う。これ
らの交線GH,IJに対応した交線データが生成される。両
交線データ（ここでは、GHとIJ）における「重なる交線
へのポインタs」には互に他方の交線のデータのアドレ
スが保持される。このことを以後「ポインタsは互いに
他を示し合う」と記載する。

【００４２】図6の(a)の点G,H、(b)の点Kのように、交
線の端点が三角形面の辺上となる場合は以下のような処
理が行われる。図7の(a)の例を用いて説明する。この例
では交線GHの端点Gは三角形面ABCの辺AB上にある。この
場合、３点線分ABGが生成されて三角形面ABCが分割され
る。辺AB上にすでに交線KLが存在し、交線GHと交線KLが
交差する場合は、図7の(b)に示すように、３点線分ABG
を３点線分KLGのように変形し、交線の再構成を行い、
点Gにおいてすべての交線HG, KG, LGを接続する。この
ように交線を接続することにより三角形面の消去処理な
どを効率よく行うことができる。

【００４３】上記のような交線の再構成および接続を行
うために、「交線は、その交線上に三角形面の頂点が存
在するときはその頂点で分割される」というルールを設
ける。これを、「交線構成ルール」と呼ぶことにする。
この交線構成ルールにより、交線は必ず三角形面の頂点
で接続され、かつ交線を構成する線分は一意に決まる。
例えば図7の(b)では、辺AB間の交線の構成において、交
線AG-GB, AG-GL-LBなどいろんな交線の構成が存在す
る。しかし、上記の交線構成ルールを適用すると、AB間
の交線は交線AK-KG-GL-LBとなり、一意に決まる。ま
た、頂点Gにおいてこの交線AK-KG-GL-LBと交線GHが接続
される。

【００４４】さらに、この交線の再構成処理では、これ
らの交線に対応した交線データの重なり合う交線へのポ
インタsの変更処理も行なう。図7の(c)に示す交線のみ
を取り出して表示した例の図では、交線KLのデータと交
線MBのデータが互いに他を示しあっている。この状態を
矢印で示す。これに対して図7の(d)では、交線の再構成
が行われ、交線KLは交線KG, GLとに分割される。従っ
て、もう一度、交線KGとGLのどちらが交線MBと重なり合
うかをチェックする必要がある。この例では、交線GLと
MBが重なり合うので、この両者が互いを示し合うように
変更される。交線KGとGLの両方が交線MBと重なり合う場
合は交線KGとGLのどちらか一方が選択される。この選択
はどちらでもよい。そして、この交線データの相互参照
情報に基づいて、三角形面の接続（境界面接続）が行わ
れる。

【００４５】図１に示すように、本実施例の形状演算を
行なう三角形面データ処理部03は共通空間処理部06、分
割処理部07、消去処理部08、接続処理部09、および統合
処理部10から構成される。形状αと形状βとの形状和演
算処理の場合を例に挙げてその処理を具体的に説明す
る。形状和演算処理の概要を図８のフローチャートに示
す。以下、図1及び図8を参照してそれぞれの処理につい
て詳細に説明する。

【００４６】まず、共通空間処理部06の処理（図8のフ
ローチャートのステップ106）について説明する。前処
理として、形状αと形状βが共に存在する直方体の共通
空間Qを求める。そのためにまず、形状αを包含する直
方体を求める。この処理では、形状αの三角形面データ
が三角形面データ記憶部11から順次取り出され、その頂
点座標値の比較を行う。そして頂点のX, Y, Z座標のそ
れぞれの座標値の最小値xα₁, yα₁, zα₁および最大値
xα₂, yα₂, zα₂が求められる。そして、頂点(xα₁, y
α₁, zα₁)と頂点(xα₂, yα₂, zα₂)を対角頂点とする
直方体[(xα₁, yα₁, zα₁)，(xα₂, yα₂, zα₂)]が形
状αの包含直方体となる。同様の処理により、形状βを
包含する直方体[(xβ₁, yβ₁, zβ₁)，(xβ₂, yβ₂, z
β₂)]を求める。両者の共通空間は、[(max(xα₁,xβ₁),
max(yα₁,yβ₁), max(zα₁,zβ₁))，(min(xα₂,xβ₂),
min(yα₂,yβ₂), min(zα₂,zβ₂))]として求められ
る。上記の表示中のmin, maxはそれぞれ、かっこ内の数
値の中の最小値、最大値を表す。判定ステップ１０６Ｄ
において、共通空間Qが存在しない場合は、以下のすべ
ての処理は行われず、形状演算処理は終了となる。

【００４７】次に、この共通空間Qに含まれる形状αお
よび形状βの三角形面データがそれぞれ三角形面データ
記憶部11から順次取り出される。この処理も三角形面デ
ータの頂点の座標値と共通空間の頂点の座標値を比較す
ることにより行われる。この共通空間処理部06の共通空
間を求める処理により、次のステップの三角形面の交差
判定処理の回数を一般的にかなり減らすことができる。

【００４８】共通空間Qが存在する場合は分割処理部07
による処理が行われる（ステップ１０７）。上記の共通
空間処理により取り出された形状αおよび形状βの三角
形面データ間において、交差判定を順次行なう。両者が
交わる場合はその交線を生成し、その交線においてそれ
ぞれの三角形面を分割する。この処理で求められた交線
データは交線データ記憶部13に保存される。分割により
新たに生成された３点線分データおよび頂点データはそ
れぞれ、３点線分データ記憶部12および頂点データ記憶
部14に保存される。そして、分割により新たに生成され
た三角形面データは、三角形面データ記憶部11にすぐに
は保存されずに、処理される三角形面データの群に入れ
られ引き続き上記の交差判定及び分割処理が行われる。
そして、すべての交差判定及び分割処理が終わった時点
で、三角形面データは、三角形面データ記憶部11に保存
される。

【００４９】分割される三角形面の辺と交線が交差する
場合（例えば図6の(a),(b)）には、三角形面の分割に付
随して以下のような３通りの処理が行われる。これらの
３通りの処理はすべてが同時に行われることはなく、常
に１つの処理のみが行われる。図9の(a)に例を示すよう
に、分割される三角形面ABCの辺ABとACが交線DEと交差
しているので、両方の辺ABとACがこの処理の対象とな
る。ここでは、この処理を辺AB側の場合について説明す
る。３点線分表現においては、辺AB上にある交線の端点
Dと一致する頂点が他に存在する可能性がある。そこ
で、頂点が重複して存在するのを避けるために、同一点
がないかどうかの探索を行う。その結果から以下の３つ
の場合が得られる。

【００５０】（１）端点Dと同一の点が存在する場合 図9の(a)の例では端点Dと一致する頂点Fが存在するとす
る。この場合は、３点線分FHGを図9の(b)に示すようにF
BAに変形した後、図9の(c)に示すように、この３点線分
を消去し三角形面ABCを分割する。 （２）Dが交線上に乗る場合 同一点の探索中に、図9の(d)のように点Dが乗る交線IJ
が存在した場合は、探索を中止する。これは、前述した
「交線構成ルール」により、端点Dと同一となる点は存
在しないからである。この場合は、図7の(a)及び(b)の
例で説明した三角形面の分割と交線の再構成処理を行
う。 （３）上記以外の場合 同一点の探索において端点Dの同一点も端点Dが乗る交線
も存在しない場合は、図9の(e)に示すように、３点線分
ABDを生成して三角形面を分割する処理だけが行われ
る。

【００５１】次に、図6の(c)の場合の処理に関して説明
する。この場合には三角形面の分割は行われず、交線デ
ータを求める処理だけが行われる。すなわち、交線はBC
となるが、前述した交線構成ルールにより、交線は交線
上に三角形の頂点が存在する場合はその点で分割され最
小の長さの線分（辺）で構成されるので、これに基づい
て交線に隣接するすべての三角形面の辺および３点線分
をチェックし、交線データを再構成する必要がある。こ
の処理内容を図10を用いて説明する。この例では辺AB上
に初期交線ABが存在し、これを再構成する。この処理
は、以下の３ステップから成る。そして、以下の交線処
理に対応した交線データが交線データ記憶部13へ追加さ
れるかあるいは交線データ記憶部13から消去される。

【００５２】（ステップ１）まず、三角形面ABCの頂点A
が乗りかつ辺ABと重なる辺を持つ三角形面T₁を探索す
る。この探索結果は、図10の(a-1)〜(a-6)に示す６通り
となる。図10の(a-1)および(a-4)は辺AB上に頂点Dが存
在するので、交線構成ルールにより交線ABを消去し辺AD
上に交線ADを生成し、次のステップ２に移る。ただし、
図10の(a-4)の場合は３点線分の変形を行い、３点線分A
EDを形成し線分ADを生成する処理が必要である。これら
以外の場合は、辺AB上に頂点は存在しないので、以下の
ステップの交線ABの再構成は行われず処理を終了する。

【００５３】（ステップ２）次に、三角形面ABCの頂点B
に関しても、頂点Aにおける処理と同様に、頂点Bが乗り
かつ辺ABと重なる辺を持つ三角形面T₂を探索する。ここ
では、ステップ１において頂点Dがすでに存在している
ので、この探索結果は図10の(b-1)または(b-2)のに示す
２通りのみとなる。すなわち、辺AB上に乗る頂点Fが必
ず存在する。図10の(b-1)に示す場合は、辺FB上に交線F
Bを生成する。図10(b-2)の場合は、３点線分の変形を行
い３点線分BFGを形成し、線分FB上に交線（以後交線FB
と称する）を生成する。そして、次のステップ３に移
る。

【００５４】（ステップ３）ステップ２までの処理によ
り、交線ABは、図10の(c)に示すように、交線ADとFBに
より部分的に再構成される。そこで、次の処理として、
頂点DとFの間の交線を生成する。ここで、頂点Dと頂点F
が一致する場合は、交線の再構成が完了したことになる
ので、処理を終了する。そうでない場合は以下の処理を
行う。まず、頂点Dを持ちかつ辺AB上の頂点がDとFの間
となる三角形面を探索する。図10の(c)では三角形面DIH
が該当する。そして、辺DH上に交線（以後交線DHと称す
る）を生成する。次に、この頂点Hを頂点Dと置き換え
て、同様の処理を、頂点DとFが一致するまで、すなわち
交線が、図10の(c)に示すように完全に連結されるまで
行う。その結果交線AD-DH-HJ-JF-FBが得られる。以上の
処理が分割処理部07（図8のステップ１０７）で行われ
る。

【００５５】次に、消去処理部08（図8のステップ108）
に関して説明する。上記のように三角形面の分割処理に
おいて、交線構成ルールにより、交線データで表される
交線は図11の(a)の例に示すように必ず閉ループ(AC-CE-
EG-GH-HF-FD-DB-BA)を形成する。従って、三角形面デー
タおよび３点線分データの消去処理は以下に示すように
非常に単純な処理となる。

【００５６】まず、１つの閉ループをなす交線群で囲ま
れる三角形面のデータ群及び３点線分のデータ群が求め
られる。図11の(a)の例では、三角形面データACB, BCD,
EGF, FGHおよび３点線分データCEF, DCFがそれぞれ三
角形面のデータ群及び３点線分のデータ群を構成する。
そして、この三角形面及び３点線分のデータ群により形
成される面の内外判定をし、他の形状の内部となる場合
は、図11の(b)の例のように、これらの三角形面のデー
タ群および３点線分のデータ群を三角形面データ記憶部
11および３点線分データ記憶部12から消去する。このよ
うに、消去処理では三角形面データと３点線分データを
区別することなく統一処理できる。３次元図形である形
状αおよびβのすべての交線データに関してその閉ルー
プを求め、以上の処理を繰り返すことにより、他の形状
の内部となる三角形面データおよび３点線分データはす
べて消去される。

【００５７】次に、接続処理部09（図8のステップ109）
について説明する。境界面接続処理は、交線において接
する３次元図形の形状αと形状βを構成する三角形面又
は３点線分の対を３点線分を用いて接続する。交線デー
タは互いに重なり合う交線へのポインタsを持っている
ので、この情報を利用することにより、三角形面又は３
点線分の接する対を探索する処理が不要となる。三角形
面及び３点線分の接続（境界面接続）処理を、図12の例
を用いて説明する。

【００５８】図12の(a)に示すように、形状αに属する
交線ABと形状βに属する交線AGが互いに示し合ってい
る。すなわち、この両者の交線に対応した交線データに
おける重なり合う交線へのポインタsは互いに他を示し
合っている。同様に、交線CDとHI、交線EFとEFが互いに
示し合っている。そこでまず、このように他を示してい
る交線データの対が図1のデータ記憶部05の交線データ
記憶部13から取り出される。そして、この両交線に隣接
する三角形面又は３点線分が接続される（図12の
(b)）。この時、２本の交線EFのように両交線の両端点
が一致する場合は、交線に隣接する三角形面又は３点線
分が直接接続される。交線ABとAGのように一方の端点の
みが一致する場合は、１つの３点線分(AGB)を用いて接
続が行われる。交線CDとHIのように両端点とも一致しな
い場合には、２つの３点線分CHIとCIDを用いて接続が行
われる。そして、この接続のために新たに生成された３
点線分において、隣接する三角形面又は３点線分を持た
ない線分に対しては、この線分と一致する交線が新たに
生成される。図12の(b)の例では、交線BG, CH, DIが新
たに生成される。これらの処理により新たに生成された
３点線分データおよび交線データはそれぞれ、３点線分
データ記憶部12および交線データ記憶部13に保存され
る。

【００５９】次に、重なり合う交線データを示していな
い交線データに関する接続を行う。この場合はまず、隣
の交線と重なり合う交線を探索する。図12の(c)の交線B
Cを例にとると、隣の交線を探索する「隣接探索」によ
り、交線BCに接続する交線が探索される。隣接探索は図
12の(c)の矢印の方向に、三角形面データあるいは３点
線分データの隣接三角形面及び隣接３点線分ポインタを
順次たどることにより行われる。この例では、交線BCに
接続する交線はBGとなる。しかし、この交線BCとBGは重
なり合わないので、さらに、隣接探索が続けられ、重な
り合う交線の対GBとGHが探索される。図12の(d)に示す
ように、交線GBに隣接する三角形面又は３点線分と、交
線GHに隣接する三角形面又は３点線分が３点線分GHBを
用いて接続される。接続のために新たに生成された３点
線分において、隣接する三角形面又は３点線分を持たな
い線分に対しては、この線分と一致する交線が新たに生
成される。図12の(d)の例では、交線BHが新たに生成さ
れる。これらの処理により新たに生成された３点線分デ
ータおよび交線データはそれぞれ、３点線分データ記憶
部12および交線データ記憶部13に保存される。これらの
処理が、重なり合う交線を示していないすべての交線デ
ータに対して行われる。

【００６０】最後に、図1の三角形面データ処理部03の
統合処理部10（図8のステップ110）について説明する。
この処理の主目的は三角形面データおよび３点線分デー
タの数を減らすことである。三角形面の頂点は、下に説
明する外点と内点に分類することができる。図18におい
て外点200とは、この点を頂点に持つ三角形面群におい
て、その面の傾き（法線ベクトル）が３つ以上の異なる
値を持つ点である。一方、内点201とは、これを頂点に
持つ三角形面群において、その面の傾きが２つ以下の異
なる値しか持たない点である。すなわち、外点200はこ
れを消去すると形状が変形する頂点であり、内点201は
これを消去しても形状が変化しない頂点である。本実施
例では、すべての内点を消去することにより三角形面の
統合を行い、三角形面データおよび３点線分データの数
を最少にする。

【００６１】内点を頂点に持つ可能性がある三角形面及
び３点線分は、分割処理において分割された三角形面、
および接続処理において接続された三角形面及び３点線
分である。これらの三角形面および３点線分はいずれ
も、交線に隣接する三角形面および３点線分である。言
い換えれば、交線の端点のみが内点となる可能性があ
る。そこで、まず最初に交線データ記憶部13からすべて
の交線データを順次取り出し、その２つの端点（頂点）
が内点となるかどうかを調べる。すなわち、その頂点を
有するすべての三角形面データを三角形面データ記憶部
11から取り出し、その法線ベクトルを調べる。法線ベク
トルの値が２種類以下の異なる値しか持たないのであれ
ば、この頂点は内点となる。そして、内点となる場合
は、三角形面データ記憶部11および３点線分データ記憶
部12から、この内点を頂点に持つすべての三角形面デー
タおよび３点線分データを取り出し、その形状を順次調
べ、統合できる三角形面データ及び３点線分データがあ
れば統合を繰り返す。この時の統合パターンは、図13に
示している。ここでは、消去する内点をVとする。

【００６２】図13の(a)のパターンは、隣接する２つの
三角形面が作る４角形が凹でない場合である。この場合
は、内点Vに集まる辺を減らすために２つの三角形面VA
B,VBCから、図13の(a')のように三角形面VAC, ABCを生
成し辺VBを消去する。図13の(a'')に示す例もすべて図1
3の(a)のパターンに属する。

【００６３】図13の(b)のパターンは、内点Vが３つの三
角形面で囲まれる場合である。この場合は、この３つの
三角形面を一度に統合し、図13の(b')に示すように１つ
の大きな三角形面ABCを生成する。これにより、内点Vは
消えることになる。この例では、三角形面VAB, VBC, VC
Aはすべて三角形面となっているが、これらの一部また
はすべてが３点線分となる場合も、この図13の(b)のパ
ターンに属する。

【００６４】図13の(c)は２つの３点線分により形成さ
れるパターンである。すなわち、隣接する２つの３点線
分L₁,L₂が２つの線分P₁V,VP₂を共有する場合である。こ
の場合は、この２つの３点線分を一度に消去することが
でき、頂点Vも消去される。図13の(c')は(c)と同じパタ
ーンであり、２つの３点線分は消去されるが、Vは消去
されない。

【００６５】以上のパターンにおいて三角形面の統合を
繰り返し、内点が消去されるまで続ける。そして、上記
の処理をすべての内点において繰り返し、すべての内点
を消去する。その結果として三角形面データおよび３点
線分データの数が最少になる。

【００６６】以上が３次元図形の形状和の演算処理内容
である。３次元図形の形状差(α−β)および形状積(α
＊β)の場合は消去処理部08のみが異なる処理を行う。
すなわち形状差の場合は、形状βの内側となる形状αの
三角形面データ及び３点線分データ、および形状αの外
側となる形状βの三角形面データ及び３点線分データを
消去する。そして、残った形状βの三角形面データ及び
３点線分データの表裏をひっくり返す処理を行う。

【００６７】また形状積の場合は、両形状の三角形面デ
ータ及び３点線分データそれぞれにおいて、他の形状の
外側となる三角形面データ及び３点線分データを消去す
る処理となる。

【００６８】《第２実施例》本発明の第２実施例につい
て図14を用いて説明する。図14は、図1の三角形データ
処理部03に対応する三角形データ処理部03Aのブロック
図である。第２実施例においては、この三角形データ処
理部03Aのみが図1の第１実施例の構成と異なっており、
他の構成は図1のものと同じである。第２実施例は、図1
の第１実施例における三角形面データ処理部03内の共通
空間処理部06と分割処理部07の間に、空間分割処理部15
が付加されている。形状演算処理において、演算量が最
も多いのが、図14の分割処理部07における三角形面の交
差判定及び分割処理（分割処理部07）である。この処理
を効率化すれば、処理の効率を大幅に改善しかつ処理を
高速化することができる。第２実施例では、第６の処理
部としての空間分割処理部15を設けることによって、三
角形面分割処理の演算量を大幅に減らし処理の効率を改
善するとともに処理を高速化する。

【００６９】３点線分処理方式の高い優位性の１つは、
三角形面の交差判定及び分割処理において３点線分デー
タを用いることによって、分割により新たに生成される
三角形面データの数を、従来の通常三角形面分割の場合
よりも大幅に減少させることができる「三角形面の減少
効果」である。この効果により、一般的に交差判定及び
分割処理の回数をかなり削減することができる。

【００７０】第１の実施例における共通空間処理部06で
は、図15に示すように、３次元の形状αと形状βが共に
存在する直方体の共通空間Qを求め、この共通空間Qに含
まれる形状α及び形状βの三角形面データを三角形面デ
ータ記憶装置11から取り出す。これを共通空間処理とい
う。この共通空間処理により、一般的に処理対象となる
三角形面データをかなり絞り込むことができる。図16の
ステップ161では、この共通空間処理後の形状αの三角
形面データ列の状態を示している。図16では、形状αの
三角形面データの状態のみを示しているが、形状βの三
角形面データの場合も同様の状態にある。第１実施例で
は、三角形面減少効果により減少した三角形面に共通空
間処理を適用することにより、三角形面の交差判定及び
分割処理を効率化している。しかし、第１実施例では、
依然として多くの交差しない（分割されない）三角形面
データの交差判定処理がなされる。すなわち無駄な交差
判定処理が繰り返される場合が多い。

【００７１】第２実施例は、この無駄な交差判定処理の
回数を更に減らすことを目的としている。そのために
「共通空間の分割」を行う。すなわち、共通空間Qを図1
5に示すようにX, Y, Z座標軸に関してそれぞれN等分に
分割する。この時のX, Y, Z座標軸における分割座標値
をそれぞれ、x_i (i = 0, 1,…, N), y_j (j = 0, 1,…,
N), z_k (k = 0, 1,…, N)とする。そして、これらの細
分割された部分空間単位に、三角形面データの交差判定
及び分割処理を行う。

【００７２】このように処理すべき空間を部分空間単位
の局所に限定することにより、一般的にかなり演算量を
削減することができる。第２実施例では、この空間分割
による「処理局所化効果」と、前記の３点線分処理の
「三角形面減少効果」とを組み合わせることにより、そ
の相乗効果による処理の高速化が実現される。

【００７３】以下に、空間分割による方法を用いた空間
分割処理部15の処理内容についてのみ説明する。他の処
理部での処理は、第１の実施例とまったく同じ処理内容
となる。まず、共通空間処理部06で求められた共通空間
Q（直方体空間）が図15に示すように細分割され、部分
空間(i, j, k) (0 ≦ i ≦ N-1, 0 ≦ j ≦ N-1, 0≦ k
≦N-1)が生成される。ここで、部分空間(i, j, k)と
は、頂点(x_i, y_j, z_k)および(x_i+1, y_j+1, z_k+1)を対角
に持つ直方体空間を示す。そして、部分空間(i, j, k)
の単位で以下の処理が進められる。

【００７４】共通空間処理部06において三角形面データ
記憶部11から取り出された三角形面データ群から更に、
空間z_k ≦z ≦ z_k+1に完全に含まれるかあるいは一部分
が含まれる形状αの三角形面データが取り出される（図
16のステップ162のZ抽出）。同様に、Z抽出された三角
形面データ群（図16のステップ162）から、空間y_j ≦y
≦ y_j+1に完全に含まれるかあるいは一部分が含まれる
形状αの三角形面データが取り出される（図16のステッ
プ163のY抽出）。更に、Y抽出された三角形面データ群
（図16のステップ163）から、空間x_i ≦ x ≦ x_i+1に完
全に含まれるかあるいは一部分が含まれる形状αの三角
形面データが取り出されれる（図16のステップ164のX抽
出）。同様にして、形状βの三角形面データに関して
も、Z抽出、Y抽出、X抽出が順次行われる。

【００７５】このようにして取り出された形状αの三角
形面データと、形状βの三角形面データの間で、分割処
理部07により交差判定が順次行われる。この時、両者の
三角形面データが交差する場合は、それぞれの三角形面
データの分割処理および交線データの生成処理が行われ
る。この分割処理により新たに生成された３点線分デー
タは、３点線分データ記憶部12に記憶される。また同様
に、新たに生成された交線データおよび頂点データはそ
れぞれ、交線データ記憶部13および頂点データ記憶部14
に記憶される。そして、分割処理により新たに生成され
た三角形面データは、再度交差判定及び分割処理の対象
となるため、すぐには三角形面データ記憶部11に保存さ
れずに、処理される三角形面データ群に再び入れられ
る。以上のZ抽出、Y抽出、X抽出および交差判定及び分
割処理（分割処理部07の処理）が、すべての部分空間
(i, j, k)(0 ≦ i ≦ N-1, 0 ≦ J ≦ N-1, 0 ≦ k ≦
N-1)に関して行われる。

【００７６】

【発明の効果】本発明によれば、３次元図形を三角形面
に分割して３点線分データと三角形面データを用いる３
点線分データ処理方法と交線データにより３次元図形
（ソリッド図形）を表現し形状演算処理する。この処理
方法はすべてのデータ構造が固定長の１次元リスト構造
になるという優れた特徴を有し、データ構造及び処理が
単純となり計算機での処理効率がよい。それに加えて３
点線分データを用いることにより、従来の三角形面デー
タ処理法の欠点であったデータ量（三角形面データの
数）の増大が抑制できる。これは、３点線分データを用
いることにより、分割される三角形面に隣接する周辺の
三角形面への分割の波及が阻止されるからである。その
結果データ処理量を大幅に減らすことができるので、高
い処理効率を有し、かつ高速で処理が行える３次元図形
データの演算処理方法が得られる。また、この３次元図
形データの演算処理方法により高効率かつ高速に演算処
理を実行する演算処理装置を得ることができる。

【００７７】また、３次元図形の形状演算処理における
三角形面の分割処理において、交線データを生成し、保
持する。この交線データを利用することにより、その後
に続く三角形面及び３点線分データの消去処理、接続処
理、統合処理が効率化及び高速化される。そして、この
交線データも固定長の１次元リスト構造となるので、計
算機処理に適したデータ形式となる。三角形面データ、
３点線分データ及びこの交線データを用いることによ
り、高効率かつ高速な共通空間処理、分割処理、消去処
理、接続処理及び統合処理を行う演算処理方法及び演算
処理装置が得られる。

【００７８】さらに、形状演算を行う２つの３次元図形
が共に存在する共通空間をより小さな部分空間に細分割
する空間分割法と、３点線分データおよび交線データを
用いる処理法を組み合わせることにより交差判定及び分
割処理の対象となる三角形面データをかなり絞り込むこ
とができる。その結果、分割処理が高効率かつ高速に行
える。また、この処理方法により高効率かつ高速の形状
演算装置を実現することができる。

【図面の簡単な説明】

【図１】本発明の第１実施例の３次元図形データの演算
処理装置のブロック図

【図２】(a)は３次元図形を三角形面に分割する場合
の、本発明の分割の例を示す斜視図 (b)は３次元図形
を三角形面に分割する場合の、従来の分割の例を示す斜
視図

【図３】(a)は３点線分処理のデータ構造を示す図 (b)は通常三角形処理のデータを示す図 (c)は３点線分処理のデータを示す図

【図４】(a)は形状の１例を示す図 (b)は(a)の形状を最少個数の三角形面に分割した状態を
示す図 (c)は(a)の形状を従来法により三角形面に分割した状態
を示す図 (d)は隣接する三角形面間に３点線分を介在させた状態
を示す図 (e)は他の形状の例を示す図

【図５】(a)は３点線分を介して隣接する三角形面と交
線を示す図 (b)は(a)に示す三角形面を交線51で分割した図 (c)は(b)に示す三角形面を交線52で分割した図 (d)は(c)に示す三角形面を交線53で分割した図 (e)は通常の分割法により分割された三角形面と交線の
図 (f)は(e)の三角形面を交線51、52、53で分割した図

【図６】(a)は２つの三角形面ABCとDEFの交差を示す図 (a')は(a)における三角形面ABCの分割と交線を示す図 (a'')は(a)における三角形面DEFの分割と交線を示す図 (b)は交線の両端点が頂点と辺上にある例の交差を示す
図 (c)は交線が辺上にある例の交差を示す図

【図７】(a)は交線の端点が辺上にある場合の三角形面
の分割を示す図 (b)は(a)の交線の接続を示す図 (c)は交線のデータ例を示す図 (d)は(c)の交線データを分割し再構成した状態を示す図

【図８】図１の三角形面データ処理部での処理のステッ
プを示すフローチャート

【図９】(a)ないし(e)は分割処理部での処理を説明する
ための図

【図１０】(a-1)ないし(a-6)、(b-1)ないし(b-2)及び
(c)は、交線データの再構成を説明するための図

【図１１】(a)及び(b)は三角形面及び３点線分の消去処
理を説明するための図

【図１２】(a)ないし(d)は三角形面及び３点線分の接続
処理を説明するための図

【図１３】(a)ないし(a'')、(b)ないし(b')及び(c)ない
し(c')は三角形面及び３点線分の統合処理を説明するた
めの図

【図１４】本発明の第２実施例における三角形面データ
処理部のブロック図

【図１５】第２実施例における３次元形状α及びβの共
通空間Ｑの分割を示す斜視図

【図１６】第２実施例における、データの流れを示す図

【図１７】(a)ないし(e)は第１実施例における３次元形
状α及びβの形状和の処理を説明するための図

【図１８】３次元形状における内点及び外点を説明する
ための図

【図１９】３次元図形データ演算処理における従来の多
角形を用いた処理方法を示す斜視図

【図２０】従来の多角形を用いた処理方法におけるデー
タ構造を示す図

フロントページの続き (56)参考文献 特開 平６−223201（ＪＰ，Ａ) 特開 平３−232076（ＪＰ，Ａ) 荒川佳樹”面積ゼロ３角形を用いた３ 角形ＢＲｅｐ”，情報処理学会論文誌, 1995年２月10日，第36巻，第２号，ｐ. 362−373 荒川佳樹”体積ゼロ４面体を用いた３ 次元形状モデリング”，グラフィックス とＣＡＤシンポジウム論文集，情報処理 学会，Ｖｏｌ．93，Ｎｏ．６，ｐ．51− 58 荒川佳樹”超３角形を用いた３次元図 形処理 統一処理と超高速処理を実現し た３次元形状モデリング”，画像ラボ, 1998年４月１日，第７巻，第４号，ｐ. 63−66 荒川佳樹”仮想空間における立体形状 モデリング”，グラフィックスとＣＡＤ シンポジウム論文集，情報処理学会，Ｖ ｏｌ．91，Ｎｏ．７，ｐ．33−42 (58)調査した分野(Int.Cl.⁷，ＤＢ名) G06T 17/00 - 17/50 ＪＩＣＳＴファイル（ＪＯＩＳ)

Claims (3)

(57)【特許請求の範囲】
1. 【請求項１】 対話表示部等により入力された３次元図
   形をデータ化する図形データ作成装置、 図形データ作成装置から入力されたデータを変換処理す
   る図形入力処理部、 図形入力処理部で変換されたデータに対して前記３次元
   図形の形状演算処理を行うデータ演算処理部、 データ演算処理部から与えられた前記３次元図形から表
   示図形データを生成して対話表示部に出力する図形出力
   処理部、 前記各処理部において変換または生成された図形データ
   を記憶するデータ記憶装置をそれぞれ具備し、 前記図形入力処理部は、入力された３次元図形の表面で
   ある境界面のデータから、各境界面を三角形面に分割し
   て三角形面データを生成するとともに、隣接する三角形
   面の境界に、境界上の線分の両端点と線分上にある前記
   隣接する三角形面の１つの頂点から構成される３点線分
   を介在させ、この３点線分を表す３点線分データを生成
   する手段を有し、 前記データ演算処理部は、前記三角形面及び前記３点線
   分によって境界面が構成される複数の３次元図形の形状
   演算を前記三角形面データ及び前記３点線分データ及び
   前記三角形面の交差情報を保持する交線データを用いて
   行う手段を有し、 前記データ記憶装置は、前記３点線分データ及び前記交
   線データを記憶する手段を有することを特徴とする３次
   元図形データの演算処理装置。
2. 【請求項２】 対話表示部等により入力された３次元図
   形をデータ化する図形データ作成装置、 図形データ作成装置から入力されたデータを変換処理す
   る図形入力処理部、 図形入力処理部で変換されたデータに対して前記３次元
   図形の形状演算処理を行うデータ演算処理部、 データ演算処理部から与えられた前記３次元図形から表
   示図形データを生成して対話表示部に出力する図形出力
   処理部、 前記各処理部において変換または生成された図形データ
   を記憶するデータ記憶部をそれぞれ具備し、 前記図形入力処理部は、入力された３次元図形の表面で
   ある境界面のデータから、各境界面を三角形面に分割し
   て三角形面データを生成しデータ記憶部に記憶させると
   ともに、隣接する三角形面の境界に、境界上の線分の両
   端点と線分上にある前記隣接する三角形面の１つの頂点
   から構成される３点線分を介在させ、この３点線分を表
   す３点線分データを生成し前記データ記憶部に記憶させ
   る手段を有し、 前記データ演算処理部は、前記三角形面データ及び前記
   ３点線分データとによって境界面が構成される２つの３
   次元図形において、前記２つの３次元図形が共に存在す
   る共通空間を求め、この共通空間内に存在する前記２つ
   の図形の三角形面データを前記データ記憶部から取り出
   す第１の処理部と、 前記取り出された２つの図形の三角形面データ間におい
   て交差判定を順次行い、交わる場合は両者の交線を求め
   て、その交線に基づいて、三角形面を、三角形面とそれ
   に隣接する三角形面の境界に介在する３点線分との集合
   体に分割し、これらの分割された三角形面の交差分割情
   報を保持する交線データ、前記三角形面を表す三角形面
   データ、及び前記３点線分を表す３点線分データを生成
   し、これらのデータを前記データ記憶部に記憶する第２
   の処理部と、 前記交線データを用いて、前記各三角形面データ及び３
   点線分データが、他方の図形に包含されているかどうか
   の内外判定を行い、その結果に応じて三角形面データ及
   び３点線分データを前記データ記憶部から消去する第３
   の処理部と、 前記交線データが保持している三角形面の交差情報を用
   いて、交線において隣接する２つの図形の三角形面デー
   タ及び３点線分データを取り出し、３点線分データを用
   いて接続する第４の処理部と、 前記交線データが保持している交差情報を用いて、分割
   あるいは接続操作がなされた三角形面データまたは３点
   線分データを取り出し、これらに隣接する三角形面また
   は３点線分から構成される図形が三角形面あるいは３点
   線分を形成する場合は、三角形面データ及び３点線分デ
   ータの統合を行なう第５の処理部とを有し、 前記図形出力処理部は、三角形面データ及び３点線分デ
   ータにより境界面が構成される３次元図形の隠線処理及
   び隠面処理を、三角形面データ及び３点線分データを用
   いて行い表示図形データを生成する手段を有し、 前記データ記憶部は、上記の処理において、変換、生成
   されかつ処理される三角形面データ、３点線分データ、
   交線データ、および頂点データをすべて固定長データ構
   造の形式でそれぞれ記憶する、三角形面データを記憶す
   る記憶部と、３点線分データを記憶する記憶部と、交線
   データを記憶する記憶部と、頂点データを記憶する記憶
   部とを有する３次元図形データの演算処理装置。
3. 【請求項３】 対話表示部から入力された３次元図形の
   図形データのデータ変換処理及び前記３次元図形の形状
   演算処理を行い、前記３次元図形の表示図形データを生
   成して、対話表示部に表示し、これらの処理過程で生成
   されかつ処理された図形データをデータ記憶部に記憶さ
   せる３次元図形データ処理システムにおいて、 入力された３次元図形の表面である境界面のデータか
   ら、各境界面を三角形面に分割して三角形面データを生
   成しデータ記憶部に記憶するとともに、隣接する三角形
   面の境界に、境界上の線分の両端点と線分上にある前記
   隣接する三角形面の１つの頂点から構成される３点線分
   を介在させ、この３点線分を表す３点線分データを生成
   しデータ記憶部に記憶するステップと、 前記三角形面及び前記３点線分によって境界面が構成さ
   れる２つの３次元図形において、前記２つの３次元図形
   が共に存在する共通空間を求め、この共通空間内に存在
   する前記２つの図形の三角形面データを前記データ記憶
   部から取り出すステップと、 前記取り出された２つの図形の三角形面データ間におい
   て交差判定を順次行い、交差する場合は両者の交線を求
   めて、その交線に基づいて、三角形面を、三角形面とそ
   れに隣接する三角形面との境界に介在する３点線分との
   集合体に分割し、これらの分割された三角形面の交差分
   割情報を保持する交線データ、前記三角形面を表す三角
   形面データ、及び前記３点線分を表す３点線分データを
   生成し、これらのデータを前記データ記憶部に記憶する
   ステップと、 前記交線データを用いて、前記各三角形面データ及び３
   点線分データが、他方の図形に包含されているかどうか
   の内外判定を行い、その結果に応じて三角形面データ及
   び３点線分データを前記データ記憶部から消去するステ
   ップと、 前記交線データが保持している三角形面の交差情報を用
   いて、交線において隣接する２つの図形の三角形面デー
   タ及び３点線分データを取り出し、３点線分データを用
   いて接続するステップと、 前記交線データが保持している交差情報を用いて、分割
   あるいは接続操作がなされた三角形面データまたは３点
   線分データを取り出し、これに隣接する三角形面または
   ３点線分から構成される図形が三角形面あるいは３点線
   分を形成する場合は、三角形面データ及び３点線分デー
   タの統合を行なうステップと、 三角形面データ及び３点線分データにより境界面が構成
   される３次元図形の隠線処理及び隠面処理を、三角形面
   データ及び３点線分データを用いて行い表示図形データ
   を生成するステップと、 上記の各処理ステップにおいて、生成及び処理される三
   角形面データ、３点線分データ、交線データ、および頂
   点データをすべて固定長データ構造の形式で記憶させる
   ステップとを有する３次元図形データの演算処理方法。