Xiaolin-Wu-Algorithmus zu Zeichnen von Linien

[Ralph S. (jjflash)]

Weil ich nicht fremde Threads kapern will (ging hier um Emojis in 
Forensoftware) mache ich einen neuen Thread auf.

Es ging um veraltetes Wissen oder veraltetes Vorgehen auch an einem 
Beispiel zum Linienzeichnen.

Ich bin wohl in manchen Dingen wirklich veraltet, hier am Beispiel 
Linienzeichnen.

Laberkopp hat mir das um die Ohren gehauen (ich gebe es ungern zu, hier 
wohl zu Recht) und darauf hin habe ich seine Aussagen zum Linienzeichnen 
für mich überprüft:

Einen Linienalgorithmus auf PC interessiert mich eher weniger, weil ich 
graphische Programme auf dem PC nur in soweit erstelle, dass ich (wie 
wohl viele auch) "einfach" fertige Bibliotheken verwende und ich mich um 
die Implementierung relativ wenig bis gar nicht kümmere (Asche über mein 
Haupt).

Bei Mikrocontrollern sieht das anders aus und ich habe mich daran 
gemacht, seine Vorschläge auszuprobieren.

Das Ergebnis war:

Xiaolin-Wu-Algorithmus ist auf Mikrocontrollern ohne 
Floatingpointunterstützung wenig brauchbar (implementiert habe ich den 
Algorithmus wie auf Wikipedia erläutert 
https://de.wikipedia.org/wiki/Xiaolin_Wus_Linien-Algorithmus):

- durch die Verwendung von Floatingpoint wird das wirklich langsam, auf 
einem AVR ist es relativ unerträglich

- auf ARM Controllern ist das bei einem STM32F4 und STM32F7 (andere 
Controller mit FP habe ich nicht) verwendbar und wenn Antialiassing 
gemacht wird wohl wirklich die erste Wahl.

Dann hat er diese Links angegeben:

--------------------------------------------------
Michael B. (laberkopp) schrieb:
Dann gibt es noch weitere Quellen

http://www.edepot.com/algorithm.html (wenn floating point so schnell wie
int ist)

https://www.phatcode.net/res/224/files/html/ch36/36-01.html
(Linienalgorithmus für schnelles clippen an Regionen)

https://www.geeksforgeeks.org/anti-aliased-line-xiaolin-wus-algorithm/
(Wu, Midpoint, Bresenham, DDA)

https://jacksondunstan.com/articles/506 (EFL verwendet in Adobe Flash)
https://github.com/skyboy/AS3-Utilities/blob/master/skyboy/utils/efla.as
--------------------------------------------------

Hiervon habe ich Algorithmen des ersten Links auf einem Controller 
laufen lassen und stelle für mich fest:

EFLA in Variation E ist auf Displays mit 480x320 Pixel Auflösung 
wirklich besser als Bresenham.

Ich werde also meine Mikrocontrollersourcen überarbeiten.

Warum dieser Thread?

Vllt. mag außer mir noch jemand diese Dinge auf einem Mikrocontroller 
nachvollziehen.

[Yalu X. (yalu) (Moderator)]

Ralph S. schrieb:
> Hiervon habe ich Algorithmen des ersten Links auf einem Controller
> laufen lassen und stelle für mich fest:
>
> EFLA in Variation E ist auf Displays mit 480x320 Pixel Auflösung
> wirklich besser als Bresenham.

Die EFLA-Algorithmen sind die direkte (und damit naheliegende) Umsetzung
der parametrischen Liniengleichungen

   x = x0 +   t
   y = y0 + m·t

bzw.

   x = x0 + m·t
   y = y0 +   t

In den Varianten A und B wird das Produk m·t direkt berechnet, in C, D
und E inkrementell, d.h. wie im DDA-Algorithmus durch fortgesetzte
Addition. In A, B und C erfolgt die Berechnung in FLoating-Point, in D
und E in Fixed-Point.

Die Verfahren sind zwar schnell, aber nicht direkt mit dem Bresenham-
Algorithmus vergleichbar, da sie i.Allg. andere Ergebnisse liefern:

Während der Bresenham-Algorithmus und der in dem Artikel zum Vergleich
herangezogene Doppelschrittalgorithmus von Wu die bestmögliche
Annäherung an die ideale Linie liefern, können die Ergebnisse der
EFLA-Algorithmen auf Grund von Rundungsfehlern mehr oder weniger von
diesem Optimum abweichen.

Bei den drei Floating-Point-Varianten wird man wegen der hohen
numerischen Auflösung selten einen Unterschied feststellen, bei den
Fixed-Point-Varianten hingegen wird an den Treppenübergängen schon
einmal ein Pixel um eine Rastereinheit verrutschen. Wenn das nicht stört
und die Effizienz im Vordergrund steht, sind die EFLA-Algorithmen
dennoch eine gute Alternative.

Ralph S. schrieb:
> Xiaolin-Wu-Algorithmus ist auf Mikrocontrollern ohne
> Floatingpointunterstützung wenig brauchbar (implementiert habe ich den
> Algorithmus wie auf Wikipedia erläutert

Das Beispiel in Wikipedia soll nicht effizient sein, sondern den
Algorithmus verständlich machen. Reale Implementation kommen auch ohne
Floating-Point aus. Wenn du aber kein Antialiasing möchtest, ist dieser
Algorithmus unnötig aufwendig.

[Ralph S. (jjflash)]

Yalu X. schrieb:
> Das Beispiel in Wikipedia soll nicht effizient sein, sondern den
> Algorithmus verständlich machen. Reale Implementation kommen auch ohne
> Floating-Point aus. Wenn du aber kein Antialiasing möchtest, ist dieser
> Algorithmus unnötig aufwendig.

Das würde ich nur für Antialiasing einsetzen. Momentan benötige ich das 
gar nicht, aber wie das bei mir immer so ist: Das ist mein Spielzeug und 
ich wurde hier angetriggert.

Jetzt möchte ich mal sehen was es in dieser Richtung so alles gibt und 
implementiere das, damit ich dann, wenn ich das eventuell brauchen kann 
auch gleich verfügbar hab.

Ich hatte mir bisher auf Controllern über Antialiasing keine Gedanken 
gemacht und auf PC einfach nur benutzt.

Aber wie gesagt, da bin ich jetzt angetriggert und guck was für mich 
eventuell Sinn macht und was nicht.