algorithme général pour l'image vectorielle tramage

Question

Quel est l'algorithme général de pixelliser image vectorielle? Je l'ai trouvé beaucoup d'algorithmes de primitives pixelliser tels que des lignes, des cercles, des courbes de Bézier, etc. Mais pour général, que dois-je faire? Simplement, aller foreach figure vecteur dans le vecteur image, obtenir ses pixels et les mettre en image raster? Ou autre chose?

Et une autre question, comment puis-je améliorer le temps de traitement à l'aide concurrency? Je peux, par exemple, les chiffres de vecteurs séparés et obtenir en même temps que leurs pixels. Mais peut-être il y a d'autres méthodes pour le faire?

Answer 1

L'algorithme de tramage générale est la suivante, pour chaque polygone dans l'image.

(polygone A est défini comme une ou plusieurs courbes fermées à base de segments de droites et les splines paramétriques - dans la pratique normale ce sont d'ordre 2 (de quadratique alias conique) et troisième ordre (cubique) courbes de Bézier Ces courbes fermées sont. définie de sorte que l'intérieur est toujours à gauche, la courbe est traversée,. si les formes ordinaires courent dans le sens antihoraire et des trous entrent dans le sens horaire)

(i) (projection) Autre polygone dans le même système de coordonnées que l'image bitmap de destination. La nécessité de la résolution ne soit pas la même, et pour les images lissées est souvent plus. Par exemple, FreeType utilise 64e de pixels

(ii) (marque monotone en Y) Si nécessaire, diviser chaque segment du polygone en segments plus petits qui fonctionnent en continu vers le haut ou vers le bas. Cette étape est nécessaire uniquement pour les segments courbes, et il est relativement facile lors de l'utilisation de Bézier splines. La méthode habituelle consiste à bissectrice jusqu'à ce que monotonicity soit atteint. Jeter tous les segments horizontaux.

(iii) (marquer les limites d'exécution) Tracer chaque segment en un bitmap temporaire. Utilisez l'algorithme de Bresenham pour les lignes droites; pour les courbes, bisect jusqu'à ce que la ligne est plus loin que (par exemple) 1/8 d'un pixel à partir de la courbe réelle, puis utiliser une ligne droite du début à la fin. Lors de l'élaboration, les pixels de la marque dans une certaine façon à indiquer (a) si elles sont commence ou se termine de pistes - lignes vers le bas sont commence, et les lignes vers le haut sont extrémités; (B) la couverture - la fraction du pixel qui est à l'intérieur de la forme. C'est là algorithmes diffèrent dans les détails, et où les règles d'enroulement ( non nul par rapport à pair-impair) se distinguent.

(iv) (scan) Traverse le bitmap temporaire, rangée par rangée. Pour chaque ligne, balayage de gauche à droite. Maintenir un état qui indique si la position courante est à l'intérieur de la forme ou non par (par exemple) en ajoutant le nombre mémorisé dans le bitmap à un numéro enregistré. En simple, tramage monochrome ce nombre, écrit à l'étape précédente, sera +1 lors du franchissement d'un bord en forme et -1 en sortant de la forme. exécute Accumulez de pixels dans le même état. Envoyer les pistes de votre module de dessin: par exemple, FreeType émet se composant d'une coordonnée Y, démarrer et coordonnées extrémité X, et une couverture de 0 à 255. Le module de dessin peut à l'aide de la couverture comme une valeur alpha appliquée à la couleur de dessin ou comme un masque appliqué à une texture.

Ce qui précède est une grande simplification, mais donne l'idée générale.

La plupart des programmes open source utilisent le code de tramage dérivé de l'un des projets suivants:

FreeType - un tramage de polices qui contient à la fois des modules mono et rasterizer anti-aliasing qui sont relativement faciles à utiliser autonome - qui est, pour toute forme, non seulement pour les polices. Je l'ai utilisé ce système avec succès dans plusieurs projets C ++ portable commercial.

Le système de FreeType de a été inspiré par Raph Levien Libart .

Anti-Grain est une autre bibliothèque populaire et influente C ++.

Il y a aussi système de drapeau de bord de balayage ligne mis en œuvre par Kiia KALLIO, qui semble prometteur et semble être plus rapide que Anti-grain.

La plupart, mais pas toutes ces bibliothèques acceptent des formes à base de splines Bézier et cubiques, ainsi que des segments de ligne droite. Ceux qui ne le font pas (par exemple, la bibliothèque de K. Kallio) ne prennent que des polygones à bord droit; mais il est assez facile de « aplatir » une courbe en une série de segments de ligne plus d'un choixdistance maximale de la courbe réelle. FreeType fait qu'en interne, et son code peut être emprunté si nécessaire.