diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/live_effects/CMakeLists.txt | 2 | ||||
| -rw-r--r-- | src/live_effects/Makefile_insert | 4 | ||||
| -rw-r--r-- | src/live_effects/effect-enum.h | 1 | ||||
| -rw-r--r-- | src/live_effects/effect.cpp | 7 | ||||
| -rw-r--r-- | src/live_effects/lpe-bool.cpp | 434 | ||||
| -rw-r--r-- | src/live_effects/lpe-bool.h | 66 |
6 files changed, 513 insertions, 1 deletions
diff --git a/src/live_effects/CMakeLists.txt b/src/live_effects/CMakeLists.txt index 9a2f06a76..2728d8fcd 100644 --- a/src/live_effects/CMakeLists.txt +++ b/src/live_effects/CMakeLists.txt @@ -52,6 +52,7 @@ set(live_effects_SRC lpegroupbbox.cpp lpeobject-reference.cpp lpe-vonkoch.cpp + lpe-bool.cpp lpeobject.cpp spiro-converters.cpp spiro.cpp @@ -129,6 +130,7 @@ set(live_effects_SRC lpe-test-doEffect-stack.h lpe-text_label.h lpe-vonkoch.h + lpe-bool.h lpegroupbbox.h lpeobject-reference.h lpeobject.h diff --git a/src/live_effects/Makefile_insert b/src/live_effects/Makefile_insert index b5bee55c8..c03606eb3 100644 --- a/src/live_effects/Makefile_insert +++ b/src/live_effects/Makefile_insert @@ -112,4 +112,6 @@ ink_common_sources += \ live_effects/lpe-jointype.cpp \ live_effects/lpe-jointype.h \ live_effects/lpe-taperstroke.cpp \ - live_effects/lpe-taperstroke.h + live_effects/lpe-taperstroke.h \ + live_effects/lpe-bool.cpp \ + live_effects/lpe-bool.h diff --git a/src/live_effects/effect-enum.h b/src/live_effects/effect-enum.h index eea26184c..0f770b0ad 100644 --- a/src/live_effects/effect-enum.h +++ b/src/live_effects/effect-enum.h @@ -66,6 +66,7 @@ enum EffectType { TAPER_STROKE, PERSPECTIVE_ENVELOPE, FILLET_CHAMFER, + BOOL_OP, INVALID_LPE // This must be last (I made it such that it is not needed anymore I think..., Don't trust on it being last. - johan) }; diff --git a/src/live_effects/effect.cpp b/src/live_effects/effect.cpp index c6ecba30a..b03671027 100644 --- a/src/live_effects/effect.cpp +++ b/src/live_effects/effect.cpp @@ -62,6 +62,7 @@ #include "live_effects/lpe-test-doEffect-stack.h" #include "live_effects/lpe-text_label.h" #include "live_effects/lpe-vonkoch.h" +#include "live_effects/lpe-bool.h" #include "xml/node-event-vector.h" #include "sp-object.h" @@ -151,6 +152,8 @@ const Util::EnumData<EffectType> LPETypeData[] = { {FILL_BETWEEN_MANY, N_("Fill between many"), "fill_between_many"}, {ELLIPSE_5PTS, N_("Ellipse by 5 points"), "ellipse_5pts"}, {BOUNDING_BOX, N_("Bounding Box"), "bounding_box"}, +/* MSoegtrop */ + {BOOL_OP, N_("Boolean operation"), "bool_op"}, }; const Util::EnumDataConverter<EffectType> LPETypeConverter(LPETypeData, sizeof(LPETypeData)/sizeof(*LPETypeData)); @@ -172,6 +175,10 @@ Effect::New(EffectType lpenr, LivePathEffectObject *lpeobj) { Effect* neweffect = NULL; switch (lpenr) { + case BOOL_OP: + neweffect = static_cast<Effect*> ( new LPEBool(lpeobj) ); + break; + case PATTERN_ALONG_PATH: neweffect = static_cast<Effect*> ( new LPEPatternAlongPath(lpeobj) ); break; diff --git a/src/live_effects/lpe-bool.cpp b/src/live_effects/lpe-bool.cpp new file mode 100644 index 000000000..902bb081b --- /dev/null +++ b/src/live_effects/lpe-bool.cpp @@ -0,0 +1,434 @@ +/* + * Boolean operation live path effect + * + * Copyright (C) 2016 Michael Soegtrop + * + * Released under GNU GPL, read the file 'COPYING' for more information + */ + +#include <glibmm/i18n.h> +#include <math.h> +#include <string.h> +#include <algorithm> + +#include "live_effects/lpe-bool.h" + +#include "display/curve.h" +#include "sp-item.h" +#include "2geom/path.h" +#include "sp-shape.h" +#include "sp-text.h" +#include "2geom/bezier-curve.h" +#include "2geom/path-sink.h" +#include "2geom/affine.h" +#include "splivarot.h" +#include "helper/geom.h" +#include "livarot/Path.h" +#include "livarot/Shape.h" +#include "livarot/path-description.h" +#include "2geom/svg-path-parser.h" + +namespace Inkscape { +namespace LivePathEffect { + +// Define an extended boolean operation type + +static const Util::EnumData<LPEBool::bool_op_ex> BoolOpData[LPEBool::bool_op_ex_count] = { + { LPEBool::bool_op_ex_union, N_("union"), "union" }, + { LPEBool::bool_op_ex_inters, N_("intersection"), "inters" }, + { LPEBool::bool_op_ex_diff, N_("difference"), "diff" }, + { LPEBool::bool_op_ex_symdiff, N_("symmetric difference"), "symdiff" }, + { LPEBool::bool_op_ex_cut, N_("cut"), "cut" }, + { LPEBool::bool_op_ex_slice, N_("slice, keep inner contours"), "slice" }, + { LPEBool::bool_op_ex_slice_inside, N_("slice inside, keep inner contours"), "slice-inside" }, + { LPEBool::bool_op_ex_slice_outside, N_("slice outside, keep inner contours"), "slice-outside" }, + { LPEBool::bool_op_ex_slice_rmv_inner, N_("slice, remove inner contours"), "slice-rmv-inner" }, + { LPEBool::bool_op_ex_slice_inside_rmv_inner, N_("slice inside, remove inner contours"), "slice-inside-rmv-inner" }, + { LPEBool::bool_op_ex_slice_outside_rmv_inner, N_("slice outside, remove inner contours"), "slice-outside-rmv-inner" } +}; + +static const Util::EnumDataConverter<LPEBool::bool_op_ex> BoolOpConverter(BoolOpData, sizeof(BoolOpData)/sizeof(*BoolOpData)); + +static const Util::EnumData<fill_typ> FillTypeData[] = { + { fill_oddEven, N_("odd-even"), "oddeven" }, + { fill_nonZero, N_("non-zero"), "nonzero" }, + { fill_positive, N_("positive"), "positive" }, + { fill_justDont, N_("from curve"), "from-curve" } +}; + +static const Util::EnumDataConverter<fill_typ> FillTypeConverter(FillTypeData, sizeof(FillTypeData)/sizeof(*FillTypeData)); + +static const Util::EnumData<fill_typ> FillTypeDataThis[] = { + { fill_oddEven, N_("odd-even"), "oddeven" }, + { fill_nonZero, N_("non-zero"), "nonzero" }, + { fill_positive, N_("positive"), "positive" } +}; + +static const Util::EnumDataConverter<fill_typ> FillTypeConverterThis(FillTypeDataThis, sizeof(FillTypeDataThis)/sizeof(*FillTypeDataThis)); + +LPEBool::LPEBool(LivePathEffectObject *lpeobject) : + Effect(lpeobject), + operand_path(_("Operand path:"), _("Operand for the boolean operation"), "operand-path", &wr, this), + bool_operation(_("Operation:"), _("Boolean Operation"), "operation", BoolOpConverter, &wr, this, bool_op_ex_union), + swap_operands(_("Swap operands:"), _("Swap operands (useful e.g. for difference)"), "swap-operands", &wr, this), + fill_type_this(_("Fill type this:"), _("Fill type (winding mode) for this path"), "filltype-this", FillTypeConverterThis, &wr, this, fill_oddEven), + fill_type_operand(_("Fill type operand:"), _("Fill type (winding mode) for operand path"), "filltype-operand", FillTypeConverter, &wr, this, fill_justDont) +{ + registerParameter(&operand_path); + registerParameter(&bool_operation); + registerParameter(&swap_operands); + registerParameter(&fill_type_this); + registerParameter(&fill_type_operand); + + show_orig_path = true; +} + +LPEBool::~LPEBool() +{ + +} + +void LPEBool::resetDefaults(SPItem const * /*item*/) +{ +} + +bool cmp_cut_position( const Path::cut_position &a, const Path::cut_position &b ) +{ + return a.piece==b.piece ? a.t<b.t : a.piece<b.piece; +} + +Geom::PathVector +sp_pathvector_boolop_slice_intersect(Geom::PathVector const &pathva, Geom::PathVector const &pathvb, bool inside, fill_typ fra, fill_typ frb) +{ + // This is similar to sp_pathvector_boolop/bool_op_slice, but keeps only edges inside the cutter area. + // The code is also based on sp_pathvector_boolop_slice. + // + // We have two paths on input + // - a closed area which is used to cut out pieces from a contour (called area below) + // - a contour which is cut into pieces by the border of thr area (called contour below) + // + // The code below works in the following steps + // (a) Convert the area to a shape, so that we can ask the winding number for any point + // (b) Add both, the contour and the area to a single shape and intersect them + // (c) Find the intersection points between area border and contour (vector toCut) + // (d) Split the original contour at the intersection points + // (e) check for each contour edge in combined shape if its center is inside the area - if not discard it + // (f) create a vector of all inside edges + // (g) convert the piece numbers to the piece numbers after applying the cuts + // (h) fill a bool vector with information which pieces are in + // (i) filter the descr_cmd of the result path with this bool vector + // + // The main inefficieny here is step (e) because I use a winding function of the area-shape which goes + // through teh complete edge list for each point I ask for, so effort is n-edges-contour * n-edges-area. + // It is tricky to improve this without building into the livarot code. + // One way might be to decide at the intersection points which edges touching the intersection points are + // in by making a loop through all edges on the intersection vertex. Since this is a directed non intersecting + // graph, this should provide sufficient information. + // But since I anyway will change this to the new mechanism some time speed is fairly ok, I didn't look into this. + + + // extract the livarot Paths from the source objects + // also get the winding rule specified in the style + // Livarot's outline of arcs is broken. So convert the path to linear and cubics only, for which the outline is created correctly. + Path *contour_path = Path_for_pathvector(pathv_to_linear_and_cubic_beziers( pathva) ); + Path *area_path = Path_for_pathvector(pathv_to_linear_and_cubic_beziers( pathvb) ); + + // Shapes from above paths + Shape *area_shape = new Shape; + Shape *combined_shape = new Shape; + Shape *combined_inters = new Shape; + + // Add the area (process to intersection free shape) + area_path->ConvertWithBackData(1.0); + area_path->Fill(combined_shape, 1); + + // Convert this to a shape with full winding information + area_shape->ConvertToShape(combined_shape, frb); + + // Add the contour to the combined path (just add, no winding processing) + contour_path->ConvertWithBackData(1.0); + contour_path->Fill(combined_shape, 0,true,false,false); + + // Intersect the area and the contour - no fill processing + combined_inters->ConvertToShape(combined_shape, fill_justDont); + + // Result path + Path *result_path = new Path; + result_path->SetBackData(false); + + // Cutting positions for contour + std::vector<Path::cut_position> toCut; + + if ( combined_inters->hasBackData() ) { + // should always be the case, but ya never know + { + for (int i = 0; i < combined_inters->numberOfPoints(); i++) { + if ( combined_inters->getPoint(i).totalDegree() > 2 ) { + // possibly an intersection + // we need to check that at least one edge from the source path is incident to it + // before we declare it's an intersection + int cb = combined_inters->getPoint(i).incidentEdge[FIRST]; + int nbOrig=0; + int nbOther=0; + int piece=-1; + float t=0.0; + while ( cb >= 0 && cb < combined_inters->numberOfEdges() ) { + if ( combined_inters->ebData[cb].pathID == 0 ) { + // the source has an edge incident to the point, get its position on the path + piece=combined_inters->ebData[cb].pieceID; + if ( combined_inters->getEdge(cb).st == i ) { + t=combined_inters->ebData[cb].tSt; + } else { + t=combined_inters->ebData[cb].tEn; + } + nbOrig++; + } + if ( combined_inters->ebData[cb].pathID == 1 ) nbOther++; // the cut is incident to this point + cb=combined_inters->NextAt(i, cb); + } + if ( nbOrig > 0 && nbOther > 0 ) { + // point incident to both path and cut: an intersection + // note that you only keep one position on the source; you could have degenerate + // cases where the source crosses itself at this point, and you wouyld miss an intersection + Path::cut_position cutpos; + cutpos.piece=piece; + cutpos.t=t; + toCut.push_back( cutpos ); + } + } + } + } + { + // remove the edges from the intersection polygon + int i = combined_inters->numberOfEdges() - 1; + for (;i>=0;i--) { + if ( combined_inters->ebData[i].pathID == 1 ) { + combined_inters->SubEdge(i); + } else { + const Shape::dg_arete &edge = combined_inters->getEdge(i); + const Shape::dg_point &start = combined_inters->getPoint(edge.st); + const Shape::dg_point &end = combined_inters->getPoint(edge.en); + Geom::Point mid = 0.5*(start.x+end.x); + int wind = area_shape->PtWinding( mid ); + if ( wind==0 ) { + combined_inters->SubEdge(i); + } + } + } + } + } + + // create a vector of pieces, which are in the intersection + std::vector<Path::cut_position> inside_pieces( combined_inters->numberOfEdges() ); + for( int i=0; i<combined_inters->numberOfEdges(); i++ ) { + inside_pieces[i].piece = combined_inters->ebData[i].pieceID; + // Use the t middle point, this is safe to compare with values from toCut in the presence of roundoff errors + inside_pieces[i].t = 0.5 * (combined_inters->ebData[i].tSt + combined_inters->ebData[i].tEn); + } + std::sort( inside_pieces.begin(), inside_pieces.end(), cmp_cut_position ); + + // sort cut positions + std::sort( toCut.begin(), toCut.end(), cmp_cut_position ); + + // Compute piece ids after ConvertPositionsToMoveTo + { + int idIncr=0; + std::vector<Path::cut_position>::iterator itPiece=inside_pieces.begin(); + std::vector<Path::cut_position>::iterator itCut=toCut.begin(); + while( itPiece!=inside_pieces.end() ) + { + while( itCut!=toCut.end() && cmp_cut_position( *itCut, *itPiece ) ) + { + ++itCut; + idIncr+=2; + } + itPiece->piece += idIncr; + ++itPiece; + } + } + + // Copy the original path to result and cut at the intersection points + result_path->Copy( contour_path ); + result_path->ConvertPositionsToMoveTo( toCut.size(), toCut.data() ); // cut where you found intersections + + // Create an array of bools which states which pieces are in + std::vector<bool> inside_flags(result_path->descr_cmd.size(), false ); + for( std::vector<Path::cut_position>::iterator itPiece=inside_pieces.begin(); itPiece!=inside_pieces.end(); ++itPiece ) + { + inside_flags[ itPiece->piece ] = true; + // also enable the element -1 to get the MoveTo + if( itPiece->piece>=1 ) + { + inside_flags[ itPiece->piece-1 ] = true; + } + } + +#if 0 // CONCEPT TESTING + //Check if the inside/outside verdict is consistent - just for testing the concept + // Retrieve the pieces + int nParts=0; + Path** parts=result_path->SubPaths(nParts,false); + + // Each piece should be either fully in or fully out + int iPiece=0; + for( int iPart=0; iPart<nParts; iPart++ ) + { + bool andsum=true; + bool orsum=false; + for( int iCmd=0; iCmd<parts[iPart]->descr_cmd.size(); iCmd++, iPiece++ ) + { + andsum = andsum && inside_flags[ iPiece ]; + orsum = andsum || inside_flags[ iPiece ]; + } + + if( andsum!=orsum ) + { + g_warning( "Inconsistent inside/outside verdict for part=%d", iPart ); + } + } + g_free(parts); +#endif + + // iterate over the commands of a path and keep those which are inside + int iDest=0; + for( int iSrc=0; iSrc<result_path->descr_cmd.size(); iSrc++ ) + { + if( inside_flags[iSrc]==inside ) + { + result_path->descr_cmd[iDest++] = result_path->descr_cmd[iSrc]; + } + else + { + delete result_path->descr_cmd[iSrc]; + } + } + result_path->descr_cmd.resize( iDest ); + + delete combined_inters; + delete combined_shape; + delete area_shape; + delete contour_path; + delete area_path; + + gchar *result_str = result_path->svg_dump_path(); + Geom::PathVector outres = Geom::parse_svg_path(result_str); + // CONCEPT TESTING g_warning( "%s", result_str ); + g_free(result_str); + delete result_path; + + return outres; +} + +// remove inner contours +Geom::PathVector +sp_pathvector_boolop_remove_inner(Geom::PathVector const &pathva, fill_typ fra) +{ + Geom::PathVector patht; + Path *patha = Path_for_pathvector(pathv_to_linear_and_cubic_beziers( pathva ) ); + + Shape *shape = new Shape; + Shape *shapeshape = new Shape; + Path *resultp = new Path; + resultp->SetBackData(false); + + patha->ConvertWithBackData(0.1); + patha->Fill(shape, 0); + shapeshape->ConvertToShape(shape, fra); + shapeshape->ConvertToForme(resultp, 1, &patha); + + delete shape; + delete shapeshape; + delete patha; + + gchar *result_str = resultp->svg_dump_path(); + Geom::PathVector resultpv = Geom::parse_svg_path(result_str); + g_free(result_str); + + delete resultp; + return resultpv; +} + +static fill_typ GetFillTyp(SPItem *item) +{ + SPCSSAttr *css = sp_repr_css_attr(item->getRepr(), "style"); + gchar const *val = sp_repr_css_property(css, "fill-rule", NULL); + if (val && strcmp(val, "nonzero") == 0) { + return fill_nonZero; + } else if (val && strcmp(val, "evenodd") == 0) { + return fill_oddEven; + } else { + return fill_nonZero; + } +} + +void LPEBool::doEffect (SPCurve * curve) +{ + Geom::PathVector path_in = curve->get_pathvector(); + + if ( operand_path.linksToPath() && operand_path.getObject() ) + { + bool_op_ex op = bool_operation.get_value(); + bool swap = swap_operands.get_value(); + + Geom::PathVector path_a = swap ? operand_path.get_pathvector() : path_in; + Geom::PathVector path_b = swap ? path_in : operand_path.get_pathvector(); + + // TODO: I would like to use the original objects fill rule if the UI selected rule is fill_justDont. + // But it doesn't seem possible to access them from here, because SPCurve is not derived from SPItem. + // The nearest function in the call stack, where this is available is SPLPEItem::performPathEffect (this is then an SPItem) + // For the parameter curve, this is possible. + // fill_typ fill_this = fill_type_this. get_value()!=fill_justDont ? fill_type_this.get_value() : GetFillTyp( curve ) ; + fill_typ fill_this = fill_type_this.get_value(); + fill_typ fill_operand = fill_type_operand.get_value()!=fill_justDont ? fill_type_operand.get_value() : GetFillTyp( operand_path.getObject() ); + + fill_typ fill_a = swap ? fill_operand : fill_this; + fill_typ fill_b = swap ? fill_this : fill_operand; + + switch( op ) + { + case bool_op_ex_slice_rmv_inner: + op = bool_op_ex_slice; + path_b = sp_pathvector_boolop_remove_inner( path_b, fill_b ); + break; + + case bool_op_ex_slice_inside_rmv_inner: + op = bool_op_ex_slice_inside; + path_b = sp_pathvector_boolop_remove_inner( path_b, fill_b ); + break; + + case bool_op_ex_slice_outside_rmv_inner: + op = bool_op_ex_slice_outside; + path_b = sp_pathvector_boolop_remove_inner( path_b, fill_b ); + break; + } + + Geom::PathVector path_out; + + if( op==bool_op_ex_slice || op == bool_op_ex_slice_rmv_inner) { + if( op==bool_op_ex_slice_rmv_inner ) + { + path_b = sp_pathvector_boolop_remove_inner( path_b, fill_b ); + } + path_out = sp_pathvector_boolop( path_b, path_a, to_bool_op(op), fill_b, fill_a); + } + else if( op==bool_op_ex_slice_inside || op==bool_op_ex_slice_inside_rmv_inner ) { + if( op==bool_op_ex_slice_inside_rmv_inner ) + { + path_b = sp_pathvector_boolop_remove_inner( path_b, fill_b ); + } + path_out = sp_pathvector_boolop_slice_intersect( path_a, path_b, true, fill_a, fill_b); + } else if( op==bool_op_ex_slice_outside || op == bool_op_ex_slice_outside_rmv_inner ) { + if( op==bool_op_ex_slice_outside_rmv_inner ) + { + path_b = sp_pathvector_boolop_remove_inner( path_b, fill_b ); + } + path_out = sp_pathvector_boolop_slice_intersect( path_a, path_b, false, fill_a, fill_b); + } else { + path_out = sp_pathvector_boolop( path_a, path_b, to_bool_op(op), fill_a, fill_b); + } + curve->set_pathvector( path_out ); + } +} + +} // namespace LivePathEffect +} /* namespace Inkscape */ diff --git a/src/live_effects/lpe-bool.h b/src/live_effects/lpe-bool.h new file mode 100644 index 000000000..12c51b4ec --- /dev/null +++ b/src/live_effects/lpe-bool.h @@ -0,0 +1,66 @@ +/* + * Boolean operation live path effect + * + * Copyright (C) 2016 Michael Soegtrop + * + * Released under GNU GPL, read the file 'COPYING' for more information + */ + +#ifndef INKSCAPE_LPE_BOOL_H +#define INKSCAPE_LPE_BOOL_H + +#include "live_effects/effect.h" +#include "live_effects/parameter/parameter.h" +#include "live_effects/parameter/originalpath.h" +#include "live_effects/parameter/bool.h" +#include "live_effects/parameter/enum.h" +#include "livarot/LivarotDefs.h" + +namespace Inkscape { +namespace LivePathEffect { + +class LPEBool : public Effect { +public: + LPEBool(LivePathEffectObject *lpeobject); + virtual ~LPEBool(); + + void doEffect (SPCurve * curve); + virtual void resetDefaults(SPItem const * item); + + enum bool_op_ex + { + bool_op_ex_union = bool_op_union, + bool_op_ex_inters = bool_op_inters, + bool_op_ex_diff = bool_op_diff, + bool_op_ex_symdiff = bool_op_symdiff, + bool_op_ex_cut = bool_op_cut, + bool_op_ex_slice = bool_op_slice, + bool_op_ex_slice_inside, // like bool_op_slice, but leaves only the contour pieces inside of the cut path + bool_op_ex_slice_outside, // like bool_op_slice, but leaves only the contour pieces outside of the cut path + bool_op_ex_slice_rmv_inner, // like bool_op_ex_slice, but remove inner contours + bool_op_ex_slice_inside_rmv_inner, // like bool_op_ex_slice_inside, but remove inner contours + bool_op_ex_slice_outside_rmv_inner, // like bool_op_ex_slice_outside, but remove inner contours + bool_op_ex_count + }; + + inline friend bool_op to_bool_op( bool_op_ex val ) + { + assert( val<=bool_op_ex_slice ); + (bool_op) val; + } + +private: + LPEBool(const LPEBool&); + LPEBool& operator=(const LPEBool&); + + OriginalPathParam operand_path; + EnumParam<bool_op_ex> bool_operation; + EnumParam<fill_typ> fill_type_this; + EnumParam<fill_typ> fill_type_operand; + BoolParam swap_operands; +}; + +}; //namespace LivePathEffect +}; //namespace Inkscape + +#endif |