ずっと君のターン

2015-02-16 窓から外を見る限りは春っぽい

PaintUp/teddy.jsの作り方

| 14:00 |  PaintUp/teddy.jsの作り方を含むブックマーク

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

https://github.com/technohippy/teddyjs

Teddy

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

f:id:technohippy:20150212141435p:image

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) の軸の端点の処理についてですが

f:id:technohippy:20150212142454j:image:w100

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

f:id:technohippy:20150212141531p:image

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

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

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

f:id:technohippy:20150212141620p:image

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;
};

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

f:id:technohippy:20150215231610p:image:left:h200

f:id:technohippy:20150215231609p:image:h200

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

f:id:technohippy:20150215232919j:image:w150

  • 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

f:id:technohippy:20150215231747p:image:left:h200

f:id:technohippy:20150215231746p:image:h200

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

テクスチャ

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

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

f:id:technohippy:20150215235125j:image:h150

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

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

凹包

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

f:id:technohippy:20150216001527p:image:h200

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

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

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

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

f:id:technohippy:20150216003207p:image:h200

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

クラスタリング

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

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

f:id:technohippy:20150216004612p:image:w150

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

ということで輪郭線を抽出する前に連続しているグループごとに分けておくことにします。最初は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にする、みたいな感じでやってたような気がします。これをクラスタリングと読んでいいのか分からないけど、まぁとりあえずこんな感じで期待したように動いてます。

f:id:technohippy:20150216004940p:image:left:h150

f:id:technohippy:20150216005024p:image:h150

CSG

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

f:id:technohippy:20150216005918p:image:h150

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

f:id:technohippy:20150216005917p:image:left:h150

f:id:technohippy:20150216005916p:image:h150

できれば表示されない内側のポリゴンは削除して、交わっている物体は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したり、いい感じに集合演算っぽいことができます。

f:id:technohippy:20150216011001p:image:w250

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

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

Export/Download

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

上の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プリンタで出力することも可能になります。

f:id:technohippy:20141216114716j:image:h300

今後の展開

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

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

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

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

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

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

mattatzmattatz 2015/02/16 15:59 僕もthree.jsでTeddyのアルゴリズムを組んでみているのですが,Meshにシワができてしまうという全く同じ問題にあたりました.
論文の5.1の最後に"Finally, the system applies mesh refinement algorithms to remove short eges and small triangles"と書いてあるように,Meshの最適化処理をかければシワがなくなるかなーと思っています.
Meshの最適化処理に関してはこのアルゴリズム(http://research.microsoft.com/en-us/um/people/hoppe/meshopt.pdf)を使ってるようです.

technohippytechnohippy 2015/02/16 16:10 ありがとうございます。やっぱりそのまま実装すると原理的にシワ出ますよね。教えていただいたペーパーはあとでちゃんと読んで時間があるときにでも試してみます。

2015-02-05 ちょっと雪

WebGLを使った3Dモデリングツールを作りました

| 12:22 |  WebGLを使った3Dモデリングツールを作りましたを含むブックマーク

というのはウソで。

いやウソではないかもしれないけど、そんなガチな感じではなくて「こどもが適当に描いた落描きがなんとなく立体になったら面白い」くらいの空気感で作ってみた。実際、我が家の3才児でもそれなりに楽しそうに使えてたり。

要するにTeddyなんだけど、JS使ってブラウザ上でできたらおもしろそうだとたぶん5-6年くらい前から思ってて、やっと実装できたので今は新しいパンツをはいたばかりの正月元旦の朝のようにすっきり。(最近はブラウザで動く3Dスカルプトソフト既にいくつかあるみたいだけど・・・)

f:id:technohippy:20150205005127p:image:w300

https://github.com/technohippy/teddyjs

結構動作が重たいとはいえスマホでもそれなりに動くし、マウスを使うよりも指を使ったほうがずいぶん楽しい感じになるので、できればぜひスマホで試していただきたく。

f:id:technohippy:20150205010647p:image:h300

https://technohippy.github.io/teddyjs/

一番簡単な使い方としては、1.メニューからペンの太さや色を選びつつお絵かきして、2.描き終わったら右下の「3D」ボタンを押すだけ。待ってれば3Dになるので(複雑な輪郭だとよくエラーになるけど)、その後はスワイプして視点変更したり、ピンチイン・ピンチアウトでカメラを近づけたり遠ざけたりできる。その状態でもう一度「3D」ボタンを押せばテクスチャの追加編集も可能。

先に立体の形を決めてから色を塗りたい場合はヘッダのハサミアイコンを選択して輪郭線を描いてから、ペンアイコンを選んでさっきと同じように色塗りして「3D」ボタン押下。

ちなみに絵を描くのが面倒ならカメラ機能も付けたので、映像を取り込んでからハサミで切り取って立体にすることも可能。この機能はアプリとしてはちょっと浮いてるのでどうしようかなと思ったけど、人にデモして見せる分には面白いのでとりあえず残してる。

f:id:technohippy:20150205011336p:image:h300

あとObj形式またはSTL形式でダウンロードする機能もあって、適当に作ったモデルをBlenderとかのまっとうなモデリングソフトに取り込んで編集したり、3Dプリンタで出力したりできる。以下はカブクさんに3Dプリントしてもらった落描き。アプリのバージョンはちょっと古い。

f:id:technohippy:20150205011427p:image:left:h300

f:id:technohippy:20141216114716j:image:h300

https://www.rinkak.com/

カブクさんは3Dプリント機能を利用できるAPIを公開してくれてるのでホントはプリントボタンを作ってウェブアプリから直接リアルなモノを出力するところまで作りたかったんだけど、それにはサーバーサイドを実装する必要があって、じゃあいっそモデルをアップロードして公開・共有できるようにしようとか、やりだすとなんやかやで時間がかかりそうな気配があるので一先ずペンディング。

ということで、気持ち未完成な部分もあるけど、例えばタブレットで子供に触らせたりすると結構楽しんでもらえるはず。よかったら触ってみてください。

2014-10-22 あめ

これが・・・俺の異能vationだ!

| 12:10 | これが・・・俺の異能vationだ!を含むブックマーク

「あんどうさん最近おっぱいが足りないんじゃないですか?」

Androidの偉い人にそんなことを言われたのは確か今年のはじめくらいでしたか。それを聞いた私は「いきなり何を言ってるんだこの人は」と思うより先に「あぁ、そうかもしれないな・・・」と思ってしまったわけで。

・・・

で、まぁそんなこんなでやっとそれなりに動くようになったので成果発表。

D

操作方法は以下のとおり。

画面の操作動作
マウスドラッグ触る
カーソルキー視点を変更する
スペースキーボールをぶつける
enterキー上下に揺らす
wキーワイヤフレームと肌色を切り替える
http://technohippy.github.io/oppai/images/f_003_85.pngメニューを開閉する
http://technohippy.github.io/oppai/images/f_001_36.pngスマホコントローラを開始/停止する
http://technohippy.github.io/oppai/images/f_002_61.pngスマホコントローラの画像認識を確認する

スマホコントローラの操作方法は以下。簡単に弾性体を貫通してしまうので、特に前後に動かす場合はゆっくりと動かしてください。

スマホコントローラの操作動作
平行移動(上下左右前後)手を平行移動する
左右に傾ける手を傾ける
前後に傾ける指を曲げる

なお、暗いところや正面に光源があるような場所で試すとうまく認識されません。メニューのデバッグ(虫)ボタンを押してスマホのディスプレイの明るさを調節してください。多くの場合、一番暗くするとうまく認識されます。

・・・

中身について、弾性体のアルゴリズム?は大昔に作った2D版と基本的に同じで、3Dに拡張しただけ。具体的には半球を構成するポリゴンの各頂点にポリゴンの面積に比例した大きさを持つ法線方向の力を加えています。正直に言えば期待したほどの動きは見られなかったものの、ずーっと3Dで試してみたいと思っていたことをやっと試せたので割と満足。

コントローラについては7月にHTML5 Japan Cupで優秀賞を頂いた3D版AngryBirdsと基本同じ。といっても後発なのでノイズに強くしたり、無理やり傾きを取れるようにしたりとそれなりに拡張していますが。こっちはシンプルな作りにも関わらず思った以上にそれっぽく動いてるので、もう少し真っ当な使い道を探ってみたいところです。

あ、あと3D版AngryBirdsと大きく違うのは物理エンジンの処理をWeb Workersで行うようにしたこと。これでずいぶん反応良くなったのでAngiryBirdsでもそうすればよかったなと。three.jsのGeometryがtransferableってわかったのも収穫でした。

・・・

そういえばタイトルですが言ってみたかっただけです。応募して落選しましたが、おっぱいで応募したわけではありません。

2014-08-27 急に涼しくなってきた

LL Diverでいい忘れたこと

| 21:33 |  LL Diverでいい忘れたことを含むブックマーク

LL Diverのmozaic.fm出張版でDartについてこれは言っときたいなーと思ってたことをいい忘れてたことにたった今気がついたので忘れないうちにブログに書いておきます。

ホントはあの場で言っておきたかったこと、それは

「DartはDX(Developer Experience)を重視している」

ということです。

これはI/Oのとあるセッションでの発言ですが、要するに「Dartは単なる一プログラミング言語ではなく、開発体験全体を改善することを目的としている」と理解しました。プログラミング言語自体はその目的を果たすためのパーツの一つに過ぎません。クライアント・サーバーで同じ言語が使えることや、コード補完の効くIDEが存在すること、パッケージマネージャや専用リポジトリが初めから存在すること、すべてこれまで開発体験を損ねていた問題に対応しようとしているものです。JSにクラスや型がないのが不満だから作りましたとか、ブラウザ上でhoge言語を使いたいので作りました、とかいう凡百のaltJSとは初めからその志の高さが違います。

セッションでは「TypeScriptは現実、Dartは夢」と言いました。しかしもういっそのことこう言ってもいいかもしれません。「(Dart以外の)実用に足るaltJSは現実、Dartは夢」。

なぜか頭のなかで「I Dreamed a Dream」が鳴り響いてるけど、成就するといいなぁ。

2014-08-21

土曜日にLL DiverでDartについて話します

| 01:15 |  土曜日にLL DiverでDartについて話しますを含むブックマーク

登壇するセッションのタイトルは「mozaic.fm出張版: TypeScript and Dart」ですが、分かりやすく言えば私とわかめさんJxck先生「これから皆さんに殺し合いをしてもらいます」って言われるというセッションです。もしかしたら私は早々に殺られて死んだ目で「ヘーソウナンダー」ってつぶやくだけの1時間になるかもしれません。コワイヨー。

まだチケットはあるようなので、そんな残酷絵巻に興味あればみなさんでお誘い合わせの上ぜひお台場までお越しください。