C# performance tuning, part 4. Quad Tree

When profiling application with sampling mode, dotTrace does not show call count unfortunately. Switching to Tracing mode changes that. It has bigger performance impact on code – profiling will take more time, but it shows some interesting details. For example – Triangle.Contains method, which is slowest part of the code at the moment is being called 11 903 344 times! It should be halved since I’m running collision counting twice (serial and parallel) but that’s still close to 6 million calls. And it’s just 1000 triangles. Why is that? Well, I’m checking collisions between all triangles in the area, no matter where they are. One is in left top corner, the other in right bottom. Clearly far enough to not collide, but still check is done. And Contains check happens so often because it happens each time when triangle sides are not colliding.

So that needs to be fixed as soon as possible. One thing the code is missing is bounding box definition. Bounding box is pretty standard technique in collision detection – you surround your object with virtual rectangle to be able to quickly check if two objects are possibly colliding. If they don’t collide at bounding box level you don’t need to check anything else.

Rectangle definition looks like this:

    public class Rectangle
    {
        public Point LeftBottom { get; private set; }

        public int Width { get; private set; }
        public int Height { get; private set; }

        public Rectangle(Point leftBottom, int width, int height)
        {
            LeftBottom = leftBottom;
            Width = width;
            Height = height;
        }

        public bool Intersects(Rectangle b)
        {
            return
                (LeftBottom.X + Width) >= b.LeftBottom.X &&
                LeftBottom.X <= (b.LeftBottom.X + b.Width) &&
                (LeftBottom.Y + Height) >= b.LeftBottom.Y &&
                LeftBottom.Y <= (b.LeftBottom.Y + b.Height);
        }
    }

Rectangle intersection check is pretty simple to understand, try following the logic and it should be pretty obvious how it works.

Now adding bounding box to Triangle and quick check if boxes are intersecting should give some performance kick.

        private Line[] _lines;
        private Rectangle _boundingBox;
                
        public Triangle(Point a, Point b, Point c)
        {
            A = a;
            B = b;
            C = c;

            _lines = new[]
            {
                new Line(A, B),
                new Line(B, C),
                new Line(C, A)
            };
            
            var xCoordinates = new List<int> { A.X, B.X, C.X };
            var yCoordinates = new List<int> { A.Y, B.Y, C.Y };
            var leftBottom = new Point(xCoordinates.Min(), yCoordinates.Min());
            int width = xCoordinates.Max() - leftBottom.X;
            int height = yCoordinates.Max() - leftBottom.Y;

            _boundingBox = new Rectangle(leftBottom, width, height);
        }
		
		...
		
		public bool Intersects(Triangle b)
        {
            if (!_boundingBox.Intersects(b._boundingBox))
                return false;

            return SegmentsAreCrossing(b) || OneIsInsideTheOther(b);
        }

Simple and straightforward. And results? 25 and 7 milliseconds for serial and parallel respectively! Wow, that’s huge! To be honest I probably should have started with something as obvious as this. Now there are just 108 520 calls to slow Contains method.

Parallel version went below 16ms target. Serial version is still quite well above this limit. Am I satisfied with that? Of course not. There must be a lot that can be done to squeeze every bit of performance there is. Collision detection is not all.

So we have bounding boxes, but we still check each object with every other. Some are obviously in different areas so we could skip them. But how do we know? There is pretty well know structure called Quad Tree. It is similar to binary tree but each node can have up to four child nodes, not two. How is that useful? You can split screen area in 4 equal sections and just check collisions between objects in the this one section plus with objects that are placed across the borders. Again – code is bellow. It is pretty simple to follow, so go through with it.

    public class QuadTree
    {
        private List<Triangle> _objects;
        private QuadTree[] _nodes;
        private Rectangle _area;
        private uint _level;
        private readonly uint MaxLevel = 4;

        public QuadTree(Rectangle area) : this(area, 0)
        { }

        private QuadTree(Rectangle area, uint level)
        {
            _level = level;
            _objects = new List<Triangle>(4);
            _nodes = new QuadTree[4];
            _area = area;
        }

        public void Insert(Triangle obj)
        {
            if (_nodes[0] != null)
            {
                int index = GetIndex(obj);
                if (index != -1)
                {
                    _nodes[index].Insert(obj);
                    return;
                }
            }

            _objects.Add(obj);

            if (_objects.Count > 4 && _level < MaxLevel)
            {
                if (_nodes[0] == null)
                    Split();

                int i = 0;
                while (i < _objects.Count)
                {
                    int index = GetIndex(_objects[i]);
                    if (index != -1)
                    {
                        Triangle objToMove = _objects[i];
                        _objects.Remove(objToMove);
                        _nodes[index].Insert(objToMove);
                    }
                    else
                        i++;
                }
            }
        }

        public IReadOnlyList<Triangle> GetObjects(Triangle obj)
        {
            var all = new List<Triangle>(_objects);
            all.AddRange(GetChildObjects(obj));
            all.Remove(obj);
            return all;
        }

        private IReadOnlyList<Triangle> GetChildObjects(Triangle obj)
        {
            if (_nodes[0] == null)
                return new Triangle[0];

            int index = GetIndex(obj);
            if (index != -1)
            {
                return _nodes[index].GetObjects(obj);
            }
            else
            {
                var all = new List<Triangle>();
                for (int i = 0; i < _nodes.Length; i++)
                    all.AddRange(_nodes[i].GetObjects());

                return all;
            }
        }

        public IReadOnlyList<Triangle> GetObjects()
        {
            var all = new List<Triangle>(_objects);
            if (_nodes[0] != null)
                for (int i = 0; i < _nodes.Length; i++)
                    all.AddRange(_nodes[i].GetObjects());
            
            return all;
        }

        private void Split()
        {
            int subWidth = (int)(_area.Width / 2);
            int subHeight = (int)(_area.Height / 2);
            int x = _area.LeftBottom.X;
            int y = _area.LeftBottom.Y;

            // 1 | 0
            // -----
            // 2 | 3
            _nodes[0] = new QuadTree(new Rectangle(new Point(x + subWidth, y + subHeight), subWidth, subHeight), _level + 1);
            _nodes[1] = new QuadTree(new Rectangle(new Point(x, y + subHeight), subWidth, subHeight), _level + 1);
            _nodes[2] = new QuadTree(new Rectangle(new Point(x, y), subWidth, subHeight), _level + 1);
            _nodes[3] = new QuadTree(new Rectangle(new Point(x + subWidth, y), subWidth, subHeight), _level + 1);
        }

        private int GetIndex(Triangle obj)
        {
            int index = -1;
            int vMid = _area.LeftBottom.X + (_area.Width / 2);
            int hMid = _area.LeftBottom.Y + (_area.Height / 2);

            Rectangle box = obj.BoundingBox;

            bool topQuadrant = box.LeftBottom.Y > hMid;
            bool bottomQuadrant = box.LeftBottom.Y < hMid && box.LeftBottom.Y + box.Height < hMid;

            if (box.LeftBottom.X < vMid && box.LeftBottom.X + box.Width < vMid)
            {
                if (topQuadrant)
                    index = 1;
                else if (bottomQuadrant)
                    index = 2;
            }
            else if (box.LeftBottom.X > vMid)
            {
                if (topQuadrant)
                    index = 0;
                else if (bottomQuadrant)
                    index = 3;
            }

            return index;
        }
    }

It’s not the shortest code, but it is not that complex as well. And how do you use it? First – populate it with objects:

        static void Main(string[] args)
        {
            const int screenWidth = 1000;
            const int screenHeight = 1000;
            var rand = new Random(0);
            var triangles = new QuadTree(new Rectangle(new Point(0, 0), screenWidth, screenHeight));

            for (int i = 0; i < 1000; i++)
            {
                var a = new Point(rand.Next(0, screenWidth), rand.Next(0, screenHeight));
                var b = new Point(a.X + rand.Next(0, 100), a.Y + rand.Next(0, 100));
                var c = new Point(a.X + rand.Next(0, 100), a.Y + rand.Next(0, 100));
                triangles.Insert(new Triangle(a, b, c));
            }

            Collisions(triangles);
            CollisionsParallel(triangles);

            Console.ReadKey();
        }

And then slightly modified collision checkings:

       private static void Collisions(QuadTree triangles)
        {
            Stopwatch watch;
            int collisions;
            watch = new Stopwatch();

            watch.Start();
            collisions = 0;
            var trianglesList = triangles.GetObjects();
            for (int i = 0; i < trianglesList.Count; i++)
            {
                Triangle triangle = trianglesList[i];
                var pottentialColliding = triangles.GetObjects(triangle);
                collisions += CheckCollisions(pottentialColliding, triangle);
            }
            watch.Stop();
            Console.WriteLine("Collisions: {0}\t time: {1}", collisions, watch.ElapsedMilliseconds);
        }

        private static int CollisionsParallel(QuadTree triangles)
        {
            Stopwatch watch;
            int collisions;
            watch = new Stopwatch();

            watch.Start();
            collisions = 0;
            var trianglesList = triangles.GetObjects();
            Parallel.For(0, trianglesList.Count,
                i =>
                {
                    Triangle triangle = trianglesList[i];
                    var pottentiatlColliding = triangles.GetObjects(triangle);
                    int coll = CheckCollisions(pottentiatlColliding, triangle);
                    Interlocked.Add(ref collisions, coll);
                });
            watch.Stop();
            Console.WriteLine("Collisions: {0}\t time: {1}", collisions, watch.ElapsedMilliseconds);
            return collisions;
        }

        private static int CheckCollisions(IReadOnlyList<Triangle> triangles, Triangle triangle)
        {
            int collisions = 0;
            for (int j = 0; j < triangles.Count; j++)
                if (triangle.Intersects(triangles[j]))
                    ++collisions;

            return collisions;
        }
    }

So how did it go? Surprisingly not to well. 30 and 10 milliseconds is significant slowdown compared to previous version! And collisions detected fell down to 7054? What’s with that? Did I break the code?

First let’s handle performance downgrade. If you think about it a little bit and use profiler, it’s not all that unexpected. We are doing less collision checks – true. But we are paying the price of Quad Tree getting us the objects, calculating object position, traversing tree, allocating new lists for objects. That’s a lot of work. But I feel that Quad Tree is still a good choice. It just needs some performance tuning on its own and it may shine. And if not – I will admit defeat and go back to simple list.

But how can I even compare broken code’s performance? I’m close to 1000 collisions detected short! Well, truth be told – I’m not. You see – checking all objects against all others have one serious problem – you are doing double checks and double counting of collisions.
Imagine list of objects {A, B, C}. I’m checking A+B and A+C collisions first, then B+A, B+C and at the end C+A and C+B. See the problem? If A is colliding with B, then clearly B must be colliding with A and I’m still doing the check.

Quad Tree partially saves me from that. Objects at root level will check collisions with all sub-level objects, but objects at lower levels will not go back up to check those collisions again, so less checks are done and less collisions are counted. But that gets me closer to actual number of collisions.

Next I will look how Quad Tree can be optimized so that we will be doing step forward instead of backward.

Advertisements

3 thoughts on “C# performance tuning, part 4. Quad Tree

  1. Pingback: C# performance tuning, part 7. Summary. | Why u no code?!

    • Hmm, why not? ;)
      Triangles are used in computer graphics to approximate shape of more complex elements. Of course you could approximate circle with squares/rectangles as well, but with triangles it seems simpler (at least to me).
      In 3D graphics, triangles are commonly used since every triangle is always part of single plane. For rectangles that is not necesarily true. Hence – you would still need to convert those rectangles into triangles to render them, operate on them etc. Triangles offer simple math to find collisions, are easy to render etc.

      But, of course, in this blog series, I chose triangles simply because – why not. Served the purpose well :)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s