/* GIMP - The GNU Image Manipulation Program * Copyright (C) 1995 Spencer Kimball and Peter Mattis * * gimpbezierstroke.c * Copyright (C) 2002 Simon Budig * * This program is free software: you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation; either version 3 of the License, or * (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program. If not, see . */ #include "config.h" #include #include #include "libgimpmath/gimpmath.h" #include "vectors-types.h" #include "core/gimp-transform-utils.h" #include "core/gimpbezierdesc.h" #include "core/gimpcoords.h" #include "core/gimpcoords-interpolate.h" #include "gimpanchor.h" #include "gimpbezierstroke.h" /* local prototypes */ static gdouble gimp_bezier_stroke_nearest_point_get (GimpStroke *stroke, const GimpCoords *coord, gdouble precision, GimpCoords *ret_point, GimpAnchor **ret_segment_start, GimpAnchor **ret_segment_end, gdouble *ret_pos); static gdouble gimp_bezier_stroke_segment_nearest_point_get (const GimpCoords *beziercoords, const GimpCoords *coord, gdouble precision, GimpCoords *ret_point, gdouble *ret_pos, gint depth); static gdouble gimp_bezier_stroke_nearest_tangent_get (GimpStroke *stroke, const GimpCoords *coord1, const GimpCoords *coord2, gdouble precision, GimpCoords *nearest, GimpAnchor **ret_segment_start, GimpAnchor **ret_segment_end, gdouble *ret_pos); static gdouble gimp_bezier_stroke_segment_nearest_tangent_get (const GimpCoords *beziercoords, const GimpCoords *coord1, const GimpCoords *coord2, gdouble precision, GimpCoords *ret_point, gdouble *ret_pos); static void gimp_bezier_stroke_anchor_move_relative (GimpStroke *stroke, GimpAnchor *anchor, const GimpCoords *deltacoord, GimpAnchorFeatureType feature); static void gimp_bezier_stroke_anchor_move_absolute (GimpStroke *stroke, GimpAnchor *anchor, const GimpCoords *coord, GimpAnchorFeatureType feature); static void gimp_bezier_stroke_anchor_convert (GimpStroke *stroke, GimpAnchor *anchor, GimpAnchorFeatureType feature); static void gimp_bezier_stroke_anchor_delete (GimpStroke *stroke, GimpAnchor *anchor); static gboolean gimp_bezier_stroke_point_is_movable (GimpStroke *stroke, GimpAnchor *predec, gdouble position); static void gimp_bezier_stroke_point_move_relative (GimpStroke *stroke, GimpAnchor *predec, gdouble position, const GimpCoords *deltacoord, GimpAnchorFeatureType feature); static void gimp_bezier_stroke_point_move_absolute (GimpStroke *stroke, GimpAnchor *predec, gdouble position, const GimpCoords *coord, GimpAnchorFeatureType feature); static void gimp_bezier_stroke_close (GimpStroke *stroke); static GimpStroke * gimp_bezier_stroke_open (GimpStroke *stroke, GimpAnchor *end_anchor); static gboolean gimp_bezier_stroke_anchor_is_insertable (GimpStroke *stroke, GimpAnchor *predec, gdouble position); static GimpAnchor * gimp_bezier_stroke_anchor_insert (GimpStroke *stroke, GimpAnchor *predec, gdouble position); static gboolean gimp_bezier_stroke_is_extendable (GimpStroke *stroke, GimpAnchor *neighbor); static gboolean gimp_bezier_stroke_connect_stroke (GimpStroke *stroke, GimpAnchor *anchor, GimpStroke *extension, GimpAnchor *neighbor); static GArray * gimp_bezier_stroke_interpolate (GimpStroke *stroke, gdouble precision, gboolean *closed); static GimpBezierDesc * gimp_bezier_stroke_make_bezier (GimpStroke *stroke); static void gimp_bezier_stroke_transform (GimpStroke *stroke, const GimpMatrix3 *matrix, GQueue *ret_strokes); static void gimp_bezier_stroke_finalize (GObject *object); static GList * gimp_bezier_stroke_get_anchor_listitem (GList *list); G_DEFINE_TYPE (GimpBezierStroke, gimp_bezier_stroke, GIMP_TYPE_STROKE) #define parent_class gimp_bezier_stroke_parent_class static void gimp_bezier_stroke_class_init (GimpBezierStrokeClass *klass) { GObjectClass *object_class = G_OBJECT_CLASS (klass); GimpStrokeClass *stroke_class = GIMP_STROKE_CLASS (klass); object_class->finalize = gimp_bezier_stroke_finalize; stroke_class->nearest_point_get = gimp_bezier_stroke_nearest_point_get; stroke_class->nearest_tangent_get = gimp_bezier_stroke_nearest_tangent_get; stroke_class->nearest_intersection_get = NULL; stroke_class->anchor_move_relative = gimp_bezier_stroke_anchor_move_relative; stroke_class->anchor_move_absolute = gimp_bezier_stroke_anchor_move_absolute; stroke_class->anchor_convert = gimp_bezier_stroke_anchor_convert; stroke_class->anchor_delete = gimp_bezier_stroke_anchor_delete; stroke_class->point_is_movable = gimp_bezier_stroke_point_is_movable; stroke_class->point_move_relative = gimp_bezier_stroke_point_move_relative; stroke_class->point_move_absolute = gimp_bezier_stroke_point_move_absolute; stroke_class->close = gimp_bezier_stroke_close; stroke_class->open = gimp_bezier_stroke_open; stroke_class->anchor_is_insertable = gimp_bezier_stroke_anchor_is_insertable; stroke_class->anchor_insert = gimp_bezier_stroke_anchor_insert; stroke_class->is_extendable = gimp_bezier_stroke_is_extendable; stroke_class->extend = gimp_bezier_stroke_extend; stroke_class->connect_stroke = gimp_bezier_stroke_connect_stroke; stroke_class->interpolate = gimp_bezier_stroke_interpolate; stroke_class->make_bezier = gimp_bezier_stroke_make_bezier; stroke_class->transform = gimp_bezier_stroke_transform; } static void gimp_bezier_stroke_init (GimpBezierStroke *stroke) { } static void gimp_bezier_stroke_finalize (GObject *object) { G_OBJECT_CLASS (parent_class)->finalize (object); } /* Bezier specific functions */ GimpStroke * gimp_bezier_stroke_new (void) { return g_object_new (GIMP_TYPE_BEZIER_STROKE, NULL); } GimpStroke * gimp_bezier_stroke_new_from_coords (const GimpCoords *coords, gint n_coords, gboolean closed) { GimpStroke *stroke; GimpAnchor *last_anchor; gint count; g_return_val_if_fail (coords != NULL, NULL); g_return_val_if_fail (n_coords >= 3, NULL); g_return_val_if_fail ((n_coords % 3) == 0, NULL); stroke = gimp_bezier_stroke_new (); last_anchor = NULL; for (count = 0; count < n_coords; count++) last_anchor = gimp_bezier_stroke_extend (stroke, &coords[count], last_anchor, EXTEND_SIMPLE); if (closed) gimp_stroke_close (stroke); return stroke; } static void gimp_bezier_stroke_anchor_delete (GimpStroke *stroke, GimpAnchor *anchor) { GList *list; GList *list2; gint i; /* Anchors always are surrounded by two handles that have to * be deleted too */ list2 = g_queue_find (stroke->anchors, anchor); list = g_list_previous (list2); for (i = 0; i < 3; i++) { g_return_if_fail (list != NULL); list2 = g_list_next (list); gimp_anchor_free (list->data); g_queue_delete_link (stroke->anchors, list); list = list2; } } static GimpStroke * gimp_bezier_stroke_open (GimpStroke *stroke, GimpAnchor *end_anchor) { GList *list; GList *list2; GimpStroke *new_stroke = NULL; list = g_queue_find (stroke->anchors, end_anchor); g_return_val_if_fail (list != NULL && list->next != NULL, NULL); list = g_list_next (list); /* protect the handle... */ list2 = list->next; list->next = NULL; if (list2 != NULL) { GList *tail = stroke->anchors->tail; stroke->anchors->tail = list; stroke->anchors->length -= g_list_length (list2); list2->prev = NULL; if (stroke->closed) { GList *l; for (l = tail; l; l = g_list_previous (l)) g_queue_push_head (stroke->anchors, l->data); g_list_free (list2); } else { new_stroke = gimp_bezier_stroke_new (); new_stroke->anchors->head = list2; new_stroke->anchors->tail = g_list_last (list2); new_stroke->anchors->length = g_list_length (list2); } } stroke->closed = FALSE; g_object_notify (G_OBJECT (stroke), "closed"); return new_stroke; } static gboolean gimp_bezier_stroke_anchor_is_insertable (GimpStroke *stroke, GimpAnchor *predec, gdouble position) { return (g_queue_find (stroke->anchors, predec) != NULL); } static GimpAnchor * gimp_bezier_stroke_anchor_insert (GimpStroke *stroke, GimpAnchor *predec, gdouble position) { GList *segment_start; GList *list; GList *list2; GimpCoords subdivided[8]; GimpCoords beziercoords[4]; gint i; segment_start = g_queue_find (stroke->anchors, predec); if (! segment_start) return NULL; list = segment_start; for (i = 0; i <= 3; i++) { beziercoords[i] = GIMP_ANCHOR (list->data)->position; list = g_list_next (list); if (! list) list = stroke->anchors->head; } subdivided[0] = beziercoords[0]; subdivided[6] = beziercoords[3]; gimp_coords_mix (1-position, &(beziercoords[0]), position, &(beziercoords[1]), &(subdivided[1])); gimp_coords_mix (1-position, &(beziercoords[1]), position, &(beziercoords[2]), &(subdivided[7])); gimp_coords_mix (1-position, &(beziercoords[2]), position, &(beziercoords[3]), &(subdivided[5])); gimp_coords_mix (1-position, &(subdivided[1]), position, &(subdivided[7]), &(subdivided[2])); gimp_coords_mix (1-position, &(subdivided[7]), position, &(subdivided[5]), &(subdivided[4])); gimp_coords_mix (1-position, &(subdivided[2]), position, &(subdivided[4]), &(subdivided[3])); /* subdivided 0-6 contains the bezier segment subdivided at */ list = segment_start; for (i = 0; i <= 6; i++) { if (i >= 2 && i <= 4) { list2 = g_list_append (NULL, gimp_anchor_new ((i == 3 ? GIMP_ANCHOR_ANCHOR: GIMP_ANCHOR_CONTROL), &(subdivided[i]))); /* insert it *before* list manually. */ list2->next = list; list2->prev = list->prev; if (list->prev) list->prev->next = list2; list->prev = list2; list = list2; if (i == 3) segment_start = list; } else { GIMP_ANCHOR (list->data)->position = subdivided[i]; } list = g_list_next (list); if (! list) list = stroke->anchors->head; } stroke->anchors->head = g_list_first (list); stroke->anchors->tail = g_list_last (list); stroke->anchors->length += 3; return GIMP_ANCHOR (segment_start->data); } static gboolean gimp_bezier_stroke_point_is_movable (GimpStroke *stroke, GimpAnchor *predec, gdouble position) { return (g_queue_find (stroke->anchors, predec) != NULL); } static void gimp_bezier_stroke_point_move_relative (GimpStroke *stroke, GimpAnchor *predec, gdouble position, const GimpCoords *deltacoord, GimpAnchorFeatureType feature) { GimpCoords offsetcoords[2]; GList *segment_start; GList *list; gint i; gdouble feel_good; segment_start = g_queue_find (stroke->anchors, predec); g_return_if_fail (segment_start != NULL); /* dragging close to endpoints just moves the handle related to * the endpoint. Just make sure that feel_good is in the range from * 0 to 1. The 1.0 / 6.0 and 5.0 / 6.0 are duplicated in * tools/gimpvectortool.c. */ if (position <= 1.0 / 6.0) feel_good = 0; else if (position <= 0.5) feel_good = (pow((6 * position - 1) / 2.0, 3)) / 2; else if (position <= 5.0 / 6.0) feel_good = (1 - pow((6 * (1-position) - 1) / 2.0, 3)) / 2 + 0.5; else feel_good = 1; gimp_coords_scale ((1-feel_good)/(3*position* (1-position)*(1-position)), deltacoord, &(offsetcoords[0])); gimp_coords_scale (feel_good/(3*position*position*(1-position)), deltacoord, &(offsetcoords[1])); list = segment_start; list = g_list_next (list); if (! list) list = stroke->anchors->head; for (i = 0; i <= 1; i++) { gimp_stroke_anchor_move_relative (stroke, GIMP_ANCHOR (list->data), &(offsetcoords[i]), feature); list = g_list_next (list); if (! list) list = stroke->anchors->head; } } static void gimp_bezier_stroke_point_move_absolute (GimpStroke *stroke, GimpAnchor *predec, gdouble position, const GimpCoords *coord, GimpAnchorFeatureType feature) { GimpCoords deltacoord; GimpCoords tmp1, tmp2, abs_pos; GimpCoords beziercoords[4]; GList *segment_start; GList *list; gint i; segment_start = g_queue_find (stroke->anchors, predec); g_return_if_fail (segment_start != NULL); list = segment_start; for (i = 0; i <= 3; i++) { beziercoords[i] = GIMP_ANCHOR (list->data)->position; list = g_list_next (list); if (! list) list = stroke->anchors->head; } gimp_coords_mix ((1-position)*(1-position)*(1-position), &(beziercoords[0]), 3*(1-position)*(1-position)*position, &(beziercoords[1]), &tmp1); gimp_coords_mix (3*(1-position)*position*position, &(beziercoords[2]), position*position*position, &(beziercoords[3]), &tmp2); gimp_coords_add (&tmp1, &tmp2, &abs_pos); gimp_coords_difference (coord, &abs_pos, &deltacoord); gimp_bezier_stroke_point_move_relative (stroke, predec, position, &deltacoord, feature); } static void gimp_bezier_stroke_close (GimpStroke *stroke) { GList *start; GList *end; GimpAnchor *anchor; start = stroke->anchors->head; end = stroke->anchors->tail; g_return_if_fail (start->next != NULL && end->prev != NULL); if (start->next != end->prev) { if (gimp_coords_equal (&(GIMP_ANCHOR (start->next->data)->position), &(GIMP_ANCHOR (start->data)->position)) && gimp_coords_equal (&(GIMP_ANCHOR (start->data)->position), &(GIMP_ANCHOR (end->data)->position)) && gimp_coords_equal (&(GIMP_ANCHOR (end->data)->position), &(GIMP_ANCHOR (end->prev->data)->position))) { /* redundant segment */ gimp_anchor_free (stroke->anchors->tail->data); g_queue_delete_link (stroke->anchors, stroke->anchors->tail); gimp_anchor_free (stroke->anchors->tail->data); g_queue_delete_link (stroke->anchors, stroke->anchors->tail); anchor = stroke->anchors->tail->data; g_queue_delete_link (stroke->anchors, stroke->anchors->tail); gimp_anchor_free (stroke->anchors->head->data); stroke->anchors->head->data = anchor; } } GIMP_STROKE_CLASS (parent_class)->close (stroke); } static gdouble gimp_bezier_stroke_nearest_point_get (GimpStroke *stroke, const GimpCoords *coord, gdouble precision, GimpCoords *ret_point, GimpAnchor **ret_segment_start, GimpAnchor **ret_segment_end, gdouble *ret_pos) { gdouble min_dist, dist, pos; GimpCoords point = { 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0 }; GimpCoords segmentcoords[4]; GList *anchorlist; GimpAnchor *segment_start; GimpAnchor *segment_end = NULL; GimpAnchor *anchor; gint count; if (g_queue_is_empty (stroke->anchors)) return -1.0; count = 0; min_dist = -1; pos = 0; for (anchorlist = stroke->anchors->head; GIMP_ANCHOR (anchorlist->data)->type != GIMP_ANCHOR_ANCHOR; anchorlist = g_list_next (anchorlist)); segment_start = anchorlist->data; for ( ; anchorlist; anchorlist = g_list_next (anchorlist)) { anchor = anchorlist->data; segmentcoords[count] = anchor->position; count++; if (count == 4) { segment_end = anchorlist->data; dist = gimp_bezier_stroke_segment_nearest_point_get (segmentcoords, coord, precision, &point, &pos, 10); if (dist < min_dist || min_dist < 0) { min_dist = dist; if (ret_pos) *ret_pos = pos; if (ret_point) *ret_point = point; if (ret_segment_start) *ret_segment_start = segment_start; if (ret_segment_end) *ret_segment_end = segment_end; } segment_start = anchorlist->data; segmentcoords[0] = segmentcoords[3]; count = 1; } } if (stroke->closed && stroke->anchors->head) { anchorlist = stroke->anchors->head; while (count < 3) { segmentcoords[count] = GIMP_ANCHOR (anchorlist->data)->position; count++; } anchorlist = g_list_next (anchorlist); if (anchorlist) { segment_end = GIMP_ANCHOR (anchorlist->data); segmentcoords[3] = segment_end->position; } dist = gimp_bezier_stroke_segment_nearest_point_get (segmentcoords, coord, precision, &point, &pos, 10); if (dist < min_dist || min_dist < 0) { min_dist = dist; if (ret_pos) *ret_pos = pos; if (ret_point) *ret_point = point; if (ret_segment_start) *ret_segment_start = segment_start; if (ret_segment_end) *ret_segment_end = segment_end; } } return min_dist; } static gdouble gimp_bezier_stroke_segment_nearest_point_get (const GimpCoords *beziercoords, const GimpCoords *coord, gdouble precision, GimpCoords *ret_point, gdouble *ret_pos, gint depth) { /* * beziercoords has to contain four GimpCoords with the four control points * of the bezier segment. We subdivide it at the parameter 0.5. */ GimpCoords subdivided[8]; gdouble dist1, dist2; GimpCoords point1, point2; gdouble pos1, pos2; gimp_coords_difference (&beziercoords[1], &beziercoords[0], &point1); gimp_coords_difference (&beziercoords[3], &beziercoords[2], &point2); if (! depth || (gimp_coords_bezier_is_straight (beziercoords, precision) && gimp_coords_length_squared (&point1) < precision && gimp_coords_length_squared (&point2) < precision)) { GimpCoords line, dcoord; gdouble length2, scalar; gint i; gimp_coords_difference (&(beziercoords[3]), &(beziercoords[0]), &line); gimp_coords_difference (coord, &(beziercoords[0]), &dcoord); length2 = gimp_coords_scalarprod (&line, &line); scalar = gimp_coords_scalarprod (&line, &dcoord) / length2; scalar = CLAMP (scalar, 0.0, 1.0); /* lines look the same as bezier curves where the handles * sit on the anchors, however, they are parametrized * differently. Hence we have to do some weird approximation. */ pos1 = pos2 = 0.5; for (i = 0; i <= 15; i++) { pos2 *= 0.5; if (3 * pos1 * pos1 * (1-pos1) + pos1 * pos1 * pos1 < scalar) pos1 += pos2; else pos1 -= pos2; } *ret_pos = pos1; gimp_coords_mix (1.0, &(beziercoords[0]), scalar, &line, ret_point); gimp_coords_difference (coord, ret_point, &dcoord); return gimp_coords_length (&dcoord); } /* ok, we have to subdivide */ subdivided[0] = beziercoords[0]; subdivided[6] = beziercoords[3]; /* if (!depth) g_printerr ("Hit recursion depth limit!\n"); */ gimp_coords_average (&(beziercoords[0]), &(beziercoords[1]), &(subdivided[1])); gimp_coords_average (&(beziercoords[1]), &(beziercoords[2]), &(subdivided[7])); gimp_coords_average (&(beziercoords[2]), &(beziercoords[3]), &(subdivided[5])); gimp_coords_average (&(subdivided[1]), &(subdivided[7]), &(subdivided[2])); gimp_coords_average (&(subdivided[7]), &(subdivided[5]), &(subdivided[4])); gimp_coords_average (&(subdivided[2]), &(subdivided[4]), &(subdivided[3])); /* * We now have the coordinates of the two bezier segments in * subdivided [0-3] and subdivided [3-6] */ dist1 = gimp_bezier_stroke_segment_nearest_point_get (&(subdivided[0]), coord, precision, &point1, &pos1, depth - 1); dist2 = gimp_bezier_stroke_segment_nearest_point_get (&(subdivided[3]), coord, precision, &point2, &pos2, depth - 1); if (dist1 <= dist2) { *ret_point = point1; *ret_pos = 0.5 * pos1; return dist1; } else { *ret_point = point2; *ret_pos = 0.5 + 0.5 * pos2; return dist2; } } static gdouble gimp_bezier_stroke_nearest_tangent_get (GimpStroke *stroke, const GimpCoords *coord1, const GimpCoords *coord2, gdouble precision, GimpCoords *nearest, GimpAnchor **ret_segment_start, GimpAnchor **ret_segment_end, gdouble *ret_pos) { gdouble min_dist, dist, pos; GimpCoords point; GimpCoords segmentcoords[4]; GList *anchorlist; GimpAnchor *segment_start; GimpAnchor *segment_end = NULL; GimpAnchor *anchor; gint count; if (g_queue_is_empty (stroke->anchors)) return -1.0; count = 0; min_dist = -1; for (anchorlist = stroke->anchors->head; GIMP_ANCHOR (anchorlist->data)->type != GIMP_ANCHOR_ANCHOR; anchorlist = g_list_next (anchorlist)); segment_start = anchorlist->data; for ( ; anchorlist; anchorlist = g_list_next (anchorlist)) { anchor = anchorlist->data; segmentcoords[count] = anchor->position; count++; if (count == 4) { segment_end = anchorlist->data; dist = gimp_bezier_stroke_segment_nearest_tangent_get (segmentcoords, coord1, coord2, precision, &point, &pos); if (dist >= 0 && (dist < min_dist || min_dist < 0)) { min_dist = dist; if (ret_pos) *ret_pos = pos; if (nearest) *nearest = point; if (ret_segment_start) *ret_segment_start = segment_start; if (ret_segment_end) *ret_segment_end = segment_end; } segment_start = anchorlist->data; segmentcoords[0] = segmentcoords[3]; count = 1; } } if (stroke->closed && ! g_queue_is_empty (stroke->anchors)) { anchorlist = stroke->anchors->head; while (count < 3) { segmentcoords[count] = GIMP_ANCHOR (anchorlist->data)->position; count++; } anchorlist = g_list_next (anchorlist); if (anchorlist) { segment_end = GIMP_ANCHOR (anchorlist->data); segmentcoords[3] = segment_end->position; } dist = gimp_bezier_stroke_segment_nearest_tangent_get (segmentcoords, coord1, coord2, precision, &point, &pos); if (dist >= 0 && (dist < min_dist || min_dist < 0)) { min_dist = dist; if (ret_pos) *ret_pos = pos; if (nearest) *nearest = point; if (ret_segment_start) *ret_segment_start = segment_start; if (ret_segment_end) *ret_segment_end = segment_end; } } return min_dist; } static gdouble gimp_bezier_stroke_segment_nearest_tangent_get (const GimpCoords *beziercoords, const GimpCoords *coord1, const GimpCoords *coord2, gdouble precision, GimpCoords *ret_point, gdouble *ret_pos) { GArray *ret_coords; GArray *ret_params; GimpCoords dir, line, dcoord, min_point; gdouble min_dist = -1; gdouble dist, length2, scalar, ori, ori2; gint i; gimp_coords_difference (coord2, coord1, &line); ret_coords = g_array_new (FALSE, FALSE, sizeof (GimpCoords)); ret_params = g_array_new (FALSE, FALSE, sizeof (gdouble)); g_printerr ("(%.2f, %.2f)-(%.2f,%.2f): ", coord1->x, coord1->y, coord2->x, coord2->y); gimp_coords_interpolate_bezier (beziercoords, precision, ret_coords, ret_params); g_return_val_if_fail (ret_coords->len == ret_params->len, -1.0); if (ret_coords->len < 2) return -1; gimp_coords_difference (&g_array_index (ret_coords, GimpCoords, 1), &g_array_index (ret_coords, GimpCoords, 0), &dir); ori = dir.x * line.y - dir.y * line.x; for (i = 2; i < ret_coords->len; i++) { gimp_coords_difference (&g_array_index (ret_coords, GimpCoords, i), &g_array_index (ret_coords, GimpCoords, i-1), &dir); ori2 = dir.x * line.y - dir.y * line.x; if (ori * ori2 <= 0) { gimp_coords_difference (&g_array_index (ret_coords, GimpCoords, i), coord1, &dcoord); length2 = gimp_coords_scalarprod (&line, &line); scalar = gimp_coords_scalarprod (&line, &dcoord) / length2; if (scalar >= 0 && scalar <= 1) { gimp_coords_mix (1.0, coord1, scalar, &line, &min_point); gimp_coords_difference (&min_point, &g_array_index (ret_coords, GimpCoords, i), &dcoord); dist = gimp_coords_length (&dcoord); if (dist < min_dist || min_dist < 0) { min_dist = dist; *ret_point = g_array_index (ret_coords, GimpCoords, i); *ret_pos = g_array_index (ret_params, gdouble, i); } } } ori = ori2; } if (min_dist < 0) g_printerr ("-\n"); else g_printerr ("%f: (%.2f, %.2f) /%.3f/\n", min_dist, (*ret_point).x, (*ret_point).y, *ret_pos); g_array_free (ret_coords, TRUE); g_array_free (ret_params, TRUE); return min_dist; } static gboolean gimp_bezier_stroke_is_extendable (GimpStroke *stroke, GimpAnchor *neighbor) { GList *listneighbor; gint loose_end; if (stroke->closed) return FALSE; if (g_queue_is_empty (stroke->anchors)) return TRUE; /* assure that there is a neighbor specified */ g_return_val_if_fail (neighbor != NULL, FALSE); loose_end = 0; listneighbor = stroke->anchors->tail; /* Check if the neighbor is at an end of the control points */ if (listneighbor->data == neighbor) { loose_end = 1; } else { listneighbor = g_list_first (stroke->anchors->head); if (listneighbor->data == neighbor) { loose_end = -1; } else { /* * It isn't. If we are on a handle go to the nearest * anchor and see if we can find an end from it. * Yes, this is tedious. */ listneighbor = g_queue_find (stroke->anchors, neighbor); if (listneighbor && neighbor->type == GIMP_ANCHOR_CONTROL) { if (listneighbor->prev && GIMP_ANCHOR (listneighbor->prev->data)->type == GIMP_ANCHOR_ANCHOR) { listneighbor = listneighbor->prev; } else if (listneighbor->next && GIMP_ANCHOR (listneighbor->next->data)->type == GIMP_ANCHOR_ANCHOR) { listneighbor = listneighbor->next; } else { loose_end = 0; listneighbor = NULL; } } if (listneighbor) /* we found a suitable ANCHOR_ANCHOR now, lets * search for its loose end. */ { if (listneighbor->prev && listneighbor->prev->prev == NULL) { loose_end = -1; } else if (listneighbor->next && listneighbor->next->next == NULL) { loose_end = 1; } } } } return (loose_end != 0); } GimpAnchor * gimp_bezier_stroke_extend (GimpStroke *stroke, const GimpCoords *coords, GimpAnchor *neighbor, GimpVectorExtendMode extend_mode) { GimpAnchor *anchor = NULL; GList *listneighbor; gint loose_end, control_count; if (g_queue_is_empty (stroke->anchors)) { /* assure that there is no neighbor specified */ g_return_val_if_fail (neighbor == NULL, NULL); anchor = gimp_anchor_new (GIMP_ANCHOR_CONTROL, coords); g_queue_push_tail (stroke->anchors, anchor); switch (extend_mode) { case EXTEND_SIMPLE: break; case EXTEND_EDITABLE: anchor = gimp_bezier_stroke_extend (stroke, coords, anchor, EXTEND_SIMPLE); /* we return the GIMP_ANCHOR_ANCHOR */ gimp_bezier_stroke_extend (stroke, coords, anchor, EXTEND_SIMPLE); break; default: anchor = NULL; } return anchor; } else { /* assure that there is a neighbor specified */ g_return_val_if_fail (neighbor != NULL, NULL); loose_end = 0; listneighbor = stroke->anchors->tail; /* Check if the neighbor is at an end of the control points */ if (listneighbor->data == neighbor) { loose_end = 1; } else { listneighbor = stroke->anchors->head; if (listneighbor->data == neighbor) { loose_end = -1; } else { /* * It isn't. If we are on a handle go to the nearest * anchor and see if we can find an end from it. * Yes, this is tedious. */ listneighbor = g_queue_find (stroke->anchors, neighbor); if (listneighbor && neighbor->type == GIMP_ANCHOR_CONTROL) { if (listneighbor->prev && GIMP_ANCHOR (listneighbor->prev->data)->type == GIMP_ANCHOR_ANCHOR) { listneighbor = listneighbor->prev; } else if (listneighbor->next && GIMP_ANCHOR (listneighbor->next->data)->type == GIMP_ANCHOR_ANCHOR) { listneighbor = listneighbor->next; } else { loose_end = 0; listneighbor = NULL; } } if (listneighbor) /* we found a suitable ANCHOR_ANCHOR now, lets * search for its loose end. */ { if (listneighbor->next && listneighbor->next->next == NULL) { loose_end = 1; listneighbor = listneighbor->next; } else if (listneighbor->prev && listneighbor->prev->prev == NULL) { loose_end = -1; listneighbor = listneighbor->prev; } } } } if (loose_end) { GimpAnchorType type; /* We have to detect the type of the point to add... */ control_count = 0; if (loose_end == 1) { while (listneighbor && GIMP_ANCHOR (listneighbor->data)->type == GIMP_ANCHOR_CONTROL) { control_count++; listneighbor = listneighbor->prev; } } else { while (listneighbor && GIMP_ANCHOR (listneighbor->data)->type == GIMP_ANCHOR_CONTROL) { control_count++; listneighbor = listneighbor->next; } } switch (extend_mode) { case EXTEND_SIMPLE: switch (control_count) { case 0: type = GIMP_ANCHOR_CONTROL; break; case 1: if (listneighbor) /* only one handle in the path? */ type = GIMP_ANCHOR_CONTROL; else type = GIMP_ANCHOR_ANCHOR; break; case 2: type = GIMP_ANCHOR_ANCHOR; break; default: g_warning ("inconsistent bezier curve: " "%d successive control handles", control_count); type = GIMP_ANCHOR_ANCHOR; } anchor = gimp_anchor_new (type, coords); if (loose_end == 1) g_queue_push_tail (stroke->anchors, anchor); if (loose_end == -1) g_queue_push_head (stroke->anchors, anchor); break; case EXTEND_EDITABLE: switch (control_count) { case 0: neighbor = gimp_bezier_stroke_extend (stroke, &(neighbor->position), neighbor, EXTEND_SIMPLE); case 1: neighbor = gimp_bezier_stroke_extend (stroke, coords, neighbor, EXTEND_SIMPLE); case 2: anchor = gimp_bezier_stroke_extend (stroke, coords, neighbor, EXTEND_SIMPLE); neighbor = gimp_bezier_stroke_extend (stroke, coords, anchor, EXTEND_SIMPLE); break; default: g_warning ("inconsistent bezier curve: " "%d successive control handles", control_count); } } return anchor; } return NULL; } } static gboolean gimp_bezier_stroke_connect_stroke (GimpStroke *stroke, GimpAnchor *anchor, GimpStroke *extension, GimpAnchor *neighbor) { GList *list1; GList *list2; list1 = g_queue_find (stroke->anchors, anchor); list1 = gimp_bezier_stroke_get_anchor_listitem (list1); list2 = g_queue_find (extension->anchors, neighbor); list2 = gimp_bezier_stroke_get_anchor_listitem (list2); g_return_val_if_fail (list1 != NULL && list2 != NULL, FALSE); if (stroke == extension) { g_return_val_if_fail ((list1->prev && list1->prev->prev == NULL && list2->next && list2->next->next == NULL) || (list1->next && list1->next->next == NULL && list2->prev && list2->prev->prev == NULL), FALSE); gimp_stroke_close (stroke); return TRUE; } if (list1->prev && list1->prev->prev == NULL) { g_queue_reverse (stroke->anchors); } g_return_val_if_fail (list1->next && list1->next->next == NULL, FALSE); if (list2->next && list2->next->next == NULL) { g_queue_reverse (extension->anchors); } g_return_val_if_fail (list2->prev && list2->prev->prev == NULL, FALSE); for (list1 = extension->anchors->head; list1; list1 = g_list_next (list1)) g_queue_push_tail (stroke->anchors, list1->data); g_queue_clear (extension->anchors); return TRUE; } static void gimp_bezier_stroke_anchor_move_relative (GimpStroke *stroke, GimpAnchor *anchor, const GimpCoords *deltacoord, GimpAnchorFeatureType feature) { GimpCoords delta, coord1, coord2; GList *anchor_list; delta = *deltacoord; delta.pressure = 0; delta.xtilt = 0; delta.ytilt = 0; delta.wheel = 0; gimp_coords_add (&(anchor->position), &delta, &coord1); anchor->position = coord1; anchor_list = g_queue_find (stroke->anchors, anchor); g_return_if_fail (anchor_list != NULL); if (anchor->type == GIMP_ANCHOR_ANCHOR) { if (g_list_previous (anchor_list)) { coord2 = GIMP_ANCHOR (g_list_previous (anchor_list)->data)->position; gimp_coords_add (&coord2, &delta, &coord1); GIMP_ANCHOR (g_list_previous (anchor_list)->data)->position = coord1; } if (g_list_next (anchor_list)) { coord2 = GIMP_ANCHOR (g_list_next (anchor_list)->data)->position; gimp_coords_add (&coord2, &delta, &coord1); GIMP_ANCHOR (g_list_next (anchor_list)->data)->position = coord1; } } else { if (feature == GIMP_ANCHOR_FEATURE_SYMMETRIC) { GList *neighbour = NULL, *opposite = NULL; /* search for opposite control point. Sigh. */ neighbour = g_list_previous (anchor_list); if (neighbour && GIMP_ANCHOR (neighbour->data)->type == GIMP_ANCHOR_ANCHOR) { opposite = g_list_previous (neighbour); } else { neighbour = g_list_next (anchor_list); if (neighbour && GIMP_ANCHOR (neighbour->data)->type == GIMP_ANCHOR_ANCHOR) { opposite = g_list_next (neighbour); } } if (opposite && GIMP_ANCHOR (opposite->data)->type == GIMP_ANCHOR_CONTROL) { gimp_coords_difference (&(GIMP_ANCHOR (neighbour->data)->position), &(anchor->position), &delta); gimp_coords_add (&(GIMP_ANCHOR (neighbour->data)->position), &delta, &coord1); GIMP_ANCHOR (opposite->data)->position = coord1; } } } } static void gimp_bezier_stroke_anchor_move_absolute (GimpStroke *stroke, GimpAnchor *anchor, const GimpCoords *coord, GimpAnchorFeatureType feature) { GimpCoords deltacoord; gimp_coords_difference (coord, &anchor->position, &deltacoord); gimp_bezier_stroke_anchor_move_relative (stroke, anchor, &deltacoord, feature); } static void gimp_bezier_stroke_anchor_convert (GimpStroke *stroke, GimpAnchor *anchor, GimpAnchorFeatureType feature) { GList *anchor_list; anchor_list = g_queue_find (stroke->anchors, anchor); g_return_if_fail (anchor_list != NULL); switch (feature) { case GIMP_ANCHOR_FEATURE_EDGE: if (anchor->type == GIMP_ANCHOR_ANCHOR) { if (g_list_previous (anchor_list)) GIMP_ANCHOR (g_list_previous (anchor_list)->data)->position = anchor->position; if (g_list_next (anchor_list)) GIMP_ANCHOR (g_list_next (anchor_list)->data)->position = anchor->position; } else { if (g_list_previous (anchor_list) && GIMP_ANCHOR (g_list_previous (anchor_list)->data)->type == GIMP_ANCHOR_ANCHOR) anchor->position = GIMP_ANCHOR (g_list_previous (anchor_list)->data)->position; if (g_list_next (anchor_list) && GIMP_ANCHOR (g_list_next (anchor_list)->data)->type == GIMP_ANCHOR_ANCHOR) anchor->position = GIMP_ANCHOR (g_list_next (anchor_list)->data)->position; } break; default: g_warning ("gimp_bezier_stroke_anchor_convert: " "unimplemented anchor conversion %d\n", feature); } } static GimpBezierDesc * gimp_bezier_stroke_make_bezier (GimpStroke *stroke) { GArray *points; GArray *cmd_array; GimpBezierDesc *bezdesc; cairo_path_data_t pathdata; gint num_cmds, i; points = gimp_stroke_control_points_get (stroke, NULL); g_return_val_if_fail (points && points->len % 3 == 0, NULL); if (points->len < 3) return NULL; /* Moveto + (n-1) * curveto + (if closed) curveto + closepath */ num_cmds = 2 + (points->len / 3 - 1) * 4; if (stroke->closed) num_cmds += 1 + 4; cmd_array = g_array_sized_new (FALSE, FALSE, sizeof (cairo_path_data_t), num_cmds); pathdata.header.type = CAIRO_PATH_MOVE_TO; pathdata.header.length = 2; g_array_append_val (cmd_array, pathdata); pathdata.point.x = g_array_index (points, GimpAnchor, 1).position.x; pathdata.point.y = g_array_index (points, GimpAnchor, 1).position.y; g_array_append_val (cmd_array, pathdata); for (i = 2; i+2 < points->len; i += 3) { pathdata.header.type = CAIRO_PATH_CURVE_TO; pathdata.header.length = 4; g_array_append_val (cmd_array, pathdata); pathdata.point.x = g_array_index (points, GimpAnchor, i).position.x; pathdata.point.y = g_array_index (points, GimpAnchor, i).position.y; g_array_append_val (cmd_array, pathdata); pathdata.point.x = g_array_index (points, GimpAnchor, i+1).position.x; pathdata.point.y = g_array_index (points, GimpAnchor, i+1).position.y; g_array_append_val (cmd_array, pathdata); pathdata.point.x = g_array_index (points, GimpAnchor, i+2).position.x; pathdata.point.y = g_array_index (points, GimpAnchor, i+2).position.y; g_array_append_val (cmd_array, pathdata); } if (stroke->closed) { pathdata.header.type = CAIRO_PATH_CURVE_TO; pathdata.header.length = 4; g_array_append_val (cmd_array, pathdata); pathdata.point.x = g_array_index (points, GimpAnchor, i).position.x; pathdata.point.y = g_array_index (points, GimpAnchor, i).position.y; g_array_append_val (cmd_array, pathdata); pathdata.point.x = g_array_index (points, GimpAnchor, 0).position.x; pathdata.point.y = g_array_index (points, GimpAnchor, 0).position.y; g_array_append_val (cmd_array, pathdata); pathdata.point.x = g_array_index (points, GimpAnchor, 1).position.x; pathdata.point.y = g_array_index (points, GimpAnchor, 1).position.y; g_array_append_val (cmd_array, pathdata); pathdata.header.type = CAIRO_PATH_CLOSE_PATH; pathdata.header.length = 1; g_array_append_val (cmd_array, pathdata); } if (cmd_array->len != num_cmds) g_printerr ("miscalculated path cmd length! (%d vs. %d)\n", cmd_array->len, num_cmds); bezdesc = gimp_bezier_desc_new ((cairo_path_data_t *) cmd_array->data, cmd_array->len); g_array_free (points, TRUE); g_array_free (cmd_array, FALSE); return bezdesc; } static GArray * gimp_bezier_stroke_interpolate (GimpStroke *stroke, gdouble precision, gboolean *ret_closed) { GArray *ret_coords; GimpAnchor *anchor; GList *anchorlist; GimpCoords segmentcoords[4]; gint count; gboolean need_endpoint = FALSE; if (g_queue_is_empty (stroke->anchors)) { if (ret_closed) *ret_closed = FALSE; return NULL; } ret_coords = g_array_new (FALSE, FALSE, sizeof (GimpCoords)); count = 0; for (anchorlist = stroke->anchors->head; anchorlist && GIMP_ANCHOR (anchorlist->data)->type != GIMP_ANCHOR_ANCHOR; anchorlist = g_list_next (anchorlist)); for ( ; anchorlist; anchorlist = g_list_next (anchorlist)) { anchor = anchorlist->data; segmentcoords[count] = anchor->position; count++; if (count == 4) { gimp_coords_interpolate_bezier (segmentcoords, precision, ret_coords, NULL); segmentcoords[0] = segmentcoords[3]; count = 1; need_endpoint = TRUE; } } if (stroke->closed && ! g_queue_is_empty (stroke->anchors)) { anchorlist = stroke->anchors->head; while (count < 3) { segmentcoords[count] = GIMP_ANCHOR (anchorlist->data)->position; count++; } anchorlist = g_list_next (anchorlist); if (anchorlist) segmentcoords[3] = GIMP_ANCHOR (anchorlist->data)->position; gimp_coords_interpolate_bezier (segmentcoords, precision, ret_coords, NULL); need_endpoint = TRUE; } if (need_endpoint) ret_coords = g_array_append_val (ret_coords, segmentcoords[3]); if (ret_closed) *ret_closed = stroke->closed; if (ret_coords->len == 0) { g_array_free (ret_coords, TRUE); ret_coords = NULL; } return ret_coords; } static void gimp_bezier_stroke_transform (GimpStroke *stroke, const GimpMatrix3 *matrix, GQueue *ret_strokes) { GimpStroke *first_stroke = NULL; GimpStroke *last_stroke = NULL; GList *anchorlist; GimpAnchor *anchor; GimpCoords segmentcoords[4]; GQueue *transformed[2]; gint n_transformed; gint count; gboolean first; gboolean last; /* if there's no need for clipping, use the default implementation */ if (! ret_strokes || gimp_matrix3_is_affine (matrix) || g_queue_is_empty (stroke->anchors)) { GIMP_STROKE_CLASS (parent_class)->transform (stroke, matrix, ret_strokes); return; } /* transform the individual segments */ count = 0; first = TRUE; last = FALSE; /* find the first non-control anchor */ for (anchorlist = stroke->anchors->head; anchorlist && GIMP_ANCHOR (anchorlist->data)->type != GIMP_ANCHOR_ANCHOR; anchorlist = g_list_next (anchorlist)); for ( ; anchorlist || stroke->closed; anchorlist = g_list_next (anchorlist)) { /* wrap around if 'stroke' is closed, so that we transform the final * segment */ if (! anchorlist) { anchorlist = stroke->anchors->head; last = TRUE; } anchor = anchorlist->data; segmentcoords[count] = anchor->position; count++; if (count == 4) { gboolean start_in; gboolean end_in; gint i; gimp_transform_bezier_coords (matrix, segmentcoords, transformed, &n_transformed, &start_in, &end_in); for (i = 0; i < n_transformed; i++) { GimpStroke *s = NULL; GList *list; gint j; if (i == 0 && start_in) { /* current stroke is connected to last stroke */ s = last_stroke; } else if (last_stroke) { /* current stroke is not connected to last stroke. finalize * last stroke. */ anchor = g_queue_peek_tail (last_stroke->anchors); g_queue_push_tail (last_stroke->anchors, gimp_anchor_new (GIMP_ANCHOR_CONTROL, &anchor->position)); } for (list = transformed[i]->head; list; list = g_list_next (list)) { GimpCoords *transformedcoords = list->data; if (! s) { /* start a new stroke */ s = gimp_bezier_stroke_new (); g_queue_push_tail (s->anchors, gimp_anchor_new (GIMP_ANCHOR_CONTROL, &transformedcoords[0])); g_queue_push_tail (ret_strokes, s); j = 0; } else { /* continue an existing stroke, skipping the first anchor, * which is the same as the last anchor of the last stroke */ j = 1; } for (; j < 4; j++) { GimpAnchorType type; if (j == 0 || j == 3) type = GIMP_ANCHOR_ANCHOR; else type = GIMP_ANCHOR_CONTROL; g_queue_push_tail (s->anchors, gimp_anchor_new (type, &transformedcoords[j])); } g_free (transformedcoords); } g_queue_free (transformed[i]); /* if the current stroke is an initial segment of 'stroke', * remember it, so that we can possibly connect it to the last * stroke later. */ if (i == 0 && start_in && first) first_stroke = s; last_stroke = s; first = FALSE; } if (! end_in && last_stroke) { /* the next stroke is not connected to the last stroke. finalize * the last stroke. */ anchor = g_queue_peek_tail (last_stroke->anchors); g_queue_push_tail (last_stroke->anchors, gimp_anchor_new (GIMP_ANCHOR_CONTROL, &anchor->position)); last_stroke = NULL; } if (last) break; segmentcoords[0] = segmentcoords[3]; count = 1; } } /* if the last stroke is a final segment of 'stroke'... */ if (last_stroke) { /* ... and the first stroke is an initial segment of 'stroke', and * 'stroke' is closed ... */ if (first_stroke && stroke->closed) { /* connect the first and last strokes */ /* remove the first anchor, which is a synthetic control point */ gimp_anchor_free (g_queue_pop_head (first_stroke->anchors)); /* remove the last anchor, which is the same anchor point as the * first anchor */ gimp_anchor_free (g_queue_pop_tail (last_stroke->anchors)); if (first_stroke == last_stroke) { /* the result is a single stroke. move the last anchor, which is * an orphan control point, to the front, to fill in the removed * control point of the first anchor, and close the stroke. */ g_queue_push_head (first_stroke->anchors, g_queue_pop_tail (first_stroke->anchors)); first_stroke->closed = TRUE; } else { /* the result is multiple strokes. prepend the last stroke to * the first stroke, and discard it. */ while ((anchor = g_queue_pop_tail (last_stroke->anchors))) g_queue_push_head (first_stroke->anchors, anchor); g_object_unref (g_queue_pop_tail (ret_strokes)); } } else { /* otherwise, the first and last strokes are not connected. finalize * the last stroke. */ anchor = g_queue_peek_tail (last_stroke->anchors); g_queue_push_tail (last_stroke->anchors, gimp_anchor_new (GIMP_ANCHOR_CONTROL, &anchor->position)); } } } GimpStroke * gimp_bezier_stroke_new_moveto (const GimpCoords *start) { GimpStroke *stroke = gimp_bezier_stroke_new (); g_queue_push_tail (stroke->anchors, gimp_anchor_new (GIMP_ANCHOR_CONTROL, start)); g_queue_push_tail (stroke->anchors, gimp_anchor_new (GIMP_ANCHOR_ANCHOR, start)); g_queue_push_tail (stroke->anchors, gimp_anchor_new (GIMP_ANCHOR_CONTROL, start)); return stroke; } void gimp_bezier_stroke_lineto (GimpStroke *stroke, const GimpCoords *end) { g_return_if_fail (GIMP_IS_BEZIER_STROKE (stroke)); g_return_if_fail (stroke->closed == FALSE); g_return_if_fail (g_queue_is_empty (stroke->anchors) == FALSE); g_queue_push_tail (stroke->anchors, gimp_anchor_new (GIMP_ANCHOR_CONTROL, end)); g_queue_push_tail (stroke->anchors, gimp_anchor_new (GIMP_ANCHOR_ANCHOR, end)); g_queue_push_tail (stroke->anchors, gimp_anchor_new (GIMP_ANCHOR_CONTROL, end)); } void gimp_bezier_stroke_conicto (GimpStroke *stroke, const GimpCoords *control, const GimpCoords *end) { GimpCoords start, coords; g_return_if_fail (GIMP_IS_BEZIER_STROKE (stroke)); g_return_if_fail (stroke->closed == FALSE); g_return_if_fail (g_queue_get_length (stroke->anchors) > 1); start = GIMP_ANCHOR (stroke->anchors->tail->prev->data)->position; gimp_coords_mix (2.0 / 3.0, control, 1.0 / 3.0, &start, &coords); GIMP_ANCHOR (stroke->anchors->tail->data)->position = coords; gimp_coords_mix (2.0 / 3.0, control, 1.0 / 3.0, end, &coords); g_queue_push_tail (stroke->anchors, gimp_anchor_new (GIMP_ANCHOR_CONTROL, &coords)); g_queue_push_tail (stroke->anchors, gimp_anchor_new (GIMP_ANCHOR_ANCHOR, end)); g_queue_push_tail (stroke->anchors, gimp_anchor_new (GIMP_ANCHOR_CONTROL, end)); } void gimp_bezier_stroke_cubicto (GimpStroke *stroke, const GimpCoords *control1, const GimpCoords *control2, const GimpCoords *end) { g_return_if_fail (GIMP_IS_BEZIER_STROKE (stroke)); g_return_if_fail (stroke->closed == FALSE); g_return_if_fail (g_queue_is_empty (stroke->anchors) == FALSE); GIMP_ANCHOR (stroke->anchors->tail->data)->position = *control1; g_queue_push_tail (stroke->anchors, gimp_anchor_new (GIMP_ANCHOR_CONTROL, control2)); g_queue_push_tail (stroke->anchors, gimp_anchor_new (GIMP_ANCHOR_ANCHOR, end)); g_queue_push_tail (stroke->anchors, gimp_anchor_new (GIMP_ANCHOR_CONTROL, end)); } static gdouble arcto_circleparam (gdouble h, gdouble *y) { gdouble t0 = 0.5; gdouble dt = 0.25; gdouble pt0; gdouble y01, y12, y23, y012, y123, y0123; /* subdividing y[] */ while (dt >= 0.00001) { pt0 = ( y[0] * (1-t0) * (1-t0) * (1-t0) + 3 * y[1] * (1-t0) * (1-t0) * t0 + 3 * y[2] * (1-t0) * t0 * t0 + y[3] * t0 * t0 * t0 ); if (pt0 > h) t0 = t0 - dt; else if (pt0 < h) t0 = t0 + dt; else break; dt = dt/2; } y01 = y[0] * (1-t0) + y[1] * t0; y12 = y[1] * (1-t0) + y[2] * t0; y23 = y[2] * (1-t0) + y[3] * t0; y012 = y01 * (1-t0) + y12 * t0; y123 = y12 * (1-t0) + y23 * t0; y0123 = y012 * (1-t0) + y123 * t0; y[0] = y0123; y[1] = y123; y[2] = y23; /* y[3] unchanged */ return t0; } static void arcto_subdivide (gdouble t, gint part, GimpCoords *p) { GimpCoords p01, p12, p23, p012, p123, p0123; gimp_coords_mix (1-t, &(p[0]), t, &(p[1]), &p01 ); gimp_coords_mix (1-t, &(p[1]), t, &(p[2]), &p12 ); gimp_coords_mix (1-t, &(p[2]), t, &(p[3]), &p23 ); gimp_coords_mix (1-t, &p01 , t, &p12 , &p012 ); gimp_coords_mix (1-t, &p12 , t, &p23 , &p123 ); gimp_coords_mix (1-t, &p012 , t, &p123 , &p0123); if (part == 0) { /* p[0] unchanged */ p[1] = p01; p[2] = p012; p[3] = p0123; } else { p[0] = p0123; p[1] = p123; p[2] = p23; /* p[3] unchanged */ } } static void arcto_ellipsesegment (gdouble radius_x, gdouble radius_y, gdouble phi0, gdouble phi1, GimpCoords *ellips) { const GimpCoords template = GIMP_COORDS_DEFAULT_VALUES; const gdouble circlemagic = 4.0 * (G_SQRT2 - 1.0) / 3.0; gdouble phi_s, phi_e; gdouble y[4]; gdouble h0, h1; gdouble t0, t1; g_return_if_fail (ellips != NULL); y[0] = 0.0; y[1] = circlemagic; y[2] = 1.0; y[3] = 1.0; ellips[0] = template; ellips[1] = template; ellips[2] = template; ellips[3] = template; if (phi0 < phi1) { phi_s = floor (phi0 / G_PI_2) * G_PI_2; while (phi_s < 0) phi_s += 2 * G_PI; phi_e = phi_s + G_PI_2; } else { phi_e = floor (phi1 / G_PI_2) * G_PI_2; while (phi_e < 0) phi_e += 2 * G_PI; phi_s = phi_e + G_PI_2; } h0 = sin (fabs (phi0-phi_s)); h1 = sin (fabs (phi1-phi_s)); ellips[0].x = cos (phi_s); ellips[0].y = sin (phi_s); ellips[3].x = cos (phi_e); ellips[3].y = sin (phi_e); gimp_coords_mix (1, &(ellips[0]), circlemagic, &(ellips[3]), &(ellips[1])); gimp_coords_mix (circlemagic, &(ellips[0]), 1, &(ellips[3]), &(ellips[2])); if (h0 > y[0]) { t0 = arcto_circleparam (h0, y); /* also subdivides y[] at t0 */ arcto_subdivide (t0, 1, ellips); } if (h1 < y[3]) { t1 = arcto_circleparam (h1, y); arcto_subdivide (t1, 0, ellips); } ellips[0].x *= radius_x ; ellips[0].y *= radius_y; ellips[1].x *= radius_x ; ellips[1].y *= radius_y; ellips[2].x *= radius_x ; ellips[2].y *= radius_y; ellips[3].x *= radius_x ; ellips[3].y *= radius_y; } void gimp_bezier_stroke_arcto (GimpStroke *bez_stroke, gdouble radius_x, gdouble radius_y, gdouble angle_rad, gboolean large_arc, gboolean sweep, const GimpCoords *end) { GimpCoords start; GimpCoords middle; /* between start and end */ GimpCoords trans_delta; GimpCoords trans_center; GimpCoords tmp_center; GimpCoords center; GimpCoords ellips[4]; /* control points of untransformed ellipse segment */ GimpCoords ctrl[4]; /* control points of next bezier segment */ GimpMatrix3 anglerot; gdouble lambda; gdouble phi0, phi1, phi2; gdouble tmpx, tmpy; g_return_if_fail (GIMP_IS_BEZIER_STROKE (bez_stroke)); g_return_if_fail (bez_stroke->closed == FALSE); g_return_if_fail (g_queue_get_length (bez_stroke->anchors) > 1); if (radius_x == 0 || radius_y == 0) { gimp_bezier_stroke_lineto (bez_stroke, end); return; } start = GIMP_ANCHOR (bez_stroke->anchors->tail->prev->data)->position; gimp_matrix3_identity (&anglerot); gimp_matrix3_rotate (&anglerot, -angle_rad); gimp_coords_mix (0.5, &start, -0.5, end, &trans_delta); gimp_matrix3_transform_point (&anglerot, trans_delta.x, trans_delta.y, &tmpx, &tmpy); trans_delta.x = tmpx; trans_delta.y = tmpy; lambda = (SQR (trans_delta.x) / SQR (radius_x) + SQR (trans_delta.y) / SQR (radius_y)); if (lambda < 0.00001) { /* don't bother with it - endpoint is too close to startpoint */ return; } trans_center = trans_delta; if (lambda > 1.0) { /* The radii are too small for a matching ellipse. We expand them * so that they fit exactly (center of the ellipse between the * start- and endpoint */ radius_x *= sqrt (lambda); radius_y *= sqrt (lambda); trans_center.x = 0.0; trans_center.y = 0.0; } else { gdouble factor = sqrt ((1.0 - lambda) / lambda); trans_center.x = trans_delta.y * radius_x / radius_y * factor; trans_center.y = - trans_delta.x * radius_y / radius_x * factor; } if ((large_arc && sweep) || (!large_arc && !sweep)) { trans_center.x *= -1; trans_center.y *= -1; } gimp_matrix3_identity (&anglerot); gimp_matrix3_rotate (&anglerot, angle_rad); tmp_center = trans_center; gimp_matrix3_transform_point (&anglerot, tmp_center.x, tmp_center.y, &tmpx, &tmpy); tmp_center.x = tmpx; tmp_center.y = tmpy; gimp_coords_mix (0.5, &start, 0.5, end, &middle); gimp_coords_add (&tmp_center, &middle, ¢er); phi1 = atan2 ((trans_delta.y - trans_center.y) / radius_y, (trans_delta.x - trans_center.x) / radius_x); phi2 = atan2 ((- trans_delta.y - trans_center.y) / radius_y, (- trans_delta.x - trans_center.x) / radius_x); if (phi1 < 0) phi1 += 2 * G_PI; if (phi2 < 0) phi2 += 2 * G_PI; if (sweep) { while (phi2 < phi1) phi2 += 2 * G_PI; phi0 = floor (phi1 / G_PI_2) * G_PI_2; while (phi0 < phi2) { arcto_ellipsesegment (radius_x, radius_y, MAX (phi0, phi1), MIN (phi0 + G_PI_2, phi2), ellips); gimp_matrix3_transform_point (&anglerot, ellips[0].x, ellips[0].y, &tmpx, &tmpy); ellips[0].x = tmpx; ellips[0].y = tmpy; gimp_matrix3_transform_point (&anglerot, ellips[1].x, ellips[1].y, &tmpx, &tmpy); ellips[1].x = tmpx; ellips[1].y = tmpy; gimp_matrix3_transform_point (&anglerot, ellips[2].x, ellips[2].y, &tmpx, &tmpy); ellips[2].x = tmpx; ellips[2].y = tmpy; gimp_matrix3_transform_point (&anglerot, ellips[3].x, ellips[3].y, &tmpx, &tmpy); ellips[3].x = tmpx; ellips[3].y = tmpy; gimp_coords_add (¢er, &(ellips[1]), &(ctrl[1])); gimp_coords_add (¢er, &(ellips[2]), &(ctrl[2])); gimp_coords_add (¢er, &(ellips[3]), &(ctrl[3])); gimp_bezier_stroke_cubicto (bez_stroke, &(ctrl[1]), &(ctrl[2]), &(ctrl[3])); phi0 += G_PI_2; } } else { while (phi1 < phi2) phi1 += 2 * G_PI; phi0 = ceil (phi1 / G_PI_2) * G_PI_2; while (phi0 > phi2) { arcto_ellipsesegment (radius_x, radius_y, MIN (phi0, phi1), MAX (phi0 - G_PI_2, phi2), ellips); gimp_matrix3_transform_point (&anglerot, ellips[0].x, ellips[0].y, &tmpx, &tmpy); ellips[0].x = tmpx; ellips[0].y = tmpy; gimp_matrix3_transform_point (&anglerot, ellips[1].x, ellips[1].y, &tmpx, &tmpy); ellips[1].x = tmpx; ellips[1].y = tmpy; gimp_matrix3_transform_point (&anglerot, ellips[2].x, ellips[2].y, &tmpx, &tmpy); ellips[2].x = tmpx; ellips[2].y = tmpy; gimp_matrix3_transform_point (&anglerot, ellips[3].x, ellips[3].y, &tmpx, &tmpy); ellips[3].x = tmpx; ellips[3].y = tmpy; gimp_coords_add (¢er, &(ellips[1]), &(ctrl[1])); gimp_coords_add (¢er, &(ellips[2]), &(ctrl[2])); gimp_coords_add (¢er, &(ellips[3]), &(ctrl[3])); gimp_bezier_stroke_cubicto (bez_stroke, &(ctrl[1]), &(ctrl[2]), &(ctrl[3])); phi0 -= G_PI_2; } } } GimpStroke * gimp_bezier_stroke_new_ellipse (const GimpCoords *center, gdouble radius_x, gdouble radius_y, gdouble angle) { GimpStroke *stroke; GimpCoords p1 = *center; GimpCoords p2 = *center; GimpCoords p3 = *center; GimpCoords dx = { 0, }; GimpCoords dy = { 0, }; const gdouble circlemagic = 4.0 * (G_SQRT2 - 1.0) / 3.0; GimpAnchor *handle; dx.x = radius_x * cos (angle); dx.y = - radius_x * sin (angle); dy.x = radius_y * sin (angle); dy.y = radius_y * cos (angle); gimp_coords_mix (1.0, center, 1.0, &dx, &p1); stroke = gimp_bezier_stroke_new_moveto (&p1); handle = g_queue_peek_head (stroke->anchors); gimp_coords_mix (1.0, &p1, -circlemagic, &dy, &handle->position); gimp_coords_mix (1.0, &p1, circlemagic, &dy, &p1); gimp_coords_mix (1.0, center, 1.0, &dy, &p3); gimp_coords_mix (1.0, &p3, circlemagic, &dx, &p2); gimp_bezier_stroke_cubicto (stroke, &p1, &p2, &p3); gimp_coords_mix (1.0, &p3, -circlemagic, &dx, &p1); gimp_coords_mix (1.0, center, -1.0, &dx, &p3); gimp_coords_mix (1.0, &p3, circlemagic, &dy, &p2); gimp_bezier_stroke_cubicto (stroke, &p1, &p2, &p3); gimp_coords_mix (1.0, &p3, -circlemagic, &dy, &p1); gimp_coords_mix (1.0, center, -1.0, &dy, &p3); gimp_coords_mix (1.0, &p3, -circlemagic, &dx, &p2); gimp_bezier_stroke_cubicto (stroke, &p1, &p2, &p3); handle = g_queue_peek_tail (stroke->anchors); gimp_coords_mix (1.0, &p3, circlemagic, &dx, &handle->position); gimp_stroke_close (stroke); return stroke; } /* helper function to get the associated anchor of a listitem */ static GList * gimp_bezier_stroke_get_anchor_listitem (GList *list) { if (!list) return NULL; if (GIMP_ANCHOR (list->data)->type == GIMP_ANCHOR_ANCHOR) return list; if (list->prev && GIMP_ANCHOR (list->prev->data)->type == GIMP_ANCHOR_ANCHOR) return list->prev; if (list->next && GIMP_ANCHOR (list->next->data)->type == GIMP_ANCHOR_ANCHOR) return list->next; g_return_val_if_fail (/* bezier stroke inconsistent! */ FALSE, NULL); return NULL; }