Schnittpunkt einer gerade mit einem durch eine funktion transformierten Objekt berechnen?



  • Also, ich möchte gerne eine Gerade mit einem Objekt schneiden, dass auf irgendeine Weise durch eine Funktion f transformiert ist.

    bei einem normalen Objekt ist das ja einfach(bei der Kugel zb):
    g: \stackrel{\rightarrow}{x}= p+s \cdot \stackrel{\rightarrow}{u}
    K: \left(\stackrel{\rightarrow}{x}-\stackrel{\rightarrow}{m}\right)^2=r^2
    dann g in K einsetzen und nach s auflösen.

    wenn ich jetzt aber die Kugel mit einer Funktion f transformieren(also zb verdrehen oder strecken...) will, müsste das ganze meines wissens nach am Ende so aussehen:

    K\_f: \left[\stackrel{\\_}{f}\left(\stackrel{\rightarrow}{x}\right)-\stackrel{\rightarrow}{m}\right]^2=r^2
    Die Punkte werden also alle mit der Umkehrfunktion transformiert. Die Frage ist nun, wie ich das ganze wieder nach s auflösen kann,nachdem ich g eingesetzt hab. f ist wirklich variabel.

    oder gibt es vielleicht einen anderen Weg, Objekte mit einem variablen f zu transformieren? Es ist am Ende nur wichtig, dass ich einen richtigen Schnittpunkt rauskrieg, und dass ich nicht Bruteforcemäßig jeden Punkt nacheinander einsetzen muss 😃

    //edit wie kann man eigentlich hier in latex zeilenumbrüche machen?



  • die Kugel mit einer Funktion f transformieren

    Die Punkte werden also alle mit der Umkehrfunktion transformiert

    wiederspricht sich das nicht?...
    kann im moment nicht so wirklich nachvollziehen, was du erreichen willst. Wäre evtl. möglich einen konkreten beispiel anzugeben?



  • Andrey schrieb:

    die Kugel mit einer Funktion f transformieren

    Die Punkte werden also alle mit der Umkehrfunktion transformiert

    wiederspricht sich das nicht?...
    kann im moment nicht so wirklich nachvollziehen, was du erreichen willst. Wäre evtl. möglich einen konkreten beispiel anzugeben?

    wenn man ein Objekt mit einer funktion f transformiert, muss man beim kollisionstest erst wieder zurücktransformieren, damit der transformierte Punkt wieder teil der Gleichung ist, die das Objekt beschreibt.

    kleines beispiel: du hast eine Ebene.

    seitenansicht:
    
    ________________________________________
    

    nun wird eine "Wellenfunktion" draufgepackt, sodass nun längs der x-achse eine schöne sinuswelle entsteht.

    seitenansicht:
         _.--._       _.--._
     _.-'      '-._.-'      '-._  (sinuswelle)
    

    Nehmen wir mal einen beliebigen punkt von einem Wellenmaximum. Dieser liegt logischerweise nicht mehr auf der Ebene. Deshalb muss der Punkt zuerst wieder durch die umkehrfunktion gejagd werden, damit er wieder zu der Ebenengleichung gehört.

    seitenansicht:
    
          Der Punkt        Zum Vergleich die ebenenfunktion       
           |                Der rücktransformierte Punkt   
           v                      |  
         _.--._                   v     
     _.-'      '-._        __________________
    

    Diese transformation hat natürlich auch konsequenzen beim hittest:

    ->=gerade
     untransformiert                              transformiert
    (trifft das Objekt nicht)                (trifft das Objekt)
    
    ------>                           ------------->_.--._ ----->                       
    __________________                          _.-'      '-._
    

    Was ich damit erreichen will:

    ich arbeite an einem raytracer, und bin es leid, mir ständig neue objekte basteln zu müssen, nur weil eine kleinigkeit anders ist. Wenn ich eine Ebene transformieren will, rechne ich derzeit per hand immer die neue kollisionsgleichung aus(absolut ätzend), und kopier das dann in den sourcecode.

    Was ich erreichen will ist, dass ich mir meine Objekte "zusammenbauen" kann.
    also sowas in der art: Objekt=drehung(sinuswelle(transformationFoo(Ebene)));
    und dafür muss ich einen weg finden, die jeweiligen gleichungen unabhängig von der transformation nach s umzuformen.



  • respekt, schöne zeichnungen 👍 mal sehen ob ich es auch so schön hinkriege... 🤡

    also. nur dass ich das richtig verstehe: du transformierst dein objekt mit f(), dann transformierst es zurück mit ~f() [umkehrfunktion] hinundher, und weisst nicht, wie du jetzt die gleichung von dem unverformten objekt und die kollisionserkennung unter einen hut kriegst?

    mein vorschlag: dein objekt transformierst du gar nicht. du nimmst einfach die umkehrfunktion, und transformiert mit der die gerade. Dann kriegst du irgendeine gekrümmte kurve im 3D raum:

    deine methode:
    
    -----------------------------------------------------------------> ray
    
             ___                   ___                   ___
        _.--'   '--._         _.--'   '--._         _.--'   '--._
    _.-'             '-.___.-'             '-.___.-'             '-.__ f(surface)
    
    mein vorschlag:
    
             ___                   ___                   ___
        _.--'   '--._         _.--'   '--._         _.--'   '--._
    _.-'             '-.___.-'             '-.___.-'             '-> ~f(ray)
    
    ----------------------------------------------------------------- surface
    

    dann hast du zwar immer noch keine simple formel, die du auf papier herleiten kannst, wie für gerade und kugel (die kannst du imho auch nicht kriegen, das was du da tust ist keine primitive lineare abbildung)
    dafür musst du aber nicht alle punkte des großen soliden objektes transformieren, sondern nur "stichprobenartig" in regelmäsigen abständen einige punkte auf deinem strahl.

    \ps: wenn die idee vollkommenere quatsch ist, bitte ich um entschuldigung 😃

    frage: wozu brauchst du denn sowas konkret beim raytracer? simulierst du da wasser und ähnliches?



  • dafür musst du aber nicht alle punkte des großen soliden objektes transformieren, sondern nur "stichprobenartig" in regelmäsigen abständen einige punkte auf deinem strahl.

    Ja, aber das wär dann nicht nur sehr langsam, sondern auch ungenau. Dann würde ich ja automatisch bei Kantigen oberflächen landen. Und bei dem Lichtsystem das ich verwende, würde das wohl sehr schnell raus kommen(denn das verzeiht Kanten und normalenverschiebungen überhaupt nicht. sieht sofort falsch aus).

    frage: wozu brauchst du denn sowas konkret beim raytracer? simulierst du da wasser und ähnliches?

    damit kann man recht viel machen.

    Ich zeig dir mal ein paar beispielbilder, die ich dabei im Hinterkopf hatte:
    Non-Cubic Space Division
    Man könnte so ein bild erzeugen, indem man ein normales Gitter als Objekt nimmt, und dann mit einer entsprechenden funktion transformiert.

    Techno Garb
    ähnliche regelmäßige muster wie die auf dem metall könnte man auch so erzeugen.

    Lonely Sphere
    ist fast genau wie das Ebenenbeispiel das ich genannt hab.



  • Ja, aber das wär dann nicht nur sehr langsam

    ja, schneller wirst du das auch nicht hinkriegen, wenn du wirklich irgendwelche hardcore berechnungen mit verzerrten oberflächen zur laufzeit vornehmen willst. Wäre das nicht einfacher, dein verzerrtes objekt komplett im voraus als durch polygone angenähertes modell zu erstellen? weil... naja, mit mathematisch perfekten kugeln klappt es noch ganz gut während der laufzeit, aber mit mathematisch exakt beschriebenen objekten, die du da eben gezeigt hast?? ist das nicht ein wenig zu viel des guten?

    ungenau. Dann würde ich ja automatisch bei Kantigen oberflächen landen. Und bei dem Lichtsystem das ich verwende, würde das wohl sehr schnell raus kommen(denn das verzeiht Kanten und normalenverschiebungen überhaupt nicht. sieht sofort falsch aus).

    warum denn plötzlich ungenau? solange du irgendein dünnes objekt nicht komplett überspringst, kriegst du doch immer irgendeinen ungefähren schnittpunkt. den kannst du danach immer genauer iterativ berechnen, zB mitm newton-verfahren (intervall einfach immer wieder halbieren) da steigt die genauigkeit exponentiell, nach 10 iterationen hast du also schon die 1024-fache deiner ursprünglichen genauigkeit erreicht. Das sollte doch reichen. Und dann kannst du dir auch die sortierung der schnittpunkte mit mehreren objekten ersparen. Wird zwar trotzdem um einiges langsamer als sonst, aber wenn du meinst, dass es sich für solch komplizierte objekte lohnt... 👍

    und wen du da auch noch ein verzerrtes octree reinhaust, könnte das schon richtig schnell werden 😃 (kP, hab nicht mal theoretisch ahnung, wie sowas gehen soll, und ob es überhaupt möglich ist)



  • Andrey schrieb:

    Ja, aber das wär dann nicht nur sehr langsam

    ja, schneller wirst du das auch nicht hinkriegen, wenn du wirklich irgendwelche hardcore berechnungen mit verzerrten oberflächen zur laufzeit vornehmen willst.

    schon. ich müsste nur von hand die gleichung aufstellen und auflösen, dann wär ich deutlich schneller. immerhin müsste ich bei jeder iteration in diesem fall mindestens einmal sin und eine wurzel aufrufen, und das wär mal der ziemliche hammer. mal davon ab geht es auch nicht um laufzeit. Echtzeit raytracing kriegt man wohl mit heutigen mitteln und reiner CPU power nicht hin. no chance.
    Hier gehts nur um einzelne Bilder, aber es ist ein unterschied, ob man minuten, oder stunden wartet für ein qualitativ hochwertiges Bild.

    Wäre das nicht einfacher, dein verzerrtes objekt komplett im voraus als durch polygone angenähertes modell zu erstellen?

    nein, denn das ist ja gerade der reiz des raytracings, dass man mathematisch korrekte, runde Oberflächen erzeugen kann.

    @topic hmm, da bis auf die iteration keine andere Lösung vorgeschlagen wurde, stehen die chancen wohl schlecht, dass sowas geht, oder? Wie machen das denn dann die großen Raytracer wie PovRay? muss man diese Objekte dort auch von "Hand" erstellen, also mit der kompletten schnittpunkt berechnung?



  • nene, von "echtzeit" hab ich auch nie was gesagt 😉
    ich habe damit eigentlich genau das gemeint, dass es wohl schöner wäre, wenn du etwas weniger als drei wochen für ein bildchen brauchen würdest^^ 😃

    @topic hmm, da bis auf die iteration keine andere Lösung vorgeschlagen wurde, stehen die chancen wohl schlecht, dass sowas geht, oder?

    na! immer langsam 😉 verzweifeln kannst du auch später!
    erstens: ich bin bisher der einzige, der diese frage hier zufällig gesehen hat
    zweitens: ich bin in sachen raytracing ein unerfahrener volltrottel, wenn mir nicht gleich eine lösung einfällt, heißt es noch nicht, dass es keine gibt :p

    also... wenn ich hier schon mit der theorie nicht weiterkomme, dann versuch ichs mal mit irgendeinem konkreten beispiel, vielleicht fällt mir doch noch was ein... 🤡



  • ich glaub ich habs!
    du musst dein modell immer noch im voraus berechnen, aber statt es mit dreiecken anzunähern, kannst du genau das gleiche mit Spline- oder Bezier-flächen machen. Dadurch kannst du eine mathematisch exakte fläche sehr gut annähern, und hast dabei immer noch nur eine einzige allgemeingültige methode zur berechnung des schnittpunktes.
    Das wär doch mal was? 😉 ich glaube alle anderen raytracer, die du erwähnt hast, machen es auch irgendwie so..



  • ich hab nun eine Lösung gefunden:

    man kann die Gleichungen etwas umschreiben:

    aus der Geradengleichung wird:

    x = px+s * ux
    y = py+s * uy
    z = pz+s * uz
    

    und aus der kreisgleichung wird:

    x = sin(u) * sin(v)
    y = cos(u) * sin(v)
    z = cos(v)
    

    (in den grenzen 0<=u,v<=2∏)

    die 3 gleichungen gleichsetzen, nach u,v,s auflösen und dann mit s den punkt berechnen.

    nun kann man jede dieser teilgleichungen modifizieren, wie man lustig ist

    //edit latex will net, deshalb normal darstellung



  • hm... und? jetzt hast du irgendeine spezialrechnung für eine kugel, und was willst du machen, wenn du irgendwann mal lust hast, statt kugeln verdrehte spiralförmige ringe zu rendern? 😕


Anmelden zum Antworten