JPS6284381A - 面法線決定処理装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔概　要〕 立体のモデルの面情報から、該立体のソリッドモデルの
面法線を決定するための方式である。面法線を求める各
面について、面の内点を適当に定めて、該内点を始点と
して面に垂直な半直線を引き、その半直線が交わる面の
個数を計数する。その交わる面の個数の例えば奇偶によ
って、両生直線のうちの一方を、核部から立体の外側へ
向く法線である面法線として決定する。この構成により
、面情報からソリッドモデルの面法線を求める処理を効
率よく実行することができる。

〔産業上の利用分野〕

本発明は、立体の情報処理等における、立体モデルの面
情報から、ソリッドモデルの面法線情報を決定するため
の方式に関する。

立体の認識処理、画像処理等において、空間のある１点
が立体の外側にあるか内側かを識別することが必要であ
り、そのための基本情報として、立体を構成する各面に
ついて外側に向（法線が用いられ、ソリッドモデルの面
法線といわれる。

〔従来の技術と発明が解決しようとする問題点〕計算機
システムにおける処理において、立体ヲ表すための一方
式におけるソリッドモデルの情報は、通常その表面を複
数の多角形平面で近似するようにした、該各条角形平面
を示ず面情報の集合を主体にして構成される。

該面情報から、各面の面法線を決定する場合に、従来は
まず適当な方法で１構成面についての面法線を定めた後
、面法線の決定した面に隣接する面の面法線を逐次決定
する方法を採っている。

即ち、第３図に例示するように、立体１の面２の、該限
定された面内の面上の点である内点３かろ、垂直に立て
られた半直線である面法線１によって、この面２につい
て立体１の外側が示されるとする。

このとき、隣接する、例えば面５の外側は、面２上の適
当な点６から、面法線４で示される側に出発して、例え
ば他の面と交わることなく面５上に到達することのでき
る検査バス７が存在することにより、その側か而５につ
いて立体の外側であることが識別される。

従って、面５の適当な内点８を始点とする法線９が面法
線として決定され、反対方向の、図に破線で示すいわゆ
る反注線１ｏは立体１の内側を向く法線である。

以上の説明から明らかなように、上記従来の方式は、面
法線の決定した面から隣接面の面法線が定まるために、
基本的に逐次処理を要する方式であり、処理の高速化の
ために、多数の面の処理を並列処理化することが、一般
に困難であるという問題があった。

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

第１図は、本発明の構成を示すブロック図である。

図において、１１は立体を構成する面情報を保持する記
憶装置、１２は処理装置、１３は処理装置１２がら出力
される面法線情報を保持する記憶装置であり、処理装置
１２には、記憶装置装置１１の面情報を処理して、面法
線情報を作成するだめの、内点抽出部１４、交点検出部
１５、及び法線決定部１６を有する。

〔作　用〕

処理装置１２の内点抽出部１４は、記憶装置１１から１
平面の面情報を続出して、その面情報で示される多角形
平面上の１内点を選定する。

交点検出部１５は、該内点を始点とし、面の両側に延び
、面に垂直な２本の半直線を設定し、記憶装置１１に保
持している面情報によって、立体を構成する他の面と各
半直線との交点を求め、交点の個数を集計する。

法線決定部１６は、両手直線のうち、上記交点個数の集
計値が０又は偶数である半直線を面法線と決定し、該半
直線を示す面法線情報を記憶装置１３へ出力する。

以上の処理は明らかに、他の面については、それらの面
情報のみを参照して、各面ごとに独立に処理を実行でき
るので、例えば複数の処理ｇＷによって、異なる面の処
理を分担する方法により、容易に並列処理を行うことが
できる。

〔実施例〕

第２図は第１図の実施例の処理装置１２における、内点
抽出部１４、交点検出部１５、法線決定部１６の処理の
詳細を示す処理の流れ図である。

本処理が開始されると、処理のステシブ２０における初
期設定により、処理対象の先頭の面情報の記憶アドレス
、個数及びその他の制御変数の初期値等の設定が行われ
る。

ステップ２１において、１個の面情報ｆ、が記憶装置１
１から読み出されて、面情報で指定される多角形平面の
内点（ＰＩＭとする）を選定する。

記憶装置１１の各面情報ｆ１、ｆ２、−ｆｌｌ−は、一
般に多角形の複数の頂点の座標情報ＶＩｋ、■２いＶ３
１．−−−−−・によって、ｆｋ＝（Ｖ＋ｖ　、Ｖｚ＋
＝　、−）と表される。

Ｐｌｆｉの選定処理は公知の適当な一方式によればよく
、該多角形の周縁線上に無い、多角形平面内の１点を選
ぶ。

次のステップ２２で、Ｐ　ｋｎを始点として、この平面
ｆ、に垂直な、互いに反対方向の２半直ｖＡ（１１及び
−ｎとする）を表す関数を生成する。

次のステップ２３で、２個のカウンタ（Ｃ０、ＣＩとす
る）をＯにリセットし、その他、次の交点検出処理のた
めの各種制御変数に初期値を設定した後、ステップ２４
以降の交点検出部１５の処理を開始する。

カウンタＣいＣＩは２を法とする計数値を保持するカウ
ンタでよい。

交点検出部１５では、半直線ｎ及び−ｎと、ｆ４以外の
ずべての面との交点を検出し、交点の個数を各半直線ご
とに計数する処理を行う。

そのために、ステップ２４では、記憶装置１１からｆ、
以外の１面情報（ｆ、とする）を読み出して、この多角
形を含む平面と、半直線ｎ及び−ｎである直線との交点
を通常の方法で求め、交点が無い場合にはステップ２９
に分岐して、この平面についての処理を終わる。

交点がある場合には、ステップ２５に進み、この交点（
ＰＸとする）が多角形ｆ、の内点かを判定し、内点てな
ければステップ２９に分岐して、この平面についての処
理を終わる。

内点てあれば、ステップ２６に進んで、ＰＸが半直線ｎ
上の点か−ｎ上かを判定し、ｎ上の点であればステップ
２７でカウンタＣ０を＋１し、−ｎ上の点であればステ
ップ２８でカウンタＣ１を＋１して、ステップ２９に進
む。− ステップ２９ですべての面との交点検出処理を終了した
か判定し、未処理の面があればステップ２４に戻って、
次の面情報による処理を開始し、ｆ。

以外のすべての面との交点検出処理を終わった場合には
、ステップ３０へ進んで、法線決定部１６の処理に入る
。

法線決定部１６では、ステップ３０でカウンタＣ０、Ｃ
，を検査し、計数値がＯ又は偶数のカウンタに対応する
半直線、即ちカウンタＣ０が０又は偶数の場合はｎ５ｃ
１の場合は−ｎを、求める面ｆ、の面法線と決定する。

この場合、他方の半直線は面法線と反対の方向、即ち立
体の内側に向くので、立体の外側へ突き抜けるために少
なくとも１面と交叉する必要があり、面との交点数が１
以上の奇数となることは明らかであり、従って対応する
カウンタの値は必ず奇数を示す。

次のステップ３１で、要すれば決定した面法線情報を出
力し、ステップ３２ですべての面の面法線の決定処理が
終わったか判定し、未処理の面があればステップ２１に
戻って、次の面の処理を開始し、未処理の面がなければ
処理を完了する。

〔発明の効果〕

以上の説明から明らかなように、本発明によれば、計算
機システムにおける、立体図形のソリッドモデルの面法
線決定処理が、各面ごとに、他の面の処理に依存するこ
となく独立に実行できるので、並行処理によって、処理
を高速化することが容易になるという著しい工業的効果
がある。

【図面の簡単な説明】

第１図は本発明の実施例構成ブロック図、第２図は本発
明の処理の流れ図、 第３図は従来方式の説明図 である。 図において、 １は立体、　　　　　　２．５は面、 ３．８は内点、　　　　　４．９は面法線、１１．１３
は記憶装置、　　１２は処理装置、１４は内点抽出部、
　　　１５は交点検出部、１６は法線決定部、　　　２
０〜３２は処理のステップ本発明の実施例構成ブロック
図 第１図

Claims (1)

1. 【特許請求の範囲】 立体のソリッドモデルの面情報より、面法線を決定する
   に際し、 各面の面情報より、該面の１内点を抽出する手段（１４
   ）、 該内点を始点とし、該面に垂直な半直線を設定し、上記
   面情報により該半直線と交わる面の個数を計数する手段
   （１５）、 該面の個数によって、該半直線が上記面法線であるか否
   かを決定する手段（１６）を有することを特徴とする面
   法線決定方式。