Files

586 lines
22 KiB
Python

# coding=utf-8
"""
Noyau de calcul de l'extension « Skull Pattern Fill », sans dependance a inkex.
Testable avec pytest seul et reutilisable hors Inkscape (scripts, schema
des parametres).
Le remplissage reprend le principe du motif de reference (doc/patern.png) :
un meme crane, repete a des tailles, des angles et en miroir differents, les
cranes s'empilant sans laisser de vide ; les petits sont dessines d'abord,
les grands viennent par-dessus.
Conventions :
- un contour (`rings`) est une liste d'anneaux, chaque anneau etant une liste
de points (x, y) fermee implicitement ; les trous suivent la regle pair-impair ;
- une polyligne est une liste de points (x, y) ;
- une boucle de Bezier est une liste de segments cubiques (p0, c1, c2, p3),
fermee ;
- le crane est dessine dans un repere unite : centre en (0, 0), hauteur 1
(y de -0,5 a 0,5), largeur 0,80 ; c'est le dessin de doc/dessin.svg sans
ses cornes, vu de trois quarts et tourne vers la gauche ;
- l'axe y est oriente vers le bas (repere SVG).
"""
import math
import random
from skull_drawing import BODY_D, INK_D
def parse_color(value, default=("#b3b3b3", 1.0)):
"""Couleur Inkscape (entier RGBA decimal ou 0x..., ou #rrggbb[aa]).
Renvoie (couleur CSS #rrggbb, opacite entre 0 et 1). Le parametre
« color » d'Inkscape arrive sous forme d'entier RGBA ; on le decode
nous-memes pour ne pas dependre de l'API couleur d'inkex, qui a change
entre les versions 1.x.
"""
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):
"""Donnees `d` d'un chemin SVG : une polyligne par sous-chemin."""
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)
# --------------------------------------------------------------------------
# Le crane
# --------------------------------------------------------------------------
def parse_loops(d):
"""Donnees `d` en commandes absolues M, C, Z -> boucles de Bezier.
Ne lit que la forme produite par docs/extraire_crane.py (et par
loops_to_d) : un sous-chemin par boucle, uniquement des cubiques.
"""
loops, loop, start, current = [], None, None, None
tokens = d.replace(",", " ").split()
i = 0
while i < len(tokens):
command = tokens[i]
if command == "M":
start = current = (float(tokens[i + 1]), float(tokens[i + 2]))
loop = []
i += 3
elif command == "C":
values = [float(v) for v in tokens[i + 1:i + 7]]
c1, c2, p3 = tuple(values[0:2]), tuple(values[2:4]), tuple(values[4:6])
loop.append((current, c1, c2, p3))
current = p3
i += 7
elif command == "Z":
if current != start:
loop.append((current, current, start, start))
loops.append(loop)
current = start
i += 1
else:
raise ValueError("commande non geree : {}".format(command))
return loops
_GEOMETRY = None
def skull_geometry():
"""Le crane dans son repere unite : (silhouette, encre).
Dessin de doc/dessin.svg, cornes retirees (donnees de skull_drawing.py,
regenerees par docs/extraire_crane.py). `silhouette` est le contour
exterieur, a remplir de la couleur de l'os pour cacher les cranes du
dessous ; `encre` est le trait et les ombres, un seul chemin a remplir
en regle non nulle (les trous blancs tournent en sens inverse).
"""
global _GEOMETRY
if _GEOMETRY is None:
_GEOMETRY = (parse_loops(BODY_D), parse_loops(INK_D))
return _GEOMETRY
def placement_matrix(x, y, size, angle=0.0, mirror=False):
"""Matrice affine (a, b, c, d, e, f) du repere unite vers le document.
Ordre : miroir horizontal, mise a l'echelle `size`, rotation `angle`
(degres, sens horaire a l'ecran comme dans Inkscape), translation.
"""
rad = math.radians(angle)
cos_a, sin_a = math.cos(rad) * size, math.sin(rad) * size
sx = -1.0 if mirror else 1.0
return (cos_a * sx, sin_a * sx, -sin_a, cos_a, x, y)
def apply_matrix(matrix, point):
a, b, c, d, e, f = matrix
return (a * point[0] + c * point[1] + e, b * point[0] + d * point[1] + f)
def loops_to_d(loops, matrix=(1, 0, 0, 1, 0, 0), precision=3):
"""Donnees `d` (M, C, Z absolus) de boucles de Bezier transformees.
Une transformation affine laisse une courbe de Bezier de meme forme :
transformer les points de controle suffit, le chemin produit n'a pas
besoin d'attribut `transform`.
"""
fmt = "{:.%df},{:.%df}" % (precision, precision)
parts = []
for loop in loops:
start = apply_matrix(matrix, loop[0][0])
parts.append("M " + fmt.format(*start))
for _p0, c1, c2, p3 in loop:
parts.append("C " + " ".join(fmt.format(*apply_matrix(matrix, p))
for p in (c1, c2, p3)))
parts.append("Z")
return " ".join(parts)
def skull_paths(placement, precision=3):
"""(d de la silhouette, d de l'encre) d'un crane place."""
matrix = placement_matrix(*placement)
return tuple(loops_to_d(loops, matrix, precision) for loops in skull_geometry())
# --------------------------------------------------------------------------
# Region a remplir
# --------------------------------------------------------------------------
def rings_bbox(rings):
xs = [x for ring in rings for x, _y in ring]
ys = [y for ring in rings for _x, y in ring]
if not xs:
return None
return min(xs), min(ys), max(xs), max(ys)
def point_in_rings(point, rings):
"""Point dans la region (regle pair-impair, les trous sont exclus)."""
x, y = point
inside = False
for ring in rings:
n = len(ring)
for i in range(n):
x1, y1 = ring[i]
x2, y2 = ring[(i + 1) % n]
if (y1 > y) != (y2 > y):
if x < x1 + (y - y1) * (x2 - x1) / (y2 - y1):
inside = not inside
return inside
def distance_to_rings(point, rings):
"""Distance d'un point au bord de la region."""
px, py = point
best = float("inf")
for ring in rings:
n = len(ring)
for i in range(n):
x1, y1 = ring[i]
x2, y2 = ring[(i + 1) % n]
dx, dy = x2 - x1, y2 - y1
length2 = dx * dx + dy * dy
t = 0.0 if not length2 else max(0.0, min(1.0, ((px - x1) * dx + (py - y1) * dy) / length2))
best = min(best, math.hypot(px - x1 - t * dx, py - y1 - t * dy))
return best
# --------------------------------------------------------------------------
# Geometrie visible
#
# Destination : la gravure laser. La machine grave tout trait present dans
# le fichier, meme cache sous un autre objet ou rendu invisible par un
# masque. On ne produit donc que l'encre reellement visible :
# - pour chaque crane, son encre, limitee a la forme, moins les silhouettes
# de tous les cranes poses au-dessus de lui ;
# - les interstices : la forme moins l'union de toutes les silhouettes.
# Les silhouettes elles-memes (le blanc de l'os) ne sont pas ecrites.
#
# Les calculs se font sur des polygones (courbes aplaties) avec le moteur
# booleen de boolean_ops. L'encre se lit en regle pair-impair (equivalente,
# pour ce dessin, a sa regle non nulle : ses trous tournent en sens inverse
# et ne se chevauchent pas) ; les silhouettes, toutes remises dans le meme
# sens, en regle non nulle, ce qui revient a leur union.
# --------------------------------------------------------------------------
IDENTITY = (1.0, 0.0, 0.0, 1.0, 0.0, 0.0)
def _bezier_point(q, t):
s = 1.0 - t
a, b, c, d = s * s * s, 3 * s * s * t, 3 * s * t * t, t * t * t
return (a * q[0][0] + b * q[1][0] + c * q[2][0] + d * q[3][0],
a * q[0][1] + b * q[1][1] + c * q[2][1] + d * q[3][1])
def flatten_loops(loops, matrix=IDENTITY, step=0.01):
"""Boucles de Bezier transformees -> anneaux (polygones fermes).
Chaque courbe est decoupee en morceaux d'au plus `step` environ (longueur
du polygone de controle), 24 au plus.
"""
rings = []
for loop in loops:
ring = []
for segment in loop:
q = [apply_matrix(matrix, p) for p in segment]
length = sum(math.hypot(b[0] - a[0], b[1] - a[1]) for a, b in zip(q, q[1:]))
count = max(1, min(24, int(math.ceil(length / step))))
ring.extend(_bezier_point(q, k / count) for k in range(count))
if len(ring) >= 3:
rings.append(ring)
return rings
def simplify_ring(ring, tolerance):
"""Anneau simplifie (Douglas-Peucker) : ecart au trace d'origine <= tolerance."""
n = len(ring)
if n < 4:
return ring
# On coupe l'anneau en deux au point le plus eloigne du premier.
far = max(range(n), key=lambda i: (ring[i][0] - ring[0][0]) ** 2 + (ring[i][1] - ring[0][1]) ** 2)
keep = [False] * (n + 1)
keep[0] = keep[far] = keep[n] = True
points = ring + [ring[0]]
stack = [(0, far), (far, n)]
while stack:
i, j = stack.pop()
a, b = points[i], points[j]
dx, dy = b[0] - a[0], b[1] - a[1]
norm = math.hypot(dx, dy)
best, index = tolerance, None
for k in range(i + 1, j):
p = points[k]
if norm:
dist = abs(dx * (p[1] - a[1]) - dy * (p[0] - a[0])) / norm
else:
dist = math.hypot(p[0] - a[0], p[1] - a[1])
if dist > best:
best, index = dist, k
if index is not None:
keep[index] = True
stack.append((i, index))
stack.append((index, j))
result = [points[k] for k in range(n) if keep[k]]
return result if len(result) >= 3 else ring
def rings_to_d(rings, precision=2):
"""Donnees `d` compactes d'anneaux fermes : M absolu, puis l relatifs.
Les ecarts sont pris entre points deja arrondis : ils ne cumulent pas
d'erreur. Les points confondus apres arrondi sont omis.
"""
scale = 10 ** precision
def num(v):
text = "{:.{}f}".format(v / scale, precision).rstrip("0").rstrip(".")
return "0" if text in ("", "-0") else text
parts = []
for ring in rings:
pts = [(int(round(x * scale)), int(round(y * scale))) for x, y in ring]
kept = [pts[0]]
for p in pts[1:]:
if p != kept[-1]:
kept.append(p)
if len(kept) < 3:
continue
parts.append("M{},{}l".format(num(kept[0][0]), num(kept[0][1])))
parts.append(" ".join("{},{}".format(num(b[0] - a[0]), num(b[1] - a[1]))
for a, b in zip(kept, kept[1:])))
parts.append("z")
return "".join(parts)
def ring_area(ring):
"""Aire signee (positive dans le sens horaire a l'ecran, y vers le bas)."""
return 0.5 * sum(a[0] * b[1] - b[0] * a[1] for a, b in zip(ring, ring[1:] + ring[:1]))
def _ring_bbox(ring):
xs = [p[0] for p in ring]
ys = [p[1] for p in ring]
return min(xs), min(ys), max(xs), max(ys)
def _boxes_overlap(a, b):
return a[0] <= b[2] and b[0] <= a[2] and a[1] <= b[3] and b[1] <= a[3]
class _EdgeGrid(object):
"""Cases traversees par les cotes d'anneaux : dit vite si une boite
est loin de tout bord."""
def __init__(self, rings):
edges = [(r[i], r[(i + 1) % len(r)]) for r in rings for i in range(len(r))]
total = sum(math.hypot(b[0] - a[0], b[1] - a[1]) for a, b in edges)
self.cell = max(4.0 * total / max(len(edges), 1), 1e-9)
self.cells = set()
c = self.cell
for a, b in edges:
for i in range(int(math.floor(min(a[0], b[0]) / c)), int(math.floor(max(a[0], b[0]) / c)) + 1):
for j in range(int(math.floor(min(a[1], b[1]) / c)), int(math.floor(max(a[1], b[1]) / c)) + 1):
self.cells.add((i, j))
def touches(self, box):
c = self.cell
for i in range(int(math.floor(box[0] / c)), int(math.floor(box[2] / c)) + 1):
for j in range(int(math.floor(box[1] / c)), int(math.floor(box[3] / c)) + 1):
if (i, j) in self.cells:
return True
return False
class Region(object):
"""Region a remplir : anneaux en regle pair-impair."""
def __init__(self, rings):
self.rings = [ring for ring in rings if len(ring) >= 3]
self.box = rings_bbox(self.rings)
self.grid = _EdgeGrid(self.rings)
def contains(self, point):
return point_in_rings(point, self.rings)
_RADIUS = None
def skull_radius():
"""Rayon du disque contenant le crane, pour une hauteur 1."""
global _RADIUS
if _RADIUS is None:
body, _ink = skull_geometry()
_RADIUS = max(math.hypot(*p) for seg in body[0] for p in seg)
return _RADIUS
_FLAT = {}
def _flat_skull(step):
"""Crane aplati et simplifie une fois pour toutes, dans son repere unite.
Renvoie (silhouette, anneaux d'encre). La silhouette est remise dans le
sens horaire, pour que l'union des silhouettes en regle non nulle ne
fasse pas de trou la ou deux cranes de sens opposes se chevauchent.
"""
if step not in _FLAT:
body, ink = skull_geometry()
# Ecart tolere : 0,25 % de la hauteur (moins d'un dixieme de
# millimetre sur un crane de 30 mm, sous la finesse d'un laser).
tolerance = 0.25 * step
outline = simplify_ring(flatten_loops(body, step=step)[0], tolerance)
if ring_area(outline) < 0:
outline = outline[::-1]
rings = [simplify_ring(ring, tolerance) for ring in flatten_loops(ink, step=step)]
_FLAT[step] = (outline, rings)
return _FLAT[step]
def _move(ring, matrix):
a, b, c, d, e, f = matrix
return [(a * x + c * y + e, b * x + d * y + f) for x, y in ring]
class _Placed(object):
"""Crane place : silhouette et encre en coordonnees du document."""
def __init__(self, placement, step):
outline, rings = _flat_skull(step)
matrix = placement_matrix(*placement)
self.placement = placement
self.body = _move(outline, matrix)
if placement[4]:
# Le miroir inverse le sens de parcours : on le retablit.
self.body.reverse()
self.box = _ring_bbox(self.body)
self.ink = [_move(ring, matrix) for ring in rings]
def visible_skulls(placements, region, step=0.01, progress=None):
"""Encre visible de chaque crane : [(placement, anneaux pair-impair)].
`placements` est dans l'ordre de dessin (du dessous vers le dessus).
Un crane entierement cache n'apparait pas. `progress(k, total)`, s'il est
donne, est appele apres chaque crane.
"""
from boolean_ops import boolean
skulls = [_Placed(p, step) for p in placements]
# Index des silhouettes par cases, pour trouver vite celles du dessus.
cell = max((max(s.box[2] - s.box[0], s.box[3] - s.box[1]) for s in skulls), default=1.0)
grid = {}
for k, s in enumerate(skulls):
for i in range(int(math.floor(s.box[0] / cell)), int(math.floor(s.box[2] / cell)) + 1):
for j in range(int(math.floor(s.box[1] / cell)), int(math.floor(s.box[3] / cell)) + 1):
grid.setdefault((i, j), []).append(k)
result = []
for k, skull in enumerate(skulls):
above = set()
box = skull.box
for i in range(int(math.floor(box[0] / cell)), int(math.floor(box[2] / cell)) + 1):
for j in range(int(math.floor(box[1] / cell)), int(math.floor(box[3] / cell)) + 1):
for other in grid.get((i, j), ()):
if other > k and _boxes_overlap(box, skulls[other].box):
above.add(other)
covers = [skulls[o] for o in sorted(above)]
border = region.grid.touches(box)
if not border and not region.contains(skull.body[0]):
# Loin du bord et dehors : entierement hors de la forme.
if progress:
progress(k + 1, len(skulls))
continue
if not covers and not border:
# Ni recouvert ni au bord : toute l'encre est visible.
result.append((skull.placement, list(skull.ink)))
if progress:
progress(k + 1, len(skulls))
continue
# Partie visible de la silhouette : petit polygone, vite calcule.
# Vide, le crane est entierement cache.
sets = [([skull.body], "nonzero"), ([c.body for c in covers], "nonzero")]
if border:
sets.append((region.rings, "evenodd"))
shown = boolean(sets, lambda inside: inside[0] and not inside[1] and inside[2])
else:
shown = boolean(sets, lambda inside: inside[0] and not inside[1])
kept = []
if shown:
# Les anneaux d'encre loin du bord de cette partie visible sont
# gardes ou ecartes d'un coup ; les autres sont intersectes avec
# elle (l'intersection se distribue sur le OU exclusif).
edges = _EdgeGrid(shown)
work = []
for ring in skull.ink:
ring_box = _ring_bbox(ring)
if edges.touches(ring_box):
work.append(ring)
elif point_in_rings(ring[0], shown):
kept.append(ring)
if work:
kept.extend(boolean([(work, "evenodd"), (shown, "evenodd")],
lambda inside: inside[0] and inside[1]))
if kept:
result.append((skull.placement, kept))
if progress:
progress(k + 1, len(skulls))
return result
def visible_gaps(placements, region, step=0.01):
"""Interstices : la forme moins l'union des silhouettes des cranes."""
from boolean_ops import boolean
bodies = [_Placed(p, step).body for p in placements]
return boolean([(region.rings, "evenodd"), (bodies, "nonzero")],
lambda inside: inside[0] and not inside[1])
# --------------------------------------------------------------------------
# Placement
# --------------------------------------------------------------------------
def random_size(rng, size_min, size_max, exponent=3.0):
"""Taille tiree selon une loi de puissance tronquee sur [min, max].
Densite proportionnelle a s^-exponent : beaucoup de petits cranes, peu
de grands ; avec 3, chaque octave de tailles couvre une surface
comparable, comme dans le motif de reference.
"""
if size_max <= size_min:
return size_min
k = 1.0 - exponent
lo, hi = size_min ** k, size_max ** k
return (lo + rng.random() * (hi - lo)) ** (1.0 / k)
def estimate_count(rings, size_min, spacing):
"""Nombre de positions candidates (pour refuser un calcul demesure)."""
box = rings_bbox(rings)
if box is None or size_min <= 0 or spacing <= 0:
return 0
step = size_min * spacing
return int(((box[2] - box[0]) / step + 2) * ((box[3] - box[1]) / step + 2))
def skull_placements(rings, size_min, size_max, spacing=0.7, max_rotation=30.0,
mirror=True, seed=1, origin=(0.0, 0.0)):
"""Positions des cranes couvrant la region.
Une grille, de pas `spacing` x taille minimale, decalee une ligne sur
deux et secouee au hasard, donne une position par case : la couverture
est assuree par les petits cranes. Chaque position recoit une taille
(loi de puissance), un angle dans [-max_rotation, max_rotation] et un
miroir aleatoire. On ne garde que les cranes qui touchent la region.
`origin` cale la grille (origine du document par defaut) : deux formes
voisines remplies avec la meme graine partagent les memes positions.
Renvoie des tuples (x, y, taille, angle, miroir), du plus petit au plus
grand : dessines dans cet ordre, les grands cranes passent devant.
"""
box = rings_bbox(rings)
if box is None or size_min <= 0:
return []
size_max = max(size_max, size_min)
step = size_min * spacing
if step <= 0:
return []
row_h = step * 0.866
margin = size_max * skull_radius()
x0, y0, x1, y1 = box[0] - margin, box[1] - margin, box[2] + margin, box[3] + margin
j_start = int(math.floor((y0 - origin[1]) / row_h))
j_end = int(math.ceil((y1 - origin[1]) / row_h))
i_start = int(math.floor((x0 - origin[0]) / step)) - 1
i_end = int(math.ceil((x1 - origin[0]) / step)) + 1
result = []
for j in range(j_start, j_end + 1):
for i in range(i_start, i_end + 1):
# Une graine par case : le tirage ne depend pas de l'etendue de la
# region, donc pas de la forme remplie.
rng = random.Random((seed * 73856093) ^ (i * 19349663) ^ (j * 83492791))
x = origin[0] + (i + 0.5 * (j % 2) + (rng.random() - 0.5) * 0.6) * step
y = origin[1] + (j + (rng.random() - 0.5) * 0.6) * row_h
size = random_size(rng, size_min, size_max)
angle = (rng.random() * 2.0 - 1.0) * max_rotation
flip = mirror and rng.random() < 0.5
if not (x0 <= x <= x1 and y0 <= y <= y1):
continue
# Un crane tient dans un disque de rayon skull_radius() x taille.
if not point_in_rings((x, y), rings) and \
distance_to_rings((x, y), rings) > skull_radius() * size:
continue
result.append((x, y, size, angle, flip))
result.sort(key=lambda p: p[2])
return result