No Slide Title

メディア情報学 論文輪講 「歴史的システム」
Sketchpad
A Man-Machine Graphical
Communication System
2003年10月17日
電子情報学専攻 D2 柿本正憲
(原島・苗村研究室)
2015/9/30
1
出典
• Ivan E. Sutherland (MIT)
• Sketchpad: A Man-Machine Graphical
Communication System
• Proc. AFIPS Spring Joint Computer Conference,
pp. 329-346, May 1963.
• MIT Lincoln Laboratory Technical Report #296,
January 1963. (PhD thesisの一部)
2/32
著者について
アイバン・サザーランド(1938- )
(コンピュータグラフィックスの父と
呼ばれている)
1963 MITでSketchpadを発表(PhD論文)
1966 「10の未解決のCG問題」発表
1967 Head Mounted 3D Displayを発表(ハーバード大)
1968 「10種類の隠面消去アルゴリズム」発表
1968 Evans & Sutherland社を設立
1970代
ユタ大・Caltechで、のちのCG界の重鎮たちを育てる
1988 ACM チューリング賞受賞
1996 Smithsonian Computer World Award受賞
3/32
概要
• Sketchpadシステムを開発
• ディスプレイ上にライトペンで線を描くことでコン
ピュータと対話
– キーボード入力では困難な応用に使う
• マン・マシン・コミュニケーションに新たな領域
• CADの概念を提唱し、種々の機能を実装
• 想定する応用
– 機械部品の形状入力
– 電気回路の結線入力
4/32
構成
I.
簡単な描画例と応用分野の説明
(5)
II.
Ring構造
(1)
III. ライトペン
(2)
IV. 図形の描画
(3)
V.
(1)
さまざまな再帰的機能
VI. 製図のためのコピー機能
(5)
VII. 制約条件の適用
(1)
VIII. 応用例と結論
(7)
5/32
I. 簡単な作図例と応用分野の説明
ハードウェア構成
• TX-2 computer
– SPARCstation10の
百万分の一の性能
• ディスプレイ
• ライトペン
• 押しボタン
draw
move
circle center
terminate ・・・・・
• PACE(メーカー名)の1959年製プロッタ
– この論文のための作図
6/32
I. 簡単な作図例と応用分野の説明
直線の作図方法
円弧の作図方法
• draw で始点を固定
• circle center で中心決定
• 終点がライトペンに追従
• ライトペンを移動
• terminate で終点固定
• draw で始点と半径決定
• 円弧の終点がライトペンの
位置(角度)に応じ動く
• terminate で終点固定
7/32
I. 簡単な作図例と応用分野の説明
蜂の巣模様の作図に
使うさまざまな機能
• move で、以前描いた頂点
を選択して移動する
• terminate で移動終了
• 移動中の頂点を円弧上に
ロックする
• ボタンを押しながら指定した
複数の線分の長さを同じに
• delete で図形を消す
• 頂点を二つ指定してくっつける
8/32
I. 簡単な作図例と応用分野の説明
以上の作図例で言いたいこと
• 図形の座標データだけでなく接続・制約関係も保持
• Subpictureの概念(グループ化)
– Subpictureを作って、たくさんコピーした後にsubpicture形状を変
えると、全部がいっぺんに変わる
• 作図のプロセスはデザインのプロセスそのもの
– 従来の製図では、制約条件は部品の絵に追記
– Sketchpadでは、条件を「その部品」という概念に付加
• コンピュータは、図をきれいに描くだけでなく
健全なデザインを生み出す支援をする
9/32
I. 簡単な作図例と応用分野の説明
Sketchpadが役立つ応用分野
1. 部品の再利用を必要とする分野
2. 動きの可視化によって人間の洞察が深まる、科学
・工学分野
3. 回路図やダイアグラムなど、トポロジー情報(接続
情報)を必要とする分野
4. 非常に多くの繰り返しや再帰のある図形を描く必
要のある分野
10/32
II. リング構造
リング構造
• n-component要素(リスト)の最後から最初へポインタ
• さらに、要素を双方向ポインタでつなぐ
• 挿入・削除・追加・繰り
返し(順方向/逆方向)
階層的データ構造
• クラス階層と、実行時の
図形階層を定義
• 例えばLINESの中に
すべてのLINEのリング
構造を集約
11/32
III. ライトペン
光学的入力の利用
• 座標を入力するだけなら他のデバイスでもいい
• 既存図形の選択にペン先での入力を利用
– たくさんspotを、時分割で一つずつ次々表示
→ 視野(直径1.6cm)に入るspotを捉える
– そのspotにかかる図形(すぐに分かる)を候補に
– 選択のための計算時間を大幅に節約
空間分割法で図形の分布情報を作っておけば、ペン先の
座標がわかるだけで候補が絞れるのでは???
12/32
III. ライトペン
「ライトペンを捕まえる」ための領域
• ほとんどの図形には近傍の領域を用意
– ペン位置との距離計算ルーチンも
• ペンが図形の近傍にきたら
– カーソル(bright dot)が
その図形上にロックされる
– 擬似ペン位置
(pseudo pen location)
• ペンで移動中の図形は
ロックされた擬似ペン
位置に従う
– 他の図形と接続するのが
容易に
13/32
IV. 図形の描画
ランダムスキャンディスプレイ
• X軸Y軸それぞれ解像度10bitで制御
• 毎秒100,000個の点(spot)を表示
– 座標を一種の共有メモリ(display file)に格納
→ コンピュータとディスプレイが独立にアクセス
– Spotひとつ(36ビット長)のデータ構造
10bit
10bit
X座標
Y座標
16bit
ポインタ
n-componentの要素
– ポインタは、ライトペンで部品を認識するために使う
14/32
IV. 図形の描画
画面の拡大機能
• 2000倍まで拡大可能(20cm→400mの仮想世界)
線分と円の生成
• 差分方程式に従って点を描いていく
– 線分: xi  xi 1  x
yi  yi 1  y
2
– 円弧: x  x   y  y 
i
i 2
i 1
c
R
2
yi  yi  2   xi 1  xc 
R
15/32
IV. 図形の描画
英数字の表示
• 線分と円弧を組み合わせ、テーブルに格納
• さらに、文字と図形を組み合わせてSubpicture
として登録し、繰り返し使用できる
抽象概念の表示
• 制約条件のシンボル
• 数値情報
16/32
V. さまざまな再帰的機能
Subpictureの再帰呼
び出し
• Subpictureの中で同じ
Subpictureを使用可能
再帰的な削除
• 削除された要素を使って
いる要素も削除される
再帰的なマージ
• マージする前の要素が持
つ制約条件なども全要素
に波及する
17/32
VI. 製図のためのコピー機能
定義図形(definition picture)
• 点・線分・円弧を生成する操作を組み合わせて作った特定の形
• コピーして使うための図形
• 任意の部分に“attacher”を設定できる
定義図形のコピー
• 最後に設定されたattacherはライトペンとともに動く
• その前のattacherは、コピーボタンを押した瞬間にライトペンが近
傍にある別の図形にロックされる
• 制約条件もコピーされる
• そのほかのattacherは、制約条件がなければ元の図形とマージ
される
18/32
VI. 製図のためのコピー機能
Quiz 1
• この図形をコピーして、
ライトペンを動かしたら
どうなるか?
• 制約Mは「同じ長さ」
19/32
VI. 製図のためのコピー機能
Quiz 2
• 右の図形Bを
選択し、ライ
トペンをここ
に置いてコピーボタンを押した
• ライトペンを動かしたら、コピーさ
れた図形はどうなるか?
• 制約Mは「同じ長さ」
20/32
VI. 製図のためのコピー機能
コピー時の構造の変化
• コピー元の図形は構造が変わらない
– グループ化された同一性は保たれる
• コピーされた図形は構造をばらばらにできる
– 別の言い方をするとグループ化を解除できる
• 個々の部品を削除することもできる
– 構造をどのレベルまでばらばらにするかはユーザ設定
可能
21/32
VI. 製図のためのコピー機能
Quiz 3
• この矢印をコピーして、ライトペンを動かしたら
どうなるか?
• 制約Eは「回転しない」
• 制約Fは「サイズ不変」
22/32
VII. 制約条件の適用
制約条件
• 変数の新しい値の自動計算を行なう
• 制約条件のタイプの設定はできるだけ汎用にした
– 幾何学的な形状だけでなく、デザイン条件も簡単に追加できる
One pass vs Relaxation
• One passでは、新しい値の計算が一回で終わる
– 高速・正確
• Relaxationでは、何回も繰り返して収束させる
– エラーが最小になるような値が求まる
– ちょっと複雑だと膨大な時間がかかる
23/32
VIII. 応用例と結論
繰り返しパターンの例1
• Subpictureを変更するとパターン全部が変わる
• 900の六角形の模様を考えて作るのに1.5時間
– プロットするのに25分
24/32
VIII. 応用例と結論
繰り返しパターンの例2
• 500回繰り返しのジグザグ模様を4列作るのに45分
• プロットするのに15分
25/32
VIII. 応用例と結論
リンクの例
固定
リンク
固定
ライトペンの軌跡?
15秒間露出して撮影
26/32
VIII. 応用例と結論
橋の形の例
• 片持ち梁(4点支持)と
アーチ橋(2点支持)
• それぞれの中央に負荷
をかける
• 各部分の負荷のかかり
具合を計算
これって有限要素法の原型?
27/32
VIII. 応用例と結論
アートの例
• パーツを動かすことも
可能
• アニメーション製作への
応用を示唆
28/32
VIII. 応用例と結論
回路図の例
• Subpictureとしてどんな回
路を用意したらいいか、予
測するのが難しい
• この図にはないが、約40
個のトランジスタからなる
大規模な回路を作成した
– 初心者がやって10時間
– 「手で描いた方がよかった」
29/32
VIII. 応用例と結論
結論
• 単なる作図(drawing)以上の何かがあって初めてコ
ンピュータで描くことが価値を持つ
– 膨大な繰り返しパターンは簡単に正確に描ける
– リンクの例では、振る舞いを目で見て理解が深まる
– もし回路シミュレーションができるのならば、コンピュータで回
路図を描く価値がある
• コンピュータで単調な作図を効率よく行なうためには
まだまだ長い道のりがある
30/32
VIII. 応用例と結論
今後の課題
• 三次元物体への拡張“Sketchpad III”
– 作図は最初から直接三次元で行なうことになるだろう
• 写真から線画への直接変換も研究が進行中
• 部品の消去も含むような変更処理の定義と適用
– たとえば角の丸めを定義し、あとは角をポイントするだけで簡
単に丸めができる
31/32
感想
• Sketchpadは見かけのインタラクションの印象が強かったが、
読んでみるとその裏に洗練されたデータ構造があった
• 現代のCADの基礎となる概念が、40年前の時点でこんなに
たくさん盛り込まれていることに感動
• つい最近までCADは単なる作図ソフトとしてしか使われてい
なかったが、Sutherlandは当初からCADの本質を見極めてい
た
• 最近のSIGGRAPH論文スタイルの原型を見た
– 最初に分かりやすい典型例
– 中盤は理論・実装の説明
– 最後に華麗な応用例
32/32