How is it done?
Normally, rotating a vector A(x1, y1) through t radians in order to get vector B(x2, y2) is done with x2 = x1*cos(t) - y1*sin(t), y2 = x1*sin(t) + y1*cos(t).
But trigonometry is expensive, especially without an FPU, so there must be another way.
I was thinking of something similar to Bresenham's circle algorithm, or perhaps reflecting the vector about the origin or something.
So, uh, how would you do it?
Name:
Anonymous2010-07-03 9:38
Tables for sin(t) and cos(t).
Name:
Anonymous2010-07-03 9:40
Lookup tables for trigonometric functions? I think that's how it was done on the GBA.
Name:
Anonymous2010-07-03 9:40
Store vector as angle and length. Use sin and cos tables for conversion to (x,y)
Name:
Anonymous2010-07-03 9:42
In before Xarn.
Name:
Anonymous2010-07-03 9:54
So the consensus is a LUT. Not as elegant as I'd like (I was wondering if there was an alternative when I posted), but very well, thank you all for participating.
>>6
LUTs are extremely elegant. You also won't find anything faster. Two multiplies and two adds for precision you could peel an apple with.
Name:
Anonymous2010-07-03 10:15
>>6 >>9
This pretty much. You can linearly interpolate on a relatively small LUT and get great accuracy for very few cycles. Note that you don't want your LUT to be too large; it's bad for your cache. Besides, do you really care about accuracy that much?
Also just to clarify, LUT is generally used for trig, and trig is used to generate a rotation matrix. So lets say you've got 100 such vectors to rotate, you're best off making an affine transformation matrix and multiplying them through.
>>1 without an FPU
What platform are you coding for?
Name:
Anonymous2010-07-03 11:16
If you don't have an FPU, and you're going to end up on lattice points, you may want to look into continued fractions, which rely pretty much exclusively on integers.
>>17
Off the top of my head I can't determine whether it is cheaper to flub FP math or do a bit of continued fraction arithmetic, and I'm not going to investigate. It is probably cheaper to flub FP, since CF arithmetic is basically matrix multiplication.
Name:
Anonymous2010-07-03 16:34
ITT No one read SICP.
Maybe use a different representation for the vector: length, angle and point of origin. Converting to Cartesian coordinates is cheaper then rotating in the Cartesian coordinate system.
>>18
Hm, what I meant was that I'm quite interested in what lattice points are and how you'd do arithmetic using continued fractions; however, I'm not interested enough to research myself (as I'm quite busy at the moment) and it would be absolutely terrific if I could read a post written by a fellow /prog/rider on this matter. My reaction in >>17 was due to my disappointment that you would refuse my polite request (>>14); however you do have the right to do so and what I said in >>17 was quite ungentlemanly, for which I'm sorry.
>>19 Maybe use a different representation for the vector: length, angle and point of origin.
I think you need to read SICP again.
Name:
Anonymous2010-07-03 16:52
>>23 >>4 suggested a sin and cos of the angle would be needed for conversion but you can do away with a cos of the angle and its complementary.
The definition of the dot product here is your friend.
Look below at "assuming a and b are real". This is the above expression where
z = ai/b.
It is good for about three digits, x.yz, which you don't have if you don't have an FPU, so... yeah.
Long story short: either use an FP library and a lookup table or bust. There's a reason they've been in use forever.
>>32
I don't recall a distinction being established in this thread. Was it the last time you said ``FP'' without clarification? Or the time before that?
>>34
And yet he didn't mention what platform he's working on.
Given the context of the question, the only thing I can guess is that he's working on Android. He knows some devices don't have FPUs, and he thinks his game will be so awesome that softfloats won't cut it for him.