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 +#endif +#include +#include + +/** + * 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 /* 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 + +#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 /* 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 /* for rand() */ +#include + +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 +#include + +#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 +#include + +#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 /* 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 + #include } #endif +#endif +#include +#include +#include +#include +#include +#include +#include #ifdef W31 #include @@ -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; + } +} + // -----------------------------------------------------------------------