Controlled Circle Packing with Processing

How to implement a controlled circle packing algorithm with Processing

Today we will implement a circle packing algorithm using Processing. The inspiration for this tutorial came from this YouTube video, where Grasshopper was used. Also this time I have to thank Entagma for giving useful hints on how to achieve the result.

We are calling this controlled circle packing as opposed to random circle packing (here an example of the latter), where we randomly try to fit new circles inside the space left. In our case the circles will try to find by themselves their optimal/sub-optimal position by moving inside the given space.

The algorithm goes like this:

• If two circles are overlapping, move them apart;
• If a circle is not overlapping with any other circle, zero its velocity, hence stop its motion.

Also in this case, my starting point was the flocking algorithm written by Daniel Shiffman in the way they we revisited it on our Differential line growth with Processing tutorial.

We will then have a Circle class storing the information about position, velocity, acceleration and radius of each circle:

class Circle {

  PVector position;
  PVector velocity;
  PVector acceleration;
  
  float radius;

  Circle(float x, float y) {
    acceleration = new PVector(0, 0);
    velocity = PVector.random2D();
    position = new PVector(x, y);
    radius = 10;
  }

  void applyForce(PVector force) {
    acceleration.add(force);
  }

  void update() {
    velocity.add(acceleration);
    position.add(velocity);
    acceleration.mult(0);
  }

  void display() {
    ellipse(position.x, position.y, radius, radius);
  }
}

We will then create a Pack class which will perform the algorithm. Inside the Pack class, first of all we populate the array of circles with the initiate() method. The array can eventually be expanded while running the program with the addCircle() method. The main method of the class if run(), where the following operations are conducted for each circle:

• With checkBorders() we make sure that the circles don’t go out of the canvas’ borders by bouncing them back when this happens;
• With checkCirclePosition() we zero the velocity of the circle once we have verified that it is not overlapping with any other circle;
• With applySeparationForcesToCircle() we check the position of the circle against the position of all the other circles and if there is an overlapping we apply a repulsing force to both;
• Finally, we render the circle with displayCircle();

class Pack {
  ArrayList<Circle> circles;

  float max_speed = 1;
  float max_force = 1;

  Pack() {  
    initiate();
  }

  void initiate() {
    circles = new ArrayList<Circle>(); 
    for (int i = 0; i < 750; i++) {
      addCircle(new Circle(width/2, height/2));
    }
  }

  void addCircle(Circle b) {
    circles.add(b);
  }

  void run() {

    PVector[] separate_forces = new PVector[circles.size()];
    int[] near_circles = new int[circles.size()];

    for (int i=0; i<circles.size(); i++) {
      checkBorders(i);
      checkCirclePosition(i);
      applySeparationForcesToCircle(i, separate_forces, near_circles);
      displayCircle(i);
    }
  }

  void checkBorders(int i) {
    Circle circle_i=circles.get(i);
    if (circle_i.position.x-circle_i.radius/2 < 0 || circle_i.position.x+circle_i.radius/2 > width)
    {
      circle_i.velocity.x*=-1;
      circle_i.update();
    }
    if (circle_i.position.y-circle_i.radius/2 < 0 || circle_i.position.y+circle_i.radius/2 > height)
    {
      circle_i.velocity.y*=-1;
      circle_i.update();
    }
  }


  void checkCirclePosition(int i) {

    Circle circle_i=circles.get(i);

    for (int j=i+1; j<=circles.size(); j++) {

      Circle circle_j = circles.get(j == circles.size() ? 0 : j);

      int count = 0;

      float d = PVector.dist(circle_i.position, circle_j.position);

      if (d < circle_i.radius/2+circle_j.radius/2) {
        count++;
      }

      // Zero velocity if no neighbours
      if (count == 0) {
        circle_i.velocity.x = 0.0;
        circle_i.velocity.y = 0.0;
      }
    }
  }


  void applySeparationForcesToCircle(int i, PVector[] separate_forces, int[] near_circles) {

    if (separate_forces[i]==null)
      separate_forces[i]=new PVector();

    Circle circle_i=circles.get(i);

    for (int j=i+1; j<circles.size(); j++) {

      if (separate_forces[j] == null) 
        separate_forces[j]=new PVector();

      Circle circle_j=circles.get(j);

      PVector forceij = getSeparationForce(circle_i, circle_j);

      if (forceij.mag()>0) {
        separate_forces[i].add(forceij);        
        separate_forces[j].sub(forceij);
        near_circles[i]++;
        near_circles[j]++;
      }
    }

    if (near_circles[i]>0) {
      separate_forces[i].div((float)near_circles[i]);
    }

    if (separate_forces[i].mag() >0) {
      separate_forces[i].setMag(max_speed);
      separate_forces[i].sub(circles.get(i).velocity);
      separate_forces[i].limit(max_force);
    }

    PVector separation = separate_forces[i];

    circles.get(i).applyForce(separation);
    circles.get(i).update();
  }

  PVector getSeparationForce(Circle n1, Circle n2) {
    PVector steer = new PVector(0, 0, 0);
    float d = PVector.dist(n1.position, n2.position);
    if ((d > 0) && (d < n1.radius/2+n2.radius/2)) {
      PVector diff = PVector.sub(n1.position, n2.position);
      diff.normalize();
      diff.div(d);
      steer.add(diff);
    }
    return steer;
  }

  void displayCircle(int i) {
    circles.get(i).display();
  }
}

Here we have a fixed circles’ radius:

Here a random radius:

Finally, like in the image at the top of the article, we can make the radius adapt to some value, for example a Perlin noise field. For this purpose I’ve created a new method inside the Circle class and one inside the Pack class:

class Pack {

  [...]

  void run() {

    PVector[] separate_forces = new PVector[circles.size()];
    int[] near_circles = new int[circles.size()];

    for (int i=0; i<circles.size(); i++) {
      checkBorders(i);
      updateCircleRadius(i);
      checkCirclePosition(i);
      applySeparationForcesToCircle(i, separate_forces, near_circles);
      displayCircle(i);
    }
  }

  void updateCircleRadius(int i) {
    circles.get(i).updateRadius();
  }

  [...]
}

class Circle {
  
  [...]

  void updateRadius() {
    radius = 2 + noise(position.x*0.01, position.y*0.01) * 50;
  }

}

Now I am wondering how this could be use to make something out of CNC or 3D printing… material for the next tutorial 😉

Code!