Bug 3785 - RotatePointAroundVector() optimization
Status: RESOLVED DUPLICATE of bug 3323
Alias: None
Product: ioquake3
Classification: Unclassified
Component: Misc
Version: GIT MASTER
Hardware: All All
: P3 enhancement
Assignee: Zachary J. Slater
QA Contact: ioquake3 bugzilla mailing list
URL:
Depends on:
Blocks:
 
Reported: 2008-09-20 07:04 EDT by Ivan Sorokin
Modified: 2008-09-20 18:41:23 EDT
0 users

See Also:



Description Ivan Sorokin 2008-09-20 07:04:24 EDT
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.
Comment 1 Ivan Sorokin 2008-09-20 07:25:27 EDT
Oops, variable s can be eliminated.
Comment 2 /dev/humancontroller 2008-09-20 18:13:43 EDT
What about bug 3323?
Comment 3 Ivan Sorokin 2008-09-20 18:41:23 EDT
I didn't know about it. :-(

Now, I think that we can consider my report as duplicate.

*** This bug has been marked as a duplicate of bug 3323 ***