機能パターン設計システムの一提案

機能パターン設計システムの一提案

宮 崎 敬

One Efficient Functional Oriented  Pattern Design System

Takashi MIYAZAXI

Recently,inusingCAD andCAM,morehumanfriendlygraphicsystem isoften required.Soitmusthaveadatastructurethatitisfasttoretrieveaplain丘guredata.

Wealreadyappliedthedatamanagementstructures,namedthelayerBD･treeandthe uni丘cationBD･tree.Weexaminedtheeだiciencyoftwodatastructures,thentheformer provedtobefast.SothispaperproposesoneIC‑CADsystemwithit.

1. は じ め に

最近,図形処理や コンピュータグラフィック分野の研究が盛 んにな り,また,高解像度 デ ィスプレイ装置の低価格化,グラフィック関連機器のメモ リの増大,そ してマ ウスや タ ッチ パネル等の対話性の良い座標指示装置の普及等に ともない,CAD,地理情報処理お よび自 動図面入力 の分野で対話性 の長いグラフィックシステムが強 く求め られている.図形 データ 処理の対話性を向上 させるためには,効率の長いデータ管理構造 とそのデータ構造上 での検 索や処理性能が重要 となる.す なわち,ある問題 に対 してデータ構造を検索 し検出す るのに 要する検索時間やデータ管理構造を構成するのに要す る前処理時間および動的なデータ環境 に対 して一つのデータを投入 ･削除す るのに要す るデータ構造の更新時間が短い ことが必要 である.また,データ構造 を管理す るのに必要なメモ リ量が少ない ことが必要 となる.

また,対話性の良いグラフィックシステムで重要な要素には,ある範囲を指定 してその範 囲内にある図形データを拡大表示 した り,その範囲内の図形データに対 して処理を施す機能 早,座標指示装置を用いて処理対象の図形データを直接ではな くその近傍点 を指 し示 し的確 な所望 の対象図形データの指示を高速に行 うことができる機能が上 げられる. これ らの空間 的位置関係 に基づ く検索においては,平面上における図形データと指 し示 された範囲や点 の 位置関係が重要 となる. このため,対話性の良いグラフィックシステムでは,図形デ‑タの 空間的位置関係に基づ く検索に適 したデータ管理構造が必要 と考 えられ る.

従来から,空間的位置関係に基づ くデータ管理構造 としては,対象平面を縦 ･横で等間隔 にn等分を行い,近 くにある要素をブロック化 して2次記憶上 に蓄積 し管理す る方法等が提 案 されている(1)(2).しか し,図形データの遍在や動的環境下での検索効率の低下が指摘 され

●昭和61年3月 電子通信学会総合全国大会において一部発表 日 電気工学科 講師

原稿受付 平成3年9月30日

32 宮 崎 敬

ている. これ らの欠点を改良 し空間的位置関係に依存 した検索 に適 したデータ管理構造 とし てBD木構造 が提案 されている(3)(4).BD木構造では,縦 ･横 とい う順 に2等分割 を繰 り返 し,分割領域 を ｢領域式｣ と呼ぶ領域表現を用いることにより2分木を構成 し管理す るデー タ管理構造であ り,多次元情報管理のために開発 されたものである.

本論では, この良好 な検索効率 をもつBD木構造 を図形 デ‑タ管理 に用いたIC‑CADシ ステムについて提案す る.

2. BD木構造による図形データの管理 2‑ 1 図形データの管理

BD木構造 には,図形データを一括 して一つのBD木構造上で図形 データを管理す る一括 型 と,図形の種類や属性 をもとに種類毎や属性毎 にBD木構造で管理するレイヤー型 とがあ る(5).BD木構造で重畳関係 にある多種類 の図形 データを管理す るような場合 には,重畳す る斑形 データを分 けて管理す るレイヤー型 の方が有利 である(6).従 って,今 回のIC‑CAD

システムではICの各層 (レイヤー)毎 にデータ構造 を持つ レイヤ‑型BD木構造 を取 り入 れている. このデータ構造を用いると,数種類のレイヤーの重畳か ら構成 され る素子部分な どを検索する場合,その使用 されているレイヤーの図形データのみ,その重畳関係 に基づい た検索を行えば良いことになる.

図形データの最小単位 は各部分ノミクーソの多角形 としている.木構造の葉 ノー ドで管理す る情報 としてはこの単位 となる図形データの各頂点座標 と, この図形 データに外接す る長方 形お よび長方形の中心座標である.外接長方形の情報 については,次節で説明する.木構造 の構成 には, この外接長方形の中心座標から得 られる ｢領域式｣を用いる.また,各 ノー ド には各々の子 ノー ドの外接長方形に外接す る長方形の情報を階層的に持たせてある. このた め複雑 な図形データの領域 もその概形が容易に把握で きる管理構造 となっている.

空間的位置関係 による処理対象の検索 としては,指定点 に最 も近い図形データを検出す る 最近図形検索,ある範囲内の全図形デ二タや特定の図形データを検出する範囲検索,お よび 図形データ間の重畳関係を検出す る重畳図形検索がある.

最近図形検索 は削除や位置確認のために,範囲検索 は複写や拡大 ･縮小のために,重畳図 形検索は重畳パ ターンの検出のために利用 される.最近図形検索では,指定点が含 まれる外 接長方形を領域式 による演算で求め,得 られた第一候補 との距離を基 に範囲検索を行 いなが ら戻 るため効率良い検索が行われる.範囲検索 は指定 された矩形 とデータ構造上に持た され た外接長方形 との重複検査 により,検索が階層的に効率 よく進め られ る.重畳図形検索では, 範囲検索の指定 された矩形の代わ りに図形データの外接長方形を基に範囲検索 と同様 に効率 長い検索が進め られる.

2‑ 2 データ構造の作成

図1の場合 について, どのようにt/イヤ‑型BD木構造が作成 されるか説明する.図1は

CMOS･NAND回路2個 のICパターン図を示 した ものである. レイヤー型では初めにIC

パ ターンの各層をレイヤーとして登録 (最大64層まで) してお き,各 レイヤーに分配 し各 レ イヤー毎 にBD木構造 の作成 にはいる.図 1で は(a)メタル層,(b)n+ポ リシ リコン層,(C)

p+拡散層お よび(d)n+拡散層の4層からなるため4つのBD木構造がで きることになる.

0G HP

図1 CMOS･NAND回路 のIC バ ク ‑ ソ図 図4 一括型 に よるBD木構造

d h

E 也A BH FC D (a) メタル層 のBD木構造

√入

(b) n+ポ リシ リコン層 (b) n+ポ リシ リコソ層のBD木構造

r=?.二二!= 聖 二

N 〜

ll (C) p+拡散層

よ1 (d)n+拡散 層

図2 各層のバターソ図

M

/＼

/ へ

O P

(d) n+拡散層のBD木構造 図3 作成 された各層のBD木構造

34 宮 崎 敬

図2の(a)から(d)に各層に分離 した′くターン図を示す.図2(a)の図形データをAか らH,その 各図形データの外接長方形の中心座標 をMAか らMHとす る.BD木構造 における領域分割 方法 は, まず,対象平面を2分割を行 ってい く段階で,Y軸お よびⅩ軸 に平行 な軸で2等分 割 されてできる領域 の左側お よび下側領域 を ｢0｣,右側および上側領域 を ｢1｣ とした2

進符号系列表記をしなが ら分割 して行 く方法である.そ して符号 の最後 には終了符 として

｢*｣を付けることにしている.従 って,(a)の場合にはⅩ1軸 で分割が行われ,続いてYl

軸,x2軸,そ してⅩ3軸により分割が進められる.最終的に各図形データの中心座標が各 領域 に一つずつになるまで分割が行われるので,できる分割領域は8個 になる.例 えば,A を含む領域はⅩ1軸,Yl軸,そ してⅩ2軸で分割が行われるので ｢010*｣ とい う符号列 で表わされることになる.以上の分割によ り作成 されたBD木構造を図3(a)に示す.

次 に,図2(b)の図形データを Ⅰか らL,外接長方形の中心座標をMIか らM^Lとす る.BD 木構造作成のための分割 はⅩ1軸,x2軸,そ してⅩ3軸で行われる.その結果を図3(b)に 示す.

同様 に,図2(C)と(d)については,図形データをM,Nお よび0,Pとし,その外接長方形 の中心座標をMM,MNおよびM｡,MpとしてBD木構造 を求めると,図3(C)お よび(d)とな る.両方 とも分割 はXl軸 による1回だけで終 る.

次 に各木構造のすべてのノ‑ ドに対 して,各 ノー ドを根 とす る部分木中に含 まれるすべて の図形データに外接する長方形を作 り, この長方形の位置 と大 きさの情報を部分木の根 ノー ド (親 ノー ド) に持たせてある.従 って,葉 ノー ドにおいては,対象 となる1つの図形デー タの外接長方形の情報が ノー ドに記憶 され ることになる. また,根 ノー ド(ルー D には木 構造 に含 まれ るすべての図形データに対 して設定 された外接長方形が記憶 され る.土の外接 長方形は具体的には外接長方形の対角線の両端点,すなわち左下隅および右上隅の2点の座 標で示 される.以下に ノー ドのデータ型を示す.

Structnode(Structnode●left,事rigth;/●左右子 ノー ド‑のポイソタ '/ longintreg; /● 領域式 '/

intxs,ys,Xe,ye;) /●外接長方形の座標データ '/

参考のため,図4には一括型 のBD木構造による場合のデータ構造を示 してお く. この場 合 には上記のデータ型 にレイヤーの種類 まで持たせる必要があ る.

3.システムの編集機能

図5に本システムの構成 を示す.本 システムはデータゼネラル社 のMV/4000を中心 とし て,マ ウス操作 による編集作業 が主体 となるシステムである.開発言語 はUNIX‑OS上 の

C言語 によるものである. また,表示には1024×1024のフルカラーデ ィスプレイを持 ち,出 力機器 としてはMT装置, フロッピィ装置,Ⅹ‑Yプpッタお よびプ リソタを持つ ものであ

る.

システムの編集画面を図6に示す.編集作業領域 は400万×400万画素で, レイヤー数 は最 大64個が可能である.編集用の コマン ドとしては,大 きく分けて次 の5種類である.

① 作画 ･修正 コマン ド:ICパ ターソの作画,修正,削除および追加等を行 う.

② 画面 変 換 コマ ン ド :表示 されているICバ ク‑ソの拡大,縮小お よび回転操 作を行 う.

③ 確認 ･解析 コマン ド:マウスカーソルの位置す るレイヤーの確認お よびt/イヤ ーの重畳関係の確認を行 う.

④ 入 出 力 コ マ ン ド :ICパ ターン図のMT装置や フロッピィ装置 との入出力 およびX‑Yプ ロッタへの出力

⑤ 回路検 証 コマ ン ド :作成 されたIC,(タ‑ソ図が禁止項 目に該当 しないか調 べる.

本 システムの特徴 は,図形データをBD木構造上で管理す ることにより処理対象の図形デ ータを高速 に検出できた り,直接ではな く近傍を指示す るだけで検出できるといった操作性 において,マン ･マシソ ･インターフェースを良 くした点にある.また,図形データ間の重 畳関係により機能素子を表すパ ターソの検出が容易である点 も上 げられ る. なお,⑤ につい

ては現在開発中である.

レイヤー暮す コマンド

1 1

属 [ □

マウス X‑Yプロッタ MT裳荘 フロッピィ装3(

図5 システムの構成 メッセージ表示^I

図6 システムの編集画面

4.検索効率の性能

IC‑CAD等で扱 う図形データは部分的に非常に大 きかった り,広い範囲に複雑 にまたがっ ていた りす る特殊 な形状 のものが含 まれ る.BD木構造では外接長方形が図形データの概形 を把握するのに利用 されているため, これらの図形データが各検索に与 える影響 は大 きい と 考えられる.各検索の性能を一括型 とレイヤー型 とで考 えた場合,最近図形検索 と範囲検索 では現在編集中か表示されている場合に行 うことが多いので,つま り, どの レイヤーか明確 なため レイヤ‑型の方が検索効率が長い と考 えられる. しか し,重畳図形検索の場合 にはレ イヤーが指定 されないで検索の必要な場合もある. このため どちらの型が有効か明確でない ため,図7の図形データ用いて,各型の効率を次 のような測定 により評価す ることにした.

4‑1 測定方法

36 宮 崎 測定 に用いる図形データとして図7に示す 形状 のものを用意 し,それぞれ Ⅰ型,L型,

Z型およびN型 と名付けた. これ らの図形デ ータの外接長方形の中心座標を疑似乱数 によ り8000×8000の2次元空間に500個発生 させ, また,図形データの種類 も疑似乱数によ り決 定 した.

図形データの大 きさは表1に示す ようにA

敬

‑ = 二 : ‡ ≡ ‡

エ聖図形データ

Z聖固形データ

≡ : : = ≡ : ≡:

L型EgZ形データ N聖Eg形データ

図7 測定に用いた図形データの形状 表1 測定に用いた図形データの資料

図 形 デ ー タ 群 A B C D E F G 図 形 数 500 500 500 500 500 500p 500 平均図形面積 23176 30013 39007 49978 30572 70854 80962 平均外接長方形面積 45056 66816 97408 137728 178688 220160 262144 平均フイット率 (%)I) 51.40 44.94 40.02 36.30 33.91 32.19 30.88 図形の重なり度2) 0.181 0.234 0.305 0.390 0.473 0.554 0.633 外接長方形の重なり度³⁾ 0.352 0.522 0.761 1.076 1.396 1.720 2.048 1) [フイット率]‑ 外去誤 認 積】 2)[図形の重なり度]‑ E堅塁諾 諾 3) [外接長方形の重なり度]‑ [総篭 誤 認 郡

か らGまでの7段階に変化 させた.測定 の内容 は次 に示す.

(9 1種類 の図形データを指定 し,木構造 よ りその図形データすべてを検索 した とき の検索時間.

② 4種類 の図形データか ら2種類を選 び (全部で16通 りの組合せ),その重畳関係 を持つ図形データの検索 した ときの検索時間.

③ 4種類 の図形 データか ら3種類を選 び (全部 で64通 りの組合せ),その重畳関係 を持つ図形データの検索 した ときの検索時間.

なお,今回の測定 にはデータゼネラル社のMV/4000を用い, プpグラムはC言語で記述 している.

4‑ 2 測定結果 と考察

測定結果を図8に示す.図中の(彰〜③ は測定項目の番号を表 している.(丑の1種類の図形 データを指定 した場合,検索時間にほとんど変化はみ られない. これは一括型BD木におい ては全体の木構造 を探索 し指察 された種類の図形データであるかの判断を行 うだけであ り, レイヤー型BD木 においては指定 された種類の図形 データの木構造を探索す るだけであるた め,図形データの重な り.外接長方形の重 な りおよび図形データのフイット率の影響をまっ た く受けないためである.

(卦の2種類の図形データを指定 しその重畳関係を持つ図形データを検索す る場合,お よび

③ の3種類の図形データを指定 しその重畳関係を持つ図形データを検索する場合 は図形デー

1 2 3 4 回形の重なり度

(a) .02(S)nJ世搬井野浄 0

1 2 3 4 5

外接長方形の土なりJl

(b) 図8 重畳図形検索における性能測定結果

クの重 な りが増加す る,あるいは外接長方形の重 な りが増加するほど検索時間は増加 してい る. また,(卦よ り(卦の方が検索時間の増加する割合が大 きい.重畳図形検索では図形の重 な り,外接長方形の重 な りおよび図形データのフイット率の影響を強 く受けることがわかる.

これは,重畳図形検索が範囲検索を基礎 としている (今回の測定では外接長方形の一辺 は対 象空間の一辺の2.7%〜6.4%に当たる)ため と考 えられる. このように重畳図形検索 の よう な狭い範囲での範囲検索を何度 も繰 り返す ような検索の時,外接長方形の重複部分 の増加 が 検索性能の低下を招 くことになる.

また,一括型BD木構造 とレイヤー型木構造を比較す ると,一括型の方が検索時間が大 き く増加 してお りレイヤー型の方の割合が小 さい.重畳図形検索においては,一括型木構造 よ りもレイヤー型木構造の方が,無効 な図形データの重な りや外接長方形の重 な りの影響 を受 けに くいため検索性能が良好であると言える.

5.む す び

本研究では,対話性の長い コンピュータグラフィックシステムの構築 を目的 として,空間 的位置関係 による効率の長いデータ管理構造 として提案 されているBD木構造 の導入 を試み た. また,BD木構造では一括型 とレイヤー型 とがあるが,今回のIC‑CADのように図形デ ータ間の重畳関係が機能を持つ ような場合 にはどちらの方が重畳図形検索において有効 かを シ ミュレーション実験 により調べた.その性能測定の結果, レイヤー型 の方が有効 であ るこ とがわかった. また, このデータ構造の導入 によ り各検索において演算 コス トの高い計算部 分を大幅に減少 させているため,人間の座標指示 に要す る時間に比べ検索時間 も無視で きる 程度で,CAD等のグラフィックシステムへの応用 には十分 な性能 と考 えられ る. さらに一 括型 とレイヤ‑型 とそれぞれ長所 ･短所があるため,用いるグラフィックシステムに合わせ て選択することによりより良い性能のグラフィックシステムが構築できると思われ る.

38 _{宮 崎 敬}

謝 辞

本研究 を行 うにあた り御 指導頂 きました東京大学生産技術研究所 の坂 内正夫教授お よび大 沢裕助手 (現在埼玉大学助 教授) に深 く感謝 申 し上 げます. また,実験 の際 に御協力頂 いた 信州大学大学院生 の松本健志君 (現在三洋電気株式会社) に感謝 いた します.

参 考 文 献

(1)笠原,他 : ｢地理情報 システ ムとその応用｣,グラフィックスとCADシグポジウム予稿集, pp.59‑66,1983.12.

(2)大金''｢公益事業における地理情報データベース｣,電気学会情報工学研究会資料,Ⅰp‑8ト4, PP.33‑42,1981.

(3)大沢,坂内 : ｢良好 な動特性を持つ多次元点データ管理構造の一提案｣,信学論 J66‑D,No.

10,1983.10.

(4) 大沢,坂内 :｢2段階の木構造による領域情報管理方式｣,信芋論 J67‑D,No.4,1984.10.

(5)宮崎.大沢,坂内 : ｢多次元′(ターン管理構造の図形管理‑の応用｣,長野高専紀要,第18号, 1987.I.

(6)宮崎 : ｢図形管理におけるBD木の性能評価｣,長野高専紀要,第19号,1988.12.