[Bug 3785] New: RotatePointAroundVector() optimization

bugzilla-daemon at icculus.org bugzilla-daemon at icculus.org
Sat Sep 20 07:04:28 EDT 2008

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

Summary: RotatePointAroundVector() optimization
Product: Quake 3
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 s;

VectorScale(dir, s, q);
}

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)