Remaining files transfered

1 files changed, 294 insertions, 0 deletions

diff --git a/potrace/render.cpp b/potrace/render.cpp
new file mode 100644
index 0000000..833f6b0
--- /dev/null
+++ b/potrace/render.cpp
@@ -0,0 +1,294 @@
+/* Copyright (C) 2001-2007 Peter Selinger.
+ *  This file is part of Potrace. It is free software and it is covered
+ *  by the GNU General Public License. See the file COPYING for details. */
+
+/* $Id: render.c 147 2007-04-09 00:44:09Z selinger $ */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <cmath>
+#include <string.h>
+
+#include <render.h>
+#include <greymap.h>
+#include <auxiliary.h>
+
+/* ---------------------------------------------------------------------- */
+/* routines for anti-aliased rendering of curves */
+
+/* we use the following method. Given a point (x,y) (with real-valued
+ *  coordinates) in the plane, let (xi,yi) be the integer part of the
+ *  coordinates, i.e., xi=floor(x), yi=floor(y). Define a path from
+ *  (x,y) to infinity as follows: path(x,y) =
+ *  (x,y)--(xi+1,y)--(xi+1,yi)--(+infty,yi).  Now as the point (x,y)
+ *  moves smoothly across the plane, the path path(x,y) sweeps
+ *  (non-smoothly) across a certain area. We proportionately blacken
+ *  the area as the path moves "downward", and we whiten the area as
+ *  the path moves "upward". This way, after the point has traversed a
+ *  closed curve, the interior of the curve has been darkened
+ *  (counterclockwise movement) or lightened (clockwise movement). (The
+ *  "grey shift" is actually proportional to the winding number). By
+ *  choosing the above path with mostly integer coordinates, we achieve
+ *  that only pixels close to (x,y) receive grey values and are subject
+ *  to round-off errors. The grey value of pixels far away from (x,y)
+ *  is always in "integer" (where 0=black, 1=white).  As a special
+ *  trick, we keep an accumulator rm->a1, which holds a double value to
+ *  be added to the grey value to be added to the current pixel
+ *  (xi,yi).  Only when changing "current" pixels, we convert this
+ *  double value to an integer. This way we avoid round-off errors at
+ *  the meeting points of line segments. Another speedup measure is
+ *  that we sometimes use the rm->incrow_buf array to postpone
+ *  incrementing or decrementing an entire row. If incrow_buf[y]=x+1!=0,
+ *  then all the pixels (x,y),(x+1,y),(x+2,y),... are scheduled to be
+ *  incremented/decremented (which one is the case will be clear from
+ *  context). This keeps the greymap operations reasonably local. */
+
+/* allocate a new rendering state */
+render_t* render_new( greymap_t* gm )
+{
+    render_t* rm;
+
+    rm = (render_t*) malloc( sizeof(render_t) );
+    if( !rm )
+    {
+        return NULL;
+    }
+    memset( rm, 0, sizeof(render_t) );
+    rm->gm = gm;
+    rm->incrow_buf = (int*) malloc( gm->h * sizeof(int) );
+    if( !rm->incrow_buf )
+    {
+        free( rm );
+        return NULL;
+    }
+    memset( rm->incrow_buf, 0, gm->h * sizeof(int) );
+    return rm;
+}
+
+
+/* free a given rendering state. Note: this does not free the
+ *  underlying greymap. */
+void render_free( render_t* rm )
+{
+    free( rm->incrow_buf );
+    free( rm );
+}
+
+
+/* close path */
+void render_close( render_t* rm )
+{
+    if( rm->x0 != rm->x1 || rm->y0 != rm->y1 )
+    {
+        render_lineto( rm, rm->x0, rm->y0 );
+    }
+    GM_INC( rm->gm, rm->x0i, rm->y0i, (rm->a0 + rm->a1) * 255 );
+
+    /* assert (rm->x0i != rm->x1i || rm->y0i != rm->y1i); */
+
+    /* the persistent state is now undefined */
+}
+
+
+/* move point */
+void render_moveto( render_t* rm, double x, double y )
+{
+    /* close the previous path */
+    render_close( rm );
+
+    rm->x0  = rm->x1 = x;
+    rm->y0  = rm->y1 = y;
+    rm->x0i = (int) floor( rm->x0 );
+    rm->x1i = (int) floor( rm->x1 );
+    rm->y0i = (int) floor( rm->y0 );
+    rm->y1i = (int) floor( rm->y1 );
+    rm->a0  = rm->a1 = 0;
+}
+
+
+/* add b to pixels (x,y) and all pixels to the right of it. However,
+ *  use rm->incrow_buf as a buffer to economize on multiple calls */
+static void incrow( render_t* rm, int x, int y, int b )
+{
+    int i, x0;
+
+    if( y < 0 || y >= rm->gm->h )
+    {
+        return;
+    }
+
+    if( x < 0 )
+    {
+        x = 0;
+    }
+    else if( x > rm->gm->w )
+    {
+        x = rm->gm->w;
+    }
+    if( rm->incrow_buf[y] == 0 )
+    {
+        rm->incrow_buf[y] = x + 1; /* store x+1 so that we can use 0 for "vacant" */
+        return;
+    }
+    x0 = rm->incrow_buf[y] - 1;
+    rm->incrow_buf[y] = 0;
+    if( x0 < x )
+    {
+        for( i = x0; i<x; i++ )
+        {
+            GM_INC( rm->gm, i, y, -b );
+        }
+    }
+    else
+    {
+        for( i = x; i<x0; i++ )
+        {
+            GM_INC( rm->gm, i, y, b );
+        }
+    }
+}
+
+
+/* render a straight line */
+void render_lineto( render_t* rm, double x2, double y2 )
+{
+    int    x2i, y2i;
+    double t0 = 2, s0 = 2;
+    int    sn, tn;
+    double ss = 2, ts = 2;
+    double r0, r1;
+    int    i, j;
+    int    rxi, ryi;
+    int    s;
+
+    x2i = (int) floor( x2 );
+    y2i = (int) floor( y2 );
+
+    sn = abs( x2i - rm->x1i );
+    tn = abs( y2i - rm->y1i );
+
+    if( sn )
+    {
+        s0 = ( (x2>rm->x1 ? rm->x1i + 1 : rm->x1i) - rm->x1 ) / (x2 - rm->x1);
+        ss = fabs( 1.0 / (x2 - rm->x1) );
+    }
+    if( tn )
+    {
+        t0 = ( (y2>rm->y1 ? rm->y1i + 1 : rm->y1i) - rm->y1 ) / (y2 - rm->y1);
+        ts = fabs( 1.0 / (y2 - rm->y1) );
+    }
+
+    r0 = 0;
+
+    i = 0;
+    j = 0;
+
+    rxi = rm->x1i;
+    ryi = rm->y1i;
+
+    while( i<sn || j<tn )
+    {
+        if( j>=tn || (i<sn && s0 + i * ss < t0 + j * ts) )
+        {
+            r1 = s0 + i * ss;
+            i++;
+            s = 1;
+        }
+        else
+        {
+            r1 = t0 + j * ts;
+            j++;
+            s = 0;
+        }
+        /* render line from r0 to r1 segment of (rm->x1,rm->y1)..(x2,y2) */
+
+        /* move point to r1 */
+        rm->a1 +=
+            (r1 - r0) * (y2 - rm->y1) * ( rxi + 1 - ( (r0 + r1) / 2.0 * (x2 - rm->x1) + rm->x1 ) );
+
+        /* move point across pixel boundary */
+        if( s && x2>rm->x1 )
+        {
+            GM_INC( rm->gm, rxi, ryi, rm->a1 * 255 );
+            rm->a1 = 0;
+            rxi++;
+            rm->a1 += rm->y1 + r1 * (y2 - rm->y1) - ryi;
+        }
+        else if( !s && y2>rm->y1 )
+        {
+            GM_INC( rm->gm, rxi, ryi, rm->a1 * 255 );
+            rm->a1 = 0;
+            incrow( rm, rxi + 1, ryi, 255 );
+            ryi++;
+        }
+        else if( s && x2<=rm->x1 )
+        {
+            rm->a1 -= rm->y1 + r1 * (y2 - rm->y1) - ryi;
+            GM_INC( rm->gm, rxi, ryi, rm->a1 * 255 );
+            rm->a1 = 0;
+            rxi--;
+        }
+        else if( !s && y2<=rm->y1 )
+        {
+            GM_INC( rm->gm, rxi, ryi, rm->a1 * 255 );
+            rm->a1 = 0;
+            ryi--;
+            incrow( rm, rxi + 1, ryi, -255 );
+        }
+
+        r0 = r1;
+    }
+
+    /* move point to (x2,y2) */
+
+    r1      = 1;
+    rm->a1 += (r1 - r0) * (y2 - rm->y1) * ( rxi + 1 - ( (r0 + r1) / 2.0 * (x2 - rm->x1) + rm->x1 ) );
+
+    rm->x1i = x2i;
+    rm->y1i = y2i;
+    rm->x1  = x2;
+    rm->y1  = y2;
+
+    /* assert (rxi != rm->x1i || ryi != rm->y1i); */
+}
+
+
+/* render a Bezier curve. */
+void render_curveto( render_t* rm,
+                     double    x2,
+                     double    y2,
+                     double    x3,
+                     double    y3,
+                     double    x4,
+                     double    y4 )
+{
+    double x1, y1, dd0, dd1, dd, delta, e2, epsilon, t;
+
+    x1 = rm->x1; /* starting point */
+    y1 = rm->y1;
+
+    /* we approximate the curve by small line segments. The interval
+     *  size, epsilon, is determined on the fly so that the distance
+     *  between the true curve and its approximation does not exceed the
+     *  desired accuracy delta. */
+
+    delta = .1; /* desired accuracy, in pixels */
+
+    /* let dd = maximal value of 2nd derivative over curve - this must
+     *  occur at an endpoint. */
+    dd0     = sq( x1 - 2 * x2 + x3 ) + sq( y1 - 2 * y2 + y3 );
+    dd1     = sq( x2 - 2 * x3 + x4 ) + sq( y2 - 2 * y3 + y4 );
+    dd      = 6 * sqrt( max( dd0, dd1 ) );
+    e2      = 8 * delta <= dd ? 8 * delta / dd : 1;
+    epsilon = sqrt( e2 ); /* necessary interval size */
+
+    for( t = epsilon; t<1; t += epsilon )
+    {
+        render_lineto( rm, x1 * cu( 1 - t ) + 3 * x2 * sq( 1 - t ) * t + 3 * x3 * (1 - t) * sq(
+                          t ) + x4 * cu( t ),
+                      y1 * cu( 1 - t ) + 3 * y2 * sq( 1 - t ) * t + 3 * y3 * (1 - t) * sq(
+                          t ) + y4 * cu( t ) );
+    }
+
+    render_lineto( rm, x4, y4 );
+}