Circle Circle Optimization

Topics: Developer Forum
Jan 3, 2008 at 4:24 AM
I thought I would try hacking in an optimized solution for circle geometries. After taking a shot at it, everything seems to work and I increase performance of my app considerably....

The technique was simply this:
  • Add a "CanTreatAsCircle" property to geometry and set it when farseer's CreateACircle method is called.
  • Modify the Arbiter's Collide method so that it checks this flag on both geometries. In case of circle-circle, we do the fast method.

The one problem I have encountered though is that I no longer get "rotations" as a result of circle geometries colliding into each other. Anyone know why? My thought is that maybe rotations are not occuring after collisions any longer because, whereas previously the normals were coming from sampled verticies - they are now perfectly reflective (I generate them from circle center to center)? Anyone know if this is the reason? If so, Lol - maybe, I'll have to perturb them a little so I can get rotations!

Also, a engine question. While placing in this hack, I had to create contacts and I was confused by the contactID part as in this line:

Contact contact = new Contact(geometryB.WorldVertices[i], feature.Normal, feature.Distance, new ContactId(2, vertexIndex, 1));

I'm confused on what the vertexIndex gets used for. Why stepping through unmodified source (w/o the hack), I noticed that the vertexIndex is sometimes higher than the count on geometryB.WorldVertices. That doesn't seem to cause any harm... but it did confuse me.... is it possible that I'm not getting rotations because in my hacked version, I'm setting this incorrectly?

Thanks....

If it helps, here is my hack:

        private void Collide(Geom geometryA, Geom geometryB, ContactList contactList) {
        {
            if (geometryA.hintIsCircle == true && geometryB.hintIsCircle == true)
            {
                // Special optimization: Circle versus Circle
                // We assume that the 1st local vertex is of the form [0,x] and x is our radius.
                // (This is how the CreateACirclue function generates its first vertex)
                float radiusA = geometryA.localVertices[0].X;
                float radiusB = geometryB.localVertices[0].X;
                float combinedRadius = radiusA + radiusB;
                Vector2 diff = geometryA.Position - geometryB.Position;
                float distance = diff.Length();
 
                // Check for collision. If no collision occurs, return
                if (distance > combinedRadius)
                    return;
 
                float separation = distance - combinedRadius;
                Vector2 normalA = geometryB.Position - geometryA.Position;
                normalA.Normalize();
                Vector2 worldVertexPosA = geometryA.Position + (normalA * radiusA);
                
                Vector2 normalB = -normalA;
                Vector2 worldVertexPosB = worldVertexPosA; // geometryB.Position + (normalB * radiusB);
 
                int vertexIndexA = 0;
                int vertexIndexB = 0;
 
                // Not sure if this code is necessary. It only exist to determine which "vertexIndex" to use.
                // The FindArcPercent basically gives a value of 0.0 - 1.0 over the full circle. 
               //  So we just interpolate for the correct vertex to use. 
               //  In any case, this code didn't seem to do anything for me in regards to the rotations and
              //  it doesn't seem to matter what value vertexIndex is....
                {
                    float arcAPercent = FindArcPercent(ref normalA);
                    float arcBPercent = FindArcPercent(ref normalB);
 
                    vertexIndexA = (int)(arcAPercent * (geometryA.worldVertices.Count - 1));
                    vertexIndexB = (int)(arcBPercent * (geometryB.worldVertices.Count - 1));
                }
 
                Contact contactA = new Contact(worldVertexPosA, normalA, separation, new ContactId(2, vertexIndexA, 1));
                contactList.Add(contactA);
                Contact contactB = new Contact(worldVertexPosB, normalB, separation, new ContactId(1, vertexIndexB, 2));
                contactList.Add(contactB);
            }
            else
            { .. // Do normal stuff
Coordinator
Jan 3, 2008 at 10:59 AM
Edited Jan 3, 2008 at 11:00 AM
The vertex helps to uniquely identify the contact point.

If you look at ContactId you can see that it is defined by:
int geometryAIndex;
int geometryAVertex;
int geometryBIndex;

The index of geometryA and B is determined by whether I'm checking A against B or B against A. The geometryAVertex is simply the vertices in A that is inside B.

These 3 things are used whenever any type of compare operation is done on ContactId: =, !=

Much of this stems from one of Erin Cattos paper on physics http://www.gphysics.com/files/GDC2006_ErinCatto.zip

Jan 3, 2008 at 12:49 PM
Ok thanks - I'll check that out.

At the moment, I just decided to pass in zero for geometryAVertex. I removed the code above that I was unsure about and replace it with code that randomly perturb the normals by rotating slightly cw or ccw. This simulates a non-smooth circle and gives me the rotations I'm use to seeing. All seems to be working great.... I'll have to look into the = and != for contractID's - Maybe since I only create 1 contactID with the circle-circle case, the value doesn't come into play.

Andy.