Calepinify : un moteur de calepinage 2D en coupe guillotine - Julien Saillot

Le plan affichait 92 % de rendement. À l'écran, c'était beau : les pièces imbriquées les unes dans les autres, presque aucune chute, un vrai Tetris réussi. J'étais assez fier de mon algorithme.

Puis j'ai posé la seule question qui compte : sur une scie à format, tu le coupes comment ?

On ne le coupe pas. Ce n'était pas un plan de coupe, c'était une image. Un joli remplissage de rectangles qu'aucune machine d'atelier ne saurait débiter.

Cet article raconte comment Calepinify est passé d'un optimiseur de rectangles à un moteur de débit sous contrainte de coupe guillotine — et pourquoi la deuxième version fait volontairement baisser le taux de remplissage. C'est le projet que je mets en avant dans ma recherche d'alternance en développement à Montpellier, parce qu'il se teste au lieu de se raconter.

La démo est ouverte, sans compte → calepinage.juliensaillot.fr 2 chantiers pré-remplis, 45 pièces à débiter, 3 matières et 2 épaisseurs. Un clic sur « Générer le calepinage » et le moteur pose tout. Rien n'est envoyé sur un serveur : tout reste dans votre navigateur.

Interface principale de Calepinify L'éditeur : liste de débit à gauche, panneau au centre, contraintes d'atelier en permanence à l'écran.

Le calepinage en deux minutes (pour ceux qui ne sont pas menuisiers)

Un menuisier qui fabrique une cuisine ne commande pas des morceaux de bois à la bonne taille. Il achète des panneaux bruts — typiquement du mélaminé 2800 × 2070 mm — et il y découpe les 45 pièces de son meuble : côtés, fonds, étagères, façades.

Décider quelle pièce va où sur quel panneau, c'est le calepinage. On parle aussi de plan de coupe, de liste de débit, ou d'optimisation de découpe — c'est le terme qu'on tape dans Google quand on cherche un logiciel de calepinage. C'est une étape invisible pour le client final, mais elle décide de deux choses très concrètes :

combien de panneaux il faut acheter (un panneau mélaminé, c'est 40 à 90 € pièce) ;
combien de temps l'opérateur passe devant la scie.

Et le calepinage n'est pas un puzzle géométrique libre. Il traîne derrière lui quatre contraintes physiques dont aucune n'est négociable :

Contrainte	Ce que ça veut dire	Ce que ça coûte si on l'oublie
Trait de scie (kerf)	La lame mange 3 à 4 mm de matière à chaque coupe	La dernière pièce de la bande ne rentre pas — on le découvre à la scie
Affranchissement	Les rives du panneau brut ne sont ni droites ni propres, on les rogne	La première pièce est hors cote
Sens du fil	Le veinage doit courir dans un sens précis sur une façade	Le meuble est visuellement raté, le panneau est bon pour la chute
Matière × épaisseur	Une pièce de 19 mm en chêne ne se débite pas dans un panneau de 8 mm en blanc	Le plan est tout simplement inapplicable

Tant que ces règles restent dans la tête de celui qui calepine, elles tiennent. Le jour où la cote change et qu'il faut tout replacer à la main, elles sautent — et ça se paie au débit.

C'est de là que part le projet.

V1 : le bin packing 2D, ou comment optimiser le mauvais chiffre

La première version de Calepinify, écrite pendant mon BTS SIO SLAM, attaquait le problème de face : du bin packing 2D. Un problème d'optimisation combinatoire classique, NP-difficile, pour lequel on n'espère pas l'optimum mais une bonne heuristique.

L'implémentation suivait la recette habituelle, proche d'un MaxRects : tri des pièces par surface décroissante, placement glouton, entretien d'une liste d'espaces libres. Chaque fois qu'une pièce se posait, elle découpait l'espace résiduel en sous-espaces plus petits, eux-mêmes candidats pour la pièce suivante.

Ça marchait. Le remplissage grimpait à 85, 87, parfois 92 %. Le chiffre montait, donc j'allais dans le bon sens. C'est ce que je croyais.

Le problème, c'est que ce chiffre ne mesurait rien d'utile. Un algorithme à espaces libres pose les pièces partout où elles rentrent, y compris dans des configurations en moulin à vent : quatre pièces qui s'enroulent autour d'un vide central. Densité maximale, et aucune ligne droite ne traverse le panneau.

Or une scie à format ne sait faire qu'une chose : pousser le panneau contre une butée et passer la lame de bord à bord. Elle ne descend pas au milieu du panneau pour contourner une pièce — ça, c'est une défonceuse à commande numérique, que l'artisan qui teste Calepinify n'a pas.

Un plan sans lignes traversantes n'est donc pas un plan difficile à couper. Il est impossible à couper.

J'avais construit un optimiseur qui produisait des solutions mathématiquement excellentes et physiquement inexistantes.

Placement libre contre coupe guillotine : à gauche un moulin à vent dense mais indébitable, à droite un plan en bandes guillotine À gauche : densité maximale, aucune coupe traversante possible, et une chute enclavée au centre. À droite : le même lot en bandes guillotine, quelques points de rendement en moins, et un plan que la scie sait exécuter.

La contrainte guillotine, expliquée proprement

Une coupe guillotine traverse le panneau entier, d'un bord à l'autre. Rien d'autre.

La conséquence est plus intéressante que la définition : elle transforme le panneau en arbre binaire. La première coupe le sépare en deux rectangles. Chacun peut à son tour être coupé en deux. Et ainsi de suite, jusqu'aux feuilles de l'arbre, qui sont les pièces finales.

Voici un début d'arbre réel, trait de scie et affranchissement compris :

Panneau brut 2800 × 2070 — rives affranchies de 10 mm → zone utile 2780 × 2050
│
├── Coupe 1 · horizontale, bord à bord, à y = 630
│   │
│   ├── Bande A · 2780 × 620
│   │   └── Coupe 1.1 · verticale à x = 810
│   │       ├── Côté gauche · 800 × 620
│   │       └── Reste A′ · 1976 × 620      ← 814 → 2790, le trait de 4 mm est déduit
│   │           └── Coupe 1.1.1 · verticale à x = 1614
│   │               ├── Côté droit · 800 × 620
│   │               └── Reste A″ · 1172 × 620   → chute de bande
│   │
│   └── Reste du panneau · 2780 × 1426     ← 634 → 2060
│       └── Coupe 2 · horizontale à y = 1050 → bande B, puis bande C…

Chaque nœud a exactement deux enfants, chaque coupe consomme 4 mm, et rien ne commence avant les 10 mm d'affranchissement. Un plan est débitable si et seulement s'il se décrit ainsi. Ce n'est pas une préférence esthétique : c'est la géométrie de la machine.

Dans le métier, on parle de patrons de coupe à deux ou trois étages selon la profondeur de l'arbre — une formalisation qui remonte aux travaux de Gilmore et Gomory sur le cutting stock problem dans les années 1960. Plus il y a d'étages, plus le plan est dense, et plus il y a de manipulations à la scie.

C'est là que la V2 a commencé : non pas en améliorant l'algorithme existant, mais en le contraignant.

V2 : le moteur, étape par étape

Le moteur actuel exécute quatre étapes. Chacune supprime des solutions possibles — et c'est exactement le but.

1. Éclater le lot par couple matière × épaisseur

Deux pièces ne peuvent partager un panneau que si elles ont la même matière et la même épaisseur. Ce n'est pas une optimisation, c'est un fait.

Concrètement, un lot de 45 pièces en 3 matières et 2 épaisseurs ne forme pas un problème à 45 pièces : il forme jusqu'à six problèmes indépendants, de cinq à quinze pièces chacun, résolus séparément. Effet de bord agréable sur un problème NP-difficile : la complexité s'effondre.

// Une clé de lot = une famille de panneaux. Simplifié.
const lots = new Map<string, Piece[]>()
for (const piece of pieces) {
  const key = `${piece.matiere}|${piece.epaisseur}`
  lots.set(key, [...(lots.get(key) ?? []), piece])
}
// Chaque lot est ensuite calepiné indépendamment.

2. Verrouiller les pièces à fil imposé

Sur une façade, le veinage doit courir dans le sens de la hauteur. Si le fil est imposé, la pièce ne peut pas pivoter de 90°. Sa largeur reste sa largeur.

C'est la contrainte la plus coûteuse en rendement, parce qu'elle supprime une orientation sur deux pour chaque pièce concernée. C'est aussi celle qu'on ne peut jamais assouplir : un plan qui gagne trois points de matière en couchant une façade produit un meuble raté.

3. Grouper en bandes homogènes

Les pièces sont triées puis regroupées par hauteur proche dans des bandes. Une bande, c'est le premier étage de l'arbre : une coupe horizontale l'isole du reste du panneau.

C'est la famille du shelf packing, et plus précisément du First-Fit Decreasing Height : on trie par hauteur décroissante, on ouvre une bande à la hauteur de la première pièce, on y range tout ce qui tient, on ouvre la bande suivante. Guillotine par construction — c'est justement ce qui manquait à la V1.

Pourquoi « homogènes » ? Parce qu'une bande a la hauteur de sa pièce la plus haute. Y glisser une pièce beaucoup plus courte crée une zone morte sur toute sa largeur — de la chute qu'aucune coupe ultérieure ne récupère proprement.

4. Tronçonner à l'intérieur de la bande

Une fois la bande isolée, les pièces s'y alignent côte à côte, et des coupes verticales les séparent. Deuxième étage de l'arbre.

C'est ici que la comptabilité du trait de scie se joue, et c'est ici qu'on se plante :

// Ce qu'il reste vraiment dans une bande après avoir posé n pièces
const largeurUtile = panneau.largeur - 2 * affranchissement
const consomme = pieces.reduce((s, p) => s + p.largeur, 0) + trait * (pieces.length - 1)
const restant  = largeurUtile - consomme
// (pieces.length - 1) : il n'y a pas de trait de scie après la dernière pièce.

Le - 1 a l'air anodin. Écrire trait * pieces.length fait perdre 4 mm par bande — assez pour qu'une pièce cesse de rentrer quand la bande est pleine à quelques millimètres près. Oublier complètement le trait de scie est plus brutal : sur une bande de douze pièces, ce sont 44 mm qui n'existent pas, et la dernière pièce sort du panneau. Sur l'écran, tout va bien. À la scie, il manque une pièce.

Noter un plan sans se mentir

Un plan qui gagne 2 % de matière mais fait perdre 20 minutes à la scie reste un mauvais plan.

C'est l'ajout de la V2 qui a le plus changé le produit, et il ne tient pas dans l'algorithme de placement : il tient dans la façon de juger le résultat.

Le taux de remplissage est un chiffre honnête mais borgne. Il mesure la matière économisée et ignore complètement le temps machine. Chaque panneau généré par Calepinify est donc noté sur cinq critères, dont un seul est la densité.

Densité. Surface des pièces divisée par surface utile du panneau. Le chiffre classique, celui qu'on affiche. Il reste utile — il n'est simplement plus seul.

Familles de largeurs. Combien de largeurs de bande différentes le plan contient-il ? Sur une scie à format, chaque nouvelle largeur, c'est un nouveau réglage de butée : l'opérateur s'arrête, mesure, règle, contrôle. Un plan à trois familles se débite bien plus vite qu'un plan à onze, même s'il perd un point de densité.

Homogénéité des bandes. L'écart de hauteur entre les pièces d'une même bande. Faible écart = peu de zones mortes en haut de bande.

Alignement des coupes. Est-ce que les traits verticaux d'une bande se prolongent dans la bande voisine ? Quand c'est le cas, l'opérateur enchaîne deux bandes sans reprendre son réglage.

Zones mortes internes. Les chutes enclavées : trop petites pour être réutilisées, mal placées pour être récupérées d'un seul trait. On les mesure explicitement au lieu de les diluer dans le taux de remplissage.

Le résultat est contre-intuitif et c'est tout l'intérêt : le moteur V2 rend souvent des plans moins denses que la V1, et bien meilleurs. Passer de 92 % théorique et indébitable à 84 % réel, régulier, en trois familles de largeurs, c'est un gain net pour l'atelier.

Cette bascule — du « chiffre qui monte » vers « la métrique qui décrit vraiment le problème » — est la leçon que je réutilise partout ailleurs.

L'éditeur : rendre la main à l'humain

Le moteur ne connaît pas le chantier. Il ignore que ce panneau-là a un défaut dans le coin, que le client a changé d'avis sur une façade, que l'atelier préfère toujours débiter les grandes pièces en premier.

L'éditeur existe pour ça : permettre de casser l'optimum.

Glisser-déposer au millimètre. On attrape une pièce, on la repose ailleurs.
Aimantation aux bords et aux pièces. Des guides apparaissent à l'approche, la pièce s'accroche. Sans ça, placer précisément à la souris est une épreuve ; avec, c'est immédiat.
Annuler / refaire illimité. Condition non négociable pour que l'utilisateur ose essayer. Un éditeur où l'erreur coûte cher est un éditeur où personne ne touche à rien.

Le point de conception important : après un déplacement manuel, le score qualité se recalcule et s'affiche. L'outil n'interdit pas de dégrader le plan — il montre le prix du choix, et laisse décider.

Placement par glisser-déposer Aimantation aux bords et aux pièces pendant le déplacement : les guides d'alignement apparaissent à l'approche.

Sortir de l'écran : PDF, CSV, étiquettes

Un calepinage qui reste dans un navigateur ne sert à rien. Le livrable réel, c'est ce que l'opérateur pose à côté de la scie.

Plans de coupe PDF : un panneau par page, à l'échelle, avec les cotes en millimètres, le sens du fil matérialisé et les pièces nommées. Format paysage, calcul d'échelle automatique pour tenir sur une A4.
Liste de débit CSV : la même chose en tableur, pour ceux qui préfèrent une feuille ou qui la réinjectent ailleurs.
Étiquettes : une par pièce, à coller au sortir de la scie. C'est le détail le moins spectaculaire et l'un des plus utiles : sur 45 pièces, deux fonds de 596 × 780 et 596 × 800 se ressemblent beaucoup trop.

Export PDF Le plan tel qu'il arrive à l'atelier : cotes, sens du fil, tableau récapitulatif.

L'infrastructure, en bref

Le moteur tourne dans une application Next.js. La landing est rendue côté serveur pour le référencement ; l'éditeur est entièrement client, parce qu'un aller-retour réseau à chaque pixel de déplacement serait injouable. La séparation Server Components / Client Components tombe exactement sur cette frontière.

Supabase (PostgreSQL) assure la persistance, l'authentification et le stockage. Le choix décisif est le Row Level Security : l'isolation des données est déclarée une fois en SQL, dans la base, plutôt que vérifiée à la main dans chaque route.

alter table projects enable row level security;   -- sans cette ligne, la policy est inerte

create policy "un utilisateur ne voit que ses projets"
on projects for select
using (auth.uid() = user_id);

Quelques lignes qui remplacent un if répété partout — et surtout un if qu'on peut oublier. J'ai poussé ce raisonnement beaucoup plus loin sur mon second projet, Devisify, où l'isolation multi-entreprises est le sujet central de l'architecture.

Le déploiement passe par une image Docker multi-stage basée sur le build standalone de Next.js, poussée sur un VPS Debian via Dokploy, avec Traefik en frontal et Let's Encrypt pour le TLS. Un git push déclenche un webhook, l'image se reconstruit, le conteneur est remplacé.

FROM node:20-alpine AS builder
WORKDIR /app
COPY package*.json ./
RUN npm ci
COPY . .
RUN npm run build

FROM node:20-alpine AS runner
WORKDIR /app
COPY --from=builder /app/.next/standalone ./
COPY --from=builder /app/.next/static ./.next/static
COPY --from=builder /app/public ./public
EXPOSE 3000
CMD ["node", "server.js"]

La dernière ligne de copie est celle qu'on oublie : en mode standalone, public/ n'est pas embarqué automatiquement, et tous les assets statiques répondent 404 en production.

Le choix du self-hosted plutôt qu'une plateforme managée était volontairement pédagogique : je voulais comprendre ce qui se passe entre le commit et la requête HTTP, pas seulement le déléguer.

Déploiement continu avec Dokploy Le pipeline : webhook GitHub, build Docker, remplacement du conteneur.

Questions fréquentes

Qu'est-ce que le calepinage, exactement ?

C'est l'organisation de la découpe de pièces sur des panneaux de matière brute. On parle indifféremment de calepinage, de plan de coupe, de liste de débit ou d'optimisation de découpe. L'objectif est double : consommer le moins de panneaux possible, et produire un plan que l'atelier exécute vite et sans erreur.

Qu'est-ce qu'une coupe guillotine, et pourquoi ça change tout ?

C'est une coupe qui traverse le panneau d'un bord à l'autre, sans s'arrêter au milieu. C'est la seule que sache faire une scie à format. Un logiciel d'optimisation de découpe qui ignore cette contrainte produit des plans plus denses… et non débitables.

Un taux de remplissage élevé suffit-il à juger un plan de coupe ?

Non, et c'est le cœur de cet article. Un plan très dense peut multiplier les réglages de butée et les manipulations, et coûter plus cher en temps machine qu'il ne rapporte en matière. Calepinify note donc aussi les familles de largeurs, l'homogénéité des bandes, l'alignement des coupes et les zones mortes.

Faut-il créer un compte pour tester Calepinify ?

Non. La démo est ouverte, sans inscription et sans installation : deux chantiers sont pré-remplis, les données restent dans votre navigateur, et un bouton remet tout à zéro. Ce que la démo ne montre pas, en revanche, ce sont les comptes, l'authentification et la persistance serveur, qui existent dans la version applicative complète.

Ce que ce projet m'a appris

Calepinify a démarré comme un projet de BTS SIO SLAM. Je le maintiens aujourd'hui en Bachelor 3, et il a surtout été une longue leçon sur trois points.

Comprendre le métier avant de coder. Je ne suis pas menuisier. J'ai passé un temps considérable sur des forums d'artisans et des vidéos d'atelier avant d'écrire une ligne utile. Le trait de scie, l'affranchissement, le sens du fil ne sont pas des paramètres de configuration : ce sont les raisons pour lesquelles l'outil existe. Une contrainte métier mal comprise produit un logiciel qui a l'air de marcher.

Choisir la bonne métrique. J'ai passé une version entière à faire monter un chiffre qui ne décrivait pas le problème. Le vrai travail d'ingénierie a commencé quand j'ai remplacé « maximiser la densité » par « produire un plan qu'un opérateur exécute vite et sans erreur ».

Contraindre plutôt qu'étendre. La V2 est meilleure parce qu'elle s'interdit des choses. C'est valable au-delà de ce projet : beaucoup de bons choix techniques consistent à réduire l'espace des états possibles.

Je cherche actuellement une alternance en développement, cybersécurité ou réseaux à Montpellier. Calepinify est le projet que je préfère montrer sur le volet algorithmique — la démo est ouverte, les arbitrages décrits ici se discutent volontiers en entretien.

Ouvrir la démo → · Me contacter · GitHub · LinkedIn

La suite

Découpe à trois étages — descendre d'un niveau supplémentaire dans l'arbre pour récupérer les zones mortes, avec un arbitrage explicite entre densité gagnée et manipulations ajoutées.

Réutilisation des chutes d'un chantier à l'autre — un stock de chutes qui alimente les calepinages suivants. C'est le vrai gisement d'économies dans un atelier, et personne ne le gère correctement.

Import DXF — récupérer une liste de débit directement depuis un plan de conception.

Export vers commande numérique — générer les patrons de coupe dans un format que les scies à commande numérique consomment directement.

Stack : Next.js · React · Tailwind CSS · shadcn/ui · Supabase (PostgreSQL, Auth, Storage) · jsPDF · Docker · Dokploy · Traefik Sujet technique central : bin packing 2D sous contrainte de coupe guillotine, shelf packing (FFDH), patrons de coupe en bandes, scoring multi-critères