Myriad Blog 1.3.0 Friday, Dec 15th, 2017 at 09:05am 

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


Most recent first
Oldest first

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