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 |  |
|
| |
|
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 | |
| |
|
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 | |
| |
|
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 | |
|
| |
|
|
