Hack of the day: Render circles without trigonometry
March 12, 2011
The Bresenham line algorithm avoids trigonometry and uses integer math to calculate the points of a line, circle or ellipse.
Here is a small example (implemented in C++ / SFML):
#include <SFML/Graphics.hpp>
void drawEllipse(sf::RenderWindow &w, int cx, int cy, int r1, int r2) {
sf::Shape point = sf::Shape::Circle(0, 0, 1, sf::Color::White);
int x = -r1, y = 0;
int err = r1 * r1 - (2 * r1 - 1) * r2 * r2, e2;
do {
point.SetPosition(cx - x, cy + y) ; w.Draw(point);
point.SetPosition(cx + x, cy + y) ; w.Draw(point);
point.SetPosition(cx + x, cy - y) ; w.Draw(point);
point.SetPosition(cx - x, cy - y) ; w.Draw(point);
e2 = 2 * err;
if (e2 >= (x * 2 + 1) * r2 * r2)
err += (++x * 2 + 1) * r2 * r2;
if (e2
To learn more about the theory behind the algorithm, please have a look at the Midpoint Circle Algorithm at Wikipedia.
Awesome, its spaghetti code, but awesome !
How much more efficient is this than using standard trig?