path: root/converter/other/pamtosvg/curve.c

/* curve.c: operations on the lists of pixels and lists of curves.

   The code was partially derived from limn.

   Copyright (C) 1992 Free Software Foundation, Inc.

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2, or (at your option)
   any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.  */

#include <assert.h>

#include "mallocvar.h"

#include "logreport.h"
#include "curve.h"


static Point
realCoordFromInt(pm_pixelcoord const int_coord) {
/*----------------------------------------------------------------------------
  Turn an integer point into a real one.
-----------------------------------------------------------------------------*/
    Point real_coord;

    real_coord.x = int_coord.col;
    real_coord.y = int_coord.row;
    real_coord.z = 0.0;

    return real_coord;
}



Curve *
curve_new(void) {
/*----------------------------------------------------------------------------
  A new, entirely empty curve.
-----------------------------------------------------------------------------*/
    Curve * curveP;

    MALLOCVAR_NOFAIL(curveP);

    curveP->pointList       = NULL;
    CURVE_LENGTH(curveP)    = 0;
    CURVE_CYCLIC(curveP)    = false;
    PREVIOUS_CURVE(curveP)  = NULL;
    NEXT_CURVE(curveP)      = NULL;

    return curveP;
}



Curve *
curve_copyMost(Curve * const oldCurveP) {
/*----------------------------------------------------------------------------
  New curve that is the same as *curveP, except without any points.

  Don't copy the points or tangents, but copy everything else.
-----------------------------------------------------------------------------*/
    Curve * curveP = curve_new();

    CURVE_CYCLIC(curveP)   = CURVE_CYCLIC(oldCurveP);
    PREVIOUS_CURVE(curveP) = PREVIOUS_CURVE(oldCurveP);
    NEXT_CURVE(curveP)     = NEXT_CURVE(oldCurveP);

    return curveP;
}



void
curve_move(Curve * const dstP,
           Curve * const srcP) {
/*----------------------------------------------------------------------------
  Move ownership of dynamically allocated memory from source to destination;
  destroy source.
-----------------------------------------------------------------------------*/
   if (CURVE_LENGTH(dstP) > 0)
       free(dstP->pointList);

   *dstP = *srcP;

   free(srcP);
}



void
curve_free(Curve * const curveP) {

    /* The length of CURVE will be zero if we ended up not being able to fit
       it (which in turn implies a problem elsewhere in the program, but at
       any rate, we shouldn't try here to free the nonexistent curve).
    */

     if (CURVE_LENGTH(curveP) > 0)
         free(curveP->pointList);

     free(curveP);
}



void
curve_appendPoint(Curve * const curveP,
                  Point   const coord) {
/*----------------------------------------------------------------------------
  Like `append_pixel', for a point in real coordinates.
-----------------------------------------------------------------------------*/
    CURVE_LENGTH(curveP)++;
    REALLOCARRAY_NOFAIL(curveP->pointList, CURVE_LENGTH(curveP));
    LAST_CURVE_POINT(curveP) = coord;
    /* The t value does not need to be set.  */
}



void
curve_appendPixel(Curve *       const curveP,
                  pm_pixelcoord const coord) {
/*----------------------------------------------------------------------------
  Append the point 'coord' to the end of *curveP's list.
-----------------------------------------------------------------------------*/
    curve_appendPoint(curveP, realCoordFromInt(coord));
}



void
curve_setDistance(Curve * const curveP) {
/*----------------------------------------------------------------------------
   Fill in the distance values in *curveP.

   The distance value for point P on a curve is the distance P is along the
   curve from the initial point, normalized so the entire curve is length 1.0
   (i.e. t of the initial point is 0.0; t of the final point is 1.0).

   There are a lot of curves that pass through the points indicated by
   *curveP, but for practical computation of t, we just take the piecewise
   linear locus that runs through all of them.  That means we can just step
   through *curveP, adding up the distance from one point to the next to get
   the t value for each point.

   This is the "chord-length parameterization" method, which is described in
   Plass & Stone.
-----------------------------------------------------------------------------*/
    unsigned int p;

    LOG("\nAssigning initial t values:\n  ");

    /* Algorithm: We do a pass through the curve establishing how far each
       point is along the curve in absolute terms, and then another pass
       to normalize those distances to the fraction of the curve (i.e.
       if the curve is 5 units long and Point P is 2 units in, we record
       2 units for Point P in the first pass, and then compute 0.2 as the
       fraction of the curve length in the second pass.

       In the first pass, we abuse the distance property of the CurvePoint
       object to remember the unnormalized distances.
    */

    CURVE_DIST(curveP, 0) = 0.0;

    for (p = 1; p < CURVE_LENGTH(curveP); ++p) {
        Point const point      = CURVE_POINT(curveP, p);
        Point const previous_p = CURVE_POINT(curveP, p - 1);
        float const d          = point_distance(point, previous_p);
        CURVE_DIST(curveP, p)  = CURVE_DIST(curveP, p - 1) + d;
    }

    assert(LAST_CURVE_DIST(curveP) != 0.0);

    /* Normalize to a curve length of 1.0 */

    for (p = 1; p < CURVE_LENGTH(curveP); ++p)
        CURVE_DIST(curveP, p) =
            CURVE_DIST(curveP, p) / LAST_CURVE_DIST(curveP);

    curve_logEntire(curveP);
}



#define NUM_TO_PRINT 3

#define LOG_CURVE_POINT(c, p, printDistance) \
    do  \
    {                                   \
      LOG2 ("(%.3f,%.3f)", CURVE_POINT (c, p).x, CURVE_POINT (c, p).y); \
      if (printDistance) \
        LOG1 ("/%.2f", CURVE_DIST(c, p)); \
    } \
  while (0)



void
curve_log(Curve * const curveP,
          bool    const printDistance) {
/*----------------------------------------------------------------------------
  Print a curve in human-readable form.  It turns out we never care
  about most of the points on the curve, and so it is pointless to
  print them all out umpteen times.  What matters is that we have some
  from the end and some from the beginning.
-----------------------------------------------------------------------------*/
    if (!log_file)
        return;

    LOG1("curve id = %lx:\n", (unsigned long) curveP);
    LOG1("  length = %u.\n", CURVE_LENGTH(curveP));
    if (CURVE_CYCLIC(curveP))
        LOG("  cyclic.\n");

    LOG("  ");

    /* If the curve is short enough, don't use ellipses.  */
    if (CURVE_LENGTH(curveP) <= NUM_TO_PRINT * 2) {
        unsigned int thisPoint;

        for (thisPoint = 0; thisPoint < CURVE_LENGTH(curveP); ++thisPoint) {
            LOG_CURVE_POINT(curveP, thisPoint, printDistance);
            LOG(" ");

            if (thisPoint != CURVE_LENGTH(curveP) - 1
                && (thisPoint + 1) % NUM_TO_PRINT == 0)
                LOG("\n  ");
        }
    } else {
        unsigned int thisPoint;
        for (thisPoint = 0;
             thisPoint < NUM_TO_PRINT && thisPoint < CURVE_LENGTH(curveP);
             ++thisPoint) {
            LOG_CURVE_POINT(curveP, thisPoint, printDistance);
            LOG(" ");
        }

        LOG("...\n   ...");

        for (thisPoint = CURVE_LENGTH(curveP) - NUM_TO_PRINT;
             thisPoint < CURVE_LENGTH(curveP);
             ++thisPoint) {
            LOG(" ");
            LOG_CURVE_POINT(curveP, thisPoint, printDistance);
        }
    }
    LOG(".\n");
}



void
curve_logEntire(Curve * const curveP) {
/*----------------------------------------------------------------------------
  Like `log_curve', but write the whole thing.
-----------------------------------------------------------------------------*/
    unsigned int thisPoint;

    if (!log_file)
        return;

    LOG1("curve id = %lx:\n", (unsigned long) curveP);
    LOG1("  length = %u.\n", CURVE_LENGTH(curveP));
    if (CURVE_CYCLIC(curveP))
        LOG("  cyclic.\n");

    LOG(" ");

    for (thisPoint = 0; thisPoint < CURVE_LENGTH(curveP); ++thisPoint) {
        LOG(" ");
        LOG_CURVE_POINT(curveP, thisPoint, true);
        /* Compiler warning `Condition is always true' can be ignored */
    }

    LOG(".\n");
}



CurveList
curve_newList(void) {
/*----------------------------------------------------------------------------
  A new initialized but empty curve list.
-----------------------------------------------------------------------------*/
    CurveList curveList;

    curveList.length = 0;
    curveList.data   = NULL;

    return curveList;
}



void
curve_freeList(CurveList * const curveListP) {
/*----------------------------------------------------------------------------
  Free curve list and all the curves it contains.
-----------------------------------------------------------------------------*/
    unsigned int thisCurve;

    for (thisCurve = 0; thisCurve < curveListP->length; ++thisCurve)
        curve_free(curveListP->data[thisCurve]);

    /* If the character was empty, it won't have any curves.  */
    if (curveListP->data != NULL)
        free(curveListP->data);
}



void
curve_appendList(CurveList * const curveListP,
                 Curve *     const curveP) {
/*----------------------------------------------------------------------------
  Add an element to a curve list.
-----------------------------------------------------------------------------*/
    ++curveListP->length;
    REALLOCARRAY_NOFAIL(curveListP->data, curveListP->length);
    curveListP->data[curveListP->length - 1] = curveP;
}



CurveListArray
curve_newListArray(void) {
/*----------------------------------------------------------------------------
    An initialized but empty curve list array.
-----------------------------------------------------------------------------*/
    CurveListArray curveListArray;

    CURVE_LIST_ARRAY_LENGTH(curveListArray) = 0;
    curveListArray.data = NULL;

    return curveListArray;
}



void
curve_freeListArray(const CurveListArray * const curveListArrayP,
                    at_progress_func             notify_progress,
                    void *                 const clientData) {
/*----------------------------------------------------------------------------
  Free all the curve lists curveListArray contains.
-----------------------------------------------------------------------------*/
    unsigned int thisList;

    for (thisList = 0;
         thisList < CURVE_LIST_ARRAY_LENGTH(*curveListArrayP);
         ++thisList) {

      if (notify_progress)
          notify_progress(((float)thisList)/
                          (CURVE_LIST_ARRAY_LENGTH(*curveListArrayP) *
                           (float)3.0)+(float)0.666 ,
                          clientData);
      curve_freeList(&CURVE_LIST_ARRAY_ELT(*curveListArrayP, thisList));
    }

    /* If the character was empty, it won't have any curves.  */
    if (curveListArrayP->data)
        free(curveListArrayP->data);
}



void
curve_appendArray(CurveListArray * const curveListArrayP,
                  CurveList        const curveList) {
/*----------------------------------------------------------------------------
  Add an element to *curveListArrayP.
-----------------------------------------------------------------------------*/
    CURVE_LIST_ARRAY_LENGTH(*curveListArrayP)++;
    REALLOCARRAY_NOFAIL(curveListArrayP->data,
                        CURVE_LIST_ARRAY_LENGTH(*curveListArrayP));
    LAST_CURVE_LIST_ARRAY_ELT(*curveListArrayP) = curveList;
}