メンガースポンジMenger Sponge

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/510257/1019a6d9-9899-4fe3-aaa6-140af011e5b2.png)


![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/510257/a2e52445-c708-4577-b318-55eb1da3bf82.png)


メンガースポンジのプログラムです。
　面を9分割して、押し出す。
　これを繰り返す。
という内容です。

1ポリゴンが12ポリゴンになるので、ポリゴン数は以下のとおり。
| Level | polygon |
|:-:|--:|
| 0 | 6 |
| 1 | 72 |
| 2 | 864 |
| 3 | 10368 |
| 4 | 124416 |
| 5 | 1492992 |
| 6 | 17915904 |

# 環境
Processing 4.2

# ソースコード
```java
ArrayList<Face> faces;
int level = 4;   // 再帰深さ
float depth = 3*3*3*3*3*2; // 押し出し距離

void setup() {
  size(600, 600, P3D);
  stroke(128);
  fill(255);
  // 最初の立方体の6面
  float w = 3*3*3*3*3;
  PVector[] c = {
    new PVector(-w, -w, -w),
    new PVector( w, -w, -w),
    new PVector( w, w, -w),
    new PVector(-w, w, -w),
    new PVector(-w, -w, w),
    new PVector( w, -w, w),
    new PVector( w, w, w),
    new PVector(-w, w, w),
  };
  faces = new ArrayList<Face>();
  // 6面
  faces.add(new Face(c[0], c[1], c[2], c[3])); // -Z
  faces.add(new Face(c[4], c[7], c[6], c[5])); // +Z
  faces.add(new Face(c[0], c[4], c[5], c[1])); // -Y
  faces.add(new Face(c[3], c[2], c[6], c[7])); // +Y
  faces.add(new Face(c[1], c[5], c[6], c[2])); // +X
  faces.add(new Face(c[0], c[3], c[7], c[4])); // -X

  // 再帰分割
  for (int i=0; i<level; i++) {
    ArrayList<Face> next = new ArrayList<Face>();
    for (Face f : faces) next.addAll(f.subdivide(depth/pow(3, i+1)));
    faces = next;
  }
}

void draw() {
  background(30);
  lights();
  translate(width/2, height/2, 0);
  rotateY(millis()*0.0005);
  rotateX(millis()*0.0003);
  for (Face f : faces) f.draw();
}


class Face {
  PVector[] v = new PVector[4]; // 頂点（四隅）
  PVector n; // 法線

  Face(PVector a, PVector b, PVector c, PVector d) {
    v[0] = a.copy();
    v[1] = b.copy();
    v[2] = c.copy();
    v[3] = d.copy();
    n = calcNormal();
  }

  PVector calcNormal() {
    PVector e1 = PVector.sub(v[1], v[0]);
    PVector e2 = PVector.sub(v[2], v[0]);
    return e1.cross(e2).normalize();
  }

  // 9分割して中央だけ押し出す
  ArrayList<Face> subdivide(float depth) {
    ArrayList<Face> faces = new ArrayList<Face>();
    // 4x4グリッドを生成
    PVector[][] p = new PVector[4][4];
    for (int i=0; i<4; i++) {
      float u = i / 3.0;
      for (int j=0; j<4; j++) {
        float vv = j / 3.0;
        PVector a = PVector.lerp(v[0], v[1], u);
        PVector b = PVector.lerp(v[3], v[2], u);
        p[i][j] = PVector.lerp(a, b, vv);
      }
    }
    // 3x3の面生成
    for (int i=0; i<3; i++) {
      for (int j=0; j<3; j++) {
        PVector a = p[i][j];
        PVector b = p[i+1][j];
        PVector c = p[i+1][j+1];
        PVector d = p[i][j+1];
        Face f = new Face(a, b, c, d);

        if (i == 1 && j == 1) {
          // 中央面を押し出す：押し出し後の頂点も生成
          PVector[] extruded = new PVector[4];
          for (int k = 0; k < 4; k++) {
            extruded[k] = f.v[k].copy().add(PVector.mult(f.n, depth));
          }
          // 押し出し後の面
          //Face top = new Face(extruded[0], extruded[1], extruded[2], extruded[3]);
          //faces.add(top);

          // 側面4面を生成
          for (int k = 0; k < 4; k++) {
            int k1 = (k + 1) % 4;
            Face side = new Face(
              f.v[k], f.v[k1], extruded[k1], extruded[k]
              );
            faces.add(side);
          }

        } else {
          faces.add(f);
        }
      }
    }
    return faces;
  }

  void draw() {
    beginShape(QUADS);
    normal(n.x, n.y, n.z);
    for (int i=0; i<4; i++) vertex(v[i].x, v[i].y, v[i].z);
    endShape();
  }
}
```

# 参考
https://en.wikipedia.org/wiki/Menger_sponge

3Dプリント用のデータなら、最初から、斜めに切ってあるモデルがあります。サポートいらず。

https://www.printables.com/model/648813-menger-sponges