diff options
Diffstat (limited to 'lib/elements/utils/stroke_to_satin.py')
| -rw-r--r-- | lib/elements/utils/stroke_to_satin.py | 303 |
1 files changed, 303 insertions, 0 deletions
diff --git a/lib/elements/utils/stroke_to_satin.py b/lib/elements/utils/stroke_to_satin.py new file mode 100644 index 00000000..ab14ab18 --- /dev/null +++ b/lib/elements/utils/stroke_to_satin.py @@ -0,0 +1,303 @@ +# Authors: see git history +# +# Copyright (c) 2025 Authors +# Licensed under the GNU GPL version 3.0 or later. See the file LICENSE for details. + +from numpy import zeros, convolve, int32, diff, setdiff1d, sign +from math import degrees, acos +from ...svg import PIXELS_PER_MM + +from ...utils import Point +from shapely import geometry as shgeo +from inkex import errormsg +from ...utils.geometry import remove_duplicate_points +from shapely.ops import substring +from shapely.affinity import scale +from ...i18n import _ +import sys + + +class SelfIntersectionError(Exception): + pass + + +def convert_path_to_satin(path, stroke_width, style_args): + path = remove_duplicate_points(fix_loop(path)) + + if len(path) < 2: + # ignore paths with just one point -- they're not visible to the user anyway + return None + + sections = list(convert_path_to_satins(path, stroke_width, style_args)) + + if sections: + joined_satin = list(sections)[0] + for satin in sections[1:]: + joined_satin = merge(joined_satin, satin) + return joined_satin + return None + + +def convert_path_to_satins(path, stroke_width, style_args, depth=0): + try: + rails, rungs = path_to_satin(path, stroke_width, style_args) + yield (rails, rungs) + except SelfIntersectionError: + # The path intersects itself. Split it in two and try doing the halves + # individually. + + if depth >= 20: + # At this point we're slicing the path way too small and still + # getting nowhere. Just give up on this section of the path. + return + + halves = split_path(path) + + for path in halves: + for section in convert_path_to_satins(path, stroke_width, style_args, depth=depth + 1): + yield section + + +def split_path(path): + linestring = shgeo.LineString(path) + halves = [ + list(substring(linestring, 0, 0.5, normalized=True).coords), + list(substring(linestring, 0.5, 1, normalized=True).coords), + ] + + return halves + + +def fix_loop(path): + if path[0] == path[-1] and len(path) > 1: + first = Point.from_tuple(path[0]) + second = Point.from_tuple(path[1]) + midpoint = (first + second) / 2 + midpoint = midpoint.as_tuple() + + return [midpoint] + path[1:] + [path[0], midpoint] + else: + return path + + +def path_to_satin(path, stroke_width, style_args): + if Point(*path[0]).distance(Point(*path[-1])) < 1: + raise SelfIntersectionError() + + path = shgeo.LineString(path) + distance = stroke_width / 2.0 + + try: + left_rail = path.offset_curve(-distance, **style_args) + right_rail = path.offset_curve(distance, **style_args) + except ValueError: + # TODO: fix this error automatically + # Error reference: https://github.com/inkstitch/inkstitch/issues/964 + errormsg(_("Ink/Stitch cannot convert your stroke into a satin column. " + "Please break up your path and try again.") + '\n') + sys.exit(1) + + if left_rail.geom_type != 'LineString' or right_rail.geom_type != 'LineString': + # If the offset curve come out as anything but a LineString, that means the + # path intersects itself, when taking its stroke width into consideration. + raise SelfIntersectionError() + + rungs = generate_rungs(path, stroke_width, left_rail, right_rail) + + left_rail = list(left_rail.coords) + right_rail = list(right_rail.coords) + + return (left_rail, right_rail), rungs + + +def get_scores(path): + """Generate an array of "scores" of the sharpness of corners in a path + + A higher score means that there are sharper corners in that section of + the path. We'll divide the path into boxes, with the score in each + box indicating the sharpness of corners at around that percentage of + the way through the path. For example, if scores[40] is 100 and + scores[45] is 200, then the path has sharper corners at a spot 45% + along its length than at a spot 40% along its length. + """ + + # need 101 boxes in order to encompass percentages from 0% to 100% + scores = zeros(101, int32) + path_length = path.length + + prev_point = None + prev_direction = None + length_so_far = 0 + for point in path.coords: + point = Point(*point) + + if prev_point is None: + prev_point = point + continue + + direction = (point - prev_point).unit() + + if prev_direction is not None: + # The dot product of two vectors is |v1| * |v2| * cos(angle). + # These are unit vectors, so their magnitudes are 1. + cos_angle_between = prev_direction * direction + + # Clamp to the valid range for a cosine. The above _should_ + # already be in this range, but floating point inaccuracy can + # push it outside the range causing math.acos to throw + # ValueError ("math domain error"). + cos_angle_between = max(-1.0, min(1.0, cos_angle_between)) + + angle = abs(degrees(acos(cos_angle_between))) + + # Use the square of the angle, measured in degrees. + # + # Why the square? This penalizes bigger angles more than + # smaller ones. + # + # Why degrees? This is kind of arbitrary but allows us to + # use integer math effectively and avoid taking the square + # of a fraction between 0 and 1. + scores[int(round(length_so_far / path_length * 100.0))] += angle ** 2 + + length_so_far += (point - prev_point).length() + prev_direction = direction + prev_point = point + + return scores + + +def local_minima(array): + # from: https://stackoverflow.com/a/9667121/4249120 + # This finds spots where the curvature (second derivative) is > 0. + # + # This method has the convenient benefit of choosing points around + # 5% before and after a sharp corner such as in a square. + return (diff(sign(diff(array))) > 0).nonzero()[0] + 1 + + +def generate_rungs(path, stroke_width, left_rail, right_rail): + """Create rungs for a satin column. + + Where should we put the rungs along a path? We want to ensure that the + resulting satin matches the original path as closely as possible. We + want to avoid having a ton of rungs that will annoy the user. We want + to ensure that the rungs we choose actually intersect both rails. + + We'll place a few rungs perpendicular to the tangent of the path. + Things get pretty tricky at sharp corners. If we naively place a rung + perpendicular to the path just on either side of a sharp corner, the + rung may not intersect both paths: + | | + _______________| | + ______|_ + ____________________| + + It'd be best to place rungs in the straight sections before and after + the sharp corner and allow the satin column to bend the stitches around + the corner automatically. + + How can we find those spots? + + The general algorithm below is: + + * assign a "score" to each section of the path based on how sharp its + corners are (higher means a sharper corner) + * pick spots with lower scores + """ + + scores = get_scores(path) + + # This is kind of like a 1-dimensional gaussian blur filter. We want to + # avoid the area near a sharp corner, so we spread out its effect for + # 5 buckets in either direction. + scores = convolve(scores, [1, 2, 4, 8, 16, 8, 4, 2, 1], mode='same') + + # Now we'll find the spots that aren't near corners, whose scores are + # low -- the local minima. + rung_locations = local_minima(scores) + + # Remove the start and end, because we can't stick a rung there. + rung_locations = setdiff1d(rung_locations, [0, 100]) + + if len(rung_locations) == 0: + # Straight lines won't have local minima, so add a rung in the center. + rung_locations = [50] + + rungs = [] + last_rung_center = None + + for location in rung_locations: + # Convert percentage to a fraction so that we can use interpolate's + # normalized parameter. + location = location / 100.0 + + rung_center = path.interpolate(location, normalized=True) + rung_center = Point(rung_center.x, rung_center.y) + + # Avoid placing rungs too close together. This somewhat + # arbitrarily rejects the rung if there was one less than 2 + # millimeters before this one. + if last_rung_center is not None and \ + (rung_center - last_rung_center).length() < 2 * PIXELS_PER_MM: + continue + else: + last_rung_center = rung_center + + # We need to know the tangent of the path's curve at this point. + # Pick another point just after this one and subtract them to + # approximate a tangent vector. + tangent_end = path.interpolate(location + 0.001, normalized=True) + tangent_end = Point(tangent_end.x, tangent_end.y) + tangent = (tangent_end - rung_center).unit() + + # Rotate 90 degrees left to make a normal vector. + normal = tangent.rotate_left() + + # Extend the rungs by an offset value to make sure they will cross the rails + offset = normal * (stroke_width / 2) * 1.2 + rung_start = rung_center + offset + rung_end = rung_center - offset + + rung_tuple = (rung_start.as_tuple(), rung_end.as_tuple()) + rung_linestring = shgeo.LineString(rung_tuple) + if (isinstance(rung_linestring.intersection(left_rail), shgeo.Point) and + isinstance(rung_linestring.intersection(right_rail), shgeo.Point)): + rungs.append(rung_tuple) + + return rungs + + +def merge(section, other_section): + """Merge this satin with another satin + + This method expects that the provided satin continues on directly after + this one, as would be the case, for example, if the two satins were the + result of the split() method. + + Returns a new SatinColumn instance that combines the rails and rungs of + this satin and the provided satin. A rung is added at the end of this + satin. + + The returned SatinColumn will not be in the SVG document and will have + its transforms applied. + """ + rails, rungs = section + other_rails, other_rungs = other_section + + if len(rails) != 2 or len(other_rails) != 2: + # weird non-satin things, give up and don't merge + return section + + # remove first node of each other rail before merging (avoid duplicated nodes) + rails[0].extend(other_rails[0][1:]) + rails[1].extend(other_rails[1][1:]) + + # add a rung in between the two satins and extend it just a litte to ensure it is crossing the rails + new_rung = shgeo.LineString([other_rails[0][0], other_rails[1][0]]) + rungs.append(list(scale(new_rung, 1.2, 1.2).coords)) + + # add on the other satin's rungs + rungs.extend(other_rungs) + + return (rails, rungs) |