diff options
Diffstat (limited to 'src/3rdparty/autotrace')
49 files changed, 8464 insertions, 0 deletions
diff --git a/src/3rdparty/autotrace/CMakeLists.txt b/src/3rdparty/autotrace/CMakeLists.txt new file mode 100644 index 0000000..2f5db82 --- /dev/null +++ b/src/3rdparty/autotrace/CMakeLists.txt @@ -0,0 +1,53 @@ +set ( autotrace_SRC +config.h +atou.c +atou.h +autotrace.c +autotrace.h +bitmap.c +bitmap.h +CMakeLists.txt +cmdline.h +color.c +color.h +curve.c +curve.h +datetime.c +datetime.h +despeckle.c +despeckle.h +epsilon-equal.c +epsilon-equal.h +exception.c +exception.h +filename.c +filename.h +fit.c +fit.h +image-header.h +image-proc.c +image-proc.h +input.c +input.h +intl.h +logreport.c +logreport.h +median.c +module.c +output.c +output.h +private.h +pxl-outline.c +pxl-outline.h +quantize.h +spline.c +spline.h +thin-image.c +thin-image.h +types.h +vector.c +vector.h +xstd.h +) + +add_inkscape_lib(autotrace_LIB "${autotrace_SRC}") diff --git a/src/3rdparty/autotrace/atou.c b/src/3rdparty/autotrace/atou.c new file mode 100644 index 0000000..4d29654 --- /dev/null +++ b/src/3rdparty/autotrace/atou.c @@ -0,0 +1,18 @@ +/* atou.c: like atoi, but if the number is negative, abort. */ + +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif /* Def: HAVE_CONFIG_H */ + +#include "logreport.h" +#include "atou.h" + +unsigned atou(gchar * s) +{ + int i = atoi(s); + + if (i < 0) + FATAL("I expected a positive number, not %d", i); + + return (unsigned)i; +} diff --git a/src/3rdparty/autotrace/atou.h b/src/3rdparty/autotrace/atou.h new file mode 100644 index 0000000..f430310 --- /dev/null +++ b/src/3rdparty/autotrace/atou.h @@ -0,0 +1,9 @@ +/* atou.h: like atoi, but if the number is negative, abort. */ + +#ifndef ATOU_H +#define ATOU_H + +#include "types.h" +unsigned atou(gchar * s); + +#endif /* not ATOU_H */ diff --git a/src/3rdparty/autotrace/autotrace.c b/src/3rdparty/autotrace/autotrace.c new file mode 100644 index 0000000..a2b65de --- /dev/null +++ b/src/3rdparty/autotrace/autotrace.c @@ -0,0 +1,386 @@ +/* autotrace.c --- Autotrace API + + Copyright (C) 2000, 2001, 2002 Martin Weber + + The author can be contacted at <martweb@gmx.net> + + 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 of the License, 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. */ + +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif /* Def: HAVE_CONFIG_H */ +#include "intl.h" + +#include "private.h" + +#include "autotrace.h" +#include "exception.h" + +#include "fit.h" +#include "bitmap.h" +#include "spline.h" + +#include "input.h" + +#include "xstd.h" +#include "image-header.h" +#include "image-proc.h" +#include "quantize.h" +#include "thin-image.h" +#include "despeckle.h" + +#include <locale.h> +#include <time.h> +#include <stdlib.h> +#include <string.h> + +#define AT_DEFAULT_DPI 72 + +at_fitting_opts_type *at_fitting_opts_new(void) +{ + at_fitting_opts_type *opts; + XMALLOC(opts, sizeof(at_fitting_opts_type)); + *opts = new_fitting_opts(); + return opts; +} + +at_fitting_opts_type *at_fitting_opts_copy(at_fitting_opts_type * original) +{ + at_fitting_opts_type *new_opts; + if (original == NULL) + return NULL; + + new_opts = at_fitting_opts_new(); + *new_opts = *original; + if (original->background_color) + new_opts->background_color = at_color_copy(original->background_color); + return new_opts; +} + +void at_fitting_opts_free(at_fitting_opts_type * opts) +{ + free(opts->background_color); + free(opts); +} + +at_input_opts_type *at_input_opts_new(void) +{ + at_input_opts_type *opts; + XMALLOC(opts, sizeof(at_input_opts_type)); + opts->background_color = NULL; + opts->charcode = 0; + return opts; +} + +at_input_opts_type *at_input_opts_copy(at_input_opts_type * original) +{ + at_input_opts_type *opts; + opts = at_input_opts_new(); + *opts = *original; + if (original->background_color) + opts->background_color = at_color_copy(original->background_color); + return opts; +} + +void at_input_opts_free(at_input_opts_type * opts) +{ + free(opts->background_color); + free(opts); +} + +at_output_opts_type *at_output_opts_new(void) +{ + at_output_opts_type *opts; + XMALLOC(opts, sizeof(at_output_opts_type)); + opts->dpi = AT_DEFAULT_DPI; + return opts; +} + +at_output_opts_type *at_output_opts_copy(at_output_opts_type * original) +{ + at_output_opts_type *opts = at_output_opts_new(); + *opts = *original; + return opts; +} + +void at_output_opts_free(at_output_opts_type * opts) +{ + free(opts); +} + +at_bitmap *at_bitmap_read(at_bitmap_reader * reader, gchar * filename, at_input_opts_type * opts, at_msg_func msg_func, gpointer msg_data) +{ + gboolean new_opts = FALSE; + at_bitmap *bitmap; + XMALLOC(bitmap, sizeof(at_bitmap)); + if (opts == NULL) { + opts = at_input_opts_new(); + new_opts = TRUE; + } + *bitmap = (*reader->func) (filename, opts, msg_func, msg_data, reader->data); + if (new_opts) + at_input_opts_free(opts); + return bitmap; +} + +at_bitmap *at_bitmap_new(unsigned short width, unsigned short height, unsigned int planes) +{ + at_bitmap *bitmap; + XMALLOC(bitmap, sizeof(at_bitmap)); + *bitmap = at_bitmap_init(NULL, width, height, planes); + return bitmap; +} + +at_bitmap *at_bitmap_copy(const at_bitmap * src) +{ + at_bitmap *dist; + unsigned short width, height, planes; + + width = at_bitmap_get_width(src); + height = at_bitmap_get_height(src); + planes = at_bitmap_get_planes(src); + + dist = at_bitmap_new(width, height, planes); + memcpy(dist->bitmap, src->bitmap, width * height * planes * sizeof(unsigned char)); + return dist; +} + +at_bitmap at_bitmap_init(unsigned char *area, unsigned short width, unsigned short height, unsigned int planes) +{ + at_bitmap bitmap; + + if (area) + bitmap.bitmap = area; + else { + if (0 == (width * height)) + bitmap.bitmap = NULL; + else + XCALLOC(bitmap.bitmap, width * height * planes * sizeof(unsigned char)); + } + + bitmap.width = width; + bitmap.height = height; + bitmap.np = planes; + return bitmap; +} + +void at_bitmap_free(at_bitmap * bitmap) +{ + free(AT_BITMAP_BITS(bitmap)); + free(bitmap); +} + +unsigned short at_bitmap_get_width(const at_bitmap * bitmap) +{ + return bitmap->width; +} + +unsigned short at_bitmap_get_height(const at_bitmap * bitmap) +{ + return bitmap->height; +} + +unsigned short at_bitmap_get_planes(const at_bitmap * bitmap) +{ + /* Here we use cast rather changing the type definition of + at_bitmap::np to keep binary compatibility. */ + return (unsigned short)bitmap->np; +} + +void at_bitmap_get_color(const at_bitmap * bitmap, unsigned int row, unsigned int col, at_color * color) +{ + unsigned char *p; + g_return_if_fail(color); + g_return_if_fail(bitmap); + + p = AT_BITMAP_PIXEL(bitmap, row, col); + if (at_bitmap_get_planes(bitmap) >= 3) + at_color_set(color, p[0], p[1], p[2]); + else + at_color_set(color, p[0], p[0], p[0]); +} + +gboolean at_bitmap_equal_color(const at_bitmap * bitmap, unsigned int row, unsigned int col, at_color * color) +{ + at_color c; + + g_return_val_if_fail(bitmap, FALSE); + g_return_val_if_fail(color, FALSE); + + at_bitmap_get_color(bitmap, row, col, &c); + return at_color_equal(&c, color); +} + +at_splines_type *at_splines_new(at_bitmap * bitmap, at_fitting_opts_type * opts, at_msg_func msg_func, gpointer msg_data) +{ + return at_splines_new_full(bitmap, opts, msg_func, msg_data, NULL, NULL, NULL, NULL); +} + +/* at_splines_new_full modify its argument: BITMAP + when despeckle, quantize and/or thin_image are invoked. */ +at_splines_type *at_splines_new_full(at_bitmap * bitmap, at_fitting_opts_type * opts, at_msg_func msg_func, gpointer msg_data, at_progress_func notify_progress, gpointer progress_data, at_testcancel_func test_cancel, gpointer testcancel_data) +{ + image_header_type image_header; + at_splines_type *splines = NULL; + pixel_outline_list_type pixels; + QuantizeObj *myQuant = NULL; /* curently not used */ + at_exception_type exp = at_exception_new(msg_func, msg_data); + at_distance_map dist_map, *dist = NULL; + +#define CANCELP (test_cancel && test_cancel(testcancel_data)) +#define FATALP (at_exception_got_fatal(&exp)) +#define FREE_SPLINE() do {if (splines) {at_splines_free(splines); splines = NULL;}} while(0) + +#define CANCEL_THEN_CLEANUP_DIST() if (CANCELP) goto cleanup_dist; +#define CANCEL_THEN_CLEANUP_PIXELS() if (CANCELP) {FREE_SPLINE(); goto cleanup_pixels;} + +#define FATAL_THEN_RETURN() if (FATALP) return splines; +#define FATAL_THEN_CLEANUP_DIST() if (FATALP) goto cleanup_dist; +#define FATAL_THEN_CLEANUP_PIXELS() if (FATALP) {FREE_SPLINE(); goto cleanup_pixels;} + + if (opts->despeckle_level > 0) { + despeckle(bitmap, opts->despeckle_level, opts->despeckle_tightness, opts->noise_removal, &exp); + FATAL_THEN_RETURN(); + } + + image_header.width = at_bitmap_get_width(bitmap); + image_header.height = at_bitmap_get_height(bitmap); + + if (opts->color_count > 0) { + quantize(bitmap, opts->color_count, opts->background_color, &myQuant, &exp); + if (myQuant) + quantize_object_free(myQuant); /* curently not used */ + FATAL_THEN_RETURN(); + } + + if (opts->centerline) { + if (opts->preserve_width) { + /* Preserve line width prior to thinning. */ + dist_map = new_distance_map(bitmap, 255, /*padded= */ TRUE, &exp); + dist = &dist_map; + FATAL_THEN_RETURN(); + } + /* Hereafter, dist is allocated. dist must be freed if + the execution is canceled or exception is raised; + use FATAL_THEN_CLEANUP_DIST. */ + thin_image(bitmap, opts->background_color, &exp); + FATAL_THEN_CLEANUP_DIST() + } + + /* Hereafter, pixels is allocated. pixels must be freed if + the execution is canceled; use CANCEL_THEN_CLEANUP_PIXELS. */ + if (opts->centerline) { + at_color background_color = { 0xff, 0xff, 0xff }; + if (opts->background_color) + background_color = *opts->background_color; + + pixels = find_centerline_pixels(bitmap, background_color, notify_progress, progress_data, test_cancel, testcancel_data, &exp); + } else + pixels = find_outline_pixels(bitmap, opts->background_color, notify_progress, progress_data, test_cancel, testcancel_data, &exp); + FATAL_THEN_CLEANUP_DIST(); + CANCEL_THEN_CLEANUP_DIST(); + + XMALLOC(splines, sizeof(at_splines_type)); + *splines = fitted_splines(pixels, opts, dist, image_header.width, image_header.height, &exp, notify_progress, progress_data, test_cancel, testcancel_data); + FATAL_THEN_CLEANUP_PIXELS(); + CANCEL_THEN_CLEANUP_PIXELS(); + + if (notify_progress) + notify_progress(1.0, progress_data); + +cleanup_pixels: + free_pixel_outline_list(&pixels); +cleanup_dist: + if (dist) + free_distance_map(dist); + return splines; +#undef CANCELP +#undef FATALP +#undef FREE_SPLINE +#undef CANCEL_THEN_CLEANUP_DIST +#undef CANCEL_THEN_CLEANUP_PIXELS + +#undef FATAL_THEN_RETURN +#undef FATAL_THEN_CLEANUP_DIST +#undef FATAL_THEN_CLEANUP_PIXELS + +} + +void at_splines_write(at_spline_writer * writer, FILE * writeto, gchar * file_name, at_output_opts_type * opts, at_splines_type * splines, at_msg_func msg_func, gpointer msg_data) +{ + gboolean new_opts = FALSE; + int llx, lly, urx, ury; + llx = 0; + lly = 0; + urx = splines->width; + ury = splines->height; + + if (!file_name) + file_name = ""; + + if (opts == NULL) { + new_opts = TRUE; + opts = at_output_opts_new(); + } + + setlocale(LC_NUMERIC, "C"); + (*writer->func) (writeto, file_name, llx, lly, urx, ury, opts, *splines, msg_func, msg_data, writer->data); + if (new_opts) + at_output_opts_free(opts); +} + +void at_splines_free(at_splines_type * splines) +{ + free_spline_list_array(splines); + if (splines->background_color) + at_color_free(splines->background_color); + free(splines); +} + +const char *at_version(gboolean long_format) +{ + if (long_format) + return "AutoTrace version " AUTOTRACE_VERSION; + + return AUTOTRACE_VERSION; +} + +const char *at_home_site(void) +{ + return AUTOTRACE_WEB; +} + +void autotrace_init(void) +{ + static int initialized = 0; + if (!initialized) { +#ifdef ENABLE_NLS + setlocale(LC_ALL, ""); + //bindtextdomain(PACKAGE, LOCALEDIR); +#endif /* Def: ENABLE_NLS */ + + /* Initialize subsystems */ + at_input_init(); + at_output_init(); + at_module_init(); + + initialized = 1; + } +} + +const char *at_fitting_opts_doc_func(char *string) +{ + return _(string); +} diff --git a/src/3rdparty/autotrace/autotrace.h b/src/3rdparty/autotrace/autotrace.h new file mode 100644 index 0000000..e56be9a --- /dev/null +++ b/src/3rdparty/autotrace/autotrace.h @@ -0,0 +1,413 @@ +/* autotrace.h --- Autotrace API + + Copyright (C) 2000, 2001, 2002 Martin Weber + + The author can be contacted at <martweb@gmx.net> + + 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 of the License, 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. */ + +#ifndef AUTOTRACE_H +#define AUTOTRACE_H + +#include <stdio.h> + +#include "types.h" +#include "color.h" + +#ifdef __cplusplus +extern "C" { +#endif /* __cplusplus */ + +#ifndef N_ +#define N_(x) x +#endif /* Not def: N_ */ + +/* ===================================================================== * + * Typedefs + * ===================================================================== */ + +/* Third degree is the highest we deal with. */ + enum _at_polynomial_degree { + AT_LINEARTYPE = 1, + AT_QUADRATICTYPE = 2, + AT_CUBICTYPE = 3, + AT_PARALLELELLIPSETYPE = 4, + AT_ELLIPSETYPE = 5, + AT_CIRCLETYPE = 6 + /* not the real number of points to define a + circle but to distinguish between a cubic spline */ + }; + + enum _at_msg_type { + AT_MSG_NOT_SET = 0, /* is used in autotrace internally */ + AT_MSG_FATAL = 1, + AT_MSG_WARNING, + }; + + typedef struct _at_fitting_opts_type at_fitting_opts_type; + typedef struct _at_input_opts_type at_input_opts_type; + typedef struct _at_output_opts_type at_output_opts_type; + typedef struct _at_bitmap at_bitmap; + typedef enum _at_polynomial_degree at_polynomial_degree; + typedef struct _at_spline_type at_spline_type; + typedef struct _at_spline_list_type at_spline_list_type; + typedef struct _at_spline_list_array_type at_spline_list_array_type; +#define at_splines_type at_spline_list_array_type + typedef enum _at_msg_type at_msg_type; + +/* A Bezier spline can be represented as four points in the real plane: + a starting point, ending point, and two control points. The + curve always lies in the convex hull defined by the four points. It + is also convenient to save the divergence of the spline from the + straight line defined by the endpoints. */ + struct _at_spline_type { + at_real_coord v[4]; /* The control points. */ + at_polynomial_degree degree; + gfloat linearity; + }; + +/* Each outline in a character is typically represented by many + splines. So, here is a list structure for that: */ + struct _at_spline_list_type { + at_spline_type *data; + unsigned length; + gboolean clockwise; + at_color color; + gboolean open; + }; + +/* Each character is in general made up of many outlines. So here is one + more list structure. */ + struct _at_spline_list_array_type { + at_spline_list_type *data; + unsigned length; + + /* splines bbox */ + unsigned short height, width; + + /* the values for following members are inherited from + at_fitting_opts_type */ + at_color *background_color; + gboolean centerline; + gboolean preserve_width; + gfloat width_weight_factor; + + }; + +/* Fitting option. + With using at_fitting_opts_doc macro, the description of + each option could be get. e.g. at_fitting_opts_doc(background_color) */ + struct _at_fitting_opts_type { +#define at_doc__background_color \ +N_("background-color <hexadezimal>: the color of the background that " \ +"should be ignored, for example FFFFFF; " \ +"default is no background color.") + at_color *background_color; + +#define at_doc__charcode \ +N_("charcode <unsigned>: code of character to load from GF file, " \ +"allowed are 0..255; default is the first character in font.") + unsigned charcode; + +#define at_doc__color_count \ +N_("color-count <unsigned>: number of colors a color bitmap is reduced to, " \ +"it does not work on grayscale, allowed are 1..256; " \ +"default is 0, that means not color reduction is done.") + unsigned color_count; + +#define at_doc__corner_always_threshold \ +N_("corner-always-threshold <angle-in-degrees>: if the angle at a pixel is " \ +"less than this, it is considered a corner, even if it is within " \ +"`corner-surround' pixels of another corner; default is 60. ") + gfloat corner_always_threshold; + +#define at_doc__corner_surround \ +N_("corner-surround <unsigned>: number of pixels on either side of a " \ +"point to consider when determining if that point is a corner; " \ +"default is 4. ") + unsigned corner_surround; + +#define at_doc__corner_threshold \ +N_("corner-threshold <angle-in-degrees>: if a pixel, its predecessor(s), " \ +"and its successor(s) meet at an angle smaller than this, it's a " \ +"corner; default is 100. ") + gfloat corner_threshold; + +#define at_doc__error_threshold \ +N_("error-threshold <real>: subdivide fitted curves that are off by " \ +"more pixels than this; default is 2.0. ") + gfloat error_threshold; + +#define at_doc__filter_iterations \ +N_("filter-iterations <unsigned>: smooth the curve this many times " \ +"before fitting; default is 4.") + unsigned filter_iterations; + +#define at_doc__line_reversion_threshold \ +N_("line-reversion-threshold <real>: if a spline is closer to a straight " \ +"line than this, weighted by the square of the curve length, keep it a " \ +"straight line even if it is a list with curves; default is .01. ") + gfloat line_reversion_threshold; + +#define at_doc__line_threshold \ +N_("line-threshold <real>: if the spline is not more than this far away " \ +"from the straight line defined by its endpoints," \ +"then output a straight line; default is 1. ") + gfloat line_threshold; + +#define at_doc__remove_adjacent_corners \ +N_("remove-adjacent-corners: remove corners that are adjacent; " \ +"default doesn't remove.") + gboolean remove_adjacent_corners; + +#define at_doc__tangent_surround \ +N_("tangent-surround <unsigned>: number of points on either side of a " \ +"point to consider when computing the tangent at that point; " \ +" default is 3.") + unsigned tangent_surround; + +#define at_doc__despeckle_level \ +N_("despeckle-level <unsigned>: 0..20; default is no despeckling. ") + unsigned despeckle_level; + +#define at_doc__despeckle_tightness \ +N_("despeckle-tightness <real>: 0.0..8.0; default is 2.0. ") + gfloat despeckle_tightness; + +#define at_doc__noise_removal \ +N_("noise-removal <real>: 1.0..0.0; default is 0.99. ") + gfloat noise_removal; + +#define at_doc__centerline \ +N_("centerline: trace a character's centerline, rather than its outline. ") + gboolean centerline; + +#define at_doc__preserve_width \ +N_("preserve-width: whether to preserve linewith with centerline fitting; " \ +"default doesn't preserve.") + gboolean preserve_width; + +#define at_doc__width_weight_factor \ +N_("width-weight-factor <real>: weight factor for fitting the linewidth.") + gfloat width_weight_factor; + }; + + struct _at_input_opts_type { + at_color *background_color; + unsigned charcode; /* Character code used only in GF input. */ + }; + + struct _at_output_opts_type { + int dpi; /* DPI is used only in MIF output. */ + }; + + struct _at_bitmap { + unsigned short height; + unsigned short width; + unsigned char *bitmap; + unsigned int np; + }; + + typedef + void (*at_msg_func) (const gchar * msg, at_msg_type msg_type, gpointer client_data); + +/* + * Autotrace initializer + */ +#define AUTOTRACE_INIT + void autotrace_init(void); + +/* + * IO Handler typedefs + */ + + typedef struct _at_bitmap_reader at_bitmap_reader; + struct _at_bitmap_reader; + + typedef struct _at_spline_writer at_spline_writer; + struct _at_spline_writer; + +/* + * Progress handler typedefs + * 0.0 <= percentage <= 1.0 + */ + typedef void (*at_progress_func) (gfloat percentage, gpointer client_data); + +/* + * Test cancel + * Return TRUE if auto-tracing should be stopped. + */ + typedef gboolean(*at_testcancel_func) (gpointer client_data); + +/* ===================================================================== * + * Functions + * ===================================================================== */ + +/* --------------------------------------------------------------------- * + * Fitting option related + * + * TODO: internal data access, copy + * --------------------------------------------------------------------- */ + at_fitting_opts_type *at_fitting_opts_new(void); + at_fitting_opts_type *at_fitting_opts_copy(at_fitting_opts_type * original); + void at_fitting_opts_free(at_fitting_opts_type * opts); + +/* Gettextize */ +#define at_fitting_opts_doc(opt) at_fitting_opts_doc_func(at_doc__##opt) +/* Don't use next function directly from clients */ + const char *at_fitting_opts_doc_func(char *string); + +/* --------------------------------------------------------------------- * + * Input option related + * + * TODO: internal data access + * --------------------------------------------------------------------- */ + at_input_opts_type *at_input_opts_new(void); + at_input_opts_type *at_input_opts_copy(at_input_opts_type * original); + void at_input_opts_free(at_input_opts_type * opts); + +/* --------------------------------------------------------------------- * + * Output option related + * + * TODO: internal data access + * --------------------------------------------------------------------- */ + at_output_opts_type *at_output_opts_new(void); + at_output_opts_type *at_output_opts_copy(at_output_opts_type * original); + void at_output_opts_free(at_output_opts_type * opts); + +/* --------------------------------------------------------------------- * + * Bitmap related + * + * TODO: internal data access + * --------------------------------------------------------------------- */ + +/* There is two way to build at_bitmap. + 1. Using input reader + Use at_bitmap_read. + at_input_get_handler_by_suffix or + at_input_get_handler will help you to get at_bitmap_reader. + 2. Allocating a bitmap and rendering an image on it by yourself + Use at_bitmap_new. + + In both case, you have to call at_bitmap_free when at_bitmap * + data are no longer needed. */ + at_bitmap *at_bitmap_read(at_bitmap_reader * reader, gchar * filename, at_input_opts_type * opts, at_msg_func msg_func, gpointer msg_data); + at_bitmap *at_bitmap_new(unsigned short width, unsigned short height, unsigned int planes); + at_bitmap *at_bitmap_copy(const at_bitmap * src); + +/* We have to export functions that supports internal datum + access. Such functions might be useful for + at_bitmap_new user. */ + unsigned short at_bitmap_get_width(const at_bitmap * bitmap); + unsigned short at_bitmap_get_height(const at_bitmap * bitmap); + unsigned short at_bitmap_get_planes(const at_bitmap * bitmap); + void at_bitmap_get_color(const at_bitmap * bitmap, unsigned int row, unsigned int col, at_color * color); + gboolean at_bitmap_equal_color(const at_bitmap * bitmap, unsigned int row, unsigned int col, at_color * color); + void at_bitmap_free(at_bitmap * bitmap); + +/* --------------------------------------------------------------------- * + * Spline related + * + * TODO: internal data access + * --------------------------------------------------------------------- */ +/* at_splines_new + + args: + + BITMAP is modified in at_splines_new according to opts. Therefore + if you need the original bitmap image, you have to make a backup of + BITMAP with using at_bitmap_copy. + + MSG_FUNC and MSG_DATA are used to notify a client errors and + warning from autotrace. NULL is valid value for MSG_FUNC if + the client is not interested in the notifications. */ + at_splines_type *at_splines_new(at_bitmap * bitmap, at_fitting_opts_type * opts, at_msg_func msg_func, gpointer msg_data); + +/* at_splines_new_full + + args: + + NOTIFY_PROGRESS is called repeatedly inside at_splines_new_full + to notify the progress of the execution. This might be useful for + interactive applications. NOTIFY_PROGRESS is called following + format: + + NOTIFY_PROGRESS (percentage, progress_data); + + test_cancel is called repeatedly inside at_splines_new_full + to test whether the execution is canceled or not. + If test_cancel returns TRUE, execution of at_splines_new_full + is stopped as soon as possible and returns NULL. If test_cancel + returns FALSE, nothing happens. test_cancel is called following + format: + + TEST_CANCEL (testcancel_data); + + NULL is valid value for notify_progress and/or test_cancel if + you don't need to know the progress of the execution and/or + cancel the execution */ + at_splines_type *at_splines_new_full(at_bitmap * bitmap, at_fitting_opts_type * opts, at_msg_func msg_func, gpointer msg_data, at_progress_func notify_progress, gpointer progress_data, at_testcancel_func test_cancel, gpointer testcancel_data); + + void at_splines_write(at_spline_writer * writer, FILE * writeto, gchar * file_name, at_output_opts_type * opts, at_splines_type * splines, at_msg_func msg_func, gpointer msg_data); + + void at_splines_free(at_splines_type * splines); + +/* --------------------------------------------------------------------- * + * Input related + * --------------------------------------------------------------------- */ + at_bitmap_reader *at_input_get_handler(gchar * filename); + at_bitmap_reader *at_input_get_handler_by_suffix(gchar * suffix); + + const char **at_input_list_new(void); + void at_input_list_free(const char **list); + +/* at_input_shortlist + return value: Do free by yourself */ + char *at_input_shortlist(void); + +/* --------------------------------------------------------------------- * + * Output related + * --------------------------------------------------------------------- */ + at_spline_writer *at_output_get_handler(gchar * filename); + at_spline_writer *at_output_get_handler_by_suffix(const gchar * suffix); + const char **at_output_list_new(void); + void at_output_list_free(const char **list); + +/* at_output_shortlist + return value: Do free by yourself */ + char *at_output_shortlist(void); + +/* --------------------------------------------------------------------- * + * Misc + * --------------------------------------------------------------------- */ + +/* at_version + + args: + LONG_FORMAT == TRUE: "AutoTrace version x.y" + LONG_FORMAT == FALSE: "x.y" + + return value: Don't free. It is allocated statically */ + const char *at_version(gboolean long_format); + +/* at_home_site + + return value: Don't free. It is allocated statically */ + const char *at_home_site(void); + +#ifdef __cplusplus +} +#endif /* __cplusplus */ +#endif /* AUTOTRACE_H */ diff --git a/src/3rdparty/autotrace/bitmap.c b/src/3rdparty/autotrace/bitmap.c new file mode 100644 index 0000000..759a0df --- /dev/null +++ b/src/3rdparty/autotrace/bitmap.c @@ -0,0 +1,8 @@ +/* bitmap.c: operations on bitmaps. */ + +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif /* Def: HAVE_CONFIG_H */ + +#include "bitmap.h" +#include "xstd.h" diff --git a/src/3rdparty/autotrace/bitmap.h b/src/3rdparty/autotrace/bitmap.h new file mode 100644 index 0000000..0f9b45a --- /dev/null +++ b/src/3rdparty/autotrace/bitmap.h @@ -0,0 +1,13 @@ +/* bitmap.h: definition for a bitmap type. No packing is done by + default; each pixel is represented by an entire byte. Among other + things, this means the type can be used for both grayscale and binary + images. */ + +#ifndef BITMAP_H +#define BITMAP_H + +#include "autotrace.h" +#include "input.h" +#include <stdio.h> + +#endif /* not BITMAP_H */ diff --git a/src/3rdparty/autotrace/cmdline.h b/src/3rdparty/autotrace/cmdline.h new file mode 100644 index 0000000..160a389 --- /dev/null +++ b/src/3rdparty/autotrace/cmdline.h @@ -0,0 +1,56 @@ +/* cmdline.h: macros to help process command-line arguments. */ + +#ifndef CMDLINE_H +#define CMDLINE_H + +#include "getopt.h" +#include "types.h" +#include <string.h> + +/* Test whether getopt found an option ``A''. + Assumes the option index is in the variable `option_index', and the + option table in a variable `long_options'. */ + +#define ARGUMENT_IS(a) (long_options[option_index].name != NULL && a != NULL && 0 == strcasecmp(long_options[option_index].name, a)) + +/* Perform common actions at the end of parsing the arguments. Assumes + lots of variables: `printed_version', a boolean for whether the + version number has been printed; `optind', the current option index; + `argc'; `argv'. */ + +#define FINISH_COMMAND_LINE() \ + do \ + { \ + /* Just wanted to know the version number? */ \ + if (printed_version && optind == argc) exit (0); \ + \ + /* Exactly one (non-empty) argument left? */ \ + if (optind + 1 == argc && *argv[optind] != 0) \ + { \ + return (argv[optind]); \ + } \ + else \ + { \ + fprintf (stderr, "Usage: %s [options] <image_name>.\n", argv[0]);\ + fprintf (stderr, "(%s.)\n", optind == argc ? "Missing <image_name>"\ + : "Too many <image_name>s"); \ + fputs ("For more information, use ``-help''.\n", stderr); \ + exit (1); \ + } \ + return NULL; /* stop warnings */ \ + } \ + while (0) + +#define GETOPT_USAGE \ +" You can use `--' or `-' to start an option.\n\ + You can use any unambiguous abbreviation for an option name.\n\ + You can separate option names and values with `=' or ` '.\n\ +" + +/* What to pass to `strtok' to separate different arguments to an + option, as in `-option=arg1,arg2,arg3'. It is useful to allow + whitespace as well so that the option value can come from a file, via + the shell construct "`cat file`" (including the quotes). */ +#define ARG_SEP ", \t\n" + +#endif /* not CMDLINE_H */ diff --git a/src/3rdparty/autotrace/color.c b/src/3rdparty/autotrace/color.c new file mode 100644 index 0000000..e986e9c --- /dev/null +++ b/src/3rdparty/autotrace/color.c @@ -0,0 +1,109 @@ +/* color.c: declarations for color handling. + + Copyright (C) 2000, 2001, 2002 Martin Weber + + The author can be contacted at <martweb@gmx.net> + + 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 of the License, 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. */ + +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif /* Def: HAVE_CONFIG_H */ + +#include "intl.h" +#include "color.h" +#include "exception.h" + +#include <string.h> +#include <stdlib.h> + +at_color *at_color_new(unsigned char r, unsigned char g, unsigned char b) +{ + at_color *color; + color = g_new(at_color, 1); + color->r = r; + color->g = g; + color->b = b; + return color; +} + +at_color *at_color_parse(const gchar * string, GError ** err) +{ + GError *local_err = NULL; + unsigned char c[6]; + int i; + + if (!string) + return NULL; + else if (string[0] == '\0') + return NULL; + else if (strlen(string) != 6) { + g_set_error(err, AT_ERROR, AT_ERROR_WRONG_COLOR_STRING, _("color string is too short: %s"), string); + return NULL; + } + + for (i = 0; i < 6; i++) { + char *endptr; + c[i] = (int)strtol(&string[i], &endptr, 16); + if (endptr == &string[i]) { + g_set_error(&local_err, AT_ERROR, AT_ERROR_WRONG_COLOR_STRING, _("wrong char in color string: %c"), string[i]); + g_propagate_error(err, local_err); + return NULL; + } + } + return at_color_new((unsigned char)(16 * c[0] + c[1]), (unsigned char)(16 * c[2] + c[3]), (unsigned char)(16 * c[4] + c[5])); +} + +at_color *at_color_copy(const at_color * original) +{ + if (original == NULL) + return NULL; + + return at_color_new(original->r, original->g, original->b); +} + +gboolean at_color_equal(const at_color * c1, const at_color * c2) +{ + if (c1 == c2 || ((c1->r == c2->r) && (c1->g == c2->g) && (c1->b == c2->b))) + return TRUE; + + return FALSE; +} + +void at_color_set(at_color * c, unsigned char r, unsigned char g, unsigned char b) +{ + g_return_if_fail(c); + c->r = r; + c->g = g; + c->b = b; +} + +unsigned char at_color_luminance(const at_color * color) +{ + return ((unsigned char)((color->r) * 0.30 + (color->g) * 0.59 + (color->b) * 0.11 + 0.5)); +} + +void at_color_free(at_color * color) +{ + g_free(color); +} + +GType at_color_get_type(void) +{ + static GType our_type = 0; + if (our_type == 0) + our_type = g_boxed_type_register_static("AtColor", (GBoxedCopyFunc) at_color_copy, (GBoxedFreeFunc) at_color_free); + return our_type; +} diff --git a/src/3rdparty/autotrace/color.h b/src/3rdparty/autotrace/color.h new file mode 100644 index 0000000..88651db --- /dev/null +++ b/src/3rdparty/autotrace/color.h @@ -0,0 +1,53 @@ +/* color.h: declarations for color handling. + + Copyright (C) 2000, 2001, 2002 Martin Weber + + The author can be contacted at <martweb@gmx.net> + + 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 of the License, 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. */ + +#ifndef AT_COLOR_H +#define AT_COLOR_H + +#include <glib.h> +#include <glib-object.h> + +#ifdef __cplusplus +extern "C" { +#endif /* __cplusplus */ + +typedef struct _at_color at_color; +struct _at_color { + guint8 r; + guint8 g; + guint8 b; +}; + +at_color *at_color_new(guint8 r, guint8 g, guint8 b); +at_color *at_color_parse(const gchar * string, GError ** err); +at_color *at_color_copy(const at_color * original); +gboolean at_color_equal(const at_color * c1, const at_color * c2); +void at_color_set(at_color * c1, guint8 r, guint8 g, guint8 b); +/* RGB to grayscale */ +unsigned char at_color_luminance(const at_color * color); +void at_color_free(at_color * color); + +GType at_color_get_type(void); +#define AT_TYPE_COLOR (at_color_get_type ()) + +#ifdef __cplusplus +} +#endif /* __cplusplus */ +#endif /* not AT_COLOR_H */ diff --git a/src/3rdparty/autotrace/config.h b/src/3rdparty/autotrace/config.h new file mode 100644 index 0000000..5d5d611 --- /dev/null +++ b/src/3rdparty/autotrace/config.h @@ -0,0 +1,118 @@ +/* config.h. Generated from config.h.in by configure. */ +/* config.h.in. Generated from configure.ac by autoheader. */ + +/* Package version */ +#define AUTOTRACE_VERSION "0.40.0" + +/* Project home page */ +#define AUTOTRACE_WEB "https://github.com/autotrace/autotrace" + +/* always defined to indicate that i18n is enabled */ +#define ENABLE_NLS 1 + +/* Define to the gettext package name. */ +#define GETTEXT_PACKAGE "autotrace" + +/* Define to 1 if you have the `bind_textdomain_codeset' function. */ +#define HAVE_BIND_TEXTDOMAIN_CODESET 1 + +/* Define to 1 if you have the Mac OS X function CFLocaleCopyCurrent in the + CoreFoundation framework. */ +/* #undef HAVE_CFLOCALECOPYCURRENT */ + +/* Define to 1 if you have the Mac OS X function CFPreferencesCopyAppValue in + the CoreFoundation framework. */ +/* #undef HAVE_CFPREFERENCESCOPYAPPVALUE */ + +/* Define to 1 if you have the `dcgettext' function. */ +#define HAVE_DCGETTEXT 1 + +/* Define to 1 if you have the <dlfcn.h> header file. */ +#define HAVE_DLFCN_H 1 + +/* Define if the GNU gettext() function is already present or preinstalled. */ +#define HAVE_GETTEXT 1 + +/* Define if you have the iconv() function and it works. */ +/* #undef HAVE_ICONV */ + +/* Define to 1 if you have the <inttypes.h> header file. */ +#define HAVE_INTTYPES_H 1 + +/* Define if your <locale.h> file defines LC_MESSAGES. */ +#define HAVE_LC_MESSAGES 1 + +/* PNG library is available or not */ +#define HAVE_LIBPNG 1 + +/* pstoedit library is available or not */ +#define HAVE_LIBPSTOEDIT 1 + +/* SWF library is available or not */ +/* #undef HAVE_LIBSWF */ + +/* Define to 1 if you have the <locale.h> header file. */ +#define HAVE_LOCALE_H 1 + +/* Define to 1 if you have the `localtime_r' function. */ +#define HAVE_LOCALTIME_R 1 + +/* ImageMagick library is available or not */ +#define HAVE_MAGICK 1 + +/* Define to 1 if you have the <malloc.h> header file. */ +#define HAVE_MALLOC_H 1 + +/* Define to 1 if you have the <memory.h> header file. */ +#define HAVE_MEMORY_H 1 + +/* Define to 1 if you have the <stdint.h> header file. */ +#define HAVE_STDINT_H 1 + +/* Define to 1 if you have the <stdlib.h> header file. */ +#define HAVE_STDLIB_H 1 + +/* Define to 1 if you have the <strings.h> header file. */ +#define HAVE_STRINGS_H 1 + +/* Define to 1 if you have the <string.h> header file. */ +#define HAVE_STRING_H 1 + +/* Define to 1 if you have the <sys/stat.h> header file. */ +#define HAVE_SYS_STAT_H 1 + +/* Define to 1 if you have the <sys/types.h> header file. */ +#define HAVE_SYS_TYPES_H 1 + +/* Define to 1 if you have the <unistd.h> header file. */ +#define HAVE_UNISTD_H 1 + +/* Define to the sub-directory where libtool stores uninstalled libraries. */ +#define LT_OBJDIR ".libs/" + +/* Package name */ +#define PACKAGE "autotrace" + +/* Define to the address where bug reports for this package should be sent. */ +#define PACKAGE_BUGREPORT "" + +/* Define to the full name of this package. */ +#define PACKAGE_NAME "autotrace" + +/* Define to the full name and version of this package. */ +#define PACKAGE_STRING "autotrace 0.40.0" + +/* Define to the one symbol short name of this package. */ +#define PACKAGE_TARNAME "autotrace" + +/* Define to the home page for this package. */ +#define PACKAGE_URL "" + +/* Define to the version of this package. */ +#define PACKAGE_VERSION "0.40.0" + +/* Define to 1 if you have the ANSI C header files. */ +#define STDC_HEADERS 1 + +/* Version number of package */ +#define VERSION "0.40.0" diff --git a/src/3rdparty/autotrace/curve.c b/src/3rdparty/autotrace/curve.c new file mode 100644 index 0000000..343c8fa --- /dev/null +++ b/src/3rdparty/autotrace/curve.c @@ -0,0 +1,255 @@ +/* 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. */ + +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif /* Def: HAVE_CONFIG_H */ + +#include "logreport.h" +#include "curve.h" +#include "xstd.h" + +static at_real_coord int_to_real_coord(at_coord); + +/* Return an entirely empty curve. */ + +curve_type new_curve(void) +{ + curve_type curve; + XMALLOC(curve, sizeof(struct curve)); + curve->point_list = NULL; + CURVE_LENGTH(curve) = 0; + CURVE_CYCLIC(curve) = FALSE; + CURVE_START_TANGENT(curve) = CURVE_END_TANGENT(curve) = NULL; + PREVIOUS_CURVE(curve) = NEXT_CURVE(curve) = NULL; + + return curve; +} + +/* Don't copy the points or tangents, but copy everything else. */ + +curve_type copy_most_of_curve(curve_type old_curve) +{ + curve_type curve = new_curve(); + + CURVE_CYCLIC(curve) = CURVE_CYCLIC(old_curve); + PREVIOUS_CURVE(curve) = PREVIOUS_CURVE(old_curve); + NEXT_CURVE(curve) = NEXT_CURVE(old_curve); + + return curve; +} + +/* 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). */ + +void free_curve(curve_type curve) +{ + if (CURVE_LENGTH(curve) > 0) + free(curve->point_list); + if (CURVE_START_TANGENT(curve)) + free(CURVE_START_TANGENT(curve)); + if (CURVE_END_TANGENT(curve)) + free(CURVE_END_TANGENT(curve)); +} + +void append_pixel(curve_type curve, at_coord coord) +{ + append_point(curve, int_to_real_coord(coord)); +} + +void append_point(curve_type curve, at_real_coord coord) +{ + CURVE_LENGTH(curve)++; + XREALLOC(curve->point_list, CURVE_LENGTH(curve) * sizeof(point_type)); + LAST_CURVE_POINT(curve) = coord; + /* The t value does not need to be set. */ +} + +/* 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. */ + +#define NUM_TO_PRINT 3 + +#define LOG_CURVE_POINT(c, p, print_t) \ + do \ + { \ + LOG ("(%.3f,%.3f)", CURVE_POINT (c, p).x, CURVE_POINT (c, p).y); \ + if (print_t) \ + LOG ("/%.2f", CURVE_T (c, p)); \ + } \ + while (0) + +void log_curve(curve_type curve, gboolean print_t) +{ + unsigned this_point; + + LOG("curve id = %lx:\n", (unsigned long)curve); + LOG(" length = %u.\n", CURVE_LENGTH(curve)); + if (CURVE_CYCLIC(curve)) + LOG(" cyclic.\n"); + + /* It should suffice to check just one of the tangents for being null + -- either they both should be, or neither should be. */ + if (CURVE_START_TANGENT(curve) != NULL) + LOG(" tangents = (%.3f,%.3f) & (%.3f,%.3f).\n", CURVE_START_TANGENT(curve)->dx, CURVE_START_TANGENT(curve)->dy, CURVE_END_TANGENT(curve)->dx, CURVE_END_TANGENT(curve)->dy); + + LOG(" "); + + /* If the curve is short enough, don't use ellipses. */ + if (CURVE_LENGTH(curve) <= NUM_TO_PRINT * 2) { + for (this_point = 0; this_point < CURVE_LENGTH(curve); this_point++) { + LOG_CURVE_POINT(curve, this_point, print_t); + LOG(" "); + + if (this_point != CURVE_LENGTH(curve) - 1 && (this_point + 1) % NUM_TO_PRINT == 0) + LOG("\n "); + } + } else { + for (this_point = 0; this_point < NUM_TO_PRINT && this_point < CURVE_LENGTH(curve); this_point++) { + LOG_CURVE_POINT(curve, this_point, print_t); + LOG(" "); + } + + LOG("...\n ..."); + + for (this_point = CURVE_LENGTH(curve) - NUM_TO_PRINT; this_point < CURVE_LENGTH(curve); this_point++) { + LOG(" "); + LOG_CURVE_POINT(curve, this_point, print_t); + } + } + + LOG(".\n"); +} + +/* Like `log_curve', but write the whole thing. */ + +void log_entire_curve(curve_type curve) +{ + unsigned this_point; + + LOG("curve id = %lx:\n", (unsigned long)curve); + LOG(" length = %u.\n", CURVE_LENGTH(curve)); + if (CURVE_CYCLIC(curve)) + LOG(" cyclic.\n"); + + /* It should suffice to check just one of the tangents for being null + -- either they both should be, or neither should be. */ + if (CURVE_START_TANGENT(curve) != NULL) + LOG(" tangents = (%.3f,%.3f) & (%.3f,%.3f).\n", CURVE_START_TANGENT(curve)->dx, CURVE_START_TANGENT(curve)->dy, CURVE_END_TANGENT(curve)->dx, CURVE_END_TANGENT(curve)->dy); + + LOG(" "); + + for (this_point = 0; this_point < CURVE_LENGTH(curve); this_point++) { + LOG(" "); + LOG_CURVE_POINT(curve, this_point, TRUE); + /* Compiler warning `Condition is always true' can be ignored */ + } + + LOG(".\n"); +} + +/* Return an initialized but empty curve list. */ + +curve_list_type new_curve_list(void) +{ + curve_list_type curve_list; + + curve_list.length = 0; + curve_list.data = NULL; + + return curve_list; +} + +/* Free a curve list and all the curves it contains. */ + +void free_curve_list(curve_list_type * curve_list) +{ + unsigned this_curve; + + for (this_curve = 0; this_curve < curve_list->length; this_curve++) { + free_curve(curve_list->data[this_curve]); + free(curve_list->data[this_curve]); + } + + /* If the character was empty, it won't have any curves. */ + free(curve_list->data); +} + +/* Add an element to a curve list. */ + +void append_curve(curve_list_type * curve_list, curve_type curve) +{ + curve_list->length++; + XREALLOC(curve_list->data, curve_list->length * sizeof(curve_type)); + curve_list->data[curve_list->length - 1] = curve; +} + +/* Return an initialized but empty curve list array. */ + +curve_list_array_type new_curve_list_array(void) +{ + curve_list_array_type curve_list_array; + + CURVE_LIST_ARRAY_LENGTH(curve_list_array) = 0; + curve_list_array.data = NULL; + + return curve_list_array; +} + +/* Free a curve list array and all the curve lists it contains. */ + +void free_curve_list_array(curve_list_array_type * curve_list_array, at_progress_func notify_progress, gpointer client_data) +{ + unsigned this_list; + + for (this_list = 0; this_list < CURVE_LIST_ARRAY_LENGTH(*curve_list_array); this_list++) { + if (notify_progress) + notify_progress(((gfloat) this_list) / (CURVE_LIST_ARRAY_LENGTH(*curve_list_array) * (gfloat) 3.0) + (gfloat) 0.666, client_data); + free_curve_list(&CURVE_LIST_ARRAY_ELT(*curve_list_array, this_list)); + } + + /* If the character was empty, it won't have any curves. */ + free(curve_list_array->data); +} + +/* Add an element to a curve list array. */ + +void append_curve_list(curve_list_array_type * curve_list_array, curve_list_type curve_list) +{ + CURVE_LIST_ARRAY_LENGTH(*curve_list_array)++; + XREALLOC(curve_list_array->data, CURVE_LIST_ARRAY_LENGTH(*curve_list_array) * sizeof(curve_list_type)); + LAST_CURVE_LIST_ARRAY_ELT(*curve_list_array) = curve_list; +} + +/* Turn an integer point into a real one. */ + +static at_real_coord int_to_real_coord(at_coord int_coord) +{ + at_real_coord real_coord; + + real_coord.x = int_coord.x; + real_coord.y = int_coord.y; + real_coord.z = 0.0; + + return real_coord; +} diff --git a/src/3rdparty/autotrace/curve.h b/src/3rdparty/autotrace/curve.h new file mode 100644 index 0000000..1efcf4e --- /dev/null +++ b/src/3rdparty/autotrace/curve.h @@ -0,0 +1,131 @@ +/* curve.h: data structures for the conversion from pixels to splines. */ + +#ifndef CURVE_H +#define CURVE_H + +#include "autotrace.h" +#include "vector.h" + +/* We are simultaneously manipulating two different representations of + the same outline: one based on (x,y) positions in the plane, and one + based on parametric splines. (We are trying to match the latter to + the former.) Although the original (x,y)'s are pixel positions, + i.e., integers, after filtering they are reals. */ + +typedef struct { + at_real_coord coord; + gfloat t; +} point_type; + +/* It turns out to be convenient to break the list of all the pixels in + the outline into sublists, divided at ``corners''. Then each of the + sublists is treated independently. Each of these sublists is a `curve'. */ + +struct curve { + point_type *point_list; + unsigned length; + gboolean cyclic; + vector_type *start_tangent; + vector_type *end_tangent; + struct curve *previous; + struct curve *next; +}; + +typedef struct curve *curve_type; + +/* Get at the coordinates and the t values. */ +#define CURVE_POINT(c, n) ((c)->point_list[n].coord) +#define LAST_CURVE_POINT(c) ((c)->point_list[(c)->length-1].coord) +#define CURVE_T(c, n) ((c)->point_list[n].t) +#define LAST_CURVE_T(c) ((c)->point_list[(c)->length-1].t) + +/* This is the length of `point_list'. */ +#define CURVE_LENGTH(c) ((c)->length) + +/* A curve is ``cyclic'' if it didn't have any corners, after all, so + the last point is adjacent to the first. */ +#define CURVE_CYCLIC(c) ((c)->cyclic) + +/* If the curve is cyclic, the next and previous points should wrap + around; otherwise, if we get to the end, we return CURVE_LENGTH and + -1, respectively. */ +#define CURVE_NEXT(c, n) \ + ((n) + 1 >= CURVE_LENGTH (c) \ + ? CURVE_CYCLIC (c) ? ((n) + 1) % CURVE_LENGTH (c) : CURVE_LENGTH (c) \ + : (n) + 1) +#define CURVE_PREV(c, n) \ + ((signed int) (n) - 1 < 0 \ + ? CURVE_CYCLIC (c) ? (signed int) CURVE_LENGTH (c) + (signed int) (n) - 1 : -1\ + : (signed int) (n) - 1) + +/* The tangents at the endpoints are computed using the neighboring curves. */ +#define CURVE_START_TANGENT(c) ((c)->start_tangent) +#define CURVE_END_TANGENT(c) ((c)->end_tangent) +#define PREVIOUS_CURVE(c) ((c)->previous) +#define NEXT_CURVE(c) ((c)->next) + +/* Return an entirely empty curve. */ +extern curve_type new_curve(void); + +/* Return a curve the same as C, except without any points. */ +extern curve_type copy_most_of_curve(curve_type c); + +/* Free the memory C uses. */ +extern void free_curve(curve_type c); + +/* Append the point P to the end of C's list. */ +extern void append_pixel(curve_type c, at_coord p); + +/* Like `append_pixel', for a point in real coordinates. */ +extern void append_point(curve_type c, at_real_coord p); + +/* Write some or all, respectively, of the curve C in human-readable + form to the log file, if logging is enabled. */ +extern void log_curve(curve_type c, gboolean print_t); +extern void log_entire_curve(curve_type c); + +/* Display the curve C online, if displaying is enabled. */ +extern void display_curve(curve_type); + +/* So, an outline is a list of curves. */ +typedef struct { + curve_type *data; + unsigned length; + gboolean clockwise; + gboolean open; +} curve_list_type; + +/* Number of curves in the list. */ +#define CURVE_LIST_LENGTH(c_l) ((c_l).length) + +/* Access the individual curves. */ +#define CURVE_LIST_ELT(c_l, n) ((c_l).data[n]) +#define LAST_CURVE_LIST_ELT(c_l) ((c_l).data[CURVE_LIST_LENGTH (c_l) - 1]) + +/* Says whether the outline that this curve list represents moves + clockwise or counterclockwise. */ +#define CURVE_LIST_CLOCKWISE(c_l) ((c_l).clockwise) + +extern curve_list_type new_curve_list(void); +extern void free_curve_list(curve_list_type *); +extern void append_curve(curve_list_type *, curve_type); + +/* And a character is a list of outlines. I named this + `curve_list_array_type' because `curve_list_list_type' seemed pretty + monstrous. */ +typedef struct { + curve_list_type *data; + unsigned length; +} curve_list_array_type; + +/* Turns out we can use the same definitions for lists of lists as for + just lists. But we define the usual names, just in case. */ +#define CURVE_LIST_ARRAY_LENGTH CURVE_LIST_LENGTH +#define CURVE_LIST_ARRAY_ELT CURVE_LIST_ELT +#define LAST_CURVE_LIST_ARRAY_ELT LAST_CURVE_LIST_ELT + +extern curve_list_array_type new_curve_list_array(void); +extern void free_curve_list_array(curve_list_array_type *, at_progress_func, gpointer); +extern void append_curve_list(curve_list_array_type *, curve_list_type); + +#endif /* not CURVE_H */ diff --git a/src/3rdparty/autotrace/datetime.c b/src/3rdparty/autotrace/datetime.c new file mode 100644 index 0000000..ff3e779 --- /dev/null +++ b/src/3rdparty/autotrace/datetime.c @@ -0,0 +1,20 @@ +#include <stdlib.h> +#include <time.h> +#include <config.h> + +char *at_time_string(void) +{ + char *time_string = calloc(sizeof(char), 25); + time_t t = time(NULL); +#if HAVE_LOCALTIME_R + struct tm newtime; + + localtime_r(&t, &newtime); + strftime(time_string, 25, "%c", &newtime); +#else + // the mingw-w64 toolchain does not have localtime_r() + strftime(time_string, 25, "%c", localtime(&t)); +#endif + + return time_string; +} diff --git a/src/3rdparty/autotrace/datetime.h b/src/3rdparty/autotrace/datetime.h new file mode 100644 index 0000000..afc6140 --- /dev/null +++ b/src/3rdparty/autotrace/datetime.h @@ -0,0 +1 @@ +char *at_time_string(void); diff --git a/src/3rdparty/autotrace/despeckle.c b/src/3rdparty/autotrace/despeckle.c new file mode 100644 index 0000000..3ab66ac --- /dev/null +++ b/src/3rdparty/autotrace/despeckle.c @@ -0,0 +1,710 @@ +/* despeckle.c: Bitmap despeckler + + Copyright (C) 2001 David A. Bartold / Martin Weber + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public License + as published by the Free Software Foundation; either version 2.1 of + the License, or (at your option) any later version. + + This library 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 + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with this library; if not, write to the Free Software + Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 + USA. */ + +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif /* Def: HAVE_CONFIG_H */ + +#include <assert.h> +#include <math.h> +#include <stdio.h> +#include <time.h> +#include "xstd.h" +#include "logreport.h" +#include "types.h" +#include "bitmap.h" +#include "despeckle.h" + +/* Calculate Error - compute the error between two colors + * + * Input parameters: + * Two 24 bit RGB colors + * + * Returns: + * The squared error between the two colors + */ + +static int calc_error(unsigned char *color1, unsigned char *color2) +{ + int the_error; + int temp; + + temp = color1[0] - color2[0]; + the_error = temp * temp; + temp = color1[1] - color2[1]; + the_error += temp * temp; + temp = color1[2] - color2[2]; + the_error += temp * temp; + + return the_error; +} + +/* Calculate Error - compute the error between two colors + * + * Input parameters: + * Two 8 bit gray scale colors + * + * Returns: + * The squared error between the two colors + */ + +static int calc_error_8(unsigned char *color1, unsigned char *color2) +{ + int the_error; + + the_error = abs(color1[0] - color2[0]); + + return the_error; +} + +/* Find Size - Find the number of adjacent pixels of the same color + * + * Input Parameters: + * An 24 bit image, the current location inside the image, and the palette + * index of the color we are looking for + * + * Modified Parameters: + * A mask array used to prevent backtracking over already counted pixels + * + * Returns: + * Number of adjacent pixels found having the same color + */ + +static int find_size( /* in */ unsigned char *index, + /* in */ int x, + /* in */ int y, + /* in */ int width, + /* in */ int height, + /* in */ unsigned char *bitmap, + /* in/out */ unsigned char *mask) +{ + int count; + int x1, x2; + + if (y < 0 || y >= height || mask[y * width + x] == 1 || bitmap[3 * (y * width + x)] != index[0] || bitmap[3 * (y * width + x) + 1] != index[1] || bitmap[3 * (y * width + x) + 2] != index[2]) + return 0; + + for (x1 = x; x1 >= 0 && bitmap[3 * (y * width + x1)] == index[0] && bitmap[3 * (y * width + x1) + 1] == index[1] && bitmap[3 * (y * width + x1) + 2] == index[2] && mask[y * width + x] != 1; x1--) ; + x1++; + + for (x2 = x; x2 < width && bitmap[3 * (y * width + x2)] == index[0] && bitmap[3 * (y * width + x2) + 1] == index[1] && bitmap[3 * (y * width + x2) + 2] == index[2] && mask[y * width + x] != 1; x2++) ; + x2--; + + count = x2 - x1 + 1; + for (x = x1; x <= x2; x++) + mask[y * width + x] = 1; + + for (x = x1; x <= x2; x++) { + count += find_size(index, x, y - 1, width, height, bitmap, mask); + count += find_size(index, x, y + 1, width, height, bitmap, mask); + } + + return count; +} + +/* Find Size - Find the number of adjacent pixels of the same color + * + * Input Parameters: + * An 8 bit image, the current location inside the image, and the palette + * index of the color we are looking for + * + * Modified Parameters: + * A mask array used to prevent backtracking over already counted pixels + * + * Returns: + * Number of adjacent pixels found having the same color + */ + +static int find_size_8( /* in */ unsigned char *index, + /* in */ int x, + /* in */ int y, + /* in */ int width, + /* in */ int height, + /* in */ unsigned char *bitmap, + /* in/out */ unsigned char *mask) +{ + int count; + int x1, x2; + + if (y < 0 || y >= height || mask[y * width + x] == 1 || bitmap[(y * width + x)] != index[0]) + return 0; + + for (x1 = x; x1 >= 0 && bitmap[(y * width + x1)] == index[0] && mask[y * width + x] != 1; x1--) ; + x1++; + + for (x2 = x; x2 < width && bitmap[(y * width + x2)] == index[0] && mask[y * width + x] != 1; x2++) ; + x2--; + + count = x2 - x1 + 1; + for (x = x1; x <= x2; x++) + mask[y * width + x] = 1; + + for (x = x1; x <= x2; x++) { + count += find_size_8(index, x, y - 1, width, height, bitmap, mask); + count += find_size_8(index, x, y + 1, width, height, bitmap, mask); + } + + return count; +} + +/* Find Most Similar Neighbor - Given a position in an 24 bit bitmap and a color + * index, traverse over a blob of adjacent pixels having the same value. + * Return the color index of the neighbor pixel that has the most similar + * color. + * + * Input parameters: + * 24 bit bitmap, the current location inside the image, + * and the color index of the blob + * + * Modified parameters: + * Mask used to prevent backtracking + * + * Output parameters: + * Closest index != index and the error between the two colors squared + */ + +static void find_most_similar_neighbor( /* in */ unsigned char *index, + /* in/out */ unsigned char **closest_index, + /* in/out */ int *error_amt, + /* in */ int x, + /* in */ int y, + /* in */ int width, + /* in */ int height, + /* in */ unsigned char *bitmap, + /* in/out */ unsigned char *mask) +{ + int x1, x2; + int temp_error; + unsigned char *value, *temp; + + if (y < 0 || y >= height || mask[y * width + x] == 2) + return; + + temp = &bitmap[3 * (y * width + x)]; + + assert(closest_index != NULL); + + if (temp[0] != index[0] || temp[1] != index[1] || temp[2] != index[2]) { + value = temp; + + temp_error = calc_error(index, value); + + if (*closest_index == NULL || temp_error < *error_amt) + *closest_index = value, *error_amt = temp_error; + + return; + } + + for (x1 = x; x1 >= 0 && bitmap[3 * (y * width + x1)] == index[0] && bitmap[3 * (y * width + x1) + 1] == index[1] && bitmap[3 * (y * width + x1) + 2] == index[2]; x1--) ; + x1++; + + for (x2 = x; x2 < width && bitmap[3 * (y * width + x2)] == index[0] && bitmap[3 * (y * width + x2) + 1] == index[1] && bitmap[3 * (y * width + x2) + 2] == index[2]; x2++) ; + x2--; + + if (x1 > 0) { + value = &bitmap[3 * (y * width + x1 - 1)]; + + temp_error = calc_error(index, value); + + if (*closest_index == NULL || temp_error < *error_amt) + *closest_index = value, *error_amt = temp_error; + } + + if (x2 < width - 1) { + value = &bitmap[3 * (y * width + x2 + 1)]; + + temp_error = calc_error(index, value); + + if (*closest_index == NULL || temp_error < *error_amt) + *closest_index = value, *error_amt = temp_error; + } + + for (x = x1; x <= x2; x++) + mask[y * width + x] = 2; + + for (x = x1; x <= x2; x++) { + find_most_similar_neighbor(index, closest_index, error_amt, x, y - 1, width, height, bitmap, mask); + find_most_similar_neighbor(index, closest_index, error_amt, x, y + 1, width, height, bitmap, mask); + } +} + +/* Find Most Similar Neighbor - Given a position in an 8 bit bitmap and a color + * index, traverse over a blob of adjacent pixels having the same value. + * Return the color index of the neighbor pixel that has the most similar + * color. + * + * Input parameters: + * 8 bit bitmap, the current location inside the image, + * and the color index of the blob + * + * Modified parameters: + * Mask used to prevent backtracking + * + * Output parameters: + * Closest index != index and the error between the two colors squared + */ + +static void find_most_similar_neighbor_8( /* in */ unsigned char *index, + /* in/out */ unsigned char **closest_index, + /* in/out */ int *error_amt, + /* in */ int x, + /* in */ int y, + /* in */ int width, + /* in */ int height, + /* in */ unsigned char *bitmap, + /* in/out */ unsigned char *mask) +{ + int x1, x2; + int temp_error; + unsigned char *value, *temp; + + if (y < 0 || y >= height || mask[y * width + x] == 2) + return; + + temp = &bitmap[(y * width + x)]; + + assert(closest_index != NULL); + + if (temp[0] != index[0]) { + value = temp; + + temp_error = calc_error_8(index, value); + + if (*closest_index == NULL || temp_error < *error_amt) + *closest_index = value, *error_amt = temp_error; + + return; + } + + for (x1 = x; x1 >= 0 && bitmap[(y * width + x1)] == index[0]; x1--) ; + x1++; + + for (x2 = x; x2 < width && bitmap[(y * width + x2)] == index[0]; x2++) ; + x2--; + + if (x1 > 0) { + value = &bitmap[(y * width + x1 - 1)]; + + temp_error = calc_error_8(index, value); + + if (*closest_index == NULL || temp_error < *error_amt) + *closest_index = value, *error_amt = temp_error; + } + + if (x2 < width - 1) { + value = &bitmap[(y * width + x2 + 1)]; + + temp_error = calc_error_8(index, value); + + if (*closest_index == NULL || temp_error < *error_amt) + *closest_index = value, *error_amt = temp_error; + } + + for (x = x1; x <= x2; x++) + mask[y * width + x] = 2; + + for (x = x1; x <= x2; x++) { + find_most_similar_neighbor_8(index, closest_index, error_amt, x, y - 1, width, height, bitmap, mask); + find_most_similar_neighbor_8(index, closest_index, error_amt, x, y + 1, width, height, bitmap, mask); + } +} + +/* Fill - change the color of a blob + * + * Input parameters: + * The new color + * + * Modified parameters: + * 24 bit pixbuf and its mask (used to prevent backtracking) + */ + +static void fill( /* in */ unsigned char *to_index, + /* in */ int x, + /* in */ int y, + /* in */ int width, + /* in */ int height, + /* in/out */ unsigned char *bitmap, + /* in/out */ unsigned char *mask) +{ + int x1, x2; + + if (y < 0 || y >= height || mask[y * width + x] != 2) + return; + + for (x1 = x; x1 >= 0 && mask[y * width + x1] == 2; x1--) ; + x1++; + for (x2 = x; x2 < width && mask[y * width + x2] == 2; x2++) ; + x2--; + + assert(x1 >= 0 && x2 < width); + + for (x = x1; x <= x2; x++) { + bitmap[3 * (y * width + x)] = to_index[0]; + bitmap[3 * (y * width + x) + 1] = to_index[1]; + bitmap[3 * (y * width + x) + 2] = to_index[2]; + mask[y * width + x] = 3; + } + + for (x = x1; x <= x2; x++) { + fill(to_index, x, y - 1, width, height, bitmap, mask); + fill(to_index, x, y + 1, width, height, bitmap, mask); + } +} + +/* Fill - change the color of a blob + * + * Input parameters: + * The new color + * + * Modified parameters: + * 8 bit pixbuf and its mask (used to prevent backtracking) + */ + +static void fill_8( /* in */ unsigned char *to_index, + /* in */ int x, + /* in */ int y, + /* in */ int width, + /* in */ int height, + /* in/out */ unsigned char *bitmap, + /* in/out */ unsigned char *mask) +{ + int x1, x2; + + if (y < 0 || y >= height || mask[y * width + x] != 2) + return; + + for (x1 = x; x1 >= 0 && mask[y * width + x1] == 2; x1--) ; + x1++; + for (x2 = x; x2 < width && mask[y * width + x2] == 2; x2++) ; + x2--; + + assert(x1 >= 0 && x2 < width); + + for (x = x1; x <= x2; x++) { + bitmap[(y * width + x)] = to_index[0]; + mask[y * width + x] = 3; + } + + for (x = x1; x <= x2; x++) { + fill_8(to_index, x, y - 1, width, height, bitmap, mask); + fill_8(to_index, x, y + 1, width, height, bitmap, mask); + } +} + +/* Ignore - blob is big enough, mask it off + * + * Modified parameters: + * its mask (used to prevent backtracking) + */ + +static void ignore( /* in */ int x, + /* in */ int y, + /* in */ int width, + /* in */ int height, + /* in/out */ unsigned char *mask) +{ + int x1, x2; + + if (y < 0 || y >= height || mask[y * width + x] != 1) + return; + + for (x1 = x; x1 >= 0 && mask[y * width + x1] == 1; x1--) ; + x1++; + for (x2 = x; x2 < width && mask[y * width + x2] == 1; x2++) ; + x2--; + + assert(x1 >= 0 && x2 < width); + + for (x = x1; x <= x2; x++) + mask[y * width + x] = 3; + + for (x = x1; x <= x2; x++) { + ignore(x, y - 1, width, height, mask); + ignore(x, y + 1, width, height, mask); + } +} + +/* Recolor - conditionally change a feature's color to the closest color of all + * neighboring pixels + * + * Input parameters: + * The color palette, current blob size, and adaptive tightness + * + * Adaptive Tightness: (integer 1 to 256) + * 1 = really tight + * 256 = turn off the feature + * + * Modified parameters: + * 24 bit pixbuf and its mask (used to prevent backtracking) + * + * Returns: + * TRUE - feature was recolored, thus coalesced + * FALSE - feature wasn't recolored + */ + +static gboolean recolor( /* in */ double adaptive_tightness, + /* in */ int x, + /* in */ int y, + /* in */ int width, + /* in */ int height, + /* in/out */ unsigned char *bitmap, + /* in/out */ unsigned char *mask) +{ + unsigned char *index, *to_index; + int error_amt, max_error; + + index = &bitmap[3 * (y * width + x)]; + to_index = NULL; + error_amt = 0; + max_error = (int)(3.0 * adaptive_tightness * adaptive_tightness); + + find_most_similar_neighbor(index, &to_index, &error_amt, x, y, width, height, bitmap, mask); + + /* This condition only fails if the bitmap is all the same color */ + if (to_index != NULL) { + /* + * If the difference between the two colors is too great, + * don't coalesce the feature with its neighbor(s). This prevents a + * color from turning into its complement. + */ + + if (calc_error(index, to_index) > max_error) + fill(index, x, y, width, height, bitmap, mask); + else { + fill(to_index, x, y, width, height, bitmap, mask); + + return TRUE; + } + } + + return FALSE; +} + +/* Recolor - conditionally change a feature's color to the closest color of all + * neighboring pixels + * + * Input parameters: + * The color palette, current blob size, and adaptive tightness + * + * Adaptive Tightness: (integer 1 to 256) + * 1 = really tight + * 256 = turn off the feature + * + * Modified parameters: + * 8 bit pixbuf and its mask (used to prevent backtracking) + * + * Returns: + * TRUE - feature was recolored, thus coalesced + * FALSE - feature wasn't recolored + */ + +static gboolean recolor_8( /* in */ double adaptive_tightness, + /* in */ int x, + /* in */ int y, + /* in */ int width, + /* in */ int height, + /* in/out */ unsigned char *bitmap, + /* in/out */ unsigned char *mask) +{ + unsigned char *index, *to_index; + int error_amt; + + index = &bitmap[(y * width + x)]; + to_index = NULL; + error_amt = 0; + + find_most_similar_neighbor_8(index, &to_index, &error_amt, x, y, width, height, bitmap, mask); + + /* This condition only fails if the bitmap is all the same color */ + if (to_index != NULL) { + /* + * If the difference between the two colors is too great, + * don't coalesce the feature with its neighbor(s). This prevents a + * color from turning into its complement. + */ + + if (calc_error_8(index, to_index) > adaptive_tightness) + fill_8(index, x, y, width, height, bitmap, mask); + else { + fill_8(to_index, x, y, width, height, bitmap, mask); + + return TRUE; + } + } + + return FALSE; +} + +/* Despeckle Iteration - Despeckle all regions smaller than cur_size pixels + * + * Input Parameters: + * Current blob size, maximum blob size + * for all iterations (used to selectively recolor blobs), adaptive + * tightness and noise removal + * + * Modified Parameters: + * The 24 bit pixbuf is despeckled + */ + +static void despeckle_iteration( /* in */ int level, + /* in */ double adaptive_tightness, + /* in */ double noise_max, + /* in */ int width, + /* in */ int height, + /* in/out */ unsigned char *bitmap) +{ + unsigned char *mask; + int x, y; + int current_size; + int tightness; + + /* Size doubles each iteration level, so current_size = 2^level */ + current_size = 1 << level; + tightness = (int)(noise_max / (1.0 + adaptive_tightness * level)); + + mask = (unsigned char *)calloc(width * height, sizeof(unsigned char)); + for (y = 0; y < height; y++) { + for (x = 0; x < width; x++) { + if (mask[y * width + x] == 0) { + int size; + + size = find_size(&bitmap[3 * (y * width + x)], x, y, width, height, bitmap, mask); + + assert(size > 0); + + if (size < current_size) { + if (recolor(tightness, x, y, width, height, bitmap, mask)) + x--; + } else + ignore(x, y, width, height, mask); + } + } + } + + free(mask); +} + +/* Despeckle Iteration - Despeckle all regions smaller than cur_size pixels + * + * Input Parameters: + * Current blob size, maximum blob size + * for all iterations (used to selectively recolor blobs), adaptive + * tightness and noise removal + * + * Modified Parameters: + * The 8 bit pixbuf is despeckled + */ + +static void despeckle_iteration_8( /* in */ int level, + /* in */ double adaptive_tightness, + /* in */ double noise_max, + /* in */ int width, + /* in */ int height, + /* in/out */ unsigned char *bitmap) +{ + unsigned char *mask; + int x, y; + int current_size; + int tightness; + + /* Size doubles each iteration level, so current_size = 2^level */ + current_size = 1 << level; + tightness = (int)(noise_max / (1.0 + adaptive_tightness * level)); + + mask = (unsigned char *)calloc(width * height, sizeof(unsigned char)); + for (y = 0; y < height; y++) { + for (x = 0; x < width; x++) { + if (mask[y * width + x] == 0) { + int size; + + size = find_size_8(&bitmap[(y * width + x)], x, y, width, height, bitmap, mask); + + assert(size > 0); + + if (size < current_size) { + if (recolor_8(tightness, x, y, width, height, bitmap, mask)) + x--; + } else + ignore(x, y, width, height, mask); + } + } + } + + free(mask); +} + +/* Despeckle - Despeckle a 8 or 24 bit image + * + * Input Parameters: + * Adaptive feature coalescing value, the despeckling level and noise removal + * + * Despeckling level (level): Integer from 0 to ~20 + * 0 = perform no despeckling + * An increase of the despeckling level by one doubles the size of features. + * The Maximum value must be smaller then the logarithm base two of the number + * of pixels. + * + * Feature coalescing (tightness): Real from 0.0 to ~8.0 + * 0 = Turn it off (whites may turn black and vice versa, etc) + * 3 = Good middle value + * 8 = Really tight + * + * Noise removal (noise_removal): Real from 1.0 to 0.0 + * 1 = Maximum noise removal + * You should always use the highest value, only if certain parts of the image + * disappear you should lower it. + * + * Modified Parameters: + * The bitmap is despeckled. + */ + +void despeckle( /* in/out */ at_bitmap * bitmap, + /* in */ int level, + /* in */ gfloat tightness, + /* in */ gfloat noise_removal, + /* exception handling */ at_exception_type * excep) +{ + int i, planes, max_level; + short width, height; + unsigned char *bits; + double noise_max, adaptive_tightness; + + planes = AT_BITMAP_PLANES(bitmap); + noise_max = noise_removal * 255.0; + width = AT_BITMAP_WIDTH(bitmap); + height = AT_BITMAP_HEIGHT(bitmap); + bits = AT_BITMAP_BITS(bitmap); + max_level = (int)(log(width * height) / log(2.0) - 0.5); + if (level > max_level) + level = max_level; + adaptive_tightness = (noise_removal * (1.0 + tightness * level) - 1.0) / level; + + if (planes == 3) { + for (i = 0; i < level; i++) + despeckle_iteration(i, adaptive_tightness, noise_max, width, height, bits); + } else if (planes == 1) { + for (i = 0; i < level; i++) + despeckle_iteration_8(i, adaptive_tightness, noise_max, width, height, bits); + } else { + LOG("despeckle: %u-plane images are not supported", planes); + at_exception_fatal(excep, "despeckle: wrong plane images are passed"); + return; + } + +} diff --git a/src/3rdparty/autotrace/despeckle.h b/src/3rdparty/autotrace/despeckle.h new file mode 100644 index 0000000..3b206e7 --- /dev/null +++ b/src/3rdparty/autotrace/despeckle.h @@ -0,0 +1,54 @@ +/* despeckle.h: Bitmap despeckler for AutoTrace + + Copyright (C) 2001 David A. Bartold / Martin Weber + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public License + as published by the Free Software Foundation; either version 2.1 of + the License, or (at your option) any later version. + + This library 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 + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with this library; if not, write to the Free Software + Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 + USA. */ + +#ifndef DESPECKLE_H +#define DESPECKLE_H + +#include "types.h" +#include "bitmap.h" +#include "exception.h" + +/* Despeckle - Despeckle a 8 or 24 bit image + * + * Input Parameters: + * Adaptive feature coalescing value, the despeckling level and noise removal + * + * Despeckling level (level): Integer from 0 to ~20 + * 0 = perform no despeckling + * An increase of the despeckling level by one doubles the size of features. + * The Maximum value must be smaller then the logarithm base two of the number + * of pixels. + * + * Feature coalescing (tightness): Real from 0.0 to ~8.0 + * 0 = Turn it off (whites may turn black and vice versa, etc) + * 3 = Good middle value + * 8 = Really tight + * + * Noise removal (noise_removal): Real from 1.0 to 0.0 + * 1 = Maximum noise removal + * You should always use the highest value, only if certain parts of the image + * disappear you should lower it. + * + * Modified Parameters: + * The bitmap is despeckled. + */ + +extern void despeckle(at_bitmap * bitmap, int level, gfloat tightness, gfloat noise_removal, at_exception_type * exp); + +#endif /* not DESPECKLE_H */ diff --git a/src/3rdparty/autotrace/epsilon-equal.c b/src/3rdparty/autotrace/epsilon-equal.c new file mode 100644 index 0000000..8d26886 --- /dev/null +++ b/src/3rdparty/autotrace/epsilon-equal.c @@ -0,0 +1,22 @@ +/* epsilon-equal.c: define a error resist compare. */ + +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif /* Def: HAVE_CONFIG_H */ + +#include "types.h" +#include "epsilon-equal.h" +#include <math.h> + +/* Numerical errors sometimes make a floating point number just slightly + larger or smaller than its TRUE value. When it matters, we need to + compare with some tolerance, REAL_EPSILON, defined in kbase.h. */ + +gboolean epsilon_equal(gfloat v1, gfloat v2) +{ + if (v1 == v2 /* Usually they'll be exactly equal, anyway. */ + || fabs(v1 - v2) <= REAL_EPSILON) + return TRUE; + + return FALSE; +} diff --git a/src/3rdparty/autotrace/epsilon-equal.h b/src/3rdparty/autotrace/epsilon-equal.h new file mode 100644 index 0000000..8b547ba --- /dev/null +++ b/src/3rdparty/autotrace/epsilon-equal.h @@ -0,0 +1,17 @@ +/* epsilon-equal.h: define an error resist compare. */ + +#ifndef EPSILON_EQUAL_H +#define EPSILON_EQUAL_H + +#include "types.h" + +/* Says whether V1 and V2 are within REAL_EPSILON of each other. + Fixed-point arithmetic would be better, to guarantee machine + independence, but it's so much more painful to work with. The value + here is smaller than can be represented in either a `fix_word' or a + `scaled_num', so more precision than this will be lost when we + output, anyway. */ +extern gboolean epsilon_equal(gfloat v1, gfloat v2); +#define REAL_EPSILON 0.00001 + +#endif /* not EPSILON_EQUAL_H */ diff --git a/src/3rdparty/autotrace/exception.c b/src/3rdparty/autotrace/exception.c new file mode 100644 index 0000000..c98777e --- /dev/null +++ b/src/3rdparty/autotrace/exception.c @@ -0,0 +1,47 @@ +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif /* Def: HAVE_CONFIG_H */ + +#include "exception.h" + +at_exception_type at_exception_new(at_msg_func client_func, gpointer client_data) +{ + at_exception_type e; + e.msg_type = AT_MSG_NOT_SET; + e.client_func = client_func; + e.client_data = client_data; + return e; +} + +gboolean at_exception_got_fatal(at_exception_type * exception) +{ + return (exception->msg_type == AT_MSG_FATAL) ? TRUE : FALSE; +} + +void at_exception_fatal(at_exception_type * exception, const gchar * message) +{ + if (!exception) + return; + exception->msg_type = AT_MSG_FATAL; + if (exception->client_func) { + exception->client_func(message, AT_MSG_FATAL, exception->client_data); + } +} + +void at_exception_warning(at_exception_type * exception, const gchar * message) +{ + if (!exception) + return; + exception->msg_type = AT_MSG_WARNING; + if (exception->client_func) { + exception->client_func(message, AT_MSG_WARNING, exception->client_data); + } +} + +GQuark at_error_quark(void) +{ + static GQuark q = 0; + if (q == 0) + q = g_quark_from_static_string("at-error-quark"); + return q; +} diff --git a/src/3rdparty/autotrace/exception.h b/src/3rdparty/autotrace/exception.h new file mode 100644 index 0000000..793e879 --- /dev/null +++ b/src/3rdparty/autotrace/exception.h @@ -0,0 +1,39 @@ +/* exception.h: facility to handle error in autotrace */ + +#ifndef AT_EXCEPTION_H +#define AT_EXCEPTION_H + +#include "autotrace.h" +#include "types.h" +#include <glib.h> + +#ifdef __cplusplus +extern "C" { +#endif /* __cplusplus */ + +/* Protocol: + If a function raises a FATAL(including propagation), + the function must release resources allocated by the + function itself. */ + typedef struct _at_exception_type at_exception_type; + struct _at_exception_type { + at_msg_type msg_type; + at_msg_func client_func; + gpointer client_data; + }; + + at_exception_type at_exception_new(at_msg_func client_func, gpointer client_data); + gboolean at_exception_got_fatal(at_exception_type * exception); + void at_exception_fatal(at_exception_type * exception, const gchar * message); + void at_exception_warning(at_exception_type * exception, const gchar * message); + +#define AT_ERROR at_error_quark() + GQuark at_error_quark(void); + typedef enum { + AT_ERROR_WRONG_COLOR_STRING, + } AtError; + +#ifdef __cplusplus +} +#endif /* __cplusplus */ +#endif /* Not def: AT_EXCEPTION_H */ diff --git a/src/3rdparty/autotrace/filename.c b/src/3rdparty/autotrace/filename.c new file mode 100644 index 0000000..cd42172 --- /dev/null +++ b/src/3rdparty/autotrace/filename.c @@ -0,0 +1,121 @@ +/* filename.c: Function manipulate file names + Was: find-suffix, extend-fname, make-suffix, remove-suffx + substring, concat3 */ + +/* remove-suffx.c: remove any suffix. + +Copyright (C) 1999 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. */ + +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif /* Def: HAVE_CONFIG_H */ + +#include "filename.h" +#include "xstd.h" +#include <string.h> + +/* Return a fresh copy of SOURCE[START..LIMIT], or NULL if LIMIT<START. + If LIMIT>strlen(START), it is reassigned. */ +static gchar *substring(gchar * source, const unsigned start, const unsigned limit); + +/* Return a fresh copy of S1 followed by S2, et al. */ +static gchar *concat3(gchar *, gchar *, gchar *); + +gchar *find_suffix(gchar * name) +{ + gchar *dot_pos = strrchr(name, '.'); +#ifdef WIN32 + gchar *slash_pos = strrchr(name, '\\'); +#else + gchar *slash_pos = strrchr(name, '/'); +#endif + + /* If the name is `foo' or `/foo.bar/baz', we have no extension. */ + return dot_pos == NULL || dot_pos < slash_pos ? NULL : dot_pos + 1; +} + +gchar *extend_filename(gchar * name, gchar * default_suffix) +{ + gchar *new_s; + gchar *suffix = find_suffix(name); + + new_s = suffix == NULL ? concat3(name, ".", default_suffix) : name; + return new_s; +} + +gchar *make_suffix(gchar * s, gchar * new_suffix) +{ + gchar *new_s; + gchar *old_suffix = find_suffix(s); + + if (old_suffix == NULL) + new_s = concat3(s, ".", new_suffix); + else { + size_t length_through_dot = old_suffix - s; + + XMALLOC(new_s, length_through_dot + strlen(new_suffix) + 1); + strncpy(new_s, s, length_through_dot); + strcpy(new_s + length_through_dot, new_suffix); + } + + return new_s; +} + +gchar *remove_suffix(gchar * s) +{ + gchar *suffix = find_suffix(s); + + return suffix == NULL ? s : suffix - 2 - s < 0 ? NULL : substring(s, 0, (unsigned)(suffix - 2 - s)); +} + +/* From substring.c */ +static gchar *substring(gchar * source, const unsigned start, const unsigned limit) +{ + gchar *result; + unsigned this_char; + size_t length = strlen(source); + size_t lim = limit; + + /* Upper bound out of range? */ + if (lim >= length) + lim = length - 1; + + /* Null substring? */ + if (start > lim) + return ""; + + /* The `2' here is one for the null and one for limit - start inclusive. */ + XMALLOC(result, lim - start + 2); + + for (this_char = start; this_char <= lim; this_char++) + result[this_char - start] = source[this_char]; + + result[this_char - start] = 0; + + return result; +} + +static gchar *concat3(gchar * s1, gchar * s2, gchar * s3) +{ + gchar *answer; + XMALLOC(answer, strlen(s1) + strlen(s2) + strlen(s3) + 1); + strcpy(answer, s1); + strcat(answer, s2); + strcat(answer, s3); + + return answer; +} diff --git a/src/3rdparty/autotrace/filename.h b/src/3rdparty/autotrace/filename.h new file mode 100644 index 0000000..bd55965 --- /dev/null +++ b/src/3rdparty/autotrace/filename.h @@ -0,0 +1,42 @@ +/* filename.h: Function manipulate file names + Was: find-suffix, extend-fname, make-suffix, remove-suffix */ + +/* remove-suffx.h: declarations for shared routines. + +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. */ + +#ifndef FILENAME_H +#define FILENAME_H +#include "types.h" + +/* If NAME has a suffix, return a pointer to its first character (i.e., + the one after the `.'); otherwise, return NULL. */ +extern gchar *find_suffix(gchar * name); + +/* If NAME has a suffix, simply return it; otherwise, return + `NAME.SUFFIX'. */ +extern gchar *extend_filename(gchar * name, gchar * suffix); + +/* Return S with the suffix SUFFIX, removing any suffix already present. + For example, `make_suffix ("/foo/bar.baz", "karl")' returns + `/foo/bar.karl'. Returns a string allocated with malloc. */ +extern gchar *make_suffix(gchar * s, gchar * suffix); + +/* Return NAME with any suffix removed. */ +extern gchar *remove_suffix(gchar * name); + +#endif /* Not def: FILENAME_H */ diff --git a/src/3rdparty/autotrace/fit.c b/src/3rdparty/autotrace/fit.c new file mode 100644 index 0000000..a6ca2b6 --- /dev/null +++ b/src/3rdparty/autotrace/fit.c @@ -0,0 +1,1442 @@ +/* fit.c: turn a bitmap representation of a curve into a list of splines. + Some of the ideas, but not the code, comes from the Phoenix thesis. + See README for the reference. + + 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. */ + +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif /* Def: HAVE_CONFIG_H */ + +#include "autotrace.h" +#include "fit.h" +#include "logreport.h" +#include "spline.h" +#include "vector.h" +#include "curve.h" +#include "pxl-outline.h" +#include "epsilon-equal.h" +#include "xstd.h" +#include <math.h> +#ifndef FLT_MAX +#include <limits.h> +#include <float.h> +#endif +#ifndef FLT_MIN +#include <limits.h> +#include <float.h> +#endif +#include <string.h> +#include <assert.h> + +#define SQUARE(x) ((x) * (x)) +#define CUBE(x) ((x) * (x) * (x)) + +/* We need to manipulate lists of array indices. */ + +typedef struct index_list { + unsigned *data; + unsigned length; +} index_list_type; + +/* The usual accessor macros. */ +#define GET_INDEX(i_l, n) ((i_l).data[n]) +#define INDEX_LIST_LENGTH(i_l) ((i_l).length) +#define GET_LAST_INDEX(i_l) ((i_l).data[INDEX_LIST_LENGTH (i_l) - 1]) + +static void append_index(index_list_type *, unsigned); +static void free_index_list(index_list_type *); +static index_list_type new_index_list(void); +static void remove_adjacent_corners(index_list_type *, unsigned, gboolean, at_exception_type * exception); +static void change_bad_lines(spline_list_type *, fitting_opts_type *); +static void filter(curve_type, fitting_opts_type *); +static void find_vectors(unsigned, pixel_outline_type, vector_type *, vector_type *, unsigned); +static index_list_type find_corners(pixel_outline_type, fitting_opts_type *, at_exception_type * exception); +static gfloat find_error(curve_type, spline_type, unsigned *, at_exception_type * exception); +static vector_type find_half_tangent(curve_type, gboolean start, unsigned *, unsigned); +static void find_tangent(curve_type, gboolean, gboolean, unsigned); +static spline_type fit_one_spline(curve_type, at_exception_type * exception); +static spline_list_type *fit_curve(curve_type, fitting_opts_type *, at_exception_type * exception); +static spline_list_type fit_curve_list(curve_list_type, fitting_opts_type *, at_distance_map *, at_exception_type * exception); +static spline_list_type *fit_with_least_squares(curve_type, fitting_opts_type *, at_exception_type * exception); +static spline_list_type *fit_with_line(curve_type); +static void remove_knee_points(curve_type, gboolean); +static void set_initial_parameter_values(curve_type); +static gboolean spline_linear_enough(spline_type *, curve_type, fitting_opts_type *); +static curve_list_array_type split_at_corners(pixel_outline_list_type, fitting_opts_type *, at_exception_type * exception); +static at_coord real_to_int_coord(at_real_coord); +static gfloat distance(at_real_coord, at_real_coord); + +/* Get a new set of fitting options */ +fitting_opts_type new_fitting_opts(void) +{ + fitting_opts_type fitting_opts; + + fitting_opts.background_color = NULL; + fitting_opts.charcode = 0; + fitting_opts.color_count = 0; + fitting_opts.corner_always_threshold = (gfloat) 60.0; + fitting_opts.corner_surround = 4; + fitting_opts.corner_threshold = (gfloat) 100.0; + fitting_opts.error_threshold = (gfloat) 2.0; + fitting_opts.filter_iterations = 4; + fitting_opts.line_reversion_threshold = (gfloat) .01; + fitting_opts.line_threshold = (gfloat) 1.0; + fitting_opts.remove_adjacent_corners = FALSE; + fitting_opts.tangent_surround = 3; + fitting_opts.despeckle_level = 0; + fitting_opts.despeckle_tightness = 2.0; + fitting_opts.noise_removal = (gfloat) 0.99; + fitting_opts.centerline = FALSE; + fitting_opts.preserve_width = FALSE; + fitting_opts.width_weight_factor = 6.0; + + return (fitting_opts); +} + +/* The top-level call that transforms the list of pixels in the outlines + of the original character to a list of spline lists fitted to those + pixels. */ + +spline_list_array_type fitted_splines(pixel_outline_list_type pixel_outline_list, fitting_opts_type * fitting_opts, at_distance_map * dist, unsigned short width, unsigned short height, at_exception_type * exception, at_progress_func notify_progress, gpointer progress_data, at_testcancel_func test_cancel, gpointer testcancel_data) +{ + unsigned this_list; + + spline_list_array_type char_splines = new_spline_list_array(); + curve_list_array_type curve_array = split_at_corners(pixel_outline_list, + fitting_opts, + exception); + + char_splines.centerline = fitting_opts->centerline; + char_splines.preserve_width = fitting_opts->preserve_width; + char_splines.width_weight_factor = fitting_opts->width_weight_factor; + + if (fitting_opts->background_color) + char_splines.background_color = at_color_copy(fitting_opts->background_color); + else + char_splines.background_color = NULL; + /* Set dummy values. Real value is set in upper context. */ + char_splines.width = width; + char_splines.height = height; + + for (this_list = 0; this_list < CURVE_LIST_ARRAY_LENGTH(curve_array); this_list++) { + spline_list_type curve_list_splines; + curve_list_type curves = CURVE_LIST_ARRAY_ELT(curve_array, this_list); + + if (notify_progress) + notify_progress((((gfloat) this_list) / ((gfloat) CURVE_LIST_ARRAY_LENGTH(curve_array) * (gfloat) 3.0) + (gfloat) 0.333), progress_data); + if (test_cancel && test_cancel(testcancel_data)) + goto cleanup; + + LOG("\nFitting curve list #%u:\n", this_list); + + curve_list_splines = fit_curve_list(curves, fitting_opts, dist, exception); + if (at_exception_got_fatal(exception)) { + if (char_splines.background_color) + at_color_free(char_splines.background_color); + goto cleanup; + } + curve_list_splines.clockwise = curves.clockwise; + + memcpy(&(curve_list_splines.color), &(O_LIST_OUTLINE(pixel_outline_list, this_list).color), sizeof(at_color)); + append_spline_list(&char_splines, curve_list_splines); + } +cleanup: + free_curve_list_array(&curve_array, notify_progress, progress_data); + + return char_splines; +} + +/* Fit the list of curves CURVE_LIST to a list of splines, and return + it. CURVE_LIST represents a single closed paths, e.g., either the + inside or outside outline of an `o'. */ + +static spline_list_type fit_curve_list(curve_list_type curve_list, fitting_opts_type * fitting_opts, at_distance_map * dist, at_exception_type * exception) +{ + curve_type curve; + unsigned this_curve, this_spline; + unsigned curve_list_length = CURVE_LIST_LENGTH(curve_list); + spline_list_type curve_list_splines = empty_spline_list(); + + curve_list_splines.open = curve_list.open; + + /* Remove the extraneous ``knee'' points before filtering. Since the + corners have already been found, we don't need to worry about + removing a point that should be a corner. */ + + LOG("\nRemoving knees:\n"); + for (this_curve = 0; this_curve < curve_list_length; this_curve++) { + LOG("#%u:", this_curve); + remove_knee_points(CURVE_LIST_ELT(curve_list, this_curve), CURVE_LIST_CLOCKWISE(curve_list)); + } + + if (dist != NULL) { + unsigned this_point; + unsigned height = dist->height; + for (this_curve = 0; this_curve < curve_list_length; this_curve++) { + curve = CURVE_LIST_ELT(curve_list, this_curve); + for (this_point = 0; this_point < CURVE_LENGTH(curve); this_point++) { + unsigned x, y; + float width, w; + at_real_coord *coord = &CURVE_POINT(curve, this_point); + x = (unsigned)(coord->x); + y = height - (unsigned)(coord->y) - 1; + + /* Each (x, y) is a point on the skeleton of the curve, which + might be offset from the TRUE centerline, where the width + is maximal. Therefore, use as the local line width the + maximum distance over the neighborhood of (x, y). */ + width = dist->d[y][x]; + if (y >= 1) { + if ((w = dist->d[y - 1][x]) > width) + width = w; + if (x >= 1) { + if ((w = dist->d[y][x - 1]) > width) + width = w; + if ((w = dist->d[y - 1][x - 1]) > width) + width = w; + } + if (x + 1 < dist->width) { + if ((w = dist->d[y][x + 1]) > width) + width = w; + if ((w = dist->d[y - 1][x + 1]) > width) + width = w; + } + } + if (y + 1 < height) { + if ((w = dist->d[y + 1][x]) > width) + width = w; + if (x >= 1 && (w = dist->d[y + 1][x - 1]) > width) + width = w; + if (x + 1 < dist->width && (w = dist->d[y + 1][x + 1]) > width) + width = w; + } + coord->z = width * (fitting_opts->width_weight_factor); + } + } + } + + /* We filter all the curves in CURVE_LIST at once; otherwise, we would + look at an unfiltered curve when computing tangents. */ + + LOG("\nFiltering curves:\n"); + for (this_curve = 0; this_curve < curve_list.length; this_curve++) { + LOG("#%u: ", this_curve); + filter(CURVE_LIST_ELT(curve_list, this_curve), fitting_opts); + } + + /* Make the first point in the first curve also be the last point in + the last curve, so the fit to the whole curve list will begin and + end at the same point. This may cause slight errors in computing + the tangents and t values, but it's worth it for the continuity. + Of course we don't want to do this if the two points are already + the same, as they are if the curve is cyclic. (We don't append it + earlier, in `split_at_corners', because that confuses the + filtering.) Finally, we can't append the point if the curve is + exactly three points long, because we aren't adding any more data, + and three points isn't enough to determine a spline. Therefore, + the fitting will fail. */ + curve = CURVE_LIST_ELT(curve_list, 0); + if (CURVE_CYCLIC(curve) == TRUE) + append_point(curve, CURVE_POINT(curve, 0)); + + /* Finally, fit each curve in the list to a list of splines. */ + for (this_curve = 0; this_curve < curve_list_length; this_curve++) { + spline_list_type *curve_splines; + curve_type current_curve = CURVE_LIST_ELT(curve_list, this_curve); + + LOG("\nFitting curve #%u:\n", this_curve); + + curve_splines = fit_curve(current_curve, fitting_opts, exception); + if (at_exception_got_fatal(exception)) + goto cleanup; + else if (curve_splines == NULL) { + LOG("Could not fit curve #%u", this_curve); + at_exception_warning(exception, "Could not fit curve"); + } else { + LOG("Fitted splines for curve #%u:\n", this_curve); + for (this_spline = 0; this_spline < SPLINE_LIST_LENGTH(*curve_splines); this_spline++) { + LOG(" %u: ", this_spline); + if (logging) + print_spline(SPLINE_LIST_ELT(*curve_splines, this_spline)); + } + + /* After fitting, we may need to change some would-be lines + back to curves, because they are in a list with other + curves. */ + change_bad_lines(curve_splines, fitting_opts); + + concat_spline_lists(&curve_list_splines, *curve_splines); + free_spline_list(*curve_splines); + free(curve_splines); + } + } + + if (logging) { + LOG("\nFitted splines are:\n"); + for (this_spline = 0; this_spline < SPLINE_LIST_LENGTH(curve_list_splines); this_spline++) { + LOG(" %u: ", this_spline); + print_spline(SPLINE_LIST_ELT(curve_list_splines, this_spline)); + } + } +cleanup: + return curve_list_splines; +} + +/* Transform a set of locations to a list of splines (the fewer the + better). We are guaranteed that CURVE does not contain any corners. + We return NULL if we cannot fit the points at all. */ + +static spline_list_type *fit_curve(curve_type curve, fitting_opts_type * fitting_opts, at_exception_type * exception) +{ + spline_list_type *fittedsplines; + + if (CURVE_LENGTH(curve) < 2) { + LOG("Tried to fit curve with less than two points"); + at_exception_warning(exception, "Tried to fit curve with less than two points"); + return NULL; + } + + /* Do we have enough points to fit with a spline? */ + fittedsplines = CURVE_LENGTH(curve) < 4 ? fit_with_line(curve) + : fit_with_least_squares(curve, fitting_opts, exception); + + return fittedsplines; +} + +/* As mentioned above, the first step is to find the corners in + PIXEL_LIST, the list of points. (Presumably we can't fit a single + spline around a corner.) The general strategy is to look through all + the points, remembering which we want to consider corners. Then go + through that list, producing the curve_list. This is dictated by the + fact that PIXEL_LIST does not necessarily start on a corner---it just + starts at the character's first outline pixel, going left-to-right, + top-to-bottom. But we want all our splines to start and end on real + corners. + + For example, consider the top of a capital `C' (this is in cmss20): + x + *********** + ****************** + + PIXEL_LIST will start at the pixel below the `x'. If we considered + this pixel a corner, we would wind up matching a very small segment + from there to the end of the line, probably as a straight line, which + is certainly not what we want. + + PIXEL_LIST has one element for each closed outline on the character. + To preserve this information, we return an array of curve_lists, one + element (which in turn consists of several curves, one between each + pair of corners) for each element in PIXEL_LIST. */ + +static curve_list_array_type split_at_corners(pixel_outline_list_type pixel_list, fitting_opts_type * fitting_opts, at_exception_type * exception) +{ + unsigned this_pixel_o; + curve_list_array_type curve_array = new_curve_list_array(); + + LOG("\nFinding corners:\n"); + + for (this_pixel_o = 0; this_pixel_o < O_LIST_LENGTH(pixel_list); this_pixel_o++) { + curve_type curve, first_curve; + index_list_type corner_list; + unsigned p, this_corner; + curve_list_type curve_list = new_curve_list(); + pixel_outline_type pixel_o = O_LIST_OUTLINE(pixel_list, this_pixel_o); + + CURVE_LIST_CLOCKWISE(curve_list) = O_CLOCKWISE(pixel_o); + curve_list.open = pixel_o.open; + + LOG("#%u:", this_pixel_o); + + /* If the outline does not have enough points, we can't do + anything. The endpoints of the outlines are automatically + corners. We need at least `corner_surround' more pixels on + either side of a point before it is conceivable that we might + want another corner. */ + if (O_LENGTH(pixel_o) > fitting_opts->corner_surround * 2 + 2) + corner_list = find_corners(pixel_o, fitting_opts, exception); + + else { + int surround; + if ((surround = (int)(O_LENGTH(pixel_o) - 3) / 2) >= 2) { + unsigned save_corner_surround = fitting_opts->corner_surround; + fitting_opts->corner_surround = surround; + corner_list = find_corners(pixel_o, fitting_opts, exception); + fitting_opts->corner_surround = save_corner_surround; + } else { + corner_list.length = 0; + corner_list.data = NULL; + } + } + + /* Remember the first curve so we can make it be the `next' of the + last one. (And vice versa.) */ + first_curve = new_curve(); + + curve = first_curve; + + if (corner_list.length == 0) { /* No corners. Use all of the pixel outline as the curve. */ + for (p = 0; p < O_LENGTH(pixel_o); p++) + append_pixel(curve, O_COORDINATE(pixel_o, p)); + + if (curve_list.open == TRUE) + CURVE_CYCLIC(curve) = FALSE; + else + CURVE_CYCLIC(curve) = TRUE; + } else { /* Each curve consists of the points between (inclusive) each pair + of corners. */ + for (this_corner = 0; this_corner < corner_list.length - 1; this_corner++) { + curve_type previous_curve = curve; + unsigned corner = GET_INDEX(corner_list, this_corner); + unsigned next_corner = GET_INDEX(corner_list, this_corner + 1); + + for (p = corner; p <= next_corner; p++) + append_pixel(curve, O_COORDINATE(pixel_o, p)); + + append_curve(&curve_list, curve); + curve = new_curve(); + NEXT_CURVE(previous_curve) = curve; + PREVIOUS_CURVE(curve) = previous_curve; + } + + /* The last curve is different. It consists of the points + (inclusive) between the last corner and the end of the list, + and the beginning of the list and the first corner. */ + for (p = GET_LAST_INDEX(corner_list); p < O_LENGTH(pixel_o); p++) + append_pixel(curve, O_COORDINATE(pixel_o, p)); + + if (!pixel_o.open) { + for (p = 0; p <= GET_INDEX(corner_list, 0); p++) + append_pixel(curve, O_COORDINATE(pixel_o, p)); + } else { + curve_type last_curve = PREVIOUS_CURVE(curve); + PREVIOUS_CURVE(first_curve) = NULL; + if (last_curve) + NEXT_CURVE(last_curve) = NULL; + } + } + + LOG(" [%u].\n", corner_list.length); + free_index_list(&corner_list); + + /* Add `curve' to the end of the list, updating the pointers in + the chain. */ + append_curve(&curve_list, curve); + NEXT_CURVE(curve) = first_curve; + PREVIOUS_CURVE(first_curve) = curve; + + /* And now add the just-completed curve list to the array. */ + append_curve_list(&curve_array, curve_list); + } /* End of considering each pixel outline. */ + + return curve_array; +} + +/* We consider a point to be a corner if (1) the angle defined by the + `corner_surround' points coming into it and going out from it is less + than `corner_threshold' degrees, and no point within + `corner_surround' points has a smaller angle; or (2) the angle is less + than `corner_always_threshold' degrees. + + Because of the different cases, it is convenient to have the + following macro to append a corner on to the list we return. The + character argument C is simply so that the different cases can be + distinguished in the log file. */ + +#define APPEND_CORNER(index, angle, c) \ + do \ + { \ + append_index (&corner_list, index); \ + LOG (" (%d,%d)%c%.3f", \ + O_COORDINATE (pixel_outline, index).x, \ + O_COORDINATE (pixel_outline, index).y, \ + c, angle); \ + } \ + while (0) + +static index_list_type find_corners(pixel_outline_type pixel_outline, fitting_opts_type * fitting_opts, at_exception_type * exception) +{ + unsigned p, start_p, end_p; + index_list_type corner_list = new_index_list(); + + start_p = 0; + end_p = O_LENGTH(pixel_outline) - 1; + if (pixel_outline.open) { + if (end_p <= fitting_opts->corner_surround * 2) + return corner_list; + APPEND_CORNER(0, 0.0, '@'); + start_p += fitting_opts->corner_surround; + end_p -= fitting_opts->corner_surround; + } + + /* Consider each pixel on the outline in turn. */ + for (p = start_p; p <= end_p; p++) { + gfloat corner_angle; + vector_type in_vector, out_vector; + + /* Check if the angle is small enough. */ + find_vectors(p, pixel_outline, &in_vector, &out_vector, fitting_opts->corner_surround); + corner_angle = Vangle(in_vector, out_vector, exception); + if (at_exception_got_fatal(exception)) + goto cleanup; + + if (fabs(corner_angle) <= fitting_opts->corner_threshold) { + /* We want to keep looking, instead of just appending the + first pixel we find with a small enough angle, since there + might be another corner within `corner_surround' pixels, with + a smaller angle. If that is the case, we want that one. */ + gfloat best_corner_angle = corner_angle; + unsigned best_corner_index = p; + index_list_type equally_good_list = new_index_list(); + /* As we come into the loop, `p' is the index of the point + that has an angle less than `corner_angle'. We use `i' to + move through the pixels next to that, and `q' for moving + through the adjacent pixels to each `p'. */ + unsigned q = p; + unsigned i = p + 1; + + while (TRUE) { + /* Perhaps the angle is sufficiently small that we want to + consider this a corner, even if it's not the best + (unless we've already wrapped around in the search, + i.e., `q<i', in which case we have already added the + corner, and we don't want to add it again). We want to + do this check on the first candidate we find, as well + as the others in the loop, hence this comes before the + stopping condition. */ + if (corner_angle <= fitting_opts->corner_always_threshold && q >= p) + APPEND_CORNER(q, corner_angle, '\\'); + + /* Exit the loop if we've looked at `corner_surround' + pixels past the best one we found, or if we've looked + at all the pixels. */ + if (i >= best_corner_index + fitting_opts->corner_surround || i >= O_LENGTH(pixel_outline)) + break; + + /* Check the angle. */ + q = i % O_LENGTH(pixel_outline); + find_vectors(q, pixel_outline, &in_vector, &out_vector, fitting_opts->corner_surround); + corner_angle = Vangle(in_vector, out_vector, exception); + if (at_exception_got_fatal(exception)) + goto cleanup; + + /* If we come across a corner that is just as good as the + best one, we should make it a corner, too. This + happens, for example, at the points on the `W' in some + typefaces, where the ``points'' are flat. */ + if (epsilon_equal(corner_angle, best_corner_angle)) + append_index(&equally_good_list, q); + + else if (corner_angle < best_corner_angle) { + best_corner_angle = corner_angle; + /* We want to check `corner_surround' pixels beyond the + new best corner. */ + i = best_corner_index = q; + free_index_list(&equally_good_list); + equally_good_list = new_index_list(); + } + + i++; + } + + /* After we exit the loop, `q' is the index of the last point + we checked. We have already added the corner if + `best_corner_angle' is less than `corner_always_threshold'. + Again, if we've already wrapped around, we don't want to + add the corner again. */ + if (best_corner_angle > fitting_opts->corner_always_threshold && best_corner_index >= p) { + unsigned j; + + APPEND_CORNER(best_corner_index, best_corner_angle, '/'); + + for (j = 0; j < INDEX_LIST_LENGTH(equally_good_list); j++) + APPEND_CORNER(GET_INDEX(equally_good_list, j), best_corner_angle, '@'); + } + free_index_list(&equally_good_list); + + /* If we wrapped around in our search, we're done; otherwise, + we don't want the outer loop to look at the pixels that we + already looked at in searching for the best corner. */ + p = (q < p) ? O_LENGTH(pixel_outline) : q; + } /* End of searching for the best corner. */ + } /* End of considering each pixel. */ + + if (INDEX_LIST_LENGTH(corner_list) > 0) + /* We never want two corners next to each other, since the + only way to fit such a ``curve'' would be with a straight + line, which usually interrupts the continuity dreadfully. */ + remove_adjacent_corners(&corner_list, O_LENGTH(pixel_outline) - (pixel_outline.open ? 2 : 1), fitting_opts->remove_adjacent_corners, exception); +cleanup: + return corner_list; +} + +/* Return the difference vectors coming in and going out of the outline + OUTLINE at the point whose index is TEST_INDEX. In Phoenix, + Schneider looks at a single point on either side of the point we're + considering. That works for him because his points are not touching. + But our points *are* touching, and so we have to look at + `corner_surround' points on either side, to get a better picture of + the outline's shape. */ + +static void find_vectors(unsigned test_index, pixel_outline_type outline, vector_type * in, vector_type * out, unsigned corner_surround) +{ + int i; + unsigned n_done; + at_coord candidate = O_COORDINATE(outline, test_index); + + in->dx = in->dy = in->dz = 0.0; + out->dx = out->dy = out->dz = 0.0; + + /* Add up the differences from p of the `corner_surround' points + before p. */ + for (i = O_PREV(outline, test_index), n_done = 0; n_done < corner_surround; i = O_PREV(outline, i), n_done++) + *in = Vadd(*in, IPsubtract(O_COORDINATE(outline, i), candidate)); + + /* And the points after p. */ + for (i = O_NEXT(outline, test_index), n_done = 0; n_done < corner_surround; i = O_NEXT(outline, i), n_done++) + *out = Vadd(*out, IPsubtract(O_COORDINATE(outline, i), candidate)); +} + +/* Remove adjacent points from the index list LIST. We do this by first + sorting the list and then running through it. Since these lists are + quite short, a straight selection sort (e.g., p.139 of the Art of + Computer Programming, vol.3) is good enough. LAST_INDEX is the index + of the last pixel on the outline, i.e., the next one is the first + pixel. We need this for checking the adjacency of the last corner. + + We need to do this because the adjacent corners turn into + two-pixel-long curves, which can only be fit by straight lines. */ + +static void remove_adjacent_corners(index_list_type * list, unsigned last_index, gboolean remove_adj_corners, at_exception_type * exception) +{ + unsigned j; + unsigned last; + index_list_type new_list = new_index_list(); + + for (j = INDEX_LIST_LENGTH(*list) - 1; j > 0; j--) { + unsigned search; + unsigned temp; + /* Find maximal element below `j'. */ + unsigned max_index = j; + + for (search = 0; search < j; search++) + if (GET_INDEX(*list, search) > GET_INDEX(*list, max_index)) + max_index = search; + + if (max_index != j) { + temp = GET_INDEX(*list, j); + GET_INDEX(*list, j) = GET_INDEX(*list, max_index); + GET_INDEX(*list, max_index) = temp; + + /* xx -- really have to sort? */ + LOG("needed exchange"); + at_exception_warning(exception, "needed exchange"); + } + } + + /* The list is sorted. Now look for adjacent entries. Each time + through the loop we insert the current entry and, if appropriate, + the next entry. */ + for (j = 0; j < INDEX_LIST_LENGTH(*list) - 1; j++) { + unsigned current = GET_INDEX(*list, j); + unsigned next = GET_INDEX(*list, j + 1); + + /* We should never have inserted the same element twice. */ + /* assert (current != next); */ + + if ((remove_adj_corners) && ((next == current + 1) || (next == current))) + j++; + + append_index(&new_list, current); + } + + /* Don't append the last element if it is 1) adjacent to the previous + one; or 2) adjacent to the very first one. */ + last = GET_LAST_INDEX(*list); + if (INDEX_LIST_LENGTH(new_list) == 0 || !(last == GET_LAST_INDEX(new_list) + 1 || (last == last_index && GET_INDEX(*list, 0) == 0))) + append_index(&new_list, last); + + free_index_list(list); + *list = new_list; +} + +/* A ``knee'' is a point which forms a ``right angle'' with its + predecessor and successor. See the documentation (the `Removing + knees' section) for an example and more details. + + The argument CLOCKWISE tells us which direction we're moving. (We + can't figure that information out from just the single segment with + which we are given to work.) + + We should never find two consecutive knees. + + Since the first and last points are corners (unless the curve is + cyclic), it doesn't make sense to remove those. */ + +/* This evaluates to TRUE if the vector V is zero in one direction and + nonzero in the other. */ +#define ONLY_ONE_ZERO(v) \ + (((v).dx == 0.0 && (v).dy != 0.0) || ((v).dy == 0.0 && (v).dx != 0.0)) + +/* There are four possible cases for knees, one for each of the four + corners of a rectangle; and then the cases differ depending on which + direction we are going around the curve. The tests are listed here + in the order of upper left, upper right, lower right, lower left. + Perhaps there is some simple pattern to the + clockwise/counterclockwise differences, but I don't see one. */ +#define CLOCKWISE_KNEE(prev_delta, next_delta) \ + ((prev_delta.dx == -1.0 && next_delta.dy == 1.0) \ + || (prev_delta.dy == 1.0 && next_delta.dx == 1.0) \ + || (prev_delta.dx == 1.0 && next_delta.dy == -1.0) \ + || (prev_delta.dy == -1.0 && next_delta.dx == -1.0)) + +#define COUNTERCLOCKWISE_KNEE(prev_delta, next_delta) \ + ((prev_delta.dy == 1.0 && next_delta.dx == -1.0) \ + || (prev_delta.dx == 1.0 && next_delta.dy == 1.0) \ + || (prev_delta.dy == -1.0 && next_delta.dx == 1.0) \ + || (prev_delta.dx == -1.0 && next_delta.dy == -1.0)) + +static void remove_knee_points(curve_type curve, gboolean clockwise) +{ + unsigned i; + unsigned offset = (CURVE_CYCLIC(curve) == TRUE) ? 0 : 1; + at_coord previous = real_to_int_coord(CURVE_POINT(curve, CURVE_PREV(curve, offset))); + curve_type trimmed_curve = copy_most_of_curve(curve); + + if (CURVE_CYCLIC(curve) == FALSE) + append_pixel(trimmed_curve, real_to_int_coord(CURVE_POINT(curve, 0))); + + for (i = offset; i < CURVE_LENGTH(curve) - offset; i++) { + at_coord current = real_to_int_coord(CURVE_POINT(curve, i)); + at_coord next = real_to_int_coord(CURVE_POINT(curve, CURVE_NEXT(curve, i))); + vector_type prev_delta = IPsubtract(previous, current); + vector_type next_delta = IPsubtract(next, current); + + if (ONLY_ONE_ZERO(prev_delta) && ONLY_ONE_ZERO(next_delta) + && ((clockwise && CLOCKWISE_KNEE(prev_delta, next_delta)) + || (!clockwise && COUNTERCLOCKWISE_KNEE(prev_delta, next_delta)))) + LOG(" (%d,%d)", current.x, current.y); + else { + previous = current; + append_pixel(trimmed_curve, current); + } + } + + if (CURVE_CYCLIC(curve) == FALSE) + append_pixel(trimmed_curve, real_to_int_coord(LAST_CURVE_POINT(curve))); + + if (CURVE_LENGTH(trimmed_curve) == CURVE_LENGTH(curve)) + LOG(" (none)"); + + LOG(".\n"); + + free_curve(curve); + *curve = *trimmed_curve; + free(trimmed_curve); /* free_curve? --- Masatake */ +} + +/* Smooth the curve by adding in neighboring points. Do this + `filter_iterations' times. But don't change the corners. */ + +static void filter(curve_type curve, fitting_opts_type * fitting_opts) +{ + unsigned iteration, this_point; + unsigned offset = (CURVE_CYCLIC(curve) == TRUE) ? 0 : 1; + at_real_coord prev_new_point; + + /* We must have at least three points---the previous one, the current + one, and the next one. But if we don't have at least five, we will + probably collapse the curve down onto a single point, which means + we won't be able to fit it with a spline. */ + if (CURVE_LENGTH(curve) < 5) { + LOG("Length is %u, not enough to filter.\n", CURVE_LENGTH(curve)); + return; + } + + prev_new_point.x = FLT_MAX; + prev_new_point.y = FLT_MAX; + prev_new_point.z = FLT_MAX; + + for (iteration = 0; iteration < fitting_opts->filter_iterations; iteration++) { + curve_type newcurve = copy_most_of_curve(curve); + gboolean collapsed = FALSE; + + /* Keep the first point on the curve. */ + if (offset) + append_point(newcurve, CURVE_POINT(curve, 0)); + + for (this_point = offset; this_point < CURVE_LENGTH(curve) - offset; this_point++) { + vector_type in, out, sum; + at_real_coord new_point; + + /* Calculate the vectors in and out, computed by looking at n points + on either side of this_point. Experimental it was found that 2 is + optimal. */ + + signed int prev, prevprev; /* have to be signed */ + unsigned int next, nextnext; + at_real_coord candidate = CURVE_POINT(curve, this_point); + + prev = CURVE_PREV(curve, this_point); + prevprev = CURVE_PREV(curve, prev); + next = CURVE_NEXT(curve, this_point); + nextnext = CURVE_NEXT(curve, next); + + /* Add up the differences from p of the `surround' points + before p. */ + in.dx = in.dy = in.dz = 0.0; + + in = Vadd(in, Psubtract(CURVE_POINT(curve, prev), candidate)); + if (prevprev >= 0) + in = Vadd(in, Psubtract(CURVE_POINT(curve, prevprev), candidate)); + + /* And the points after p. Don't use more points after p than we + ended up with before it. */ + out.dx = out.dy = out.dz = 0.0; + + out = Vadd(out, Psubtract(CURVE_POINT(curve, next), candidate)); + if (nextnext < CURVE_LENGTH(curve)) + out = Vadd(out, Psubtract(CURVE_POINT(curve, nextnext), candidate)); + + /* Start with the old point. */ + new_point = candidate; + sum = Vadd(in, out); + /* We added 2*n+2 points, so we have to divide the sum by 2*n+2 */ + new_point.x += sum.dx / 6; + new_point.y += sum.dy / 6; + new_point.z += sum.dz / 6; + if (fabs(prev_new_point.x - new_point.x) < 0.3 && fabs(prev_new_point.y - new_point.y) < 0.3 && fabs(prev_new_point.z - new_point.z) < 0.3) { + collapsed = TRUE; + break; + } + + /* Put the newly computed point into a separate curve, so it + doesn't affect future computation (on this iteration). */ + append_point(newcurve, prev_new_point = new_point); + } + + if (collapsed) + free_curve(newcurve); + else { + /* Just as with the first point, we have to keep the last point. */ + if (offset) + append_point(newcurve, LAST_CURVE_POINT(curve)); + + /* Set the original curve to the newly filtered one, and go again. */ + free_curve(curve); + *curve = *newcurve; + } + free(newcurve); + } + + if (logging) + log_curve(curve, FALSE); +} + +/* This routine returns the curve fitted to a straight line in a very + simple way: make the first and last points on the curve be the + endpoints of the line. This simplicity is justified because we are + called only on very short curves. */ + +static spline_list_type *fit_with_line(curve_type curve) +{ + spline_type line; + + LOG("Fitting with straight line:\n"); + + SPLINE_DEGREE(line) = LINEARTYPE; + START_POINT(line) = CONTROL1(line) = CURVE_POINT(curve, 0); + END_POINT(line) = CONTROL2(line) = LAST_CURVE_POINT(curve); + + /* Make sure that this line is never changed to a cubic. */ + SPLINE_LINEARITY(line) = 0; + + if (logging) { + LOG(" "); + print_spline(line); + } + + return new_spline_list_with_spline(line); +} + +/* The least squares method is well described in Schneider's thesis. + Briefly, we try to fit the entire curve with one spline. If that + fails, we subdivide the curve. */ + +static spline_list_type *fit_with_least_squares(curve_type curve, fitting_opts_type * fitting_opts, at_exception_type * exception) +{ + gfloat error = 0, best_error = FLT_MAX; + spline_type spline, best_spline; + spline_list_type *spline_list = NULL; + unsigned worst_point = 0; + gfloat previous_error = FLT_MAX; + + LOG("\nFitting with least squares:\n"); + + /* Phoenix reduces the number of points with a ``linear spline + technique''. But for fitting letterforms, that is + inappropriate. We want all the points we can get. */ + + /* It makes no difference whether we first set the `t' values or + find the tangents. This order makes the documentation a little + more coherent. */ + + LOG("Finding tangents:\n"); + find_tangent(curve, /* to_start */ TRUE, /* cross_curve */ FALSE, + fitting_opts->tangent_surround); + find_tangent(curve, /* to_start */ FALSE, /* cross_curve */ FALSE, + fitting_opts->tangent_surround); + + set_initial_parameter_values(curve); + + /* Now we loop, subdividing, until CURVE has + been fit. */ + while (TRUE) { + spline = best_spline = fit_one_spline(curve, exception); + if (at_exception_got_fatal(exception)) + goto cleanup; + + if (SPLINE_DEGREE(spline) == LINEARTYPE) + LOG(" fitted to line:\n"); + else + LOG(" fitted to spline:\n"); + + if (logging) { + LOG(" "); + print_spline(spline); + } + + if (SPLINE_DEGREE(spline) == LINEARTYPE) + break; + + error = find_error(curve, spline, &worst_point, exception); + if (error <= previous_error) { + best_error = error; + best_spline = spline; + } + break; + } + + if (SPLINE_DEGREE(spline) == LINEARTYPE) { + spline_list = new_spline_list_with_spline(spline); + LOG("Accepted error of %.3f.\n", error); + return (spline_list); + } + + /* Go back to the best fit. */ + spline = best_spline; + error = best_error; + + if (error < fitting_opts->error_threshold && CURVE_CYCLIC(curve) == FALSE) { + /* The points were fitted with a + spline. We end up here whenever a fit is accepted. We have + one more job: see if the ``curve'' that was fit should really + be a straight line. */ + if (spline_linear_enough(&spline, curve, fitting_opts)) { + SPLINE_DEGREE(spline) = LINEARTYPE; + LOG("Changed to line.\n"); + } + spline_list = new_spline_list_with_spline(spline); + LOG("Accepted error of %.3f.\n", error); + } else { + /* We couldn't fit the curve acceptably, so subdivide. */ + unsigned subdivision_index; + spline_list_type *left_spline_list; + spline_list_type *right_spline_list; + curve_type left_curve = new_curve(); + curve_type right_curve = new_curve(); + + /* Keep the linked list of curves intact. */ + NEXT_CURVE(right_curve) = NEXT_CURVE(curve); + PREVIOUS_CURVE(right_curve) = left_curve; + NEXT_CURVE(left_curve) = right_curve; + PREVIOUS_CURVE(left_curve) = curve; + NEXT_CURVE(curve) = left_curve; + + LOG("\nSubdividing (error %.3f):\n", error); + LOG(" Original point: (%.3f,%.3f), #%u.\n", CURVE_POINT(curve, worst_point).x, CURVE_POINT(curve, worst_point).y, worst_point); + subdivision_index = worst_point; + LOG(" Final point: (%.3f,%.3f), #%u.\n", CURVE_POINT(curve, subdivision_index).x, CURVE_POINT(curve, subdivision_index).y, subdivision_index); + + /* The last point of the left-hand curve will also be the first + point of the right-hand curve. */ + CURVE_LENGTH(left_curve) = subdivision_index + 1; + CURVE_LENGTH(right_curve) = CURVE_LENGTH(curve) - subdivision_index; + left_curve->point_list = curve->point_list; + right_curve->point_list = curve->point_list + subdivision_index; + + /* We want to use the tangents of the curve which we are + subdividing for the start tangent for left_curve and the + end tangent for right_curve. */ + CURVE_START_TANGENT(left_curve) = CURVE_START_TANGENT(curve); + CURVE_END_TANGENT(right_curve) = CURVE_END_TANGENT(curve); + + /* We have to set up the two curves before finding the tangent at + the subdivision point. The tangent at that point must be the + same for both curves, or noticeable bumps will occur in the + character. But we want to use information on both sides of the + point to compute the tangent, hence cross_curve = true. */ + find_tangent(left_curve, /* to_start_point: */ FALSE, + /* cross_curve: */ TRUE, fitting_opts->tangent_surround); + CURVE_START_TANGENT(right_curve) = CURVE_END_TANGENT(left_curve); + + /* Now that we've set up the curves, we can fit them. */ + left_spline_list = fit_curve(left_curve, fitting_opts, exception); + if (at_exception_got_fatal(exception)) + /* TODO: Memory allocated for left_curve and right_curve + will leak. */ + goto cleanup; + + right_spline_list = fit_curve(right_curve, fitting_opts, exception); + /* TODO: Memory allocated for left_curve and right_curve + will leak. */ + if (at_exception_got_fatal(exception)) + goto cleanup; + + /* Neither of the subdivided curves could be fit, so fail. */ + if (left_spline_list == NULL && right_spline_list == NULL) + return NULL; + + /* Put the two together (or whichever of them exist). */ + spline_list = new_spline_list(); + + if (left_spline_list == NULL) { + LOG("Could not fit spline to left curve (%lx).\n", (unsigned long)left_curve); + at_exception_warning(exception, "Could not fit left spline list"); + } else { + concat_spline_lists(spline_list, *left_spline_list); + free_spline_list(*left_spline_list); + free(left_spline_list); + } + + if (right_spline_list == NULL) { + LOG("Could not fit spline to right curve (%lx).\n", (unsigned long)right_curve); + at_exception_warning(exception, "Could not fit right spline list"); + } else { + concat_spline_lists(spline_list, *right_spline_list); + free_spline_list(*right_spline_list); + free(right_spline_list); + } + if (CURVE_END_TANGENT(left_curve)) + free(CURVE_END_TANGENT(left_curve)); + free(left_curve); + free(right_curve); + } +cleanup: + return spline_list; +} + +/* Our job here is to find alpha1 (and alpha2), where t1_hat (t2_hat) is + the tangent to CURVE at the starting (ending) point, such that: + + control1 = alpha1*t1_hat + starting point + control2 = alpha2*t2_hat + ending_point + + and the resulting spline (starting_point .. control1 and control2 .. + ending_point) minimizes the least-square error from CURVE. + + See pp.57--59 of the Phoenix thesis. + + The B?(t) here corresponds to B_i^3(U_i) there. + The Bernshte\u in polynomials of degree n are defined by + B_i^n(t) = { n \choose i } t^i (1-t)^{n-i}, i = 0..n */ + +#define B0(t) CUBE ((gfloat) 1.0 - (t)) +#define B1(t) ((gfloat) 3.0 * (t) * SQUARE ((gfloat) 1.0 - (t))) +#define B2(t) ((gfloat) 3.0 * SQUARE (t) * ((gfloat) 1.0 - (t))) +#define B3(t) CUBE (t) + +static spline_type fit_one_spline(curve_type curve, at_exception_type * exception) +{ + /* Since our arrays are zero-based, the `C0' and `C1' here correspond + to `C1' and `C2' in the paper. */ + gfloat X_C1_det, C0_X_det, C0_C1_det; + gfloat alpha1, alpha2; + spline_type spline; + vector_type start_vector, end_vector; + unsigned i; + vector_type *A; + vector_type t1_hat = *CURVE_START_TANGENT(curve); + vector_type t2_hat = *CURVE_END_TANGENT(curve); + gfloat C[2][2] = { {0.0, 0.0}, {0.0, 0.0} }; + gfloat X[2] = { 0.0, 0.0 }; + + XMALLOC(A, CURVE_LENGTH(curve) * 2 * sizeof(vector_type)); /* A dynamically allocated array. */ + + START_POINT(spline) = CURVE_POINT(curve, 0); + END_POINT(spline) = LAST_CURVE_POINT(curve); + start_vector = make_vector(START_POINT(spline)); + end_vector = make_vector(END_POINT(spline)); + + for (i = 0; i < CURVE_LENGTH(curve); i++) { + A[(i << 1) + 0] = Vmult_scalar(t1_hat, B1(CURVE_T(curve, i))); + A[(i << 1) + 1] = Vmult_scalar(t2_hat, B2(CURVE_T(curve, i))); + } + + for (i = 0; i < CURVE_LENGTH(curve); i++) { + vector_type temp, temp0, temp1, temp2, temp3; + vector_type *Ai = A + (i << 1); + + C[0][0] += Vdot(Ai[0], Ai[0]); + C[0][1] += Vdot(Ai[0], Ai[1]); + /* C[1][0] = C[0][1] (this is assigned outside the loop) */ + C[1][1] += Vdot(Ai[1], Ai[1]); + + /* Now the right-hand side of the equation in the paper. */ + temp0 = Vmult_scalar(start_vector, B0(CURVE_T(curve, i))); + temp1 = Vmult_scalar(start_vector, B1(CURVE_T(curve, i))); + temp2 = Vmult_scalar(end_vector, B2(CURVE_T(curve, i))); + temp3 = Vmult_scalar(end_vector, B3(CURVE_T(curve, i))); + + temp = make_vector(Vsubtract_point(CURVE_POINT(curve, i), Vadd(temp0, Vadd(temp1, Vadd(temp2, temp3))))); + + X[0] += Vdot(temp, Ai[0]); + X[1] += Vdot(temp, Ai[1]); + } + free(A); + + C[1][0] = C[0][1]; + + X_C1_det = X[0] * C[1][1] - X[1] * C[0][1]; + C0_X_det = C[0][0] * X[1] - C[0][1] * X[0]; + C0_C1_det = C[0][0] * C[1][1] - C[1][0] * C[0][1]; + if (C0_C1_det == 0.0) { + /* Zero determinant */ + alpha1 = 0; + alpha2 = 0; + } else { + alpha1 = X_C1_det / C0_C1_det; + alpha2 = C0_X_det / C0_C1_det; + } + CONTROL1(spline) = Vadd_point(START_POINT(spline), Vmult_scalar(t1_hat, alpha1)); + CONTROL2(spline) = Vadd_point(END_POINT(spline), Vmult_scalar(t2_hat, alpha2)); + SPLINE_DEGREE(spline) = CUBICTYPE; + + return spline; +} + +/* Find reasonable values for t for each point on CURVE. The method is + called chord-length parameterization, which is described in Plass & + Stone. The basic idea is just to use the distance from one point to + the next as the t value, normalized to produce values that increase + from zero for the first point to one for the last point. */ + +static void set_initial_parameter_values(curve_type curve) +{ + unsigned p; + + LOG("\nAssigning initial t values:\n "); + + CURVE_T(curve, 0) = 0.0; + + for (p = 1; p < CURVE_LENGTH(curve); p++) { + at_real_coord point = CURVE_POINT(curve, p), previous_p = CURVE_POINT(curve, p - 1); + gfloat d = distance(point, previous_p); + CURVE_T(curve, p) = CURVE_T(curve, p - 1) + d; + } + + if (LAST_CURVE_T(curve) == 0.0) + LAST_CURVE_T(curve) = 1.0; + + for (p = 1; p < CURVE_LENGTH(curve); p++) + CURVE_T(curve, p) = CURVE_T(curve, p) / LAST_CURVE_T(curve); + + if (logging) + log_entire_curve(curve); +} + +/* Find an approximation to the tangent to an endpoint of CURVE (to the + first point if TO_START_POINT is TRUE, else the last). If + CROSS_CURVE is TRUE, consider points on the adjacent curve to CURVE. + + It is important to compute an accurate approximation, because the + control points that we eventually decide upon to fit the curve will + be placed on the half-lines defined by the tangents and + endpoints...and we never recompute the tangent after this. */ + +static void find_tangent(curve_type curve, gboolean to_start_point, gboolean cross_curve, unsigned tangent_surround) +{ + vector_type tangent; + vector_type **curve_tangent = (to_start_point == TRUE) ? &(CURVE_START_TANGENT(curve)) + : &(CURVE_END_TANGENT(curve)); + unsigned n_points = 0; + + LOG(" tangent to %s: ", (to_start_point == TRUE) ? "start" : "end"); + + if (*curve_tangent == NULL) { + XMALLOC(*curve_tangent, sizeof(vector_type)); + do { + tangent = find_half_tangent(curve, to_start_point, &n_points, tangent_surround); + + if ((cross_curve == TRUE) || (CURVE_CYCLIC(curve) == TRUE)) { + curve_type adjacent_curve = (to_start_point == TRUE) ? PREVIOUS_CURVE(curve) : NEXT_CURVE(curve); + vector_type tangent2 = (to_start_point == FALSE) ? find_half_tangent(adjacent_curve, TRUE, &n_points, + tangent_surround) : find_half_tangent(adjacent_curve, TRUE, &n_points, + tangent_surround); + + LOG("(adjacent curve half tangent (%.3f,%.3f,%.3f)) ", tangent2.dx, tangent2.dy, tangent2.dz); + tangent = Vadd(tangent, tangent2); + } + tangent_surround--; + + } + while (tangent.dx == 0.0 && tangent.dy == 0.0); + + assert(n_points > 0); + **curve_tangent = Vmult_scalar(tangent, (gfloat) (1.0 / n_points)); + if ((CURVE_CYCLIC(curve) == TRUE) && CURVE_START_TANGENT(curve)) + *CURVE_START_TANGENT(curve) = **curve_tangent; + if ((CURVE_CYCLIC(curve) == TRUE) && CURVE_END_TANGENT(curve)) + *CURVE_END_TANGENT(curve) = **curve_tangent; + } else + LOG("(already computed) "); + + LOG("(%.3f,%.3f,%.3f).\n", (*curve_tangent)->dx, (*curve_tangent)->dy, (*curve_tangent)->dz); +} + +/* Find the change in y and change in x for `tangent_surround' (a global) + points along CURVE. Increment N_POINTS by the number of points we + actually look at. */ + +static vector_type find_half_tangent(curve_type c, gboolean to_start_point, unsigned *n_points, unsigned tangent_surround) +{ + unsigned p; + int factor = to_start_point ? 1 : -1; + unsigned tangent_index = to_start_point ? 0 : c->length - 1; + at_real_coord tangent_point = CURVE_POINT(c, tangent_index); + vector_type tangent = { 0.0, 0.0 }; + unsigned int surround; + + if ((surround = CURVE_LENGTH(c) / 2) > tangent_surround) + surround = tangent_surround; + + for (p = 1; p <= surround; p++) { + int this_index = p * factor + tangent_index; + at_real_coord this_point; + + if (this_index < 0 || this_index >= (int)c->length) + break; + + this_point = CURVE_POINT(c, p * factor + tangent_index); + + /* Perhaps we should weight the tangent from `this_point' by some + factor dependent on the distance from the tangent point. */ + tangent = Vadd(tangent, Vmult_scalar(Psubtract(this_point, tangent_point), (gfloat) factor)); + (*n_points)++; + } + + return tangent; +} + +/* When this routine is called, we have computed a spline representation + for the digitized curve. The question is, how good is it? If the + fit is very good indeed, we might have an error of zero on each + point, and then WORST_POINT becomes irrelevant. But normally, we + return the error at the worst point, and the index of that point in + WORST_POINT. The error computation itself is the Euclidean distance + from the original curve CURVE to the fitted spline SPLINE. */ + +static gfloat find_error(curve_type curve, spline_type spline, unsigned *worst_point, at_exception_type * exception) +{ + unsigned this_point; + gfloat total_error = 0.0; + gfloat worst_error = FLT_MIN; + + *worst_point = CURVE_LENGTH(curve) + 1; /* A sentinel value. */ + + for (this_point = 0; this_point < CURVE_LENGTH(curve); this_point++) { + at_real_coord curve_point = CURVE_POINT(curve, this_point); + gfloat t = CURVE_T(curve, this_point); + at_real_coord spline_point = evaluate_spline(spline, t); + gfloat this_error = distance(curve_point, spline_point); + if (this_error >= worst_error) { + *worst_point = this_point; + worst_error = this_error; + } + total_error += this_error; + } + + if (*worst_point == CURVE_LENGTH(curve) + 1) { /* Didn't have any ``worst point''; the error should be zero. */ + if (epsilon_equal(total_error, 0.0)) + LOG(" Every point fit perfectly.\n"); + else { + LOG("No worst point found; something is wrong"); + at_exception_warning(exception, "No worst point found; something is wrong"); + } + } else { + if (epsilon_equal(total_error, 0.0)) + LOG(" Every point fit perfectly.\n"); + else { + LOG(" Worst error (at (%.3f,%.3f,%.3f), point #%u) was %.3f.\n", CURVE_POINT(curve, *worst_point).x, CURVE_POINT(curve, *worst_point).y, CURVE_POINT(curve, *worst_point).z, *worst_point, worst_error); + LOG(" Total error was %.3f.\n", total_error); + LOG(" Average error (over %u points) was %.3f.\n", CURVE_LENGTH(curve), total_error / CURVE_LENGTH(curve)); + } + } + + return worst_error; +} + +/* Supposing that we have accepted the error, another question arises: + would we be better off just using a straight line? */ + +static gboolean spline_linear_enough(spline_type * spline, curve_type curve, fitting_opts_type * fitting_opts) +{ + gfloat A, B, C; + unsigned this_point; + gfloat dist = 0.0, start_end_dist, threshold; + + LOG("Checking linearity:\n"); + + A = END_POINT(*spline).x - START_POINT(*spline).x; + B = END_POINT(*spline).y - START_POINT(*spline).y; + C = END_POINT(*spline).z - START_POINT(*spline).z; + + start_end_dist = (gfloat) (SQUARE(A) + SQUARE(B) + SQUARE(C)); + LOG("start_end_distance is %.3f.\n", sqrt(start_end_dist)); + + LOG(" Line endpoints are (%.3f, %.3f, %.3f) and ", START_POINT(*spline).x, START_POINT(*spline).y, START_POINT(*spline).z); + LOG("(%.3f, %.3f, %.3f)\n", END_POINT(*spline).x, END_POINT(*spline).y, END_POINT(*spline).z); + + /* LOG (" Line is %.3fx + %.3fy + %.3f = 0.\n", A, B, C); */ + + for (this_point = 0; this_point < CURVE_LENGTH(curve); this_point++) { + gfloat a, b, c, w; + gfloat t = CURVE_T(curve, this_point); + at_real_coord spline_point = evaluate_spline(*spline, t); + + a = spline_point.x - START_POINT(*spline).x; + b = spline_point.y - START_POINT(*spline).y; + c = spline_point.z - START_POINT(*spline).z; + w = (A * a + B * b + C * c) / start_end_dist; + + dist += (gfloat) sqrt(SQUARE(a - A * w) + SQUARE(b - B * w) + SQUARE(c - C * w)); + } + LOG(" Total distance is %.3f, ", dist); + + dist /= (CURVE_LENGTH(curve) - 1); + LOG("which is %.3f normalized.\n", dist); + + /* We want reversion of short curves to splines to be more likely than + reversion of long curves, hence the second division by the curve + length, for use in `change_bad_lines'. */ + SPLINE_LINEARITY(*spline) = dist; + LOG(" Final linearity: %.3f.\n", SPLINE_LINEARITY(*spline)); + if (start_end_dist * (gfloat) 0.5 > fitting_opts->line_threshold) + threshold = fitting_opts->line_threshold; + else + threshold = start_end_dist * (gfloat) 0.5; + LOG("threshold is %.3f .\n", threshold); + if (dist < threshold) + return TRUE; + else + return FALSE; +} + +/* Unfortunately, we cannot tell in isolation whether a given spline + should be changed to a line or not. That can only be known after the + entire curve has been fit to a list of splines. (The curve is the + pixel outline between two corners.) After subdividing the curve, a + line may very well fit a portion of the curve just as well as the + spline---but unless a spline is truly close to being a line, it + should not be combined with other lines. */ + +static void change_bad_lines(spline_list_type * spline_list, fitting_opts_type * fitting_opts) +{ + unsigned this_spline; + gboolean found_cubic = FALSE; + unsigned length = SPLINE_LIST_LENGTH(*spline_list); + + LOG("\nChecking for bad lines (length %u):\n", length); + + /* First see if there are any splines in the fitted shape. */ + for (this_spline = 0; this_spline < length; this_spline++) { + if (SPLINE_DEGREE(SPLINE_LIST_ELT(*spline_list, this_spline)) == CUBICTYPE) { + found_cubic = TRUE; + break; + } + } + + /* If so, change lines back to splines (we haven't done anything to + their control points, so we only have to change the degree) unless + the spline is close enough to being a line. */ + if (found_cubic) + for (this_spline = 0; this_spline < length; this_spline++) { + spline_type s = SPLINE_LIST_ELT(*spline_list, this_spline); + + if (SPLINE_DEGREE(s) == LINEARTYPE) { + LOG(" #%u: ", this_spline); + if (SPLINE_LINEARITY(s) > fitting_opts->line_reversion_threshold) { + LOG("reverted, "); + SPLINE_DEGREE(SPLINE_LIST_ELT(*spline_list, this_spline)) + = CUBICTYPE; + } + LOG("linearity %.3f.\n", SPLINE_LINEARITY(s)); + } + } else + LOG(" No lines.\n"); +} + +/* Lists of array indices (well, that is what we use it for). */ + +static index_list_type new_index_list(void) +{ + index_list_type index_list; + + index_list.data = NULL; + INDEX_LIST_LENGTH(index_list) = 0; + + return index_list; +} + +static void free_index_list(index_list_type * index_list) +{ + if (INDEX_LIST_LENGTH(*index_list) > 0) { + free(index_list->data); + index_list->data = NULL; + INDEX_LIST_LENGTH(*index_list) = 0; + } +} + +static void append_index(index_list_type * list, unsigned new_index) +{ + INDEX_LIST_LENGTH(*list)++; + XREALLOC(list->data, INDEX_LIST_LENGTH(*list) * sizeof(unsigned)); + list->data[INDEX_LIST_LENGTH(*list) - 1] = new_index; +} + +/* Turn an real point into a integer one. */ + +static at_coord real_to_int_coord(at_real_coord real_coord) +{ + at_coord int_coord; + + int_coord.x = lround(real_coord.x); + int_coord.y = lround(real_coord.y); + + return int_coord; +} + +/* Return the Euclidean distance between P1 and P2. */ + +static gfloat distance(at_real_coord p1, at_real_coord p2) +{ + gfloat x = p1.x - p2.x, y = p1.y - p2.y, z = p1.z - p2.z; + return (gfloat) sqrt(SQUARE(x) + + SQUARE(y) + SQUARE(z)); +} diff --git a/src/3rdparty/autotrace/fit.h b/src/3rdparty/autotrace/fit.h new file mode 100644 index 0000000..1875887 --- /dev/null +++ b/src/3rdparty/autotrace/fit.h @@ -0,0 +1,22 @@ +/* fit.h: convert the pixel representation to splines. */ + +#ifndef FIT_H +#define FIT_H + +#include "autotrace.h" +#include "image-proc.h" +#include "pxl-outline.h" +#include "spline.h" +#include "exception.h" + +/* See fit.c for descriptions of these variables, all of which can be + set using options. */ +typedef at_fitting_opts_type fitting_opts_type; + +/* Fit splines and lines to LIST. */ +extern spline_list_array_type fitted_splines(pixel_outline_list_type, fitting_opts_type *, at_distance_map *, unsigned short width, unsigned short height, at_exception_type * exception, at_progress_func, gpointer, at_testcancel_func, gpointer); + +/* Get a new set of fitting options */ +extern fitting_opts_type new_fitting_opts(void); + +#endif /* not FIT_H */ diff --git a/src/3rdparty/autotrace/image-header.h b/src/3rdparty/autotrace/image-header.h new file mode 100644 index 0000000..c685735 --- /dev/null +++ b/src/3rdparty/autotrace/image-header.h @@ -0,0 +1,18 @@ +/* image-header.h: declarations for a generic image header. */ + +#ifndef IMAGE_HEADER_H +#define IMAGE_HEADER_H + +#include "types.h" + +/* The important general information about the image data. + See `get_{img,pbm}_header' for the full details of the headers for + the particular formats. */ +typedef struct { + unsigned short hres, vres; /* In pixels per inch. */ + unsigned short width, height; /* In bits. */ + unsigned short depth; /* Perhaps the depth? */ + unsigned format; /* (for pbm) Whether packed or not. */ +} image_header_type; + +#endif /* not IMAGE_HEADER_H */ diff --git a/src/3rdparty/autotrace/image-proc.c b/src/3rdparty/autotrace/image-proc.c new file mode 100644 index 0000000..7709175 --- /dev/null +++ b/src/3rdparty/autotrace/image-proc.c @@ -0,0 +1,493 @@ +/* image-proc.c: image processing routines */ + +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif /* Def: HAVE_CONFIG_H */ + +#include <assert.h> +#include <math.h> +#include "xstd.h" +#include "logreport.h" +#include "image-proc.h" + +#define BLACK 0 +#define WHITE 0xff +#ifndef M_SQRT2 +#define M_SQRT2 1.41421356237 +#endif + +/* Threshold for binarizing a monochrome image */ +#define GRAY_THRESHOLD 225 + +/* RGB to grayscale */ +#define LUMINANCE(r, g, b) ((r) * 0.30 + (g) * 0.59 + (b) * 0.11 + 0.5) + +#if 0 +struct etyp { + int t00, t11, t01, t01s; +}; + +static gboolean get_edge(bitmap_type, int y, int x, struct etyp *t); +static void check(int v1, int v2, int v3, struct etyp *t); +#endif + +/* Allocate storage for a new distance map with the same dimensions + as BITMAP and initialize it so that pixels in BITMAP with value + TARGET_VALUE are at distance zero and all other pixels are at + distance infinity. Then compute the gray-weighted distance from + every non-target point to the nearest target point. */ + +at_distance_map new_distance_map(at_bitmap * bitmap, unsigned char target_value, gboolean padded, at_exception_type * exp) +{ + signed x, y; + float d, min; + at_distance_map dist; + unsigned char *b = AT_BITMAP_BITS(bitmap); + unsigned w = AT_BITMAP_WIDTH(bitmap); + unsigned h = AT_BITMAP_HEIGHT(bitmap); + unsigned spp = AT_BITMAP_PLANES(bitmap); + + dist.height = h; + dist.width = w; + XMALLOC(dist.d, h * sizeof(float *)); + XMALLOC(dist.weight, h * sizeof(float *)); + for (y = 0; y < (signed)h; y++) { + XCALLOC(dist.d[y], w * sizeof(float)); + XMALLOC(dist.weight[y], w * sizeof(float)); + } + + if (spp == 3) { + for (y = 0; y < (signed)h; y++) { + for (x = 0; x < (signed)w; x++, b += spp) { + int gray; + float fgray; + gray = (int)LUMINANCE(b[0], b[1], b[2]); + dist.d[y][x] = (gray == target_value ? 0.0F : 1.0e10F); + fgray = gray * 0.0039215686F; /* = gray / 255.0F */ + dist.weight[y][x] = 1.0F - fgray; +/* dist.weight[y][x] = 1.0F - (fgray * fgray);*/ +/* dist.weight[y][x] = (fgray < 0.5F ? 1.0F - fgray : -2.0F * fgray * (fgray - 1.0F));*/ + } + } + } else { + for (y = 0; y < (signed)h; y++) { + for (x = 0; x < (signed)w; x++, b += spp) { + int gray; + float fgray; + gray = b[0]; + dist.d[y][x] = (gray == target_value ? 0.0F : 1.0e10F); + fgray = gray * 0.0039215686F; /* = gray / 255.0F */ + dist.weight[y][x] = 1.0F - fgray; +/* dist.weight[y][x] = 1.0F - (fgray * fgray);*/ +/* dist.weight[y][x] = (fgray < 0.5F ? 1.0F - fgray : -2.0F * fgray * (fgray - 1.0F)); */ + } + } + } + + /* If the image is padded then border points are all at most + one unit away from the nearest target point. */ + if (padded) { + for (y = 0; y < (signed)h; y++) { + if (dist.d[y][0] > dist.weight[y][0]) + dist.d[y][0] = dist.weight[y][0]; + if (dist.d[y][w - 1] > dist.weight[y][w - 1]) + dist.d[y][w - 1] = dist.weight[y][w - 1]; + } + for (x = 0; x < (signed)w; x++) { + if (dist.d[0][x] > dist.weight[0][x]) + dist.d[0][x] = dist.weight[0][x]; + if (dist.d[h - 1][x] > dist.weight[h - 1][x]) + dist.d[h - 1][x] = dist.weight[h - 1][x]; + } + } + + /* Scan the image from left to right, top to bottom. + Examine the already-visited neighbors of each point (those + situated above or to the left of it). Each neighbor knows + the distance to its nearest target point; add to this distance + the distance from the central point to the neighbor (either + sqrt(2) or one) multiplied by the central point's weight + (derived from its gray level). Replace the distance already + stored at the central point if the new distance is smaller. */ + for (y = 1; y < (signed)h; y++) { + for (x = 1; x < (signed)w; x++) { + if (dist.d[y][x] == 0.0F) + continue; + + min = dist.d[y][x]; + + /* upper-left neighbor */ + d = dist.d[y - 1][x - 1] + (float)M_SQRT2 *dist.weight[y][x]; + if (d < min) + min = dist.d[y][x] = d; + + /* upper neighbor */ + d = dist.d[y - 1][x] + dist.weight[y][x]; + if (d < min) + min = dist.d[y][x] = d; + + /* left neighbor */ + d = dist.d[y][x - 1] + dist.weight[y][x]; + if (d < min) + min = dist.d[y][x] = d; + + /* upper-right neighbor (except at the last column) */ + if (x + 1 < (signed)w) { + d = dist.d[y - 1][x + 1] + (float)M_SQRT2 *dist.weight[y][x]; + if (d < min) + min = dist.d[y][x] = d; + } + } + } + + /* Same as above, but now scanning right to left, bottom to top. */ + for (y = h - 2; y >= 0; y--) { + for (x = w - 2; x >= 0; x--) { + min = dist.d[y][x]; + + /* lower-right neighbor */ + d = dist.d[y + 1][x + 1] + (float)M_SQRT2 *dist.weight[y][x]; + if (d < min) + min = dist.d[y][x] = d; + + /* lower neighbor */ + d = dist.d[y + 1][x] + dist.weight[y][x]; + if (d < min) + min = dist.d[y][x] = d; + + /* right neighbor */ + d = dist.d[y][x + 1] + dist.weight[y][x]; + if (d < min) + min = dist.d[y][x] = d; + + /* lower-left neighbor (except at the first column) */ + if (x - 1 >= 0) { + d = dist.d[y + 1][x - 1] + (float)M_SQRT2 *dist.weight[y][x]; + if (d < min) + min = dist.d[y][x] = d; + } + } + } + return dist; +} + +/* Free the dynamically-allocated storage associated with a distance map. */ + +void free_distance_map(at_distance_map * dist) +{ + unsigned y, h; + + if (!dist) + return; + + h = dist->height; + + if (dist->d != NULL) { + for (y = 0; y < h; y++) + free((gpointer *) dist->d[y]); + free((gpointer *) dist->d); + } + if (dist->weight != NULL) { + for (y = 0; y < h; y++) + free((gpointer *) dist->weight[y]); + free((gpointer *) dist->weight); + } +} + +#if 0 +void medial_axis(bitmap_type * bitmap, at_distance_map * dist, const at_color * bg_color) +{ + unsigned x, y, test; + unsigned w, h; + unsigned char *b; + float **d, f; + at_color bg; + + assert(bitmap != NULL); + + assert(AT_BITMAP_PLANES(*bitmap) == 1); + + b = AT_BITMAP_BITS(*bitmap); + assert(b != NULL); + assert(dist != NULL); + d = dist->d; + assert(d != NULL); + + h = AT_BITMAP_HEIGHT(*dist); + w = AT_BITMAP_WIDTH(*dist); + assert(AT_BITMAP_WIDTH(*bitmap) == w && AT_BITMAP_HEIGHT(*bitmap) == h); + + if (bg_color) + bg = *bg_color; + else + bg.r = bg.g = bg.b = 255; + + f = d[0][0] + 0.5; + test = (f < d[1][0]) + (f < d[1][1]) + (f < d[0][1]); + if (test > 1) + b[0] = bg.r; + + f = d[0][w - 1] + 0.5; + test = (f < d[1][w - 1]) + (f < d[1][w - 2]) + (f < d[0][w - 2]); + if (test > 1) + b[w - 1] = bg.r; + + for (x = 1; x < w - 1; x++) { + f = d[0][x] + 0.5; + test = (f < d[0][x - 1]) + (f < d[0][x + 1]) + (f < d[1][x - 1]) + + (f < d[1][x]) + (f < d[1][x + 1]); + if (test > 1) + b[x] = bg.r; + } + b += w; + + for (y = 1; y < h - 1; y++) { + f = d[y][0] + 0.5; + test = (f < d[y - 1][0]) + (f < d[y - 1][1]) + (f < d[y][1]) + + (f < d[y + 1][0]) + (f < d[y + 1][1]); + if (test > 1) + b[0] = bg.r; + + for (x = 1; x < w - 1; x++) { + f = d[y][x] + 0.5; + test = (f < d[y - 1][x - 1]) + (f < d[y - 1][x]) + (f < d[y - 1][x + 1]) + + (f < d[y][x - 1]) + (f < d[y][x + 1]) + + (f < d[y + 1][x - 1]) + (f < d[y + 1][x]) + (f < d[y + 1][x + 1]); + if (test > 1) + b[x] = bg.r; + } + + f = d[y][w - 1] + 0.5; + test = (f < d[y - 1][w - 1]) + (f < d[y - 1][w - 2]) + (f < d[y][w - 2]) + + (f < d[y + 1][w - 1]) + (f < d[y + 1][w - 2]); + if (test > 1) + b[w - 1] = bg.r; + + b += w; + } + + for (x = 1; x < w - 1; x++) { + f = d[h - 1][x] + 0.5; + test = (f < d[h - 1][x - 1]) + (f < d[h - 1][x + 1]) + + (f < d[h - 2][x - 1]) + (f < d[h - 2][x]) + (f < d[h - 2][x + 1]); + if (test > 1) + b[x] = bg.r; + } + + f = d[h - 1][0] + 0.5; + test = (f < d[h - 2][0]) + (f < d[h - 2][1]) + (f < d[h - 1][1]); + if (test > 1) + b[0] = bg.r; + + f = d[h - 1][w - 1] + 0.5; + test = (f < d[h - 2][w - 1]) + (f < d[h - 2][w - 2]) + (f < d[h - 1][w - 2]); + if (test > 1) + b[w - 1] = bg.r; +} +#endif + +/* Binarize a grayscale or color image. */ + +void binarize(at_bitmap * bitmap) +{ + unsigned i, npixels, spp; + unsigned char *b; + + assert(bitmap != NULL); + assert(AT_BITMAP_BITS(bitmap) != NULL); + + b = AT_BITMAP_BITS(bitmap); + spp = AT_BITMAP_PLANES(bitmap); + npixels = AT_BITMAP_WIDTH(bitmap) * AT_BITMAP_HEIGHT(bitmap); + + if (spp == 1) { + for (i = 0; i < npixels; i++) + b[i] = (b[i] > GRAY_THRESHOLD ? WHITE : BLACK); + } else if (spp == 3) { + unsigned char *rgb = b; + for (i = 0; i < npixels; i++, rgb += 3) { + b[i] = (LUMINANCE(rgb[0], rgb[1], rgb[2]) > GRAY_THRESHOLD ? WHITE : BLACK); + } + XREALLOC(AT_BITMAP_BITS(bitmap), npixels); + AT_BITMAP_PLANES(bitmap) = 1; + } else { + WARNING("binarize: %u-plane images are not supported", spp); + } +} + +#if 0 +/* Thin a binary image, replacing the original image with the thinned one. */ + +at_bitmap ip_thin(bitmap_type input_b) +{ + unsigned y, x, i; + gboolean k, again; + struct etyp t; + unsigned w = AT_BITMAP_WIDTH(input_b); + unsigned h = AT_BITMAP_HEIGHT(input_b); + size_t num_bytes = w * h; + bitmap_type b = input_b; + + if (AT_BITMAP_PLANES(input_b) != 1) { + FATAL("thin: single-plane image required; " "%u-plane images cannot be thinned", AT_BITMAP_PLANES(input_b)); + return b; + } + + /* Process and return a copy of the input image. */ + XMALLOC(b.bitmap, num_bytes); + memcpy(b.bitmap, input_b.bitmap, num_bytes); + + /* Set background pixels to zero, foreground pixels to one. */ + for (i = 0; i < num_bytes; i++) + b.bitmap[i] = (b.bitmap[i] == BLACK ? 1 : 0); + + again = TRUE; + while (again) { + again = FALSE; + + for (y = 1; y < h - 1; y++) { + for (x = 1; x < w - 1; x++) { + /* During processing, pixels are used to store edge + type codes, so we can't just test for WHITE or BLACK. */ + if (*AT_BITMAP_PIXEL(b, y, x) == 0) + continue; + + k = (!get_edge(b, y, x, &t) + || (get_edge(b, y, x + 1, &t) && *AT_BITMAP_PIXEL(b, y - 1, x) + && *AT_BITMAP_PIXEL(b, y + 1, x)) + || (get_edge(b, y + 1, x, &t) && *AT_BITMAP_PIXEL(b, y, x - 1) + && *AT_BITMAP_PIXEL(b, y, x + 1)) + || (get_edge(b, y, x + 1, &t) && get_edge(b, y + 1, x + 1, &t) + && get_edge(b, y + 1, x, &t))); + if (k) + continue; + + get_edge(b, y, x, &t); + if (t.t01) + *AT_BITMAP_PIXEL(b, y, x) |= 4; + *AT_BITMAP_PIXEL(b, y, x) |= 2; + again = TRUE; + } + } + + for (y = 0; y < h; y++) + for (x = 0; x < w; x++) + if (*AT_BITMAP_PIXEL(b, y, x) & 02) + *AT_BITMAP_PIXEL(b, y, x) = 0; + + for (y = 1; y < h - 1; y++) { + for (x = 1; x < w - 1; x++) { + if (*AT_BITMAP_PIXEL(b, y, x) == 0) + continue; + + k = (!get_edge(b, y, x, &t) + || ((*AT_BITMAP_PIXEL(b, y, x) & 04) == 0) + || (get_edge(b, y + 1, x, &t) && (*AT_BITMAP_PIXEL(b, y, x - 1)) + && *AT_BITMAP_PIXEL(b, y, x + 1)) + || (get_edge(b, y, x + 1, &t) && *AT_BITMAP_PIXEL(b, y - 1, x) + && *AT_BITMAP_PIXEL(b, y + 1, x)) + || (get_edge(b, y + 1, x, &t) && get_edge(b, y, x + 1, &t) + && get_edge(b, y + 1, x + 1, &t))); + if (k) + continue; + + *AT_BITMAP_PIXEL(b, y, x) |= 02; + again = TRUE; + } + } + + for (y = 0; y < h; y++) { + for (x = 0; x < w; x++) { + if (*AT_BITMAP_PIXEL(b, y, x) & 02) + *AT_BITMAP_PIXEL(b, y, x) = 0; + else if (*AT_BITMAP_PIXEL(b, y, x) > 0) + *AT_BITMAP_PIXEL(b, y, x) = 1; + } + } + } + + /* Staircase removal; northward bias. */ + for (y = 1; y < h - 1; y++) { + for (x = 1; x < w - 1; x++) { + if (*AT_BITMAP_PIXEL(b, y, x) == 0) + continue; + + k = !(*AT_BITMAP_PIXEL(b, y - 1, x) + && ((*AT_BITMAP_PIXEL(b, y, x + 1) && !*AT_BITMAP_PIXEL(b, y - 1, x + 1) + && !*AT_BITMAP_PIXEL(b, y + 1, x - 1) + && (!*AT_BITMAP_PIXEL(b, y, x - 1) || !*AT_BITMAP_PIXEL(b, y + 1, x))) + || (*AT_BITMAP_PIXEL(b, y, x - 1) && !*AT_BITMAP_PIXEL(b, y - 1, x - 1) + && !*AT_BITMAP_PIXEL(b, y + 1, x + 1) && (!*AT_BITMAP_PIXEL(b, y, x + 1) || !*AT_BITMAP_PIXEL(b, y + 1, x))))); + if (k) + continue; + + *AT_BITMAP_PIXEL(b, y, x) |= 02; + } + } + for (y = 0; y < h; y++) { + for (x = 0; x < w; x++) { + if (*AT_BITMAP_PIXEL(b, y, x) & 02) + *AT_BITMAP_PIXEL(b, y, x) = 0; + else if (*AT_BITMAP_PIXEL(b, y, x) > 0) + *AT_BITMAP_PIXEL(b, y, x) = 1; + } + } + + /* Southward bias */ + for (y = 1; y < h - 1; y++) { + for (x = 1; x < w - 1; x++) { + if (*AT_BITMAP_PIXEL(b, y, x) == 0) + continue; + + k = !(*AT_BITMAP_PIXEL(b, y + 1, x) + && ((*AT_BITMAP_PIXEL(b, y, x + 1) && !*AT_BITMAP_PIXEL(b, y + 1, x + 1) + && !*AT_BITMAP_PIXEL(b, y - 1, x - 1) && (!*AT_BITMAP_PIXEL(b, y, x - 1) + || !*AT_BITMAP_PIXEL(b, y - 1, x))) || (*AT_BITMAP_PIXEL(b, y, x - 1) + && !*AT_BITMAP_PIXEL(b, y + 1, x - 1) && !*AT_BITMAP_PIXEL(b, y - 1, x + 1) + && (!*AT_BITMAP_PIXEL(b, y, x + 1) || !*AT_BITMAP_PIXEL(b, y - 1, x))))); + if (k) + continue; + + *AT_BITMAP_PIXEL(b, y, x) |= 02; + } + } + for (y = 0; y < h; y++) { + for (x = 0; x < w; x++) { + if (*AT_BITMAP_PIXEL(b, y, x) & 02) + *AT_BITMAP_PIXEL(b, y, x) = 0; + else if (*AT_BITMAP_PIXEL(b, y, x) > 0) + *AT_BITMAP_PIXEL(b, y, x) = 1; + } + } + + /* Set background pixels to WHITE, foreground pixels to BLACK. */ + for (i = 0; i < num_bytes; i++) + b.bitmap[i] = (b.bitmap[i] == 0 ? WHITE : BLACK); + return b; +} + +gboolean get_edge(bitmap_type b, int y, int x, struct etyp * t) +{ + t->t00 = 0; + t->t01 = 0; + t->t01s = 0; + t->t11 = 0; + check(*AT_BITMAP_PIXEL(b, y - 1, x - 1), *AT_BITMAP_PIXEL(b, y - 1, x), *AT_BITMAP_PIXEL(b, y - 1, x + 1), t); + check(*AT_BITMAP_PIXEL(b, y - 1, x + 1), *AT_BITMAP_PIXEL(b, y, x + 1), *AT_BITMAP_PIXEL(b, y + 1, x + 1), t); + check(*AT_BITMAP_PIXEL(b, y + 1, x + 1), *AT_BITMAP_PIXEL(b, y + 1, x), *AT_BITMAP_PIXEL(b, y + 1, x - 1), t); + check(*AT_BITMAP_PIXEL(b, y + 1, x - 1), *AT_BITMAP_PIXEL(b, y, x - 1), *AT_BITMAP_PIXEL(b, y - 1, x - 1), t); + return *AT_BITMAP_PIXEL(b, y, x) && t->t00 && t->t11 && !t->t01s; +} + +void check(int v1, int v2, int v3, struct etyp *t) +{ + if (!v2 && (!v1 || !v3)) + t->t00 = 1; + if (v2 && (v1 || v3)) + t->t11 = 1; + if ((!v1 && v2) || (!v2 && v3)) { + t->t01s = t->t01; + t->t01 = 1; + } +} +#endif diff --git a/src/3rdparty/autotrace/image-proc.h b/src/3rdparty/autotrace/image-proc.h new file mode 100644 index 0000000..5c131a7 --- /dev/null +++ b/src/3rdparty/autotrace/image-proc.h @@ -0,0 +1,21 @@ +/* image-proc.h: image processing routines */ + +#ifndef IMAGE_PROC_H +#define IMAGE_PROC_H + +#include "bitmap.h" +#include "color.h" + +typedef struct { + unsigned height, width; + float **weight; + float **d; +} at_distance_map; + +/* Allocate and compute a new distance map. */ +extern at_distance_map new_distance_map(at_bitmap *, unsigned char target_value, gboolean padded, at_exception_type * exp); + +/* Free the dynamically-allocated storage associated with a distance map. */ +extern void free_distance_map(at_distance_map *); + +#endif /* not IMAGE_PROC_H */ diff --git a/src/3rdparty/autotrace/input.c b/src/3rdparty/autotrace/input.c new file mode 100644 index 0000000..8ffb719 --- /dev/null +++ b/src/3rdparty/autotrace/input.c @@ -0,0 +1,227 @@ +/* input.c: interface for input handlers + + Copyright (C) 1999, 2000, 2001 Bernhard Herzog. + Copyright (C) 2003 Masatake YAMATO + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public License + as published by the Free Software Foundation; either version 2.1 of + the License, or (at your option) any later version. + + This library 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 + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with this library; if not, write to the Free Software + Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 + USA. */ + +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif /* Def: HAVE_CONFIG_H */ + +#include "autotrace.h" +#include "private.h" +#include "input.h" +#include "xstd.h" +#include "filename.h" +#include <string.h> +#include <glib.h> + +typedef struct _at_input_format_entry at_input_format_entry; +struct _at_input_format_entry { + at_bitmap_reader reader; + const gchar *descr; + GDestroyNotify user_data_destroy_func; +}; + +static GHashTable *at_input_formats = NULL; +static at_input_format_entry *at_input_format_new(const char *descr, at_input_func reader, gpointer user_data, GDestroyNotify user_data_destroy_func); +static void at_input_format_free(at_input_format_entry * entry); + +/* + * Helper functions + */ +static void input_list_set(gpointer key, gpointer value, gpointer user_data); +static void input_list_strlen(gpointer key, gpointer value, gpointer user_data); +static void input_list_strcat(gpointer key, gpointer value, gpointer user_data); + +/** + * at_input_init: + * Initialize at_input input plugin sub system. + * + * Return value: 1 for success, else for failure + **/ +int at_input_init(void) +{ + if (at_input_formats) + return 1; + + at_input_formats = g_hash_table_new_full(g_str_hash, (GEqualFunc) g_str_equal, g_free, (GDestroyNotify) at_input_format_free); + if (!at_input_formats) + return 0; + return 1; +} + +static at_input_format_entry *at_input_format_new(const gchar * descr, at_input_func reader, gpointer user_data, GDestroyNotify user_data_destroy_func) +{ + at_input_format_entry *entry; + entry = g_malloc(sizeof(at_input_format_entry)); + if (entry) { + entry->reader.func = reader; + entry->reader.data = user_data; + entry->descr = g_strdup(descr); + entry->user_data_destroy_func = user_data_destroy_func; + } + return entry; +} + +static void at_input_format_free(at_input_format_entry * entry) +{ + g_free((gpointer) entry->descr); + if (entry->user_data_destroy_func) + entry->user_data_destroy_func(entry->reader.data); + g_free(entry); + +} + +int at_input_add_handler(const gchar * suffix, const gchar * description, at_input_func reader) +{ + return at_input_add_handler_full(suffix, description, reader, 0, NULL, NULL); +} + +int at_input_add_handler_full(const gchar * suffix, const gchar * description, at_input_func reader, gboolean override, gpointer user_data, GDestroyNotify user_data_destroy_func) +{ + gchar *gsuffix; + const gchar *gdescription; + at_input_format_entry *old_entry; + at_input_format_entry *new_entry; + + g_return_val_if_fail(suffix, 0); + g_return_val_if_fail(description, 0); + g_return_val_if_fail(reader, 0); + + gsuffix = g_strdup((gchar *) suffix); + g_return_val_if_fail(gsuffix, 0); + gsuffix = g_ascii_strdown(gsuffix, strlen(gsuffix)); + + gdescription = (const gchar *)description; + + old_entry = g_hash_table_lookup(at_input_formats, gsuffix); + if (old_entry && !override) { + g_free(gsuffix); + return 1; + } + + new_entry = at_input_format_new(gdescription, reader, user_data, user_data_destroy_func); + g_return_val_if_fail(new_entry, 0); + + g_hash_table_replace(at_input_formats, gsuffix, new_entry); + return 1; +} + +at_bitmap_reader *at_input_get_handler(gchar * filename) +{ + char *ext = find_suffix(filename); + if (ext == NULL) + ext = ""; + + return at_input_get_handler_by_suffix(ext); +} + +at_bitmap_reader *at_input_get_handler_by_suffix(gchar * suffix) +{ + at_input_format_entry *format; + gchar *gsuffix; + + if (!suffix || suffix[0] == '\0') + return NULL; + + gsuffix = g_strdup(suffix); + g_return_val_if_fail(gsuffix, NULL); + gsuffix = g_ascii_strdown(gsuffix, strlen(gsuffix)); + format = g_hash_table_lookup(at_input_formats, gsuffix); + g_free(gsuffix); + + if (format) + return &(format->reader); + else + return NULL; +} + +const char **at_input_list_new(void) +{ + char **list, **tmp; + gint format_count; + gint list_count; + + format_count = g_hash_table_size(at_input_formats); + list_count = 2 * format_count; + list = g_new(gchar *, list_count + 1); + list[list_count] = NULL; + + tmp = list; + g_hash_table_foreach(at_input_formats, input_list_set, &tmp); + return (const char **)list; +} + +void at_input_list_free(const char **list) +{ + free((char **)list); +} + +char *at_input_shortlist(void) +{ + gint length = 0, count; + char *list, *tmp; + g_hash_table_foreach(at_input_formats, input_list_strlen, &length); + count = g_hash_table_size(at_input_formats); + + /* 2 for ", " */ + length += (2 * count); + list = g_malloc(length + 1); + list[0] = '\0'; + + tmp = list; + g_hash_table_foreach(at_input_formats, input_list_strcat, &tmp); + + /* remove final ", " */ + g_return_val_if_fail(list[length - 2] == ',', NULL); + list[length - 2] = '\0'; + return list; +} + +static void input_list_set(gpointer key, gpointer value, gpointer user_data) +{ + at_input_format_entry *format = value; + const char ***list_ptr = user_data; + const char **list = *list_ptr; + list[0] = key; + list[1] = format->descr; + *list_ptr = &(list[2]); +} + +static void input_list_strlen(gpointer key, gpointer value, gpointer user_data) +{ + gint *length; + g_return_if_fail(key); + g_return_if_fail(user_data); + + length = user_data; + *length += strlen(key); +} + +static void input_list_strcat(gpointer key, gpointer value, gpointer user_data) +{ + gchar **list_ptr; + gchar *list; + list_ptr = user_data; + list = *list_ptr; + strcat(list, key); + strcat(list, ", "); + + /* 2 for ", " */ + *list_ptr = list + strlen(key) + 2; +} diff --git a/src/3rdparty/autotrace/input.h b/src/3rdparty/autotrace/input.h new file mode 100644 index 0000000..b4a7d9b --- /dev/null +++ b/src/3rdparty/autotrace/input.h @@ -0,0 +1,95 @@ +/* input.h: interface for input handlers + + Copyright (C) 1999, 2000, 2001 Bernhard Herzog. + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public License + as published by the Free Software Foundation; either version 2.1 of + the License, or (at your option) any later version. + + This library 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 + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with this library; if not, write to the Free Software + Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 + USA. */ + +#ifndef INPUT_H +#define INPUT_H +#include "types.h" +#include "autotrace.h" +#include "exception.h" + +#include <glib.h> + +#ifdef __cplusplus +extern "C" { +#endif /* __cplusplus */ + +/* Input handler should be implemented with using + following functions and macros. */ + + typedef + at_bitmap(*at_input_func) (gchar * name, at_input_opts_type * opts, at_msg_func msg_func, gpointer msg_data, gpointer user_data); + +/* at_input_add_handler + Register an input handler to autotrace. + If a handler for the suffix is already existed, do nothing. */ + extern int at_input_add_handler(const gchar * suffix, const gchar * description, at_input_func reader); +/* at_input_add_handler_full + If OVERRIDE is TRUE and if the old handler for suffix is existed, + remove the old handler first then add new handler. + If OVERRIDE is false, do nothing. */ + extern int at_input_add_handler_full(const gchar * suffix, const gchar * description, at_input_func reader, gboolean override, gpointer user_data, GDestroyNotify user_data_destroy_func); + +/* at_bitmap_init + Return initialized at_bitmap value. + + args: + AREA is used as a storage of returned value. + If AREA is NULL, the storage is newly allocated + by at_bitmap_init. In such case the size of storage + is automatically calculated by WIDTH, HEIGHT and PLANES. + + PLANES must be 1(gray scale) or 3(RGB color). + + return value: + The return value is not newly allocated. + Only the storage is allocated if AREA is NULL. + On the other hand, at_bitmap_new allocates + mem for at_bitmap; and returns a pointer + for the mem. + at_bitmap_new is for autotrace library user. + at_bitmap_init is for input-handler developer. + Don't use at_bitmap_new in your input-handler. */ + extern at_bitmap at_bitmap_init(unsigned char *area, unsigned short width, unsigned short height, unsigned int planes); + +/* TODO: free storage */ + +/* The number of color planes of each pixel */ +#define AT_BITMAP_PLANES(b) ((b)->np) + +/* The pixels, represented as an array of bytes (in contiguous storage). + Each pixel is represented by np bytes. */ +#define AT_BITMAP_BITS(b) ((b)->bitmap) + +/* These are convenient abbreviations for geting inside the members. */ +#define AT_BITMAP_WIDTH(b) ((b)->width) +#define AT_BITMAP_HEIGHT(b) ((b)->height) + +/* This is the pixel at [ROW,COL]. */ +#define AT_BITMAP_PIXEL(b, row, col) \ + ((AT_BITMAP_BITS (b) + (row) * AT_BITMAP_PLANES (b) * AT_BITMAP_WIDTH (b) \ + + (col) * AT_BITMAP_PLANES(b))) + +/* at_ prefix removed version */ +#define AT_BITMAP_VALID_PIXEL(b, row, col) \ + ((row) < AT_BITMAP_HEIGHT (b) && (col) < AT_BITMAP_WIDTH (b)) + +#ifdef __cplusplus +} +#endif /* __cplusplus */ +#endif /* Not def: INPUT_H */ diff --git a/src/3rdparty/autotrace/intl.h b/src/3rdparty/autotrace/intl.h new file mode 100644 index 0000000..7cc6f81 --- /dev/null +++ b/src/3rdparty/autotrace/intl.h @@ -0,0 +1,22 @@ +#ifndef __INTL_H__ +#define __INTL_H__ + +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif /* Def: HAVE_CONFIG_H */ + +#ifdef ENABLE_NLS +#include <libintl.h> +#define _(String) dgettext(PACKAGE,String) +#define N_(String) (String) +#else /* NLS is disabled */ +#define _(String) (String) +#define N_(String) (String) +#define textdomain(String) (String) +#define gettext(String) (String) +#define dgettext(Domain,String) (String) +#define dcgettext(Domain,String,Type) (String) +#define bindtextdomain(Domain,Directory) (Domain) +#endif + +#endif diff --git a/src/3rdparty/autotrace/logreport.c b/src/3rdparty/autotrace/logreport.c new file mode 100644 index 0000000..7784a7c --- /dev/null +++ b/src/3rdparty/autotrace/logreport.c @@ -0,0 +1,9 @@ +/* logreport.c: showing information to the user. */ + +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif /* Def: HAVE_CONFIG_H */ + +#include "logreport.h" + +gboolean logging = FALSE; diff --git a/src/3rdparty/autotrace/logreport.h b/src/3rdparty/autotrace/logreport.h new file mode 100644 index 0000000..04a548c --- /dev/null +++ b/src/3rdparty/autotrace/logreport.h @@ -0,0 +1,32 @@ +/* logreport.h: status reporting routines. */ + +#ifndef LOGREPORT_H +#define LOGREPORT_H + +#include <stdio.h> +#include "types.h" +#include <stdlib.h> + +#ifdef _EXPORTING +#define DECLSPEC __declspec(dllexport) +#elif _IMPORTING +#define DECLSPEC __declspec(dllimport) +#else +#define DECLSPEC +#endif + +/* Whether to write a log */ +extern gboolean logging; + +#define LOG(...) \ + do { if (logging) fprintf (stdout, __VA_ARGS__); } while (0) + +/* Define common sorts of messages. */ + +#define FATAL(...) \ + do { fputs ("fatal: ", stderr); LOG("fatal: "); fprintf (stderr, __VA_ARGS__); LOG (__VA_ARGS__); fputs (".\n", stderr); exit (1); } while (0) + +#define WARNING(...) \ + do { fputs ("warning: ", stderr); LOG ("warning: "); fprintf (stderr, __VA_ARGS__); LOG (__VA_ARGS__); fputs (".\n", stderr); } while (0) + +#endif /* not LOGREPORT_H */ diff --git a/src/3rdparty/autotrace/median.c b/src/3rdparty/autotrace/median.c new file mode 100644 index 0000000..60e8c7f --- /dev/null +++ b/src/3rdparty/autotrace/median.c @@ -0,0 +1,863 @@ +/* median.c: median cut - reducing a high color bitmap to certain number of colors + + Copyright (C) 2001, 2002 Martin Weber + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public License + as published by the Free Software Foundation; either version 2.1 of + the License, or (at your option) any later version. + + This library 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 + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with this library; if not, write to the Free Software + Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 + USA. */ + +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif /* Def: HAVE_CONFIG_H */ + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include "logreport.h" +#include "xstd.h" +#include "quantize.h" + +#define MAXNUMCOLORS 256 + +#if 0 +#define R_SCALE +#define G_SCALE +#define B_SCALE +#else + +/* scale RGB distances by *2,*3,*1 */ +#define R_SCALE <<1 +#define G_SCALE *3 +#define B_SCALE +#endif + +#define BITS_IN_SAMPLE 8 + +#define R_SHIFT (BITS_IN_SAMPLE - PRECISION_R) +#define G_SHIFT (BITS_IN_SAMPLE - PRECISION_G) +#define B_SHIFT (BITS_IN_SAMPLE - PRECISION_B) + +typedef struct { + /* The bounds of the box (inclusive); expressed as histogram indexes */ + int Rmin, Rmax; + int Gmin, Gmax; + int Bmin, Bmax; + /* The volume (actually 2-norm) of the box */ + int volume; + /* The number of nonzero histogram cells within this box */ + long colorcount; +} box, *boxptr; + +static void zero_histogram_rgb(Histogram histogram) +{ + int r, g, b; + for (r = 0; r < HIST_R_ELEMS; r++) + for (g = 0; g < HIST_G_ELEMS; g++) + for (b = 0; b < HIST_B_ELEMS; b++) + histogram[r * MR + g * MG + b] = 0; +} + +static void generate_histogram_rgb(Histogram histogram, at_bitmap * image, const at_color * ignoreColor) +{ + unsigned char *src = image->bitmap; + int num_elems; + ColorFreq *col; + + num_elems = AT_BITMAP_WIDTH(image) * AT_BITMAP_HEIGHT(image); + zero_histogram_rgb(histogram); + + switch (AT_BITMAP_PLANES(image)) { + case 3: + while (num_elems--) { + /* If we have an ignorecolor, skip it. */ + if (ignoreColor) { + if ((src[0] == ignoreColor->r) + && (src[1] == ignoreColor->g) + && (src[2] == ignoreColor->b)) { + src += 3; + continue; + } + } + col = &histogram[(src[0] >> R_SHIFT) * MR + (src[1] >> G_SHIFT) * MG + (src[2] >> B_SHIFT)]; + (*col)++; + src += 3; + } + break; + + case 1: + while (--num_elems >= 0) { + if (ignoreColor && src[num_elems] == ignoreColor->r) + continue; + col = &histogram[(src[num_elems] >> R_SHIFT) * MR + (src[num_elems] >> G_SHIFT) * MG + (src[num_elems] >> B_SHIFT)]; + (*col)++; + } + break; + default: + /* To avoid compiler warning */ ; + } +} + +static boxptr find_biggest_volume(boxptr boxlist, int numboxes) +/* Find the splittable box with the largest (scaled) volume */ +/* Returns 0 if no splittable boxes remain */ +{ + boxptr boxp; + int i; + int maxv = 0; + boxptr which = 0; + + for (i = 0, boxp = boxlist; i < numboxes; i++, boxp++) { + if (boxp->volume > maxv) { + which = boxp; + maxv = boxp->volume; + } + } + + return which; +} + +static void update_box_rgb(Histogram histogram, boxptr boxp) +/* Shrink the min/max bounds of a box to enclose only nonzero elements, */ +/* and recompute its volume and population */ +{ + ColorFreq *histp; + int R, G, B; + int Rmin, Rmax, Gmin, Gmax, Bmin, Bmax; + int dist0, dist1, dist2; + long ccount; + + Rmin = boxp->Rmin; + Rmax = boxp->Rmax; + Gmin = boxp->Gmin; + Gmax = boxp->Gmax; + Bmin = boxp->Bmin; + Bmax = boxp->Bmax; + + if (Rmax > Rmin) + for (R = Rmin; R <= Rmax; R++) + for (G = Gmin; G <= Gmax; G++) { + histp = histogram + R * MR + G * MG + Bmin; + for (B = Bmin; B <= Bmax; B++) + if (*histp++ != 0) { + boxp->Rmin = Rmin = R; + goto have_Rmin; + } + } +have_Rmin: + if (Rmax > Rmin) + for (R = Rmax; R >= Rmin; R--) + for (G = Gmin; G <= Gmax; G++) { + histp = histogram + R * MR + G * MG + Bmin; + for (B = Bmin; B <= Bmax; B++) + if (*histp++ != 0) { + boxp->Rmax = Rmax = R; + goto have_Rmax; + } + } +have_Rmax: + if (Gmax > Gmin) + for (G = Gmin; G <= Gmax; G++) + for (R = Rmin; R <= Rmax; R++) { + histp = histogram + R * MR + G * MG + Bmin; + for (B = Bmin; B <= Bmax; B++) + if (*histp++ != 0) { + boxp->Gmin = Gmin = G; + goto have_Gmin; + } + } +have_Gmin: + if (Gmax > Gmin) + for (G = Gmax; G >= Gmin; G--) + for (R = Rmin; R <= Rmax; R++) { + histp = histogram + R * MR + G * MG + Bmin; + for (B = Bmin; B <= Bmax; B++) + if (*histp++ != 0) { + boxp->Gmax = Gmax = G; + goto have_Gmax; + } + } +have_Gmax: + if (Bmax > Bmin) + for (B = Bmin; B <= Bmax; B++) + for (R = Rmin; R <= Rmax; R++) { + histp = histogram + R * MR + Gmin * MG + B; + for (G = Gmin; G <= Gmax; G++, histp += MG) + if (*histp != 0) { + boxp->Bmin = Bmin = B; + goto have_Bmin; + } + } +have_Bmin: + if (Bmax > Bmin) + for (B = Bmax; B >= Bmin; B--) + for (R = Rmin; R <= Rmax; R++) { + histp = histogram + R * MR + Gmin * MG + B; + for (G = Gmin; G <= Gmax; G++, histp += MG) + if (*histp != 0) { + boxp->Bmax = Bmax = B; + goto have_Bmax; + } + } +have_Bmax: + + /* Update box volume. + * We use 2-norm rather than real volume here; this biases the method + * against making long narrow boxes, and it has the side benefit that + * a box is splittable iff norm > 0. + * Since the differences are expressed in histogram-cell units, + * we have to shift back to JSAMPLE units to get consistent distances; + * after which, we scale according to the selected distance scale factors. + */ + dist0 = Rmax - Rmin; + dist1 = Gmax - Gmin; + dist2 = Bmax - Bmin; + boxp->volume = dist0 * dist0 + dist1 * dist1 + dist2 * dist2; + + /* Now scan remaining volume of box and compute population */ + ccount = 0; + for (R = Rmin; R <= Rmax; R++) + for (G = Gmin; G <= Gmax; G++) { + histp = histogram + R * MR + G * MG + Bmin; + for (B = Bmin; B <= Bmax; B++, histp++) + if (*histp != 0) { + ccount++; + } + } + + boxp->colorcount = ccount; +} + +static int median_cut_rgb(Histogram histogram, boxptr boxlist, int numboxes, int desired_colors) +/* Repeatedly select and split the largest box until we have enough boxes */ +{ + int n, lb; + int R, G, B, cmax; + boxptr b1, b2; + + while (numboxes < desired_colors) { + /* Select box to split. + * Current algorithm: by population for first half, then by volume. + */ + b1 = find_biggest_volume(boxlist, numboxes); + + if (b1 == 0) /* no splittable boxes left! */ + break; + b2 = boxlist + numboxes; /* where new box will go */ + /* Copy the color bounds to the new box. */ + b2->Rmax = b1->Rmax; + b2->Gmax = b1->Gmax; + b2->Bmax = b1->Bmax; + b2->Rmin = b1->Rmin; + b2->Gmin = b1->Gmin; + b2->Bmin = b1->Bmin; + /* Choose which axis to split the box on. + * Current algorithm: longest scaled axis. + * See notes in update_box about scaling distances. + */ + R = b1->Rmax - b1->Rmin; + G = b1->Gmax - b1->Gmin; + B = b1->Bmax - b1->Bmin; + /* We want to break any ties in favor of green, then red, blue last. + */ + cmax = G; + n = 1; + if (R > cmax) { + cmax = R; + n = 0; + } + if (B > cmax) { + n = 2; + } + /* Choose split point along selected axis, and update box bounds. + * Current algorithm: split at halfway point. + * (Since the box has been shrunk to minimum volume, + * any split will produce two nonempty subboxes.) + * Note that lb value is max for lower box, so must be < old max. + */ + switch (n) { + case 0: + lb = (b1->Rmax + b1->Rmin) / 2; + b1->Rmax = lb; + b2->Rmin = lb + 1; + break; + case 1: + lb = (b1->Gmax + b1->Gmin) / 2; + b1->Gmax = lb; + b2->Gmin = lb + 1; + break; + case 2: + lb = (b1->Bmax + b1->Bmin) / 2; + b1->Bmax = lb; + b2->Bmin = lb + 1; + break; + } + /* Update stats for boxes */ + update_box_rgb(histogram, b1); + update_box_rgb(histogram, b2); + numboxes++; + } + return numboxes; +} + +static void compute_color_rgb(QuantizeObj * quantobj, Histogram histogram, boxptr boxp, int icolor) +/* Compute representative color for a box, put it in colormap[icolor] */ +{ + /* Current algorithm: mean weighted by pixels (not colors) */ + /* Note it is important to get the rounding correct! */ + ColorFreq *histp; + int R, G, B; + int Rmin, Rmax; + int Gmin, Gmax; + int Bmin, Bmax; + unsigned long count; + unsigned long total = 0; + unsigned long Rtotal = 0; + unsigned long Gtotal = 0; + unsigned long Btotal = 0; + + Rmin = boxp->Rmin; + Rmax = boxp->Rmax; + Gmin = boxp->Gmin; + Gmax = boxp->Gmax; + Bmin = boxp->Bmin; + Bmax = boxp->Bmax; + + for (R = Rmin; R <= Rmax; R++) + for (G = Gmin; G <= Gmax; G++) { + histp = histogram + R * MR + G * MG + Bmin; + for (B = Bmin; B <= Bmax; B++) { + if ((count = *histp++) != 0) { + total += count; + Rtotal += ((R << R_SHIFT) + ((1 << R_SHIFT) >> 1)) * count; + Gtotal += ((G << G_SHIFT) + ((1 << G_SHIFT) >> 1)) * count; + Btotal += ((B << B_SHIFT) + ((1 << B_SHIFT) >> 1)) * count; + } + } + } + + quantobj->cmap[icolor].r = (unsigned char)((Rtotal + (total >> 1)) / total); + quantobj->cmap[icolor].g = (unsigned char)((Gtotal + (total >> 1)) / total); + quantobj->cmap[icolor].b = (unsigned char)((Btotal + (total >> 1)) / total); + quantobj->freq[icolor] = total; +} + +static void select_colors_rgb(QuantizeObj * quantobj, Histogram histogram) +/* Master routine for color selection */ +{ + boxptr boxlist; + int numboxes; + int desired = quantobj->desired_number_of_colors; + int i; + + /* Allocate workspace for box list */ + XMALLOC(boxlist, desired * sizeof(box)); + + /* Initialize one box containing whole space */ + numboxes = 1; + boxlist[0].Rmin = 0; + boxlist[0].Rmax = (1 << PRECISION_R) - 1; + boxlist[0].Gmin = 0; + boxlist[0].Gmax = (1 << PRECISION_G) - 1; + boxlist[0].Bmin = 0; + boxlist[0].Bmax = (1 << PRECISION_B) - 1; + /* Shrink it to actually-used volume and set its statistics */ + update_box_rgb(histogram, boxlist); + /* Perform median-cut to produce final box list */ + numboxes = median_cut_rgb(histogram, boxlist, numboxes, desired); + quantobj->actual_number_of_colors = numboxes; + /* Compute the representative color for each box, fill colormap */ + for (i = 0; i < numboxes; i++) + compute_color_rgb(quantobj, histogram, boxlist + i, i); + free(boxlist); +} + +/* + * These routines are concerned with the time-critical task of mapping input + * colors to the nearest color in the selected colormap. + * + * We re-use the histogram space as an "inverse color map", essentially a + * cache for the results of nearest-color searches. All colors within a + * histogram cell will be mapped to the same colormap entry, namely the one + * closest to the cell's center. This may not be quite the closest entry to + * the actual input color, but it's almost as good. A zero in the cache + * indicates we haven't found the nearest color for that cell yet; the array + * is cleared to zeroes before starting the mapping pass. When we find the + * nearest color for a cell, its colormap index plus one is recorded in the + * cache for future use. The pass2 scanning routines call fill_inverse_cmap + * when they need to use an unfilled entry in the cache. + * + * Our method of efficiently finding nearest colors is based on the "locally + * sorted search" idea described by Heckbert and on the incremental distance + * calculation described by Spencer W. Thomas in chapter III.1 of Graphics + * Gems II (James Arvo, ed. Academic Press, 1991). Thomas points out that + * the distances from a given colormap entry to each cell of the histogram can + * be computed quickly using an incremental method: the differences between + * distances to adjacent cells themselves differ by a constant. This allows a + * fairly fast implementation of the "brute force" approach of computing the + * distance from every colormap entry to every histogram cell. Unfortunately, + * it needs a work array to hold the best-distance-so-far for each histogram + * cell (because the inner loop has to be over cells, not colormap entries). + * The work array elements have to be ints, so the work array would need + * 256Kb at our recommended precision. This is not feasible in DOS machines. + +[ 256*1024/4 = 65,536 ] + + * To get around these problems, we apply Thomas' method to compute the + * nearest colors for only the cells within a small subbox of the histogram. + * The work array need be only as big as the subbox, so the memory usage + * problem is solved. Furthermore, we need not fill subboxes that are never + * referenced in pass2; many images use only part of the color gamut, so a + * fair amount of work is saved. An additional advantage of this + * approach is that we can apply Heckbert's locality criterion to quickly + * eliminate colormap entries that are far away from the subbox; typically + * three-fourths of the colormap entries are rejected by Heckbert's criterion, + * and we need not compute their distances to individual cells in the subbox. + * The speed of this approach is heavily influenced by the subbox size: too + * small means too much overhead, too big loses because Heckbert's criterion + * can't eliminate as many colormap entries. Empirically the best subbox + * size seems to be about 1/512th of the histogram (1/8th in each direction). + * + * Thomas' article also describes a refined method which is asymptotically + * faster than the brute-force method, but it is also far more complex and + * cannot efficiently be applied to small subboxes. It is therefore not + * useful for programs intended to be portable to DOS machines. On machines + * with plenty of memory, filling the whole histogram in one shot with Thomas' + * refined method might be faster than the present code --- but then again, + * it might not be any faster, and it's certainly more complicated. + */ + +/* log2(histogram cells in update box) for each axis; this can be adjusted */ +#define BOX_R_LOG (PRECISION_R-3) +#define BOX_G_LOG (PRECISION_G-3) +#define BOX_B_LOG (PRECISION_B-3) + +#define BOX_R_ELEMS (1<<BOX_R_LOG) /* # of hist cells in update box */ +#define BOX_G_ELEMS (1<<BOX_G_LOG) +#define BOX_B_ELEMS (1<<BOX_B_LOG) + +#define BOX_R_SHIFT (R_SHIFT + BOX_R_LOG) +#define BOX_G_SHIFT (G_SHIFT + BOX_G_LOG) +#define BOX_B_SHIFT (B_SHIFT + BOX_B_LOG) + +/* + * The next three routines implement inverse colormap filling. They could + * all be folded into one big routine, but splitting them up this way saves + * some stack space (the mindist[] and bestdist[] arrays need not coexist) + * and may allow some compilers to produce better code by registerizing more + * inner-loop variables. + */ + +static int find_nearby_colors(QuantizeObj * quantobj, int minR, int minG, int minB, int *colorlist) +/* Locate the colormap entries close enough to an update box to be candidates + * for the nearest entry to some cell(s) in the update box. The update box + * is specified by the center coordinates of its first cell. The number of + * candidate colormap entries is returned, and their colormap indexes are + * placed in colorlist[]. + * This routine uses Heckbert's "locally sorted search" criterion to select + * the colors that need further consideration. + */ +{ + int numcolors = quantobj->actual_number_of_colors; + int maxR, maxG, maxB; + int centerR, centerG, centerB; + int i, x, ncolors; + int minmaxdist, min_dist = 0, max_dist, tdist; + int mindist[MAXNUMCOLORS]; /* min distance to colormap entry i */ + + /* Compute TRUE coordinates of update box's upper corner and center. + * Actually we compute the coordinates of the center of the upper-corner + * histogram cell, which are the upper bounds of the volume we care about. + * Note that since ">>" rounds down, the "center" values may be closer to + * min than to max; hence comparisons to them must be "<=", not "<". + */ + maxR = minR + ((1 << BOX_R_SHIFT) - (1 << R_SHIFT)); + centerR = (minR + maxR) >> 1; + maxG = minG + ((1 << BOX_G_SHIFT) - (1 << G_SHIFT)); + centerG = (minG + maxG) >> 1; + maxB = minB + ((1 << BOX_B_SHIFT) - (1 << B_SHIFT)); + centerB = (minB + maxB) >> 1; + + /* For each color in colormap, find: + * 1. its minimum squared-distance to any point in the update box + * (zero if color is within update box); + * 2. its maximum squared-distance to any point in the update box. + * Both of these can be found by considering only the corners of the box. + * We save the minimum distance for each color in mindist[]; + * only the smallest maximum distance is of interest. + */ + minmaxdist = 0x7FFFFFFFL; + + for (i = 0; i < numcolors; i++) { + /* We compute the squared-R-distance term, then add in the other two. */ + x = quantobj->cmap[i].r; + if (x < minR) { + tdist = (x - minR) R_SCALE; + min_dist = tdist * tdist; + tdist = (x - maxR) R_SCALE; + max_dist = tdist * tdist; + } else if (x > maxR) { + tdist = (x - maxR) R_SCALE; + min_dist = tdist * tdist; + tdist = (x - minR) R_SCALE; + max_dist = tdist * tdist; + } else { + /* within cell range so no contribution to min_dist */ + min_dist = 0; + if (x <= centerR) { + tdist = (x - maxR) R_SCALE; + max_dist = tdist * tdist; + } else { + tdist = (x - minR) R_SCALE; + max_dist = tdist * tdist; + } + } + + x = quantobj->cmap[i].g; + if (x < minG) { + tdist = (x - minG) G_SCALE; + min_dist += tdist * tdist; + tdist = (x - maxG) G_SCALE; + max_dist += tdist * tdist; + } else if (x > maxG) { + tdist = (x - maxG) G_SCALE; + min_dist += tdist * tdist; + tdist = (x - minG) G_SCALE; + max_dist += tdist * tdist; + } else { + /* within cell range so no contribution to min_dist */ + if (x <= centerG) { + tdist = (x - maxG) G_SCALE; + max_dist += tdist * tdist; + } else { + tdist = (x - minG) G_SCALE; + max_dist += tdist * tdist; + } + } + + x = quantobj->cmap[i].b; + if (x < minB) { + tdist = (x - minB) B_SCALE; + min_dist += tdist * tdist; + tdist = (x - maxB) B_SCALE; + max_dist += tdist * tdist; + } else if (x > maxB) { + tdist = (x - maxB) B_SCALE; + min_dist += tdist * tdist; + tdist = (x - minB) B_SCALE; + max_dist += tdist * tdist; + } else { + /* within cell range so no contribution to min_dist */ + if (x <= centerB) { + tdist = (x - maxB) B_SCALE; + max_dist += tdist * tdist; + } else { + tdist = (x - minB) B_SCALE; + max_dist += tdist * tdist; + } + } + + mindist[i] = min_dist; /* save away the results */ + if (max_dist < minmaxdist) + minmaxdist = max_dist; + } + + /* Now we know that no cell in the update box is more than minmaxdist + * away from some colormap entry. Therefore, only colors that are + * within minmaxdist of some part of the box need be considered. + */ + ncolors = 0; + for (i = 0; i < numcolors; i++) { + if (mindist[i] <= minmaxdist) + colorlist[ncolors++] = i; + } + return ncolors; +} + +static void find_best_colors(QuantizeObj * quantobj, int minR, int minG, int minB, int numcolors, int *colorlist, int *bestcolor) +/* Find the closest colormap entry for each cell in the update box, + given the list of candidate colors prepared by find_nearby_colors. + Return the indexes of the closest entries in the bestcolor[] array. + This routine uses Thomas' incremental distance calculation method to + find the distance from a colormap entry to successive cells in the box. + */ +{ + int iR, iG, iB; + int i, icolor; + int *bptr; /* pointer into bestdist[] array */ + int *cptr; /* pointer into bestcolor[] array */ + int dist0, dist1; /* initial distance values */ + int dist2; /* current distance in inner loop */ + int xx0, xx1; /* distance increments */ + int xx2; + int inR, inG, inB; /* initial values for increments */ + + /* This array holds the distance to the nearest-so-far color for each cell */ + int bestdist[BOX_R_ELEMS * BOX_G_ELEMS * BOX_B_ELEMS]; + + /* Initialize best-distance for each cell of the update box */ + bptr = bestdist; + for (i = BOX_R_ELEMS * BOX_G_ELEMS * BOX_B_ELEMS - 1; i >= 0; i--) + *bptr++ = 0x7FFFFFFFL; + + /* For each color selected by find_nearby_colors, + * compute its distance to the center of each cell in the box. + * If that's less than best-so-far, update best distance and color number. + */ + + /* Nominal steps between cell centers ("x" in Thomas article) */ +#define STEP_R ((1 << R_SHIFT) R_SCALE) +#define STEP_G ((1 << G_SHIFT) G_SCALE) +#define STEP_B ((1 << B_SHIFT) B_SCALE) + + for (i = 0; i < numcolors; i++) { + icolor = colorlist[i]; + /* Compute (square of) distance from minR/G/B to this color */ + inR = (minR - quantobj->cmap[icolor].r) R_SCALE; + dist0 = inR * inR; + inG = (minG - quantobj->cmap[icolor].g) G_SCALE; + dist0 += inG * inG; + inB = (minB - quantobj->cmap[icolor].b) B_SCALE; + dist0 += inB * inB; + /* Form the initial difference increments */ + inR = inR * (2 * STEP_R) + STEP_R * STEP_R; + inG = inG * (2 * STEP_G) + STEP_G * STEP_G; + inB = inB * (2 * STEP_B) + STEP_B * STEP_B; + /* Now loop over all cells in box, updating distance per Thomas method */ + bptr = bestdist; + cptr = bestcolor; + xx0 = inR; + for (iR = BOX_R_ELEMS - 1; iR >= 0; iR--) { + dist1 = dist0; + xx1 = inG; + for (iG = BOX_G_ELEMS - 1; iG >= 0; iG--) { + dist2 = dist1; + xx2 = inB; + for (iB = BOX_B_ELEMS - 1; iB >= 0; iB--) { + if (dist2 < *bptr) { + *bptr = dist2; + *cptr = icolor; + } + dist2 += xx2; + xx2 += 2 * STEP_B * STEP_B; + bptr++; + cptr++; + } + dist1 += xx1; + xx1 += 2 * STEP_G * STEP_G; + } + dist0 += xx0; + xx0 += 2 * STEP_R * STEP_R; + } + } +} + +static void fill_inverse_cmap_rgb(QuantizeObj * quantobj, Histogram histogram, int R, int G, int B) +/* Fill the inverse-colormap entries in the update box that contains + histogram cell R/G/B. (Only that one cell MUST be filled, but + we can fill as many others as we wish.) */ +{ + int minR, minG, minB; /* lower left corner of update box */ + int iR, iG, iB; + int *cptr; /* pointer into bestcolor[] array */ + ColorFreq *cachep; /* pointer into main cache array */ + /* This array lists the candidate colormap indexes. */ + int colorlist[MAXNUMCOLORS]; + int numcolors; /* number of candidate colors */ + /* This array holds the actually closest colormap index for each cell. */ + int bestcolor[BOX_R_ELEMS * BOX_G_ELEMS * BOX_B_ELEMS]; + + /* Convert cell coordinates to update box ID */ + R >>= BOX_R_LOG; + G >>= BOX_G_LOG; + B >>= BOX_B_LOG; + + /* Compute TRUE coordinates of update box's origin corner. + * Actually we compute the coordinates of the center of the corner + * histogram cell, which are the lower bounds of the volume we care about. + */ + minR = (R << BOX_R_SHIFT) + ((1 << R_SHIFT) >> 1); + minG = (G << BOX_G_SHIFT) + ((1 << G_SHIFT) >> 1); + minB = (B << BOX_B_SHIFT) + ((1 << B_SHIFT) >> 1); + + /* Determine which colormap entries are close enough to be candidates + * for the nearest entry to some cell in the update box. + */ + numcolors = find_nearby_colors(quantobj, minR, minG, minB, colorlist); + + /* Determine the actually nearest colors. */ + find_best_colors(quantobj, minR, minG, minB, numcolors, colorlist, bestcolor); + + /* Save the best color numbers (plus 1) in the main cache array */ + R <<= BOX_R_LOG; /* convert ID back to base cell indexes */ + G <<= BOX_G_LOG; + B <<= BOX_B_LOG; + cptr = bestcolor; + for (iR = 0; iR < BOX_R_ELEMS; iR++) { + for (iG = 0; iG < BOX_G_ELEMS; iG++) { + cachep = &histogram[(R + iR) * MR + (G + iG) * MG + B]; + for (iB = 0; iB < BOX_B_ELEMS; iB++) { + *cachep++ = (*cptr++) + 1; + } + } + } +} + +/* This is pass 1 */ +static void median_cut_pass1_rgb(QuantizeObj * quantobj, at_bitmap * image, const at_color * ignoreColor) +{ + generate_histogram_rgb(quantobj->histogram, image, ignoreColor); + select_colors_rgb(quantobj, quantobj->histogram); +} + +/* Map some rows of pixels to the output colormapped representation. */ +static void median_cut_pass2_rgb(QuantizeObj * quantobj, at_bitmap * image, const at_color * bgColor) + /* This version performs no dithering */ +{ + Histogram histogram = quantobj->histogram; + ColorFreq *cachep; + int R, G, B; + int origR, origG, origB; + int row, col; + int spp = AT_BITMAP_PLANES(image); + int width = AT_BITMAP_WIDTH(image); + int height = AT_BITMAP_HEIGHT(image); + unsigned char *src, *dest; + at_color bg_color = { 0xff, 0xff, 0xff }; + + zero_histogram_rgb(histogram); + + if (bgColor) { + /* Find the nearest colormap entry for the background color. */ + R = bgColor->r >> R_SHIFT; + G = bgColor->g >> G_SHIFT; + B = bgColor->b >> B_SHIFT; + cachep = &histogram[R * MR + G * MG + B]; + if (*cachep == 0) + fill_inverse_cmap_rgb(quantobj, histogram, R, G, B); + bg_color = quantobj->cmap[*cachep - 1]; + } + + src = dest = image->bitmap; + if (spp == 3) { + for (row = 0; row < height; row++) { + for (col = 0; col < width; col++) { + /* get pixel value and index into the cache */ + origR = (*src++); + origG = (*src++); + origB = (*src++); + + /* + if (origR > 253 && origG > 253 && origB > 253) + { + (*dest++) = 255; (*dest++) = 255; (*dest++) = 255; + continue; + } + */ + + /* get pixel value and index into the cache */ + R = origR >> R_SHIFT; + G = origG >> G_SHIFT; + B = origB >> B_SHIFT; + cachep = &histogram[R * MR + G * MG + B]; + /* If we have not seen this color before, find nearest + colormap entry and update the cache */ + if (*cachep == 0) { + fill_inverse_cmap_rgb(quantobj, histogram, R, G, B); + } + /* Now emit the colormap index for this cell */ + dest[0] = quantobj->cmap[*cachep - 1].r; + dest[1] = quantobj->cmap[*cachep - 1].g; + dest[2] = quantobj->cmap[*cachep - 1].b; + + /* If the colormap entry for this pixel is the same as the + background's colormap entry, set the pixel to the + background color. */ + if (bgColor && (dest[0] == bg_color.r && dest[1] == bg_color.g && dest[2] == bg_color.b)) { + dest[0] = bgColor->r; + dest[1] = bgColor->g; + dest[2] = bgColor->b; + } + dest += 3; + } + } + } else if (spp == 1) { + long idx = width * height; + while (--idx >= 0) { + origR = src[idx]; + R = origR >> R_SHIFT; + G = origR >> G_SHIFT; + B = origR >> B_SHIFT; + cachep = &histogram[R * MR + G * MG + B]; + if (*cachep == 0) + fill_inverse_cmap_rgb(quantobj, histogram, R, G, B); + + dest[idx] = quantobj->cmap[*cachep - 1].r; + + /* If the colormap entry for this pixel is the same as the + background's colormap entry, set the pixel to the + background color. */ + if (bgColor && dest[idx] == bg_color.r) + dest[idx] = bgColor->r; + } + } +} + +static QuantizeObj *initialize_median_cut(int num_colors) +{ + QuantizeObj *quantobj; + + /* Initialize the data structures */ + XMALLOC(quantobj, sizeof(QuantizeObj)); + + XMALLOC(quantobj->histogram, sizeof(ColorFreq) * HIST_R_ELEMS * HIST_G_ELEMS * HIST_B_ELEMS); + quantobj->desired_number_of_colors = num_colors; + + return quantobj; +} + +void quantize(at_bitmap * image, long ncolors, const at_color * bgColor, QuantizeObj ** iQuant, at_exception_type * exp) +{ + QuantizeObj *quantobj; + unsigned int spp = AT_BITMAP_PLANES(image); + + if (spp != 3 && spp != 1) { + LOG("quantize: %u-plane images are not supported", spp); + at_exception_fatal(exp, "quantize: wrong plane images are passed"); + return; + } + + /* If a pointer was sent in, let's use it. */ + if (iQuant) { + if (*iQuant == NULL) { + quantobj = initialize_median_cut(ncolors); + median_cut_pass1_rgb(quantobj, image, bgColor); + *iQuant = quantobj; + } else + quantobj = *iQuant; + } else { + quantobj = initialize_median_cut(ncolors); + median_cut_pass1_rgb(quantobj, image, NULL); + } + + median_cut_pass2_rgb(quantobj, image, bgColor); + + if (iQuant == NULL) + quantize_object_free(quantobj); +} + +void quantize_object_free(QuantizeObj * quantobj) +{ + free(quantobj->histogram); + free(quantobj); +} diff --git a/src/3rdparty/autotrace/module.c b/src/3rdparty/autotrace/module.c new file mode 100644 index 0000000..9cb3693 --- /dev/null +++ b/src/3rdparty/autotrace/module.c @@ -0,0 +1,72 @@ +/* module.c --- Autotrace plugin module management subsystem + + Copyright (C) 2003 Martin Weber + Copyright (C) 2003 Masatake YAMATO + + The author can be contacted at <martweb@gmx.net> + + 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 of the License, 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. */ + +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif /* Def: HAVE_CONFIG_H */ +#include "intl.h" + +#include "private.h" + +#include "input.h" + +#ifdef HAVE_LIBPNG +#endif /* HAVE_LIBPNG */ +#if HAVE_MAGICK +#else +int install_input_magick_readers(void) +{ + return 0; +} +#endif /* HAVE_MAGICK */ + +#if HAVE_LIBPSTOEDIT +#else +int install_output_pstoedit_writers(void) +{ + return 0; +} +#endif /* HAVE_LIBPSTOEDIT */ + +static int install_input_readers(void); +static int install_output_writers(void); + +int at_module_init(void) +{ + int r, w; + /* TODO: Loading every thing in dynamic. + For a while, these are staticly added. */ + r = install_input_readers(); + w = install_output_writers(); + return (int)(r << 2 | w); +} + +static int install_input_readers(void) +{ + return 0; +#ifdef HAVE_LIBPNG +#endif +} + +static int install_output_writers(void) +{ + return 0; +} diff --git a/src/3rdparty/autotrace/output.c b/src/3rdparty/autotrace/output.c new file mode 100644 index 0000000..ae44cde --- /dev/null +++ b/src/3rdparty/autotrace/output.c @@ -0,0 +1,239 @@ +/* output.c: interface for output handlers + + Copyright (C) 1999, 2000, 2001 Bernhard Herzog. + Copyright (C) 2003 Masatake YAMATO + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public License + as published by the Free Software Foundation; either version 2.1 of + the License, or (at your option) any later version. + + This library 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 + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with this library; if not, write to the Free Software + Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 + USA. */ + +/* TODO: Unify output codes and input codes. */ + +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif /* Def: HAVE_CONFIG_H */ + +#include "autotrace.h" +#include "private.h" +#include "output.h" +#include "xstd.h" +#include "filename.h" +#include <string.h> +#include <glib.h> + +typedef struct _at_output_format_entry at_output_format_entry; +struct _at_output_format_entry { + at_spline_writer writer; + const char *descr; + GDestroyNotify user_data_destroy_func; +}; + +static GHashTable *at_output_formats = NULL; +static at_output_format_entry *at_output_format_new(const char *descr, at_output_func writer, gpointer user_data, GDestroyNotify user_data_destroy_func); +static void at_output_format_free(at_output_format_entry * entry); + +/* + * Helper functions + */ +static void output_list_set(gpointer key, gpointer value, gpointer user_data); +static void output_list_strlen(gpointer key, gpointer value, gpointer user_data); +static void output_list_strcat(gpointer key, gpointer value, gpointer user_data); + +int at_output_init(void) +{ + if (at_output_formats) + return 1; + + at_output_formats = g_hash_table_new_full(g_str_hash, (GEqualFunc) g_str_equal, g_free, (GDestroyNotify) at_output_format_free); + if (!at_output_formats) + return 0; + return 1; +} + +static at_output_format_entry *at_output_format_new(const gchar * descr, at_output_func writer, gpointer user_data, GDestroyNotify user_data_destroy_func) +{ + at_output_format_entry *entry; + entry = g_malloc(sizeof(at_output_format_entry)); + if (entry) { + entry->writer.func = writer; + entry->writer.data = user_data; + entry->descr = g_strdup(descr); + entry->user_data_destroy_func = user_data_destroy_func; + } + return entry; +} + +static void at_output_format_free(at_output_format_entry * entry) +{ + g_free((gpointer) entry->descr); + if (entry->user_data_destroy_func) + entry->user_data_destroy_func(entry->writer.data); + g_free(entry); + +} + +int at_output_add_handler(const gchar * suffix, const gchar * description, at_output_func writer) +{ + return at_output_add_handler_full(suffix, description, writer, 0, NULL, NULL); +} + +int at_output_add_handler_full(const gchar * suffix, const gchar * description, at_output_func writer, gboolean override, gpointer user_data, GDestroyNotify user_data_destroy_func) +{ + gchar *gsuffix; + const gchar *gdescription; + at_output_format_entry *old_entry; + at_output_format_entry *new_entry; + + g_return_val_if_fail(suffix, 0); + g_return_val_if_fail(description, 0); + g_return_val_if_fail(writer, 0); + + gsuffix = g_strdup((gchar *) suffix); + g_return_val_if_fail(gsuffix, 0); + gsuffix = g_ascii_strdown(gsuffix, strlen(gsuffix)); + + gdescription = (const gchar *)description; + + old_entry = g_hash_table_lookup(at_output_formats, gsuffix); + if (old_entry && !override) { + g_free(gsuffix); + return 1; + } + + new_entry = at_output_format_new(gdescription, writer, user_data, user_data_destroy_func); + g_return_val_if_fail(new_entry, 0); + + g_hash_table_replace(at_output_formats, gsuffix, new_entry); + return 1; +} + +at_spline_writer *at_output_get_handler(gchar * filename) +{ + char *ext = find_suffix(filename); + if (ext == NULL) + ext = ""; + + return at_output_get_handler_by_suffix(ext); +} + +at_spline_writer *at_output_get_handler_by_suffix(const gchar * suffix) +{ + at_output_format_entry *format; + gchar *gsuffix; + + if (!suffix || suffix[0] == '\0') + return NULL; + + gsuffix = g_strdup(suffix); + g_return_val_if_fail(gsuffix, NULL); + gsuffix = g_ascii_strdown(gsuffix, strlen(gsuffix)); + format = g_hash_table_lookup(at_output_formats, gsuffix); + g_free(gsuffix); + + if (format) + return &(format->writer); + else + return NULL; +} + +const char **at_output_list_new(void) +{ + char **list, **tmp; + gint format_count; + gint list_count; + + format_count = g_hash_table_size(at_output_formats); + list_count = 2 * format_count; + list = g_new(gchar *, list_count + 1); + list[list_count] = NULL; + + tmp = list; + g_hash_table_foreach(at_output_formats, output_list_set, &tmp); + return (const char **)list; +} + +void at_output_list_free(const char **list) +{ + free((char **)list); +} + +char *at_output_shortlist(void) +{ + gint length = 0, count; + char *list, *tmp; + g_hash_table_foreach(at_output_formats, output_list_strlen, &length); + count = g_hash_table_size(at_output_formats); + + /* 2 for ", " */ + length += (2 * count); + list = g_malloc(length + 1); + list[0] = '\0'; + + tmp = list; + g_hash_table_foreach(at_output_formats, output_list_strcat, &tmp); + + /* remove final ", " */ + g_return_val_if_fail(list[length - 2] == ',', NULL); + list[length - 2] = '\0'; + return list; +} + +static void output_list_set(gpointer key, gpointer value, gpointer user_data) +{ + at_output_format_entry *format = value; + const char ***list_ptr = user_data; + const char **list = *list_ptr; + list[0] = key; + list[1] = format->descr; + *list_ptr = &(list[2]); +} + +static void output_list_strlen(gpointer key, gpointer value, gpointer user_data) +{ + gint *length; + g_return_if_fail(key); + g_return_if_fail(user_data); + + length = user_data; + *length += strlen(key); +} + +static void output_list_strcat(gpointer key, gpointer value, gpointer user_data) +{ + gchar **list_ptr; + gchar *list; + list_ptr = user_data; + list = *list_ptr; + strcat(list, key); + strcat(list, ", "); + + /* 2 for ", " */ + *list_ptr = list + strlen(key) + 2; +} + +void at_spline_list_foreach(at_spline_list_type * list, AtSplineListForeachFunc func, gpointer user_data) +{ + unsigned i; + for (i = 0; i < AT_SPLINE_LIST_LENGTH(list); i++) { + func(list, AT_SPLINE_LIST_ELT(list, i), i, user_data); + } +} + +void at_spline_list_array_foreach(at_spline_list_array_type * list_array, AtSplineListArrayForeachFunc func, gpointer user_data) +{ + unsigned i; + for (i = 0; i < AT_SPLINE_LIST_ARRAY_LENGTH(list_array); i++) { + func(list_array, AT_SPLINE_LIST_ARRAY_ELT(list_array, i), i, user_data); + } +} diff --git a/src/3rdparty/autotrace/output.h b/src/3rdparty/autotrace/output.h new file mode 100644 index 0000000..de88abc --- /dev/null +++ b/src/3rdparty/autotrace/output.h @@ -0,0 +1,89 @@ +/* output.h: interface for output handlers + + Copyright (C) 1999, 2000, 2001, 2002 Bernhard Herzog. + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public License + as published by the Free Software Foundation; either version 2.1 of + the License, or (at your option) any later version. + + This library 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 + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with this library; if not, write to the Free Software + Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 + USA. */ + +#ifndef OUTPUT_H +#define OUTPUT_H +#include <stdio.h> +#include "autotrace.h" +#include "types.h" +#include "exception.h" +#include <glib.h> + +#ifdef __cplusplus +extern "C" { +#endif /* __cplusplus */ + + typedef + int (*at_output_func) (FILE *, gchar * name, int llx, int lly, int urx, int ury, at_output_opts_type * opts, at_splines_type shape, at_msg_func msg_func, gpointer msg_data, gpointer user_data); + + extern int at_output_add_handler(const gchar * suffix, const gchar * description, at_output_func writer); + + extern int at_output_add_handler_full(const gchar * suffix, const gchar * description, at_output_func writer, gboolean override, gpointer user_data, GDestroyNotify user_data_destroy_func); + +/* Data struct hierarchy: + spline_list_array (splines) + -> spline_list... + --> spline */ + +/* Accessors to the Data member */ +#define AT_SPLINE_START_POINT_VALUE(spl) ((spl).v[0]) +#define AT_SPLINE_CONTROL1_VALUE(spl) ((spl).v[1]) +#define AT_SPLINE_CONTROL2_VALUE(spl) ((spl).v[2]) +#define AT_SPLINE_END_POINT_VALUE(spl) ((spl).v[3]) +#define AT_SPLINE_DEGREE_VALUE(spl) ((spl).degree) + +#define AT_SPLINE_START_POINT(spl) (&AT_SPLINE_START_POINT_VALUE(*(spl))) +#define AT_SPLINE_CONTROL1(spl) (&AT_SPLINE_CONTROL1_VALUE(*(spl))) +#define AT_SPLINE_CONTROL2(spl) (&AT_SPLINE_CONTROL2_VALUE(*(spl))) +#define AT_SPLINE_END_POINT(spl) (&AT_SPLINE_END_POINT_VALUE(*(spl))) +#define AT_SPLINE_DEGREE(spl) AT_SPLINE_DEGREE_VALUE(*(spl)) + +#define AT_SPLINE_LIST_LENGTH_VALUE(spll) ((spll).length) +#define AT_SPLINE_LIST_LENGTH(spll) AT_SPLINE_LIST_LENGTH_VALUE(*(spll)) +#define AT_SPLINE_LIST_DATA_VALUE(spll) ((spll).data) +#define AT_SPLINE_LIST_DATA(spll) AT_SPLINE_LIST_DATA_VALUE((*spll)) +#define AT_SPLINE_LIST_ELT_VALUE(spll,index) AT_SPLINE_LIST_DATA_VALUE(spll)[(index)] +#define AT_SPLINE_LIST_ELT(spll,index) (&(AT_SPLINE_LIST_ELT_VALUE((*spll), (index)))) +#define AT_SPLINE_LIST_COLOR_VALUE(spll) ((spll).color) +#define AT_SPLINE_LIST_COLOR(spll) (&(AT_SPLINE_LIST_COLOR_VALUE(*spll))) +#define AT_SPLINE_LIST_IS_OPENED_VALUE(spll) ((spll).open) +#define AT_SPLINE_LIST_IS_OPENED(spll) AT_SPLINE_LIST_IS_OPENED_VALUE(*(spll)) + +#define AT_SPLINE_LIST_ARRAY_LENGTH_VALUE AT_SPLINE_LIST_LENGTH_VALUE +#define AT_SPLINE_LIST_ARRAY_LENGTH AT_SPLINE_LIST_LENGTH +#define AT_SPLINE_LIST_ARRAY_ELT_VALUE AT_SPLINE_LIST_ELT_VALUE +#define AT_SPLINE_LIST_ARRAY_ELT AT_SPLINE_LIST_ELT + +#define AT_SPLINE_LIST_ARRAY_IS_CENTERLINE_VALUE(splla) ((splla).centerline) +#define AT_SPLINE_LIST_ARRAY_IS_CENTERLINE(splla) AT_SPLINE_LIST_ARRAY_IS_CENTERLINE_VALUE(*(splla)) + +/* + * Glib style traversing + */ + + typedef void (*AtSplineListForeachFunc) (at_spline_list_type * spline_list, at_spline_type * spline, int index, gpointer user_data); + typedef void (*AtSplineListArrayForeachFunc) (at_spline_list_array_type * spline_list_array, at_spline_list_type * spline_list, int index, gpointer user_data); + + void at_spline_list_foreach(at_spline_list_type *, AtSplineListForeachFunc func, gpointer user_data); + void at_spline_list_array_foreach(at_spline_list_array_type *, AtSplineListArrayForeachFunc func, gpointer user_data); + +#ifdef __cplusplus +} +#endif /* __cplusplus */ +#endif /* not OUTPUT_H */ diff --git a/src/3rdparty/autotrace/private.h b/src/3rdparty/autotrace/private.h new file mode 100644 index 0000000..acb6815 --- /dev/null +++ b/src/3rdparty/autotrace/private.h @@ -0,0 +1,43 @@ +/* private.h --- Autotrace library private decls + + Copyright (C) 2003 Martin Weber + Copyright (C) 2003 Masatake YAMATO + + The author can be contacted at <martweb@gmx.net> + + 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 of the License, 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. */ + +#ifndef PRIVATE_H +#define PRIVATE_H + +#include "autotrace.h" +#include "input.h" +#include "output.h" + +struct _at_bitmap_reader { + at_input_func func; + gpointer data; +}; + +struct _at_spline_writer { + at_output_func func; + gpointer data; +}; + +int at_input_init(void); +int at_output_init(void); +int at_param_init(void); +int at_module_init(void); +#endif /* Not def: PRIVATE_H */ diff --git a/src/3rdparty/autotrace/pxl-outline.c b/src/3rdparty/autotrace/pxl-outline.c new file mode 100644 index 0000000..6bc5a56 --- /dev/null +++ b/src/3rdparty/autotrace/pxl-outline.c @@ -0,0 +1,887 @@ +/* pxl-outline.c: find the outlines of a bitmap image; each outline is made up of one or more pixels; + and each pixel participates via one or more edges. */ + +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif /* Def: HAVE_CONFIG_H */ + +#include "logreport.h" +#include "types.h" +#include "bitmap.h" +#include "color.h" +#include "bitmap.h" +#include "xstd.h" +#include "pxl-outline.h" +#include <assert.h> + +/* We consider each pixel to consist of four edges, and we travel along + edges, instead of through pixel centers. This is necessary for those + unfortunate times when a single pixel is on both an inside and an + outside outline. + + The numbers chosen here are not arbitrary; the code that figures out + which edge to move to depends on particular values. See the + `TRY_PIXEL' macro in `edge.c'. To emphasize this, I've written in the + numbers we need for each edge value. */ + +typedef enum { + TOP = 1, LEFT = 2, BOTTOM = 3, RIGHT = 0, NO_EDGE = 4 +} edge_type; + +/* This choice is also not arbitrary: starting at the top edge makes the + code find outside outlines before inside ones, which is certainly + what we want. */ +#define START_EDGE top + +typedef enum { + NORTH = 0, NORTHWEST = 1, WEST = 2, SOUTHWEST = 3, SOUTH = 4, + SOUTHEAST = 5, EAST = 6, NORTHEAST = 7 +} direction_type; + +#define NUM_EDGES NO_EDGE + +#define COMPUTE_DELTA(axis, dir) \ + ((dir) % 2 != 0 \ + ? COMPUTE_##axis##_DELTA ((dir) - 1) \ + + COMPUTE_##axis##_DELTA (((dir) + 1) % 8) \ + : COMPUTE_##axis##_DELTA (dir) \ + ) + +#define COMPUTE_ROW_DELTA(dir) \ + ((dir) == NORTH ? -1 : (dir) == SOUTH ? +1 : 0) + +#define COMPUTE_COL_DELTA(dir) \ + ((dir) == WEST ? -1 : (dir) == EAST ? +1 : 0) + +static pixel_outline_type find_one_outline(at_bitmap *, edge_type, unsigned short, unsigned short, at_bitmap *, gboolean, gboolean, at_exception_type *); +static pixel_outline_type find_one_centerline(at_bitmap *, direction_type, unsigned short, unsigned short, at_bitmap *); +static void append_pixel_outline(pixel_outline_list_type *, pixel_outline_type); +static pixel_outline_type new_pixel_outline(void); +static void free_pixel_outline(pixel_outline_type *); +static void concat_pixel_outline(pixel_outline_type *, const pixel_outline_type *); +static void append_outline_pixel(pixel_outline_type *, at_coord); +static gboolean is_marked_edge(edge_type, unsigned short, unsigned short, at_bitmap *); +static gboolean is_outline_edge(edge_type, at_bitmap *, unsigned short, unsigned short, at_color, at_exception_type *); +static gboolean is_unmarked_outline_edge(unsigned short, unsigned short, edge_type, at_bitmap *, at_bitmap *, at_color, at_exception_type *); + +static void mark_edge(edge_type e, unsigned short, unsigned short, at_bitmap *); +/* static edge_type opposite_edge(edge_type); */ + +static gboolean is_marked_dir(unsigned short, unsigned short, direction_type, at_bitmap *); +static gboolean is_other_dir_marked(unsigned short, unsigned short, direction_type, at_bitmap *); +static void mark_dir(unsigned short, unsigned short, direction_type, at_bitmap *); +static gboolean next_unmarked_pixel(unsigned short *, unsigned short *, direction_type *, at_bitmap *, at_bitmap *); + +gboolean is_valid_dir(unsigned short, unsigned short, direction_type, at_bitmap *, at_bitmap *); + +static at_coord next_point(at_bitmap *, edge_type *, unsigned short *, unsigned short *, at_color, gboolean, at_bitmap *, at_exception_type *); +static unsigned num_neighbors(unsigned short, unsigned short, at_bitmap *); + +#define CHECK_FATAL() if (at_exception_got_fatal(exp)) goto cleanup; + +/* We go through a bitmap TOP to BOTTOM, LEFT to RIGHT, looking for each pixel with an unmarked edge + that we consider a starting point of an outline. */ + +pixel_outline_list_type find_outline_pixels(at_bitmap * bitmap, at_color * bg_color, at_progress_func notify_progress, gpointer progress_data, at_testcancel_func test_cancel, gpointer testcancel_data, at_exception_type * exp) +{ + pixel_outline_list_type outline_list; + unsigned short row, col; + at_bitmap *marked = at_bitmap_new(AT_BITMAP_WIDTH(bitmap), AT_BITMAP_HEIGHT(bitmap), 1); + unsigned int max_progress = AT_BITMAP_HEIGHT(bitmap) * AT_BITMAP_WIDTH(bitmap); + + O_LIST_LENGTH(outline_list) = 0; + outline_list.data = NULL; + + for (row = 0; row < AT_BITMAP_HEIGHT(bitmap); row++) { + for (col = 0; col < AT_BITMAP_WIDTH(bitmap); col++) { + edge_type edge; + at_color color; + gboolean is_background; + + if (notify_progress) + notify_progress((gfloat) (row * AT_BITMAP_WIDTH(bitmap) + col) / ((gfloat) max_progress * (gfloat) 3.0), progress_data); + + /* A valid edge can be TOP for an outside outline. + Outside outlines are traced counterclockwise */ + at_bitmap_get_color(bitmap, row, col, &color); + if (!(is_background = (gboolean) (bg_color && at_color_equal(&color, bg_color))) + && is_unmarked_outline_edge(row, col, edge = TOP, bitmap, marked, color, exp)) { + pixel_outline_type outline; + + CHECK_FATAL(); /* FREE(DONE) outline_list */ + + LOG("#%u: (counterclockwise)", O_LIST_LENGTH(outline_list)); + + outline = find_one_outline(bitmap, edge, row, col, marked, FALSE, FALSE, exp); + CHECK_FATAL(); /* FREE(DONE) outline_list */ + + O_CLOCKWISE(outline) = FALSE; + append_pixel_outline(&outline_list, outline); + + LOG(" [%u].\n", O_LENGTH(outline)); + } else + CHECK_FATAL(); /* FREE(DONE) outline_list */ + + /* A valid edge can be BOTTOM for an inside outline. + Inside outlines are traced clockwise */ + if (row != 0) { + at_bitmap_get_color(bitmap, row - 1, col, &color); + if (!(bg_color && at_color_equal(&color, bg_color)) + && is_unmarked_outline_edge(row - 1, col, edge = BOTTOM, bitmap, marked, color, exp)) { + pixel_outline_type outline; + + CHECK_FATAL(); /* FREE(DONE) outline_list */ + + /* This lines are for debugging only: */ + if (is_background) { + LOG("#%u: (clockwise)", O_LIST_LENGTH(outline_list)); + + outline = find_one_outline(bitmap, edge, row - 1, col, marked, TRUE, FALSE, exp); + CHECK_FATAL(); /* FREE(DONE) outline_list */ + + O_CLOCKWISE(outline) = TRUE; + append_pixel_outline(&outline_list, outline); + + LOG(" [%u].\n", O_LENGTH(outline)); + } else { + outline = find_one_outline(bitmap, edge, row - 1, col, marked, TRUE, TRUE, exp); + CHECK_FATAL(); /* FREE(DONE) outline_list */ + } + } else + CHECK_FATAL(); /* FREE(DONE) outline_list */ + } + if (test_cancel && test_cancel(testcancel_data)) { + free_pixel_outline_list(&outline_list); + goto cleanup; + } + } + } +cleanup: + at_bitmap_free(marked); + if (at_exception_got_fatal(exp)) + free_pixel_outline_list(&outline_list); + return outline_list; +} + +/* We calculate one single outline here. We pass the position of the starting pixel and the + starting edge. All edges we track along will be marked and the outline pixels are appended + to the coordinate list. */ + +static pixel_outline_type find_one_outline(at_bitmap * bitmap, edge_type original_edge, unsigned short original_row, unsigned short original_col, at_bitmap * marked, gboolean clockwise, gboolean ignore, at_exception_type * exp) +{ + pixel_outline_type outline; + unsigned short row = original_row, col = original_col; + edge_type edge = original_edge; + at_coord pos; + + pos.x = col + ((edge == RIGHT) || (edge == BOTTOM) ? 1 : 0); + pos.y = AT_BITMAP_HEIGHT(bitmap) - row - 1 + ((edge == TOP) || (edge == RIGHT) ? 1 : 0); + + if (!ignore) + outline = new_pixel_outline(); + at_bitmap_get_color(bitmap, row, col, &outline.color); + + do { + /* Put this edge into the output list */ + if (!ignore) { + LOG(" (%d,%d)", pos.x, pos.y); + append_outline_pixel(&outline, pos); + } + + mark_edge(edge, row, col, marked); + pos = next_point(bitmap, &edge, &row, &col, outline.color, clockwise, marked, exp); + CHECK_FATAL(); + } + while (edge != NO_EDGE); + +cleanup: + if (at_exception_got_fatal(exp)) + free_pixel_outline(&outline); + return outline; +} + +gboolean is_valid_dir(unsigned short row, unsigned short col, direction_type dir, at_bitmap * bitmap, at_bitmap * marked) +{ + + at_color c; + + if ((COMPUTE_DELTA(ROW, dir) + row < 0) || (COMPUTE_DELTA(COL, dir) + col < 0)) + return FALSE; // Must not call at_bitmap_get_color() with negative row or col. + + at_bitmap_get_color(bitmap, COMPUTE_DELTA(ROW, dir) + row, COMPUTE_DELTA(COL, dir) + col, &c); + return ((gboolean) (!is_marked_dir(row, col, dir, marked) + && COMPUTE_DELTA(ROW, dir) + row > 0 && COMPUTE_DELTA(COL, dir) + col > 0 && AT_BITMAP_VALID_PIXEL(bitmap, COMPUTE_DELTA(ROW, dir) + row, COMPUTE_DELTA(COL, dir) + col) + && at_bitmap_equal_color(bitmap, row, col, &c))); +} + +pixel_outline_list_type find_centerline_pixels(at_bitmap * bitmap, at_color bg_color, at_progress_func notify_progress, gpointer progress_data, at_testcancel_func test_cancel, gpointer testcancel_data, at_exception_type * exp) +{ + pixel_outline_list_type outline_list; + signed short row, col; + at_bitmap *marked = at_bitmap_new(AT_BITMAP_WIDTH(bitmap), AT_BITMAP_HEIGHT(bitmap), 1); + unsigned int max_progress = AT_BITMAP_HEIGHT(bitmap) * AT_BITMAP_WIDTH(bitmap); + + O_LIST_LENGTH(outline_list) = 0; + outline_list.data = NULL; + + for (row = 0; row < AT_BITMAP_HEIGHT(bitmap); row++) { + for (col = 0; col < AT_BITMAP_WIDTH(bitmap);) { + direction_type dir = EAST; + pixel_outline_type outline; + gboolean clockwise = FALSE; + + if (notify_progress) + notify_progress((gfloat) (row * AT_BITMAP_WIDTH(bitmap) + col) / ((gfloat) max_progress * (gfloat) 3.0), progress_data); + + if (at_bitmap_equal_color(bitmap, row, col, &bg_color)) { + col++; + continue; + } + + if (!is_valid_dir(row, col, dir, bitmap, marked) + || (!is_valid_dir(COMPUTE_DELTA(ROW, dir) + row, COMPUTE_DELTA(COL, dir) + col, dir, bitmap, marked) + && num_neighbors(row, col, bitmap) > 2) + || num_neighbors(row, col, bitmap) > 4 || num_neighbors(COMPUTE_DELTA(ROW, dir) + row, COMPUTE_DELTA(COL, dir) + col, bitmap) > 4 || (is_other_dir_marked(row, col, dir, marked) + && is_other_dir_marked(row + COMPUTE_DELTA(ROW, dir), col + COMPUTE_DELTA(COL, dir), dir, marked))) { + dir = SOUTHEAST; + if (!is_valid_dir(row, col, dir, bitmap, marked) + || (!is_valid_dir(COMPUTE_DELTA(ROW, dir) + row, COMPUTE_DELTA(COL, dir) + col, dir, bitmap, marked) + && num_neighbors(row, col, bitmap) > 2) + || num_neighbors(row, col, bitmap) > 4 || num_neighbors(COMPUTE_DELTA(ROW, dir) + row, COMPUTE_DELTA(COL, dir) + col, bitmap) > 4 || (is_other_dir_marked(row, col, dir, marked) + && is_other_dir_marked(row + COMPUTE_DELTA(ROW, dir), col + COMPUTE_DELTA(COL, dir), dir, marked))) { + dir = SOUTH; + if (!is_valid_dir(row, col, dir, bitmap, marked) + || (!is_valid_dir(COMPUTE_DELTA(ROW, dir) + row, COMPUTE_DELTA(COL, dir) + col, dir, bitmap, marked) + && num_neighbors(row, col, bitmap) > 2) + || num_neighbors(row, col, bitmap) > 4 || num_neighbors(COMPUTE_DELTA(ROW, dir) + row, COMPUTE_DELTA(COL, dir) + col, bitmap) > 4 || (is_other_dir_marked(row, col, dir, marked) + && is_other_dir_marked(row + COMPUTE_DELTA(ROW, dir), col + COMPUTE_DELTA(COL, dir), dir, marked))) { + dir = SOUTHWEST; + if (!is_valid_dir(row, col, dir, bitmap, marked) + || (!is_valid_dir(COMPUTE_DELTA(ROW, dir) + row, COMPUTE_DELTA(COL, dir) + col, dir, bitmap, marked) + && num_neighbors(row, col, bitmap) > 2) + || num_neighbors(row, col, bitmap) > 4 || num_neighbors(COMPUTE_DELTA(ROW, dir) + row, COMPUTE_DELTA(COL, dir) + col, bitmap) > 4 || (is_other_dir_marked(row, col, dir, marked) + && is_other_dir_marked(row + COMPUTE_DELTA(ROW, dir), col + COMPUTE_DELTA(COL, dir), dir, marked))) { + col++; + continue; + } + } + } + } + + LOG("#%u: (%sclockwise) ", O_LIST_LENGTH(outline_list), clockwise ? "" : "counter"); + + outline = find_one_centerline(bitmap, dir, row, col, marked); + + /* If the outline is open (i.e., we didn't return to the + starting pixel), search from the starting pixel in the + opposite direction and concatenate the two outlines. */ + + if (outline.open) { + pixel_outline_type partial_outline; + gboolean okay = FALSE; + + if (dir == EAST) { + dir = SOUTH; + if (!(okay = is_valid_dir(row, col, dir, bitmap, marked))) { + dir = SOUTHWEST; + if (!(okay = is_valid_dir(row, col, dir, bitmap, marked))) { + dir = SOUTHEAST; + okay = is_valid_dir(row, col, dir, bitmap, marked); + } + } + } else if (dir == SOUTHEAST) { + dir = SOUTHWEST; + if (!(okay = is_valid_dir(row, col, dir, bitmap, marked))) { + dir = EAST; + if (!(okay = is_valid_dir(row, col, dir, bitmap, marked))) { + dir = SOUTH; + okay = is_valid_dir(row, col, dir, bitmap, marked); + } + } + } else if (dir == SOUTH) { + dir = EAST; + if (!(okay = is_valid_dir(row, col, dir, bitmap, marked))) { + dir = SOUTHEAST; + if (!(okay = is_valid_dir(row, col, dir, bitmap, marked))) { + dir = SOUTHWEST; + okay = is_valid_dir(row, col, dir, bitmap, marked); + } + } + } else if (dir == SOUTHWEST) { + dir = SOUTHEAST; + if (!(okay = is_valid_dir(row, col, dir, bitmap, marked))) { + dir = EAST; + if (!(okay = is_valid_dir(row, col, dir, bitmap, marked))) { + dir = SOUTH; + okay = is_valid_dir(row, col, dir, bitmap, marked); + } + } + } + if (okay) { + partial_outline = find_one_centerline(bitmap, dir, row, col, marked); + concat_pixel_outline(&outline, &partial_outline); + if (partial_outline.data) + free(partial_outline.data); + } else + col++; + } + + /* Outside outlines will start at a top edge, and move + counterclockwise, and inside outlines will start at a + bottom edge, and move clockwise. This happens because of + the order in which we look at the edges. */ + O_CLOCKWISE(outline) = clockwise; + if (O_LENGTH(outline) > 1) + append_pixel_outline(&outline_list, outline); + LOG("(%s)", (outline.open ? " open" : " closed")); + LOG(" [%u].\n", O_LENGTH(outline)); + if (O_LENGTH(outline) == 1) + free_pixel_outline(&outline); + } + } + if (test_cancel && test_cancel(testcancel_data)) { + if (O_LIST_LENGTH(outline_list) != 0) + free_pixel_outline_list(&outline_list); + goto cleanup; + } +cleanup: + at_bitmap_free(marked); + return outline_list; +} + +static pixel_outline_type find_one_centerline(at_bitmap * bitmap, direction_type search_dir, unsigned short original_row, unsigned short original_col, at_bitmap * marked) +{ + pixel_outline_type outline = new_pixel_outline(); + direction_type original_dir = search_dir; + unsigned short row = original_row, col = original_col; + unsigned short prev_row, prev_col; + at_coord pos; + + outline.open = FALSE; + at_bitmap_get_color(bitmap, row, col, &outline.color); + + /* Add the starting pixel to the output list, changing from bitmap + to Cartesian coordinates and specifying the left edge so that + the coordinates won't be adjusted. */ + pos.x = col; + pos.y = AT_BITMAP_HEIGHT(bitmap) - row - 1; + LOG(" (%d,%d)", pos.x, pos.y); + append_outline_pixel(&outline, pos); + + for (;;) { + prev_row = row; + prev_col = col; + + /* If there is no adjacent, unmarked pixel, we can't proceed + any further, so return an open outline. */ + if (!next_unmarked_pixel(&row, &col, &search_dir, bitmap, marked)) { + outline.open = TRUE; + break; + } + + /* If we've moved to a new pixel, mark all edges of the previous + pixel so that it won't be revisited. */ + if (!(prev_row == original_row && prev_col == original_col)) + mark_dir(prev_row, prev_col, search_dir, marked); + mark_dir(row, col, (direction_type) ((search_dir + 4) % 8), marked); + + /* If we've returned to the starting pixel, we're done. */ + if (row == original_row && col == original_col) + break; + + /* Add the new pixel to the output list. */ + pos.x = col; + pos.y = AT_BITMAP_HEIGHT(bitmap) - row - 1; + LOG(" (%d,%d)", pos.x, pos.y); + append_outline_pixel(&outline, pos); + } + mark_dir(original_row, original_col, original_dir, marked); + return outline; +} + +/* Add an outline to an outline list. */ + +static void append_pixel_outline(pixel_outline_list_type * outline_list, pixel_outline_type outline) +{ + O_LIST_LENGTH(*outline_list)++; + XREALLOC(outline_list->data, outline_list->length * sizeof(pixel_outline_type)); + O_LIST_OUTLINE(*outline_list, O_LIST_LENGTH(*outline_list) - 1) = outline; +} + +/* Free the list of outline lists. */ + +void free_pixel_outline_list(pixel_outline_list_type * outline_list) +{ + unsigned this_outline; + + for (this_outline = 0; this_outline < outline_list->length; this_outline++) { + pixel_outline_type o = outline_list->data[this_outline]; + free_pixel_outline(&o); + } + free(outline_list->data); + outline_list->data = NULL; + outline_list->length = 0; +} + +/* Return an empty list of pixels. */ + +static pixel_outline_type new_pixel_outline(void) +{ + pixel_outline_type pixel_outline; + + O_LENGTH(pixel_outline) = 0; + pixel_outline.data = NULL; + pixel_outline.open = FALSE; + + return pixel_outline; +} + +static void free_pixel_outline(pixel_outline_type * outline) +{ + free(outline->data); + outline->data = NULL; + outline->length = 0; +} + +/* Concatenate two pixel lists. The two lists are assumed to have the + same starting pixel and to proceed in opposite directions therefrom. */ + +static void concat_pixel_outline(pixel_outline_type * o1, const pixel_outline_type * o2) +{ + int src, dst; + unsigned o1_length, o2_length; + if (!o1 || !o2 || O_LENGTH(*o2) <= 1) + return; + + o1_length = O_LENGTH(*o1); + o2_length = O_LENGTH(*o2); + O_LENGTH(*o1) += o2_length - 1; + /* Resize o1 to the sum of the lengths of o1 and o2 minus one (because + the two lists are assumed to share the same starting pixel). */ + XREALLOC(o1->data, O_LENGTH(*o1) * sizeof(at_coord)); + /* Shift the contents of o1 to the end of the new array to make room + to prepend o2. */ + for (src = o1_length - 1, dst = O_LENGTH(*o1) - 1; src >= 0; src--, dst--) + O_COORDINATE(*o1, dst) = O_COORDINATE(*o1, src); + /* Prepend the contents of o2 (in reverse order) to o1. */ + for (src = o2_length - 1, dst = 0; src > 0; src--, dst++) + O_COORDINATE(*o1, dst) = O_COORDINATE(*o2, src); +} + +/* Add a point to the pixel list. */ + +static void append_outline_pixel(pixel_outline_type * o, at_coord c) +{ + O_LENGTH(*o)++; + XREALLOC(o->data, O_LENGTH(*o) * sizeof(at_coord)); + O_COORDINATE(*o, O_LENGTH(*o) - 1) = c; +} + +/* Is this really an edge and is it still unmarked? */ + +static gboolean is_unmarked_outline_edge(unsigned short row, unsigned short col, edge_type edge, at_bitmap * bitmap, at_bitmap * marked, at_color color, at_exception_type * exp) +{ + return (gboolean) (!is_marked_edge(edge, row, col, marked) + && is_outline_edge(edge, bitmap, row, col, color, exp)); +} + +/* We check to see if the edge of the pixel at position ROW and COL + is an outline edge */ + +static gboolean is_outline_edge(edge_type edge, at_bitmap * bitmap, unsigned short row, unsigned short col, at_color color, at_exception_type * exp) +{ + /* If this pixel isn't of the same color, it's not part of the outline. */ + if (!at_bitmap_equal_color(bitmap, row, col, &color)) + return FALSE; + + switch (edge) { + case LEFT: + return (gboolean) (col == 0 || !at_bitmap_equal_color(bitmap, row, col - 1, &color)); + case TOP: + return (gboolean) (row == 0 || !at_bitmap_equal_color(bitmap, row - 1, col, &color)); + + case RIGHT: + return (gboolean) (col == AT_BITMAP_WIDTH(bitmap) - 1 || !at_bitmap_equal_color(bitmap, row, col + 1, &color)); + + case BOTTOM: + return (gboolean) (row == AT_BITMAP_HEIGHT(bitmap) - 1 || !at_bitmap_equal_color(bitmap, row + 1, col, &color)); + + case NO_EDGE: + g_assert_not_reached(); + default: + g_assert_not_reached(); + } + return FALSE; /* NOT REACHED */ +} + +/* If EDGE is not already marked, we mark it; otherwise, it's a fatal error. + The position ROW and COL should be inside the bitmap MARKED. EDGE can be + NO_EDGE. */ + +static void mark_edge(edge_type edge, unsigned short row, unsigned short col, at_bitmap * marked) +{ + *AT_BITMAP_PIXEL(marked, row, col) |= 1 << edge; +} + +/* Mark the direction of the pixel ROW/COL in MARKED. */ + +static void mark_dir(unsigned short row, unsigned short col, direction_type dir, at_bitmap * marked) +{ + *AT_BITMAP_PIXEL(marked, row, col) |= 1 << dir; +} + +/* Test if the direction of pixel at ROW/COL in MARKED is marked. */ + +static gboolean is_marked_dir(unsigned short row, unsigned short col, direction_type dir, at_bitmap * marked) +{ + return (gboolean) ((*AT_BITMAP_PIXEL(marked, row, col) & 1 << dir) != 0); +} + +static gboolean is_other_dir_marked(unsigned short row, unsigned short col, direction_type dir, at_bitmap * marked) +{ + return (gboolean) ((*AT_BITMAP_PIXEL(marked, row, col) & (255 - (1 << dir) - (1 << ((dir + 4) % 8)))) != 0); +} + +static gboolean next_unmarked_pixel(unsigned short *row, unsigned short *col, direction_type * dir, at_bitmap * bitmap, at_bitmap * marked) +{ + unsigned short orig_row = *row, orig_col = *col; + direction_type orig_dir = *dir, test_dir = *dir; + + do { + if (is_valid_dir(orig_row, orig_col, test_dir, bitmap, marked)) { + *row = orig_row + COMPUTE_DELTA(ROW, test_dir); + *col = orig_col + COMPUTE_DELTA(COL, test_dir); + *dir = test_dir; + break; + } + + if (orig_dir == test_dir) + test_dir = (direction_type) ((orig_dir + 2) % 8); + else if ((orig_dir + 2) % 8 == test_dir) + test_dir = (direction_type) ((orig_dir + 6) % 8); + else if ((orig_dir + 6) % 8 == test_dir) + test_dir = (direction_type) ((orig_dir + 1) % 8); + else if ((orig_dir + 1) % 8 == test_dir) + test_dir = (direction_type) ((orig_dir + 7) % 8); + else if ((orig_dir + 7) % 8 == test_dir) + test_dir = (direction_type) ((orig_dir + 3) % 8); + else if ((orig_dir + 3) % 8 == test_dir) + test_dir = (direction_type) ((orig_dir + 5) % 8); + else if ((orig_dir + 5) % 8 == test_dir) + break; + } + while (1); + if ((*row != orig_row || *col != orig_col) && (!(is_other_dir_marked(orig_row, orig_col, test_dir, marked) + && is_other_dir_marked(orig_row + COMPUTE_DELTA(ROW, test_dir), orig_col + COMPUTE_DELTA(COL, test_dir), test_dir, marked)))) + return TRUE; + else + return FALSE; +} + +/* Return the number of pixels adjacent to pixel ROW/COL that are black. */ + +static unsigned num_neighbors(unsigned short row, unsigned short col, at_bitmap * bitmap) +{ + unsigned dir, count = 0; + at_color color; + + at_bitmap_get_color(bitmap, row, col, &color); + for (dir = NORTH; dir <= NORTHEAST; dir++) { + int delta_r = COMPUTE_DELTA(ROW, dir); + int delta_c = COMPUTE_DELTA(COL, dir); + unsigned int test_row = row + delta_r; + unsigned int test_col = col + delta_c; + if (AT_BITMAP_VALID_PIXEL(bitmap, test_row, test_col) + && at_bitmap_equal_color(bitmap, test_row, test_col, &color)) + ++count; + } + return count; +} + +/* Test if the edge EDGE at ROW/COL in MARKED is marked. */ + +static gboolean is_marked_edge(edge_type edge, unsigned short row, unsigned short col, at_bitmap * marked) +{ + return (gboolean) (edge == NO_EDGE ? FALSE : (*AT_BITMAP_PIXEL(marked, row, col) & (1 << edge)) != 0); +} + +static at_coord next_point(at_bitmap * bitmap, edge_type * edge, unsigned short *row, unsigned short *col, at_color color, gboolean clockwise, at_bitmap * marked, at_exception_type * exp) +{ + at_coord pos = { 0, 0 }; + + if (!clockwise) + switch (*edge) { + case TOP: + /* WEST */ + if ((*col >= 1 && !is_marked_edge(TOP, *row, *col - 1, marked) + && is_outline_edge(TOP, bitmap, *row, *col - 1, color, exp))) { + /**edge = TOP;*/ + (*col)--; + pos.x = *col; + pos.y = AT_BITMAP_HEIGHT(bitmap) - *row; + break; + } + CHECK_FATAL(); + /* NORTHWEST */ + if ((*col >= 1 && *row >= 1 && !is_marked_edge(RIGHT, *row - 1, *col - 1, marked) + && is_outline_edge(RIGHT, bitmap, *row - 1, *col - 1, color, exp)) && !(is_marked_edge(LEFT, *row - 1, *col, marked) && is_marked_edge(TOP, *row, *col - 1, marked)) && !(is_marked_edge(BOTTOM, *row - 1, *col, marked) && is_marked_edge(RIGHT, *row, *col - 1, marked))) { + *edge = RIGHT; + (*col)--; + (*row)--; + pos.x = *col + 1; + pos.y = AT_BITMAP_HEIGHT(bitmap) - *row; + break; + } + CHECK_FATAL(); + if ((!is_marked_edge(LEFT, *row, *col, marked) + && is_outline_edge(LEFT, bitmap, *row, *col, color, exp))) { + *edge = LEFT; + pos.x = *col; + pos.y = AT_BITMAP_HEIGHT(bitmap) - *row - 1; + break; + } + CHECK_FATAL(); + *edge = NO_EDGE; + break; + case RIGHT: + /* NORTH */ + if ((*row >= 1 && !is_marked_edge(RIGHT, *row - 1, *col, marked) + && is_outline_edge(RIGHT, bitmap, *row - 1, *col, color, exp))) { + /**edge = RIGHT;*/ + (*row)--; + pos.x = *col + 1; + pos.y = AT_BITMAP_HEIGHT(bitmap) - *row; + break; + } + CHECK_FATAL(); + /* NORTHEAST */ + if ((*col + 1 < AT_BITMAP_WIDTH(marked) && *row >= 1 && !is_marked_edge(BOTTOM, *row - 1, *col + 1, marked) + && is_outline_edge(BOTTOM, bitmap, *row - 1, *col + 1, color, exp)) && !(is_marked_edge(LEFT, *row, *col + 1, marked) && is_marked_edge(BOTTOM, *row - 1, *col, marked)) && !(is_marked_edge(TOP, *row, *col + 1, marked) && is_marked_edge(RIGHT, *row - 1, *col, marked))) { + *edge = BOTTOM; + (*col)++; + (*row)--; + pos.x = *col + 1; + pos.y = AT_BITMAP_HEIGHT(bitmap) - *row - 1; + break; + } + CHECK_FATAL(); + if ((!is_marked_edge(TOP, *row, *col, marked) + && is_outline_edge(TOP, bitmap, *row, *col, color, exp))) { + *edge = TOP; + pos.x = *col; + pos.y = AT_BITMAP_HEIGHT(bitmap) - *row; + break; + } + CHECK_FATAL(); + *edge = NO_EDGE; + break; + case BOTTOM: + /* EAST */ + if ((*col + 1 < AT_BITMAP_WIDTH(marked) + && !is_marked_edge(BOTTOM, *row, *col + 1, marked) + && is_outline_edge(BOTTOM, bitmap, *row, *col + 1, color, exp))) { + /**edge = BOTTOM;*/ + (*col)++; + pos.x = *col + 1; + pos.y = AT_BITMAP_HEIGHT(bitmap) - *row - 1; + break; + } + CHECK_FATAL(); + /* SOUTHEAST */ + if ((*col + 1 < AT_BITMAP_WIDTH(marked) && *row + 1 < AT_BITMAP_HEIGHT(marked) + && !is_marked_edge(LEFT, *row + 1, *col + 1, marked) + && is_outline_edge(LEFT, bitmap, *row + 1, *col + 1, color, exp)) && !(is_marked_edge(TOP, *row + 1, *col, marked) && is_marked_edge(LEFT, *row, *col + 1, marked)) && !(is_marked_edge(RIGHT, *row + 1, *col, marked) && is_marked_edge(BOTTOM, *row, *col + 1, marked))) { + *edge = LEFT; + (*col)++; + (*row)++; + pos.x = *col; + pos.y = AT_BITMAP_HEIGHT(bitmap) - *row - 1; + break; + } + CHECK_FATAL(); + if ((!is_marked_edge(RIGHT, *row, *col, marked) + && is_outline_edge(RIGHT, bitmap, *row, *col, color, exp))) { + *edge = RIGHT; + pos.x = *col + 1; + pos.y = AT_BITMAP_HEIGHT(bitmap) - *row; + break; + } + CHECK_FATAL(); + *edge = NO_EDGE; + break; + case LEFT: + /* SOUTH */ + if ((*row + 1 < AT_BITMAP_HEIGHT(marked) + && !is_marked_edge(LEFT, *row + 1, *col, marked) + && is_outline_edge(LEFT, bitmap, *row + 1, *col, color, exp))) { + /**edge = LEFT;*/ + (*row)++; + pos.x = *col; + pos.y = AT_BITMAP_HEIGHT(bitmap) - *row - 1; + break; + } + CHECK_FATAL(); + /* SOUTHWEST */ + if ((*col >= 1 && *row + 1 < AT_BITMAP_HEIGHT(marked) + && !is_marked_edge(TOP, *row + 1, *col - 1, marked) + && is_outline_edge(TOP, bitmap, *row + 1, *col - 1, color, exp)) && !(is_marked_edge(RIGHT, *row, *col - 1, marked) && is_marked_edge(TOP, *row + 1, *col, marked)) && !(is_marked_edge(BOTTOM, *row, *col - 1, marked) && is_marked_edge(LEFT, *row + 1, *col, marked))) { + *edge = TOP; + (*col)--; + (*row)++; + pos.x = *col; + pos.y = AT_BITMAP_HEIGHT(bitmap) - *row; + break; + } + CHECK_FATAL(); + if ((!is_marked_edge(BOTTOM, *row, *col, marked) + && is_outline_edge(BOTTOM, bitmap, *row, *col, color, exp))) { + *edge = BOTTOM; + pos.x = *col + 1; + pos.y = AT_BITMAP_HEIGHT(bitmap) - *row - 1; + break; + } + CHECK_FATAL(); + case NO_EDGE: + default: + *edge = NO_EDGE; + break; + } else + switch (*edge) { + case TOP: + if ((!is_marked_edge(LEFT, *row, *col, marked) + && is_outline_edge(LEFT, bitmap, *row, *col, color, exp))) { + *edge = LEFT; + pos.x = *col; + pos.y = AT_BITMAP_HEIGHT(bitmap) - *row - 1; + break; + } + CHECK_FATAL(); + /* WEST */ + if ((*col >= 1 && !is_marked_edge(TOP, *row, *col - 1, marked) + && is_outline_edge(TOP, bitmap, *row, *col - 1, color, exp))) { + /**edge = TOP;*/ + (*col)--; + pos.x = *col; + pos.y = AT_BITMAP_HEIGHT(bitmap) - *row; + break; + } + CHECK_FATAL(); + /* NORTHWEST */ + if ((*col >= 1 && *row >= 1 && !is_marked_edge(RIGHT, *row - 1, *col - 1, marked) + && is_outline_edge(RIGHT, bitmap, *row - 1, *col - 1, color, exp))) { + *edge = RIGHT; + (*col)--; + (*row)--; + pos.x = *col + 1; + pos.y = AT_BITMAP_HEIGHT(bitmap) - *row; + break; + } + CHECK_FATAL(); + *edge = NO_EDGE; + break; + case RIGHT: + if ((!is_marked_edge(TOP, *row, *col, marked) + && is_outline_edge(TOP, bitmap, *row, *col, color, exp))) { + *edge = TOP; + pos.x = *col; + pos.y = AT_BITMAP_HEIGHT(bitmap) - *row; + break; + } + CHECK_FATAL(); + /* NORTH */ + if ((*row >= 1 && !is_marked_edge(RIGHT, *row - 1, *col, marked) + && is_outline_edge(RIGHT, bitmap, *row - 1, *col, color, exp))) { + /**edge = RIGHT;*/ + (*row)--; + pos.x = *col + 1; + pos.y = AT_BITMAP_HEIGHT(bitmap) - *row; + break; + } + CHECK_FATAL(); + /* NORTHEAST */ + if ((*col + 1 < AT_BITMAP_WIDTH(marked) && *row >= 1 && !is_marked_edge(BOTTOM, *row - 1, *col + 1, marked) + && is_outline_edge(BOTTOM, bitmap, *row - 1, *col + 1, color, exp))) { + *edge = BOTTOM; + (*col)++; + (*row)--; + pos.x = *col + 1; + pos.y = AT_BITMAP_HEIGHT(bitmap) - *row - 1; + break; + } + CHECK_FATAL(); + *edge = NO_EDGE; + break; + case BOTTOM: + if ((!is_marked_edge(RIGHT, *row, *col, marked) + && is_outline_edge(RIGHT, bitmap, *row, *col, color, exp))) { + *edge = RIGHT; + pos.x = *col + 1; + pos.y = AT_BITMAP_HEIGHT(bitmap) - *row; + break; + } + CHECK_FATAL(); + /* EAST */ + if ((*col + 1 < AT_BITMAP_WIDTH(marked) + && !is_marked_edge(BOTTOM, *row, *col + 1, marked) + && is_outline_edge(BOTTOM, bitmap, *row, *col + 1, color, exp))) { + /**edge = BOTTOM;*/ + (*col)++; + pos.x = *col + 1; + pos.y = AT_BITMAP_HEIGHT(bitmap) - *row - 1; + break; + } + CHECK_FATAL(); + /* SOUTHEAST */ + if ((*col + 1 < AT_BITMAP_WIDTH(marked) && *row + 1 < AT_BITMAP_HEIGHT(marked) + && !is_marked_edge(LEFT, *row + 1, *col + 1, marked) + && is_outline_edge(LEFT, bitmap, *row + 1, *col + 1, color, exp))) { + *edge = LEFT; + (*col)++; + (*row)++; + pos.x = *col; + pos.y = AT_BITMAP_HEIGHT(bitmap) - *row - 1; + break; + } + CHECK_FATAL(); + *edge = NO_EDGE; + break; + case LEFT: + if ((!is_marked_edge(BOTTOM, *row, *col, marked) + && is_outline_edge(BOTTOM, bitmap, *row, *col, color, exp))) { + *edge = BOTTOM; + pos.x = *col + 1; + pos.y = AT_BITMAP_HEIGHT(bitmap) - *row - 1; + break; + } + CHECK_FATAL(); + /* SOUTH */ + if ((*row + 1 < AT_BITMAP_HEIGHT(marked) + && !is_marked_edge(LEFT, *row + 1, *col, marked) + && is_outline_edge(LEFT, bitmap, *row + 1, *col, color, exp))) { + /**edge = LEFT;*/ + (*row)++; + pos.x = *col; + pos.y = AT_BITMAP_HEIGHT(bitmap) - *row - 1; + break; + } + CHECK_FATAL(); + /* SOUTHWEST */ + if ((*col >= 1 && *row + 1 < AT_BITMAP_HEIGHT(marked) + && !is_marked_edge(TOP, *row + 1, *col - 1, marked) + && is_outline_edge(TOP, bitmap, *row + 1, *col - 1, color, exp))) { + *edge = TOP; + (*col)--; + (*row)++; + pos.x = *col; + pos.y = AT_BITMAP_HEIGHT(bitmap) - *row; + break; + } + CHECK_FATAL(); + case NO_EDGE: + default: + *edge = NO_EDGE; + break; + } +cleanup: + return (pos); +} diff --git a/src/3rdparty/autotrace/pxl-outline.h b/src/3rdparty/autotrace/pxl-outline.h new file mode 100644 index 0000000..e00d802 --- /dev/null +++ b/src/3rdparty/autotrace/pxl-outline.h @@ -0,0 +1,58 @@ +/* pxl-outline.h: find a list of outlines which make up one character. */ + +#ifndef PXL_OUTLINE_H +#define PXL_OUTLINE_H + +#include "autotrace.h" +#include "exception.h" +#include "bitmap.h" +#include "color.h" + +/* This is a list of contiguous points on the bitmap. */ +typedef struct { + at_coord *data; + unsigned length; + gboolean clockwise; + at_color color; + gboolean open; +} pixel_outline_type; + +/* The Nth coordinate in the list. */ +#define O_COORDINATE(p_o, n) ((p_o).data[n]) + +/* The length of the list. */ +#define O_LENGTH(p_o) ((p_o).length) + +/* Whether the outline moves clockwise or counterclockwise. */ +#define O_CLOCKWISE(p_o) ((p_o).clockwise) + +/* Since a pixel outline is cyclic, the index of the next coordinate + after the last is the first, and the previous coordinate before the + first is the last. */ +#define O_NEXT(p_o, n) (((n) + 1) % O_LENGTH (p_o)) +#define O_PREV(p_o, n) ((n) == 0 \ + ? O_LENGTH (p_o) - 1 \ + : (n) - 1) + +/* And the character turns into a list of such lists. */ +typedef struct { + pixel_outline_type *data; + unsigned length; +} pixel_outline_list_type; + +/* The Nth list in the list of lists. */ +#define O_LIST_OUTLINE(p_o_l, n) ((p_o_l).data[n]) + +/* The length of the list of lists. */ +#define O_LIST_LENGTH(p_o_l) ((p_o_l).length) + +/* Find all pixels on the outline in the character C. */ +extern pixel_outline_list_type find_outline_pixels(at_bitmap * bitmap, at_color * bg_color, at_progress_func notify_progress, gpointer progress_data, at_testcancel_func test_cancel, gpointer testcancel_data, at_exception_type * exp); + +/* Find all pixels on the center line of the character C. */ +extern pixel_outline_list_type find_centerline_pixels(at_bitmap * bitmap, at_color bg_color, at_progress_func notify_progress, gpointer progress_data, at_testcancel_func test_cancel, gpointer testcancel_data, at_exception_type * exp); + +/* Free the memory in the list. */ +extern void free_pixel_outline_list(pixel_outline_list_type *); + +#endif /* not PXL_OUTLINE_H */ diff --git a/src/3rdparty/autotrace/quantize.h b/src/3rdparty/autotrace/quantize.h new file mode 100644 index 0000000..3e62c2e --- /dev/null +++ b/src/3rdparty/autotrace/quantize.h @@ -0,0 +1,52 @@ +/* quantize.h: Quantize a high color bitmap + + Copyright (C) 2001, 2002 Martin Weber + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public License + as published by the Free Software Foundation; either version 2.1 of + the License, or (at your option) any later version. + + This library 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 + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with this library; if not, write to the Free Software + Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 + USA. */ + +#include "bitmap.h" +#include "color.h" +#include "exception.h" + +#ifndef QUANTIZE_H +#define QUANTIZE_H + +#define PRECISION_R 7 +#define PRECISION_G 7 +#define PRECISION_B 7 + +#define HIST_R_ELEMS (1<<PRECISION_R) +#define HIST_G_ELEMS (1<<PRECISION_G) +#define HIST_B_ELEMS (1<<PRECISION_B) + +#define MR HIST_G_ELEMS*HIST_B_ELEMS +#define MG HIST_B_ELEMS + +typedef unsigned long ColorFreq; +typedef ColorFreq *Histogram; + +typedef struct { + int desired_number_of_colors; /* Number of colors we will allow */ + int actual_number_of_colors; /* Number of colors actually needed */ + at_color cmap[256]; /* colormap created by quantization */ + ColorFreq freq[256]; + Histogram histogram; /* holds the histogram */ +} QuantizeObj; + +void quantize(at_bitmap *, long ncolors, const at_color * bgColor, QuantizeObj **, at_exception_type * exp); + +void quantize_object_free(QuantizeObj * obj); +#endif /* NOT QUANTIZE_H */ diff --git a/src/3rdparty/autotrace/spline.c b/src/3rdparty/autotrace/spline.c new file mode 100644 index 0000000..3aa0f73 --- /dev/null +++ b/src/3rdparty/autotrace/spline.c @@ -0,0 +1,160 @@ +/* spline.c: spline and spline list (represented as arrays) manipulation. */ + +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif /* Def: HAVE_CONFIG_H */ + +#include "logreport.h" +#include "types.h" +#include "spline.h" +#include "vector.h" +#include "xstd.h" +#include <assert.h> + +/* Print a spline in human-readable form. */ + +void print_spline(spline_type s) +{ + assert(SPLINE_DEGREE(s) == LINEARTYPE || SPLINE_DEGREE(s) == CUBICTYPE); + + if (SPLINE_DEGREE(s) == LINEARTYPE) + fprintf(stdout, "(%.3f,%.3f)--(%.3f,%.3f).\n", START_POINT(s).x, START_POINT(s).y, END_POINT(s).x, END_POINT(s).y); + + else if (SPLINE_DEGREE(s) == CUBICTYPE) + fprintf(stdout, "(%.3f,%.3f)..ctrls(%.3f,%.3f)&(%.3f,%.3f)..(%.3f,%.3f).\n", START_POINT(s).x, START_POINT(s).y, CONTROL1(s).x, CONTROL1(s).y, CONTROL2(s).x, CONTROL2(s).y, END_POINT(s).x, END_POINT(s).y); +} + +/* Evaluate the spline S at a given T value. This is an implementation + of de Casteljau's algorithm. See Schneider's thesis, p.37. + The variable names are taken from there. */ + +at_real_coord evaluate_spline(spline_type s, gfloat t) +{ + spline_type V[4]; /* We need degree+1 splines, but assert degree <= 3. */ + signed i, j; + gfloat one_minus_t = (gfloat) 1.0 - t; + polynomial_degree degree = SPLINE_DEGREE(s); + + for (i = 0; i <= degree; i++) { + V[0].v[i].x = s.v[i].x; + V[0].v[i].y = s.v[i].y; + V[0].v[i].z = s.v[i].z; + } + + for (j = 1; j <= degree; j++) + for (i = 0; i <= degree - j; i++) { + at_real_coord t1 = Pmult_scalar(V[j - 1].v[i], one_minus_t); + at_real_coord t2 = Pmult_scalar(V[j - 1].v[i + 1], t); + at_real_coord temp = Padd(t1, t2); + V[j].v[i].x = temp.x; + V[j].v[i].y = temp.y; + V[j].v[i].z = temp.z; + } + + return V[degree].v[0]; +} + +/* Return a new, empty, spline list. */ + +spline_list_type *new_spline_list(void) +{ + spline_list_type *answer; + + XMALLOC(answer, sizeof(spline_list_type)); + *answer = empty_spline_list(); + return answer; +} + +spline_list_type empty_spline_list(void) +{ + spline_list_type answer; + SPLINE_LIST_DATA(answer) = NULL; + SPLINE_LIST_LENGTH(answer) = 0; + return answer; +} + +/* Return a new spline list with SPLINE as the first element. */ + +spline_list_type *new_spline_list_with_spline(spline_type spline) +{ + spline_list_type *answer; + + answer = new_spline_list(); + XMALLOC(SPLINE_LIST_DATA(*answer), sizeof(spline_type)); + SPLINE_LIST_ELT(*answer, 0) = spline; + SPLINE_LIST_LENGTH(*answer) = 1; + + return answer; +} + +/* Free the storage in a spline list. We don't have to free the + elements, since they are arrays in automatic storage. And we don't + want to free the list if it was empty. */ + +void free_spline_list(spline_list_type spline_list) +{ + free(SPLINE_LIST_DATA(spline_list)); +} + +/* Append the spline S to the list SPLINE_LIST. */ + +void append_spline(spline_list_type * l, spline_type s) +{ + assert(l != NULL); + + SPLINE_LIST_LENGTH(*l)++; + XREALLOC(SPLINE_LIST_DATA(*l), SPLINE_LIST_LENGTH(*l) * sizeof(spline_type)); + LAST_SPLINE_LIST_ELT(*l) = s; +} + +/* Tack the elements in the list S2 onto the end of S1. + S2 is not changed. */ + +void concat_spline_lists(spline_list_type * s1, spline_list_type s2) +{ + unsigned this_spline; + unsigned new_length; + + assert(s1 != NULL); + + new_length = SPLINE_LIST_LENGTH(*s1) + SPLINE_LIST_LENGTH(s2); + + XREALLOC(SPLINE_LIST_DATA(*s1), new_length * sizeof(spline_type)); + + for (this_spline = 0; this_spline < SPLINE_LIST_LENGTH(s2); this_spline++) + SPLINE_LIST_ELT(*s1, SPLINE_LIST_LENGTH(*s1)++) + = SPLINE_LIST_ELT(s2, this_spline); +} + +/* Return a new, empty, spline list array. */ + +spline_list_array_type new_spline_list_array(void) +{ + spline_list_array_type answer; + + SPLINE_LIST_ARRAY_DATA(answer) = NULL; + SPLINE_LIST_ARRAY_LENGTH(answer) = 0; + + return answer; +} + +/* Free the storage in a spline list array. We don't + want to free the list if it is empty. */ +void free_spline_list_array(spline_list_array_type * spline_list_array) +{ + unsigned this_list; + + for (this_list = 0; this_list < SPLINE_LIST_ARRAY_LENGTH(*spline_list_array); this_list++) + free_spline_list(SPLINE_LIST_ARRAY_ELT(*spline_list_array, this_list)); + + free(SPLINE_LIST_ARRAY_DATA(*spline_list_array)); +} + +/* Append the spline S to the list SPLINE_LIST_ARRAY. */ + +void append_spline_list(spline_list_array_type * l, spline_list_type s) +{ + SPLINE_LIST_ARRAY_LENGTH(*l)++; + XREALLOC(SPLINE_LIST_ARRAY_DATA(*l), SPLINE_LIST_ARRAY_LENGTH(*l) * sizeof(spline_list_type)); + LAST_SPLINE_LIST_ARRAY_ELT(*l) = s; +} diff --git a/src/3rdparty/autotrace/spline.h b/src/3rdparty/autotrace/spline.h new file mode 100644 index 0000000..6cbd143 --- /dev/null +++ b/src/3rdparty/autotrace/spline.h @@ -0,0 +1,88 @@ +/* spline.h: manipulate the spline representation. + Some of macrs are only renamed macros in output.h. */ + +#ifndef SPLINE_H +#define SPLINE_H + +#include <stdio.h> +#include "autotrace.h" +#include "output.h" + +typedef at_polynomial_degree polynomial_degree; +typedef at_spline_type spline_type; + +#define LINEARTYPE AT_LINEARTYPE +#define QUADRATICTYPE AT_QUADRATICTYPE +#define CUBICTYPE AT_CUBICTYPE +#define PARALLELELLIPSETYPE AT_PARALLELELLIPSETYPE +#define ELLIPSETYPE AT_ELLIPSETYPE +#define CIRCLETYPE AT_CIRCLETYPE + +#define START_POINT AT_SPLINE_START_POINT_VALUE +#define CONTROL1 AT_SPLINE_CONTROL1_VALUE +#define CONTROL2 AT_SPLINE_CONTROL2_VALUE +#define END_POINT AT_SPLINE_END_POINT_VALUE +#define SPLINE_DEGREE AT_SPLINE_DEGREE_VALUE +#define SPLINE_LINEARITY(spl) ((spl).linearity) + +#ifndef _IMPORTING +/* Print a spline on the given file. */ +extern void print_spline(spline_type); + +/* Evaluate SPLINE at the given T value. */ +extern at_real_coord evaluate_spline(spline_type spline, gfloat t); +#endif + +/* Each outline in a character is typically represented by many + splines. So, here is a list structure for that: */ +typedef at_spline_list_type spline_list_type; + +/* An empty list will have length zero (and null data). */ +#define SPLINE_LIST_LENGTH AT_SPLINE_LIST_LENGTH_VALUE + +/* The address of the beginning of the array of data. */ +#define SPLINE_LIST_DATA AT_SPLINE_LIST_DATA_VALUE + +/* The element INDEX in S_L. */ +#define SPLINE_LIST_ELT AT_SPLINE_LIST_ELT_VALUE + +/* The last element in S_L. */ +#define LAST_SPLINE_LIST_ELT(s_l) \ + (SPLINE_LIST_DATA (s_l)[SPLINE_LIST_LENGTH (s_l) - 1]) + +/* The previous and next elements to INDEX in S_L. */ +#define NEXT_SPLINE_LIST_ELT(s_l, index) \ + SPLINE_LIST_ELT (s_l, ((index) + 1) % SPLINE_LIST_LENGTH (s_l)) +#define PREV_SPLINE_LIST_ELT(s_l, index) \ + SPLINE_LIST_ELT (s_l, index == 0 \ + ? SPLINE_LIST_LENGTH (s_l) - 1 \ + : index - 1) + +#ifndef _IMPORTING +/* Construct and destroy new `spline_list_type' objects. */ +extern spline_list_type *new_spline_list(void); /* Allocate new memory */ +extern spline_list_type empty_spline_list(void); /* No allocation */ +extern spline_list_type *new_spline_list_with_spline(spline_type); +extern void free_spline_list(spline_list_type); + +/* Append the spline S to the list S_LIST. */ +extern void append_spline(spline_list_type * s_list, spline_type s); + +/* Append the elements in list S2 to S1, changing S1. */ +extern void concat_spline_lists(spline_list_type * s1, spline_list_type s2); +#endif + +typedef at_spline_list_array_type spline_list_array_type; + +/* Turns out we can use the same definitions for lists of lists as for + just lists. But we define the usual names, just in case. */ +#define SPLINE_LIST_ARRAY_LENGTH AT_SPLINE_LIST_ARRAY_LENGTH_VALUE +#define SPLINE_LIST_ARRAY_DATA SPLINE_LIST_DATA +#define SPLINE_LIST_ARRAY_ELT AT_SPLINE_LIST_ARRAY_ELT_VALUE +#define LAST_SPLINE_LIST_ARRAY_ELT LAST_SPLINE_LIST_ELT + +extern spline_list_array_type new_spline_list_array(void); +extern void append_spline_list(spline_list_array_type *, spline_list_type); +extern void free_spline_list_array(spline_list_array_type *); + +#endif /* not SPLINE_H */ diff --git a/src/3rdparty/autotrace/thin-image.c b/src/3rdparty/autotrace/thin-image.c new file mode 100644 index 0000000..2e220ec --- /dev/null +++ b/src/3rdparty/autotrace/thin-image.c @@ -0,0 +1,353 @@ +/* thin-image.c: thin binary image + + Copyright (C) 2001, 2002 Martin Weber + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public License + as published by the Free Software Foundation; either version 2.1 of + the License, or (at your option) any later version. + + This library 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 + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with this library; if not, write to the Free Software + Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 + USA. */ + +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif /* Def: HAVE_CONFIG_H */ + +#include <stdlib.h> +#include <stdio.h> +#include "thin-image.h" +#include "logreport.h" +#include "types.h" +#include "bitmap.h" +#include "xstd.h" +#include <string.h> + +#define PIXEL_SET(p, new) ((void)memcpy((p), (new), sizeof(Pixel))) +#define PIXEL_EQUAL(p1, p2) \ + ((p1)[0] == (p2)[0] && (p1)[1] == (p2)[1] && (p1)[2] == (p2)[2]) + +typedef unsigned char Pixel[3]; /* RGB pixel data type */ + +void thin3(at_bitmap * image, Pixel colour); +void thin1(at_bitmap * image, unsigned char colour); + +/* -------------------------------- ThinImage - Thin binary image. --------------------------- * + * + * Description: + * Thins the supplied binary image using Rosenfeld's parallel + * thinning algorithm. + * + * On Entry: + * image = Image to thin. + * + * -------------------------------------------------------------------------------------------- */ + +/* Direction masks: */ +/* N S W E */ +static unsigned int masks[] = { 0200, 0002, 0040, 0010 }; + +/* True if pixel neighbor map indicates the pixel is 8-simple and */ +/* not an end point and thus can be deleted. The neighborhood */ +/* map is defined as an integer of bits abcdefghi with a non-zero */ +/* bit representing a non-zero pixel. The bit assignment for the */ +/* neighborhood is: */ +/* */ +/* a b c */ +/* d e f */ +/* g h i */ + +static unsigned char todelete[512] = { + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 +}; + +static at_color background = { 0xff, 0xff, 0xff }; + +void thin_image(at_bitmap * image, const at_color * bg, at_exception_type * exp) +{ + /* This is nasty as we need to call thin once for each + * colour in the image the way I do this is to keep a second + * copy of the bitmap and to use this to keep + * track of which colours have not yet been processed, + * trades time for pathological case memory.....*/ + long m, n, num_pixels; + at_bitmap bm; + unsigned int spp = AT_BITMAP_PLANES(image), width = AT_BITMAP_WIDTH(image), height = AT_BITMAP_HEIGHT(image); + + if (bg) + background = *bg; + + bm.height = image->height; + bm.width = image->width; + bm.np = image->np; + XMALLOC(bm.bitmap, height * width * spp); + memcpy(bm.bitmap, image->bitmap, height * width * spp); + /* that clones the image */ + + num_pixels = height * width; + switch (spp) { + case 3: + { + Pixel *ptr = (Pixel *) AT_BITMAP_BITS(&bm); + Pixel bg_color; + bg_color[0] = background.r; + bg_color[1] = background.g; + bg_color[2] = background.b; + + for (n = num_pixels - 1; n >= 0L; --n) { + Pixel p; + + PIXEL_SET(p, ptr[n]); + if (!PIXEL_EQUAL(p, bg_color)) { + /* we have a new colour in the image */ + LOG("Thinning colour (%x, %x, %x)\n", p[0], p[1], p[2]); + for (m = n - 1; m >= 0L; --m) { + if (PIXEL_EQUAL(ptr[m], p)) + PIXEL_SET(ptr[m], bg_color); + } + thin3(image, p); + } + } + break; + } + + case 1: + { + unsigned char *ptr = AT_BITMAP_BITS(&bm); + unsigned char bg_color; + + if (background.r == background.g && background.g == background.b) + bg_color = background.r; + else + bg_color = at_color_luminance(&background); + + for (n = num_pixels - 1; n >= 0L; --n) { + unsigned char c = ptr[n]; + if (c != bg_color) { + LOG("Thinning colour %x\n", c); + for (m = n - 1; m >= 0L; --m) + if (ptr[m] == c) + ptr[m] = bg_color; + thin1(image, c); + } + } + break; + } + + default: + { + LOG("thin_image: %u-plane images are not supported", spp); + at_exception_fatal(exp, "thin_image: wrong plane images are passed"); + goto cleanup; + } + } +cleanup: + free(bm.bitmap); +} + +void thin3(at_bitmap * image, Pixel colour) +{ + Pixel *ptr, *y_ptr, *y1_ptr; + Pixel bg_color; + unsigned int xsize, ysize; /* Image resolution */ + unsigned int x, y; /* Pixel location */ + unsigned int i; /* Pass index */ + unsigned int pc = 0; /* Pass count */ + unsigned int count = 1; /* Deleted pixel count */ + unsigned int p, q; /* Neighborhood maps of adjacent */ + /* cells */ + unsigned char *qb; /* Neighborhood maps of previous */ + /* scanline */ + unsigned int m; /* Deletion direction mask */ + + bg_color[0] = background.r; + bg_color[1] = background.g; + bg_color[2] = background.b; + + LOG(" Thinning image.....\n "); + xsize = AT_BITMAP_WIDTH(image); + ysize = AT_BITMAP_HEIGHT(image); + XMALLOC(qb, xsize * sizeof(unsigned char)); + qb[xsize - 1] = 0; /* Used for lower-right pixel */ + ptr = (Pixel *) AT_BITMAP_BITS(image); + + while (count) { /* Scan image while deletions */ + pc++; + count = 0; + + for (i = 0; i < 4; i++) { + + m = masks[i]; + + /* Build initial previous scan buffer. */ + p = PIXEL_EQUAL(ptr[0], colour); + for (x = 0; x < xsize - 1; x++) + qb[x] = (unsigned char)(p = ((p << 1) & 0006) | (unsigned int)PIXEL_EQUAL(ptr[x + 1], colour)); + + /* Scan image for pixel deletion candidates. */ + y_ptr = ptr; + y1_ptr = ptr + xsize; + for (y = 0; y < ysize - 1; y++, y_ptr += xsize, y1_ptr += xsize) { + q = qb[0]; + p = ((q << 2) & 0330) | (unsigned int)PIXEL_EQUAL(y1_ptr[0], colour); + + for (x = 0; x < xsize - 1; x++) { + q = qb[x]; + p = ((p << 1) & 0666) | ((q << 3) & 0110) | (unsigned int)PIXEL_EQUAL(y1_ptr[x + 1], colour); + qb[x] = (unsigned char)p; + if ((i != 2 || x != 0) && ((p & m) == 0) && todelete[p]) { + count++; /* delete the pixel */ + PIXEL_SET(y_ptr[x], bg_color); + } + } + + /* Process right edge pixel. */ + p = (p << 1) & 0666; + if (i != 3 && (p & m) == 0 && todelete[p]) { + count++; + PIXEL_SET(y_ptr[xsize - 1], bg_color); + } + } + + if (i != 1) { + /* Process bottom scan line. */ + q = qb[0]; + p = ((q << 2) & 0330); + + y_ptr = ptr + xsize * (ysize - 1); + for (x = 0; x < xsize; x++) { + q = qb[x]; + p = ((p << 1) & 0666) | ((q << 3) & 0110); + if ((i != 2 || x != 0) && (p & m) == 0 && todelete[p]) { + count++; + PIXEL_SET(y_ptr[x], bg_color); + } + } + } + } + LOG("ThinImage: pass %d, %d pixels deleted\n", pc, count); + } + free(qb); +} + +void thin1(at_bitmap * image, unsigned char colour) +{ + unsigned char *ptr, *y_ptr, *y1_ptr; + unsigned char bg_color; + unsigned int xsize, ysize; /* Image resolution */ + unsigned int x, y; /* Pixel location */ + unsigned int i; /* Pass index */ + unsigned int pc = 0; /* Pass count */ + unsigned int count = 1; /* Deleted pixel count */ + unsigned int p, q; /* Neighborhood maps of adjacent */ + /* cells */ + unsigned char *qb; /* Neighborhood maps of previous */ + /* scanline */ + unsigned int m; /* Deletion direction mask */ + + if (background.r == background.g && background.g == background.b) + bg_color = background.r; + else + bg_color = at_color_luminance(&background); + + LOG(" Thinning image.....\n "); + xsize = AT_BITMAP_WIDTH(image); + ysize = AT_BITMAP_HEIGHT(image); + XMALLOC(qb, xsize * sizeof(unsigned char)); + qb[xsize - 1] = 0; /* Used for lower-right pixel */ + ptr = AT_BITMAP_BITS(image); + + while (count) { /* Scan image while deletions */ + pc++; + count = 0; + + for (i = 0; i < 4; i++) { + + m = masks[i]; + + /* Build initial previous scan buffer. */ + p = (ptr[0] == colour); + for (x = 0; x < xsize - 1; x++) + qb[x] = (unsigned char)(p = ((p << 1) & 0006) | (unsigned int)(ptr[x + 1] == colour)); + + /* Scan image for pixel deletion candidates. */ + y_ptr = ptr; + y1_ptr = ptr + xsize; + for (y = 0; y < ysize - 1; y++, y_ptr += xsize, y1_ptr += xsize) { + q = qb[0]; + p = ((q << 2) & 0330) | (y1_ptr[0] == colour); + + for (x = 0; x < xsize - 1; x++) { + q = qb[x]; + p = ((p << 1) & 0666) | ((q << 3) & 0110) | (unsigned int)(y1_ptr[x + 1] == colour); + qb[x] = (unsigned char)p; + if (((p & m) == 0) && todelete[p]) { + count++; + y_ptr[x] = bg_color; /* delete the pixel */ + } + } + + /* Process right edge pixel. */ + p = (p << 1) & 0666; + if ((p & m) == 0 && todelete[p]) { + count++; + y_ptr[xsize - 1] = bg_color; + } + } + + /* Process bottom scan line. */ + q = qb[0]; + p = ((q << 2) & 0330); + + y_ptr = ptr + xsize * (ysize - 1); + for (x = 0; x < xsize; x++) { + q = qb[x]; + p = ((p << 1) & 0666) | ((q << 3) & 0110); + if ((p & m) == 0 && todelete[p]) { + count++; + y_ptr[x] = bg_color; + } + } + } + LOG("thin1: pass %d, %d pixels deleted\n", pc, count); + } + free(qb); +} diff --git a/src/3rdparty/autotrace/thin-image.h b/src/3rdparty/autotrace/thin-image.h new file mode 100644 index 0000000..fdeba2a --- /dev/null +++ b/src/3rdparty/autotrace/thin-image.h @@ -0,0 +1,36 @@ +/* thin-image.h: thin binary image + + Copyright (C) 2001, 2002 Martin Weber + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public License + as published by the Free Software Foundation; either version 2.1 of + the License, or (at your option) any later version. + + This library 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 + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with this library; if not, write to the Free Software + Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 + USA. */ + +#ifndef THIN_IMAGE_H +#define THIN_IMAGE_H + +/* + * C code from the article + * "Efficient Binary Image Thinning using Neighborhood Maps" + * by Joseph M. Cychosz, 3ksnn64@ecn.purdue.edu + * in "Graphics Gems IV", Academic Press, 1994 + */ + +#include "bitmap.h" +#include "color.h" +#include "exception.h" + +void thin_image(at_bitmap * image, const at_color * bg_color, at_exception_type * exp); + +#endif /* not THIN_IMAGE_H */ diff --git a/src/3rdparty/autotrace/types.h b/src/3rdparty/autotrace/types.h new file mode 100644 index 0000000..a7b6843 --- /dev/null +++ b/src/3rdparty/autotrace/types.h @@ -0,0 +1,42 @@ +/* types.h: general types + Copyright (C) 2000, 2001 Martin Weber + + The author can be contacted at <martweb@gmx.net> + + 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 of the License, 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. */ + +#ifndef AT_TYPES_H +#define AT_TYPES_H + +#include <stdint.h> +#include <glib.h> + +#ifdef __cplusplus +extern "C" { +#endif /* __cplusplus */ + +/* Cartesian points. */ + typedef struct _at_coord { + gushort x, y; + } at_coord; + + typedef struct _at_real_coord { + gfloat x, y, z; + } at_real_coord; + +#ifdef __cplusplus +} +#endif /* __cplusplus */ +#endif /* not AT_TYPES_H */ diff --git a/src/3rdparty/autotrace/vector.c b/src/3rdparty/autotrace/vector.c new file mode 100644 index 0000000..2b6375a --- /dev/null +++ b/src/3rdparty/autotrace/vector.c @@ -0,0 +1,260 @@ +/* vector.c: vector/point operations. */ + +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif /* Def: HAVE_CONFIG_H */ + +#include "vector.h" +#include "logreport.h" +#include "epsilon-equal.h" +#include <math.h> +#include <errno.h> +#include <assert.h> +#include <string.h> + +static gfloat acos_d(gfloat, at_exception_type * excep); + +#define _USE_MATH_DEFINES +#include <math.h> + +/* Given the point COORD, return the corresponding vector. */ + +vector_type make_vector(const at_real_coord c) +{ + vector_type v; + + v.dx = c.x; + v.dy = c.y; + v.dz = c.z; + + return v; +} + +/* And the converse: given a vector, return the corresponding point. */ + +at_real_coord vector_to_point(const vector_type v) +{ + at_real_coord coord; + + coord.x = v.dx; + coord.y = v.dy; + + return coord; +} + +gfloat magnitude(const vector_type v) +{ + return (gfloat) sqrt(v.dx * v.dx + v.dy * v.dy + v.dz * v.dz); +} + +vector_type normalize(const vector_type v) +{ + vector_type new_v; + gfloat m = magnitude(v); + + /* assert (m > 0.0); */ + + if (m > 0.0) { + new_v.dx = v.dx / m; + new_v.dy = v.dy / m; + new_v.dz = v.dz / m; + } else { + new_v.dx = v.dx; + new_v.dy = v.dy; + new_v.dz = v.dz; + } + + return new_v; +} + +vector_type Vadd(const vector_type v1, const vector_type v2) +{ + vector_type new_v; + + new_v.dx = v1.dx + v2.dx; + new_v.dy = v1.dy + v2.dy; + new_v.dz = v1.dz + v2.dz; + + return new_v; +} + +gfloat Vdot(const vector_type v1, const vector_type v2) +{ + return v1.dx * v2.dx + v1.dy * v2.dy + v1.dz * v2.dz; +} + +vector_type Vmult_scalar(const vector_type v, const gfloat r) +{ + vector_type new_v; + + new_v.dx = v.dx * r; + new_v.dy = v.dy * r; + new_v.dz = v.dz * r; + + return new_v; +} + +/* Given the IN_VECTOR and OUT_VECTOR, return the angle between them in + degrees, in the range zero to 180. */ + +gfloat Vangle(const vector_type in_vector, const vector_type out_vector, at_exception_type * exp) +{ + vector_type v1 = normalize(in_vector); + vector_type v2 = normalize(out_vector); + + return acos_d(Vdot(v2, v1), exp); +} + +at_real_coord Vadd_point(const at_real_coord c, const vector_type v) +{ + at_real_coord new_c; + + new_c.x = c.x + v.dx; + new_c.y = c.y + v.dy; + new_c.z = c.z + v.dz; + return new_c; +} + +at_real_coord Vsubtract_point(const at_real_coord c, const vector_type v) +{ + at_real_coord new_c; + + new_c.x = c.x - v.dx; + new_c.y = c.y - v.dy; + new_c.z = c.z - v.dz; + return new_c; +} + +at_coord Vadd_int_point(const at_coord c, const vector_type v) +{ + at_coord a; + + a.x = (unsigned short)lround((gfloat) c.x + v.dx); + a.y = (unsigned short)lround((gfloat) c.y + v.dy); + return a; +} + +vector_type Vabs(const vector_type v) +{ + vector_type new_v; + + new_v.dx = (gfloat) fabs(v.dx); + new_v.dy = (gfloat) fabs(v.dy); + new_v.dz = (gfloat) fabs(v.dz); + return new_v; +} + +/* Operations on points. */ + +at_real_coord Padd(const at_real_coord coord1, const at_real_coord coord2) +{ + at_real_coord sum; + + sum.x = coord1.x + coord2.x; + sum.y = coord1.y + coord2.y; + sum.z = coord1.z + coord2.z; + + return sum; +} + +at_real_coord Pmult_scalar(const at_real_coord coord, const gfloat r) +{ + at_real_coord answer; + + answer.x = coord.x * r; + answer.y = coord.y * r; + answer.z = coord.z * r; + + return answer; +} + +vector_type Psubtract(const at_real_coord c1, const at_real_coord c2) +{ + vector_type v; + + v.dx = c1.x - c2.x; + v.dy = c1.y - c2.y; + v.dz = c1.z - c2.z; + + return v; +} + +/* Operations on integer points. */ + +vector_type IPsubtract(const at_coord coord1, const at_coord coord2) +{ + vector_type v; + + v.dx = (gfloat) (coord1.x - coord2.x); + v.dy = (gfloat) (coord1.y - coord2.y); + v.dz = 0.0; + + return v; +} + +at_coord IPsubtractP(const at_coord c1, const at_coord c2) +{ + at_coord c; + + c.x = c1.x - c2.x; + c.y = c1.y - c2.y; + + return c; +} + +at_coord IPadd(const at_coord c1, const at_coord c2) +{ + at_coord c; + + c.x = c1.x + c2.x; + c.y = c1.y + c2.y; + + return c; +} + +at_coord IPmult_scalar(const at_coord c, const int i) +{ + at_coord a; + + a.x = (unsigned short)(c.x * i); + a.y = (unsigned short)(c.y * i); + + return a; +} + +at_real_coord IPmult_real(const at_coord c, const gfloat r) +{ + at_real_coord a; + + a.x = c.x * r; + a.y = c.y * r; + + return a; +} + +gboolean IPequal(const at_coord c1, const at_coord c2) +{ + if ((c1.x == c2.x) && (c1.y == c2.y)) + return TRUE; + else + return FALSE; +} + +static gfloat acos_d(gfloat v, at_exception_type * excep) +{ + gfloat a; + + if (epsilon_equal(v, 1.0)) + v = 1.0; + else if (epsilon_equal(v, -1.0)) + v = -1.0; + + errno = 0; + a = (gfloat) acos(v); + if (errno == ERANGE || errno == EDOM) { + at_exception_fatal(excep, strerror(errno)); + return 0.0; + } + + return a * (gfloat) 180.0 / (gfloat) M_PI; +} diff --git a/src/3rdparty/autotrace/vector.h b/src/3rdparty/autotrace/vector.h new file mode 100644 index 0000000..fe26254 --- /dev/null +++ b/src/3rdparty/autotrace/vector.h @@ -0,0 +1,65 @@ +/* vector.h: operations on vectors and points. */ + +#ifndef VECTOR_H +#define VECTOR_H + +#include "types.h" +#include "exception.h" + +/* Our vectors are represented as displacements along the x and y axes. */ + +typedef struct { + gfloat dx, dy, dz; +} vector_type; + +/* Consider a point as a vector from the origin. */ +extern vector_type make_vector(const at_real_coord); + +/* And a vector as a point, i.e., a displacement from the origin. */ +extern at_real_coord vector_to_point(const vector_type); + +/* Definitions for these common operations can be found in any decent + linear algebra book, and most calculus books. */ + +extern gfloat magnitude(const vector_type); +extern vector_type normalize(const vector_type); + +extern vector_type Vadd(const vector_type, const vector_type); +extern gfloat Vdot(const vector_type, const vector_type); +extern vector_type Vmult_scalar(const vector_type, const gfloat); +extern gfloat Vangle(const vector_type in, const vector_type out, at_exception_type * exp); + +/* These operations could have been named `P..._vector' just as well as + V..._point, so we may as well allow both names. */ +#define Padd_vector Vadd_point +extern at_real_coord Vadd_point(const at_real_coord, const vector_type); + +#define Psubtract_vector Vsubtract_point +extern at_real_coord Vsubtract_point(const at_real_coord, const vector_type); + +/* This returns the rounded sum. */ +#define IPadd_vector Vadd_int_point +extern at_coord Vadd_int_point(const at_coord, const vector_type); + +/* Take the absolute value of both components. */ +extern vector_type Vabs(const vector_type); + +/* Operations on points with real coordinates. It is not orthogonal, + but more convenient, to have the subtraction operator return a + vector, and the addition operator return a point. */ +extern vector_type Psubtract(const at_real_coord, const at_real_coord); + +/* These are heavily used in spline fitting. */ +extern at_real_coord Padd(const at_real_coord, const at_real_coord); +extern at_real_coord Pmult_scalar(const at_real_coord, const gfloat); + +/* Similarly, for points with integer coordinates; here, a subtraction + operator that does return another point is useful. */ +extern vector_type IPsubtract(const at_coord, const at_coord); +extern at_coord IPsubtractP(const at_coord, const at_coord); +extern at_coord IPadd(const at_coord, const at_coord); +extern at_coord IPmult_scalar(const at_coord, const int); +extern at_real_coord IPmult_real(const at_coord, const gfloat); +extern gboolean IPequal(const at_coord, const at_coord); + +#endif /* not VECTOR_H */ diff --git a/src/3rdparty/autotrace/xstd.h b/src/3rdparty/autotrace/xstd.h new file mode 100644 index 0000000..18e4d5b --- /dev/null +++ b/src/3rdparty/autotrace/xstd.h @@ -0,0 +1,81 @@ +/* xstd.h: Wrappers for functions in C standard library + Was: xmem, xfile */ + +/* These call the corresponding function in the standard library, and + abort if those routines fail. */ + +#ifndef XSTD_H +#define XSTD_H + +#include "types.h" +#include <assert.h> +#include <stdlib.h> + +/* + * XMEM + */ +#ifndef __cplusplus +#define XMALLOC(new_mem, size) \ +do \ + { \ + new_mem = (gpointer) malloc (size); \ + assert(new_mem); \ + } while (0) + +#define XCALLOC(new_mem, size) \ +do \ + { \ + new_mem = (gpointer) calloc (size, 1); \ + assert(new_mem); \ + } while (0) + +#define XREALLOC(old_ptr, size) \ +do \ + { \ + gpointer new_mem; \ + \ + if (old_ptr == NULL) \ + XMALLOC (new_mem, size); \ + else \ + { \ + new_mem = (gpointer) realloc (old_ptr, size); \ + assert(new_mem); \ + } \ + \ + old_ptr = new_mem; \ +} while (0) + +#else +/* Use templates if Cplusplus... */ +#define XMALLOC(new_mem, size) \ +do \ + { \ + (gpointer&)(new_mem) = (gpointer) malloc (size); \ + assert(new_mem); \ + } while (0) + +#define XCALLOC(new_mem, sizex) \ +do \ + { \ + (gpointer&)(new_mem) = (void *) calloc (sizex, 1); \ + assert(new_mem); \ + } while (0) + +#define XREALLOC(old_ptr, size) \ +do \ + { \ + gpointer new_mem; \ + \ + if (old_ptr == NULL) \ + XMALLOC (new_mem, (size)); \ + else \ + { \ + (gpointer&) new_mem = (gpointer) realloc ((old_ptr), (size)); \ + assert(new_mem); \ + } \ + \ + (gpointer&)old_ptr = new_mem; \ + } while (0) +#endif + +#endif /* Not XSTD_H */ |