[dia] path: add binary path operations to <Selection> context menu
- From: Hans Breuer <hans src gnome org>
- To: commits-list gnome org
- Cc:
- Subject: [dia] path: add binary path operations to <Selection> context menu
- Date: Sun, 3 Aug 2014 13:38:59 +0000 (UTC)
commit ff19fc77f59b1e89640492a5ab9968727df9650a
Author: Hans Breuer <hans breuer org>
Date: Sun Aug 3 15:10:25 2014 +0200
path: add binary path operations to <Selection> context menu
If there is more than one object selected the context menu offers extra
entries: Union, Difference, Intersection and Exclusion. These are implemented
based on DiaPathRenderer and new path_combine() function. The latter still has
some issues, but it's good enough to check with another compiler/build system.
app/disp_callbacks.c | 63 ++++-
lib/Makefile.am | 1 +
lib/create.h | 2 +
lib/diapathrenderer.c | 87 +++++-
lib/diapathrenderer.h | 3 +
lib/diatypes.h | 7 +
lib/libdia.def | 1 +
lib/makefile.msc | 1 +
lib/object.c | 20 +-
lib/object.h | 1 +
lib/path-math.c | 778 ++++++++++++++++++++++++++++++++++++++++++++++
samples/path-combine.dia | Bin 0 -> 34654 bytes
12 files changed, 945 insertions(+), 19 deletions(-)
---
diff --git a/app/disp_callbacks.c b/app/disp_callbacks.c
index 305a858..750e86e 100644
--- a/app/disp_callbacks.c
+++ b/app/disp_callbacks.c
@@ -217,8 +217,63 @@ add_convert_to_path_menu_item (GtkMenu *menu)
gtk_menu_shell_append (GTK_MENU_SHELL (menu), menu_item);
gtk_widget_show(menu_item);
}
+
+static void
+_combine_to_path_callback (GtkAction *action, gpointer data)
+{
+ DDisplay *ddisp = ddisplay_active();
+ GList *cut_list;
+ DiaObject *obj;
+ Diagram *dia;
+
+ if (!ddisp) return;
+ dia = ddisp->diagram;
+
+ diagram_selected_break_external(ddisp->diagram);
+ cut_list = parent_list_affected(diagram_get_sorted_selected(ddisp->diagram));
+ obj = create_standard_path_from_list (cut_list, GPOINTER_TO_INT (data));
+ if (obj) {
+ /* remove the objects just combined */
+ Change *change = undo_delete_objects_children(dia, cut_list);
+ (change->apply)(change, dia);
+ /* add the new object with undo */
+ undo_insert_objects(dia, g_list_prepend(NULL, obj), 1);
+ undo_set_transactionpoint(ddisp->diagram->undo);
+
+ diagram_add_object (dia, obj);
+ diagram_select(dia, obj);
+ object_add_updates(obj, dia);
+
+ ddisplay_do_update_menu_sensitivity(ddisp);
+ diagram_flush(dia);
+ } else {
+ g_list_free (cut_list);
+ }
+}
+static void
+add_combine_to_path_menu_items (GtkMenu *menu)
+{
+ struct {
+ const gchar *name;
+ PathCombineMode mode;
+ } _ops[] = {
+ { N_("Union"), PATH_UNION },
+ { N_("Difference"), PATH_DIFFERENCE },
+ { N_("Intersection"), PATH_INTERSECTION },
+ { N_("Exclusion"), PATH_EXCLUSION },
+ };
+ int i;
+ for (i = 0; i < G_N_ELEMENTS (_ops); ++i) {
+ GtkWidget *menu_item = gtk_menu_item_new_with_label(_ops[i].name);
+ g_signal_connect(G_OBJECT(menu_item), "activate",
+ G_CALLBACK(_combine_to_path_callback), GINT_TO_POINTER (_ops[i].mode));
+ gtk_menu_shell_append (GTK_MENU_SHELL (menu), menu_item);
+ gtk_widget_show(menu_item);
+ }
+}
+
static void
-create_object_menu(DiaMenu *dia_menu, gboolean root_menu)
+create_object_menu(DiaMenu *dia_menu, gboolean root_menu, gboolean combining)
{
int i;
GtkWidget *menu;
@@ -273,7 +328,7 @@ create_object_menu(DiaMenu *dia_menu, gboolean root_menu)
* DiaMenu pointer for the submenu. */
if ( ((DiaMenu*)item->callback_data)->app_data == NULL ) {
/* Create the popup menu items for the submenu. */
- create_object_menu((DiaMenu*)(item->callback_data), FALSE) ;
+ create_object_menu((DiaMenu*)(item->callback_data), FALSE, FALSE) ;
gtk_menu_item_set_submenu( GTK_MENU_ITEM (menu_item),
GTK_WIDGET(((DiaMenu*)(item->callback_data))->app_data));
}
@@ -287,6 +342,8 @@ create_object_menu(DiaMenu *dia_menu, gboolean root_menu)
add_follow_link_menu_item(GTK_MENU (menu));
if (!native_convert_to_path)
add_convert_to_path_menu_item(GTK_MENU (menu));
+ if (combining)
+ add_combine_to_path_menu_items (GTK_MENU (menu));
}
dia_menu->app_data = menu;
@@ -353,7 +410,7 @@ popup_object_menu(DDisplay *ddisp, GdkEvent *event)
}
if (dia_menu->app_data == NULL) {
- create_object_menu(dia_menu, TRUE);
+ create_object_menu(dia_menu, TRUE, g_list_length (diagram->data->selected) > 1);
/* append the Input Methods menu, if there is canvas editable text */
if (obj && focus_get_first_on_object(obj) != NULL) {
GtkWidget *menuitem = gtk_menu_item_new_with_mnemonic (_("Input _Methods"));
diff --git a/lib/Makefile.am b/lib/Makefile.am
index 1475d5c..fc1590c 100644
--- a/lib/Makefile.am
+++ b/lib/Makefile.am
@@ -171,6 +171,7 @@ libdia_la_SOURCES = \
diagdkrenderer.c \
diapathrenderer.h \
diapathrenderer.c \
+ path-math.c \
diapatternselector.h \
diapatternselector.c \
diatransformrenderer.h \
diff --git a/lib/create.h b/lib/create.h
index ad8b01a..37065f0 100644
--- a/lib/create.h
+++ b/lib/create.h
@@ -142,6 +142,8 @@ DiaObject *create_standard_group(GList *items);
DiaObject *create_standard_path_from_object (DiaObject *obj);
+DiaObject *create_standard_path_from_list (GList *objects, PathCombineMode mode);
+
G_END_DECLS
#endif
diff --git a/lib/diapathrenderer.c b/lib/diapathrenderer.c
index 12f0700..8786f69 100644
--- a/lib/diapathrenderer.c
+++ b/lib/diapathrenderer.c
@@ -72,15 +72,10 @@ dia_path_renderer_init (DiaPathRenderer *self)
self->stroke = attributes_get_foreground ();
self->fill = attributes_get_background ();
}
-/*!
- * \brief Destructor
- * If there are still pathes left, deallocate them
- */
+
static void
-dia_path_renderer_finalize (GObject *object)
+_path_renderer_clear (DiaPathRenderer *self)
{
- DiaPathRenderer *self = DIA_PATH_RENDERER (object);
-
if (self->pathes) {
guint i;
@@ -92,6 +87,18 @@ dia_path_renderer_finalize (GObject *object)
g_ptr_array_free (self->pathes, TRUE);
self->pathes = NULL;
}
+}
+/*!
+ * \brief Destructor
+ * If there are still paths left, deallocate them
+ * \memberof _DiaPathRenderer
+ */
+static void
+dia_path_renderer_finalize (GObject *object)
+{
+ DiaPathRenderer *self = DIA_PATH_RENDERER (object);
+
+ _path_renderer_clear (self);
G_OBJECT_CLASS (dia_path_renderer_parent_class)->finalize (object);
}
@@ -566,8 +573,6 @@ _bezier (DiaRenderer *self,
}
for (; i < numpoints; ++i)
g_array_append_val (path, points[i]);
- if (fill) /* might not be necessary anymore with draw_beziergon*/
- _path_lineto (path, &points[0].p1);
}
/*!
* \brief Create path from bezier line
@@ -713,9 +718,14 @@ draw_rounded_rect (DiaRenderer *self,
radius = rx;
if (radius > ry)
radius = ry;
- DIA_RENDERER_CLASS(dia_path_renderer_parent_class)->draw_rounded_rect(self,
- ul_corner, lr_corner,
- NULL, stroke ? stroke : fill, radius);
+ if (stroke) /* deliberately ignoring fill for path building */
+ DIA_RENDERER_CLASS(dia_path_renderer_parent_class)->draw_rounded_rect(self,
+ ul_corner, lr_corner,
+ NULL, stroke, radius);
+ else
+ DIA_RENDERER_CLASS(dia_path_renderer_parent_class)->draw_rounded_rect(self,
+ ul_corner, lr_corner,
+ fill, NULL, radius);
/* stroke is set by the piecewise rendering above already */
if (fill)
renderer->fill = *fill;
@@ -807,7 +817,6 @@ create_standard_path_from_object (DiaObject *obj)
for (i = 0; i < pr->pathes->len; ++i) {
GArray *points = g_ptr_array_index (pr->pathes, i);
DiaObject *obj;
-
if (points->len < 2)
obj = NULL;
else
@@ -829,3 +838,55 @@ create_standard_path_from_object (DiaObject *obj)
return path;
}
+
+/*!
+ * \brief Combine the list of object into a new path object
+ *
+ * Every single object get into a single path which gets combined
+ * with the following object. The result of that operation than gets
+ * combined again with the following object.
+ */
+DiaObject *
+create_standard_path_from_list (GList *objects,
+ PathCombineMode mode)
+{
+ DiaObject *path;
+ DiaRenderer *renderer;
+ DiaPathRenderer *pr;
+ GList *list;
+ GArray *p1 = NULL, *p2 = NULL;
+
+ renderer = g_object_new (DIA_TYPE_PATH_RENDERER, 0);
+ pr = DIA_PATH_RENDERER (renderer);
+
+ for (list = objects; list != NULL; list = list->next) {
+ DiaObject *obj = list->data;
+ int i;
+
+ _path_renderer_clear (pr);
+ obj->ops->draw (obj, renderer);
+ /* get a single path from this rendererer run */
+ p2 = g_array_new (FALSE, FALSE, sizeof(BezPoint));
+ for (i = 0; i < pr->pathes->len; ++i) {
+ GArray *points = g_ptr_array_index (pr->pathes, i);
+ g_array_append_vals (p2, &g_array_index (points, BezPoint, 0), points->len);
+ }
+ if (p1 && p2) {
+ GArray *combined = path_combine (p1, p2, mode);
+ if (combined) {
+ g_array_free (p1, TRUE);
+ p1 = combined;
+ g_array_free (p2, TRUE);
+ p2 = NULL;
+ }
+ } else {
+ p1 = p2;
+ p2 = NULL;
+ }
+ }
+ path = create_standard_path (p1->len, &g_array_index (p1, BezPoint, 0));
+ /* copy style from first object processed */
+ object_copy_style (path, (DiaObject *)objects->data);
+ g_array_free (p1, TRUE);
+ return path;
+}
diff --git a/lib/diapathrenderer.h b/lib/diapathrenderer.h
index a679f03..f94ef85 100644
--- a/lib/diapathrenderer.h
+++ b/lib/diapathrenderer.h
@@ -47,4 +47,7 @@ void path_build_ellipse (GArray *path,
Point *center,
real width, real height);
+/* in path-math.c */
+GArray *path_combine (const GArray *p1, const GArray *p2, PathCombineMode mode);
+
#endif
diff --git a/lib/diatypes.h b/lib/diatypes.h
index 35b38fc..4748c46 100644
--- a/lib/diatypes.h
+++ b/lib/diatypes.h
@@ -193,4 +193,11 @@ typedef struct _DiaFileSelectorClass DiaFileSelectorClass;
/** A standard definition of a function that takes a DiaObject */
typedef void (*DiaObjectFunc) (const DiaObject *obj);
+typedef enum {
+ PATH_UNION = 1,
+ PATH_DIFFERENCE,
+ PATH_INTERSECTION,
+ PATH_EXCLUSION
+} PathCombineMode;
+
#endif
diff --git a/lib/libdia.def b/lib/libdia.def
index 38d1f65..3afaa56 100644
--- a/lib/libdia.def
+++ b/lib/libdia.def
@@ -120,6 +120,7 @@ EXPORTS
create_standard_group
create_standard_image
create_standard_path
+ create_standard_path_from_list
create_standard_path_from_object
create_standard_path_from_text
create_standard_polygon
diff --git a/lib/makefile.msc b/lib/makefile.msc
index 7727296..01ba2ab 100644
--- a/lib/makefile.msc
+++ b/lib/makefile.msc
@@ -96,6 +96,7 @@ OBJECTS = \
orth_conn.obj \
paper.obj \
parent.obj \
+ path-math.obj \
pattern.obj \
persistence.obj \
plug-ins.obj \
diff --git a/lib/object.c b/lib/object.c
index 5e055b9..5ef482c 100644
--- a/lib/object.c
+++ b/lib/object.c
@@ -373,6 +373,20 @@ static PropDescription _style_prop_descs[] = {
PROP_DESC_END
};
+void
+object_copy_style (DiaObject *dest, const DiaObject *src)
+{
+ GPtrArray *props;
+
+ g_return_if_fail (src && src->ops->get_props != NULL);
+ g_return_if_fail (dest && dest->ops->set_props != NULL);
+
+ props = prop_list_from_descs (_style_prop_descs, pdtpp_true);
+ src->ops->get_props((DiaObject *)src, props);
+ dest->ops->set_props(dest, props);
+ prop_list_free(props);
+}
+
static void
_object_exchange (ObjectChange *change, DiaObject *obj)
{
@@ -427,8 +441,8 @@ _object_exchange (ObjectChange *change, DiaObject *obj)
parent_object->children = g_list_insert_before (parent_object->children, sibling, subst);
parent_object->children = g_list_remove (parent_object->children, obj);
}
- /* apply style properties */
- if (subst->ops->get_props)
+ /* apply style properties - only if it's not restore of original */
+ if (subst->ops->get_props && subst != c->orig)
subst->ops->set_props(subst, props);
prop_list_free(props);
/* adding to the diagram last, to have the right update areas */
@@ -473,7 +487,7 @@ _object_exchange_free (ObjectChange *change)
* \brief Replace an object with another one
*
* The type of an object can not change dynamically. To substitute one
- * object with another this function help. It does it's best to transfer
+ * object with another this function helps. It does it's best to transfer
* all the existing object relations, e.g. connections, parent_layer
* and parenting information.
*
diff --git a/lib/object.h b/lib/object.h
index 968305a..fb57e5d 100644
--- a/lib/object.h
+++ b/lib/object.h
@@ -600,6 +600,7 @@ void object_save_props(DiaObject *obj, ObjectNode obj_node, DiaContext
same type) */
void object_copy_props(DiaObject *dest, const DiaObject *src,
gboolean is_default);
+void object_copy_style(DiaObject *dest, const DiaObject *src);
G_END_DECLS
diff --git a/lib/path-math.c b/lib/path-math.c
new file mode 100644
index 0000000..90b1e58
--- /dev/null
+++ b/lib/path-math.c
@@ -0,0 +1,778 @@
+/* Dia -- an diagram creation/manipulation program
+ * Copyright (C) 1998 Alexander Larsson
+ *
+ * path-math.c -- some helper function for binary path operations
+ * Copyright (C) 2014, Hans Breuer <Hans Breuer Org>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
+ */
+#include <config.h>
+
+#include "geometry.h"
+#include "boundingbox.h"
+
+#include <string.h> /* memcmp() */
+
+/*!
+ * \brief Take a path and calculate it to non overlapping pieces
+ */
+
+typedef struct _BezierSegment BezierSegment;
+struct _BezierSegment {
+ Point p0;
+ Point p1;
+ Point p2;
+ Point p3;
+};
+
+/*!
+ * \brief Split a bezier segment into left and right half
+ */
+static void
+bezier_split (const BezierSegment *a,
+ BezierSegment *a1,
+ BezierSegment *a2)
+{
+ /* see: Foley et al., Computer Graphics, p508 */
+ Point L2, L3, L4, H, R2, R3;
+ /* P1 = L1 */
+ a1->p0 = a->p0;
+ /* L2 = (P1 + P2) / 2 */
+ L2.x = (a->p0.x + a->p1.x) / 2;
+ L2.y = (a->p0.y + a->p1.y) / 2;
+ /* H = (P2 + P3) / 2 */
+ H.x = (a->p1.x + a->p2.x) / 2;
+ H.y = (a->p1.y + a->p2.y) / 2;
+ /* R3 = (P3 + P4) / 2 */
+ R3.x = (a->p2.x + a->p3.x) / 2;
+ R3.y = (a->p2.y + a->p3.y) / 2;
+ /* L3 = (L2 + H) / 2 */
+ L3.x = (L2.x + H.x) / 2;
+ L3.y = (L2.y + H.y) / 2;
+ /* R2 = (H + R3) / 2 */
+ R2.x = (H.x + R3.x) / 2;
+ R2.y = (H.y + R3.y) / 2;
+
+ a1->p1 = L2;
+ a1->p2 = L3;
+ /* L4 = R1 = (L3 + R2) / 2 */
+ L4.x = (L3.x + R2.x) / 2;
+ L4.y = (L3.y + R2.y) / 2;
+ a1->p3 = a2->p0 = L4;
+ a2->p1 = R2;
+ a2->p2 = R3;
+ /* P4 = R4 */
+ a2->p3 = a->p3;
+}
+
+static void
+bezier_split_at (const BezierSegment *a,
+ BezierSegment *a1,
+ BezierSegment *a2,
+ real split)
+{
+ real left = 1.0 - split;
+ real right = split;
+ /* see: Foley et al., Computer Graphics, p508 */
+ Point L2, L3, L4, H, R2, R3;
+ /* P1 = L1 */
+ a1->p0 = a->p0;
+ /* L2 = (P1 + P2) / 2 */
+ L2.x = (a->p0.x * left + a->p1.x * right);
+ L2.y = (a->p0.y * left + a->p1.y * right);
+ /* H = (P2 + P3) / 2 */
+ H.x = (a->p1.x * left + a->p2.x * right);
+ H.y = (a->p1.y * left + a->p2.y * right);
+ /* R3 = (P3 + P4) / 2 */
+ R3.x = (a->p2.x * left + a->p3.x * right);
+ R3.y = (a->p2.y * left + a->p3.y * right);
+ /* L3 = (L2 + H) / 2 */
+ L3.x = (L2.x * left + H.x * right);
+ L3.y = (L2.y * left + H.y * right);
+ /* R2 = (H + R3) / 2 */
+ R2.x = (H.x * left + R3.x * right);
+ R2.y = (H.y * left + R3.y * right);
+
+ a1->p1 = L2;
+ a1->p2 = L3;
+ /* L4 = R1 = (L3 + R2) / 2 */
+ L4.x = (L3.x * left + R2.x * right);
+ L4.y = (L3.y * left + R2.y * right);
+ a1->p3 = a2->p0 = L4;
+ a2->p1 = R2;
+ a2->p2 = R3;
+ /* P4 = R4 */
+ a2->p3 = a->p3;
+}
+
+typedef struct _Intersection Intersection;
+struct _Intersection {
+ Point pt; /*!< the crossing point */
+ real split_one; /*!< 0..1: relative placement on segment one */
+ real split_two; /*!< 0..1: relative placement on segment two */
+ int seg_one; /*!< index of the segment */
+ int seg_two; /*!< index of the segment */
+};
+
+static gboolean
+_segment_has_point (const BezierSegment *bs,
+ const Point *pt)
+{
+ BezPoint bp;
+ real dist;
+ bp.type = BEZ_CURVE_TO;
+ bp.p1 = bs->p1;
+ bp.p2 = bs->p2;
+ bp.p3 = bs->p3;
+ dist = distance_bez_seg_point (&bs->p0, &bp, 0, pt);
+
+ return dist <= 0.0;
+}
+
+static gboolean
+_segment_is_moveto (const BezierSegment *bs)
+{
+ if ( memcmp (&bs->p0, &bs->p1, sizeof (Point)) == 0
+ && memcmp (&bs->p0, &bs->p2, sizeof (Point)) == 0
+ && memcmp (&bs->p0, &bs->p3, sizeof (Point)) == 0)
+ return TRUE;
+ return FALSE;
+}
+
+/* search precision */
+static const real EPSILON = 0.0001;
+
+/*!
+ * \brief Calculate crossing points of two bezier segments
+ *
+ * Beware two bezier segments can intersect more than once, but this
+ * function only returns the first or no intersection. It is the
+ * responsibility of the caller to further split segments until there
+ * is no intersection left.
+ */
+static gboolean
+bezier_bezier_intersection (GArray *crossing,
+ const BezierSegment *a,
+ const BezierSegment *b,
+ int depth,
+ real asplit,
+ real bsplit)
+{
+ Rectangle abox, bbox;
+ PolyBBExtras extra = { 0, };
+ gboolean small_a, small_b;
+
+ /* Avoid intersection overflow: if start and end are on the other segment
+ * assume full overlap and no crossing.
+ */
+ if ( (_segment_has_point (a, &b->p0) && _segment_has_point (a, &b->p3))
+ || (_segment_has_point (b, &a->p0) && _segment_has_point (b, &a->p3)))
+ return FALSE; /* XXX: more variants pending, partial overlap */
+
+ /* With very similar segments we would create a lot of points with not
+ * a very deep recursion (test with ying-yang symbol).
+ * Just comparing the segments on depth=1 is not good enough, so for
+ * now we are limiting the number of intersections
+ */
+ if (crossing->len > 127) { /* XXX: arbitrary limit */
+ g_warning ("Crossing limit (%d) reached", crossing->len);
+ return FALSE;
+ }
+
+ bicubicbezier2D_bbox (&a->p0, &a->p1, &a->p2, &a->p3, &extra, &abox);
+ bicubicbezier2D_bbox (&b->p0, &b->p1, &b->p2, &b->p3, &extra, &bbox);
+
+ if (!rectangle_intersects (&abox, &bbox))
+ return FALSE;
+ small_a = (abox.right - abox.left) < EPSILON && (abox.bottom - abox.top) < EPSILON;
+ small_b = (bbox.right - bbox.left) < EPSILON && (bbox.bottom - bbox.top) < EPSILON;
+ /* if the boxes are small enough we can calculate the point */
+ if (small_a && small_b) {
+ /* intersecting and both small, should not matter which one is used */
+ Point pt = { (bbox.right + bbox.left) / 2, (bbox.bottom + bbox.top) / 2 };
+ Intersection is;
+ int i;
+ for (i = 0; i < crossing->len; ++i) {
+ /* if it's already included we are done */
+ if (distance_point_point (&g_array_index (crossing, Intersection, i).pt, &pt) < 1.4142*EPSILON)
+ return TRUE; /* although we did not add it */
+ }
+ is.split_one = asplit;
+ is.split_two = bsplit;
+ is.pt = pt;
+ g_print ("d=%d; as=%g; bs=%g; ", depth, asplit, bsplit);
+ g_array_append_val (crossing, is);
+ return TRUE;
+ } else {
+ /* further splitting of a and b; it could be smart to only search in the
+ * intersection of a-box and b-box ... */
+ BezierSegment a1, a2;
+ BezierSegment b1, b2;
+ real ofs = 1.0/(1<<(depth+1));
+ gboolean ret = FALSE;
+
+ bezier_split (a, &a1, &a2);
+ bezier_split (b, &b1, &b2);
+
+ ret |= bezier_bezier_intersection (crossing, &a1, &b1, depth+1, asplit-ofs, bsplit-ofs);
+ ret |= bezier_bezier_intersection (crossing, &a2, &b1, depth+1, asplit+ofs, bsplit-ofs);
+ ret |= bezier_bezier_intersection (crossing, &a1, &b2, depth+1, asplit-ofs, bsplit+ofs);
+ ret |= bezier_bezier_intersection (crossing, &a2, &b2, depth+1, asplit+ofs, bsplit+ofs);
+ /* XXX: check !ret case, not sure if it should happen */
+ return ret;
+ }
+}
+
+static gboolean
+_segment_from_path (BezierSegment *a, const GArray *p1, int i)
+{
+ const BezPoint *abp0 = &g_array_index (p1, BezPoint, i-1);
+ const BezPoint *abp1 = &g_array_index (p1, BezPoint, i);
+ a->p0 = abp0->type == BEZ_CURVE_TO ? abp0->p3 : abp0->p1;
+ switch (abp1->type) {
+ case BEZ_CURVE_TO :
+ a->p1 = abp1->p1; a->p2 = abp1->p2; a->p3 = abp1->p3;
+ break;
+ case BEZ_LINE_TO :
+ if (distance_point_point (&a->p0, &abp1->p1) < EPSILON)
+ return FALSE; /* avoid a zero length line-to for confusion with move-to */
+ a->p1 = a->p2 = a->p3 = abp1->p1;
+ break;
+ case BEZ_MOVE_TO :
+ a->p0 = a->p1 = a->p2 = a->p3 = abp1->p1;
+ break;
+ }
+ return TRUE;
+}
+
+static void
+_curve_from_segment (BezPoint *bp, const BezierSegment *a, gboolean flip)
+{
+ if (_segment_is_moveto (a))
+ bp->type = BEZ_MOVE_TO;
+ else if (memcmp (&a->p1, &a->p2, sizeof(Point)) == 0)
+ bp->type = BEZ_LINE_TO;
+ else
+ bp->type = BEZ_CURVE_TO;
+ if (!flip) {
+ bp->p1 = a->p1;
+ bp->p2 = a->p2;
+ bp->p3 = a->p3;
+ } else {
+ bp->p1 = a->p2;
+ bp->p2 = a->p1;
+ bp->p3 = a->p0;
+ }
+}
+
+typedef struct _Split Split;
+struct _Split {
+ Point pt; /*!< the position of the split */
+ int seg; /*!< the index of the segment to split */
+ real split; /*!< 0..1: relative placement on segment */
+ gboolean used; /*!< marked during _make_path() */
+ gboolean outside; /*!< not inside the other path */
+ GArray *path; /*!< subpath copy */
+};
+
+static GArray *
+_extract_splits (const GArray *crossing, gboolean one)
+{
+ GArray *result = g_array_new (FALSE, FALSE, sizeof(Split));
+ int i;
+ for (i = 0; i < crossing->len; ++i) {
+ Split sp = { 0 };
+ sp.pt = g_array_index (crossing, Intersection, i).pt;
+ if (one) {
+ sp.seg = g_array_index (crossing, Intersection, i).seg_one;
+ sp.split = g_array_index (crossing, Intersection, i).split_one;
+ } else {
+ sp.seg = g_array_index (crossing, Intersection, i).seg_two;
+ sp.split = g_array_index (crossing, Intersection, i).split_two;
+ }
+ sp.used = FALSE;
+ g_array_append_val (result, sp);
+ }
+ return result;
+}
+
+static GArray *
+_path_to_segments (const GArray *path)
+{
+ GArray *segs = g_array_new (FALSE, FALSE, sizeof(BezierSegment));
+ BezierSegment bs;
+ int i;
+ BezPoint *last_move = &g_array_index (path, BezPoint, 0);
+
+ for (i = 1; i < path->len; ++i) {
+ if (g_array_index (path, BezPoint, i).type == BEZ_MOVE_TO)
+ last_move = &g_array_index (path, BezPoint, i);
+ if (_segment_from_path (&bs, path, i))
+ g_array_append_val (segs, bs);
+ }
+ /* if the path is not closed do an explicit line-to */
+ if (memcmp (&last_move->p1, &bs.p3, sizeof(Point)) != 0) {
+ bs.p0 = bs.p3;
+ bs.p1 = bs.p2 = bs.p3 = last_move->p1;
+ g_array_append_val (segs, bs);
+ }
+
+ return segs;
+}
+
+/* GCompareFunc to sort Split */
+static gint
+_compare_split (gconstpointer as, gconstpointer bs)
+{
+ const Split *a = as;
+ const Split *b = bs;
+ if (a->seg > b->seg)
+ return 1;
+ if (a->seg < b->seg)
+ return -1;
+ if (a->split > b->split)
+ return 1;
+ if (a->split < b->split)
+ return -1;
+ return 0;
+}
+
+/*!
+ * Given the original segments and splits apply
+ * all segment splits and create unique segment index.
+ *
+ * Split.seg is the index to the segment to split before this function.
+ * After the split it indexes the last segment in the row of splits.
+ */
+static void
+_split_segments (GArray *segs, GArray *splits, const GArray *other)
+{
+ int i, sofs = 0;
+ GArray *pending;
+
+ /* splits must be sorted for the algorithm below */
+ g_array_sort (splits, _compare_split);
+
+ for (i = 0; i < splits->len; ++i) {
+ int j, to;
+ int from = i;
+ int from_seg = g_array_index (splits, Split, i).seg;
+ BezierSegment bs;
+ real t = 0;
+
+ g_return_if_fail (from_seg + sofs < segs->len);
+ bs = g_array_index (segs, BezierSegment, from_seg + sofs);
+ while (i < splits->len - 1 && from_seg == g_array_index (splits, Split, i+1).seg)
+ ++i; /* advance while segment reference is the same */
+ to = i;
+ for (j = from; j <= to; j++) {
+ BezierSegment left, right;
+ /* scale t to split the right segment */
+ real tL = g_array_index (splits, Split, j).split;
+ real tR = (tL - t) / (1.0 - t);
+ bezier_split_at (&bs, &left, &right, tR);
+ bs = right;
+ t = tL;
+ /* overwrite the exisiting */
+ g_return_if_fail (from_seg + sofs < segs->len);
+ g_array_index (segs, BezierSegment, from_seg + sofs) = left;
+ sofs += 1; /* increment segment offset for every segment added */
+ /* insert a new one behind that ... */
+ g_array_insert_val (segs, from_seg + sofs, right); /* ... potentially overwritten */
+ /* adjust the segment reference */
+ g_array_index (splits, Split, j).seg = from_seg + sofs;
+ }
+ }
+ pending = g_array_new (FALSE, FALSE, sizeof(BezierSegment));
+ /* for every sub-path determine if it is inside the full other path */
+ for (i = 0; i < splits->len; ++i) {
+ Split *sp = &g_array_index (splits, Split, i);
+ BezierSegment *bs = &g_array_index (segs, BezierSegment, sp->seg);
+ BezierSegment left, right;
+ Point pt;
+ int to, j;
+
+ if (i == 0 && sp->seg > 0)
+ g_array_append_vals (pending, &g_array_index (segs, BezierSegment, 0), sp->seg);
+
+ bezier_split (bs, &left, &right);
+ pt = right.p0;
+ sp->outside = distance_bez_shape_point (&g_array_index (other, BezPoint, 0), other->len,
+ 0 /* line width */, &pt) > 0.0;
+ /* also remember the sub-path */
+ to = g_array_index (splits, Split, (i+1)%splits->len).seg;
+ sp->path = g_array_new (FALSE, FALSE, sizeof(BezierSegment));
+ if (to < sp->seg) {
+ g_array_append_vals (sp->path, bs, segs->len - sp->seg);
+#if 0
+ /* XXX: this is only correct if there is no move-to within the segments */
+ g_array_append_vals (sp->path, &g_array_index (segs, BezierSegment, 0), to);
+#else
+ g_array_append_vals (sp->path, &g_array_index (pending, BezierSegment, 0), pending->len);
+ g_array_set_size (pending, 0);
+#endif
+ } else {
+ for (j = sp->seg; j < to; ++j) {
+ if (_segment_is_moveto (bs)) {
+ g_array_append_vals (sp->path, &g_array_index (pending, BezierSegment, 0), pending->len);
+ g_array_set_size (pending, 0);
+ break;
+ }
+ g_array_append_val (sp->path, *bs);
+ bs++;
+ }
+ for (/* remains */; j < to; ++j) {
+ g_array_append_val (pending, *bs);
+ bs++;
+ }
+ }
+ }
+ g_array_free (pending, TRUE);
+}
+
+static void
+_free_splits (GArray *splits)
+{
+ int i;
+
+ g_return_if_fail (splits != NULL);
+
+ for (i = 0; i < splits->len; ++i) {
+ Split *sp = &g_array_index (splits, Split, i);
+ if (sp->path)
+ g_array_free (sp->path, TRUE);
+ }
+ g_array_free (splits, TRUE);
+}
+
+static GArray *
+_find_intersections (GArray *one, GArray *two)
+{
+ GArray *crossing = g_array_new (FALSE, FALSE, sizeof(Intersection));
+ int i, j, k;
+
+ /* find intersections */
+ for (i = 0; i < one->len; ++i) {
+ BezierSegment a = g_array_index (one, BezierSegment, i);
+ for (j = 0; j < two->len; ++j) {
+ BezierSegment b = g_array_index (two, BezierSegment, j);
+ int start = crossing->len;
+ if (bezier_bezier_intersection (crossing, &a, &b, 1, 0.5, 0.5)) {
+ /* Found intersection splits a and b into left and right.
+ * Any segment might be split more than once so seg_one and seg_two
+ * are not unique yet. Also the calculated split always refers to
+ * the whole segment. We could avoid the _split_segments() below by
+ * modifying `one� and `two� in place. But instead of later
+ * segmentation that would complicate the seq_* reference _and_ give
+ * worse runtime behavior because we would need to start over with
+ * every intersection found.
+ */
+ for (k = start; k < crossing->len; ++k) {
+ Intersection *is = &g_array_index (crossing, Intersection, k);
+ is->seg_one = i;
+ is->seg_two = j;
+ }
+ g_print ("with a:b %d:%d\n", i, j);
+ }
+ }
+ }
+
+ if (crossing->len > 0)
+ return crossing;
+ g_array_free (crossing, TRUE);
+ return NULL;
+}
+
+/*!
+ * \brief Find the next sub path to connect
+ *
+ * Ignores the crossing point of the Split, but just looks at the
+ * start and end of the given sub path.
+ */
+static gboolean
+_find_split (GArray *splits, Point *pt, gboolean outside, Split **next)
+{
+ int i;
+
+ for (i = 0; i < splits->len; ++i) {
+ Split *sp = &g_array_index (splits, Split, i);
+ /* one of two splits - prefer the one matching in start point */
+ BezierSegment *bs = &g_array_index (sp->path, BezierSegment, 0);
+ if ( !sp->used
+ && (sp->outside == outside)
+ && distance_point_point (&bs->p0, pt) < 1.4142 * EPSILON) {
+ *next = sp;
+ sp->used = TRUE;
+ return TRUE;
+ }
+ }
+ /* but also deliver segments ending in pt */
+ for (i = 0; i < splits->len; ++i) {
+ Split *sp = &g_array_index (splits, Split, i);
+ BezierSegment *bs = &g_array_index (sp->path, BezierSegment, sp->path->len - 1);
+ if ( !sp->used
+ && (sp->outside == outside)
+ && distance_point_point (&bs->p3, pt) < 1.4142 * EPSILON) {
+ *next = sp;
+ sp->used = TRUE;
+ return TRUE;
+ }
+ }
+ return FALSE;
+}
+
+static Point
+_append_segments (GArray *path,
+ GArray *segs)
+{
+ BezPoint bp;
+ int i;
+ gboolean flip;
+ BezPoint *ebp = &g_array_index (path, BezPoint, path->len - 1);
+ const BezierSegment *sseg = &g_array_index (segs, BezierSegment, 0);
+ const BezierSegment *eseg = &g_array_index (segs, BezierSegment, segs->len - 1);
+
+ /* always try to join with what we have */
+ if (distance_point_point (&sseg->p0,
+ ebp->type == BEZ_CURVE_TO ? &ebp->p3 : &ebp->p1) < EPSILON) {
+ /* matching in given direction */
+ flip = FALSE;
+ } else if (distance_point_point (&eseg->p3,
+ ebp->type == BEZ_CURVE_TO ? &ebp->p3 : &ebp->p1) < EPSILON) {
+ /* change direction of segments */
+ flip = TRUE;
+ } else {
+ /* neither matches so we can use any direction but should add a move-to */
+ bp.type = BEZ_MOVE_TO;
+ bp.p1 = sseg->p0;
+ g_array_append_val (path, bp);
+ }
+
+ if (flip) {
+ for (i = segs->len - 1; i >= 0; --i) { /* counting down - backwards append */
+ _curve_from_segment (&bp, &g_array_index (segs, BezierSegment, i), flip);
+ if (bp.type != BEZ_MOVE_TO) /* just ignore move-to here */
+ g_array_append_val (path, bp);
+ }
+ } else {
+ for (i = 0; i < segs->len; ++i) { /* preserve original direction */
+ _curve_from_segment (&bp, &g_array_index (segs, BezierSegment, i), flip);
+ if (bp.type != BEZ_MOVE_TO)
+ g_array_append_val (path, bp);
+ }
+ }
+ ebp = &g_array_index (path, BezPoint, path->len - 1);
+ return ebp->type == BEZ_CURVE_TO ? ebp->p3 : ebp->p1;
+}
+/*!
+ * \brief Just reassamble both paths again for debugging
+ */
+static GArray *
+_make_path0 (GArray *one, /*!< array<BezierSegment> from first path */
+ GArray *one_splits, /*!< array<Split> for first path */
+ GArray *two, /*!< second path */
+ GArray *two_splits /*!< splits */
+ )
+{
+ GArray *result = g_array_new (FALSE, FALSE, sizeof(BezPoint));
+ int sel;
+ for (sel = 0; sel < 2; ++sel) {
+ GArray *segs = sel == 0 ? one : two;
+ GArray *splits = sel == 0 ? one_splits : two_splits;
+ int i, isp = 0;
+ BezPoint bp;
+ bp.type = BEZ_MOVE_TO;
+ bp.p1 = g_array_index (segs, BezierSegment, 0).p0;
+ g_array_append_val (result, bp);
+ for (i = 0; i < segs->len; ++i) {
+ BezierSegment *seg = &g_array_index (segs, BezierSegment, i);
+ /* every split starts with a move-to */
+ if ( isp < splits->len
+ && 0
+ && i == g_array_index (splits, Split, isp).seg
+ && g_array_index (result, BezPoint, result->len - 1).type != BEZ_MOVE_TO) {
+ bp.type = BEZ_MOVE_TO;
+ bp.p1 = seg->p0;
+ g_array_append_val (result, bp);
+ ++isp;
+ }
+ _curve_from_segment (&bp, seg, FALSE);
+ g_array_append_val (result, bp);
+
+ }
+ }
+ return result;
+}
+/*!
+ * \brief Another reassambling for debugging
+ */
+static GArray *
+_make_path1 (GArray *one, /*!< array<BezierSegment> from first path */
+ GArray *one_splits, /*!< array<Split> for first path */
+ GArray *two, /*!< second path */
+ GArray *two_splits /*!< splits */
+ )
+{
+ GArray *result = g_array_new (FALSE, FALSE, sizeof(BezPoint));
+ int i, sel;
+
+ for (sel = 0; sel < 2; ++sel) {
+ GArray *splits = sel == 0 ? one_splits : two_splits;
+ for (i = 0; i < splits->len; ++i) {
+ Split *sp = &g_array_index (splits, Split, i);
+
+ if (i == 0) { /* must at least start with move-to */
+ BezPoint bp;
+ bp.type = BEZ_MOVE_TO;
+ bp.p1 = g_array_index (sp->path, BezierSegment, 0).p0;
+ g_array_append_val (result, bp);
+ }
+ _append_segments (result, sp->path);
+ }
+ }
+ return result;
+}
+/*!
+ * \brief Convert back to a single BezPoint path
+ */
+static GArray *
+_make_path (GArray *one, /*!< array<BezierSegment> from first path */
+ GArray *one_splits, /*!< array<Split> for first path */
+ GArray *two, /*!< second path */
+ GArray *two_splits, /*!< splits */
+ PathCombineMode mode)
+{
+ GArray *result = g_array_new (FALSE, FALSE, sizeof(BezPoint));
+ Split *sp;
+ int i, n = 0;
+ BezPoint bp;
+ Point cur_pt;
+ GArray *splits;
+ /* only intersection starts with an inside segment */
+ gboolean outside = mode == PATH_INTERSECTION ? FALSE : TRUE;
+
+ g_return_val_if_fail (mode != PATH_EXCLUSION, NULL);
+
+ bp.type = BEZ_MOVE_TO;
+ /* start with the first point of segment one */
+ for (i = 0; i < one_splits->len; ++i) {
+ sp = &g_array_index (one_splits, Split, i);
+ if (sp->outside == outside)
+ break;
+ }
+ sp->used = TRUE;
+ bp.p1 = g_array_index (one, BezierSegment, sp->seg).p0;
+ g_array_append_val (result, bp);
+ do {
+ cur_pt = _append_segments (result, sp->path);
+ n++;
+ if (mode == PATH_DIFFERENCE)
+ outside = (n % 2) == 0 ? TRUE : FALSE;
+ splits = (n % 2) == 0 ? one_splits : two_splits;
+ /* find next intersection start from the last point of this sub path */
+ if (!_find_split (splits, &cur_pt, outside, &sp)) {
+ /* if we can not find something connected search for an unused 'one' path
+ * XXX: this might be part of the issue with lost move-to within the segment
+ * The other part might be in _append_segments or even _split_segments
+ */
+ outside = mode == PATH_INTERSECTION ? FALSE : TRUE;
+ for (i = 0; i < one_splits->len; ++i) {
+ sp = &g_array_index (one_splits, Split, i);
+ if (!sp->used && (sp->outside == outside))
+ break;
+ else
+ sp = NULL;
+ }
+ if (sp) { /* found a new start, make a move-to */
+ sp->used = TRUE;
+ bp.type = BEZ_MOVE_TO;
+ bp.p1 = g_array_index (sp->path, BezierSegment, 0).p0;
+ g_array_append_val (result, bp);
+ }
+ }
+ } while (sp);
+
+ return result;
+}
+
+/*!
+ * \brief Combine two path into a single one with the given operation
+ *
+ * This should (but does not) consider
+ * - self intersections in a path
+ * - winding rule
+ * - typical path operations (Union, Difference, Intersection, Exclusion, ...)
+ */
+GArray *
+path_combine (const GArray *p1,
+ const GArray *p2,
+ PathCombineMode mode)
+{
+ GArray *result = NULL;
+ int i, j, k;
+ int total = 0;
+ GArray *crossing = NULL;
+ GArray *one, *two;
+ static int debug = 0;
+
+ g_return_val_if_fail (p1->len > 1 && p2->len > 1, NULL);
+
+ /* convert both paths to segment representation - TODO: self intersections */
+ one = _path_to_segments (p1);
+ two = _path_to_segments (p2);
+ crossing = _find_intersections (one, two);
+
+ if (crossing)
+ g_print ("Total path intersections: %d\n", crossing->len);
+
+ if (crossing) {
+ /* Now crossing includes points in arbitrary order. Every point has four lines
+ * going in or out - two from p1, two from p2. Split one and two into segments
+ * at the crossing points.
+ */
+ GArray *one_splits = _extract_splits (crossing, TRUE);
+ GArray *two_splits = _extract_splits (crossing, FALSE);
+ _split_segments (one, one_splits, p2);
+ _split_segments (two, two_splits, p1);
+
+ /* XXX: convert segments back to a single path */
+ if (one_splits->len < 2) { /* XXX: just joining again */
+ result = _make_path0 (one, one_splits, two, two_splits);
+ } else if (debug) {
+ result = _make_path1 (one, one_splits, two, two_splits);
+ } else {
+ if (mode == PATH_EXCLUSION) { /* most simple impl. */
+ GArray *res2;
+ result = _make_path (one, one_splits, two, two_splits, PATH_DIFFERENCE);
+ res2 = _make_path (two, two_splits, one, one_splits, PATH_DIFFERENCE);
+ g_array_append_vals (result, &g_array_index (res2, BezPoint, 0), res2->len);
+ g_array_free (res2, TRUE);
+ } else {
+ result = _make_path (one, one_splits, two, two_splits, mode);
+ }
+ }
+ _free_splits (one_splits);
+ _free_splits (two_splits);
+ g_array_free (crossing, TRUE);
+ }
+ g_array_free (one, TRUE);
+ g_array_free (two, TRUE);
+ if (!result || result->len < 2) {
+ if (result)
+ g_array_free (result, TRUE);
+ return NULL;
+ }
+ return result;
+}
diff --git a/samples/path-combine.dia b/samples/path-combine.dia
new file mode 100644
index 0000000..b1ea4e6
Binary files /dev/null and b/samples/path-combine.dia differ
[
Date Prev][
Date Next] [
Thread Prev][
Thread Next]
[
Thread Index]
[
Date Index]
[
Author Index]
