## Taking advantage of the Symmetry of a Circle in Computer Graphics

Eh, late na pero sayang effort kaya sige na lang

If you were to create a program in that draws circle pixel by pixel, what would you do? Well, you can use this equation to get the points of a circle of radius $r$ and centered at $(h,k)$ as basis:

$r^2 = (x-h)^2 + (y-k)^2$

Or, if we compute for $y$:

$y = k \pm \sqrt{r^2 - (x-h)^2}$

Let’s try drawing a circle using C++11, OpenGL, and freeglut. We will use this as the template of our program. Note that we will be using GL_POINTS to represent pixels.

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 #include #include #include #include #include #define MAX_FRAMES 100000000 #define WIN_HEIGHT 720 #define WIN_WIDTH 720 using namespace std; struct Point{ int x; int y; Point(int x_0, int y_0): x(x_0), y(y_0) {}; }; struct Color{ float r; float g; float b; Color(float r_0, float g_0, float b_0): r(r_0), g(g_0), b(b_0) {}; }; typedef struct Point Point; typedef struct Color Color; int r = 350; int x; int y; bool running = false; vector points; Color black(0.0f, 0.0f, 0.0f); Color red(1.0f, 0.0f, 0.0f); // Integer Square root int int_sqrt(int num){ int res = 0; int bit = 1ul << 30; while (bit != 0){ if( num >= res + bit ){ num -= res + bit; res = (res >> 1) + bit; } else res >>= 1; bit >>= 2; } return res; } void clear_points(){ for(Point *p : points) delete p; points.clear(); } void reset_circle(){ // Reset circle code here } void draw_point(Point *p, Color *c){ glBegin(GL_POINTS); glColor3f(c->r, c->g, c->b); glVertex2i(p->x, p->y); glEnd(); } // Draw circle void draw_circle(){ // Draw circle code here } void init(){ glClearColor(1.0f,1.0f,1.0f,0.0f); glMatrixMode(GL_PROJECTION); gluOrtho2D(0.0f, float(WIN_WIDTH), 0.0f, float(WIN_HEIGHT)); } void mouse_action(int button, int m_state, int m_x, int m_y){ if (button == GLUT_LEFT_BUTTON && m_state == GLUT_DOWN) running = !running; else if(button == GLUT_RIGHT_BUTTON && m_state == GLUT_DOWN) reset_circle(); } void keyboard_action(unsigned char key, int x, int y){ switch(key) { case ' ': running = !running; break; } } int main(int argc , char **argv){ // init GLUT and Create Window glutInit(&argc, argv); glutInitDisplayMode(GLUT_DOUBLE | GLUT_RGB); glutSetOption(GLUT_ACTION_ON_WINDOW_CLOSE, GLUT_ACTION_CONTINUE_EXECUTION); glutInitWindowSize(WIN_WIDTH,WIN_HEIGHT); glutCreateWindow("Circle"); reset_circle(); init(); glutMouseFunc(mouse_action); glutKeyboardFunc(keyboard_action); glutDisplayFunc(draw_circle); glutIdleFunc(draw_circle); glutMainLoop(); cout << "Cleaning up..." << endl; clear_points(); return 0; } 

Let’s try a direct implementation of the equation.

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 void reset_circle(){ x = -r; y = 0; clear_points(); } // Draw circle void draw_circle(){ int h = WIN_WIDTH/2; int k = WIN_HEIGHT/2; glClear(GL_COLOR_BUFFER_BIT); glPointSize(5.0f); for(Point *point : points){ draw_point(point, &black); } if(x <= r && running){ y = int_sqrt((r*r) - (x*x)); Point *new_point = new Point(h + x, k + y); draw_point(new_point, &red); points.push_back(new_point); new_point = new Point(h + x, k - y); draw_point(new_point, &red); points.push_back(new_point); x++; } if( x > r) reset_circle(); glutSwapBuffers(); } 

This would be the resulting render.

Not quite a circle yet and on top of that slow, but why isn’t the produced render a complete circle? Remember that we only computed the integer parts of the equation and as such, in the areas with enough slope, one pixel won’t be enough to fill that area. Why not use floats then? Remember that pixels are discrete and not dimensionless and on top of that computing the floats part would add more multiplication and square root computations, both of which are relatively heavy operations, to our program. So what can we do? For now, let’ improve our program.

Note that a circle is highly symmetrical, so let’s try to compute 4 points at once instead of just 2 and see what happens.

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 void reset_circle(){ x = 0; y = 0; clear_points(); } // Draw circle void draw_circle(){ int h = WIN_WIDTH/2; int k = WIN_HEIGHT/2; glClear(GL_COLOR_BUFFER_BIT); glPointSize(5.0f); for(Point *point : points){ draw_point(point, &black); } if(x <= r && running){ y = int_sqrt((r*r) - (x*x)); Point *new_point = new Point(h + x, k + y); draw_point(new_point, &red); points.push_back(new_point); new_point = new Point(h + x, k - y); draw_point(new_point, &red); points.push_back(new_point); new_point = new Point(h - x, k + y); draw_point(new_point, &red); points.push_back(new_point); new_point = new Point(h - x, k - y); draw_point(new_point, &red); points.push_back(new_point); x++; } if( x > r) reset_circle(); glutSwapBuffers(); }

This is the resulting render:

Faster but we still have discontinuities on the left and right side. Let’s improve our code further by computing 8 points at once, this time we add the left and right sides as starting points.

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 void reset_circle(){ x = 0; y = r; clear_points(); } // Draw circle void draw_circle(){ int h = WIN_WIDTH/2; int k = WIN_HEIGHT/2; glClear(GL_COLOR_BUFFER_BIT); glPointSize(5.0f); for(Point *point : points){ draw_point(point, &black); } if( x <= y && running ){ Point *new_point = new Point(h + x, k + y); draw_point(new_point, &red); points.push_back(new_point); new_point = new Point(h + x, k - y); draw_point(new_point, &red); points.push_back(new_point); new_point = new Point(h - x, k + y); draw_point(new_point, &red); points.push_back(new_point); new_point = new Point(h - x, k - y); draw_point(new_point, &red); points.push_back(new_point); new_point = new Point(h + y, k + x); draw_point(new_point, &red); points.push_back(new_point); new_point = new Point(h + y, k - x); draw_point(new_point, &red); points.push_back(new_point); new_point = new Point(h - y, k + x); draw_point(new_point, &red); points.push_back(new_point); new_point = new Point(h - y, k - x); draw_point(new_point, &red); points.push_back(new_point); x++; y = int_sqrt((r*r) - (x*x)); } if( x >= y) reset_circle(); glutSwapBuffers(); } 

The resulting render:

FINALLY! We have a full circle.

The last code is actually a simplified implementation of the Midpoint circle algorithm, an algorithm that takes advantage of a circle’s symmetry in order to render it fast. This implementation still uses square root and multiplication operations. Actual implementations implements the algorithm such that no multiplication or square root operations are done.

Source code