Notizen

Signed-Distance-Rasterisierungsverfahren

tagscomputergrafik
aliasesSD-Rasterisierung

Das Signed-Distance-Rasterisierungsverfahren ist der quasi-Standard zum Rasterisieren von Dreiecken.

Voraussetzungen

Die Verticies der Dreiecke sind gegen den Uhrzeigersinn angeordnet. Dies entspricht auch dem Standard in der Mathematik.

Grundidee

Wir malen ein Pixel an, wenn dessen Mittelpunkt im Dreieck liegt. Zum bestimmen, ob ein Punkt in einem Dreieck liegt, geht man die Vektoren des Dreiecks ab. Wenn ein Punkt links von jedem der Vektoren des Dreiecks liegt, dann ist er innerhalb des Dreiecks.

Beispiel

  • Der Punkt ist innerhalb des Dreiecks, denn er ist links von jedem der Dreiecksvektoren , und .
  • Der Punkt ist nicht innerhalb des Dreiecks. Er ist zwar links von den Vektoren und , aber nicht links vom Vektor .

Mathematische Bestimmung

Ein Punkt ist links von einer Kante , wenn:

Dabei ist die Normale nach links.

Siehe auch

Beispiel

Gebeben:

Der Punkt wäre links von , wenn das Ergebnis positiv wäre. Es ist aber negativ, deswegen ist nicht links von .

Algorithmisch

Wendet man diese Regel für alle 3 Kanten des Dreiecks an, kann man bestimmen, ob ein Punkt im Dreieck ist.

Optimierung

Bounding Box, die das Dreieck so enganliegend umschließt wie möglich

Notizen aus der VL

Signed-Distance Rasterisierungsverfahren

  • Standard

Dreiecke rotieren standardmäßig in der Mathematik gegen den Uhrzeigersinn.

Idee des Algorithmus: Man geht die Vektoren des Dreiecks ab. Wenn bei jedem der 3 Vektoren der Punkt links von dem Vektor ist, dann ist er innerhalb. Ist der Punkt nicht an allen Vektoren links, ist er außerhalb.

Idee (tafel): Wir gehen den (konvexen) Polygonzug entlang und prüfen, ob der gegebene Punkt immer auf der Seite “nach innen” ist. Heißt: Polygonzug -> gerichtete Kanten:

algorithmisch:

Oft hilft es Richtungen zu Normalisieren:

“Die Richtung von a nach b ist der Vektor b-a geteilt durch seine Länge (=> normalisiert)”

Aus einer Richtung in 2D kann direkt eine orthogonale Richtung, eine Normale, abgedeckt werden:

“Die Normale von einer Richtung.”

Man tauscht die Komponenten und bei einer streut man ein negatives Vorzeichen rein

Skalarprodukt

Wir haben 2 Vektoren 𝕣, dann ist das Skalarprodukt (in der Computergrafik so geschrieben, “bracket notation”), alternativ , aus der Grundschule eher bekannt

Auch gut zu Wissen: .

Dementsprechend ist das Skalarprodukt von 2 orthogonalen Richtungen = 0.

=> Wann ist der Punkt p links von der Kante b-c ?

Wenn

Also wenn ist, dann ist p links von der Kante.

Performance Optimierung

-> Bounding Box, die das Dreieck so enganliegend umschließt wie möglich

Backlinks