(23) KL/1による宣言型三次元アルゴリズム アニメーション システム
平成８年度委託研究中間報告
１ 研究テーマ、研究代表者：
（１）研究テーマ
KL/1による宣言型三次元アルゴリズムアニメーションシステム
（２）研究代表者（氏名、所属、役職）
東京工業大学大学院 情報理工学研究科 数理・計算科学専攻
助教授 松岡聡
〒152 東京都目黒区大岡山 2-12-1 (本館1F 73号室)
Tel/Fax 03-5734-3876
E-mail: matsu@is.titech.ac.jp
２ 記述項目：
（１）研究進捗状況
KL/1を含む並列言語で書かれたアルゴリズムやプログラムを、宣言的な視覚化
規則により三次元のアルゴリズムアニメーションとしてユーザに提示するシス
テムTRIP-3DAを、KLICを宣言規則の変換エンジンとして用いて研究開発してい
る。TRIP-3DAでは、ユーザは簡便な宣言的な規則によって様々な三次元の視覚
化技法やアニメーション技法を用いることが可能となるため、 Visual Janus
のような、従来の並列プログラム視覚化システムのように、ある特定の視覚化
のスタイルや技法に縛られることがない。また、複雑なアニメーションなども、
簡潔な記述によって可能であり、システムのデフォルトの視覚化も容易に修正
できる。本システムにより、KLICの並列プログラムのユーザは、アルゴリズム
やプログラムに適した様々な視覚化が容易に行えるようになることにより、並
列アルゴリズムやプログラムの開発・デバッグ・チューニング・解説・教育な
どを高度に支援することが可能になる。
現状では、研究の進捗状況は以下の通りである。
A) まず、三次元とそのアニメーション用の各VSRプリミティブの詳細仕様を決
定した(VSRについては(2)を参照)。特に、その具体的なインターフェースと、
制約解消系へのインターフェースを、実行時に制約系に矛盾が起きないように
設計した。
B) 現在は、Sicstus Prologで書かれている前身システムであるTRIP2-aをベース
に、KLIC用に新たに変換エンジンを開発中である。開発はOpenGL三次元アクセ
ラレータの搭載されたPC上で行なわれている。
B.1) 移植したTRIP-2aシステムの上に、設計した新たなVSRプリミティブを実
装中である。これらは、KLICのgeneric object機能を用いて実現している。
B.2) 同時に、制約解消系から、三次元のツールキットである
OpenGL/OpenInventorへのインターフェースや、その他のGUI部分を開発してい
る。この部分は、主にC/C++で記述している。
（２）現在までの主な成果
システムの完成により、ユーザは以下のようなモデルをベースに簡便にKLICの
プログラム上のアルゴリズムを三次元アルゴリズムアニメーションとして視覚
化可能になる。このモデルにおけるアプリケーションデータの視覚化は，アプ
リケーションのデータ表現(AR)から 絵のデータ表現(PR)への一連の変換と考
える．逆に，ユーザの絵に対する操作/変更のアプリケーションデータへの反
映は， PR から AR への変換として捉える．抽象構造表現(ASR)と絵構造表現
(VSR)とは，この変換を AR や PR に依存せずに実現するためのもので，それ
ぞれ AR と PR との構造を表すための一般的な中間表現である．つまり，
AR=>PR の変換を， ASR=>VSR の変換で表現する．また，それは宣言的に対応
規則によって記述できる．例えば、グラフ構造の視覚化のためには、ユーザは
以下のような規則を宣言する:
node(X) :-
sphere(X,15,[]),
label(l(X),X,[]),
contain(X,l(X),0,[]).
edge(A,B) :-
connect(A,B,center,center,[]),
planar_adjacent(A,B,1).
これにより、任意のグラフが三次元空間内のある平面上に表示される。
それぞれのグラフのノードは球として、ノード間のエッジは球をつなぐ
線として表示される。
さらに、アニメーションを扱うため，アプリケーションの実行にともなって変
化していくアプリケーションデータの列とそれに対応する図の列，及びそれら
をつないでいく「操作」の列がモデル化されている。アプリケーションが何ら
かの「操作」の実行をすると，モデル内の各データはそのデータ表現上での対
応する「操作」によって次の状態に移り、同時に絵のデータも対応する「操作」
によって，次の状態に移る。ここで、抽象構造表現(ASR)上での操作を「抽象
操作」絵構造表現(VSR)上での操作を「遷移操作」と呼ぶ。それぞれの「操作」
間を変換規則で対応づけ，遷移方法の指定ができるようにすることにより、ア
ニメーションの作成者は，この二つの間の対応規則を与えることで様々なアニ
メーションを作成できる。また、ユーザが指定しない部分は、操作のそれぞれ
の前後のモデル上でのデータの視覚化をキーフレームとして、その間を保管す
ることにより、アニメーションのデータを自動生成する。
具体的には、先のグラフ上でのなんらかのデータの遷移を、ノードの大きさの
変化(データがあるノードが大きい)で表すとすると、
traverse(X,Y) :- shrink(X, [smooth]), enlarge(X, [smooth]).
といった遷移操作の変換規則を指定するだけで良く、ノードのサイズの変化による
配置の変化などは、制約解消系が自動的に行う。また、本例では[smooth]といった
アニメーションに対する属性を付加することにより、アニメーションの遷移時にそ
れぞれがスムースに(この場合は線形な大きさの変化)かつ同時に大きさの変化のア
ニメーションが自動的に起こる。
（３）今後の研究概要
今後は、上記の B.1), B.2)のシステムの開発を続行させ、されにそれらを融
合することにより、TRIP-3DAを完成させる。さらに、システムの完成後、サン
プルプログラムとして、幾つかの並列アルゴリズムの三次元アニメーションの
視覚化を通じ、有効な視覚化法を探る。現状では、ハノイの塔、ソーティング、
8-queensを含む探索問題, グラフ系のアルゴリズム、等を予定している。
（４）今年度目標成果ソフトウェアイメージ
システムは大きく分けて、KLICユーザのためのAPI及びライブラリ、宣言的規則変
換部(ASR=>VSR)、制約解消部(VSR=>VR)、及び三次元アニメーション表示部の四つ
の部分より構成されている
- KLICユーザのためのAPI及びライブラリは、並列プログラムのプログラマが
視覚化したいアルゴリズム・プログラムで、状態の遷移を起こす部分を
Interesting Eventとして宣言する述語群よりなる。例えば、ソーティング
において、ユーザはSwapという状態変化を起こす遷移に対して、対応する
Intesting Eventを発生する述語をプログラム内に挿入する。
- 宣言的規則変換部(ASR=>VSR)はKLICにより記述されている。ここで、
Interesting Event, およびTRIP-3DA内のアプリケーションプログラムに対応
する内部状態が管理され、必要に応じて規則が適用されて、AR=>VRの変換が行
われる。ユーザは、上記のような三次元視覚化のためのルール群、および状態
遷移操作の視覚化のルール群を用意された述語のプリミティブを用いて記述
するだけで良い。これらは、多くの場合数十行程度である。これらの
ルールに基づき、VSRへの変換による視覚化およびアニメーション生成が
行われる。
- 制約解消部はC,C++で記述されており、VSRの制約集合からアニメーションの
キーフレームをシステムが制約解消により自動的に生成する。
- 視覚化およびGUIの部分は、制約解消系からの幾何座標などの出力を、VSRに
あった属性データと融合する。この段回で、キーフレーム補完やユーザからの
属性指定を総合し、適当なタイムステップで画面上にアニメーションとして表
示する。この部分は、三次元グラフィックスライブラリである
OpenGL/OpenInventorを用いて、C++で記述されており、ユーザはアニメーショ
ンが実行されている間、様々な空間内の視点からアニメーションを眺めること
ができる。また、アニメーションのスロー・ステップ実行や、バックトラック
なども、用意されたユーザインターフェースで制御可能である。
---
以上
www-admin@icot.or.jp