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 :

make release
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.
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 :

Vous demandez à générer la version Release du projet si ce n'est pas celle qui s'affiche dans la barre de menu.
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.
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.
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 :

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 !).
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é.
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).
Ensuite, à partir de ces chemins, le programme crée des polygones approchant les chemins (avec une erreur de moins de 0.1mm en moyenne).
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.
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 !
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 !
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)² !

Évolutions possibles

Que peut-on faire de plus une fois la 1ère version réalisée ?

Bilbiographie

pourquoi pas
une liste
de liens