Collision Detection: Simulation Inexplicably Slowing Down/How To Efficiently Calculate Extremes In Each Dimension

Question

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!

Answer 1

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.