Computergrafik - lineare Interpolation (Theorie)

[wry]

Hi,

hab folgendes theoretisches Problem (zu Computergrafik):

Gegeben ist ein Dreieck mit den Punkten:
p1=(0,0,0), p2=(1,0,0), p3=(0,1,0)

und den jeweiligen Ecken-Farben:
c1=(0.5,0.6,07), c2(..), c3(..)

Welche Farbe ergiebt sich am Punkt
p=(...)
durch lineare Interpolation?



Hab jetzt schon ein ganzes weilchen gegoogelt aber ich hab nichts verständliches dazu gefunden ..
Kann mir vielleicht jemand einen Tipp geben? ;(

[huha]

X-D -- ich sitze am selben Problem.
Ich habe versucht, das Ganze mit einem Verlaufsalgorithmus zu lösen, was auf den ersten Blick ganz okay aussieht, ich muß das aber nochmal nachprüfen, ob das wirklich so einfach ist.
Wenn du gräßlichen VB-Code akzeptierst (das Zeug mußte schnell geschrieben werden und VB ist für sowas ideal), dann melde dich.

-huha

edit: urgs, gerade nachgeprüft, aber der Verlauf ist so buggy und geht auch nur in Grenzfällen so, wie man's will ;(

-huha

[wry]

Einfach hört sich gut an :)
Würd mir deinen Code gerne angucken

Edit:
naja, vielleicht weiß ja ein andere bescheid :redface:

[Trap]

Ich würde es als 2 mal 1d interpolation nacheinander implementieren. Zumindest um schnell eine richtige Version zu implementieren.

Zuerst Schnittpunkt px der Graden p1-p2 und p3-p suchen. Dann auf p1-p2 nach px interpolieren. Dann auf p3-px bis p.

[huha]

...was nichts anderes ist, als ein 2dimensionaler Verlauf. Der bringt aber relativ blöde Resultate, irgendwie.
Zweimal eindimensional, was senkrecht aufeinandersitzt, geht also schonmal nicht.

-huha

[Trap]

Der Winkel zwischen p1-p2 und px-p muss nicht 90 Grad sein. Kann auch fast 0 Grad sein. Meine Lösung berücksichtigt das, deine auch?

[Silpion]

Edit: Ich seh gerade, dass du das Dreieck in den R³ eingebettet hast. Sofern du das Dreieck nicht auf eine Ebene projizierst, wirst du Probleme bekommen, Punkte aus dem Dreieck anzugeben.

Grundsätzlich ist das natürlich alles mit recht wenig Aufwand machbar, wenn man sich ein bischen damit auskennt. Welche Berechnungsmöglichkeiten hast du denn schon implementiert? Kannst du mit Matrizen rechnen? Wie sieht es mit der Lösung von linearen Gleichungssystemen aus?

[wry]

@Silpion
:confused:

Gibts da auch eine einfache Lösung für den Mann von der Straße?
Eine die ich auch händisch ausführen kann, speziell für mein obiges Dreieck?

Worte wie "Konvexkombination" deprimieren mich :(

[Silpion]

Hab nochmal oben editiert.

Ich kann dir gerne ein Beispiel vorrechnen, per Hand ist es nicht allzuschwer. Gib mir einfach drei Punkte mit Farben und den Zielpunkt, von dem du die Farbe willst.

[huha]

Mich würde es im Übrigen auch interessieren :)


-huha

[wry]

@Silpion
zum Beispiel:
Gegeben ist ein Dreieck mit den Punkten:
p1=(0,0,0), p2=(1,0,0), p3=(0,1,0)

und den jeweiligen Ecken-Farben:
c1=(0.3,0.1,07), c2(0.5,0.8,0.4), c3(0.2,0.1,0.9)

Welche Farbe ergiebt sich am Punkt
p=(0.2,0.3,0)

[huha]

Dann geb' ich auch mal ein Beispiel, bei mir geht's ja nur um's Zweidimensionale:

P1(1|1|255|0|0)
P2(10|10|0|255|0)
P3(5|3|0|255|0)

die ersten beiden Koordinaten sind X und Y, die letzten drei die Farbanteile. Wäre nett, wenn du mir erklären könntest, wie man das macht, ich bin mir nicht sicher, ob ich mit Matritzen und Vektoren rumrechnen kann, somit wäre Integer- oder Floating-Point-Mathematik *SEHR* hilfreich.

-huha

[Silpion]

Okay, ich gehe hier von ein paar Vereinfachung aus:
- Die Punkte haben nur zwei Koordinaten und p liegt auf der Fläche des Dreiecks (d.h. im ersten Beispiel lasse ich die dritte Koordinate weg, da sie überall 0 ist).
- Ihr könnt mit Matrizen rechnen und lineare Gleichungssysteme lösen.
- Ich Unterscheide nicht großartig zwischen Vektoren und Matrizen. Vektoren sind für mich Matrizen mit nur einer Spalte (oder Zeile).
- Das Allerwichtigste: Die Erklärungen sind erstmal sehr knapp. Ich habe voraussichtlich Freitag und Sonntag abends mehr Zeit, da kann ich ausführlicher erklären.

Die Punkte und Farben seien als Spaltenvektoren gegeben. Setze
A = [p1,p2,p3] und C = [c1,c2,c3].

A (2x3 Matrix) hat jetzt folgende Gestalt:
[0 1 0]
[0 0 1]
C (3x3 Matrix) hat jetzt folgende Gestalt:
[.3 .5 .2]
[.1 .8 .1]
[.7 .4 .9]
p (2x1 Matrix) hat folgende Gestalt:
[.2]
[.3]

Füge nun die Bedingung hinzu, dass alle Koordinaten aufaddiert 1 ergeben (hier als unterste Zeile):
A hat jetzt folgende Gestalt:
[0 1 0]
[0 0 1]
[1 1 1]
p hat jetzt folgende Gestalt:
[.2]
[.3]
[1]

Damit haben wir nun das Gleichungssystem A*a = p (wobei a eine 3x1 Matrix ist, die später die Lösung enthält).
Löse mittels Gaussalgorithmus oder ähnlichem.
Setze nun c = C*a. In c ist nun die Farbe von p enthalten, in diesem Beispiel kommt c = (.31, .24, .7) heraus.

Wie gesagt, die Erklärungen sind knapp, ich kann Freitag und ab Sonntag ausführlicher werden.

@huha:
Du hast den Punkt vergessen, von dem du die Farbe möchtest. ;)
Versuch mal das obige Beispiel mit deinen Punkten nachzuvollziehen.

[pancho]

ich hab zwar keinen plan, wie "man" sowas macht, mich würde aber mal interessieren, wie meine idee ausschaut:

farbe= (1/enfernung von A * farbe A + 1/e B * f B + 1/e C * f C) * evtl irgendeinen faktor oder normalisieren oder so.

falls also jemand lust hat, das mal zu implementieren und nen screenie zu machen...

[Frank]

Baryzentrische Koordinaten für eine Ebene einführen und das Problem ist gegessen. Oder hab ich etwas in der Aufgabenstellung noch überlesen?

[muhkuh_rs]

Hi,

hab folgendes theoretisches Problem (zu Computergrafik):

Gegeben ist ein Dreieck mit den Punkten:
p1=(0,0,0), p2=(1,0,0), p3=(0,1,0)

und den jeweiligen Ecken-Farben:
c1=(0.5,0.6,07), c2(..), c3(..)

Welche Farbe ergiebt sich am Punkt
p=(...)
durch lineare Interpolation?


Bei der Computergrafik will man ja meistens wissen, welche Farbe der Pixel auf dem Screen hat. Dazu werden die drei Vertices zunächst in den clip space transformiert. Der einfachste Fall ist die Parallelprojektion. Dann erhält man je drei Koordinaten (x,y,z) von denen x,y Koordinaten in der Screenebene sind.

Jetzt wird IIRC zeilenweise vorgegangen. Für jede Zeile in die das Dreieck fällt, ergeben sich zwei Schnittpunkte mit zwei Seiten des Dreiecks. Die Farben der Schnittpunkte werden zwischen den betreffenden Eckpunkten linear anhand des y-Abstandes zu beiden interpoliert. Für jeden Pixel zwischen den beiden Schnittpunkten wird dann anhand des x-Abstandes zu diesen interpoliert.

Bei perspektivischer Projektion erhält man nach der Transformation mit der Projektionsmatrix Koordinaten der Form (x,y,z,w) mit w!=1. Die Koordinaten der Vertices auf der Screenebene ergeben sich durch (x/w, y/w, z/w). Man interpoliert jetzt nicht die Farben direkt sondern color/w und 1/w. Pro gerendertem Pixel wird dann das interpolierte color/w durch das interpolierte 1/w geteilt, wordurch sich die Farbe ergibt.

Ich hoffe das ist was Du meintest.

[wry]

@Silpion
Das werd ich mir jetzt mal genauer angucken müssen.
Ein großes Dankeschön schon mal an dich :)

Danke auch an die anderen

[Baalzamon]

Baryzentrische Koordinaten für eine Ebene einführen und das Problem ist gegessen. Oder hab ich etwas in der Aufgabenstellung noch überlesen?

Hätte ich jetzt auch gesagt. das klingt doch nach _dem_ Anwendungsfall dafür. Oder bin ich auch zu blind da noch ein anderes Problem drin zu sehen?

[wry]

Habs jetzt auch mal mit den baryzentrischen Koordinaten berechnet und komme auf das selbe Ergebnis wie Silpion.

Danke Leute!!

[huha]

Kann mir mal jemand erklären, was baryzentrische Koordinaten sind und wie ich von karthesischen in baryzentrische Koordinaten umrechne?

Danke!

-huha

[Neomi]

Kann mir mal jemand erklären, was baryzentrische Koordinaten sind und wie ich von karthesischen in baryzentrische Koordinaten umrechne?

Am besten durch ein Beispiel...

P = a*A + b*B + c*C

ABC ist ein Dreieck, P ist ein Punkt der in der Ebene des Dreiecks liegt. Die Werte a, b und c sind die baryzentrischen Koordinaten, die sich leicht berechnen lassen. Dabei gilt...

1. a + b + c = 1

2. Ist a, b oder c negativ, liegt P außerhalb des Dreiecks.

3. Ist a = 1, dann ist P = A, gleiches gilt für b und c.

Daraus lassen sich auch noch andere Sachen ableiten. Jedenfalls kann man mit diesen Koordinaten auch noch andere Sachen als die Position interpolieren, z.B. Texturkoordinaten und Farben.

a = |PBC| / |ABC|
b = |PCA| / |BCA|
c = |PAB| / |CAB|

|ABC| steht dabei für die Fläche des Dreiecks aus den Punkten A, B und C, wobei natürlich |ABC|, |BCA| und |CAB| identisch sind. Am leichtesten ist es, wenn man die Flächen in Form der Kreuzprodukte (Länge des Vektors = 2 * Fläche) verrechnet, immerhin können auch negative Werte rauskommen.

N = CrossProd (B - A, C - A); // gerichtete Fläche von ABC
N = N / DotProd (N, N); // Reziprok der Länge

a = DotProd (CrossProd (B - P, C - P), N);
b = DotProd (CrossProd (C - P, A - P), N);
c = DotProd (CrossProd (A - P, B - P), N);

Edit: ich hab das mal so angepaßt, daß alle kleinen Buchstaben Skalaren entsprechen, alle großen Buchstaben stehen für Vektoren. Das Kreuzprodukt liefert wie immer einen Vektor, das Skalarprodukt einen Skalar. Entsprechende Typen, Operatoren und Funktionen müssen natürlich definiert sein, aber das sollte für keinen Programmierer ein Problem darstellen.

[huha]

Geht das auch irgendwie ohne Matrix- und Vektormathematik respektive entsprechende Befehle?

-huha

[wry]

@huha

http://www.inf.tu-dresden.de/ST2/cg/pdf_daten/Informatik/HS/cg3/rendering_script.pdf

Wie man das genau berechnet steht unter baryzentrische Interpolation.

Brauchst eigentlich nur die Flächenformel fürs Dreieck (c*h)/2 damit du die Flächen der kleinen(Au,Av,Aw) und des großen Dreiecks(=A) berechnen kannst.

[Silpion]

@ Frank & Baalzamon:
Wenn es sich um Berechnungen am PC handelt, findet man spätestens bei der Anwendung immer Probleme. ;)
Spontan fällt mir z.B. Folgendes ein:
Sobald man zum drei oder höherdimensionalen übergeht, kann durch die Rechenungenauigkeit kann nicht garantiert werden kann, dass der Punkt wirklich auf der Ebene des Dreiecks liegt. Es wäre auch unnötig aufwändig die Koeffizienten der kompletten Affinkombination auszurechnen. Spätestens hier würde ich ein wenig lineare Optimierung einfließen lassen, damit die Berechnung noch numerisch optimal und effizient verläuft.

@ Neomi:
Es ergibt sich ein Problem, wenn man die Berechnung sehr häufig benötigt: Das Vektorprodukt basiert auf Determinantenberechnung und bringt damit einen hohen Aufwand mit sich.

@ huha:
Lineare Algebra passt hier wie die Faust auf's Auge. Alles Nötige zum Rechnen mit Matrizen ist Stoff des ersten Semesters. Vielleicht kannst du dir ja einfach mal anschauen, wie man Matrizen multipliziert und wie man lineare Gleichungssysteme damit darstellt. Das Gauß-System zum Lösen von LGS macht man teilweise schon in der Schule, es fehlt nur noch die kürzere Notation in Matrizenschreibweise. Verstehen wirst du beim einfachen Reinschauen nicht viel, aber vielleicht reicht es, um damit zu rechnen.

[Frank]

@ Frank & Baalzamon:
Wenn es sich um Berechnungen am PC handelt, findet man spätestens bei der Anwendung immer Probleme. ;)
Ist meistens so - aber man braucht die baryzentrischen Koordianten ja zb. schon zwingend bei Bézierdreiecken. Und die gibts ja nun recht häufig in der Computerwelt. Numerische Probleme sehe ich da auch keine großen - da gibts ganz andere heikle Sachen.