smiller@wet.UUCP (Gregory Shane Miller) (10/29/90)
I'm looking for anybody who has implemented the Hong Toa's circular
DDA as taken from:
Fundamental Algorithms on Graphics
NATO ASI Series F., Volume 17 1985
Published by Spinger-Verlag
I've implemented this algorithm but was unable to reduce any
of the varibles to integers (eg. int or unsigned in C) as the
authour seems to imply in his opening comments.
BTW:
This particular DDA is more accurate than Breshenham's. In fact
the error tends toward zero as the radius tends toward infinity.
Moreover, for those who want a *fast* floating point CDDA this is
it.
------ Exact Problem ------
The algorithm calls for right shifting by a number which is proportional
to the radius. For example with r=50, 9 and 19 are used. So one
might have:
m = n >> 9 where m,n,l are given in the
l = n >> 18 algorithm
Problem: when m,n,l are 16 bit (or even) 32 bit integers, right shifting
by such large numbers leaves m,l almost always equal to zero which causes
all of the interpolation loops to get "stuck". I used float for everything
and simulated the right shift by writing a small ASM function to decrement
the exponent by 9 or 19 (for example) as required. Recall that IEEE format
calls for floating point numbers to have their exponent stored base 2.
While this certainly helps the speed, floating point addition and subtraction
is still required.
-----------------
Any help would very much appreciated. Thanks.
Regards-
smiller@wet.UUCP
--
--
G. Shane Miller [ smiller@wet.UUCP ] Von Neumann eat your heart out!