[A] Primitive zeichnen

Vertexwahn

mit Bilder:

Als Word2003: http://loop.servehttp.com/~vertexwahn/RunLengthSlice.pdf
Als PDF: http://loop.servehttp.com/~vertexwahn/RunLengthSlice.doc

Ben04

Ich finde, dass deinen Weg diesen Algorithmus zu erklären sich viel leichter geometrisch erklären lässt als mit mathematischen Formeln. Hier ist mein Ansatz. Vielleicht kannst du ja irgendetwas gebrauchen.

Als erstes würde ich das Segment nicht in der Mitte eines Pixels starten lassen sondern an einer Kreuzung des Rasters. Hierdurch gibt es nur noch 2 verschiedene Teilsegmente, deren Länge sich auch leicht herausfinden lässt.

Man beschränkt sich auf das erste Oktant und auf Segmente welche vom Nullpunkt aus auf einen Punkt (x, y) gehen (also an sich zeichnet man einen Vektor). Man stellt sich das Segment zum Punkt (y, y) vor. Dieser Spezialfall ist einfach und besteht aus y 1-Pixel Teilsegmenten.

Diese zieht man entlang der X-Axe auseinander bis man die gewünschte Länge erreicht hat (ohne auf das Raster zu achten, also die Pixels werden zu Rechtecken mit rationaler Länge) und man erhält ein Segment das immer noch aus y Teilen besteht. Da wir nichts entlang der Y-Axe verändert haben sind diese Teile immer noch 1 Pixel hoch. Die Länge lässt sich einfach mittels Thales bestimmen da die Höhe bekannt ist und sie ist y/x.

Da diese verzogenen Pixel aber nicht mehr rastergerecht sind müssen wir sie etwas anpassen damit sie wieder in das Gitter passen. Da die Höhe passt müssen wir nur die Länge anpassen. Da gibt es zwei Möglichkeiten : Auf- oder Abrunden. Also dein Q oder Q+1.

Wie man ein Teilsegment raster dürfte klar sein. Bleibt also nur noch zu bestimmen wann man welches Teilsegment rastert. Hier kann ich dir nicht mehr ohne weiteres folgen in deinem Artikel allerdings ist es glaub ich ist es der gleiche Ansatz wie im normalen Bresenham Algo.

Man verhält sich die reale Länge des Segments entlang der X-Axe und die des Rasterstrichs. Dies läuft auf banales Aufsummen heraus da man die Längen aller Teilstücke kennt. Ist der Betrag der Differenz (also die Abweichung vom optimalen Strich) kleiner als 0,5 gibt es ein kleines Stück und falls sie größer ist gibt es ein großes (da der Rasterstrich hinterher hinkt).

Durch genauere Betrachtung stellt man fest, dass die reale Länge immer eine rationale Zahl ist mit Teiler y. Durch ein wenig ausmultiplizieren kann man also auch alles mit Ganzzahlen machen. (Man sollte hier aber über den möglichen Überlauf sprechen und wieso dieser hier keine Rolle spielt.)

Um die Endpunkte in der Mitte der Pixel zu haben schneidet man die Anfangs- und Endteilstücke einfach in zwei und rundest wie man es gerade braucht.

Du geht ausgiebig auf das Problem des Abrundens bei 0,5 ein. Wieso ist das so wichtig? Mich stört es nicht wenn da abgerundet wird. Ich habe deine Funktion welche alle Oktanten beherrscht jetzt nicht im Detail angeschaut allerdings wird da auch richtig gerundet wenn es sich nicht um das 1. Oktant handelt? Darauf müsstest du eigentlich eingehen um konsequent zu sein. Dadurch, dass man dein Segment nämlich auf den Kopf stellt wird das Runden verändert.

Du wirfst den Leuten an den Kopf, dass es 4 verschiedene Teilsegmente gibt ohne wirkliche Begründung. Nicht sonderlich schön allerdings kann man das durchaus in einem Artikel machen der sich mehr mit der Implementierung beschäftigt. Dann gehst du aber ausgiebig auf das Problem der Länge dieser Teilsegmente ein. Diese könntest du konsequenterweise in diesem Fall auch den Leuten einfach an den Kopf werfen.

Wer sich für eine Begründung interessiert, der ließt bis er dies an den Kopf geworfen kriegt. Wer sich nur für einen funktionierenden Algo interessiert der hört bei den Formeln auf zu lesen. Du wechselst in der Mitte des Artikels die Zielgruppe.

Die Implementierung könntest viel lesbarer machen indem du die horizontalen Striche in eine eigene Funktion auslagerst.

Ist CImg<T> ein realer MS Type oder etwas was du dir ausgedacht hast?

Die Einleitung finde ich gut gemacht.

Soll nur konstruktive Kritik sein. Ist nicht schlecht was bis jetzt hast.

Jester

Ben04 schrieb:

Als erstes würde ich das Segment nicht in der Mitte eines Pixels starten lassen sondern an einer Kreuzung des Rasters. Hierdurch gibt es nur noch 2 verschiedene Teilsegmente, deren Länge sich auch leicht herausfinden lässt.

Das sehe ich gerade nicht. Welchen der jeweils vier in Frage kommenden Gitterpunkte wählst Du? Und entspricht das nicht gerade der Verschiebung des Gitters um eine halbe Gitterzelle in beiden Richtungen, so wie's auch in den Zeichnungen angedeutet ist?

Du wirfst den Leuten an den Kopf, dass es 4 verschiedene Teilsegmente gibt ohne wirkliche Begründung. Nicht sonderlich schön allerdings kann man das durchaus in einem Artikel machen der sich mehr mit der Implementierung beschäftigt. Dann gehst du aber ausgiebig auf das Problem der Länge dieser Teilsegmente ein. Diese könntest du konsequenterweise in diesem Fall auch den Leuten einfach an den Kopf werfen.

Wer sich für eine Begründung interessiert, der ließt bis er dies an den Kopf geworfen kriegt. Wer sich nur für einen funktionierenden Algo interessiert der hört bei den Formeln auf zu lesen. Du wechselst in der Mitte des Artikels die Zielgruppe.

Das sehe ich ähnlich. Ich hab mir die Rechnung angesehen. Die wird sich aber wohl sonst kaum jemand antun. Schon der Anfang "Klar ist:" und dann eine Formel mit Variablen, die irgendwo 2 Seiten vorher mal definiert wurden und dann eine völlig unmotivierte Berechnung wo in der Mitte noch lauter neue Variablen eingeführt werden. Sowas ist extrem anstrengend zu lesen. (und ich hab einiges an übung mit sowas). Vielleicht hilft eine Zeichnung in der die wichtigsten Variablen eingezeichnet sind? Und bitte mehr Motivation... was willst Du rauskriegen? Warum? Was ist die Idee, die hinter dem Beweis/der Rechnung steckt? So sieht das alles so aus als würde es vom Himmel fallen.

Ich finde es schön, dass Du auch die Theorie mit darstellen möchtest. Damit das aber von vielen Lesern genutzt wird, solltest Du versuchen es dem Leser so angenehm wie möglich zu machen. Eventuell ist es auch interessant dem leser die Möglichkeit zu geben nur das Ergebnis zu lesen und die Rechnungen zu überspringen, indem Du irgendwo genau sagt was Aussage ist und was zur Rechnung gehört.

Ben04

Jester schrieb:

Ben04 schrieb:

Als erstes würde ich das Segment nicht in der Mitte eines Pixels starten lassen sondern an einer Kreuzung des Rasters. Hierdurch gibt es nur noch 2 verschiedene Teilsegmente, deren Länge sich auch leicht herausfinden lässt.

Das sehe ich gerade nicht. Welchen der jeweils vier in Frage kommenden Gitterpunkte wählst Du? Und entspricht das nicht gerade der Verschiebung des Gitters um eine halbe Gitterzelle in beiden Richtungen, so wie's auch in den Zeichnungen angedeutet ist?

Ich wollte nicht sagen, dass der fertige Algo in der Mitte starten soll, sondern dass sich der Algo einfacher entwickeln lässt wenn man davon ausgeht. Am Ende geht man halt dann das erste und das letzte Segment in der Mitte durchschneiden und schon kann man wieder die Mitten der Pixel als Start und Ende angeben. An sich macht Vertexwahn ja auch nichts anderes in dem er sagt, dass M = Q/2. Du definierst es halt so wie es dir gerade am besten passt.

Vertexwahn

Ben04 schrieb:

Ist CImg<T> ein realer MS Type oder etwas was du dir ausgedacht hast?:)

Nö das ist eine Klasse von dieser Bibliothek:
http://cimg.sourceforge.net/

Kleiens Beispiel:

int main() {
    CImg<unsigned char> img(640,400,1,3);    // Define a 640x400 color image with 8 bits per color component.

    img.save_png("test.png");
    img.display("Test");  // Display the image in a display window.
    return 0;
}

ich wollte dem Leser nur einen Weg aufzeigen, wie man mit ganz einfachen mitteln ein paar Pixel auf dem Bildschirm einfärben kann. Jedoch bin ich mir jetzt nicht sicher ob ich im Artikel auf die Bibliothek kurz eingehen soll oder ob ich einfach nur Pseudocodemäßig einfach DrawPixel schreiben soll, wenn ein Pixel gepolottet wird...

Ben04

An sich brauchst du ja nur einen Weg eine Punktmenge auszugeben. Da hast du sehr viele Möglichkeiten : Array, Funktor. DrawPixel ist ja an sich der Funktorweg. Ich würde schon C++ verwenden und eine hypothetische Funktion PutPixel(x, y) verwenden. Die kann jeder dann seinen Bedürfnissen anpassen.

Vertexwahn

was ich momentan so treibe:

http://loop.servehttp.com/~vertexwahn/uploads/Rastern von Strecken.pdf
http://loop.servehttp.com/~vertexwahn/uploads/Rastern von Strecken.doc

der Hauptteil fehlt noch

Ben04

Ich hab jetzt keine Zeit mir das im Detail durch zu lesen. Es sieht aber schon viel besser aus als die Vorgängerversion.

Vertexwahn

So: nochmal überarbeitet:

http://loop.servehttp.com/~vertexwahn/uploads/Rastern von Strecken2.pdf
http://loop.servehttp.com/~vertexwahn/uploads/Rastern von Strecken2.doc

Jester

Hi,

ich lese es mal durch und schreib nebenbei gleich meine Meinung dazu hier rein, alles IMHO(!). Zunächst fällt mir auf, dass der Artikel unheimlich lang ist. Zu lang imho. Ich denke, da solltest Du imho was kürzen, wenn Du darauf hoffen möchtest, dass sich jemand komplett durchbeißt.

Der erste Teil über Koordinatensysteme lässt sich denke ich ganz gut kürzen. Ist das Rastern von Punkten und deren Abweichung vom echten Punkt für den restlichen Artikel überhaupt von Bedeutung? Ich hab das Gefühl, dass das nicht wirklich der Fall ist. Der Inhalt ist auch wenig überraschend. Die Bilder würde ich etwas kleiner machen und nebeneinander setzen. Das spart Platz.

Warum benötigst du einen eigenen abschnitt, um dich auf ganzzahlige werte einzuschränken? Ich denke, die Mehrheit wird mit ihrer Vorstellung bereits an dieser Stelle einsteigen: Pixelgrafik und ganzzahlige Koordinaten.

Der Teil in dem Du die Bibliotheken kurz einführst ist zwar nett, aber für den Artikel nicht zwingend nötig. Setze doch einfach eine drawPixel-Funktion als gegeben voraus. Die Beschreibung der Bibliotheken würde ich dann in einen Anhang verschieben und auf den Verweisen. Wer das direkt sehen will springt nach hinten und schaut. Aber die Mehrheit glaubt, dass es sowas wie drawPixel gibt und liest lieber was über das Thema des Artikels.

Das Kapitel "der triviale Ansatz" gefällt mir sehr gut. Das sollte aber imho viel viel früher im Artikel kommen. Eventuell geht das Bild, das die Problematik bei Strecken mit starker Steigung zeigt auch etwas kleiner?

Den kurzen Abstecher zu Bresenham würde ich einfach mit in den vorigen Abschnitt aufnehmen. Eine richtige Quellenangabe fände ich besser.

Die Idee zum Run-Length-Slice-Algorithmus kommt jetzt viel besser rüber! (den teil der unter "die beobachtung" steht).

Der Teil unter "Die idee" ist nicht wirklich neu. Das machten wir doch schon bei "der triviale ansatz", oder? Bring es doch dort schon. Das einzige was neu ist, ist die idee die segmentlängen vorher zu berechnen. Das passt auch in den Teil "Die Beobachtung" noch mit rein. Vielleicht kannste da dann ja da dann "Idee" drüber schreiben?

Die Überschrift des Teils "Schafe und Mathematiker" hat imho wenig mit dem Inhalt des Abschnitts zu tun. Ich würde die Geschichte ganz weglassen. Deine Interpretation ist imho ziemlich einseitig und macht auch wenig lust darauf den rest des abschnitts zu lesen (ist schließlich nur unpraktisches zeug über dessen betrachtung man das ziel aus den augen verliert). Kennt jeder die Interfallschreibweise? vielleicht wäre 0 < m < 1 sicherer. Auch eine Erklärung, was das für die Steigung bedeutet könnte helfen (Steigung kleiner als 45° und man kann daher entlang der x-achse rastern). Außerdem vereinfachst Du zu Ursprung (0,0). Das geht doch generell und immer für alle Linienzeichenalgorithmen, oder? Dann würde ich mir überlegen, das als warm-up direkt zu Anfang zu bringen. Dann kannst du im ganzen restlichen artikel darauf zurückgreifen.

Die Definition von A_i geht ein bißchen unter, weil es ganz verschämt am Ende eines Satzes steht. Auch eine sprachliche Definition hilft sicher die Bedeutung zu erfassen.

Bei der Berechnung von A_i:
Du schreibst "Durch Umformen ergibt sich"... umgeformt ist schon. Das ist eher Einsetzen.

Das Q würde ich ganz zu Anfang definieren und dort auch den Sinn des Restes direkt nennen. Nämlich eine Formel für die Segmentlängen zu erhalten... die enthält dann ja auch das Q.

Vielleicht hilft es auch, wenn Du Definitionen durch die Verwendung von := deutlich machst. Ich muss oft nach oben scrollen um zu sehen, ob der ausdruck nun gerade ne gleichung ist, oder eine neue variable definiert wird.

Der Teil ist sehr anstrengend zu lesen. Mir fehlt ein bißchen das Ziel, es fallen ständig neue Variablen vom Himmel und es wird mehr oder weniger unmotiviert umgerechnet. Ich würde versuchen genauer zu formulieren, was rauskommen soll (kann man die formeln vielleicht einfach direkt angeben?) und auch darauf eingehen, wie man diese nun implementieren kann. die rechnung würde ich evtl. dann weglassen oder in nen anhang packen. ich kann mir kaum vorstellen, dass sich das jemand komplett durchliest.

Was hilft es try1 zuerst vorzustellen? Würde ich entweder weglassen, oder nur die nötigen Modifikationen für try2 erklären, nicht nochmal komplett abdrucken.

Du zeigst zwei Varianten, die für alle Steigungen funktionieren. Kannst Du was zum Unterschied sagen? Mir persönlich ist das etwas zu viel Code.

Vertexwahn

Jester schrieb:

ich lese es mal durch und schreib nebenbei gleich meine Meinung dazu hier rein, alles IMHO(!). Zunächst fällt mir auf, dass der Artikel unheimlich lang ist. Zu lang imho. Ich denke, da solltest Du imho was kürzen, wenn Du darauf hoffen möchtest, dass sich jemand komplett durchbeißt.

hab den Artikel um 10 Seiten gekürzt

Jester schrieb:

Der erste Teil über Koordinatensysteme lässt sich denke ich ganz gut kürzen. Ist das Rastern von Punkten und deren Abweichung vom echten Punkt für den restlichen Artikel überhaupt von Bedeutung? Ich hab das Gefühl, dass das nicht wirklich der Fall ist. Der Inhalt ist auch wenig überraschend. Die Bilder würde ich etwas kleiner machen und nebeneinander setzen. Das spart Platz.

ich habe diesen Teil jetzt ganz verschwinden lassen

Jester schrieb:

Warum benötigst du einen eigenen abschnitt, um dich auf ganzzahlige werte einzuschränken? Ich denke, die Mehrheit wird mit ihrer Vorstellung bereits an dieser Stelle einsteigen: Pixelgrafik und ganzzahlige Koordinaten.

Hab den Abschnit auch vernichtet

Jester schrieb:

Das Kapitel "der triviale Ansatz" gefällt mir sehr gut. Das sollte aber imho viel viel früher im Artikel kommen. Eventuell geht das Bild, das die Problematik bei Strecken mit starker Steigung zeigt auch etwas kleiner?

Grafik ist jetzt kleiner. Hab den Abschnit jetzt ziemlich nah an den Anfang gepackt

Jester schrieb:

Der Teil unter "Die idee" ist nicht wirklich neu. Das machten wir doch schon bei "der triviale ansatz", oder? Bring es doch dort schon. Das einzige was neu ist, ist die idee die segmentlängen vorher zu berechnen. Das passt auch in den Teil "Die Beobachtung" noch mit rein. Vielleicht kannste da dann ja da dann "Idee" drüber schreiben?

ich habs zusammengefasst - überschrift ist weiterhin "die beobachtung"

Jester schrieb:

Die Überschrift des Teils "Schafe und Mathematiker" hat imho wenig mit dem Inhalt des Abschnitts zu tun. Ich würde die Geschichte ganz weglassen.

schon passiert

Jester schrieb:

Bei der Berechnung von A_i:
Du schreibst "Durch Umformen ergibt sich"... umgeformt ist schon. Das ist eher Einsetzen.

hab ich geändert

Jester schrieb:

Kennt jeder die Interfallschreibweise? vielleicht wäre 0 < m < 1 sicherer. Auch eine Erklärung, was das für die Steigung bedeutet könnte helfen (Steigung kleiner als 45° und man kann daher entlang der x-achse rastern). Außerdem vereinfachst Du zu Ursprung (0,0). Das geht doch generell und immer für alle Linienzeichenalgorithmen, oder? Dann würde ich mir überlegen, das als warm-up direkt zu Anfang zu bringen. Dann kannst du im ganzen restlichen artikel darauf zurückgreifen.

Die Definition von A_i geht ein bißchen unter, weil es ganz verschämt am Ende eines Satzes steht. Auch eine sprachliche Definition hilft sicher die Bedeutung zu erfassen.

Das Q würde ich ganz zu Anfang definieren und dort auch den Sinn des Restes direkt nennen. Nämlich eine Formel für die Segmentlängen zu erhalten... die enthält dann ja auch das Q.

Vielleicht hilft es auch, wenn Du Definitionen durch die Verwendung von := deutlich machst. Ich muss oft nach oben scrollen um zu sehen, ob der ausdruck nun gerade ne gleichung ist, oder eine neue variable definiert wird.

Der Teil ist sehr anstrengend zu lesen. Mir fehlt ein bißchen das Ziel, es fallen ständig neue Variablen vom Himmel und es wird mehr oder weniger unmotiviert umgerechnet. Ich würde versuchen genauer zu formulieren, was rauskommen soll (kann man die formeln vielleicht einfach direkt angeben?) und auch darauf eingehen, wie man diese nun implementieren kann. die rechnung würde ich evtl. dann weglassen oder in nen anhang packen. ich kann mir kaum vorstellen, dass sich das jemand komplett durchliest.

Was hilft es try1 zuerst vorzustellen? Würde ich entweder weglassen, oder nur die nötigen Modifikationen für try2 erklären, nicht nochmal komplett abdrucken.

heute keine Zeit mehr dafür

http://loop.servehttp.com/~vertexwahn/uploads/Rastern von Strecken3.pdf
http://loop.servehttp.com/~vertexwahn/uploads/Rastern von Strecken3.doc

Jester

hey, ich hab grad nochmal drüber geschaut. Bin bis Seite 6 einschließlich gekommen (also etwa bis da wo du überarbeitet hast). Liest sich prima!