Tuesday, October 7, 2008

Xiaolin Wu look like circle

Xiaolin Wu had implement an algorithm to draw fast antialiased lines and circles.

In this post i will consider the circle.

His idea is based on draw the points next to the real circumference. Drawing that points with different intensity so that will be inverse proportion to the distance from the center and the total sum of the intensities will be constant.

The lemma that leads the plot loop is interesting as complex, so i advise you to search others resources, such as "Graphics Gems II" (you can find on google books the description i'm talkin about).

But i thought to change a little Xiaolin Wu's algorithm in this way:

  • I first plot the original circle;
  • I add two points with different intensity to the nearest real one.
It's a very fast way to draw antialias circle in php.

If you need a fast antialias cirlce to draw in php here's an implementation:

[EDIT : antialias circle full implementation here]

function distance(rad, y) {
real_point = SQRT ( rad*rad - y*y)
return CEIL(real_point) - real_point

i = rad
j = 0
I(i, j) = I
T = 0

WHILE ( i <= j ) { j = j + 1; IF distance(rad, j) > T THEN i = i + 1
I(i, j) = distance(rad, j)
I(i - 1, j) = distance(rad, j)
T = distance(rad, j)

How I translate sum pieces in PHP?

function distance($r, $y) {
$real_point = sqrt(pow($r, 2) - pow($y, 2));
return ceil($real_point) - $real_point;

function new_color($i) {
return $i * 127;

// ... plot loop

$current_distance = distance($r, $y);
$transparency = new_color($current_distance);

$alpha = imagecolorallocatealpha($img, /* colore */, $transparency);
$alpha2 = imagecolorallocatealpha($img, /* colore */, 127 - $transparency);

imagesetpixel($image, $x, $y, imagecolorallocate(/* ... */)); // real point
imagesetpixel($image, $x - 1, $y, $alpha2 ); // nearest, inside
imagesetpixel($image, $x + 1, $y, $alpha ); //nearest, outside

The results, high zoom to recognize how the algorithm works:

Finally the result: