2D surface growth: how to make my code run faster?

Processing Coding Questions
1

Hello,

I am programming some pixel-based 2d growth on a PImage from a random point.

However I would like the code to run faster, especially the addNeighbour() function. On an i7-7820HQ/2.90GHz I need something like 5s for each growth cycle after the first cycles whereas I would like the advance to be perceived as continuous.

Any suggestion?

Thank you in advance.

PImage pict;
int zoomFactor = 1; // increase to reduce resolution
int myWidth = 1600/zoomFactor;
int myHeight = 900/zoomFactor;
int startPos;

int colorCounter = 1;

int[][] baseNeighbours = {{-1, -1},{0,-1},{1,-1},{-1,0},{1,0},{-1,1},{0,1},{1,1}};

ArrayList<Integer> emptyPix = new ArrayList<Integer>();
ArrayList<Integer> filledPix = new ArrayList<Integer>();
ArrayList<Integer> neighbourPix = new ArrayList<Integer>();

void setup() {
  fullScreen();
  noStroke();
  frameRate(30);
  smooth(1); // avoids anti-aliasing when at 0
  pict = createImage(myWidth, myHeight, RGB);
  fillEmptyPix(pict, emptyPix);
  fillBlack(pict);
  setStartPoint();
  getInitialNeighbours();  
}

void draw() {
  background(128);
  image(pict, 50, 50, myWidth * zoomFactor, myHeight * zoomFactor);
  addNeighbour();
}

void fillEmptyPix(PImage pict, ArrayList list) {
  int size = pict.width*pict.height;
  for (int i  = 0; i < size; i++) {
    list.add(i);
  }
}

// function to fill PImage in black
void fillBlack(PImage pict) {
  for (int x  = 0; x < pict.width ; x++) {
    for (int y  = 0; y < pict.height ; y++) {
      int pos = y * pict.width + x;
      pict.pixels[pos] = color(0);
    }
  }
  pict.updatePixels();
}

// function to generate the first point
void setStartPoint() {
  int pos = int(random(pict.width*pict.height));    
  pict.pixels[pos] = color(int(colorCounter/100),0,255-(int(colorCounter/100)));
  colorCounter += 100;
  colorCounter %= 25501;
  filledPix.add(pos);
  emptyPix.remove(pos);
  startPos = pos;
  pict.updatePixels();
}

// get neighbour pixels on first go
void getInitialNeighbours() {
  int startX = startPos % pict.width; 
  int startY = startPos / pict.width ;
  for (int i = 0; i < 8 ; i++) {
    int newX = startX+baseNeighbours[i][0];
    int newY = startY+baseNeighbours[i][1];
    // tests whether neighbour is within image limits
    if ((newX >= 0 && newX < pict.width) && (newY >= 0 && newY < pict.height)) {
      int point = newY*pict.width+newX;      
      neighbourPix.add(point);
      emptyPix.remove(emptyPix.indexOf(point));     
      pict.pixels[point] = color(0,255,0);
    }
  }
  pict.updatePixels();
}

void addNeighbour() {
  int batchSize = neighbourPix.size() / 3;
  for (int x = 0;  x < batchSize ; x++) {
    // prend un point au hasard dans neighbourg
    int posInArray = int(random(neighbourPix.size()));
    int value = neighbourPix.get(posInArray);
    filledPix.add(value);
    neighbourPix.remove(posInArray);
    // new reference position
    int pos = value;
    // updates neighbourPix et filledPix
    int refX = pos % pict.width; 
    int refY = pos / pict.width ;
    for (int i = 0; i < 8 ; i++) {
      int newX = refX+baseNeighbours[i][0];
      int newY = refY+baseNeighbours[i][1];
      // tests whether neighbour is within image limits
      if ((newX >= 0 && newX < pict.width) && (newY >= 0 && newY < pict.height)) {
        int newPosInArray = newY*pict.width+newX; 
        // tests whether neighbour is in emptyPix (otherwise it's already in filledPix or neighbourPix)
        // then moves position to neighbourPix
        if (emptyPix.contains(newPosInArray)) { 
          neighbourPix.add(newPosInArray);
          emptyPix.remove(emptyPix.indexOf(newPosInArray)); 
        } 
        pict.pixels[value] = color(0,255,0);
      }
    }
    pict.pixels[pos] = color(int(colorCounter/100),0,255-int(colorCounter/100));
  }
  colorCounter += 2400;
  colorCounter %= 25501;
  pict.updatePixels();
}

}
1 Like
2

Your code is being hammered by the statement if (emptyPix.contains(newPosInArray)) since this is doing an O(N) lookup (on an array the size of the #pixels!) within a nested for-loop.

Simply changing this variable from a List to Set speeds things up massively. Using a boolean[] for this would be even more appropriate.

Situations like this are why even a cursory knowledge of different data structures is useful.

import java.util.HashSet;
import java.util.Collection;

PImage pict;
int zoomFactor = 1; // increase to reduce resolution
int myWidth = 800;
int myHeight = 800;
int startPos;

int colorCounter = 1;

int[][] baseNeighbours = {{-1, -1}, {0, -1}, {1, -1}, {-1, 0}, {1, 0}, {-1, 1}, {0, 1}, {1, 1}};

HashSet<Integer> emptyPix = new HashSet<Integer>(myWidth*myHeight);
HashSet<Integer> filledPix = new HashSet<Integer>(myWidth*myHeight);
ArrayList<Integer> neighbourPix = new ArrayList<Integer>();

void setup() {
  //fullScreen();
  size(1000, 1000);
  noStroke();
  frameRate(666);
  smooth(1); // avoids anti-aliasing when at 0
  pict = createImage(myWidth, myHeight, RGB);
  fillEmptyPix(pict, emptyPix);
  fillBlack(pict);
  setStartPoint();
  getInitialNeighbours();
}

void draw() {
  background(128);
  image(pict, 50, 50, myWidth * zoomFactor, myHeight * zoomFactor);
  addNeighbour();
}

void fillEmptyPix(PImage pict, Collection list) {
  int size = pict.width*pict.height;
  for (int i  = 0; i < size; i++) {
    list.add(i);
  }
}

// function to fill PImage in black
void fillBlack(PImage pict) {
  for (int x  = 0; x < pict.width; x++) {
    for (int y  = 0; y < pict.height; y++) {
      int pos = y * pict.width + x;
      pict.pixels[pos] = color(0);
    }
  }
  pict.updatePixels();
}

// function to generate the first point
void setStartPoint() {
  int pos = int(random(pict.width*pict.height));
  pict.pixels[pos] = color(int(colorCounter/100), 0, 255-(int(colorCounter/100)));
  colorCounter += 100;
  colorCounter %= 25501;
  filledPix.add(pos);
  emptyPix.remove(pos);
  startPos = pos;
  pict.updatePixels();
}

// get neighbour pixels on first go
void getInitialNeighbours() {
  int startX = startPos % pict.width;
  int startY = startPos / pict.width ;
  for (int i = 0; i < 8; i++) {
    int newX = startX+baseNeighbours[i][0];
    int newY = startY+baseNeighbours[i][1];
    // tests whether neighbour is within image limits
    if ((newX >= 0 && newX < pict.width) && (newY >= 0 && newY < pict.height)) {
      int point = newY*pict.width+newX;
      neighbourPix.add(point);
      emptyPix.remove(point);
      pict.pixels[point] = color(0, 255, 0);
    }
  }
  pict.updatePixels();
}

void addNeighbour() {
  int batchSize = neighbourPix.size() / 3;
  for (int x = 0; x < batchSize; x++) {
    // prend un point au hasard dans neighbourg
    int posInArray = int(random(neighbourPix.size()));
    int value = neighbourPix.get(posInArray);
    filledPix.add(value);
    neighbourPix.remove(posInArray);
    // new reference position
    int pos = value;
    // updates neighbourPix et filledPix
    int refX = pos % pict.width;
    int refY = pos / pict.width ;
    for (int i = 0; i < 8; i++) {
      int newX = refX+baseNeighbours[i][0];
      int newY = refY+baseNeighbours[i][1];
      // tests whether neighbour is within image limits
      if ((newX >= 0 && newX < pict.width) && (newY >= 0 && newY < pict.height)) {
        int newPosInArray = newY*pict.width+newX;
        // tests whether neighbour is in emptyPix (otherwise it's already in filledPix or neighbourPix)
        // then moves position to neighbourPix
        if (emptyPix.contains(newPosInArray)) {
          neighbourPix.add(newPosInArray);
          emptyPix.remove(newPosInArray);
        }
        pict.pixels[value] = color(0, 255, 0);
      }
    }
    pict.pixels[pos] = color(int(colorCounter/100), 0, 255-int(colorCounter/100));
  }
  colorCounter += 2400;
  colorCounter %= 25501;
  pict.updatePixels();
}

image
image1000×1000 174 KB

1 Like
3

You’re certainly right but I don’t even see HashSet in the Data section of the Processing reference.

Thank you anyway because the sketch is indeed much faster now!

4

You can find it in the Java doc: HashSet (Java Platform SE 7 )