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