Drawing Antialiased Circles and Ellipses

posted December 1, 2011 by Stephan Brumme

Fast But Ugly

PHP's GD image library can draw all kinds of circles and ellipses. But they look rather ugly because they lack proper antialiasing:

Standard

Aside from GD image handling stuff, it's a single line of code:


     imageellipse($img, $width/2,$height/2, $width,$height, $color);

The image above was created by the following PHP file (click show):

show PHP's built-in imageellipse


     <?php
       $start = microtime(true);
     
       // default size
       $width  = 150;
       $height = 100;
       // ... or user defined
       if (is_numeric($_REQUEST["width" ])) $width  = $_REQUEST["width" ];
       if (is_numeric($_REQUEST["height"])) $height = $_REQUEST["height"];
     
       // create new image
       $img = imagecreatetruecolor($width, $height);
     
       // transparent background
       $background = imagecolorallocate($img, 0xFF, 0xFF, 0xFF);
       imagefilledrectangle ($img, 0,0, $width,$height, $background);
       imagecolortransparent($img, $background);
     
       // draw red ellipse, 2*10px border
       $red = imagecolorallocate($img, 0xFF, 0x00, 0x00);
       imageellipse($img, $width/2,$height/2, $width-20,$height-20, $red);
     
       // measure speed
       $end = microtime(true);
       $duration = number_format(($end - $start)*1000, 3)."ms";
       imagestring($img, 1, $width-50,$height-10, $duration, 0);
     
       // send PNG to browser
       header("Content-type: image/png");
       imagepng($img, NULL, 9, PNG_ALL_FILTERS);
     ?>

This article will show five ways how to add antialiasing to circles/ellipses:

Algorithm	Quality	Speed	Code Size
`imageellipse`	bad	very fast	one line
Zooming Trick	okay	very slow	about 10 lines
Polygon Approximation	depends	fast	about 10 lines
Implicit Equation	good	very slow	about 20 lines
Wu's Algorithm	good	slow	about 30 lines
True-Type Font	depends	fast	about 10 lines

All images on this page are drawn on-the-fly. Rendering time (in milliseconds) is displayed in the lower right corner and will be different if you reload.

The Zooming Trick

The image can drawn at a higher resolution and then downsampled to the final size with a blurry filter.
For example, everything is drawn at twice the resolution and then imagecopyresampled applied. The higher the scaling factor, the better the image quality. From 2x2 to 4x4 (only integer values possible):

Zoomed and Downsampled 2x

However, a few tricky workarounds are required to get the desired result. First, the circle's line width is 1 pixel by default but it has to be changed - otherwise after downsampling the circle's border would look very thin (assuming $scale to be the zoom factor):


     imagesetthickness($img, $scale);

Oops, it doesn't work ... the image isn't affected at all.
To me it seems like a bug that imageellipse doesn't care about imagesetthickness. If we replace it by an arc (imagearc) that is almost an ellipse, then everything works as expected.
Strangely, you cannot draw an arc from 0 to 360 degrees because then the GD library falls back to imageellipse. Therefore the best we can do is an arc from 0 to 359.999. If you look closely you might notice a small white gap on the right side of each ellipse (at 3 o'clock position).

The basic idea looks like this:

hide


     $scale = 2.0;
     $zoomWidth  = $width  * $scale;
     $zoomHeight = $height * $scale;
     // draw
     imagesetthickness($img, $scale);
     imagearc($img, $zoomWidth/2,$zoomHeight/2, $zoomWidth-20*$scale,$zoomHeight-20*$scale, 0, 359.99, $color);
     // downsampling
     $img2 = imagecreatetruecolor($width, $height);
     imagecopyresampled($img2, $img, 0,0, 0,0, $width,$height, $zoomWidth,$zoomHeight);
     // and then output $img2 instead of $img
     // ...

Full code (click show):

show Zooming Technique


     <?php
       $start = microtime(true);
     
       // default size
       $width  = 150;
       $height = 100;
       $scale  = 2.0;
       // ... or user defined
       if (is_numeric($_REQUEST["width" ])) $width  = $_REQUEST["width" ];
       if (is_numeric($_REQUEST["height"])) $height = $_REQUEST["height"];
       if (is_numeric($_REQUEST["scale" ])) $scale  = $_REQUEST["scale" ];
     
       // enlarge
       $zoomWidth  = $width  * $scale;
       $zoomHeight = $height * $scale;
     
       // create new image
       $img = imagecreatetruecolor($zoomWidth, $zoomHeight);
     
       // transparent background
       $background = imagecolorallocate($img, 0xFF, 0xFF, 0xFF);
       imagefilledrectangle ($img, 0,0, $zoomWidth,$zoomHeight, $background);
       imagecolortransparent($img, $background);
     
       // draw red ellipse, 2*10px border
       $red = imagecolorallocate($img, 0xFF, 0x00, 0x00);
       imagesetthickness($img, $scale);
       imagearc($img, $zoomWidth/2,$zoomHeight/2, $zoomWidth-20*$scale,$zoomHeight-20*$scale, 0, 359.999, $red);
     
       // downsampling
       $img2 = imagecreatetruecolor($width, $height);
       imagecopyresampled($img2, $img, 0,0, 0,0, $width,$height, $zoomWidth,$zoomHeight);
     
       // measure speed
       $end = microtime(true);
       $duration = number_format(($end - $start)*1000, 3)."ms";
       imagestring($img, 1, $width-50,$height-10, $duration, 0);
     
       // measure speed
       $end = microtime(true);
       $duration = number_format(($end - $start)*1000, 3)."ms";
       imagestring($img2, 1, $width-50,$height-10, $duration, 0);
     
       // send PNG to browser
       header("Content-type: image/png");
       imagepng($img2, NULL, 9, PNG_ALL_FILTERS);
     ?>

Polygon Approximation

Every circle can be approximated by a sufficiently high number of lines. Antialiased line drawing is natively supported by PHP/GD, the same is valid for polygons. These three ellipses are in fact polygons with 10, 50 and 500 lines.

10-sided Polygon

I thought that increasing the number of lines (or better let's call them sides) will always be better. But there is certain threshold, depending on the circle's size, where antialiasing fails due to too small side length. I cannot give you a formula when that happens but I suggest keeping each side at least 2 pixels long.

My sides' lengths vary because I chose a very simple algorithm - better ones exist but they are much more complex. Nevertheless, my code is a strechted circle, based on sin and cos:

hide


     $sections = 50;
     $centerX = $width /2; $radiusX = ($width -20) /2;
     $centerY = $height/2; $radiusY = ($height-20) /2;
     $points = array();
     for ($i = 0; $i < $sections; $i++)
     {
       $angle = 2*pi()*$i/$sections;
       $points[] = $centerX + $radiusX * cos($angle);
       $points[] = $centerY + $radiusY * sin($angle);
     }
     imageantialias($img, true);
     imagepolygon($img, $points, $sections, $red);

Full code (click show):

show Antialiased Polygon


     <?php
       $start = microtime(true);
     
       // default size
       $width  = 150;
       $height = 100;
       $sections = min($width, $height);
       // ... or user defined
       if (is_numeric($_REQUEST["width"   ])) $width    = $_REQUEST["width"   ];
       if (is_numeric($_REQUEST["height"  ])) $height   = $_REQUEST["height"  ];
       if (is_numeric($_REQUEST["sections"])) $sections = $_REQUEST["sections"];
     
       // create new image
       $img = imagecreatetruecolor($width, $height);
     
       // transparent background
       $background = imagecolorallocate($img, 0xFF, 0xFF, 0xFF);
       imagefilledrectangle ($img, 0,0, $width,$height, $background);
       imagecolortransparent($img, $background);
     
       // draw red ellipse, 2*10px border
       $red = imagecolorallocate($img, 0xFF, 0x00, 0x00);
       $centerX = $width /2; $radiusX = ($width -20) /2;
       $centerY = $height/2; $radiusY = ($height-20) /2;
       $points = array();
       for ($i = 0; $i < $sections; $i++)
       {
         $angle = 2*pi()*$i/$sections;
         $points[] = $centerX + $radiusX * cos($angle);
         $points[] = $centerY + $radiusY * sin($angle);
       }
       imageantialias($img, true);
       imagepolygon($img, $points, $sections, $red);
     
       // measure speed
       $end = microtime(true);
       $duration = number_format(($end - $start)*1000, 3)."ms";
       imagestring($img, 1, $width-50,$height-10, $duration, 0);
     
       // send PNG to browser
       header("Content-type: image/png");
       imagepng($img, NULL, 9, PNG_ALL_FILTERS);
     ?>

Implicit Equation

An ellipses is mathematically defined as x*x/a*a + y*y/b*b = 1 where a and b are the smallest and biggest radius, i.e. a = width/2 and b = height/2.

Implicit Equation

For each pixel we can compute x*x/a*a + y*y/b*b. If it's sufficiently close to 1, then the border was reached and the pixel is drawn. A simple approximation for a one-pixel-wide border is:


     $thickness = 1 / min($a, $b);

I prefer 1.5 instead of 1 because that's visually more pleasant.
The rendering code runs a little bit faster when the inner loop is aborted as soon as we are outside the ellipse (line 9):

hide


     for ($x = 0; $x <= $a+1; $x++)
       for ($y = 0; $y <= $b+1; $y++)
       {
         // implicit formula: 1 = $x*$x/($a*$a) + $y*$y/($b*$b)
         $one = $x*$x/($a*$a) + $y*$y/($b*$b);
         $error = ($one - 1) / $thickness;
     
         // outside ?
         if ($error > 1)
           break;
         // inside ?
         if ($error < -1)
           continue;
     
         // draw border
         $transparency = round(abs($error) * $maxTransparency);
         $alpha        = $color | ($transparency << 24);
         imagesetpixel($img, $centerX+$x, $centerY+$y, $alpha);
         imagesetpixel($img, $centerX-$x, $centerY+$y, $alpha);
         imagesetpixel($img, $centerX-$x, $centerY-$y, $alpha);
         imagesetpixel($img, $centerX+$x, $centerY-$y, $alpha);
       }

Full code (click show):

show Implicit Algorithm


     <?php
       $start = microtime(true);
     
       // default size
       $width  = 150;
       $height = 100;
       // ... or user defined
       if (is_numeric($_REQUEST["width" ])) $width  = $_REQUEST["width" ];
       if (is_numeric($_REQUEST["height"])) $height = $_REQUEST["height"];
     
       // create new image
       $img = imagecreatetruecolor($width, $height);
     
       // transparent background
       $background = imagecolorallocate($img, 0xFF, 0xFF, 0xFF);
       imagefilledrectangle ($img, 0,0, $width,$height, $background);
       imagecolortransparent($img, $background);
     
       // draw red ellipse, 2*10px border
       $color = imagecolorallocatealpha($img, 0xFF, 0x00, 0x00, 0x00);
       $centerX =  $width  / 2;
       $centerY =  $height / 2;
       $a       = ($width  - 20) / 2;
       $b       = ($height - 20) / 2;
       $thickness = 1.5 / min($a, $b);
       $maxTransparency = 0x7F; // 127
       for ($x = 0; $x <= $a+1; $x++)
         for ($y = 0; $y <= $b+1; $y++)
         {
           // implicit formula: 1 = $x*$x/($a*$a) + $y*$y/($b*$b)
           $one = $x*$x/($a*$a) + $y*$y/($b*$b);
           $error = ($one - 1) / $thickness;
     
           // outside ?
           if ($error > 1)
             break;
           // inside ?
           if ($error < -1)
             continue;
     
           // draw border
           $transparency = round(abs($error) * $maxTransparency);
           $alpha        = $color | ($transparency << 24);
           imagesetpixel($img, $centerX+$x, $centerY+$y, $alpha);
           imagesetpixel($img, $centerX-$x, $centerY+$y, $alpha);
           imagesetpixel($img, $centerX-$x, $centerY-$y, $alpha);
           imagesetpixel($img, $centerX+$x, $centerY-$y, $alpha);
         }
     
       // measure speed
       $end = microtime(true);
       $duration = number_format(($end - $start)*1000, 3)."ms";
       imagestring($img, 1, $width-50,$height-10, $duration, 0);
     
       // send PNG to browser
       header("Content-type: image/png");
       imagepng($img, NULL, 9, PNG_ALL_FILTERS);
     ?>

Wu's Algorithm

Xiaolin Wu presented an antialiased circle drawing algorithm in the book Graphics Gems II. Slightly modified it can draw ellipses, too.
It's slower than most other approaches (except for Implicit Equation) but yields the best image quality:

Wu's Algorithm

It subdivides the ellipse into eight regions: 0 to 45 degrees, 45 to 90, 90 to 135, ..., 315 to 360 degrees. We only have to compute the first two of these eight regions and can derive the other six by mirroring:

hide


     function setpixel4($img, $centerX, $centerY, $deltaX, $deltaY, $color)
     {
       imagesetpixel($img, $centerX + $deltaX, $centerY + $deltaY, $color);
       imagesetpixel($img, $centerX - $deltaX, $centerY + $deltaY, $color);
       imagesetpixel($img, $centerX + $deltaX, $centerY - $deltaY, $color);
       imagesetpixel($img, $centerX - $deltaX, $centerY - $deltaY, $color);
     }

I don't want to dissect the mathematics (take a look here if you're curious) and just show the code:

hide


     $radiusX2 = $radiusX * $radiusX;
     $radiusY2 = $radiusY * $radiusY;
     static $maxTransparency = 0x7F; // 127
     // upper and lower halves
     $quarter = round($radiusX2 / sqrt($radiusX2 + $radiusY2));
     for ($x = 0; $x <= $quarter; $x++)
     {
       $y = $radiusY * sqrt(1-$x*$x/$radiusX2);
       $error = $y - floor($y);
     
       $transparency = round($error * $maxTransparency);
       $alpha  = $color | ($transparency << 24);
       $alpha2 = $color | (($maxTransparency - $transparency) << 24);
     
       setpixel4($img, $centerX, $centerY, $x, floor($y),   $alpha);
       setpixel4($img, $centerX, $centerY, $x, floor($y)+1, $alpha2);
     }
     // right and left halves
     $quarter = round($radiusY2 / sqrt($radiusX2 + $radiusY2));
     for ($y = 0; $y <= $quarter; $y++)
     {
       $x = $radiusX * sqrt(1-$y*$y/$radiusY2);
       $error = $x - floor($x);
     
       $transparency = round($error * $maxTransparency);
       $alpha  = $color | ($transparency << 24);
       $alpha2 = $color | (($maxTransparency - $transparency) << 24);
     
       setpixel4($img, $centerX, $centerY, floor($x),   $y, $alpha);
       setpixel4($img, $centerX, $centerY, floor($x)+1, $y, $alpha2);
     }

Full code (click show):

show Wu's Algorithm


     <?php
       $start = microtime(true);
     
       // default size
       $width  = 150;
       $height = 100;
       // ... or user defined
       if (is_numeric($_REQUEST["width"   ])) $width    = $_REQUEST["width"   ];
       if (is_numeric($_REQUEST["height"  ])) $height   = $_REQUEST["height"  ];
     
       // create new image
       $img = imagecreatetruecolor($width, $height);
     
       // transparent background
       $background = imagecolorallocate($img, 0xFF, 0xFF, 0xFF);
       imagefilledrectangle ($img, 0,0, $width,$height, $background);
       imagecolortransparent($img, $background);
     
       // helper function, draws pixel and mirrors it
       function setpixel4($img, $centerX, $centerY, $deltaX, $deltaY, $color)
       {
         imagesetpixel($img, $centerX + $deltaX, $centerY + $deltaY, $color);
         imagesetpixel($img, $centerX - $deltaX, $centerY + $deltaY, $color);
         imagesetpixel($img, $centerX + $deltaX, $centerY - $deltaY, $color);
         imagesetpixel($img, $centerX - $deltaX, $centerY - $deltaY, $color);
       }
     
       // red ellipse, 2*10px border
       $color = imagecolorallocate($img, 0xFF, 0x00, 0x00);
       $centerX = $width /2; $radiusX = ($width -20) / 2;
       $centerY = $height/2; $radiusY = ($height-20) / 2;
       static $maxTransparency = 0x7F; // 127
     
       $radiusX2 = $radiusX * $radiusX;
       $radiusY2 = $radiusY * $radiusY;
       // upper and lower halves
       $quarter = round($radiusX2 / sqrt($radiusX2 + $radiusY2));
       for ($x = 0; $x <= $quarter; $x++)
       {
         $y = $radiusY * sqrt(1-$x*$x/$radiusX2);
         $error = $y - floor($y);
     
         $transparency = round($error * $maxTransparency);
         $alpha  = $color | ($transparency << 24);
         $alpha2 = $color | (($maxTransparency - $transparency) << 24);
     
         setpixel4($img, $centerX, $centerY, $x, floor($y),   $alpha);
         setpixel4($img, $centerX, $centerY, $x, floor($y)+1, $alpha2);
       }
       // right and left halves
       $quarter = round($radiusY2 / sqrt($radiusX2 + $radiusY2));
       for ($y = 0; $y <= $quarter; $y++)
       {
         $x = $radiusX * sqrt(1-$y*$y/$radiusY2);
         $error = $x - floor($x);
     
         $transparency = round($error * $maxTransparency);
         $alpha  = $color | ($transparency << 24);
         $alpha2 = $color | (($maxTransparency - $transparency) << 24);
     
         setpixel4($img, $centerX, $centerY, floor($x),   $y, $alpha);
         setpixel4($img, $centerX, $centerY, floor($x)+1, $y, $alpha2);
       }
     
       // measure speed
       $end = microtime(true);
       $duration = number_format(($end - $start)*1000, 3)."ms";
       imagestring($img, 1, $width-50,$height-10, $duration, 0);
     
       // send PNG to browser
       header("Content-type: image/png");
       imagepng($img, NULL, 9, PNG_ALL_FILTERS);
     ?>

Faking Circles With A True-Type Font

Recently I became aware of a neat trick: for some fonts o or 0 look almost like a circle.
Below is the free FashionVictim font from www.nicksfonts.com rendering a large zero:

Wu's Algorithm

The main problem is finding a good font. I recommend www.fontspace.com, it has a good variety of free fonts (some also free for commercial use) and the website comes with a great interactive interface.

hide


     // draw a zero
     $letter = "0";
     $font   = "./FashionVictim.ttf";
     // font size
     $size   = 2*min($width, $height);
     // move to image's center
     $bbox   = imagettfbbox($size, 0, $font, $letter);
     $x      =            $width/2  - abs($bbox[4] - $bbox[0])/2  - $bbox[0];
     $y      = $height - ($height/2 - abs($bbox[5] - $bbox[1])/2) - $bbox[1];
     $color  = imagecolorallocate($img, 0xFF, 0x00, 0x00);
     imagettftext($img, $size, 0, $x,$y, $color, $font, $letter);

Full code (click show):

show Abusing A True-Type Font


     <?php
       $start = microtime(true);
     
       // default size
       $width  = 150;
       $height = 100;
       // ... or user defined
       if (is_numeric($_REQUEST["width" ])) $width    = $_REQUEST["width" ];
       if (is_numeric($_REQUEST["height"])) $height   = $_REQUEST["height"];
     
       // create new image
       $img = imagecreatetruecolor($width, $height);
     
       // transparent background
       $background = imagecolorallocate($img, 0xFF, 0xFF, 0xFF);
       imagefilledrectangle ($img, 0,0, $width,$height, $background);
       imagecolortransparent($img, $background);
     
       // draw a zero
       $letter = "0";
       $font   = "./FashionVictim.ttf";
       // font size
       $size   = 2*min($width, $height);
       // move to image's center
       $bbox   = imagettfbbox($size, 0, $font, $letter);
       $x      =            $width/2  - abs($bbox[4] - $bbox[0])/2  - $bbox[0];
       $y      = $height - ($height/2 - abs($bbox[5] - $bbox[1])/2) - $bbox[1];
       $color  = imagecolorallocate($img, 0xFF, 0x00, 0x00);
       imagettftext($img, $size, 0, $x,$y, $color, $font, $letter);
     
       // measure speed
       $end = microtime(true);
       $duration = number_format(($end - $start)*1000, 3)."ms";
       imagestring($img, 1, $width-50,$height-10, $duration, 0);
     
       // send PNG to browser
       header("Content-type: image/png");
       imagepng($img, NULL, 9, PNG_ALL_FILTERS);
     ?>


June 30, 2021: Length-Limited Prefix Codes April 13, 2020: smalLZ4 - optimal LZ4 compression June 17, 2019: toojpeg - a JPEG encoder in a single C++ file ... and 30 more !	RSS	www.stephan-brumme.com bits.stephan-brumme.com photos.stephan-brumme.com minime.stephan-brumme.com
© 2011-2024 Stephan Brumme products and company names mentioned may be trademarks of their respective owners. see my disclaimer. dude, this is the end ... of this page.