I've asked Karl if he can help simplify the algorithm like he did before (to remove the sin/cos stuff) - the extra speed boost would be so welcome...
OK people, here we go:
simplifying your formulae on multiplying the angles by whatever integer. I have to admit I'm a little bit astonished about the fact that people who want to learn (or freshen up) multidimensional calculus by reading a book over the weekend don't seem to know about Euler's Formula or the Binomial Theorem. These (and the definition of tan() from sin() and cos()
)are all that is needed to get rid of the trigonometric functions for every integer you may choose to multiply your angles by, and you will always have just polynomials in x,y and z, and the occasional sqrt(x^2+y^2). Minor drawback: these polynomials are getting more complicated the higher your "exponent" becomes, so there will be an exponent where working WITH trigonometric functions will be FASTER than with these polynomials; WHICH exponent that is probably depends on your math-library/processor, and I will NOT try to find it...
Suggested reading:
http://en.wikipedia.org/wiki/Euler%27s_formulahttp://en.wikipedia.org/wiki/Binomial_theoremhttp://en.wikipedia.org/wiki/Binomial_coefficientThe general argument works like this:
Euler's formula states that for any real number f
exp( i*f ) = cos(f)+i*sin(f) ( i being sqrt(-1), of course )
Now, if you take an integer (say "n") multiple of f, you get (reversing the order)
cos(n*f) + i*sin(n*f) = exp( i*n*f )
The right side is, since it IS the exponential function, equal to (exp(i*f))^n !
So:
cos(n*f) + i*sin(n*f) = exp( i*n*f ) = (exp(i*f))^n = (cos(f)+i*sin(f))^n
(last equation comes from substituting the first one again)
By using the Binomial Theorem we expand
(cos(f)+i*sin(f))^n = Sum( k=0 to n, C(n,k)*cos(f)^k*i^(n-k)*sin(f)^(n-k) )
C(n,k) being the Binomial Coefficents
Remembering i^2 = -1 this sum can be sorted into real and imaginary parts, and we end with polynomial expressions for
cos(n*f) = real( Sum( k=0 to n, C(n,k)*cos(f)^k*i^(n-k)*sin(f)^(n-k) ) )
sin(n*f) = imag( Sum( k=0 to n, C(n,k)*cos(f)^k*i^(n-k)*sin(f)^(n-k) ) )
For shorter lines, I will write "F" (think "phi") instead of "zang", and "T" (think "theta") instead of "yang", if you don't mind...
We have
(old)x = r*cos(F)*sin(T)
(old)y = r*sin(F)*sin(T)
(old)z = r*cos(T)
and we want
newx = r^n*cos(n*F)*sin(n*T)
newy = r^n*sin(n*F)*sin(n*T)
newz = r^n*cos(n*T)
If we would insert the general expressions for sines and cosines of n*F and n*T here, everything becomes lengthy, so it is probably best to argue by example: LET n = 3:
Pascal's triangle states the relevant binomial coefficients are 1,3,3 and 1
(see example on the wikipedia page mentioned above):
(a+b)^3 = a^3 + 3*a^2*b + 3*a*b^2 + b^3, thus
( cos(f) + i*sin(f) )^3 =
cos(f)^3 + 3*cos(f)^2*i*sin(f) + 3*cos(f)*(i*sin(f))^2 + (i*sin(f))^3
remember that i^2 = -1, thus i^3 = -i, sort into real and imaginary parts and find
a) for the real part: cos(3*f) = cos(f)^3 - 3*cos(f)*sin(f)^2
b) for the imaginary part: sin(3*f) = 3*cos(f)^2*sin(f) - sin(f)^3
so we have:
newx = r^3 * (cos(F)^3 - 3*cos(F)*sin(F)^2) * (3*cos(T)^2*sin(T) - sin(T)^3)
newy = r^3 * (3*cos(F)^2*sin(F) - sin(F)^3) * (3*cos(T)^2*sin(T) - sin(T)^3)
newz = r^3 * (cos(T)^3 - 3*cos(T)*sin(T)^2)
"newz" seems most simple, relatively speaking. Let's factor out cos(T)^3, and remember the definition of the tan():
newz = r^3 * cos(T)^3 * ( 1 - 3*tan(T)^2 )
but remember:
1) r^3*cos(T)^3 = z^3 !
2) tan(T) = sqrt(x^2+y^2)/z
thus newz = z^3 * ( 1 - 3*(x^2+y^2)/z^2 ) = z * ( z^2 - 3*x^2 - 3*y^2 )
This can be done for EVERY exponent; you can always factor out cos(T)^n from newz and are left with z^n and a polynomial in tan(T), which can be expressed in x,y,z using formula "2" above.
For newx, we factor out sin(T)^3 from the second bracket and get
newx = r^3 * sin(T)^3 * (cos(F)^3 - 3*cos(F)*sin(F)^2) * (3*tan(T)^-2 - 1 )
now, one "r", one "sin(T)", and one of the factors in the first bracket always combine to an old coordinate, and tan(T)^-2 = z^2/(x^2+y^2), so
newx = ( x^3 - 3*x*y^2 ) * ( 3*z^2 - x^2 - y^2 ) / ( x^2+y^2 )
by the same arguments:
newy = ( 3*x^2*y - y^3) * ( 3*z^2 - x^2 - y^2 ) / ( x^2+y^2 )
This can in principle be done for every exponent, too; you always factor out sin(T)^n from the second bracket, than you combine one "r", one "sin(T)" with a cos(F) from the first bracket into x, or with a sin(F) from the first bracket into y; and the second bracket is a polynomial in ( z/sqrt(x^2+y^2) )
Minor drawback again, more explicitly: each of these brackets has, in the general case for "exponent" n, exacly (n+1) summands, as per Binomial Theorem. I personally would not want to find the closed expressions as above for, say, n>8 or so, and definitely NOT for n=32. I am quite sure that, even if one would use one of those symbolic algebra thingies to find the correct polynomials, for n=32 using the trigonometric functions will be faster, since these polynomials are of order n (=32), all of them!
I hope this was helpful.
I hope I didn't step on anyones toes (too heavily
).
Any grammatical errors or strange english formulations are due to me being german, but the math SHOULD be sound!
Have fun
Karl