[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
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.
More information about the quake3-bugzilla
mailing list