Effiziente Lidarsimulation



  • Hallo zusammen,

    ich habe einen oder mehrere Lidarsensoren deren Richtungen in die sie ihre Strahlen abfeuern kenne, und eine 3D-Umgebung bestehend aus Polygonen. Ich habe KEINE Punktwolken oder ähnliches.
    Jetzt möchte ich eine echtzeitfähige Visualisierung auf der GPU programmieren, die mir anzeigt wo meine Umgebung von den Lidarstrahlen getroffen wird. Also so wie hier in etwa (auf dem Bild sieht man einen extrem langsamen CPU raytracer).

    Meine Idee ist es, für jeden Sensor eine Shadowmap (Cubemap) zu rendern, dann die gesamte Szene rendern und im Fragmentshader für jeden Sensor checken: Kann das Pixel vom Sensor getroffen werden? Wenn ja, gibt es überhaupt einen Strahl in Richtung Pixel?
    Aktuell zerbreche ich mir den Kopf über den letzten Schritt. Wie mache ich diesen Check, ist das überhaupt so einfach möglich? Und wie realisiere ich zB. dass ein Strahl einen 3 Pixel statt einem 1 Pixel Punkt erzeugen soll?

    Bin ich mit der Idee auf dem Holzweg, oder hat jemand eine Idee, wie das funktionieren könnte?
    Einen Raytracer auf der GPU zu programmieren möchte ich eigentlich vermeiden, da dieser mit dynamischen Objekten wahrscheinlich nicht echtzeitfähig sein wird.



  • Das ganze ist ja nicht eindeutig, deswegen kannst du nur eine Hülle um den leeren Raum berechnen. Das einfachste ist diese dann zu visualisieren.



  • Verstehe ich dass richtig dass du im Prinzip mehrere Laser-Fächer auf deine Szene projizieren willst, und zwar so dass die Linien jeweils ca. 3 Pixel dick werden?



  • @TGGC sagte in Effiziente Lidarsimulation:

    Das ganze ist ja nicht eindeutig

    Was genau meinst du mit nicht eindeutig?

    @hustbaer sagte in Effiziente Lidarsimulation:

    Verstehe ich dass richtig dass du im Prinzip mehrere Laser-Fächer auf deine Szene projizieren willst, und zwar so dass die Linien jeweils ca. 3 Pixel dick werden?

    Jein. Es sollen keine Fächer/Linien, sondern Punkte gezeichnet werden. Bei nahen Objekten sind die Punkte dann natürlich so nahe beieinander, dass sie wie Linien aussehen. Bei fernen Objekten macht es aber schon einen Unterschied.



  • @Pikkolini
    also wenn du herausfinden willst, ob eine gerade durch einen punkt läuft, kannst du das tun, indem du d = | a x (rq - r1) | / |a| ausrechnest und das ergebnis auf 0 (plus/minus toleranz) prüfst, wobei r1 den ursprungsvektor (die quelle des lasers), a der richtungsvektor und rq den (möglichen) zielpunkt darstellen.



  • Den Winkel zwischen dem Strahl und dem Vektor von Sensor zu Pixel auszurechnen ist einfach. Aber wie groß darf dieser Winkel maximal sein, damit das Pixel als getroffen gilt? Klar, es gibt eine Beziehung zwischen maximalen Winkel und der Entfernung vom Pixel zum Sensor. Aber wie "groß" ist das Pixel? Das ist eine Information, die ich benötige. Gibt es eine Möglichkeit die Größe eines Pixels in Weltkoordinaten abzuschätzen?



  • warum willst du den winkel zwischen strahl und pixel haben? und warum willst du überhaupt pixel verwenden?

    wenn du bspw. eine senkrechte quadratische fläche von "1 * 1" hast und du überprüfen willst, ob der strahl irgendwo zwischen (0,0; 0,0), (0,1; 0,0), (0,0; 0,1) und (0,1; 0,1) bzw. dem quadrat oben links mit der seitenlänge von 0,1 auftrifft, dann ist das immer dann der fall, wenn der abstand von (0,0; 0,0) und (0,0; 0,1), also horizontal gesehen, kleiner oder gleich 0,1 ist und gleichzeitig der abstand von (0,1; 0,0) und (0,1; 0,1) kleiner oder gleich 0,1 ist.

    da rechnest du dann nicht mit pixeln, sondern mit koordinaten. ob du als längeneinheit km, m, eier, elefantenrüssel oder sonst was nimmst, ist dabei völlig egal.



  • @Wade1234 sagte in Effiziente Lidarsimulation:

    warum willst du den winkel zwischen strahl und pixel haben? und warum willst du überhaupt pixel verwenden?

    Weil ich mir keinen Raytracer basteln will, sondern möglichst effizient im fragment shader überprüfen will ob das zu rendernde Pixel von einem Strahl getroffen wird oder nicht. Und im fragment shader habe ich leider keine Informationen mehr zu welchem Polygon das Pixel gehört oder sonstiges, sondern (als relevante Information) nur dessen Position in Weltkoordinaten. Ich hab auch die Position meines Sensors in Weltkoordinaten, ich weiß in welche Richtung die Strahlen gehen, also muss ich nur herausfinden ob ein Strahl nah genug an der Position meines Pixel vorbeigeht, dass ich das Pixel als "getroffen" markieren kann. Da stellt sich mir jetzt die Frage, wie definiere ich sinnvoll "nah genug"?

    Das ist nur meine Idee das zu bewerkstelligen. Falls jemand bessere Ideen hat, wie man ohne ray tracing das Problem lösen kann, immer her damit 🙂



  • rq: position des pixels
    r1: position des sensors
    a: richtung des strahls
    sinnvolles d: 5% bzw. 0,05



  • Wenn das d konstant ist, werden Punkte weiter weg vom Sensor immer größer, da dann immer mehr Pixel die Bedingung erfüllen. Das kann man rausrechnen, da man die Entfernung Pixel zu Sensor kennt. Jetzt will ich aber auch sagen können, der Punkt soll genau 3 Pixel groß sein. Wie groß ist dann mein d? Da spielt dann rein, wie meine view und projection matrix gesetzt ist, etc.



  • nein das d entspricht im grunde dem radius eines kreises um die gerade herum.

    wenn d <= 0,05 ist, dann heißt das, dass sich der punkt, den du überprüft hast, innerhalb dieses kreises mit dem radius 0,05 befindet. versuch dir das wie eine dartscheibe vorzustellen, wobei der strahl eben immer dem bullseye entspricht. das maximale d musst du dann eben so bemessen, dass es deinen anforderungen entspricht.



  • Genau, der Kreis um die Gerade ist in Weltkoordinaten konstant. Wenn man das ganze nun projeziert wird der Kreis um die Gerade nach hinten hin immer kleiner. Ich habe mal versuch das in einem Bild deutlicher zu machen: https://i.imgur.com/Gr7LEzc.png
    Es schneiden also immer weniger Pixel diesen Kreis. Mein gerenderter Punkt wird immer kleiner. Das ganze kann ich lösen in dem ich das d abhängig von der Entfernung Fragment-Weltkoordinate zu Quelle mache. Jetzt möchte ich aber ganz explizit sagen der Kreis soll immer 3 Pixel schneiden. Und da hakt es bei mir gerade.



  • warum rechnest du nicht mit den weltkoordinaten? wenn es nur darum geht herauszufinden, ob der punkt mit einer gewissen toleranz getroffen wurde, wäre das doch das einfachste. projektion hat doch den zweck, ein zweidimensionales bild zu erzeugen, oder irre ich da?



  • also bezogen auf das bild, das du oben geposted hast: angenommen, die autos würden einen kasten darstellen, der 2 * 4 größeneinheiten bzw. m groß ist, dann hast du mit d = 0,05 doch eine super geile genauigkeit.



  • @Wade1234 sagte in Effiziente Lidarsimulation:

    warum rechnest du nicht mit den weltkoordinaten?

    Das tue ich doch.

    @Wade1234 sagte in Effiziente Lidarsimulation:

    wenn es nur darum geht herauszufinden, ob der punkt mit einer gewissen toleranz getroffen wurde

    Darum geht es immer noch nicht.



  • @Pikkolini sagte in Effiziente Lidarsimulation:

    Das tue ich doch.

    nein du rechnest mit pixeln, bzw. möchtest gerne mit pixeln rechnen.

    @Wade1234 sagte in Effiziente Lidarsimulation:
    Darum geht es immer noch nicht.

    ja gut dann geht es darum, ob ein pixel getroffen wurde bzw. die mitte von 3 pixeln.

    bist du dir sicher, dass das alles sinnvoll ist und du da nicht unnötigen rechenaufwand hast?



  • Verstehe nicht so ganz, warum man da was auf Pixelebene zu berechnen will. Der Sinn eines Lidar ist die freie Fläche um den Sensor zu erfassen. Diesen würde ich durch ein Dreiecksnetz erfassen. Bei mehreren Sensoren kann man dann die Dreiecksnetze kombinieren. Dabei kann man halt unter verschiedenen Annahmen (z.B. eine quaderförmige Kiste mit 4x2m ist ein Auto) versuchen ein genaueres Bild zu erzeugen, aber das ist eben je nach Anzahl und Lage der Sensoren nicht eindeutig. Dann wird z.b. eine Werbetafel zu einem Transporter, weil gerade kein Sensor hinter die Tafeln schauen kann um zu wissen das sie sehr schmal ist.

    Später kann man dann die Dreiecke projezieren und rasterizieren, aber das doch ein ganz anderes Problem.



  • Du kannst den gleichen Algorithmus wie beim Shadowmapping anwenden. D.h. für jeden Sensor hast du eine Shadow-Matrix, welche einen Punkt von Weltkoordinaten in die lokalen Koordinaten eines Sensors umrechnet. Im Fragmentshader nimmst du nun den Weltkoordinaten-Punkt und rechnest diesen mit jeder Shadowmatrix jeweils in die Koordinaten vom Sensor und vergleichst nun dort den so ermittelten lokalen Abstandswert mit den Wert aus der Deepmap. Wenn der Abstand des Fragment-Punktes zum Deepmap-Wert innerhalb eines festgelegten Schwelbereichs liegt, dann malt dein Fragmentshader eine Farbe. Du machst eine Oder-Verknüpfung zwischen den einzelnen Sensoren. Wenn einer von den Sensoren sagt: "Ja dieser Abstandswert passt mit den Fragment-Punkt überein" dann ist die Bedingung zum Pixel-Zeichnen erfüllt.

    @Edit: Mir ist gerade noch eingefallen, das man ja so nur eine einzelne Ebene aber kein komletten Raum abscannt. D.h. für ein einzelnen Pixel hat man ja nicht nur ein 3D-Punkt sondern ein Strahl. Tja in diesen Falle wäre das ja dann eher eine Abfrage zwischen ein Volumentrischen Strahl und einer 3D-Punktwolke. Du könntes dafür ein 3D-Grid nehmen. Du trägst von jeden Abstandssensor seine Abstandsabtast-3D-Punkte in diesen Grid ein. Und dann gehst du mit Raymarching entlang des Primärstrahls von der Kamera und fragst aus dem Grid die Punkte ab. Wäre dann also doch eher ein Raytracing-Algorithmus, den du aber trotzdem noch gut im Fragmentshader machen kannst.



  • @XMAMan Interessante Idee 🙂 Wie genau würdest du das Grid erstellen?
    Ich hatte dieses Wochenende noch eine ähnliche Idee:
    Angenommen, die vertikale/horizontale Winkelauflösung ist jeweils äquidistant. Dann kann ich zB für einen Sensor der vertikal 40° mit 1 Ray/° und horizontal 90° mir 10 Rays/° einen 900x40 Framebuffer erstellen, den Kameraursprung an die Sensorposition setzen, mein FOV auf 90°H/40°V setzen und dann von jedem Fragment die Weltkoordinaten in den Framebuffer schreiben. Aus dem Framebuffer kann ich dann eine Punktwolke machen und diese dann irgendwie rendern (octree, raymarching, mal schauen). Ist meine Annahme, dass das so funktionieren könnte richtig?


Log in to reply