メディア情報学 論文輪講 「歴史的システム」 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
© Copyright 2024 ExpyDoc