JPS62212783A - 凹多面体の凸包多面体形成方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 ［概　要］ 本発明は凹多面体の白色処理に関するもので、凹多面体
中の凹領域を抽出して凸閉包し、それらと元の多面体を
統合して、これが凸多面体となれば処理を終了し、凹多
面体ならば、再び統合された多面体に対して同じ処理を
行うという再帰的処理により凹多面体の最小６包多面体
を形成するようにしたもので、無駄な処理が無く、速く
処理できる。

［産業上の利用分野］ 本発明はコンピュータによる形状処理に係わり、特に与
えられた凹多面体から、その最小６包多面体を形成する
ための処理方式に関する。

三次元物体の認識および表示等のためのコンピュータに
よる形状処理、或いは部品加工における部材からの切削
等においては、形状が多面体であるものを対象とした場
合、凹多面体より凸多面体の方が温かに扱い易い。

従って凹多面体の場合、まずそれを包む凸多面体、即ち
６包多面体を形成し、その凸多面体に対して処理を行い
、後に凹部に対して処理を行うことが一般的に行われて
いる。

このため、与えられた凹多面体から、そのような６包多
面体を形成し、さらに６包多面体のどの部分が元の多面
体の凹部に対応するかを示すデータが自動的に作成され
ることが必要とされる。

［従来の技術］ 従来技術による凹多面体の５包多面体形成方式を第４図
に、その適用例を第５図に示す。

従来技術による凹多面体の５包多面体形成方式は、純数
学的に取り扱い処理するものであった。

（例えば、Ｆ、Ｐ、Ｐｒｅｐａｒａｔａ、、ａｎｄ　Ｓ
、Ｊ、ＩＩｏｎｇ　：　Ｃｏｎ−ｖｅｘ　Ｈｕｌｌｓ　
ｏｆ　Ｆｉｎｉｔｅ　５ｅｔｓ　ｏｆ　Ｐｏ１ｎｔｓ　
ｉｎ　Ｔｗ。

ａｎｄ　Ｔｈｒｅｅ　Ｄｉｍｅｎｓｉｏｎｓ、　Ｃｏｍ
ｍ、ＡＣＭ　２帆２　（１９７７）ｐ８７−９３参照）
。

第４図において、６は点集合白色部、７は閉包部抽出部
、８はメモリである。

第５図に示すように、まず点集合白色部６において、各
頂点の配置だけから最終的な６包多面体を形成し、メモ
リ８に記憶する。

形成された６包多面体は、与えられた凹多面体と無関係
に形成されたもので、これと与えられた凹多面体との対
応づけを行う必要があり、次いで、閉包部抽出部７によ
り、各頂点から新たに形成された接続関係を閉包稜線と
し、これによって作られる面を閉包面として、閉包部を
決定する。

さらに、決定した閉包部が、どの凹部を包んでいるのか
を調べる。

［発明が解決しようとする問題点］ 上記の従来技術の凹多面体の５包多面体形成方式におい
ては、四部に対して５包処理を行うのではなく、凹多面
体を構成する総ての頂点に対して５包を行うため、与え
られた凹多面体の凹部が小さい場合には、無駄な５包稜
線の探索処理が殆どであり、処理時間を長くしていると
いう問題点がある。

本発明は、このような問題点を解消した新規な凹多面体
の５包多面体形成方式を提供しようとするものである。

し問題点を解決するだめの手段］ 第１図は本発明の凹多面体の５包多面体形成方式の原理
ブロック図である。

図中、１は与えられた凹多面体における凹領域を抽出す
る凹領域抽出部であり、３は抽出された凹領域を凸閉包
する凹領域凸閉包部である。

また、２は抽出された凹領域が総て凸閉包されたか、ま
た再帰処理を行うかどうかを判定する制御部であり、４
は抽出された凹領域、処理された閉包面等のデータを記
憶するメモリである。

凹領域抽出については、そのひとつの処理方式を本出願
人から別件で出願しているが、物体を外側から見て出っ
張っている稜線を（＋）とし、凹んでいる稜線を（−）
として、（−）の稜線を検出し、（−）稜線を辺とする
面を検出し、その面の他の辺に（−）のものがあるとき
はこれを辺とする他の面もこの凹領域の連続とし、他の
辺が総て（＋）となったときこれを１つの独立の凹領域
として抽出するものである。

［作用］ 本発明の凹領域抽出部１は、人力された凹多面体の総て
の凹領域を抽出し、制御部２は、それらから１つを選び
凹領域凸閉包部３に送る。凹領域凸閉包部３では、送ら
れた凹領域を凸閉包する。

この結果、凹領域だけについて凸閉包処理を行うので、
無駄な処理を行わな（でも済むようになる。

また、凹領域凸閉包部３は１つづつ独立に凹領域を凸閉
包するから、凹領域凸閉包部３を複数個備え、並列に処
理させれば、さらに高速な処理が期待できる。

［実施例］ 以下第２図および第３図に示す実施例により、本発明を
さらに具体的に説明する。

第２図は、本発明の実施例による処理を示すフローチャ
ートであり、第３図は本発明の実施例による処理の通用
例を示す図である。

以下、第２図のフローチャートに従って、第３図の適用
例を参照して、処理の流れを説明する。

１０１は凹領域抽出部であって、入力された多面体の総
ての凹領域を抽出する。

２０１は終了条件判定部であって、凹領域抽出部１０１
で抽出された凹領域が１つでも存在するかを判定し、存
在しなければ凸多面体であるとして処理を終了する。凹
領域が存在すれば、３０１の処理に渡す。

３０１は凹領域凸閉包部であって、凹領域抽出部１０１
で抽出した凹領域を凸閉包する。

２０２は凸閉包終了判定部であって、終了条件判定部２
０１から渡された凹領域の凸閉包が総て終了したかを判
定する。終了していなければ、３０１の処理に戻り、総
て終了していれば、２０３の処理に渡す。

２０３は中間多面体生成部であって、個々の凹領域をそ
れぞれの凸閉包面で置き換えることによって、目的の５
包多面体の候補ともいうべき中間多面体（第３図（ｂ）
参照）を生成し、再び１０１の処理に戻る。

［発明の効果］ 以上説明のように本発明によれば、凹領域を抽出して凹
領域だけを凸閉包する処理を行うので、無駄の処理がな
く凹領域が小さい凹多面体に対しては処理速度が速く、
また、凹領域凸閉包部を複数個備え独立に処理させるこ
とによりさらに処理速度を上げることが可能となり、そ
の実用上の効果は大である。

【図面の簡単な説明】

第１図は本発明の原理ブロック図、 第２図は本発明の実施例による処理を示すフローチャー
ト、 第３図は本発明の実施例による処理の適用例を示す図、 第４図は従来例を示すブロック図、 第５図は従来例による処理の適用例を示す図である。 図面において、 １は凹領域抽出部、　　　　２は制御部、３は凹領域凸
閉包部、　　　４，８はメモリ、６は点集合白色部、　
　　　７は閉包部抽出部、をそれぞれ示す。 入力 本発明の原理図ブロック図 第　　１　　図 出力 従来例を示すブロック図 第　　４　　図

Claims (1)

1. 【特許請求の範囲】 凹多面体を表す形状データから、それを包む最小の凸多
   面体を形成する処理方式において、凹多面体の凹領域を
   抽出する凹領域抽出部と、該凹領域抽出部により抽出さ
   れた凹領域を凸閉包する凹領域凸閉包部と、 前記凹領域抽出部および凹領域凸閉包部の処理結果を格
   納するメモリと、 前記各部の動作を制御する制御部とを備え、与えられた
   凹多面体の凹領域を、それぞれ独立に凸閉包し、該凸閉
   包稜線と元の凹多面体との統合により形成された多面体
   に凹領域が存在するかを判定し、凹領域が存在しないと
   きは処理を終了し、存在するときは該統合された多面体
   に対し、再度同一の処理を適用するよう構成したことを
   特徴とする凹多面体の凸包多面体形成方式。