We are about to switch to a new forum software. Until then we have removed the registration on this forum.
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
Answers
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)
.Move this outside the double loop, instantiate them there.
Inside the loop use set() rather than new()
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.
How are you calling isIntersectingWith?
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):
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!!
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
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?)
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)
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
as its skips objects that are not growing, so i change it to
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
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.