[Bug 3785] New: RotatePointAroundVector() optimization

[bugzilla-daemon at icculus.org]

http://bugzilla.icculus.org/show_bug.cgi?id=3785

           Summary: RotatePointAroundVector() optimization
           Product: Quake 3
           Version: SVN HEAD
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: enhancement
          Priority: P3
         Component: Misc
        AssignedTo: zakk at icculus.org
        ReportedBy: sorokin at rain.ifmo.ru
         QAContact: quake3-bugzilla at icculus.org


Hello.

When I was looking through q_math.c, I noticed that RotatePointAroundVector()
isn't implemented very well. It use a lot of multiplications and should work
slowly than it can. I've write my own implementation which use only 27
multiplications and, according to my testing, it work at about 9-16% faster
than orginal implementation. It has 30 lines of code fewer (22 against 52). It
contains only 10 local variables (agains 56).

My implementation is based on quaternion rotation algoritm, which I can write
in pseudo code as:
point_3f rotate(point_3f v, quaternion q)
{
   return quaternion2point(q * point2quaternion(v) * inverse(q));
}

I use the following optimizations:
1. Orginal function can work only with normalized dir vector, so we can replace
inverse(q) by conjugate(q)
2. point2quaternion returns quaternion with 0 fourth element. So multiplication
on it gives 0.
3. quaternion2point use only first 3 items. So we can avoid it's forth element
computation.
4. Some minor transformations.

So, I've got the following function:

void RotatePointAroundVector( vec3_t dst, const vec3_t dir, const vec3_t point,
float degrees )
{
   float q[3];
   float q3;
   float t[3];
   float t3;

   {
      float hrad;
      float s;

      hrad = DEG2RAD(degrees) / 2;
      s = sin(hrad);
      VectorScale(dir, s, q);
      q3 = cos(hrad);
   }

   CrossProduct(q, point, t);
   VectorMA(t, q3, point, t);
   t3 = DotProduct(q, point);

   CrossProduct(q, t, dst);
   VectorMA(dst, t3, q, dst);
   VectorMA(dst, q3, t, dst);
}

I also try other implementations which use less multiplications (at about 20).
But all of them work at the same speed. (with a glance measure error)

Here (http://rain.ifmo.ru/~sorokin/mirror/quattest.7z) you can download the
program by that I test correctness and performance of new implementation.


-- 
Configure bugmail: http://bugzilla.icculus.org/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are the QA contact for the bug, or are watching the QA contact.