JPH07105409A - 三次元移動体の衝突検知装置 - Google Patents

Abstract

(57)【要約】 【目的】 三次元画像のリアルタイム・ウォークスルー
等における衝突検出に関し、衝突検出を高速に実行でき
る三次元移動体の衝突検知装置を目的とする。 【構成】 平面図記憶部１は、移動平面でクリッピング
した三次元データに関して、該移動平面から基準平面ま
でに配置されている構造物を、該基準平面に平行投影し
た図形を表す二次元データを平面図５として保持し、指
示部２は、移動体を代表する点の各現位置を該基準平面
上に投影した点を示す二次元座標値を現位置座標として
判定部３に順次入力し、判定部３の線分生成部６は、該
現位置座標と該前位置記憶部に記憶する座標との両点を
結ぶ線分を生成し、交差検出部７は、平面図５の該平行
投影された構造物と、線分生成部６が生成した線分との
交差を識別して、該交差の有無を指示部２に返し、前位
置記憶部４は記憶内容を判定部３の処理した該現位置座
標に更新するように構成する。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、建築物の内部の景観等
を示す三次元透視図画像を、いわゆるリアルタイム・ウ
ォークスルー方式で視点の移動に伴って逐次三次元デー
タから生成するような装置のために、視点等の移動体が
障害となる構造物に衝突することを検出する三次元移動
体の衝突検知装置に関する。

【０００２】

【従来の技術と発明が解決しようとする課題】いわゆる
コンピュータグラヒックス（ＣＧ）技術におけるリアル
タイム・ウォークスルーとは公知のように、いわゆるＣ
ＡＤ等で設計された建築物について、その建築物の内部
を歩きまわって見るような感覚で見えるように、建築物
の透視図様の三次元画像を表示するものであり、観察者
を代表する点として定める視点の移動に合わせて、視点
から所要の方向を見た場合の視野内の三次元画像を生成
して、アニメーション表示する手法であり、リアルタイ
ム・ウォークスルーは、建築物のプレゼンテーション等
の分野で有効な技術となっている。

【０００３】ここで、自然に見える良質の画像を表示す
るためには極めて高速のリアルタイム画像処理が要求さ
れるが、三次元画像処理は一般に計算量が膨大であり、
通常の計算機では１フレームの画像作成に数秒ないし数
分を要する。

【０００４】そのために、三次元画像生成のための専用
のハードウェアが開発され、それを用いることによって
毎秒数フレームないし数十フレームを生成することが可
能となってきた。

【０００５】しかしリアルタイム・ウォークスルーに特
有の問題もあり、特に例えばオペレータが建物の中を自
由に歩きまわるように、経路をマウス等の入力手段で指
示し、その指示に伴って内部の景観を表示する場合等
に、その入力を容易にすることが必要であり、そのため
に設ける機能の一つとして、観察者と構造物等との衝突
検出がある。

【０００６】ここで衝突検出とは、前記視点のような移
動体の点が建築物等で本来入れない所を通ってしまう
（例えば壁の中を突き抜ける）ような移動を行うことを
検出することをいい、そのようなことを検出した場合に
は、本来あり得ない画像を表示することを避け、例えば
警告を発して指示を改めさせる等の処置をする必要があ
る。

【０００７】一般的な衝突検出では、対象の三次元デー
タで表される空間について、壁や設置物等の障害物を指
定しておき、移動体の移動経路が、空間内のそれらすべ
ての障害物と交差しないことを、移動ごとに識別する処
理を行うので、衝突検出には比較的長い処理時間を要す
る。

【０００８】本発明は、建築物内のリアルタイム・ウォ
ークスルー等の条件における衝突検出を高速に実行でき
る三次元移動体の衝突検知装置を目的とする。

【０００９】

【課題を解決するための手段】図１は、本発明の構成を
示すブロック図である。図は三次元移動体の衝突検知装
置の構成であって、三次元データによって表される三次
元空間内の構造物について、該構造物に設定した基準平
面に関して、該基準平面に平行な移動平面内を移動する
点で代表される移動体と、該基準平面上に配置されてい
る構造物との衝突を検知する装置であって、平面図記憶
部１と、指示部２と、判定部３と、前位置記憶部４とを
有する。

【００１０】第１の発明において、平面図記憶部１は、
該移動平面でクリッピングした該三次元データに関し
て、該移動平面から該基準平面までに配置されている構
造物を、該基準平面に平行投影した図形を表す二次元デ
ータを平面図５として保持している。

【００１１】指示部２は、該移動体を代表する点の各現
位置を該基準平面上に投影した点を示す二次元座標値を
現位置座標として判定部３に順次入力する。判定部３
は、線分生成部６と、交差検出部７とを有し、線分生成
部６は、指示部２から入力された該現位置座標と該前位
置記憶部に記憶する座標とで表される両点を結ぶ線分を
生成する。

【００１２】交差検出部７は、平面図記憶部１に保持す
る平面図５について、平面図５の該平行投影された構造
物と、線分生成部６が生成した線分との交差を識別し
て、該交差の有無を指示部２に返し、前位置記憶部４は
記憶内容を判定部３の処理した該現位置座標に更新す
る。

【００１３】第２の発明において、前記平面図記憶部１
の保持する前記平面図５には色指定を有し、前記基準平
面が該平面図上に表れているすべての部分には識別色と
する所定の色が指定され、他の部分すべてには該識別色
以外の色が指定されていて、前記交差検出部７の前記交
差の識別では、前記線分上のすべての点に対応する部分
の該色指定が該識別色であることにより交差が無いと識
別する。

【００１４】

【作用】本発明の三次元移動体の衝突検知装置により、
床面等の基準平面に対して、移動体が基準平面に平行な
移動平面内を移動する場合における衝突検出を、構造物
をその基準平面に投影した平面図を表す二次元データの
みを使用して、移動体の移動経路と障害物との交差を識
別することにより衝突を検出するので、三次元空間内の
すべての障害物について識別する必要が無く、高速に衝
突検出の処理を行うことができる。

【００１５】建築物の内部のリアルタイム・ウォークス
ルー等で、観察者が或る部屋の内部を移動して見る場合
には、通常は観察者は当然その部屋の床面上を移動し、
従っておよそ観察者の眼の位置に設定される視点は、床
面から一定の高さで床面に平行な平面内を移動すること
になる。

【００１６】従って、そのようなリアルタイム・ウォー
クスルー等の場合に、上記の視点、床面、及び視点の移
動する平面を、それぞれ前記の移動体、基準平面、移動
平面に対応付ければ、平面図を使用して衝突検出を行う
ことが可能になる。

【００１７】又、平面図に色指定を設ける場合に、基準
平面とする例えば床面の色を他の構造物等と区別できる
色にしておけば、交差の識別を色の識別に代えて、視点
の移動経路の線分上の画素すべてが床面の色であれば非
衝突とし、一部でも床面と異なる色の画素があれば衝突
として判定することにより、更に衝突検出を高速化でき
る。

【００１８】

【実施例】図２は本発明の一実施例を示すブロック図で
あって、利用者が入力部21から入力するフロア指定、擬
似観察者の移動経路指定に従って、三次元データ28とし
て保持する建造物の三次元画像データにより、その建造
物内について前記のようなリアルタイム・ウォークスル
ーを行い、視野設定部22、画像生成部23により順次生成
する透視図をディスプレイ29に表示するシステムであ
る。

【００１９】そのリアルタイム・ウォークスルーの間の
観察者の移動における衝突検出のために、視野設定部22
に平面図管理部24と本発明の衝突検知装置30が接続され
ている。

【００２０】三次元データ28は、例えばしばしば行われ
るように曲面を適当な大きさの多角形平面で近似する方
法により、多数の多角形平面のみで所要の画像を構成す
るようにしたデータである。

【００２１】その場合の各多角形平面を定義するデータ
（以下に多角形データという）は、その平面を限定する
多角形の頂点を示す三次元座標を、平面の表面側から見
て一定の方向に多角形を一周するように並べたデータ
と、その平面の色指定等からなり、各多角形データは概
念的に「(x₁,y₁,z₁),(x₂,y₂,z₂),(x₃,y₃,z₃),..., 色指
定,...」のような情報である。

【００２２】三次元座標は、水平面にＸ及びＺ軸を有
し、垂直（高さ）方向にＹ軸を有する画像空間の座標と
し、例えば建造物の床面をＸＺ軸で作る平面に平行とす
る。三次元データ28は、そのような多角形データの集ま
りを、例えば各部屋ごとのデータに区分してアクセス可
能なように構成されているものとする。

【００２３】図３は図２のシステムのリアルタイム・ウ
ォークスルー処理の全体の処理の流れの一例を示す図で
あり、本例のシステムでは利用者が入力部21から観察し
たい部屋を先ず指定し、次いで指定の部屋の一定の位置
から始まる擬似観察者の視点(例えば部屋の床面の上に
立った人の眼の位置付近として定める１点) の移動経路
を逐次指定し、終了指定によりその部屋の観察を終了す
るものとする。

【００２４】図３において、利用者の入力する指定を処
理ステップ40で入力部21から視野設定部22が受け取る
と、処理ステップ41で視野設定部22は、その指定が部屋
の指定か、視点の位置及び進行方向の指定か、終了の指
定か識別する。

【００２５】部屋の指定であれば視野設定部22は処理ス
テップ42で、その部屋のリアルタイム・ウォークスルー
を開始する準備として、例えば予め保持するテーブルに
よって、三次元データ28中にある画像データで、指定さ
れた部屋に対応する画像データのアドレスと、その擬似
観察者の視点の出発点の位置を示す３次元座標を識別し
て記憶する等の初期設定を行うと共に、その画像データ
のアドレスを平面図管理部24に通知し、視点の出発点位
置を衝突検知装置30に通知する。

【００２６】以後、視野設定部22は前記視点が出発点の
Ｙ軸座標で定まる高さの床面に平行な平面を移動平面と
して、終了指定があるまで視点はこの移動平面内を移動
するものとして処理する。

【００２７】処理ステップ43で、平面図管理部24は通知
を受けた部屋の画像データに基づいて作成された平面図
を衝突検知装置30に渡し、衝突検知装置30はこれを平面
図35として平面図記憶部31に保持し、又視点の出発点位
置を前位置記憶部34に記憶して、処理ステップ40に戻
る。なお、この平面図は後述のようにして三次元データ
28の当該部屋の画像データから作成するか、又はそのよ
うにして予め作成された平面図が平面図データ27として
保存されている。

【００２８】処理ステップ41で、視点の位置と進行方向
との指定であると識別した場合には、処理ステップ44で
部屋の指定済み (従って処理ステップ42の初期設定等が
終わっている) か識別し、部屋を未指定であれば処理ス
テップ45で、利用者に対しエラーの通知を発して処理ス
テップ40に戻る。

【００２９】部屋指定済みであれば処理ステップ46で、
視野設定部22から衝突検知装置30に対して視点の現位置
座標を渡して衝突検出を要求するので、衝突検知装置30
は処理ステップ47で後述のように平面図35を使用して衝
突検出処理を行って、衝突の有無を示す結果を視野設定
部22に返す。

【００３０】視野設定部22は処理ステップ48で衝突の有
無を識別し、衝突が無ければ処理ステップ49で、視点の
現位置から指定の方向の視野を設定し、画像生成部23に
視野を指定して、画像生成部23は指定の視野の三次元透
視画像を生成して、ディスプレイ29に表示する。

【００３１】衝突が有った場合には、処理ステップ50で
利用者に再入力を要求し処理ステップ40に戻る。視野設
定部22が処理ステップ41で、終了指定と識別した場合に
は、処理ステップ51で、前に部屋の指定で設定した諸制
御情報等をクリアし、処理ステップ40に戻る。

【００３２】本発明の衝突検知装置30が衝突検出のため
に使用する前記の平面図35は、移動平面でクリッピング
した、三次元データ28の例えば部屋ごとのデータに関し
て、移動平面から基準平面とする床面までに配置されて
いる構造物を、床面に平行投影した図形を表す二次元デ
ータ」である。

【００３３】このような平面図は、床面をｙ＝αの平
面、移動平面をｙ＝βとした場合に、三次元データ28か
ら次のように図４に例示する処理によって作成できるこ
とは明らかである。

【００３４】即ち、三次元データ28の或る部屋のデータ
について、図４の処理ステップ52で多角形データを一つ
づつ読み出して、処理ステップ53で前記のような各多角
形データの頂点座標の並び「(x₁,y₁,z₁),(x₂,y₂,z₂),(x
₃,y₃,z₃),...」で、各頂点のＹ座標をβと比較し、すべ
ての頂点のＹ座標がβより大きければ多角形平面全体が
移動平面より上にあるので、その多角形平面は捨てて処
理ステップ52に戻り次の多角形データを処理する。

【００３５】Ｙ座標がβ以下の頂点がある場合には、処
理ステップ54で全頂点のＹ座標がβ以下か識別し、すべ
てβ以下ならその多角形平面全体が移動平面より下にあ
るので、処理ステップ57でその各頂点のＸ及びＺ座標か
らなる二次元多角形データに変換する。

【００３６】又Ｙ座標がβより大きい頂点を含む場合
は、処理ステップ55でＹ座標がβより大きい頂点と、そ
れに隣接しＹ座標がβ以下の頂点とを結ぶ多角形の辺に
ついて、移動平面ｙ＝βとの交点を求める。

【００３７】処理ステップ56で、求まった各交点と、元
の頂点のうちのＹ座標がβ以下の頂点とを新たな多角形
の頂点とし、その他の色指定等情報は元のデータを受け
継いだ多角形データを生成した後、処理ステップ57でそ
れを前記と同様に二次元多角形データに変換する。

【００３８】その後処理ステップ58で三次元データ28の
必要な全データを処理したか識別し、未処理があれば処
理ステップ52に戻って次の多角形データを処理し、以上
により集積される二次元多角形データで平面図が構成さ
れる。なお、三次元データ28の多角形データで表される
多角形はすべて外側に凸な多角形とする。

【００３９】図５は、以上のようにして作成される平面
図と元の三次元データで表される画像との関係を簡単な
例で説明する図であり、図５(a) が三次元データで表さ
れる立体画像、(b)がその平面図であり、(a)で棚状突起
物T1は一部が移動平面より上にあるので、移動平面でク
リッピングされて、下の部分のみ（本例では、説明のた
めに斜線網かけ模様で示す面）が(b)のT1'のように投影
され、机状突起物T2のように全体が移動平面の下にある
ものはそのままT2' のように投影されて平面図が作成さ
れる。

【００４０】以上で作成された平面図を使用して衝突検
出を行うには、後述のようにして設定する視点の移動経
路の線分が前記で生成される二次元の多角形の何れかと
交差することを衝突として検出すればよい。

【００４１】即ち、視点が移動平面を移動した場合に、
その平面図上への投影は、障害物の投影図形との位置関
係において、図５(b）のｐ点を前位置として矢印線の矢
の先端の点a₁、a₂又はa₃が現位置となるような３つの場
合があり得る。

【００４２】それらの場合において、図から明らかなよ
うに、a₁の場合の矢印線（移動経路の前位置と現位置を
結ぶ線分に相当）は何れの障害物図形とも交差していな
いので衝突が無い場合となる。

【００４３】a₂は視点の現位置が障害物図形の内部に止
まっている場合であり、a₃は現位置は障害物図形の外に
あるが、現位置と前位置を結ぶ線分が障害物図形を通過
している場合であるが、図の矢印線から明らかなよう
に、何れも障害物の図形(T1')と交差があるので衝突が
有る場合となる。

【００４４】平面図上の図形と線分との交差の検出は、
二次元多角形データで表される各多角形の各辺の線分
と、視点移動経路の線分との交点を求める計算によって
行うことができるが、床面と、床面以外の構造物や備品
等とを異なる色指定にし、床面に指定する色（複数の色
でもよい）を識別色として、識別色を床面以外の部分に
使わないようにすれば、色によって交差を識別できる。

【００４５】そのように色指定で交差を識別する場合に
は、前記の処理で生成された二次元多角形データから、
ディスプレイ等に表示する場合と同様の画素ごとの色を
示すデータを生成して、これを平面図とする。

【００４６】そのような色指定平面図は、例えば所要の
全画素について各画素に対応して色指定情報を保持する
データを、各画素の画素座標で索引できるように配置
し、先ず全画素のデータを床面の或る識別色に設定した
後、各二次元多角形データに従う多角形領域に対応する
画素の色指定を、その二次元多角形データに指定されて
いる色指定に更新していくことにより作成される。

【００４７】二次元多角形データで表される図形と、色
指定平面図の画素との対応付けは、図形について適当な
小間隔で取る各点の座標を、一定の線形変換によって画
素座標に変換することにより行う。

【００４８】図７は、このような画素の色指定データか
らなる色指定平面図を概念的に説明する図であり、ベッ
ド、机、洗面台その他の構造物の有る室内の平面図であ
り、それらの構造物で隠されない床面に、網かけ模様で
示すように識別色（床と出入口で異なる２色がある）の
色指定がされ、白地のままの部分は識別色以外の色の色
指定とされる。

【００４９】図２において、衝突検知装置30は平面図記
憶部31、指示部32、判定部33、前位置記憶部34からな
り、各部はそれぞれ図１の平面図記憶部１、指示部２、
判定部３、前位置記憶部４に対応する。

【００５０】又判定部33は、図１の線分生成部６及び交
差検出部７に対応する、線分生成部36及び交差検出部37
からなる。図６は衝突検知装置30の処理の流れの一例を
示す図であり、この衝突検知装置30は識別色によって交
差検出を行うものとし、このために交差検出部７には、
必要な識別色の色指定が予め記憶されているものとす
る。

【００５１】衝突検知装置30は図６の処理ステップ10で
前記のように視野設定部22から視点の出発点位置又は現
位置を受け取って処理を開始する。例えば前記ＸＺ軸の
二次元座標によって示す視点の位置を、出発点位置又は
現位置の別を示す情報と共に指示部32が受け取ると、処
理ステップ11でその情報種別を識別して、出発点位置の
場合には処理ステップ12で前位置記憶部34に前位置とし
てその座標値を記憶し、処理ステップ10に戻る。

【００５２】現位置であれば判定部33に現位置座標を渡
すので、線分生成部36が処理ステップ13で現位置座標と
前位置記憶部34に保持する前位置座標とで表される両点
を結ぶ線分を定める。

【００５３】この線分について、交差検出部37が平面図
記憶部31に平面図管理部24から渡されている平面図35
（色指定平面図）を使用して、線分と平面図上の障害物
図形との交差を検出するために、処理ステップ14で前記
線分上の点を平面図の画素に対応付ける変換を前記のよ
うに行い、対応する画素の色指定を調べる。

【００５４】処理ステップ15で、色を調べた結果を識別
し、線分に対応する画素の指定色がすべて識別色であっ
た場合には、処理ステップ16で指示部32を経て視野設定
部22に衝突無しを通知し、処理ステップ17で前位置記憶
部34の記憶を視点の現位置の値に更新して処理ステップ
10に戻る。

【００５５】処理ステップ15で、線分に対応する画素の
中に１画素でも識別色と異なる色の色指定があったと識
別した場合には、処理ステップ18で、視野設定部22に衝
突有りを通知して処理ステップ10に戻る。

【００５６】

【発明の効果】以上の説明から明らかなように本発明に
よれば、リアルタイム・ウォークスルーにおける視点等
の移動体の移動における衝突検出処理において、移動体
の衝突検出を高速に処理できるという著しい工業的効果
がある。

【図面の簡単な説明】

【図１】 本発明の構成を示すブロック図

【図２】 本発明の実施例を示すブロック図

【図３】 本発明実施例の処理の流れ図

【図４】 平面図作成処理の流れ図

【図５】 平面図を説明する図

【図６】 衝突検知装置の処理の流れ図

【図７】 色指定平面図の例を説明する図

【符号の説明】

１、31 平面図記憶部 ２、32 指示部 ３、33 判定部 ４、34 前位置記憶部 ５、35 平面図 ６、36 線分生成部 ７、37 交差検出部 10〜18、40〜58 処理ステップ 21 入力部 22 視野設定部 23 画像生成部 24 平面図管理部 27 平面図データ 28 三次元データ 29 ディスプレイ 30 衝突検知装置

Claims (2)

【特許請求の範囲】
1. 【請求項１】 三次元データによって表される三次元空
   間内の構造物について、該構造物に設定した基準平面に
   関して、該基準平面に平行な移動平面内を移動する点で
   代表される移動体と、該基準平面上に配置されている構
   造物との衝突を検知する装置であって、 平面図記憶部(1)と、指示部(2)と、判定部(3)と、前位
   置記憶部(4)とを有し、 該平面図記憶部(1）は、該移動平面でクリッピングした
   該三次元データに関して、該移動平面から該基準平面ま
   でに配置されている構造物を、該基準平面に平行投影し
   た図形を表す二次元データを平面図(5)として保持して
   おり、 該指示部(2）は、該移動体を代表する点の各現位置を該
   基準平面上に投影した点を示す二次元座標値を現位置座
   標として該判定部(3)に順次入力し、 該判定部(3)は、線分生成部(6)と、交差検出部(7)とを
   有し、 該線分生成部(6)は、該指示部(3)から入力された該現位
   置座標と該前位置記憶部(4)に記憶する座標とで表され
   る両点を結ぶ線分を生成し、 該交差検出部(7)は、該平面図記憶部(1)に保持する該平
   面図(5）を参照して、該平面図の該平行投影された構造
   物と、該線分生成部(6)が生成した線分との交差を識別
   して、該交差の有無を該指示部(2)に返し、 該前位置記憶部(4)は、記憶内容を該判定部(3)の処理し
   た該現位置座標に更新するように構成されている三次元
   移動体の衝突検知装置。
2. 【請求項２】 前記平面図記憶部(1)の保持する前記平
   面図(5)には色指定を有し、前記基準平面が該平面図上
   に表れているすべての部分には識別色とする所定の色が
   指定され、他の部分すべてには該識別色以外の色が指定
   されていて、 前記交差検出部(7)の前記交差の識別は、前記線分上の
   すべての点に対応する部分の該色指定が該識別色である
   ことにより交差が無いと識別する、請求項１記載の三次
   元移動体の衝突検知装置。