CutOptim

Présentation

Tous les utilisateurs de la découpeuse laser ont sans doute été confronté au problème: mon dessin ne rentre pas dans la feuille de bois à ma disposition ou même dans la découpeuse laser ! Pour tenter de remédier à ce problème, je me suis attelé à l'écriture d'un programme d'optimisation de placement d'objets sur une feuille.
Pour les lecteurs intéressés, il s'agit d'une variante d'un problème bien connu dans le monde de l'optimisation (bin packing problem).En faisant une petite recherche sur le Web, on trouve d'ailleurs de nombreux liens vers des programmes réalisant cette tâche, mais les versions gratuites sont souvent très limitées, elles se contentent d'optimiser la découpe de rectangles. Cela peut aider un fabricant de meubles, mais c'est trop limitant pour une découpeuse laser !

Ce programme lit un fichier SVG en entrée contenant les objets à placer et crée en sortie un second fichier SVG contenant les objets placés.
Il peut être utilisé tel quel (ligne de commande, pas d'interface graphique !) ou comme une extension inkscape qui fournit alors l'interface graphique.

Environnement

Comme indiqué ci dessus, ce programme peut être utilisé seul ou comme une extension inkscape.
Le travail à réaliser peut prendre un temps relativement long, il est préférable de l'exécuter sur un processeur moderne, mais si vous n'êtes pas pressés...
La consommation mémoire reste raisonnable, pas la peine de se précipiter pour acheter de nouvelles barrettes de RAM !

Logiciels

Tout d'abord comme il s'agit d'un programme écrit en C++ pour une question de performance, celui-ci devra être compilé sur votre machine.
J'ai écrit ce programme sous Linux/Ubuntu (compilé avec gcc), mais comme il n'y a pas de dépendance système, il devrait fonctionner tel quel sous tout autre version de Linux. Pour les inconditionnels de Windows (il y en a !), j'ai créé un projet Visual Studio qui permet de compiler sur cette plate-forme. Pour les utilisateurs de Mac, désolé je n'en ai pas, il faudra vous débrouiller par vous même, mais le C++ utilisé est vraiment standard, cela devrait fonctionner dès lors que vous avez accès à un compilateur. Pour information, je n'ai rien changé au code entre Linux et Windows, c'est dire !

Installation Linux

Le code est disponible ici : https://github.com/thierry7100/CutOptim Pour les non initiés, vous clonez (ou téléchargez) le répertoire, celui-ci arrive sous forme d'une archive .zip, qu'il faut extraire. Ensuite vous ouvrez un terminal, vous allez dans le répertoire créé et lancez les commandes :

1. make release
2. make install : ceci va copier le logiciel dans le répertoire ~/.local/bin qui se trouve dans la liste des répertoires d’exécutables, ce qui vous permettra de l'utiliser directement (ceci est peut-être spécifique Ubuntu, à vous de mettre le programme ailleurs sur un autre système.
3. make install_inkscape : ceci va copier le programme dans le répertoire d'extension inkscape (~/.config/inkscape/extensions). Si vous voulez mettre à disposition cette extension pour tous les comptes de votre machine, copiez le fichier cutoptim.inx + l'exécutable dans /usr/share/inkscape/extensions (vous devez être root).

Si vous avez opté pour l'extension inkscape, lors du prochain démarrage vous allez avoir une extension Fablab/Laser Cutting Optimizer

Installation Windows

Le code est disponible ici : https://github.com/thierry7100/CutOptim Pour les non initiés, vous clonez (ou téléchargez) le répertoire, celui-ci arrive sous forme d'une archive .zip, qu'il faut extraire. Ensuite vous lancez Visual Studio, vous pouvez obtenir une version gratuite à titre particulier, voir https://visualstudio.microsoft.com/fr/thank-you-downloading-visual-studio/?sku=Community&rel=16 Ensuite, une fois Visual studio démarré, vous ouvez le projet CutOptim, puis :

1. Vous demandez à générer la version Release du projet si ce n'est pas celle qui s'affiche dans la barre de menu.
2. Vous choisissez la plateforme (x86 ou x64) de votre choix. Par défaut le fichier est configuré en x64, si vous avez une version 32bit de Windows, changez en x86.
3. Vous cliquez sur Générer / Générer la solution, la compilation débute et au bout de quelques secondes, votre programme est disponible.
4. Ensuite, sous windows, mieux vaut utiliser ce programme comme extension inkscape, la ligne de commande n'étant guère utilisée? ! Pour cela copiez les fichiers cutoptim.inx et CutOptm/x64/Release/CutOptim.exe dans le répertoire d'extensions inkscape. Celui-ci peut être trouvé via la commande Edition/Préférences/Système, mais c'est généralement sous C:\USERS\<Votre nom d'utilisateur>\AppData\Roaming/inkscape/extensions. Attention, pour voir ce répertoire, vous devrez valider la visualisation de fichiers cachés sous l'explorateur de fichiers, si ce n'était pas fait.
   

Comme sous Linux, au prochain démarrage d'inkscape vous allez avoir une extension Fablab/Laser Cutting Optimizer

Fonctionnement

Le format d'entrée et de sortie des fichiers est le format SVG, disponible sur de nombreux logiciels. Si vous utilisez inkscape, c'est le format natif, le programme a été testé dans ce contexte. Il devrait également fonctionner avec des fichiers venant d'autres logiciels de dessin générant du SVG. Si vous rencontrez un problème dites le moi (thierry@fablab-lannion.org)

Description du processus :

1. Le document inkscape (tout au moins sa taille) a généralement peut d'importance, ici elle fixe la taille de la feuille utilisée pour la découpe. Vous devrez donc fixer une taille de document compatible avec votre matériau (et la découpeuse bien sûr !).
2. Tout d'abord le programme lit le document inkscape, il ne tient compte que des chemins ou objets simples. Les textes non transformés en chemin, les images... sont ignorés. Je conseille donc de tout transformer en chemin avant de lancer le programme. Sous inkscape Ctrl+A puis Objets en chemin (MAJ+Ctrl+C).Les chemins non fermés sont également ingnorés, le logiciel n'est capable que de traiter des formes avec un contour fermé.
3. Les chemins peuvent être placés n'importe où, dans la feuille ou en dehors, cela n'a aucune importance. Dans une certaine mesure, ils peuvent même être superposés (voir plus loin).
4. Ensuite, à partir de ces chemins, le programme crée des polygones approchant les chemins (avec une erreur de moins de 0.1mm en moyenne).
5. Puis le programme "agrandit" ces polygones pour éviter que les chemins se touchent dans le résultat final. La taille de l'agrandissement est paramétrable.
6. Le programme prend ensuite ces polygones agrandis et va essayer de les placer d'un manière non pas optimale mais bonne. Pourquoi pas optimale, car le problème est difficile (NP complet en termes mathématiques) et nécessite un temps très long même pour des configurations simples. L'idée de base ici est de partir du polygone le plus grand, puis de placer ensuite les polygones triés par taille décroissante tels qu'un sommet du polygone à placer soit positionné sur un sommet d'un polygone déjà placé. Cela réduit 'espace des possibles, même si celui ci reste très grand !
7. La "meilleure" configuration est obtenue quand la taille de l'enveloppe convexe est minimale. Encore un terme mathématique! L'enveloppe convexe est le plus petit convexe contenant tous es points de tous les polygones tracés. Intuitivement, cela maximise la place libre sur la plaque, ce qui est le résultat recherché. Attention, ce n'est pas forcément le rectangle le plus petit, l'enveloppe convexe n'étant généralement pas un rectangle !
8. Pour placer les chemins, le logiciel s'autorise de tourner les objets, à moins que vous ne bloquiez cette possibilité. Selon vos besoins (matériau non homogène) vous pourrez être amené à limiter les rotations à 0 et 180° par exemple, voire à bloquer toute rotation (ce sera le cas par exemlple avec du tissu imprimé).

Options du programme sous inkscape

Le programme possède de nombreuses options détaillées ci dessous :

• Unités : Toujours utiliser le mm, le programme n'est pas testé pour d'autres choix.
• Min distance between objects : C'est la taille dont seront agrandis les polygones créés. Cette valeur doit être supérieure à 0.8mm, l'approximation par des polygones n'est pas parfaite.
• Max length of single segment : comme expliqué ci-dessus le logiciel va essayer de trouver une bonne configuration en positionnant des sommets sur d'autres sommets. Il peut être intéressant dans certains cas "d'ajouter" des sommets pour avoir plus de possibilités. Si une arête a une taille supérieure à la taille indiquée elle sera brisée en plusieurs segments, avec donc des sommets supplémentaires. Ne pas abuser de cette option, une valeur trop faible va ralentir énormément le traitement. Ne pas descendre en dessous de 100mm dans la plupart des cas, même si la valeur 0 est permise pour indiquer que vous ne voulez PAS utiliser cette possibilité.
• Optimizing level : comme indiqué plus haut le programme place les polygones par ordre de taille décroissante (on place les plus gros cailloux d'abord...). Cela conduit parfois à des situations clairement sous-optimales. En augmentant ce paramètre, le logiciel va optimiser le placement d'un groupe de N polygones. Cela donne de meilleurs résultats, mais attention cela augmente considérablement le temps de traitement. Ne pas dépasser 2 ou 3, si la valeur par défaut de 1 ne donne pas de bons résultats. Si vous dessin possède 300 sommets déjà placés (valeur assez faible en fait) et que vous autorisez des rotations par pas de 10°, utiliser N=2 va multiplier les opérations par 36*300 ! Et pour N=3 par (36*300)² !
• Keep original layer in output. Si vous n'avez pas confiance !, vous pouvez cocher cette option, les formes originales seront conservées ainsi que celles placées, mais placées dans des calques différents. Vous pourrez ainsi vérifier le travail réalisé.
• Select option for largest element placement. Le premier élément peut être placé où vous le souhaitez sur la page. Généralement en haut à gauche, mais le centre donne également de bons résultats.
• Allow free rotation of paths, angle parameter not used : Si cette option est cochée, l'angle de rotation de chaque objet va être choisi parmi 4 pour faire coïncider l'arête avec l'une des deux du sommet sur lequel l'objet va être positionné. Cette option est économe en temps de traitement (au plus 4 essais) mais peut donner de moins bons résultats que la fixation de l'angle de rotation. Les résultats sont moins bons quand les segments sont très courts, si la forme d'entrée n'est pas un polygone par exemple.
• Try rotation by (0 no rotation allowed) : Cette option est incompatible avec la précédente, elle n'est valide que si l'option précédente n'est PAS cochée. Dans ce cas, les objets sont positionnés sur des pas de rotations discrets. 0 signifie que les rotations sont interdites, c'est utile quand le matériau nb'est pas homogène. Pour du MDF, pas de restrictions, mais pour du bois ou même du contreplaqué,si vous voulez respecter le sens du bois, les rotations sont à déconseiller. Choisir 180° dans ce cas. Attention, des valeurs faibles augmentent beaucoup le temps de calcul. Avec 10°, il y a 36 fois plus de calculs qu'avec 0° ! Si les formes d'entrée sont rectangulaires, une valeur de 90° donne de bons résultats.
• Attach nested path to the bigger one : Dans la pratique, on a souvent affaire à des situations ou des objets liés. Par exemple, une plaque avec des trous de fixation. Si cette case est cochée, le logiciel vérifie si le chemin est inclus dans un autre, et si c'est le cas, il ne va pas le traiter mais le lier au chemin le plus grand. Une fois celui-ci placé, la même transformation (rotation/translation) sera appliquée au "petit" objet inclus. Attention le logiciel n'est pas capable de récupérer l'espace libéré dans des trous, il faut bien vous laisser un peu de travail tout de même.
• Debug file generation : si cette case est cochée, un fichier de débogage (Debug_CutOptim.txt) est crée dans le répertoire d'extension inkscape. Cela peut servir à comprendre ce qui s'est (mal) passé.

Options du programme via la ligne de commande

Le logiciel possède à peu près les mêmes options que via inkscape, avec quelques ajouts.

Une aide succincte peut-être obtenue en tapant CutOptim -h.

thierry@thierry-UX410UAR:~/Programmes/CutOptim$ CutOptim -h - example command line options Usage: CutOptim [OPTION...] [optional args] -f, --file SVG Input File File (default: TestPoly1.svg) -o, --output SVG Output File Output file --positional arg File to be processed -h, --help Print help -d, --distance 1.0 Min distance between paths to be cut -m, --max_length 1000.0 Max length of one segment, break than longer -l, --optimizing_level 1 Optimizing level, process list_size elements together --debug_level 0 Level of debug info in specific debug file --debug_file Generate debug info from inkscape (default: true) -k, --original Output Original layer -n, --nested Keep nested path together (default: true) -y, --layer_output 0 Output internal layers : 1 Input layer, 2 Polygon, 4 Large polygon, 8 Hull layer, 16 Placed Polygon layer, OR these values to output multiple layers -a, --angle 90.0 Rotation step -r, --free_rot allow free rotation (default: true) -p, --firstpos Position of largest object on the sheet Position of largest object

Évolutions possibles

Sans doute beaucoup de choses, à vous de proposer et même de réaliser, le code est ouvert !

Bilbiographie

Comme indiqué le sujet est très connu dans le monde scientifique, je me suis servi des deux articles suivants

• Waste minimization in irregular stock cutting publié en 2014 par Doraid Dalalah, Samir Khrais et Khaled Bataineh. Cet article donne la base de ce qui est réalisé.
• Jostle heuristics for the 2D-irregular shapes bin packing problems with free rotation publié en 2018 par Ranga P. Abeysooriya, Julia A. Bennell et Antonio Martinez-Sykora

Bonne lecture !