Bad raycasting performance :(

[Alan-FGR]

Hi there.

Since I'm using this library for the physics in my game, I decided to also use it for 2d light raycasting, however, I'm having some really bad performance, I don't need anything too fancy, and it's a pixel art game, but I'd like to have at least 15+ lights on screen running @ 60fps, but I get lower framerates with much less lights I am getting the closest shapes using QueryAABB and then I get the shapes vertices and fire 3 rays for each of them. I've profiled it and apparently the problem parts are Vector2 subtractions, and PolygonShape.get_Normals (what's very odd because after a quick look at the code it just seems to return cached stuff), and also some other operations like Dot product, I wonder if the fact I'm using FNA has something to do with that, maybe the math isn't as fast as in XNA? Anyway, I'm planning to MT the raycaster since it's not critical for gameplay so we can safely drop some frames and have it lag behind the other stuff, but even though, I don't think the performance is OK, maybe there's a gotcha or something, here's the code I'm using:

//get colliders in range
AABB rect = new AABB(entity.Position, size_*2f-(2+SHADOW_BIAS), size_*2f-(2+SHADOW_BIAS));
List<Fixture> cols = Sz.physWorld.QueryAABB(ref rect);

// build list of points in radius to add to the perimeter
List<Vector2> radiusPoints = new List<Vector2>();
foreach (Fixture col in cols)
{
    PolygonShape shape = col.Shape as PolygonShape;

    // skip the light emitter
    if((col.Body.UserData as Component).entity == entity) continue;

    //cast one ray for each vertex of shapes in range
    foreach (Vector2 v in shape.Vertices)
    {
        var worldPoint = col.Body.GetWorldPoint(v);

        Vector2 rayDirection = worldPoint-center;
        Quadrant quadrant = rayDirection.GetQuadrant();

        //get offset for auxiliary rays (fast)
        Vector2 auxOffset = new Vector2(-1,1);
        if (quadrant == Quadrant.TR) auxOffset = new Vector2(1, -1);
        else if (quadrant == Quadrant.TL) auxOffset = Vector2.One;
        else if (quadrant == Quadrant.BR) auxOffset = -Vector2.One;

        var hit = Sz.physWorld.RayCastSingle(center, worldPoint);

        float distMult = (center-hit.Value).Length();
        Vector2 normalizedDirection = Vector2.Normalize(rayDirection);

        float auxOffsetAmount = distMult*0.001f;
        Vector2 longRay = center+normalizedDirection*size_*1.4f; //ray besides points

        var auxA = Sz.physWorld.RayCastSingle(center, longRay+auxOffset*auxOffsetAmount);
        var auxB = Sz.physWorld.RayCastSingle(center, longRay-auxOffset*auxOffsetAmount);

        //if we hit something, propagate light a tad bit
        radiusPoints.Add(hit.Value+normalizedDirection *SHADOW_BIAS);
        radiusPoints.Add(auxA.Value+normalizedDirection*SHADOW_BIAS);
        radiusPoints.Add(auxB.Value+normalizedDirection*SHADOW_BIAS);
    }
}

//cast one ray for each corner of the quad
radiusPoints.Add(Sz.physWorld.RayCastSingle(center, center+Vector2.One*      size_).Value+Vector2.One*0.71f*SHADOW_BIAS);
radiusPoints.Add(Sz.physWorld.RayCastSingle(center, center-Vector2.One*      size_).Value-Vector2.One*0.71f*SHADOW_BIAS);
radiusPoints.Add(Sz.physWorld.RayCastSingle(center, center+new Vector2(-1,1)*size_).Value+new Vector2(-1,1)*0.71f*SHADOW_BIAS);
radiusPoints.Add(Sz.physWorld.RayCastSingle(center, center+new Vector2(1,-1)*size_).Value+new Vector2(1,-1)*0.71f*SHADOW_BIAS);     

Extension method:

    public static KeyValuePair<Fixture, Vector2> RayCastSingle(this World w, Vector2 point1, Vector2 point2)
    {
        Fixture fixture = null;
        Vector2 point = point2;

        w.RayCast((f, p, n, fr) =>
        {
            fixture = f;
            point = p;
            return fr;
        }, point1, point2);

        return new KeyValuePair<Fixture, Vector2>(fixture, point);
    }

I don't see anything that could be considerably optimized there. The profiles only shows the Dynamics.World.RayCast function there, the other stuff is negligible, but the tree is somewhat confusing, Collision.DynamicTree`1.RayCast(Func, ref RayCastInput) takes a lot of time, but below it there's a lot of stuff, including Wrapper and OverlapTester.

Am I doing something wrong? Would you guys recommend another approach, maybe using a fast library specialized on raycasting ( I couldn't find any though )? Thanks in advance.

[Genbox]

What is FNA?

There are some micro-optimizations that can be done in your code, such as sending value types as references and not boxing values. The delegate for RayCast is also created on each call if I remember correctly, so you could skip a bit of garbage by not using an anon delegate, but making it a named method. Other than that, I'm not sure how to do lighting efficiently.

Could you take a screenshot of the profiler output?

[Alan-FGR]

@Genbox thanks for your reply. FNA is a modern XNA4 implementation.

I've decided to go with shaders for the shadows, the effect looks much better and it runs literally more than five-hundred times faster... I'm using a vertex shader to 'move' duplicated vertices away from some points I'm passing from CPU and also projecting a quad 'below' them with the light projection image, so in a single draw call I can project lights of any complexity, and the only cost is creating the VBO, which could be done only once if there's no dynamic light occluders. I don't think using the physics engine is appropriate for that actually. Apparently some people can get away with that but it's certainly far from ideal.