Non-Circular packing without script in TouchDesigner

こんなのノードだけで作れるようになります！
![img02.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/175399/96e416a2-87cd-0fd9-5dc6-764613c37d8d.jpeg)

English ver.
[https://poisson.works/post/non-circular-packing-without-script-in-touchdesigner/](https://poisson.works/post/non-circular-packing-without-script-in-touchdesigner/)

### 概要

今回実装したのはTouchDesignerで全くスクリプトを書かずに、Non-Circular Packing を行うものとなっております

ネットワーク図
![non-circular packing.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/175399/7ca1ab80-725e-6458-a959-09523662b59d.png)


### Non-Circular Packingとは？？

非円形図形（サンプルではバナナ）などを隙間なく埋めていくようなアルゴリズムです

参考リンク
[https://ippsketch.com/posts/non-circular-packing/](https://ippsketch.com/posts/non-circular-packing/)

なぜ、非円形図形なのか？
よくジェネラティブアートではサークルパッキングで絵を作るものが多くあります。

サークルパッキングとは円を特定の領域内に重なりなく敷き詰めるものになっており、アルゴリズムも大変シンプルで理解しやすいものとなっております。

こんなの
↓
<blockquote class="twitter-tweet"><p lang="ja" dir="ltr">みちみち<a href="https://twitter.com/hashtag/p5js?src=hash&amp;ref_src=twsrc%5Etfw">#p5js</a> <a href="https://twitter.com/hashtag/creativecoding?src=hash&amp;ref_src=twsrc%5Etfw">#creativecoding</a> <a href="https://twitter.com/hashtag/generative?src=hash&amp;ref_src=twsrc%5Etfw">#generative</a><a href="https://t.co/I7EqSB74Th">https://t.co/I7EqSB74Th</a> <a href="https://t.co/4FyAgW3TMP">pic.twitter.com/4FyAgW3TMP</a></p>&mdash; おかず Okazz (@okazz_) <a href="https://twitter.com/okazz_/status/1406907219052957697?ref_src=twsrc%5Etfw">June 21, 2021</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

しかし、非円形図形だと図形毎に形や大きさなどが変わり、中心点と半径のようなシンプルな値だけでは重なりを判定することが難しくなってきます。
ここではその非円形図形の重なり判定をTouchDesignerのオペレーターのみで行うことを目的としております。

今回は、入力画像の位置、回転、大きさをランダムに変えていき、現在の描画されているレイヤーと重なっているかを判定します。
もし重ならなかった場合には描画レイヤーに入力画像を描画し、重なっていた場合にはランダム値を変え、重ならず次に描画できるところを探していきます。

![img03.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/175399/e3474327-582b-9592-0512-0c0cc41dd9f0.jpeg)

### 入力画像と準備

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/175399/e49bf0ec-1d99-e5c2-28a0-f228b08036bc.png)

まず作成したい絵の解像度で空のConstantTOPと入力したい画像を用意します
入力画像がはみ出す場合、Over2で正方形に収まるようにサイズを調整してください

### ランダム値の生成

続いて描画するために位置、回転、大きさの値を作成していきます。
まず一番左のtimelineCHOPではプログラム起動時からの経過時間を取得しています。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/175399/1ac4952e-a40c-9abc-e72c-adfe41a9b1cc.png)


これはよくエクスプレッションで書かれている ```absTime.seconds``` と同じ値になります

その値をランダム値のSeedに設定し毎フレーム変わるランダムな値を作成します。
それぞれ0~1の間の値が生成されます

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/175399/411b21cb-56da-7f0d-4d8a-0b86db3b9910.png)

続いて、位置、回転、大きさの値を各々適切な範囲の値に調整していきます
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/175399/90016a53-e911-e027-f1e4-fd257eadd108.png)

それぞれMathCHOPを使用して値の調整を行っていきます
まずScopeというパラメータで特定のチャンネルのみを操作できるよう設定します

位置 : -0.5 ~ 0.5 (Transformのtranslateで値の単位をFractionにし、上下左右を-0.5~0.5の値で指定するため)
角度 : 0~360
大きさ : 0.25~0.75　(好みのサイズにしてね)
の値の範囲に設定します

### 描画候補画像

生成させたランダムな値をtransformTOPで使ってあげることで毎フレームランダムに発生する入力画像を用意することができ、これを毎フレーム次の描画候補として判定していきます
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/175399/cb29e72f-24ae-e8a9-a84f-bf3d6b9b9659.png)


### 描画と更新

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/175399/4ef0d52c-eae1-4fda-0ac6-259043632fe9.png)

描画にはTouchDesignerでよく使われるFeedbakTOPとOverTOPの組み合わせを用いていきます

FeedbackTOPで現在の描画を保持し、switch1に画像が入ってくるとOverTOPで合成され、その結果がFeedbackTOPに更新されます。（いろいろチュートリアルが出ています）
![download.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/175399/5c9cc70b-46c8-33a3-717e-2ea8a8e9448d.gif)


### 重なり判定
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/175399/713c473a-83e7-8472-fe49-c402d4171b3c.png)

最後に現在の描画と次に描画したいものが重なっているかどうかを判定します

MultiplyTOPを用いてfeedbackTOPとtransformTOPを乗算合成します

重なっていない場合は乗算合成の結果はすべて0となり、重なる場合にはどこかのピクセルが色の情報を持つこととなります。

重なりの判定にはアルファの値を使用し、AnalyzeTOPを用いて画像全体のアルファの最大値を取得します。

アルファの値をtoptoCHOPを用いて数値に変換し、logicCHOPを用いて、重なっていなかったら描画するために１を、重なっている場合描画させないために０を返す値にします。

その値をswitchTOPのindexに与えてあげることにより、重なっている場合には透明な画像、重なっていない場合には、ランダムなTransformの画像に切り替えることができます

![img01.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/175399/2954bf4c-5161-1ddf-e0ee-b9479192d5db.jpeg)

### まとめ
少ないノード数で比較的面白味のある絵作りができTouchDesignerというかノードベース環境の良さを最大限に引き出せたプログラムになっているかと思います。
課題としては、1フレーム1判定しか行えないためみっちり充填されるにはそれなりに時間がかかる点があります。
参考リンクで上げたような位置を決めてだんだん大きくしていくアルゴリズムなどを用いるともう少し早く充填されますが今回はスクリプトを書かないという縛りの中でやったのでこういった実装となっております。