Transformations - Transformations and Projections in Computer Graphics - page 21

i i (degrees) θ i (radians) K i

0 45. 0.785398 0.70710678118654746

1 26.5651 0.463648 0.63245553203367577

2 14.0362 0.244979 0.61357199107789628

3 7.12502 0.124355 0.60883391251775243

4 3.57633 0.0624188 0.60764825625616825

5 1.78991 0.0312398 0.60735177014129604

6 0.895174 0.0156237 0.60727764409352614

7 0.447614 0.00781234 0.60725911229889284

8 0.223811 0.00390623 0.60725447933256249

9 0.111906 0.00195312 0.60725332108987529

10 0.0559529 0.000976562 0.60725303152913446

11 0.0279765 0.000488281 0.60725295913894495

12 0.0139882 0.000244141 0.60725294104139727

13 0.00699411 0.00012207 0.60725293651701029

14 0.00349706 0.0000610352 0.60725293538591352

15 0.00174853 0.0000305176 0.60725293510313938

Table 1.11: The First 16 θ i 's and Scale Factors.

Once the number m of necessary d i 's and their values have been determined, we
rotate ( x, y )to( x ∗ ,y ∗ ) in a loop where each iteration rotates a point ( x i ,y i ) through
an angle d i θ i toapoint( x i +1 ,y i +1 ). A general iteration can be expressed in the form

( x i +1 ,y i +1 ) = cos( d i θ i )( x i ,y i ) 1

− tan θ i

tan θ i 1

=cos( d i θ i )( x i ,y i ) 1

d i 2 −i −

d i 2 −i

1

=cos( d i θ i )( x i + y i d i 2 −i ,y i − x i d i 2 −i ) . (1.18)

We interpret the result ( x i +1 ,y i +1 ) of an iteration as the vector from the origin to
point ( x i +1 ,y i +1 ). Equation (1.18) shows that this vector is the product of two terms.
The second term, ( x i + y i d i 2 −i ,y i − x i d i 2 −i ), determines the direction of the vector,

while the first term, cos( d i θ i ), affects only the magnitude of the vector. The second
term is easy to calculate since it just involves shifts. We know that d i is just a sign and
that a product of the form x i 2 −i can be computed by shifting x i i positions to the right.
The problem is to calculate the first term, cos( d i θ i ), and to multiply the two terms.
This is why CORDIC proceeds by first performing all the iterations

( x i + y i d i 2 −i ,y i − x i d i 2 −i ) ( x i +1 ,y i +1 ) ←

using just right shifts and additions/subtractions; the cosine terms are ignored. The
result is a vector that points in the right direction but is too long (Figure 1.13). To