0
\$\begingroup\$

BACKGROUND: As discussed here: Fast 2D collision detection in an unbounded space I am working on a collision detection algorithm for a simulation. The catch that makes this case unique is that the objects in the simulation could all be in a very small area (e.g. 1000x1000) or in a very large area (e.g. 9 bil x 10 bil). Moreover, changes like this could occur very rapidly because of high object velocities, so I needed a somewhat sophisticated algorithm to deal with this situation. In the end, I went with quadtrees (http://en.wikipedia.org/wiki/Quadtree). When I finished writing the quadtree class and determined that it was functioning correctly, I uploaded it into my simulation.

THE PROBLEM: At first, the quadtree worked wonderfully. I was just testing it out for the first time, so instead of feeding it updated bounds every time step of the objects with the least x value/greatest x value/least y value/greatest y value, I just fed is a large area that I knew would be good enough for the test case (10 mil x 10 mil).

In a test involving 1600 objects, my simulation ran almost four times faster than the brute force solution of checking every object against itself! (about 28 fps instead of 7 fps) Wonderful! I then proceeded to feed the quadtree the updated "bounds" of the simulation by finding the min/max x/y each frame (this is where the problem begins). After updating each object's position, I simply checked to see if it was the new min/max extreme in each dimension:

    double tempradius = (*getMoveableEntityVector()[n]).Retradius();
    double tempx = (*getMoveableEntityVector()[n]).Retxpos();
    double tempy = (*getMoveableEntityVector()[n]).Retypos();

    if (n == 0) { //if it's the first object initialize the variables based off it
        minx = tempx - tempradius;
        maxx = tempx + tempradius;
        miny = tempy - tempradius;
        maxy = tempy + tempradius;
    }
    else { //all other objects
        if (minx > tempx - tempradius) { //if this object has the lowest x value
            minx = tempx - tempradius;
        }
        else if (maxx < tempx + tempradius) { //if has the highest x value
            maxx = tempx + tempradius;
        }

        if (miny > tempy - tempradius) { //if has lowest y value
            miny = tempy - tempradius;
        }
        else if (maxy < tempy + tempradius) { //if has highest y value
            maxy = tempy + tempradius;
        }
    }

Running through this simple code a mere 1600 times per time step slowed the simulation back down below the speed of my original brute force implementation! (about 7 fps)

WHY THIS DOESN'T MAKE SENSE TO ME: The original brute force implementation had to run through the relatively computationally intense distance formula (http://math.about.com/library/bldistance.htm) about 1600*1600 times per time step, or more exactly, 1600*1599/2 = 1,279,200 times per time step. I would think running through the above code once would be about as computationally intensive as doing the distance formula once. How is going through the above code only 1,600 times costing me as much processor time as going through the distance formula more than a million times?!?

EDIT: The question is not directly about the quadtree; it is about the code above that finds the objects with the least/greatest x/y coordinates. (This code feeds its calcuations to the quadtree so the quadtree knows where to start, but it is definitely not quadtree code). The quadtree code ran quite fast until I added the above helper code. The only reason I mentioned the quadtree and the background to this issue is because the quadtree/background stuff gives context on why I think that this code should be going much faster (1000 comparable checks vs 1,000,000!)

TLDR (TOO LONG DIDN'T READ): Check out the code above. Is there something making it take up WAY more (about 1000x more!) processor time than I think it should be taking?

Thanks in advance for the time and help!

\$\endgroup\$
  • 2
    \$\begingroup\$ A 4:1 change could come from anywhere from cache thrashing when data layouts changed to extra work in one place eating up the savings elsewhere. You need to profile each change for cache hits, call counts and time spent in each logical block to figure it all out. My first reaction is that rebuilding the tree every frame is eating all your time, and that's destroying any savings from avoiding the computations later. But it really does need to be measured, especially since we don't know what's inside your quadtree code. \$\endgroup\$ – Patrick Hughes Aug 17 '13 at 22:44
  • 1
    \$\begingroup\$ Cache misses are going to dominate a lot of performance. Your tree might have been written without the cache in mind. With tons of fast moving objects if you have to rebuild your tree from frame to frame, you might defeat the purpose of using the tree at all. \$\endgroup\$ – RandyGaul Aug 17 '13 at 23:04
  • \$\begingroup\$ @PatrickHughes @ RandyGaul Thanks for the information! However, the question isn't directly referring to the quadtree. As I mentioned above, things were going well when I first implemented the quadtree, it's just the code above that is finding the outer-most bounds of the quadtree that is causing the slowdown. I will try to be more clear with an edit. \$\endgroup\$ – MindSeeker Aug 17 '13 at 23:46
  • \$\begingroup\$ @PatrickHughes @ RandyGaul Even though your two responses didn't quite answer the question I was asking, I really appreciate both of them! The things you were talking about (I admit to being more than a little over my head in these topics, but I'll study up) could explain why the quadtree was great, but not as great performance-wise as I had hoped. Once I deal with the current issue I'll definitely dig into the whole cache thing to optimize my quadtree code. Thanks again! \$\endgroup\$ – MindSeeker Aug 17 '13 at 23:48
  • 1
    \$\begingroup\$ @MindSeeker "optimise code for the cache" - wow, where to begin? It's complicated. Use contiguous memory, don't dynamically (de)alloc, use memory in a predictable fashion. Here's a video (jump to ~18:30 for a more relevant example): channel9.msdn.com/Events/Build/2013/4-329 \$\endgroup\$ – congusbongus Aug 22 '13 at 4:46
1
\$\begingroup\$

First, my apologies to Patrick and RandyGaul; I originally phrased my question poorly, but through this misunderstanding they did in fact point me towards the right answer.

The answer is that even though the code was building the quadtree from scratch each time step, having the constant bounds drastically decreases the time required to build the quadtree, even when I have 10,000 objects all moving rapidly. Solution? Round the bounds to the most appropriate multiple (round up for the greater bounds and down for the lesser bounds) of x, where x is some very large number. This "smooths out" the changes in the quadtree's bounds and solves the issue.

The reason why this works is beyond me, but if someone else wants to address that issue that would be awesome. Obviously (well...maybe) it has something to do with fewer bits in the cache being rearranged. Speaking of the mechanics of the cache, the video that congusbongus posted is great; I highly recommend it, although I don't think it gets into the topic deep enough to answer the "why" of why my solution is an effective solution.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.