2
\$\begingroup\$

From my tests:

AABB-Sphere: 2954.8 tests per ms.

AABB-AABB: 1087.0 tests per ms.

The sphere test is almost 3 times faster, but the two intersection tests seem to perform about the same number of operations (or even more in the sphere test).

My question is: why? I can't seem to figure this one out. Is there a better aabb intersection test?

For testing performance, I fill an array with 50 million randomly generated Vector3 points. These points should be more-or-less uniformly distributed. I create a Sphere and AABB (Bounds), both of which cover 50% of the volume in which the random points where generated. So half the tests should return true and the other half false for both Sphere and Bounds. (note: results are the same when sphere and bounds have equal surface areas as well).

My Vector3 class uses doubles, so there should be no converting back and forth between float<-->double.

AABB-Sphere intersection:

class Sphere
{
    public readonly Vector3 center;
    public readonly double radius;

    public Sphere(Vector3 center, double radius)
    {
        this.center = center;
        this.radius = radius;
    }

    public bool test(Bounds bounds)
    {
        Vector3 min = bounds.center - bounds.halfsize;
        Vector3 max = bounds.center + bounds.halfsize;

        double ex = Math.Max(min.x - center.x, 0) + Math.Max(center.x - max.x, 0);
        double ey = Math.Max(min.y - center.y, 0) + Math.Max(center.y - max.y, 0);
        double ez = Math.Max(min.z - center.z, 0) + Math.Max(center.z - max.z, 0);

        return (ex < radius) && (ey < radius) && (ez < radius) && (ex * ex + ey * ey + ez * ez < radius * radius);
    }
}

AABB-AABB intersection:

class Bounds
{
    public readonly Vector3 center;
    public readonly Vector3 halfsize;

    public Bounds(Vector3 center, Vector3 halfsize)
    {
        this.center = center;
        this.halfsize = halfsize;
    }

    public bool test(Bounds b2)
    {
        Vector3 d = this.center - b2.center;

        double ex = Math.Abs(d.x) - (this.halfsize.x + b2.halfsize.x);
        double ey = Math.Abs(d.y) - (this.halfsize.y + b2.halfsize.y);
        double ez = Math.Abs(d.z) - (this.halfsize.z + b2.halfsize.z);

        return (ex < 0) && (ey < 0) && (ez < 0);
    }
}

The test code:

int count = 50000000;
Vector3[] points= new Vector3[count];
bool[] results = new bool[count];

/* populate points array here */ 

Sphere geometry = new Sphere(center,radius);
// Bounds geometry = new Bounds(center,halfsize);

Stopwatch stopWatch = new Stopwatch();

stopWatch.Start();
for ( int i = 0; i < count; ++i )
{
    results[i] = geometry.test( points[i] );
}
stopWatch.Stop();

TimeSpan ts = stopWatch.Elapsed;
String time = String.Format("{0:00}:{1:00}:{2:00}.{3:00}",   ts.Hours, ts.Minutes, ts.Seconds, ts.Milliseconds / 10);

In case it's relevant:

public struct Vector3
{
    public readonly double x, y, z;

    public static Vector3 operator +(Vector3 a, Vector3 b) { return new Vector3(a.x + b.x, a.y + b.y, a.z + b.z); }
    public static Vector3 operator -(Vector3 a, Vector3 b) { return new Vector3(a.x - b.x, a.y - b.y, a.z - b.z); }
    public static Vector3 operator *(Vector3 a, double f) { return new Vector3(a.x * f, a.y * f, a.z * f); }
    public static Vector3 operator *(double f, Vector3 a) { return new Vector3(a.x * f, a.y * f, a.z * f); }
    public static Vector3 operator /(Vector3 a, double f) { double ff = 1.0 / f; return new Vector3(a.x * ff, a.y * ff, a.z * ff); }
}

Profiling:

I didn't get very detailed logs from the Unity profiler, but it narrows things down:

enter image description here

It shows that calculating ex,ey,ez (extents) takes twice as long for bounds-bounds compared to sphere-bounds.

The center of the sphere was originally at (0,0,0), but I changed that to ensure it was't giving the sphere an unfair advantage.

I think both tests include the same number of additions/subtractions when calculating extents (6). So my next step is to test the performance of Math.Max() vs Math.Abs().

In the bounds-bounds test, I tried changing:

 Math.Abs(x);

to

 Math.Max(x,-x);

and the performance dropped further. I'm not sure why, both those operations calls should be highly optimized. After the change, the extents calculations are nearly identical in both intersection tests. Sphere is still faster.

I implemented my own Max/Abs functions. Sphere-bounds got even faster! Bounds-bounds stayed the same:

AABB-Sphere: 3574.9 tests per ms.

AABB-AABB: 1083.5 tests per ms.

The functions were simple:

public static double Max(double a, double b)
{
   return (a > b) ? a : b;
}

public static double Abs( double a )
{
    return (a > 0) ? a : -a;
}

Profiling again:

Implementing the functions means I can profile them now!

Results: Max() and Abs() don't contribute to the issue. They are equivalent and only take a fraction of the time needed to calculate the extents.

enter image description here

Which means it comes down to the arithmetic, but...

This:

(a-b) + (b-c)

should not be significantly faster than this:

(a) - (b+c)

What optimizations could be at play?

\$\endgroup\$
  • 1
    \$\begingroup\$ You may want to mention that AABB is an axis-aligned bounding box. \$\endgroup\$ – RJFalconer Nov 1 '16 at 9:39
  • 2
    \$\begingroup\$ Have you tried profiling to see where the hotspots are? \$\endgroup\$ – RJFalconer Nov 1 '16 at 9:39
  • \$\begingroup\$ The sphere looks like it does much havier calculations then the bounds. \$\endgroup\$ – t3chb0t Nov 1 '16 at 19:32
  • \$\begingroup\$ Hence my confusion! I don't think it's much heavier though, and testing shows the opposite. Can't ignore that! I will try profiling tonight and post results. I'm just now figuring out how to use Unity3D for profiling :) \$\endgroup\$ – jpx Nov 1 '16 at 23:14
  • \$\begingroup\$ Is that your actual test code? Are you really passing a Vector3 to a function that takes a Bounds in this call? geometry.test( points[i] ); \$\endgroup\$ – JS1 Nov 3 '16 at 8:39
1
\$\begingroup\$

Contradicting result

I ran your program and got the opposite result. I got that the sphere test was slower than the aabb test. Here is the test program I used, which is essentially the OP's program with parts filled in:

using System;
using System.Diagnostics;

public struct Vector3
{
    public readonly double x, y, z;

    public Vector3 (double x0, double y0, double z0) { x = x0; y = y0; z = z0; }
    public static Vector3 operator +(Vector3 a, Vector3 b) { return new Vector3(a.x + b.x, a.y + b.y, a.z + b.z); }
    public static Vector3 operator -(Vector3 a, Vector3 b) { return new Vector3(a.x - b.x, a.y - b.y, a.z - b.z); }
    public static Vector3 operator *(Vector3 a, double f) { return new Vector3(a.x * f, a.y * f, a.z * f); }
    public static Vector3 operator *(double f, Vector3 a) { return new Vector3(a.x * f, a.y * f, a.z * f); }
    public static Vector3 operator /(Vector3 a, double f) { double ff = 1.0 / f; return new Vector3(a.x * ff, a.y * ff, a.z * ff); }
}

class Bounds
{
    public readonly Vector3 center;
    public readonly Vector3 halfsize;

    public Bounds(Vector3 center, Vector3 halfsize)
    {
        this.center = center;
        this.halfsize = halfsize;
    }

    public bool test(Bounds b2)
    {
        Vector3 d = this.center - b2.center;

        double ex = Math.Abs(d.x) - (this.halfsize.x + b2.halfsize.x);
        double ey = Math.Abs(d.y) - (this.halfsize.y + b2.halfsize.y);
        double ez = Math.Abs(d.z) - (this.halfsize.z + b2.halfsize.z);

        return (ex < 0) && (ey < 0) && (ez < 0);
    }
}
class Sphere
{
    public readonly Vector3 center;
    public readonly double radius;

    public Sphere(Vector3 center, double radius)
    {
        this.center = center;
        this.radius = radius;
    }

    public bool test(Bounds bounds)
    {
        Vector3 min = bounds.center - bounds.halfsize;
        Vector3 max = bounds.center + bounds.halfsize;

        double ex = Math.Max(min.x - center.x, 0) + Math.Max(center.x - max.x, 0);
        double ey = Math.Max(min.y - center.y, 0) + Math.Max(center.y - max.y, 0);
        double ez = Math.Max(min.z - center.z, 0) + Math.Max(center.z - max.z, 0);

        return (ex < radius) && (ey < radius) && (ez < radius) && (ex * ex + ey * ey + ez * ez < radius * radius);
    }
}

class Test
{
    static void Main(string[] args)
    {
        int count = 100000;
        Bounds[] boundsArray= new Bounds[count];
        bool[] results = new bool[count];
        Vector3 center = new Vector3(500.0, 500.0, 500.0);
        Vector3 halfsize = new Vector3(250.0, 250.0, 250.0);
        double radius = 300.0;
        long numIntersected = 0;
        Random random = new Random(1);

        /* populate bounds array here */
        for (int i=0;i<count;i++) {
            double x  = random.Next(0, 1000);
            double y  = random.Next(0, 1000);
            double z  = random.Next(0, 1000);
            double sx = random.Next(1, 100);
            double sy = random.Next(1, 100);
            double sz = random.Next(1, 100);
            Vector3 c = new Vector3(x, y, z);
            Vector3 hs = new Vector3(sx, sy, sz);
            boundsArray[i] = new Bounds(c, hs);
        }

        Sphere sphere = new Sphere(center, radius);
        Stopwatch stopWatch = new Stopwatch();

        stopWatch.Start();
        for (int j=0;j<1000;j++) {
            for (int i = 0; i < count; ++i )
            {
                results[i] = sphere.test( boundsArray[i] );
                if (results[i])
                    numIntersected++;
            }
        }
        stopWatch.Stop();

        TimeSpan ts = stopWatch.Elapsed;
        String time = String.Format("{0:00}:{1:00}:{2:00}.{3:00}",   ts.Hours, ts.Minutes, ts.Seconds, ts.Milliseconds / 10);
        Console.Write("Sphere time = ");
        Console.Write(time);
        Console.WriteLine(", num intersected = " + numIntersected);

        Bounds aabb = new Bounds(center,halfsize);
        numIntersected = 0;
        stopWatch.Reset();
        stopWatch.Start();
        for (int j=0;j<1000;j++) {
            for (int i = 0; i < count; ++i )
            {
                results[i] = aabb.test( boundsArray[i] );
                if (results[i])
                    numIntersected++;
            }
        }
        stopWatch.Stop();

        ts = stopWatch.Elapsed;
        time = String.Format("{0:00}:{1:00}:{2:00}.{3:00}",   ts.Hours, ts.Minutes, ts.Seconds, ts.Milliseconds / 10);
        Console.Write("AABB   time = ");
        Console.Write(time);
        Console.WriteLine(", num intersected = " + numIntersected);
    }
}

And here are the results:

Sphere time = 00:00:06.36, num intersected = 21474000
AABB   time = 00:00:01.67, num intersected = 21234000
\$\endgroup\$
  • \$\begingroup\$ +1 Thanks! This led me to test my code inside vs outside Unity engine. The results blew my mind. Unity is sloooow. My external test shows both take about the same amount of time. Still don't know why bounds-bounds is slower when running in Unity. This might be out of scope? Not sure. I will update my post with these results. \$\endgroup\$ – jpx Nov 4 '16 at 3:15
0
\$\begingroup\$

Note that I've been running the code in Unity Engine, launched from the editor. Running the exact same code in a compiled console application shows that the two intersection tests perform very well, and as expected the AABB-AABB test is slightly faster!

Console Application:
Environment Version: 4.0.30319.42000

Testing Sphere vs AABB
- 10,614,220 intersections found
- rate: 20529.61 checks/ms

Testing AABB vs AABB
- 10,510,623 intersections found
- rate: 24097.01 checks/ms

To be sure launching from the Unity editor wasn't causing the problem, I built and ran the Unity project. This showed much better performance, but the AABB-AABB intersection test was still slower.

Unity Engine (Build & Run):
Environment Version: 3.0.40818.0

Testing Sphere vs AABB
- 10,398,417 intersections found
- rate: 9620.18 checks/ms

Testing AABB vs AABB
- 10,328,325 intersections found
- rate: 7170.23 checks/ms

The full answer will be related to how Unity runs the code; compiled vs interpreted, Mono runtime version quirks, and optimizations applied.

I believe part of the reason that the AABB-AABB intersection test code runs slower is because it's missing optimizations which have been made to the other intersection test.

I can show that playing around with the code structure, while not changing any of the operations, can result in drastically different performance.

Example: slow @ 6205 checks per ms:

public bool intersects(Bounds b2)
{
    double dx = bounds.center.x - b2.center.x;
    double dy = bounds.center.y - b2.center.y;
    double dz = bounds.center.z - b2.center.z;

    dx = (dx < 0) ? -dx : dx;
    dy = (dy < 0) ? -dy : dy;
    dz = (dz < 0) ? -dz : dz;

    double ex = dx - ( bounds.halfsize.x + b2.halfsize.x );
    double ey = dy - ( bounds.halfsize.y + b2.halfsize.y );
    double ez = dz - ( bounds.halfsize.z + b2.halfsize.z );

    return  (ex <= 0) && (ey <= 0) && (ez <= 0);
}

Example: fast(er) @ 8050 checks per ms:

public bool intersects(Bounds b2)
{
    Vector3 d = bounds.center - b2.center;
    Vector3 e = Abs(d) - (bounds.halfsize + b2.halfsize);

    return (e.x <= 0) && (e.y <= 0) && (e.z <= 0);
}

public static Vector3 Abs(Vector3 v)
{
     return new Vector3( 
            ((v.x < 0) ? -v.x : v.x), 
            ((v.y < 0) ? -v.y : v.y), 
            ((v.z < 0) ? -v.z : v.z)  );  
}

This is as fast as I could get it while running in Unity Engine, but it's still slower than the 9600 checks per ms that the Sphere-AABB consistently gets.

These same structural changes to the code had no effect when running in the compiled console application, which tells me that in this scenario the code is properly optimized.

\$\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.