Anzahl Iterationen beim Bresenham Algorithmus?
-
Hallo allerseits!
Leider hat meine Suche im Web keine Antwort zu Tage gefördert. Ich berechne einen Kreis mit Hilfe des Bresenham Algorithmus. Die Pixelkoordianten des resultierenden Kreises möchte ich gerne in einem Array speichern. Kann ich im Vorfeld bestimmen aus wie vielen Pixeln der Kreis bei einem gegebenen Radius bestehen würde bzw. nach wie vielen Schritten der Algorithmus sich terminiert? Eigentlich sollte man das doch über den Umfang bestimmen können: U=2*pi*r. Aber leider sehe ich da keinen mathematischen Zusammenhang mit meinem Testprogramm...
-
Ich glaube diese Vorberechnung wäre aufwendiger als die eigentliche Berechnung. PI bringt dich da auch nicht weiter da du im Vorfeld nicht weißt welche der Pixel in Nähe des idealen Kreises du setzen musst.
-
Danke für deine Antwort. Aber das währe doch höchst ineffizient: erst durchlaufe ich den Algorithmus um die Anzahl der Pixel zu bestimmen. Damit reserviere ich mir dann entsprechend viel Speicher um dann noch mal Breshenham zu durchlaufen? Dann währe ein Dynamisches Array effizienter oder?
Ich habe gelesen, dass der Code u.a. auch auf Graphikkarten zur Anwendung kommt. Brauchen die so etwas nicht?
-
Ich muss dazu sagen das ich kein Experte auf dem Gebiet bin es gibt hier bestimmt welche die dir das vom Mathematischen und auch von der Implementierung in Hardware besser erklären können. Aber warum willst du die Pixel in ein einzelnes Array packen? Ich würde sie direkt in ein Framebuffer packen der immer so groß ist wie die Auflösung die du anzeigen möchtest. So ähnlich machen es auch Grafikkarten nur das der Buffer im Grafikspeicher ist. Es wird also meines Wissens nie die Ergebnisse extra in ein Array abgelegt sondern direkt beim Iterieren in den Buffer geschrieben.
-
Hi,
Die Anzahl der Pixel eines Kreises läst sich relativ genau berechnen. Bis zu einem Winkel von 45° ab Mitte oben gehts unabhängig von der vertikalen Ausdehnung horizontal immer ein Pixel weiter. Also so viele Pixel wie es bis zu dem Punkt ab Mitte sind. Wie weit es bis dahin ist sagt der Sinus des Radius aus. Und das ganze wiederholt sich dann noch 7 weitere male. Unterschiede gibts nur, ob sin 45° auf einen Punkt oder zwischen zwei Punkte fällt. Aber wenn man rund 20 Punkte reserve lässt, kommt man in jedem Fall hin. Obs aber wirklich nötig ist, den gesamten Kreis zu berechnen hab ich so meine Zweifel. Wenn es nicht um extrem schelle Echtzeitbedingungen geht müsste 1/8-Kreis entsprechend 0-45° genügen, der nur jeweils Addiert oder Subtrahiert wird und jeweils mit umgekehrten Vorzeichenund vertauschten Achsen genutzt wird.
Gruß Mümmel
-
Müsste nicht der Umfang des Quadrates, das den Kreis genau einschließt, eine ziemlich gute obere Schranke für die Pixelanzahl sein?
-
Ja eigentlich schon, auch wenn mir der Sinn dahinter nicht erschließt, aber das war ja auch nicht die Frage des Threaderstellers.
-
Erstmal danke für eure Antworten!
muemmel schrieb:
Hi,
[...] Wie weit es bis dahin ist sagt der Sinus des Radius aus. Und das ganze wiederholt sich dann noch 7 weitere male. Unterschiede gibts nur, ob sin 45° auf einen Punkt oder zwischen zwei Punkte fällt. Aber wenn man rund 20 Punkte reserve lässt, kommt man in jedem Fall hin. [...]
Gruß Mümmel
Mümmel, so ganz kann ich nicht nachvollziehen was du meinst. Wenn ich von einem Radius von 20 Pixeln ausgehe und ich rechne: r*sin(pi/4)=14,1. Nach meinen Tests liegt aber erst das 21. Pixel auf der Winkelhalbierenden zwischen y- und x- Achse und nicht das 14. oder 15. Habe ich dich irgendwie falsch verstanden?
Bashar schrieb:
Müsste nicht der Umfang des Quadrates, das den Kreis genau einschließt, eine ziemlich gute obere Schranke für die Pixelanzahl sein?
Ja, die Idee ist mir auch schon gekommen. Das wäre meine "quick and dirty" Lösung
blue-tec schrieb:
[...]Aber warum willst du die Pixel in ein einzelnes Array packen[...]
Ich will eine kreisförmig über ein Bild Pixelwerte aufsummieren. Dazu muss ich wissen, ob sich ein Pixel im Inneren des Kreises oder außerhalb befindet. Wenn ich die Koordinaten eines Kreise im Speicher habe, kann ich einfach vergleichen, wo sich ein Pixel befindet. Alternativ könnte ich auch bei jedem Pixel den Abstand zum Kreismittelpunkt bestimmen und danach entscheiden. Aber ich denke das ist langsamer (?).
Also, Ich habe einige Tests gemacht. Wenn ich von einem Radius n ausgehe, dann sieht es so aus, als ob das n+1 Pixel das Ende des ersten 1/8 Kreises ist. Damit währen 8n der Vollkreis. Leider ist das nur eine Vermutung und ich habe keine Ahnung wie man das Beweisen soll...
-
8*radius+4 sollte immer genug sein.
-
wie genau? schrieb:
8*radius+4 sollte immer genug sein.
Das das genug ist, glaube ich, immerhin sind 8*radius der umfang eines Quadrats "um den Kreis mit dem Radius radius herum". Aber woher kommt die "+4"?
-
Hi waschbaerFurcht,
wenn Du von oben in der Mitte ausgehst, dann ist nach 45° der Punkt gekommen, wo der senkrechte Abstand der Pixel größer wird als der wagerechte. Das heist bis dahin kannst Du jeweils einen nach rechts gehen und die Höhe musst Du dann berechnen. Danach musst Du jeweils einen nach unten gehen und die seitliche Position berechnen. An diesem Punkt hast Du aber bei weitem keine seitliche Auslankung von 20 Pixeln, sondern nur von rund 14 Pixeln.
Aber ich glaube nciht, dass das die schnellere Variante ist. Auch ist es nicht so ganz trivial, festzustellen, ob ein Pixel im innern oder außerhalb ist. Du hast ja von jedem Pixel nur die x und die y-Position. Die einfachste Version ist, in einer richtung bis zum Rand zu gehen und zu gucken, wie oft es die linie schneidet. Bei 1 mal ists innerhalb, sonst außerhalb. Das heist es sind jede Menge indirekte Speicherzugriffe über Index nötig.
Wesentlich einfacher geht es mit der Kreisformel r² = x² + y².
Du berechnest einmal das Quadrat des Raddiusses und addierst anschleißend die Quadrate der x und der y-Abweichungen vom Mittelpunkt. Wenn die Summe kleiner ist als der vorher aus dem Radius berechnete Quadratwert ist es innerhalb. Auf modernen leistungsfähigen Prozessoren sind solche Berechnungen ein Klacks. Was anderes war es zu Zeiten von 286ern ohne FPU.Gruß Mümmel
-
Danke, ich denke ich werde das so machen.
Schade... Nicht immer ist der einfachste Weg der bei dem man am meisten lernt...