541 lines
20 KiB
Python
541 lines
20 KiB
Python
# coding=utf-8
|
|
# SPDX-License-Identifier: GPL-2.0-or-later
|
|
# Copyright (C) 2026 Alex
|
|
"""
|
|
Computation core of the "Dog Bandana Pattern Fill" extension, without inkex.
|
|
|
|
Testable with pytest alone and reusable outside Inkscape (scripts, parameter
|
|
diagram).
|
|
|
|
Conventions:
|
|
- an outline (`rings`) is a list of rings, each ring being a list of (x, y)
|
|
points, implicitly closed; holes follow the even-odd rule;
|
|
- a polyline is a list of (x, y) points;
|
|
- the y axis points down (SVG coordinates).
|
|
|
|
The pattern is a Turing maze (bands of constant width that wind, branch and
|
|
end in round tips): `turing_pattern` returns the center line of each band,
|
|
to be drawn with a round-capped stroke. Only dependency: numpy, shipped with
|
|
Inkscape (inkex depends on it).
|
|
|
|
Generated strokes go through `laser_order` before being written: they are
|
|
chained and ordered to limit the idle travel of the laser head.
|
|
"""
|
|
|
|
import math
|
|
|
|
import numpy as np
|
|
|
|
__version__ = "1.0.0"
|
|
|
|
|
|
def parse_color(value, default=("#b3b3b3", 1.0)):
|
|
"""Inkscape color (decimal RGBA integer or 0x..., or #rrggbb[aa]).
|
|
|
|
Returns (CSS color #rrggbb, opacity between 0 and 1). Inkscape's "color"
|
|
parameter arrives as an RGBA integer; we decode it ourselves so as not to
|
|
depend on inkex's color API, which changed across 1.x versions.
|
|
"""
|
|
text = str(value).strip()
|
|
try:
|
|
if text.startswith("#"):
|
|
digits = text[1:]
|
|
if len(digits) == 3:
|
|
digits = "".join(c * 2 for c in digits)
|
|
if len(digits) == 6:
|
|
digits += "ff"
|
|
if len(digits) != 8:
|
|
return default
|
|
number = int(digits, 16)
|
|
else:
|
|
number = int(text, 0)
|
|
except ValueError:
|
|
return default
|
|
number &= 0xFFFFFFFF
|
|
red, green, blue = (number >> 24) & 255, (number >> 16) & 255, (number >> 8) & 255
|
|
alpha = (number & 255) / 255.0
|
|
return "#{:02x}{:02x}{:02x}".format(red, green, blue), round(alpha, 4)
|
|
|
|
|
|
def polylines_to_d(polylines, precision=4):
|
|
"""`d` data of an SVG path: one polyline per subpath."""
|
|
fmt = "{:.%df},{:.%df}" % (precision, precision)
|
|
parts = []
|
|
for polyline in polylines:
|
|
if len(polyline) < 2:
|
|
continue
|
|
parts.append("M " + fmt.format(*polyline[0]))
|
|
parts.extend("L " + fmt.format(*point) for point in polyline[1:])
|
|
return " ".join(parts)
|
|
|
|
|
|
# --------------------------------------------------------------------------
|
|
# Engraving order (laser cutter)
|
|
# --------------------------------------------------------------------------
|
|
|
|
def _key(point):
|
|
"""Key of a point: two end points within 1e-6 are the same node."""
|
|
return round(point[0], 6), round(point[1], 6)
|
|
|
|
|
|
def _is_closed(line):
|
|
return len(line) > 2 and _key(line[0]) == _key(line[-1])
|
|
|
|
|
|
def chain_polylines(polylines):
|
|
"""Join end to end the polylines that touch at their end points.
|
|
|
|
The laser then follows each result in one stroke, without lifting.
|
|
Polylines are the edges of a graph whose nodes are their end points;
|
|
walks start from odd-degree nodes first (branch tips): a walk starting
|
|
there can only stop on another odd node, which limits the number of
|
|
strokes, hence of idle jumps. An already closed polyline (loop) is kept
|
|
as is.
|
|
"""
|
|
out = []
|
|
points = {}
|
|
adjacency = {} # node -> [(polyline index, neighbour)]
|
|
lines = [list(line) for line in polylines if len(line) >= 2]
|
|
for index, line in enumerate(lines):
|
|
a, b = _key(line[0]), _key(line[-1])
|
|
if a == b:
|
|
out.append(line)
|
|
continue
|
|
points.setdefault(a, line[0])
|
|
points.setdefault(b, line[-1])
|
|
adjacency.setdefault(a, []).append((index, b))
|
|
adjacency.setdefault(b, []).append((index, a))
|
|
used = [False] * len(lines)
|
|
|
|
def free_edges(node):
|
|
edges = adjacency[node]
|
|
edges[:] = [edge for edge in edges if not used[edge[0]]]
|
|
return edges
|
|
|
|
def walk(node):
|
|
chain = [points[node]]
|
|
while True:
|
|
edges = free_edges(node)
|
|
if not edges:
|
|
return chain
|
|
index, following = edges.pop()
|
|
used[index] = True
|
|
line = lines[index]
|
|
if _key(line[0]) != node:
|
|
line = line[::-1]
|
|
chain.extend(line[1:])
|
|
node = following
|
|
|
|
for node in adjacency:
|
|
if len(free_edges(node)) % 2:
|
|
out.append(walk(node))
|
|
for node in adjacency: # what remains: closed circuits
|
|
while free_edges(node):
|
|
out.append(walk(node))
|
|
return out
|
|
|
|
|
|
def order_polylines(polylines, start=(0.0, 0.0)):
|
|
"""Order the polylines to limit the idle travel of the laser.
|
|
|
|
Nearest neighbour: from the end of the previous polyline (or `start`),
|
|
continue with the closest free entry point. An open polyline can be
|
|
followed in either direction; a closed loop can start at any of its
|
|
vertices. Entry points are stored in a grid so that not everything is
|
|
compared at each step.
|
|
"""
|
|
polylines = [list(line) for line in polylines if len(line) >= 2]
|
|
if not polylines:
|
|
return []
|
|
entries = [] # (polyline index, entry vertex)
|
|
for index, line in enumerate(polylines):
|
|
if _is_closed(line):
|
|
entries.extend((index, k) for k in range(len(line) - 1))
|
|
else:
|
|
entries.extend(((index, 0), (index, len(line) - 1)))
|
|
|
|
xs = [polylines[i][k][0] for i, k in entries]
|
|
ys = [polylines[i][k][1] for i, k in entries]
|
|
x0, y0 = min(xs), min(ys)
|
|
width, height = max(xs) - x0, max(ys) - y0
|
|
cell = math.sqrt(width * height / len(entries)) or max(width, height) / len(entries) or 1.0
|
|
nx, ny = int(width / cell), int(height / cell)
|
|
grid = {}
|
|
for entry, x, y in zip(entries, xs, ys):
|
|
grid.setdefault((int((x - x0) / cell), int((y - y0) / cell)), []).append(entry)
|
|
|
|
done = [False] * len(polylines)
|
|
|
|
def ring(cx, cy, r):
|
|
"""Grid cells at distance r (in cells) from (cx, cy)."""
|
|
if r == 0:
|
|
yield cx, cy
|
|
return
|
|
for gx in range(max(cx - r, 0), min(cx + r, nx) + 1):
|
|
if 0 <= cy - r <= ny:
|
|
yield gx, cy - r
|
|
if 0 <= cy + r <= ny:
|
|
yield gx, cy + r
|
|
for gy in range(max(cy - r + 1, 0), min(cy + r - 1, ny) + 1):
|
|
if 0 <= cx - r <= nx:
|
|
yield cx - r, gy
|
|
if 0 <= cx + r <= nx:
|
|
yield cx + r, gy
|
|
|
|
def nearest(x, y):
|
|
cx = int(math.floor((x - x0) / cell))
|
|
cy = int(math.floor((y - y0) / cell))
|
|
r = max(0, -cx, cx - nx, -cy, cy - ny) # first ring inside the grid
|
|
r_max = max(cx, nx - cx, cy, ny - cy, r)
|
|
best, best_d = None, float("inf")
|
|
while r <= r_max and (r - 1) * cell < best_d:
|
|
for key in ring(cx, cy, r):
|
|
bucket = grid.get(key)
|
|
if not bucket:
|
|
continue
|
|
bucket[:] = [e for e in bucket if not done[e[0]]]
|
|
for index, k in bucket:
|
|
px, py = polylines[index][k]
|
|
d = math.hypot(px - x, py - y)
|
|
if d < best_d:
|
|
best, best_d = (index, k), d
|
|
r += 1
|
|
return best
|
|
|
|
ordered = []
|
|
position = start
|
|
for _ in range(len(polylines)):
|
|
index, k = nearest(*position)
|
|
done[index] = True
|
|
line = polylines[index]
|
|
if k == 0:
|
|
pass
|
|
elif not _is_closed(line):
|
|
line = line[::-1]
|
|
else: # loop: rotate it
|
|
line = line[k:-1] + line[:k] + [line[k]]
|
|
ordered.append(line)
|
|
position = line[-1]
|
|
return ordered
|
|
|
|
|
|
def laser_order(polylines, start=(0.0, 0.0)):
|
|
"""Chain then order the strokes: apply before polylines_to_d.
|
|
|
|
`start`: position of the head (end of the previous drawing, or origin).
|
|
The final position is the last point of the last polyline.
|
|
"""
|
|
return order_polylines(chain_polylines(polylines), start)
|
|
|
|
|
|
def travel_length(polylines, start=(0.0, 0.0)):
|
|
"""Total length of idle moves (head off) between polylines."""
|
|
total = 0.0
|
|
position = start
|
|
for line in polylines:
|
|
total += math.hypot(line[0][0] - position[0], line[0][1] - position[1])
|
|
position = line[-1]
|
|
return total
|
|
|
|
|
|
# --------------------------------------------------------------------------
|
|
# Turing pattern (maze)
|
|
# --------------------------------------------------------------------------
|
|
#
|
|
# "Labyrinth" regime of the Swift-Hohenberg equation:
|
|
# du/dt = r.u - (1 + laplacian)^2 u - u^3
|
|
# integrated on a pixel grid covering the shape. Starting from random noise,
|
|
# the field u organizes into bands of period 2.pi (reduced units). Positive
|
|
# bands are thinned to a one-pixel skeleton, traced as polylines, smoothed
|
|
# and simplified.
|
|
|
|
PIXELS_PER_PERIOD = 8 # computation resolution
|
|
STEPS = 60 # integration steps: more, longer bands
|
|
SMOOTHING = 4 # smoothing passes of the center lines
|
|
EDGE_MODES = ("cut", "follow")
|
|
MAX_PIXELS = 3000000 # beyond this, too slow inside Inkscape
|
|
|
|
|
|
def rasterize(rings, x0, y0, step, nx, ny):
|
|
"""Boolean mask (ny, nx) of pixel centers inside the rings (even-odd).
|
|
|
|
Pixel (i, j): center at (x0 + (j + 0.5) * step, y0 + (i + 0.5) * step).
|
|
Scanline fill: for each row, sorted abscissas of the crossings with the
|
|
edges; a pixel is inside if it has an odd number of crossings on its
|
|
left.
|
|
"""
|
|
mask = np.zeros((ny, nx), dtype=bool)
|
|
edges = [(ring[k], ring[(k + 1) % len(ring)]) for ring in rings
|
|
for k in range(len(ring))]
|
|
if not edges:
|
|
return mask
|
|
ax, ay, bx, by = (np.array(v, dtype=float) for v in zip(
|
|
*[(a[0], a[1], b[0], b[1]) for a, b in edges]))
|
|
columns = x0 + (np.arange(nx) + 0.5) * step
|
|
for i in range(ny):
|
|
y = y0 + (i + 0.5) * step
|
|
# Half-open edge: a shared vertex is counted only once.
|
|
hit = (ay <= y) != (by <= y)
|
|
if not hit.any():
|
|
continue
|
|
t = (y - ay[hit]) / (by[hit] - ay[hit])
|
|
xs = np.sort(ax[hit] + t * (bx[hit] - ax[hit]))
|
|
mask[i] = np.searchsorted(xs, columns) % 2 == 1
|
|
return mask
|
|
|
|
|
|
def erode(mask, radius):
|
|
"""Erosion of the mask by a disk of `radius` pixels.
|
|
|
|
FFT convolution: a pixel stays if there is no outside pixel in the disk
|
|
around it. The convolution is periodic: the grid must keep an outer
|
|
border of at least `radius` pixels.
|
|
"""
|
|
if radius <= 0:
|
|
return mask.copy()
|
|
ny, nx = mask.shape
|
|
iy = np.minimum(np.arange(ny), ny - np.arange(ny))[:, None]
|
|
ix = np.minimum(np.arange(nx), nx - np.arange(nx))[None, :]
|
|
disk = (ix ** 2 + iy ** 2 <= radius ** 2).astype(float)
|
|
hits = np.fft.irfft2(np.fft.rfft2((~mask).astype(float)) * np.fft.rfft2(disk),
|
|
s=mask.shape)
|
|
return mask & (hits < 0.5)
|
|
|
|
|
|
def swift_hohenberg(shape, pixels_per_period=PIXELS_PER_PERIOD, seed=1,
|
|
steps=STEPS, outside=None, r=0.35, dt=0.5):
|
|
"""Field u (ny, nx) in the labyrinth regime.
|
|
|
|
Semi-implicit spectral scheme: implicit linear part (stable whatever the
|
|
time step), explicit cubic term; periodic boundaries. `outside`
|
|
(optional boolean mask): pixels where u is forced to -1 at each step;
|
|
bands then stop before this mask and run along its edge, instead of
|
|
being cut sharply.
|
|
"""
|
|
ny, nx = shape
|
|
rng = np.random.default_rng(seed)
|
|
u = 0.1 * rng.standard_normal((ny, nx))
|
|
spacing = 2 * math.pi / pixels_per_period # pixel in reduced units
|
|
kx = 2 * math.pi * np.fft.rfftfreq(nx, d=spacing)
|
|
ky = 2 * math.pi * np.fft.fftfreq(ny, d=spacing)
|
|
k2 = ky[:, None] ** 2 + kx[None, :] ** 2
|
|
denominator = 1 - dt * (r - (1 - k2) ** 2)
|
|
for _ in range(steps):
|
|
if outside is not None:
|
|
u[outside] = -1.0
|
|
u_hat = np.fft.rfft2(u - dt * u ** 3)
|
|
u = np.fft.irfft2(u_hat / denominator, s=(ny, nx))
|
|
if outside is not None:
|
|
u[outside] = -1.0
|
|
return u
|
|
|
|
|
|
def skeletonize(binary):
|
|
"""One-pixel-wide skeleton (Zhang-Suen), vectorized with numpy."""
|
|
img = np.pad(binary.astype(np.uint8), 1)
|
|
while True:
|
|
changed = False
|
|
for first in (True, False):
|
|
p2, p3, p4 = img[:-2, 1:-1], img[:-2, 2:], img[1:-1, 2:]
|
|
p5, p6, p7 = img[2:, 2:], img[2:, 1:-1], img[2:, :-2]
|
|
p8, p9 = img[1:-1, :-2], img[:-2, :-2]
|
|
around = [p2, p3, p4, p5, p6, p7, p8, p9, p2]
|
|
neighbours = sum(around[:8])
|
|
transitions = sum(((a == 0) & (b == 1)).astype(np.uint8)
|
|
for a, b in zip(around, around[1:]))
|
|
if first:
|
|
c1, c2 = p2 * p4 * p6, p4 * p6 * p8
|
|
else:
|
|
c1, c2 = p2 * p4 * p8, p2 * p6 * p8
|
|
remove = ((img[1:-1, 1:-1] == 1) & (neighbours >= 2) & (neighbours <= 6)
|
|
& (transitions == 1) & (c1 == 0) & (c2 == 0))
|
|
if remove.any():
|
|
img[1:-1, 1:-1][remove] = 0
|
|
changed = True
|
|
if not changed:
|
|
return img[1:-1, 1:-1].astype(bool)
|
|
|
|
|
|
_NEIGHBOURS = ((-1, 0), (0, 1), (1, 0), (0, -1), (-1, -1), (-1, 1), (1, 1), (1, -1))
|
|
|
|
|
|
def _skeleton_graph(skeleton):
|
|
"""Neighbours of each skeleton pixel.
|
|
|
|
8-connected links, except a diagonal doubled by two straight links
|
|
("L" corner): it would create false junctions.
|
|
"""
|
|
pixels = set(zip(*(index.tolist() for index in np.nonzero(skeleton))))
|
|
graph = {}
|
|
for (i, j) in pixels:
|
|
links = []
|
|
for di, dj in _NEIGHBOURS:
|
|
q = (i + di, j + dj)
|
|
if q not in pixels:
|
|
continue
|
|
if di and dj and ((i + di, j) in pixels or (i, j + dj) in pixels):
|
|
continue
|
|
links.append(q)
|
|
graph[(i, j)] = links
|
|
return graph
|
|
|
|
|
|
def trace_skeleton(skeleton, min_spur=0):
|
|
"""Polylines of pixels (row, column) that follow the skeleton.
|
|
|
|
Each branch joins two nodes (tips or junctions); loops without a node
|
|
are traced separately; an isolated pixel gives a one-point polyline.
|
|
Spurs (free branch shorter than `min_spur` pixels attached to a junction,
|
|
thinning artifacts) are removed.
|
|
"""
|
|
graph = _skeleton_graph(skeleton)
|
|
seen = set() # links already followed
|
|
|
|
def follow(previous, current, line):
|
|
seen.add((previous, current))
|
|
seen.add((current, previous))
|
|
while len(graph[current]) == 2 and current != line[0]:
|
|
line.append(current)
|
|
a, b = graph[current]
|
|
following = b if a == previous else a
|
|
if (current, following) in seen:
|
|
break
|
|
seen.add((current, following))
|
|
seen.add((following, current))
|
|
previous, current = current, following
|
|
line.append(current)
|
|
return line
|
|
|
|
lines = []
|
|
for node in sorted(p for p, links in graph.items() if len(links) != 2):
|
|
if not graph[node]:
|
|
lines.append([node])
|
|
for nxt in graph[node]:
|
|
if (node, nxt) not in seen:
|
|
lines.append(follow(node, nxt, [node]))
|
|
for p in sorted(graph): # isolated loops
|
|
links = graph[p]
|
|
if len(links) == 2 and (p, links[0]) not in seen:
|
|
lines.append(follow(p, links[0], [p]))
|
|
|
|
if min_spur <= 0:
|
|
return lines
|
|
degree = {p: len(links) for p, links in graph.items()}
|
|
kept = []
|
|
for line in lines:
|
|
ends = sorted((degree[line[0]], degree[line[-1]]))
|
|
if 1 < len(line) <= min_spur and ends[0] == 1 and ends[1] >= 3:
|
|
continue
|
|
kept.append(line)
|
|
return kept
|
|
|
|
|
|
def smooth_polyline(points, passes=2):
|
|
"""Moving-average smoothing (1/4, 1/2, 1/4), end points fixed.
|
|
|
|
A closed loop (first point = last point) is smoothed all along.
|
|
"""
|
|
if len(points) < 3:
|
|
return [tuple(p) for p in points]
|
|
closed = tuple(points[0]) == tuple(points[-1])
|
|
pts = np.array(points[:-1] if closed else points, dtype=float)
|
|
for _ in range(passes):
|
|
if closed:
|
|
pts = 0.25 * np.roll(pts, 1, 0) + 0.5 * pts + 0.25 * np.roll(pts, -1, 0)
|
|
else:
|
|
inner = 0.25 * pts[:-2] + 0.5 * pts[1:-1] + 0.25 * pts[2:]
|
|
pts = np.vstack((pts[:1], inner, pts[-1:]))
|
|
out = [tuple(p) for p in pts.tolist()]
|
|
if closed:
|
|
out.append(out[0])
|
|
return out
|
|
|
|
|
|
def simplify_polyline(points, tolerance):
|
|
"""Ramer-Douglas-Peucker: keep only the vertices needed within `tolerance`."""
|
|
if len(points) < 3:
|
|
return [tuple(p) for p in points]
|
|
pts = np.asarray(points, dtype=float)
|
|
keep = np.zeros(len(pts), dtype=bool)
|
|
keep[0] = keep[-1] = True
|
|
stack = [(0, len(pts) - 1)]
|
|
while stack:
|
|
a, b = stack.pop()
|
|
if b - a < 2:
|
|
continue
|
|
sx, sy = pts[b] - pts[a]
|
|
rel = pts[a + 1:b] - pts[a]
|
|
length = math.hypot(sx, sy)
|
|
if length == 0:
|
|
dist = np.hypot(rel[:, 0], rel[:, 1])
|
|
else:
|
|
dist = np.abs(rel[:, 0] * sy - rel[:, 1] * sx) / length
|
|
k = int(np.argmax(dist))
|
|
if dist[k] > tolerance:
|
|
keep[a + 1 + k] = True
|
|
stack.extend(((a, a + 1 + k), (a + 1 + k, b)))
|
|
return [tuple(p) for p in pts[keep].tolist()]
|
|
|
|
|
|
def _grid(rings, period, pixels_per_period):
|
|
"""Origin, step and size (x0, y0, step, nx, ny) of the computation grid.
|
|
|
|
Outer border of two periods: the field is -1 there and the (periodic)
|
|
FFT erosion does not leak from one side to the other.
|
|
"""
|
|
xs = [x for ring in rings for x, _y in ring]
|
|
ys = [y for ring in rings for _x, y in ring]
|
|
step = period / pixels_per_period
|
|
pad = 2 * pixels_per_period
|
|
nx = int(math.ceil((max(xs) - min(xs)) / step)) + 2 * pad
|
|
ny = int(math.ceil((max(ys) - min(ys)) / step)) + 2 * pad
|
|
return min(xs) - pad * step, min(ys) - pad * step, step, nx, ny
|
|
|
|
|
|
def grid_pixels(rings, period, pixels_per_period=PIXELS_PER_PERIOD):
|
|
"""Number of pixels of the computation grid (0 if nothing to compute)."""
|
|
if period <= 0 or not any(rings):
|
|
return 0
|
|
_x0, _y0, _step, nx, ny = _grid(rings, period, pixels_per_period)
|
|
return nx * ny
|
|
|
|
|
|
def turing_pattern(rings, period, line_width, margin=0.0, seed=1, edge="cut",
|
|
pixels_per_period=PIXELS_PER_PERIOD, steps=STEPS):
|
|
"""Center lines of the Turing maze that fills `rings`.
|
|
|
|
- period: distance between the center lines of two neighbouring bands;
|
|
- line_width: stroke width (round tips included): the whole stroke stays
|
|
inside the shape;
|
|
- margin: free space between the shape edge and the stroke;
|
|
- seed: random seed (another number, another pattern);
|
|
- edge: "cut", the pattern is computed regardless of the shape then cut
|
|
at its edge (like cut fabric); "follow", bands stop before the edge
|
|
and run along it.
|
|
|
|
Returns polylines in document coordinates; an isolated dot is a polyline
|
|
of two identical points (a round-capped stroke draws it).
|
|
"""
|
|
if period <= 0 or not any(rings):
|
|
return []
|
|
x0, y0, step, nx, ny = _grid(rings, period, pixels_per_period)
|
|
mask = rasterize(rings, x0, y0, step, nx, ny)
|
|
inset = max(0.0, margin) + max(0.0, line_width) / 2
|
|
region = erode(mask, inset / step)
|
|
if not region.any():
|
|
return []
|
|
follow = edge == "follow"
|
|
u = swift_hohenberg(region.shape, pixels_per_period, seed, steps,
|
|
outside=~region if follow else None)
|
|
skeleton = skeletonize(u > 0) & region
|
|
lines = trace_skeleton(skeleton, min_spur=pixels_per_period / 2)
|
|
|
|
out = []
|
|
for line in lines:
|
|
points = [(x0 + (j + 0.5) * step, y0 + (i + 0.5) * step) for i, j in line]
|
|
if len(points) == 1:
|
|
out.append([points[0], points[0]])
|
|
else:
|
|
out.append(simplify_polyline(smooth_polyline(points, SMOOTHING), 0.1 * step))
|
|
return out
|