Farseer Raycast Issue - Missing Collisions

Topics: Developer Forum
Aug 18, 2012 at 3:10 PM
Edited Aug 18, 2012 at 3:39 PM

Hello everyone,

This is my first post here, I have an issue using Farseer's Raycast method.

Firstly, Farseer is brilliant, and hats off the the creators

The Raycast occasionally misses shapes, either returning a collision at the wrong edge or occasionally colliding with another shape. (All shapes are polygon types on static bodies)

I have studied the following fix, and related links to solve this. They have not worked

I have tried:

* Modifying the MaxFraction part of the RayCast as per the fix

* Returned -1, stored all the collision points, checked and returned the closest collision point

http://farseerphysics.codeplex.com/discussions/265543

Here is a video of a test ray showing the issue. Please excuse the frame rate / quality, I just used any old screen capture application I could find.

http://www.youtube.com/watch?v=qqdl4Q4OgMg

I have noticed that there is never an issue with a ray check between 0 and 45 degrees (clockwise) from the horizontal in the forward (left to right) direction.

At the start you can (sort of ) see the ammended raycast code as per the fix below.

Unfortuantely the threads on this issue seemed to have died (I suppose the fix worked for most). Can anyone help? I'll even throw in $25 on paypal for a solution!!

Thanks

Aug 18, 2012 at 7:07 PM

Do you mind posting up the code raycast on pastebin?

 

 

Here is something you might want to look out for:

The polygons must be created in counterclockwise order. Or clockwise order, I forgot which one.  To test for this, rotate the static body rotation.

Using the "Force Clockwise" doesn't always work. All it does is reverse points. If you need a force clockwise function, I would be happy to supply mine.

Aug 18, 2012 at 9:51 PM

Hi Fnorder,

Thanks for your response. Regarding the vertices ordering, that's a great point. The level editor creates the collision polygons using marching square algorithm and I used the Force Clockwise method on the polygons before storing them in xml. I remember looking at it and thinking "that surely doesn't work", but left it.

I will have a stab at writing a quick ordering method. I guess you find the average x,y vertex position for the centre (or use GetCentroid or whatever it is) and look at the angle the vectors out to the vertices are, and ordering them that way. Having said that, I'd appreciate using yours!! :)

If it turns out to be the ordering, you're in for the $25 :)

I don't use paste bin, but will put the test code i've been using below. There are two ray cast approaches switched by the manualsortcast bool, one looks for shortest of all points returned and the second uses just the first contact. well that's the idea anyway.

 

            Vector2 v2_collision_point = Vector2.Zero; //This is the final position we get out the end - where the ray ends. If no contact then is at max length
            Vector2 v2_point1 = world.ConvertToSimulation(ref      Transform.v2_WorldPosition);
            Vector2 v2_delta = Vector2.UnitX;
            v2_delta = Vector2.Transform(v2_delta,                 Matrix.CreateRotationZ(f_RayAngle));
            v2_delta *= world.ConvertToSimulation(ref f_RayLength_World);
            Vector2 v2_point2 = v2_point1 + v2_delta;

            bool b_hitclosest = false;

            //Dirty - Store all points in Vector list then look for shortest
            if (b_UseManualSortCast)
            {
                List<Vector2> HitPoints = new List<Vector2>();
                world.RayCast((f, p, n, fr) =>
                {
                    Body body = f.Body;
                    if (body.UserData != null)
                    {
                        int index = (int)body.UserData;
                        /* //Doesn't seem to do anything for me, commented or not
                        if (index == 0)
                        {
                            // filter
                            return -1.0f;
                        }
                         */ 
                    }

                    b_hitclosest = true;
                    HitPoints.Add(p);
                    return -1;

                }, v2_point1, v2_point2);

                if (b_hitclosest)
                {
                    //Quick find shortest method. dirt code
                    Vector2 v2_shortest = HitPoints[0];
                    float f_shortest_length_squared = HitPoints[0].LengthSquared();
                    int n = HitPoints.Count;
                    for (int k = 1; k < n; k++)
                    {
                        float f_l =HitPoints[k].LengthSquared();
                        if (f_l < f_shortest_length_squared)
                        {
                            f_shortest_length_squared = f_l;
                            v2_shortest = HitPoints[k];
                        }
                    }
                    v2_collision_point = v2_shortest;
                }
            }
            else
            {
//Normal closest point test
    world.RayCast((f, p, n, fr) =>
                        {
                            Body body = f.Body;
                            if (body.UserData != null)
                            {
                                int index = (int)body.UserData;
                                /* //Again, seem to have no effect commented or not
                                if (index == 0)
                                {
                                    // filter
                                    return -1.0f;
                                }
                                 */ 
                            }

                            b_hitclosest = true;
                            v2_collision_point = p;
                            return 0;

                        }, v2_point1, v2_point2);
                }
            }

            if (!b_hitclosest)
            {
               //If we don't hit anything, just the end point at the end of ray
                v2_collision_point = v2_point1 + v2_delta;
            }

}

Aug 18, 2012 at 10:24 PM

I just tried implementing the following algorithm, sourced from this

http://stackoverflow.com/questions/1165647/how-to-determine-if-a-list-of-polygon-points-are-in-clockwise-order

"Sum over the edges, (x2-x1)(y2+y1). If the result is positive the curve is clockwise, if it's negative the curve is counter-clockwise. (The result is twice the enclosed area, with a +/- convention.)"

 

  public static void ForceCounterClockwise(Vertices verts)
        {
            float f_edgeSum = 0.0f;
            int i_numVerts = verts.Count;
            for (int v = 0; v < i_numVerts; v++)
            {
                if (v < i_numVerts - 1)
                    f_edgeSum += (verts[v + 1].X - verts[v].X) * (verts[v + 1].Y + verts[v].Y);
                else
                    f_edgeSum += (verts[0].X - verts[v].X) * (verts[0].Y + verts[v].Y);
            }

            if (f_edgeSum <= 0.0f)
                return;

            //Reverse ordering
            Vertices copy = new Vertices(i_numVerts);
            for (int v = 0; v < i_numVerts; v++)
                copy[v] = verts[v];
            for (int v = 0; v < i_numVerts; v++)
                verts[v] = copy[i_numVerts - 1 - v];
        }

It runs, but never returns a positive number, so with that do you think I can assume my polygons are counterclockwise?

As nothing gets reordered, there is no change in effect

Ah, stumped. For good measure, here is the modified raycast method in farseer, reflecting the change found in that link in the OP.

 

        public void RayCast(RayCastCallback callback, Vector2 point1, Vector2 point2)
        {
            RayCastInput input = new RayCastInput();
            input.MaxFraction = 1.0f;
            input.Point1 = point1;
            input.Point2 = point2;

            ContactManager.BroadPhase.RayCast((rayCastInput, proxyId) =>
            {
                FixtureProxy proxy = ContactManager.BroadPhase.GetProxy(proxyId);
                Fixture fixture = proxy.Fixture;
                int index = proxy.ChildIndex;
                RayCastOutput output;
                bool hit = fixture.RayCast(out output, ref rayCastInput, index);

                if (hit)
                {
                    float fraction = output.Fraction;
                    Vector2 point = (1.0f - fraction) * input.Point1 +
                                    fraction * input.Point2;
                    return callback(fixture, point, output.Normal, fraction);
                }

                //return input.MaxFraction;
                return rayCastInput.MaxFraction; //THIS IS THE CHANGE HERE
            }, ref input);
        }

Aug 19, 2012 at 1:38 AM
Edited Aug 19, 2012 at 1:47 AM

$25 dollars isn't necessary. I do have a little hobby of collecting postcards though if you want to :)

 

Farseer's ForceClockwise does two things:

1) Checks to see if it's clockwise

2) Reverses order if it isn't

It does not check for things like, "polygons" with intersecting lines, which was what I thought was happening at the time. Now that I think of it, your video makes that point unlikely.  You would be OK with using Farseer's ForceClockwise function.  I would just do a bit of simple tests to make sure.

Something about this is bugging me:

 

                          Body body = f.Body;
                            if (body.UserData != null)
                            {
                                int index = (int)body.UserData;
                                /* //Again, seem to have no effect commented or not
                                if (index == 0)
                                {
                                    // filter
                                    return -1.0f;
                                }
                                 */ 
                            }

                            b_hitclosest = true;
                            v2_collision_point = p;
                            return 0;


I will go home to compare it with my working Raycast code tonight. Haven't touched it in a while.

What does "Body.UserData==0" represent?
return 0, if I remember, terminates the raycast. It just pretends it never happens. -1 I think is what you're looking for.

Try returning fr, 0f (a float, and therefore a fraction), and 1f. If you return fr, you return the spot where the collision happens. Eg.  If you raycast from P1 to P2, and there's a collision X1 halfway, if you decide to Console.Writeline(fr);, it will display .5f.  


        /// Inside the callback:
        /// return -1: ignore this fixture and continue
        /// return 0: terminate the ray cast
        /// return fraction: clip the ray to this point
        /// return 1: don't clip the ray and continue

Fractions are floats, typically between 0 and 1 (0% and 100% range, between the two points). return -1f is a float. return -1 is not a float.

Aug 19, 2012 at 1:03 PM
Edited Aug 19, 2012 at 1:07 PM

Hehe, sure a postcard sounds interesting. Would be a London one though (where I live).

So, I sort of blindly used the code from the Test bed, and you are right, that Body.UserData isn't being used.

I've changed to check for the fixture's collision category, only accepting those that hit with the "static level"

It has not helped, but I tested the code and the filtering is working correctly.

I also use the p in callback as the point of collision, so returning fr would just clip v2_point2 to collision point?

I also Tried changing the return values from integer to floating point, across 0, 1 and -1, still the same effect :( 

 

           Vector2 v2_collision_point = Vector2.Zero;
            Vector2 v2_point1 = world.ConvertToSimulation(ref Transform.v2_WorldPosition);
            Vector2 v2_delta = Vector2.UnitX;
            v2_delta = Vector2.Transform(v2_delta, Matrix.CreateRotationZ(f_RayAngle));
            v2_delta *= world.ConvertToSimulation(ref f_RayLength_World);
            Vector2 v2_point2 = v2_point1 + v2_delta;

            bool b_hitclosest = false;

            if (b_UseManualSortCast) //FIND ALL COLLISION POINTS THEN FIND CLOSEST
            {
                List<Vector2> HitPoints = new List<Vector2>();
                world.RayCast((f, p, n, fr) =>
                {
                    if (f.CollisionCategories == lyr_Game.Category_StaticLevel)
                    {
                        b_hitclosest = true;
                        HitPoints.Add(p);
                    }
                    return -1; //Ignore and continue so picks up each collision point and adds to list to later sort

                }, v2_point1, v2_point2);

                if (b_hitclosest)
                {
                    Vector2 v2_shortest = HitPoints[0];
                    float f_shortest_length_squared = HitPoints[0].LengthSquared();
                    int n = HitPoints.Count;
                    for (int k = 1; k < n; k++)
                    {
                        float f_l =HitPoints[k].LengthSquared();
                        if (f_l < f_shortest_length_squared)
                        {
                            f_shortest_length_squared = f_l;
                            v2_shortest = HitPoints[k];
                        }
                    }
                    v2_collision_point = v2_shortest;
                }
            }
            else  //FIND FIRST VALID COLLISION POINT AND DEEM CLOSEST
{ world.RayCast((f, p, n, fr) => { if (f.CollisionCategories == lyr_Game.Category_StaticLevel) { b_hitclosest = true; v2_collision_point = p; return 0; //Found nearest (first?) fixture so end and return } return -1; //Collided with something not in the static level collision group, so just ignore and continue }, v2_point1, v2_point2); }

This is driving me crazy!

Thanks again for your help with this.

Aug 19, 2012 at 8:42 PM
Edited Aug 19, 2012 at 8:43 PM

NP! I'm happy to help :)

Alright, first for comparison, what my raycasting looks like (kindof). It's from memory, so I know it's not 100% correct. I post this for the secondary reason of showing the idea behind Body.UserData:

Vector2 _p; //a copy of collisionpoint p

Vector2 _n; //a copy of normal n. I do the same with fraction and fixture

World.RayCast(
                                (f, p, n, fr) =>
                                {

                                    _p=p; _n=n;  //I save the values  

                                    if (f.Body.UserData==this) return -1; //I don't want the laser hitting myself. My UserData are of type GameObject.

                                    if (f.Body.UserData is Destructible) (f.Body.UserData as Destructible).HP-=1;          

                                    return fr;                     

                                },
                               start, end);

DebugDraw.Drawline( start, _p);   //always draws a line from beginning to closest collision

 

You'll notice that it's more or less the same code as your final Raycast.  From this, I can assume you have manual sort=true.

 

 

1) Now, this is where there is a definite bug:

 Let's say your guy is at  8,0. There is a collision at 9,0. Expected distance is 1.

HOWEVER, HitPoints[k].LengthSquared(); is equal to 81.  That is because it compares distance from Collision to Vector2.Zero.

Here is what you want:

(Hitpoints[k]-v2_point1).LengthSquares();

 

2)

LengthSquared() is unnecessary. You probably want to use Length(). Length() returns a positive float distance. 

 

3)

Sorting is unneccessary. Raycasting collides in order [see my code]

 

 

I recommend fixing #1, and probably even setting ManualSort=false. Let me know about the results!

 

 

Aug 19, 2012 at 10:36 PM
Edited Aug 19, 2012 at 10:37 PM

Hello, thanks again for the reply!

1. Yes! How silly, I'm measuring the distance from the origin rather than versus the source of the ray :) Thanks for spotting. I am away from my dev PC for another 24 hours :( so do not have time to test. I have a horrible feeling I am actually using manualcast false at the moment, but fingers crossed as that would solve it hopefully.

2. I will try the change. I use lengthsquared() as habit to save the square root and should still be an OK length test, but computers are fast enough these days :)

3. This is what I had thought, but when I got back collision points on the other side of the shape, it made me want to check

I will report back in around 24 hours :)

Aug 26, 2012 at 12:59 PM

Hi Fnorder. Sorry it has taken me some time to reply. I as away from home, and then tied up for a few days. Sad news I am afraid. I fixed the length squared issue and it had no effect. For manual sort = false, I returned fr, and there has been no effect. I cannot work out why the raycast is not working

1. All Polygons are winded anti-clockwise

2. I have tried manually finding the shortest of all ray cast points found

3. I have tried returning the first found point, using all filters from fraction fr to 0.0f to end raycast, -1 to ignore and continue, etc

 

I rewrote a bit of code, and this is currently the piece that displays exactly the same behaviour problem that I have had throughout. Any ideas? Im stumped

                    //Caculate the end of ray position delta
                    Vector2 v2_RayDelta = v2_Unit * f_current_length; //Take the direction of the ray cast unit vector and find end point in that direction
                    //Ray Cast
                    Vector2 v2_start = body.Position; //Store the source of the ray cast
                    Vector2 v2_end = body.Position + v2_RayDelta; //Mark the end point of the ray cast
                    Vector2 v2_hit_point = Vector2.Zero; //Will store the ray cast collision point here
                    bool b_ray_collides = false; //A boolean I use to tell me if we had a collision that was with a fixture of the right collision category or not
                    world.RayCast((f, p, n, fr) =>
                        {
                            if (f.CollisionCategories == collisionCat) //If the fixture hit is of the right type of level collision category
                            {
                                b_ray_collides = true; //set my bool
                                v2_hit_point = p; //store the point
                                return fr; //End the ray (I used to return 0.0f / 0 to end ray and continue, now i am trimming ray, but this shouldnt matter as I dont use the return?
                            }
                            else
                                return -1; //Ignore and Continue (wrong collision category, continue ray cast)
                        }, v2_start, v2_end);

                    if (b_ray_collides) //If we have a hit
                    {
                        //We Hit the level and the point is stored in v2_hit_point. Use it!
                    }

 

Aug 26, 2012 at 1:40 PM

a shameless bump because I started posting in other discussions :P

Aug 26, 2012 at 8:17 PM
Edited Aug 26, 2012 at 8:27 PM

Use f.CollisionCategories.HasFlag(collisionCat). Hopefully it works

 

If that doesn't work, I'd start doing sanity checks, throwing exceptions to make sure its enterring.

eg:

    if (f.CollisionCategories.HasFlag(collisionCat) //If the fixture hit is of the right type of level collision category
                            {
                                b_ray_collides = true; //set my bool
                                v2_hit_point = p; //store the point
                                return fr; //End the ray (I used to return 0.0f / 0 to end ray and continue, now i am trimming ray, but this shouldnt matter as I dont use the return?
                            }
                            else
{
DebugDraw.DrawText(p,collisionCat);
//or, if you dont have debug tools that do that
if (KeyPress.F1) throw new exception(collisionCat);
//note: if you dont want to pass Input everywhere, make it static. for release, you can change it back

 return -1; //Ignore and Continue (wrong collision category, continue

}

Coordinator
Aug 27, 2012 at 11:44 PM

Writing here to make sure that you got my mail. I'll also quickly write what I wrote in the mail:

I think the problem lies in the assumptions. What you need to do, is to always return the fraction, and only in the special case of filtering, filter the fixtures.
That way, the rays will always clip at the intersection point between the polygon and the ray - and only in the special case; filter out the collision.

The reason is that there are multiple cases and you try to only handle one of them (the filtering case). But retuning the fraction all the time will make the ray work correctly all the time, and in the case of filtering, it will work as well.

Aug 28, 2012 at 6:29 PM

Thanks again Fnorder.

Any many thanks for your reply GenBox.

I am again away from my dev PC (in fact, the parts are coming for the new i7 rig tomorrow morning :). Ill check this out tomorrow and come back!

Sep 8, 2012 at 4:15 PM

I now always return the fraction. It is better, but not perfect. I need some time to ensure that the less frequent problems of rays passing through objects are not down to other parts of my code.

Sorry for the delay in coming back, have been busy with annoying life things.

Think am on the right track!

Fnorder ill need your address somehow if you want a post card. GenBox thanks for the link.

Coordinator
Sep 8, 2012 at 7:06 PM

You should also take a look at this:

https://farseerphysics.codeplex.com/discussions/265543

Sep 8, 2012 at 7:29 PM

I had seen that, and made the change :) Thanks for the link in any case!!