Myriad Blog 1.3.0 Friday, Nov 24th, 2017 at 02:22pm 

Thursday, Apr 24th, 2014 at 05:14pm
Figures anticrénelées (3/3) -  Contours et performances

 
Nous sommes parvenus à tracer des formes polygonales pleines, et à convertir une figure formée d'un ensemble de courbes de Bezier en polygone pour pouvoir la tracer.
 
Il faut maintenant pouvoir tracer seulement le contour de la forme, sans la remplir.  
 
I- Contours fins
 
L'idée est de conserver le principe des "scan lines" utilisé dans le remplissage, et de l'adapter au tracé de contour. La couleur d'un point dépend alors de la distance minimale qui le sépare d'un segment ou d'une extrémité de segment constituant le polygone.
 
Calculer, pour chaque point de l'image, la distance à chacun des segments ou extrémités de segment serait trop lourd et trop lent pour être viable. Il faut donc éliminer rapidement tous les segments qui n'ont aucune chance d'être à proximité immédiate du point considéré, et  calculer uniquement les distances jusqu'aux segments proches.  
Plusieurs méthodes ont été implémentées, mais n'ont pas d'effet sur le résultat, seulement sur la rapidité.  
 
On obtient donc, même avant que la rapidité soit optimisée :
 

 
II- Contours épais
 
Il est assez facile de faire varier l'épaisseur du trait :
 
Lorsque la distance qui sépare le point considéré du plus proche segment est inférieure à la demi-épaisseur, on est dans le trait. Lorsqu'elle est supérieure, on est en dehors du trait.
 

 
III- La totale
 
On peut maintenant combiner les deux, traits et remplissage, et vérifier qu'ils s'ajustent correctement.  
 

 
La même chose avec des traits encore plus épais :
 

 
IV- Performance
 
Il est assez difficile d'évaluer la performance du tracé. Cela dépend en effet de la complexité de la figure, de sa taille, et des capacités de la machine.
 
Cependant, sur un PC qui n'est plus de la première jeunesse, on obtient, pour le test précédent, une moyenne d'environ 1 milliseconde (1/1000e de seconde) par tracé de figure, donc 1 ms pour le remplissage du 1er polygone, 1 pour son contour... soit 6 millisecondes pour l'ensemble du dessin.
 
Pour ce que nous voulons en faire (nos programmes ne sont pas des jeux avec des centaines de formes dessinées en temps réel), cela nous paraît suffisant.
 
V- Implémentation
 
Ces algorithmes ont été mis en place dans ACAM-Winter, et essayés dans Harmony Assistant, pour le tracé des accolades et des liaisons entre les notes.
 
Nous avons pu comparer le rendu entre notre méthode et les courbes de Bezier traitées par cairo, la librairie système de notre Linux Ubuntu :


 
Les deux rendus sont tellement proches que nous avons dû superposer les images dans un logiciel de dessin pour pouvoir constater une différence sur quelques pixels.
 
On peut donc considérer que notre algorithme remplace parfaitement la bibliothèque système, nous permettant de nous affranchir complètement de cette dernière. Il y aura probablement quelques erreurs de tracé dans certains cas limites, que nous devrons corriger, mais cela pourra être détecté dans la version alpha ou beta du programme.
by Olivier Guillion
Comments

Comment from Bubu42 Thursday, Apr 24th, 2014 at 07:38pm
(No subject)
Apparemment, il n'y a pas que Linux qui est concerné, puisque le travail est utilisable sous Mac OS (dont certaines bibliothèques sont menacées de disparition).

Comment from Thursday, Apr 24th, 2014 at 06:54pm
(No subject)
Est-il la peine?  
Pour les quelques utilisateurs de Linux?  
 
Comment voulez-vous attendre pour tout système!

Comment from Bubu42 Thursday, Apr 24th, 2014 at 05:34pm
(No subject)
Très intéressant !
Juste par curiosité, avez-vous pu comparer la rapidité de traçage entre les deux méthodes ?
Je suppose que la couleur du tracé ou du remplissage ne pose pas de problème. Ce n'est sans doute qu'un (ou deux si on cherche la petite bête) octet(s) à renseigner.
Si ça continue, il va falloir modifier le nom du programme en ACAMAL (pour ajouter And Linux !)  
Encore que... Après la petite aventure de la gestion du presse-papier, le "Clever" est peut-être un peu surfait pour X.


Most recent first
Oldest first

Top of page
Legal information Last update:  (c) Myriad