Intersektion von Gerade und Wellen



  • Hallo zusammen
    Ich muss irgendwie herausfinden, an welchen Koordinaten (x,y,z) eine Gerade (Vektor3) ein Wellenmeer schneidet. Die Position der Wellen wird mit einer komplexen, nicht linearen Funktion berechnet. Hat jemand eine Idee, wie ich sowas performant implementieren kann. Ich denke an ein nummerisches Lösungsverfahren à la Newton. Gibt es möglicherweise noch andere Möglichkeiten?

    Ach ja, da habe ich gleich noch eine Frage: Die Position der Vertices wird auf der Grafikkarte mit Hilfe eines Vertexshaders berechnet. Die Position der Schiffe hängt aber natürlich ebenfalls von den aktuellen Positionen der Wellen ab. Nun ist meine Frage, ob die Wellen nochmals auf der CPU berechnen muss, oder ob es eine Möglichkeit gibt, die Berechnungen der GPU wieder in den Arbeitsspeicher zu schreiben?

    Mfg Samuel



  • Falls du die Schnittstellen auf ein bestimmtes Interval einschränken kannst und du garantieren kannst, dass die Richtungsableitung der Funktion in Richtung der Gerade entlang dieses Intervalls einen bestimmten Wert nicht überschreitet, gibt es da ein Verfahren, das ich kenne. Schau dir einfach mal den Quellcode von POV-Ray für isosurfaces an. Ist im Grunde eine Art Bisektion. Schnell ist das nicht. Es gibt auch einen langsamen Algorithmus namens Sphere Tracing oder so ähnlich. Problem mit Newton wäre wahrscheinlich, dass man nie weiß, wann man alle Schnittpunkte gefunden hat. Ohne bestimmte Informationen über die Funktion steht man aber immer auf verlorenem Posten.
    Wenn man mehr über diese Funktion wüsste könnte man vielleicht ein weniger allgemeines Verfahren einsetzen. Vielleicht wäre es auch sinnvoller, erst ein Mesh aus der Welle zu erzeugen und dieses dann mit der Gerade zu schneiden.
    geloescht



  • Nun ja, die Funktion, welche ich verwende, lautet folgendermassen:
    P(x,z,t) = (x,Sum(A_i*sin(dot(x,z)*f_i-t*v_i)),z)
    P'(x,z,t) = (x,Sum(A_i*f_i*cos(dot(x,z)*f_i-t*v_i)),z)

    Also so wie ich das sehe, habe ich 3 Gleichungen sowie 3 Unbekannte. Sollte eigentlich mit einem 3dimensionalen Newton Approximationsverfahren lösbar sein oder täusche ich mich da?

    Bsp:
    (1,2,3)-d*(2,3,4) = (x,y,sum(A_i*sin(dot(x,y)*f_i-t*vi)))
    wobei d,x und y die Unbekannten sind. Natürlich wird es abhängig vom Einfallswinkel bis zu unendlich viele Lösungen geben. Ich habe mir da überlegt, dass ich mit Hilfe des Kreuzproduktes der partiellen Ableitungen den Normalenvektor eines bestimmen Lösungspunktes ermitteln und somit festellen kann, ob der Punkt zu mir oder von mir wegschaut. Somit filtere ich all jene raus, welche von mir weg schauen. Von den übriggebliebenen nehme ich denjenigen, der meinem Kamera Eye Vektor am nächsten ist...

    Ich muss leider zugeben, dass ich nicht gerade ein Mathegenie bin, habe ich vielleicht etwas übersehen, oder wäre dies ein möglicher Lösungsansatz?


  • Mod

    einfach x und z vom schiff eintragen und die position auslesen, wozu brauchst du das ganze komplexe zeug?



  • @rapso
    Hehe, naja diese Berechnungen benötige ich nicht für die Bestimmung der Postionen der Schiffe, welche auf dem Wasser schwimmen sondern für für die Auswahl von Spielfelder mit der Maus 😉



  • Das Problem ist identisch mit der Suche des Oberflaechenschnittpunktes bei Parallax-Mapping.
    Aus der maximalen Wellenamplitude sollte sich ein verhaeltnismaessig kleiner Bereich ergeben, in dem Dein Strahl ueberhaupt die Oberflaeche treffen kann.


  • Mod

    dafuer reicht normalerweise die durchschnittshoeche des wassers, ehrlich, so genau wie du das machen willst ist es nicht noetig und es kann sogar irritierend sein wenn man bei jedem klick ein anderes feld bekommen wuerde wegen den wellen (wenn auch technisch sicherlich cool, zweifelsfrei 😉 ).

    versuch es also erstmal mit ner simplen ray-plane intersection, oder habt ihr das schon und es reicht nicht aus? habt ihr vielleicht nen sehr schraegen winkel? (ich hab einfach mal iso ansicht angenommen 😉 )



  • Nun ja, ich rendere zuerst das Spielfeld in eine Textur und lege diese schlisslich auf das Wasser. Die Wellen können unter umständen relativ hoch sein (Sturm). Aus diesem Grund ist es wichtig, die Berechnung genau zu machen, weil es kann verheerend sein, auf das falsche Feld zu klicken. Es ist mir gelungen, das Problem soweit zu vereinfachen, dass ich ein simples 1 dimensionales Newtonverfahren anwenden kann. Nun bleibt nur noch die Frage nach den korrekten Startwerten...



  • Irgendwie kriege ich es nicht gebacken 😞 Folgendes habe ich bisher gemacht:

    Wave wa = this.arrWav[0];
    float   A = wa.Amplitude;
    Vector2 D = wa.Direction;
    float   V = wa.Velocity;
    float   F = MathHelper.TwoPi/wa.Length;
    float   T = this.cmpWtr.Time;
    
    Vector3 vp = this.srvCam.Position;
    
    // determine the current mouse - position and calculate the normalized device coordinates
    Vector2 crs = this.Cursor.Position;
    Vector2 ndc = new Vector2(-1.0f+2.0f*crs.X,1.0f-2.0f*crs.Y);
    
    // calculate a ray from the ndc
    Vector3 ve = this.srvCam.GetRayFromNDC(ndc)-vp;
    
    Vector2 vr;
    float x;
    
    /*
    if(ve.Y < 0.0f) {
     x = -vp.Y/ve.Y;
     vr = new Vector2(vp.X+x*ve.X,vp.Z+x*ve.Z);
    }
    else { vr = Vector2.Zero; x = 0.0f; }
    */
    
    if(ve.Y < 0.0f){
     x = -vp.Y/ve.Y;
    
     for(int i=0;i<100;++i){
      // pre - calculate as much as possible due to performance increase
      float tmp = Vector2.Dot(D,new Vector2(vp.X+x*ve.X,vp.Z+x*ve.Z))*F-T*V;
    
      // calculate the function - value and the derivation
      float fx = A*(float)Math.Sin(tmp)-vp.Y-x*ve.Y;
      float dx = A*F*(float)Math.Cos(tmp)-ve.Y;
      x -= fx/dx;
    
      if(Math.Abs(fx) <= 0.001f) break;
     }
    }
    else{vr = Vector2.Zero; x = 0.0f;}
    
    vr = new Vector2(vp.X+x*ve.X,vp.Z+x*ve.Z);
    

    Aber aus irgendeinem Grund funktioniert gar nichts. Wenn ich die Amplitude auf 0.0f setze, dann funktioniert alles einwandfrei. Mit der linearen Gleichung sowie mit Newton. Aber sobald ich die Amplitude auch nur geringfügig erhöhe, bspw. auf 1.0f, dann fangen die Probleme an 😞

    Sieht vielleich jemand den Fehler?

    Ich benutze vorerst nur eine einzige Welle, um die Situation möglichst simpel zu halten, solange noch Fehler darin auftauchen

    Hier ist noch die Funktion von der Camera

    // --------------------------------- method "GetRayFromNDC" ---------------------------------
      public Vector3 GetRayFromNDC(Vector2 NDC){
       // transform from normalized device coordinates into view coordinates and finally into
       // world coordinates by multiplying the view coordinates by the inverse view matrix
       Vector3 vecViw = new Vector3(NDC.X*this.aAsp,NDC.Y,-1.0f/(float)Math.Tan(this.aFov/2.0f));  
       return Vector3.Transform(vecViw,Matrix.Invert(this.mtxViw));
      }
      // ------------------------------------------------------------------------------------------
    


  • Ich habe das Problem nun völlig anders lösen können. Newton hat leider wegen diversten bekannten Problemen mit sinusähnlichen Funktionen nicht funktioniert...


Log in to reply