Files |  Tutorials |  Articles |  Links |  Home |  Team |  Forum |  Wiki |  Impressum

Aktuelle Zeit: Fr Jul 11, 2025 09:02

Foren-Übersicht » Programmierung » Allgemein
Unbeantwortete Themen | Aktive Themen



Ein neues Thema erstellen Auf das Thema antworten  [ 29 Beiträge ]  Gehe zu Seite Vorherige  1, 2
Autor Nachricht
 Betreff des Beitrags:
BeitragVerfasst: Fr Sep 21, 2007 19:28 
Offline
DGL Member

Registriert: So Aug 20, 2006 23:19
Beiträge: 564
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?


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags:
BeitragVerfasst: Fr Sep 21, 2007 19:46 
Offline
DGL Member
Benutzeravatar

Registriert: Mo Sep 02, 2002 15:41
Beiträge: 867
Wohnort: nahe Stuttgart
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


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags:
BeitragVerfasst: Fr Sep 21, 2007 21:16 
Offline
DGL Member
Benutzeravatar

Registriert: Sa Dez 28, 2002 11:13
Beiträge: 2244
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.


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags:
BeitragVerfasst: Sa Sep 22, 2007 00:10 
Offline
DGL Member

Registriert: So Aug 20, 2006 23:19
Beiträge: 564
@ 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.


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags:
BeitragVerfasst: Sa Sep 22, 2007 00:28 
Offline
DGL Member
Benutzeravatar

Registriert: Sa Dez 28, 2002 11:13
Beiträge: 2244
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


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags:
BeitragVerfasst: Sa Sep 22, 2007 09:32 
Offline
DGL Member

Registriert: So Aug 20, 2006 23:19
Beiträge: 564
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


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags:
BeitragVerfasst: Sa Sep 22, 2007 10:00 
Offline
DGL Member
Benutzeravatar

Registriert: Sa Dez 28, 2002 11:13
Beiträge: 2244
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:

Code:
  1. for i:=1 to Genauigkeit do
  2. begin
  3.  Verdopplen;
  4.  for j:=1 to Grad do
  5.    Mitteln;
  6. end;


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]


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags:
BeitragVerfasst: Sa Sep 22, 2007 12:57 
Offline
DGL Member

Registriert: So Aug 20, 2006 23:19
Beiträge: 564
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^^
Code:
  1. function TMap.DoubleStrip(Strip: TStrip): TStrip;
  2. var i: Integer;
  3. begin
  4.   SetLength(Result, Length(Strip)*2);
  5.  
  6.   for i := 0 to High(strip) do
  7.   begin
  8.     Result[2*i] := strip[i];
  9.     Result[2*i+1] := strip[i];
  10.   end;
  11. end;
  12.  
  13. function TMap.MiddleStrip(Strip, Strip2: TStrip): TStrip;
  14. var i: Integer;
  15. begin
  16.   Result := Strip2;
  17.   for i := 0 to High(Strip) do
  18.     Result[i][1] := Strip[i][1]*0.5 + Strip[i+1][1]*0.5;
  19. end;


Der aufruf:
Code:
  1.       test2 := fmap.DoubleStrip(test);
  2.       test2 := fmap.MiddleStrip(test,test2);  end;


TStrip ist ein Array of TGLVector3f

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


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags:
BeitragVerfasst: So Sep 23, 2007 00:34 
Offline
DGL Member

Registriert: So Aug 20, 2006 23:19
Beiträge: 564
So ich hab noch etwas umhergebastelt und mal folgende Funktion erstellt:
Code:
  1. procedure TMap.Middle;
  2. var i,j:Integer;
  3.     tmp: Single;
  4. begin
  5.   for i := 1 to High(Ground)-1 do
  6.     for j := 1 to High(Ground)-1 do
  7.     begin
  8.       tmp := Ground[i,j-1].Heights + Ground[i,j].Heights +Ground[i,j+1].Heights + Ground[i-1,j].Heights + Ground[i+1,j].Heights ;
  9.       Ground[i,j].Heights := tmp/5;
  10.     end;
  11. end;


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"


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags:
BeitragVerfasst: Mo Sep 24, 2007 19:03 
Offline
DGL Member

Registriert: So Aug 20, 2006 23:19
Beiträge: 564
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:
Code:
  1.  
  2. for i:=0 to High(Ground) do
  3.   for j:=0 to High(Ground[i]) do
  4.   begin
  5.     Ground[i,j].Height := ....;
  6.   end;


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


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags:
BeitragVerfasst: Mo Sep 24, 2007 20:37 
Offline
DGL Member
Benutzeravatar

Registriert: Mo Sep 02, 2002 15:41
Beiträge: 867
Wohnort: nahe Stuttgart
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:
Code:
  1. Neue Spalten generieren, dh. Vervielfachungsfunktion auf Zeile anwenden:
  2. (a b)      (a m b n)
  3. (c d)  --> (c o d p)
  4.  
  5. Anschließend neue Zeilen generieren, dh. Vervielfachungsfunktion auf Spalte anwenden:
  6. (a b c d)       (a b c d)
  7. (e f g h)  ---> (m n o p)
  8.                 (e f g h)
  9.                 (q r s t)
  10.  


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


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags:
BeitragVerfasst: Di Sep 25, 2007 08:28 
Offline
DGL Member

Registriert: So Aug 20, 2006 23:19
Beiträge: 564
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:

WhiteHunter hat geschrieben:
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.


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 :oops:


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags:
BeitragVerfasst: Di Sep 25, 2007 15:49 
Offline
DGL Member
Benutzeravatar

Registriert: Mo Sep 02, 2002 15:41
Beiträge: 867
Wohnort: nahe Stuttgart
Shaddow hat geschrieben:
WhiteHunter hat geschrieben:
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.


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?

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)

Zitat:
Danke schonmal fuer deine Geduld :oops:

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

MfG


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags:
BeitragVerfasst: Di Sep 25, 2007 17:12 
Offline
DGL Member

Registriert: So Aug 20, 2006 23:19
Beiträge: 564
Okay das ist soweit klar. ich versuche grad nach besten bemuehungen diese Formeln herzubasteln und bin zur Zeit so weit:

Code:
  1.  
  2.     for j := x1 to x2 do
  3.     begin
  4.       // (xi-xi-1)bi-1 + 2(xi+1-xi-1)bi + (xi+1-xi)bi+1 = 3((di+1-di)/(xi+1-xi) - (di-di-1)/(xi-xi-1))
  5.  
  6.       // r = 3((d[i+1]-d[i])/(x[i+1]-x[i]) - (d[i]-d[i-1])/(x[i]-x[i-1]))
  7.       r  := 3*((Ground[1,j+1].Position[1]-Ground[1,j].Position[1])/
  8.                Ground[1,j+1].Position[0]-Ground[1,j].Position[0] -
  9.               (Ground[1,j].Position[1]-Ground[1,j-1].Position[1])/
  10.                Ground[1,j].Position[0]-Ground[1,j-1].Position[0]);
  11.  
  12.       b1 :=    Ground[1,j].Position[0]   - Ground[1,j-1].Position[0];
  13.       b2 := 2*(Ground[1,j+1].Position[0] - Ground[1,j-1].Position[0]);
  14.       b3 :=    Ground[1,j+1].Position[0] - Ground[1,j].Position[0];
  15.  
  16.  
  17.     end;
  18.  


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.


Nach oben
 Profil  
Mit Zitat antworten  
Beiträge der letzten Zeit anzeigen:  Sortiere nach  
Ein neues Thema erstellen Auf das Thema antworten  [ 29 Beiträge ]  Gehe zu Seite Vorherige  1, 2
Foren-Übersicht » Programmierung » Allgemein


Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 7 Gäste


Du darfst keine neuen Themen in diesem Forum erstellen.
Du darfst keine Antworten zu Themen in diesem Forum erstellen.
Du darfst deine Beiträge in diesem Forum nicht ändern.
Du darfst deine Beiträge in diesem Forum nicht löschen.
Du darfst keine Dateianhänge in diesem Forum erstellen.

Suche nach:
Gehe zu:  
  Powered by phpBB® Forum Software © phpBB Group
Deutsche Übersetzung durch phpBB.de
[ Time : 0.009s | 14 Queries | GZIP : On ]