CADのための基本立体図形の生成
古川進
（昭和53年8月28日受理）
Algorithms Generating Primitive Objects for CAD
SusumuFURUKAWA
Abstract Algorithms to construct the data structure of various primitives are discussed， as the first step to making the objects of desirable forms in computer aided design（CAD）process． And some figures drawn by computer are illustrated．1．緒
言 計算機援助型の設計（ComPuter Aided Design）シ ステムにおいては，人がイメージとして持っている図 形を計算機の中に組み立ててゆくための手段を備えて いることが必要である。 この問題に対しては，基本的には図形の形状に関す る情報をあらかじめ定められた内部構造に従って計算 機に入力すれば良いのであるが，この作業は，入力し ようとする図形の形状が比較的単純な場合でも，相当 に複雑である。したがって，単純な形状の立体図形に 対しては，計算機内で自動的にその内部データ構造を 組み立ててゆく方法を開発しておくことが必要であ る。 このような目的のために，1．C・Braidらは6種類 の基本立体図形を選び，それらに対しては，それぞれ 一つのコマソドを与えるだけで生成することのできる 図形処理システムを開発した1）。またB．G． Baumgart は基本図形として，直方体，（近似的な意味での）球， 柱体，トーラスなどを発生するプログラムをその内部 に含む図形処理言語を開発した2｝。この方法は基本的 には2次元図形の移動により，立体図形を生成しよう とする考え方に基づいたものであり，所望の図形は人 がつぎつぎに与えた指令を実行した結果として実現さ れる。さらに出沢は，最初三面図の形式で与えられた 図面を読み取る装置を開発し，それから自動的に内部 データ構造を組み立ててゆくといった方式を開発し た3）。ただ特別の場合として，三面図のみでは，立体 図形を一意に定めることができない場合が考えられる が，このときは副面図を考慮する4）とか，あるいは人 が介入して指示するという方法を採用することが必要 である。さらにその後，人が自分自身のイメージを立 体視するという考え方にもとついて，2次元図形から 3次元図形を組み立ててゆくという方向に発展させて いる5）。 穂坂らは最初8種類の基本立体図形を生成すること のできる図形処理システムを開発した6）が，その後， タブレット上に書かれた略式図面より，内部データ構 造を組み立てることのできるシステム7）を完成し，種 々の形状の立体図形が比較的容易に生成され得るよう になった。 沖野らは3次元立体図形を“数式化パターン”およ び‘‘パターソ・マトリックス”によって表現する方法8｝ を確立し，さらにそれらの立体図形を一連のコマンド を与えることによって生成することのできる形状記述 言語TIPS−1を開発した9）。 本論文においては，CADシステムにおいて頻繁に使 用される直方体，柱体，錐体などの簡単な形状の立体 図形，また使用される機会はそれほど多くないが，そ の生成が比較的面倒である球，楕円体，トーラスなど の立体図形を選び，それらに対しては自動的に内部デ ータ構造1°）を組み立ててゆく方法について考察する。 ただし，本論文においては対象となる立体図形はすべ て多面体に限定されているため，一般に曲面を表すと考えられる立体図形（たとえば球，トーラスなど）に 対しては，多面体で近似することが必要であり，その 近似法についても合わせて考察する。 また，すでに作成されている多面体の輪郭線を求め るプログラム11）を利用することによって得られる任意 の閉曲線を底面とする柱体，錐体の生成法についても 考察する。 さらに実際にプログラムを作成し，いくつかの作図 例も得られたので，合わせて報告する。 2． 立体図形の内部データ構造 立体図形（多面体）の内部データ構造およびデータ の入力法についてはすでに文献10）に詳述されている ので，ここでは簡単に述べることにする。 多面体Pを記憶するためには，4つの表が用意され る。第1は多面体Pの各頂点を記憶しておく表であ り，これは頂点表（Vテーブル）と呼ぽれる。この頂 点表に書き込まれる各頂点には，それぞれ頂点番号が つけられる。第2はPの稜線を記憶するための表であ り，稜線表（Lテーブル）と呼ぼれる。Lテープルに は，各稜線の両端点の頂点の頂点番号の組が書き込ま れる。 面に関する情報を記憶するために，二つの表が用意 される。まず第一にはPの各面が何本の稜線によって 表一1多面体のデータ構造の例 頂点番号
座標値
‡ ’y 2 1 2 3 4 （a） Vテーブル 稜 線 番 号 1 2 3 4 頂点番号 1 2 1 1 2 3 3 4 面 要 素 番 号 ’1 2’ 3 4 稜 線 番 号 ．1 5 4 1 （b） Lテーブル 形成されているかを示す表（稜線数表あるいはNテー ブルという）であり，第二は面を構成する稜線のL テーブルにおける位置（稜線番号という）を記憶する ための表（面要素表あるいはSテーブルという）であ る。 これらの諸表の例を表一1に示す。ただし，表中の Vテーブルの空白の部分には，実際にはそれぞれの座 標値が書き込まれる。Lテーブルにおいて，たとえぽ 線L、は頂点V，，V，を結ぶことを示している。また， Nテーブルにおいては，面S、が3本の稜線によって 構成されていることを示し，Sテーブルにおいて，そ れらがLi， L，およびL，である（第1番目から第3番 目までを参照）ことを示している。 3．柱体の生成 図一1に示されるような正n角形の内部データ構造 の組み立て方について考察する。断面の外接円の半径 をr，高さをhとし，底面が（x，y）平面上にくるよ うにその位置を定めることにすれば，2n個の頂点の座 標値はそれぞれ次の式によって定められる。 Xτ＝夕COSθ‘ yi＝rsinθi Zt＝0 （i≦nのとき）（i＝1，2，…，2n） （1） ＝h （i＞nのとき） （ただし，・‘−2・？’） このようにして定められた各頂点V、の座標値（Xt， y、，2，）をVテーブルのi番目の位置に書き込むこと により，頂点表が作成される。稜線表，面要素表およ び稜線数表の生成手順は図一2のフローチャートに示 されるように，二つの部分に分けて考えることができ る○ まず第一の部分（図の左半分）において，正n角形 の底面および上面を形成する稜線および面に対する各 面 番 号 1 2 3 4 稜 線 数 3 3 3 3 （c） Sテーブル （d） Nテープル 図一1正8角柱の例DO
i＝1，n L（1，の＝i L（2，i）＝i十1 L（1，ノ）＝戊 L（2，j）＝j斗1 s（り＝i SO）＝ノ L（2，n）＝＝1 L（2，元）＝n十1 N（1）＝n N（2）＝n m＝・：2 nl＝2n ns＝2nDO
j＝1，n m＝m十1 nl＝nt十1 L（1，nl）＝i L（2，ni）＝i十n S（ns＋1）＝＝i S（ns−｝−2）＝i→−n S（ns十3）＝＝nt S（ns十4）＝ni一ト1 1V（m）＝4 ns＝ns十4 図一2 n角柱に対するL，S，Nテーブルの作成の手順 種テーブルが作成される。 底面の稜線Li（i＝1，2， …，n）はとなり合う二つの頂点れおよびV，．1を結ぶ 線として表される。そしてこのことはLテーブルのi 番目に頂点番号iおよびi＋1を最き込むことを意味 している。ただし，線LnはV。， Vlを結ぶ線であるの で，Lテーブルのn＋1と書き込まれたところはそれ を1で置きかえるという操作が必要となる。上面の稜 線に対しても同様な手続きによって，そのLテーブル が生成される。また，このn角柱の底面の面番号を1， 上面の面番号を2と定めれぽ，面Siは線L、， L2，…， L。によって構成され，Sテーブルの末尾に稜線番号 1，2，…，ηが書き加えられる。 したがってNテーブル の第1番目にnが記憶される。面S2に対しても同様 である。 第二の部分（図の右半分）においては，底面と上面 を結ぶ稜線および面に関するデータ構造が作成され る。図のフローチャートからも明らかなように，線 L2。＋i（i＝1，2，…，n）は点れとれ．nを結ぶ線分とし て定義される。また面Si．2はすべて4角形面であり， それはwa L，， Li＋n， L2n＋iおよびL2n＋i＋1によって囲 まれる部分である。ただし，i＝nのときには線L2n＋i．、 はL2。＋、で置き換える。 なお図中に示されている変数〃2，nsおよびneはそ れぞれ多面体の面の数，面要素表に書き込まれている 情報の最終の位置および稜線数を表している。 直方体が柱体の場合と異なるのは各頂点の座標値だ けであり，したがってその内部データ構造もn角柱の 場合と同様にして生成することができる。実際の処理 プログラムにおいても，直方体生成のためのコマンド が用意されている。 4．錐体の生成 図一3に示されるような正n角錐の生成法について 考察する。底面の外接円の半径をr，高さをhとし， 底面が（x，y）平面上にあり，かつその中心が原点と 一致するようにその位置を定めるものとすれぽ，各頂 点の座標値V、（x、，yi， Zi）はそれぞれ， Xi＝rCOSθi Yi ＝rsinθi！コ
（i＝1，2，…，n） （ただし…＝＝・・7’） および ｛ Xn＋1＝O Yn＋i＝O Zn＋i＝h によって決定される。 （2） （3） このように各頂点の位置と頂点番号（各座標値の添 字）が定められれぽ，頂点表は容易に組み立てること ができる。また稜線表，面要素表および稜線数表は前 節の正n角柱の場合と同様な考え方によって生成でき る（図一4）。ただこの場合には，n角柱の上面に対す る面がないので，その面の生成に関連する処理はすべ て省略できる。 図一3正8角錐iの例START
πs＝π m（1）＝η DO ﾃ＝1，η L（1，の＝‘ k（2，の＝汁1 k（1，i十n）＝i k（2，i十n）＝π＋1 N（i十1）＝3 刀iり＝匡 W（ns十1）；i r（η，＋2）＝汗η r（ns十3）＝社π＋1 η5＝π8十3 L（z，n）＝1 r（ns）＝π＋1 ηη＝η十1 ﾅρ＝π十1 ﾎ∈2πEND
図一4錐体に対す るL，S，2Vテー ブルの作成の手順 なぎ合わせた折線Kで近似することができる（図一5）。 いまt＝tiにおける2， xの値の組を（Zi， Xi）で表 す。このとき，直線分（Zi．1， Xi．1）（Zi，κDをK，（i ＝1，2，…，m）で表すと，線分Kiのz軸まわりの回転 体は2i．1＝Ziの場合を除けぽ，すべて円錐台形の立体 図形となる。この回転体のデータ構造は第3節で考察 された円柱と同様な手順によって生成することができ る。ただし，この場合には，二直線分の接点部分（た とえぽ，Ki−1とK，を結ぶ点）の回転により生ずる面 （円柱の場合の底面および上面に対応する）は二つの 円錐台に共有されることになるので，これらの面に関 する情報は生成する必要がない（図一2のフローチャー ト中の左側の部分において，SおよびNテーブルに関 する操作が省略できる）。 Zi−1＝Ziの場合には線分Kiはz軸に直角となり， したがってこの場合にはKiをz軸まわりに回転して 得られる図形は，半径lxτ．11およびlx、1の二つの同心 円で囲まれる領域を表すことになる。この場合には円 柱の底面と上面を結ぶ線および面に対応するデータを 作成する必要はなく，したがってそれに対する各種の 処理（図一2に示されるフローチャートの右半分の部分 に対する処理）は不必要となる。そのかわりに，この 面は穴のあいた2n角形の面となる。 6． 近似的に二次曲面を表す多面体 5．軸まわりの回転体 図一5に示されるような区間［to， tm］で定義され， かつ自分自身とは交わらない曲線分C z＝9（t） ｛ （to≦t≦tm） （4） x＝ψω をz軸まわりに回転して得られる立体図形を近似的に 多面体で表すことを考える。 区間［t。，tm］を適当にm分割（等分でなくても良 い）することにより，この曲線分はm個の直線分をつ 6．1球，楕円体の生成 式（4）において，関数ψ（の，ψ（t）がそれぞれ 9（t）＝RCOS・t ｛ （0≦t≦π） （5） ψ（t）＝Rsint で表されるとき，曲線Cは図一6に示されるような半 円となる。ここでRは正の定数であり，円の半径を表 す。 いま，mをm＞1なる整数として，区間［0，π］を m＋2分割し， x C 工3 一 工 一 一 一 一 ⇔ 一 一 ● ● 一 一 一 一 一 一 一 Z2 一 一 一 一 一 一 一 一 一 一 一 一 Il ‘ κ π1 一 一 一 一 一 ’ 1 1 1 ‘ 工0 ‘ 1 ‘ 1 ‘ ‘ ‘ ， n 8 0 ZO 21 z2 z3 名 図一5 曲線分の折線による近似 図一6 円弧の折線近似のようにm＋1個の（Zi， Xi）の組を定めて，曲線分 Cを図一6に示される折線Kで近似することにする。 このようにして定められた折線Kをz軸まわりに回 転して得られる立体図形は近似的に球を表す。このよ うな球に対する内部データ構造は，前節の場合と全く 同様にして組み立てることができる。したがって，人 は球の半径R，曲線の分割数〃2および正多角形の角数 nを与えるだけで良い。 楕円体はa，bを相異なる二つの正定数として，式 （5）の関数ψ（の，ψ（t）をそれぞれ q（t）＝acost ｛ （0≦t≦π） （7） ψ（t）＝bsint で置き換えることによって，球の場合と全く同様にそ の内部データ構造を組み立てることができる。 6．2 双曲面体の生成 区間［−to， toコで定i義される曲線 ｛ 2＝asinht （−to≦t≦to） （8） x＝bcosht を考える。式（8）で表される曲線は無限遠にのびる双曲 線の両端を途中で打ち切ったものである。 一般に双曲面体は閉じた曲面を形成しないので，わ れわれは（それを多面体で表すために）式（8）で表され る曲線のz軸まわりの回転体を双曲面体として取り扱 うことにする。 いま区間［−t。，t。］をm等分して，この双曲線分 を折線で近似することにすれぽ，前節で述べられた多 面体と同様な手順で（近似的に）双曲面体を生成する ことができる。ただし，われわれはあらかじめ与える べきパラメータとして，定tw toのかわりに，双曲面 体のz軸方向の長さhを与えることにする。ここで定
数toは
t… 1・g（㌃＋Vi＋（☆）2） なる関係式によって導かれる。 7． トーラスの生成 （9） トーラスに対する内部データ構造の組み立て方につ いて考察する。図一7に示すように，（z，x）平面上に 半径Rの円を描き，これを正m角形で近似する。そし てこのm角形の各辺をL， （i＝1，2，…，m）で表すこ とにする。 いま辺Liの一つの端点をP」とし，点P」を中心と 図一7 トーラスの近似法 して線分0動を含み，かつ（z，x）平面に直交する ような平面内に半径r（〈R）の小円C」を考える。同 様な小円oノを線分Liの他の端点においても考える と，図一7に示すように線分ムを中心とした一つの柱 体が考えられる。 同様のことを他のすべてのLi（i＝1，2，…， m）に ついて考えれぽ，トーラスはこのような柱体をつなぎ 合わせた図形で近似することができる。 この場合には第5節で述べられた軸まわりの回転体 における底面および上面（線KlおよびK。，の他の線 K2， Km，．1に共有されない各端点の回転により得られる 面）が一致していると考えることができる。したがっ て，この部分においては各種のテーブルは作成する必 要がない。他の部分における各テープルは第5節の場 合と同様にして生成することができる。 なお前述の各柱体の底面をそれぞれ正n角形で近似 することにすればmn個の頂点の位置は式 ｛i；iト（（R−〆cOS q）ゴ）sinθz r Sln qj（R−rsinψτ）COSθτ）（；二1：；：：1：：） ただし θ、＿互（i−1）m
9ゴ＝互（」−1） によって与えられる。 ⑭ 8． 任意の多角形を底面とする柱体，錐体の生成 2次元多角形Sが表一2に示されるようなn個の線 分によって表されているものとする（実際，輪郭線抽出 のプログラム11）によってこのような表が作成される）。 ここで線Liは点P2i．1およびP2τを結ぶ線として定 義される。このように定義された線Liの端点1）2i．1 およびP2iは他の線分Lゴ， Lkの端点にそれぞれ一致 している（線Lz．1あるいはLi．、の端点とはかぎらな い）はずであり，したがって相異なる頂点の数はnで ある。表一2閉多角形を表す線分表 線 始 点 終 点 L， L2 P1（Xl， y、） P，（x3， Y3） P2（X2， Y3） P4（x4， Y4） Ln P2。．、（X，。．、， Y2n．、） P2。（X2n・Y2n） いまこれらの相異なるn個の頂点に順次（1からn までの）頂点番号を割り当て，それらの座標値（2i＝0 とする）をVテーブルに書き込む。また，表一2に示さ れる各頂点の先に定められた頂点番号の組を線分Lzに 対応させる表を作成すれば，この表が面S、の稜線に 対するLテーブルとなる。 面S，を底面として高さhの柱体Pの生成について 考察する。柱体Pの上面S2の各頂点V，．n（i＝1，2， …，n）の座標値はそれぞれ（Xi， yi， h）で表される。 ここでXi， yzは頂点番号iの座標値を表すものとす る。 面S2の稜線Lt＋nは2点Vゴ．。， Vk．nを結ぶ線分と して表すことができる。ここで」，kは線Liの両端 点のそれぞれの頂点番号を表すものとする。このよう に各稜線を定めれぽ面S1およびS2はそれぞれ線Li およびLt＋n（i＝1，2，…，n）によって構成されること は明らかである。 面S、とS2を結ぶ稜線L2。＋i（i＝1，2，…，n）は頂点 V、およびV，＋。によって表される。また面Si＋2（i＝ 1，2，…sn）は，稜線Li， Ln＋i， L2n＋」およびL2n＋leに よって構成される。ここでノおよびkは線Liの両端 点のそれぞれの頂点番号である。 面Siを底面とする錐体に対しても同様な考えによ ってそのデータ構造を生成することができる。 9． 計算機による作図例 前節までに述べられた方法に従って，実際にプログ ラムが作成され，いくつかの作図例が得られた。図一 8∼11はそれぞれ，16角柱，軸まわりの回転体，球お よびトーラスの例を示している。なお，これらの図に おいては，視点から見て見えないはずの線（隠れ線と いう）はすべて消去されている。 これらの作図例はすべて（多面体というより，むし ろ）曲面を表していると考えるべきである。一般に， このような曲面を表すのに不必要な線分（自動的に検 出される）も，同時に消去される。たとえぽ，図一8が 図一8近似的な意味での 円柱の生成例 図一9軸まわりの回転体の例 図一10球の生成 例 図一11 トーラス の生成例 円柱を表すものと考えれぽ，上面と底面を結ぶ縦の線 は，輪郭線を除けぽすべて消去しても差し支えないも のである。したがって，本例題においては，そのよう な処理も合わせて施こされている。 ただし，球および楕円体においては，輪郭要素（文 献11，p．26参照）とならない線分（内線という）を消 去すると2次元的な図形と区別できなくなってしまう 恐れがあり，この場合に限って，内線は消去しないよ うにプログラムが作成されている。また図一11に示す トーラスのように複雑な曲面を表す場合には，立体感 を出すために，輪郭線以外の線分も付け加えられる。 もちろんこのような処理はすべて自動的に行われるも のであるが，そのアルゴリズムに関する報告は別の機 会にゆずりたい。‘ 図一12，13はディスプレイ画面上に出力された図一14， 15のような図形を利用して生成されたものである。 なお，本論文で考察された基本立体図形の種類およ びデータとして与えるべきパラメータについては付録 として表にまとめられている。
図一12ディスプレイ画面上の閉曲線を利用して生成さ れた錐体 図一13ディスプレイ画面上の閉曲線を利用して生成さ れた柱体 10． 結 言 本論文で考察された立体図形の多くは，いくつかの パラメータを与えるだけで生成することができるが， 逆に限られた種類の図形しか生成することができない という欠点を持っている。これに対して，ディスプレ イ画面上に出力された2次元図形を利用する方法は種 々の立体図形を得るために利用することができる。 しかしこのようにして得られる立体図形の種類には 限りがあり，少し複雑な図形になると本論文で考察さ れた方法だけでは生成することができない。そのよう な場合には，すでに開発されている追加，削除12）等の プログラムを利用することにより，人はその内部デー タ構造を直接操作することなく所望の形状の立体図形 を組み立てることができる。 なお本論文で得られた作図例はすべて東京大学大型 計算機セソターのHITAC 8800／8700システムを利用 して得られたものであることを付記する。 終わりに日頃御指導賜わる東京大学渡辺茂教授，同 三浦宏文教授ならびに本学前澤成一郎教授に感謝の意 を表する。
参考文献
図一14二つの三角柱の輪郭線図■
○
○
○
図一15五つの円柱より得られる輪郭線図 1） LC． Braid and C． A． Lang：Computer Aided Design of Mechanical Components with Volume Building Bricks， Computer Language for Nume− rical Contro1， pp．173∼184（1973）， North Holland．2）B．G． Baumgart：GEOMED：AGEOMETRIC
EDITOR， pp．1∼43， Stanford Artificial Intelli・ gence Laboratory Memo， AIM 232（1974） 3） 出沢正徳：三面図から立体形成のためのシステム，日 本機械学会論文集，Vol．38， No．10， pp．1267∼1276 （1972） 4）出沢正徳：三面図から立体形成の際の副面図の考慮 法，日本機械学会講演論文集，No．720−3， pp．33 ∼36（1972） 5） 出沢正徳：立体視による対話型設計法についての検 討，日本機械学会講演論文集，No．750−3， pp．45∼ 48 （1975） 6）穂坂衛，木村文彦：機械設計自動化のための幾何モデ ル生成システム，日本機械学会論文集，Vol．44， No． 378， pp． 661∼669 （1978） 7）穂坂衛，木村文彦：手書き図面入力とその幾何モデル 生成への応用について，日本機械学会講演論文集， No． 780−8， PP． 16∼23 （1978） 8） 沖野教郎：コンピュータによる自動デザイン，p．41 （1967），日刊工業新聞社 9）沖野教郎他：自動設計プロセッサTIPS−1のシステム 設計，精密機械，Vo1．42， No．10， pp．17∼24（1976） 10）古川進：多面体の干渉問題に対する一解法，情報処 理，Vol．14， No．3， pp．173∼181（1973）11） 古川進：隠線消去処理と輪郭線、の抽出，山梨大学工学 12） 古川進：CADのための立体図形の結合，切断，情報 部研究報告，Vol．26， pp．25∼30（1975） 処理， Vol．16， No．8， pp．678∼684（1975） 付録 基本立体図形の種類と入力形式 図 形 の 種 類 直方体
