Frage

Ich möchte den Schnittpunkt zwischen einem Strahl und einem Quader bestimmen.Der Quader wird durch seine minimale 3D-Koordinate und seine maximale 3D-Koordinate definiert und der Strahl wird durch seinen Ursprung und die Richtung, in die er zeigt, definiert.

Derzeit bilde ich eine Ebene für jede Seite des Kastens und schneide den Strahl mit der Ebene.Wenn der Strahl die Ebene schneidet, überprüfe ich, ob der Schnittpunkt tatsächlich auf der Oberfläche des Kastens liegt.Wenn ja, überprüfe ich, ob es der nächstgelegene Schnittpunkt für diesen Strahl ist, und gebe den nächstgelegenen Schnittpunkt zurück.

Die Art und Weise, wie ich überprüfe, ob der Ebenenschnittpunkt auf der Boxoberfläche selbst liegt, erfolgt über eine Funktion 

bool PointOnBoxFace(R3Point point, R3Point corner1, R3Point corner2)
{
  double min_x = min(corner1.X(), corner2.X());
  double max_x = max(corner1.X(), corner2.X());
  double min_y = min(corner1.Y(), corner2.Y());
  double max_y = max(corner1.Y(), corner2.Y());
  double min_z = min(corner1.Z(), corner2.Z());
  double max_z = max(corner1.Z(), corner2.Z());
  if(point.X() >= min_x && point.X() <= max_x && 
     point.Y() >= min_y && point.Y() <= max_y &&
     point.Z() >= min_z && point.Z() <= max_z)
     return true;

  return false;
}

Wo corner1 ist eine Ecke des Rechtecks ​​für diese Boxfläche und corner2 ist die gegenüberliegende Ecke.Meine Implementierung funktioniert die meiste Zeit, aber manchmal erhalte ich den falschen Schnittpunkt.Bitte siehe Bild:

alt text

Das Bild zeigt Strahlen, die vom Kameraauge ausgehen und auf die Kastenoberfläche treffen.Die anderen Strahlen sind die Normalen zur Kastenoberfläche.Es ist zu erkennen, dass insbesondere der eine Strahl (eigentlich ist es das Normale, das man sieht) von der „Rückseite“ der Box ausgeht, während die Normale von der Oberseite der Box nach oben kommen sollte.Dies scheint seltsam zu sein, da es mehrere andere Strahlen gibt, die die Oberseite der Box korrekt treffen.

Ich habe mich gefragt, ob die Art und Weise, wie ich überprüfe, ob der Schnittpunkt auf dem Feld liegt, korrekt ist oder ob ich einen anderen Algorithmus verwenden sollte.

Danke.

War es hilfreich?

Lösung

Das Vergrößern von Dingen um Epsilon ist eigentlich keine gute Möglichkeit, dies zu tun, da Sie jetzt am Rand Ihrer Box einen Rand der Größe Epsilon haben, durch den Strahlen hindurchtreten können.Sie werden also diese (relativ häufige) seltsame Reihe seltsamer Fehler los und haben am Ende eine weitere (seltenere) Reihe seltsamer Fehler.

Ich gehe davon aus, dass Sie sich bereits vorstellen, dass sich Ihr Strahl mit einer bestimmten Geschwindigkeit entlang seines Vektors bewegt, und den Zeitpunkt des Schnittpunkts mit jeder Ebene ermitteln.Also zum Beispiel, wenn Sie das Flugzeug schneiden x=x0, und dein Strahl geht in die richtige Richtung (rx,ry,rz) aus (0,0,0), dann ist die Schnittzeit t = x0/rx.Wenn t negativ ist, ignorieren Sie es – Sie gehen in die andere Richtung.Wenn t Null ist, müssen Sie entscheiden, wie Sie mit diesem Sonderfall umgehen – wenn Sie sich bereits in einem Flugzeug befinden, prallen Sie davon ab oder fliegen Sie hindurch?Möglicherweise möchten Sie auch damit umgehen rx==0 als Sonderfall (damit man den Rand der Box treffen kann).

Wie auch immer, jetzt haben Sie genau die Koordinaten, an denen Sie das Flugzeug getroffen haben:sie sind (t*rx , t*ry , t*rz).Jetzt können Sie einfach ablesen, ob t*ry Und t*rz sich innerhalb des Rechtecks ​​befinden, in dem sie sein müssen (d. h.zwischen dem Minimum und Maximum für den Würfel entlang dieser Achsen). Sie testen die x-Koordinate nicht, weil Sie bereits wissen, dass Sie sie getroffen haben Auch hier müssen Sie entscheiden, ob/wie Sie das Einschlagen von Ecken als Sonderfall behandeln.Darüber hinaus können Sie jetzt Ihre Kollisionen mit den verschiedenen Oberflächen nach Zeit ordnen und die erste als Kollisionspunkt auswählen.

Dies ermöglicht Ihnen, ohne auf willkürliche Epsilon-Faktoren zurückzugreifen, zu berechnen, ob und wo Ihr Strahl Ihren Würfel schneidet, und zwar mit der Genauigkeit, die mit Gleitkomma-Arithmetik möglich ist.

Sie benötigen also nur drei Funktionen, wie Sie sie bereits haben:eine, um zu testen, ob Sie nach innen treffen yz Vorausgesetzt, du hast getroffen x, und die entsprechenden für xz Und xy Vorausgesetzt, du hast getroffen y Und z jeweils.

Bearbeiten:Code hinzugefügt, um (ausführlich) zu zeigen, wie die Tests für jede Achse unterschiedlich durchgeführt werden:

#define X_FACE 0
#define Y_FACE 1
#define Z_FACE 2
#define MAX_FACE 4

// true if we hit a box face, false otherwise
bool hit_face(double uhit,double vhit,
                 double umin,double umax,double vmin,double vmax)
{
  return (umin <= uhit && uhit <= umax && vmin <= vhit && vhit <= vmax);
}

// 0.0 if we missed, the time of impact otherwise
double hit_box(double rx,double ry, double rz,
                double min_x,double min_y,double min_z,
                double max_x,double max_y,double max_z)
{
  double times[6];
  bool hits[6];
  int faces[6];
  double t;
  if (rx==0) { times[0] = times[1] = 0.0; }
  else {
    t = min_x/rx;
    times[0] = t; faces[0] = X_FACE; 
    hits[0] = hit_box(t*ry , t*rz , min_y , max_y , min_z , max_z);
    t = max_x/rx;
    times[1] = t; faces[1] = X_FACE + MAX_FACE;
    hits[1] = hit_box(t*ry , t*rz , min_y , max_y , min_z , max_z);
  }
  if (ry==0) { times[2] = times[3] = 0.0; }
  else {
    t = min_y/ry;
    times[2] = t; faces[2] = Y_FACE;
    hits[2] = hit_box(t*rx , t*rz , min_x , max_x , min_z , max_z);
    t = max_y/ry;
    times[3] = t; faces[3] = Y_FACE + MAX_FACE;
    hits[3] = hit_box(t*rx , t*rz , min_x , max_x , min_z , max_z);
  }
  if (rz==0) { times[4] = times[5] = 0.0; }
  else {
    t = min_z/rz;
    times[4] = t; faces[4] = Z_FACE;
    hits[4] = hit_box(t*rx , t*ry , min_x , max_x , min_y , max_y);
    t = max_z/rz;
    times[5] = t; faces[5] = Z_FACE + MAX_FACE;
    hits[5] = hit_box(t*rx , t*ry , min_x , max_x , min_y , max_y);
  }
  int first = 6;
  t = 0.0;
  for (int i=0 ; i<6 ; i++) {
    if (times[i] > 0.0 && (times[i]<t || t==0.0)) {
      first = i;
      t = times[i];
    }
  }
  if (first>5) return 0.0;  // Found nothing
  else return times[first];  // Probably want hits[first] and faces[first] also....
}

(Ich habe das gerade eingegeben, es nicht kompiliert, also hüte ich vor Fehler.) (Bearbeiten:habe gerade eine korrigiert i -> first.)

Wie auch immer, der Punkt ist, dass Sie die drei Richtungen getrennt behandeln und testen, ob der Aufprall innerhalb des rechten Felds in (u,v)-Koordinaten stattgefunden hat, wobei (u,v) entweder (x,y), (x) sind ,z) oder (y,z), je nachdem, welches Flugzeug Sie treffen.

Andere Tipps

PointOnBoxFace Es sollte eine zweidimensionale statt einer dreidimensionalen Prüfung erfolgen.Wenn Sie beispielsweise gegen das testen z = z_min Flugzeug, dann müssten Sie nur vergleichen x Und y an ihre jeweiligen Grenzen.Das hast du schon herausgefunden z Koordinate stimmt.Die Gleitkomma-Präzision wird Sie wahrscheinlich zum Stolpern bringen, wenn Sie die dritte Koordinate „erneut überprüfen“.

Zum Beispiel, wenn z_min 1,0 ist, testen Sie zuerst gegen dieses Flugzeug.Sie finden einen Schnittpunkt von (x, y, 0,999999999).Jetzt allerdings x Und y liegen im Rahmen, die z ist nicht ganz richtig.

Code sieht gut aus.Versuchen Sie, diesen bestimmten Strahl zu finden und ihn zu debuggen.

Könnte es sein, dass dieser Strahl am Ende genau durch den Rand der Box geht?Fehler bei der Gleitkomma-Rundung können dazu führen, dass sie sowohl auf der rechten als auch auf der Rückseite übersehen wird.

BEARBEITEN:Ignorieren Sie diese Antwort (siehe Kommentare unten, wo mir der Fehler meiner Vorgehensweise ziemlich überzeugend gezeigt wird).

Sie testen, ob sich der Punkt innerhalb des Volumens befindet, aber der Punkt liegt an der Peripherie dieses Volumens, sodass Sie möglicherweise feststellen, dass es sich um einen „unendlichen“ Abstand außerhalb des Volumens handelt.Versuchen Sie, die Box um ein kleines Epsilon zu vergrößern, z. B.:

double epsilon = 1e-10; // Depends the scale of things in your code.
double min_x = min(corner1.X(), corner2.X()) - epsilon;
double max_x = max(corner1.X(), corner2.X()) + epsilon;
double min_y = min(corner1.Y(), corner2.Y()) - epsilon;
...

Technisch gesehen besteht der korrekte Weg, nahezu gleiche Zahlen zu vergleichen, darin, ihre Bitdarstellungen in Ganzzahlen umzuwandeln und die Ganzzahlen um einen kleinen Versatz zu vergleichen, z. B. in C:

#define EPSILON 10 /* some small int; tune to suit */
int almostequal(double a, double b) {
    return llabs(*(long long*)&a - *(long long*)&b) < EPSILON;
}

Natürlich ist das in C# nicht so einfach, aber vielleicht kann eine unsichere Semantik den gleichen Effekt erzielen.(Danke an @Novox für seine Kommentare, die mich zu einem netten Ergebnis geführt haben Seite diese Technik im Detail erklären.)

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top