diff options
Diffstat (limited to 'plug-ins/selection-to-path')
24 files changed, 6637 insertions, 0 deletions
diff --git a/plug-ins/selection-to-path/Makefile.am b/plug-ins/selection-to-path/Makefile.am new file mode 100644 index 0000000..e27d85e --- /dev/null +++ b/plug-ins/selection-to-path/Makefile.am @@ -0,0 +1,73 @@ +## Process this file with automake to produce Makefile.in + +if OS_WIN32 +mwindows = -mwindows +else +libm = -lm +endif + +libgimpui = $(top_builddir)/libgimp/libgimpui-$(GIMP_API_VERSION).la +libgimpconfig = $(top_builddir)/libgimpconfig/libgimpconfig-$(GIMP_API_VERSION).la +libgimpwidgets = $(top_builddir)/libgimpwidgets/libgimpwidgets-$(GIMP_API_VERSION).la +libgimp = $(top_builddir)/libgimp/libgimp-$(GIMP_API_VERSION).la +libgimpcolor = $(top_builddir)/libgimpcolor/libgimpcolor-$(GIMP_API_VERSION).la +libgimpbase = $(top_builddir)/libgimpbase/libgimpbase-$(GIMP_API_VERSION).la +libgimpmath = $(top_builddir)/libgimpmath/libgimpmath-$(GIMP_API_VERSION).la + +if HAVE_WINDRES +include $(top_srcdir)/build/windows/gimprc-plug-ins.rule +selection_to_path_RC = selection-to-path.rc.o +endif + +AM_LDFLAGS = $(mwindows) + +libexecdir = $(gimpplugindir)/plug-ins/selection-to-path + +libexec_PROGRAMS = selection-to-path + +selection_to_path_SOURCES = \ + bitmap.h \ + bounding-box.h \ + curve.c \ + curve.h \ + edge.c \ + edge.h \ + fit.c \ + fit.h \ + global.h \ + math.c \ + pxl-outline.c \ + pxl-outline.h \ + selection-to-path.c \ + selection-to-path.h \ + selection-to-path-dialog.c \ + spline.c \ + spline.h \ + types.h \ + vector.c \ + vector.h + +EXTRA_DIST = \ + README \ + README.limn + +AM_CPPFLAGS = \ + -I$(top_srcdir) \ + $(GTK_CFLAGS) \ + $(GEGL_CFLAGS) \ + -I$(includedir) + +LDADD = \ + $(libm) \ + $(libgimpui) \ + $(libgimpwidgets) \ + $(libgimpconfig) \ + $(libgimpmath) \ + $(libgimp) \ + $(libgimpcolor) \ + $(libgimpbase) \ + $(GTK_LIBS) \ + $(GEGL_LIBS) \ + $(RT_LIBS) \ + $(INTLLIBS) \ + $(selection_to_path_RC) diff --git a/plug-ins/selection-to-path/Makefile.in b/plug-ins/selection-to-path/Makefile.in new file mode 100644 index 0000000..2ac5eba --- /dev/null +++ b/plug-ins/selection-to-path/Makefile.in @@ -0,0 +1,1057 @@ +# Makefile.in generated by automake 1.16.3 from Makefile.am. +# @configure_input@ + +# Copyright (C) 1994-2020 Free Software Foundation, Inc. + +# This Makefile.in is free software; the Free Software Foundation +# gives unlimited permission to copy and/or distribute it, +# with or without modifications, as long as this notice is preserved. + +# This program is distributed in the hope that it will be useful, +# but WITHOUT ANY WARRANTY, to the extent permitted by law; without +# even the implied warranty of MERCHANTABILITY or FITNESS FOR A +# PARTICULAR PURPOSE. + +@SET_MAKE@ + +# Version resources for Microsoft Windows + +VPATH = @srcdir@ +am__is_gnu_make = { \ + if test -z '$(MAKELEVEL)'; then \ + false; \ + elif test -n '$(MAKE_HOST)'; then \ + true; \ + elif test -n '$(MAKE_VERSION)' && test -n '$(CURDIR)'; then \ + true; \ + else \ + false; \ + fi; \ +} +am__make_running_with_option = \ + case $${target_option-} in \ + ?) ;; \ + *) echo "am__make_running_with_option: internal error: invalid" \ + "target option '$${target_option-}' specified" >&2; \ + exit 1;; \ + esac; \ + has_opt=no; \ + sane_makeflags=$$MAKEFLAGS; \ + if $(am__is_gnu_make); then \ + sane_makeflags=$$MFLAGS; \ + else \ + case $$MAKEFLAGS in \ + *\\[\ \ ]*) \ + bs=\\; \ + sane_makeflags=`printf '%s\n' "$$MAKEFLAGS" \ + | sed "s/$$bs$$bs[$$bs $$bs ]*//g"`;; \ + esac; \ + fi; \ + skip_next=no; \ + strip_trailopt () \ + { \ + flg=`printf '%s\n' "$$flg" | sed "s/$$1.*$$//"`; \ + }; \ + for flg in $$sane_makeflags; do \ + test $$skip_next = yes && { skip_next=no; continue; }; \ + case $$flg in \ + *=*|--*) continue;; \ + -*I) strip_trailopt 'I'; skip_next=yes;; \ + -*I?*) strip_trailopt 'I';; \ + -*O) strip_trailopt 'O'; skip_next=yes;; \ + -*O?*) strip_trailopt 'O';; \ + -*l) strip_trailopt 'l'; skip_next=yes;; \ + -*l?*) strip_trailopt 'l';; \ + -[dEDm]) skip_next=yes;; \ + -[JT]) skip_next=yes;; \ + esac; \ + case $$flg in \ + *$$target_option*) has_opt=yes; break;; \ + esac; \ + done; \ + test $$has_opt = yes +am__make_dryrun = (target_option=n; $(am__make_running_with_option)) +am__make_keepgoing = (target_option=k; $(am__make_running_with_option)) +pkgdatadir = $(datadir)/@PACKAGE@ +pkgincludedir = $(includedir)/@PACKAGE@ +pkglibdir = $(libdir)/@PACKAGE@ +pkglibexecdir = $(libexecdir)/@PACKAGE@ +am__cd = CDPATH="$${ZSH_VERSION+.}$(PATH_SEPARATOR)" && cd +install_sh_DATA = $(install_sh) -c -m 644 +install_sh_PROGRAM = $(install_sh) -c +install_sh_SCRIPT = $(install_sh) -c +INSTALL_HEADER = $(INSTALL_DATA) +transform = $(program_transform_name) +NORMAL_INSTALL = : +PRE_INSTALL = : +POST_INSTALL = : +NORMAL_UNINSTALL = : +PRE_UNINSTALL = : +POST_UNINSTALL = : +build_triplet = @build@ +host_triplet = @host@ +libexec_PROGRAMS = selection-to-path$(EXEEXT) +subdir = plug-ins/selection-to-path +ACLOCAL_M4 = $(top_srcdir)/aclocal.m4 +am__aclocal_m4_deps = $(top_srcdir)/acinclude.m4 \ + $(top_srcdir)/m4macros/alsa.m4 \ + $(top_srcdir)/m4macros/ax_compare_version.m4 \ + $(top_srcdir)/m4macros/ax_cxx_compile_stdcxx.m4 \ + $(top_srcdir)/m4macros/ax_gcc_func_attribute.m4 \ + $(top_srcdir)/m4macros/ax_prog_cc_for_build.m4 \ + $(top_srcdir)/m4macros/ax_prog_perl_version.m4 \ + $(top_srcdir)/m4macros/detectcflags.m4 \ + $(top_srcdir)/m4macros/pythondev.m4 $(top_srcdir)/configure.ac +am__configure_deps = $(am__aclocal_m4_deps) $(CONFIGURE_DEPENDENCIES) \ + $(ACLOCAL_M4) +DIST_COMMON = $(srcdir)/Makefile.am $(am__DIST_COMMON) +mkinstalldirs = $(install_sh) -d +CONFIG_HEADER = $(top_builddir)/config.h +CONFIG_CLEAN_FILES = +CONFIG_CLEAN_VPATH_FILES = +am__installdirs = "$(DESTDIR)$(libexecdir)" +PROGRAMS = $(libexec_PROGRAMS) +am_selection_to_path_OBJECTS = curve.$(OBJEXT) edge.$(OBJEXT) \ + fit.$(OBJEXT) math.$(OBJEXT) pxl-outline.$(OBJEXT) \ + selection-to-path.$(OBJEXT) selection-to-path-dialog.$(OBJEXT) \ + spline.$(OBJEXT) vector.$(OBJEXT) +selection_to_path_OBJECTS = $(am_selection_to_path_OBJECTS) +selection_to_path_LDADD = $(LDADD) +am__DEPENDENCIES_1 = +selection_to_path_DEPENDENCIES = $(am__DEPENDENCIES_1) $(libgimpui) \ + $(libgimpwidgets) $(libgimpconfig) $(libgimpmath) $(libgimp) \ + $(libgimpcolor) $(libgimpbase) $(am__DEPENDENCIES_1) \ + $(am__DEPENDENCIES_1) $(am__DEPENDENCIES_1) \ + $(am__DEPENDENCIES_1) $(selection_to_path_RC) +AM_V_lt = $(am__v_lt_@AM_V@) +am__v_lt_ = $(am__v_lt_@AM_DEFAULT_V@) +am__v_lt_0 = --silent +am__v_lt_1 = +AM_V_P = $(am__v_P_@AM_V@) +am__v_P_ = $(am__v_P_@AM_DEFAULT_V@) +am__v_P_0 = false +am__v_P_1 = : +AM_V_GEN = $(am__v_GEN_@AM_V@) +am__v_GEN_ = $(am__v_GEN_@AM_DEFAULT_V@) +am__v_GEN_0 = @echo " GEN " $@; +am__v_GEN_1 = +AM_V_at = $(am__v_at_@AM_V@) +am__v_at_ = $(am__v_at_@AM_DEFAULT_V@) +am__v_at_0 = @ +am__v_at_1 = +DEFAULT_INCLUDES = -I.@am__isrc@ -I$(top_builddir) +depcomp = $(SHELL) $(top_srcdir)/depcomp +am__maybe_remake_depfiles = depfiles +am__depfiles_remade = ./$(DEPDIR)/curve.Po ./$(DEPDIR)/edge.Po \ + ./$(DEPDIR)/fit.Po ./$(DEPDIR)/math.Po \ + ./$(DEPDIR)/pxl-outline.Po \ + ./$(DEPDIR)/selection-to-path-dialog.Po \ + ./$(DEPDIR)/selection-to-path.Po ./$(DEPDIR)/spline.Po \ + ./$(DEPDIR)/vector.Po +am__mv = mv -f +COMPILE = $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) \ + $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) +LTCOMPILE = $(LIBTOOL) $(AM_V_lt) --tag=CC $(AM_LIBTOOLFLAGS) \ + $(LIBTOOLFLAGS) --mode=compile $(CC) $(DEFS) \ + $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) \ + $(AM_CFLAGS) $(CFLAGS) +AM_V_CC = $(am__v_CC_@AM_V@) +am__v_CC_ = $(am__v_CC_@AM_DEFAULT_V@) +am__v_CC_0 = @echo " CC " $@; +am__v_CC_1 = +CCLD = $(CC) +LINK = $(LIBTOOL) $(AM_V_lt) --tag=CC $(AM_LIBTOOLFLAGS) \ + $(LIBTOOLFLAGS) --mode=link $(CCLD) $(AM_CFLAGS) $(CFLAGS) \ + $(AM_LDFLAGS) $(LDFLAGS) -o $@ +AM_V_CCLD = $(am__v_CCLD_@AM_V@) +am__v_CCLD_ = $(am__v_CCLD_@AM_DEFAULT_V@) +am__v_CCLD_0 = @echo " CCLD " $@; +am__v_CCLD_1 = +SOURCES = $(selection_to_path_SOURCES) +DIST_SOURCES = $(selection_to_path_SOURCES) +am__can_run_installinfo = \ + case $$AM_UPDATE_INFO_DIR in \ + n|no|NO) false;; \ + *) (install-info --version) >/dev/null 2>&1;; \ + esac +am__tagged_files = $(HEADERS) $(SOURCES) $(TAGS_FILES) $(LISP) +# Read a list of newline-separated strings from the standard input, +# and print each of them once, without duplicates. Input order is +# *not* preserved. +am__uniquify_input = $(AWK) '\ + BEGIN { nonempty = 0; } \ + { items[$$0] = 1; nonempty = 1; } \ + END { if (nonempty) { for (i in items) print i; }; } \ +' +# Make sure the list of sources is unique. This is necessary because, +# e.g., the same source file might be shared among _SOURCES variables +# for different programs/libraries. +am__define_uniq_tagged_files = \ + list='$(am__tagged_files)'; \ + unique=`for i in $$list; do \ + if test -f "$$i"; then echo $$i; else echo $(srcdir)/$$i; fi; \ + done | $(am__uniquify_input)` +ETAGS = etags +CTAGS = ctags +am__DIST_COMMON = $(srcdir)/Makefile.in \ + $(top_srcdir)/build/windows/gimprc-plug-ins.rule \ + $(top_srcdir)/depcomp README +DISTFILES = $(DIST_COMMON) $(DIST_SOURCES) $(TEXINFOS) $(EXTRA_DIST) +AA_LIBS = @AA_LIBS@ +ACLOCAL = @ACLOCAL@ +ALLOCA = @ALLOCA@ +ALL_LINGUAS = @ALL_LINGUAS@ +ALSA_CFLAGS = @ALSA_CFLAGS@ +ALSA_LIBS = @ALSA_LIBS@ +ALTIVEC_EXTRA_CFLAGS = @ALTIVEC_EXTRA_CFLAGS@ +AMTAR = @AMTAR@ +AM_DEFAULT_VERBOSITY = @AM_DEFAULT_VERBOSITY@ +APPSTREAM_UTIL = @APPSTREAM_UTIL@ +AR = @AR@ +AS = @AS@ +ATK_CFLAGS = @ATK_CFLAGS@ +ATK_LIBS = @ATK_LIBS@ +ATK_REQUIRED_VERSION = @ATK_REQUIRED_VERSION@ +AUTOCONF = @AUTOCONF@ +AUTOHEADER = @AUTOHEADER@ +AUTOMAKE = @AUTOMAKE@ +AWK = @AWK@ +BABL_CFLAGS = @BABL_CFLAGS@ +BABL_LIBS = @BABL_LIBS@ +BABL_REQUIRED_VERSION = @BABL_REQUIRED_VERSION@ +BUG_REPORT_URL = @BUG_REPORT_URL@ +BUILD_EXEEXT = @BUILD_EXEEXT@ +BUILD_OBJEXT = @BUILD_OBJEXT@ +BZIP2_LIBS = @BZIP2_LIBS@ +CAIRO_CFLAGS = @CAIRO_CFLAGS@ +CAIRO_LIBS = @CAIRO_LIBS@ +CAIRO_PDF_CFLAGS = @CAIRO_PDF_CFLAGS@ +CAIRO_PDF_LIBS = @CAIRO_PDF_LIBS@ +CAIRO_PDF_REQUIRED_VERSION = @CAIRO_PDF_REQUIRED_VERSION@ +CAIRO_REQUIRED_VERSION = @CAIRO_REQUIRED_VERSION@ +CATALOGS = @CATALOGS@ +CATOBJEXT = @CATOBJEXT@ +CC = @CC@ +CCAS = @CCAS@ +CCASDEPMODE = @CCASDEPMODE@ +CCASFLAGS = @CCASFLAGS@ +CCDEPMODE = @CCDEPMODE@ +CC_FOR_BUILD = @CC_FOR_BUILD@ +CC_VERSION = @CC_VERSION@ +CFLAGS = @CFLAGS@ +CFLAGS_FOR_BUILD = @CFLAGS_FOR_BUILD@ +CPP = @CPP@ +CPPFLAGS = @CPPFLAGS@ +CPPFLAGS_FOR_BUILD = @CPPFLAGS_FOR_BUILD@ +CPP_FOR_BUILD = @CPP_FOR_BUILD@ +CXX = @CXX@ +CXXCPP = @CXXCPP@ +CXXDEPMODE = @CXXDEPMODE@ +CXXFLAGS = @CXXFLAGS@ +CYGPATH_W = @CYGPATH_W@ +DATADIRNAME = @DATADIRNAME@ +DEFS = @DEFS@ +DEPDIR = @DEPDIR@ +DESKTOP_DATADIR = @DESKTOP_DATADIR@ +DESKTOP_FILE_VALIDATE = @DESKTOP_FILE_VALIDATE@ +DLLTOOL = @DLLTOOL@ +DOC_SHOOTER = @DOC_SHOOTER@ +DSYMUTIL = @DSYMUTIL@ +DUMPBIN = @DUMPBIN@ +ECHO_C = @ECHO_C@ +ECHO_N = @ECHO_N@ +ECHO_T = @ECHO_T@ +EGREP = @EGREP@ +EXEEXT = @EXEEXT@ +FGREP = @FGREP@ +FILE_AA = @FILE_AA@ +FILE_EXR = @FILE_EXR@ +FILE_HEIF = @FILE_HEIF@ +FILE_JP2_LOAD = @FILE_JP2_LOAD@ +FILE_JPEGXL = @FILE_JPEGXL@ +FILE_MNG = @FILE_MNG@ +FILE_PDF_SAVE = @FILE_PDF_SAVE@ +FILE_PS = @FILE_PS@ +FILE_WMF = @FILE_WMF@ +FILE_XMC = @FILE_XMC@ +FILE_XPM = @FILE_XPM@ +FONTCONFIG_CFLAGS = @FONTCONFIG_CFLAGS@ +FONTCONFIG_LIBS = @FONTCONFIG_LIBS@ +FONTCONFIG_REQUIRED_VERSION = @FONTCONFIG_REQUIRED_VERSION@ +FREETYPE2_REQUIRED_VERSION = @FREETYPE2_REQUIRED_VERSION@ +FREETYPE_CFLAGS = @FREETYPE_CFLAGS@ +FREETYPE_LIBS = @FREETYPE_LIBS@ +GDBUS_CODEGEN = @GDBUS_CODEGEN@ +GDK_PIXBUF_CFLAGS = @GDK_PIXBUF_CFLAGS@ +GDK_PIXBUF_CSOURCE = @GDK_PIXBUF_CSOURCE@ +GDK_PIXBUF_LIBS = @GDK_PIXBUF_LIBS@ +GDK_PIXBUF_REQUIRED_VERSION = @GDK_PIXBUF_REQUIRED_VERSION@ +GEGL = @GEGL@ +GEGL_CFLAGS = @GEGL_CFLAGS@ +GEGL_LIBS = @GEGL_LIBS@ +GEGL_MAJOR_MINOR_VERSION = @GEGL_MAJOR_MINOR_VERSION@ +GEGL_REQUIRED_VERSION = @GEGL_REQUIRED_VERSION@ +GETTEXT_PACKAGE = @GETTEXT_PACKAGE@ +GEXIV2_CFLAGS = @GEXIV2_CFLAGS@ +GEXIV2_LIBS = @GEXIV2_LIBS@ +GEXIV2_REQUIRED_VERSION = @GEXIV2_REQUIRED_VERSION@ +GIMP_API_VERSION = @GIMP_API_VERSION@ +GIMP_APP_VERSION = @GIMP_APP_VERSION@ +GIMP_BINARY_AGE = @GIMP_BINARY_AGE@ +GIMP_COMMAND = @GIMP_COMMAND@ +GIMP_DATA_VERSION = @GIMP_DATA_VERSION@ +GIMP_FULL_NAME = @GIMP_FULL_NAME@ +GIMP_INTERFACE_AGE = @GIMP_INTERFACE_AGE@ +GIMP_MAJOR_VERSION = @GIMP_MAJOR_VERSION@ +GIMP_MICRO_VERSION = @GIMP_MICRO_VERSION@ +GIMP_MINOR_VERSION = @GIMP_MINOR_VERSION@ +GIMP_MKENUMS = @GIMP_MKENUMS@ +GIMP_MODULES = @GIMP_MODULES@ +GIMP_PACKAGE_REVISION = @GIMP_PACKAGE_REVISION@ +GIMP_PKGCONFIG_VERSION = @GIMP_PKGCONFIG_VERSION@ +GIMP_PLUGINS = @GIMP_PLUGINS@ +GIMP_PLUGIN_VERSION = @GIMP_PLUGIN_VERSION@ +GIMP_REAL_VERSION = @GIMP_REAL_VERSION@ +GIMP_RELEASE = @GIMP_RELEASE@ +GIMP_SYSCONF_VERSION = @GIMP_SYSCONF_VERSION@ +GIMP_TOOL_VERSION = @GIMP_TOOL_VERSION@ +GIMP_UNSTABLE = @GIMP_UNSTABLE@ +GIMP_USER_VERSION = @GIMP_USER_VERSION@ +GIMP_VERSION = @GIMP_VERSION@ +GIO_CFLAGS = @GIO_CFLAGS@ +GIO_LIBS = @GIO_LIBS@ +GIO_UNIX_CFLAGS = @GIO_UNIX_CFLAGS@ +GIO_UNIX_LIBS = @GIO_UNIX_LIBS@ +GIO_WINDOWS_CFLAGS = @GIO_WINDOWS_CFLAGS@ +GIO_WINDOWS_LIBS = @GIO_WINDOWS_LIBS@ +GLIB_CFLAGS = @GLIB_CFLAGS@ +GLIB_COMPILE_RESOURCES = @GLIB_COMPILE_RESOURCES@ +GLIB_GENMARSHAL = @GLIB_GENMARSHAL@ +GLIB_LIBS = @GLIB_LIBS@ +GLIB_MKENUMS = @GLIB_MKENUMS@ +GLIB_REQUIRED_VERSION = @GLIB_REQUIRED_VERSION@ +GMODULE_NO_EXPORT_CFLAGS = @GMODULE_NO_EXPORT_CFLAGS@ +GMODULE_NO_EXPORT_LIBS = @GMODULE_NO_EXPORT_LIBS@ +GMOFILES = @GMOFILES@ +GMSGFMT = @GMSGFMT@ +GOBJECT_QUERY = @GOBJECT_QUERY@ +GREP = @GREP@ +GS_LIBS = @GS_LIBS@ +GTKDOC_CHECK = @GTKDOC_CHECK@ +GTKDOC_CHECK_PATH = @GTKDOC_CHECK_PATH@ +GTKDOC_DEPS_CFLAGS = @GTKDOC_DEPS_CFLAGS@ +GTKDOC_DEPS_LIBS = @GTKDOC_DEPS_LIBS@ +GTKDOC_MKPDF = @GTKDOC_MKPDF@ +GTKDOC_REBASE = @GTKDOC_REBASE@ +GTK_CFLAGS = @GTK_CFLAGS@ +GTK_LIBS = @GTK_LIBS@ +GTK_MAC_INTEGRATION_CFLAGS = @GTK_MAC_INTEGRATION_CFLAGS@ +GTK_MAC_INTEGRATION_LIBS = @GTK_MAC_INTEGRATION_LIBS@ +GTK_REQUIRED_VERSION = @GTK_REQUIRED_VERSION@ +GTK_UPDATE_ICON_CACHE = @GTK_UPDATE_ICON_CACHE@ +GUDEV_CFLAGS = @GUDEV_CFLAGS@ +GUDEV_LIBS = @GUDEV_LIBS@ +HARFBUZZ_CFLAGS = @HARFBUZZ_CFLAGS@ +HARFBUZZ_LIBS = @HARFBUZZ_LIBS@ +HARFBUZZ_REQUIRED_VERSION = @HARFBUZZ_REQUIRED_VERSION@ +HAVE_CXX14 = @HAVE_CXX14@ +HAVE_FINITE = @HAVE_FINITE@ +HAVE_ISFINITE = @HAVE_ISFINITE@ +HAVE_VFORK = @HAVE_VFORK@ +HOST_GLIB_COMPILE_RESOURCES = @HOST_GLIB_COMPILE_RESOURCES@ +HTML_DIR = @HTML_DIR@ +INSTALL = @INSTALL@ +INSTALL_DATA = @INSTALL_DATA@ +INSTALL_PROGRAM = @INSTALL_PROGRAM@ +INSTALL_SCRIPT = @INSTALL_SCRIPT@ +INSTALL_STRIP_PROGRAM = @INSTALL_STRIP_PROGRAM@ +INSTOBJEXT = @INSTOBJEXT@ +INTLLIBS = @INTLLIBS@ +INTLTOOL_EXTRACT = @INTLTOOL_EXTRACT@ +INTLTOOL_MERGE = @INTLTOOL_MERGE@ +INTLTOOL_PERL = @INTLTOOL_PERL@ +INTLTOOL_REQUIRED_VERSION = @INTLTOOL_REQUIRED_VERSION@ +INTLTOOL_UPDATE = @INTLTOOL_UPDATE@ +INTLTOOL_V_MERGE = @INTLTOOL_V_MERGE@ +INTLTOOL_V_MERGE_OPTIONS = @INTLTOOL_V_MERGE_OPTIONS@ +INTLTOOL__v_MERGE_ = @INTLTOOL__v_MERGE_@ +INTLTOOL__v_MERGE_0 = @INTLTOOL__v_MERGE_0@ +INTL_MACOSX_LIBS = @INTL_MACOSX_LIBS@ +ISO_CODES_LOCALEDIR = @ISO_CODES_LOCALEDIR@ +ISO_CODES_LOCATION = @ISO_CODES_LOCATION@ +JPEG_LIBS = @JPEG_LIBS@ +JSON_GLIB_CFLAGS = @JSON_GLIB_CFLAGS@ +JSON_GLIB_LIBS = @JSON_GLIB_LIBS@ +JXL_CFLAGS = @JXL_CFLAGS@ +JXL_LIBS = @JXL_LIBS@ +JXL_THREADS_CFLAGS = @JXL_THREADS_CFLAGS@ +JXL_THREADS_LIBS = @JXL_THREADS_LIBS@ +LCMS_CFLAGS = @LCMS_CFLAGS@ +LCMS_LIBS = @LCMS_LIBS@ +LCMS_REQUIRED_VERSION = @LCMS_REQUIRED_VERSION@ +LD = @LD@ +LDFLAGS = @LDFLAGS@ +LDFLAGS_FOR_BUILD = @LDFLAGS_FOR_BUILD@ +LIBBACKTRACE_LIBS = @LIBBACKTRACE_LIBS@ +LIBHEIF_CFLAGS = @LIBHEIF_CFLAGS@ +LIBHEIF_LIBS = @LIBHEIF_LIBS@ +LIBHEIF_REQUIRED_VERSION = @LIBHEIF_REQUIRED_VERSION@ +LIBJXL_REQUIRED_VERSION = @LIBJXL_REQUIRED_VERSION@ +LIBLZMA_REQUIRED_VERSION = @LIBLZMA_REQUIRED_VERSION@ +LIBMYPAINT_CFLAGS = @LIBMYPAINT_CFLAGS@ +LIBMYPAINT_LIBS = @LIBMYPAINT_LIBS@ +LIBMYPAINT_REQUIRED_VERSION = @LIBMYPAINT_REQUIRED_VERSION@ +LIBOBJS = @LIBOBJS@ +LIBPNG_REQUIRED_VERSION = @LIBPNG_REQUIRED_VERSION@ +LIBS = @LIBS@ +LIBTOOL = @LIBTOOL@ +LIBUNWIND_CFLAGS = @LIBUNWIND_CFLAGS@ +LIBUNWIND_LIBS = @LIBUNWIND_LIBS@ +LIBUNWIND_REQUIRED_VERSION = @LIBUNWIND_REQUIRED_VERSION@ +LIPO = @LIPO@ +LN_S = @LN_S@ +LTLIBOBJS = @LTLIBOBJS@ +LT_CURRENT_MINUS_AGE = @LT_CURRENT_MINUS_AGE@ +LT_SYS_LIBRARY_PATH = @LT_SYS_LIBRARY_PATH@ +LT_VERSION_INFO = @LT_VERSION_INFO@ +LZMA_CFLAGS = @LZMA_CFLAGS@ +LZMA_LIBS = @LZMA_LIBS@ +MAIL = @MAIL@ +MAINT = @MAINT@ +MAKEINFO = @MAKEINFO@ +MANIFEST_TOOL = @MANIFEST_TOOL@ +MIME_INFO_CFLAGS = @MIME_INFO_CFLAGS@ +MIME_INFO_LIBS = @MIME_INFO_LIBS@ +MIME_TYPES = @MIME_TYPES@ +MKDIR_P = @MKDIR_P@ +MKINSTALLDIRS = @MKINSTALLDIRS@ +MMX_EXTRA_CFLAGS = @MMX_EXTRA_CFLAGS@ +MNG_CFLAGS = @MNG_CFLAGS@ +MNG_LIBS = @MNG_LIBS@ +MSGFMT = @MSGFMT@ +MSGFMT_OPTS = @MSGFMT_OPTS@ +MSGMERGE = @MSGMERGE@ +MYPAINT_BRUSHES_CFLAGS = @MYPAINT_BRUSHES_CFLAGS@ +MYPAINT_BRUSHES_LIBS = @MYPAINT_BRUSHES_LIBS@ +NATIVE_GLIB_CFLAGS = @NATIVE_GLIB_CFLAGS@ +NATIVE_GLIB_LIBS = @NATIVE_GLIB_LIBS@ +NM = @NM@ +NMEDIT = @NMEDIT@ +OBJDUMP = @OBJDUMP@ +OBJEXT = @OBJEXT@ +OPENEXR_CFLAGS = @OPENEXR_CFLAGS@ +OPENEXR_LIBS = @OPENEXR_LIBS@ +OPENEXR_REQUIRED_VERSION = @OPENEXR_REQUIRED_VERSION@ +OPENJPEG_CFLAGS = @OPENJPEG_CFLAGS@ +OPENJPEG_LIBS = @OPENJPEG_LIBS@ +OPENJPEG_REQUIRED_VERSION = @OPENJPEG_REQUIRED_VERSION@ +OTOOL = @OTOOL@ +OTOOL64 = @OTOOL64@ +PACKAGE = @PACKAGE@ +PACKAGE_BUGREPORT = @PACKAGE_BUGREPORT@ +PACKAGE_NAME = @PACKAGE_NAME@ +PACKAGE_STRING = @PACKAGE_STRING@ +PACKAGE_TARNAME = @PACKAGE_TARNAME@ +PACKAGE_URL = @PACKAGE_URL@ +PACKAGE_VERSION = @PACKAGE_VERSION@ +PANGOCAIRO_CFLAGS = @PANGOCAIRO_CFLAGS@ +PANGOCAIRO_LIBS = @PANGOCAIRO_LIBS@ +PANGOCAIRO_REQUIRED_VERSION = @PANGOCAIRO_REQUIRED_VERSION@ +PATHSEP = @PATHSEP@ +PATH_SEPARATOR = @PATH_SEPARATOR@ +PERL = @PERL@ +PERL_REQUIRED_VERSION = @PERL_REQUIRED_VERSION@ +PERL_VERSION = @PERL_VERSION@ +PKG_CONFIG = @PKG_CONFIG@ +PKG_CONFIG_LIBDIR = @PKG_CONFIG_LIBDIR@ +PKG_CONFIG_PATH = @PKG_CONFIG_PATH@ +PNG_CFLAGS = @PNG_CFLAGS@ +PNG_LIBS = @PNG_LIBS@ +POFILES = @POFILES@ +POPPLER_CFLAGS = @POPPLER_CFLAGS@ +POPPLER_DATA_CFLAGS = @POPPLER_DATA_CFLAGS@ +POPPLER_DATA_LIBS = @POPPLER_DATA_LIBS@ +POPPLER_DATA_REQUIRED_VERSION = @POPPLER_DATA_REQUIRED_VERSION@ +POPPLER_LIBS = @POPPLER_LIBS@ +POPPLER_REQUIRED_VERSION = @POPPLER_REQUIRED_VERSION@ +POSUB = @POSUB@ +PO_IN_DATADIR_FALSE = @PO_IN_DATADIR_FALSE@ +PO_IN_DATADIR_TRUE = @PO_IN_DATADIR_TRUE@ +PYBIN_PATH = @PYBIN_PATH@ +PYCAIRO_CFLAGS = @PYCAIRO_CFLAGS@ +PYCAIRO_LIBS = @PYCAIRO_LIBS@ +PYGIMP_EXTRA_CFLAGS = @PYGIMP_EXTRA_CFLAGS@ +PYGTK_CFLAGS = @PYGTK_CFLAGS@ +PYGTK_CODEGEN = @PYGTK_CODEGEN@ +PYGTK_DEFSDIR = @PYGTK_DEFSDIR@ +PYGTK_LIBS = @PYGTK_LIBS@ +PYLINK_LIBS = @PYLINK_LIBS@ +PYTHON = @PYTHON@ +PYTHON2_REQUIRED_VERSION = @PYTHON2_REQUIRED_VERSION@ +PYTHON_EXEC_PREFIX = @PYTHON_EXEC_PREFIX@ +PYTHON_INCLUDES = @PYTHON_INCLUDES@ +PYTHON_PLATFORM = @PYTHON_PLATFORM@ +PYTHON_PREFIX = @PYTHON_PREFIX@ +PYTHON_VERSION = @PYTHON_VERSION@ +RANLIB = @RANLIB@ +RSVG_REQUIRED_VERSION = @RSVG_REQUIRED_VERSION@ +RT_LIBS = @RT_LIBS@ +SCREENSHOT_LIBS = @SCREENSHOT_LIBS@ +SED = @SED@ +SENDMAIL = @SENDMAIL@ +SET_MAKE = @SET_MAKE@ +SHELL = @SHELL@ +SOCKET_LIBS = @SOCKET_LIBS@ +SSE2_EXTRA_CFLAGS = @SSE2_EXTRA_CFLAGS@ +SSE4_1_EXTRA_CFLAGS = @SSE4_1_EXTRA_CFLAGS@ +SSE_EXTRA_CFLAGS = @SSE_EXTRA_CFLAGS@ +STRIP = @STRIP@ +SVG_CFLAGS = @SVG_CFLAGS@ +SVG_LIBS = @SVG_LIBS@ +SYMPREFIX = @SYMPREFIX@ +TIFF_LIBS = @TIFF_LIBS@ +USE_NLS = @USE_NLS@ +VERSION = @VERSION@ +WEBKIT_CFLAGS = @WEBKIT_CFLAGS@ +WEBKIT_LIBS = @WEBKIT_LIBS@ +WEBKIT_REQUIRED_VERSION = @WEBKIT_REQUIRED_VERSION@ +WEBPDEMUX_CFLAGS = @WEBPDEMUX_CFLAGS@ +WEBPDEMUX_LIBS = @WEBPDEMUX_LIBS@ +WEBPMUX_CFLAGS = @WEBPMUX_CFLAGS@ +WEBPMUX_LIBS = @WEBPMUX_LIBS@ +WEBP_CFLAGS = @WEBP_CFLAGS@ +WEBP_LIBS = @WEBP_LIBS@ +WEBP_REQUIRED_VERSION = @WEBP_REQUIRED_VERSION@ +WEB_PAGE = @WEB_PAGE@ +WIN32_LARGE_ADDRESS_AWARE = @WIN32_LARGE_ADDRESS_AWARE@ +WINDRES = @WINDRES@ +WMF_CFLAGS = @WMF_CFLAGS@ +WMF_CONFIG = @WMF_CONFIG@ +WMF_LIBS = @WMF_LIBS@ +WMF_REQUIRED_VERSION = @WMF_REQUIRED_VERSION@ +XDG_EMAIL = @XDG_EMAIL@ +XFIXES_CFLAGS = @XFIXES_CFLAGS@ +XFIXES_LIBS = @XFIXES_LIBS@ +XGETTEXT = @XGETTEXT@ +XGETTEXT_REQUIRED_VERSION = @XGETTEXT_REQUIRED_VERSION@ +XMC_CFLAGS = @XMC_CFLAGS@ +XMC_LIBS = @XMC_LIBS@ +XMKMF = @XMKMF@ +XMLLINT = @XMLLINT@ +XMU_LIBS = @XMU_LIBS@ +XPM_LIBS = @XPM_LIBS@ +XSLTPROC = @XSLTPROC@ +XVFB_RUN = @XVFB_RUN@ +X_CFLAGS = @X_CFLAGS@ +X_EXTRA_LIBS = @X_EXTRA_LIBS@ +X_LIBS = @X_LIBS@ +X_PRE_LIBS = @X_PRE_LIBS@ +Z_LIBS = @Z_LIBS@ +abs_builddir = @abs_builddir@ +abs_srcdir = @abs_srcdir@ +abs_top_builddir = @abs_top_builddir@ +abs_top_srcdir = @abs_top_srcdir@ +ac_ct_AR = @ac_ct_AR@ +ac_ct_CC = @ac_ct_CC@ +ac_ct_CC_FOR_BUILD = @ac_ct_CC_FOR_BUILD@ +ac_ct_CXX = @ac_ct_CXX@ +ac_ct_DUMPBIN = @ac_ct_DUMPBIN@ +am__include = @am__include@ +am__leading_dot = @am__leading_dot@ +am__quote = @am__quote@ +am__tar = @am__tar@ +am__untar = @am__untar@ +bindir = @bindir@ +build = @build@ +build_alias = @build_alias@ +build_cpu = @build_cpu@ +build_os = @build_os@ +build_vendor = @build_vendor@ +builddir = @builddir@ +datadir = @datadir@ +datarootdir = @datarootdir@ +docdir = @docdir@ +dvidir = @dvidir@ +exec_prefix = @exec_prefix@ +gimpdatadir = @gimpdatadir@ +gimpdir = @gimpdir@ +gimplocaledir = @gimplocaledir@ +gimpplugindir = @gimpplugindir@ +gimpsysconfdir = @gimpsysconfdir@ +host = @host@ +host_alias = @host_alias@ +host_cpu = @host_cpu@ +host_os = @host_os@ +host_vendor = @host_vendor@ +htmldir = @htmldir@ +includedir = @includedir@ +infodir = @infodir@ +install_sh = @install_sh@ +intltool__v_merge_options_ = @intltool__v_merge_options_@ +intltool__v_merge_options_0 = @intltool__v_merge_options_0@ +libdir = @libdir@ +libexecdir = $(gimpplugindir)/plug-ins/selection-to-path +localedir = @localedir@ +localstatedir = @localstatedir@ +mandir = @mandir@ +manpage_gimpdir = @manpage_gimpdir@ +mkdir_p = @mkdir_p@ +ms_librarian = @ms_librarian@ +mypaint_brushes_dir = @mypaint_brushes_dir@ +oldincludedir = @oldincludedir@ +pdfdir = @pdfdir@ +pkgpyexecdir = @pkgpyexecdir@ +pkgpythondir = @pkgpythondir@ +prefix = @prefix@ +program_transform_name = @program_transform_name@ +psdir = @psdir@ +pyexecdir = @pyexecdir@ +pythondir = @pythondir@ +runstatedir = @runstatedir@ +sbindir = @sbindir@ +sharedstatedir = @sharedstatedir@ +srcdir = @srcdir@ +sysconfdir = @sysconfdir@ +target_alias = @target_alias@ +top_build_prefix = @top_build_prefix@ +top_builddir = @top_builddir@ +top_srcdir = @top_srcdir@ +@OS_WIN32_TRUE@mwindows = -mwindows +@OS_WIN32_FALSE@libm = -lm +libgimpui = $(top_builddir)/libgimp/libgimpui-$(GIMP_API_VERSION).la +libgimpconfig = $(top_builddir)/libgimpconfig/libgimpconfig-$(GIMP_API_VERSION).la +libgimpwidgets = $(top_builddir)/libgimpwidgets/libgimpwidgets-$(GIMP_API_VERSION).la +libgimp = $(top_builddir)/libgimp/libgimp-$(GIMP_API_VERSION).la +libgimpcolor = $(top_builddir)/libgimpcolor/libgimpcolor-$(GIMP_API_VERSION).la +libgimpbase = $(top_builddir)/libgimpbase/libgimpbase-$(GIMP_API_VERSION).la +libgimpmath = $(top_builddir)/libgimpmath/libgimpmath-$(GIMP_API_VERSION).la +@HAVE_WINDRES_TRUE@GIMPPLUGINRC = $(top_builddir)/build/windows/gimp-plug-ins.rc +@HAVE_WINDRES_TRUE@selection_to_path_RC = selection-to-path.rc.o +AM_LDFLAGS = $(mwindows) +selection_to_path_SOURCES = \ + bitmap.h \ + bounding-box.h \ + curve.c \ + curve.h \ + edge.c \ + edge.h \ + fit.c \ + fit.h \ + global.h \ + math.c \ + pxl-outline.c \ + pxl-outline.h \ + selection-to-path.c \ + selection-to-path.h \ + selection-to-path-dialog.c \ + spline.c \ + spline.h \ + types.h \ + vector.c \ + vector.h + +EXTRA_DIST = \ + README \ + README.limn + +AM_CPPFLAGS = \ + -I$(top_srcdir) \ + $(GTK_CFLAGS) \ + $(GEGL_CFLAGS) \ + -I$(includedir) + +LDADD = \ + $(libm) \ + $(libgimpui) \ + $(libgimpwidgets) \ + $(libgimpconfig) \ + $(libgimpmath) \ + $(libgimp) \ + $(libgimpcolor) \ + $(libgimpbase) \ + $(GTK_LIBS) \ + $(GEGL_LIBS) \ + $(RT_LIBS) \ + $(INTLLIBS) \ + $(selection_to_path_RC) + +all: all-am + +.SUFFIXES: +.SUFFIXES: .c .lo .o .obj +$(srcdir)/Makefile.in: @MAINTAINER_MODE_TRUE@ $(srcdir)/Makefile.am $(top_srcdir)/build/windows/gimprc-plug-ins.rule $(am__configure_deps) + @for dep in $?; do \ + case '$(am__configure_deps)' in \ + *$$dep*) \ + ( cd $(top_builddir) && $(MAKE) $(AM_MAKEFLAGS) am--refresh ) \ + && { if test -f $@; then exit 0; else break; fi; }; \ + exit 1;; \ + esac; \ + done; \ + echo ' cd $(top_srcdir) && $(AUTOMAKE) --gnu plug-ins/selection-to-path/Makefile'; \ + $(am__cd) $(top_srcdir) && \ + $(AUTOMAKE) --gnu plug-ins/selection-to-path/Makefile +Makefile: $(srcdir)/Makefile.in $(top_builddir)/config.status + @case '$?' in \ + *config.status*) \ + cd $(top_builddir) && $(MAKE) $(AM_MAKEFLAGS) am--refresh;; \ + *) \ + echo ' cd $(top_builddir) && $(SHELL) ./config.status $(subdir)/$@ $(am__maybe_remake_depfiles)'; \ + cd $(top_builddir) && $(SHELL) ./config.status $(subdir)/$@ $(am__maybe_remake_depfiles);; \ + esac; +$(top_srcdir)/build/windows/gimprc-plug-ins.rule $(am__empty): + +$(top_builddir)/config.status: $(top_srcdir)/configure $(CONFIG_STATUS_DEPENDENCIES) + cd $(top_builddir) && $(MAKE) $(AM_MAKEFLAGS) am--refresh + +$(top_srcdir)/configure: @MAINTAINER_MODE_TRUE@ $(am__configure_deps) + cd $(top_builddir) && $(MAKE) $(AM_MAKEFLAGS) am--refresh +$(ACLOCAL_M4): @MAINTAINER_MODE_TRUE@ $(am__aclocal_m4_deps) + cd $(top_builddir) && $(MAKE) $(AM_MAKEFLAGS) am--refresh +$(am__aclocal_m4_deps): +install-libexecPROGRAMS: $(libexec_PROGRAMS) + @$(NORMAL_INSTALL) + @list='$(libexec_PROGRAMS)'; test -n "$(libexecdir)" || list=; \ + if test -n "$$list"; then \ + echo " $(MKDIR_P) '$(DESTDIR)$(libexecdir)'"; \ + $(MKDIR_P) "$(DESTDIR)$(libexecdir)" || exit 1; \ + fi; \ + for p in $$list; do echo "$$p $$p"; done | \ + sed 's/$(EXEEXT)$$//' | \ + while read p p1; do if test -f $$p \ + || test -f $$p1 \ + ; then echo "$$p"; echo "$$p"; else :; fi; \ + done | \ + sed -e 'p;s,.*/,,;n;h' \ + -e 's|.*|.|' \ + -e 'p;x;s,.*/,,;s/$(EXEEXT)$$//;$(transform);s/$$/$(EXEEXT)/' | \ + sed 'N;N;N;s,\n, ,g' | \ + $(AWK) 'BEGIN { files["."] = ""; dirs["."] = 1 } \ + { d=$$3; if (dirs[d] != 1) { print "d", d; dirs[d] = 1 } \ + if ($$2 == $$4) files[d] = files[d] " " $$1; \ + else { print "f", $$3 "/" $$4, $$1; } } \ + END { for (d in files) print "f", d, files[d] }' | \ + while read type dir files; do \ + if test "$$dir" = .; then dir=; else dir=/$$dir; fi; \ + test -z "$$files" || { \ + echo " $(INSTALL_PROGRAM_ENV) $(LIBTOOL) $(AM_LIBTOOLFLAGS) $(LIBTOOLFLAGS) --mode=install $(INSTALL_PROGRAM) $$files '$(DESTDIR)$(libexecdir)$$dir'"; \ + $(INSTALL_PROGRAM_ENV) $(LIBTOOL) $(AM_LIBTOOLFLAGS) $(LIBTOOLFLAGS) --mode=install $(INSTALL_PROGRAM) $$files "$(DESTDIR)$(libexecdir)$$dir" || exit $$?; \ + } \ + ; done + +uninstall-libexecPROGRAMS: + @$(NORMAL_UNINSTALL) + @list='$(libexec_PROGRAMS)'; test -n "$(libexecdir)" || list=; \ + files=`for p in $$list; do echo "$$p"; done | \ + sed -e 'h;s,^.*/,,;s/$(EXEEXT)$$//;$(transform)' \ + -e 's/$$/$(EXEEXT)/' \ + `; \ + test -n "$$list" || exit 0; \ + echo " ( cd '$(DESTDIR)$(libexecdir)' && rm -f" $$files ")"; \ + cd "$(DESTDIR)$(libexecdir)" && rm -f $$files + +clean-libexecPROGRAMS: + @list='$(libexec_PROGRAMS)'; test -n "$$list" || exit 0; \ + echo " rm -f" $$list; \ + rm -f $$list || exit $$?; \ + test -n "$(EXEEXT)" || exit 0; \ + list=`for p in $$list; do echo "$$p"; done | sed 's/$(EXEEXT)$$//'`; \ + echo " rm -f" $$list; \ + rm -f $$list + +selection-to-path$(EXEEXT): $(selection_to_path_OBJECTS) $(selection_to_path_DEPENDENCIES) $(EXTRA_selection_to_path_DEPENDENCIES) + @rm -f selection-to-path$(EXEEXT) + $(AM_V_CCLD)$(LINK) $(selection_to_path_OBJECTS) $(selection_to_path_LDADD) $(LIBS) + +mostlyclean-compile: + -rm -f *.$(OBJEXT) + +distclean-compile: + -rm -f *.tab.c + +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/curve.Po@am__quote@ # am--include-marker +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/edge.Po@am__quote@ # am--include-marker +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/fit.Po@am__quote@ # am--include-marker +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/math.Po@am__quote@ # am--include-marker +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/pxl-outline.Po@am__quote@ # am--include-marker +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/selection-to-path-dialog.Po@am__quote@ # am--include-marker +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/selection-to-path.Po@am__quote@ # am--include-marker +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/spline.Po@am__quote@ # am--include-marker +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/vector.Po@am__quote@ # am--include-marker + +$(am__depfiles_remade): + @$(MKDIR_P) $(@D) + @echo '# dummy' >$@-t && $(am__mv) $@-t $@ + +am--depfiles: $(am__depfiles_remade) + +.c.o: +@am__fastdepCC_TRUE@ $(AM_V_CC)$(COMPILE) -MT $@ -MD -MP -MF $(DEPDIR)/$*.Tpo -c -o $@ $< +@am__fastdepCC_TRUE@ $(AM_V_at)$(am__mv) $(DEPDIR)/$*.Tpo $(DEPDIR)/$*.Po +@AMDEP_TRUE@@am__fastdepCC_FALSE@ $(AM_V_CC)source='$<' object='$@' libtool=no @AMDEPBACKSLASH@ +@AMDEP_TRUE@@am__fastdepCC_FALSE@ DEPDIR=$(DEPDIR) $(CCDEPMODE) $(depcomp) @AMDEPBACKSLASH@ +@am__fastdepCC_FALSE@ $(AM_V_CC@am__nodep@)$(COMPILE) -c -o $@ $< + +.c.obj: +@am__fastdepCC_TRUE@ $(AM_V_CC)$(COMPILE) -MT $@ -MD -MP -MF $(DEPDIR)/$*.Tpo -c -o $@ `$(CYGPATH_W) '$<'` +@am__fastdepCC_TRUE@ $(AM_V_at)$(am__mv) $(DEPDIR)/$*.Tpo $(DEPDIR)/$*.Po +@AMDEP_TRUE@@am__fastdepCC_FALSE@ $(AM_V_CC)source='$<' object='$@' libtool=no @AMDEPBACKSLASH@ +@AMDEP_TRUE@@am__fastdepCC_FALSE@ DEPDIR=$(DEPDIR) $(CCDEPMODE) $(depcomp) @AMDEPBACKSLASH@ +@am__fastdepCC_FALSE@ $(AM_V_CC@am__nodep@)$(COMPILE) -c -o $@ `$(CYGPATH_W) '$<'` + +.c.lo: +@am__fastdepCC_TRUE@ $(AM_V_CC)$(LTCOMPILE) -MT $@ -MD -MP -MF $(DEPDIR)/$*.Tpo -c -o $@ $< +@am__fastdepCC_TRUE@ $(AM_V_at)$(am__mv) $(DEPDIR)/$*.Tpo $(DEPDIR)/$*.Plo +@AMDEP_TRUE@@am__fastdepCC_FALSE@ $(AM_V_CC)source='$<' object='$@' libtool=yes @AMDEPBACKSLASH@ +@AMDEP_TRUE@@am__fastdepCC_FALSE@ DEPDIR=$(DEPDIR) $(CCDEPMODE) $(depcomp) @AMDEPBACKSLASH@ +@am__fastdepCC_FALSE@ $(AM_V_CC@am__nodep@)$(LTCOMPILE) -c -o $@ $< + +mostlyclean-libtool: + -rm -f *.lo + +clean-libtool: + -rm -rf .libs _libs + +ID: $(am__tagged_files) + $(am__define_uniq_tagged_files); mkid -fID $$unique +tags: tags-am +TAGS: tags + +tags-am: $(TAGS_DEPENDENCIES) $(am__tagged_files) + set x; \ + here=`pwd`; \ + $(am__define_uniq_tagged_files); \ + shift; \ + if test -z "$(ETAGS_ARGS)$$*$$unique"; then :; else \ + test -n "$$unique" || unique=$$empty_fix; \ + if test $$# -gt 0; then \ + $(ETAGS) $(ETAGSFLAGS) $(AM_ETAGSFLAGS) $(ETAGS_ARGS) \ + "$$@" $$unique; \ + else \ + $(ETAGS) $(ETAGSFLAGS) $(AM_ETAGSFLAGS) $(ETAGS_ARGS) \ + $$unique; \ + fi; \ + fi +ctags: ctags-am + +CTAGS: ctags +ctags-am: $(TAGS_DEPENDENCIES) $(am__tagged_files) + $(am__define_uniq_tagged_files); \ + test -z "$(CTAGS_ARGS)$$unique" \ + || $(CTAGS) $(CTAGSFLAGS) $(AM_CTAGSFLAGS) $(CTAGS_ARGS) \ + $$unique + +GTAGS: + here=`$(am__cd) $(top_builddir) && pwd` \ + && $(am__cd) $(top_srcdir) \ + && gtags -i $(GTAGS_ARGS) "$$here" +cscopelist: cscopelist-am + +cscopelist-am: $(am__tagged_files) + list='$(am__tagged_files)'; \ + case "$(srcdir)" in \ + [\\/]* | ?:[\\/]*) sdir="$(srcdir)" ;; \ + *) sdir=$(subdir)/$(srcdir) ;; \ + esac; \ + for i in $$list; do \ + if test -f "$$i"; then \ + echo "$(subdir)/$$i"; \ + else \ + echo "$$sdir/$$i"; \ + fi; \ + done >> $(top_builddir)/cscope.files + +distclean-tags: + -rm -f TAGS ID GTAGS GRTAGS GSYMS GPATH tags + +distdir: $(BUILT_SOURCES) + $(MAKE) $(AM_MAKEFLAGS) distdir-am + +distdir-am: $(DISTFILES) + @srcdirstrip=`echo "$(srcdir)" | sed 's/[].[^$$\\*]/\\\\&/g'`; \ + topsrcdirstrip=`echo "$(top_srcdir)" | sed 's/[].[^$$\\*]/\\\\&/g'`; \ + list='$(DISTFILES)'; \ + dist_files=`for file in $$list; do echo $$file; done | \ + sed -e "s|^$$srcdirstrip/||;t" \ + -e "s|^$$topsrcdirstrip/|$(top_builddir)/|;t"`; \ + case $$dist_files in \ + */*) $(MKDIR_P) `echo "$$dist_files" | \ + sed '/\//!d;s|^|$(distdir)/|;s,/[^/]*$$,,' | \ + sort -u` ;; \ + esac; \ + for file in $$dist_files; do \ + if test -f $$file || test -d $$file; then d=.; else d=$(srcdir); fi; \ + if test -d $$d/$$file; then \ + dir=`echo "/$$file" | sed -e 's,/[^/]*$$,,'`; \ + if test -d "$(distdir)/$$file"; then \ + find "$(distdir)/$$file" -type d ! -perm -700 -exec chmod u+rwx {} \;; \ + fi; \ + if test -d $(srcdir)/$$file && test $$d != $(srcdir); then \ + cp -fpR $(srcdir)/$$file "$(distdir)$$dir" || exit 1; \ + find "$(distdir)/$$file" -type d ! -perm -700 -exec chmod u+rwx {} \;; \ + fi; \ + cp -fpR $$d/$$file "$(distdir)$$dir" || exit 1; \ + else \ + test -f "$(distdir)/$$file" \ + || cp -p $$d/$$file "$(distdir)/$$file" \ + || exit 1; \ + fi; \ + done +check-am: all-am +check: check-am +all-am: Makefile $(PROGRAMS) +installdirs: + for dir in "$(DESTDIR)$(libexecdir)"; do \ + test -z "$$dir" || $(MKDIR_P) "$$dir"; \ + done +install: install-am +install-exec: install-exec-am +install-data: install-data-am +uninstall: uninstall-am + +install-am: all-am + @$(MAKE) $(AM_MAKEFLAGS) install-exec-am install-data-am + +installcheck: installcheck-am +install-strip: + if test -z '$(STRIP)'; then \ + $(MAKE) $(AM_MAKEFLAGS) INSTALL_PROGRAM="$(INSTALL_STRIP_PROGRAM)" \ + install_sh_PROGRAM="$(INSTALL_STRIP_PROGRAM)" INSTALL_STRIP_FLAG=-s \ + install; \ + else \ + $(MAKE) $(AM_MAKEFLAGS) INSTALL_PROGRAM="$(INSTALL_STRIP_PROGRAM)" \ + install_sh_PROGRAM="$(INSTALL_STRIP_PROGRAM)" INSTALL_STRIP_FLAG=-s \ + "INSTALL_PROGRAM_ENV=STRIPPROG='$(STRIP)'" install; \ + fi +mostlyclean-generic: + +clean-generic: + +distclean-generic: + -test -z "$(CONFIG_CLEAN_FILES)" || rm -f $(CONFIG_CLEAN_FILES) + -test . = "$(srcdir)" || test -z "$(CONFIG_CLEAN_VPATH_FILES)" || rm -f $(CONFIG_CLEAN_VPATH_FILES) + +maintainer-clean-generic: + @echo "This command is intended for maintainers to use" + @echo "it deletes files that may require special tools to rebuild." +clean: clean-am + +clean-am: clean-generic clean-libexecPROGRAMS clean-libtool \ + mostlyclean-am + +distclean: distclean-am + -rm -f ./$(DEPDIR)/curve.Po + -rm -f ./$(DEPDIR)/edge.Po + -rm -f ./$(DEPDIR)/fit.Po + -rm -f ./$(DEPDIR)/math.Po + -rm -f ./$(DEPDIR)/pxl-outline.Po + -rm -f ./$(DEPDIR)/selection-to-path-dialog.Po + -rm -f ./$(DEPDIR)/selection-to-path.Po + -rm -f ./$(DEPDIR)/spline.Po + -rm -f ./$(DEPDIR)/vector.Po + -rm -f Makefile +distclean-am: clean-am distclean-compile distclean-generic \ + distclean-tags + +dvi: dvi-am + +dvi-am: + +html: html-am + +html-am: + +info: info-am + +info-am: + +install-data-am: + +install-dvi: install-dvi-am + +install-dvi-am: + +install-exec-am: install-libexecPROGRAMS + +install-html: install-html-am + +install-html-am: + +install-info: install-info-am + +install-info-am: + +install-man: + +install-pdf: install-pdf-am + +install-pdf-am: + +install-ps: install-ps-am + +install-ps-am: + +installcheck-am: + +maintainer-clean: maintainer-clean-am + -rm -f ./$(DEPDIR)/curve.Po + -rm -f ./$(DEPDIR)/edge.Po + -rm -f ./$(DEPDIR)/fit.Po + -rm -f ./$(DEPDIR)/math.Po + -rm -f ./$(DEPDIR)/pxl-outline.Po + -rm -f ./$(DEPDIR)/selection-to-path-dialog.Po + -rm -f ./$(DEPDIR)/selection-to-path.Po + -rm -f ./$(DEPDIR)/spline.Po + -rm -f ./$(DEPDIR)/vector.Po + -rm -f Makefile +maintainer-clean-am: distclean-am maintainer-clean-generic + +mostlyclean: mostlyclean-am + +mostlyclean-am: mostlyclean-compile mostlyclean-generic \ + mostlyclean-libtool + +pdf: pdf-am + +pdf-am: + +ps: ps-am + +ps-am: + +uninstall-am: uninstall-libexecPROGRAMS + +.MAKE: install-am install-strip + +.PHONY: CTAGS GTAGS TAGS all all-am am--depfiles check check-am clean \ + clean-generic clean-libexecPROGRAMS clean-libtool \ + cscopelist-am ctags ctags-am distclean distclean-compile \ + distclean-generic distclean-libtool distclean-tags distdir dvi \ + dvi-am html html-am info info-am install install-am \ + install-data install-data-am install-dvi install-dvi-am \ + install-exec install-exec-am install-html install-html-am \ + install-info install-info-am install-libexecPROGRAMS \ + install-man install-pdf install-pdf-am install-ps \ + install-ps-am install-strip installcheck installcheck-am \ + installdirs maintainer-clean maintainer-clean-generic \ + mostlyclean mostlyclean-compile mostlyclean-generic \ + mostlyclean-libtool pdf pdf-am ps ps-am tags tags-am uninstall \ + uninstall-am uninstall-libexecPROGRAMS + +.PRECIOUS: Makefile + + +# `windres` seems a very stupid tool and it breaks with double shlashes +# in parameter paths. Strengthen the rule a little. +@HAVE_WINDRES_TRUE@%.rc.o: +@HAVE_WINDRES_TRUE@ $(WINDRES) --define ORIGINALFILENAME_STR="$*$(EXEEXT)" \ +@HAVE_WINDRES_TRUE@ --define INTERNALNAME_STR="$*" \ +@HAVE_WINDRES_TRUE@ --define TOP_SRCDIR="`echo $(top_srcdir) | sed 's*//*/*'`" \ +@HAVE_WINDRES_TRUE@ -I"`echo $(top_srcdir)/app | sed 's%/\+%/%'`" \ +@HAVE_WINDRES_TRUE@ -I"`echo $(top_builddir)/app | sed 's%/\+%/%'`"\ +@HAVE_WINDRES_TRUE@ -I"`echo $(top_builddir) | sed 's%/\+%/%'`"\ +@HAVE_WINDRES_TRUE@ $(GIMPPLUGINRC) $@ + +# Tell versions [3.59,3.63) of GNU make to not export all variables. +# Otherwise a system limit (for SysV at least) may be exceeded. +.NOEXPORT: diff --git a/plug-ins/selection-to-path/README b/plug-ins/selection-to-path/README new file mode 100644 index 0000000..80fa1c0 --- /dev/null +++ b/plug-ins/selection-to-path/README @@ -0,0 +1,51 @@ + + +Andy Thomas (alt@gimp.org) 9th July 1999 + + +This plug-in will take a selection and convert it into a path. +For the purpose of the plug-in the selection boundary is defined +in a similar manner to that worked out for the "marching ants" markers +of the selection. I think this gives the best user feel/feedback since +the created path "follows" the "marching ants". + +I cannot claim responsibility for the underlying algorithms. These +were taken directly from the GNU font utilities (the "limn" program +in particular) written by Karl Berry and Kathryn Hargreaves. + +Their email addresses quoted in the README are:- + +Karl Berry karl@cs.umb.edu +Kathryn Hargreaves letters@cs.umb.edu + +Please see fontutils-0.6 package for more details. I have included the +README from the limn part of the package. + +I thank Karl & Kathryn for producing such a well written set of utilities. + +I have just added a gimp front-end onto them. + + +How to use it. +~~~~~~~~~~~~~~ + +Simply select an area and then select either "<Image>/Selection/To Path" +menu item or the "Selection To Image" button in the paths dialog. The new +path will be created. Currently if the LCP dialog has not been activated +then the path will not be visible... A bug I have just found - simply +bring up the LCP dialog and select the Paths tab to see the newly created +path. + +An additional function can be obtained by having the "Shift" modifier pressed +while using the button in the paths dialog. This will pop-up a "power-users" +menu where the parameters to the underlying algorithms can be modified. +WARNING:- Some values may cause the plugin to enter extremely long operations. +You have been warned. + +Have fun! + + +Andy. + +PS. Please direct any bugs etc found in this plugin to either +myself or the gimp-developer mailing list. Thank. diff --git a/plug-ins/selection-to-path/README.limn b/plug-ins/selection-to-path/README.limn new file mode 100644 index 0000000..3e0e568 --- /dev/null +++ b/plug-ins/selection-to-path/README.limn @@ -0,0 +1,56 @@ +This program converts bitmap fonts to a homegrown outline format, bezier +(BZR). The program `bzrto' converts that format to something usable for +typesetting. + +We used two main sources in writing the program: + +@mastersthesis{Schneider:PIC-88, + author = "Philip J. Schneider", + title = "Phoenix: An Interactive Curve Design System Based on the + Automatic Fitting of Hand-Sketched Curves", + school = inst-u-wash, + year = 1988, +} + +@article{Plass:CG-17-229, + author = "Michael Plass and Maureen Stone", + title = "Curve-fitting with Piecewise Parametric Cubics", + journal = j-comp-graphics, + year = 1983, + volume = 17, + number = 3, + month = jul, + pages = "229-239", +} + +We had access to the code for Phoenix, thanks to Philip, but none of our +code is based on his (mostly because his task was allow interactive +sketching, and ours to fit bitmap characters, and the two require +different data structures). The general outline of the fitting +algorithm does come from Phoenix. + +We also found this article helpful: + +@Inproceedings{Gonczarowski:RIDT91-1, + author = "Jakob Gonczarowski", + title = "A Fast Approach to Auto-tracing (with Parametric + Cubics)", + pages = "1--15", + crossref = "Morris:RIDT91", + acknowledgement = ack-kb, +} + +@String{proc-RIDT91 = "Raster Imaging and Digital Typography II"} + +@Proceedings{Morris:RIDT91, + title = proc-RIDT91, + booktitle = proc-RIDT91, + year = "1991", + editor = "Robert A. Morris and Jacques Andr{\'e}", + publisher = pub-CUP, + address = pub-CUP:adr, + acknowledgement = ack-kb, +} + +(These BibTeX entries are from the type.bib and ep.bib files on +math.utah.edu:pub/tex/bib.) diff --git a/plug-ins/selection-to-path/bitmap.h b/plug-ins/selection-to-path/bitmap.h new file mode 100644 index 0000000..98c89ac --- /dev/null +++ b/plug-ins/selection-to-path/bitmap.h @@ -0,0 +1,112 @@ +/* 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. + * + * 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 3, 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, see <https://www.gnu.org/licenses/>. + */ + +#ifndef BITMAP_H +#define BITMAP_H + +#include <stdio.h> +#include "bounding-box.h" +#include "types.h" + + +/* If the bitmap holds 8-bit values, rather than one-bit, the + definition of BLACK here is wrong. So don't use it in that case! */ +#define WHITE 0 +#define BLACK 1 + + +/* The basic structure and macros to access it. */ +typedef struct +{ + dimensions_type dimensions; + one_byte *bitmap; +} bitmap_type; + +/* The dimensions of the bitmap, in pixels. */ +#define BITMAP_DIMENSIONS(b) ((b).dimensions) + +/* The pixels, represented as an array of bytes (in contiguous storage). + Each pixel is a single byte, even for binary fonts. */ +#define BITMAP_BITS(b) ((b).bitmap) + +/* These are convenient abbreviations for getting inside the members. */ +#define BITMAP_WIDTH(b) DIMENSIONS_WIDTH (BITMAP_DIMENSIONS (b)) +#define BITMAP_HEIGHT(b) DIMENSIONS_HEIGHT (BITMAP_DIMENSIONS (b)) + +/* This is the address of the first pixel in the row ROW. */ +#define BITMAP_ROW(b, row) (BITMAP_BITS (b) + (row) * BITMAP_WIDTH (b)) + +/* This is the pixel at [ROW,COL]. */ +#define BITMAP_PIXEL(b, row, col) \ + (*(BITMAP_BITS (b) + (row) * BITMAP_WIDTH (b) + (col))) + +#define BITMAP_VALID_PIXEL(b, row, col) \ + (0 <= (row) && (row) < BITMAP_HEIGHT (b) \ + && 0 <= (col) && (col) < BITMAP_WIDTH (b)) + +/* Assume that the pixel at [ROW,COL] itself is black. */ + +#define BITMAP_INTERIOR_PIXEL(b, row, col) \ + (0 != (row) && (row) != BITMAP_HEIGHT (b) - 1 \ + && 0 != (col) && (col) != BITMAP_WIDTH (b) - 1 \ + && BITMAP_PIXEL (b, row - 1, col - 1) == BLACK \ + && BITMAP_PIXEL (b, row - 1, col) == BLACK \ + && BITMAP_PIXEL (b, row - 1, col + 1) == BLACK \ + && BITMAP_PIXEL (b, row, col - 1) == BLACK \ + && BITMAP_PIXEL (b, row, col + 1) == BLACK \ + && BITMAP_PIXEL (b, row + 1, col - 1) == BLACK \ + && BITMAP_PIXEL (b, row + 1, col) == BLACK \ + && BITMAP_PIXEL (b, row + 1, col + 1) == BLACK) + +/* Allocate storage for the bits, set them all to white, and return an + initialized structure. */ +extern bitmap_type new_bitmap (dimensions_type); + +/* Free that storage. */ +extern void free_bitmap (bitmap_type *); + +/* Make a fresh copy of BITMAP in a new structure, and return it. */ +extern bitmap_type copy_bitmap (bitmap_type bitmap); + +/* Return the pixels in the bitmap B enclosed by the bounding box BB. + The result is put in newly allocated storage. */ +extern bitmap_type extract_subbitmap (bitmap_type b, bounding_box_type bb); + +/* Consider the dimensions of a bitmap as a bounding box. The bounding + box returned is in bitmap coordinates, rather than Cartesian, and + refers to pixels, rather than edges. Specifically, this means that + the maximum column is one less than results from `dimensions_to_bb + (BITMAP_DIMENSIONS ())'. */ +extern bounding_box_type bitmap_to_bb (const bitmap_type); + +/* Return a vector of zero-based column numbers marking transitions from + black to white or white to black in ROW, which is of length WIDTH. + The end of the vector is marked with an element of length WIDTH + 1. + The first element always marks a white-to-black transition (or it's + 0, if the first pixel in ROW is black). */ +extern unsigned *bitmap_find_transitions (const one_byte *row, unsigned width); + +/* Print part of or all of a bitmap. */ +extern void print_bounded_bitmap (FILE *, bitmap_type, bounding_box_type); +extern void print_bitmap (FILE *, bitmap_type); + +#endif /* not BITMAP_H */ + diff --git a/plug-ins/selection-to-path/bounding-box.h b/plug-ins/selection-to-path/bounding-box.h new file mode 100644 index 0000000..54f1e71 --- /dev/null +++ b/plug-ins/selection-to-path/bounding-box.h @@ -0,0 +1,63 @@ +/* bounding-box.h: operations on both real- and integer-valued bounding boxes. + * + * 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 3, 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, see <https://www.gnu.org/licenses/>. + */ + +#ifndef BOUNDING_BOX_H +#define BOUNDING_BOX_H + +#include "types.h" + + +/* The bounding box's numbers are usually in Cartesian/Metafont + coordinates: (0,0) is towards the lower left. */ +typedef struct +{ + signed_4_bytes min_row, max_row; + signed_4_bytes min_col, max_col; +} bounding_box_type; + +typedef struct +{ + real min_row, max_row; + real min_col, max_col; +} real_bounding_box_type; + +/* These accessing macros work for both types of bounding boxes, since + the member names are the same. */ +#define MIN_ROW(bb) ((bb).min_row) +#define MAX_ROW(bb) ((bb).max_row) +#define MIN_COL(bb) ((bb).min_col) +#define MAX_COL(bb) ((bb).max_col) + +/* See the comments at `get_character_bitmap' in gf_input.c for why the + width and height are treated asymmetrically. */ +#define BB_WIDTH(bb) (MAX_COL (bb) - MIN_COL (bb)) +#define BB_HEIGHT(bb) (MAX_ROW (bb) - MIN_ROW (bb) + 1) + + +/* Convert a dimensions structure to an integer bounding box, and vice + versa. */ +extern bounding_box_type dimensions_to_bb (dimensions_type); +extern dimensions_type bb_to_dimensions (bounding_box_type); + + +/* Update the bounding box BB from the point P. */ +extern void update_real_bounding_box (real_bounding_box_type *bb, + real_coordinate_type p); +extern void update_bounding_box (bounding_box_type *bb, coordinate_type p); + +#endif /* not BOUNDING_BOX_H */ diff --git a/plug-ins/selection-to-path/curve.c b/plug-ins/selection-to-path/curve.c new file mode 100644 index 0000000..afb157c --- /dev/null +++ b/plug-ins/selection-to-path/curve.c @@ -0,0 +1,184 @@ +/* curve.c: operations on the lists of pixels and lists of curves. + * + * 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 3, 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, see <https://www.gnu.org/licenses/>. + */ + +#include "config.h" + +#include <glib.h> + +#include "global.h" +#include "curve.h" + + +/* Return an entirely empty curve. */ + +curve_type +new_curve (void) +{ + curve_type curve = g_new (struct curve, 1); + + 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; +} + + +/* Start the returned curve off with COORD as the first point. */ + +curve_type +init_curve (coordinate_type coord) +{ + curve_type curve = new_curve (); + + curve->point_list = g_new (point_type, 1); + CURVE_LENGTH (curve) = 1; + + CURVE_POINT (curve, 0) = int_to_real_coord (coord); + + 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) + safe_free ((address *) &(curve->point_list)); +} + + +void +append_pixel (curve_type curve, coordinate_type coord) +{ + append_point (curve, int_to_real_coord (coord)); +} + + +void +append_point (curve_type curve, real_coordinate_type coord) +{ + CURVE_LENGTH (curve)++; + curve->point_list = g_realloc (curve->point_list,CURVE_LENGTH (curve) * sizeof(point_type)); + LAST_CURVE_POINT (curve) = coord; + /* The t value does not need to be set. */ +} + +/* 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; + curve_list.clockwise = FALSE; + + 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]); + + /* If the character was empty, it won't have any curves. */ + if (curve_list->data != NULL) + safe_free ((address *) &(curve_list->data)); +} + + +/* Add an element to a curve list. */ + +void +append_curve (curve_list_type *curve_list, curve_type curve) +{ + curve_list->length++; + curve_list->data = g_realloc (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) +{ + unsigned this_list; + + for (this_list = 0; this_list < CURVE_LIST_ARRAY_LENGTH (*curve_list_array); + this_list++) + free_curve_list (&CURVE_LIST_ARRAY_ELT (*curve_list_array, this_list)); + + /* If the character was empty, it won't have any curves. */ + if (curve_list_array->data != NULL) + safe_free ((address *) &(curve_list_array->data)); +} + + +/* Add an element to a curve list array. */ + +void +append_curve_list (curve_list_array_type *l, curve_list_type curve_list) +{ + CURVE_LIST_ARRAY_LENGTH (*l)++; + l->data = g_realloc (l->data,( CURVE_LIST_ARRAY_LENGTH (*l))*sizeof(curve_list_type)); + LAST_CURVE_LIST_ARRAY_ELT (*l) = curve_list; +} diff --git a/plug-ins/selection-to-path/curve.h b/plug-ins/selection-to-path/curve.h new file mode 100644 index 0000000..b0bd374 --- /dev/null +++ b/plug-ins/selection-to-path/curve.h @@ -0,0 +1,157 @@ +/* curve.h: data structures for the conversion from pixels to splines. + * + * 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 3, 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, see <https://www.gnu.org/licenses/>. + */ + +#ifndef CURVE_H +#define CURVE_H + +#include "types.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 +{ + real_coordinate_type coord; + real 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; + int length; + boolean 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) \ + ((int) (n) - 1 < 0 \ + ? CURVE_CYCLIC (c) ? CURVE_LENGTH (c) + (int) (n) - 1 : -1 \ + : (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 with the point P as its first element. */ +extern curve_type init_curve (coordinate_type p); + +/* 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, coordinate_type p); + +/* Like `append_pixel', for a point in real coordinates. */ +extern void append_point (curve_type c, real_coordinate_type 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, boolean 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; + boolean clockwise; +} 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 *); +extern void append_curve_list (curve_list_array_type *, curve_list_type); + +#endif /* not CURVE_H */ diff --git a/plug-ins/selection-to-path/edge.c b/plug-ins/selection-to-path/edge.c new file mode 100644 index 0000000..8aa20be --- /dev/null +++ b/plug-ins/selection-to-path/edge.c @@ -0,0 +1,268 @@ +/* edge.c: operations on edges in bitmaps. + * + * 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 3, 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, see <https://www.gnu.org/licenses/>. + */ + +#include "config.h" + +#include <assert.h> + +#include "types.h" +#include "selection-to-path.h" +#include "edge.h" + +/* We can move in any of eight directions as we are traversing + the outline. These numbers are not arbitrary; TRY_PIXEL depends on + them. */ + +typedef enum +{ + north = 0, northwest = 1, west = 2, southwest = 3, south = 4, + southeast = 5, east = 6, northeast = 7 +} direction_type; + + +static boolean is_marked_edge (edge_type, unsigned, unsigned, bitmap_type); +static boolean is_outline_edge (edge_type, unsigned, unsigned); +static edge_type next_edge (edge_type); + +/* The following macros are used (directly or indirectly) by the + `next_outline_edge' routine. */ + +/* Given the direction DIR of the pixel to test, decide which edge on + that pixel we are supposed to test. Because we've chosen the mapping + from directions to numbers carefully, we don't have to do much. */ + +#define FIND_TEST_EDGE(dir) ((dir) / 2) + + +/* Find how to move in direction DIR on the axis AXIS (either `ROW' or + `COL'). We are in the ``display'' coordinate system, with y + increasing downward and x increasing to the right. Therefore, we are + implementing the following table: + + direction row delta col delta + north -1 0 + south +1 0 + east 0 +1 + west 0 +1 + + with the other four directions (e.g., northwest) being the sum of + their components (e.g., north + west). + + The first macro, `COMPUTE_DELTA', handles splitting up the latter + cases, all of which have been assigned odd numbers. */ + +#define COMPUTE_DELTA(axis, dir) \ + ((dir) % 2 != 0 \ + ? COMPUTE_##axis##_DELTA ((dir) - 1) \ + + COMPUTE_##axis##_DELTA (((dir) + 1) % 8) \ + : COMPUTE_##axis##_DELTA (dir) \ + ) + +/* Now it is trivial to implement the four cardinal directions. */ +#define COMPUTE_ROW_DELTA(dir) \ + ((dir) == north ? -1 : (dir) == south ? +1 : 0) + +#define COMPUTE_COL_DELTA(dir) \ + ((dir) == west ? -1 : (dir) == east ? +1 : 0) + + +/* See if the appropriate edge on the pixel from (row,col) in direction + DIR is on the outline. If so, update `row', `col', and `edge', and + break. We also use the variable `character' as the bitmap in which + to look. */ + +#define TRY_PIXEL(dir) \ + { \ + int delta_r = COMPUTE_DELTA (ROW, dir); \ + int delta_c = COMPUTE_DELTA (COL, dir); \ + int test_row = *row + delta_r; \ + int test_col = *col + delta_c; \ + edge_type test_edge = FIND_TEST_EDGE (dir); \ + \ + if (sel_valid_pixel(test_row, test_col) \ + && is_outline_edge (test_edge, test_row, test_col)) \ + { \ + *row = test_row; \ + *col = test_col; \ + *edge = test_edge; \ + break; \ + } \ + } + +/* Finally, we are ready to implement the routine that finds the next + edge on the outline. We look first for an adjacent edge that is not + on the current pixel. We want to go around outside outlines + counterclockwise, and inside outlines clockwise (because that is how + both Metafont and Adobe Type 1 format want their curves to be drawn). + + The very first outline (an outside one) on each character starts on a + top edge (STARTING_EDGE in edge.h defines this); so, if we're at a + top edge, we want to go only to the left (on the pixel to the west) + or down (on the same pixel), to begin with. Then, when we're on a + left edge, we want to go to the top edge (on the southwest pixel) or + to the left edge (on the south pixel). + + All well and good. But if you draw a rasterized circle (or whatever), + eventually we have to come back around to the beginning; at that + point, we'll be on a top edge, and we'll have to go to the right edge + on the northwest pixel. Draw pictures. + + The upshot is, if we find an edge on another pixel, we return (in ROW + and COL) the position of the new pixel, and (in EDGE) the kind of + edge it is. If we don't find such an edge, we return (in EDGE) the + next (in a counterclockwise direction) edge on the current pixel. */ + +void +next_outline_edge (edge_type *edge, + unsigned *row, unsigned *col) +{ + unsigned original_row = *row; + unsigned original_col = *col; + + switch (*edge) + { + case right: + TRY_PIXEL (north); + TRY_PIXEL (northeast); + break; + + case top: + TRY_PIXEL (west); + TRY_PIXEL (northwest); + break; + + case left: + TRY_PIXEL (south); + TRY_PIXEL (southwest); + break; + + case bottom: + TRY_PIXEL (east); + TRY_PIXEL (southeast); + break; + + default: + printf ("next_outline_edge: Bad edge value (%d)", *edge); + + } + + /* If we didn't find an adjacent edge on another pixel, return the + next edge on the current pixel. */ + if (*row == original_row && *col == original_col) + *edge = next_edge (*edge); +} + +/* We return the next edge on the pixel at position ROW and COL which is + an unmarked outline edge. By ``next'' we mean either the one sent in + in STARTING_EDGE, if it qualifies, or the next such returned by + `next_edge'. */ + +edge_type +next_unmarked_outline_edge (unsigned row, unsigned col, + edge_type starting_edge, + bitmap_type marked) +{ + edge_type edge = starting_edge; + + assert (edge != no_edge); + + while (is_marked_edge (edge, row, col, marked) + || !is_outline_edge (edge, row, col)) + { + edge = next_edge (edge); + if (edge == starting_edge) + return no_edge; + } + + return edge; +} + + +/* We check to see if the edge EDGE of the pixel at position ROW and COL + is an outline edge; i.e., that it is a black pixel which shares that + edge with a white pixel. The position ROW and COL should be inside + the bitmap CHARACTER. */ + +static boolean +is_outline_edge (edge_type edge, + unsigned row, unsigned col) +{ + /* If this pixel isn't black, it's not part of the outline. */ + if (sel_pixel_is_white(row, col)) + return false; + + switch (edge) + { + case left: + return col == 0 || sel_pixel_is_white(row, col - 1); + + case top: + return row == 0 || sel_pixel_is_white(row - 1, col); + + case right: + return (col == sel_get_width() - 1) + || sel_pixel_is_white(row, col + 1); + + case bottom: + return (row == sel_get_height() - 1) + || sel_pixel_is_white(row + 1, col); + + case no_edge: + default: + printf ("is_outline_edge: Bad edge value(%d)", edge); + } + + return 0; /* NOTREACHED */ +} + +/* 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'; we just return false. */ + +void +mark_edge (edge_type edge, unsigned row, unsigned col, bitmap_type *marked) +{ + /* printf("row = %d, col = %d \n",row,col); */ + assert (!is_marked_edge (edge, row, col, *marked)); + + if (edge != no_edge) + BITMAP_PIXEL (*marked, row, col) |= 1 << edge; +} + + +/* Test if the edge EDGE at ROW/COL in MARKED is marked. */ + +static boolean +is_marked_edge (edge_type edge, unsigned row, unsigned col, bitmap_type marked) +{ + return + edge == no_edge ? false : BITMAP_PIXEL (marked, row, col) & (1 << edge); +} + + +/* Return the edge which is counterclockwise-adjacent to EDGE. This + code makes use of the ``numericness'' of C enumeration constants; + sorry about that. */ + +#define NUM_EDGES no_edge + +static edge_type +next_edge (edge_type edge) +{ + return edge == no_edge ? edge : (edge + 1) % NUM_EDGES; +} diff --git a/plug-ins/selection-to-path/edge.h b/plug-ins/selection-to-path/edge.h new file mode 100644 index 0000000..1d9d347 --- /dev/null +++ b/plug-ins/selection-to-path/edge.h @@ -0,0 +1,59 @@ +/* edge.h: declarations for edge traversing. + * + * 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 3, 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, see <https://www.gnu.org/licenses/>. + */ + +#ifndef EDGE_H +#define EDGE_H + +#include "bitmap.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 + + +/* Return the next outline edge on B in EDGE, ROW, and COL. */ +extern void next_outline_edge (edge_type *edge, + unsigned *row, unsigned *col); + +/* Return the next edge after START on the pixel ROW/COL in B that is + unmarked, according to the MARKED array. */ +extern edge_type next_unmarked_outline_edge (unsigned row, unsigned col, + edge_type start, + bitmap_type marked); + +/* Mark the edge E at the pixel ROW/COL in MARKED. */ +extern void mark_edge (edge_type e, unsigned row, unsigned col, + bitmap_type *marked); + +#endif /* not EDGE_H */ diff --git a/plug-ins/selection-to-path/fit.c b/plug-ins/selection-to-path/fit.c new file mode 100644 index 0000000..8ee57ae --- /dev/null +++ b/plug-ins/selection-to-path/fit.c @@ -0,0 +1,1967 @@ +/* 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. + * + * 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 3, 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, see <https://www.gnu.org/licenses/>. + */ + +#include "config.h" + +#include <string.h> +#include <float.h> +#include <math.h> +#include <assert.h> + +#include <glib.h> + +#include "global.h" +#include "spline.h" +#include "vector.h" + +#include "curve.h" +#include "fit.h" +#include "pxl-outline.h" + +/* If two endpoints are closer than this, they are made to be equal. + (-align-threshold) */ +real align_threshold = 0.5; + +/* If the angle defined by a point and its predecessors and successors + is smaller than this, it's a corner, even if it's within + `corner_surround' pixels of a point with a smaller angle. + (-corner-always-threshold) */ +real corner_always_threshold = 60.0; + +/* Number of points to consider when determining if a point is a corner + or not. (-corner-surround) */ +unsigned corner_surround = 4; + +/* If a point, its predecessors, and its successors define an angle + smaller than this, it's a corner. Should be in range 0..180. + (-corner-threshold) */ +real corner_threshold = 100.0; + +/* Amount of error at which a fitted spline is unacceptable. If any + pixel is further away than this from the fitted curve, we try again. + (-error-threshold) */ +/* real error_threshold = .8; ALT */ +real error_threshold = .4; + +/* A second number of adjacent points to consider when filtering. + (-filter-alternative-surround) */ +unsigned filter_alternative_surround = 1; + +/* If the angles between the vectors produced by filter_surround and + filter_alternative_surround points differ by more than this, use + the one from filter_alternative_surround. (-filter-epsilon) */ +real filter_epsilon = 10.0; + +/* Number of times to smooth original data points. Increasing this + number dramatically---to 50 or so---can produce vastly better + results. But if any points that ``should'' be corners aren't found, + the curve goes to hell around that point. (-filter-iterations) */ +/* unsigned filter_iteration_count = 4; ALT */ +unsigned filter_iteration_count = 4; + +/* To produce the new point, use the old point plus this times the + neighbors. (-filter-percent) */ +real filter_percent = .33; + +/* Number of adjacent points to consider if `filter_surround' points + defines a straight line. (-filter-secondary-surround) */ +static unsigned filter_secondary_surround = 3; + +/* Number of adjacent points to consider when filtering. + (-filter-surround) */ +unsigned filter_surround = 2; + +/* Says whether or not to remove ``knee'' points after finding the outline. + (See the comments at `remove_knee_points'.) (-remove-knees). */ +boolean keep_knees = false; + +/* If a spline is closer to a straight line than this, it remains a + straight line, even if it would otherwise be changed back to a curve. + This is weighted by the square of the curve length, to make shorter + curves more likely to be reverted. (-line-reversion-threshold) */ +real line_reversion_threshold = .01; + +/* How many pixels (on the average) a spline can diverge from the line + determined by its endpoints before it is changed to a straight line. + (-line-threshold) */ +/* real line_threshold = 1.0; ALT */ +real line_threshold = 0.5; + +/* If reparameterization doesn't improve the fit by this much percent, + stop doing it. (-reparameterize-improve) */ +/* real reparameterize_improvement = .10; ALT */ +real reparameterize_improvement = .01; + +/* Amount of error at which it is pointless to reparameterize. This + happens, for example, when we are trying to fit the outline of the + outside of an `O' with a single spline. The initial fit is not good + enough for the Newton-Raphson iteration to improve it. It may be + that it would be better to detect the cases where we didn't find any + corners. (-reparameterize-threshold) */ +/* real reparameterize_threshold = 30.0; ALT */ +real reparameterize_threshold = 1.0; + +/* Percentage of the curve away from the worst point to look for a + better place to subdivide. (-subdivide-search) */ +real subdivide_search = .1; + +/* Number of points to consider when deciding whether a given point is a + better place to subdivide. (-subdivide-surround) */ +unsigned subdivide_surround = 4; + +/* How many pixels a point can diverge from a straight line and still be + considered a better place to subdivide. (-subdivide-threshold) */ +real subdivide_threshold = .03; + +/* Number of points to look at on either side of a point when computing + the approximation to the tangent at that point. (-tangent-surround) */ +unsigned tangent_surround = 3; + + +/* 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); + +static void align (spline_list_type *); +static void change_bad_lines (spline_list_type *); +static void filter (curve_type); +static real filter_angle (vector_type, vector_type); +static void find_curve_vectors + (unsigned, curve_type, unsigned, vector_type *, vector_type *, unsigned *); +static unsigned find_subdivision (curve_type, unsigned initial); +static void find_vectors + (unsigned, pixel_outline_type, vector_type *, vector_type *); +static index_list_type find_corners (pixel_outline_type); +static real find_error (curve_type, spline_type, unsigned *); +static vector_type find_half_tangent (curve_type, boolean start, unsigned *); +static void find_tangent (curve_type, boolean, boolean); +static spline_type fit_one_spline (curve_type); +static spline_list_type *fit_curve (curve_type); +static spline_list_type fit_curve_list (curve_list_type); +static spline_list_type *fit_with_least_squares (curve_type); +static spline_list_type *fit_with_line (curve_type); +static void remove_knee_points (curve_type, boolean); +static boolean reparameterize (curve_type, spline_type); +static void set_initial_parameter_values (curve_type); +static boolean spline_linear_enough (spline_type *, curve_type); +static curve_list_array_type split_at_corners (pixel_outline_list_type); +static boolean test_subdivision_point (curve_type, unsigned, vector_type *); + +/* 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) +{ + unsigned this_list; + unsigned total = 0; + spline_list_array_type char_splines = new_spline_list_array (); + curve_list_array_type curve_array = split_at_corners (pixel_outline_list); + + 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); + + curve_list_splines = fit_curve_list (curves); + append_spline_list (&char_splines, curve_list_splines); + +/* REPORT ("* "); */ + } + + free_curve_list_array (&curve_array); + + for (this_list = 0; this_list < SPLINE_LIST_ARRAY_LENGTH (char_splines); + this_list++) + total + += SPLINE_LIST_LENGTH (SPLINE_LIST_ARRAY_ELT (char_splines, this_list)); + +/* REPORT1 ("=%u", total); */ + + return char_splines; +} + +/* Set up the internal parameters from the external ones */ + +void +fit_set_params(SELVALS *selVals) +{ + align_threshold = selVals->align_threshold; + corner_always_threshold = selVals->corner_always_threshold; + corner_surround = selVals->corner_surround; + corner_threshold = selVals->corner_threshold; + error_threshold = selVals->error_threshold; + filter_alternative_surround = selVals->filter_alternative_surround; + filter_epsilon = selVals->filter_epsilon; + filter_iteration_count = selVals->filter_iteration_count; + filter_percent = selVals->filter_percent; + filter_secondary_surround = selVals->filter_secondary_surround; + filter_surround = selVals->filter_surround; + keep_knees = selVals->keep_knees; + line_reversion_threshold = selVals->line_reversion_threshold; + line_threshold = selVals->line_threshold; + reparameterize_improvement = selVals->reparameterize_improvement; + reparameterize_threshold = selVals->reparameterize_threshold; + subdivide_search = selVals->subdivide_search; + subdivide_surround = selVals->subdivide_surround; + subdivide_threshold = selVals->subdivide_threshold; + tangent_surround = selVals->tangent_surround; +} + +void +fit_set_default_params(SELVALS *selVals) +{ + selVals->align_threshold = align_threshold; + selVals->corner_always_threshold = corner_always_threshold; + selVals->corner_surround = corner_surround; + selVals->corner_threshold = corner_threshold; + selVals->error_threshold = error_threshold; + selVals->filter_alternative_surround = filter_alternative_surround; + selVals->filter_epsilon = filter_epsilon; + selVals->filter_iteration_count = filter_iteration_count; + selVals->filter_percent = filter_percent; + selVals->filter_secondary_surround = filter_secondary_surround; + selVals->filter_surround = filter_surround; + selVals->keep_knees = keep_knees; + selVals->line_reversion_threshold = line_reversion_threshold; + selVals->line_threshold = line_threshold; + selVals->reparameterize_improvement = reparameterize_improvement; + selVals->reparameterize_threshold = reparameterize_threshold; + selVals->subdivide_search = subdivide_search; + selVals->subdivide_surround = subdivide_surround; + selVals->subdivide_threshold = subdivide_threshold; + selVals->tangent_surround = tangent_surround; +} + +/* 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) +{ + curve_type curve; + unsigned this_curve, this_spline; + unsigned curve_list_length = CURVE_LIST_LENGTH (curve_list); + spline_list_type curve_list_splines = *new_spline_list (); + + /* 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. */ + if (!keep_knees) + { +/* LOG ("\nRemoving knees:\n"); */ + for (this_curve = 0; this_curve < curve_list_length; this_curve++) + { +/* LOG1 ("#%u:", this_curve); */ + remove_knee_points (CURVE_LIST_ELT (curve_list, this_curve), + CURVE_LIST_CLOCKWISE (curve_list)); + } + } + + /* 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++) + { +/* LOG1 ("#%u: ", this_curve); */ + filter (CURVE_LIST_ELT (curve_list, this_curve)); +/* REPORT ("f"); */ + } + + /* 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) && CURVE_LENGTH (curve) != 3) + 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); + +/* REPORT1 (" %u", this_curve); */ +/* LOG1 ("\nFitting curve #%u:\n", this_curve); */ + + curve_splines = fit_curve (current_curve); + if (curve_splines == NULL) + printf("Could not fit curve #%u", this_curve); + else + { +/* LOG1 ("Fitted splines for curve #%u:\n", this_curve); */ + for (this_spline = 0; + this_spline < SPLINE_LIST_LENGTH (*curve_splines); + this_spline++) + { +/* LOG1 (" %u: ", this_spline); */ +/* if (logging) */ +/* print_spline (log_ +file, */ +/* 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); + + concat_spline_lists (&curve_list_splines, *curve_splines); +/* REPORT1 ("(%u)", SPLINE_LIST_LENGTH (*curve_splines)); */ + } + } + + + /* We do this for each outline's spline list because when a point + is changed, it needs to be changed in both segments in which it + appears---and the segments might be in different curves. */ + align (&curve_list_splines); + + 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) +{ + spline_list_type *fitted_splines; + + if (CURVE_LENGTH (curve) < 2) + { + printf ("Tried to fit curve with less than two points"); + return NULL; + } + + /* Do we have enough points to fit with a spline? */ + fitted_splines = CURVE_LENGTH (curve) < 4 + ? fit_with_line (curve) + : fit_with_least_squares (curve); + + return fitted_splines; +} + +/* 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) +{ + 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); + +/* LOG1 ("#%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) > corner_surround * 2 + 2) + { + corner_list = find_corners (pixel_o); + } + else + { + corner_list.data = NULL; + corner_list.length = 0; + } + + /* 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)); + + /* This curve is cyclic. */ + 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)); + + for (p = 0; p <= GET_INDEX (corner_list, 0); p++) + append_pixel (curve, O_COORDINATE (pixel_o, p)); + } + +/* LOG1 (" [%u].\n", corner_list.length); */ + + /* 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); \ + /*LOG4 (" (%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) +{ + unsigned p; + index_list_type corner_list = new_index_list (); + + /* Consider each pixel on the outline in turn. */ + for (p = 0; p < O_LENGTH (pixel_outline); p++) + { + real corner_angle; + vector_type in_vector, out_vector; + + /* Check if the angle is small enough. */ + find_vectors (p, pixel_outline, &in_vector, &out_vector); + corner_angle = Vangle (in_vector, out_vector); + + if (fabs (corner_angle) <= 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. */ + real 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 <= 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 + 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); + corner_angle = Vangle (in_vector, out_vector); + + /* 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 > corner_always_threshold + && best_corner_index >= p) + { + unsigned i; + + APPEND_CORNER (best_corner_index, best_corner_angle, '/'); + + for (i = 0; i < INDEX_LIST_LENGTH (equally_good_list); i++) + APPEND_CORNER (GET_INDEX (equally_good_list, i), + 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) - 1); + + 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) +{ + int i; + unsigned n_done; + coordinate_type candidate = O_COORDINATE (outline, test_index); + + in->dx = 0.0; + in->dy = 0.0; + out->dx = 0.0; + out->dy = 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)); + +#if 0 + /* We don't need this code any more, because now we create the pixel + outline from the corners of the pixels, rather than the edges. */ + + /* To see why we need this test, consider the following + case: four pixels stacked vertically with no other adjacent pixels, + i.e., * + *x + * + * + *** (etc.) We are considering the pixel marked `x' for cornerhood. + The out vector at this point is going to be the zero vector (if + `corner_surround' is 3), because the first + pixel on the outline is the one above the x, the second pixel x + itself, and the third the one below x. (Remember that we go + around the edges of the pixels to find the outlines, not the + pixels themselves.) */ + if (magnitude (*in) == 0.0) + { + WARNING ("Zero magnitude in"); + return corner_threshold + 1.0; + } +#endif /* 0 */ + + /* 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)); + +#if 0 + /* As with the test for the in vector, we don't need this any more. */ + if (magnitude (*out) == 0.0) + { + WARNING ("Zero magnitude out"); + return corner_threshold + 1.0; + } +#endif /* 0 */ +} + + +/* 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) +{ + unsigned j; + unsigned last; + index_list_type new = 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; + printf ("needed exchange"); /* xx -- really have to sort? */ + } + } + + /* 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); + + append_index (&new, current); + if (next == current + 1) + j++; + } + + /* 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) == 0 + || !(last == GET_LAST_INDEX (new) + 1 + || (last == last_index && GET_INDEX (*list, 0) == 0))) + append_index (&new, last); + + free_index_list (list); + *list = new; +} + +/* 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, boolean clockwise) +{ + int i; + unsigned offset = CURVE_CYCLIC (curve) ? 0 : 1; + coordinate_type 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)) + append_pixel (trimmed_curve, real_to_int_coord (CURVE_POINT (curve, 0))); + + for (i = offset; i < CURVE_LENGTH (curve) - offset; i++) + { + coordinate_type current + = real_to_int_coord (CURVE_POINT (curve, i)); + coordinate_type 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)))) + { + /* LOG2 (" (%d,%d)", current.x, current.y); */ + } + else + { + previous = current; + append_pixel (trimmed_curve, current); + } + } + + if (!CURVE_CYCLIC (curve)) + 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; +} + +/* Smooth the curve by adding in neighboring points. Do this + `filter_iteration_count' times. But don't change the corners. */ + +#if 0 +/* Computing the new point based on a single neighboring point and with + constant percentages, as the `SMOOTH' macro did, isn't quite good + enough. For example, at the top of an `o' the curve might well have + three consecutive horizontal pixels, even though there isn't really a + straight there. With this code, the middle point would remain + unfiltered. */ + +#define SMOOTH(axis) \ + CURVE_POINT (curve, this_point).axis \ + = ((1.0 - center_percent) / 2) \ + * CURVE_POINT (curve, CURVE_PREV (curve, this_point)).axis \ + + center_percent * CURVE_POINT (curve, this_point).axis \ + + ((1.0 - center_percent) / 2) \ + * CURVE_POINT (curve, CURVE_NEXT (curve, this_point)).axis +#endif /* 0 */ + +/* We sometimes need to change the information about the filtered point. + This macro assigns to the relevant variables. */ +#define FILTER_ASSIGN(new) \ + do \ + { \ + in = in_##new; \ + out = out_##new; \ + count = new##_count; \ + angle = angle_##new; \ + } \ + while (0) + +static void +filter (curve_type curve) +{ + unsigned iteration, this_point; + unsigned offset = CURVE_CYCLIC (curve) ? 0 : 1; + + /* 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) + { +/* LOG1 ("Length is %u, not enough to filter.\n", CURVE_LENGTH (curve)); */ + return; + } + + for (iteration = 0; iteration < filter_iteration_count; iteration++) + { + curve_type new_curve = copy_most_of_curve (curve); + + /* Keep the first point on the curve. */ + if (offset) + append_point (new_curve, CURVE_POINT (curve, 0)); + + for (this_point = offset; this_point < CURVE_LENGTH (curve) - offset; + this_point++) + { + real angle, angle_alt; + vector_type in, in_alt, out, out_alt, sum; + unsigned count, alt_count; + real_coordinate_type new_point; + + /* Find the angle using the usual number of surrounding points + on the curve. */ + find_curve_vectors (this_point, curve, filter_surround, + &in, &out, &count); + angle = filter_angle (in, out); + + /* Find the angle using the alternative (presumably smaller) + number. */ + find_curve_vectors (this_point, curve, filter_alternative_surround, + &in_alt, &out_alt, &alt_count); + angle_alt = filter_angle (in_alt, out_alt); + + /* If the alternate angle is enough larger than the usual one + and neither of the components of the sum are zero, use it. + (We don't use absolute value here, since if the alternate + angle is smaller, we don't particularly care, since that + means the curve is pretty flat around the current point, + anyway.) This helps keep small features from disappearing + into the surrounding curve. */ + sum = Vadd (in_alt, out_alt); + if (angle_alt - angle >= filter_epsilon + && sum.dx != 0 && sum.dy != 0) + FILTER_ASSIGN (alt); + +#if 0 +/* This code isn't needed anymore, since we do the filtering in a + somewhat more general way. */ + /* If we're left with an angle of zero, don't stop yet; we + might be at a straight which really isn't one (as in the `o' + discussed above). */ + if (epsilon_equal (angle, 0.0)) + { + real angle_secondary; + vector_type in_secondary, out_secondary; + unsigned in_secondary_count, out_secondary_count; + + find_curve_vectors (this_point, curve, filter_secondary_surround, + &in_secondary, &out_secondary, + &in_secondary_count, &out_secondary_count); + angle_secondary = filter_angle (in_secondary, out_secondary); + if (!epsilon_equal (angle_secondary, 0.0)) + FILTER_ASSIGN (secondary); + } +#endif /* 0 */ + + /* Start with the old point. */ + new_point = CURVE_POINT (curve, this_point); + sum = Vadd (in, out); + new_point.x += sum.dx * filter_percent / count; + new_point.y += sum.dy * filter_percent / count; + + /* Put the newly computed point into a separate curve, so it + doesn't affect future computation (on this iteration). */ + append_point (new_curve, new_point); + } + + /* Just as with the first point, we have to keep the last point. */ + if (offset) + append_point (new_curve, LAST_CURVE_POINT (curve)); + + /* Set the original curve to the newly filtered one, and go again. */ + free_curve (curve); + *curve = *new_curve; + } + +/* log_curve (curve, false); */ +/* display_curve (curve); */ +} + + +/* Return the vectors IN and OUT, computed by looking at SURROUND points + on either side of TEST_INDEX. Also return the number of points in + the vectors in COUNT (we make sure they are the same). */ + +static void +find_curve_vectors (unsigned test_index, curve_type curve, + unsigned surround, + vector_type *in, vector_type *out, unsigned *count) +{ + int i; + unsigned in_count, out_count; + unsigned n_done; + real_coordinate_type candidate = CURVE_POINT (curve, test_index); + + /* Add up the differences from p of the `surround' points + before p. */ + + in->dx = 0.0; + in->dy = 0.0; + + for (i = CURVE_PREV (curve, test_index), n_done = 0; + i >= 0 && n_done < surround; /* Do not wrap around. */ + i = CURVE_PREV (curve, i), n_done++) + *in = Vadd (*in, Psubtract (CURVE_POINT (curve, i), candidate)); + in_count = n_done; + + /* And the points after p. Don't use more points after p than we + ended up with before it. */ + out->dx = 0.0; + out->dy = 0.0; + + for (i = CURVE_NEXT (curve, test_index), n_done = 0; + i < CURVE_LENGTH (curve) && n_done < surround && n_done < in_count; + i = CURVE_NEXT (curve, i), n_done++) + *out = Vadd (*out, Psubtract (CURVE_POINT (curve, i), candidate)); + out_count = n_done; + + /* If we used more points before p than after p, we have to go back + and redo it. (We could just subtract the ones that were missing, + but for this few of points, efficiency doesn't matter.) */ + if (out_count < in_count) + { + in->dx = 0.0; + in->dy = 0.0; + + for (i = CURVE_PREV (curve, test_index), n_done = 0; + i >= 0 && n_done < out_count; + i = CURVE_PREV (curve, i), n_done++) + *in = Vadd (*in, Psubtract (CURVE_POINT (curve, i), candidate)); + in_count = n_done; + } + + assert (in_count == out_count); + *count = in_count; +} + + +/* Find the angle between the vectors IN and OUT, and bring it into the + range [0,45]. */ + +static real +filter_angle (vector_type in, vector_type out) +{ + real angle = Vangle (in, out); + + /* What we want to do between 90 and 180 is the same as what we + want to do between 0 and 90. */ + angle = fmod (angle, 1990.0); + + /* And what we want to do between 45 and 90 is the same as + between 0 and 45, only reversed. */ + if (angle > 45.0) angle = 90.0 - angle; + + return angle; +} + +/* 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 = new_spline (); + +/* LOG ("Fitting with straight line:\n"); */ +/* REPORT ("l"); */ + + SPLINE_DEGREE (line) = LINEAR; + 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 (log_file, line); */ +/* } */ + + return init_spline_list (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 try reparameterizing, i.e., finding new, and supposedly better, + t values. If that still fails, we subdivide the curve. */ + +static spline_list_type * +fit_with_least_squares (curve_type curve) +{ + real error, best_error = FLT_MAX; + spline_type spline, best_spline; + spline_list_type *spline_list; + unsigned worst_point; + unsigned iteration = 0; + real previous_error = FLT_MAX; + real improvement = FLT_MAX; + + /* FIXME: Initialize best_spline to zeroes. This is strictly not + necessary as best_spline is always set in the loop below. But the + compiler thinks it isn't and warns. Ideally, the code should be + rewritten such that best_spline and best_error are initialized with + the first values before the loop begins. */ + memset (&best_spline, 0, sizeof best_spline); + +/* 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); + find_tangent (curve, /* to_start */ false, /* cross_curve */ false); + + set_initial_parameter_values (curve); + + /* Now we loop, reparameterizing and/or subdividing, until CURVE has + been fit. */ + while (true) + { +/* LOG (" fitted to spline:\n"); */ + + spline = fit_one_spline (curve); + +/* if (logging) */ +/* { */ +/* LOG (" "); */ +/* print_spline (log_file, spline); */ +/* } */ + + error = find_error (curve, spline, &worst_point); + if (error > previous_error) + { +/* LOG ("Reparameterization made it worse.\n"); */ + /* Just fall through; we will subdivide. */ + } + else + { + best_error = error; + best_spline = spline; + } + + improvement = 1.0 - error / previous_error; + + /* Don't exit, even if the error is less than `error_threshold', + since we might be able to improve the fit with further + reparameterization. If the reparameterization made it worse, + we will exit here, since `improvement' will be negative. */ + if (improvement < reparameterize_improvement + || error > reparameterize_threshold) + break; + + iteration++; +/* LOG3 ("Reparameterization #%u (error was %.3f, a %u%% improvement):\n", */ +/* iteration, error, ((unsigned) (improvement * 100.0))); */ + + /* The reparameterization might fail, if the initial fit was + better than `reparameterize_threshold', yet worse than the + Newton-Raphson algorithm could handle. */ + if (!reparameterize (curve, spline)) + break; + + previous_error = error; + } + + /* Go back to the best fit. */ + spline = best_spline; + error = best_error; + + if (error < error_threshold) + { + /* The points were fitted with a (possibly reparameterized) + 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)) + { + SPLINE_DEGREE (spline) = LINEAR; +/* LOG ("Changed to line.\n"); */ + } + spline_list = init_spline_list (spline); +/* LOG1 ("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; + +/* REPORT ("s"); */ +/* LOG1 ("\nSubdividing (error %.3f):\n", error); */ +/* LOG3 (" Original point: (%.3f,%.3f), #%u.\n", */ +/* CURVE_POINT (curve, worst_point).x, */ +/* CURVE_POINT (curve, worst_point).y, worst_point); */ + subdivision_index = find_subdivision (curve, worst_point); +/* LOG3 (" Final point: (%.3f,%.3f), #%u.\n", */ +/* CURVE_POINT (curve, subdivision_index).x, */ +/* CURVE_POINT (curve, subdivision_index).y, subdivision_index); */ +/* display_subdivision (CURVE_POINT (curve, 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); + 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); + right_spline_list = fit_curve (right_curve); + + /* 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) + { + WARNING ("could not fit left spline list"); +/* LOG1 ("Could not fit spline to left curve (%x).\n", */ +/* (unsigned) left_curve); */ + } + else + concat_spline_lists (spline_list, *left_spline_list); + + if (right_spline_list == NULL) + { + WARNING ("could not fit right spline list"); +/* LOG1 ("Could not fit spline to right curve (%x).\n", */ +/* (unsigned) right_curve); */ + } + else + concat_spline_lists (spline_list, *right_spline_list); + } + + 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 (1 - (t)) +#define B1(t) (3.0 * (t) * SQUARE (1 - (t))) +#define B2(t) (3.0 * SQUARE (t) * (1 - (t))) +#define B3(t) CUBE (t) + +#define U(i) CURVE_T (curve, i) + +static spline_type +fit_one_spline (curve_type curve) +{ + /* Since our arrays are zero-based, the `C0' and `C1' here correspond + to `C1' and `C2' in the paper. */ + real X_C1_det, C0_X_det, C0_C1_det; + real alpha1, alpha2; + spline_type spline; + vector_type start_vector, end_vector; + unsigned i; + vector_type t1_hat = *CURVE_START_TANGENT (curve); + vector_type t2_hat = *CURVE_END_TANGENT (curve); + real C[2][2] = { { 0.0, 0.0 }, { 0.0, 0.0 } }; + real X[2] = { 0.0, 0.0 }; + int Alen = CURVE_LENGTH (curve); + vector_type *A; + + A = g_new0 (vector_type, Alen * 2); + + START_POINT (spline) = CURVE_POINT (curve, 0); + END_POINT (spline) = LAST_CURVE_POINT (curve); + SPLINE_LINEARITY (spline) = 0; + start_vector = make_vector (START_POINT (spline)); + end_vector = make_vector (END_POINT (spline)); + + for (i = 0; i < CURVE_LENGTH (curve); i++) + { + A[i*2+0] = Vmult_scalar (t1_hat, B1 (U (i))); + A[i*2+1] = Vmult_scalar (t2_hat, B2 (U (i))); + } + + for (i = 0; i < CURVE_LENGTH (curve); i++) + { + vector_type temp, temp0, temp1, temp2, temp3; + vector_type *Ai = &A[i*2]; + + 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 (U (i))); + temp1 = Vmult_scalar (start_vector, B1 (U (i))); + temp2 = Vmult_scalar (end_vector, B2 (U (i))); + temp3 = Vmult_scalar (end_vector, B3 (U (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]); + } + + 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) + FATAL ("zero determinant of C0*C1"); + + 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) = CUBIC; + + g_free (A); + + return spline; +} + +/* Find closer-to-optimal t values for the given x,y's and control + points, using Newton-Raphson iteration. A good description of this + is in Plass & Stone. This routine performs one step in the + iteration, not the whole thing. */ + +static boolean +reparameterize (curve_type curve, spline_type S) +{ + unsigned p, i; + spline_type S1, S2; /* S' and S''. */ + +/* REPORT ("r"); */ + + /* Find the first and second derivatives of S. To make + `evaluate_spline' work, we fill the beginning points (i.e., the first + two for a linear spline and the first three for a quadratic one), + even though this is at odds with the rest of the program. */ + for (i = 0; i < 3; i++) + { + S1.v[i].x = 3.0 * (S.v[i + 1].x - S.v[i].x); + S1.v[i].y = 3.0 * (S.v[i + 1].y - S.v[i].y); + } + S1.v[i].x = S1.v[i].y = -1.0; /* These will never be accessed. */ + SPLINE_DEGREE (S1) = QUADRATIC; + + for (i = 0; i < 2; i++) + { + S2.v[i].x = 2.0 * (S1.v[i + 1].x - S1.v[i].x); + S2.v[i].y = 2.0 * (S1.v[i + 1].y - S1.v[i].y); + } + S2.v[2].x = S2.v[2].y = S2.v[3].x = S2.v[3].y = -1.0; + SPLINE_DEGREE (S2) = LINEAR; + + for (p = 0; p < CURVE_LENGTH (curve); p++) + { + real new_distance, old_distance; + real_coordinate_type new_point; + real_coordinate_type point = CURVE_POINT (curve, p); + real t = CURVE_T (curve, p); + + /* Find the points at this t on S, S', and S''. */ + real_coordinate_type S_t = evaluate_spline (S, t); + real_coordinate_type S1_t = evaluate_spline (S1, t); + real_coordinate_type S2_t = evaluate_spline (S2, t); + + /* The differences in x and y (Q1(t) on p.62 of Schneider's thesis). */ + real_coordinate_type d; + real numerator; + real denominator; + + d.x = S_t.x - point.x; + d.y = S_t.y - point.y; + + /* The step size, f(t)/f'(t). */ + numerator = d.x * S1_t.x + d.y * S1_t.y; + denominator = (SQUARE (S1_t.x) + d.x * S2_t.x + + SQUARE (S1_t.y) + d.y * S2_t.y); + + /* We compute the distances only to be able to check that we + really are moving closer. I don't know how this condition can + be reliably checked for in advance, but I know what it means in + practice: the original fit was not good enough for the + Newton-Raphson iteration to converge. Therefore, we need to + abort the reparameterization, and subdivide. */ + old_distance = distance (S_t, point); + CURVE_T (curve, p) -= numerator / denominator; + new_point = evaluate_spline (S, CURVE_T (curve, p)); + new_distance = distance (new_point, point); + + if (new_distance > old_distance) + { +/* REPORT ("!"); */ +/* LOG3 (" Stopped reparameterizing; %.3f > %.3f at point %u.\n", */ +/* new_distance, old_distance, p); */ + return false; + } + + /* The t value might be negative or > 1, if the choice of control + points wasn't so great. We have no difficulty in evaluating + a spline at a t outside the range zero to one, though, so it + doesn't matter. (Although it is a little unconventional.) */ + } +/* LOG (" reparameterized curve:\n "); */ +/* log_curve (curve, true); */ + + return true; +} + +/* This routine finds the best place to subdivide the curve CURVE, + somewhere near to the point whose index is INITIAL. Originally, + curves were always subdivided at the point of worst error, which is + intuitively appealing, but doesn't always give the best results. For + example, at the end of a serif that tapers into the stem, the best + subdivision point is at the point where they join, even if the worst + point is a little ways into the serif. + + We return the index of the point at which to subdivide. */ + +static unsigned +find_subdivision (curve_type curve, unsigned initial) +{ + unsigned i, n_done; + int best_point = -1; + vector_type best = { FLT_MAX, FLT_MAX }; + unsigned search = subdivide_search * CURVE_LENGTH (curve); + +/* LOG1 (" Number of points to search: %u.\n", search); */ + + /* We don't want to find the first (or last) point in the curve. */ + for (i = initial, n_done = 0; i > 0 && n_done < search; + i = CURVE_PREV (curve, i), n_done++) + { + if (test_subdivision_point (curve, i, &best)) + { + best_point = i; +/* LOG3 (" Better point: (%.3f,%.3f), #%u.\n", */ +/* CURVE_POINT (curve, i).x, CURVE_POINT (curve, i).y, i); */ + } + } + + /* If we found a good one, let's take it. */ + if (best_point != -1) + return best_point; + + for (i = CURVE_NEXT (curve, initial), n_done = 0; + i < CURVE_LENGTH (curve) - 1 && n_done < search; + i = CURVE_NEXT (curve, i), n_done++) + { + if (test_subdivision_point (curve, i, &best)) + { + best_point = i; +/* LOG3 (" Better point at (%.3f,%.3f), #%u.\n", */ +/* CURVE_POINT (curve, i).x, CURVE_POINT (curve, i).y, i); */ + } + } + + /* If we didn't find any better point, return the original. */ + return best_point == -1 ? initial : best_point; +} + + +/* Here are some macros that decide whether or not we're at a + ``join point'', as described above. */ +#define ONLY_ONE_LESS(v) \ + (((v).dx < subdivide_threshold && (v).dy > subdivide_threshold) \ + || ((v).dy < subdivide_threshold && (v).dx > subdivide_threshold)) + +#define BOTH_GREATER(v) \ + ((v).dx > subdivide_threshold && (v).dy > subdivide_threshold) + +/* We assume that the vectors V1 and V2 are nonnegative. */ +#define JOIN(v1, v2) \ + ((ONLY_ONE_LESS (v1) && BOTH_GREATER (v2)) \ + || (ONLY_ONE_LESS (v2) && BOTH_GREATER (v1))) + +/* If the component D of the vector V is smaller than the best so far, + update the best point. */ +#define UPDATE_BEST(v, d) \ + do \ + { \ + if ((v).d < subdivide_threshold && (v).d < best->d) \ + best->d = (v).d; \ + } \ + while (0) + + +/* If the point INDEX in the curve CURVE is the best subdivision point + we've found so far, update the vector BEST. */ + +static boolean +test_subdivision_point (curve_type curve, unsigned index, vector_type *best) +{ + unsigned count; + vector_type in, out; + boolean join = false; + + find_curve_vectors (index, curve, subdivide_surround, &in, &out, &count); + + /* We don't want to subdivide at points which are very close to the + endpoints, so if the vectors aren't computed from as many points as + we asked for, don't bother checking this point. */ + if (count == subdivide_surround) + { + in = Vabs (in); + out = Vabs (out); + + join = JOIN (in, out); + if (join) + { + UPDATE_BEST (in, dx); + UPDATE_BEST (in, dy); + UPDATE_BEST (out, dx); + UPDATE_BEST (out, dy); + } + } + + return join; +} + +/* 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++) + { + real_coordinate_type point = CURVE_POINT (curve, p), + previous_p = CURVE_POINT (curve, p - 1); + real d = distance (point, previous_p); + CURVE_T (curve, p) = CURVE_T (curve, p - 1) + d; + } + + assert (LAST_CURVE_T (curve) != 0.0); + + for (p = 1; p < CURVE_LENGTH (curve); p++) + CURVE_T (curve, p) = CURVE_T (curve, p) / LAST_CURVE_T (curve); + +/* 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, boolean to_start_point, boolean cross_curve) +{ + vector_type tangent; + vector_type **curve_tangent = to_start_point ? &(CURVE_START_TANGENT (curve)) + : &(CURVE_END_TANGENT (curve)); + unsigned n_points = 0; + +/* LOG1 (" tangent to %s: ", to_start_point ? "start" : "end"); */ + + if (*curve_tangent == NULL) + { + *curve_tangent = g_new (vector_type, 1); + tangent = find_half_tangent (curve, to_start_point, &n_points); + + if (cross_curve) + { + curve_type adjacent_curve + = to_start_point ? PREVIOUS_CURVE (curve) : NEXT_CURVE (curve); + vector_type tangent2 + = find_half_tangent (adjacent_curve, !to_start_point, &n_points); + +/* LOG2 ("(adjacent curve half tangent (%.3f,%.3f)) ", */ +/* tangent2.dx, tangent2.dy); */ + tangent = Vadd (tangent, tangent2); + } + + assert (n_points > 0); + **curve_tangent = Vmult_scalar (tangent, 1.0 / n_points); + } + else + { +/* LOG ("(already computed) "); */ + } + +/* LOG2 ("(%.3f,%.3f).\n", (*curve_tangent)->dx, (*curve_tangent)->dy); */ +} + + +/* 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, boolean to_start_point, unsigned *n_points) +{ + unsigned p; + int factor = to_start_point ? 1 : -1; + unsigned tangent_index = to_start_point ? 0 : c->length - 1; + real_coordinate_type tangent_point = CURVE_POINT (c, tangent_index); + vector_type tangent; + + tangent.dx = 0.0; + tangent.dy = 0.0; + + for (p = 1; p <= tangent_surround; p++) + { + int this_index = p * factor + tangent_index; + real_coordinate_type this_point; + + if (this_index < 0 || this_index >= 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), + 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 real +find_error (curve_type curve, spline_type spline, unsigned *worst_point) +{ + unsigned this_point; + real total_error = 0.0; + real worst_error = FLT_MIN; + + *worst_point = CURVE_LENGTH (curve) + 1; /* A sentinel value. */ + + for (this_point = 0; this_point < CURVE_LENGTH (curve); this_point++) + { + real_coordinate_type curve_point = CURVE_POINT (curve, this_point); + real t = CURVE_T (curve, this_point); + real_coordinate_type spline_point = evaluate_spline (spline, t); + real 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 + printf ("No worst point found; something is wrong"); + } + else + { +/* LOG4 (" Worst error (at (%.3f,%.3f), point #%u) was %.3f.\n", */ +/* CURVE_POINT (curve, *worst_point).x, */ +/* CURVE_POINT (curve, *worst_point).y, *worst_point, worst_error); */ +/* LOG1 (" Total error was %.3f.\n", total_error); */ +/* LOG2 (" 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 boolean +spline_linear_enough (spline_type *spline, curve_type curve) +{ + real A, B, C, slope; + unsigned this_point; + real distance = 0.0; + +/* LOG ("Checking linearity:\n"); */ + + /* For a line described by Ax + By + C = 0, the distance d from a + point (x0,y0) to that line is: + + d = | Ax0 + By0 + C | / sqrt (A^2 + B^2). + + We can find A, B, and C from the starting and ending points, + unless the line defined by those two points is vertical. */ + + if (epsilon_equal (START_POINT (*spline).x, END_POINT (*spline).x)) + { + A = 1; + B = 0; + C = -START_POINT (*spline).x; + } + else + { + /* Plug the spline's starting and ending points into the two-point + equation for a line, that is, + + (y - y1) = ((y2 - y1)/(x2 - x1)) * (x - x1) + + to get the values for A, B, and C. */ + + slope = ((END_POINT (*spline).y - START_POINT (*spline).y) + / (END_POINT (*spline).x - START_POINT (*spline).x)); + A = -slope; + B = 1; + C = slope * START_POINT (*spline).x - START_POINT (*spline).y; + } +/* LOG3 (" Line is %.3fx + %.3fy + %.3f = 0.\n", A, B, C); */ + + for (this_point = 0; this_point < CURVE_LENGTH (curve); this_point++) + { + real t = CURVE_T (curve, this_point); + real_coordinate_type spline_point = evaluate_spline (*spline, t); + + distance += fabs (A * spline_point.x + B * spline_point.y + C) + / sqrt (A * A + B * B); + } +/* LOG1 (" Total distance is %.3f, ", distance); */ + + distance /= CURVE_LENGTH (curve); +/* LOG1 ("which is %.3f normalized.\n", distance); */ + + /* 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) = distance / CURVE_LENGTH (curve); +/* LOG1 (" Final linearity: %.3f.\n", SPLINE_LINEARITY (*spline)); */ + + return distance < line_threshold; +} + + +/* 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) +{ + unsigned this_spline; + boolean found_cubic = false; + unsigned length = SPLINE_LIST_LENGTH (*spline_list); + +/* LOG1 ("\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)) == CUBIC) + { + 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) == LINEAR) + { +/* LOG1 (" #%u: ", this_spline); */ + if (SPLINE_LINEARITY (s) > line_reversion_threshold) + { +/* LOG ("reverted, "); */ + SPLINE_DEGREE (SPLINE_LIST_ELT (*spline_list, this_spline)) + = CUBIC; + } +/* LOG1 ("linearity %.3f.\n", SPLINE_LINEARITY (s)); */ + } + } + else + { +/* LOG (" No lines.\n"); */ + } +} + +/* When we have finished fitting an entire pixel outline to a spline + list L, we go through L to ensure that any endpoints that are ``close + enough'' (i.e., within `align_threshold') to being the same really + are the same. */ + +/* This macro adjusts the AXIS axis on the starting and ending points on + a particular spline if necessary. */ +#define TRY_AXIS(axis) \ + do \ + { \ + real delta = fabs (end.axis - start.axis); \ + \ + if (!epsilon_equal (delta, 0.0) && delta <= align_threshold) \ + { \ + spline_type *next = &NEXT_SPLINE_LIST_ELT (*l, this_spline); \ + spline_type *prev = &PREV_SPLINE_LIST_ELT (*l, this_spline); \ + \ + START_POINT (*s).axis = END_POINT (*s).axis \ + = END_POINT (*prev).axis = START_POINT (*next).axis \ + = (start.axis + end.axis) / 2; \ + spline_change = true; \ + } \ + } \ + while (0) + +static void +align (spline_list_type *l) +{ + boolean change; + unsigned this_spline; + unsigned length = SPLINE_LIST_LENGTH (*l); + +/* LOG1 ("\nAligning spline list (length %u):\n", length); */ + + do + { + change = false; + +/* LOG (" "); */ + + for (this_spline = 0; this_spline < length; this_spline++) + { + boolean spline_change = false; + spline_type *s = &SPLINE_LIST_ELT (*l, this_spline); + real_coordinate_type start = START_POINT (*s); + real_coordinate_type end = END_POINT (*s); + + TRY_AXIS (x); + TRY_AXIS (y); + if (spline_change) + { +/* LOG1 ("%u ", this_spline); */ + change |= spline_change; + } + } +/* LOG ("\n"); */ + } + while (change); +} + +/* 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) + { + g_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)++; + list->data = (unsigned *)g_realloc(list->data,(INDEX_LIST_LENGTH (*list)) * sizeof(unsigned)); +/* XRETALLOC (list->data, INDEX_LIST_LENGTH (*list), unsigned); */ + list->data[INDEX_LIST_LENGTH (*list) - 1] = new_index; +} diff --git a/plug-ins/selection-to-path/fit.h b/plug-ins/selection-to-path/fit.h new file mode 100644 index 0000000..f009c9a --- /dev/null +++ b/plug-ins/selection-to-path/fit.h @@ -0,0 +1,54 @@ +/* fit.h: convert the pixel representation to splines. + * + * 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 3, 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, see <https://www.gnu.org/licenses/>. + */ + +#ifndef FIT_H +#define FIT_H + +#include "pxl-outline.h" +#include "spline.h" + + +/* See fit.c for descriptions of these variables, all of which can be + set using options. */ +extern real align_threshold; +extern real corner_always_threshold; +extern unsigned corner_surround; +extern real corner_threshold; +extern real error_threshold; +extern unsigned filter_alternative_surround; +extern real filter_epsilon; +extern unsigned filter_iteration_count; +extern real filter_percent; +extern unsigned filter_surround; +extern boolean keep_knees; +extern real line_reversion_threshold; +extern real line_threshold; +extern real reparameterize_improvement; +extern real reparameterize_threshold; +extern real subdivide_search; +extern unsigned subdivide_surround; +extern real subdivide_threshold; +extern unsigned tangent_surround; + + +/* Fit splines and lines to LIST. */ +extern spline_list_array_type fitted_splines (pixel_outline_list_type list); +void fit_set_params(SELVALS *); +void fit_set_default_params(SELVALS *); + +#endif /* not FIT_H */ diff --git a/plug-ins/selection-to-path/global.h b/plug-ins/selection-to-path/global.h new file mode 100644 index 0000000..1ee5962 --- /dev/null +++ b/plug-ins/selection-to-path/global.h @@ -0,0 +1,213 @@ +/* global.h: extend the standard programming environment a little. This + * is included from config.h, which everyone includes. + * + * 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 3, 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, see <https://www.gnu.org/licenses/>. + */ + +#ifndef GLOBAL_H +#define GLOBAL_H + +#include <stdlib.h> + +#include "types.h" + +/* Define common sorts of messages. */ + +/* This should be called only after a system call fails. */ +#define FATAL_PERROR(s) do { perror (s); exit (errno); } while (0) + + +#define START_FATAL() do { fputs ("fatal: ", stderr) +#define END_FATAL() fputs (".\n", stderr); exit (1); } while (0) + +#define FATAL(x) \ + START_FATAL (); fprintf (stderr, "%s", x); END_FATAL () +#define FATAL1(s, e1) \ + START_FATAL (); fprintf (stderr, s, e1); END_FATAL () +#define FATAL2(s, e1, e2) \ + START_FATAL (); fprintf (stderr, s, e1, e2); END_FATAL () +#define FATAL3(s, e1, e2, e3) \ + START_FATAL (); fprintf (stderr, s, e1, e2, e3); END_FATAL () +#define FATAL4(s, e1, e2, e3, e4) \ + START_FATAL (); fprintf (stderr, s, e1, e2, e3, e4); END_FATAL () + + +#define START_WARNING() do { fputs ("warning: ", stderr) +#define END_WARNING() fputs (".\n", stderr); fflush (stderr); } while (0) + +#define WARNING(x) \ + START_WARNING (); fprintf (stderr, "%s", x); END_WARNING () +#define WARNING1(s, e1) \ + START_WARNING (); fprintf (stderr, s, e1); END_WARNING () +#define WARNING2(s, e1, e2) \ + START_WARNING (); fprintf (stderr, s, e1, e2); END_WARNING () +#define WARNING3(s, e1, e2, e3) \ + START_WARNING (); fprintf (stderr, s, e1, e2, e3); END_WARNING () +#define WARNING4(s, e1, e2, e3, e4) \ + START_WARNING (); fprintf (stderr, s, e1, e2, e3, e4); END_WARNING () + +/* Define useful abbreviations. */ + +/* This is the maximum number of numerals that result when a 64-bit + integer is converted to a string, plus one for a trailing null byte, + plus one for a sign. */ +#define MAX_INT_LENGTH 21 + +/* Printer's points, as defined by TeX (and good typesetters everywhere). */ +#define POINTS_PER_INCH 72.27 + +/* Convert a number V in pixels to printer's points, and vice versa, + assuming a resolution of DPI pixels per inch. */ +#define PIXELS_TO_POINTS(v, dpi) (POINTS_PER_INCH * (v) / (dpi)) +#define POINTS_TO_REAL_PIXELS(v, dpi) ((v) * (dpi) / POINTS_PER_INCH) +#define POINTS_TO_PIXELS(v, dpi) ((int) (POINTS_TO_REAL_PIXELS (v, dpi) + .5)) + +/* Some simple numeric operations. It is possible to define these much + more cleanly in GNU C, but we haven't done that (yet). */ +#define SQUARE(x) ((x) * (x)) +#define CUBE(x) ((x) * (x) * (x)) +#define SAME_SIGN(u,v) ((u) >= 0 && (v) >= 0 || (u) < 0 && (v) < 0) +#define SIGN(x) ((x) > 0 ? 1 : (x) < 0 ? -1 : 0) +#define SROUND(x) ((int) ((int) (x) + .5 * SIGN (x))) + +#ifndef MAX +#define MAX(a, b) ((a) > (b) ? (a) : (b)) +#endif +#ifndef MIN +#define MIN(a, b) ((a) < (b) ? (a) : (b)) +#endif + +/* Too bad C doesn't define operators for these. */ +#define MAX_EQUALS(var, expr) if ((expr) > (var)) (var) = (expr) +#define MIN_EQUALS(var, expr) if ((expr) < (var)) (var) = (expr) + +#define STREQ(s1, s2) (strcmp (s1, s2) == 0) + +/* Declarations for commonly-used routines we provide ourselves. The + ones here are only needed by us, so we do not provide them in + unprototyped form. Others are declared both ways in lib.h. */ + +#if 0 /* These aren't actually defined anywhere */ +/* Return the current date and time a la date(1). */ +extern string now (void); + +/* Check if a string is a valid floating-point or decimal integer. + Returns false if passed NULL. */ +extern boolean float_ok (string); +extern boolean integer_ok (string); + +/* Like `atoi', but disallow negative numbers. */ +extern const unsigned atou (string); + +/* The converses of atoi, atou, and atof. These all return dynamically + allocated strings. `dtoa' is so-named because `ftoa' is a library + function on some systems (the IBM RT), and the loader complains that + is defined twice, for reasons I don't understand. */ +extern string itoa (int); +extern string utoa (unsigned); +extern string dtoa (double); + +#endif + +/* Like their stdio counterparts, but abort on error, after calling + perror(3) with FILENAME as its argument. */ +/* extern FILE *xfopen (string filename, string mode); */ +/* extern void xfclose (FILE *, string filename); */ +/* extern void xfseek (FILE *, long, int, string filename); */ +/* extern four_bytes xftell (FILE *, string filename); */ + +/* Copies the file FROM to the file TO, then unlinks FROM. */ +extern void xrename (string from, string to); + +/* Return NAME with any leading path stripped off. This returns a + pointer into NAME. */ +/* ALT extern string basename (string name); */ + + + +/* If P or *P is null, abort. Otherwise, call free(3) on P, + and then set *P to NULL. */ +extern void safe_free (address *p); + + +/* Math functions. */ + +/* 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. */ +#define REAL_EPSILON 0.00001 +extern boolean epsilon_equal (real v1, real v2); + +/* Arc cosine, in degrees. */ +extern real my_acosd (real); + +/* Return the Euclidean distance between the two points. */ +extern real distance (real_coordinate_type, real_coordinate_type); +extern real int_distance (coordinate_type, coordinate_type); + +/* Slope between two points (delta y per unit x). */ +extern real slope (real_coordinate_type, real_coordinate_type); + +/* Make a real coordinate from an integer one, and vice versa. */ +extern real_coordinate_type int_to_real_coord (coordinate_type); +extern coordinate_type real_to_int_coord (real_coordinate_type); + +/* Test if two integer points are adjacent. */ +extern boolean points_adjacent_p (int row1, int col1, int r2, int c2); + +/* Find the largest and smallest elements of an array. */ +extern void find_bounds (real values[], unsigned value_count, + /* returned: */ real *the_min, real *the_max); + +/* Make all the elements in the array between zero and one. */ +extern real *map_to_unit (real * values, unsigned value_count); + + +/* String functions. */ + +/* Return (a fresh copy of) SOURCE beginning at START and ending at + LIMIT. (Or NULL if LIMIT < START.) */ +extern string substring (string source, const unsigned start, + const unsigned limit); + +/* Change all uppercase letters in S to lowercase. */ +extern string lowercasify (string s); + + +/* Character code parsing. */ + +/* If the string S parses as a character code, this sets *VALID to + `true' and returns the number. If it doesn't, it sets *VALID to + `false' and the return value is garbage. + + We allow any of the following possibilities: a single character, as in + `a' or `0'; a decimal number, as in `21'; an octal number, as in `03' + or `0177'; a hexadecimal number, as in `0x3' or `0xff'. */ +extern charcode_type parse_charcode (string s, boolean *valid); + +/* Like `parse_charcode', but gives a fatal error if the string isn't a + valid character code. */ +extern charcode_type xparse_charcode (string s); + +/* The environment variable name with which to look up auxiliary files. */ +#ifndef LIB_ENVVAR +#define LIB_ENVVAR "FONTUTIL_LIB" +#endif + +#endif /* not GLOBAL_H */ diff --git a/plug-ins/selection-to-path/math.c b/plug-ins/selection-to-path/math.c new file mode 100644 index 0000000..58f3b3f --- /dev/null +++ b/plug-ins/selection-to-path/math.c @@ -0,0 +1,177 @@ +/* math.c: define some simple array operations, and other functions. + * + * 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 3, 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, see <https://www.gnu.org/licenses/>. + */ + +#include "config.h" + +#include <errno.h> +#include <math.h> +#include <stdio.h> + +#include "libgimp/gimp.h" + +#include "types.h" +#include "global.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. */ + +boolean +epsilon_equal (real v1, real v2) +{ + return + v1 == v2 /* Usually they'll be exactly equal, anyway. */ + || fabs (v1 - v2) <= REAL_EPSILON; +} + + +/* Return the Euclidean distance between P1 and P2. */ + +real +distance (real_coordinate_type p1, real_coordinate_type p2) +{ + return hypot (p1.x - p2.x, p1.y - p2.y); +} + + +/* Same thing, for integer points. */ +real +int_distance (coordinate_type p1, coordinate_type p2) +{ + return hypot ((double) p1.x - p2.x, (double) p1.y - p2.y); +} + + +/* Return the arc cosine of V, in degrees in the range zero to 180. V + is taken to be in radians. */ + +real +my_acosd (real v) +{ + real a; + + if (epsilon_equal (v, 1.0)) + v = 1.0; + else if (epsilon_equal (v, -1.0)) + v = -1.0; + + errno = 0; + a = acos (v); + if (errno == ERANGE || errno == EDOM) + FATAL_PERROR ("acosd"); + + return a * 180.0 / G_PI; +} + + +/* The slope of the line defined by COORD1 and COORD2. */ + +real +slope (real_coordinate_type coord1, real_coordinate_type coord2) +{ + g_assert (coord2.x - coord1.x != 0); + + return (coord2.y - coord1.y) / (coord2.x - coord1.x); +} + + +/* Turn an integer point into a real one, and vice versa. */ + +real_coordinate_type +int_to_real_coord (coordinate_type int_coord) +{ + real_coordinate_type real_coord; + + real_coord.x = int_coord.x; + real_coord.y = int_coord.y; + + return real_coord; +} + + +coordinate_type +real_to_int_coord (real_coordinate_type real_coord) +{ + coordinate_type int_coord; + + int_coord.x = SROUND (real_coord.x); + int_coord.y = SROUND (real_coord.y); + + return int_coord; +} + + +/* See if two points (described by their row and column) are adjacent. */ + +boolean +points_adjacent_p (int row1, int col1, int row2, int col2) +{ + int row_diff = abs (row1 - row2); + int col_diff = abs (col1 - col2); + + return + (row_diff == 1 && col_diff == 1) + || (row_diff == 0 && col_diff == 1) + || (row_diff == 1 && col_diff == 0); +} + + +/* Find the largest and smallest elements in an array of reals. */ + +void +find_bounds (real *values, unsigned value_count, real *min, real *max) +{ + unsigned this_value; + + /* We must use FLT_MAX and FLT_MIN, instead of the corresponding + values for double, because gcc uses the native atof to parse + floating point constants, and many atof's choke on the extremes. */ + *min = FLT_MAX; + *max = FLT_MIN; + + for (this_value = 0; this_value < value_count; this_value++) + { + if (values[this_value] < *min) + *min = values[this_value]; + + if (values[this_value] > *max) + *max = values[this_value]; + } +} + +/* Map a range of numbers, some positive and some negative, into all + positive, with the greatest being at one and the least at zero. + + This allocates new memory. */ + +real * +map_to_unit (real *values, unsigned value_count) +{ + real smallest, largest; + int this_value; + real *mapped_values = g_new (real, value_count); + + find_bounds (values, value_count, &smallest, &largest); + + largest -= smallest; /* We never care about largest itself. */ + + for (this_value = 0; this_value < value_count; this_value++) + mapped_values[this_value] = (values[this_value] - smallest) / largest; + + return mapped_values; +} diff --git a/plug-ins/selection-to-path/pxl-outline.c b/plug-ins/selection-to-path/pxl-outline.c new file mode 100644 index 0000000..a339ff3 --- /dev/null +++ b/plug-ins/selection-to-path/pxl-outline.c @@ -0,0 +1,254 @@ +/* pxl-outline.c: find the edges of the bitmap image; we call each such + * edge an ``outline''; each outline is made up of one or more pixels; + * and each pixel participates via one or more edges. + * + * 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 3, 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, see <https://www.gnu.org/licenses/>. + */ + +#include "config.h" + +#include "global.h" +#include "selection-to-path.h" +#include "bitmap.h" +#include "edge.h" +#include "pxl-outline.h" + +#include "libgimp/stdplugins-intl.h" + +static pixel_outline_type find_one_outline (edge_type, + unsigned, unsigned, bitmap_type *); +static void append_pixel_outline (pixel_outline_list_type *, + pixel_outline_type); +static pixel_outline_type new_pixel_outline (void); +static void append_outline_pixel (pixel_outline_type *, coordinate_type); +static void append_coordinate (pixel_outline_type *, int, int, edge_type); + + +static bitmap_type +local_new_bitmap (unsigned width,unsigned height) +{ + bitmap_type answer; + unsigned size = width * height; + + + BITMAP_HEIGHT(answer) = height; + BITMAP_WIDTH(answer) = width; + + BITMAP_BITS (answer) = g_new0 (one_byte, size); /* g_new returns NULL if size == 0 */ + +/* printf("local_new_bitmap size = %d @[%p]\n",size,BITMAP_BITS (answer)); */ + + return answer; +} + +static void +local_free_bitmap (bitmap_type *b) +{ + if (BITMAP_BITS (*b) != NULL) + safe_free ((address *) &BITMAP_BITS (*b)); +} + +/* A character is made up of a list of one or more outlines. Here, we + go through a character's bitmap top to bottom, left to right, looking + for the next pixel with an unmarked edge also on the character's outline. + Each one of these we find is the starting place for one outline. We + find these outlines and put them in a list to return. */ + +pixel_outline_list_type +find_outline_pixels (void) +{ + pixel_outline_list_type outline_list; + unsigned row, col; + gint height; + gint width; + bitmap_type marked = local_new_bitmap (sel_get_width(),sel_get_height()); + +/* printf("width = %d, height = %d\n",BITMAP_WIDTH(marked),BITMAP_HEIGHT(marked)); */ + + gimp_progress_init (_("Selection to Path")); + + O_LIST_LENGTH (outline_list) = 0; + outline_list.data = NULL; + + height = sel_get_height (); + width = sel_get_width (); + + for (row = 0; row < height; row++) + { + for (col = 0; col < width; col++) + { + edge_type edge; + + if (sel_pixel_is_white(row, col)) + continue; + + edge = next_unmarked_outline_edge (row, col, START_EDGE,marked); + + if (edge != no_edge) + { + pixel_outline_type outline; + boolean clockwise = edge == bottom; + + outline = find_one_outline (edge, row, col, &marked); + + /* 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; + append_pixel_outline (&outline_list, outline); + + } + } + + if ((row & 0xf) == 0) + gimp_progress_update (((gdouble)row) / height); + } + + gimp_progress_update (1.0); + + local_free_bitmap (&marked); + + return outline_list; +} + + +/* Here we find one of a character C's outlines. We're passed the + position (ORIGINAL_ROW and ORIGINAL_COL) of a starting pixel and one + of its unmarked edges, ORIGINAL_EDGE. We traverse the adjacent edges + of the outline pixels, appending to the coordinate list. We keep + track of the marked edges in MARKED, so it should be initialized to + zeros when we first get it. */ + +static pixel_outline_type +find_one_outline (edge_type original_edge, + unsigned original_row, unsigned original_col, + bitmap_type *marked) +{ + pixel_outline_type outline = new_pixel_outline (); + unsigned row = original_row, col = original_col; + edge_type edge = original_edge; + + do + { + /* Put this edge on to the output list, changing to Cartesian, and + taking account of the side bearings. */ + append_coordinate (&outline, col, + sel_get_height() - row, edge); + + mark_edge (edge, row, col, marked); + next_outline_edge (&edge, &row, &col); + } + while (row != original_row || col != original_col || edge != original_edge); + + return outline; +} + + +/* Append an outline to an outline list. This is called when we have + completed an entire pixel outline. */ + +static void +append_pixel_outline (pixel_outline_list_type *outline_list, + pixel_outline_type outline) +{ + O_LIST_LENGTH (*outline_list)++; + outline_list->data = (pixel_outline_type *)g_realloc(outline_list->data,outline_list->length *sizeof(pixel_outline_type)); + O_LIST_OUTLINE (*outline_list, O_LIST_LENGTH (*outline_list) - 1) = outline; +} + + +/* Here is a routine that frees a list of such 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]; + safe_free ((address *) &(o.data)); + } + + if (outline_list->data != NULL) + safe_free ((address *) &(outline_list->data)); +} + + +/* 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; + + return pixel_outline; +} + + +/* Add the coordinate C to the pixel list O. */ + +static void +append_outline_pixel (pixel_outline_type *o, coordinate_type c) +{ + O_LENGTH (*o)++; + o->data = (coordinate_type *)g_realloc(o->data, O_LENGTH (*o)*sizeof(coordinate_type)); + O_COORDINATE (*o, O_LENGTH (*o) - 1) = c; +} + + +/* We are given an (X,Y) in Cartesian coordinates, and the edge of the pixel + we're on. We append a corner of that pixel as our coordinate. + If we're on a top edge, we use the upper-left hand corner; right edge + => upper right; bottom edge => lower right; left edge => lower left. */ + +static void +append_coordinate (pixel_outline_type *o, int x, int y, edge_type edge) +{ + coordinate_type c; + + c.x = x; + c.y = y; + + switch (edge) + { + case top: + c.y++; + break; + + case right: + c.x++; + c.y++; + break; + + case bottom: + c.x++; + break; + + case left: + break; + + default: + g_printerr ("append_coordinate: Bad edge (%d)", edge); + } + + append_outline_pixel (o, c); +} diff --git a/plug-ins/selection-to-path/pxl-outline.h b/plug-ins/selection-to-path/pxl-outline.h new file mode 100644 index 0000000..896722f --- /dev/null +++ b/plug-ins/selection-to-path/pxl-outline.h @@ -0,0 +1,68 @@ +/* pxl-outline.h: find a list of outlines which make up one character. + * + * 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 3, 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, see <https://www.gnu.org/licenses/>. + */ + +#ifndef PXL_OUTLINE_H +#define PXL_OUTLINE_H + +#include "types.h" + + +/* This is a list of contiguous points on the bitmap. */ +typedef struct +{ + coordinate_type *data; + unsigned length; + boolean clockwise; +} 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 (void); + +/* Free the memory in the list. */ +extern void free_pixel_outline_list (pixel_outline_list_type *); + +#endif /* not PXL_OUTLINE_H */ diff --git a/plug-ins/selection-to-path/selection-to-path-dialog.c b/plug-ins/selection-to-path/selection-to-path-dialog.c new file mode 100644 index 0000000..f6f3f18 --- /dev/null +++ b/plug-ins/selection-to-path/selection-to-path-dialog.c @@ -0,0 +1,403 @@ +/* + * Copyright (C) 1995 Spencer Kimball and Peter Mattis + * + * This is a plug-in for GIMP. + * + * Plugin to convert a selection to a path. + * + * Copyright (C) 1999 Andy Thomas alt@gimp.org + * + * 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 3 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, see <https://www.gnu.org/licenses/>. + * + */ + +/* Change log:- + * 0.1 First version. + */ + +#include "config.h" + +#include <libgimp/gimp.h> +#include <libgimp/gimpui.h> + +#include "types.h" + +#include "selection-to-path.h" + +#include "libgimp/stdplugins-intl.h" + +#define SCALE_WIDTH 100 +#define SCALE_DIGITS 8 + + +static GSList * adjust_widgets = NULL; + + +/* Reset to recommended defaults */ +void +reset_adv_dialog (void) +{ + GSList *list; + GtkObject *widget; + gdouble *value; + + for (list = adjust_widgets; list; list = g_slist_next (list)) + { + widget = GTK_OBJECT (list->data); + value = (gdouble *) g_object_get_data (G_OBJECT (widget), + "default_value"); + + if (GTK_IS_ADJUSTMENT (widget)) + { + gtk_adjustment_set_value (GTK_ADJUSTMENT (widget), + *value); + } + else if (GTK_IS_TOGGLE_BUTTON (widget)) + { + gtk_toggle_button_set_active (GTK_TOGGLE_BUTTON (widget), + (gboolean)(*value)); + } + else + g_warning ("Internal widget list error"); + } +} + +static gpointer +def_val (gdouble default_value) +{ + gdouble *value = g_new0 (gdouble, 1); + *value = default_value; + return (value); +} + +GtkWidget * +dialog_create_selection_area (SELVALS *sels) +{ + GtkWidget *scrolled_win; + GtkWidget *viewport; + GtkWidget *table; + GtkWidget *check; + GtkObject *adj; + gint row; + + scrolled_win = gtk_scrolled_window_new (NULL, NULL); + gtk_widget_set_size_request (scrolled_win, -1, 400); + gtk_scrolled_window_set_shadow_type (GTK_SCROLLED_WINDOW (scrolled_win), + GTK_SHADOW_NONE); + gtk_scrolled_window_set_policy (GTK_SCROLLED_WINDOW (scrolled_win), + GTK_POLICY_NEVER, + GTK_POLICY_ALWAYS); + + viewport = gtk_viewport_new (NULL, NULL); + gtk_viewport_set_shadow_type (GTK_VIEWPORT (viewport), GTK_SHADOW_NONE); + gtk_container_add (GTK_CONTAINER (scrolled_win), viewport); + gtk_widget_show (viewport); + + table = gtk_table_new (20, 3, FALSE); + gtk_table_set_row_spacings (GTK_TABLE (table), 6); + gtk_table_set_col_spacings (GTK_TABLE (table), 6); + gtk_container_add (GTK_CONTAINER (viewport), table); + gtk_widget_show (table); + + row = 0; + + adj = gimp_scale_entry_new (GTK_TABLE (table), 0, row++, + _("Align Threshold:"), SCALE_WIDTH, SCALE_DIGITS, + sels->align_threshold, + 0.2, 2.0, 0.1, 0.1, 2, + TRUE, 0, 0, + _("If two endpoints are closer than this, " + "they are made to be equal."), NULL); + g_signal_connect (adj, "value-changed", + G_CALLBACK (gimp_double_adjustment_update), + &sels->align_threshold); + adjust_widgets = g_slist_append (adjust_widgets, adj); + g_object_set_data (G_OBJECT (adj), "default_value", def_val (0.5)); + + adj = gimp_scale_entry_new (GTK_TABLE (table), 0, row++, + _("Corner Always Threshold:"), SCALE_WIDTH, SCALE_DIGITS, + sels->corner_always_threshold, + 30, 180, 1, 1, 2, + TRUE, 0, 0, + _("If the angle defined by a point and its predecessors " + "and successors is smaller than this, it's a corner, " + "even if it's within 'corner_surround' pixels of a " + "point with a smaller angle."), NULL); + g_signal_connect (adj, "value-changed", + G_CALLBACK (gimp_double_adjustment_update), + &sels->corner_always_threshold); + adjust_widgets = g_slist_append (adjust_widgets, adj); + g_object_set_data (G_OBJECT (adj), "default_value", def_val (60.0)); + + adj = gimp_scale_entry_new (GTK_TABLE (table), 0, row++, + _("Corner Surround:"), SCALE_WIDTH, SCALE_DIGITS, + sels->corner_surround, + 3, 8, 1, 1, 0, + TRUE, 0, 0, + _("Number of points to consider when determining if a " + "point is a corner or not."), NULL); + g_signal_connect (adj, "value-changed", + G_CALLBACK (gimp_double_adjustment_update), + &sels->corner_surround); + adjust_widgets = g_slist_append (adjust_widgets, adj); + g_object_set_data (G_OBJECT (adj), "default_value", def_val (4.0)); + + adj = gimp_scale_entry_new (GTK_TABLE (table), 0, row++, + _("Corner Threshold:"), SCALE_WIDTH, SCALE_DIGITS, + sels->corner_threshold, + 0, 180, 1, 1, 2, + TRUE, 0, 0, + _("If a point, its predecessors, and its successors " + "define an angle smaller than this, it's a corner."), + NULL); + g_signal_connect (adj, "value-changed", + G_CALLBACK (gimp_double_adjustment_update), + &sels->corner_threshold); + adjust_widgets = g_slist_append (adjust_widgets, adj); + g_object_set_data (G_OBJECT (adj), "default_value", def_val (100.0)); + + + adj = gimp_scale_entry_new (GTK_TABLE (table), 0, row++, + _("Error Threshold:"), SCALE_WIDTH, SCALE_DIGITS, + sels->error_threshold, + 0.2, 10, 0.1, 0.1, 2, + TRUE, 0, 0, + _("Amount of error at which a fitted spline is " + "unacceptable. If any pixel is further away " + "than this from the fitted curve, we try again."), + NULL); + g_signal_connect (adj, "value-changed", + G_CALLBACK (gimp_double_adjustment_update), + &sels->error_threshold); + adjust_widgets = g_slist_append (adjust_widgets, adj); + g_object_set_data (G_OBJECT (adj), "default_value", def_val (0.40)); + + adj = gimp_scale_entry_new (GTK_TABLE (table), 0, row++, + _("Filter Alternative Surround:"), SCALE_WIDTH, SCALE_DIGITS, + sels->filter_alternative_surround, + 1, 10, 1, 1, 0, + TRUE, 0, 0, + _("A second number of adjacent points to consider " + "when filtering."), NULL); + g_signal_connect (adj, "value-changed", + G_CALLBACK (gimp_double_adjustment_update), + &sels->filter_alternative_surround); + adjust_widgets = g_slist_append (adjust_widgets, adj); + g_object_set_data (G_OBJECT (adj), "default_value", def_val (1.0)); + + + adj = gimp_scale_entry_new (GTK_TABLE (table), 0, row++, + _("Filter Epsilon:"), SCALE_WIDTH, SCALE_DIGITS, + sels->filter_epsilon, + 5, 40, 1, 1, 2, + TRUE, 0, 0, + _("If the angles between the vectors produced by " + "filter_surround and filter_alternative_surround " + "points differ by more than this, use the one from " + "filter_alternative_surround."), NULL); + g_signal_connect (adj, "value-changed", + G_CALLBACK (gimp_double_adjustment_update), + &sels->filter_epsilon); + adjust_widgets = g_slist_append (adjust_widgets, adj); + g_object_set_data (G_OBJECT (adj), "default_value", def_val (10.0)); + + adj = gimp_scale_entry_new (GTK_TABLE (table), 0, row++, + _("Filter Iteration Count:"), SCALE_WIDTH, SCALE_DIGITS, + sels->filter_iteration_count, + 4, 70, 1, 1, 0, + TRUE, 0, 0, + _("Number of times to smooth original data points. " + "Increasing this number dramatically --- to 50 or " + "so --- can produce vastly better results. But if " + "any points that 'should' be corners aren't found, " + "the curve goes to hell around that point."), NULL); + g_signal_connect (adj, "value-changed", + G_CALLBACK (gimp_double_adjustment_update), + &sels->filter_iteration_count); + adjust_widgets = g_slist_append (adjust_widgets, adj); + g_object_set_data (G_OBJECT (adj), "default_value", def_val (4.0)); + + adj = gimp_scale_entry_new (GTK_TABLE (table), 0, row++, + _("Filter Percent:"), SCALE_WIDTH, SCALE_DIGITS, + sels->filter_percent, + 0, 1, 0.05, 0.01, 2, + TRUE, 0, 0, + _("To produce the new point, use the old point plus " + "this times the neighbors."), NULL); + g_signal_connect (adj, "value-changed", + G_CALLBACK (gimp_double_adjustment_update), + &sels->filter_percent); + adjust_widgets = g_slist_append (adjust_widgets, adj); + g_object_set_data (G_OBJECT (adj), "default_value", def_val (0.33)); + + adj = gimp_scale_entry_new (GTK_TABLE (table), 0, row++, + _("Filter Secondary Surround:"), SCALE_WIDTH, SCALE_DIGITS, + sels->filter_secondary_surround, + 3, 10, 1, 1, 0, + TRUE, 0, 0, + _("Number of adjacent points to consider if " + "'filter_surround' points defines a straight line."), + NULL); + g_signal_connect (adj, "value-changed", + G_CALLBACK (gimp_double_adjustment_update), + &sels->filter_secondary_surround); + adjust_widgets = g_slist_append (adjust_widgets, adj); + g_object_set_data (G_OBJECT (adj), "default_value", def_val (3.0)); + + adj = gimp_scale_entry_new (GTK_TABLE (table), 0, row++, + _("Filter Surround:"), SCALE_WIDTH, SCALE_DIGITS, + sels->filter_surround, + 2, 10, 1, 1, 0, + TRUE, 0, 0, + _("Number of adjacent points to consider when filtering."), + NULL); + g_signal_connect (adj, "value-changed", + G_CALLBACK (gimp_double_adjustment_update), + &sels->filter_surround); + adjust_widgets = g_slist_append (adjust_widgets, adj); + g_object_set_data (G_OBJECT (adj), "default_value", def_val (2.0)); + + check = gtk_check_button_new_with_label (_("Keep Knees")); + gtk_toggle_button_set_active (GTK_TOGGLE_BUTTON (check), sels->keep_knees); + gtk_table_attach (GTK_TABLE (table), check, 1, 3, row, row + 1, + GTK_EXPAND | GTK_FILL, GTK_EXPAND | GTK_FILL, 0, 0); + gimp_help_set_help_data (GTK_WIDGET (check), + _("Says whether or not to remove 'knee' " + "points after finding the outline."), NULL); + g_signal_connect (check, "toggled", + G_CALLBACK (gimp_toggle_button_update), + &sels->keep_knees); + gtk_widget_show (check); + adjust_widgets = g_slist_append (adjust_widgets, check); + g_object_set_data (G_OBJECT (check), "default_value", def_val ((gdouble)FALSE)); + row++; + + adj = gimp_scale_entry_new (GTK_TABLE (table), 0, row++, + _("Line Reversion Threshold:"), SCALE_WIDTH, SCALE_DIGITS, + sels->line_reversion_threshold, + 0.01, 0.2, 0.01, 0.01, 3, + TRUE, 0, 0, + _("If a spline is closer to a straight line than this, " + "it remains a straight line, even if it would otherwise " + "be changed back to a curve. This is weighted by the " + "square of the curve length, to make shorter curves " + "more likely to be reverted."), NULL); + g_signal_connect (adj, "value-changed", + G_CALLBACK (gimp_double_adjustment_update), + &sels->line_reversion_threshold); + adjust_widgets = g_slist_append (adjust_widgets, adj); + g_object_set_data (G_OBJECT (adj), "default_value", def_val (0.01)); + + adj = gimp_scale_entry_new (GTK_TABLE (table), 0, row++, + _("Line Threshold:"), SCALE_WIDTH, SCALE_DIGITS, + sels->line_threshold, + 0.2, 4, 0.1, 0.01, 2, + TRUE, 0, 0, + _("How many pixels (on the average) a spline can " + "diverge from the line determined by its endpoints " + "before it is changed to a straight line."), NULL); + g_signal_connect (adj, "value-changed", + G_CALLBACK (gimp_double_adjustment_update), + &sels->line_threshold); + adjust_widgets = g_slist_append (adjust_widgets, adj); + g_object_set_data (G_OBJECT (adj), "default_value", def_val (0.5)); + + adj = gimp_scale_entry_new (GTK_TABLE (table), 0, row++, + _("Reparametrize Improvement:"), SCALE_WIDTH, SCALE_DIGITS, + sels->reparameterize_improvement, + 0, 1, 0.05, 0.01, 2, + TRUE, 0, 0, + _("If reparameterization doesn't improve the fit by this " + "much percent, stop doing it. ""Amount of error at which " + "it is pointless to reparameterize."), NULL); + g_signal_connect (adj, "value-changed", + G_CALLBACK (gimp_double_adjustment_update), + &sels->reparameterize_improvement); + adjust_widgets = g_slist_append (adjust_widgets, adj); + g_object_set_data (G_OBJECT (adj), "default_value", def_val (0.01)); + + adj = gimp_scale_entry_new (GTK_TABLE (table), 0, row++, + _("Reparametrize Threshold:"), SCALE_WIDTH, SCALE_DIGITS, + sels->reparameterize_threshold, + 1, 50, 0.5, 0.5, 2, + TRUE, 0, 0, + _("Amount of error at which it is pointless to reparameterize. " + "This happens, for example, when we are trying to fit the " + "outline of the outside of an 'O' with a single spline. " + "The initial fit is not good enough for the Newton-Raphson " + "iteration to improve it. It may be that it would be better " + "to detect the cases where we didn't find any corners."), NULL); + g_signal_connect (adj, "value-changed", + G_CALLBACK (gimp_double_adjustment_update), + &sels->reparameterize_threshold); + adjust_widgets = g_slist_append (adjust_widgets, adj); + g_object_set_data (G_OBJECT (adj), "default_value", def_val (1.0)); + + adj = gimp_scale_entry_new (GTK_TABLE (table), 0, row++, + _("Subdivide Search:"), SCALE_WIDTH, SCALE_DIGITS, + sels->subdivide_search, + 0.05, 1, 0.05, 0.01, 2, + TRUE, 0, 0, + _("Percentage of the curve away from the worst point " + "to look for a better place to subdivide."), NULL); + g_signal_connect (adj, "value-changed", + G_CALLBACK (gimp_double_adjustment_update), + &sels->subdivide_search); + adjust_widgets = g_slist_append (adjust_widgets, adj); + g_object_set_data (G_OBJECT (adj), "default_value", def_val (0.1)); + + adj = gimp_scale_entry_new (GTK_TABLE (table), 0, row++, + _("Subdivide Surround:"), SCALE_WIDTH, SCALE_DIGITS, + sels->subdivide_surround, + 2, 10, 1, 1, 0, + TRUE, 0, 0, + _("Number of points to consider when deciding whether " + "a given point is a better place to subdivide."), + NULL); + g_signal_connect (adj, "value-changed", + G_CALLBACK (gimp_double_adjustment_update), + &sels->subdivide_surround); + adjust_widgets = g_slist_append (adjust_widgets, adj); + g_object_set_data (G_OBJECT (adj), "default_value", def_val (4.0)); + + adj = gimp_scale_entry_new (GTK_TABLE (table), 0, row++, + _("Subdivide Threshold:"), SCALE_WIDTH, SCALE_DIGITS, + sels->subdivide_threshold, + 0.01, 1, 0.01, 0.01, 2, + TRUE, 0, 0, + _("How many pixels a point can diverge from a straight " + "line and still be considered a better place to " + "subdivide."), NULL); + g_signal_connect (adj, "value-changed", + G_CALLBACK (gimp_double_adjustment_update), + &sels->subdivide_threshold); + adjust_widgets = g_slist_append (adjust_widgets, adj); + g_object_set_data (G_OBJECT (adj), "default_value", def_val (0.03)); + + adj = gimp_scale_entry_new (GTK_TABLE (table), 0, row++, + _("Tangent Surround:"), SCALE_WIDTH, SCALE_DIGITS, + sels->tangent_surround, + 2, 10, 1, 1, 0, + TRUE, 0, 0, + _("Number of points to look at on either side of a " + "point when computing the approximation to the " + "tangent at that point."), NULL); + g_signal_connect (adj, "value-changed", + G_CALLBACK (gimp_double_adjustment_update), + &sels->tangent_surround); + adjust_widgets = g_slist_append (adjust_widgets, adj); + g_object_set_data (G_OBJECT (adj), "default_value", def_val (3.0)); + + return scrolled_win; +} diff --git a/plug-ins/selection-to-path/selection-to-path.c b/plug-ins/selection-to-path/selection-to-path.c new file mode 100644 index 0000000..52fc849 --- /dev/null +++ b/plug-ins/selection-to-path/selection-to-path.c @@ -0,0 +1,536 @@ +/* + * Copyright (C) 1995 Spencer Kimball and Peter Mattis + * + * This is a plug-in for GIMP. + * + * Plugin to convert a selection to a path. + * + * Copyright (C) 1999 Andy Thomas alt@gimp.org + * + * 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 3 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, see <https://www.gnu.org/licenses/>. + * + */ + +/* Change log:- + * 0.1 First version. + */ + +#include "config.h" + +#include <string.h> + +#include "libgimp/gimp.h" +#include "libgimp/gimpui.h" + +#include "libgimpmath/gimpmath.h" + +#include "global.h" +#include "types.h" +#include "pxl-outline.h" +#include "fit.h" +#include "spline.h" +#include "selection-to-path.h" + +#include "libgimp/stdplugins-intl.h" + + +#define PLUG_IN_BINARY "selection-to-path" +#define PLUG_IN_ROLE "gimp-selection-to-path" + +#define RESPONSE_RESET 1 +#define MID_POINT 127 + +/***** Magic numbers *****/ + +/* Variables set in dialog box */ + +static void query (void); +static void run (const gchar *name, + gint nparams, + const GimpParam *param, + gint *nreturn_vals, + GimpParam **return_vals); + +static gint sel2path_dialog (SELVALS *sels); +static void sel2path_response (GtkWidget *widget, + gint response_id, + gpointer data); +static void dialog_print_selVals (SELVALS *sels); +static gboolean sel2path (gint32 image_ID); + + +const GimpPlugInInfo PLUG_IN_INFO = +{ + NULL, /* init_proc */ + NULL, /* quit_proc */ + query, /* query_proc */ + run, /* run_proc */ +}; + +static gint sel_x1, sel_y1, sel_x2, sel_y2; +static gint has_sel, sel_width, sel_height; +static SELVALS selVals; +static GeglSampler *sel_sampler; +static gboolean retVal = TRUE; /* Toggle if cancel button clicked */ + +MAIN () + +static void +query (void) +{ + static const GimpParamDef args[] = + { + { GIMP_PDB_INT32, "run-mode", "The run mode { RUN-INTERACTIVE (0), RUN-NONINTERACTIVE (1) }" }, + { GIMP_PDB_IMAGE, "image", "Input image" }, + { GIMP_PDB_DRAWABLE, "drawable", "Input drawable (unused)" }, + }; + + static const GimpParamDef advanced_args[] = + { + { GIMP_PDB_INT32, "run-mode", "The run mode { RUN-INTERACTIVE (0), RUN-NONINTERACTIVE (1) }" }, + { GIMP_PDB_IMAGE, "image", "Input image" }, + { GIMP_PDB_DRAWABLE, "drawable", "Input drawable (unused)" }, + { GIMP_PDB_FLOAT, "align-threshold", "align_threshold"}, + { GIMP_PDB_FLOAT, "corner-always-threshold", "corner_always_threshold"}, + { GIMP_PDB_INT8, "corner-surround", "corner_surround"}, + { GIMP_PDB_FLOAT, "corner-threshold", "corner_threshold"}, + { GIMP_PDB_FLOAT, "error-threshold", "error_threshold"}, + { GIMP_PDB_INT8, "filter-alternative-surround", "filter_alternative_surround"}, + { GIMP_PDB_FLOAT, "filter-epsilon", "filter_epsilon"}, + { GIMP_PDB_INT8, "filter-iteration-count", "filter_iteration_count"}, + { GIMP_PDB_FLOAT, "filter-percent", "filter_percent"}, + { GIMP_PDB_INT8, "filter-secondary-surround", "filter_secondary_surround"}, + { GIMP_PDB_INT8, "filter-surround", "filter_surround"}, + { GIMP_PDB_INT8, "keep-knees", "{1-Yes, 0-No}"}, + { GIMP_PDB_FLOAT, "line-reversion-threshold", "line_reversion_threshold"}, + { GIMP_PDB_FLOAT, "line-threshold", "line_threshold"}, + { GIMP_PDB_FLOAT, "reparameterize-improvement", "reparameterize_improvement"}, + { GIMP_PDB_FLOAT, "reparameterize-threshold", "reparameterize_threshold"}, + { GIMP_PDB_FLOAT, "subdivide-search", "subdivide_search"}, + { GIMP_PDB_INT8, "subdivide-surround", "subdivide_surround"}, + { GIMP_PDB_FLOAT, "subdivide-threshold", "subdivide_threshold"}, + { GIMP_PDB_INT8, "tangent-surround", "tangent_surround"}, + }; + + gimp_install_procedure ("plug-in-sel2path", + "Converts a selection to a path", + "Converts a selection to a path", + "Andy Thomas", + "Andy Thomas", + "1999", + NULL, + "RGB*, INDEXED*, GRAY*", + GIMP_PLUGIN, + G_N_ELEMENTS (args), 0, + args, NULL); + + gimp_install_procedure ("plug-in-sel2path-advanced", + "Converts a selection to a path (with advanced user menu)", + "Converts a selection to a path (with advanced user menu)", + "Andy Thomas", + "Andy Thomas", + "1999", + NULL, + "RGB*, INDEXED*, GRAY*", + GIMP_PLUGIN, + G_N_ELEMENTS (advanced_args), 0, + advanced_args, NULL); +} + +static void +run (const gchar *name, + gint nparams, + const GimpParam *param, + gint *nreturn_vals, + GimpParam **return_vals) +{ + static GimpParam values[1]; + gint32 image_ID; + GimpRunMode run_mode; + GimpPDBStatusType status = GIMP_PDB_SUCCESS; + gboolean no_dialog; + + INIT_I18N (); + gegl_init (NULL, NULL); + + run_mode = param[0].data.d_int32; + + no_dialog = (strcmp (name, "plug-in-sel2path") == 0); + + *nreturn_vals = 1; + *return_vals = values; + + values[0].type = GIMP_PDB_STATUS; + values[0].data.d_status = status; + + image_ID = param[1].data.d_image; + if (image_ID < 0) + { + g_warning ("plug-in-sel2path needs a valid image ID"); + return; + } + + if (gimp_selection_is_empty (image_ID)) + { + g_message (_("No selection to convert")); + return; + } + + fit_set_default_params (&selVals); + + if (!no_dialog) + { + switch (run_mode) + { + case GIMP_RUN_INTERACTIVE: + if (gimp_get_data_size ("plug-in-sel2path-advanced") > 0) + { + gimp_get_data ("plug-in-sel2path-advanced", &selVals); + } + + if (!sel2path_dialog (&selVals)) + return; + + /* Get the current settings */ + fit_set_params (&selVals); + break; + + case GIMP_RUN_NONINTERACTIVE: + if (nparams != 23) + status = GIMP_PDB_CALLING_ERROR; + + if (status == GIMP_PDB_SUCCESS) + { + selVals.align_threshold = param[3].data.d_float; + selVals.corner_always_threshold = param[4].data.d_float; + selVals.corner_surround = param[5].data.d_int8; + selVals.corner_threshold = param[6].data.d_float; + selVals.error_threshold = param[7].data.d_float; + selVals.filter_alternative_surround = param[8].data.d_int8; + selVals.filter_epsilon = param[9].data.d_float; + selVals.filter_iteration_count = param[10].data.d_int8; + selVals.filter_percent = param[11].data.d_float; + selVals.filter_secondary_surround = param[12].data.d_int8; + selVals.filter_surround = param[13].data.d_int8; + selVals.keep_knees = param[14].data.d_int8; + selVals.line_reversion_threshold = param[15].data.d_float; + selVals.line_threshold = param[16].data.d_float; + selVals.reparameterize_improvement = param[17].data.d_float; + selVals.reparameterize_threshold = param[18].data.d_float; + selVals.subdivide_search = param[19].data.d_float; + selVals.subdivide_surround = param[20].data.d_int8; + selVals.subdivide_threshold = param[21].data.d_float; + selVals.tangent_surround = param[22].data.d_int8; + fit_set_params (&selVals); + } + break; + + case GIMP_RUN_WITH_LAST_VALS: + if(gimp_get_data_size ("plug-in-sel2path-advanced") > 0) + { + gimp_get_data ("plug-in-sel2path-advanced", &selVals); + + /* Set up the last values */ + fit_set_params (&selVals); + } + break; + + default: + break; + } + } + + sel2path (image_ID); + values[0].data.d_status = status; + + if (status == GIMP_PDB_SUCCESS) + { + dialog_print_selVals(&selVals); + if (run_mode == GIMP_RUN_INTERACTIVE && !no_dialog) + gimp_set_data ("plug-in-sel2path-advanced", &selVals, sizeof(SELVALS)); + } +} + +static void +dialog_print_selVals (SELVALS *sels) +{ +#if 0 + printf ("selVals.align_threshold %g\n", selVals.align_threshold); + printf ("selVals.corner_always_threshol %g\n", selVals.corner_always_threshold); + printf ("selVals.corner_surround %g\n", selVals.corner_surround); + printf ("selVals.corner_threshold %g\n", selVals.corner_threshold); + printf ("selVals.error_threshold %g\n", selVals.error_threshold); + printf ("selVals.filter_alternative_surround %g\n", selVals.filter_alternative_surround); + printf ("selVals.filter_epsilon %g\n", selVals.filter_epsilon); + printf ("selVals.filter_iteration_count %g\n", selVals.filter_iteration_count); + printf ("selVals.filter_percent %g\n", selVals.filter_percent); + printf ("selVals.filter_secondary_surround %g\n", selVals.filter_secondary_surround); + printf ("selVals.filter_surround %g\n", selVals.filter_surround); + printf ("selVals.keep_knees %d\n", selVals.keep_knees); + printf ("selVals.line_reversion_threshold %g\n", selVals.line_reversion_threshold); + printf ("selVals.line_threshold %g\n", selVals.line_threshold); + printf ("selVals.reparameterize_improvement %g\n", selVals.reparameterize_improvement); + printf ("selVals.reparameterize_threshold %g\n", selVals.reparameterize_threshold); + printf ("selVals.subdivide_search %g\n" selVals.subdivide_search); + printf ("selVals.subdivide_surround %g\n", selVals.subdivide_surround); + printf ("selVals.subdivide_threshold %g\n", selVals.subdivide_threshold); + printf ("selVals.tangent_surround %g\n", selVals.tangent_surround); +#endif /* 0 */ +} + +/* Build the dialog up. This was the hard part! */ +static gint +sel2path_dialog (SELVALS *sels) +{ + GtkWidget *dlg; + GtkWidget *table; + + retVal = FALSE; + + gimp_ui_init (PLUG_IN_BINARY, FALSE); + + dlg = gimp_dialog_new (_("Selection to Path Advanced Settings"), + PLUG_IN_ROLE, + NULL, 0, + gimp_standard_help_func, "plug-in-sel2path-advanced", + + _("_Reset"), RESPONSE_RESET, + _("_Cancel"), GTK_RESPONSE_CANCEL, + _("_OK"), GTK_RESPONSE_OK, + + NULL); + + gtk_dialog_set_alternative_button_order (GTK_DIALOG (dlg), + RESPONSE_RESET, + GTK_RESPONSE_OK, + GTK_RESPONSE_CANCEL, + -1); + + gimp_window_set_transient (GTK_WINDOW (dlg)); + + g_signal_connect (dlg, "response", + G_CALLBACK (sel2path_response), + NULL); + g_signal_connect (dlg, "destroy", + G_CALLBACK (gtk_main_quit), + NULL); + + table = dialog_create_selection_area (sels); + gtk_container_set_border_width (GTK_CONTAINER (table), 12); + gtk_box_pack_start (GTK_BOX (gtk_dialog_get_content_area (GTK_DIALOG (dlg))), + table, TRUE, TRUE, 0); + gtk_widget_show (table); + + gtk_widget_show (dlg); + + gtk_main (); + + return retVal; +} + +static void +sel2path_response (GtkWidget *widget, + gint response_id, + gpointer data) +{ + switch (response_id) + { + case RESPONSE_RESET: + reset_adv_dialog (); + fit_set_params (&selVals); + break; + + case GTK_RESPONSE_OK: + retVal = TRUE; + + default: + gtk_widget_destroy (widget); + break; + } +} + +guchar +sel_pixel_value (gint row, + gint col) +{ + guchar ret; + + if (col > sel_width || row > sel_height) + { + g_warning ("sel_pixel_value [%d,%d] out of bounds", col, row); + return 0; + } + + gegl_sampler_get (sel_sampler, + col + sel_x1, row + sel_y1, NULL, &ret, GEGL_ABYSS_NONE); + + return ret; +} + +gboolean +sel_pixel_is_white (gint row, + gint col) +{ + if (sel_pixel_value (row, col) < MID_POINT) + return TRUE; + else + return FALSE; +} + +gint +sel_get_width (void) +{ + return sel_width; +} + +gint +sel_get_height (void) +{ + return sel_height; +} + +gboolean +sel_valid_pixel (gint row, + gint col) +{ + return (0 <= (row) && (row) < sel_get_height () + && 0 <= (col) && (col) < sel_get_width ()); +} + + +static void +do_points (spline_list_array_type in_splines, + gint32 image_ID) +{ + gint32 vectors; + gint32 stroke; + gint i, j; + gboolean have_points = FALSE; + spline_list_type spline_list; + + /* check if there really is something to do... */ + for (i = 0; i < SPLINE_LIST_ARRAY_LENGTH (in_splines); i++) + { + spline_list = SPLINE_LIST_ARRAY_ELT (in_splines, i); + /* Ignore single points that are on their own */ + if (SPLINE_LIST_LENGTH (spline_list) < 2) + continue; + have_points = TRUE; + break; + } + + if (!have_points) + return; + + vectors = gimp_vectors_new (image_ID, _("Selection")); + + for (j = 0; j < SPLINE_LIST_ARRAY_LENGTH (in_splines); j++) + { + spline_type seg; + + spline_list = SPLINE_LIST_ARRAY_ELT (in_splines, j); + + /* Ignore single points that are on their own */ + if (SPLINE_LIST_LENGTH (spline_list) < 2) + continue; + + /* + * we're constructing the path backwards + * to have the result of least surprise for "Text along Path". + */ + seg = SPLINE_LIST_ELT (spline_list, SPLINE_LIST_LENGTH (spline_list) - 1); + stroke = gimp_vectors_bezier_stroke_new_moveto (vectors, + END_POINT (seg).x, + END_POINT (seg).y); + + for (i = SPLINE_LIST_LENGTH (spline_list); i > 0; i--) + { + seg = SPLINE_LIST_ELT (spline_list, i-1); + + if (SPLINE_DEGREE (seg) == LINEAR) + gimp_vectors_bezier_stroke_lineto (vectors, stroke, + START_POINT (seg).x, + START_POINT (seg).y); + else if (SPLINE_DEGREE (seg) == CUBIC) + gimp_vectors_bezier_stroke_cubicto (vectors, stroke, + CONTROL2 (seg).x, + CONTROL2 (seg).y, + CONTROL1 (seg).x, + CONTROL1 (seg).y, + START_POINT (seg).x, + START_POINT (seg).y); + else + g_warning ("print_spline: strange degree (%d)", + SPLINE_DEGREE (seg)); + } + + gimp_vectors_stroke_close (vectors, stroke); + + /* transform to GIMPs coordinate system, taking the selections + * bounding box into account */ + gimp_vectors_stroke_scale (vectors, stroke, 1.0, -1.0); + gimp_vectors_stroke_translate (vectors, stroke, + sel_x1, sel_y1 + sel_height + 1); + } + + gimp_image_insert_vectors (image_ID, vectors, -1, -1); +} + + +static gboolean +sel2path (gint32 image_ID) +{ + gint32 selection_ID; + GeglBuffer *sel_buffer; + pixel_outline_list_type olt; + spline_list_array_type splines; + + gimp_selection_bounds (image_ID, &has_sel, + &sel_x1, &sel_y1, &sel_x2, &sel_y2); + + sel_width = sel_x2 - sel_x1; + sel_height = sel_y2 - sel_y1; + + /* Now get the selection channel */ + + selection_ID = gimp_image_get_selection (image_ID); + + if (selection_ID < 0) + return FALSE; + + sel_buffer = gimp_drawable_get_buffer (selection_ID); + sel_sampler = gegl_buffer_sampler_new (sel_buffer, + babl_format ("Y u8"), + GEGL_SAMPLER_NEAREST); + + olt = find_outline_pixels (); + + splines = fitted_splines (olt); + + do_points (splines, image_ID); + + g_object_unref (sel_sampler); + g_object_unref (sel_buffer); + + gimp_displays_flush (); + + return TRUE; +} + +void +safe_free (address *item) +{ + g_free (*item); + *item = NULL; +} diff --git a/plug-ins/selection-to-path/selection-to-path.h b/plug-ins/selection-to-path/selection-to-path.h new file mode 100644 index 0000000..d798492 --- /dev/null +++ b/plug-ins/selection-to-path/selection-to-path.h @@ -0,0 +1,37 @@ +/* + * Copyright (C) 1995 Spencer Kimball and Peter Mattis + * + * This is a plug-in for GIMP. + * + * Plugin to convert a selection to a path. + * + * Copyright (C) 1999 Andy Thomas alt@gimp.org + * + * 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 3 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, see <https://www.gnu.org/licenses/>. + * + */ + +#include "gtk/gtk.h" +#include "libgimp/gimp.h" + +guchar sel_pixel_value (gint, gint); +gint sel_pixel_is_white (gint, gint); +gint sel_get_width (void); +gint sel_get_height (void); +gboolean sel_valid_pixel (gint, gint); +void reset_adv_dialog (void); + + +GtkWidget * dialog_create_selection_area(SELVALS *); + diff --git a/plug-ins/selection-to-path/spline.c b/plug-ins/selection-to-path/spline.c new file mode 100644 index 0000000..1e8c2e7 --- /dev/null +++ b/plug-ins/selection-to-path/spline.c @@ -0,0 +1,233 @@ +/* spline.c: spline and spline list (represented as arrays) manipulation. + * + * 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 3, 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, see <https://www.gnu.org/licenses/>. + */ + +#include "config.h" + +#include <assert.h> + +#include <glib.h> + +#include "global.h" +#include "bounding-box.h" +#include "spline.h" +#include "vector.h" + +/* Return a new spline structure, initialized with (recognizable) + garbage. */ + +spline_type +new_spline (void) +{ + real_coordinate_type coord = { -100.0, -100.0 }; + spline_type spline; + + START_POINT (spline) + = CONTROL1 (spline) + = CONTROL2 (spline) + = END_POINT (spline) + = coord; + SPLINE_DEGREE (spline) = -1; + SPLINE_LINEARITY (spline) = 0; + + return spline; +} + + +/* Print a spline in human-readable form. */ + +void +print_spline (FILE *f, spline_type s) +{ + if (SPLINE_DEGREE (s) == LINEAR) + fprintf (f, "(%.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) == CUBIC) + fprintf (f, "(%.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); + + else + { +/* FATAL1 ("print_spline: strange degree (%d)", SPLINE_DEGREE (s)); */ + } +} + +/* Evaluate the spline S at a given T value. This is an implementation + of de Casteljau's algorithm. See Schneider's thesis (reference in + ../limn/README), p.37. The variable names are taken from there. */ + +real_coordinate_type +evaluate_spline (spline_type s, real t) +{ + spline_type V[4]; /* We need degree+1 splines, but assert degree <= 3. */ + unsigned i, j; + real one_minus_t = 1.0 - t; + polynomial_degree degree = SPLINE_DEGREE (s); + + for (i = 0; i <= degree; i++) + V[0].v[i] = s.v[i]; + + for (j = 1; j <= degree; j++) + for (i = 0; i <= degree - j; i++) + { +#if defined (__GNUC__) + real_coordinate_type t1 = Pmult_scalar (V[j - 1].v[i], one_minus_t); + real_coordinate_type t2 = Pmult_scalar (V[j - 1].v[i + 1], t); + V[j].v[i] = Padd (t1, t2); +#else + /* HB: the above is really nice, but is there any other compiler + * supporting this ?? + */ + real_coordinate_type t1; + real_coordinate_type t2; + t1.x = V[j - 1].v[i].x * one_minus_t; + t1.y = V[j - 1].v[i].y * one_minus_t; + t2.x = V[j - 1].v[i + 1].x * t; + t2.y = V[j - 1].v[i + 1].y * t; + V[j].v[i].x = t1.x + t2.x; + V[j].v[i].y = t1.y + t2.y; +#endif + } + + return V[degree].v[0]; +} + + + +/* Return a new, empty, spline list. */ + +spline_list_type * +new_spline_list (void) +{ + spline_list_type *answer = g_new (spline_list_type, 1); + + 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 * +init_spline_list (spline_type spline) +{ + spline_list_type *answer = g_new (spline_list_type, 1); + + SPLINE_LIST_DATA (*answer) = g_new (spline_type, 1); + 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) +{ + if (SPLINE_LIST_DATA (*spline_list) != NULL) + safe_free ((address *) &(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)++; + SPLINE_LIST_DATA (*l) = g_realloc (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); + + SPLINE_LIST_DATA (*s1) = g_realloc(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)); + + if (SPLINE_LIST_ARRAY_DATA (*spline_list_array) != NULL) + safe_free ((address *) &(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)++; + + SPLINE_LIST_ARRAY_DATA (*l) = g_realloc(SPLINE_LIST_ARRAY_DATA (*l),(SPLINE_LIST_ARRAY_LENGTH (*l))*sizeof(spline_list_type)); + LAST_SPLINE_LIST_ARRAY_ELT (*l) = s; +} diff --git a/plug-ins/selection-to-path/spline.h b/plug-ins/selection-to-path/spline.h new file mode 100644 index 0000000..3daa9cc --- /dev/null +++ b/plug-ins/selection-to-path/spline.h @@ -0,0 +1,124 @@ +/* spline.h: manipulate the spline representation. + * + * 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 3, 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, see <https://www.gnu.org/licenses/>. + */ + +#ifndef SPLINE_H +#define SPLINE_H + +#include <stdio.h> +#include "bounding-box.h" +#include "types.h" + + +/* Third degree is the highest we deal with. */ +typedef enum +{ + LINEAR = 1, QUADRATIC = 2, CUBIC = 3 +} polynomial_degree; + + +/* 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. */ +typedef struct +{ + real_coordinate_type v[4]; /* The control points. */ + polynomial_degree degree; + real linearity; +} spline_type; + +#define START_POINT(spl) ((spl).v[0]) +#define CONTROL1(spl) ((spl).v[1]) +#define CONTROL2(spl) ((spl).v[2]) +#define END_POINT(spl) ((spl).v[3]) +#define SPLINE_DEGREE(spl) ((spl).degree) +#define SPLINE_LINEARITY(spl) ((spl).linearity) + + +/* Return a spline structure. */ +extern spline_type new_spline (void); + +/* Print a spline on the given file. */ +extern void print_spline (FILE *, spline_type); + +/* Evaluate SPLINE at the given T value. */ +extern real_coordinate_type evaluate_spline (spline_type spline, real t); + +/* Each outline in a character is typically represented by many + splines. So, here is a list structure for that: */ +typedef struct +{ + spline_type *data; + unsigned length; +} spline_list_type; + +/* An empty list will have length zero (and null data). */ +#define SPLINE_LIST_LENGTH(s_l) ((s_l).length) + +/* The address of the beginning of the array of data. */ +#define SPLINE_LIST_DATA(s_l) ((s_l).data) + +/* The element INDEX in S_L. */ +#define SPLINE_LIST_ELT(s_l, index) (SPLINE_LIST_DATA (s_l)[index]) + +/* 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) + +/* Construct and destroy new `spline_list_type' objects. */ +extern spline_list_type *new_spline_list (void); +extern spline_list_type *init_spline_list (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); + + +/* Each character is in general made up of many outlines. So here is one + more list structure. */ +typedef struct +{ + spline_list_type *data; + unsigned length; +} 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 SPLINE_LIST_LENGTH +#define SPLINE_LIST_ARRAY_DATA SPLINE_LIST_DATA +#define SPLINE_LIST_ARRAY_ELT SPLINE_LIST_ELT +#define LAST_SPLINE_LIST_ARRAY_ELT LAST_SPLINE_LIST_ELT + +/* The usual routines. */ +extern spline_list_array_type new_spline_list_array (void); +extern void free_spline_list_array (spline_list_array_type *); +extern void append_spline_list (spline_list_array_type *, spline_list_type); + +#endif /* not SPLINE_H */ diff --git a/plug-ins/selection-to-path/types.h b/plug-ins/selection-to-path/types.h new file mode 100644 index 0000000..9b040fa --- /dev/null +++ b/plug-ins/selection-to-path/types.h @@ -0,0 +1,147 @@ +/* types.h: general types. + * + * 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 3, 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, see <https://www.gnu.org/licenses/>. + */ + +#ifndef TYPES_H +#define TYPES_H + +/* Booleans. */ +typedef enum { false = 0, true = 1 } boolean; + +/* The X11 library defines `FALSE' and `TRUE', and so we only want to + define them if necessary. */ +#ifndef FALSE +#define FALSE false +#define TRUE true +#endif /* FALSE */ + +/* The usual null-terminated string. */ +typedef char *string; + +/* A generic pointer in ANSI C. */ +typedef void *address; + +/* We use `real' for our floating-point variables. */ +typedef double real; + +/* A character code. Perhaps someday we will allow for 16-bit + character codes, but for now we are restricted to 256 characters per + font (like TeX and PostScript). */ +typedef unsigned char charcode_type; + + +/* Used in file formats. */ +typedef unsigned char one_byte; +typedef signed char signed_byte; +typedef unsigned short two_bytes; +typedef short signed_2_bytes; +typedef unsigned int four_bytes; +typedef int signed_4_bytes; +typedef int byte_count_type; + +/* These are intended to be used for output in file formats where a + ``byte'' is defined to be eight bits, regardless of the hardware. */ +#define ONE_BYTE_BIG (1 << 8) +#define TWO_BYTES_BIG (1 << 16) +#define THREE_BYTES_BIG (1 << 24) + + +/* Complex numbers. */ +typedef struct +{ + real real; + real imag; +} complex; +typedef enum { first_complex_part, second_complex_part} complex_part_type; +typedef enum { polar_rep, rectangular_rep} complex_rep_type; + + +/* Dimensions of a rectangle. */ +typedef struct +{ + unsigned height, width; +} dimensions_type; + +#define DIMENSIONS_HEIGHT(d) ((d).height) +#define DIMENSIONS_WIDTH(d) ((d).width) + + +/* Cartesian points. */ +typedef struct +{ + int x, y; +} coordinate_type; + +typedef struct +{ + double x, y; +} real_coordinate_type; + +#if 0 +typedef struct +{ + double align_threshold; + double corner_always_threshold; + unsigned int corner_surround; + double corner_threshold; + double error_threshold; + unsigned int filter_alternative_surround; + double filter_epsilon; + unsigned int filter_iteration_count; + double filter_percent; + unsigned int filter_secondary_surround; + unsigned int filter_surround; + boolean keep_knees; + double line_reversion_threshold; + double line_threshold; + double reparameterize_improvement; + double reparameterize_threshold; + double subdivide_search; + unsigned int subdivide_surround; + double subdivide_threshold; + unsigned int tangent_surround; +} SELVALS; + +#else + +typedef struct +{ + double align_threshold; + double corner_always_threshold; + double corner_surround; + double corner_threshold; + double error_threshold; + double filter_alternative_surround; + double filter_epsilon; + double filter_iteration_count; + double filter_percent; + double filter_secondary_surround; + double filter_surround; + boolean keep_knees; + double line_reversion_threshold; + double line_threshold; + double reparameterize_improvement; + double reparameterize_threshold; + double subdivide_search; + double subdivide_surround; + double subdivide_threshold; + double tangent_surround; +} SELVALS; + +#endif /* 1 */ + +#endif /* not TYPES_H */ diff --git a/plug-ins/selection-to-path/vector.c b/plug-ins/selection-to-path/vector.c new file mode 100644 index 0000000..6c16700 --- /dev/null +++ b/plug-ins/selection-to-path/vector.c @@ -0,0 +1,249 @@ +/* vector.c: vector/point operations. + * + * 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 3, 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, see <https://www.gnu.org/licenses/>. + */ + +#include "config.h" + +#include <glib.h> + +#include <math.h> +#include <assert.h> + +#include "global.h" +#include "config.h" + +#include "vector.h" + + +/* Given the point COORD, return the corresponding vector. */ + +vector_type +make_vector (const real_coordinate_type c) +{ + vector_type v; + + v.dx = c.x; + v.dy = c.y; + + return v; +} + + +/* And the converse: given a vector, return the corresponding point. */ + +real_coordinate_type +vector_to_point (const vector_type v) +{ + real_coordinate_type coord; + + coord.x = v.dx; + coord.y = v.dy; + + return coord; +} + + +real +magnitude (const vector_type v) +{ + return hypot (v.dx, v.dy); +} + + +vector_type +normalize (const vector_type v) +{ + vector_type new_v; + real m = magnitude (v); + + assert (m > 0.0); + + new_v.dx = v.dx / m; + new_v.dy = v.dy / m; + + 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; + + return new_v; +} + + +real +Vdot (const vector_type v1, const vector_type v2) +{ + return v1.dx * v2.dx + v1.dy * v2.dy; +} + + +vector_type +Vmult_scalar (const vector_type v, const real r) +{ + vector_type new_v; + + new_v.dx = v.dx * r; + new_v.dy = v.dy * r; + + return new_v; +} + + +/* Given the IN_VECTOR and OUT_VECTOR, return the angle between them in + degrees, in the range zero to 180. */ + +real +Vangle (const vector_type in_vector, const vector_type out_vector) +{ + vector_type v1 = normalize (in_vector); + vector_type v2 = normalize (out_vector); + + return my_acosd (Vdot (v2, v1)); +} + + +real_coordinate_type +Vadd_point (const real_coordinate_type c, const vector_type v) +{ + real_coordinate_type new_c; + + new_c.x = c.x + v.dx; + new_c.y = c.y + v.dy; + return new_c; +} + + +real_coordinate_type +Vsubtract_point (const real_coordinate_type c, const vector_type v) +{ + real_coordinate_type new_c; + + new_c.x = c.x - v.dx; + new_c.y = c.y - v.dy; + return new_c; +} + + +coordinate_type +Vadd_int_point (const coordinate_type c, const vector_type v) +{ + coordinate_type a; + + a.x = SROUND ((real) c.x + v.dx); + a.y = SROUND ((real) c.y + v.dy); + return a; +} + + +vector_type +Vabs (const vector_type v) +{ + vector_type new_v; + + new_v.dx = fabs (v.dx); + new_v.dy = fabs (v.dy); + return new_v; +} + + +/* Operations on points. */ + +vector_type +Psubtract (const real_coordinate_type c1, const real_coordinate_type c2) +{ + vector_type v; + + v.dx = c1.x - c2.x; + v.dy = c1.y - c2.y; + + return v; +} + +/* Operations on integer points. */ + +vector_type +IPsubtract (const coordinate_type coord1, const coordinate_type coord2) +{ + vector_type v; + + v.dx = coord1.x - coord2.x; + v.dy = coord1.y - coord2.y; + + return v; +} + + +coordinate_type +IPsubtractP (const coordinate_type c1, const coordinate_type c2) +{ + coordinate_type c; + + c.x = c1.x - c2.x; + c.y = c1.y - c2.y; + + return c; +} + + +coordinate_type +IPadd (const coordinate_type c1, const coordinate_type c2) +{ + coordinate_type c; + + c.x = c1.x + c2.x; + c.y = c1.y + c2.y; + + return c; +} + + +coordinate_type +IPmult_scalar (const coordinate_type c, const int i) +{ + coordinate_type a; + + a.x = c.x * i; + a.y = c.y * i; + + return a; +} + + +real_coordinate_type +IPmult_real (const coordinate_type c, const real r) +{ + real_coordinate_type a; + + a.x = c.x * r; + a.y = c.y * r; + + return a; +} + + +boolean +IPequal (const coordinate_type c1, const coordinate_type c2) +{ + return c1.x == c2.x && c1.y == c2.y; +} diff --git a/plug-ins/selection-to-path/vector.h b/plug-ins/selection-to-path/vector.h new file mode 100644 index 0000000..bc6c213 --- /dev/null +++ b/plug-ins/selection-to-path/vector.h @@ -0,0 +1,95 @@ +/* vector.h: operations on vectors and points. + * + * 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 3, 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, see <https://www.gnu.org/licenses/>. + */ + +#ifndef VECTOR_H +#define VECTOR_H + +#include "types.h" + +/* Our vectors are represented as displacements along the x and y axes. */ + +typedef struct +{ + real dx, dy; +} vector_type; + + +/* Consider a point as a vector from the origin. */ +extern vector_type make_vector (const real_coordinate_type); + +/* And a vector as a point, i.e., a displacement from the origin. */ +extern real_coordinate_type 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 real magnitude (const vector_type); +extern vector_type normalize (const vector_type); + +extern vector_type Vadd (const vector_type, const vector_type); +extern real Vdot (const vector_type, const vector_type); +extern vector_type Vmult_scalar (const vector_type, const real); +extern real Vangle (const vector_type in, const vector_type out); + +/* 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 real_coordinate_type Vadd_point + (const real_coordinate_type, const vector_type); + +#define Psubtract_vector Vsubtract_point +extern real_coordinate_type Vsubtract_point + (const real_coordinate_type, const vector_type); + +/* This returns the rounded sum. */ +#define IPadd_vector Vadd_int_point +extern coordinate_type Vadd_int_point + (const coordinate_type, 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 real_coordinate_type, const real_coordinate_type); + +/* These are heavily used in spline fitting, so we define them as macros + instead of functions. */ +#define Padd(rc1, rc2) \ + ((real_coordinate_type) { (rc1).x + (rc2).x, (rc1).y + (rc2).y }) +#define Pmult_scalar(rc, r) \ + ((real_coordinate_type) { (rc).x * (r), (rc).y * (r) }) + +/* Similarly, for points with integer coordinates; here, a subtraction + operator that does return another point is useful. */ +extern vector_type IPsubtract + (const coordinate_type, const coordinate_type); +extern coordinate_type IPsubtractP + (const coordinate_type, const coordinate_type); +extern coordinate_type IPadd + (const coordinate_type, const coordinate_type); +extern coordinate_type IPmult_scalar (const coordinate_type, const int); +extern real_coordinate_type IPmult_real + (const coordinate_type, const real); +extern boolean IPequal (const coordinate_type, const coordinate_type); + +#endif /* not VECTOR_H */ |