Fix the Rect Version of RigidBody.PickShapesGlobal

[ilexp]

The current implementation of RigidBody.PickShapes is hacky at best and doesn't work properly.

• Write a unit test that proves the implementation doesn't work in all cases.
• Implement a version that works, and (ideally) does so faster.

[adambiltcliffe]

Test project demonstrating errors in the implementation: PickShapesBugDemo.zip

[Barsonax]

I will take a look at this, since the last comment is over a year ago I guess this one is free to pick up.

[ilexp]

It is! Good luck 👍

[Barsonax]

I have reproduced a situation in a unit test. I do not understand RigidBody.PickShapes but seeing as you call the current implementation hacky I guess that kind of makes sense.

From what I understand is that PickShapesGlobal first finds rigidbodies that could potentially be in the rectangle but then it still has to weed out the false positives which it does with PickShapes. All PickShapes has to do is check each shape in the rigidbody and see if it is in the rectangle or not. So first you would have to check what kind of shape it is and then do the check for that type.

This could be achieved by adding a abstract contains method to ShapeInfo which the shapes have to implement. A alternative could be with casting but I dont like that.

[ilexp]

From what I understand is that PickShapesGlobal first finds rigidbodies that could potentially be in the rectangle but then it still has to weed out the false positives which it does with PickShapes. All PickShapes has to do is check each shape in the rigidbody and see if it is in the rectangle or not.

Correct.

So first you would have to check what kind of shape it is and then do the check for that type.

This could be achieved by adding a abstract contains method to ShapeInfo which the shapes have to implement. A alternative could be with casting but I dont like that.

That would be a solution, but Farseer already should have logic for this and I'd prefer to use that instead of rolling our own. Maybe investigate where that logic exists and see how it can be used in that case first. Writing it from scratch shouldn't be the first approach.

[Barsonax]

Ok I will check that out.

I will keep the abstract method on ShapeInfo though and put the farseer code in there, if this is possible.

[Barsonax]

Found intersection tests in collision.cs, starting at line 761. These methods return the contact points in a Manifold struct I believe so these could be used to implement the checks.

So in order to implement this by using the farseer library I would have to cast the this.body.FixtureList[i].Shape to the correct shape and call the appropriate farseer method for that shape. Since those methods expect 2 farseer shapes I would have to convert the rectangle to a polygonshape before the for loop. No need for a abstract method on ShapeInfo either.

So for the circle for instance it would go broadly like this:
-convert the worldCoord and size arguments to a PolygonShape representing this rectangle.
-start looping through the this.body.FixtureList
-as cast the this.body.FixtureList[i].Shape to a CircleShape, if not null proceed
-call the CollidePolygonAndCircle(arguments here) method
-check the Manifold (which is passed as a ref argument to the above method) for the contact points, if so add this ShapeInfo to the pickedShapes
-skip other checks and process the next shape until none are left

However since we are checking against a polygon and not a AABB this is probably not the fastest implementation. It will get the job done though.

[ilexp]

Found intersection tests in collision.cs, starting at line 761. These methods return the contact points in a Manifold struct I believe so these could be used to implement the checks.

For discussion convenience, here's a link to the line in question.

Looking good! Where are those methods called? Perhaps there is a shape base class version somewhere that also checks which shapes are checked? Could make your job a little easier and make the manual cast-to-appropriate-type redundant. Otherwise, manually checking should be fine too.

-as cast the this.body.FixtureList[i].Shape to a CircleShape, if not null proceed

I'm assuming that you'll also check the polygon shape, but one thing that might be forgotten is the chain shape, which can be deconstructed into individual edge shapes (re-use the same temp one if possible), which can then be checked as well. Priority are circles and polygons though.

However since we are checking against a polygon and not a AABB this is probably not the fastest implementation. It will get the job done though.

Pretty sure it will be faster than the current implementation, which I think is doing hundreds of point checks 😄 To be extra sure, can you do a perf check in Release mode (Rebuild Solution when switching!) with a few thousand (or whatever it takes) rect-based pick shapes calls, before and after your change?

[Barsonax]

I have checked and those collision methods starting in Collision.cs have 0 references

EDIT: ignore this as this was caused by a failing build.

[ilexp]

I have checked and those collision methods starting in Collision.cs have 0 references

Wait.. if Farseer doesn't use them, how does it check for collisions then?

[Barsonax]

Hmm might be false since I get a error on compiling the farseer solution. It seems it cannot restore nuget packages since package restore is disabled by default (its not when I look in the options??).

EDIT: Had to edit the csproj to fix this. Do you have a problem when trying to rebuild? Found where its called: Contact.cs. Unfortunately this method is private.

[Barsonax]

If this method would not be internal it could be used to create a contact:
Contact.cs

Then you would have to make this method public to evaluate the collision:
Contact.cs

Your call I guess.

[ilexp]

Hmm, Contact and its implementation look like they're intended for a different purpose, i.e. managing existing contacts rather than checking if a new one exists. Would probably go with the manual check like you initially suggested then.

[Barsonax]

Implemented the IntersectsWith methods on all shapes and added tests for this. Need to do more testing though and possibly some cleanup.

Also added a Box class which holds all the points and the size of the box. This box is instantiated in PickShapes and passed on to the IntersectsWith method so all needed info is available without having to calculate those per shape.

The old PickShapes method is currently still there but renamed since I want to compare the performance later on.

[ilexp]

Sounds good! Looking forward to your PR as soon as you're ready 👍

[Barsonax]

Tested the new code inside a duality instance and everything seems to be working now (moving rigidbodies around etc.). I did saw that if the game is playing and you change the scale of the transform QueryRectGlobal does not pick this up but that's a different issue I think.

Also compared the performance and the new version is actually slower currently. It varies but I have seen cases where its twice as slow. Ill see if I can get it faster.

EDIT: after looking through the old implementation it seems to be doing only collisions between the AABB's? No wonder its faster.

[ilexp]

Continued discussion in PR #291.

[Barsonax]

Performance test results:
-For CircleShapes the new Pickshapes is quite alot faster
-For Chain and loop shapes its quite alot slower
-For polygons its rougly the same speed

However the old method cheats since its not finding all shapes so this is not really a fair comparison. It does not find any chain or loop shapes for instance and skips some of the polygons. If you take this into account the new method is faster in almost all cases.

I suspect you could get quite a nice performance boost if it was cheaper to transform points to world or local coordinates as I have to do this for every vertice.

[ilexp]

Progress

• A fix was implemented by @Barsonax in PR #291 Fixing Pickshapes using farseer #579.

Immediate ToDo

• As before the change, PickShapes currently does not pick up chain- and loop shapes even in area / rect overloads. Either clarify that this should be by design to reflect point-based overload behavior, or extend its implementation to do so.

[Barsonax]

I tried implementing the chain and loop pickshape implementation but I did not succeed. It did detect collisions but not in the right spot. Need to research this more to understand why this happened. Its probably just a bug in my code though but if this turns out to be unsolvable we could always use my own implementation.

[Barsonax]

Box2D doesn't seem to support chain and loop shape collision so I think we will have to roll our own solution here. Farseer probably implemented a quick and dirty check to support this.