JPH01290080A - オブジェクトのソリッド表現データ発生器および発生方法 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 Ａ、産業上の利用分野 この発明は、ソリッド・モデリング（ｓｏｌｉｄｍｏｄ
ｅｌｌｉｎｇ　）に関し、さらにはオブジェクト（対象
物）のソリッド表現に関する。

Ｂ、従来技術 一般的に［構成的ソリッド幾何学（Ｃ５Ｇ）Ｊと呼ばれ
るソリッド・モデリング技術に従うと。

３次元ソリッド・オブジェクトは、コンピュータなどに
おいて、オブジェクト内のある点につき計算がなされた
なら「真」を返し、そうでないなら「偽」を返すプール
関数によって表現される。Ｃ８Ｇ技術は、オブジェクト
の体積ではなくその表面が決定される境界技術と対照的
であると考えることができる。

Ｃ８Ｇ技術に基づくソリッド・モデリング・システムは
、境界表現あるいは通常「Ｂ−表現」として知られてい
る表現に基づくモデリング・システムに対して利点を有
する。すなわち、ソリッド・モデリング・システムにお
いてオブジェクトが−たん決定されると、ある点がソリ
ッドの内側と外側のどちらにあるかを決定するためにそ
の点について関数の値を評価するだけでよい。「Ｂ−表
現」システムの場合、ある点がオブジェクトの内側と外
側のどちらにあるかは、決定が体積でなく境界で与えら
れているので、決定がより一層困難である。この理由か
ら、境界技術のみを採用するシステムは、本明細書で言
うところのオブジェク１への「ソリッド・モデリング」
を提供しない。

「Ｂ−表現Ｊシステムの主要な利点の１つとして、オブ
ジェクトの表現を生成するのが比較的簡単である、とい
うことがある。それは本質的には、オブジェク１〜を形
成する表面と、その表面を区画する辺と、その辺を決定
する線を画定し、これらの情報を連結するべくトリー構
造をつくり上げるということである。そのとき、大型の
オブジェクトには大量のデータがあり、結果として表現
を作成するには大量のステップが必要とされるけれども
、個々のステップは簡単であり、直接自動化するには適
している。

それに比較して、今後「ソリッド表現」と称するＣ５Ｇ
タイプの表現を生成することは、特に複雑で不規則な形
状をもつオブジェクトの場合−層困難となる。実際、オ
ブジェクｌ〜の体積（内部）を決定する表現を生成する
ことは、どれがオブジェクトの内部であり、どれが外部
であるかを決定する必要があるために、ソリッド・モデ
リング・システムの主要な欠点となる。

Ｃ８Ｇシステムにおいては、半空間（すなオ〕ち一面が
無限平面である空間）や、球や、無限円筒などの基本的
なソリッド・オブジェクトまたは「プリミティブ」の関
数式を結合することによって複合オブジェクトが決定さ
れる。例えば、四面体のソリッド表現は、４つの適当な
半空間を結合させる集合共通部分演算子を含む式から形
成することができる。各半空間は四面体の個々の面と同
一延長面上にあり、四面体の内部に対応する側のソリッ
ドである。他のソリッド・オブジェク１〜のＣ１０表現
は、合併、対称差、及び差演算子などの他の集合演算子
を含むことがある。例えば、集合差演算子を用いて、切
出しまたは穴をもつ複合オブジェク１−を決定すること
が可能である。このようにして、大きいオブジェクトか
ら別のオブジエクトを「差し引く」ことによって中空の
複合オブジェクトを画定することができる。そのような
複合オブジェク１〜は、本明細書で言うところの「ソリ
ッド」である。なぜなら、ある特定の点がオブジェクト
の内部または外部のどちらにあるかを決定するために、
空間内の特定の点につきオブジェクトの表現を評価する
ことができるからである。

プリミティブから形成されるＣ８Ｇオブジエクトは典型
的にはプリミティブを結合するための論理式をあられす
構造のとして決定され、連結された一組のノード（例え
ば、トリー構造）を含み、プリミティブは第１のノード
（例えばトリーの葉ノード）において決定され、演算子
は、構造中の下位ノードで決定されるプリミティブまた
はサブオブジェクトからオブジェクトを構成するために
実行すべき組合せ演算をあられすために第２または中間
ノードにおいて決定され、複合オブジェクトは、演算子
ノードの適宜のノード（例えばトリーの根）において決
定されている。

尚、現実においては、モデリングすべきオブジェク１〜
は上述の四面体よりもはるかに複雑であり、オブジェク
トのソリッド表現を正しく生成するべくプリミティブと
集合演算子をあられすことがきわめて困難であることを
理解されたい。その結果、今までのところ、オブジェク
トのソリッド表現を生成することは、高度のユーザー操
作を要する非常に時間のかかる処理となっている。

Ｃ０発明が解決しようとする問題点 本発明の目的は、ソリッド・オブジェク１〜の表現式の
作成を容易ならしめることにある。

Ｄ８問題点を解決するための手段 本発明の一態様に従えば、ソリッド・モデリング・シス
テムのためのオブジェクト画定発生器が与えられる。こ
の発生器は、オブジェクトの個々の表面領域に基づき、
オブジェクト空間中の共通基準点に関連して画定される
構成ソリッドの対称差としてオブジェクトのソリッド表
現を形成するためのオブジェクト画定論理を有する。

空間中の共通基準点に関連して構成ソリッドを画定し構
成ソリッドの対称差を形成することによって、オブジェ
クトの内部の関数表現が自動的に生成される。ソリッド
表現は、オブジェク１〜の表面が表面領域によって完全
に画定される限りは常に生成され、表面の画定が不完全
である場合ですらも生成されることがある。対称差演算
はオブジェクトの外の空間を自動的に削除するが、これ
については後で説明する。この処理の基となる理論はあ
る種の領域充填アルゴリズムに類似している（例えば、
ＩＢＭ　Ｇｒａｐｈｉｃａｌ　Ｄａｔａ　Ｄｉｓｐｌａ
ｙ　Ｍａｎａｇｅｒ（ＧＤＤＭ）　Ｂａ５ｅ　Ｐｒｏｇ
ｒａｍｍｉｎｇ　Ｒｅｆｅｒｅｎｃｅ　（文書番号Ｎｏ
　５Ｃ３３−０１０１−４）の１６７ページを参照）。

対称差演算は、排他的論理和（ＥＸＯＲ）に相当する集
合演算である。

本発明は、オブジェクトの複雑度に拘らず、オブジェク
トの境界または表面の表現からオブジェクトのソリッド
表現を生成することを可能ならしめる。それゆえ好適に
は、画定発生器は、オブジェクトの表面領域としてその
表面を初期的に画定するための手段を有してもよい。た
だし、そのような手段は、画定発生器に外部的に与えて
もよい。

本発明に従う画定発生器の好適な実施例においては、オ
ブジェクＩ・の表面を初期的に画定するための手段が、
′表面領域としてその表面を画定するデータ構造のため
のデータ記憶のかたちで与えられる。このようにして、
本発明は、オブジェク１−の現存する表面表現からソリ
ッド・オブジェクトのソリッド表現を与えることを可能
ならしめる。

オブジェクトの表面を初期的に画定するための手段は、
追加的に、あるいは代替的に、表面領域として表面を画
定するデータ構造を発生するために、オブジェクトに関
して外部的に供給されたデータを処理するための前処理
論理手段を有してもよい。このようにすると、本発明に
従う画定発生器は、先ずオブジェクトの表面の表現を生
成し、次にその表面の表現からソリッド表面を作成する
ことによって、ソリッド・モデルの生成を容易ならしめ
ることができる。

Ｃ８Ｇ原理に従うと、後述する本発明の特定の実施例に
従うオブジェク１〜画定論理は、表面領域自体に基づく
ソリッド・プリミティブの共通部分と、表面領域の境界
に基づく１つまたはそれ以上の構成表面と、共通点を表
現することによって、表面領域に基づく構成ソリッドを
形成する。ある表面の構成プリミティブの数または形状
では、表面領域の形式に依存することになる。またそれ
は空間中で共通基準点として何が使用されているかにも
依存する。

例えば、オブジェクト空間中の基準点は、オブジェクト
空間中の特定の点である。このとき、表面領域の境界と
空間中の共通点を組込むように、生成される構成表面を
画定することができる。

あるいは、オブジェクト空間中の基準点は、例えば、オ
ブジェクト空間中の特定の方向であることもある。この
とき、生成される構成表面は、表面領域の境界を包含し
所与の方向へ延びるように画定することができる。この
ことは、その方向の無限遠点に基準点を選択することと
等価である。

構成面の生成は、各平面領域が平坦で不連続領域によっ
て接続された複数の直線によって区画さ＝８− れているときに簡易化される。というのは、そのとき構
成面が平坦で構成プリミティブが半空間の形式となるか
らである。

もしオブジェク１〜の各表面領域が三角形であるなら、
構成ソリッドの生成はさらに簡易化される。

このことは、ピラミツ１く形状の基底が平坦で凸状の境
界をもつことを保証し、以て凹状表面領域があるかどう
かを判断する必要性を解消する。この場合、もし予備処
理論理手段が与えられているなら、その論理手段は、好
適には、外部的に供給されたデータが境界を画定しない
箇所で三角形のオブジェクトの境界を画定するために、
外部室に画定されたデータを処理するための小面化（ｆ
ａｃｅｔｔｉｎｇ）論理手段を有している。しかし、本
発明は、この形式をもつ表面領域を使用することには限
定されない。本発明は、平坦でもなく三角形でもない表
面領域をもつオブジェクｉ・にも適用可能である。ただ
し、そのとき、オブジェクｉ〜の処理が複雑になること
を理解されたい。

従って、後述する画定発生器の例では、モデリングすべ
きオブジェクトの表面は三角形の平面領域として画定さ
れ、オブジェクト画定手段は次のものを具備する。

（ａ）表面領域自体と、３つの構成プリミティブに基づ
き各表面毎にプリミティブを画定するためのプリミティ
ブ画定論理手段。構成プリミティブの各々は、表面領域
の各辺と空間の共通基準点に基づく。

（ｂ）表面領域自体に基づくプリミティブと、表面領域
及び空間の共通基準点に基づく３つの構成プリミティブ
の共通部分によってあられされる構成ソリッドを、各表
面領域毎に形成するための共通部分論理手段。

（ｃ）共通部分論理手段によって生成された対称差とし
てオブジェクトのソリッド表現を形成するための対称兼
論理手段。

表面領域が三角形で共通データが空間における特定の点
である場合、各構成ソリッドは、その先端が予定の位置
に規定され、その基底が、表面領域に画定されるような
台形状ピラミッドである。

このことは原理的には、共通基準点が特定の方向の無限
遠点でありすなわち無限ピラミッドの頂点が無限遠点に
ある場合にもあてはまるけれども、この場合、ピラミッ
ドは、実際のモデルの有限的な制約により収束すること
はない。

好適には、オブジェクト画定論理手段は、オブジェクト
のソリッド表現を画定するデータ構造を生成する。そし
てこれは、画定発生器の一部であってもなくてもよいオ
ブジェ９１〜画定記憶に記憶することができる。

本発明に従うオブジェクト画定発生器によって発生され
たソリッド表現は、慣用的に作成されたソリッド表現と
同様に処理することができる。結局、本発明に従うオブ
ジェクト画定発生器と、その発生器によって発生された
オブジェクトのソリッド表現を処理するためのオブジェ
クト画定処理論理手段をもつソリッド・モデリング・シ
ステムが与えられる。

本発明の別の態様によれば、オブジェク１〜のソリッド
表現を生成するための方法が与えられ、この方法は、オ
ブジェクトの個々の表面領域に基づいており、オブジェ
クト空間中の共通データに関連して画定された構成ソリ
ッドの対称差を形成することに関与している。

この方法は好適には、表面領域としてオブジェクトの表
面を初期的に画定することに関与し、これにより第１の
原理からソリッド・モデルを生成することが容易ならし
められる。

本発明に基づく方法の特定の例においては、表面領域に
基づく構成ソリッドは、表面領域自体に基づくソリッド
・プリミティブと、表面領域の境界及び空間中の共通デ
ータに基づく１つまたはそれ以上の構成表面との共通部
分を表現することによって形成される。

Ｅ、実施例 第１Ａ図及び第１Ｂ図は１本発明に従うオブジェクト画
定発生器の機能を説明するために使用されるオブジェク
ト１０の斜視図及び平面図である。

その平面図から見てとれるように、オブジェクトは、火
影の基底をもち、オブジェクト１０の辺が頂点５で合一
する。

第２図は、第１及び第２の組の表形式のレコードをあら
れし、それらの表は結合さると、オブジェクト１０の表
面をあられすデータ構造を形成する。

符号１２で参照される第１の組のレコードは、第１の５
つのレコード（すなおち、レコード群Ｉ２の最初の５つ
の行）におけるオブジェクトの５つの頂点１ないし５の
、オブジェクト空間における座標位置をあられす。それ
らのレコードの第１、第２及び第３のフィールドにＸ、
Ｙ及びＺ座標が格納される。符号１４で参照される第２
の組のレコードは、オブジェクト１０の境界を形成する
６個の三角形領域を決定する。すなわち、それぞれのレ
コードは、頂点１．２．３：１．２．４；１．５．３；
１．５．４；２．５．３及び２．５，４である（ここで
、１．２．３などはレコード群１２の左側に付されてい
るレコード番号１ないし５に対応する）。三角形領域の
３つの頂点は、レコード群１４の第１、第２及び第３の
フィールドであられされる。

ここで、第１図のオブジェクトの各表面領域が三角形で
あることに注意されたい。オブジェクトの基底の場合、
オブジェクトの面は火影であるけれども、その境界画定
面は、２つの三角形表面領域に分割される。このことは
、オブジェクトのソリッド表現の生成を簡易化するため
に行われる。

その理由を述べると、第１に、三角形は表面領域のきわ
めてコンパクトな表現を与える。というのは、３点によ
り三角形状の表面領域が一意的に決定されるからである
（ただし、三角形は平坦であると想定する）。４点ある
いはそれ以上の場合。

面を正しく決定するためにはこれらの点をつなぐ線につ
いての余分なデータが必要である。例えば、オブジェク
トの美形基底面の４つの頂点を以てすれば、３つの異な
る閉表面を決定することができる。その第１のものは、
点１．４．２．３．１をこの順に結んだ三角形であり、
その第２のものは、点１．３．４．２．１をこの順に結
んだ三角形であり、その第３のものは、点１．２．３．
４．１をこの順に結んだ三角形である。このように、三
角形の表面領域を使用することは、オブジェクトの境界
の表現を簡易化するのである。

さらに述べると、三角形で平坦な表面領域を使用するこ
とが構成ソリッド生成の簡易化につながる。すなわち、
各表面領域の境界が凸状であるため、表面領域の境界に
凹状部分があるかどうかのチエツクをする必要がなく、
簡単なソリッド表現をもつ有効構成ソリッドを高い信頼
性で生成することができる。

オブジェクトの境界表現によって画定されるオブジェク
トの表面を、平坦な三角形表現領域を形成するように細
分割するアルゴリズムは既知である。オブジェクトの境
界表現を細分割するこの処理は一般的に小面化（ｆａｃ
ｅｔｔｉｎｇ　）と呼ばれ、結果の表面領域は一般的に
小面（ｆａｃｅｔ）と呼ばれる。平坦面から形成されて
いない表面をもつオブジェクトの場合、オブジェクトを
小面化する最初のステップは、オブジェクトのその表面
を平坦なｎ側面小面体で近似し、その後ｎ側面小面体を
三角形小面に細分割する段階を有する。この三角形小面
体を形成する処理は任意の適宜な方法でよく、それは当
技術分野の熟練した技術者には明らかであり、本発明の
一部を形成するものではない。

第３図は、本発明に基づくオブジェクト画定発生器１８
を含むソリッド・モデリング・システムの論理及び記憶
手段の全体的な概要の機能ブロック図である。第２図に
示されている表面表示のデータ構造は、表面表示データ
記憶（ＳＲ８）２０に記憶されている。オブジェクト画
定論理（ＯＤＬ）２２は、そのオブジェクトの表面表示
から、モデリングすべきオブジェクトのソリッド表現を
発生するために５Ｒ８２０にアクセスする。０ＤＬ２２
は、オブジェクトの結果のソリッド・モデルをオブジェ
クト画定記憶（ＯＤＳ）２４に記憶する。

第３図に示されているオブジェクト画定発生器１８はま
た、５Ｒ８２０に記憶するためのモデルの表面表現を生
成するためにモデリングすべきオブジェクトに関連する
入力データ２８を処理するための前処理理論（ＰＰＬ）
２６を含んでいる。この入力データは、キーボード入力
、オブジェクトの直接的なディジタイズによるか、その
オブジェクトのスケール・ドローイングによるか、他の
適当な手段により慣用的な方法で取り込んで、前処理論
理に適当な形式で処理入力してもよい。あるいは、入力
データは、直接Ｓ　ＲＳ　２０に記憶するための前処理
されたデータのファイルの形式をとってもよい。前処理
論理はまた、例えば上述したオブジェクトの表面の小面
化のために、第２図に示すような形式でない境界表現を
変更するための論理手段を含んでいてもよい。

ソリッド・モデルあるいはオブジェクト画定処理論理（
○ＤＰＬ）３０は、オブジェクト画定発生器１８が組み
こまれるソリッド・モデリング・システムの一部を形成
する。０ＤＰＬは、ＣＧＳ原理に従って所望の結果を与
えるために、０ＤＬ２２によって作成されたオブジェク
トのソリッド表現を処理するためのものである。０ＤＰ
Ｌは、例えば、英国特許第２１９４７１５号に記載され
ているようなオブジェクトの２次元イメージを発生する
ための論理手段を含んでいてもよい。

第３図に図示され、以下説明されるオブジェクト画定発
生器の例は、モデリングされるオブジェクトの表面表示
が、第２図に関連して説明した三角形小面に基づいてい
ることを想定している。後述のリスト１は、オブジェク
トの表面領域に基づく構成ソリッドの対称差を形成する
ために第３図に示されている０ＤＬ２２の動作の全体的
な概要を示すものである。第４図には、モデリングすべ
きオブジェクトのソリッド表現のためのデータ構造が示
されている。

１．１．オブジェクトのソリッド表現（ＳＲ）を、空に
セット １．２．オブジェクトの第１の表面領域を現在表面とし
て選択 １．３．現在表面領域に基づき構成ソリッド（Ｃ８）を
画定 １．４．Ｃ８で以前のＳＲの対称差を形成することによ
ってＳＲを更新 １．５．さらに表面領域があるなら、次の表面領域を現
在表面領域として選択し、１．３へ行く、さもなければ
終了。

リスト１一対称兼論理 ステップ１．１では、論理状態［空」を決定するプリミ
ティブ・ノードを指し示すデータ構造のための先頭ノー
ドＨＮを作成することによって、ＯＤＳ中にソリッド表
現のためのデータ構造が確立される。言いかえると、オ
ブジェクトは初期的には空の空間であるとして定義され
る。

ステップ１．２では、レコード群１２のうちのどの点が
、オブジェクトの第１の表面領域の頂点を形成するかを
判断するために、レコード群１４の第１の行に０ＤＬ２
２がアクセスする。

ステップ１．３では、ＯＤＬが表面領域に基づく構成ソ
リッドのソリッド表現を生成する。このことは、後述の
リスト２を参照してより詳細に説明される。

ステップ１．４では、オブジェクト（４２Ｐ、４４Ｐ、
４６Ｐ、４８Ｐ、５０Ｐ）の以前のソリッド表現と、ス
テップ１．３で生成された構成ソリッド（４２Ｃ１４４
Ｃ１４６Ｃ１４８Ｃ１５０Ｃ）のソリッド表現の対称差
を決定する中間ノード（４２，４４，４６，４８，５０
）を導入することによって、オブジェクトのソリッド表
現（第４図）をＯＤＬが更新する。

第４図に示す各ブロックは、トリー状データ構造中のノ
ードをあられす。各ノードは、ノードの定義（例えば、
対称差ノードＳＤである、など）を含む第１のフィール
ドと、従属ノード（例えば前のソリッド表現４２Ｆ’な
ど）あるいは構成ソリッド（４２Ｃなど）へのポインタ
を形成する１つまたはそれ以上のフィールドを含む。第
４図に示すトリー構造は、多くのノードにおいて、左側
のポインタによって指し示されるサブトリーが、右側の
ポインタによって指し示されるサブトリーよりも長いと
いう点でかなり非対称である。対称兼論理は、平衡サブ
トリーを生成するように変更することもできる。尚、第
７図及びリス１−２を参照して後で説明することである
が、構成ソリッドを決定する各ノードは事実上サブトリ
ーを含む。

ステップ１．５では、もし処理すべき表面領域がさらに
あるなら、ＯＤＬはレコード群１２の第１の行にアクセ
スし、ステップ１．３へ制御を渡す。

このことは、オブジェクトの表面表現の各表面領域が順
番に処理され、各表面領域に基づく構成ソリッドが生成
され、それが対゛称差演算子によって、同様に生成され
た他の構成ソリッドと論理的に結合されることを意味す
る。「対称差」演算子は、排他的論理和関数と等価な、
集合算である。すなわち、２つの容量体の対称差は、容
量が存在するけれども共存しない場合に真である。この
ことは、第５図に示す、プリミティブＡ、Ｂ、Ｃ及びＤ
についてのペン図に示されている。ここで、Ａ、Ｂ。

Ｃ及びＤの対称差が真である領域は工とラベルされてい
る。これらは奇数個のプリミティブが共存する領域であ
る（この場合、０を偶数と考える）。

対称差演算子の効果は、第１図に示したオブジェクトに
関連して第６図にも示されている。第６図においては、
４つの四面体の辺が重ね書きされており、その四面体の
各々は、オブジェクトの三角形表面の１つを基底とし、
オブジェクト空間中の共通データ点Ｐに関連して規定さ
れている。尚、四面体を規定するための論理は、リスト
２及び３に関連して後で説明される。６つの四面体は、
それぞれ、頂点Ｐ、１．２．３；Ｐ、１．２．４；Ｐ、
１．５．３；Ｐ、■、５．４；Ｐ、２．５．３及びＰ、
２．５．４である。Ｐは座標（−２，２、−２）をもっ
と仮定する。第６図を眺めることにより、頂点１．２．
３．４及び５をもつソリッド・オブジェクトの内側が、
奇数個の四面体が存在しあるいは共存する箇所の空間領
域によって決定されることが見てとれよう。これに対し
て、偶数の四面体が共存し、あるいは四面体が存在しな
い領域は、オブジェクトの外側である。

以下に示すリスト２は、構成ソリッド（リスト１のステ
ップ１．３）を形成するための共通部分論理である。

２．１．現在の表面を画定する頂点を選び、空間中の予
定の基準点に関連して現在表面領域の半空間を画定する
。

２．２．現在の表面領域の第１の辺を画定する２つの頂
点を選び、その表面領域の残りの頂点に関連してこの辺
と予定の基準点を含む半空間を画定し、ステップ２．１
で生成した半空間との共通部分を形成する。

２．３．現在の表面領域の第２の辺を画定する２つの頂
点を選び、その表面領域の残りの頂点に関連してこの辺
と予定の基準点を含む半空間を画定し、ステップ２．２
で生成した半空間との共通部分を形成する。

２．４．現在の表面領域の第３の辺を画定する２つの頂
点を選び、その表面領域の残りの頂点に関連してこの辺
と予定の基準点を含む半空間を画定し、ステップ２．３
で生成した半空間との共通部分を形成する。

リスト２−共通部分論理 ステップ２．１において、ＯＤＬは、レフ−１〜群１４
で現在アドレスされている表面領域の内容によって識別
されたレコード群１２の頂点の画定データにアクセスす
る。次に、ＯＤＬは、この表面領域に基づく半空間の関
数式を計算する。実行すべき実際の計算は、使用される
データの形式に依存するが、これについては、リスト３
乃至５に関連して示されるプリミティブ・ソリッド、ま
たはオブジェクトのソリッド表示のためのプリミティブ
のうちの１つを形成し、その半空間を画定するデータは
、第７図のプリミティブ・ノード５２に記憶される。

ステップ５２において、ＯＤＬは、三角形表面領域の３
つの辺のうちの第１の辺を決定する現在の表面領域の頂
点のうちの２つの頂点を選択する。

ＯＤＬは次に、この辺と共通点を含む半空間を画定する
計算を行う。これについては、リスト３乃至５に関連し
て示されるプリミティブ画定論理に関連して後で説明す
る。この半空間が、第２のプリミティブ・ノード５６で
ソートされることになるデータである、第２のプリミテ
ィブを形成する。

ＯＤＬは、集合共通部分演算子を規定するノード６０を
もちいて、第１の２つのプリミティブ・ノードを連結す
る構成ソリッドのソリッド表現（第７図）を更新する。

ステップ２．３及び２．４において、三角形表面領域の
第２及び第３の辺のおのおのについてステップ２．２の
処理が反復されて、第３及び第４のノードが生成され、
これは、第７図に示すように、共通部分ノード６２及び
６４を用いて構成ソリッドの表現へとリンクされる。な
お、第７図は、構成ソリッドの結果のソリッド表現を示
すものである。

ステップ２．１に関連して既述のように、表面領域に基
づく半空間の関数式を割算するために実行すべき実際の
計算は、使用される基準データの形式に依存する。三角
形の頂点の組に基づき半空間を形成するための論理は、
リスト３に記述されており、その場合、オブジェクト空
間中の共通基準データはその空間中の点Ｐである。

リスト３で設定されるプリミティブ画定論理によって要
求される入力データは、半空間Ｊ、Ｋ、及びＬの境界上
の３点の座標Ｃと、半空間内の点Ｔの座標Ｃである。表
面領域自体に基づき半空間を規定するとき（すなわち、
」二記ステップ２゜１）、三角形表面領域の頂点が、点
Ｊ＝Ｋ及びＬを形成し、オブジェクト空間中の共通点が
点Ｔを形成する。表面領域の辺のうちの１つに基づき半
空間を規定するとき（すなわち、上記ステップ２゜２．
２．３．２．４）三角形表面領域の頂点が点Ｊ、Ｋ及び
Ｔを形成し、空間中の共通点が点りを形成する。

３．１１点Ｊ、Ｋ及びＬの座標を用いて２つのベクトル
を決定： ベクトル　ＪＫ＝Ｃ（Ｊ）−Ｃ（Ｋ） ベクトル　ＪＬ＝Ｃ（Ｊ）−Ｃ（Ｌ） ３．２．その平面の法線を決定： 法線＝ベクトルＪＫとベクトルＪＬの外積３．３．原点
からその平面のオフセットを決定：オフセット（ｄ）−
法線と点Ｊの内積 ３．４．その平面の半空間決定： もし法線と点Ｐの内積がｄより大きいなら、半空間：＝
　（Ｎｘ、Ｎｙ、Ｎｚ、−ｄ）そうでないなら、 半空間：＝　（Ｎｘ、Ｎｙ、Ｎｚ、ｄ）ここで、Ｎｘ、
Ｎｙ、ＮｚはそれぞれＸ、Ｙ及び２方向のベクトル定数
であり、ｄは、原点からのオフセットである。

リスト３−基準データ２点の場合のプリミティブ画定論
理 リスト３のプリミティブ画定論理の動作の原理は、ある
平面上で３つの点Ｊ、Ｋ及びＬの座標を与えたとき、そ
の平面の数学的な表示は、その法線と、その平面の座標
系の原点からのオフセットとして決定することができる
。原点からのオフセットは、法線と、その平面上の一点
の座標との内積によって計算することができる。

ステップ３．１では、生成すべき半空間に対応する平面
上にある３つの点から第１及び第２のベクトルが生成さ
れる。第１のベタ１−ルである、ベクトルＪＫは、第１
の点Ｊの座標値ｘ、ｙ及び２を、第２の点にの対応する
値から個別に減算し、その結果を個別に記憶することに
よって生成される。第２のベクトルである、ベクトルＪ
Ｌは、第１の点Ｊと第３の点りの座標をそれぞれ使用し
て同様に計算され記憶される。各ベクトルの記憶値は、
それぞれ、ｘ、ｙ及びＺ軸に関する勾配をあられす。

ステップ３．２では、第１及び第２のベクトルの外積を
形成することによって表面に対する法線を生成すること
ができる。外積は次のように定義される。

（（ＪＫｙ＊ＪＬｚ）−（ＪＫｚ＊ＪＬｙ）、（ＪＫｚ
＊ＪＬｘ）−（ＪＫｘ＊ＪＬｚ）、（ＪＫｘ＊ＪＬｙ）
−（ＪＫｙ＊ＪＬｘ））ここで、ＪＫｘ、ＪＫｙ、ＪＫ
ｚは、それぞれベクトルＪＫのｘ、ｙ、ｚ方向のベクト
ル定数であり、ＪＬｘ、ＪＬｙ、ＪＬｚは、それぞれベ
クトルＪＬのｘ、ｙ、Ｚ方向のベクトル定数である。

ステップ３．３では、ベクトルと、平面上の点との内積
として原点からのオフセットが計算される。内積は次の
ように定義される。

（ＮｘｊＷｘ）＋（Ｎｙ＋ｌｙ）＋（ＮｘｊＷｘ）ここ
で、Ｎｘ、Ｎｙ、Ｎｚは、それぞれ法線Ｎのｘ、ｙ、ｚ
方向のベクトル定数であり、Ｗｘ、Ｗｙ、Ｗｚは、それ
ぞれ点Ｗのｘ、ｙ、ｚ座標である。この内積は、平面上
の任意の点Ｗにおける平面のオフセットを与える。

四面体の小面の１つと同一平面上にある平面の方程式と
、その小面のソリッド側の点の座標が与えられると、四
面体のソリッド表現を形成するために使用することので
きる半空間を画定することが可能になる。

このことは、ステップ３．４で実行される。最初にまず
、四面体の残りの点が平面のどちらの側に有るべきかに
ついての判断がなされる。その判断は、法線と四面体の
第４の点の内積が、平面上の点と法線の内積よりも大き
いか小さいかによりなされる。この半空間は次に、上記
判断の結果に応じて、上記ステップ３．４に示すように
、平面に対する法線のｘ、ｙ及び２勾配と、原点からの
その平面のオフセットによって画定される。この画定に
よりソリッド・プリミティブの関数的画定が形成され、
これは、ソリッド・オブジェクトをあられすデータ構造
中のプリミティブ・ノードにおいてＯＤ　Ｓ　２４に記
憶される。

尚、この段階で、法線と点Ｔの内積がｄに等しいなら、
このことは、点Ｔはその平面上にあり、四面体が平坦（
すなわち共通点が、三角形平面領域の３つの頂点によっ
て決定される平面上にある）であることを意味すること
に留意されたい。その場合、その平面の構成ソリッドは
、オブジェクトのソリッド表現の画定には寄与せず、「
空」を定義するプリミティブで置きかえることができる
。

こうして、もし平坦な構成ソリッドのための追加的論理
手段が例えばリスト２のステップ２．１の前に設けられ
るなら、処理時間を節約し、そのような場合のオブジェ
クトのソリッド表現を簡易化することができる。尚、こ
の追加的論理手段は構成ソリッドの画定を簡易化するも
のであるけれども、０ＤＬ２２の動作には本質的ではな
いことに留意されたい。

オブジェクトの表面表現が不完全であっても場合によっ
てはソリッド・オブジェクトの有効なソリッド表現を作
成することが可能であるのは、ある表面と共面的な平面
が場合によっては基準点を含むことがあり、結局オブジ
ェク１−のソリッド表現に寄与しないという理由による
。このことは、空間中で基準点を正しく選択することを
保証する。

リス１−２に示されている共通部分論理を用いると、そ
のような４つのプリミティブ・ノードが画定され、各四
面体毎にそれらのプリミティブの共通部分を画定するノ
ードによってそれらのノードが第７図に示すように連結
されることが理解される。プリミティブの共通部分は、
すへてのプリミティブによって占められている空間の領
域、すなわちピラミッド内の空間領域を画定する。

リスト３は、データが空間中の予定の点である場合に半
空間を生成するためのプリミティブ画定論理をあられし
ている。しかし、その点がある方向の無限遠に移動され
るなら、構成ソリッドを生成するための計算式は簡略化
することができる。

このことは、実際のシステムの有限の節約条件が与えら
れたとき、構成表面が収束しないという利点を有し、し
かも予定の基準線をその方向とすることができる。三角
形領域の頂点の組に基づき半空間を形成するための論理
手段は、予定の基準テ−タが空間中の所与の方向である
場合について、リスト４及び５を参照して後で説明され
る。

リスト４及び５に示されている論理に必要な入力データ
は、半空間Ｊ及びＫの境界上の２点の座標Ｃ１すなわち
その境界が延びる方向のベクトル■の画定と、半空間内
の点Ｔの座標である。

リスト４に示されている論理は、表面領域自体に基づき
半空間を生成するために（すなわちリスト２のステップ
２．１）使用される。この論理は本質的にはりスト３の
論理と同一であるが、入力パラメータとして、空間中の
共通点でなく共通ベクトルＶと、点Ｊ、Ｋ及びＬとして
の三角形平面領域の頂点を使用する。

４．１０点Ｊ、Ｋ及びＬの座標を用いて２つのベクトル
を決定： ベクトル　ＪＫ＝Ｃ（Ｊ）−Ｃ（Ｋ） ベクＩ−ル　ＪＬ＝Ｃ（Ｊ）−Ｃ（Ｌ）４．２．その平
面の法線を決定： 法線＝バク１−ルＪＫとベクトルＪＬの外積４．３．そ
の平面の原点からのオフセット＝３２− オフセット（ｄ）＝法線と点Ｊの内積 ４．４．その平面についての半空間を決定：もし法線と
ベクトル■の内積がＯより大きいなら、半空間：　＝　
（Ｎｘ、Ｎｙ、Ｎ７．、−ｄ）さもなければ 半空間：＝（−Ｎｘ、−Ｎｙ、−Ｎｚ、ｄ）ここでＮｘ
、Ｎｙ及びＮｚは、それぞれＸ、Ｙ及びＺ方向のベクト
ル定数であり、ｄは原点からのオフセットである。

リスト４−基準データコベクトルである場合の表面領域
に基づくプリミティブのプリミティブ画定論理 リスト４に示した論理は、入力パラメータが異なりまた
ステップ４．４での判断が異なる点でしかりスト３とは
異ならないことが見てとれよう。

法線とべ′クトルＶとの内積は、平面のどちらの側がソ
リッドであるがを判断するために使用される。

もし法線とベクトルが垂直なら（すなわち内積＝０）、
半空間の方向ベクトルはその平面内にある。

この結果は、目下の表面領域の構成ソリッドが平坦でオ
ブジェク１〜のソリッド表現に寄与しない、ということ
になる。リスト３に関連して指摘すると、もし平坦な構
成ソリッドについてチエツクするための追加的な論理が
設けられるなら、その構成ソリッドに対応して、オブジ
ェクトのソリッド表現には「空白」を規定するプリミテ
ィブを挿入することができる。

リスト５に示されている論理は、表面領域の辺の１つオ
ブジェクト空間の方向に基づき半空間を生成するために
（リスト２のステップ２．２．２゜３、または２．４）
使用され、この場合、点Ｊ、Ｋ及びＴが三角形の頂点で
あり、ベクトルＶが空間の予定の方向である。

５．１．座標を用いてベクトルの決定：ベクトル　ＪＫ
＝Ｃ（Ｊ）−ｃ　（Ｋ）５．２．平面に対する法線の決
定： 法線＝ベクトルＪＫとベクトルＶの外積５．３．平面の
原点からの法線オフセット決定：オフセット（ｄ）工法
線と点Ｊの内積 ５．４．平面の半空間の決定： もし法線と点Ｔの内積がｄより大きいなら、半空間：＝
　（Ｎｘ、Ｎｙ、Ｎｚ、−ｄ）そうでないなら 半空間：＝（−Ｎｘ、−Ｎｙ、−Ｎｚ、ｄ）ここでＮｘ
、Ｎｙ及びＮＺはそれぞれＸ、Ｙ及び２方向のベクトル
定数であり、ｄは原点からのオフセットである。

リスト５−基準データコベクトルである場合の表面領域
の辺に基づくプリミティブのためのプリミティブ画定論
理 ここで、ステップ５．１ないし５．４は、ベクトルＶが
ステップ５．２で第２のベクトルとして使用されるので
ステップ５．１で第２のベクトルを計算する必要がない
ということを除けば、リスト３のステップにほぼ対応し
ていることが見てとれよう。

ベクトルによって決定される、方向としてのデータの使
用は、さまざまな構成ソリッドのすべてが構成平面が有
限空間内のある点で収束する訳ではないという点で好都
合である。これは、無限空間の点を基準点として使用し
た場合である。点を基準データとして選択したときに、
その点の付近の構成表面を解像することには、実際のシ
ステムの有限の解像度のため問題が生じることがあるが
、この問題はベクトルを用いることにより回避される。

結果のデータ構造によって画定されるオブジェクトのソ
リッド表現は、ソリッド・オブジェクトの画定のために
必要な多くの構成プリミティブを含むことになるが、こ
れは直接にはオブジェクト自体の表面に寄与しない。こ
の状況は、本発明に従いオブジェクト画定発生器によっ
て発生されるソリッド表現に特有ではない。実際、得ら
れたデータ構造は慣用的なＣ１０形式のものである。

オブジェクトの空間的表現（例えば２次元イメージ）を
発生するためにオブジェクトのソリッド表現を処理する
ための慣用的なＣ１０細分割論理は、そのような空間的
表現ではレンダリングされることになっていないプリミ
ティブまたはプリミティブの一部を除去する能をもつ。

そのような２次元イメージの生成の例は、英国特許第２
１９４７１５号に記載されている。そのような慣用的な
論理手段はまた、基底を２つの三角形平面領域に分割す
る（第１図に示すような線）が、結果のイメージにあら
れれず、以て後処理論理がオブジェク１−の基底を平坦
であると考慮するようにすることを意図している。

オブジェクトのソリッド表現の処理効率を高めるために
は、構成プリミティブにラベルをつけることが望ましい
が、必ずしも本質的ではない。このことは、プリミティ
ブ・ノードに、そのプリミティブが構成プリミティブで
あるか否かを識別するフラグを設けることにより行うこ
とができる。

このフラグは、ソリッド表現の処理の間に、その作成の
間とその後のどちらでも、任意の時点でセットすること
ができ、そのときプリミティブが構成プリミティブであ
るか否かが決定される。構成プリミティブのラベル付け
は、オブジェクトのソリッド表現の処理効率を高めるこ
とができる。というのは、それによりスペースまたはボ
クセル（ＶＯＸＥＬ）を「空」または「充填」として記
述することが可能となり、そのとき非構成表面がそのボ
クセル内に含まれていないと判断される。

慣用的なＣ１０細分割論理はボクセル内にプリミティブ
の計数値を保持し、その計数値がゼロになったときボク
セル内の処理が終了する。また、非構成プリミティブの
第２の計数値を追加的に保持することにより、その第２
の計数値がゼロに達したときに処理が停止するようにす
ることができる。

オブジェクト画定論理によって生成されたソリッド表現
を簡単化するための既存の技術を、オブジェクトの空間
表現を生成するためのソリッド表現の処理の前またはそ
の間に使用することもできる。そのような技術としては
、ソリッド表現を決定するデータ構造を簡単化するため
に反復プリミティブまたはプリミティブのコンプリメン
１〜を識別するようにしたものがある。また、冗長プリ
ミティブを識別するための技術として、本出願人に係る
１９８７年１２月１８日付英国特許出願第８７２９６３
０号に記載のものがある。

本発明に従うオブジェクト画定発生器と、それを組込ん
だソリッド・モデリング・システムは、パーソナル・コ
ンピュータや、ホスト処理システムなどの汎用コンピュ
ータを適宜プログラミングすることにより、実施するこ
とができる。その場合、リスト１ないし５で示した論理
は、適当なプログラミング・コードによって与えること
ができ、ＳＲ８及びＯＤＳなどの記憶素子はシステム・
メモリを適宜構成することにより与えることができる。

そのデータ構造は、場合によっては、オペレーティング
・システムまたはプログラミング言語で管理することも
できよう。このようにすれば、ノード及びポインタの生
成は透過的となる。また。

入城変数と同様に手続内で局所変数を定義することによ
り再帰的手続の呼出を可能ならしめる言語でコンピュー
タをプログラミングすることによって上記論理を実施し
た場合、特に有利にその実施が行われる。

その場合、リストエないし５のめいめいに記述された論
理は、別個の手続として実施し得る。

しかし、本発明は、そのような実施に限定されるもので
はなく、専用プロセッサあるいは汎用プロセッサに使用
される専用アダプタとして実施することもできる。

その場合、上述の１つまたはそれ以上の記憶素子は、デ
ィスクリート記憶のユニットによって提供してもよい。

同様に、上記論理は、その全体あるいは一部を専用論理
回路として与えることができる。

尚、本発明の論理手段が第２図では個別のブロックに分
けられ、またリストエないし５で個別に記述されている
のは、説明の便宜のためであって、本発明に従うオブジ
ェクト画定発生器の別の例では、論理手段の一部または
全体を他の様式で配列することもできよう。さらに、論
理ブロックのうちのあるもので実行される動作は、論理
の他のブロックで代替的にあるいは追加的に実行するこ
とができる。

さらに、第２図においてオブジェクト画定発生器は、オ
ブジェク１−画定処理論理を組込むソリッド・モデリン
グ・システムの一部を形成するものとして図示されてい
るが、必ずしもそのようにしなくともよい。すなわち、
オブジェクト画定発生器は、後でソリッド・モデリング
・システムによって処理するためのオブジェク１−のソ
リッド表示を生成するために単独的に実施することもで
きる。

また、既述のように、本発明に従うソリッド・モデリン
グ・システムの別の例では、ＳＲ８に記憶されるオブジ
ェクトの表面表示が平坦な三角形表面領域に基づく必要
はない。しかし、この場合、構成プリミティブとソリッ
ドの生成と処理はより複雑になると思われる。

Ｆ０発明の効果 本発明は、オブジェク１−の複雑さに拘らず、ソリッド
・オブジェクトのソリッド表現を自動生成することを可
能ならしめるものであって、そのソリッド表現は、オブ
ジェクトの表面表現から慣用的なＣ８Ｇ技術に従い処理
することができる。オブジェクトの境界または表面（サ
ーフイス）表現は、オブジェクトの実物例または設剖図
面をディジタイズすることにより比較的容易に生成する
ことができ、本発明はオブジェクトのソリッド表現のき
わめて容易ならしめるのである。

【図面の簡単な説明】

第１Ａ図は、本発明に従うソリッド・モデリング・シス
テムの機能を説明するために使用されるオブジェクトの
斜視図、 第１Ｂ図は、第１Ａ図の平面図、 第２図は、第１Ａ図及び第１Ｂ図に示すオブジェクトの
表面表示のレコードをあられす図、第３図は、本発明に
従うオブジェクト画定発生器を組込んだソリッド・モデ
リング・システムのブロック図、 第４図は、オブジェクトのソリッド表現のためのデータ
構造の一部をあられす図、 第５図は、第３図に示すオブジェクト画定発生器の動作
を説明するためのペン図、 第６図は、第３図に示すオブジェクト画定発生器の一部
の動作を説明するためのペン図、第７図は、オブジェク
トのソリッド表現のデータ構造の別の部分を示す図であ
る。 出願人　　インターナショナル・ビジネス・マシーンズ
・コーポレーション 代理人　　弁理士　　山　　本　　仁　　朗（外１名）

Claims (2)

【特許請求の範囲】
1. （１）オブジェクトの個々の表面領域に基づき且つオブ
   ジェクト空間中の共通基準データに関連して画定された
   構成ソリッドの対称差として、オブジェクトのソリッド
   表現を形成するためのオブジェクト画定論理手段を含む
   ソリッド・モデリング・システム。
2. （２）オブジェクトの個々の表面領域に基づき且つオブ
   ジェクト空間中の共通基準データに関連して画定された
   構成ソリッドの対称差として、オブジェクトのソリッド
   表現を形成する段階を有する、ソリッド・モデリング・
   システムのためのソリッド表現の生成方法。