Allgemeiner Algorithmus für Rastering -Vektorbild

Question

Was ist der allgemeine Algorithmus des rasterisierenden Vektorbildes? Ich habe viele Algorithmen rasterisierender Primitiven wie Linien, Kreise, Bezier -Kurven usw. gefunden, aber für den General, was soll ich tun? Gehen Sie einfach für Vektorfigur im Vektorbild, holen Sie sich seine Pixel und setzen Sie sie in Rasterbild? Oder etwas anderes?

Und eine andere Frage: Wie kann ich die Zeit der Verarbeitung mithilfe von Parallelität verbessern? Ich kann zum Beispiel Vektorfiguren trennen und gleichzeitig ihre Pixel bekommen. Aber vielleicht gibt es andere Methoden, um dies zu tun?

Answer 1

Der allgemeine Rasterisierungsalgorithmus ist dies für jedes Polygon im Bild.

(Ein Polygon ist definiert als eine oder mehrere geschlossene Kurven aus geraden Liniensegmenten und parametrischen Splines-in der normalen Praxis sind dies 2nd-Ordnung (Conic alias quadratisch) und drittklasse (kubisch) Bézier-Splines. Diese geschlossenen Kurven sind so definiert, dass dies so definiert ist Das Innere befindet sich immer links, da die Kurve durchquert wird, so dass gewöhnliche Formen gegen den Uhrzeigersinn und die Löcher im Uhrzeigersinn laufen.)

(i) (Projektion) Konvertieren Sie das Polygon in das gleiche Koordinatensystem wie die Zielbitmap. Die Auflösung muss nicht gleich sein, und für Anti-alias-Bilder ist oft größer: Zum Beispiel verwendet Freetyp 64. Pixel.

(ii) (Machen Sie in Y monotonisch) Teilen Sie bei Bedarf jedes Segment des Polygons in kleinere Segmente auf, die kontinuierlich nach oben oder nach unten laufen. Diese Stufe ist nur für gekrümmte Segmente benötigt und ist bei der Verwendung von Bézier -Splines relativ einfach. Die übliche Methode besteht darin, wiederholt zu halbieren, bis die Monotonizität erreicht ist. Alle horizontalen Segmente verwerfen.

(iii) (markieren Sie die Laufgrenzen) Zeichnen Sie jedes Segment in eine temporäre Bitmap. Verwenden Sie Bresenhams Algorithmus für gerade Linien. Bei Kurven, bis die Linie nicht weiter als (z. B.) 1/8 eines Pixels aus der realen Kurve ist, verwenden Sie dann eine gerade Linie von Anfang bis Ende. Markieren Sie beim Zeichnen in irgendeiner Weise Pixel, um (a) festzustellen, ob sie Starts oder Enden von Läufen sind - Abwärtslinien sind Starts und Aufwärtslinien sind Enden; (b) Die Abdeckung - der Bruchteil des Pixels, der sich in der Form befindet. Hier unterscheidenungleich Null gegen gerade ungerade) Werden unterschieden.

(iv) (Scan) Durchqueren Sie die temporäre Bitmap, Zeile für Zeile. Scannen Sie für jede Zeile von links nach rechts. Verwalten Sie einen Zustand, der angibt, ob sich die aktuelle Position in der Form befindet oder nicht, indem Sie (z. B.) die in der Bitmap gespeicherte Zahl einer gespeicherten Zahl hinzufügen. Bei einer einfachen Monochrom -Rasterisierung wird diese in der vorherige Phase geschriebene Zahl +1 bei der Überquerung einer Kante in die Form und -1 sein, wenn er aus der Form kommt. Akkumulieren Sie Pixelläufe im selben Zustand. Senden Sie die Läufe an Ihr Zeichenmodul: Zum Beispiel werden Freetype -Ausläufe aus einer Y -Koordinaten-, Start- und End -X -Koordinaten und der Abdeckung von 0 bis 255. Das Zeichnungsmodul können die Abdeckung als Alpha -Wert verwendet, das auf die aktuelle Zeichnungsfarbe angewendet wird , oder als Maske, die auf eine Textur angewendet wird.

Das obige ist eine große Überverfolgung, gibt aber die allgemeine Idee.

Die meisten Open-Source-Programme verwenden den Rasterisierungscode aus einem der folgenden Projekte:

Freetyp - Ein Schriftgeräte, der sowohl Mono- als auch Anti-Aliasing-Rasterizer-Module enthält, die relativ einfach zu verwenden sind- dh für jede Form, nicht nur für Schriftarten. Ich habe dieses System in mehreren kommerziellen tragbaren C ++ - Projekten erfolgreich verwendet.

Das System von Freetype wurde von Raph Leviens inspiriert Libart.

Anti-Korn ist eine weitere beliebte und einflussreiche C ++ - Bibliothek.

Es gibt auch die Scan-Line Edge Flag-System Implementiert von Kiia Kallio, die vielversprechend aussieht und schneller zu sein scheint als Anti-Korn.

Die meisten aber nicht alle dieser Bibliotheken akzeptieren Formen aus quadratischen und kubischen Bézier -Splines sowie geraden Liniensegmenten. Diejenigen, die nicht (z. B. K. Kallios Bibliothek) nicht geschnittene Polygone nehmen; Es ist jedoch ziemlich einfach, eine Kurve in eine Reihe von Liniensegmenten zu "flach", die näher als eine gewünschte maximale Entfernung von der tatsächlichen Kurve sind. Freetype macht das intern, und sein Code kann bei Bedarf ausgeliehen werden.