p5.jsで生のフレームバッファを使って二つの図形の交叉判定

# はじめに
　言っておきます。p5.Framebufferは使いません。重いので。

　今回取り扱うのは交叉判定です。2枚の同じサイズのグラフィックがあるとき、両者で同じ位置のピクセルで共にアルファが正になっているものがあるかどうかの判定です。要するに交わり判定ですね。例えばこの記事が扱っています。

https://qiita.com/joe0hara/items/5cc70557725351f84c17

　これをブルートフォース（力ずく）でやるとひとつひとつ同じ位置のピクセルをフェッチするので途方もなく時間がかかります。そこで2枚の画像にそれぞれ描画内容を用意して、両者を重ねることで得られる画像のアルファ値を見てそれが正のピクセルがあれば交叉している、という判定方法を使うことになります。重ねるというのはアルファ値の乗算をするわけで、シェーダーが必要となります。つまり2Dではできないわけです。

　webGL = 3Dではないですからね。あくまで描画方法の違いであり、webGLはこの場合2Dよりも優れている、と言うだけのことです。それも判定する際には、です。描画自体は2Dの方が綺麗でしょう。適材適所、役割分担は重要です。

　上の記事ではアルファの最大値を取っているようですが、webGLにそんな機能は無いので自前でやることになります。ざっくりいうと、サイズを半分にしていくシークエンスを作り、上の画像を下に落とす形で圧縮していくやり方です。0しかないなら最後まで0ですし、もし0でない値がちょっとでもあれば結果は正の数となります。

　なお、いつものwebGLのユーティリティはライブラリに落としたので、今回はそれを援用する形となります。それ以外については用意していません。テクスチャも、フレームバッファも、即席で用意します。仕組みが分かってれば問題ないですからね。

 https://github.com/inaridarkfox4231/fox3Dtools

https://qiita.com/inaba_darkfox/items/8a7c7e8cb118289ba931

## コード全文
　[overlap check webGL](https://openprocessing.org/sketch/2572871)
```js
// framebufferの応用。
// 交わり判定
// 役割ごとにちょっとコードを整理しました。

const {createShaderProgram, uniformX} = webglUtils;

let loopFunction = () => {};

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

  // 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);
  }
  `;

  const prepareFS =
  `#version 300 es
  precision highp float;
  precision highp sampler2D;
  in vec2 vUv;
  uniform sampler2D uGraphic1;
  uniform sampler2D uGraphic2;
  out vec4 fragColor;
  void main () {
    float alpha1 = texture(uGraphic1, vUv).a;
    float alpha2 = texture(uGraphic2, vUv).a;
    fragColor = vec4((alpha1 * alpha2 > 0.0 ? 1.0 : 0.0));
  }
  `;

  const displayFS =
  `#version 300 es
  precision highp float;
  in vec2 vUv;
  uniform bool uUseFlagTexture;
  uniform sampler2D uGraphic;
  uniform sampler2D uFlagTexture;
  out vec4 fragColor;
  void main(){
    vec2 uv = vUv;
    uv.y = 1.0 - uv.y;
    vec4 col = texture(uGraphic, uv);
    if(uUseFlagTexture){
      float flag = (texture(uFlagTexture, vec2(0.5)).r > 0.0 ? 1.0 : 0.0);
      col *= (0.3 + 0.7 * 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;
  }
  `;

  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, wrap: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 gr1 = createGraphics(width, height);
  const gr2 = createGraphics(width, height);
  const tex1 = createTexture2D(gl, {w:width, h:height, slotIndex:1});
  const tex2 = createTexture2D(gl, {w:width, h:height, slotIndex:2});

  gr1.textSize(min(width,height)*0.2);
  gr1.textAlign(CENTER, CENTER);
  gr1.textStyle(ITALIC);
  gr1.noStroke();
  gr1.fill(255);
  gr1.text("SAMPLE", width/2, height/3);
  gr1.text("TEXT", width/2, height*2/3);

  gr2.textSize(min(width,height)*0.2);
  gr2.textAlign(CENTER, CENTER);
  gr2.noStroke();
  gr2.fill("white");

  updateTexture2D(gl, {gr:gr1, tex:tex1, slotIndex:1});

  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", "uGraphic1", 1);
    uniformX(gl, pgPrepare, "1i", "uGraphic2", 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) => {
    // gr2にお絵描き
    gr2.clear();
    gr2.resetMatrix().translate(mouseX, mouseY).rotate(time);
    gr2.text("🐬", 0, 0);
    updateTexture2D(gl, {gr:gr2, tex:tex2, slotIndex:2});

    // calc flagTexture
    bindFBO(gl, fbo);
    calcFlagTexture();

    // display part
    bindFBO(gl, null);
    gl.viewport(0, 0, width, height);

    gl.clearColor(0.5,0.5,0.5,1);
    gl.clear(gl.COLOR_BUFFER_BIT);
    
    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", false);
    uniformX(gl, pgDisplay, "1i", "uGraphic", 1);
    gl.drawArrays(gl.TRIANGLE_STRIP, 0, 4);
    uniformX(gl, pgDisplay, "1i", "uUseFlagTexture", true);
    uniformX(gl, pgDisplay, "1i", "uGraphic", 2);
    gl.drawArrays(gl.TRIANGLE_STRIP, 0, 4);

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

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

// 2Dのテクスチャを作るだけ
function createTexture2D(gl, params = {}){
  const {w, h, slotIndex, wrap = gl.REPEAT} = params;
  const tex = gl.createTexture();
  gl.activeTexture(gl.TEXTURE0 + slotIndex);
  gl.bindTexture(gl.TEXTURE_2D, tex);
  gl.texImage2D(gl.TEXTURE_2D, 0, gl.RGBA, w, h, 0, gl.RGBA, gl.UNSIGNED_BYTE, null);

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

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

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

実行結果
重ならない場合：

![wdwqfwf.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/437349/a3835c04-c71c-402f-bdc6-afc6c1b58398.png)

重なる場合：

![dfwfwfw.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/437349/1e2165f4-501f-4876-97ce-0f219be91bf1.png)

重なる場合にイルカさんがくっきりするようにしました。まあ何でもいいんですが。

## 方針
　まず全体と同じサイズのテクスチャをひとつ用意し、それのサイズを1x1になるまで半分にしていきます。その系列を作ります。最後のテクスチャだけ記録しておいて判定に使います（flagTexture）。またそれとは別に、2D画像用の、全体と同じサイズのテクスチャを2枚用意します。これらの内容を更新することで交叉判定に使うテクスチャを用意します。
　スロット番号は、判定用のテクスチャは0番を使いまわすものとし、1と2はベースのテクスチャと動的なテクスチャで専用とします。
　内容的にはループ関数のところを見ればいいんですが、まずcalcFlagTextureでflagTextureを計算します。次いで、メイン描画を実行します。その際に重なり判定の結果で以って、透明度などを下げるかどうかをけっていします。

## プログラム一覧
　なお、今回は板描画オンリーなので、アトリビュートは登場しません。バーテックスシェーダをまとめました。
### pgPrepare
　なんかもうプログラムの方がしっくりきますね...それはおいといて、prepareの仕事は2枚のグラフィックを受け取り、それらの共通ピクセルのアルファ値の乗算で色を決めて格納することです。色はアルファの乗算が正の場合に真っ白、正でない場合は透明度0の黒とします。
### pgDisplay
　言わずと知れたテクスチャ描画用です。ソースは2Dキャンバスなので上下の反転が必要です。フレームバッファを介して描画した結果を扱う場合は不要です。この辺ややこしいから場合分けしようとか事前にフリップしようとかなるんですが、まあ、その都度でいいんじゃないでしょうか。
### pgCompression
　徐々にサイズが半分になっていくテクスチャの系列に対し、後のテクスチャのピクセルに対して前のテクスチャのフェッチを実行し、該当ピクセルの周囲のピクセルの和を取っていきます。こうすれば、ちょっとでも1がある場合、それは確実に残ります。それを利用するわけです。ちなみにラップのデフォルトがREPEATなのでCLAMPに変更しています。そうしないとはみ出た時に反対側をみてしまうからです。

　なお、ライブラリからはcreateShaderProgramとuniformXをお借りしています。プログラムが無いとユニフォームをセットできませんからね。

## フレームバッファについて
　今回は全部板ポリですし、2D描画しかしないシンプル仕様で、深度値も出てこないので、fboはひとつだけ作って使いまわしています。まあテクスチャとセットで扱ってもいいんですが枠組みが煩雑になりがちなので、今回はこれで行きましょう。
```js
  const fbo = gl.createFramebuffer();
```
半々にしていくのはここでやっています。
```js
  const texArray = [];
  let currentWidth = width;
  let currentHeight = height;
  while(true){
    const tex = createTexture2D(gl, {
      w:currentWidth, h:currentHeight, slotIndex:0
    });
    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;
  }
```
テクスチャ設定には0番を使っています。同じ番号で延々と設定作業を実行するわけですね。
## 2Dグラフィックの用意
　2Dグラフィックは始めにnullで領域を作ってフィルターも指定したうえで、createGraphicsを使ってあとからアタッチしています。というか更新もこれでやるわけです。
```js
  const gr1 = createGraphics(width, height);
  const gr2 = createGraphics(width, height);
  const tex1 = createTexture2D(gl, {w:width, h:height, slotIndex:1});
  const tex2 = createTexture2D(gl, {w:width, h:height, slotIndex:2});

  gr1.textSize(min(width,height)*0.2);
  gr1.textAlign(CENTER, CENTER);
  gr1.textStyle(ITALIC);
  gr1.noStroke();
  gr1.fill(255);
  gr1.text("SAMPLE", width/2, height/3);
  gr1.text("TEXT", width/2, height*2/3);

  gr2.textSize(min(width,height)*0.2);
  gr2.textAlign(CENTER, CENTER);
  gr2.noStroke();
  gr2.fill("white");
```
　こういうときp5の2Dは本当に便利だなと実感しますね。なお1番と2番にそれぞれセットしています。以降、固定です。なのでuniformXで1や2を指定するだけでプログラム内ではtex1とtex2が参照されます。便利ですね～。

## calcFlagTexture
　この記事のコードに出てくるflagTextureというのは要するに系列の末尾のテクスチャのことです。1x1のサイズになっています。その内容を計算するパートです。
　まず系列の0番（画面と同じサイズ）をfboにセットして、1番と2番を読み込み、アルファ乗算を実行します。白と透明だけの画像ができます。
　次にコンプレッションのプログラムで圧縮していきます。0番に読み込みテクスチャを置いて、fboに書き込みテクスチャをアタッチして、書き込みテクスチャに応じてビューポートを変更します。あとはクリアしたり然るべくユニフォームをセットするとプログラムが走って圧縮が実行されます。webGLのチカラってすげーーー。

## 描画パート
　メイン描画では難しいことを一切やっていません。まずフレームバッファをnullに戻してビューポートもリセットしておきます。gr2への描画とテクスチャの更新はすでに済ませています（calcFlagTextureよりも前に）。ブレンドを機能させ、アルファ梱包済みなので通常のブレンドで重ねます。ベースはフラグテクスチャを使いませんが、落とす方のテクスチャは必要なのでフラグ分岐しています。そしてフラグを使う場合はflagTextureの唯一のピクセルのアルファが正か0かで透明度などを調整します。できました。

## 応用
　たとえば非円形パッキングなんかに使えそうですね。

![fish_packing_2280.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/437349/5da4adb8-b9b8-4177-9777-07a5df675559.png)

# おわりに
　フレームバッファがいちいちテクスチャと紐ついてないコードを書いたのは初めてだったので緊張したんですが、うまくいってよかったです。フレームバッファはただのインタフェースで、それがテクスチャ扱いされていることにずっとよくわかんない違和感があったので、それを解消する意味でも重要だと思いました。

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