Ich arbeite mit einem Microchip dsPIC33FJ128GP802. Es ist ein kleiner DSP-basierter Mikrocontroller und hat nicht viel Leistung (40 Millionen Befehle pro Sekunde). Ich suche nach einer Möglichkeit, ein konvexes (d. H. Einfaches) Polygon zu rendern. Ich beschäftige mich nur mit 2D-Formen, Integer-Mathe und gesetzten oder klaren Pixeln (dh 1 Bit pro Pixel). Ich habe bereits Routinen zum Zeichnen schneller horizontaler und vertikaler Linien (Schreiben von bis zu 16 Pixeln in 88 Zyklen), also möchte ich einen Scanline-Algorithmus zu verwenden.
Aber alle Algorithmen, die ich gefunden habe, scheinen von Division (die 18 Zyklen auf diesem Prozessor benötigt) und Fließkomma-Mathematik (die in Software emuliert wird und daher sehr langsam ist; sie benötigt auch viel ROM) oder nehme an, dass ich viel Speicher habe. Ich habe nur 2K übrig, ~ 14K wird für Grafik-RAM meiner 16K verwendet. Kennt also jemand gute Embedded-Machine-Algorithmen, auf die er mich mit einer einfachen C- oder Pseudocode-Implementierung hinweisen kann, die ich in Assembly implementieren kann? Am liebsten lebe ich nicht in der Nähe von guten Buchhandlungen mit vielen Programmierbüchern.
Danke. :)
EDIT: Klarstellung, das ist ein Polygon-Füllalgorithmus, nach dem ich suche. Ich kann einen Polygon-Umrissalgorithmus mit dem Linienzeichnungsalgorithmus von Bresenham implementieren (wie es Marc B vorschlägt.)
EDIT # 2: Ich wollte alle wissen lassen, dass ich einen grundlegenden Algorithmus in Python habe. Hier ist ein Link zum Code. Public Domain-Code.
Wie wäre es mit Bresenham Linienalgorithmus? Nach einigen Einstellungen ist es reine Ganzzahlmathematik und kann angepasst werden, um ein Polygon durch einfache Iteration von Startpunkten entlang der Polygonkanten zu zeichnen.
Kommentare folgen:
Ich werde versuchen, dies in ASCII zu zeichnen, aber es wird wahrscheinlich wie Crud aussehen. Bresenham's kann verwendet werden, um ein gefülltes Polygon zu zeichnen, indem eine Startkante ausgewählt wird und iterativ eine Bresenham-Linie über die Leinwand parallel zu diesem Punkt bewegt wird.
Nehmen wir an, Sie haben einige Punkte wie folgt:
%Vor%Diese sind in der Sortierpriorität von links nach rechts nummeriert, also wählen Sie den Startpunkt ganz links (1) und entscheiden, ob Sie vertikal (Start 1,2) oder horizontal (1,3) gehen wollen. Das hängt wahrscheinlich davon ab, wie Ihr DSP angezeigt wird, aber lassen Sie uns mit der Vertikalen gehen.
Also ... Du benutzt die 1-2-Linie als deine Start-Bresenham-Linie. Sie berechnen die Startpunkte Ihrer Fülllinien, indem Sie die Zeilen 1-3 und 2-4 als Start- / Endpunkt verwenden. Starten Sie für jeden eine Bresenham-Berechnung, und zeichnen Sie einen anderen Bresenham zwischen diesen beiden Punkten. Ein bisschen wie:
%Vor%etc ... bis Sie das Ende einer dieser Zeilen erreichen. In diesem Fall wäre das der Fall, wenn der untere Startpunkt (4) erreicht. An diesem Punkt beginnst du, die 4,3-Linie zu durchlaufen, bis du Punkt 3 mit beiden Startpunkten erreichst, und du bist fertig.
%Vor%Die Bindestriche sind die Anfangspunkte, die Sie entlang von 1-3 und 2-4 berechnet haben, und die Schrägstriche sind die Fülllinien.
Das funktioniert natürlich nur, wenn die Punkte richtig sortiert sind und Sie ein konvexes Polygon haben. Wenn es konkav ist, müssen Sie sehr darauf achten, dass Ihre Fülllinien nicht über die Grenze hinausgehen oder eine Vorverarbeitung durchführen und das ursprüngliche Poly in zwei oder mehr konvexe Teile unterteilen.
Thomas, wenn Sie einen Bresenham-Linienzeichnungsalgorithmus zur Verfügung haben, dann verwenden Sie ihn als Grundlage für weitere Verbesserungen: Unterteilen Sie Ihr Polygon in Unterpolygone mit einer horizontalen Schnittlinie durch jeden Scheitelpunkt. Beginnen Sie dann, die 2 linken und rechten Seiten jedes dieser Sub-Polys unter Verwendung von Bresenham zu verfolgen. Auf diese Weise haben Sie die 2 Endpunkte jeder Scanlinie in Ihrem Polygon.
Vielleicht möchten Sie Michael Abrashs Artikel zu Dr. Dobbs über Polygon fill / raster / etc . Es verwendet Festkomma-Mathematik
Ich würde damit beginnen, das Polygon in eine Sammlung von Dreiecken umzuwandeln und diese zu rendern, weil Dreiecke leicht von Scanlinien gerendert werden können. Obwohl es trotzdem einige Details gibt.
Im Wesentlichen erhält die draw-triangle Unterprozedur ein unformatiertes Dreieck und fährt fort:
if -Tests für jede Scanlinie durchführen möchten, um festzustellen, ob sich die Steigung geändert hat. Es kann einfacher sein, das Problem in zwei Teile zu teilen. Suchen / schreiben Sie zuerst einen Algorithmus, der ein Dreieck zeichnet und ausfüllt. Zweitens, schreibe einen Algorithmus, der ein beliebiges Polygon in Dreiecke zerlegt (mit verschiedenen Kombinationen der Ecken).
Um ein Dreieck zu zeichnen / füllen, verwenden Sie Bresenhams Linienalgorithmus, um gleichzeitig eine Linie zwischen den Punkten 0 und 1 und zwischen 1 und 2 zu zeichnen. Für jeden Eingabepunkt x , zeichnen Sie das Pixel, wenn es gleich oder dazwischen ist die y -Punkte, die von den zwei Zeilen generiert werden. Wenn Sie einen Endpunkt erreicht haben, fahren Sie fort, indem Sie die noch nicht fertiggestellte Seite und die Seite verwenden, die noch nicht verwendet wurde.
Bearbeiten:
Um Ihr konvexes Polygon in Dreiecke zu zerlegen, ordnen Sie die Punkte der Reihe nach an und nennen sie P1, P2, ... PN . Lassen Sie P1 Ihren "root" Punkt und erstellen Sie Dreiecke mit diesem Punkt und Kombinationen von benachbarten Punkten. Zum Beispiel würde ein Fünfeck die drei Dreiecke P1-P2-P3 , P1-P3-P4 und P1-P4-P5 ergeben. Im Allgemeinen wird ein konvexes Polygon mit N Seiten in N-2 Dreiecke zerlegt.