[fixed] faster implementation of tranformBoxEx()

[vitek]

This isn't super important, but I stumbled on this at work today... The following implementation of transformBoxEx() is about 3x as fast as the one currently used by Irrlicht.

The idea is from an article by James Arvo entitled Transforming Axis-Aligned Bounding Boxes. The article can be found in the old Graphics Gems book, and the source code can be found on the web here.

Code: Select all

// i made this a global function that takes a matrix as a param. you can
// easily adapt it to be a member function of the matrix class if you want.
void transformBoxEx(const core::matrix4& m, core::aabbox3df& box)
{
  f32 Amin[3];
  f32 Amax[3];
  f32 Bmin[3];
  f32 Bmax[3];
  
  Amin[0] = box.MinEdge.X;
  Amin[1] = box.MinEdge.Y;
  Amin[2] = box.MinEdge.Z;

  Amax[0] = box.MaxEdge.X;
  Amax[1] = box.MaxEdge.Y;
  Amax[2] = box.MaxEdge.Z;

  Bmin[0] = Bmax[0] = m.M[12];
  Bmin[1] = Bmax[1] = m.M[13];
  Bmin[2] = Bmax[2] = m.M[14];

  u32 i, j;
  for (i = 0; i < 3; ++i) {
    for (j = 0; j < 3; ++j) {
      f32 a = m(j,i) * Amin[j];
      f32 b = m(j,i) * Amax[j];

      if (a < b)
      {
        Bmin[i] += a;
        Bmax[i] += b;
      }
      else
      {
        Bmin[i] += b;
        Bmax[i] += a;
      }
    }
  }

  box.MinEdge.X = Bmin[0];
  box.MinEdge.Y = Bmin[1];
  box.MinEdge.Z = Bmin[2];

  box.MaxEdge.X = Bmax[0];
  box.MaxEdge.Y = Bmax[1];
  box.MaxEdge.Z = Bmax[2];
}

[vitek]

In case anyone cares, here is my test function and the output...

Code: Select all

void runBoxPerfTest(irr::ITimer* timer, scene::ISceneNode* node, u32 c)
{
  {
    core::aabbox3df b(node->getBoundingBox());
    core::matrix4& m(node->getAbsoluteTransformation());

    u32 t0 = timer->getRealTime();

    u32 n;
    for (n = 0; n < c; ++n)
      m.transformBoxEx(b);

    u32 t1 = timer->getRealTime();

    fprintf(stderr, "%u [[%0.2f %0.2f, %0.2f], [%0.2f, %0.2f, %0.2f]]\n",
      t1 - t0,
      b.MinEdge.X, b.MinEdge.Y, b.MinEdge.Z,
      b.MaxEdge.X, b.MaxEdge.Y, b.MaxEdge.Z);
  }

  {
    core::aabbox3df b(node->getBoundingBox());
    core::matrix4& m(node->getAbsoluteTransformation());

    u32 t0 = timer->getRealTime();

    u32 n;
    for (n = 0; n < c; ++n)
      transformBoxEx(m, b);

    u32 t1 = timer->getRealTime();

    fprintf(stderr, "%u [[%0.2f %0.2f, %0.2f], [%0.2f, %0.2f, %0.2f]]\n",
      t1 - t0,
      b.MinEdge.X, b.MinEdge.Y, b.MinEdge.Z,
      b.MaxEdge.X, b.MaxEdge.Y, b.MaxEdge.Z);
  }
}

Code: Select all

// output from debug build - 2.8x faster [c=0xffff]
348 [[5.56 983020.00, 1638370.00], [5.56, 983030.00, 1638380.00]]
123 [[5.56 983020.00, 1638370.00], [5.56, 983030.00, 1638380.00]]

// output from release build - 3.7x faster [c=0xffff]
26 [[5.56 983020.00, 1638370.00], [5.56, 983030.00, 1638380.00]]
7 [[5.56 983020.00, 1638370.00], [5.56, 983030.00, 1638380.00]]

[bitplane]

Cool.. I love your posts in this forum, always to the point, clean code, and come with a test case
I'll commit this asap

[niko]

Nice