diff options
Diffstat (limited to 'editors/openoffice.org-1.0/files/gpc-libart-patch')
| -rw-r--r-- | editors/openoffice.org-1.0/files/gpc-libart-patch | 4380 |
1 files changed, 0 insertions, 4380 deletions
diff --git a/editors/openoffice.org-1.0/files/gpc-libart-patch b/editors/openoffice.org-1.0/files/gpc-libart-patch deleted file mode 100644 index 759cbc89249d..000000000000 --- a/editors/openoffice.org-1.0/files/gpc-libart-patch +++ /dev/null @@ -1,4380 +0,0 @@ -taken from -http://cvs.gnome.org/viewcvs/*checkout*/openoffice/patches/OOO_1_0_3/gpc-libart.diff - -diff -u -r1.41.2.7 configure.in ---- config_office/configure.in 2002/08/16 09:59:41 1.41.2.7 -+++ config_office/configure.in 2002/10/02 00:57:24 -@@ -1075,25 +1074,20 @@ - fi - - dnl =================================================================== --dnl Test for the presence of the required gpc.{c,h} files -+dnl Test for the presence of the required libart files - dnl =================================================================== - --AC_MSG_CHECKING([GPC files]) --if test -f ../external/gpc/gpc.h; then -- HAVE_GPC_H="yes" -+AC_MSG_CHECKING([libart files]) -+if test -f ../external/gpc/art_svp.h; then -+ HAVE_LIBART="yes" - else -- HAVE_GPC_H="no" -+ HAVE_LIBART="no" - fi --if test -f ../external/gpc/gpc.c; then -- HAVE_GPC_C="yes" --else -- HAVE_GPC_C="no" --fi - --if test "$HAVE_GPC_H" = "yes" -a "$HAVE_GPC_C" = "yes"; then -- AC_MSG_RESULT([GPC files found]) -+if test "$HAVE_LIBART" = "yes" ; then -+ AC_MSG_RESULT([libart files found]) - else -- AC_MSG_ERROR([GPC files not found]) -+ AC_MSG_ERROR([libart files not found -- did you apply the Ximian patch?]) - fi - - dnl =================================================================== -diff -uNr /oocvs/OOO_STABLE_1-backup/external/gpc/art_config.h external/gpc/art_config.h ---- /oocvs/OOO_STABLE_1-backup/external/gpc/art_config.h Wed Dec 31 18:00:00 1969 -+++ external/gpc/art_config.h Fri Sep 20 21:41:27 2002 -@@ -0,0 +1,8 @@ -+#define ART_SIZEOF_CHAR (sizeof char) -+#define ART_SIZEOF_SHORT (sizeof short) -+#define ART_SIZEOF_INT (sizeof int) -+#define ART_SIZEOF_LONG (sizeof long) -+ -+typedef unsigned char art_u8; -+typedef unsigned short art_u16; -+typedef unsigned int art_u32; -diff -uNr /oocvs/OOO_STABLE_1-backup/external/gpc/art_misc.c external/gpc/art_misc.c ---- /oocvs/OOO_STABLE_1-backup/external/gpc/art_misc.c Wed Dec 31 18:00:00 1969 -+++ external/gpc/art_misc.c Fri Sep 20 16:00:43 2002 -@@ -0,0 +1,78 @@ -+/* Libart_LGPL - library of basic graphic primitives -+ * Copyright (C) 1998 Raph Levien -+ * -+ * This library is free software; you can redistribute it and/or -+ * modify it under the terms of the GNU Library General Public -+ * License as published by the Free Software Foundation; either -+ * version 2 of the License, or (at your option) any later version. -+ * -+ * This library is distributed in the hope that it will be useful, -+ * but WITHOUT ANY WARRANTY; without even the implied warranty of -+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU -+ * Library General Public License for more details. -+ * -+ * You should have received a copy of the GNU Library General Public -+ * License along with this library; if not, write to the -+ * Free Software Foundation, Inc., 59 Temple Place - Suite 330, -+ * Boston, MA 02111-1307, USA. -+ */ -+ -+/* Various utility functions RLL finds useful. */ -+ -+#include "art_misc.h" -+ -+#ifdef HAVE_UINSTD_H -+#include <unistd.h> -+#endif -+#include <stdio.h> -+#include <stdarg.h> -+ -+/** -+ * art_die: Print the error message to stderr and exit with a return code of 1. -+ * @fmt: The printf-style format for the error message. -+ * -+ * Used for dealing with severe errors. -+ **/ -+void -+art_die (const char *fmt, ...) -+{ -+ va_list ap; -+ -+ va_start (ap, fmt); -+ vfprintf (stderr, fmt, ap); -+ va_end (ap); -+ exit (1); -+} -+ -+/** -+ * art_warn: Print the warning message to stderr. -+ * @fmt: The printf-style format for the warning message. -+ * -+ * Used for generating warnings. -+ **/ -+void -+art_warn (const char *fmt, ...) -+{ -+ va_list ap; -+ -+ va_start (ap, fmt); -+ vfprintf (stderr, fmt, ap); -+ va_end (ap); -+} -+ -+/** -+ * art_dprint: Print the debug message to stderr. -+ * @fmt: The printf-style format for the debug message. -+ * -+ * Used for generating debug output. -+ **/ -+void -+art_dprint (const char *fmt, ...) -+{ -+ va_list ap; -+ -+ va_start (ap, fmt); -+ vfprintf (stderr, fmt, ap); -+ va_end (ap); -+} -+ -diff -uNr /oocvs/OOO_STABLE_1-backup/external/gpc/art_misc.h external/gpc/art_misc.h ---- /oocvs/OOO_STABLE_1-backup/external/gpc/art_misc.h Wed Dec 31 18:00:00 1969 -+++ external/gpc/art_misc.h Fri Sep 20 21:36:13 2002 -@@ -0,0 +1,89 @@ -+/* Libart_LGPL - library of basic graphic primitives -+ * Copyright (C) 1998 Raph Levien -+ * -+ * This library is free software; you can redistribute it and/or -+ * modify it under the terms of the GNU Library General Public -+ * License as published by the Free Software Foundation; either -+ * version 2 of the License, or (at your option) any later version. -+ * -+ * This library is distributed in the hope that it will be useful, -+ * but WITHOUT ANY WARRANTY; without even the implied warranty of -+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU -+ * Library General Public License for more details. -+ * -+ * You should have received a copy of the GNU Library General Public -+ * License along with this library; if not, write to the -+ * Free Software Foundation, Inc., 59 Temple Place - Suite 330, -+ * Boston, MA 02111-1307, USA. -+ */ -+ -+/* Simple macros to set up storage allocation and basic types for libart -+ functions. */ -+ -+#ifndef __ART_MISC_H__ -+#define __ART_MISC_H__ -+ -+#include <stdlib.h> /* for malloc, etc. */ -+ -+#include "art_config.h" -+ -+#define art_alloc malloc -+#define art_free free -+#define art_realloc realloc -+ -+/* These aren't, strictly speaking, configuration macros, but they're -+ damn handy to have around, and may be worth playing with for -+ debugging. */ -+#define art_new(type, n) ((type *)art_alloc ((n) * sizeof(type))) -+ -+#define art_renew(p, type, n) ((type *)art_realloc (p, (n) * sizeof(type))) -+ -+/* This one must be used carefully - in particular, p and max should -+ be variables. They can also be pstruct->el lvalues. */ -+#define art_expand(p, type, max) do { if(max) { p = art_renew (p, type, max <<= 1); } else { max = 1; p = art_new(type, 1); } } while (0) -+ -+typedef int art_boolean; -+#define ART_FALSE 0 -+#define ART_TRUE 1 -+ -+/* define pi */ -+#ifndef M_PI -+#define M_PI 3.14159265358979323846 -+#endif /* M_PI */ -+ -+#ifndef M_SQRT2 -+#define M_SQRT2 1.41421356237309504880 /* sqrt(2) */ -+#endif /* M_SQRT2 */ -+ -+/* Provide macros to feature the GCC function attribute. -+ */ -+#if defined(__GNUC__) && (__GNUC__ > 2 || (__GNUC__ == 2 && __GNUC_MINOR__ > 4)) -+#define ART_GNUC_PRINTF( format_idx, arg_idx ) \ -+ __attribute__((format (printf, format_idx, arg_idx))) -+#define ART_GNUC_NORETURN \ -+ __attribute__((noreturn)) -+#else /* !__GNUC__ */ -+#define ART_GNUC_PRINTF( format_idx, arg_idx ) -+#define ART_GNUC_NORETURN -+#endif /* !__GNUC__ */ -+ -+#ifdef __cplusplus -+extern "C" { -+#endif -+ -+void ART_GNUC_NORETURN -+art_die (const char *fmt, ...) ART_GNUC_PRINTF (1, 2); -+ -+void -+art_warn (const char *fmt, ...) ART_GNUC_PRINTF (1, 2); -+ -+void -+art_dprint (const char *fmt, ...) ART_GNUC_PRINTF (1, 2); -+ -+#ifdef __cplusplus -+} -+#endif -+ -+#define ART_USE_NEW_INTERSECTOR -+ -+#endif /* __ART_MISC_H__ */ -diff -uNr /oocvs/OOO_STABLE_1-backup/external/gpc/art_pathcode.h external/gpc/art_pathcode.h ---- /oocvs/OOO_STABLE_1-backup/external/gpc/art_pathcode.h Wed Dec 31 18:00:00 1969 -+++ external/gpc/art_pathcode.h Fri Sep 20 15:30:03 2002 -@@ -0,0 +1,39 @@ -+/* Libart_LGPL - library of basic graphic primitives -+ * Copyright (C) 1998 Raph Levien -+ * -+ * This library is free software; you can redistribute it and/or -+ * modify it under the terms of the GNU Library General Public -+ * License as published by the Free Software Foundation; either -+ * version 2 of the License, or (at your option) any later version. -+ * -+ * This library is distributed in the hope that it will be useful, -+ * but WITHOUT ANY WARRANTY; without even the implied warranty of -+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU -+ * Library General Public License for more details. -+ * -+ * You should have received a copy of the GNU Library General Public -+ * License along with this library; if not, write to the -+ * Free Software Foundation, Inc., 59 Temple Place - Suite 330, -+ * Boston, MA 02111-1307, USA. -+ */ -+ -+#ifndef __ART_PATHCODE_H__ -+#define __ART_PATHCODE_H__ -+ -+#ifdef __cplusplus -+extern "C" { -+#endif /* __cplusplus */ -+ -+typedef enum { -+ ART_MOVETO, -+ ART_MOVETO_OPEN, -+ ART_CURVETO, -+ ART_LINETO, -+ ART_END -+} ArtPathcode; -+ -+#ifdef __cplusplus -+} -+#endif /* __cplusplus */ -+ -+#endif /* __ART_PATHCODE_H__ */ -diff -uNr /oocvs/OOO_STABLE_1-backup/external/gpc/art_point.h external/gpc/art_point.h ---- /oocvs/OOO_STABLE_1-backup/external/gpc/art_point.h Wed Dec 31 18:00:00 1969 -+++ external/gpc/art_point.h Fri Sep 20 16:02:16 2002 -@@ -0,0 +1,38 @@ -+/* Libart_LGPL - library of basic graphic primitives -+ * Copyright (C) 1998 Raph Levien -+ * -+ * This library is free software; you can redistribute it and/or -+ * modify it under the terms of the GNU Library General Public -+ * License as published by the Free Software Foundation; either -+ * version 2 of the License, or (at your option) any later version. -+ * -+ * This library is distributed in the hope that it will be useful, -+ * but WITHOUT ANY WARRANTY; without even the implied warranty of -+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU -+ * Library General Public License for more details. -+ * -+ * You should have received a copy of the GNU Library General Public -+ * License along with this library; if not, write to the -+ * Free Software Foundation, Inc., 59 Temple Place - Suite 330, -+ * Boston, MA 02111-1307, USA. -+ */ -+ -+#ifndef __ART_POINT_H__ -+#define __ART_POINT_H__ -+ -+#ifdef __cplusplus -+extern "C" { -+#endif /* __cplusplus */ -+ -+typedef struct _ArtPoint ArtPoint; -+ -+struct _ArtPoint { -+ /*< public >*/ -+ double x, y; -+}; -+ -+#ifdef __cplusplus -+} -+#endif /* __cplusplus */ -+ -+#endif /* __ART_POINT_H__ */ -diff -uNr /oocvs/OOO_STABLE_1-backup/external/gpc/art_rect.c external/gpc/art_rect.c ---- /oocvs/OOO_STABLE_1-backup/external/gpc/art_rect.c Wed Dec 31 18:00:00 1969 -+++ external/gpc/art_rect.c Fri Sep 20 16:01:29 2002 -@@ -0,0 +1,214 @@ -+/* Libart_LGPL - library of basic graphic primitives -+ * Copyright (C) 1998 Raph Levien -+ * -+ * This library is free software; you can redistribute it and/or -+ * modify it under the terms of the GNU Library General Public -+ * License as published by the Free Software Foundation; either -+ * version 2 of the License, or (at your option) any later version. -+ * -+ * This library is distributed in the hope that it will be useful, -+ * but WITHOUT ANY WARRANTY; without even the implied warranty of -+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU -+ * Library General Public License for more details. -+ * -+ * You should have received a copy of the GNU Library General Public -+ * License along with this library; if not, write to the -+ * Free Software Foundation, Inc., 59 Temple Place - Suite 330, -+ * Boston, MA 02111-1307, USA. -+ */ -+ -+#include "art_rect.h" -+ -+#include <math.h> -+ -+#ifndef MAX -+#define MAX(a, b) (((a) > (b)) ? (a) : (b)) -+#endif /* MAX */ -+ -+#ifndef MIN -+#define MIN(a, b) (((a) < (b)) ? (a) : (b)) -+#endif /* MIN */ -+ -+/* rectangle primitives stolen from gzilla */ -+ -+/** -+ * art_irect_copy: Make a copy of an integer rectangle. -+ * @dest: Where the copy is stored. -+ * @src: The source rectangle. -+ * -+ * Copies the rectangle. -+ **/ -+void -+art_irect_copy (ArtIRect *dest, const ArtIRect *src) { -+ dest->x0 = src->x0; -+ dest->y0 = src->y0; -+ dest->x1 = src->x1; -+ dest->y1 = src->y1; -+} -+ -+/** -+ * art_irect_union: Find union of two integer rectangles. -+ * @dest: Where the result is stored. -+ * @src1: A source rectangle. -+ * @src2: Another source rectangle. -+ * -+ * Finds the smallest rectangle that includes @src1 and @src2. -+ **/ -+void -+art_irect_union (ArtIRect *dest, const ArtIRect *src1, const ArtIRect *src2) { -+ if (art_irect_empty (src1)) { -+ art_irect_copy (dest, src2); -+ } else if (art_irect_empty (src2)) { -+ art_irect_copy (dest, src1); -+ } else { -+ dest->x0 = MIN (src1->x0, src2->x0); -+ dest->y0 = MIN (src1->y0, src2->y0); -+ dest->x1 = MAX (src1->x1, src2->x1); -+ dest->y1 = MAX (src1->y1, src2->y1); -+ } -+} -+ -+/** -+ * art_irect_intersection: Find intersection of two integer rectangles. -+ * @dest: Where the result is stored. -+ * @src1: A source rectangle. -+ * @src2: Another source rectangle. -+ * -+ * Finds the intersection of @src1 and @src2. -+ **/ -+void -+art_irect_intersect (ArtIRect *dest, const ArtIRect *src1, const ArtIRect *src2) { -+ dest->x0 = MAX (src1->x0, src2->x0); -+ dest->y0 = MAX (src1->y0, src2->y0); -+ dest->x1 = MIN (src1->x1, src2->x1); -+ dest->y1 = MIN (src1->y1, src2->y1); -+} -+ -+/** -+ * art_irect_empty: Determine whether integer rectangle is empty. -+ * @src: The source rectangle. -+ * -+ * Return value: TRUE if @src is an empty rectangle, FALSE otherwise. -+ **/ -+int -+art_irect_empty (const ArtIRect *src) { -+ return (src->x1 <= src->x0 || src->y1 <= src->y0); -+} -+ -+#if 0 -+gboolean irect_point_inside (ArtIRect *rect, GzwPoint *point) { -+ return (point->x >= rect->x0 && point->y >= rect->y0 && -+ point->x < rect->x1 && point->y < rect->y1); -+} -+#endif -+ -+/** -+ * art_drect_copy: Make a copy of a rectangle. -+ * @dest: Where the copy is stored. -+ * @src: The source rectangle. -+ * -+ * Copies the rectangle. -+ **/ -+void -+art_drect_copy (ArtDRect *dest, const ArtDRect *src) { -+ dest->x0 = src->x0; -+ dest->y0 = src->y0; -+ dest->x1 = src->x1; -+ dest->y1 = src->y1; -+} -+ -+/** -+ * art_drect_union: Find union of two rectangles. -+ * @dest: Where the result is stored. -+ * @src1: A source rectangle. -+ * @src2: Another source rectangle. -+ * -+ * Finds the smallest rectangle that includes @src1 and @src2. -+ **/ -+void -+art_drect_union (ArtDRect *dest, const ArtDRect *src1, const ArtDRect *src2) { -+ if (art_drect_empty (src1)) { -+ art_drect_copy (dest, src2); -+ } else if (art_drect_empty (src2)) { -+ art_drect_copy (dest, src1); -+ } else { -+ dest->x0 = MIN (src1->x0, src2->x0); -+ dest->y0 = MIN (src1->y0, src2->y0); -+ dest->x1 = MAX (src1->x1, src2->x1); -+ dest->y1 = MAX (src1->y1, src2->y1); -+ } -+} -+ -+/** -+ * art_drect_intersection: Find intersection of two rectangles. -+ * @dest: Where the result is stored. -+ * @src1: A source rectangle. -+ * @src2: Another source rectangle. -+ * -+ * Finds the intersection of @src1 and @src2. -+ **/ -+void -+art_drect_intersect (ArtDRect *dest, const ArtDRect *src1, const ArtDRect *src2) { -+ dest->x0 = MAX (src1->x0, src2->x0); -+ dest->y0 = MAX (src1->y0, src2->y0); -+ dest->x1 = MIN (src1->x1, src2->x1); -+ dest->y1 = MIN (src1->y1, src2->y1); -+} -+ -+/** -+ * art_irect_empty: Determine whether rectangle is empty. -+ * @src: The source rectangle. -+ * -+ * Return value: TRUE if @src is an empty rectangle, FALSE otherwise. -+ **/ -+int -+art_drect_empty (const ArtDRect *src) { -+ return (src->x1 <= src->x0 || src->y1 <= src->y0); -+} -+ -+/** -+ * art_drect_affine_transform: Affine transform rectangle. -+ * @dst: Where to store the result. -+ * @src: The source rectangle. -+ * @matrix: The affine transformation. -+ * -+ * Find the smallest rectangle enclosing the affine transformed @src. -+ * The result is exactly the affine transformation of @src when -+ * @matrix specifies a rectilinear affine transformation, otherwise it -+ * is a conservative approximation. -+ **/ -+void -+art_drect_affine_transform (ArtDRect *dst, const ArtDRect *src, const double matrix[6]) -+{ -+ double x00, y00, x10, y10; -+ double x01, y01, x11, y11; -+ -+ x00 = src->x0 * matrix[0] + src->y0 * matrix[2] + matrix[4]; -+ y00 = src->x0 * matrix[1] + src->y0 * matrix[3] + matrix[5]; -+ x10 = src->x1 * matrix[0] + src->y0 * matrix[2] + matrix[4]; -+ y10 = src->x1 * matrix[1] + src->y0 * matrix[3] + matrix[5]; -+ x01 = src->x0 * matrix[0] + src->y1 * matrix[2] + matrix[4]; -+ y01 = src->x0 * matrix[1] + src->y1 * matrix[3] + matrix[5]; -+ x11 = src->x1 * matrix[0] + src->y1 * matrix[2] + matrix[4]; -+ y11 = src->x1 * matrix[1] + src->y1 * matrix[3] + matrix[5]; -+ dst->x0 = MIN (MIN (x00, x10), MIN (x01, x11)); -+ dst->y0 = MIN (MIN (y00, y10), MIN (y01, y11)); -+ dst->x1 = MAX (MAX (x00, x10), MAX (x01, x11)); -+ dst->y1 = MAX (MAX (y00, y10), MAX (y01, y11)); -+} -+ -+/** -+ * art_drect_to_irect: Convert rectangle to integer rectangle. -+ * @dst: Where to store resulting integer rectangle. -+ * @src: The source rectangle. -+ * -+ * Find the smallest integer rectangle that encloses @src. -+ **/ -+void -+art_drect_to_irect (ArtIRect *dst, ArtDRect *src) -+{ -+ dst->x0 = floor (src->x0); -+ dst->y0 = floor (src->y0); -+ dst->x1 = ceil (src->x1); -+ dst->y1 = ceil (src->y1); -+} -diff -uNr /oocvs/OOO_STABLE_1-backup/external/gpc/art_rect.h external/gpc/art_rect.h ---- /oocvs/OOO_STABLE_1-backup/external/gpc/art_rect.h Wed Dec 31 18:00:00 1969 -+++ external/gpc/art_rect.h Fri Sep 20 15:31:32 2002 -@@ -0,0 +1,78 @@ -+/* Libart_LGPL - library of basic graphic primitives -+ * Copyright (C) 1998 Raph Levien -+ * -+ * This library is free software; you can redistribute it and/or -+ * modify it under the terms of the GNU Library General Public -+ * License as published by the Free Software Foundation; either -+ * version 2 of the License, or (at your option) any later version. -+ * -+ * This library is distributed in the hope that it will be useful, -+ * but WITHOUT ANY WARRANTY; without even the implied warranty of -+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU -+ * Library General Public License for more details. -+ * -+ * You should have received a copy of the GNU Library General Public -+ * License along with this library; if not, write to the -+ * Free Software Foundation, Inc., 59 Temple Place - Suite 330, -+ * Boston, MA 02111-1307, USA. -+ */ -+ -+#ifndef __ART_RECT_H__ -+#define __ART_RECT_H__ -+ -+#ifdef __cplusplus -+extern "C" { -+#endif -+ -+typedef struct _ArtDRect ArtDRect; -+typedef struct _ArtIRect ArtIRect; -+ -+struct _ArtDRect { -+ /*< public >*/ -+ double x0, y0, x1, y1; -+}; -+ -+struct _ArtIRect { -+ /*< public >*/ -+ int x0, y0, x1, y1; -+}; -+ -+/* Make a copy of the rectangle. */ -+void art_irect_copy (ArtIRect *dest, const ArtIRect *src); -+ -+/* Find the smallest rectangle that includes both source rectangles. */ -+void art_irect_union (ArtIRect *dest, -+ const ArtIRect *src1, const ArtIRect *src2); -+ -+/* Return the intersection of the two rectangles */ -+void art_irect_intersect (ArtIRect *dest, -+ const ArtIRect *src1, const ArtIRect *src2); -+ -+/* Return true if the rectangle is empty. */ -+int art_irect_empty (const ArtIRect *src); -+ -+/* Make a copy of the rectangle. */ -+void art_drect_copy (ArtDRect *dest, const ArtDRect *src); -+ -+/* Find the smallest rectangle that includes both source rectangles. */ -+void art_drect_union (ArtDRect *dest, -+ const ArtDRect *src1, const ArtDRect *src2); -+ -+/* Return the intersection of the two rectangles */ -+void art_drect_intersect (ArtDRect *dest, -+ const ArtDRect *src1, const ArtDRect *src2); -+ -+/* Return true if the rectangle is empty. */ -+int art_drect_empty (const ArtDRect *src); -+ -+void -+art_drect_affine_transform (ArtDRect *dst, const ArtDRect *src, -+ const double matrix[6]); -+ -+void art_drect_to_irect (ArtIRect *dst, ArtDRect *src); -+ -+#ifdef __cplusplus -+} -+#endif -+ -+#endif -diff -uNr /oocvs/OOO_STABLE_1-backup/external/gpc/art_svp.c external/gpc/art_svp.c ---- /oocvs/OOO_STABLE_1-backup/external/gpc/art_svp.c Wed Dec 31 18:00:00 1969 -+++ external/gpc/art_svp.c Fri Sep 20 16:01:49 2002 -@@ -0,0 +1,150 @@ -+/* Libart_LGPL - library of basic graphic primitives -+ * Copyright (C) 1998 Raph Levien -+ * -+ * This library is free software; you can redistribute it and/or -+ * modify it under the terms of the GNU Library General Public -+ * License as published by the Free Software Foundation; either -+ * version 2 of the License, or (at your option) any later version. -+ * -+ * This library is distributed in the hope that it will be useful, -+ * but WITHOUT ANY WARRANTY; without even the implied warranty of -+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU -+ * Library General Public License for more details. -+ * -+ * You should have received a copy of the GNU Library General Public -+ * License along with this library; if not, write to the -+ * Free Software Foundation, Inc., 59 Temple Place - Suite 330, -+ * Boston, MA 02111-1307, USA. -+ */ -+ -+/* Basic constructors and operations for sorted vector paths */ -+ -+#include "art_svp.h" -+#include "art_misc.h" -+ -+/* Add a new segment. The arguments can be zero and NULL if the caller -+ would rather fill them in later. -+ -+ We also realloc one auxiliary array of ints of size n_segs if -+ desired. -+*/ -+/** -+ * art_svp_add_segment: Add a segment to an #ArtSVP structure. -+ * @p_vp: Pointer to where the #ArtSVP structure is stored. -+ * @pn_segs_max: Pointer to the allocated size of *@p_vp. -+ * @pn_points_max: Pointer to where auxiliary array is stored. -+ * @n_points: Number of points for new segment. -+ * @dir: Direction for new segment; 0 is up, 1 is down. -+ * @points: Points for new segment. -+ * @bbox: Bounding box for new segment. -+ * -+ * Adds a new segment to an ArtSVP structure. This routine reallocates -+ * the structure if necessary, updating *@p_vp and *@pn_segs_max as -+ * necessary. -+ * -+ * The new segment is simply added after all other segments. Thus, -+ * this routine should be called in order consistent with the #ArtSVP -+ * sorting rules. -+ * -+ * If the @bbox argument is given, it is simply stored in the new -+ * segment. Otherwise (if it is NULL), the bounding box is computed -+ * from the @points given. -+ **/ -+int -+art_svp_add_segment (ArtSVP **p_vp, int *pn_segs_max, -+ int **pn_points_max, -+ int n_points, int dir, ArtPoint *points, -+ ArtDRect *bbox) -+{ -+ int seg_num; -+ ArtSVP *svp; -+ ArtSVPSeg *seg; -+ -+ svp = *p_vp; -+ seg_num = svp->n_segs++; -+ if (*pn_segs_max == seg_num) -+ { -+ *pn_segs_max <<= 1; -+ svp = (ArtSVP *)art_realloc (svp, sizeof(ArtSVP) + -+ (*pn_segs_max - 1) * sizeof(ArtSVPSeg)); -+ *p_vp = svp; -+ if (pn_points_max != NULL) -+ *pn_points_max = art_renew (*pn_points_max, int, *pn_segs_max); -+ } -+ seg = &svp->segs[seg_num]; -+ seg->n_points = n_points; -+ seg->dir = dir; -+ seg->points = points; -+ if (bbox) -+ seg->bbox = *bbox; -+ else if (points) -+ { -+ double x_min, x_max; -+ int i; -+ -+ x_min = x_max = points[0].x; -+ for (i = 1; i < n_points; i++) -+ { -+ if (x_min > points[i].x) -+ x_min = points[i].x; -+ if (x_max < points[i].x) -+ x_max = points[i].x; -+ } -+ seg->bbox.x0 = x_min; -+ seg->bbox.y0 = points[0].y; -+ -+ seg->bbox.x1 = x_max; -+ seg->bbox.y1 = points[n_points - 1].y; -+ } -+ return seg_num; -+} -+ -+ -+/** -+ * art_svp_free: Free an #ArtSVP structure. -+ * @svp: #ArtSVP to free. -+ * -+ * Frees an #ArtSVP structure and all the segments in it. -+ **/ -+void -+art_svp_free (ArtSVP *svp) -+{ -+ int n_segs = svp->n_segs; -+ int i; -+ -+ for (i = 0; i < n_segs; i++) -+ art_free (svp->segs[i].points); -+ art_free (svp); -+} -+ -+#ifdef ART_USE_NEW_INTERSECTOR -+#define EPSILON 0 -+#else -+#define EPSILON 1e-6 -+#endif -+ -+/** -+ * art_svp_seg_compare: Compare two segments of an svp. -+ * @seg1: First segment to compare. -+ * @seg2: Second segment to compare. -+ * -+ * Compares two segments of an svp. Return 1 if @seg2 is below or to the -+ * right of @seg1, -1 otherwise. -+ **/ -+int -+art_svp_seg_compare (const void *s1, const void *s2) -+{ -+ const ArtSVPSeg *seg1 = s1; -+ const ArtSVPSeg *seg2 = s2; -+ -+ if (seg1->points[0].y - EPSILON > seg2->points[0].y) return 1; -+ else if (seg1->points[0].y + EPSILON < seg2->points[0].y) return -1; -+ else if (seg1->points[0].x - EPSILON > seg2->points[0].x) return 1; -+ else if (seg1->points[0].x + EPSILON < seg2->points[0].x) return -1; -+ else if ((seg1->points[1].x - seg1->points[0].x) * -+ (seg2->points[1].y - seg2->points[0].y) - -+ (seg1->points[1].y - seg1->points[0].y) * -+ (seg2->points[1].x - seg2->points[0].x) > 0) return 1; -+ else return -1; -+} -+ -diff -uNr /oocvs/OOO_STABLE_1-backup/external/gpc/art_svp.h external/gpc/art_svp.h ---- /oocvs/OOO_STABLE_1-backup/external/gpc/art_svp.h Wed Dec 31 18:00:00 1969 -+++ external/gpc/art_svp.h Fri Sep 20 21:36:42 2002 -@@ -0,0 +1,63 @@ -+/* Libart_LGPL - library of basic graphic primitives -+ * Copyright (C) 1998 Raph Levien -+ * -+ * This library is free software; you can redistribute it and/or -+ * modify it under the terms of the GNU Library General Public -+ * License as published by the Free Software Foundation; either -+ * version 2 of the License, or (at your option) any later version. -+ * -+ * This library is distributed in the hope that it will be useful, -+ * but WITHOUT ANY WARRANTY; without even the implied warranty of -+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU -+ * Library General Public License for more details. -+ * -+ * You should have received a copy of the GNU Library General Public -+ * License along with this library; if not, write to the -+ * Free Software Foundation, Inc., 59 Temple Place - Suite 330, -+ * Boston, MA 02111-1307, USA. -+ */ -+ -+#ifndef __ART_SVP_H__ -+#define __ART_SVP_H__ -+ -+/* Basic data structures and constructors for sorted vector paths */ -+ -+#include "art_rect.h" -+#include "art_point.h" -+ -+#ifdef __cplusplus -+extern "C" { -+#endif /* __cplusplus */ -+ -+typedef struct _ArtSVP ArtSVP; -+typedef struct _ArtSVPSeg ArtSVPSeg; -+ -+struct _ArtSVPSeg { -+ int n_points; -+ int dir; /* == 0 for "up", 1 for "down" */ -+ ArtDRect bbox; -+ ArtPoint *points; -+}; -+ -+struct _ArtSVP { -+ int n_segs; -+ ArtSVPSeg segs[1]; -+}; -+ -+int -+art_svp_add_segment (ArtSVP **p_vp, int *pn_segs_max, -+ int **pn_points_max, -+ int n_points, int dir, ArtPoint *points, -+ ArtDRect *bbox); -+ -+void -+art_svp_free (ArtSVP *svp); -+ -+int -+art_svp_seg_compare (const void *s1, const void *s2); -+ -+#ifdef __cplusplus -+} -+#endif /* __cplusplus */ -+ -+#endif /* __ART_SVP_H__ */ -diff -uNr /oocvs/OOO_STABLE_1-backup/external/gpc/art_svp_intersect.c external/gpc/art_svp_intersect.c ---- /oocvs/OOO_STABLE_1-backup/external/gpc/art_svp_intersect.c Wed Dec 31 18:00:00 1969 -+++ external/gpc/art_svp_intersect.c Fri Sep 20 21:42:30 2002 -@@ -0,0 +1,1802 @@ -+/* Libart_LGPL - library of basic graphic primitives -+ * Copyright (C) 2001 Raph Levien -+ * -+ * This library is free software; you can redistribute it and/or -+ * modify it under the terms of the GNU Library General Public -+ * License as published by the Free Software Foundation; either -+ * version 2 of the License, or (at your option) any later version. -+ * -+ * This library is distributed in the hope that it will be useful, -+ * but WITHOUT ANY WARRANTY; without even the implied warranty of -+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU -+ * Library General Public License for more details. -+ * -+ * You should have received a copy of the GNU Library General Public -+ * License along with this library; if not, write to the -+ * Free Software Foundation, Inc., 59 Temple Place - Suite 330, -+ * Boston, MA 02111-1307, USA. -+ */ -+ -+/* This file contains a testbed implementation of the new intersection -+ code. -+*/ -+ -+#include "art_svp_intersect.h" -+ -+#include <math.h> /* for sqrt */ -+ -+/* Sanitychecking verifies the main invariant on every priority queue -+ point. Do not use in production, as it slows things down way too -+ much. */ -+#define noSANITYCHECK -+ -+/* This can be used in production, to prevent hangs. Eventually, it -+ should not be necessary. */ -+#define CHEAP_SANITYCHECK -+ -+#define noVERBOSE -+ -+#include "art_misc.h" -+ -+/* A priority queue - perhaps move to a separate file if it becomes -+ needed somewhere else */ -+ -+#define ART_PRIQ_USE_HEAP -+ -+typedef struct _ArtPriQ ArtPriQ; -+typedef struct _ArtPriPoint ArtPriPoint; -+ -+struct _ArtPriQ { -+ int n_items; -+ int n_items_max; -+ ArtPriPoint **items; -+}; -+ -+struct _ArtPriPoint { -+ double x; -+ double y; -+ void *user_data; -+}; -+ -+static ArtPriQ * -+art_pri_new (void) -+{ -+ ArtPriQ *result = art_new (ArtPriQ, 1); -+ -+ result->n_items = 0; -+ result->n_items_max = 16; -+ result->items = art_new (ArtPriPoint *, result->n_items_max); -+ return result; -+} -+ -+static void -+art_pri_free (ArtPriQ *pq) -+{ -+ art_free (pq->items); -+ art_free (pq); -+} -+ -+static art_boolean -+art_pri_empty (ArtPriQ *pq) -+{ -+ return pq->n_items == 0; -+} -+ -+#ifdef ART_PRIQ_USE_HEAP -+ -+/* This heap implementation is based on Vasek Chvatal's course notes: -+ http://www.cs.rutgers.edu/~chvatal/notes/pq.html#heap */ -+ -+static void -+art_pri_bubble_up (ArtPriQ *pq, int vacant, ArtPriPoint *missing) -+{ -+ ArtPriPoint **items = pq->items; -+ int parent; -+ -+ parent = (vacant - 1) >> 1; -+ while (vacant > 0 && (missing->y < items[parent]->y || -+ (missing->y == items[parent]->y && -+ missing->x < items[parent]->x))) -+ { -+ items[vacant] = items[parent]; -+ vacant = parent; -+ parent = (vacant - 1) >> 1; -+ } -+ -+ items[vacant] = missing; -+} -+ -+static void -+art_pri_insert (ArtPriQ *pq, ArtPriPoint *point) -+{ -+ if (pq->n_items == pq->n_items_max) -+ art_expand (pq->items, ArtPriPoint *, pq->n_items_max); -+ -+ art_pri_bubble_up (pq, pq->n_items++, point); -+} -+ -+static void -+art_pri_sift_down_from_root (ArtPriQ *pq, ArtPriPoint *missing) -+{ -+ ArtPriPoint **items = pq->items; -+ int vacant = 0, child = 2; -+ int n = pq->n_items; -+ -+ while (child < n) -+ { -+ if (items[child - 1]->y < items[child]->y || -+ (items[child - 1]->y == items[child]->y && -+ items[child - 1]->x < items[child]->x)) -+ child--; -+ items[vacant] = items[child]; -+ vacant = child; -+ child = (vacant + 1) << 1; -+ } -+ if (child == n) -+ { -+ items[vacant] = items[n - 1]; -+ vacant = n - 1; -+ } -+ -+ art_pri_bubble_up (pq, vacant, missing); -+} -+ -+static ArtPriPoint * -+art_pri_choose (ArtPriQ *pq) -+{ -+ ArtPriPoint *result = pq->items[0]; -+ -+ art_pri_sift_down_from_root (pq, pq->items[--pq->n_items]); -+ return result; -+} -+ -+#else -+ -+/* Choose least point in queue */ -+static ArtPriPoint * -+art_pri_choose (ArtPriQ *pq) -+{ -+ int i; -+ int best = 0; -+ double best_x, best_y; -+ double y; -+ ArtPriPoint *result; -+ -+ if (pq->n_items == 0) -+ return NULL; -+ -+ best_x = pq->items[best]->x; -+ best_y = pq->items[best]->y; -+ -+ for (i = 1; i < pq->n_items; i++) -+ { -+ y = pq->items[i]->y; -+ if (y < best_y || (y == best_y && pq->items[i]->x < best_x)) -+ { -+ best = i; -+ best_x = pq->items[best]->x; -+ best_y = y; -+ } -+ } -+ result = pq->items[best]; -+ pq->items[best] = pq->items[--pq->n_items]; -+ return result; -+} -+ -+static void -+art_pri_insert (ArtPriQ *pq, ArtPriPoint *point) -+{ -+ if (pq->n_items == pq->n_items_max) -+ art_expand (pq->items, ArtPriPoint *, pq->n_items_max); -+ -+ pq->items[pq->n_items++] = point; -+} -+ -+#endif -+ -+#ifdef TEST_PRIQ -+ -+#include <stdlib.h> /* for rand() */ -+#include <stdio.h> -+ -+static double -+double_rand (double lo, double hi, int quant) -+{ -+ int tmp = rand () / (RAND_MAX * (1.0 / quant)) + 0.5; -+ return lo + tmp * ((hi - lo) / quant); -+} -+ -+/* -+ * This custom allocator for priority queue points is here so I can -+ * test speed. It doesn't look like it will be that significant, but -+ * if I want a small improvement later, it's something. -+ */ -+ -+typedef ArtPriPoint *ArtPriPtPool; -+ -+static ArtPriPtPool * -+art_pri_pt_pool_new (void) -+{ -+ ArtPriPtPool *result = art_new (ArtPriPtPool, 1); -+ *result = NULL; -+ return result; -+} -+ -+static ArtPriPoint * -+art_pri_pt_alloc (ArtPriPtPool *pool) -+{ -+ ArtPriPoint *result = *pool; -+ if (result == NULL) -+ return art_new (ArtPriPoint, 1); -+ else -+ { -+ *pool = result->user_data; -+ return result; -+ } -+} -+ -+static void -+art_pri_pt_free (ArtPriPtPool *pool, ArtPriPoint *pt) -+{ -+ pt->user_data = *pool; -+ *pool = pt; -+} -+ -+static void -+art_pri_pt_pool_free (ArtPriPtPool *pool) -+{ -+ ArtPriPoint *pt = *pool; -+ while (pt != NULL) -+ { -+ ArtPriPoint *next = pt->user_data; -+ art_free (pt); -+ pt = next; -+ } -+ art_free (pool); -+} -+ -+int -+main (int argc, char **argv) -+{ -+ ArtPriPtPool *pool = art_pri_pt_pool_new (); -+ ArtPriQ *pq; -+ int i, j; -+ const int n_iter = 1; -+ const int pq_size = 100; -+ -+ for (j = 0; j < n_iter; j++) -+ { -+ pq = art_pri_new (); -+ -+ for (i = 0; i < pq_size; i++) -+ { -+ ArtPriPoint *pt = art_pri_pt_alloc (pool); -+ pt->x = double_rand (0, 1, 100); -+ pt->y = double_rand (0, 1, 100); -+ pt->user_data = (void *)i; -+ art_pri_insert (pq, pt); -+ } -+ -+ while (!art_pri_empty (pq)) -+ { -+ ArtPriPoint *pt = art_pri_choose (pq); -+ if (n_iter == 1) -+ printf ("(%g, %g), %d\n", pt->x, pt->y, (int)pt->user_data); -+ art_pri_pt_free (pool, pt); -+ } -+ -+ art_pri_free (pq); -+ } -+ art_pri_pt_pool_free (pool); -+ return 0; -+} -+ -+#else /* TEST_PRIQ */ -+ -+/* A virtual class for an "svp writer". A client of this object creates an -+ SVP by repeatedly calling "add segment" and "add point" methods on it. -+*/ -+ -+typedef struct _ArtSvpWriterRewind ArtSvpWriterRewind; -+ -+/* An implementation of the svp writer virtual class that applies the -+ winding rule. */ -+ -+struct _ArtSvpWriterRewind { -+ ArtSvpWriter super; -+ ArtWindRule rule; -+ ArtSVP *svp; -+ int n_segs_max; -+ int *n_points_max; -+}; -+ -+static int -+art_svp_writer_rewind_add_segment (ArtSvpWriter *self, int wind_left, -+ int delta_wind, double x, double y) -+{ -+ ArtSvpWriterRewind *swr = (ArtSvpWriterRewind *)self; -+ ArtSVP *svp; -+ ArtSVPSeg *seg; -+ art_boolean left_filled, right_filled; -+ int wind_right = wind_left + delta_wind; -+ int seg_num; -+ const int init_n_points_max = 4; -+ -+ switch (swr->rule) -+ { -+ case ART_WIND_RULE_NONZERO: -+ left_filled = (wind_left != 0); -+ right_filled = (wind_right != 0); -+ break; -+ case ART_WIND_RULE_INTERSECT: -+ left_filled = (wind_left > 1); -+ right_filled = (wind_right > 1); -+ break; -+ case ART_WIND_RULE_ODDEVEN: -+ left_filled = (wind_left & 1); -+ right_filled = (wind_right & 1); -+ break; -+ case ART_WIND_RULE_POSITIVE: -+ left_filled = (wind_left > 0); -+ right_filled = (wind_right > 0); -+ break; -+ default: -+ art_die ("Unknown wind rule %d\n", swr->rule); -+ } -+ if (left_filled == right_filled) -+ { -+ /* discard segment now */ -+#ifdef VERBOSE -+ art_dprint ("swr add_segment: %d += %d (%g, %g) --> -1\n", -+ wind_left, delta_wind, x, y); -+#endif -+ return -1; -+ } -+ -+ svp = swr->svp; -+ seg_num = svp->n_segs++; -+ if (swr->n_segs_max == seg_num) -+ { -+ swr->n_segs_max <<= 1; -+ svp = (ArtSVP *)art_realloc (svp, sizeof(ArtSVP) + -+ (swr->n_segs_max - 1) * -+ sizeof(ArtSVPSeg)); -+ swr->svp = svp; -+ swr->n_points_max = art_renew (swr->n_points_max, int, -+ swr->n_segs_max); -+ } -+ seg = &svp->segs[seg_num]; -+ seg->n_points = 1; -+ seg->dir = right_filled; -+ swr->n_points_max[seg_num] = init_n_points_max; -+ seg->bbox.x0 = x; -+ seg->bbox.y0 = y; -+ seg->bbox.x1 = x; -+ seg->bbox.y1 = y; -+ seg->points = art_new (ArtPoint, init_n_points_max); -+ seg->points[0].x = x; -+ seg->points[0].y = y; -+#ifdef VERBOSE -+ art_dprint ("swr add_segment: %d += %d (%g, %g) --> %d(%s)\n", -+ wind_left, delta_wind, x, y, seg_num, -+ seg->dir ? "v" : "^"); -+#endif -+ return seg_num; -+} -+ -+static void -+art_svp_writer_rewind_add_point (ArtSvpWriter *self, int seg_id, -+ double x, double y) -+{ -+ ArtSvpWriterRewind *swr = (ArtSvpWriterRewind *)self; -+ ArtSVPSeg *seg; -+ int n_points; -+ -+#ifdef VERBOSE -+ art_dprint ("swr add_point: %d (%g, %g)\n", seg_id, x, y); -+#endif -+ if (seg_id < 0) -+ /* omitted segment */ -+ return; -+ -+ seg = &swr->svp->segs[seg_id]; -+ n_points = seg->n_points++; -+ if (swr->n_points_max[seg_id] == n_points) -+ art_expand (seg->points, ArtPoint, swr->n_points_max[seg_id]); -+ seg->points[n_points].x = x; -+ seg->points[n_points].y = y; -+ if (x < seg->bbox.x0) -+ seg->bbox.x0 = x; -+ if (x > seg->bbox.x1) -+ seg->bbox.x1 = x; -+ seg->bbox.y1 = y; -+} -+ -+static void -+art_svp_writer_rewind_close_segment (ArtSvpWriter *self, int seg_id) -+{ -+ /* Not needed for this simple implementation. A potential future -+ optimization is to merge segments that can be merged safely. */ -+#ifdef SANITYCHECK -+ ArtSvpWriterRewind *swr = (ArtSvpWriterRewind *)self; -+ ArtSVPSeg *seg; -+ -+ if (seg_id >= 0) -+ { -+ seg = &swr->svp->segs[seg_id]; -+ if (seg->n_points < 2) -+ art_warn ("*** closing segment %d with only %d point%s\n", -+ seg_id, seg->n_points, seg->n_points == 1 ? "" : "s"); -+ } -+#endif -+ -+#ifdef VERBOSE -+ art_dprint ("swr close_segment: %d\n", seg_id); -+#endif -+} -+ -+ArtSVP * -+art_svp_writer_rewind_reap (ArtSvpWriter *self) -+{ -+ ArtSvpWriterRewind *swr = (ArtSvpWriterRewind *)self; -+ ArtSVP *result = swr->svp; -+ -+ art_free (swr->n_points_max); -+ art_free (swr); -+ return result; -+} -+ -+ArtSvpWriter * -+art_svp_writer_rewind_new (ArtWindRule rule) -+{ -+ ArtSvpWriterRewind *result = art_new (ArtSvpWriterRewind, 1); -+ -+ result->super.add_segment = art_svp_writer_rewind_add_segment; -+ result->super.add_point = art_svp_writer_rewind_add_point; -+ result->super.close_segment = art_svp_writer_rewind_close_segment; -+ -+ result->rule = rule; -+ result->n_segs_max = 16; -+ result->svp = art_alloc (sizeof(ArtSVP) + -+ (result->n_segs_max - 1) * sizeof(ArtSVPSeg)); -+ result->svp->n_segs = 0; -+ result->n_points_max = art_new (int, result->n_segs_max); -+ -+ return &result->super; -+} -+ -+/* Now, data structures for the active list */ -+ -+typedef struct _ArtActiveSeg ArtActiveSeg; -+ -+/* Note: BNEG is 1 for \ lines, and 0 for /. Thus, -+ x[(flags & BNEG) ^ 1] <= x[flags & BNEG] */ -+#define ART_ACTIVE_FLAGS_BNEG 1 -+ -+/* This flag is set if the segment has been inserted into the active -+ list. */ -+#define ART_ACTIVE_FLAGS_IN_ACTIVE 2 -+ -+/* This flag is set when the segment is to be deleted in the -+ horiz commit process. */ -+#define ART_ACTIVE_FLAGS_DEL 4 -+ -+/* This flag is set if the seg_id is a valid output segment. */ -+#define ART_ACTIVE_FLAGS_OUT 8 -+ -+/* This flag is set if the segment is in the horiz list. */ -+#define ART_ACTIVE_FLAGS_IN_HORIZ 16 -+ -+struct _ArtActiveSeg { -+ int flags; -+ int wind_left, delta_wind; -+ ArtActiveSeg *left, *right; /* doubly linked list structure */ -+ -+ const ArtSVPSeg *in_seg; -+ int in_curs; -+ -+ double x[2]; -+ double y0, y1; -+ double a, b, c; /* line equation; ax+by+c = 0 for the line, a^2 + b^2 = 1, -+ and a>0 */ -+ -+ /* bottom point and intersection point stack */ -+ int n_stack; -+ int n_stack_max; -+ ArtPoint *stack; -+ -+ /* horiz commit list */ -+ ArtActiveSeg *horiz_left, *horiz_right; -+ double horiz_x; -+ int horiz_delta_wind; -+ int seg_id; -+}; -+ -+typedef struct _ArtIntersectCtx ArtIntersectCtx; -+ -+struct _ArtIntersectCtx { -+ const ArtSVP *in; -+ ArtSvpWriter *out; -+ -+ ArtPriQ *pq; -+ -+ ArtActiveSeg *active_head; -+ -+ double y; -+ ArtActiveSeg *horiz_first; -+ ArtActiveSeg *horiz_last; -+ -+ /* segment index of next input segment to be added to pri q */ -+ int in_curs; -+}; -+ -+#define EPSILON_A 1e-5 /* Threshold for breaking lines at point insertions */ -+ -+/** -+ * art_svp_intersect_setup_seg: Set up an active segment from input segment. -+ * @seg: Active segment. -+ * @pri_pt: Priority queue point to initialize. -+ * -+ * Sets the x[], a, b, c, flags, and stack fields according to the -+ * line from the current cursor value. Sets the priority queue point -+ * to the bottom point of this line. Also advances the input segment -+ * cursor. -+ **/ -+static void -+art_svp_intersect_setup_seg (ArtActiveSeg *seg, ArtPriPoint *pri_pt) -+{ -+ const ArtSVPSeg *in_seg = seg->in_seg; -+ int in_curs = seg->in_curs++; -+ double x0, y0, x1, y1; -+ double dx, dy, s; -+ double a, b, r2; -+ -+ x0 = in_seg->points[in_curs].x; -+ y0 = in_seg->points[in_curs].y; -+ x1 = in_seg->points[in_curs + 1].x; -+ y1 = in_seg->points[in_curs + 1].y; -+ pri_pt->x = x1; -+ pri_pt->y = y1; -+ dx = x1 - x0; -+ dy = y1 - y0; -+ r2 = dx * dx + dy * dy; -+ s = r2 == 0 ? 1 : 1 / sqrt (r2); -+ seg->a = a = dy * s; -+ seg->b = b = -dx * s; -+ seg->c = -(a * x0 + b * y0); -+ seg->flags = (seg->flags & ~ART_ACTIVE_FLAGS_BNEG) | (dx > 0); -+ seg->x[0] = x0; -+ seg->x[1] = x1; -+ seg->y0 = y0; -+ seg->y1 = y1; -+ seg->n_stack = 1; -+ seg->stack[0].x = x1; -+ seg->stack[0].y = y1; -+} -+ -+/** -+ * art_svp_intersect_add_horiz: Add point to horizontal list. -+ * @ctx: Intersector context. -+ * @seg: Segment with point to insert into horizontal list. -+ * -+ * Inserts @seg into horizontal list, keeping it in ascending horiz_x -+ * order. -+ * -+ * Note: the horiz_commit routine processes "clusters" of segs in the -+ * horiz list, all sharing the same horiz_x value. The cluster is -+ * processed in active list order, rather than horiz list order. Thus, -+ * the order of segs in the horiz list sharing the same horiz_x -+ * _should_ be irrelevant. Even so, we use b as a secondary sorting key, -+ * as a "belt and suspenders" defensive coding tactic. -+ **/ -+static void -+art_svp_intersect_add_horiz (ArtIntersectCtx *ctx, ArtActiveSeg *seg) -+{ -+ ArtActiveSeg **pp = &ctx->horiz_last; -+ ArtActiveSeg *place; -+ ArtActiveSeg *place_right = NULL; -+ -+ -+#ifdef CHEAP_SANITYCHECK -+ if (seg->flags & ART_ACTIVE_FLAGS_IN_HORIZ) -+ { -+ art_warn ("*** attempt to put segment in horiz list twice\n"); -+ return; -+ } -+ seg->flags |= ART_ACTIVE_FLAGS_IN_HORIZ; -+#endif -+ -+#ifdef VERBOSE -+ art_dprint ("add_horiz %lx, x = %g\n", (unsigned long) seg, seg->horiz_x); -+#endif -+ for (place = *pp; place != NULL && (place->horiz_x > seg->horiz_x || -+ (place->horiz_x == seg->horiz_x && -+ place->b < seg->b)); -+ place = *pp) -+ { -+ place_right = place; -+ pp = &place->horiz_left; -+ } -+ *pp = seg; -+ seg->horiz_left = place; -+ seg->horiz_right = place_right; -+ if (place == NULL) -+ ctx->horiz_first = seg; -+ else -+ place->horiz_right = seg; -+} -+ -+static void -+art_svp_intersect_push_pt (ArtIntersectCtx *ctx, ArtActiveSeg *seg, -+ double x, double y) -+{ -+ ArtPriPoint *pri_pt; -+ int n_stack = seg->n_stack; -+ -+ if (n_stack == seg->n_stack_max) -+ art_expand (seg->stack, ArtPoint, seg->n_stack_max); -+ seg->stack[n_stack].x = x; -+ seg->stack[n_stack].y = y; -+ seg->n_stack++; -+ -+ seg->x[1] = x; -+ seg->y1 = y; -+ -+ pri_pt = art_new (ArtPriPoint, 1); -+ pri_pt->x = x; -+ pri_pt->y = y; -+ pri_pt->user_data = seg; -+ art_pri_insert (ctx->pq, pri_pt); -+} -+ -+typedef enum { -+ ART_BREAK_LEFT = 1, -+ ART_BREAK_RIGHT = 2 -+} ArtBreakFlags; -+ -+/** -+ * art_svp_intersect_break: Break an active segment. -+ * -+ * Note: y must be greater than the top point's y, and less than -+ * the bottom's. -+ * -+ * Return value: x coordinate of break point. -+ */ -+static double -+art_svp_intersect_break (ArtIntersectCtx *ctx, ArtActiveSeg *seg, -+ double x_ref, double y, ArtBreakFlags break_flags) -+{ -+ double x0, y0, x1, y1; -+ const ArtSVPSeg *in_seg = seg->in_seg; -+ int in_curs = seg->in_curs; -+ double x; -+ -+ x0 = in_seg->points[in_curs - 1].x; -+ y0 = in_seg->points[in_curs - 1].y; -+ x1 = in_seg->points[in_curs].x; -+ y1 = in_seg->points[in_curs].y; -+ x = x0 + (x1 - x0) * ((y - y0) / (y1 - y0)); -+ if ((break_flags == ART_BREAK_LEFT && x > x_ref) || -+ (break_flags == ART_BREAK_RIGHT && x < x_ref)) -+ { -+#ifdef VERBOSE -+ art_dprint ("art_svp_intersect_break: limiting x to %f, was %f, %s\n", -+ x_ref, x, break_flags == ART_BREAK_LEFT ? "left" : "right"); -+ x = x_ref; -+#endif -+ } -+ -+ /* I think we can count on min(x0, x1) <= x <= max(x0, x1) with sane -+ arithmetic, but it might be worthwhile to check just in case. */ -+ -+ if (y > ctx->y) -+ art_svp_intersect_push_pt (ctx, seg, x, y); -+ else -+ { -+ seg->x[0] = x; -+ seg->y0 = y; -+ seg->horiz_x = x; -+ art_svp_intersect_add_horiz (ctx, seg); -+ } -+ -+ return x; -+} -+ -+/** -+ * art_svp_intersect_add_point: Add a point, breaking nearby neighbors. -+ * @ctx: Intersector context. -+ * @x: X coordinate of point to add. -+ * @y: Y coordinate of point to add. -+ * @seg: "nearby" segment, or NULL if leftmost. -+ * -+ * Return value: Segment immediately to the left of the new point, or -+ * NULL if the new point is leftmost. -+ **/ -+static ArtActiveSeg * -+art_svp_intersect_add_point (ArtIntersectCtx *ctx, double x, double y, -+ ArtActiveSeg *seg, ArtBreakFlags break_flags) -+{ -+ ArtActiveSeg *left, *right; -+ double x_min = x, x_max = x; -+ art_boolean left_live, right_live; -+ double d; -+ double new_x; -+ ArtActiveSeg *test, *result = NULL; -+ double x_test; -+ -+ left = seg; -+ if (left == NULL) -+ right = ctx->active_head; -+ else -+ right = left->right; -+ left_live = (break_flags & ART_BREAK_LEFT) && (left != NULL); -+ right_live = (break_flags & ART_BREAK_RIGHT) && (right != NULL); -+ while (left_live || right_live) -+ { -+ if (left_live) -+ { -+ if (x <= left->x[left->flags & ART_ACTIVE_FLAGS_BNEG] && -+ /* It may be that one of these conjuncts turns out to be always -+ true. We test both anyway, to be defensive. */ -+ y != left->y0 && y < left->y1) -+ { -+ d = x_min * left->a + y * left->b + left->c; -+ if (d < EPSILON_A) -+ { -+ new_x = art_svp_intersect_break (ctx, left, x_min, y, -+ ART_BREAK_LEFT); -+ if (new_x > x_max) -+ { -+ x_max = new_x; -+ right_live = (right != NULL); -+ } -+ else if (new_x < x_min) -+ x_min = new_x; -+ left = left->left; -+ left_live = (left != NULL); -+ } -+ else -+ left_live = ART_FALSE; -+ } -+ else -+ left_live = ART_FALSE; -+ } -+ else if (right_live) -+ { -+ if (x >= right->x[(right->flags & ART_ACTIVE_FLAGS_BNEG) ^ 1] && -+ /* It may be that one of these conjuncts turns out to be always -+ true. We test both anyway, to be defensive. */ -+ y != right->y0 && y < right->y1) -+ { -+ d = x_max * right->a + y * right->b + right->c; -+ if (d > -EPSILON_A) -+ { -+ new_x = art_svp_intersect_break (ctx, right, x_max, y, -+ ART_BREAK_RIGHT); -+ if (new_x < x_min) -+ { -+ x_min = new_x; -+ left_live = (left != NULL); -+ } -+ else if (new_x >= x_max) -+ x_max = new_x; -+ right = right->right; -+ right_live = (right != NULL); -+ } -+ else -+ right_live = ART_FALSE; -+ } -+ else -+ right_live = ART_FALSE; -+ } -+ } -+ -+ /* Ascending order is guaranteed by break_flags. Thus, we don't need -+ to actually fix up non-ascending pairs. */ -+ -+ /* Now, (left, right) defines an interval of segments broken. Sort -+ into ascending x order. */ -+ test = left == NULL ? ctx->active_head : left->right; -+ result = left; -+ if (test != NULL && test != right) -+ { -+ if (y == test->y0) -+ x_test = test->x[0]; -+ else /* assert y == test->y1, I think */ -+ x_test = test->x[1]; -+ for (;;) -+ { -+ if (x_test <= x) -+ result = test; -+ test = test->right; -+ if (test == right) -+ break; -+ new_x = x_test; -+ if (new_x < x_test) -+ { -+ art_warn ("art_svp_intersect_add_point: non-ascending x\n"); -+ } -+ x_test = new_x; -+ } -+ } -+ return result; -+} -+ -+static void -+art_svp_intersect_swap_active (ArtIntersectCtx *ctx, -+ ArtActiveSeg *left_seg, ArtActiveSeg *right_seg) -+{ -+ right_seg->left = left_seg->left; -+ if (right_seg->left != NULL) -+ right_seg->left->right = right_seg; -+ else -+ ctx->active_head = right_seg; -+ left_seg->right = right_seg->right; -+ if (left_seg->right != NULL) -+ left_seg->right->left = left_seg; -+ left_seg->left = right_seg; -+ right_seg->right = left_seg; -+} -+ -+/** -+ * art_svp_intersect_test_cross: Test crossing of a pair of active segments. -+ * @ctx: Intersector context. -+ * @left_seg: Left segment of the pair. -+ * @right_seg: Right segment of the pair. -+ * @break_flags: Flags indicating whether to break neighbors. -+ * -+ * Tests crossing of @left_seg and @right_seg. If there is a crossing, -+ * inserts the intersection point into both segments. -+ * -+ * Return value: True if the intersection took place at the current -+ * scan line, indicating further iteration is needed. -+ **/ -+static art_boolean -+art_svp_intersect_test_cross (ArtIntersectCtx *ctx, -+ ArtActiveSeg *left_seg, ArtActiveSeg *right_seg, -+ ArtBreakFlags break_flags) -+{ -+ double left_x0, left_y0, left_x1; -+ double left_y1 = left_seg->y1; -+ double right_y1 = right_seg->y1; -+ double d; -+ -+ const ArtSVPSeg *in_seg; -+ int in_curs; -+ double d0, d1, t; -+ double x, y; /* intersection point */ -+ -+#ifdef VERBOSE -+ static int count = 0; -+ -+ art_dprint ("art_svp_intersect_test_cross %lx <-> %lx: count=%d\n", -+ (unsigned long)left_seg, (unsigned long)right_seg, count++); -+#endif -+ -+ if (left_seg->y0 == right_seg->y0 && left_seg->x[0] == right_seg->x[0]) -+ { -+ /* Top points of left and right segments coincide. This case -+ feels like a bit of duplication - we may want to merge it -+ with the cases below. However, this way, we're sure that this -+ logic makes only localized changes. */ -+ -+ if (left_y1 < right_y1) -+ { -+ /* Test left (x1, y1) against right segment */ -+ double left_x1 = left_seg->x[1]; -+ -+ if (left_x1 < -+ right_seg->x[(right_seg->flags & ART_ACTIVE_FLAGS_BNEG) ^ 1] || -+ left_y1 == right_seg->y0) -+ return ART_FALSE; -+ d = left_x1 * right_seg->a + left_y1 * right_seg->b + right_seg->c; -+ if (d < -EPSILON_A) -+ return ART_FALSE; -+ else if (d < EPSILON_A) -+ { -+ /* I'm unsure about the break flags here. */ -+ double right_x1 = art_svp_intersect_break (ctx, right_seg, -+ left_x1, left_y1, -+ ART_BREAK_RIGHT); -+ if (left_x1 <= right_x1) -+ return ART_FALSE; -+ } -+ } -+ else if (left_y1 > right_y1) -+ { -+ /* Test right (x1, y1) against left segment */ -+ double right_x1 = right_seg->x[1]; -+ -+ if (right_x1 > left_seg->x[left_seg->flags & ART_ACTIVE_FLAGS_BNEG] || -+ right_y1 == left_seg->y0) -+ return ART_FALSE; -+ d = right_x1 * left_seg->a + right_y1 * left_seg->b + left_seg->c; -+ if (d > EPSILON_A) -+ return ART_FALSE; -+ else if (d > -EPSILON_A) -+ { -+ /* See above regarding break flags. */ -+ double left_x1 = art_svp_intersect_break (ctx, left_seg, -+ right_x1, right_y1, -+ ART_BREAK_LEFT); -+ if (left_x1 <= right_x1) -+ return ART_FALSE; -+ } -+ } -+ else /* left_y1 == right_y1 */ -+ { -+ double left_x1 = left_seg->x[1]; -+ double right_x1 = right_seg->x[1]; -+ -+ if (left_x1 <= right_x1) -+ return ART_FALSE; -+ } -+ art_svp_intersect_swap_active (ctx, left_seg, right_seg); -+ return ART_TRUE; -+ } -+ -+ if (left_y1 < right_y1) -+ { -+ /* Test left (x1, y1) against right segment */ -+ double left_x1 = left_seg->x[1]; -+ -+ if (left_x1 < -+ right_seg->x[(right_seg->flags & ART_ACTIVE_FLAGS_BNEG) ^ 1] || -+ left_y1 == right_seg->y0) -+ return ART_FALSE; -+ d = left_x1 * right_seg->a + left_y1 * right_seg->b + right_seg->c; -+ if (d < -EPSILON_A) -+ return ART_FALSE; -+ else if (d < EPSILON_A) -+ { -+ double right_x1 = art_svp_intersect_break (ctx, right_seg, -+ left_x1, left_y1, -+ ART_BREAK_RIGHT); -+ if (left_x1 <= right_x1) -+ return ART_FALSE; -+ } -+ } -+ else if (left_y1 > right_y1) -+ { -+ /* Test right (x1, y1) against left segment */ -+ double right_x1 = right_seg->x[1]; -+ -+ if (right_x1 > left_seg->x[left_seg->flags & ART_ACTIVE_FLAGS_BNEG] || -+ right_y1 == left_seg->y0) -+ return ART_FALSE; -+ d = right_x1 * left_seg->a + right_y1 * left_seg->b + left_seg->c; -+ if (d > EPSILON_A) -+ return ART_FALSE; -+ else if (d > -EPSILON_A) -+ { -+ double left_x1 = art_svp_intersect_break (ctx, left_seg, -+ right_x1, right_y1, -+ ART_BREAK_LEFT); -+ if (left_x1 <= right_x1) -+ return ART_FALSE; -+ } -+ } -+ else /* left_y1 == right_y1 */ -+ { -+ double left_x1 = left_seg->x[1]; -+ double right_x1 = right_seg->x[1]; -+ -+ if (left_x1 <= right_x1) -+ return ART_FALSE; -+ } -+ -+ /* The segments cross. Find the intersection point. */ -+ -+ in_seg = left_seg->in_seg; -+ in_curs = left_seg->in_curs; -+ left_x0 = in_seg->points[in_curs - 1].x; -+ left_y0 = in_seg->points[in_curs - 1].y; -+ left_x1 = in_seg->points[in_curs].x; -+ left_y1 = in_seg->points[in_curs].y; -+ d0 = left_x0 * right_seg->a + left_y0 * right_seg->b + right_seg->c; -+ d1 = left_x1 * right_seg->a + left_y1 * right_seg->b + right_seg->c; -+ if (d0 == d1) -+ { -+ x = left_x0; -+ y = left_y0; -+ } -+ else -+ { -+ /* Is this division always safe? It could possibly overflow. */ -+ t = d0 / (d0 - d1); -+ if (t <= 0) -+ { -+ x = left_x0; -+ y = left_y0; -+ } -+ else if (t >= 1) -+ { -+ x = left_x1; -+ y = left_y1; -+ } -+ else -+ { -+ x = left_x0 + t * (left_x1 - left_x0); -+ y = left_y0 + t * (left_y1 - left_y0); -+ } -+ } -+ -+ /* Make sure intersection point is within bounds of right seg. */ -+ if (y < right_seg->y0) -+ { -+ x = right_seg->x[0]; -+ y = right_seg->y0; -+ } -+ else if (y > right_seg->y1) -+ { -+ x = right_seg->x[1]; -+ y = right_seg->y1; -+ } -+ else if (x < right_seg->x[(right_seg->flags & ART_ACTIVE_FLAGS_BNEG) ^ 1]) -+ x = right_seg->x[(right_seg->flags & ART_ACTIVE_FLAGS_BNEG) ^ 1]; -+ else if (x > right_seg->x[right_seg->flags & ART_ACTIVE_FLAGS_BNEG]) -+ x = right_seg->x[right_seg->flags & ART_ACTIVE_FLAGS_BNEG]; -+ -+ if (y == left_seg->y0) -+ { -+ if (y != right_seg->y0) -+ { -+#ifdef VERBOSE -+ art_dprint ("art_svp_intersect_test_cross: intersection (%g, %g) matches former y0 of %lx, %lx\n", -+ x, y, (unsigned long)left_seg, (unsigned long)right_seg); -+#endif -+ art_svp_intersect_push_pt (ctx, right_seg, x, y); -+ if ((break_flags & ART_BREAK_RIGHT) && right_seg->right != NULL) -+ art_svp_intersect_add_point (ctx, x, y, right_seg->right, -+ break_flags); -+ } -+ else -+ { -+ /* Intersection takes place at current scan line; process -+ immediately rather than queueing intersection point into -+ priq. */ -+ ArtActiveSeg *winner, *loser; -+ -+ /* Choose "most vertical" segement */ -+ if (left_seg->a > right_seg->a) -+ { -+ winner = left_seg; -+ loser = right_seg; -+ } -+ else -+ { -+ winner = right_seg; -+ loser = left_seg; -+ } -+ -+ loser->x[0] = winner->x[0]; -+ loser->horiz_x = loser->x[0]; -+ loser->horiz_delta_wind += loser->delta_wind; -+ winner->horiz_delta_wind -= loser->delta_wind; -+ -+ art_svp_intersect_swap_active (ctx, left_seg, right_seg); -+ return ART_TRUE; -+ } -+ } -+ else if (y == right_seg->y0) -+ { -+#ifdef VERBOSE -+ art_dprint ("*** art_svp_intersect_test_cross: intersection (%g, %g) matches latter y0 of %lx, %lx\n", -+ x, y, (unsigned long)left_seg, (unsigned long)right_seg); -+#endif -+ art_svp_intersect_push_pt (ctx, left_seg, x, y); -+ if ((break_flags & ART_BREAK_LEFT) && left_seg->left != NULL) -+ art_svp_intersect_add_point (ctx, x, y, left_seg->left, -+ break_flags); -+ } -+ else -+ { -+#ifdef VERBOSE -+ art_dprint ("Inserting (%g, %g) into %lx, %lx\n", -+ x, y, (unsigned long)left_seg, (unsigned long)right_seg); -+#endif -+ /* Insert the intersection point into both segments. */ -+ art_svp_intersect_push_pt (ctx, left_seg, x, y); -+ art_svp_intersect_push_pt (ctx, right_seg, x, y); -+ if ((break_flags & ART_BREAK_LEFT) && left_seg->left != NULL) -+ art_svp_intersect_add_point (ctx, x, y, left_seg->left, break_flags); -+ if ((break_flags & ART_BREAK_RIGHT) && right_seg->right != NULL) -+ art_svp_intersect_add_point (ctx, x, y, right_seg->right, break_flags); -+ } -+ return ART_FALSE; -+} -+ -+/** -+ * art_svp_intersect_active_delete: Delete segment from active list. -+ * @ctx: Intersection context. -+ * @seg: Segment to delete. -+ * -+ * Deletes @seg from the active list. -+ **/ -+static /* todo inline */ void -+art_svp_intersect_active_delete (ArtIntersectCtx *ctx, ArtActiveSeg *seg) -+{ -+ ArtActiveSeg *left = seg->left, *right = seg->right; -+ -+ if (left != NULL) -+ left->right = right; -+ else -+ ctx->active_head = right; -+ if (right != NULL) -+ right->left = left; -+} -+ -+/** -+ * art_svp_intersect_active_free: Free an active segment. -+ * @seg: Segment to delete. -+ * -+ * Frees @seg. -+ **/ -+static /* todo inline */ void -+art_svp_intersect_active_free (ArtActiveSeg *seg) -+{ -+ art_free (seg->stack); -+#ifdef VERBOSE -+ art_dprint ("Freeing %lx\n", (unsigned long) seg); -+#endif -+ art_free (seg); -+} -+ -+/** -+ * art_svp_intersect_insert_cross: Test crossings of newly inserted line. -+ * -+ * Tests @seg against its left and right neighbors for intersections. -+ * Precondition: the line in @seg is not purely horizontal. -+ **/ -+static void -+art_svp_intersect_insert_cross (ArtIntersectCtx *ctx, -+ ArtActiveSeg *seg) -+{ -+ ArtActiveSeg *left = seg, *right = seg; -+ -+ for (;;) -+ { -+ if (left != NULL) -+ { -+ ArtActiveSeg *leftc; -+ -+ for (leftc = left->left; leftc != NULL; leftc = leftc->left) -+ if (!(leftc->flags & ART_ACTIVE_FLAGS_DEL)) -+ break; -+ if (leftc != NULL && -+ art_svp_intersect_test_cross (ctx, leftc, left, -+ ART_BREAK_LEFT)) -+ { -+ if (left == right || right == NULL) -+ right = left->right; -+ } -+ else -+ { -+ left = NULL; -+ } -+ } -+ else if (right != NULL && right->right != NULL) -+ { -+ ArtActiveSeg *rightc; -+ -+ for (rightc = right->right; rightc != NULL; rightc = rightc->right) -+ if (!(rightc->flags & ART_ACTIVE_FLAGS_DEL)) -+ break; -+ if (rightc != NULL && -+ art_svp_intersect_test_cross (ctx, right, rightc, -+ ART_BREAK_RIGHT)) -+ { -+ if (left == right || left == NULL) -+ left = right->left; -+ } -+ else -+ { -+ right = NULL; -+ } -+ } -+ else -+ break; -+ } -+} -+ -+/** -+ * art_svp_intersect_horiz: Add horizontal line segment. -+ * @ctx: Intersector context. -+ * @seg: Segment on which to add horizontal line. -+ * @x0: Old x position. -+ * @x1: New x position. -+ * -+ * Adds a horizontal line from @x0 to @x1, and updates the current -+ * location of @seg to @x1. -+ **/ -+static void -+art_svp_intersect_horiz (ArtIntersectCtx *ctx, ArtActiveSeg *seg, -+ double x0, double x1) -+{ -+ ArtActiveSeg *hs; -+ -+ if (x0 == x1) -+ return; -+ -+ hs = art_new (ArtActiveSeg, 1); -+ -+ hs->flags = ART_ACTIVE_FLAGS_DEL | (seg->flags & ART_ACTIVE_FLAGS_OUT); -+ if (seg->flags & ART_ACTIVE_FLAGS_OUT) -+ { -+ ArtSvpWriter *swr = ctx->out; -+ -+ swr->add_point (swr, seg->seg_id, x0, ctx->y); -+ } -+ hs->seg_id = seg->seg_id; -+ hs->horiz_x = x0; -+ hs->horiz_delta_wind = seg->delta_wind; -+ hs->stack = NULL; -+ -+ /* Ideally, the (a, b, c) values will never be read. However, there -+ are probably some tests remaining that don't check for _DEL -+ before evaluating the line equation. For those, these -+ initializations will at least prevent a UMR of the values, which -+ can crash on some platforms. */ -+ hs->a = 0.0; -+ hs->b = 0.0; -+ hs->c = 0.0; -+ -+ seg->horiz_delta_wind -= seg->delta_wind; -+ -+ art_svp_intersect_add_horiz (ctx, hs); -+ -+ if (x0 > x1) -+ { -+ ArtActiveSeg *left; -+ art_boolean first = ART_TRUE; -+ -+ for (left = seg->left; left != NULL; left = seg->left) -+ { -+ int left_bneg = left->flags & ART_ACTIVE_FLAGS_BNEG; -+ -+ if (left->x[left_bneg] <= x1) -+ break; -+ if (left->x[left_bneg ^ 1] <= x1 && -+ x1 * left->a + ctx->y * left->b + left->c >= 0) -+ break; -+ if (left->y0 != ctx->y && left->y1 != ctx->y) -+ { -+ art_svp_intersect_break (ctx, left, x1, ctx->y, ART_BREAK_LEFT); -+ } -+#ifdef VERBOSE -+ art_dprint ("x0=%g > x1=%g, swapping %lx, %lx\n", -+ x0, x1, (unsigned long)left, (unsigned long)seg); -+#endif -+ art_svp_intersect_swap_active (ctx, left, seg); -+ if (first && left->right != NULL) -+ { -+ art_svp_intersect_test_cross (ctx, left, left->right, -+ ART_BREAK_RIGHT); -+ first = ART_FALSE; -+ } -+ } -+ } -+ else -+ { -+ ArtActiveSeg *right; -+ art_boolean first = ART_TRUE; -+ -+ for (right = seg->right; right != NULL; right = seg->right) -+ { -+ int right_bneg = right->flags & ART_ACTIVE_FLAGS_BNEG; -+ -+ if (right->x[right_bneg ^ 1] >= x1) -+ break; -+ if (right->x[right_bneg] >= x1 && -+ x1 * right->a + ctx->y * right->b + right->c <= 0) -+ break; -+ if (right->y0 != ctx->y && right->y1 != ctx->y) -+ { -+ art_svp_intersect_break (ctx, right, x1, ctx->y, -+ ART_BREAK_LEFT); -+ } -+#ifdef VERBOSE -+ art_dprint ("[right]x0=%g < x1=%g, swapping %lx, %lx\n", -+ x0, x1, (unsigned long)seg, (unsigned long)right); -+#endif -+ art_svp_intersect_swap_active (ctx, seg, right); -+ if (first && right->left != NULL) -+ { -+ art_svp_intersect_test_cross (ctx, right->left, right, -+ ART_BREAK_RIGHT); -+ first = ART_FALSE; -+ } -+ } -+ } -+ -+ seg->x[0] = x1; -+ seg->x[1] = x1; -+ seg->horiz_x = x1; -+ seg->flags &= ~ART_ACTIVE_FLAGS_OUT; -+} -+ -+/** -+ * art_svp_intersect_insert_line: Insert a line into the active list. -+ * @ctx: Intersector context. -+ * @seg: Segment containing line to insert. -+ * -+ * Inserts the line into the intersector context, taking care of any -+ * intersections, and adding the appropriate horizontal points to the -+ * active list. -+ **/ -+static void -+art_svp_intersect_insert_line (ArtIntersectCtx *ctx, ArtActiveSeg *seg) -+{ -+ if (seg->y1 == seg->y0) -+ { -+#ifdef VERBOSE -+ art_dprint ("art_svp_intersect_insert_line: %lx is horizontal\n", -+ (unsigned long)seg); -+#endif -+ art_svp_intersect_horiz (ctx, seg, seg->x[0], seg->x[1]); -+ } -+ else -+ { -+ art_svp_intersect_insert_cross (ctx, seg); -+ art_svp_intersect_add_horiz (ctx, seg); -+ } -+} -+ -+static void -+art_svp_intersect_process_intersection (ArtIntersectCtx *ctx, -+ ArtActiveSeg *seg) -+{ -+ int n_stack = --seg->n_stack; -+ seg->x[1] = seg->stack[n_stack - 1].x; -+ seg->y1 = seg->stack[n_stack - 1].y; -+ seg->x[0] = seg->stack[n_stack].x; -+ seg->y0 = seg->stack[n_stack].y; -+ seg->horiz_x = seg->x[0]; -+ art_svp_intersect_insert_line (ctx, seg); -+} -+ -+static void -+art_svp_intersect_advance_cursor (ArtIntersectCtx *ctx, ArtActiveSeg *seg, -+ ArtPriPoint *pri_pt) -+{ -+ const ArtSVPSeg *in_seg = seg->in_seg; -+ int in_curs = seg->in_curs; -+ ArtSvpWriter *swr = seg->flags & ART_ACTIVE_FLAGS_OUT ? ctx->out : NULL; -+ -+ if (swr != NULL) -+ swr->add_point (swr, seg->seg_id, seg->x[1], seg->y1); -+ if (in_curs + 1 == in_seg->n_points) -+ { -+ ArtActiveSeg *left = seg->left, *right = seg->right; -+ -+#if 0 -+ if (swr != NULL) -+ swr->close_segment (swr, seg->seg_id); -+ seg->flags &= ~ART_ACTIVE_FLAGS_OUT; -+#endif -+ seg->flags |= ART_ACTIVE_FLAGS_DEL; -+ art_svp_intersect_add_horiz (ctx, seg); -+ art_svp_intersect_active_delete (ctx, seg); -+ if (left != NULL && right != NULL) -+ art_svp_intersect_test_cross (ctx, left, right, -+ ART_BREAK_LEFT | ART_BREAK_RIGHT); -+ art_free (pri_pt); -+ } -+ else -+ { -+ seg->horiz_x = seg->x[1]; -+ -+ art_svp_intersect_setup_seg (seg, pri_pt); -+ art_pri_insert (ctx->pq, pri_pt); -+ art_svp_intersect_insert_line (ctx, seg); -+ } -+} -+ -+static void -+art_svp_intersect_add_seg (ArtIntersectCtx *ctx, const ArtSVPSeg *in_seg) -+{ -+ ArtActiveSeg *seg = art_new (ArtActiveSeg, 1); -+ ArtActiveSeg *test; -+ double x0, y0; -+ ArtActiveSeg *beg_range; -+ ArtActiveSeg *last = NULL; -+ ArtActiveSeg *left, *right; -+ ArtPriPoint *pri_pt = art_new (ArtPriPoint, 1); -+ -+ seg->flags = 0; -+ seg->in_seg = in_seg; -+ seg->in_curs = 0; -+ -+ seg->n_stack_max = 4; -+ seg->stack = art_new (ArtPoint, seg->n_stack_max); -+ -+ seg->horiz_delta_wind = 0; -+ -+ seg->wind_left = 0; -+ -+ pri_pt->user_data = seg; -+ art_svp_intersect_setup_seg (seg, pri_pt); -+ art_pri_insert (ctx->pq, pri_pt); -+ -+ /* Find insertion place for new segment */ -+ /* This is currently a left-to-right scan, but should be replaced -+ with a binary search as soon as it's validated. */ -+ -+ x0 = in_seg->points[0].x; -+ y0 = in_seg->points[0].y; -+ beg_range = NULL; -+ for (test = ctx->active_head; test != NULL; test = test->right) -+ { -+ double d; -+ int test_bneg = test->flags & ART_ACTIVE_FLAGS_BNEG; -+ -+ if (x0 < test->x[test_bneg]) -+ { -+ if (x0 < test->x[test_bneg ^ 1]) -+ break; -+ d = x0 * test->a + y0 * test->b + test->c; -+ if (d < 0) -+ break; -+ } -+ last = test; -+ } -+ -+ left = art_svp_intersect_add_point (ctx, x0, y0, last, ART_BREAK_LEFT | ART_BREAK_RIGHT); -+ seg->left = left; -+ if (left == NULL) -+ { -+ right = ctx->active_head; -+ ctx->active_head = seg; -+ } -+ else -+ { -+ right = left->right; -+ left->right = seg; -+ } -+ seg->right = right; -+ if (right != NULL) -+ right->left = seg; -+ -+ seg->delta_wind = in_seg->dir ? 1 : -1; -+ seg->horiz_x = x0; -+ -+ art_svp_intersect_insert_line (ctx, seg); -+} -+ -+#ifdef SANITYCHECK -+static void -+art_svp_intersect_sanitycheck_winding (ArtIntersectCtx *ctx) -+{ -+#if 0 -+ /* At this point, we seem to be getting false positives, so it's -+ turned off for now. */ -+ -+ ArtActiveSeg *seg; -+ int winding_number = 0; -+ -+ for (seg = ctx->active_head; seg != NULL; seg = seg->right) -+ { -+ /* Check winding number consistency. */ -+ if (seg->flags & ART_ACTIVE_FLAGS_OUT) -+ { -+ if (winding_number != seg->wind_left) -+ art_warn ("*** art_svp_intersect_sanitycheck_winding: seg %lx has wind_left of %d, expected %d\n", -+ (unsigned long) seg, seg->wind_left, winding_number); -+ winding_number = seg->wind_left + seg->delta_wind; -+ } -+ } -+ if (winding_number != 0) -+ art_warn ("*** art_svp_intersect_sanitycheck_winding: non-balanced winding number %d\n", -+ winding_number); -+#endif -+} -+#endif -+ -+/** -+ * art_svp_intersect_horiz_commit: Commit points in horiz list to output. -+ * @ctx: Intersection context. -+ * -+ * The main function of the horizontal commit is to output new -+ * points to the output writer. -+ * -+ * This "commit" pass is also where winding numbers are assigned, -+ * because doing it here provides much greater tolerance for inputs -+ * which are not in strict SVP order. -+ * -+ * Each cluster in the horiz_list contains both segments that are in -+ * the active list (ART_ACTIVE_FLAGS_DEL is false) and that are not, -+ * and are scheduled to be deleted (ART_ACTIVE_FLAGS_DEL is true). We -+ * need to deal with both. -+ **/ -+static void -+art_svp_intersect_horiz_commit (ArtIntersectCtx *ctx) -+{ -+ ArtActiveSeg *seg; -+ int winding_number = 0; /* initialization just to avoid warning */ -+ int horiz_wind = 0; -+ double last_x = 0; /* initialization just to avoid warning */ -+ -+#ifdef VERBOSE -+ art_dprint ("art_svp_intersect_horiz_commit: y=%g\n", ctx->y); -+ for (seg = ctx->horiz_first; seg != NULL; seg = seg->horiz_right) -+ art_dprint (" %lx: %g %+d\n", -+ (unsigned long)seg, seg->horiz_x, seg->horiz_delta_wind); -+#endif -+ -+ /* Output points to svp writer. */ -+ for (seg = ctx->horiz_first; seg != NULL;) -+ { -+ /* Find a cluster with common horiz_x, */ -+ ArtActiveSeg *curs; -+ double x = seg->horiz_x; -+ -+ /* Generate any horizontal segments. */ -+ if (horiz_wind != 0) -+ { -+ ArtSvpWriter *swr = ctx->out; -+ int seg_id; -+ -+ seg_id = swr->add_segment (swr, winding_number, horiz_wind, -+ last_x, ctx->y); -+ swr->add_point (swr, seg_id, x, ctx->y); -+ swr->close_segment (swr, seg_id); -+ } -+ -+ /* Find first active segment in cluster. */ -+ -+ for (curs = seg; curs != NULL && curs->horiz_x == x; -+ curs = curs->horiz_right) -+ if (!(curs->flags & ART_ACTIVE_FLAGS_DEL)) -+ break; -+ -+ if (curs != NULL && curs->horiz_x == x) -+ { -+ /* There exists at least one active segment in this cluster. */ -+ -+ /* Find beginning of cluster. */ -+ for (; curs->left != NULL; curs = curs->left) -+ if (curs->left->horiz_x != x) -+ break; -+ -+ if (curs->left != NULL) -+ winding_number = curs->left->wind_left + curs->left->delta_wind; -+ else -+ winding_number = 0; -+ -+ do -+ { -+#ifdef VERBOSE -+ art_dprint (" curs %lx: winding_number = %d += %d\n", -+ (unsigned long)curs, winding_number, curs->delta_wind); -+#endif -+ if (!(curs->flags & ART_ACTIVE_FLAGS_OUT) || -+ curs->wind_left != winding_number) -+ { -+ ArtSvpWriter *swr = ctx->out; -+ -+ if (curs->flags & ART_ACTIVE_FLAGS_OUT) -+ { -+ swr->add_point (swr, curs->seg_id, -+ curs->horiz_x, ctx->y); -+ swr->close_segment (swr, curs->seg_id); -+ } -+ -+ curs->seg_id = swr->add_segment (swr, winding_number, -+ curs->delta_wind, -+ x, ctx->y); -+ curs->flags |= ART_ACTIVE_FLAGS_OUT; -+ } -+ curs->wind_left = winding_number; -+ winding_number += curs->delta_wind; -+ curs = curs->right; -+ } -+ while (curs != NULL && curs->horiz_x == x); -+ } -+ -+ /* Skip past cluster. */ -+ do -+ { -+ ArtActiveSeg *next = seg->horiz_right; -+ -+ seg->flags &= ~ART_ACTIVE_FLAGS_IN_HORIZ; -+ horiz_wind += seg->horiz_delta_wind; -+ seg->horiz_delta_wind = 0; -+ if (seg->flags & ART_ACTIVE_FLAGS_DEL) -+ { -+ if (seg->flags & ART_ACTIVE_FLAGS_OUT) -+ { -+ ArtSvpWriter *swr = ctx->out; -+ swr->close_segment (swr, seg->seg_id); -+ } -+ art_svp_intersect_active_free (seg); -+ } -+ seg = next; -+ } -+ while (seg != NULL && seg->horiz_x == x); -+ -+ last_x = x; -+ } -+ ctx->horiz_first = NULL; -+ ctx->horiz_last = NULL; -+#ifdef SANITYCHECK -+ art_svp_intersect_sanitycheck_winding (ctx); -+#endif -+} -+ -+#ifdef VERBOSE -+static void -+art_svp_intersect_print_active (ArtIntersectCtx *ctx) -+{ -+ ArtActiveSeg *seg; -+ -+ art_dprint ("Active list (y = %g):\n", ctx->y); -+ for (seg = ctx->active_head; seg != NULL; seg = seg->right) -+ { -+ art_dprint (" %lx: (%g, %g)-(%g, %g), (a, b, c) = (%g, %g, %g)\n", -+ (unsigned long)seg, -+ seg->x[0], seg->y0, seg->x[1], seg->y1, -+ seg->a, seg->b, seg->c); -+ } -+} -+#endif -+ -+#ifdef SANITYCHECK -+static void -+art_svp_intersect_sanitycheck (ArtIntersectCtx *ctx) -+{ -+ ArtActiveSeg *seg; -+ ArtActiveSeg *last = NULL; -+ double d; -+ -+ for (seg = ctx->active_head; seg != NULL; seg = seg->right) -+ { -+ if (seg->left != last) -+ { -+ art_warn ("*** art_svp_intersect_sanitycheck: last=%lx, seg->left=%lx\n", -+ (unsigned long)last, (unsigned long)seg->left); -+ } -+ if (last != NULL) -+ { -+ /* pairwise compare with previous seg */ -+ -+ /* First the top. */ -+ if (last->y0 < seg->y0) -+ { -+ } -+ else -+ { -+ } -+ -+ /* Then the bottom. */ -+ if (last->y1 < seg->y1) -+ { -+ if (!((last->x[1] < -+ seg->x[(seg->flags & ART_ACTIVE_FLAGS_BNEG) ^ 1]) || -+ last->y1 == seg->y0)) -+ { -+ d = last->x[1] * seg->a + last->y1 * seg->b + seg->c; -+ if (d >= -EPSILON_A) -+ art_warn ("*** bottom (%g, %g) of %lx is not clear of %lx to right (d = %g)\n", -+ last->x[1], last->y1, (unsigned long) last, -+ (unsigned long) seg, d); -+ } -+ } -+ else if (last->y1 > seg->y1) -+ -+ { -+ if (!((seg->x[1] > -+ last->x[last->flags & ART_ACTIVE_FLAGS_BNEG]) || -+ seg->y1 == last->y0)) -+ { -+ d = seg->x[1] * last->a + seg->y1 * last->b + last->c; -+ if (d <= EPSILON_A) -+ art_warn ("*** bottom (%g, %g) of %lx is not clear of %lx to left (d = %g)\n", -+ seg->x[1], seg->y1, (unsigned long) seg, -+ (unsigned long) last, d); -+ } -+ } -+ else -+ { -+ if (last->x[1] > seg->x[1]) -+ art_warn ("*** bottoms (%g, %g) of %lx and (%g, %g) of %lx out of order\n", -+ last->x[1], last->y1, (unsigned long)last, -+ seg->x[1], seg->y1, (unsigned long)seg); -+ } -+ } -+ last = seg; -+ } -+} -+#endif -+ -+void -+art_svp_intersector (const ArtSVP *in, ArtSvpWriter *out) -+{ -+ ArtIntersectCtx *ctx; -+ ArtPriQ *pq; -+ ArtPriPoint *first_point; -+#ifdef VERBOSE -+ int count = 0; -+#endif -+ -+ if (in->n_segs == 0) -+ return; -+ -+ ctx = art_new (ArtIntersectCtx, 1); -+ ctx->in = in; -+ ctx->out = out; -+ pq = art_pri_new (); -+ ctx->pq = pq; -+ -+ ctx->active_head = NULL; -+ -+ ctx->horiz_first = NULL; -+ ctx->horiz_last = NULL; -+ -+ ctx->in_curs = 0; -+ first_point = art_new (ArtPriPoint, 1); -+ first_point->x = in->segs[0].points[0].x; -+ first_point->y = in->segs[0].points[0].y; -+ first_point->user_data = NULL; -+ ctx->y = first_point->y; -+ art_pri_insert (pq, first_point); -+ -+ while (!art_pri_empty (pq)) -+ { -+ ArtPriPoint *pri_point = art_pri_choose (pq); -+ ArtActiveSeg *seg = (ArtActiveSeg *)pri_point->user_data; -+ -+#ifdef VERBOSE -+ art_dprint ("\nIntersector step %d\n", count++); -+ art_svp_intersect_print_active (ctx); -+ art_dprint ("priq choose (%g, %g) %lx\n", pri_point->x, pri_point->y, -+ (unsigned long)pri_point->user_data); -+#endif -+#ifdef SANITYCHECK -+ art_svp_intersect_sanitycheck(ctx); -+#endif -+ -+ if (ctx->y != pri_point->y) -+ { -+ art_svp_intersect_horiz_commit (ctx); -+ ctx->y = pri_point->y; -+ } -+ -+ if (seg == NULL) -+ { -+ /* Insert new segment from input */ -+ const ArtSVPSeg *in_seg = &in->segs[ctx->in_curs++]; -+ art_svp_intersect_add_seg (ctx, in_seg); -+ if (ctx->in_curs < in->n_segs) -+ { -+ const ArtSVPSeg *next_seg = &in->segs[ctx->in_curs]; -+ pri_point->x = next_seg->points[0].x; -+ pri_point->y = next_seg->points[0].y; -+ /* user_data is already NULL */ -+ art_pri_insert (pq, pri_point); -+ } -+ else -+ art_free (pri_point); -+ } -+ else -+ { -+ int n_stack = seg->n_stack; -+ -+ if (n_stack > 1) -+ { -+ art_svp_intersect_process_intersection (ctx, seg); -+ art_free (pri_point); -+ } -+ else -+ { -+ art_svp_intersect_advance_cursor (ctx, seg, pri_point); -+ } -+ } -+ } -+ -+ art_svp_intersect_horiz_commit (ctx); -+ -+ art_pri_free (pq); -+ art_free (ctx); -+} -+ -+#endif /* not TEST_PRIQ */ -diff -uNr /oocvs/OOO_STABLE_1-backup/external/gpc/art_svp_intersect.h external/gpc/art_svp_intersect.h ---- /oocvs/OOO_STABLE_1-backup/external/gpc/art_svp_intersect.h Wed Dec 31 18:00:00 1969 -+++ external/gpc/art_svp_intersect.h Fri Sep 20 21:42:19 2002 -@@ -0,0 +1,66 @@ -+/* Libart_LGPL - library of basic graphic primitives -+ * Copyright (C) 2001 Raph Levien -+ * -+ * This library is free software; you can redistribute it and/or -+ * modify it under the terms of the GNU Library General Public -+ * License as published by the Free Software Foundation; either -+ * version 2 of the License, or (at your option) any later version. -+ * -+ * This library is distributed in the hope that it will be useful, -+ * but WITHOUT ANY WARRANTY; without even the implied warranty of -+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU -+ * Library General Public License for more details. -+ * -+ * You should have received a copy of the GNU Library General Public -+ * License along with this library; if not, write to the -+ * Free Software Foundation, Inc., 59 Temple Place - Suite 330, -+ * Boston, MA 02111-1307, USA. -+ */ -+ -+#ifndef __ART_SVP_INTERSECT_H__ -+#define __ART_SVP_INTERSECT_H__ -+ -+/* The funky new SVP intersector. */ -+ -+#include "art_svp.h" -+ -+#ifdef __cplusplus -+extern "C" { -+#endif /* __cplusplus */ -+ -+#ifndef ART_WIND_RULE_DEFINED -+#define ART_WIND_RULE_DEFINED -+typedef enum { -+ ART_WIND_RULE_NONZERO, -+ ART_WIND_RULE_INTERSECT, -+ ART_WIND_RULE_ODDEVEN, -+ ART_WIND_RULE_POSITIVE -+} ArtWindRule; -+#endif -+ -+typedef struct _ArtSvpWriter ArtSvpWriter; -+ -+struct _ArtSvpWriter { -+ int (*add_segment) (ArtSvpWriter *self, int wind_left, int delta_wind, -+ double x, double y); -+ void (*add_point) (ArtSvpWriter *self, int seg_id, double x, double y); -+ void (*close_segment) (ArtSvpWriter *self, int seg_id); -+}; -+ -+ArtSvpWriter * -+art_svp_writer_rewind_new (ArtWindRule rule); -+ -+ArtSVP * -+art_svp_writer_rewind_reap (ArtSvpWriter *self); -+ -+int -+art_svp_seg_compare (const void *s1, const void *s2); -+ -+void -+art_svp_intersector (const ArtSVP *in, ArtSvpWriter *out); -+ -+#ifdef __cplusplus -+} -+#endif /* __cplusplus */ -+ -+#endif /* __ART_SVP_INTERSECT_H__ */ -diff -uNr /oocvs/OOO_STABLE_1-backup/external/gpc/art_svp_ops.c external/gpc/art_svp_ops.c ---- /oocvs/OOO_STABLE_1-backup/external/gpc/art_svp_ops.c Wed Dec 31 18:00:00 1969 -+++ external/gpc/art_svp_ops.c Wed Oct 9 20:16:52 2002 -@@ -0,0 +1,398 @@ -+/* Libart_LGPL - library of basic graphic primitives -+ * Copyright (C) 1998-2000 Raph Levien -+ * -+ * This library is free software; you can redistribute it and/or -+ * modify it under the terms of the GNU Library General Public -+ * License as published by the Free Software Foundation; either -+ * version 2 of the License, or (at your option) any later version. -+ * -+ * This library is distributed in the hope that it will be useful, -+ * but WITHOUT ANY WARRANTY; without even the implied warranty of -+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU -+ * Library General Public License for more details. -+ * -+ * You should have received a copy of the GNU Library General Public -+ * License along with this library; if not, write to the -+ * Free Software Foundation, Inc., 59 Temple Place - Suite 330, -+ * Boston, MA 02111-1307, USA. -+ */ -+ -+#define noVERBOSE -+ -+/* Vector path set operations, over sorted vpaths. */ -+ -+#include "art_svp_ops.h" -+#include "art_misc.h" -+#include "art_svp.h" -+#include "art_vpath.h" -+#include "art_svp_vpath.h" -+#include "art_svp.h" -+#ifdef ART_USE_NEW_INTERSECTOR -+#include "art_svp_intersect.h" -+#else -+#include "art_svp_wind.h" -+#endif -+#include "art_vpath_svp.h" -+ -+/* Merge the segments of the two svp's. The resulting svp will share -+ segments with args passed in, so be super-careful with the -+ allocation. */ -+/** -+ * art_svp_merge: Merge the segments of two svp's. -+ * @svp1: One svp to merge. -+ * @svp2: The other svp to merge. -+ * -+ * Merges the segments of two SVP's into a new one. The resulting -+ * #ArtSVP data structure will share the segments of the argument -+ * svp's, so it is probably a good idea to free it shallowly, -+ * especially if the arguments will be freed with art_svp_free(). -+ * -+ * Return value: The merged #ArtSVP. -+ **/ -+static ArtSVP * -+art_svp_merge (const ArtSVP *svp1, const ArtSVP *svp2) -+{ -+ ArtSVP *svp_new; -+ int ix; -+ int ix1, ix2; -+ -+ svp_new = (ArtSVP *)art_alloc (sizeof(ArtSVP) + -+ (svp1->n_segs + svp2->n_segs - 1) * -+ sizeof(ArtSVPSeg)); -+ ix1 = 0; -+ ix2 = 0; -+ for (ix = 0; ix < svp1->n_segs + svp2->n_segs; ix++) -+ { -+ if (ix1 < svp1->n_segs && -+ (ix2 == svp2->n_segs || -+ art_svp_seg_compare (&svp1->segs[ix1], &svp2->segs[ix2]) < 1)) -+ svp_new->segs[ix] = svp1->segs[ix1++]; -+ else -+ svp_new->segs[ix] = svp2->segs[ix2++]; -+ } -+ -+ svp_new->n_segs = ix; -+ return svp_new; -+} -+ -+#ifdef VERBOSE -+ -+#define XOFF 50 -+#define YOFF 700 -+ -+static void -+print_ps_vpath (ArtVpath *vpath) -+{ -+ int i; -+ -+ printf ("gsave %d %d translate 1 -1 scale\n", XOFF, YOFF); -+ for (i = 0; vpath[i].code != ART_END; i++) -+ { -+ switch (vpath[i].code) -+ { -+ case ART_MOVETO: -+ printf ("%g %g moveto\n", vpath[i].x, vpath[i].y); -+ break; -+ case ART_LINETO: -+ printf ("%g %g lineto\n", vpath[i].x, vpath[i].y); -+ break; -+ default: -+ break; -+ } -+ } -+ printf ("stroke grestore showpage\n"); -+} -+ -+#define DELT 4 -+ -+static void -+print_ps_svp (ArtSVP *vpath) -+{ -+ int i, j; -+ -+ printf ("%% begin\n"); -+ for (i = 0; i < vpath->n_segs; i++) -+ { -+ printf ("%g setgray\n", vpath->segs[i].dir ? 0.7 : 0); -+ for (j = 0; j < vpath->segs[i].n_points; j++) -+ { -+ printf ("%g %g %s\n", -+ XOFF + vpath->segs[i].points[j].x, -+ YOFF - vpath->segs[i].points[j].y, -+ j ? "lineto" : "moveto"); -+ } -+ printf ("%g %g moveto %g %g lineto %g %g lineto %g %g lineto stroke\n", -+ XOFF + vpath->segs[i].points[0].x - DELT, -+ YOFF - DELT - vpath->segs[i].points[0].y, -+ XOFF + vpath->segs[i].points[0].x - DELT, -+ YOFF - vpath->segs[i].points[0].y, -+ XOFF + vpath->segs[i].points[0].x + DELT, -+ YOFF - vpath->segs[i].points[0].y, -+ XOFF + vpath->segs[i].points[0].x + DELT, -+ YOFF - DELT - vpath->segs[i].points[0].y); -+ printf ("%g %g moveto %g %g lineto %g %g lineto %g %g lineto stroke\n", -+ XOFF + vpath->segs[i].points[j - 1].x - DELT, -+ YOFF + DELT - vpath->segs[i].points[j - 1].y, -+ XOFF + vpath->segs[i].points[j - 1].x - DELT, -+ YOFF - vpath->segs[i].points[j - 1].y, -+ XOFF + vpath->segs[i].points[j - 1].x + DELT, -+ YOFF - vpath->segs[i].points[j - 1].y, -+ XOFF + vpath->segs[i].points[j - 1].x + DELT, -+ YOFF + DELT - vpath->segs[i].points[j - 1].y); -+ printf ("stroke\n"); -+ } -+ -+ printf ("showpage\n"); -+} -+#endif -+ -+#ifndef ART_USE_NEW_INTERSECTOR -+static ArtSVP * -+art_svp_merge_perturbed (const ArtSVP *svp1, const ArtSVP *svp2) -+{ -+ ArtVpath *vpath1, *vpath2; -+ ArtVpath *vpath1_p, *vpath2_p; -+ ArtSVP *svp1_p, *svp2_p; -+ ArtSVP *svp_new; -+ -+ vpath1 = art_vpath_from_svp (svp1); -+ vpath1_p = art_vpath_perturb (vpath1); -+ art_free (vpath1); -+ svp1_p = art_svp_from_vpath (vpath1_p); -+ art_free (vpath1_p); -+ -+ vpath2 = art_vpath_from_svp (svp2); -+ vpath2_p = art_vpath_perturb (vpath2); -+ art_free (vpath2); -+ svp2_p = art_svp_from_vpath (vpath2_p); -+ art_free (vpath2_p); -+ -+ svp_new = art_svp_merge (svp1_p, svp2_p); -+#ifdef VERBOSE -+ print_ps_svp (svp1_p); -+ print_ps_svp (svp2_p); -+ print_ps_svp (svp_new); -+#endif -+ art_free (svp1_p); -+ art_free (svp2_p); -+ -+ return svp_new; -+} -+#endif -+ -+/* Compute the union of two vector paths. -+ -+ Status of this routine: -+ -+ Basic correctness: Seems to work. -+ -+ Numerical stability: We cheat (adding random perturbation). Thus, -+ it seems very likely that no numerical stability problems will be -+ seen in practice. -+ -+ Speed: Would be better if we didn't go to unsorted vector path -+ and back to add the perturbation. -+ -+ Precision: The perturbation fuzzes the coordinates slightly. In -+ cases of butting segments, razor thin long holes may appear. -+ -+*/ -+/** -+ * art_svp_union: Compute the union of two sorted vector paths. -+ * @svp1: One sorted vector path. -+ * @svp2: The other sorted vector path. -+ * -+ * Computes the union of the two argument svp's. Given two svp's with -+ * winding numbers of 0 and 1 everywhere, the resulting winding number -+ * will be 1 where either (or both) of the argument svp's has a -+ * winding number 1, 0 otherwise. The result is newly allocated. -+ * -+ * Currently, this routine has accuracy problems pending the -+ * implementation of the new intersector. -+ * -+ * Return value: The union of @svp1 and @svp2. -+ **/ -+ArtSVP * -+art_svp_union (const ArtSVP *svp1, const ArtSVP *svp2) -+{ -+#ifdef ART_USE_NEW_INTERSECTOR -+ ArtSVP *svp3, *svp_new; -+ ArtSvpWriter *swr; -+ -+ svp3 = art_svp_merge (svp1, svp2); -+ swr = art_svp_writer_rewind_new (ART_WIND_RULE_POSITIVE); -+ art_svp_intersector (svp3, swr); -+ svp_new = art_svp_writer_rewind_reap (swr); -+ art_free (svp3); /* shallow free because svp3 contains shared segments */ -+ -+ return svp_new; -+#else -+ ArtSVP *svp3, *svp4, *svp_new; -+ -+ svp3 = art_svp_merge_perturbed (svp1, svp2); -+ svp4 = art_svp_uncross (svp3); -+ art_svp_free (svp3); -+ -+ svp_new = art_svp_rewind_uncrossed (svp4, ART_WIND_RULE_POSITIVE); -+#ifdef VERBOSE -+ print_ps_svp (svp4); -+ print_ps_svp (svp_new); -+#endif -+ art_svp_free (svp4); -+ return svp_new; -+#endif -+} -+ -+/* Compute the intersection of two vector paths. -+ -+ Status of this routine: -+ -+ Basic correctness: Seems to work. -+ -+ Numerical stability: We cheat (adding random perturbation). Thus, -+ it seems very likely that no numerical stability problems will be -+ seen in practice. -+ -+ Speed: Would be better if we didn't go to unsorted vector path -+ and back to add the perturbation. -+ -+ Precision: The perturbation fuzzes the coordinates slightly. In -+ cases of butting segments, razor thin long isolated segments may -+ appear. -+ -+*/ -+ -+/** -+ * art_svp_intersect: Compute the intersection of two sorted vector paths. -+ * @svp1: One sorted vector path. -+ * @svp2: The other sorted vector path. -+ * -+ * Computes the intersection of the two argument svp's. Given two -+ * svp's with winding numbers of 0 and 1 everywhere, the resulting -+ * winding number will be 1 where both of the argument svp's has a -+ * winding number 1, 0 otherwise. The result is newly allocated. -+ * -+ * Currently, this routine has accuracy problems pending the -+ * implementation of the new intersector. -+ * -+ * Return value: The intersection of @svp1 and @svp2. -+ **/ -+ArtSVP * -+art_svp_intersect (const ArtSVP *svp1, const ArtSVP *svp2) -+{ -+#ifdef ART_USE_NEW_INTERSECTOR -+ ArtSVP *svp3, *svp_new; -+ ArtSvpWriter *swr; -+ -+ svp3 = art_svp_merge (svp1, svp2); -+ swr = art_svp_writer_rewind_new (ART_WIND_RULE_INTERSECT); -+ art_svp_intersector (svp3, swr); -+ svp_new = art_svp_writer_rewind_reap (swr); -+ art_free (svp3); /* shallow free because svp3 contains shared segments */ -+ -+ return svp_new; -+#else -+ ArtSVP *svp3, *svp4, *svp_new; -+ -+ svp3 = art_svp_merge_perturbed (svp1, svp2); -+ svp4 = art_svp_uncross (svp3); -+ art_svp_free (svp3); -+ -+ svp_new = art_svp_rewind_uncrossed (svp4, ART_WIND_RULE_INTERSECT); -+ art_svp_free (svp4); -+ return svp_new; -+#endif -+} -+ -+/* Compute the symmetric difference of two vector paths. -+ -+ Status of this routine: -+ -+ Basic correctness: Seems to work. -+ -+ Numerical stability: We cheat (adding random perturbation). Thus, -+ it seems very likely that no numerical stability problems will be -+ seen in practice. -+ -+ Speed: We could do a lot better by scanning through the svp -+ representations and culling out any segments that are exactly -+ identical. It would also be better if we didn't go to unsorted -+ vector path and back to add the perturbation. -+ -+ Precision: Awful. In the case of inputs which are similar (the -+ common case for canvas display), the entire outline is "hairy." In -+ addition, the perturbation fuzzes the coordinates slightly. It can -+ be used as a conservative approximation. -+ -+*/ -+ -+/** -+ * art_svp_diff: Compute the symmetric difference of two sorted vector paths. -+ * @svp1: One sorted vector path. -+ * @svp2: The other sorted vector path. -+ * -+ * Computes the symmetric of the two argument svp's. Given two svp's -+ * with winding numbers of 0 and 1 everywhere, the resulting winding -+ * number will be 1 where either, but not both, of the argument svp's -+ * has a winding number 1, 0 otherwise. The result is newly allocated. -+ * -+ * Currently, this routine has accuracy problems pending the -+ * implementation of the new intersector. -+ * -+ * Return value: The symmetric difference of @svp1 and @svp2. -+ **/ -+ArtSVP * -+art_svp_diff (const ArtSVP *svp1, const ArtSVP *svp2) -+{ -+#ifdef ART_USE_NEW_INTERSECTOR -+ ArtSVP *svp3, *svp_new; -+ ArtSvpWriter *swr; -+ -+ svp3 = art_svp_merge (svp1, svp2); -+ swr = art_svp_writer_rewind_new (ART_WIND_RULE_ODDEVEN); -+ art_svp_intersector (svp3, swr); -+ svp_new = art_svp_writer_rewind_reap (swr); -+ art_free (svp3); /* shallow free because svp3 contains shared segments */ -+ -+ return svp_new; -+#else -+ ArtSVP *svp3, *svp4, *svp_new; -+ -+ svp3 = art_svp_merge_perturbed (svp1, svp2); -+ svp4 = art_svp_uncross (svp3); -+ art_svp_free (svp3); -+ -+ svp_new = art_svp_rewind_uncrossed (svp4, ART_WIND_RULE_ODDEVEN); -+ art_svp_free (svp4); -+ return svp_new; -+#endif -+} -+ -+#ifdef ART_USE_NEW_INTERSECTOR -+ArtSVP * -+art_svp_minus (const ArtSVP *svp1, const ArtSVP *svp2) -+{ -+ ArtSVP *svp2_mod; -+ ArtSVP *svp3, *svp_new; -+ ArtSvpWriter *swr; -+ int i; -+ -+ svp2_mod = (ArtSVP *) svp2; /* get rid of the const for a while */ -+ -+ /* First invert svp2 to "turn it inside out" */ -+ for (i = 0; i < svp2_mod->n_segs; i++) -+ svp2_mod->segs[i].dir = !svp2_mod->segs[i].dir; -+ -+ svp3 = art_svp_merge (svp1, svp2_mod); -+ swr = art_svp_writer_rewind_new (ART_WIND_RULE_POSITIVE); -+ art_svp_intersector (svp3, swr); -+ svp_new = art_svp_writer_rewind_reap (swr); -+ art_free (svp3); /* shallow free because svp3 contains shared segments */ -+ -+ /* Flip svp2 back to its original state */ -+ for (i = 0; i < svp2_mod->n_segs; i++) -+ svp2_mod->segs[i].dir = !svp2_mod->segs[i].dir; -+ -+ return svp_new; -+} -+#endif -diff -uNr /oocvs/OOO_STABLE_1-backup/external/gpc/art_svp_ops.h external/gpc/art_svp_ops.h ---- /oocvs/OOO_STABLE_1-backup/external/gpc/art_svp_ops.h Wed Dec 31 18:00:00 1969 -+++ external/gpc/art_svp_ops.h Fri Sep 20 21:36:53 2002 -@@ -0,0 +1,40 @@ -+/* Libart_LGPL - library of basic graphic primitives -+ * Copyright (C) 1998 Raph Levien -+ * -+ * This library is free software; you can redistribute it and/or -+ * modify it under the terms of the GNU Library General Public -+ * License as published by the Free Software Foundation; either -+ * version 2 of the License, or (at your option) any later version. -+ * -+ * This library is distributed in the hope that it will be useful, -+ * but WITHOUT ANY WARRANTY; without even the implied warranty of -+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU -+ * Library General Public License for more details. -+ * -+ * You should have received a copy of the GNU Library General Public -+ * License along with this library; if not, write to the -+ * Free Software Foundation, Inc., 59 Temple Place - Suite 330, -+ * Boston, MA 02111-1307, USA. -+ */ -+ -+#ifndef __ART_SVP_OPS_H__ -+#define __ART_SVP_OPS_H__ -+ -+#include "art_svp.h" -+ -+#ifdef __cplusplus -+extern "C" { -+#endif /* __cplusplus */ -+ -+/* Vector path set operations, over sorted vpaths. */ -+ -+ArtSVP *art_svp_union (const ArtSVP *svp1, const ArtSVP *svp2); -+ArtSVP *art_svp_intersect (const ArtSVP *svp1, const ArtSVP *svp2); -+ArtSVP *art_svp_diff (const ArtSVP *svp1, const ArtSVP *svp2); -+ArtSVP *art_svp_minus (const ArtSVP *svp1, const ArtSVP *svp2); -+ -+#ifdef __cplusplus -+} -+#endif /* __cplusplus */ -+ -+#endif /* __ART_SVP_OPS_H__ */ -diff -uNr /oocvs/OOO_STABLE_1-backup/external/gpc/art_svp_vpath.c external/gpc/art_svp_vpath.c ---- /oocvs/OOO_STABLE_1-backup/external/gpc/art_svp_vpath.c Wed Dec 31 18:00:00 1969 -+++ external/gpc/art_svp_vpath.c Fri Sep 20 20:33:09 2002 -@@ -0,0 +1,213 @@ -+/* Libart_LGPL - library of basic graphic primitives -+ * Copyright (C) 1998-2000 Raph Levien -+ * -+ * This library is free software; you can redistribute it and/or -+ * modify it under the terms of the GNU Library General Public -+ * License as published by the Free Software Foundation; either -+ * version 2 of the License, or (at your option) any later version. -+ * -+ * This library is distributed in the hope that it will be useful, -+ * but WITHOUT ANY WARRANTY; without even the implied warranty of -+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU -+ * Library General Public License for more details. -+ * -+ * You should have received a copy of the GNU Library General Public -+ * License along with this library; if not, write to the -+ * Free Software Foundation, Inc., 59 Temple Place - Suite 330, -+ * Boston, MA 02111-1307, USA. -+ */ -+ -+/* Sort vector paths into sorted vector paths */ -+ -+#include "art_svp_vpath.h" -+ -+#include <stdlib.h> -+#include <math.h> -+ -+#include "art_misc.h" -+#include "art_vpath.h" -+#include "art_svp.h" -+ -+ -+/* reverse a list of points in place */ -+static void -+reverse_points (ArtPoint *points, int n_points) -+{ -+ int i; -+ ArtPoint tmp_p; -+ -+ for (i = 0; i < (n_points >> 1); i++) -+ { -+ tmp_p = points[i]; -+ points[i] = points[n_points - (i + 1)]; -+ points[n_points - (i + 1)] = tmp_p; -+ } -+} -+ -+/** -+ * art_svp_from_vpath: Convert a vpath to a sorted vector path. -+ * @vpath: #ArtVPath to convert. -+ * -+ * Converts a vector path into sorted vector path form. The svp form is -+ * more efficient for rendering and other vector operations. -+ * -+ * Basically, the implementation is to traverse the vector path, -+ * generating a new segment for each "run" of points in the vector -+ * path with monotonically increasing Y values. All the resulting -+ * values are then sorted. -+ * -+ * Note: I'm not sure that the sorting rule is correct with respect -+ * to numerical stability issues. -+ * -+ * Return value: Resulting sorted vector path. -+ **/ -+ArtSVP * -+art_svp_from_vpath (ArtVpath *vpath) -+{ -+ int n_segs, n_segs_max; -+ ArtSVP *svp; -+ int dir; -+ int new_dir; -+ int i; -+ ArtPoint *points; -+ int n_points, n_points_max; -+ double x, y; -+ double x_min, x_max; -+ -+ n_segs = 0; -+ n_segs_max = 16; -+ svp = (ArtSVP *)art_alloc (sizeof(ArtSVP) + -+ (n_segs_max - 1) * sizeof(ArtSVPSeg)); -+ -+ dir = 0; -+ n_points = 0; -+ n_points_max = 0; -+ points = NULL; -+ i = 0; -+ -+ x = y = 0; /* unnecessary, given "first code must not be LINETO" invariant, -+ but it makes gcc -Wall -ansi -pedantic happier */ -+ x_min = x_max = 0; /* same */ -+ -+ while (vpath[i].code != ART_END) { -+ if (vpath[i].code == ART_MOVETO || vpath[i].code == ART_MOVETO_OPEN) -+ { -+ if (points != NULL && n_points >= 2) -+ { -+ if (n_segs == n_segs_max) -+ { -+ n_segs_max <<= 1; -+ svp = (ArtSVP *)art_realloc (svp, sizeof(ArtSVP) + -+ (n_segs_max - 1) * -+ sizeof(ArtSVPSeg)); -+ } -+ svp->segs[n_segs].n_points = n_points; -+ svp->segs[n_segs].dir = (dir > 0); -+ if (dir < 0) -+ reverse_points (points, n_points); -+ svp->segs[n_segs].points = points; -+ svp->segs[n_segs].bbox.x0 = x_min; -+ svp->segs[n_segs].bbox.x1 = x_max; -+ svp->segs[n_segs].bbox.y0 = points[0].y; -+ svp->segs[n_segs].bbox.y1 = points[n_points - 1].y; -+ n_segs++; -+ points = NULL; -+ } -+ -+ if (points == NULL) -+ { -+ n_points_max = 4; -+ points = art_new (ArtPoint, n_points_max); -+ } -+ -+ n_points = 1; -+ points[0].x = x = vpath[i].x; -+ points[0].y = y = vpath[i].y; -+ x_min = x; -+ x_max = x; -+ dir = 0; -+ } -+ else /* must be LINETO */ -+ { -+ new_dir = (vpath[i].y > y || -+ (vpath[i].y == y && vpath[i].x > x)) ? 1 : -1; -+ if (dir && dir != new_dir) -+ { -+ /* new segment */ -+ x = points[n_points - 1].x; -+ y = points[n_points - 1].y; -+ if (n_segs == n_segs_max) -+ { -+ n_segs_max <<= 1; -+ svp = (ArtSVP *)art_realloc (svp, sizeof(ArtSVP) + -+ (n_segs_max - 1) * -+ sizeof(ArtSVPSeg)); -+ } -+ svp->segs[n_segs].n_points = n_points; -+ svp->segs[n_segs].dir = (dir > 0); -+ if (dir < 0) -+ reverse_points (points, n_points); -+ svp->segs[n_segs].points = points; -+ svp->segs[n_segs].bbox.x0 = x_min; -+ svp->segs[n_segs].bbox.x1 = x_max; -+ svp->segs[n_segs].bbox.y0 = points[0].y; -+ svp->segs[n_segs].bbox.y1 = points[n_points - 1].y; -+ n_segs++; -+ -+ n_points = 1; -+ n_points_max = 4; -+ points = art_new (ArtPoint, n_points_max); -+ points[0].x = x; -+ points[0].y = y; -+ x_min = x; -+ x_max = x; -+ } -+ -+ if (points != NULL) -+ { -+ if (n_points == n_points_max) -+ art_expand (points, ArtPoint, n_points_max); -+ points[n_points].x = x = vpath[i].x; -+ points[n_points].y = y = vpath[i].y; -+ if (x < x_min) x_min = x; -+ else if (x > x_max) x_max = x; -+ n_points++; -+ } -+ dir = new_dir; -+ } -+ i++; -+ } -+ -+ if (points != NULL) -+ { -+ if (n_points >= 2) -+ { -+ if (n_segs == n_segs_max) -+ { -+ n_segs_max <<= 1; -+ svp = (ArtSVP *)art_realloc (svp, sizeof(ArtSVP) + -+ (n_segs_max - 1) * -+ sizeof(ArtSVPSeg)); -+ } -+ svp->segs[n_segs].n_points = n_points; -+ svp->segs[n_segs].dir = (dir > 0); -+ if (dir < 0) -+ reverse_points (points, n_points); -+ svp->segs[n_segs].points = points; -+ svp->segs[n_segs].bbox.x0 = x_min; -+ svp->segs[n_segs].bbox.x1 = x_max; -+ svp->segs[n_segs].bbox.y0 = points[0].y; -+ svp->segs[n_segs].bbox.y1 = points[n_points - 1].y; -+ n_segs++; -+ } -+ else -+ art_free (points); -+ } -+ -+ svp->n_segs = n_segs; -+ -+ qsort (&svp->segs, n_segs, sizeof (ArtSVPSeg), art_svp_seg_compare); -+ -+ return svp; -+} -+ -diff -uNr /oocvs/OOO_STABLE_1-backup/external/gpc/art_svp_vpath.h external/gpc/art_svp_vpath.h ---- /oocvs/OOO_STABLE_1-backup/external/gpc/art_svp_vpath.h Wed Dec 31 18:00:00 1969 -+++ external/gpc/art_svp_vpath.h Fri Sep 20 21:37:06 2002 -@@ -0,0 +1,39 @@ -+/* Libart_LGPL - library of basic graphic primitives -+ * Copyright (C) 1998 Raph Levien -+ * -+ * This library is free software; you can redistribute it and/or -+ * modify it under the terms of the GNU Library General Public -+ * License as published by the Free Software Foundation; either -+ * version 2 of the License, or (at your option) any later version. -+ * -+ * This library is distributed in the hope that it will be useful, -+ * but WITHOUT ANY WARRANTY; without even the implied warranty of -+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU -+ * Library General Public License for more details. -+ * -+ * You should have received a copy of the GNU Library General Public -+ * License along with this library; if not, write to the -+ * Free Software Foundation, Inc., 59 Temple Place - Suite 330, -+ * Boston, MA 02111-1307, USA. -+ */ -+ -+#ifndef __ART_SVP_VPATH_H__ -+#define __ART_SVP_VPATH_H__ -+ -+#include "art_svp.h" -+#include "art_vpath.h" -+ -+/* Sort vector paths into sorted vector paths. */ -+ -+#ifdef __cplusplus -+extern "C" { -+#endif /* __cplusplus */ -+ -+ArtSVP * -+art_svp_from_vpath (ArtVpath *vpath); -+ -+#ifdef __cplusplus -+} -+#endif /* __cplusplus */ -+ -+#endif /* __ART_SVP_VPATH_H__ */ -diff -uNr /oocvs/OOO_STABLE_1-backup/external/gpc/art_vpath.c external/gpc/art_vpath.c ---- /oocvs/OOO_STABLE_1-backup/external/gpc/art_vpath.c Wed Dec 31 18:00:00 1969 -+++ external/gpc/art_vpath.c Fri Sep 20 20:33:38 2002 -@@ -0,0 +1,239 @@ -+/* Libart_LGPL - library of basic graphic primitives -+ * Copyright (C) 1998-2000 Raph Levien -+ * -+ * This library is free software; you can redistribute it and/or -+ * modify it under the terms of the GNU Library General Public -+ * License as published by the Free Software Foundation; either -+ * version 2 of the License, or (at your option) any later version. -+ * -+ * This library is distributed in the hope that it will be useful, -+ * but WITHOUT ANY WARRANTY; without even the implied warranty of -+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU -+ * Library General Public License for more details. -+ * -+ * You should have received a copy of the GNU Library General Public -+ * License along with this library; if not, write to the -+ * Free Software Foundation, Inc., 59 Temple Place - Suite 330, -+ * Boston, MA 02111-1307, USA. -+ */ -+ -+/* Basic constructors and operations for vector paths */ -+ -+#include "art_vpath.h" -+ -+#include <math.h> -+#include <stdlib.h> -+ -+#include "art_misc.h" -+#include "art_rect.h" -+ -+/** -+ * art_vpath_add_point: Add point to vpath. -+ * @p_vpath: Where the pointer to the #ArtVpath structure is stored. -+ * @pn_points: Pointer to the number of points in *@p_vpath. -+ * @pn_points_max: Pointer to the number of points allocated. -+ * @code: The pathcode for the new point. -+ * @x: The X coordinate of the new point. -+ * @y: The Y coordinate of the new point. -+ * -+ * Adds a new point to *@p_vpath, reallocating and updating *@p_vpath -+ * and *@pn_points_max as necessary. *@pn_points is incremented. -+ * -+ * This routine always adds the point after all points already in the -+ * vpath. Thus, it should be called in the order the points are -+ * desired. -+ **/ -+void -+art_vpath_add_point (ArtVpath **p_vpath, int *pn_points, int *pn_points_max, -+ ArtPathcode code, double x, double y) -+{ -+ int i; -+ -+ i = (*pn_points)++; -+ if (i == *pn_points_max) -+ art_expand (*p_vpath, ArtVpath, *pn_points_max); -+ (*p_vpath)[i].code = code; -+ (*p_vpath)[i].x = x; -+ (*p_vpath)[i].y = y; -+} -+ -+/* number of steps should really depend on radius. */ -+#define CIRCLE_STEPS 128 -+ -+/** -+ * art_vpath_new_circle: Create a new circle. -+ * @x: X coordinate of center. -+ * @y: Y coordinate of center. -+ * @r: radius. -+ * -+ * Creates a new polygon closely approximating a circle with center -+ * (@x, @y) and radius @r. Currently, the number of points used in the -+ * approximation is fixed, but that will probably change. -+ * -+ * Return value: The newly created #ArtVpath. -+ **/ -+ArtVpath * -+art_vpath_new_circle (double x, double y, double r) -+{ -+ int i; -+ ArtVpath *vec; -+ double theta; -+ -+ vec = art_new (ArtVpath, CIRCLE_STEPS + 2); -+ -+ for (i = 0; i < CIRCLE_STEPS + 1; i++) -+ { -+ vec[i].code = i ? ART_LINETO : ART_MOVETO; -+ theta = (i & (CIRCLE_STEPS - 1)) * (M_PI * 2.0 / CIRCLE_STEPS); -+ vec[i].x = x + r * cos (theta); -+ vec[i].y = y - r * sin (theta); -+ } -+ vec[i].code = ART_END; -+ -+ return vec; -+} -+ -+/** -+ * art_vpath_affine_transform: Affine transform a vpath. -+ * @src: Source vpath to transform. -+ * @matrix: Affine transform. -+ * -+ * Computes the affine transform of the vpath, using @matrix as the -+ * transform. @matrix is stored in the same format as PostScript, ie. -+ * x' = @matrix[0] * x + @matrix[2] * y + @matrix[4] -+ * y' = @matrix[1] * x + @matrix[3] * y + @matrix[5] -+ * -+ * Return value: the newly allocated vpath resulting from the transform. -+**/ -+ArtVpath * -+art_vpath_affine_transform (const ArtVpath *src, const double matrix[6]) -+{ -+ int i; -+ int size; -+ ArtVpath *new; -+ double x, y; -+ -+ for (i = 0; src[i].code != ART_END; i++); -+ size = i; -+ -+ new = art_new (ArtVpath, size + 1); -+ -+ for (i = 0; i < size; i++) -+ { -+ new[i].code = src[i].code; -+ x = src[i].x; -+ y = src[i].y; -+ new[i].x = matrix[0] * x + matrix[2] * y + matrix[4]; -+ new[i].y = matrix[1] * x + matrix[3] * y + matrix[5]; -+ } -+ new[i].code = ART_END; -+ -+ return new; -+} -+ -+/** -+ * art_vpath_bbox_drect: Determine bounding box of vpath. -+ * @vec: Source vpath. -+ * @drect: Where to store bounding box. -+ * -+ * Determines bounding box of @vec, and stores it in @drect. -+ **/ -+void -+art_vpath_bbox_drect (const ArtVpath *vec, ArtDRect *drect) -+{ -+ int i; -+ double x0, y0, x1, y1; -+ -+ if (vec[0].code == ART_END) -+ { -+ x0 = y0 = x1 = y1 = 0; -+ } -+ else -+ { -+ x0 = x1 = vec[0].x; -+ y0 = y1 = vec[0].y; -+ for (i = 1; vec[i].code != ART_END; i++) -+ { -+ if (vec[i].x < x0) x0 = vec[i].x; -+ if (vec[i].x > x1) x1 = vec[i].x; -+ if (vec[i].y < y0) y0 = vec[i].y; -+ if (vec[i].y > y1) y1 = vec[i].y; -+ } -+ } -+ drect->x0 = x0; -+ drect->y0 = y0; -+ drect->x1 = x1; -+ drect->y1 = y1; -+} -+ -+/** -+ * art_vpath_bbox_irect: Determine integer bounding box of vpath. -+ * @vec: Source vpath. -+ * idrect: Where to store bounding box. -+ * -+ * Determines integer bounding box of @vec, and stores it in @irect. -+ **/ -+void -+art_vpath_bbox_irect (const ArtVpath *vec, ArtIRect *irect) -+{ -+ ArtDRect drect; -+ -+ art_vpath_bbox_drect (vec, &drect); -+ art_drect_to_irect (irect, &drect); -+} -+ -+#define PERTURBATION 2e-3 -+ -+/** -+ * art_vpath_perturb: Perturb each point in vpath by small random amount. -+ * @src: Source vpath. -+ * -+ * Perturbs each of the points by a small random amount. This is -+ * helpful for cheating in cases when algorithms haven't attained -+ * numerical stability yet. -+ * -+ * Return value: Newly allocated vpath containing perturbed @src. -+ **/ -+ArtVpath * -+art_vpath_perturb (ArtVpath *src) -+{ -+ int i; -+ int size; -+ ArtVpath *new; -+ double x, y; -+ double x_start, y_start; -+ int open; -+ -+ for (i = 0; src[i].code != ART_END; i++); -+ size = i; -+ -+ new = art_new (ArtVpath, size + 1); -+ -+ x_start = 0; -+ y_start = 0; -+ open = 0; -+ for (i = 0; i < size; i++) -+ { -+ new[i].code = src[i].code; -+ x = src[i].x + (PERTURBATION * rand ()) / RAND_MAX - PERTURBATION * 0.5; -+ y = src[i].y + (PERTURBATION * rand ()) / RAND_MAX - PERTURBATION * 0.5; -+ if (src[i].code == ART_MOVETO) -+ { -+ x_start = x; -+ y_start = y; -+ open = 0; -+ } -+ else if (src[i].code == ART_MOVETO_OPEN) -+ open = 1; -+ if (!open && (i + 1 == size || src[i + 1].code != ART_LINETO)) -+ { -+ x = x_start; -+ y = y_start; -+ } -+ new[i].x = x; -+ new[i].y = y; -+ } -+ new[i].code = ART_END; -+ -+ return new; -+} -diff -uNr /oocvs/OOO_STABLE_1-backup/external/gpc/art_vpath.h external/gpc/art_vpath.h ---- /oocvs/OOO_STABLE_1-backup/external/gpc/art_vpath.h Wed Dec 31 18:00:00 1969 -+++ external/gpc/art_vpath.h Fri Sep 20 21:37:17 2002 -@@ -0,0 +1,66 @@ -+/* Libart_LGPL - library of basic graphic primitives -+ * Copyright (C) 1998 Raph Levien -+ * -+ * This library is free software; you can redistribute it and/or -+ * modify it under the terms of the GNU Library General Public -+ * License as published by the Free Software Foundation; either -+ * version 2 of the License, or (at your option) any later version. -+ * -+ * This library is distributed in the hope that it will be useful, -+ * but WITHOUT ANY WARRANTY; without even the implied warranty of -+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU -+ * Library General Public License for more details. -+ * -+ * You should have received a copy of the GNU Library General Public -+ * License along with this library; if not, write to the -+ * Free Software Foundation, Inc., 59 Temple Place - Suite 330, -+ * Boston, MA 02111-1307, USA. -+ */ -+ -+#ifndef __ART_VPATH_H__ -+#define __ART_VPATH_H__ -+ -+#include "art_rect.h" -+#include "art_pathcode.h" -+ -+/* Basic data structures and constructors for simple vector paths */ -+ -+#ifdef __cplusplus -+extern "C" { -+#endif /* __cplusplus */ -+ -+typedef struct _ArtVpath ArtVpath; -+ -+/* CURVETO is not allowed! */ -+struct _ArtVpath { -+ ArtPathcode code; -+ double x; -+ double y; -+}; -+ -+/* Some of the functions need to go into their own modules */ -+ -+void -+art_vpath_add_point (ArtVpath **p_vpath, int *pn_points, int *pn_points_max, -+ ArtPathcode code, double x, double y); -+ -+ArtVpath * -+art_vpath_new_circle (double x, double y, double r); -+ -+ArtVpath * -+art_vpath_affine_transform (const ArtVpath *src, const double matrix[6]); -+ -+void -+art_vpath_bbox_drect (const ArtVpath *vec, ArtDRect *drect); -+ -+void -+art_vpath_bbox_irect (const ArtVpath *vec, ArtIRect *irect); -+ -+ArtVpath * -+art_vpath_perturb (ArtVpath *src); -+ -+#ifdef __cplusplus -+} -+#endif /* __cplusplus */ -+ -+#endif /* __ART_VPATH_H__ */ -diff -uNr /oocvs/OOO_STABLE_1-backup/external/gpc/art_vpath_svp.c external/gpc/art_vpath_svp.c ---- /oocvs/OOO_STABLE_1-backup/external/gpc/art_vpath_svp.c Wed Dec 31 18:00:00 1969 -+++ external/gpc/art_vpath_svp.c Fri Sep 20 20:34:11 2002 -@@ -0,0 +1,195 @@ -+/* Libart_LGPL - library of basic graphic primitives -+ * Copyright (C) 1998-2000 Raph Levien -+ * -+ * This library is free software; you can redistribute it and/or -+ * modify it under the terms of the GNU Library General Public -+ * License as published by the Free Software Foundation; either -+ * version 2 of the License, or (at your option) any later version. -+ * -+ * This library is distributed in the hope that it will be useful, -+ * but WITHOUT ANY WARRANTY; without even the implied warranty of -+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU -+ * Library General Public License for more details. -+ * -+ * You should have received a copy of the GNU Library General Public -+ * License along with this library; if not, write to the -+ * Free Software Foundation, Inc., 59 Temple Place - Suite 330, -+ * Boston, MA 02111-1307, USA. -+ */ -+ -+/* "Unsort" a sorted vector path into an ordinary vector path. */ -+ -+#include "art_vpath_svp.h" -+ -+#include <stdio.h> /* for printf - debugging */ -+#include "art_misc.h" -+ -+#include "art_vpath.h" -+#include "art_svp.h" -+ -+typedef struct _ArtVpathSVPEnd ArtVpathSVPEnd; -+ -+struct _ArtVpathSVPEnd { -+ int seg_num; -+ int which; /* 0 = top, 1 = bottom */ -+ double x, y; -+}; -+ -+#define EPSILON 1e-6 -+ -+static int -+art_vpath_svp_point_compare (double x1, double y1, double x2, double y2) -+{ -+ if (y1 - EPSILON > y2) return 1; -+ if (y1 + EPSILON < y2) return -1; -+ if (x1 - EPSILON > x2) return 1; -+ if (x1 + EPSILON < x2) return -1; -+ return 0; -+} -+ -+static int -+art_vpath_svp_compare (const void *s1, const void *s2) -+{ -+ const ArtVpathSVPEnd *e1 = s1; -+ const ArtVpathSVPEnd *e2 = s2; -+ -+ return art_vpath_svp_point_compare (e1->x, e1->y, e2->x, e2->y); -+} -+ -+/* Convert from sorted vector path representation into regular -+ vector path representation. -+ -+ Status of this routine: -+ -+ Basic correctness: Only works with closed paths. -+ -+ Numerical stability: Not known to work when more than two segments -+ meet at a point. -+ -+ Speed: Should be pretty good. -+ -+ Precision: Does not degrade precision. -+ -+*/ -+/** -+ * art_vpath_from_svp: Convert from svp to vpath form. -+ * @svp: Original #ArtSVP. -+ * -+ * Converts the sorted vector path @svp into standard vpath form. -+ * -+ * Return value: the newly allocated vpath. -+ **/ -+ArtVpath * -+art_vpath_from_svp (const ArtSVP *svp) -+{ -+ int n_segs = svp->n_segs; -+ ArtVpathSVPEnd *ends; -+ ArtVpath *new; -+ int *visited; -+ int n_new, n_new_max; -+ int i, k; -+ int j = 0; /* Quiet compiler */ -+ int seg_num; -+ int first; -+ double last_x, last_y; -+ int n_points; -+ int pt_num; -+ -+ last_x = 0; /* to eliminate "uninitialized" warning */ -+ last_y = 0; -+ -+ ends = art_new (ArtVpathSVPEnd, n_segs * 2); -+ for (i = 0; i < svp->n_segs; i++) -+ { -+ int lastpt; -+ -+ ends[i * 2].seg_num = i; -+ ends[i * 2].which = 0; -+ ends[i * 2].x = svp->segs[i].points[0].x; -+ ends[i * 2].y = svp->segs[i].points[0].y; -+ -+ lastpt = svp->segs[i].n_points - 1; -+ ends[i * 2 + 1].seg_num = i; -+ ends[i * 2 + 1].which = 1; -+ ends[i * 2 + 1].x = svp->segs[i].points[lastpt].x; -+ ends[i * 2 + 1].y = svp->segs[i].points[lastpt].y; -+ } -+ qsort (ends, n_segs * 2, sizeof (ArtVpathSVPEnd), art_vpath_svp_compare); -+ -+ n_new = 0; -+ n_new_max = 16; /* I suppose we _could_ estimate this from traversing -+ the svp, so we don't have to reallocate */ -+ new = art_new (ArtVpath, n_new_max); -+ -+ visited = art_new (int, n_segs); -+ for (i = 0; i < n_segs; i++) -+ visited[i] = 0; -+ -+ first = 1; -+ for (i = 0; i < n_segs; i++) -+ { -+ if (!first) -+ { -+ /* search for the continuation of the existing subpath */ -+ /* This could be a binary search (which is why we sorted, above) */ -+ for (j = 0; j < n_segs * 2; j++) -+ { -+ if (!visited[ends[j].seg_num] && -+ art_vpath_svp_point_compare (last_x, last_y, -+ ends[j].x, ends[j].y) == 0) -+ break; -+ } -+ if (j == n_segs * 2) -+ first = 1; -+ } -+ if (first) -+ { -+ /* start a new subpath */ -+ for (j = 0; j < n_segs * 2; j++) -+ if (!visited[ends[j].seg_num]) -+ break; -+ } -+ if (j == n_segs * 2) -+ { -+ printf ("failure\n"); -+ } -+ seg_num = ends[j].seg_num; -+ n_points = svp->segs[seg_num].n_points; -+ for (k = 0; k < n_points; k++) -+ { -+ pt_num = svp->segs[seg_num].dir ? k : n_points - (1 + k); -+ if (k == 0) -+ { -+ if (first) -+ { -+ art_vpath_add_point (&new, &n_new, &n_new_max, -+ ART_MOVETO, -+ svp->segs[seg_num].points[pt_num].x, -+ svp->segs[seg_num].points[pt_num].y); -+ } -+ } -+ else -+ { -+ art_vpath_add_point (&new, &n_new, &n_new_max, -+ ART_LINETO, -+ svp->segs[seg_num].points[pt_num].x, -+ svp->segs[seg_num].points[pt_num].y); -+ if (k == n_points - 1) -+ { -+ last_x = svp->segs[seg_num].points[pt_num].x; -+ last_y = svp->segs[seg_num].points[pt_num].y; -+ /* to make more robust, check for meeting first_[xy], -+ set first if so */ -+ } -+ } -+ first = 0; -+ } -+ visited[seg_num] = 1; -+ } -+ -+ art_vpath_add_point (&new, &n_new, &n_new_max, -+ ART_END, 0, 0); -+ art_free (visited); -+ art_free (ends); -+ return new; -+} -diff -uNr /oocvs/OOO_STABLE_1-backup/external/gpc/art_vpath_svp.h external/gpc/art_vpath_svp.h ---- /oocvs/OOO_STABLE_1-backup/external/gpc/art_vpath_svp.h Wed Dec 31 18:00:00 1969 -+++ external/gpc/art_vpath_svp.h Fri Sep 20 21:37:33 2002 -@@ -0,0 +1,38 @@ -+/* Libart_LGPL - library of basic graphic primitives -+ * Copyright (C) 1998 Raph Levien -+ * -+ * This library is free software; you can redistribute it and/or -+ * modify it under the terms of the GNU Library General Public -+ * License as published by the Free Software Foundation; either -+ * version 2 of the License, or (at your option) any later version. -+ * -+ * This library is distributed in the hope that it will be useful, -+ * but WITHOUT ANY WARRANTY; without even the implied warranty of -+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU -+ * Library General Public License for more details. -+ * -+ * You should have received a copy of the GNU Library General Public -+ * License along with this library; if not, write to the -+ * Free Software Foundation, Inc., 59 Temple Place - Suite 330, -+ * Boston, MA 02111-1307, USA. -+ */ -+ -+#ifndef __ART_VPATH_SVP_H__ -+#define __ART_VPATH_SVP_H__ -+ -+/* "Unsort" a sorted vector path into an ordinary vector path. */ -+ -+#include "art_svp.h" -+#include "art_vpath.h" -+ -+#ifdef __cplusplus -+extern "C" { -+#endif /* __cplusplus */ -+ -+ArtVpath *art_vpath_from_svp (const ArtSVP *svp); -+ -+#ifdef __cplusplus -+} -+#endif /* __cplusplus */ -+ -+#endif /* __ART_VPATH_SVP_H__ */ -diff -uNr /oocvs/OOO_STABLE_1-backup/external/gpc/makefile.mk external/gpc/makefile.mk ---- /oocvs/OOO_STABLE_1-backup/external/gpc/makefile.mk Wed Apr 18 08:41:33 2001 -+++ external/gpc/makefile.mk Fri Sep 20 21:42:54 2002 -@@ -73,7 +73,12 @@ - - # --- Files -------------------------------------------------------- - --SLOFILES = $(SLO)$/gpc.obj -+#SLOFILES = $(SLO)$/gpc.obj -+ -+OBJFILES = $(OBJ)$/art_svp_intersect.obj $(OBJ)$/art_misc.obj $(OBJ)$/art_rect.obj $(OBJ)$/art_svp.obj $(OBJ)$/art_svp_ops.obj $(OBJ)$/art_svp_vpath.obj $(OBJ)$/art_vpath.obj $(OBJ)$/art_vpath_svp.obj -+ -+SLOFILES = $(SLO)$/art_svp_intersect.obj $(SLO)$/art_misc.obj $(SLO)$/art_rect.obj $(SLO)$/art_svp.obj $(SLO)$/art_svp_ops.obj $(SLO)$/art_svp_vpath.obj $(SLO)$/art_vpath.obj $(SLO)$/art_vpath_svp.obj -+ - - - LIB1TARGET=$(SLB)$/$(TARGET).lib -diff -uNr /oocvs/OOO_STABLE_1-backup/external/prj/d.lst external/prj/d.lst ---- /oocvs/OOO_STABLE_1-backup/external/prj/d.lst Tue Jun 26 06:07:02 2001 -+++ external/prj/d.lst Fri Sep 20 22:19:37 2002 -@@ -36,7 +36,7 @@ - ..\dt\rtufiles\*.h %_DEST%\inc%_EXT%\external\dt\*.h - ..\glibc\rtufiles\config.h %_DEST%\inc%_EXT%\external\glibc\config.h - ..\glibc\rtufiles\getopt.h %_DEST%\inc%_EXT%\external\glibc\getopt.h --..\gpc\gpc.h %_DEST%\inc%_EXT%\external\gpc\gpc.h -+..\gpc\*.h %_DEST%\inc%_EXT%\external\gpc\*.h - ..\npsdk\rtufiles\*.h %_DEST%\inc%_EXT%\external\npsdk\*.h - ..\odbc\rtufiles\*.h %_DEST%\inc%_EXT%\external\odbc\*.h - ..\sane\*.h %_DEST%\inc%_EXT%\external\sane\*.h -diff -u -r1.5 poly.hxx ---- poly.hxx 2001/03/22 13:19:21 1.5 -+++ vcl/inc/poly.hxx 2002/10/02 17:00:08 -@@ -250,13 +250,16 @@ - private: - - ImplPolyPolygon* mpImplPolyPolygon; -- -+#if 0 - #if _SOLAR__PRIVATE - - void* ImplCreateGPCPolygon() const; - void ImplDoOperation( const PolyPolygon& rPolyPoly, PolyPolygon& rResult, ULONG nOperation ) const; - - #endif // __PRIVATE -+#endif -+ void *ImplCreateArtVpath () const; -+ void ImplSetFromArtVpath (void *_vpath); - - public: - -diff -u -r1.4.16.1 poly2.cxx ---- poly2.cxx 2002/06/04 12:56:14 1.4.16.1 -+++ vcl/source/gdi/poly2.cxx 2002/10/10 00:47:04 -@@ -60,13 +60,21 @@ - ************************************************************************/ - - #define _SV_POLY2_CXX -- -+#if 0 - #ifndef __gpc_h --extern "C" -+extern "C" - { -- #include <external/gpc/gpc.h> -+ #include <external/gpc/gpc.h> - } - #endif -+#endif -+#include <external/gpc/art_misc.h> -+#include <external/gpc/art_vpath.h> -+#include <external/gpc/art_svp.h> -+#include <external/gpc/art_svp_vpath.h> -+#include <external/gpc/art_vpath_svp.h> -+#include <external/gpc/art_svp_ops.h> -+#include <external/gpc/art_svp_intersect.h> - - #ifdef W31 - #include <tools/svwin.h> -@@ -357,7 +365,7 @@ - if( bEdges ) - { - const Rectangle aBound( GetBoundRect() ); -- -+ - fArea = ( aBound.GetWidth() + aBound.GetHeight() ) * 0.5; - nPercent = pData ? pData->GetPercentValue() : 50; - nOptimizeFlags &= ~POLY_OPTIMIZE_EDGES; -@@ -402,36 +410,133 @@ - } - } - -+/* Converts an arbitrary SVP to an even-odd SVP */ -+static ArtSVP * -+svp_to_even_odd (ArtSVP *svp) -+{ -+ ArtSvpWriter *svw; -+ ArtSVP *result; -+ -+ svw = art_svp_writer_rewind_new (ART_WIND_RULE_ODDEVEN); -+ art_svp_intersector (svp, svw); -+ -+ result = art_svp_writer_rewind_reap (svw); -+ art_free (svp); /* Shallow free because the result contains shared segments */ -+ -+ return result; -+} -+ -+ - // ----------------------------------------------------------------------- - - void PolyPolygon::GetIntersection( const PolyPolygon& rPolyPoly, PolyPolygon& rResult ) const --{ -+{ -+ ArtVpath *a, *b; -+ ArtSVP *sa, *sb, *s; -+ -+ a = (ArtVpath *) ImplCreateArtVpath (); -+ b = (ArtVpath *) rPolyPoly.ImplCreateArtVpath (); -+ -+ sa = svp_to_even_odd (art_svp_from_vpath (a)); -+ sb = svp_to_even_odd (art_svp_from_vpath (b)); -+ -+ art_free (a); -+ art_free (b); -+ -+ s = art_svp_intersect (sa, sb); -+ a = art_vpath_from_svp (s); -+ art_svp_free (s); -+ -+ rResult.ImplSetFromArtVpath (a); -+ art_free (a); -+#if 0 - ImplDoOperation( rPolyPoly, rResult, GPC_INT ); -+#endif - } - - // ----------------------------------------------------------------------- - - void PolyPolygon::GetUnion( const PolyPolygon& rPolyPoly, PolyPolygon& rResult ) const - { -+ ArtVpath *a, *b; -+ ArtSVP *sa, *sb, *s; -+ -+ a = (ArtVpath *) ImplCreateArtVpath (); -+ b = (ArtVpath *) rPolyPoly.ImplCreateArtVpath (); -+ -+ sa = svp_to_even_odd (art_svp_from_vpath (a)); -+ sb = svp_to_even_odd (art_svp_from_vpath (b)); -+ -+ art_free (a); -+ art_free (b); -+ -+ s = art_svp_union (sa, sb); -+ a = art_vpath_from_svp (s); -+ art_svp_free (s); -+ -+ rResult.ImplSetFromArtVpath (a); -+ art_free (a); -+#if 0 - ImplDoOperation( rPolyPoly, rResult, GPC_UNION ); -+#endif - } - - // ----------------------------------------------------------------------- - - void PolyPolygon::GetDifference( const PolyPolygon& rPolyPoly, PolyPolygon& rResult ) const - { -+ ArtVpath *a, *b; -+ ArtSVP *sa, *sb, *s; -+ -+ a = (ArtVpath *) ImplCreateArtVpath (); -+ b = (ArtVpath *) rPolyPoly.ImplCreateArtVpath (); -+ -+ sa = svp_to_even_odd (art_svp_from_vpath (a)); -+ sb = svp_to_even_odd (art_svp_from_vpath (b)); -+ -+ art_free (a); -+ art_free (b); -+ -+ s = art_svp_minus (sa, sb); -+ a = art_vpath_from_svp (s); -+ art_svp_free (s); -+ -+ rResult.ImplSetFromArtVpath (a); -+ art_free (a); -+#if 0 - ImplDoOperation( rPolyPoly, rResult, GPC_DIFF ); -+#endif - } - - // ----------------------------------------------------------------------- - - void PolyPolygon::GetXOR( const PolyPolygon& rPolyPoly, PolyPolygon& rResult ) const - { -+ ArtVpath *a, *b; -+ ArtSVP *sa, *sb, *s; -+ -+ a = (ArtVpath *) ImplCreateArtVpath (); -+ b = (ArtVpath *) rPolyPoly.ImplCreateArtVpath (); -+ -+ sa = svp_to_even_odd (art_svp_from_vpath (a)); -+ sb = svp_to_even_odd (art_svp_from_vpath (b)); -+ -+ art_free (a); -+ art_free (b); -+ -+ s = art_svp_diff (sa, sb); /* symmetric difference, *not* set difference */ -+ a = art_vpath_from_svp (s); -+ art_svp_free (s); -+ -+ rResult.ImplSetFromArtVpath (a); -+ art_free (a); -+#if 0 - ImplDoOperation( rPolyPoly, rResult, GPC_XOR ); -+#endif - } - - // ----------------------------------------------------------------------- -- -+#if 0 - void* PolyPolygon::ImplCreateGPCPolygon() const - { - gpc_polygon* pRet = new gpc_polygon; -@@ -482,6 +587,8 @@ - - gpc_polygon_clip( (gpc_op) nOperation, pGPCPoly1, pGPCPoly2, pResult ); - -+ fprintf (stderr, "PolyPolygon::ImplDoOperation %ld\n", nOperation); -+ - rResult.Clear(); - - for( int i = 0; i < pResult->num_contours; i++ ) -@@ -508,6 +615,178 @@ - gpc_free_polygon( pResult ); - delete pResult; - } -+#endif -+ -+/* Finds the index of the upper rightmost vertex of a polygon */ -+static int -+upper_rightmost_vertex (const Polygon &poly) -+{ -+ int n; -+ int i; -+ double x, y; -+ int k; -+ -+ n = poly.GetSize (); -+ -+ k = 0; -+ x = poly[0].X (); -+ y = poly[0].Y (); -+ -+ for (i = 1; i < n; i++) -+ if (poly[i].Y () < y || (poly[0].Y () == y && poly[i].X () > x)) { -+ k = i; -+ x = poly[i].X (); -+ y = poly[i].Y (); -+ } -+ -+ return k; -+} -+ -+/* Returns whether a polygon is specified in counterclockwise order */ -+static BOOL -+poly_is_ccw (const Polygon &poly) -+{ -+ int n; -+ int k; -+ double cross; -+ -+ n = poly.GetSize (); -+ -+ if (n == 0) -+ return TRUE; -+ -+ k = upper_rightmost_vertex (poly); -+ -+ const Point &a = poly[(k + n - 1) % n]; -+ const Point &b = poly[k]; -+ const Point &c = poly[(k + 1) % n]; -+ -+ cross = -(a.X () * b.Y () - a.Y () * b.X () + -+ a.Y () * c.X () - a.X () * c.Y () + -+ b.X () * c.Y () - c.X () * b.Y ()); -+ -+ return (cross > 0); -+} -+ -+void * -+PolyPolygon::ImplCreateArtVpath () const -+{ -+ ArtVpath *vpath; -+ int n_contours; -+ int n_vertices; -+ int i, v; -+ -+ n_contours = Count (); -+ n_vertices = 0; -+ for (i = 0; i < n_contours; i++) { -+ const Polygon &poly = GetObject (i); -+ n_vertices += poly.GetSize () + 1; /* plus 1 for if we have to close the path */ -+ } -+ -+ n_vertices++; /* for the ART_END terminator */ -+ -+ vpath = art_new (ArtVpath, n_vertices); -+ v = 0; -+ -+ for (i = 0; i < n_contours; i++) { -+ int j, k; -+ int n; -+ const Polygon &poly = GetObject (i); -+ BOOL ccw; -+ -+ n = poly.GetSize (); -+ -+ ccw = poly_is_ccw (poly); -+ -+ /* Holes or inside contours need to be listed out in reverse -+ * clockwise direction to the main outwards contour, but OO.o -+ * does not seem to handle holes at all. So we'll just list all -+ * the contours as non-holes, e.g. in normal counterclockwise -+ * order. -+ */ -+ -+ if (ccw) -+ k = 0; -+ else -+ k = n - 1; -+ -+ for (j = 0; j < n; j++) { -+ const Point &point = poly[k]; -+ vpath[v].code = (j == 0) ? ART_MOVETO : ART_LINETO; -+ vpath[v].x = point.X (); -+ vpath[v].y = point.Y (); -+ -+ if (ccw) -+ k++; -+ else -+ k--; -+ -+ v++; -+ } -+ -+ /* Close the path if needed */ -+ if (n > 0 && -+ (vpath[v - 1].x != vpath[v - n].x || -+ vpath[v - 1].y != vpath[v - n].y)) { -+ vpath[v].code = ART_LINETO; -+ vpath[v].x = vpath[v - n].x; -+ vpath[v].y = vpath[v - n].y; -+ v++; -+ } -+ } -+ -+ vpath[v].code = ART_END; -+ -+ return vpath; -+} -+ -+void -+PolyPolygon::ImplSetFromArtVpath (void *_vpath) -+{ -+ ArtVpath *vpath; -+ -+ vpath = (ArtVpath *) _vpath; -+ -+ Clear (); -+ -+ while (vpath->code != ART_END) { -+ ArtVpath *p; -+ int n, n_vertices; -+ -+ n = 0; -+ for (p = vpath; n == 0 || p->code == ART_LINETO; p++) -+ n++; -+ -+ /* Remove the last duplicated point from closed subpaths */ -+ if (n > 0 && -+ vpath[n - 1].x == vpath[0].x && -+ vpath[n - 1].y == vpath[0].y) -+ n_vertices = n - 1; -+ else -+ n_vertices = n; -+ -+ if (n_vertices != 0) { -+ int i; -+ -+ Polygon poly (n_vertices); -+ -+ p = vpath; -+ for (i = 0; i < n_vertices; i++) { -+ Point &point = poly[i]; -+ -+ point.X () = FRound (p->x); -+ point.Y () = FRound (p->y); -+ -+ p++; -+ } -+ -+ Insert (poly); -+ } -+ -+ vpath += n; -+ } -+} -+ - - // ----------------------------------------------------------------------- - |