Concave polygons not working as expected

[Codezilluh]

I am having some trouble with concave polygons. The collisions were not being detected with my concave polygon, so I did a little bit of testing with a different concave polygon. It should be noted that I am checking the polygon collider against a circle collider with a radius of 1.

This is the concave polygon I tested with:

[
    { x: -13.25, y: -7.51 },
    { x: -13.25, y: 7.51 },
    { x: 0.77, y: 7.51 },
    { x: -3, y: 0.41 },
    { x: 0.77, y: -7.51 }
]

which creates a polygon that looks like this:

the collisions work as expected on the right side, but on the left edge it does not. My character is able to pass through the left edge.

removing the concavity creates a perfectly functional collider

[
    { x: -13.25, y: -7.51 },
    { x: -13.25, y: 7.51 },
    { x: 0.77, y: 7.51 },
    // { x: -3, y: 0.41 },
    { x: 0.77, y: -7.51 }
]

my original collider, which did not work at all, was this:

[
    { x: -11.25, y: -6.76 },
    { x: -12.5, y: -6.76 },
    { x: -12.5, y: 6.75 },
    { x: -3.1, y: 6.75 },
    { x: -3.1, y: 0.41 },
    { x: -2.35, y: 0.41 },
    { x: -2.35, y: 6.75 },
    { x: 0.77, y: 6.75 },
    { x: 0.77, y: 7.5 },
    { x: -13.25, y: 7.5 },
    { x: -13.25, y: -7.51 },
    { x: -11.25, y: -7.51 }
]

I don't know if this is related, but the length of body.convexPolygons and the length of body.getConvex() do not match. With the former being over double the length of the latter.

[Prozi]

I will look into it thank you for reporting!

[Prozi]

glad to report that I fixed it in v6.3.6 it was an overlook

I also updated the CI tests to add this case and even added the polygon to the demo (tank is now a circle) :)

https://prozi.github.io/detect-collisions/demo/

[Prozi]

glad to report that I fixed it in v6.3.6 it was an overlook

I also updated the CI tests to add this case and even added the polygon to the demo (tank is now a circle) :)

https://prozi.github.io/detect-collisions/demo/

Actually v6.3.7 found one case I fixed (the response was not pointing to correct original body)

[Codezilluh]

Cool, now it appears the polygons are being generated properly. There might be a bug with actual collision resolution (the overlaps), I haven't look into it much yet. This is the issue I am facing now: when heading into perpendicular walls (haven't tested other angles), you can pass through one of the walls.

hitting only one wall seems to work perfectly though.

[Prozi]

Cool, now it appears the polygons are being generated properly.

Yes I fixed the convexPolygons array length to be === this.getConvex().length

also fixed collision resolution between circles and concaves

There might be a bug with actual collision resolution (the overlaps), I haven't look into it much yet. This is the issue I am facing now: when heading into perpendicular walls (haven't tested other angles), you can pass through one of the walls.

I propably have to add all vectors from all polygons, will look into it soon maybe at the weekend or today depending on how complex it is

[Prozi]

@Codezilluh please try v6.3.8 I added those vectors since it was relatively simple, all tests still pass and in the demo I dont have such behaviour [no more]

[Codezilluh]

It's doing something that's for sure. But I can still pass through corners. I've started outputting the overlap vector and it appears to be much smaller when hitting two edges.

I'm expecting this (player speed is 0.16):

{
   x: -0.16,
   y: 0.16
}

but getting something like this:

{
    x: -0.0173....,
    y: 0.0893....
}

I'll start fiddling around to see if I can diagnose this.

[Codezilluh]

I've ben inspecting collisionVectors. When the collision with two edges begins, you see things like this:

[
    Vector { x: -0.0005755722403617074, y: 0.0029699527602664103 },
    Vector { x: 0.0005755722403617074, y: -0.0029699527602664103 }
]

which would create a the vector (0, 0) when added. And sometimes things like this:

[
    Vector { x: -0.013692434518099553, y: 0.13121788758179298 },
    Vector { x: 0.013692434518099553, y: -0.13121788758179298 },
    Vector { x: -0.013692434518099553, y: 0.13121788758179298 }
]

even though I am pretty sure I am only colliding with two edges.

[Codezilluh]

Alright, I fixed it

You need to do this.response.clear(); in the reduces

Should I create a pull request?

[Prozi]

Alright, I fixed it

You need to do this.response.clear(); in the reduces

Should I create a pull request?

Nice find!

I thought about also skipping the vector clone stuff so I will put that in myself

just instead of reusing this.response and clearing it I will reinstantiate response and use its vector that way I dont have to clear, since recreating clears it, and I dont have to clone its vector so, neat

[Prozi]

just instead of reusing this.response and clearing it I will reinstantiate response and use its vector that way I dont have to clear, since recreating clears it, and I dont have to clone its vector so, neat

On the other hand this might not work so good

I thought about one case what about concave polygons aInB and bInA in response...

Alright, I fixed it

You need to do this.response.clear(); in the reduces

Should I create a pull request?

Please do! :)

Just run npm run/yarn precommit before commit

thank you!!

[Prozi]

just instead of reusing this.response and clearing it I will reinstantiate response and use its vector that way I dont have to clear, since recreating clears it, and I dont have to clone its vector so, neat

On the other hand this might not work so good

I thought about one case what about concave polygons aInB and bInA in response...

Alright, I fixed it You need to do this.response.clear(); in the reduces Should I create a pull request?

Please do! :)

Just run npm run/yarn precommit before commit

thank you!!

I imagine with the current code you'll do something like

    const handleCollision = (collides: boolean) => {
      if (collides) {
        if (typeof collisionVector === "undefined") {
          collisionVector = new SATVector();
        }

        collisionVector.add(this.response.overlapV);
        collisions++;
      }

      this.response.clear();
    };

[Prozi]

even better would be moving this to a private system function for further optimisation not to create function each checkCollision

[Prozi]

ok I did all of that @Codezilluh

can you check v6.3.10 ?

also...

do you have any suggestions as how to solve aInB and bInA for concave polygons ?

[Codezilluh]

can you check v6.3.10 ?

Works flawlessly! (as far as I can tell, and I am using pretty complex polygons)

do you have any suggestions as how to solve aInB and bInA for concave polygons ?

I'll have to look into how it is handled for normal polygons. It's tough because simply looping and comparing the polygons will not work for most cases. Maybe something fancy could be done with the points? It may end up being better just to use the AABB for that. I am not sure if aInB or bInA would even be useful for concave polygons that are not the same, as the collision system should be able to take care of it (haven't actually tried). I am currently just using aInB to see if I need to nudge the object in a random direction.

[Prozi]

can you check v6.3.10 ?

Works flawlessly! (as far as I can tell, and I am using pretty complex polygons)

I am happy

Thank you for finding all those bugs and finding a solution

do you have any suggestions as how to solve aInB and bInA for concave polygons ?

I'll have to look into how it is handled for normal polygons. It's tough because simply looping and comparing the polygons will not work for most cases. Maybe something fancy could be done with the points? It may end up being better just to use the AABB for that. I am not sure if aInB or bInA would even be useful for concave polygons that are not the same, as the collision system should be able to take care of it (haven't actually tried). I am currently just using aInB to see if I need to nudge the object in a random direction.

I was also thinking about simple aInB and bInA with AABB it's still better than nothing and currently we have close to nothing (in case of aInB or bInA) if one is concave I'm also a bit sorry I kind of took you the opportunity to contribute so how about you open a merge request with this change if you feel you want to...

best regards

[Prozi]

I merged your MR it was great thank you!

I also saw your commend about wrong aInB and bInA for non convex and I've added 1 test for the case and

assured that even outside that if (collisionVector) { block, your util function is used for non convex polygons

in the cases where there is no concave polygon involded those overwrites wont be involved

still theres that response clear so in near future I'll try to add some more tests.

cheers!

[Prozi]

hello I think I fixed that case with convex polygons having aInB and bInA screwed up after testing with concave collisions in this.collided() and this.response.reset() so I kept the state of bodies aInB and bInA, and restore them only to convexes that had to do with concaves.

https://github.com/Prozi/detect-collisions/blob/master/src/system.ts#L281-L283

https://github.com/Prozi/detect-collisions/blob/master/src/system.ts#L218-L227

https://github.com/Prozi/detect-collisions/blob/master/src/system.spec.js#L134-L198

try v6.3.13 @Codezilluh best regards

[Codezilluh]

try v6.3.13 @Codezilluh best regards

Ok, I'll try it out right now. Sounds solid.

[Codezilluh]

Played around with it, found no problems.

[kade-robertson]

This appears to still be broken in some instances. Here's an example scenario where both lines when colliding with a concave polygon should have aInB set to false, but it's set to true: https://codesandbox.io/s/nifty-buck-t5knk0

[Codezilluh]

This appears to still be broken in some instances. Here's an example scenario where both lines when colliding with a concave polygon should have aInB set to false, but it's set to true: https://codesandbox.io/s/nifty-buck-t5knk0

Yes, this is a known issue. It is because aInB for polygons just uses the bounding box. At the moment, this is the best solution we have.

You can check out an image I made displaying this pitfall in #34

[kade-robertson]

Yes, this is a known issue. It is because aInB for concave polygons just uses the bounding box. At the moment, this is the best solution we have.

You can check out an image I made displaying this pitfall in #34

The theory was that having something is better than having nothing (there previously was no aInB for the polygons)

Ah alright, thanks for the clarification!

[Prozi]

you're right @kade-robertson and what @Codezilluh wrote is also true

I will add some remark to readme about this and then close the issue as I personally don't plan to fix it currently due to optimization reasons mostly, maybe if someone suggests a proper mr with a change that isn't too slow I might just add it but the chance is slight as I believe such alghoritm would be relatively complex

[Prozi]

I added the information to readme -> https://github.com/Prozi/detect-collisions#concave-polygons

closing the issue as aInB and bInA for non-convex will stay this way until some good merge request appears with how to calculate them, and passes the benchmarks positively