Odd even rule vs. Nonzero Winding Number rule

[hajaj]

Ich sags nur ungern, aber ich verstehe die "einfachen" Sachen wie die "Odd even rule" und die "Nonzero Winding Number rule" leider noch nicht. :(

Kann mir bitte wer die zwei Dinger erklären? Wär voll nett ... :)

[klwe]

Even odd rule:

Du nimmst eine scanline, dann schaust du für jeden Punkt auf dieser Scanline, wieviele Linien des Polygons diese schneiden, wenn ungerade, dann ist er inside, sonst outside.

Nonzero winding:
Du schaust dir wieder jeden Punkt an und schaust, in welcher Richtung die Vertices darum verlaufen (im oder gegen UZS). Im einen Fall subrahierst du 1 im andern Fall addierst du 1. Hat jetzt ein Punkt in Summe dann einen Wert <> 0 ist er inside und muss gefüllt werden, sonst ist er outside und bleibt weiss.


Bin mir zwar nicht im Klaren, bei welchem Beispiel das wichtig wäre, aber so ungefähr funktionierts (so hab ichs halt verstanden) - Details siehe Buch (zB Richtung berechnen, wenn nicht gegeben usw.)

[and_Y]

Die odd-even-rule ist mir klar:
Scanline durchlegen (z.B. knapp unter dem Punkt C)
count auf 0 setzen
Kante BC schneidet Scanline -> count=1 (anfangen auszufüllen)
Kante AB schneidet Scanline -> count=2 (aufhören auszufüllen)
Kante AG schneidet Scanline -> count=3 (anfangen auszufüllen)
Kante DB schneidet Scanline -> count=4 (aufhören auszufüllen)


die non-zero-winding-number-rule hab ich mir im Buch schon mehrmals durchgelesen und mit der Zeichnung im Buch (od. auf den Folien) versucht nachzuspielen aber ich bekomm es einfach nicht hin:

Ich lege wieder knapp unter dem Punkt C eine Scanline durch.
count=0
Kante BC schneidet v.r.n.l. -> count=1
Kante AB schneidet v.r.n.l. -> count=2
nun ist count eben nicht 0, also füllt der alg. weiter ??? und somit ist die exterior-Fläche keine mehr ???
Kante GA schneidet v.r.n.l. -> count=3
Kante DE schneidet v.l.n.r. -> count=2 -> das sieht nicht gut aus :confused:

hüfe!

[klwe]

Habe mir das im Detail nicht sooo genau angeschaut, wie das mit der nonzero-Geschichte funktioniert. Aber grob schaust du dir die Flächen an und dazu die jeweiligen Polygonkanten. Für jedes UZS (Teil-)Polygon addierst du eins für jedes GUZS-(Teil-)Polygon subtrahierst du 1 (oder vice versa). Das ist mal der grundsätzliche Algorithmus und das dürfte mit den Buch-Beispiel halbwegs stimmen. Wies im Detail zu rechnen ist = ?

[Curious Yellow]

http://www.iam.unibe.ch/~fcglib/special_www/cg_lecture/lectContent/2d_geometry/applets/applet/pointInPolyAppletIntro.php
hilft vielleicht:) ...aber kommt das in irgendeinem beispiel vor?

mfg C.

[and_Y]

Das Applet ist ja echt super!
... aber kommt das in irgendeinem beispiel vor? ...Das nicht, aber ich hab mir einfach gedacht, dass es nicht so schwer sein kann das hinzukriegen.

Wenn man sich vorstellt, dass man selber der Vektor von dem beliebigen Punkt aus ist, dann geht das ganz einfach :)
Mein Fehler war zu glauben, dass es um absolute Werte geht wie z.B. Vektor BC geht v.r.n.l wenn man das Obekt als fix in einem Koordinatensystem sieht.
Ich dachte: OK, x-Wert von B ist größer als der von C -> BC kreuzt meine "scanline" v.r.n.l.

Aber wir wissen ja: alles ist relativ ! :thumb:

[navyseal]

da die seite mit dem applet leider nicht mehr funktioniert ....
hier noch eine seite mit ner recht einfachen erklärung
http://www.cs.rit.edu/~icss571/filling/alt_parity.html