Algorithm to add Color in Bezier curves

Question

I'm playing with GD library for a while and more particuraly with Bezier curves atm.

I used some existant class which I modified a little (seriously eval()...). I found out it was a generic algorithm used in and convert for GD.

Now I want to take it to another level: I want some colors.

No problem for line color but with fill color it's harder.

My question is:

Is there any existant algorithm for that? I mean mathematical algorithm or any language doing it already so that I could transfer it to PHP + GD?

EDIT2 So, I tried @MizardX solution with a harder curve :

• 1st position : 50 - 50
• final position : 50 - 200
• 1st control point : 300 - 225
• 2nd control point : 300 - 25

Which should show this :

And gives this :

EDIT I already read about @MizardX solution. Using imagefilledpolygon to make it works.

But it doesn't work as expected. See the image below to see the problem. Top graph is what I expect (w/o the blackline for now, only the red part).

Coordinates used:

• first point is 100 - 100
• final point is 300 - 100
• first control point is 100 - 0
• final control point is 300 - 200

Bottom part is what I get with that kind of algorithm...

Answer 1

Convert the Bezier curve to a polyline/polygon, and fill that. If you evaluate the Bezier polynomial at close enough intervals (~1 pixel) it will be identical to an ideal Bezier curve.

I don't know how familiar you are with Bezier curves, but here is a crash course:

<?php

// Calculate the coordinate of the Bezier curve at $t = 0..1
function Bezier_eval($p1,$p2,$p3,$p4,$t) {
    // lines between successive pairs of points (degree 1)
    $q1  = array((1-$t) * $p1[0] + $t * $p2[0],(1-$t) * $p1[1] + $t * $p2[1]);
    $q2  = array((1-$t) * $p2[0] + $t * $p3[0],(1-$t) * $p2[1] + $t * $p3[1]);
    $q3  = array((1-$t) * $p3[0] + $t * $p4[0],(1-$t) * $p3[1] + $t * $p4[1]);
    // curves between successive pairs of lines. (degree 2)
    $r1  = array((1-$t) * $q1[0] + $t * $q2[0],(1-$t) * $q1[1] + $t * $q2[1]);
    $r2  = array((1-$t) * $q2[0] + $t * $q3[0],(1-$t) * $q2[1] + $t * $q3[1]);
    // final curve between the two 2-degree curves. (degree 3)
    return array((1-$t) * $r1[0] + $t * $r2[0],(1-$t) * $r1[1] + $t * $r2[1]);
}

// Calculate the squared distance between two points
function Point_distance2($p1,$p2) {
    $dx = $p2[0] - $p1[0];
    $dy = $p2[1] - $p1[1];
    return $dx * $dx + $dy * $dy;
}

// Convert the curve to a polyline
function Bezier_convert($p1,$p2,$p3,$p4,$tolerance) {
    $t1 = 0.0;
    $prev = $p1;
    $t2 = 0.1;
    $tol2 = $tolerance * $tolerance;
    $result []= $prev[0];
    $result []= $prev[1];
    while ($t1 < 1.0) {
        if ($t2 > 1.0) {
            $t2 = 1.0;
        }
        $next = Bezier_eval($p1,$p2,$p3,$p4,$t2);
        $dist = Point_distance2($prev,$next);
        while ($dist > $tol2) {
            // Halve the distance until small enough
            $t2 = $t1 + ($t2 - $t1) * 0.5;
            $next = Bezier_eval($p1,$p2,$p3,$p4,$t2);
            $dist = Point_distance2($prev,$next);
        }
        // the image*polygon functions expect a flattened array of coordiantes
        $result []= $next[0];
        $result []= $next[1];
        $t1 = $t2;
        $prev = $next;
        $t2 = $t1 + 0.1;
    }
    return $result;
}

// Draw a Bezier curve on an image
function Bezier_drawfilled($image,$p1,$p2,$p3,$p4,$color) {
    $polygon = Bezier_convert($p1,$p2,$p3,$p4,1.0);
    imagefilledpolygon($image,$polygon,count($polygon)/2,$color);
}

?>

Edit:

I forgot to test the routine. It is indeed as you said; It doesn't give a correct result. Now I have fixed two bugs:

1. I unintentionally re-used the variable names $p1 and $p2. I renamed them $prev and $next.
2. Wrong sign in the while-loop. Now it loops until the distance is small enough, instead of big enough.

Answer 2

I checked the algorithm for generating a Polygon ensuring a bounded distance between successive parameter-generated points, and seems to work well for all the curves I tested.

Code in Mathematica:

pts={{50,50},{300,225},{300,25},{50,200}};
f=BezierFunction[pts];
step=.1; (*initial step*)

While[ (*get the final step - Points no more than .01 appart*)
   Max[
     EuclideanDistance @@@ 
         Partition[Table[f[t],{t,0,1,step}],2,1]] > .01,
   step=step/2]

(*plot it*)
Graphics@Polygon@Table[f[t],{t,0,1,step}]  

.

.

The algorithm could be optimized (ie. generate less points) if you don't require the same parameter increment between points, meaning you can chose a parameter increment at each point that ensures a bounded distance to the next.

Random examples: