Knot Puzzle 解説 - Imaginantia

ワールド「Knot Puzzle」を Community Labs に上げました～　ひもをうにうにするパズルのワールドです　意外と難しいとおもいます　よろしくおねがいします #VRChat_world紹介 https://t.co/MeqeqGNxYh pic.twitter.com/2GSPDXvkvz
— phi16 (@phi16_) 2023年5月18日

パズルの解説はしないですよ。制作と実装の話を書きます。

あとがきにも書きましたがアイディア自体は Inter-action on the Math を作ってたとき (2020年) にはありました。その頃はまぁ曖昧に「結び目に関する展示」、くらいの気持ちだったと思います。結構方向性はいろいろあって:

結び目不変量をテーマに
- 自由な曲線を入力するにはしんどすぎるので、全部 polyline か string diagram で紐を記述？
紐の連続的変形を表示
- Perko knot はなんか話題として好きだったので、全然違うようにみえるこいつらは同じなんだよー、っていう展示程度

みたいなことを考えていたと思います。でもどちらもなんだか展示的にはもったいないなあという気持ち、そして実装がだるいという気持ちがあって案程度で止まっていました。

久々に「できるかも」と考え始めたのは voronoi tracking を理解してからです。

なんか起きてしまったのでなんとなく前からやりたかったやつをやった (voronoi tracking) pic.twitter.com/iGfrSGqfLK
— phi16 (@phi16_) 2023年2月21日

要は動的トポロジーの上でお互いの点の情報交換をするための構造です。なんかなんでもできそう。昔から空間系データ構造 (Uniform grid とか BVH とか) をやるのがなんだか苦手で敬遠していた (GPU で使いにくいし) のですが、こいつはなんかもっと単純に実装できて気軽に使えそうです。

そしてその後で d4rkpl4yer さんの解説にある「ランダムなデータを一瞬でコンパクトにする手法」を知ります。要は好きな点の動的追加・削除ができる構造です。なるほど～となって試しに作ってみたのがこれ。

唐突になにかつくりはじめる人 pic.twitter.com/txGtI9661t
— phi16 (@phi16_) 2023年3月11日

点と点を PBD (1-hop neighbor までの長さ拘束) で繋いで、0番目の点がひたすら増殖しているみたいな図だったと思います。

これに voronoi tracking を付けると自己衝突が計算できます。うにょうにょした紐が作れそう。

で、そこからワールドコンセプト固めて、結び目についていろいろ調べつつ、がーっと実装やってできたのがアレです。そんな感じです。

要素ごとに実装を解説していきます。

ひも

全部GPUで計算してます。AsyncReadbackありがとう。

各点が持つ情報は:

位置 (vector, float3)
有効か否か (1 or 0)
向き (quaternion, float4)
(直接繋がっていない) 近い頂点の番号、4つまで (int4)
それぞれとのねじり位置関係、3つまで (float3)
破壊されたかどうか (0 ～ 1)
近いゴール結び目の頂点の番号、4つまで (int4)
最も近いゴール結び目との距離 (float)
最も近いゴール結び目との距離の二乗 (float)

です。追々説明します。

点の増減

まず 2-pass で動いてます。まず圧縮された点のバッファ (例: [5,3,2,4,1]) を無と interleave したバッファ (例: [5,0,3,0,2,0,4,0,1,0]) に拡張します。そして Z-order curve に基づいてバッファを圧縮します ([5,3,2,4,1])。

これで何も変化しないループができるわけですが、これによってバッファ拡張時に 各点は自身を2点に増やす能力を得る わけです。つまり 2 を 2,0 として拡張するのではなく、2,6 として拡張すれば、その部分に 6 が挿入されます。これで点が増やせるようになります。

逆に減らすのは簡単で、自分を 0 にすればいいだけです。

上は適当な例として書きましたが、実際には有効 (1) か否 (0) かを表すデータがあり、その Mipmap を参照することで Z-order curve を用いての圧縮を実現しています。ついでにそれを使えば全部で何点あるのかも知ることができます。

紐の動き

近傍の情報はすぐわかるので、後はお互いに距離拘束を乗せます。隣接頂点とだけだとギザギザしちゃうので、さらに隣の頂点とも拘束を掛けます。

float d = 2 * Radius;
float3 dp = 0;
dp += normalize(p1 - p) * (length(p1 - p) - d * 2);
dp += normalize(p2 - p) * (length(p2 - p) - d);
dp += normalize(p3 - p) * (length(p3 - p) - d);
dp += normalize(p4 - p) * (length(p4 - p) - d * 2);
p += dp * 0.3;

また、自己衝突しそうな点がわかったらそこから離れるように移動させます。点だけだともったいないのでカプセルで判定を取っています。

線分との最近点を取ってそこから離す感じ。移動の強さには exp(-d) を掛けています (近いほど強く反発する)。

ちなみに動きについては毎フレームで3回計算を回しています。紐をある程度固くしたかったので。

紐のレンダリング

ただの線なら頂点位置だけでいいんですが、いい感じに紐にするためには向きの情報が必要でした。

向きの計算を完璧にやる方法は存在しない気がしたので、雑に「隣の頂点の向きにだんだん近づける」処理を入れています。完璧じゃないのでたまに振動しますが、まぁちょっと動かせば安定するので良いかな…。

ちなみに実際には6角形を使っています。あと頂点と頂点の中間位置にもリングがあって、曲線っぽく補間するようにはしています。

近傍探査

各点は「今のところもっとも近い4点」の情報を持っています (直接繋がっている隣接12頂点くらいは無視しています)。最近点を可視化するとこんな感じ。

で、毎フレームこれを更新していきます。頂点番号の候補をたくさん与えていって最も近い4つだけを残すイメージです。

自分自身の前回の最近4点 (n[self])
前回の最近4点それぞれの隣の点 (n[self]-1, n[self]+1)
隣の頂点の最近4点 (n[self-1], n[self+1])
ランダムな8点

これを放っておくと最近4点に収束するわけです。特に紐を伝って情報が伝播していくので意外と収束が早いです。このやりかたが voronoi tracking なのかな？まぁもはや voronoi ではありませんけど。

ゴールとの距離の計算も同じことをやっています。最も近いゴール上の4点を毎フレーム更新しています。

破壊判定

本来は当然紐はお互いをすり抜けません。しかし実装がそこそこ雑なのでそこそこすり抜けます。そうなるとゲームとして問題があるわけです。

大域的構造を読んで判定できれば最も良いかもしれませんがちょっと難しすぎます。そこで局所的な判定を行っています。

要はこれのどっちであるかを各点が知っていればいいのです。急に反転したらやばい。

とりあえず cross でなんかそれっぽい値は得られます。とは言えこれだけで交差状況を扱うには不十分で、紐は結構いろんな位置関係を持つものです。例えば遠い点との交差状況は無視されるべきです。

困りましたが、とりあえず smoothstep でやわらげておくことにしました。かなり近い点だけを判定に入れています (なので一気に遠くから遠くへ交差を抜けさせるとバレない…)。

閾値は悩ましいところですが、大きすぎると「こするような移動」でも判定が入ってしまいそうで怖かった感じでした。でも今はちょっとゆるすぎる (見逃しが多すぎる) かなぁ…。2倍くらいにしてもいいかも…。

ゴール完成度計算

各点は「最も近いゴール上の点との距離」を知っています。今回はすべてループ状の紐をテーマにしているので、「全点がゴールとの距離が0なら、完全に一致している」が成り立ちます (端点がわかれてたりすると成り立ちません)。

気持ち的にはゴールとの距離の max を取りたい (もっとも離れている点が知りたい) ところですが、mipmap はただの平均しか拾ってくれないので計算が面倒です。そこで分散を使いました。

$d$ と $d^2$ をバッファに入れて mipmap を取ると、 $E[d$ ] と $E[d^2$ ] が得られます。 $d$ の分散は $E[d^2]-E[d]^2$ と一致します。

正規分布は $3\sigma$ 範囲で 99.7% データが入るらしいので、 $\mu + 3\sigma$ を max の代わりに使ってみました。実際期待通り動いたのでまぁ良かったです。

ちなみに台に描かれている図はこれを可視化したものです。平均に従って半径が伸び、分散に従ってゆらぎを与えています。真ん中に綺麗に収まればOKというわけ。

メインシステムについてはこんなもんかな…。UIは気合で実装しました。

ワールドモデル

今回はちゃんとしたガワを入れようと最初から思っていました。あんまりそういうのつくったことなかったので…。

イメージは遺跡で、まぁだんだん奥に進むと面白いものが見つかる、みたいな感じです。イメージね。水が張ってあるところはなんか賑やかしです。

メッシュの大枠は Blender でつくりました。

で、これを入力としてHoudiniで階段組んだり床の溝 (光源用) 彫ったりして。

あと壁彫ったりしてます。

彫った図形

アレは結び目をパーツの組み合わせ的に2次元記述したデータから生成したやつです。ちょっとだけ手書きの絵が描いてあるので雰囲気はわかるかな？

かっこいいので置きました。遺跡っぽいし。かっこよすぎて装飾にしか見えないという問題がありましたが。

Houdini製です。

まず結び目を Attribute Wrangle で定義します。各行の先頭が「どこを使うか」で、その後がどのパーツを使うか。 (1なら直線、2なら∪、3なら∩、4と5は交差)

// 8_18

int data[] = {
    0b001100, 3,
    0b001100, 1, 1,
    0b111111, 3, 1, 1, 3,
    0b111111, 1, 4, 4, 1,
    0b111111, 1, 1, 5, 1, 1,
    0b111111, 1, 4, 4, 1,
    0b111111, 1, 1, 5, 1, 1,
    0b111111, 1, 4, 4, 1,
    0b001100, 2, 1, 1, 2,
    0b001100, 1, 1,
    0b000000, 2,
};

i[]@knot = data;

で、そこから頂点データを生成して。

Copy To Points で紐ができます。

Sweepしただけだと交差がアレするので、(予め入れておいた) 前後情報を使って Boolean で抜きます。

なんやかんやあって完成。

あとはこれをメインモデル側で適当に配置して切り抜いています。

そういえば解いたときに開くあのドア (？) もこれです。一個手前の問題の結び目になっています。

初期結び目・ゴール結び目

各結び目も Houdini で生成しています。

先程つくった紐生成機をまた使って今度はちゃんと立体構造をつくってあげます。

Resampleでゆるく曲げてあげるとこう。

で、ここに repulsive-curves という便利アルゴリズムがあります。これは「ひもをいい感じに解いて綺麗にしてくれるやつ」です。なかなかおもしろいので YouTube 見ると良いです。何をやってるかはよくわかりませんが…。

これを Houdini から叩く方法をつくりました (これについて Houdini 勉強会で発表したりしました)。というわけでこれを使うとこうなります。(左から2番目の紐は敢えて処理しないようにしてます)

こうして紐形状が作られています。

あとはGPUで読み出すためにテクスチャに焼きます。前と同じように「向き」の情報がほしいので、それもいい感じに計算します (こちらでは向きを伝播していって必要なねじり量を計算、それを全体に分散させることでねじりを無くしています)

あとはシェーダ側で読むだけです！

音の話

ついでに書いておきます。今回は音をできる限りつくってみました。

効果音の7割くらいは Live の Operator でできています。試行錯誤いろいろした結果やっと多少マシになってきた感じがあります。attack での変化はマジで大事なんだなあという気持ち。

あと2割はメニュー開くときの「ぽわっ」て音で、アレは私の無声両唇破裂音です。はい。イメージが一番近かったのでそのまま録音して加工して使いました。メニュー閉じるのも実は同じ音を使っています。

残りの1割はクリア時の音ですが、普通に (Wavetable + 反転と Operator と Operator で) つくっています。

BGMは Wavetable (ambient) 部分とプリセットにあった Thin Perc 8ths (結局 Operator) でぱちぱち音を入れました。あとなんか適当な (音程のある) ノイズを乗せてます。

そういえばBGMを作ろうと思ったとき、まだ「炎の台」はありませんでした。だけどワールドに変化が何もないからなんだか何も音が思いつかなくて。それで常に動き続ける物体として炎を増やしたのでした。

QvPen

そういえば QvPen のシェーダを少し弄っていました。アウトラインが入っています。実はあの実装は自明ではないというか…変なことをしています。

geometry shader で2倍に増やした上で片方だけ太くする、まではいいんですが、どうやって「後ろに置くか」(Zの値を定めるか) が難しくて。アレってただのビルボード群なので。

線の部分はまだマシで、とりあえず後ろに下げればいいです。下げる量は射影変換を考慮して計算する必要があります。

丸部分をそのまま下げるだけだと線に貫通するので困りました。そこで、線の傾きに合わせて一緒に前後にずらしてみることにしました。

ただこの傾き量もそんなに自明じゃなくて。なんかいい塩梅を探った結果今の状態になってます。

カクッとした線を描くとまぁ完璧じゃないことがバレるんですが、まぁ、最低限の要件 (空中に曲線を描いたときに前後が (両目視差無くとも) 判定できること) は満たしているのでこれで良いということにしました。しかたないです。

追記: 同期

そういえば書き忘れてました。同期は最後に実装しました。やり方は「掴んでいる間、2秒毎にバッファをCPUに読み出してRequestSerializationする」だけです。

適当に1秒毎にしたらなんかイベントが溜まってやばいことになったので2秒になりました。見た目は大丈夫そうです。

紐の動きを線形補間してなめらかにしたい気持ちはあったんですが、紐の交差が発生するとちょっと厄介なのでそのままダイレクト代入しちゃいました。

ちなみに、シェーダ内での uniform float4 で宣言できる配列の長さが 1024 以上だとだめらしく、そのせいで 1022 要素まで同期するようにしています。だから最大長だとちょっとバグる。まぁ元々紐を伸ばす工程内で最大長にはならないようにしてるので大丈夫…なはず…？

おわり

そんな感じです。加えて諸々細かい調整と実装もいろいろあって大変でした。そういえばまずパズルとして成立するのか私は制作当初は知りませんでした (思ったより簡単・不可能ほどに難しかったらどうしようと)。行き当たりばったり的ではありましたがいい感じになったのでよかったです。(最初は amphichiral knot の概念を知らなかったですし)。

久々のそこそこサイズの個人制作ができてよかったです。結構広い人々に遊んでもらえているようで幸いです (ちゃんと解けてるみたいですし！)。

なかなか他にはないVR体験 (？) ができる場所として認識されていたらいいなあとおもいます。まぁ大丈夫な気はします。

はい。

なにか詳しい話が聞きたいとか (あと答えが知りたいとか) あれば直接どうぞ。では。読んでくださいありがとうございました。