Using PShape Group with Menger Sponge

Chrisir

Hello all,

I have this little code from the forum and I thought it would be faster to add all boxes to a group PShape instead of storing all boxes in an ArrayList.

It works up to 2 but when I go to recursion depth of 3 it totally slows everything down.

What do I do wrong?

Do I have to use endShape?

Thanks !

Best, Chrisir ;-)

import peasy.*;

PeasyCam cam; 
PShape shape1;

// ------------------------------------------------

void setup() {
  size(1200, 1000, P3D);
  cam = new PeasyCam(this, 0, 0, 0, 500);
  println("working");
  shape1 = createShape(GROUP); 

  generate(0, 0, 0, 
    2, 
    167);

  println("done ");
}

void draw() {
  background(0); 
  avoidClipping();
  lights();
  shape(shape1, 0, 0);
}

// ------------------------------------------------------

void generate(float x2, float y2, float z2, 
  int depth, 
  float r) {

  PVector pos=new PVector(x2, y2, z2); 
  int sum ;

  for (int x = -1; x < 2; x++) {
    for (int y = -1; y < 2; y++) {
      for (int z = -1; z < 2; z++) {

        sum = abs(x) + abs(y) + abs(z);

        float newR = r/3;

        if (sum > 1) {
          if (depth==0) { 
            // end of recursion
            Box b = new Box(pos.x + x*newR, 
              pos.y + y*newR, 
              pos.z + z*newR, 
              newR, 
              1); // 1 or k 

            shape1.addChild(b.getShape());
          } else
          {
            //recursion
            generate(pos.x + x*newR, 
              pos.y + y*newR, 
              pos.z + z*newR, 
              depth-1, 
              newR);
          }
        }
      }
    }
  }
  // return boxes;
}//func

void avoidClipping() {
  // avoid clipping (at camera): 
  // https : // 
  // forum.processing.org/two/discussion/4128/quick-q-how-close-is-too-close-why-when-do-3d-objects-disappear
  perspective(PI/3.0, (float) width/height, 1, 1000000);
}//func 


// ========================================================

class Box {

  PVector pos;
  float r;
  //  int index; 

  Box(float x, float y, float z, 
    float r_, 
    int index_) {

    pos = new PVector(x, y, z);
    r = r_;
  }

  PShape getShape() {

    PShape s = createShape(BOX, r);

    s.setFill(color(255));
    s.setStroke(color(111));
    s.translate(pos.x, pos.y, pos.z); 

    //  s.endShape();

    return s;
  }
  //
}//class 
//

Chrisir

using in preferences 8000 MB (?) of Ram

jeremydouglass

Interesting.

So you have written another version of this code that uses an ArrayList -- and it runs faster?

Chrisir

yes, i have another version which runs fast with depth 0 to 2.

it is slow with depth 3 but working. It was so slow using an ArrayList that I attempted to write this new version with PShape but this seems to take a lot of memory.

jeremydouglass

@Chrisir -- I see. This slow-down seems expected -- a Menger sponge is 20^n, so depths are:

• 0: 1 object
• 1: 20 objects
• 2: 400 objects
• 3: 8000 objects

I wonder what the benchmark differences are between

• drawing 8000 boxes per frame
• keeping 8000 box objects in an ArrayList, then drawing
• keeping 8000 box shapes in a PShape group, then drawing

To see a related approach to a Menger Sponge, see this PixelFlow library demo:

- https://forum.processing.org/two/discussion/comment/98724/#Comment_98724

- https://github.com/diwi/PixelFlow/blob/master/examples/Skylight_BulletPhysics_MengerSponge/Skylight_BulletPhysics_MengerSponge.java

Chrisir

thanks!

here is my version with an ArrayList of boxes.

With

• done; depth = 0, 20 boxes.
• done; depth = 1, 400 boxes.
• Data: depth = 2, 8000 boxes.
• Data: depth = 3, 160'000 boxes.

(little different from yours)

Every step, multiply with 20.

With depth = 3 it's getting real slow.

import peasy.*;

ArrayList<Box> boxes = new ArrayList(); 
PeasyCam cam; 

// ------------------------------------------------

void setup() {
  size(1200, 1000, P3D);
  cam = new PeasyCam(this, 0, 0, 0, 200);
  println("working"); 
  //boxes=
  generate(0, 0, 0, 
    2, 
    167);
  println("done: "+boxes.size());
}

void draw() {
  background(0); 
  avoidClipping();
  lights();
  for (int i = 0; i<boxes.size(); i++) {
    //for (int i = 0; i<1; i++) {
    boxes.get(i).show();
  }
}

// ------------------------------------------------------

void generate(float x2, float y2, float z2, int depth, float r) {

  PVector pos=new PVector(x2, y2, z2); 
  int sum ;

  for (int x = -1; x < 2; x++) {
    for (int y = -1; y < 2; y++) {
      for (int z = -1; z < 2; z++) {

        sum = abs(x) + abs(y) + abs(z);

        if (false) {
          if (sum <= 1) {
            break;
          }
        }

        float newR = r/3;

        if (sum > 1) {
          if (depth==0) {
            Box b = new Box(pos.x + x*newR, 
              pos.y + y*newR, 
              pos.z + z*newR, 
              newR, 
              boxes.size());

            // if (x!=-1&&y!=0)
            // if (random(100)>9)
            boxes.add(b);
          } else
          {
            generate(pos.x + x*newR, 
              pos.y + y*newR, 
              pos.z + z*newR, 
              depth-1, 
              newR);
          }
        }
      }
    }
  }
  // return boxes;
}//func

void avoidClipping() {
  // avoid clipping (at camera): 
  // https : // 
  // forum.processing.org/two/discussion/4128/quick-q-how-close-is-too-close-why-when-do-3d-objects-disappear
  perspective(PI/3.0, (float) width/height, 1, 1000000);
}//func 


// ========================================================

class Box {

  PVector pos;
  float radius;
  int index; 

  Box(float x, float y, float z, 
    float radius_, 
    int index_) {
    pos = new PVector(x, y, z);
    radius = radius_;
    index = index_;     //index = boxes.size();
  }

  void show() {
    pushMatrix();
    translate(pos.x, pos.y, pos.z);

    // text 
    if (false) {
      pushMatrix(); // store Matrix
      fill(255, 2, 2); //red
      textAlign(CENTER, CENTER); // alignment  
      textMode(SHAPE);           // looks much better 
      text(index, 0, 0, 0); // this is new
      popMatrix(); // restore Matrix
    }

    // how to draw the box
    if (!keyPressed) {
      //  noStroke();
      stroke(111); 
      fill(255);//white
      fill(255, 0, 0);//white
    } else {
      noFill(); 
      stroke(255);
    }

    //box
    box(radius);

    popMatrix();
  }//method
  //
}//class 
//

jeremydouglass

Ah, yes. If you are numbering that way, then even moreso!

"Why are my 160,000 boxes rendering so slowly?"
"Because there are 160,000 of them."
"Why are my 160,000 objects taking up so much memory?"
"Because there are 160,000 of them."

Chrisir

Yeah, I understand this.

My questions:

1. Do I have to use endShape? Do I use PShape correctly?

2. Are there more efficient ways to copy everything to my graphics card or so?

3. Does peasycam make it slower than necessary?

T_D

Grouped PShapes are not that bad, and have its advantages, e.g. if you want to modify each child in a later process (style, transformation, etc...).

But for a rather static Menger Sponge you can save a lot of time and memory if you create just one PShape and put all generated quads (cube-faces) in it.

shp_ms = createShape(); shp_ms.beginShape(QUADS); shp_ms.vertex(x,y,z); shp_ms.vertex(x,yz); ... shp_ms.endShape();

Another optimization is, to not generate invisible faces in the first place, ... and there are actually quite a lot of them.

Here is an older sketch, ... now updated for Processing 3. It is a bit complicated, but therefore creates and renders pretty fast.

To run level 6 (key '6') you probably need to increase the max available memory in the preferences.

//
// Menger Sponge
//
// Author: Thomas Diewald
//
// Source: www.openprocessing.org/sketch/84986
//
//
// block:     28     24     20    16     12     8     4     0
// content:   -   DEPTH     XN    XP     YN    YP    ZN    ZP
// integer: 0000   0000   0000  0000   0000  0000  0000  0000
//
//
//    depth |     cubes  |   faces max  |  faces real |   saved
//        1 |         1  |           6  |          6  |   1.000
//        2 |        20  |         120  |         72  |   0.600
//        3 |       400  |       2.400  |      1.056  |   0.440
//        4 |     8.000  |      48.000  |     17.856  |   0.372
//        5 |   160.000  |     960.000  |    321.600  |   0.335
//        6 | 3.200.000  |  19.200.000  |  5.896.512  |   0.307
//
//
// keys '1' - '6' ... create sponge with depth 1 to 6
//

import java.util.Locale;
import peasy.*;

PeasyCam cam;
PShape shp_ms;

int DEPTH = 5;
float SIZE = 300; 

float box_scale = 0.49f;
int FACE_COUNT = 0;

// color for new faces at each depth
int[][] table = {
    new int[]{   0,   0,   0 }, // depth 0
    new int[]{  64,  64,  64 }, // depth 1
    new int[]{ 220, 220, 220 }, // depth 2
    new int[]{ 255, 190,   0 }, // depth 3
    new int[]{ 255,  96,   0 }, // depth 4
    new int[]{ 255,  32,   0 }, // depth 5
    new int[]{ 180,   0,   0 }, // depth 6
    new int[]{  64,   0,   0 }, // depth 7
};

int[] col = new int[table.length];

public void settings() {
  size(1000, 1000, P3D);
  smooth(8);
}

public void setup() {

  cam = new PeasyCam(this, 0, 0, 0, 500);
  perspective(60 * PI/180f, width / (float) height, 1, 1000000);
  
  for(int i = 0; i < table.length; i++) {
    col[i] = color(table[i][0], table[i][1], table[i][2]);
  }
  
  createMengerSponge();

  frameRate(1000);
}

public void draw() {
  float s = 0.5f;
  directionalLight(255 * s, 255 * s, 255  * s, +125, +250, +500);
  directionalLight(255 * s, 200 * s, 220  * s, -125, -500, +250);
  directionalLight(200 * s, 220 * s, 255  * s, +250, -125, -500);
  ambientLight(64, 64, 64);
  pointLight(255, 255, 255, 0,0,0);
  
  background(16);

  shape(shp_ms);
  
  String title = String.format(Locale.ENGLISH, "[depth %d]  [faces %d]  [fps %6.2f]", DEPTH, FACE_COUNT, frameRate);
  surface.setTitle(title);
}


void createMengerSponge(){
  long timer = System.currentTimeMillis();
  shp_ms = createShape();
  shp_ms.beginShape(QUADS);
  shp_ms.noStroke();
  shp_ms.fill(0xFFFFFFFF);
  
  FACE_COUNT = 0;
  DEPTH <<=24;
  mengerSponge(0,0,0, SIZE, 0x01111111/*.DEPTH.FACES.*/);
  DEPTH >>=24;

  shp_ms.endShape();
  timer = System.currentTimeMillis() - timer;

  int cubes_max = (int) Math.pow(20, DEPTH-1);  
  int face_max  = cubes_max * 6;
  int face_real = FACE_COUNT;
  float real_v_max = face_real / (float) face_max;
  
  System.out.println("mengerSponge "+timer +"ms");
  System.out.println("  depth "+ DEPTH);
  System.out.println("  cubes "+ cubes_max);
  System.out.println("  faces "+ face_real+" (instead of "+face_max+") --> "+real_v_max);
}


void mengerSponge(float x, float y, float z, float s, int F){ 
  if( (F & 0x00FFFFFF) == 0 )  return; // box got completely eliminated 
  if( (F & 0x0F000000) == DEPTH) {
    createCube(x, y, z, s, F);
  } else {
    s /= 3f;
    final float xn = x-s, xp = x+s;
    final float yn = y-s, yp = y+s;
    final float zn = z-s, zp = z+s;
    
    final int D = (F+=0x01000000) & 0x0F000000; // increment and extract depth
    final int XN = D >> 4, YN = D >> 12, ZN = D >> 20;
    final int XP = D >> 8, YP = D >> 16, ZP = D >> 24;
    
    mengerSponge( xn, yn, zn, s, (F & 0xFFF0F0F0)           );
    mengerSponge( xn, yn, z , s, (F & 0xFFF0F000) | XP | YP );
    mengerSponge( xn, yn, zp, s, (F & 0xFFF0F00F)           );
    mengerSponge( xn, y , zn, s, (F & 0xFFF000F0) | XP | ZP );
    // mengerSponge( xn, y , z , s, 0);
    mengerSponge( xn, y , zp, s, (F & 0xFFF0000F) | XP | ZN );
    mengerSponge( xn, yp, zn, s, (F & 0xFFF00FF0)           );
    mengerSponge( xn, yp, z , s, (F & 0xFFF00F00) | XP | YN );
    mengerSponge( xn, yp, zp, s, (F & 0xFFF00F0F)           );
  
    mengerSponge( x , yn, zn, s, (F & 0xFF00F0F0) | YP | ZP );
    // mengerSponge( x , yn, z , s, 0);
    mengerSponge( x , yn, zp, s, (F & 0xFF00F00F) | YP | ZN );
    // mengerSponge( x , y , zn, s, 0);
    // mengerSponge( x , y , z , s, 0);
    // mengerSponge( x , y , zp, s, 0);
    mengerSponge( x , yp, zn, s, (F & 0xFF000FF0) | YN | ZP );
    // mengerSponge( x , yp, z , s, 0); 
    mengerSponge( x , yp, zp, s, (F & 0xFF000F0F) | YN | ZN );
   
    mengerSponge( xp, yn, zn, s, (F & 0xFF0FF0F0)           );
    mengerSponge( xp, yn, z , s, (F & 0xFF0FF000) | XN | YP );
    mengerSponge( xp, yn, zp, s, (F & 0xFF0FF00F)           );
    mengerSponge( xp, y , zn, s, (F & 0xFF0F00F0) | XN | ZP );
    // mengerSponge( xp, y , z , s, 0);
    mengerSponge( xp, y , zp, s, (F & 0xFF0F000F) | XN | ZN );
    mengerSponge( xp, yp, zn, s, (F & 0xFF0F0FF0)           );
    mengerSponge( xp, yp, z , s, (F & 0xFF0F0F00) | XN | YN );
    mengerSponge( xp, yp, zp, s, (F & 0xFF0F0F0F)           );
  }
}


PVector v1 = new PVector(), v2 = new PVector(), v3 = new PVector(), v4 = new PVector();  
PVector v5 = new PVector(), v6 = new PVector(), v7 = new PVector(), v8 = new PVector();

void createCube(float x, float y, float z, float s, int F){ 
  s *= box_scale;                                //  v1--YN--v2     v5--YN--v6  
  v1.set(x-s, y-s, z-s); v5.set(x-s, y-s, z+s);  //   |      |       |      |   
  v2.set(x+s, y-s, z-s); v6.set(x+s, y-s, z+s);  //  XN  ZN  XP     XN  ZP  XP
  v3.set(x+s, y+s, z-s); v7.set(x+s, y+s, z+s);  //   |      |       |      |   
  v4.set(x-s, y+s, z-s); v8.set(x-s, y+s, z+s);  //  v4--YP--v3     v8--YP--v7  
  
  if( (F & 0x00F00000)!=0 ) createQuad(v1, v5, v8, v4, (F>>20)&0xF); // XN
  if( (F & 0x000F0000)!=0 ) createQuad(v2, v6, v7, v3, (F>>16)&0xF); // XP
  if( (F & 0x0000F000)!=0 ) createQuad(v1, v2, v6, v5, (F>>12)&0xF); // YN
  if( (F & 0x00000F00)!=0 ) createQuad(v4, v3, v7, v8, (F>> 8)&0xF); // YP
  if( (F & 0x000000F0)!=0 ) createQuad(v1, v2, v3, v4, (F>> 4)&0xF); // ZN
  if( (F & 0x0000000F)!=0 ) createQuad(v5, v6, v7, v8, (F>> 0)&0xF); // ZP
}

void createQuad(PVector a, PVector b, PVector c, PVector d, int depth){
  shp_ms.fill(col[depth]);
  shp_ms.vertex(a.x, a.y, a.z);
  shp_ms.vertex(b.x, b.y, b.z);
  shp_ms.vertex(c.x, c.y, c.z);
  shp_ms.vertex(d.x, d.y, d.z);
  FACE_COUNT++; 
}

public void keyReleased(){
  if(key >= '1' && key < '7'){
    DEPTH = key -'0';
    createMengerSponge();
  }
}

further optimizations require to use low-level opengl render. E.g. Cube Instancing, Culling, and/or Implicit Vertex Data, etc...

koogs

2) PShape should be doing that.

3) shouldn't do. It's moving the camera, not the shape.

There are a lot of hidden and common faces in 160k cubes. And does PShape do backface culling? because that would probably help (given that boxes are convex and half the faces are pointing away)

T_D

(i have no idea why it is impossible to post code in this forum that doesnt get messed up, ... <= doesnt seem to work)

thats the cropped part

public void keyReleased(){
  if(key >= '1' && key