PaintUp/teddy.jsの作り方

Teddy.jsはこう見えて意外といろいろやってて、このままだと確実に忘れて自分でも弄れない私的オーパーツになるのが目に見えてるので、記憶に残っているうちにまとめておきます。説明用というよりは実際に機能追加していった順に思い出しながら書き残しているだけです。

https://github.com/technohippy/teddyjs

Teddy

輪郭線を立体にする部分は東大の五十嵐教授のこの論文で説明されている手順を使用しています。とても有名です。この論文の図を引用しながら簡単にやっていることを説明すると

Teddy: A Sketching Interface for 3D Freeform Design, p. 5

この図のとおり、まずは図形をポリゴンに分割するのに加えてボーン的なものも抜き出します。

• a) 外周ですが、頂点が多すぎても大変なのでマウスの軌跡を全て採用するのではなく、今回はそれぞれ一定距離以上離れていて、かつ頂点部分のなす角度の絶対値が一定の範囲から逸脱しない頂点を抜き出しています。
• b) 閉曲線を三角形分割して、外周に接している辺の数に応じてポリゴンを分類します。接している辺の数が2の場合は"T"erminal Triangle（T型）、1の場合は"S"leeve Triangle（S型）、0の場合は"J"unction Triangle（J型）です。なお、三角形分割についてはpoly2triというライブラリを使用しました。
• c) ポリゴンの分類に応じて、以下のとおり仮の軸（spine）を設定します。
  • T型: 外周に接する二辺の交点と、対向する辺の中心を繋ぎます。
  • S型: 外周に接しない二辺の中点同士を繋ぎます。
  • J型: 各辺の中点をそれぞれ三角形の重心に繋ぎます。
• d), e) 軸の端点が外周に接しないよう扇型に分割し直します。詳細は次の項で。
• f) 必要に応じてポリゴンを分割します。

上記、d), e) の軸の端点の処理についてですが

軸は最終的に外周を含む平面に垂直な方向に持ち上がることになるので、外周と接しているとその部分が微妙な感じになります。上の図では分かりにくいかもしれないけど、要するに端点が尖ってしまうと。そのため、軸の端点と外周が扇型になるように分割し直します。その手順が以下のとおり。

Teddy: A Sketching Interface for 3D Freeform Design, p. 5

T型のポリゴンから順に走査して、再分割されるポリゴンを決めます。

• a), b), c), d) T型ポリゴンから開始して、接するポリゴンがS型の場合は、S型ポリゴンの内よりの辺を直径とする半円から頂点がはみ出るまで走査を続けます。頂点がはみ出したら現在の半円の中心から各頂点に線を引きます。
• e), f) 接するポリゴンがJ型の場合、走査を終了して、J型ポリゴンの重心から各頂点に線を引きます。

Teddy: A Sketching Interface for 3D Freeform Design, p. 6

ポリゴンの分割とボーンの抽出が終わると、最後にボーンを中心に膨らませます。

• a), b) 軸に含まれる頂点を外周と垂直な方向に持ち上げます。持ち上げる量はその頂点と外周を結ぶ辺の長さの平均です。
• c) 持ち上げた頂点と外周を楕円曲線で結びます。
• d) 私のアプリでは曲線の長さにかかわらず楕円曲線を10分割しています。ここはホントは楕円の大きさに合わせて分割数を変えた方がいいような気もします。

以上で論文に書かれているオブジェクト作成の手順は全てで、実際私の実装でもこのとおり愚直に実装してるつもりです。

// teddy.js
Teddy.Body.prototype.getMesh = function() {
  if (!this.mesh) {
    this.triangulate();  // 三角形分割して
    this.retrieveSpines();  // 仮の軸を設定して
    this.prunSpines();  // 端点が外周に接する軸を除去して
    this.elevateSpines();  // 軸を持ち上げて
    this.sewSkins();  // 持ち上がった軸と外周を楕円曲線で繋ぐ
    this.buildMesh();
    for (var i = 0; i < 5; i++) this.smoothMesh();
  }
  return this.mesh;
};

ただ実装が悪いのか、三角形分割になにかコツや調整が必要なのか、このままだとこういう感じのシワシワな物体になりました。

解決策がわからなかったので、とりあえずオブジェクト作成後にガウスぼかし的な感じで全頂点の座標を隣接する頂点の平均に均して回避しました。

• p1.x = (p2.x + p3.x + p4.x + p5.x + p6.x) / 5
• p1.y = (p2.y + p3.y + p4.y + p5.y + p6.y) / 5

ある程度ごまかせてるとは思いますけど、ホントはどうすべきだったのか結構気になってます。原因や正しい？解決策をご存じの方がいらっしゃいましたらコメントいただけるととてもありがたいです。

テクスチャ

以上でとりあえず3Dの物体を作ることはできるようになったのですが、単色の不思議な立体が作れるだけだといまいちどう楽しんでいいかわからないのでテクスチャを編集できるようにします。

本家Teddyでは3Dモデルにそのまま色を塗れたりするんですが、やり方がよくわからないというか、具体的にはいい感じのUVマップを機械的に生成する方法がわからなかったので、ここは何も考えずに実装できそうな以下のような方法にしました。

よくわからないと思いますが、要するにモデルのz座標は無視して、テクスチャの(x, y)座標の色がモデルの(x, y, z)座標の色になるということです。モデルを後ろから見たらテクスチャが反転して見えるわけです。とてもバカ簡単。

ただ、実はアプリを起動して初めに表示される真っ白い紙は3Dの平面です*1。単純にマウスの移動を拾って2Dのcanvas上に描画しているだけのように見えますが、実際はThree.jsのRaycasterやProjectorを使用して3D平面のどの位置にマウスカーソルが当てられているかを取得して、その座標をテクスチャとして使用している（不可視の）canvasの座標に変換してその上に描画し、その結果として3Dの平面に色が乗るという周りくどいことになっています。

凹包

初めは輪郭線を決めてから内側に色を塗るような手順でオブジェクトを作ってましたが、考えてみれば輪郭線とテクスチャを分ける必要はなくて、テクスチャの外周をそのまま輪郭線に使えばいいと気づきました。ということでそうしました。使ったのはこのライブラリ。

http://dailyjs.com/2014/10/28/hulljs/

凸包は聞いたことありましたが、今回調べるまで凹包は知りませんでした。テクスチャ用canvasのImageDataを適当な間隔でチェックして「白くない部分」の座標を抜き出してまとめ、Hull.jsでそれら全てを含む凹包（輪郭線）を得ます。

使い方はとても簡単で、hull関数に点列と閾値を渡すだけ。

// teddy.ui.js
function retrieveOutline(points) {
  var outline = hull(points, 10);
  // ...snip...
}

赤い部分がテクスチャで、見難いけど濃い目の緑の線が抽出された輪郭線です。

クラスタリング

テクスチャ用canvasのImageDataを適当な間隔でチェックして「白くない部分」を抜き出して

これで一応の輪郭線が得られたんですが、落描きが複数のパーツに分かれている時に変なことになりました。

まぁ本来ひと塊になっていないものから輪郭線を抽出しようとしてるので当然です。

ということで輪郭線を抽出する前に連続しているグループごとに分けておくことにします。最初はk-means法とかの聞いたことのある方法でクラスタリングしようかと思ったんですが、考えてみれば対象が200x200程度なので手を抜いて、なんかずーっと前に本で見たような感じの方法で適当に実装しました。

// teddy.ui.js
function clusterPoints(points, table) {
  var ly = table.length;
  var lx = table[0].length;
  var clusters = [];
  for (var y = 0; y < ly; y++) {
    var row = table[y];
    for (var x = 0; x < lx; x++) {
      var col = row[x];
      if (col.pointId !== null && !col.visited) {
        clusters.push([]);
        checkNeighbors(points, table, clusters.length - 1, clusters, x, y, lx, ly);
      }
    }
  }
  return clusters;
}

function checkNeighbors(points, table, clusterId, clusters, x, y, lx, ly) {
  var col = table[y][x];
  if (col.pointId === null || col.visited) return;

  col.visited = true;
  clusters[clusterId].push(points[col.pointId]);
  if (1 < x) {
    checkNeighbors(points, table, clusterId, clusters, x - 1, y, lx, ly);
  }
  if (x < lx - 2) {
    checkNeighbors(points, table, clusterId, clusters, x + 1, y, lx, ly);
  }
  if (1 < y) {
    checkNeighbors(points, table, clusterId, clusters, x, y - 1, lx, ly);
  }
  if (y < ly - 2) {
    checkNeighbors(points, table, clusterId, clusters, x, y + 1, lx, ly);
  }
}

なんだろこれ、なにやってるんだろ。既にイマイチわからなくなっててヤバい感じしかないんですが、雰囲気的には

　→
↓0110220000330
　0110022003300

こんな風に左上から右下に向かって走査して、連続している部分に同じグループIDを振っていって

0110220000330
0110022003300
0110002233000

接した時点で（今回の場合は2と3）どっちかにグループIDを揃える

0110220000220
0110022002200
0110002222000

で最後にグループIDが同じ点群に対して一つ前の処理を施して3Dにする、みたいな感じでやってたような気がします。これをクラスタリングと読んでいいのか分からないけど、まぁとりあえずこんな感じで期待したように動いてます。

CSG

さっきのクラスタリングからの3D化を実現するにあたって輪郭線を複数描けるようにしています。で、テクスチャから自動的に切り出した場合はそういうことは起きませんが、直接複数の輪郭線を描くとそれらが交わることがありえます。

まぁ交わったところで気にせず生成すればいいだけなんですが*2

できれば表示されない内側のポリゴンは削除して、交わっている物体は1つにまとめたい。ということでGoogle先生に聞くとcsg.jsというのを教えてくれました。CSGはConstructive Solid Geometryの略で3D物体の和や差を取れるものだそうです。

http://evanw.github.io/csg.js/

ただこれThree.jsとは情報の管理が違ってて自分で間を取り持つのが面倒くさそうだったのでさらにGoogle先生に聞くとThreeCSG.jsというのを教えてくれました。これでThree.jsからcsg.jsの機能を簡単に使えます。

http://learningthreejs.com/blog/2011/12/10/constructive-solid-geometry-with-csg-js/

で、PC版では一応これを使ってCtrl+mキーを押すと複数のオブジェクトをまとめる機能を実装しました。実際に使ってるところはこんな感じ。

self.addEventListener('message', function(event) {
  var geometries = event.data;
  var bsps = geometries.map(function(geometry) {return new ThreeBSP(geometry);});
  var bsp = bsps.pop();
  while (0 < bsps.length) {
    bsp = bsp.union(bsps.pop());
  }
  self.postMessage({status: true, geometry: bsp.toGeometry()});
});

THREE.GeometryオブジェクトをThreeBSPのコンストラクタに渡すと、得られたオブジェクトに対してsutractしたりunionしたりintersectしたり、いい感じに集合演算っぽいことができます。

分割され方が変わっていますが、交わっていた部分のポリゴンがなくなっていることがわかるはずです。

ただし、それはもうびっくりするくらい処理時間がかかってしかも画面が固まるので現状でははっきり利用はおすすめできません。解決してません。ボスケテ。

Export/Download

せっかく3Dオブジェクトを作ってもこのアプリ内でしか使えないのでは残念この上ないのでObj形式とSTL形式でダウンロードできるようにしました。使ったライブラリは以下。

• https://github.com/mrdoob/three.js/blob/master/examples/js/exporters/STLExporter.js
• https://github.com/mrdoob/three.js/blob/master/examples/js/exporters/OBJExporter.js
• https://stuk.github.io/jszip/

上の2つはThree.jsのexamplesに入っているものなので特に語るべきこともないんですが、3つめのJSZip、これすばらしいです。テキストファイルは当然として、canvasのtoDateURLを使えば画像も簡単にzipに格納できます。JSZipのvendor以下に入っているFileSaver.jsを使えばグローバルなsaveAs関数が追加されて、サーバーレスでダウンロードもできます*3。

// teddy.serializer.js
Teddy.Serializer.zipMeshesAsStl = function(meshes) {
  var zip = new JSZip();
  var stl = new THREE.STLExporter().parse({
    traverse: function(visitor) {
      meshes.forEach(visitor);
    }
  }, 5.0);
  zip.file("mesh.stl", stl);
  return zip;
};

// teddy.ui.js
  document.querySelector('html /deep/ #download-stl').addEventListener('click', function(event) {
    closeFileMenu(event.target);
    var zip = Teddy.zipMeshes(getAllMeshes(), 'stl');
    var content = zip.generate({type:"blob"});
    saveAs(content, "object.zip");
  });

前回のエントリにも書いたとおり、作成したモデルをObjまたはSTLでダウンロードすれば3Dモデリングツールに取り込んだり、3Dプリンタで出力することも可能になります。

今後の展開

いつになるか分からないけどぼちぼちやって行きたいなと思ってる追加機能。

• rinkak 3D Print Cloud APIを使ってストアに登録して原価のみで3Dプリントできるように
• 輪郭だけではなくて、色の境界も拾ってなんかいい感じに立体に
• Teddyで最初に抽出する軸をそのままボーンにしてモデルを変形可能に

これでしばらく放置しても再開時にそんなに途方に暮れずに済む・・・はず。

*1:ちなみにハサミモードの時の虹色の線も紙よりちょっとだけ手前にある3Dオブジェクト

*2:今回は内部が見えるようにワイヤーフレームにしていますが、普通にポリゴンを表示すれば内部は見えません

*3:そういえば書いてない気がしますが、今のところこのアプリはサーバーなし、JSだけで動いてます