JPH04111173A - 図形表現方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔産業上の利用分野〕 この発明は、図形を境界線分の並びにより、境界線分を
その線分の始点と終点によって表現する、いわゆる境界
表現（Ｂｏｕｎｄａｒｙ　Ｒｅｐｒｅｓｅｎｔａｔｉｏ
ｎ）による図形表現方式に関するものである。

〔従来の技術〕

境界表現は、現実に存在する設計対象物を忠実に表現す
る手段として広く使われてきた［例えば、ｆｌ）　Ｍ、
Ｍａｎｔｙｌａ著Ａｎ　１ｎｔｒｏｄｕｃｔｉｎ　ｔｏ
　５ｏｌｉｄ　ｍｏｄｅｌｉｎｇ、　Ｃｏｍｐｕｔｅｒ
　５ｃｉｅｎｃｅ　Ｐｒｅｓｓ　１９８８、（２）特許
出願公開、昭６１−２７９９８３．図形処理システム、
（３）特許出願公開、昭６２−１０５２７１．対話形形
状モデリングシステム］。境界表現では、２つの面の交
わりによって境界線分が作られるという考えから、隣接
する線分の順序づけられた並び（リング）によって面を
表現し、境界線分はその線分の始点と終点によって表現
している。境界表現には、現実の物と境界表現の基本要
素との対応が直怒的に理解しやすいという利点がある。

例えば、建築物の間取り図を境界表現によって表現した
とき、部屋は面に、壁は線に、柱は点に対応する。第１
２図は、第１１図に示した図形を境界表現で表したもの
である。

従来技術である境界表現の動作を第１３図に示した。こ
こで述べる動作１ま、図形を記憶するための図形データ
記憶卸域と、追加する図形を一時的に蓄えるデータ入力
領域を使っている。

まず、ステップ４．０１で図形データ記憶領域を初期化
する。次に、ステア・ブ４．０２てデータ入力の終了記
号が入力され１こかとうかを判定する。データ入力の終
りでなければ、ステップ４０３でデータ入力領域を初期
化し、ステップ４０４で入力しようとする面の名称およ
び境界線分データをブタ入力領域に記憶する。ステップ
４０５は図形データ記ｔａ領域内のすべての線分り、と
、データ人力領域内のすべての線分Ｌｎに対し、ステ、
プ４０６．４０７，４０８．４０９の処理をするように
制御している。ステップ４０６では、線分ＬＦと線分り
。が重なり合うかどうかを判定している。もし重なり合
わないのであれば、次の線分を処理の対象にするための
ステップ４０５の処理にもどる。もし重なり合うのなら
、ステ、プ４０７で線分Ｌ　、と線分り、の重なり合う
部分（線分Ｌｃ）を取り出し、独立した線分として図形
データ記憶領域に記憶する。続いて、ステップ４０８で
線分ＬＦから線分り。を引いた部分を新たな線分り、と
して図形データ記憶領域に記憶する。ステップ４０９て
は、線分り。から線分り。

を引いた部分を新たな線分り、とじて図形データ記憶領
域に記憶する。以上の処理を、図形データ記憶領域内の
すべての線分ＬＰと、データ人力領域内のすべての線分
１−Ｄに対して実行したら、ステップ４１０の処理でデ
ータ入力領域内のすべてのデータを図形データ記憶領域
に追加する。

例えば、第１４図の図形を定義するときは、まず面Ａ１
の名称とこの面の境界となっている線分Ｌｌ、Ｌ２．Ｌ
３．Ｌ４を入力する。このとき、図形データ記憶領域は
初期化され、何も記憶されていないので、ステップ４０
５，４０６，４０７４０８．４０９では何も処理されず
、ステップ４１０の処理で面ＡＩに関するデータは図形
データ記憶領域に移される。続いて、面Ａ２の名称とこ
の面の境界となっている線分Ｌ５．Ｌ６．Ｌ７Ｌ８．Ｌ
９を人力する。今度は、図形データ記憶領域に面Ａ１に
関するデータがあるので、ステップ４０り、４０６，４
０７．４０８．４０９の処理が行われる。第１４図の図
形の場合、線分Ｌ２とＬｌが重なり合っている。重なり
合っている部分はステ、プ４０７で独立した線分として
図形ブタ記憶領域に追加される（第１４図ではＬｚｂと
いう名称になっている）。元の線分Ｌ２とＬｌは、重な
り合った線分Ｌ２ｂの部分をそれぞれ取り除き、線分Ｌ
　２ａ＋　　Ｌ　７ｂとして再定義される。その後、ス
テップ４１０の処理が行われ、図形データ記憶領域には
第１５図に示したデータが格納される。

〔発明が解決しようとする課題〕

従来の境界表現方式では、領域の追加定義により、隣接
する領域にも影響が及ぶという問題点があった。例えば
、第１１図に示した間取り図で、第１４図に示したよう
に、部屋Ａ２を追加定義すると、すでに定義されている
部屋Ａ１に次のような影響が及ぶ。

（１）本来１枚であった壁Ｌ２が２分割される（第１４
図ではＬ２□とＬ２．）。

（２）この結果、本来４枚の壁で囲まれている部屋Ａ１
を、分割された壁ＬｅａとＬｚｂ、Ｌ３．Ｌ４．Ｌｌの
５枚の壁によって囲まれていると表現せざるを得ない。

同様に、本来５枚の壁で囲まれている部屋Ａ２を、分割
された壁Ｌ７ｂとＬｚｂ、　　Ｌ８．　　Ｌ９、Ｌ５．
Ｌ６の６枚の壁によって囲まれていると表現せざるを得
ない。

ある壁の裏側に、新しい部屋を付けたために、既存の壁
が分割されてしまうようなことは、現実の間取りに対応
づけて解釈すると不都合なものである。上記のような影
響は、境界表現における線分が数学的な意味での線分で
あり、建築物における壁のように表側、裏側という区別
がないために起こるものである。

従来の境界表現をそのまま用いた場合、部屋ＡＩから見
た場合、壁Ｌ２ｍとり、ｚｂを合わせて一枚の壁を構成
しているようにデータ構造を変換する処理が必要になる
。同様に、部屋Ａ２から見た場合、壁Ｌ７ｂとＩ−ｚｂ
を合わせて一枚の壁を構成しているようにデータ構造を
変換する処理が必要になる。このような処理は、データ
の一貫性を保っｆコめの処理を複雑に、かつ非効率にす
るという問題を発生する。

本発明は、上記のような問題点を解決するためになされ
たもので、境界表現における線分に、表側と裏側を判別
する手段を導入し、線分の表側と裏側を独立に分割でき
るようにすることにより、例えば建築物の間取り図にお
ける壁のような現実の物を、計算機上に忠実に表現する
ことを可能にする境界表現方式を得ることを目的とする
。

〔課題を解決するための手段〕

この発明に係る図形表現方式は、線分の表側と裏側を判
別し、また線分に対する分割処理が表側に対するものか
裏側に対するものかを判別する判別手段（線分表裏判別
部１４）と、この判別手段で判別された線分の表側と裏
側の分割状態情報を別々に記憶する記憶手段（図形デー
タ記憶領域１７）と、上記分割状態情報に基づいて表側
と裏側を独立に分割できる線分を用いて図形を表現する
図形モデル化手段（表裏線分図形モデル管理部１５）と
を備えたものである。

：作用： 判別手段（線分表裏判別部１４）は線分の表側と裏側を
判別し、また線分に対する分割処理が表側に対するもの
か裏側に対するものかを判別する。

記憶手段（図形データ記憶領域１７）！、：Ｊ−記判別
手段で判別された線分の表側と裏側の分割状態情報を別
々に記憶する。図形モデル化手段（表裏線分図形モデル
管理部１５）は上記分割状態情？［５こ基づいて表側と
裏側を独立に分割できる線分を用いて図形を表現する。

〔実施例〕

第１図はこの発明の一実施例に係る図形表現方式の構成
を示すブロック図である。第１図において、１１はデー
タを入出力する入出力装置、１２は図形処理などを行な
うＣＰＵ　（中央処理装置）、１３は図形処理に必要な
データを格納する主記憶装置、１４はＣＰＵＩ２内に備
えられ線分の表側と裏側を判別し、また線分に対する分
割処理が表側に対するものか裏側に対するものかを判別
する判別手段としての線分表裏判別部、１５は同じくＣ
ＰＵ１２内に備えられ下記分割状態情報に基づいて表側
と裏側を独立に分割できる線分を用いて図形を表現する
図形モデル化手段としての表裏線分図形モデル管理部、
１６は主記憶装置１３内に備えられ入出力装置１１から
人力された図形ブタを一時的に記憶するデータ入力領域
、１７は同しく主記憶装置１３内に備えられ線分表裏判
別部１４で判別された線分の表側と裏側の分割状態情報
を別々に記憶する記憶手段としての図形データ記憶領域
である。線分表裏判別部１４は線分の表側と裏側を一定
の基準に従って判別する。表裏線分図形モデル管理部１
５は線分表裏判別部１４の判別結果を参照しながら図形
モデルを構成して行く動作を規定する。図形データ記憶
領域１７は最終目標となる図形データを記憶する。デー
タ入力領域１６に記憶されている図形データと図形デー
タ記憶領域１７に記憶されている図形データとの重なり
合いく干渉）処理をした後に、データ入力領域１６のデ
ータが同形データ記憶領域１７に追加されて行く。この
ようにして、最終目標となる図形データが逐次に構成さ
れて行く。

第２図は、第１図中の線分表裏判別部１４の処理を示す
フローチャートである。この線分表裏判別部１４は、線
分の端点の座標（ｘ＋　、ｙ＋　）（ｘｚ、ｙｚ）と、
この線分の表側にあるか裏側にあるかを判定したい点（
Ｘｌｌ、ｙ３）を入力とし、表側のとき１．裏側のとき
−１を出力値としている。ステップ７０１は、線分の表
側と裏側の判定をしている処理である。判定の基準は、
点（Ｘ３．ｙ３）が線分の正の領域にあるとき、点（Ｘ
３．ｙ３）から見える側を表側（あるいは、点（Ｘ：＋
、ｙ３）が線分の表側にある）と判定している。一方、
点（ｘ：＋、ｙ：＋）が線分の負の領域にあるとき、点
（Ｘ：＋、ｙ３）から見える側を裏側（あるいは、点（
ｘ３．ｙｚ）が線分の裏側にある）と判定している。ス
テ、プ７０２では、点（Ｘ：ｌ、ｙ３）が、線分の表側
にある時に実行され、値１を返す。ステ、プ７０３では
、点（Ｘ：＋＋ｙ３）が、線分の裏側にある時に実行さ
れ、値−１に返す。

第３図は、線分を記憶するためのデータ構造を示してい
る。本実施例における線分は、２種類ある。つまり、表
側と裏側を独立に分割できる線分と、分割された表側ま
たは裏側を表現する線分である。前者の意味での線分を
単に゛′線分”と呼び、後者の意味での線分を“要素線
分”と呼ぶことにする。第３図（Ａ）は線分を記憶する
ためのデータ構造を示している。線分の表側と裏側を任
意価の要素線分に分割できるよう、“表リンク”と“裏
リンク”の２種のリンクを記憶できるようにし、た。線
分の分割がないときはｎｉｌ値が入るものとする。第３
図（Ｂ）は要素線分を記憶するためのデータ構造を示し
ている。要素線分は、線分を分割した一要素であるので
、他の要素線分へのリンク（要素リンク）を用意した。

線分と要素線分は共に、面の構成要素に成り得るので、
面を表現するリング構造を辿るためのリンク（リング・
リンク）を備えている。一方、識別名と定義パラメータ
は、線分と要素線分のどちらにも必要になる。

第４図はエツジの表側を３分割し、裏側の分割がない線
分を表している。第５図は、第４図の線分を表現したデ
ータ構造を示している。

第６図は表側と裏側を独立に分割することができる線分
を用いた図形の境界表現の動作を示したフローチャート
である。データの入力のために図形データ記憶領域とデ
ータ入力領域を使っている点、およびデータ入力の終り
を判定する処理は第１３図に示した従来の境界表現処理
と同じであるが、ステップ４０５によって制御される線
分の分割処理が異なる。

第７図および第８図は、線分の分割パターンを分類した
ものである。図中り、は図形データ記憶領域内に定義さ
れている線分で、Ｌ、はデータ入力領域内に定義されて
いる線分である。第７図は、線分Ｌｐ’の表側を線分Ｌ
ＦａとＬＦｂに分割し、線分り、の裏側を線分ＬＤａと
ＬＤｂに分割する場合を示している。一方、概念的には
、２本の線分であるＬＦｂとＬＤａが、同一の線分であ
ることを表現するためには次のようにする。まず、どち
らか一方の要素線分記憶領域のみを残す（第９図のデー
タ構造ではＬＦｂを残しでいる）。次に線分り、とり。

からこの要素線分記憶領域をリンクで繋ぐ。同一の線分
に対して、一つのデータ構造のみを容易することにより
、データの一貫性管理を容易にしている。第９図は、第
７図に対応するデータ構造を示したものである。第８図
は、線分ＬＦの裏側を線分り、の表側で分割する場合を
示したものであり、この分割によって作られるデータ構
造の一例を第１０図に示した。

第６図のステップ１１０１は、第７図に示した分割パタ
ーンを判別するものであり、ステップ１１０３はこの分
割パターンに対する処理をする。

第６図のステップ１１０２は、第８図に示した分割パタ
ーンを判別するものであり、ステップ１１０４はこの分
割パターンに対する処理をする。

なお、上記の実施例では、線分の表側と裏側を判別する
ために、直線の方程式を用いたが、線分の表側と裏側を
一意的に判別できるものであれば良く、第２図のような
処理に限られるものではない。また、線分の記憶するた
めのデータ構造も、線分の表側と裏側の分割を独立に記
憶できるものであれば良く、第３図のデータ構造に限ら
れるものではない。さらに、本実施例では、線分として
直線のみを扱っていたが、円弧、楕円弧、自由曲線など
であっても、表側と裏側を判別できるものであれば良い
。

〔発明の効果〕

以上のように本発明によれば、境界表現における線分に
対する分割処理が表側に対するものか裏側に対するもの
かを判別しつつ処理を行い、かつ、線分の表側と裏側の
分割状態情報を別々に記憶し、その分割状態情報に基づ
いて表側と裏側を独立に分割できる線分を用いて図形を
表現するようにしたので、線分の表側と裏側を独立に分
割できるようになり、例えば建築物の間取り図における
壁のような現実の物を、計算機上に忠実に表現すること
が可能になるという効果が得られる。即ち、従来方式で
は線分あるいは面の追加定義を行うと、現実の物との対
応が付かないデータ構造の変更が必要になり、データの
一貫性維持のために特別な処理が必要であったが、本発
明によれば、線分あるいは面の追加定義に対して、現実
の物との対応が明解であり、かつ、データの一貫性維持
のために特別な処理を用意する必要がないという効果が
得られる。

【図面の簡単な説明】

第１図はこの発明の一実施例に係る図形表現方式の構成
を示すブロック図、第２図は第１図の線分表裏判別部の
処理を示すフローチャート、第３図はこの実施例におい
て線分を記憶するためのデータ構造を示す図、第４図は
この実施例において説明される図形を示す図、第５図は
第４図に示した図形をデータ構造によって表現した図、
第６図は第１図中の表裏線分図形モデル管理部の処理を
示すフローチャート、第７図および第８図はこの実施例
において線分の分割パターンを示す図、第９図は第７図
の線分の分割パターンに対応するデータ構造を示す図、
第１０図は第８図の線分の分割パターンに対応するデー
タ構造を示す図、第１１図は従来の図形表現方式を説明
するための図形を示す図、第１２図は第１１図に示した
図形を従来の図形表現方式によって表現した図、第１３
図は従来方式の処理を示すフローチャート、第１４図は
従来方式を説明するための図形を示す図、第１５図は第
１４図に示した図形を従来方式によって表示した図であ
る。 １４・・・・・・線分表裏判別部（判別手段）、１５・
・・・・・表裏線分図形モデル管理部（図形モデル化手
段）、１７・・・・・・図形データ記憶領域（記憶手段
）。 代理人　　弁理士　　宮園　純− （Ａ７線分 （３）早Ｉ麹け 第１３図 手 乃）Ｃ 袖 正 書（自発） 平成 ３年 ７月 口 持Ｊ′「庁長官殿 １、事件の表示 特願平２ ２３０９４５号 一？ｑ 二二二二」 ３、補正をする者 名 称 （６０１）三菱電機株式会社 代表者　志　岐　守 哉 ４゜ 代 理 人 補正の対象 明細書の発明の詳細な説明の欄。 補正の内容 （１）明細書第１３頁第６行目 「容易」 とあるのを 「用意」 と補正する。 以 ｌ二

Claims (1)

【特許請求の範囲】
1. ２次元図形を、その図形の境界となっている線分の隣り
   合う順に並べた列によって表現し、各々の線分を、その
   線分の始点と終点を結ぶものとして表現する図形表現方
   式において、線分の表側と裏側を判別し、また線分に対
   する分割処理が表側に対するものか裏側に対するものか
   を判別する判別手段と、この判別手段で判別された線分
   の表側と裏側の分割状態情報を別々に記憶する記憶手段
   と、上記分割状態情報に基づいて表側と裏側を独立に分
   割できる線分を用いて図形を表現する図形モデル化手段
   とを備えたことを特徴とする図形表現方式。