This is another algorithm well known in the computer graphics world. And it is here because, the same way that drawing straight lines, drawing curved lines is important.
Being said as a variation of Brasenham's algorithm, the midpoint curve drawing algorithm was first described by Pitteway in 1967. Again, it is an old piece of computer science that integrates the graphics circuits until today.
Drawing must be fast ever and the problems found in drawing curves are the same as drawing lines. One could say that it is even harder.
So the curve drawing algorithm is bright cause it uses only integers additions and multiplications (of course you can represent all multiplications as additions) and uses an ingenious strategy to avoid calculations with floating points.
The main idea is to split the circle (actually works for any elliptical shape) in 8 slices, called octants. Each octant represents 45 degrees of a curve. Then, for each octant, there's a point P starting at (x,y) where the drawing will start. The next point is given by the circle equation f(x,y)=x^2 +y^2 - r^2. This is evaluated for each iteration, until the ellipse is completed the direction of the drawing (x and/or y going up or down) is related to the octant and the value of f.
I could not find the original paper for download, but it is available for members of The Computer Journal here. More details on how the algorithm can be implemented can be found in most basic computer graphics books. And of course there is an implementation at wikipedia that seems very nice.
Thank you for your time
No comments:
Post a Comment