HomeProductsDownloadOrderSupportSearch
  
 
 Myriad Blog 1.3.0 Tuesday, Mar 19th, 2024 at 04:58am 

Technical 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
 3 comments.

Technical Wednesday, Apr 23rd, 2014 at 05:03pm
Figures anticrénelées (2/3) -  Les courbes

 
Hier, nous étions parvenus à dessiner des polygones anticrénelés. Mais le but reste de dessiner des courbes. Peut-on, en créant suffisamment de segments, approximer une courbe par un polygone ?
 
I- Le test du disque
 
Afin de vérifier cela, et mettre également notre algorithme à l'épreuve, nous créons un polygone qui suit le contour d'un cercle. Un segment est créé pour chaque 5° d'angle, ce qui au final aboutit à un polygone à 72 cotés.
 
Nous lançons notre programme, et obtenons :
 

 
Le disque est correctement tracé et anticrénelé. Les pans coupés dont il est constitué ne sont pas visibles et la figure donne l'apparence d'une courbe douce.  
 
II- La transparence
 
Afin de nous permettre de mieux visualiser nos résultats, plutôt que de tracer systématiquement nos figures en noir opaque, nous introduisons un niveau de transparence.
 
Notre dessin de test, avec un nouveau polygone de 6 points, et une transparence différence pour chaque élément, donne ceci :
 

 
III- Les courbes de Bezier
 
Dans les courbes de Bezier, chaque noeud de la figure est constitué d'un point par lequel passe la figure, et de deux points de contrôle, un de chaque coté du point, définissant l'angle de la courbe lors du passage au point.
 
Nos polygones précédents peuvent être considérés comme des courbes de Bézier en ne prenant qu'un point sur trois, et en considérant les deux autres comme les points de contrôle.
 
L'algorithme de De Casteljau nous permet de diviser chaque segment en deux, et de calculer le point de Bezier intermédiaire. Répété récursivement, il permet de lisser complètement la courbe.
 
Si on ne considère qu'un point sur trois dans nos deux polygones à angles vifs, on obtient 3 points (un triangle) pour le premier, et 2 points (une ligne ultrafine, invisible) pour le second.
 

 
L'algorithme de De Casteljau nous permet de calculer les points intermédiaires sur les courbes de Bezier définissant ces figures. Voici, avec une subdivision de chaque segment en 4 :
 

 
Puis avec une subdivision en 8 :
 

 
Puis avec une subdivision et en 16 :
 

 
On ne voit presque plus les "coins" des polygones. En améliorant l'algorithme de division de De Casteljau pour continuer à diviser tant que c'est visuellement nécessaire, on obtient nos premières courbes de Bezier lisses et anticrénelées :
 

 
Le plus difficile est maintenant derrière nous. Il nous faut maintenant être capable de tracer les contours au lieu des formes pleines, et inclure ces algoritmes dans notre bibliothèque de programmation.  

(à suivre)

by Olivier Guillion

Technical Tuesday, Apr 22nd, 2014 at 05:08pm
Figures anticrénelées (1/3) -  Les polygones

 
Dans le cadre de la mise à jour de la bibliothèque de compatibilité "ACAM", nous avons dû nous pencher sur le tracé de courbes dites "de Bezier". En effet, il s'agit du seul type d'objet graphique qui nous oblige encore à utiliser les bibliothèques du système, cairo sur Linux ou GDI+ sur Windows.
 
L'idée était donc de tracer par nous-même des courbes de Bezier, et anticrénelées qui plus est, c'est-à-dire utilisant des niveaux de gris sur les arètes de la courbe pour les faire apparaître lisses.
 
Voici toutes les étapes de notre cheminement, jusqu'à la solution définitive.
 
I- Tracé simple de polygone
 
La première étape consiste à pouvoir dessiner des polygones remplis. Un polygone est une figure fermée, constituée d'un ensemble de points reliés entre eux deux par deux, le dernier point étant relié au premier.
 
Pour tracer, nous avons utilisé le système de "scan-lines" :
 
 - On considère une à une les lignes horizontales (scan-lines) de l'aire contenant la figure.
 
 - Pour chacune de ces lignes horizontales, on calcule le point d'intersection entre cette ligne et chacun des segments de la figure. Il y a toujours un nombre pair d'intersections (vous pouvez le vérifier avec un papier et un crayon).  
 
 - Il suffit alors de classer ces intersections par X croissant, les considérer deux à deux et remplir en noir entre chaque paire.  
 
On obtient alors ceci, pour un polygone quelconque de 9 points :
 

 
Le tracé est mathématiquement exact, mais si on observe en détail la figure obtenue, on voit que les bords sont crénelés :
 

 
II- Anti-crénelage horizontal
 
Plutôt que de dessiner des points en noir ou blanc, on va traiter spécialement le premier et le dernier point de chaque ligne horizontale tracée, et choisir un niveau de gris représentant la proportion de noir dans le pixel.  
Le balayage considérant des scan-lines horizontales, ce procédé ne fonctionne que sur les segments de polygone plutôt verticaux. Pour les autres, il faudrait que plusieurs points à la suite aient des gris différents. Nous verrons cela plus tard.
 
On obtient alors :
 

 
Sur le détail, on voit que les lignes verticales ont bien été traitées, mais que les lignes horizontales sont encore crénelées:
 

 
III- Anti-crénelage bidirectionnel
 
L'algorithme, jusqu'ici, est rapide, très rapide.
 
Plutôt que de s'embarrasser de calculs mathématiques complexes pour traiter les bords des segments plutôt horizontaux, ce qui ralentirait le tracé d'un facteur 3 ou 4, nous estimons qu'il est plus simple et probablement plus rapide de simplement doubler l'algorithme existant avec un balayage vertical, à même de traiter les segments restants.
 
Dans la littérature, de tels algorithme de "cross scanline" ont déjà été envisagés il y a 25 ans pour obtenir des anticrénelages de haute qualité.
 
On obtient maintenant ceci :
 

 
Le détail montre que tous les segments ont été correctement anticrénelés.
 

 
Maintenant, il va falloir s'assurer que des courbes aux formes douces peuvent être correctement approximées par des polygones.  

(à suivre...)

by Olivier Guillion

Technical Monday, Apr 14th, 2014 at 05:06pm
Heartbleed - Au coeur du problème

 
Les plus technophiles d'entre vous auront entendu parler, ces jours derniers, de Heartbleed, la faille de sécurité affectant les accès cryptés à certains sites Web.
L'impact et l'exemplarité de cet épisode méritent qu'on y revienne dessus.
Tout d'abord, de quoi s'agit-il exactement ?
 
Heartbleed, coté fonctionnement
 
Pour résumer (et simplifier un peu), le problème touche OpenSSL, qui gère les échanges sécurisés entre par exemple un serveur Web (gmail, facebook, yahoo, etc) et le client (vous, votre voisin, un hacker, un pirate ou un agent de la NSA) qui y accède.
Lors de ces échanges, le client peut demander des données au serveur, et, en exploitant une erreur de programmation, s'arranger pour recevoir, en plus de ces données, le contenu d'une zone mémoire utilisée préalablement par le serveur  lors des échanges avec quelqu'un d'autre et malencontreusement non effacée.
 
Ainsi, n'importe qui peut s'arranger pour obtenir des données qui ne lui étaient pas destinées. Ces données peuvent être totalement inutiles, mais aussi des données sensibles (noms d'utilisateur, mot de passe, échanges privés...). En récupérant beaucoup, beaucoup de données par ce biais et en les triant, une personne mal intentionnée peut récupérer des noms d'utilisateurs et des mots de passe, et donc pirater des comptes ou accéder à des données privées. Imaginez ce que ça peut donner s'il s'agit du serveur de votre banque en ligne...
 
Heartbleed, coté programmation
 
On peut légitimement se poser la question : pourquoi les données sensibles se sont-elles retrouvées en clair dans une zone mémoire non utilisée ? N'aurait-il pas été plus sûr, si cette zone mémoire n'était pas censée être utilisée telle quelle, de l'effacer ?
OpenSSL est, sauf erreur, écrit en C. Un langage rapide, mais pas réputé pour la sécurité intrinsèque du code. En gros, on peut faire beaucoup de choses, qui vont très vite, mais ça crashe facilement, ça peut déborder, ça peut lire et écrire en dehors des endroits prévus, etc.
 
On peut alors choisir de privilégier la sécurité ou la performance. La sécurité, c'est, lorsqu'une zone mémoire va être utilisée ou est libérée, de l'effacer complètement. La sécurité, c'est aussi d'utiliser un gestionnaire de mémoire qui va générer une "exception" (un arrêt du programme ou l'inscription dans un journal d'alerte) lorsqu'on accède un peu en dehors des zones prévues.
La performance, c'est tout le contraire. Dans OpenSSL, on a visiblement choisi la performance.
 
Heartbleed, coté autorités
 
On ne sait pas vraiment depuis combien de temps la faille heartbleed est connue de certains. Il se murmure que la NSA l'exploite depuis plusieurs mois, voire plusieurs années, avec l'accord explicite des plus hautes autorités américaines. Et il est strictement impossible de savoir quelles données ont été lues par ce biais, d'en remonter la trace et ainsi de savoir qui a volé quoi.
 
Le saint-Grââl de l'espionnage informatique.  
 
Heartbleed, coté philosophique
 
Cela nous amène à nous interroger. Comment une faille de cette importance, et présentant ces conséquences, a-t-elle pu perdurer dans l'un des programmes Open Source les plus utilisés au monde ? On nous a présenté l'Open Source comme un schéma dans lequel la sécurité était maximale, car tous les programmeurs avaient la possibilité d'examiner le code, trouver les erreurs, les signaler et les corriger. Ainsi, aucun défaut majeur ne pouvait perdurer bien longtemps avant d'être repéré et traité.
On s'aperçoit aujourd'hui que ce n'est pas vrai, en tout cas pas obligatoirement vrai.
 
Heartbleed, coté "Open"
 
Le beau scénario de l'Open Source ne peut fonctionner que si trois points sont respectés :
 
1- Il y a suffisamment de programmeurs compétents pour vérifier le code.  
 
2- Le code est suffisamment clair pour permettre à tous de s'y retrouver facilement
 
3- Il y a plus de programmeurs "honnètes" pour chercher les failles que de pirates ou d'agents du gouvernement.
 
Pour 1-, le nombre de programmeurs chevronnés est probablement grandement surestimé. Et dans ceux-ci, beaucoup ont autre chose à faire que d'examiner du code qui fonctionne (ou qui semble fonctionner) correctement.
 
Pour 2-, sans avoir étudié le code source d'OpenSSL, beaucoup de projets Open Source semblent avoir été écrit avec les pieds par Hannibal Lecter. La syntaxe semble avoir été compliquée à dessein, les noms de fonctions et de variables semblent issus d'un manuel de codage russe, et les commentaires se résument souvent à une belle en-tête de fichier en ASCII Art.
 
Pour 3-, Heartbleed semble avoir prouvé que les pirates et les cyberespions possèdent maintenant un avantage en terme de moyens et de main-d'oeuvre par rapport à la poignée de bénévoles décidés à passer leur week-ends à relire l'intégrale du code d'OpenSSL, on se demande pourquoi.
 
Et maintenant, tout le monde est en train de se poser la même question : "celle-ci a été repérée, mais y en a-t-il encore beaucoup, des failles comme ça ?"...
by Olivier Guillion
 2 comments.


Full view
Reduced view
Most recent first
Oldest first
All
Didier Guillion
Olivier Guillion
Sylvie Ricard
All
Technical
Myriad Life
Memories
To be seen
Mood
Dev News
30 previous days
Apr 2006
May 2006
Jun 2006
Jul 2006
Aug 2006
Sep 2006
Oct 2006
Nov 2006
Dec 2006
Jan 2007
Feb 2007
Mar 2007
Apr 2007
May 2007
Jun 2007
Jul 2007
Aug 2007
Sep 2007
Oct 2007
Nov 2007
Dec 2007
Jan 2008
Feb 2008
Mar 2008
Apr 2008
May 2008
Jun 2008
Jul 2008
Aug 2008
Sep 2008
Oct 2008
Nov 2008
Dec 2008
Jan 2009
Feb 2009
Mar 2009
Apr 2009
May 2009
Jun 2009
Jul 2009
Aug 2009
Sep 2009
Oct 2009
Nov 2009
Dec 2009
Jan 2010
Feb 2010
Mar 2010
Apr 2010
May 2010
Jun 2010
Jul 2010
Aug 2010
Sep 2010
Oct 2010
Nov 2010
Dec 2010
Jan 2011
Feb 2011
Mar 2011
Apr 2011
May 2011
Jun 2011
Jul 2011
Aug 2011
Sep 2011
Oct 2011
Nov 2011
Dec 2011
Jan 2012
Feb 2012
Mar 2012
Apr 2012
May 2012
Jun 2012
Jul 2012
Aug 2012
Sep 2012
Oct 2012
Nov 2012
Dec 2012
Jan 2013
Feb 2013
Mar 2013
Apr 2013
May 2013
Jun 2013
Jul 2013
Aug 2013
Sep 2013
Oct 2013
Nov 2013
Dec 2013
Jan 2014
Feb 2014
Mar 2014
Apr 2014
May 2014
Jun 2014
Jul 2014
Aug 2014
Sep 2014
Oct 2014
Nov 2014
Dec 2014
Jan 2015
Feb 2015
Mar 2015
Apr 2015
May 2015
Jun 2015
Jul 2015
Aug 2015
Sep 2015
Oct 2015
Nov 2015
Dec 2015
Jan 2016
Feb 2016
Mar 2016
Apr 2016
May 2016
Jun 2016
Jul 2016
Aug 2016
Sep 2016
Oct 2016
Nov 2016
Dec 2016
Jan 2017
Feb 2017
Mar 2017
Apr 2017
May 2017
Jun 2017
Jul 2017
Aug 2017
Sep 2017
Oct 2017
Nov 2017
Dec 2017
Jan 2018
Feb 2018
Mar 2018
Apr 2018
May 2018
Jun 2018
Jul 2018
Aug 2018
Sep 2018
Oct 2018
Nov 2018
Dec 2018
Jan 2019
Feb 2019
Mar 2019
Apr 2019
May 2019
Jun 2019
Jul 2019
Aug 2019
Sep 2019
Oct 2019
Nov 2019
Dec 2019
Jan 2020
Feb 2020
Mar 2020
Apr 2020
May 2020
Jun 2020
Jul 2020
Aug 2020
Sep 2020
Oct 2020
Nov 2020
Dec 2020
Jan 2021
Feb 2021
Mar 2021
Apr 2021
May 2021
Jun 2021
Jul 2021
Aug 2021
Sep 2021
Oct 2021
Nov 2021
Dec 2021
Jan 2022
Feb 2022
Mar 2022
Apr 2022
May 2022
Jun 2022
Jul 2022
Aug 2022
Sep 2022
Oct 2022
Nov 2022
Dec 2022
Jan 2023
Feb 2023
Mar 2023
Apr 2023
May 2023
Jun 2023
Jul 2023
Aug 2023
Sep 2023
Oct 2023
Nov 2023
Dec 2023
Jan 2024
Feb 2024
Mar 2024
Mar 18th, 2024 at 08:14pm 
Comment from Sylvain
Mar 18th, 2024 at 08:13pm 
Comment from Sylvain
@André
Mar 18th, 2024 at 07:28pm 
Comment from Antoine Bautista
Build 82....
Mar 18th, 2024 at 05:02pm 
Article from Didier Guillion
Harmony Assistant 9.9.8  étape 198
Mar 18th, 2024 at 05:02pm 
Article from Didier Guillion
Harmony Assistant 9.9.8  étape 198
Mar 17th, 2024 at 11:40am 
Comment from Antoine Bautista
Frite....
Mar 17th, 2024 at 11:40am 
Comment from Antoine Bautista
Frite....
Mar 16th, 2024 at 09:16am 
Comment from André Baeck
Mar 16th, 2024 at 09:16am 
Comment from André Baeck
Mar 16th, 2024 at 09:13am 
Comment from André Baeck

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