Change to speed up grid creation

Apr 16, 2009 at 7:20 PM
Edited Apr 16, 2009 at 7:21 PM
I've got some large geometries (which I should really break up, but that's another story...) and grid creation for them can be quite slow. I dug around the code and manage to speed things up a bit. If you replace the existing GetNearestDistance method in Geom.cs with the following, grid creation is roughly twice as fast. The key is calculating the full feature information only on the closest edge, and not each time in the loop to find the closest.

        /// Gets the nearest distance relative to the point given.
        /// </summary>
        /// <param name="point">The point that should be calculated against.</param>
        /// <returns>The distance</returns>
        public float GetNearestDistance(Vector2 point)
        {
            float distance = float.MaxValue;
            int nearestIndex = 0;

            for (int i = 0; i < localVertices.Count; i++)
            {
                float pointDistance = GetDistanceToEdge(ref point, i);

                if (pointDistance < distance)
                {
                    distance = pointDistance;
                    nearestIndex = i;
                }
            }

            Feature nearestFeature = GetNearestFeature(point, nearestIndex);

            //Determine if inside or outside of geometry.
            Vector2 diff = Vector2.Subtract(point, nearestFeature.Position);
            float dot = Vector2.Dot(diff, nearestFeature.Normal);

            if (dot < 0)
            {
                distance = -nearestFeature.Distance;
            }
            else
            {
                distance = nearestFeature.Distance;
            }
            return distance;
        }

        private float GetDistanceToEdge(ref Vector2 point, int index)
        {
            Vector2 edge = localVertices.GetEdge(index);
            Vector2 diff = Vector2.Subtract(point, localVertices[index]);

            float c1 = Vector2.Dot(diff, edge);
            if (c1 < 0)
            {
                return Math.Abs(diff.Length());
            }

            float c2 = Vector2.Dot(edge, edge);
            if (c2 <= c1)
            {
                return Vector2.Distance(point, localVertices[localVertices.NextIndex(index)]);
            }

            float b = c1 / c2;
            edge = Vector2.Multiply(edge, b);
            Vector2 pb = Vector2.Add(localVertices[index], edge);

            return Vector2.Distance(point, pb);
        }

Coordinator
Apr 16, 2009 at 8:06 PM
Nice one ladron!

You effectively increased the performance on the grid creation by 71% in my tests. Even the preloading demo from the advanced samples runs at 91-100fps on my computer (compared to 50-60 before).

Great work.