Creating SAT geometry bottleneck, need tips on solving this problem

Aug 22, 2009 at 3:18 PM

Hi all,

I have narrowed down a huge bottleneck in my game to creation of SAT geometry, and am attempting to optimize this problem.

In my game I have arbitrary shaped terrain geometry, defined by placing vertices to create a convex or concave landmass, below is the function which uses these vertices to create the terrain for farseer to use:

 

        private void BuildPhysicsData(FarseerGames.FarseerPhysics.PhysicsSimulator sim)
        {
            FarseerGames.FarseerPhysics.Collisions.Vertices verts =
                new FarseerGames.FarseerPhysics.Collisions.Vertices(geom.Vertices.ToArray());

            physicsBody = FarseerGames.FarseerPhysics.Factories.BodyFactory.Instance.CreatePolygonBody(
                    verts,
                    1.0f);

            physicsBody.IsStatic = true;

            physicsGeometry = FarseerGames.FarseerPhysics.Factories.GeomFactory.Instance.CreateSATPolygonGeom(
                    physicsBody,
                    verts,
                    triangles.Count + 1);

            for (int i = 0; i < physicsGeometry.Count; ++i)
            {
                physicsGeometry[i].FrictionCoefficient = geom.FrictionCoef;
                physicsGeometry[i].RestitutionCoefficient = geom.RestitutionCoef;
            }
        }

Im pretty much stuck for how I can optimize this, any idea's would be very appreciated and helpful.

 

Scott

Coordinator
Aug 22, 2009 at 3:32 PM

It depends on what the problem is. Is it garbage? is it the number of polygons? is it the division of geometries? (happens inside CreateSATPolygonGeom())

Coordinator
Aug 22, 2009 at 4:28 PM

By the way, you might want to have a look at my blog about optimization: http://ianqvist.blogspot.com/ click the optimization category to see posts related to the category.

Aug 22, 2009 at 4:29 PM
Edited Aug 22, 2009 at 4:30 PM

I think it may be to do with the division of geometries, my reasoning is because this modification speeds it up a lot:

 

            physicsGeometry = new List<FarseerGames.FarseerPhysics.Collisions.Geom>();
            foreach (Triangle tri in triangles)
            {               
                physicsGeometry.InsertRange(
                    physicsGeometry.Count,
                    FarseerGames.FarseerPhysics.Factories.GeomFactory.Instance.CreateSATPolygonGeom(
                        physicsBody,
                        new FarseerGames.FarseerPhysics.Collisions.Vertices(tri.Verts),
                        1));
            }

 

A triangle is defined as:

 

struct Triangle
        {
            public Vector2[] verts;
            public Vector2[] vertsCompleteTriangle;

            public Triangle(Vector2 a, Vector2 b, Vector2 c)
            {
                verts = new Vector2[] { a, b, c };
                vertsCompleteTriangle = new Vector2[] { a, b, c, a };
            }
        }
        List<Triangle> triangles = new List<Triangle>();

 

 

triangles is filled up by the triangulator (nick gravelyn's) and is essentially a list of the triangles I draw to render the terrain, the idea being I am skipping the division process by simply supplying it with convex triangles, the problem with this (and this is where I'm at now) is that inside farseer these triangles seem to translate towards the center of the object by an amount in relation to the size of the object, see the picture:

 

Photobucket

 

 

I attempted to fix this by transforming the vertices of the triangles by the body's matrix:

 

 

Vector2[] v = tri.vertsCompleteTriangle;

                for (int i = 0; i < v.Length; ++i)
                {
                    v[i] = Vector2.Transform(v[i], physicsBody.GetBodyMatrix());
                }

 

 

But this has no effect.

Coordinator
Aug 22, 2009 at 5:00 PM

The triangulation process can be quite expensive and the current algorithms might not be the best to use for convex decomposition. I've been looking at using the Seidel algorithm instead of Earclip or even a CDT (Constrained Delaunay Triangulation) algorithm. Seidel uses trapezoids as a base for the triangulation and might be better suited for convex decomposition instead of triangles.

The algorithms are all implemented here, written in Scala. I'm waiting until 3.0 to implement the algorithms, you are welcome to give it a try now if you want to.

Aug 22, 2009 at 5:37 PM
Edited Aug 22, 2009 at 5:37 PM

If I can't work out why my triangles are offset strangely, I may have a go at implementing the same algorithm used by nick.

 

Thanks for the help =]

Coordinator
Aug 22, 2009 at 6:40 PM

The Earclip algorithm was ported over by Matthew, so I don't know the exact details about the algorithm or the implementation. The algorithm itself is inside the Vertices class and it should be 100% decoupled from the rest of the engine. No need to implement the algorithm when it is right there. Like this:

Vertices.DecomposeGeom(vertices, body, numberOfGeoms)

Have in mind that this method calls Polygon.DecomposeVertices(vertices, numberOfVertices) and takes the centroid into account and offsets the geometries. If there are any problems with the offset, that is where you should look.

Aug 23, 2009 at 6:48 PM

One thing I noticed in your code was the following line:

physicsBody = FarseerGames.FarseerPhysics.Factories.BodyFactory.Instance.CreatePolygonBody(
                    verts,
                    1.0f);

IIRC, this does a reasonably large amount of work considering you're just making it static. That's probably not your primary performance issue, but you might as well just make a body in a way that requires less calculation.

Aug 23, 2009 at 7:08 PM
Cowdozer wrote:

One thing I noticed in your code was the following line:

physicsBody = FarseerGames.FarseerPhysics.Factories.BodyFactory.Instance.CreatePolygonBody(
                    verts,
                    1.0f);

IIRC, this does a reasonably large amount of work considering you're just making it static. That's probably not your primary performance issue, but you might as well just make a body in a way that requires less calculation.

That's a very reasonable point, I may as well just make the terrain body a rectangle and save any extra overhead. Thanks for pointing it out.

 

Scott

Aug 23, 2009 at 10:27 PM

Ok, solved now guys, I decided to look int what was actually going on inside the factory calls I was using, and realised that I may aswell just bypass them all, and create my geometry manually, the new function works and is much quicker.

private void BuildPhysicsData(FarseerGames.FarseerPhysics.PhysicsSimulator sim)
        {
            FarseerGames.FarseerPhysics.Collisions.Vertices verts =
                new FarseerGames.FarseerPhysics.Collisions.Vertices(geom.Vertices.ToArray());

            physicsBody = FarseerGames.FarseerPhysics.Factories.BodyFactory.Instance.CreateBody(
                1.0f,
                1.0f);

            physicsBody.Position = sprite.Position;
            physicsBody.IsStatic = true;

            physicsGeometry = new List<FarseerGames.FarseerPhysics.Collisions.Geom>();
            foreach (Triangle tri in triangles)
            {
                Vector2[] v = tri.verts;

                v[0] -= sprite.Position;
                v[1] -= sprite.Position;
                v[2] -= sprite.Position;

                physicsGeometry.Add(new FarseerGames.FarseerPhysics.Collisions.Geom(
                    physicsBody,
                    new FarseerGames.FarseerPhysics.Collisions.Vertices(v),
                    Vector2.Zero,
                    0.0f,
                    1.0f));
            }

            for (int i = 0; i < physicsGeometry.Count; ++i)
            {
                physicsGeometry[i].FrictionCoefficient = geom.FrictionCoef;
                physicsGeometry[i].RestitutionCoefficient = geom.RestitutionCoef;
            }
        }

 

I think I'm still gonna have to find some more performance from somewhere, as level loading still takes too long in my opinion, however at least for now I can test without waiting a decade for my levels to build =]

Thanks for all the help, Scott

Sep 1, 2009 at 5:17 PM

Good to hear you have it performing better now! Is it this particular method that's taking so much time? It doesn't look particularly bad in any way, unless you happen to have many vertices and triangles. I'm not sure what else you are doing in your loading phase, but it might be worth looking at those other parts to see if performance could be improved there. Anyway, it sounds like it loads quickly enough now so that you can get on with things!