ahja das hab ich soweit verstanden, nur wie bastel ich ein LGS aus dieser Matrix da raus?


EDIT:
Also ich glaub ich hab das soweit hinbekommen. Ich setze einfach fuer i einen Wert ein zb 1 und bekomme dann heraus, dass fuer
B0 kein Wert
B1 = x2-x0
B2 = x2-x1
gilt.

Aus diesen B-Werten errechne ich dann die zugehörigen A-, C- und D-Werte und kann meine Gleichung aufstellen, um letzten Endes Y zu errechnen. Damit haette ich praktisch die Zeileninterpolation.

Aber wie verbinde ich das nun auch noch mit der Spalteninterpolation?

Die Matrix ist bereits ein LGS. Wenn du in den Artikel zum Gauß-Jordan-Verfahren schaust, ist dort ein Beispiel zu finden.
Nur in diesem Fall ist es halt nicht a, b, c, ... sondern b0, b1, b2, ...;
die rechte Spalte, also die jeweilige Lösung des LGS errechnet sich als die rechte Seite der Gleichung (VI). Das geht, denn di kennst du, denn Si(xi) = yi, also di = yi, weil alle anderen Koeffizienten 0 werden.

Edit: Die einzelnen is sind die notwendigen Gleichungen für die ite Spline, du berechnest also die b-Koeffizienten für alle Splines im Voraus.
Wenn du aus [4,4] zB. [32,4] interpoliert hast, also jeweils eine Zeile, hast du ja 4 mal 32 interpolierte Zeilen. Jetzt wendest du die Interpolation statt auf 4 Zeilenwerte [i,0], [i,1],... [i,3] auf 4 Spaltenwerte an [0,i], [1,i], ... [31,i] und kannst daraus dann [32,32] berechnen.

MfG

Eine wesentliche einfachere Möglichkeit um Splines zu erzeugen, sind Unterteilungsalgorithmen. Man benötigt nur zwei Funktionen: Verdoppeln der Punkte(1), und Mittelwerte bilden(2).

x[] = Punkte
x'[] =neue Punkte

Verdopplungsoperator:
x'[2*i] = x[i]
x'[2*i+1] = x[i]

Mittelpunktoperator
x'[i] = x[i]*0.5 + x[i+1]*0.5

Eine Iteration besteht jetzt darin, die Punkte zuerst zu verdoppelt und danach n Mal den Mittelpunktoperator anzuwenden.
Der aus mehrfacher Anwendung entstehende Polygonzug konvergiert dann gegen einen B-Spline vom Grad n.

@ Lars: Also ich weiss nich genau, ob ich deine Lösung richtig verstanden hab.

Ich versteh zb nicht, warum du hier:
x'[2*i] = x[i]
x'[2*i+1] = x[i]

Deinen Neuen Feld X' etwas zuweist und es hier:
x'[i] = x[i]*0.5 + x[i+1]*0.5

wieder überschreibst?

Ungeachtet dieser Tatsache errechnet sich aus dieser Formel ja lediglich der Durchschnitt zweier benachbarter Punkte. Auf einer Gerade wird in der Mitte also ein weiterer Punkt eingefügt. Das bringt mir zwar mehr Vertices für meine Berge, aber rund wirds deswegen noch nicht.

Wenn man nach dem Verdoppeln nur einmal mittelt, bleibt es eckig. Das wäre dann ein Spline vom Grad 1. Daher muss man den Mittelungsoperator öfter anwenden.

also z.B. bei kubischen Splines für jede Iteration:

Verdoppeln
Mitteln
Mitteln
Mitteln

Verdoppeln und Mitteln waren im voherigen Beitrag als eigene Funktion gedacht. Daher wird nichts überschrieben.

http://www.mpi-inf.mpg.de/~shin/Java_Ap ... Curve.html

Ah ok das macht sinn. in der demo werden aber bei jedem apply die punkte mehr.
Heisst das die führen immer
Verdopplung und Mitteln aus? Also würde meins, wenn ich nur am anfang verdoppel und dann mehrfach mittel genauso aussehen, nur mit weniger punkten?
Ich frage, weil bei drei mal Mitteln da eine enorme Zahl punkte herauskommt und ich um die Performance bange ^^

ansonsten ist diese technik wirklich gut und leicht verstaendlich

Das wichtigste ist bei mir jetzt aber erstmal, dass ich meine bisher noch auf Quadstrips ausgelegten Felder in Trianglestrips bzw -fans umbau, sodass mir diese ganzen funktionen ueberhaupt was bringen, denn ich kann mir kaum vorstellen, dass ich hier mit quads viel erreichen kann

Ja man muss diese Folge von Verdopplen mit anschließendem mehrfachen Mitteln so oft anwenden bis man die gewünschte Genauigkeit erreicht hat. Das Apply macht in dem Applet jedesmal eine Iteration.

So könnte die komplette Berechnung in Pascal aussehen:



Mehrfaches Mitteln (und auch verdoppeln) kann zusammengefasst werden:

Anstelle das man zuerst bei a die Mittelpunkte berechnet und dann bei b nochmal, kann man das auch direkt einsetzen:

b[i] = a[i]*0.5 + a[i+1]+0.5
c[i] = b[i]*0.5 + b[i+1]+0.5

c[i] = a[i]*0.25+a[i+1]*0.25 + a[i+1]+0.25 + a[i+2]*0.25
c[i] = a[i]*0.25+a[i+1]+0.5 + a[i+2]*0.25

Man erhält eine Reihe von Filtern:

Grad 1: [0.5,0.5]
Grad 2: [0.25,0.5,0.25]
Grad 3: [0.125,0.375,0.375,0.125]

also ich hab das, bevor ich mich in die ebene stuerze, erstmal versucht in der geraden nachzubaun und es sieht bei mir irgendwie noch zackiger aus als vorher^^


Der aufruf:


TStrip ist ein Array of TGLVector3f

Naja sieht halt irgendwie sehr viel zackiger aus als vorher^^

So ich hab noch etwas umhergebastelt und mal folgende Funktion erstellt:


Wenn cih die jetzt mehrfach ausführe, wird meine Ebene immer glatter, ohne dass dabei neue Punkte erstellt werden. Eigentlich liegt in der Erstellung neuer Punkte kein Problem ausser, dass dadurch direkt doppelt soviele neue Triangles gezeichnet werden müssen, was die Performance evlt erheblich beeinträchtigt.

Bei dieser Rechnung jetzt gefällt mir im Grunde nur der Punkt nicht, dass alles sehr schnell sehr flach wird, wodurch sich zwar Wiesen zb sehr nett nachbauen lassen, Gebirge hingegen, die rasant abfallen, überhaupt nicht. Zumindest geht diese Funktion jetzt, aber vllt hat ja noch wer den "Stein der Weisen"

also so ganz funkt das noch nicht, wie ich das moechte. wahrscheinlich muss ich doch bsplines nutzen.
ich versteh aber immernoch nicht wie.

Meine darstellung wuerde in etwa so aussehen:


Ich habe also ein X*Y Raster mit allen Höhen und moechte daraus das "rundere" raster machen. Ich denke, die Felderanzahl verdoppeln, ist schonmal der erste Schritt, damit ich das ganze Runder gestalten kann. nun muessen nur die Punkte noch ausgerechnet werden. EBen ueber diese Bezierfunktion, aber wie gesagt, ich schnall nicht ganz, wie

Vllt kann das ja jemand mal kurz erklaeren, wär sehr nett

Ich versuch mal, meinen Vorschlag nochmals zu erläutern:

Schreib dir zunächst eine Funktion, die ein 1dimensionales Array mit einem bestimmten Wert vervielfacht (also für ein 4 Werte großes Array und Vervielfachung = 4 zB. 4*4 = 32). Wenn du nun deine Funktion erstellst, haben die Punkte die X-Werte 0, 1, 2 etc. wenn du jetzt in Schritten von 1/Vervielfachungsfaktor einen neuen Punkt erstellst, erzeugst du das gewünschte größere Array. Im Beispiel oben: Jedes 1/4 von 0 bis 8 ist ein neuer Punkt, der Y-Wert wird durch die jeweils gültige Spline bestimmt; dadurch entstehen dann 32 neue Werte.

Dann: Mach es erst zeilen-, dann spaltenweise.

Hast du zB. eine 4x4 Matrix (Zeilen x Spalten), führst du das Verfahren erstmal auf jede Zeile aus, sodass du für Vervielfachung=4 eine 4x16 Matrix erhälst. Wenn man sich das bildlich vorstellt oder aufzeichnet, kann man die Matrix so hindrehen/hindenken, dass jede Spalte jetzt 4 Zeilenwerte enthält. Wendest du jetzt auf jede Spalte mit den 4 Werten das Verfahren an, erhält jede Spalte 16 Zeilenwerte. Das bedeutet, du hast eine 16x16 Matrix.

Für eine 2x2 Matrix mit Vervielfachung sähe das dann quasi so aus:


Selbstverständlich musst du die Fkt. nicht unbedingt erst auf Zeilen und dann auf Spalten anwenden, umgekehrt - also erst auf Spalten, dann auf Zeilen - würde es natürlich auch funktionieren.

MfG

Okay das hab ich jetz so in etwa verstanden, ich nehm also mein Array mit x Punkten und vervielfache es zuerst zeilen- dann spaltenweise um den Faktor t. Und danach errechne ich die neuen Punkte, indem ich zwischen allen x Punkten nochmal im Abstand von 1/t einen neuen Punkt errechne.

Beispiel: 4 Punkte. Verfielfachung 10 (Verfielfachung gaebe ja dann praktisch die Genauigkeit der Funktion an)
Dann wäre mein neues Array 40*40 und der Abstand zwischen den Punkten wäre 0.1

Okay soweit hab ich das verstanden.

Nun aber der Knackpunkt:



Diese Berechnung ist es ja, die ich nicht verstehe. Nehmen wir also an, ich habe aus meinem Array[0..3] of TGLVector3f; ein Array[0..39,0..39] of TGLVector3f; gemacht. Wie genau errechne ich denn nun die Werte? Meine vier Punkte aus dem ersten Array müssten im zweiten Array ja jetzt bei [9,9],[19,19],[29,29] und [39,39] liegen und wären damit diese Stützpunkte, von denen in dem Beispiel die Rede ist. Aber wie bekomm ich nun all die anderen Punkte heraus, das ist es ja, was ich nicht verstanden hab. Wie sieht da die Rechnung aus?


Ahja und noch eine kurze Frage zu Nachtrag: Muss ich unbedingt ein Eindimensionales Array haben? Also muss ich ein Array[0..3] haben, ginge nicht stattdessen auch direkt ein Array[0..3,0..3] woraus ich dann mein Array[0..39,0..39] mach?

Danke schonmal fuer deine Geduld

Du hast mich nicht richtig verstanden. Du hast eine Heightmap quasi als [Zeilen,Spalten] array of Single zB. Dabei haben alle Punkte in der Heightmap den gleichen Abstand. Wenn du nun Zeilen oder Spalten betrachtest, erhälst du deine Stützpunkte.

Konkreter: In deinem Beispiel nimmst du zeilenweise immer ein eindimensionales Array der 4 Spalten zu jeder Zeile und erzeugst aus diesen 4 Punkten dann die Splines. Dann hast du eine Funktion (oder auch nur Anweisung), welche je nach X-Wert die richtige Spline für das Intervall auswählt und dort an diesem X-Wert den neuen Y-Wert zurückgibt.
Dein neues Array erhält dann die neuen Y-Werte, indem die Durchlaufvariable (i in: "for i := 0 to 39 do") mit (4-1)/(40-1) multipliziert* wird, also die Punkte im Abstand 3/39 = 0.0769... erzeugt und in die oben genannte Funktion eingesetzt werden. Dadurch machst du aus einem [0..3]er Array ein [0..39]er Array.

Dann hast du ein [0..3, 0..39]er Array. Jetzt betrachtest du einfach jede der 40 neuen Spalten. Jede Spalte enthält 4 Zeilenwerte. Hier wendest du das oben erwähnte einfach wieder an und hast wieder aus einem [0..3]er Array ein [0..39]er Array gemacht.

Abschließend hast du ein [0..39, 0..39] Array - wie gewünscht.

Das sollte auch die Sache mit dem eindimensionalen Array erklären.

* Mir fiel eben auf, dass es ja nur so geht... die Formel ist also (Length(AltesArray)-1)/(Length(NeuesArray)-1) = High(AltesArray)/High(NeuesArray)


Kein Problem, ich helfe gerne und bei nicht simplen Themen lernt man selbst auch fast immer was dazu.

MfG

Okay das ist soweit klar. ich versuche grad nach besten bemuehungen diese Formeln herzubasteln und bin zur Zeit so weit:



r ist die Rechte Seite, der Gleichung, mit der b errechnet wird (hoffe ich hab das richtig umgesetzt).
Nur weiss ich gar nicht, wie ich r jetzt in die berechnung von b eingliedere.

Wenn ich das erstmal hab, muss ich ja mit b1, b2 und b3 nur noch a und c ausrechnen und ich hab alles.