JP2000268192A - 近接判定方法及びプログラム提供媒体、並びに情報処理装置 - Google Patents

Abstract

(57)【要約】 【課題】 従来、分散共有仮想空間システムにおいて
は、仮想物体や、知覚領域（ＡＯＩ）が定期的に位置を
更新すると、サーバの単位時間あたりの演算量が、仮想
物体とＡＯＩの数の積に比例して増大してしまってい
た。 【解決手段】 仮想空間に仮想物体を追加・削除・移動
した場合には、先ず、空間テーブルを更新する。続い
て、空間テーブルに示された部分領域に関係のあるＡＯ
Ｉを求める。そして、ＡＯＩ内の仮想物体を再チェック
し、必要があれば、すなわち近接検出の候補が変わって
いればルーティングテーブルを更新する。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、分散共有仮想空間
システムにおいて、多数の情報処理端末がそれぞを反映
させて動かす仮想物体間の、知覚領域への出入りを検出
するための近接判定方法、及び近接判定プログラムを提
供するプログラム提供媒体、並びに複数の操作者が操作
する複数の情報処理端末にネットワークを介して接続
し、上記近接判定方法を実行する情報処理装置に関す
る。

【０００２】

【従来の技術】複数の操作者（ユーザ）が操作する複数
の情報処理端末（クライアント）と、これら複数のクラ
イアントにネットワークを介して接続している情報処理
装置（サーバ）からなり、サーバを介して複数のクライ
アントに分散して展開される共有の仮想空間上でクライ
アント同士等がコミュニケーションをとる分散共有仮想
空間システムが広く知られるようになった。

【０００３】このシステム上で行われる分散共有空間コ
ミュニケーションでは、ネットワーク的に分散したユー
ザがクライアントプログラムを通じてあるサーバにアク
セスし、他のユーザとコミュニケーションをとる。ま
た、クライアントプログラムはユーザなしで自律動作す
るプログラムである場合もある。

【０００４】分散共有仮想空間システムの具体例として
は、Habitat（商標）と呼ばれるサイバースペースのサ
ービスが知られている。Habitatは、米国LucasFilm社に
よって1985年から開発が始められ、米国商業ネットワー
クであるQuantumLink社で約３年間運用された後、1990
年2月に富士通Habitat（商標）としてNIFTY~Serveでそ
のサービスが開始されたものである。このHabitatにお
いては、２次元グラフィックスで描画された「ポピュロ
ポリス（Populopolis）」と呼ばれる仮想の都市に、ア
バタ（avatar；インド神話に登場する神の化身）と呼ば
れるユーザの分身（ユーザ自身を表すオブジェクト）を
送り込み、ユーザ同士がチャット（Chat；文字の入力と
表示によるテキストベースでのリアルタイムの対話）な
どを行うことができる。このHabitatの更に詳細な説明
は、サイバースペース，マイケル・ベネディクト編，19
94年3月20日初版発行，ＮＴＴ出版 ISBN4−87188−265
−9C0010（原著；Cyberspace：First Steps ,Michael B
enedikt,ed. 1991,MIT PressCambrige,MA ISBN0−262−
02327−X）第282頁乃至第307頁に記載されている。

【０００５】この種のパソコン通信サービスで運用され
ている従来のサイバースペースシステムにおいては、仮
想的な街並みや部屋の内部の様子が２次元グラフィック
スで描画されており、アバタを奥行きまたは手前方向へ
移動させる場合、単にアバタを２次元グラフィックスの
背景上で上下に移動させるだけであり、仮想空間内での
歩行や移動を疑似体験させるには表示の上での表現力が
乏しかった。また、自分の分身であるアバタと他人のア
バタが表示された仮想空間を、第３者の視点で見ること
になるため、この点においても、疑似体験の感覚が損な
われるものであった。

【０００６】そこで、特開平9-81781号公報に開示され
ているように、仮想空間を３次元グラフィックスで表示
し、ユーザがアバタの視点で自由に歩き回れる機能が、
VRML(Virtual Reality Modeling Language)と呼ばれる
３次元グラフィクスデータの記述言語を利用することに
よって実現されている。このVRMLの詳細は、例えば、
「VRMLを知る：３次元電脳空間の構築とブラウジング
〔マーク・ペッシ著，松田晃一・蒲地輝尚・竹内彰一・
本田康晃・暦本純一・石川真之・宮下健・原和弘訳，１
９９６年３月２５日初版発行，プレンティスホール出版
ISBN4-931356-37-0〕（原著；VRML：Browsing & Buildi
ng Cyberspace,Mark Pesce, 1995 New Readers Publish
ing ISBN 1-56205-498-8））」、または「VRMLの最新動
向とCyberPassage〔松田晃一・本田康晃著、bit（共立
出版）／1996 Vol.28 No.7 pp29乃至pp36, No.8 pp57乃
至pp65, No.9 pp29乃至pp36, No.10 pp49乃至pp58〕」
等の文献に記載されている。

【０００７】また、「The Virtual Reality Modeling L
anguage Version 2.0, ISO/IEC CD14772」の公式かつ
完全な仕様書は、「http://www.vrml.org/Specificatio
ns/VRML2.0/FINAL/spec/index.html」で公開されてお
り、その日本語版は、「http://www.webcity.co.jp/inf
o/andoh/VRML/vrml2.0/spec-jp/index.html」で公開さ
れている。

【０００８】VRMLの最新の言語であるVRML2.0において
は、３次元的な仮想空間内におけるオブジェクトの自律
的な振る舞い（Behavior）を記述し、表現することが可
能とされている。これにより、例えば、VRML2.0用ブラ
ウザに３次元グラフィックスで表示された仮想空間、す
なわち、３次元仮想空間を、アバタの視点で歩き回る場
合には、ユーザは、自身がその３次元仮想空間内に実際
にいるかのような感覚を享受することができる。

【０００９】このVRML2.0用ブラウザおよび共有サーバ
用ソフトウェアとしては、例えば、本出願人であるソニ
ー株式会社が「Community Place(商標) Browser / Bure
au」として開発し、製品化しており、そのβ版（試供
版）を、インターネット上のホームページ「http://vs.
sony.co.jp」からダウンロードすることが可能とされて
いる。

【００１０】ところで、３次元仮想空間には複数のユー
ザに対応するアバタやオブジェクトが存在しているが、
実際にクライアントＰＣに分散されて表示される３次元
仮想空間はその一部であり、自己のアバタから遠く離れ
たオブジェクト（アバタを含む）の位置情報等は当分必
要ではない。

【００１１】そこで、クライアントＰＣとして使用する
パーソナルコンピュータの処理能力やネットワークの通
信量を考慮して、相互に位置情報を通信するオブジェク
トの数を制限することにより、３次元仮想空間の表示を
速やかに行えるようにしている。このため、クライアン
トはシステムに接続された膨大な他のクライアントの全
体を知ることなく、コミュニケーションの必要な相手を
見つけ出せる。この機能はサーバによって提供されなけ
ればならない。

【００１２】したがって、このような分散共有仮想空間
システムに使われるサーバは、アバタなどの遠隔仮想物
体同士が近接したイベントをもらさず検出する機能を有
している。この機能を近接検出とよぶ。

【００１３】この近接検出は、各仮想物体毎に知覚領域
（Area Of Interest：ＡＯＩ）として所定の半径の球状
領域を設定し、そのＡＯＩへの他の仮想物体の出入りを
判定することで行われてきた。

【００１４】また、仮想物体が位置を更新する度に仮想
空間の全てのＡＯＩとの距離判定を行い、ＡＯＩが位置
を更新する度に全ての仮想物体との距離判定を行ってい
た。

【００１５】

【発明が解決しようとする課題】しかし、仮想物体や、
ＡＯＩが定期的に位置を更新すると、サーバの単位時間
あたりの演算量が、仮想物体とＡＯＩの数の積に比例し
て増大してしまうという問題が発生してしまう。

【００１６】また、その結果、ある仮想空間を同時に共
有できる仮想物体の数やクライアントの数が制限されて
しまうという問題も発生してしまう。

【００１７】本発明は、上記実情に鑑みてなされたもの
であり、知覚領域と仮想物体の近接を調べるための演算
量を減らし、情報処理装置の負荷を減少させることので
きる近接判定方法及びそのプログラム提供媒体の提供を
目的とする。

【００１８】また、知覚領域と仮想物体の近接を調べる
ための演算量を減らすことができ、より多くのユーザが
同時に接続できるようになる情報処理装置の提供を目的
とする。

【００１９】

【課題を解決するための手段】本発明に係る近接判定方
法は、上記課題を解決するために、仮想空間を分割した
部分領域を、任意の仮想物体が別の仮想物体を知覚する
ための知覚領域の単位とし、任意の仮想物体の知覚領域
内に別の仮想物体（又は別の知覚領域）が入ったときに
任意の仮想物体に対して別の仮想物体が近接したと判定
する。

【００２０】また、本発明に係る近接判定方法は、上記
課題を解決するために、仮想空間を分割した部分領域
を、仮想物体毎の持つ別の仮想物体を知覚するための知
覚領域に、別の仮想物体が近接したか否かの判定に用い
る。

【００２１】また、本発明に係るプログラム提供媒体
は、上記課題を解決するために、仮想空間における任意
の仮想物体に対して別の仮想物体が近接したことを判定
する近接判定プログラムを提供するプログラム提供媒体
であって、任意の仮想物体が別の仮想物体を知覚するた
めの知覚領域を求める工程と、上記仮想空間を分割した
部分領域に属する仮想物体リストを示す空間テーブルを
更新し、この空間テーブルを用いて上記知覚領域に対す
る仮想物体の入出の変化を判定する工程とを備えてなる
近接判定プログラムを提供する。

【００２２】また、本発明に係るプログラム提供媒体
は、上記課題を解決するために、仮想空間における任意
の仮想物体に対して別の仮想物体が近接したことを判定
する近接判定プログラムを提供するプログラム提供媒体
であって、上記仮想空間を分割した複数の部分領域の内
で、任意の仮想物体が別の仮想物体を知覚するための知
覚領域の中心から別の仮想物体の中心までの距離が、上
記知覚領域の半径よりも小さいか否かを判定する工程
と、上記工程で上記知覚領域の半径よりも小さい距離に
あると判定した別の仮想物体を近接したとする工程とを
備えてなる近接判定プログラムを提供する。

【００２３】本発明に係る情報処理装置は、上記課題を
解決するために、複数の操作者が操作する複数の情報処
理端末に、ネットワークを介して接続している情報処理
装置において、上記複数の情報処理端末上に展開される
共通の仮想空間を分割した部分領域を、任意の情報処理
端末を反映した任意の仮想物体が別の仮想物体を知覚す
るための知覚領域の単位とし、任意の仮想物体の知覚領
域内に別の仮想物体（又は別の知覚領域）が入ったとき
に任意の仮想物体に対して別の仮想物体が近接したと判
定する制御手段を備え、上記任意の情報処理端末を反映
した任意の仮想物体に対して上記制御手段が近接したと
判定した別の仮想物体に反映された別の情報処理端末
に、上記任意の情報処理端末からメッセージを送受信さ
せる。

【００２４】また、本発明に係る情報処理装置は、上記
課題を解決するために、複数の操作者が操作する複数の
情報処理端末に、ネットワークを介して接続している情
報処理装置において、上記複数の情報処理端末上に分散
して展開される共有の仮想空間を分割した部分領域を、
仮想物体毎の持つ別の仮想物体を知覚するための知覚領
域に、別の仮想物体が近接したか否かの判定に用いる制
御手段を備え、上記任意の情報処理端末を反映した任意
の仮想物体に対して上記制御手段が近接したと判定した
別の仮想物体に反映された別の情報処理端末を、上記任
意の情報処理端末との間でメッセージを送受信させる対
象とする。

【００２５】

【発明の実施の形態】以下、本発明の実施の形態につい
て図面を参照しながら説明する。図１は本発明を適用し
た分散共有仮想空間システムの構成例を表している。な
お、本明細書中において、システムとは、複数の装置が
論理的に集合した物をいい、各構成の装置が同一筐体中
にあるか否かは問わない。

【００２６】図１において、クライアントＰＣ（パーソ
ナルコンピュータ）１乃至３は、IP（インターネット接
続サービスプロバイダ）４乃至６を介してインターネッ
ト（The Internet）７と接続されており、VRMLブラウザ
及びWWWブラウザがインストールされ、インストールさ
れたこれらのブラウザが動作するようになされている。

【００２７】クライアントＰＣ１乃至３は、３Ｄクライ
アントおよび２Ｄクライアントの２つの機能を有してい
る。３Ｄクライアントは、定期的あるいは必要なときに
自分の位置情報などの情報を共有サーバ１２に通知し、
また、共有サーバ１２から送られてくる他の３Ｄオブジ
ェクトの共有情報を受信し、それを表示させる機能を有
している。２Ｄクライアントは、HTTPに基づいてWWWサ
ーバ１０に情報をリクエストし、その返事を受け取っ
て、主に２次元情報を表示する機能を有する。３Ｄクラ
イアントは、共有サーバ１２から受け取った情報内にUR
Lが含まれている場合、２Ｄクライアントに、URLへのア
クセスを要求する。２Ｄクライアントは、この要求に基
づいてURL（WWWサーバ１０）にアクセスし、そこからデ
ータ（例えばオブジェクトの形状データ）をダウンロー
ドして、３Ｄクライアントに転送する。

【００２８】インターネット７とルータ８を介して接続
されたLAN(Local Area Network)９には、WWWサーバ１
０、WLS（World Location Server）１１、共有サーバ１
２、ＡＯ(Application Object)サーバ１３，１４、メー
ルサーバ１５、およびコミュニケーションサーバ１６が
接続されている。これらの各サーバ１０乃至１６には、
ハードディスク（HDD）１０ａ，１０ｂ，１１ａ乃至１
６ａが、各々設けられている。

【００２９】なお、ＡＯサーバ１３は、共有サーバ１２
と通信するプログラムを有し、例えば仮想空間内におい
て、自律的に動作するロボットや電子ペットなどのアプ
リケーションオブジェクト（ＡＯ）を提供する。ＡＯサ
ーバ１３は、３Ｄクライアントと同様に、共有サーバ１
２と通信し、自分自身の情報を通知したり、他の３Ｄオ
ブジェクトの共有情報を受信したりする。

【００３０】コミュニケーションサーバ１６は、公衆電
話回線網１７を介して電話機１８やファクシミリ１９と
接続され、また、ＰＨＳ（登録商標）（Ｐｅｒｓｏｎａ
ｌ Ｈａｎｄｙｐｈｏｎｅ Ｓｙｓｔｅｍ）サービスプ
ロバイダ２０を介してPHS端末２３に無線接続され、さ
らに、ポケットベル（登録商標）サービスプロバイダー
２１を介してポケットベル端末２４に無線接続されてい
る。

【００３１】図２はクライアントＰＣ１のハードウェア
の構成例を示すブロック図である。この例において、CP
U３０は、ROM３４に記録されているプログラムに従って
各種の処理を実行するようになされており、HDD３１はV
RML 2.0ファイルや、Java(米国 Sun Microsystems社の
商標)により記述された所定のスクリプトプログラム等
からなるVRMLコンテンツなどが格納されている。CD-ROM
ドライブ３２は、CD−ROMディスク３３に格納されたVRM
Lコンテンツ等の情報を読み取るようになされている。

【００３２】サウンド処理回路３５は、マイクロフォン
３６と左右のスピーカ３７，３８が接続されており、マ
イクロフォン３６からの音声を入力し、または、音楽や
効果音等をスピーカ３７，３８から出力する。モデム３
９は、インターネット７に接続され、データを授受する
ようになされている。I/O（入出力）インタフェース４
０はマウス４１とキーボード４２からの操作信号を受け
付けるようになされている。グラフィックス回路４３
は、VRAM４４が内蔵されており、各種の処理を施した画
像データをVRAM４４に格納し、VRAM４４から読み出した
画像データを、CRTモニタ４５に表示させる。

【００３３】RAM４６には、実行時に、例えば、Windows
95(米国Micro Soft社の商標) の上で動作するWWWブラウ
ザであるNetscape Navigator、Javaインタプリタ、およ
び、本出願人であるソニー株式会社によって開発された
VRML2.0ブラウザであるCommunity Place Browserが読み
込まれて、CPU３０によって実行される状態とされてい
る。

【００３４】VRML2.0ブラウザには、米国シリコングラ
フィクス社によって開発され、無償公開されているVRML
の構文解釈用ライブラリ(パーサ)であるQvLibと、英国C
riterion Software Ltd.のソフトウエアレンダラである
RenderWare等、もしくはこれらと同等の機能を有するパ
ーサやレンダラが実装されている。

【００３５】そして、 Community Place Browserは、図
１に示すように、WWWブラウザとしてのNetscape Naviga
torとの間において、NCAPI（Netscape Client Applicat
ionPrograming Interface）（商標）に基づいて各種デ
ータの授受を行う。

【００３６】Netscape Navigatorは、インターネット７
を介してWWWサーバ１０よりHTMLファイルとVRMLコンテ
ンツ(VRMLファイルとJavaによるスクリプトプログラム
とを含む）の供給を受けると、これらをローカルのHDD
３１にそれぞれ記憶させる。Netscape Navigatorは、こ
のうちのHTMLファイルを処理してテキストや画像をCRT
モニタ４５に表示する一方、 Community Place Browser
はVRMLファイルを処理して３次元仮想空間をCRTモニタ
４５に表示させるとともに、Javaインタプリタによるス
クリプトプログラムの処理結果に応じて、３次元仮想空
間内のオブジェクトの挙動、その他の表示状態を変化さ
せる。

【００３７】なお、図示は省略するが、他のクライアン
トＰＣ２やクライアントＰＣ３も、クライアントＰＣ１
と同様に構成されている。

【００３８】次に上述した一実施の形態の動作につい
て、図３乃至５を参照して説明する。図３において、番
号１で示すように、最初に、WWWブラウザを用いて、VRM
Lコンテンツを提供しているWebサイトのホームページを
閲覧する。この例では、 「http://pc.sony.co.jp/sapa
ri/」を閲覧している。次に、番号２で示すように、ク
ライアントＰＣ１またはクライアントＰＣ２のユーザ
は、VRML2.0ファイルと、VRML空間内での自律的な動き
を実現するためのスクリプトプログラム（Javaによるス
クリプトプログラム）とからなるVRMLコンテンツを、そ
れぞれダウンロードする。

【００３９】勿論、 CD-ROMディスク３３で提供されるV
RMLコンテンツをCD−ROMドライブ３２で読み込んでも良
い。

【００４０】次に、図４に示すように、クライアントＰ
Ｃ１またはクライアントＰＣ２では、それぞれにダウン
ロードされ、一旦ローカルのHDD３１に格納されたVRML
2.0ファイルを、VRML2.0ブラウザであるCommunity Plac
e Browserが解釈するとともに実行し、さらに番号３で
示すように、VSCP(Virtual Society Server Client Pro
tocol)に基づいて、WLS１１に対して共有サーバ１２のU
RLを問い合わせる。このとき番号４で示すように、WLS
１１は、HDD１１ａに格納された共有サーバURL管理テー
ブルを参照して、クライアントＰＣ１またはクライアン
トＰＣ２に対して、共有サーバ１２のURLを通知する。

【００４１】このURLを用いて、図５に示すように、ク
ライアントＰＣ１とクライアントＰＣ２が、共有サーバ
１２に接続する。その結果、番号５で示すように、この
共有サーバ１２を介して共有3Dオブジェクトの位置や動
きなどに関する共有メッセージの送信が行われ、番号６
で示すように、その転送が行われ、マルチユーザ環境が
実現される。

【００４２】なお、以上の接続手順の詳しい説明につい
ては、特開平9-81781号公報を参照されたい。

【００４３】また、ここでは、３次元仮想空間を、マル
チユーザ環境で使用することとしているが、マルチユー
ザ環境で使用しないこと（以下、適宜、シングルユーザ
環境という）、即ち、自身以外の他のユーザのアバタ
（ドローンアバタ）を登場させないようにするととも
に、自身のアバタ（パイロットアバタ）を、他のユーザ
のクライアントの３次元仮想空間に登場させないように
することも可能である。これは、上述した番号３乃至６
で表した処理を行わないようにすることで実現すること
ができる。

【００４４】次に、図６を参照して、知覚領域（ＡＯ
Ｉ）の具体例である、オーラについて説明する。同図に
示すように、パイロットアバタ５１の周囲には、パイロ
ットアバタ５１を中心とする所定の半径を有する球より
なるオーラ５２が形成される。パイロットアバタ５１
は、オーラ５２の内部に位置する他のオブジェクトから
の情報を受信することができる。具体的には、図６に示
すように、パイロットアバタ５１は、オーラ５２内に位
置するドローンアバタ５３−１とオブジェクト（ＡＯ）
５４−１を視認することができる（それらの画像がパイ
ロットアバタ５１のクライアントＰＣのCRTモニタに表
示される）が、オーラ５２の外部に位置するドローンア
バタ５３−２やオブジェクト５４−２を視認することが
できない（ドローンアバタ５３−２やオブジェクト（Ａ
Ｏ）５４−２の画像は、パイロットアバタ５１のクライ
アントＰＣのCRTモニタには表示されない）。

【００４５】他のドローンアバタ５３−１，５３−２、
オブジェクト５４−１，５４−２にも同様にオーラが設
定される。なお、このシステムにおいては、各クライア
ントＰＣが対応するアバタのオーラは同一の大きさとさ
れるが、ＡＯのオーラは、必要に応じてアバタのオーラ
とは異なる範囲に設定される。

【００４６】このように、オーラ５２を規定すること
で、パイロットアバタ５１は、ドローンアバタ５３−１
とオブジェクト５４−１からの情報を受け取る必要があ
るが、オーラ５２の外部に位置するドローンアバタ５３
−２またはオブジェクト５４−２からの情報は受信する
必要がないので、受信する情報量を制限することが可能
となる。

【００４７】すなわち、例えば、図７に示すように、ア
バタ５１が移動すると、その新たな位置情報が共有サー
バ１２に転送される。共有サーバ１２は、アバタ５１の
新たな位置に対応するオーラ５２の内部にどのようなオ
ブジェクト（アバタを含む）が位置するのかを判断し、
そのオブジェクトに関する情報をアバタ５１のクライア
ントＰＣに通知する。図７に示す例では、アバタ５１の
移動後のオーラ５２の内部にオブジェクト５４−１が存
在するため、共有サーバ１２は、オブジェクト５４−１
の情報をアバタ５１のクライアントＰＣに通知する。こ
れにより、アバタ５１のクライアントＰＣには、オブジ
ェクト５４−１の画像が表示され、アバタ５１のユーザ
は、オブジェクト５４−１を視認することができる。

【００４８】つまり、共有サーバ１２は、アバタなどの
遠隔仮想物体同士が近接したイベントをもらさず検出し
ている。この近接検出は、各仮想物体毎に所定の半径の
球状領域をＡＯＩと設定し、そのＡＯＩへの他の仮想物
体の出入りを判定することで行ってきた。

【００４９】したがって、仮想物体が位置を更新する度
に仮想空間の全てのＡＯＩとの距離判定を行い、ＡＯＩ
が位置を更新する度に全ての仮想物体との距離判定を行
っていた。

【００５０】しかし、仮想物体や、ＡＯＩが定期的に位
置を更新すると、サーバの単位時間あたりの演算量が、
仮想物体とＡＯＩの数の積に比例して増大してしまうと
いう問題が発生してしまう。

【００５１】また、その結果、ある仮想空間を同時に共
有できる仮想物体の数やクライアントの数が制限されて
しまうという問題も発生してしまう。

【００５２】そこで、共有サーバ１２は、本発明の近接
判定方法を用いて別の仮想物体の近接を判定する。すな
わち、仮想空間を分割した部分領域を、任意の仮想物体
が別の仮想物体を知覚するための知覚領域の単位とし、
任意の仮想物体の知覚領域内に別の仮想物体（又は別の
知覚領域）が入ったときに別の仮想物体が近接したと判
定する。

【００５３】図８は上記共有サーバ１２がマルチユーザ
サーバとして動作するときの概念を説明するための図で
ある。共有サーバ１２は各ユーザが発するメッセージを
どのユーザに転送するかを表すルーティングテーブルを
持っており、そのテーブルに沿って各ユーザからのメッ
セージを他の各ユーザに転送する。図８に示した具体例
では、ユーザＤの発するメッセージ（チャットテキスト
による）はユーザＣ，Ａ，Ｂに転送されるが、ユーザＥ
の発するメッセージは誰も受け取らない。

【００５４】一般に、仮想空間アプリケーションの場
合、仮想空間内で近いユーザ同士がインタラクションで
きるように、共有サーバは常に各ユーザの仮想空間内で
の位置を監視し、ルーティングテーブルを更新する。

【００５５】次に、図９には本発明の近接判定方法の概
念図を示す。３次元の仮想空間の一部を、平面に投影し
たものである。多くの場合、仮想空間の水平面であるＸ
−Ｚ平面が用いられる。投影面として仮想物体の分散が
大きい部分空間（平面）を選ぶと、仮想物体の集合を効
率良く分離できる。ただし投影は本発明に必ずしも必要
なわけではない。また、３次元空間以外の多次元空間で
あっても同様に適用できる。

【００５６】以後、簡単のため、投影された２次元空間
座標系を（ｘ，ｚ）と表記する。ある仮想物体の中心点
（ｘ，ｚ）がどの領域に存在するかは、以下の式（１）
に示すマッピング関数を用いて領域に固有なインデック
スを求めることによって高速に実現される。このマッピ
ング関数は、投影面を原点からある幅ｕ（＝１．０ｍ）
で格子状に分割する。分割された各領域には、ユニーク
なインデックスが割り当てられる。

【００５７】

【数１】

【００５８】ここで、int(a)は、aを越えない最大の整
数を返す関数である。

【００５９】仮想物体のＡＯＩは、その仮想物体に最も
近い４領域とする。このとき、ＡＯＩの領域の４つのイ
ンデックスは、（ｘ、ｚ）にオフセット（ｕ／２，ｕ／
２），（ｕ／２，−ｕ／２），（−ｕ／２，−ｕ／
２），（−ｕ／２，ｕ／２）をそれぞれ加えた座標を、
上記（１）式のマッピング関数を用いてマッピングする
ことで得られる。図９の例では、中心点（ｘ，ｚ）＝
（11.4m，11.3m）である仮想物体ＣのＡＯＩは、（１
０，１０），（１０，１１），（１１，１０），（１
１，１１）である。

【００６０】次に、ある領域を指定して、その中の仮想
物体のリストを取得するためのデータ構造について述べ
る。図１０には、図９の状態における、仮想物体リスト
のメモリへの格納イメージを示すハッシュ表を示す。ハ
ッシュ表は、メモリ上でデータを高速に検索するための
手法であり、各種のツリー構造とは異なり、静的な配列
だけで簡単に実装でき、効率が極めて高い。領域のイン
デックスをキーとし、仮想物体リストを格納するコンテ
ナを要素とする。この例では、領域（１０，１１）には
仮想物体Ａ，Ｂが存在している。また、領域（１１，１
０）には仮想物体Ｄが、領域（１２，１１）には仮想物
体Ｅが、領域（１１，１１）には仮想物体Ｃが存在して
いる。以後、この図１０に示すハッシュ表を部分領域の
インデックスをキーとし、その部分領域内の仮想物体リ
ストをエントリーする空間テーブルという。

【００６１】この方式の空間テーブルを用いると、空間
テーブルの大きさ、すなわち必要なメモリの量は仮想物
体の存在する領域の数に依存し、空間の広さに依存しな
いという利点がある。物体が存在する部分領域の数が著
しく増えたときのみ、動的にテーブルを拡張すればよ
い。また、このテーブルをハッシュ表を用いて実装する
ことで、インデックスからのエントリーの探索が高速と
なり、周囲の部分領域内の仮想物体をわずかな計算量で
リストアップできる。

【００６２】上記システムでは、仮想物体（とそのＡＯ
Ｉ）が仮想空間に追加・削除されたり、仮想空間内で移
動すると、共有サーバ１２はその仮想物体と周囲の仮想
物体群との近接検出を行う。

【００６３】図１１は、図９に示した仮想物体Ｃが移動
した例である。この例では図１０に示した空間テーブル
上での仮想物体リストの更新は起こらないが、仮想物体
ＣのＡＯＩは新たに（１１，１０），（１１，１１），
（１１，１２），（１２，１０）となる。この場合の近
接検出の候補は仮想物体Ｄ，Ｅである。

【００６４】通常、仮想空間に仮想物体を追加・削除・
移動した場合には、先ず、空間テーブルを更新する。続
いて、空間テーブルに示された部分領域に関係のあるＡ
ＯＩを求める。そして、ＡＯＩ内の仮想物体を再チェッ
クし、必要があれば、すなわち近接検出の候補が変わっ
ていればルーティングテーブルを更新する。

【００６５】図１２には仮想物体の更新による空間テー
ブルの更新処理を示す。仮想物体が、追加・削除・移動
したとき、ステップＳ１ではその仮想物体が属する部分
領域のインデックスを上記（１）式のマッピング関数を
用いて計算する。ステップＳ２では以前のインデックス
と変わったか否かを判定する。変わっていればステップ
Ｓ３に進む。

【００６６】ステップＳ３では領域テーブルの前のイン
デックスのエントリーからその仮想物体の参照を削除す
る。ステップＳ４では新しいインデックスのエントリー
にその仮想物体の参照を追加する。

【００６７】ステップＳ５では更新が起きた領域内のす
べてのＡＯＩに対して、それぞれ更新を通知する。そし
て、ステップＳ６ではその仮想物体のＡＯＩに対して更
新を通知する。これにより空間テーブルが更新される。

【００６８】なお、ステップＳ２で以前のインデックス
と変わっていないと判断すればステップＳ６に進み、上
述した処理を行う。

【００６９】次に、図１３には、ＡＯＩの更新によるル
ーティングテーブルの更新処理を示す。

【００７０】ＡＯＩに、追加・削除・移動などの更新が
起きたとき、ステップＳ１１ではそのＡＯＩが属する部
分領域のインデックスを求める。ステップＳ１２ではイ
ンデックスを用いて空間テーブルから新しい仮想物体の
リストを取得する。

【００７１】ステップＳ１３では以前の近接仮想物体リ
ストと新しい近接仮想物体リストとを比較し、増減を得
る。ステップＳ１４ではルーティングテーブルの新たに
減った物体のエントリーから、それぞれＡＯＩを削除す
る。ステップＳ１５ではルーティングテーブルの新たに
増えた物体のエントリーに、それぞれＡＯＩを追加す
る。これによりルーティングテーブルが更新される。図
１４には更新されたルーティングテーブルの具体例を示
す。ユーザＣの移動にしたがって、ユーザＣはユーザ
Ａ，Ｂのルーティングエントリーから削除され、ユーザ
Ｅのルーティングエントリーに追加される。以後、ユー
ザＥの発したチャットテキスト等のメッセージは、ユー
ザＣにもルーティングされるようになる。

【００７２】なお、上記具体例では、仮想物体のＡＯＩ
を、その仮想物体に最も近い、４領域としたが、９領域
としてもよい。この場合、ＡＯＩの領域の９つのインデ
ックスは、０を含むプラスマイナスｕの組合せをオフセ
ットとして上記座標に加えることによって得られる。

【００７３】また、共有サーバ１２は、他の近接判定方
法を適用してもよい。仮想空間を分割した部分領域を、
仮想物体毎の持つ別の仮想物体を知覚するための知覚領
域の決定に用い、ここで決定した任意の仮想物体の知覚
領域内に別の仮想物体（又は別の知覚領域）が入ったと
きに別の仮想物体が近接したと判定する方法である。

【００７４】ＡＯＩは、しばしば球形の領域として実現
される。仮想物体の代表点がＡＯＩ球に入っているかど
うかは、物体の代表点とＡＯＩの代表点との距離と、Ａ
ＯＩ球の半径を比較して、距離が半径より小さければＡ
ＯＩに入っているものとしてルーティングが行われる。

【００７５】図１５には、ＡＯＩが球である場合の具体
例を示す。この例では、仮想物体ＣにはＤのみが近接し
ている。従来は仮想空間内のすべての物体と距離判定す
る必要があったが、この発明では限られた部分領域内
で、仮想物体の代表点とＡＯＩの代表点との距離と、Ａ
ＯＩ球の半径を比較すればよく、計算量を少なくでき
る。

【００７６】これは、図１２に示した処理により空間テ
ーブルを更新したのち、図１６に示す、ルーティングテ
ーブルの更新処理を行うことにより実行される。

【００７７】図１６のフローにおいて、ステップＳ１２
で周囲の部分空間に存在する仮想物体リストを取得した
後に、新しい物体リストから、ＡＯＩの代表点から物体
の代表点までの距離がＡＯＩ半径ｄより離れている物体
を除く、というしきい値処理をステップＳ１６で追加
し、ＡＯＩ球の外の候補を削ることで、球形のＡＯＩを
実現できる。

【００７８】このため、上記図１５に示したように限ら
れた領域内の仮想物体のみと距離判定を行えばよいため
従来の空間内のすべての仮想物体との距離判定を行う場
合に比べて大幅に計算量を減らすことができる。

【００７９】ただし、候補となる周囲の部分領域は、Ａ
ＯＩの球を投影した円を含まなければならない。つま
り、大きなＡＯＩであれば、候補として多くの部分領域
から仮想物体リストを取得するように実装しなければな
らない。

【００８０】さらに、本発明は、以下に示す具体例を適
用してもよい。この具体例は仮想物体が大きさを持つ場
合を想定している。

【００８１】これまでの実施例では、すべての仮想物体
の大きさは点として扱われてきた。しかし、仮想物体が
ある大きさを持つ場合にも本発明を適用できる。この場
合、図１７に示すように仮想物体の大きさを表す球を含
むように部分領域を選び、そのすべてに仮想物体の参照
を登録しておけばよい。

【００８２】すると、空間テーブルの例は図１８に示す
ようになる。つまり、仮想物体Ｂの代表点に最も近い４
つの領域にＢは存在する。この４つの領域は、ＡＯＩの
場合と同様に簡単に求められる。そして、この空間テー
ブルを用いて、ルーティングテーブルを更新する。

【００８３】なお、上記システムにおいて、供給サーバ
１２は、本発明のプログラム提供媒体から、近接判定プ
ログラムを読み取り、逐次実行することにより、本発明
の近接判定方法を容易に実行することができる。

【００８４】

【発明の効果】本発明に係る近接判定方法及びそのプロ
グラム提供媒体によれば、知覚領域と仮想物体の近接を
調べるための演算量を減らし、情報処理装置の負荷を減
少させることができる。

【００８５】また、本発明に係る情報処理装置によれ
ば、知覚領域と仮想物体の近接を調べるための演算量を
減らすことができ、より多くのユーザが同時に接続でき
るようになる。

【図面の簡単な説明】

【図１】本発明を適用した分散共有仮想空間システムの
構成例を示すブロック図である。

【図２】上記図１に示した分散共有仮想空間システム中
のクライアントＰＣの構成例を示すブロック図である。

【図３】上記図１に示した分散共有仮想空間システムの
動作を説明するための図である。

【図４】上記図１に示した分散共有仮想空間システムの
動作を説明するための他の図である。

【図５】上記図１に示した分散共有仮想空間システムの
動作を説明するためのさらに他の図である。

【図６】ＡＯＩの具体例を説明するための図である。

【図７】仮想物体（アバタ）が移動した場合のオブジェ
クトの知覚を説明するための図である。

【図８】上記分散供給仮想空間システム中の共有サーバ
がマルチユーザサーバとして動作するときの概念を説明
するための図である。

【図９】本発明の近接判定方法の概念を説明するための
図である。

【図１０】部分領域内の仮想物体リストをエントリーす
る空間テーブルを、ハッシュ表として示した図である。

【図１１】上記図９に示した仮想物体Ｃが移動した様子
を示す図である。

【図１２】仮想物体の更新による空間テーブルの更新処
理を示すフローチャートである。

【図１３】ＡＯＩの更新によるルーティングテーブルの
更新処理を示すフローチャートである。

【図１４】更新されたルーティングテーブルの具体例を
示す図である。

【図１５】ＡＯＩが球である場合を示す図である。

【図１６】ＡＯＩが球である場合に、ルーティングテー
ブルの更新処理を示す図である。

【図１７】仮想物体がある大きさを持つ場合を説明する
ための図である。

【図１８】仮想物体がある大きさを持つ場合の空間テー
ブルの具体例を示す図である。

【符号の説明】

１〜３ クライアントＰＣ、１２ 共有サーバ、５１
パイロットアバタ、５２ オーラ

フロントページの続き Ｆターム(参考） 5B050 BA07 CA08 FA02 5B089 GA11 GA21 JA17 JA18 JB16 KA06 KC15 KC47 KC60 LB18 LB21 5E501 AA02 AB19 AC16 AC32 BA12 CA02 DA02 DA04 EB20 FA15 FA27 FA36 FA43 FB44

Claims (12)

【特許請求の範囲】
1. 【請求項１】 仮想空間を分割した部分領域を、任意の
   仮想物体が別の仮想物体を知覚するための知覚領域の単
   位とし、任意の仮想物体の知覚領域内に別の仮想物体又
   は別の知覚領域が入ったときに別の仮想物体が近接した
   と判定することを特徴とする近接判定方法。
2. 【請求項２】 上記任意の仮想物体の中心に近い隣接し
   た複数の部分領域を上記知覚領域とし、別の仮想物体の
   中心がその中に入ったときに近接したと判定することを
   特徴とする請求項１記載の近接判定方法。
3. 【請求項３】 上記任意の仮想物体の中心に近い隣接し
   た４又は９の部分領域を上記知覚領域とすることを特徴
   とする請求項３記載の近接判定方法。
4. 【請求項４】 上記知覚領域を求める工程と、 上記部分領域に属する仮想物体リストを示す空間テーブ
   ルを更新し、この空間テーブルを用いて上記知覚領域に
   対する仮想物体の入出の変化を判定する工程とを備える
   ことを特徴とする請求項２記載の近接判定方法。
5. 【請求項５】 仮想空間を分割した部分領域を、仮想物
   体毎の持つ別の仮想物体を知覚するための知覚領域に別
   の仮想物体が近接したか否かの判定に用いることを特徴
   とする近接判定方法。
6. 【請求項６】 上記任意の仮想物体を中心とする所定半
   径の球を知覚領域とし、別の仮想物体の中心がその知覚
   領域に入ったときに近接したと判定することを特徴とす
   る請求項５記載の近接判定方法。
7. 【請求項７】 上記知覚領域と仮想物体はそれぞれを代
   表とする点を中心とする所定半径の球であり、球が接し
   たときに近接したと判定することを特徴とする請求項５
   記載の近接判定方法。
8. 【請求項８】 隣接した複数の上記部分領域内で、上記
   知覚領域の中心から別の仮想物体の中心までの距離が、
   上記知覚領域の半径よりも小さいか否かを判定する工程
   と、 上記工程で上記知覚領域の半径よりも小さい距離にある
   と判定した別の仮想物体を近接したとする工程とを備え
   ることを特徴とする請求項６記載の近接判定方法。
9. 【請求項９】 仮想空間における任意の仮想物体に対し
   て別の仮想物体が近接したことを判定する近接判定プロ
   グラムを提供するプログラム提供媒体であって、 任意の仮想物体が別の仮想物体を知覚するための知覚領
   域を求める工程と、 上記仮想空間を分割した部分領域に属する仮想物体リス
   トを示す空間テーブルを更新し、この空間テーブルを用
   いて上記知覚領域に対する仮想物体の入出の変化を判定
   する工程とを備えてなる近接判定プログラムを提供する
   ことを特徴とするプログラム提供媒体。
10. 【請求項１０】 仮想空間における任意の仮想物体に対
    して別の仮想物体が近接したことを判定する近接判定プ
    ログラムを提供するプログラム提供媒体であって、 上記仮想空間を分割した複数の部分領域の内で、任意の
    仮想物体が別の仮想物体を知覚するための知覚領域の中
    心から別の仮想物体の中心までの距離が、上記知覚領域
    の半径よりも小さいか否かを判定する工程と、 上記工程で上記知覚領域の半径よりも小さい距離にある
    と判定した別の仮想物体を近接したとする工程とを備え
    てなる近接判定プログラムを提供することを特徴とする
    プログラム提供媒体。
11. 【請求項１１】 複数の操作者が操作する複数の情報処
    理端末に、ネットワークを介して接続している情報処理
    装置において、 上記複数の情報処理端末上に展開される共通の仮想空間
    を分割した部分領域を、任意の情報処理端末を反映した
    任意の仮想物体が別の仮想物体を知覚するための知覚領
    域の単位とし、任意の仮想物体の知覚領域内に別の仮想
    物体又は別の知覚領域が入ったときに別の仮想物体が近
    接したと判定する制御手段を備え、 上記任意の情報処理端末を反映した任意の仮想物体に対
    して上記制御手段が近接したと判定した別の仮想物体に
    反映された別の情報処理端末を、上記任意の情報処理端
    末との間でメッセージを送受信させる対象とすることを
    特徴とする情報処理装置。
12. 【請求項１２】 複数の操作者が操作する複数の情報処
    理端末に、ネットワークを介して接続している情報処理
    装置において、 上記複数の情報処理端末上に分散して展開される共有の
    仮想空間を分割した部分領域を、仮想物体毎の持つ別の
    仮想物体を知覚するための知覚領域に、別の仮想物体が
    近接したか否かの判定に用いる制御手段を備え、 上記任意の情報処理端末を反映した任意の仮想物体に対
    して上記制御手段が近接したと判定した別の仮想物体に
    反映された別の情報処理端末を、上記任意の情報処理端
    末との間でメッセージを送受信させる対象とすることを
    特徴とする情報処理装置。