FloodFillネタ前半の記事。
別途制作している３Dスキャンモデルのパイプライン処理の一機能としてFlood Fillに近い機能が欲しくなったので、SOPソルバの練習がてらで作ってみた。ここで処理内容的にはソルバを使う必要はないが、ペイントしている過程が見えると、何かの演出に使えて楽しいかもと思い。
いろいろ調整しているうちに、面白い結果を出力する方法が見つかった。その件は後半の記事で。この記事ではまず基本の実装までの過程と処理結果を記す。
FloodFillとは
今回はwikipedia見ながら作った。古き良きペイントアルゴリズムという感じだ。
https://en.wikipedia.org/wiki/Flood_fill
これをHoudiniで実現する。例によってすでに標準ノードでそのような物があるかもしれないが、見つからなければ作ってみるが信条なので良いのだ。どうせカスタム化を施す。もっと言えばほかに作ってる人もいそう。
実装結果
とりあえずうまく行った。1色だけでなく、多色を同時に塗れるように一般に見つかるロジックから実装を調整してある。
アニメーションは処理に必須ではない。塗りを1フレームで終わらせることもできる。wikipediaの解説例と少し塗る経路や太さが異なるのは、3Dサーフェース上での適用をふまえて、隣接エリア判定が単純に上下左右にあるものを採用していないから。しかし、QueueとStackどちらを処理のタスク管理に使うかで結果が変わるのは同じだ。
いくつかランダムに打った点から塗りを発展させてみたが、最終結果を見ると、QUEUE処理を使った右側はボロノイの処理結果のようである。実際、ほぼコアとなった点からの距離で塗りのエリアが決まっているので、距離の計算がちょっと異なるボロノイの亜種であるといえそうだ。STACKの処理では最初に打った点のみの処理ですべてが埋まってしまった（それで正しい）。
// 隣接するプリムをあらかじめ配列に入れている
if(! haspointattrib(0, "neighbours")){
// neighbours cache
i[]@neighbours = {};
int pts[] = primpoints(0, @primnum);
foreach(int pt;pts){
int prims[] = pointprims(0, pt);
foreach(int prim;prims){
if(@primnum == prim) {
continue;
}
int found = find(i[]@neighbours, prim);
if(found < 0){
push(i[]@neighbours, prim);
}
i[]@neighbours = sort(i[]@neighbours);
}
}
}上のコードは、隣接したプリムをあらかじめ配列に入れておくvex処理（ランオーバーはプリム）。今回はポイントではなく、ポリゴン（プリム）単位で色を塗りたかったので、ポイント用関数であるneighboursが使えない。neighboursのプリム版がないかなっと探したが見つからなかったので自分で作った。処理に無駄があるかもしれないが、あらかじめ計算してあるので大きな問題にはならないだろう。ここを書き換える事でいわゆる2D版のfloodfillに近くなるはずだ。
３Dモデルへの適用
テストはグリッド平面で行ったが、３Dサーフェス上で動くように実装してある。当然だが細かいメッシュのジオメトリにペイントを適用すると処理が重くなる。
実装のポイント
SOP処理のポイントだけかいつまんで書いておく。
処理をかけたいモデルに、適用にプリム番号のソートをかけ（このソートのかけ方で結果ががらっと変わる。詳しくは後半の記事に。）pointwrangleで適用にカラーの点を打つ。
if(($FF % 10000) == 2){
if(random(@primnum * $FF + 10) < 0.001){
i@fillIndex = $FF;
v@fillColor = random(@primnum + $FF);
}
}先の動画では初期値として点を打つだけだが、後追いで任意のタイミングで点を打ってもそこからペイントが発展するようにしてある。i@fillIndexはペイントの優先順位（値が大きいほうが強い）になるので、点を打ったフレーム番号を（浮動小数点フレーム番号をintとして）入力としている。塗りたい色はv@fillColorに設定する。あとはソルバ処理に任せている。
ソルバのネットワーク。最初に初期値を設定し、input1からペイント色の起点データが入力されるのを待つ。指定回数だけドットのペイントを繰り返すのにループを使っている。対象ドットがない場合は処理をしないようにswitch（右側）を差し込んである。ほぼ何もしなくてもループが回っているだけで重くなるようだ。
先ほどの隣接したプリムをあらかじめ配列に入れておくvex処理はinit_attribノードに書かれている。
ソルバには追加パラメータが設定してある。QueueなのかStackなのかを選択するスライダー（ここがトグルボタンではなく、スライダーなのがミソである。詳しくは後半の記事にて。）、何フレーム目からペイントを始めるのかの設定（動画撮影用に処理が始まる前の絵も欲しかったので。）、1フレームにペイントしようとするトライの回数（内部処理のループ回数、実際にペイントできるとは限らない）の3つ。
int fillIndex = primattrib(1, "fillIndex", @primnum, 1);
vector fillColor = primattrib(1, "fillColor", @primnum, 1);
// vector qBgColor = primattrib(1, "qBgColor", @primnum, 1);
if(fillIndex > 0){
setdetailattrib(0, "p_queue", @primnum, "append");
i@fillIndex = fillIndex;
v@qBgColor = @Cd;
@Cd = fillColor;
}上記はqという名前のノードに書かれているvex処理。第一入力に入ってきたペイントの起点データがあれば、保存して後続のシミュレーション処理で使えるようにする。v@qBgColorはペイントする対象となる背景色。fillColorはペイント色だがこのタイミングで塗ってしまっている。p_queueというのは処理をするプリム番号を蓄えておく配列で、ここがquiueまたはstackで処理される。
int success;
int p;
int fillIndex;
vector color;
vector bgcolor;
i@paintCount++;
if(len(i[]@p_queue) > 0){
float r = random(len(i[]@p_queue));
int fifo = r < chf("../../../fifoRatio");
if(fifo){
p = removeindex(i[]@p_queue, 0);
} else {
p = pop(i[]@p_queue);
}
color = primattrib(0, "Cd", p, success);
fillIndex = primattrib(0, "fillIndex", p, success);
bgcolor = primattrib(0, "qBgColor", p, success);
int neighbours[] = primattrib(0, "neighbours", p, success);
foreach(int nb;neighbours){
vector nbColor = primattrib(0, "Cd", nb, success);
int nbFillIndex = primattrib(0, "fillIndex", nb, success);
if(nbColor != color && nbColor == bgcolor && nbFillIndex < fillIndex){
int found = find(i[]@p_queue, nb);
if(found < 0){
setprimattrib(0, "Cd", nb, color);
setprimattrib(0, "fillIndex", nb, fillIndex);
setprimattrib(0, "qBgColor", nb, bgcolor);
push(i[]@p_queue, nb);
}
}
}
}
i@queueLength = len(i[]@p_queue);primattrib関数が多用されているため見通しが悪いが、基本的にはwikipediaに書かれているアルゴリズムの応用である。塗る前に背景色が指定の色か確かめているが、やりたいことによっては、境界色判定などに書き換えてもいいだろう。他にはfillIndexでの優先順位判定を行っている。これによって、時間をずらしたペイントの追加登録が可能となっている。
