Simple Bezier Curve Implementation

The problem
Bezier curve is a very common tool in geometric computation. I do this because suddenly I feel interested in how it is implemented. It all starts from this thesis of Phillip J. Schneider. In
his master thesis, he gives a detailed algorithm of Bezier curve. And as for the "improvement" of his algorithms, I am not very sure and try to make a comparison.
The code is written on Gtk/Gdk and it is derived from some sample code. One small issue tortures me for more than one hour, GdkGC, the gdk_gc_new takes a parameter of "widget->window" which is
a "gtkwidget", I believe. However, gtkWidget, gdkDrawable etc., they all seem same to me as they are simply opaque "void*". Compiler doesn't know which is which.

Another issue is a joke. I try this:
const int ArraySize=2;
GdkPoint pointArray[ArraySize]={{1,1},{2,2}};
And I get compilation error of being unable to initialize array. This seems impossible for MS vc++6. And I am not sure if it is C99 issue of compiler issue.
Finally I have to work around by:

GdkPoint pointArray[]={{1,1},{2,2}};
const int ArraySize=sizeof(pointArray)/sizeof(GdkPoint);

This is ridiculous!

Now if you take a look of two different implementation, and you will see there is no difference of computation! Schneider's algorithms simply replace "power" with multiple multiplication, combinatorial
with double loop. (Of course, we can argue that power implementation is more expensive than multiplication, but it is another issue.)
Also I noticed that there is some approximation issues as the points generated by two methods are not strictly coincide. Which one is more accurate? I don't know.


　

/* GTK - GIMP工具包
 * 版权 (C) 1995-1997 Peter Mattis, Spencer Kimball 和 Josh MacDonald 所有
 *
 * 本程序是自由软件。你可以在自由软件基金发布的 GNU GPL 的条款下重新分发
 * 或修改它。GPL 可以使用版本 2 或(由你选择)任何随后的版本。
 *
 * 本程序分发的目的是它可能对其他人有用，但不提供任何的担保，包括隐含的
 * 和适合特定用途的保证。请查阅GNU通用公共许可证获得详细的信息。
 *
 * 你应该已经随该软件一起收到一份GNU通用公共许可。如果还没有，请写信给
 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
 * Boston, MA 02111-1307, USA.
 */

#include <gtk/gtk.h>
#include <math.h>

static GdkPixmap *pixmap = NULL;

double ConstFactorial[33] =
{
    1.0,
    1.0,
    2.0,
    6.0,
    24.0,
    120.0,
    720.0,
    5040.0,
    40320.0,
    362880.0,
    3628800.0,
    39916800.0,
    479001600.0,
    6227020800.0,
    87178291200.0,
    1307674368000.0,
    20922789888000.0,
    355687428096000.0,
    6402373705728000.0,
    121645100408832000.0,
    2432902008176640000.0,
    51090942171709440000.0,
    1124000727777607680000.0,
    25852016738884976640000.0,
    620448401733239439360000.0,
    15511210043330985984000000.0,
    403291461126605635584000000.0,
    10888869450418352160768000000.0,
    304888344611713860501504000000.0,
    8841761993739701954543616000000.0,
    265252859812191058636308480000000.0,
    8222838654177922817725562880000000.0,
    263130836933693530167218012160000000.0,
};

double Combinatorial(int n, int i)
{
    if (n > 32 || i > 32 || n < i)
    {
        return 1.0; //error
    }
    return ConstFactorial[n]/ConstFactorial[i]/ConstFactorial[n-i];
}

double Bernstein(int n, int i, double t)
{
    double ti; /* t^i */
    double tni; /* (1 - t)^i */

    /* Prevent problems with pow */

    if (t == 0.0 && i == 0)
    {
        ti = 1.0;
    }
    else
    {
        ti = pow(t, i);
    }

    if (n == i && t == 1.0)
    {
        tni = 1.0;
    }
    else
    {
        tni = pow((1 - t), (n - i));
    }

    return Combinatorial(n, i) * ti * tni;
}

void BezierExponent(int ctrlPtrCount, GdkPoint* ctrlPointArray, double t, GdkPoint* plotPoint)
{
    int i;
    double x = 0.0, y = 0.0;
    for ( i = 0; i < ctrlPtrCount; i ++)
    {
        double basis = Bernstein(ctrlPtrCount - 1, i, t);
        x += basis * ctrlPointArray[i].x;
        y += basis * ctrlPointArray[i].y;
    }
    plotPoint->x = x;
    plotPoint->y = y;
}


void BezierRecursion(int ctrlPtrCount, GdkPoint* ctrlPointArray, double t, GdkPoint* plotPoint)
{
    GdkPoint* pointArray = (GdkPoint*) malloc(sizeof(GdkPoint) * ctrlPtrCount);
    int i, j;
    if (pointArray)
    {
        for (i = 0; i < ctrlPtrCount; i ++)
        {
            pointArray[i] = ctrlPointArray[i];
        }
        for (j = 1; j < ctrlPtrCount; j ++)
        {
            for (i = 0; i < ctrlPtrCount - j; i ++)
            {
                pointArray[i].x = pointArray[i].x * (1 - t) + pointArray[i + 1].x * t;
                pointArray[i].y = pointArray[i].y * (1 - t) + pointArray[i + 1].y * t;
            }
        }
        plotPoint->x = pointArray[0].x;
        plotPoint->y = pointArray[0].y;
        free(pointArray);
    }
}

static int bUseRecursion = FALSE;

void Bezier2D(int ctrlPtrCount, GdkPoint* ctrlPointArray, int plotPtrCount, GdkPoint* plotPointArray)
{

    double step, t;
    int counter, i;
    if (ctrlPtrCount < 2 || plotPtrCount < 2)
    {
        return;
    }

    step = (double)1.0 / (plotPtrCount - 1);

    for (counter = 0, t = 0.0; counter < plotPtrCount; counter ++, t += step)
    {
        if ((1.0 - t) < 0.0000001)
        {
            t = 1.0;
        }
        if (!bUseRecursion)
        {
            BezierExponent(ctrlPtrCount, ctrlPointArray, t, plotPointArray + counter);
        }
        else
        {
            BezierRecursion(ctrlPtrCount, ctrlPointArray, t, plotPointArray + counter);
        }
    }
}


static void drawBezier(GtkWidget* widget)
{
    int i;
    GdkPoint ControlPtrArray[] =
    {
        {100, 500},
        {200, 100},
        {300, 300},
        {400, 450},
        {500, 550},
        {600, 250},
        {700, 200},
        {750, 550},
    };
    const int CtrlPtrCount = sizeof(ControlPtrArray)/sizeof(GdkPoint);
    const int PlotPtrCount = 80;

    GdkPoint plotPtrArray[PlotPtrCount];

    Bezier2D(CtrlPtrCount, ControlPtrArray, PlotPtrCount, plotPtrArray);

    gdk_draw_lines(pixmap, widget->style->black_gc, plotPtrArray, PlotPtrCount);

    GdkGC*  pointGC = gdk_gc_new(widget->window);
    GdkColor pointColor;

    if (bUseRecursion)
    {
        bUseRecursion = FALSE;
        pointColor.red = 65535;
        pointColor.green = 0;
        pointColor.blue = 0;
    }
    else
    {
        bUseRecursion = TRUE;
        pointColor.red = 0;
        pointColor.green = 65535;
        pointColor.blue = 0;
    }

    gdk_gc_set_rgb_fg_color(pointGC, &pointColor);

    for ( i = 0; i < PlotPtrCount; i ++)
    {
        gdk_draw_rectangle(pixmap, pointGC, TRUE, plotPtrArray[i].x - 5, plotPtrArray[i].y - 5, 10, 10);
    }

    GdkRectangle update_rect;

    update_rect.x = 0;
    update_rect.y = 0;
    update_rect.width = 800;
    update_rect.height = 600;

    gtk_widget_queue_draw_area (widget,
                                update_rect.x, update_rect.y,
                                update_rect.width, update_rect.height);

}

static gint configure_event( GtkWidget         *widget,
                             GdkEventConfigure *event )
{
    if (pixmap)
        g_object_unref (pixmap);

    pixmap = gdk_pixmap_new (widget->window,
                             widget->allocation.width,
                             widget->allocation.height,
                             -1);
    gdk_draw_rectangle (pixmap,
                        widget->style->white_gc,
                        TRUE,
                        0, 0,
                        widget->allocation.width,
                        widget->allocation.height);

    return TRUE;
}

static gint expose_event( GtkWidget      *widget,
                          GdkEventExpose *event )
{
    gdk_draw_drawable (widget->window,
                       widget->style->fg_gc[GTK_WIDGET_STATE (widget)],
                       pixmap,
                       event->area.x, event->area.y,
                       event->area.x, event->area.y,
                       event->area.width, event->area.height);

    return FALSE;
}



static void quit()
{
    exit(0);
}

int main( int   argc,
          char *argv[] )
{
    GtkWidget *window;
    GtkWidget *drawing_area;
    GtkWidget *vbox;

    GtkWidget *drawButton;

    gtk_init (&argc, &argv);

    window = gtk_window_new (GTK_WINDOW_TOPLEVEL);
    gtk_widget_set_name (window, "Test Input");

    vbox = gtk_vbox_new (FALSE, 0);
    gtk_container_add (GTK_CONTAINER (window), vbox);
    gtk_widget_show (vbox);

    g_signal_connect (G_OBJECT (window), "destroy", G_CALLBACK (quit), NULL);


    drawing_area = gtk_drawing_area_new ();
    gtk_widget_set_size_request (GTK_WIDGET (drawing_area), 800, 600);
    gtk_box_pack_start (GTK_BOX (vbox), drawing_area, TRUE, TRUE, 0);

    gtk_widget_show (drawing_area);

    g_signal_connect (G_OBJECT (drawing_area), "expose_event", G_CALLBACK (expose_event), NULL);
    g_signal_connect (G_OBJECT (drawing_area),"configure_event", G_CALLBACK (configure_event), NULL);

    drawButton = gtk_button_new_with_label("Draw");


    gtk_box_pack_start (GTK_BOX (vbox), drawButton, FALSE, FALSE, 0);

    g_signal_connect_swapped (G_OBJECT (drawButton), "clicked",
                                G_CALLBACK (drawBezier),
                                drawing_area);

    gtk_widget_show (drawButton);
    gtk_widget_show (window);

    gtk_main ();

    return 0;
}
　

　










                            
   
                   







                       back.gif (341 bytes)       

up.gif (335 bytes)                                       
next.gif (337 bytes)