Need help optimizing a collision detection method.

AgustinQ

Hi, I have written a collision detection method that detects collision of arbitrary shapes made by line segmentes in a PShape that is made with beginShape() endShape() method. The program is inspired by Daniel Shiffman's circle packing tutorial but i change it so it could pack arbitrary shapes (in this case Star Wars icons :P). But as more and more shapes are added the code runs really slow.

Here is the code:

    boolean isIntersectingWith(Circle other) {
        int thisVertexCount =shp.getVertexCount();
        int otherVertexCount = other.shp.getVertexCount();

        float distanceBetweenObjets = dist(x,y, other.x,other.y);
        if(distanceBetweenObjets < r + other.r){  //if the distance between centers is large don't check segment by segment collision
        for (int i = 0; i < thisVertexCount; i++) {
          int iPlusOne = i+1;
          if (iPlusOne>= thisVertexCount) { //wraps around to make the segment of the last element and the first.
            iPlusOne -=thisVertexCount;
          }
          for (int j = 0; j < otherVertexCount; j++) {
            int jPlusOne = j+1;
            if (jPlusOne>= otherVertexCount) {
              jPlusOne -=otherVertexCount;
            }

            PVector thisP1, thisP2, otherP1, otherP2;
            thisP1 = new PVector(x, y);
            thisP1.add(shp.getVertex(i).mult(shapeScale));

            thisP2 = new PVector(x, y);
            thisP2.add(shp.getVertex(iPlusOne).mult(shapeScale));

            otherP1 = new PVector(other.x, other.y);
            otherP1.add(other.shp.getVertex(j).mult(other.shapeScale));

            otherP2 = new PVector(other.x, other.y);
            otherP2.add(other.shp.getVertex(jPlusOne).mult(other.shapeScale));


            if (lineIntersect(thisP1, thisP2, otherP1, otherP2) != null) {
              return true;
            }
          }
        }
        }
        return false;
      }

      PVector lineIntersect(float x1, float y1, float x2, float y2, float x3, float y3, float x4, float y4) {
        double denom = (y4 - y3) * (x2 - x1) - (x4 - x3) * (y2 - y1);
        if (denom == 0.0) { // Lines are parallel.
          return null;
        }
        double ua = ((x4 - x3) * (y1 - y3) - (y4 - y3) * (x1 - x3))/denom;
        double ub = ((x2 - x1) * (y1 - y3) - (y2 - y1) * (x1 - x3))/denom;
        if (ua >= 0.0f && ua <= 1.0f && ub >= 0.0f && ub <= 1.0f) {
          // Get the intersection point.
          return new PVector((int) (x1 + ua*(x2 - x1)), (int) (y1 + ua*(y2 - y1)));
        }

        return null;
      }
      PVector lineIntersect(PVector p1, PVector p2, PVector p3, PVector p4) {
        return lineIntersect(p1.x, p1.y, p2.x, p2.y, p3.x, p3.y, p4.x, p4.y );
      }

Any suggestions are appreciated

Thanks

PS: sorry for my English its my second language

Lord_of_the_Galaxy

One way is to remove all usage of dist() as it relies on finding a square root - a slow process. Instead make a function distSq() and use it instead.
dist(x1, y1, x2, y2) return this - sqrt(sq(x1 - x2) + sq(y1 - y2)) .
distSq(x1, y1, x2, y2) should then return this - sq(x1 - x2) + sq(y1 - y2).

koogs

PVector thisP1, thisP2, otherP1, otherP2;

Move this outside the double loop, instantiate them there.

Inside the loop use set() rather than new()

koogs

If you aren't interested in where the lines intersect then just make that method return a boolean rather than calculating the intersection and ignoring it.

koogs

How are you calling isIntersectingWith?

AgustinQ

Hi, thanks a lot! will try your suggestions and post back.

isIntercectingWith is calles in a nested for loop to check every object with every other object. Here is the main code (sorry if it's ugly but i am a beginner):

// Daniel Shiffman
// http://codingtra.in
// http://patreon.com/codingtrain
// Code for: https://youtu.be /QHEQuoIKgNE

ArrayList<Circle> circles;
ArrayList<PImage> iconos;
ArrayList<PShape> formas;
PImage maskImg;
ArrayList<PVector> seedPoints;
boolean finished = false;

void setup() {
  size(400, 345, P2D);
  circles = new ArrayList<Circle>();
  iconos = new ArrayList<PImage>();
  formas = new ArrayList<PShape>();
  iconos.add(loadImage("Darth Vader.png"));
  iconos.add(loadImage("Storm Trooper.png"));
  iconos.add(loadImage("Death Star.png"));
  iconos.add(loadImage("C3PO.png"));
  iconos.add(loadImage("Chuwaca.png"));
  iconos.add(loadImage("Milenium Falcon.png"));
  iconos.add(loadImage("Princes Leia.png"));
  iconos.add(loadImage("R2D2.png"));
  formas.add(createDarthVaderShape());
  formas.add(createStormTrooperShape());
  formas.add(createDeathStarShape());
  formas.add(createC3POShape());
  formas.add(createChuwacaShape());
  formas.add(createMileniumFalconShape());
  formas.add(createPrincesLeiaShape());
  formas.add(createR2D2Shape());


  seedPoints = new ArrayList<PVector>();
  maskImg = loadImage("maskImage400x345.png");  
  maskImg.loadPixels();  
  for (int x = 0; x < maskImg.width; x++) {
    for (int y = 0; y < maskImg.height; y++) {
      color pix = maskImg.pixels[x + y * maskImg.width];
      if (brightness(pix)<50) {        
        seedPoints.add(new PVector(x, y));
      }
    }
  }
}

void draw() {
  background(255);


  int max = 30000;
  int total = 20;
  int count = 0;
  int attempts = 0;


  if (circles.size() <max) {
    while (count <  total) {
      Circle newC = newCircle();
      if (newC != null) {
        circles.add(newC);
        count++;
      }
      attempts++;
      if (attempts > 1000) {
        finished = true;
        break;
      }
    }
  }


  for (int i = 0; i < circles.size(); i++) {
    if (circles.get(i).growing) {
      if (circles.get(i).edges()) {
        circles.get(i).growing = false;
      } else {
        for (int j = 0; j < circles.size(); j++) {
          if (circles.get(i) != circles.get(j)) {

            if (circles.get(i).isIntersectingWith(circles.get(j))) {
              circles.get(i).growing = false;
              break;
            }
          }
        }
      }
    }
    circles.get(i).show();
    circles.get(i).grow();
  }
  println(circles.size());
  println(frameRate);

if(mousePressed){
  save("output");
}

  if (finished) {
    save("finishedOutput");
    noLoop();
    println(millis());
    println("FINISHED");
  }
}

Circle newCircle() {

  PVector seed = seedPoints.get(int(random(0, seedPoints.size())));
  float x = seed.x;
  float y = seed.y;
  int index = int(random(formas.size()));

  boolean valid = true;
  for (Circle c : circles) {

    if (c.containsPoint(x, y)) {
      valid = false;
    }
  }

  if (valid) {
    return new Circle(x, y, iconos.get(index), formas.get(index));
  } else {
    return null;
  }
}

/*
void mousePressed() {
  for (Circle c : circles) {
    c.noDisplay();
  }
}

void keyPressed() {
  for (Circle c : circles) {
    c.display();
  }
}
*/

Here I made a GitHub repository to share the whole code so you can run it: https://github.com/Agustin-Q/Arbitrary-Shape-Packing.git

And here is the final output of the sketch:

Thanks a lot!!

koogs

400x345

so potentially 138k items then. maybe a third of that is dark pixels. call it 40k items.

i think there's your problem 8) i wouldn't sample EVERY pixel

and this is a classic optimisation opportunity

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

i know you are ignoring items when i = j but you are comparing, eg item 1 against item 2 (i=1, j=2) and, later, item 2 against item 1 (i=2, j=1) when the latter is bound to collide if the former does.

i suggest using j = i + 1 in the for loop and processing both i and j at the same time, stopping them both if there is a collision?

(but given that they all start a pixel apart, aren't there always collisions?)

koogs

having run it, it's a bit subtler than that and the i+1 optimisation results in uglier results.

(they don't start a pixel apart, all the dark pixels are put into a pot as candidates, 20 are chosen each frame and grow from there until they hit something)

AgustinQ

koogs, you are right, de i+1 optimization will run much faster, but i cant get my head around why does not produce expected results. I thought that this line was causing to skip some objects

 if (circles.get(i).growing) {

as its skips objects that are not growing, so i change it to

  if (true) {

and same ugly results.

Thanks a lot, I am running a 4000x3500 with 30000 objects and takes a few minutes to finish is not so bad. I want to make a print so its fine.

Thanks a lot!!

Kind Regards

koogs

I thought that this line was causing to skip some objects

ha, i thought exactly the same thing, couldn't easily fix it though.

that line means that something that isn't growing won't be checked (and won't grow any more), but things that are growing WILL be checked against all the non-growing things. i think this is correct.