Transformations - Transformations and Projections in Computer Graphics - page 20

by a 16-bit integer sine value yields a 32-bit product. The right shift effectively divides
the product by 2 14 =16 , 384, a necessary operation because our integer sine values have
been premultiplied by this scale factor.

Exercise 1.27: Use this method to calculate the results of rotating point (1 , 2) by 60 ◦
and by 80 ◦ . Ineachcase,comparetheresultswiththoseobtainedwhenbuilt-insine
and cosine functions are used.

1.2.4 CORDIC Rotations
We routinely use calculators to compute values of common functions, but have you ever
wondered how a calculator determines the value of, say, tan 72 . 81 ◦ so fast? Many cal-
culators use CORDIC (COordinate Rotation, DIgital Computer), a general method for
computing many elementary functions. CORDIC was originally proposed by [Volder 59]
and was extended by [Walther 71]. The original references are hard to find but are in-
cluded in [Swartzlander 90]. Here, we show how CORDIC can be used to implement
fast rotations.
It is su cient to consider a rotation about the origin where the rotation angle θ is in
the interval [0 , 90 ◦ ) (the first quadrant). The special case θ =90 ◦ can be implemented
by the negate and exchange rule [Equation (1.6)]. Rotations in other quadrants can be
achieved by a first-quadrant rotation, followed by a reflection.
The rotation is expressed by [see Equation (1.4)]
( x ∗ ,y ∗ )=( x, y ) cos θ

.

− sin θ

(1.17)

sin θ cos θ

Because θ is less than 90 ◦ ,weknowthatcos θ is nonzero, so we can factor out cos θ ,
yielding

.
We now express θ as the sum i =0 θ i , where angles θ i are defined by the relation
tan θ i =2 −i

( x ∗ ,y ∗ )=cos θ ( x, y ) 1

− tan θ

tan θ 1

def =arctan(2 −i ). The first 16 θ i ,for i =0 , 1 ,..., 15, are listed in

or θ i

Table 1.11.
In order to express any angle θ as the sum of these particular θ i ,some θ i will have
to be subtracted. Consider, for example, θ =58 ◦ . We start with θ 0 =45 ◦ .Since θ 0 <θ ,
we add θ 1 .Thesum θ 0 + θ 1 =45+26 . 5651 = 71 . 5651 is greater than θ , so we subtract
θ 2 . The new sum, 57.5289, is less than θ ,soweadd θ 3 ,andsoon.

Exercise 1.28: We want to be able to express any angle θ in the range [0 ◦ , 90 ◦ )by
adding and subtracting a number of consecutive θ i ,from θ 0 to some θ m , without skipping
any θ i in between. Is that possible?
It is easy to write a program that decides which of the θ i 's should be added and
which should be subtracted. Thus, we end up with

m m

d i arctan(2 −i ) , θ = d i θ i = where d i = ± 1 .

i =0 i =0