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
Friday, 23 January 2009
Wednesday, 21 January 2009
1- The first one: bright, clean and really useful
Have I told you that my area of expertise is Computer Graphics? Well, now you know.
So, for that matter, our first algorithm should be CG related. I've chosen one that everybody can ascertain its existence. May I present you the Line Drawing Bresenham's Algorithm.
Given 2 points in a discrete plane, this algorithm draws a line connecting these two points. Have you ever thought about how the lines are draw in your amazing GUI? Well, it is done by connecting sequential pixels, which is easy if the line is absolutely horizontal or vertical. But if the line has some slope, than we need a line drawing algorithm.
In first place, this algorithm could be used in every computer system today, so even a plant could agree that it is useful (right, I can tell if this algorithm was really used in a raster computer system like the ones implemented Next or X11, but could be it or some variation/evolution. Some graphics cards do implement line drawing algorithms based on the original Bresenham code).
The algorithm is was first written in 1962, and the paper was published in 1965 at IBM Systems Journal. Then, in a world where computing power was very very expensive, floating point calculations were yet more expensive (no, no hardware acceleration kids), and the work had to get done, this algorithm came to be perfect.
It is great cause avoid floating point calculations, multiplications and fractions. So, using just addition and subtraction with integer numbers (some implementations use bit shift to accomplish integer multiplication/division by 2, which is fast even on simple processors) the algorithm is also really fast. It works trying to draw the perfect line by finding the next pixel to draw. As more the one pixel can be chosen, the algorithm select the best by attributing errors to each option. The one pixel with the best error value is next in the line.
I have coded myself this algorithm during my Bachelors, but of course I have not this code anymore. Wikipedia has an implementation here that, to me, looks correct. Also the original (first implementation) can be found here, and the paper here.
With all of theses positive points, our number one take leave of our presence, thank you and say to wait for the next one in the line.
References: Jack E. Bresenham, Algorithm for Computer Control of a Digital Plotter, IBM Systems Journal, 4(1):25-30, 1965. On-line at http://researchweb.watson.ibm.com/journal/sj/041/ibmsjIVRIC.pdf
Reprinted in Interactive Computer Graphics, Herbert Freeman ed., 1980, and Seminal Graphics: Pioneering Efforts That Shaped The Field, Rosalee Wolfe ed., ACM SIGGRAPH, 1998.
So, for that matter, our first algorithm should be CG related. I've chosen one that everybody can ascertain its existence. May I present you the Line Drawing Bresenham's Algorithm.
Given 2 points in a discrete plane, this algorithm draws a line connecting these two points. Have you ever thought about how the lines are draw in your amazing GUI? Well, it is done by connecting sequential pixels, which is easy if the line is absolutely horizontal or vertical. But if the line has some slope, than we need a line drawing algorithm.
In first place, this algorithm could be used in every computer system today, so even a plant could agree that it is useful (right, I can tell if this algorithm was really used in a raster computer system like the ones implemented Next or X11, but could be it or some variation/evolution. Some graphics cards do implement line drawing algorithms based on the original Bresenham code).
The algorithm is was first written in 1962, and the paper was published in 1965 at IBM Systems Journal. Then, in a world where computing power was very very expensive, floating point calculations were yet more expensive (no, no hardware acceleration kids), and the work had to get done, this algorithm came to be perfect.
It is great cause avoid floating point calculations, multiplications and fractions. So, using just addition and subtraction with integer numbers (some implementations use bit shift to accomplish integer multiplication/division by 2, which is fast even on simple processors) the algorithm is also really fast. It works trying to draw the perfect line by finding the next pixel to draw. As more the one pixel can be chosen, the algorithm select the best by attributing errors to each option. The one pixel with the best error value is next in the line.
I have coded myself this algorithm during my Bachelors, but of course I have not this code anymore. Wikipedia has an implementation here that, to me, looks correct. Also the original (first implementation) can be found here, and the paper here.
With all of theses positive points, our number one take leave of our presence, thank you and say to wait for the next one in the line.
References: Jack E. Bresenham, Algorithm for Computer Control of a Digital Plotter, IBM Systems Journal, 4(1):25-30, 1965. On-line at http://researchweb.watson.ibm.com/journal/sj/041/ibmsjIVRIC.pdf
Reprinted in Interactive Computer Graphics, Herbert Freeman ed., 1980, and Seminal Graphics: Pioneering Efforts That Shaped The Field, Rosalee Wolfe ed., ACM SIGGRAPH, 1998.
Subscribe to:
Posts (Atom)