はじめに

　フレームバッファを使った交叉判定：

をやったので、応用として非円形のパッキングをします。やることはほぼ一緒です。flagTextureを計算して、これが正の値を返すならばシェーダー内部で透明度を0にして落とせばOKです。readPixelsは使いません。あれを使って描画すればいいかどうかを決めるやり方は一見すると合理的ですが、readPixelsは毎フレーム実行するには重すぎるので採用できません。1x1でも、100x100でも、600x600でも一緒です。小さいから速いということはありません。即時的にインタラクションで実行する分にはいいんですが...

コード全文

　non-circular-packing

const {createShaderProgram, uniformX} = webglUtils;

let loopFunction = () => {};

function setup() {
  createCanvas(windowWidth, windowHeight, WEBGL);
  pixelDensity(1); // 面倒なので
  const gl = this._renderer.GL;

  // float textureの場合にちゃんとfloatが書き込まれるようにする拡張機能
  // 汎用性を意識して利用可能状況を出力
  const ext = gl.getExtension("EXT_color_buffer_float");
  console.log(`${"EXT_color_buffer_float"} is${(ext !== null ? " " : " not ")}available.`);

  // prepareシェーダーは2枚の画像を読み込んで両者のalphaが共に正のところだけ
  // 真っ白にしあとは透明度0の黒にする
  const commonVS =
  `#version 300 es
  const vec2[4] corners = vec2[](
    vec2(-1.0, -1.0), vec2(1.0, -1.0), vec2(-1.0, 1.0), vec2(1.0, 1.0)
  );
  out vec2 vUv;
  void main () {
    vec2 position = corners[gl_VertexID];
    vUv = position * 0.5 + 0.5;
    gl_Position = vec4(position, 0.0, 1.0);
  }
  `;

  // まずここは両方とも同じuvで問題ないです
  const prepareFS =
  `#version 300 es
  precision highp float;
  precision highp sampler2D;
  in vec2 vUv;
  uniform sampler2D uTextureDST;
  uniform sampler2D uTextureSRC;
  out vec4 fragColor;
  void main () {
    float alpha1 = texture(uTextureDST, vUv).a;
    float alpha2 = texture(uTextureSRC, vUv).a;
    fragColor = vec4((alpha1 * alpha2 > 0.0 ? 1.0 : 0.0));
  }
  `;

  // 今回はソースをデストに焼くのにも使う。デストを地に落とすのにも使う。
  // flipの使い方が重要になってくる
  // 両者はノンフリップで比較されるゆえ、焼く際もノンフリップでないと矛盾する。
  // 描画時だけフリップする。それはいつものことですね。
  const displayFS =
  `#version 300 es
  precision highp float;
  in vec2 vUv;
  uniform bool uUseFlagTexture;
  uniform sampler2D uTexture;
  uniform sampler2D uFlagTexture;
  uniform bool uFlip;
  out vec4 fragColor;
  void main(){
    vec2 uv = vUv;
    if(uFlip) uv.y = 1.0 - uv.y;
    vec4 col = texture(uTexture, uv);
    if(uUseFlagTexture){
      float flag = (texture(uFlagTexture, vec2(0.5)).r > 0.0 ? 0.0 : 1.0);
      col *= flag;
    }
    fragColor = col;
  }
  `;

  // 大きさを徐々に半分にしていくことでどれかのピクセルが白であることを判定する。
  const compressionFS =
  `#version 300 es
  precision highp float;
  precision highp sampler2D;
  in vec2 vUv;
  uniform vec2 uTexelSize;
  uniform sampler2D uTexture;
  out vec4 fragColor;
  void main () {
    vec4 sum = texture(uTexture, vUv);
    sum += texture(uTexture, vUv + vec2(uTexelSize.x, 0.0));
    sum += texture(uTexture, vUv + vec2(0.0, uTexelSize.y));
    sum += texture(uTexture, vUv + uTexelSize);
    sum += texture(uTexture, vUv - vec2(uTexelSize.x, 0.0));
    sum += texture(uTexture, vUv - vec2(0.0, uTexelSize.y));
    sum += texture(uTexture, vUv - uTexelSize);
    sum += texture(uTexture, vUv + uTexelSize * vec2(1.0, -1.0));
    sum += texture(uTexture, vUv - uTexelSize * vec2(1.0, -1.0));
    fragColor = sum * 255.0;
  }
  `;

  const pgPrepare = createShaderProgram(gl, {vs:commonVS, fs:prepareFS});
  const pgDisplay = createShaderProgram(gl, {vs:commonVS, fs:displayFS});
  const pgCompression = createShaderProgram(gl, {vs:commonVS, fs:compressionFS});

  // まずこのキャンバスと同じ大きさのテクスチャを作る
  // それを半分にしていく系列を作る
  // スロットは0だけを使いまわす
  // それとは別にfboを用意しておく
  // update可能な2枚のグラフィックを別に用意しておく
  // こちらは1と2で固定とする

  const fbo = gl.createFramebuffer();

  const texArray = [];
  let currentWidth = width;
  let currentHeight = height;
  // コンプレッションなのでREPEATよりはCLAMPの方がいいですね
  while(true){
    const tex = createTexture2D(gl, {
      w:currentWidth, h:currentHeight, slotIndex:0,
      texWrap:gl.CLAMP_TO_EDGE
    });
    texArray.push({tex, w:currentWidth, h:currentHeight});
    currentWidth = Math.floor((currentWidth+1)/2);
    currentHeight = Math.floor((currentHeight+1)/2);
    if(currentWidth === 1 && currentHeight === 1) break;
  }
  const flagTexture = texArray[texArray.length-1]; // 1x1.
  const texArrayLength = texArray.length;

  // まじめにやりたいんで名前をきちんと付けます。
  const grDST = createGraphics(width, height);
  const texDST = createTexture2D(gl, {w:width, h:height, slotIndex:1});
  grDST.stroke(0);
  grDST.strokeWeight(2);
  grDST.line(0,0,width,0);
  grDST.line(width,0,width,height);
  grDST.line(width,height,0,height);
  grDST.line(0,0,0,height);
  grDST.noStroke();
  grDST.fill(255);
  grDST.textSize(Math.min(width, height)*0.2);
  grDST.textAlign(CENTER, CENTER);
  grDST.textStyle(ITALIC);
  grDST.text("PACKING", width/2, height/4);
  updateTexture2D(gl, {gr:grDST, tex:texDST, slotIndex:1});

  // ソースは毎回クリアする。なんか描いたらとりあえずupdateする。
  const grSRC = createGraphics(width, height);
  const texSRC = createTexture2D(gl, {w:width, h:height, slotIndex:2});
  // 今回はテキストを配置する。色と位置とサイズはランダム。
  grSRC.textAlign(CENTER, CENTER);
  grSRC.textStyle(ITALIC);
  grSRC.noStroke();

  // SRCに描画する
  const drawFigure = () => {
    const x = Math.random()*width;
    const y = Math.random()*height;
    const textSizeFactor = 0.03 + 0.17*Math.random();
    grSRC.clear();
    grSRC.textSize(Math.min(width,height)*textSizeFactor);
    grSRC.resetMatrix();
    grSRC.translate(x, y);
    grSRC.rotate(Math.random()*2*Math.PI);
    grSRC.fill(128+Math.random()*128);
    grSRC.text("F", 0, 0);
    updateTexture2D(gl, {gr:grSRC, tex:texSRC, slotIndex:2})
  }

  // SRCとDSTの衝突判定。無修正でOKですね。もうスロットに入ってるし。
  const calcFlagTexture = () => {
    gl.clearColor(0,0,0,0);

    // gr1とgr2を材料にtexArray[0]に落とす
    // そのあとは1をfboして0を、2をfboして1を、...
    // lengthがlなら最後はl-1をfboしてl-2を落とす。

    attachTexture2DtoFBO(gl, fbo, texArray[0].tex);
    gl.viewport(0, 0, texArray[0].w, texArray[0].h);
    gl.clear(gl.COLOR_BUFFER_BIT);

    gl.useProgram(pgPrepare);
    uniformX(gl, pgPrepare, "1i", "uTextureDST", 1);
    uniformX(gl, pgPrepare, "1i", "uTextureSRC", 2);
    gl.drawArrays(gl.TRIANGLE_STRIP, 0, 4);

    gl.useProgram(pgCompression);
    for(let i=1; i<texArrayLength; i++){
      const from = texArray[i-1];
      const to = texArray[i];

      updateTexture2D(gl, {tex:from.tex, slotIndex:0});

      attachTexture2DtoFBO(gl, fbo, to.tex);
      gl.viewport(0, 0, to.w, to.h);
      gl.clear(gl.COLOR_BUFFER_BIT);

      uniformX(gl, pgCompression, "vec2", "uTexelSize", 1/from.w, 1/from.h);
      uniformX(gl, pgCompression, "1i", "uTexture", 0);
      gl.drawArrays(gl.TRIANGLE_STRIP, 0, 4);
    }
  }
  
  loopFunction = (time) => {
    
    // ここでなんかgrSRCに描く。描いたらtexSRCに反映させる。
    drawFigure();

    // flagTextureを計算する
    bindFBO(gl, fbo);
    calcFlagTexture();

    // SRCをDSTに焼く。その際flagTextureを参照する。
    attachTexture2DtoFBO(gl, fbo, texDST);
    gl.viewport(0, 0, width, height);

    gl.useProgram(pgDisplay);
    gl.enable(gl.BLEND);
    gl.blendFunc(gl.ONE, gl.ONE_MINUS_SRC_ALPHA);

    updateTexture2D(gl, {tex:flagTexture.tex, slotIndex:0});
    uniformX(gl, pgDisplay, "1i", "uFlagTexture", 0);
    uniformX(gl, pgDisplay, "1i", "uUseFlagTexture", true);
    uniformX(gl, pgDisplay, "1i", "uTexture", 2);
    uniformX(gl, pgDisplay, "1i", "uFlip", false);
    gl.drawArrays(gl.TRIANGLE_STRIP, 0, 4);

    // ここまでのパートを繰り返すことで高速化できる

    // DSTをベースに落とす
    bindFBO(gl, null);
    gl.viewport(0, 0, width, height);

    gl.clearColor(0, 0, 0, 1);
    gl.clear(gl.COLOR_BUFFER_BIT);

    uniformX(gl, pgDisplay, "1i", "uUseFlagTexture", false);
    uniformX(gl, pgDisplay, "1i", "uTexture", 1);
    uniformX(gl, pgDisplay, "1i", "uFlip", true);
    gl.drawArrays(gl.TRIANGLE_STRIP, 0, 4);

    gl.disable(gl.BLEND);
    gl.flush();
  }

  doubleClicked = () => { save(`non-circular-packing ${frameCount}`); }
}

function draw() {
  loopFunction(millis()/1000);
}

// 2Dのテクスチャを作るだけ
function createTexture2D(gl, params = {}){
  const {
    w, h, slotIndex,
    texFormat = "color", texFilter = gl.LINEAR, texWrap = gl.REPEAT
  } = params;
  const tex = gl.createTexture();
  gl.activeTexture(gl.TEXTURE0 + slotIndex);
  gl.bindTexture(gl.TEXTURE_2D, tex);

  switch(texFormat){
    case "color":
      gl.texImage2D(gl.TEXTURE_2D, 0, gl.RGBA, w, h, 0, gl.RGBA, gl.UNSIGNED_BYTE, null);
      break;
    case "red":
      gl.texImage2D(gl.TEXTURE_2D, 0, gl.R32F, w, h, 0, gl.RED, gl.FLOAT, null);
      break;
    case "float":
      gl.texImage2D(gl.TEXTURE_2D, 0, gl.RGBA32F, w, h, 0, gl.RGBA, gl.FLOAT, null);
      break;
  }

  gl.texParameteri(gl.TEXTURE_2D, gl.TEXTURE_MAG_FILTER, texFilter);
  gl.texParameteri(gl.TEXTURE_2D, gl.TEXTURE_MIN_FILTER, texFilter);

  // ちなみにデフォルトはREPEATだそうです。
  gl.texParameteri(gl.TEXTURE_2D, gl.TEXTURE_WRAP_S, texWrap);
  gl.texParameteri(gl.TEXTURE_2D, gl.TEXTURE_WRAP_T, texWrap);

  return tex;
}

// 2Dのテクスチャの内容更新
// grがnullの場合はスロットに置いたテクスチャを差し替えるだけ
function updateTexture2D(gl, params = {}){
  const {gr = null, tex, slotIndex} = params;
  gl.activeTexture(gl.TEXTURE0 + slotIndex);
  gl.bindTexture(gl.TEXTURE_2D, tex);
  if(gr === null) return;
  const src = gr.elt;
  gl.texImage2D(gl.TEXTURE_2D, 0, gl.RGBA, src.width, src.height, 0, gl.RGBA, gl.UNSIGNED_BYTE, src);
}

// fboをbindするだけ。
function bindFBO(gl, fbo){
  gl.bindFramebuffer(gl.FRAMEBUFFER, fbo);
}

// fboに2Dのtexをくっつけるだけ。
function attachTexture2DtoFBO(gl, fbo, tex){
  gl.framebufferTexture2D(gl.FRAMEBUFFER, gl.COLOR_ATTACHMENT0, gl.TEXTURE_2D, tex, 0);
}

実行結果：

互いに交わってないことを確認できます。

方針

　まずDST（destination）として描画先のキャンバスを用意します。ここにSRC（source）に2D描画した結果を落としていきます。ただしフレームバッファ経由で、です。SRCの方は普通に2D描画したものをtexImageで格納します。入れ方が異なるわけです。SRCとDSTで以前書いたコードにより交叉判定をします。交叉判定の結果により得られるフラグが交叉を示すものなら、落とす際に色をゼロにすることで画像が落ちないようにします。こうすればreadPixelsに頼らず毎フレーム描画できるので、負荷を抑えられます。最後に、キャンバスに落とす際にはいつものように上下を反転させます。

DSTキャンバスの用意

　ここで作っています。

  const grDST = createGraphics(width, height);
  const texDST = createTexture2D(gl, {w:width, h:height, slotIndex:1});
  grDST.stroke(0);
  grDST.strokeWeight(2);
  grDST.line(0,0,width,0);
  grDST.line(width,0,width,height);
  grDST.line(width,height,0,height);
  grDST.line(0,0,0,height);
  grDST.noStroke();
  grDST.fill(255);
  grDST.textSize(Math.min(width, height)*0.2);
  grDST.textAlign(CENTER, CENTER);
  grDST.textStyle(ITALIC);
  grDST.text("PACKING", width/2, height/4);
  updateTexture2D(gl, {gr:grDST, tex:texDST, slotIndex:1});

真ん中よりちょっと上に文字を置きます。外周には黒い線を引いて枠としています。これを用意する意味は、画面の外にはみ出して描画されるのを防ぐことです。枠をまたぐ場合はNGなわけです。一般の場合は目立たないように透明度を落とすといいかもですね。最後にupdateTexture2Dで内容をテクスチャに落としています。

SRCに画像を落とす

　毎フレーム、SRCに何かしら画像を落とし、それとDSTで交叉判定して、OKならそのまま焼くわけですが、まずSRCを用意しましょう。

  const grSRC = createGraphics(width, height);
  const texSRC = createTexture2D(gl, {w:width, h:height, slotIndex:2});
  // 今回はテキストを配置する。色と位置とサイズはランダム。
  grSRC.textAlign(CENTER, CENTER);
  grSRC.textStyle(ITALIC);
  grSRC.noStroke();

今回はテキストなのでこういったセッティングになります。絵文字やSVGやロード画像の場合はまた異なるでしょう。次に毎フレームの更新は次の通り：

  // SRCに描画する
  const drawFigure = () => {
    const x = Math.random()*width;
    const y = Math.random()*height;
    const textSizeFactor = 0.03 + 0.17*Math.random();
    grSRC.clear();
    grSRC.textSize(Math.min(width,height)*textSizeFactor);
    grSRC.resetMatrix();
    grSRC.translate(x, y);
    grSRC.rotate(Math.random()*2*Math.PI);
    grSRC.fill(128+Math.random()*128);
    grSRC.text("F", 0, 0);
    updateTexture2D(gl, {gr:grSRC, tex:texSRC, slotIndex:2})
  }

落とす側は毎回クリアしてスタートします。位置と回転と大きさをランダムに決めています。キャンバスの大きさに応じて異なるサイズとしています。createGraphicsで作る画像はトランスフォームがリセットされないので注意が必要です。push～popでもいいんですがトランスフォーム以外はどうでもいいので使う必要はないです。今回描画するのは$F$の文字だけです。上下左右が分かりやすい優秀なテキストです（アルファベットで上下左右が区別できる最初の文字）。最後にupdateTexture2Dでテクスチャに落とします。

交叉判定

　まずprepareのprogramで両者のテクスチャを取り、どっちもアルファが正のところに真っ白を置きます。

    float alpha1 = texture(uTextureDST, vUv).a;
    float alpha2 = texture(uTextureSRC, vUv).a;
    fragColor = vec4((alpha1 * alpha2 > 0.0 ? 1.0 : 0.0));

ここで採取の際に特に不自然なことはしていません。いずれのテクスチャも、キャンバス要素における「左上」が(0,0)となっています。なので当然ですね。次に、コンプレッションを実行します。その辺の詳しい説明は前回やったので割愛します。flagTextureができました。
　なお、sumで出力するときに255.0を掛けているのはLINEARでやっていて、小さくなってしまうと判定に失敗することが分かったからです。255.0を掛ければ正である限り常に1を保てるので、そういう感じでやろうかと。ほんとはもっといい方法があればいいんですが。

DSTの更新

　flagTextureができたらDSTに落とします。その際の処理がポイントです。使うのはdisplayのprogramですが、これは画像をデフォルトのキャンバスに落とす際にも使います。共用なのでちょっと注意が必要なわけです。

シェーダーサイド：

  void main(){
    vec2 uv = vUv;
    if(uFlip) uv.y = 1.0 - uv.y;
    vec4 col = texture(uTexture, uv);
    if(uUseFlagTexture){
      float flag = (texture(uFlagTexture, vec2(0.5)).r > 0.0 ? 0.0 : 1.0);
      col *= flag;
    }
    fragColor = col;
  }

jsサイド：

    // SRCをDSTに焼く。その際flagTextureを参照する。
    attachTexture2DtoFBO(gl, fbo, texDST);
    gl.viewport(0, 0, width, height);

    gl.useProgram(pgDisplay);
    gl.enable(gl.BLEND);
    gl.blendFunc(gl.ONE, gl.ONE_MINUS_SRC_ALPHA);

    updateTexture2D(gl, {tex:flagTexture.tex, slotIndex:0});
    uniformX(gl, pgDisplay, "1i", "uFlagTexture", 0);
    uniformX(gl, pgDisplay, "1i", "uUseFlagTexture", true);
    uniformX(gl, pgDisplay, "1i", "uTexture", 2);
    uniformX(gl, pgDisplay, "1i", "uFlip", false);
    gl.drawArrays(gl.TRIANGLE_STRIP, 0, 4);

フラグメントシェーダで使っているvUvというのは通常の正規化ビューポート座標です。これの（0,0）に落ちるのがSRCの（0,0）である必要があります。なぜならそういう風に比較したからです。ゆえにフリップは必要なく、vUvでそのままフェッチすればいいわけです。uFlipはfalseです。これで落とされます。SRCはずっと2番を使っているのでuniformでは2を指定するだけでいいです。楽ちんですね。
　素直に考えれば難しくないですね。

キャンバスへの描画

　最後に更新されたDSTを毎フレームベースのキャンバスに落とします。背景色は黒とします。

    // DSTをベースに落とす
    bindFBO(gl, null);
    gl.viewport(0, 0, width, height);

    gl.clearColor(0, 0, 0, 1);
    gl.clear(gl.COLOR_BUFFER_BIT);

    uniformX(gl, pgDisplay, "1i", "uUseFlagTexture", false);
    uniformX(gl, pgDisplay, "1i", "uTexture", 1);
    uniformX(gl, pgDisplay, "1i", "uFlip", true);
    gl.drawArrays(gl.TRIANGLE_STRIP, 0, 4);

    gl.disable(gl.BLEND);
    gl.flush();

fboを切ってビューポートをキャンバスサイズに合わせます。背景を黒にします。フラグテクスチャは使いません。2Dのキャンバスの内容を落とすので上下は反転させます。これで描画されます。
　今回はいずれも2Dの内容でやっているのでそういう感じにはなるんですが、たとえばDSTとSRCを共にシェーダープログラミングで用意する場合、共に画像において（0,0）が左下に来るので、そういう場合はフリップ不要というわけです。そこら辺はその都度考えればよいかと思います。

　一応、申し訳程度にダブルクリックでセーブできるようにしておきました。

    doubleClicked = () => { save(`non-circular-packing ${frameCount}`); }

高速化について

　次の部分を毎フレーム実行するようにすると高速化できます。

  let repeat = 8;
  while(repeat--){

    // ここでなんかgrSRCに描く。描いたらtexSRCに反映させる。
    drawFigure();

    /* 中略 */

    uniformX(gl, pgDisplay, "1i", "uFlip", false);
    gl.drawArrays(gl.TRIANGLE_STRIP, 0, 4);

    // ここまでのパートを繰り返すことで高速化できる
  }

たとえばこうすると8倍速になります。急いでるときとかにおすすめです。あとは多くなったら意図的にサイズの上限を小さくするなどの手法があります。バリエーションは無限にあるので、いろいろ試してみると良いかと思い案す。

おわりに

　非円形パッキングは普通にやると遅いので、速くできるのは嬉しいですね。絵文字などで色々遊んでみると良いかと思います。

ここまでお読みいただいてありがとうございました。