Schnitt: Gerade/Rechteck

[Medium]

Zitat von Nikolas:

Warum willst du denn keine Bibliothek einsetzen? Räder neu zu erfinden ist nicht immer notwendig.

Das Einweben einer externen Lib wäre bei mir recht rechenintensiv, da diese Prüfungen sehr eng in einem Kontext passieren. Im schlimmsten Fall müsste ich etliche Zeilen bestehendes Programm auf die Lib anpassen. Zudem geht's um meine Bachelorarbeit, wo ich schon ganz gerne den Großteil selbst in der Hand haben mag

Zitat:

Kleiner Vorschlag:

Bresenham hatte ich auch schon als Alternative im Kopf, aber zunächst zugunsten anderer Ansätze hinten angestellt. Die Variante mit der Form y=mx+c hat leider zwei gravierende Nachteile: Ich müsste jeden Strahl erst von Vektorform in diese Form überführen, und der "Spezial"-Fall flacher Geraden käme recht oft vor.

Zitat:

Du willst aber nicht die Gerade und eine Parabel über Pixelvergleiche schneiden, oder?

Neee! Ich will Vektoren um Pixel drehen, und diese mit Catmull-Rom-Splines schneiden (wirklich)


Ich hab bei meiner Suche 2 Ansätze gefunden die ganz nett sind jetzt:

1) Schnitt des Vektors mit den 4 Kanten des Rechtecks (bzw. mit den 4 Geraden die längs durch diese Kanten verlaufen). Da von diesen immer eine Koordinate 0 ist, reduziert sich das auf 4 Mal einen Term der Form "(a1-a0) / b". Daraus bekomme ich letztlich 4 Skalare für den Richtungsvektor meines Strahls, welche gestaffelt die Reihenfolge ergeben in der der Strahl diese 4 Geraden schneidet. Je nach dem wie diese Reihenfolge aussieht, kann ich aussagen ob ein Schnitt passiert oder nicht.

2) Der ist schon was heftiger, und basiert auf dem Separating-Axis-Theorem. Dafür werden Strahl und Rechteck auf die Senkrechte zum Strahl projeziert, und wenn diese sich nicht überlappen habe ich auch keinen Schnitt. Das klingt im Anstaz sehr aufwendig, ist in Code gegossen (dank Achsenparallelität der Rechtecke) lediglich das hier:

Code:

private static bool RayIntersectsRect(float posX, float posY, float dirX, float dirY, Rect rect)
{
   float rayProj = (posX*dirY - posY*dirX);
   float radProj = Math.Abs(dirY*rect.extX) + Math.Abs(dirX*rect.extY);
   float centProj = rect.centerX*dirY - rect.centerY*dirX;
   
   float min = centProj-radProj;
   float max = centProj+radProj;
   
   return !((rayProj < min) || (rayProj > max));
}

Wobei posX/posY der Ursprung des Strahls ist, dirX/dirY die normalisierte Richtung (ich hab sie von vorn herein eh schon normalisiert vorliegen), Rect.centerX/Y ist die Mitte eines Rechtecks, und Rect.extX/Y ist die halbe Kantenlänge in X bzw. Y.


Allein schon die Tatsache dass bei (2) keine Divisionen vorkommen macht es merkbar schneller als (1), was ich vom "Klang" her erstmal für schneller gehalten hätte. Das scheint wohl auch Stand der Theorie in 3D zu sein, weswegen ich erstmal nicht davon ausgehe dass das noch flotter gehen wird. Man darf nur nicht erwähnen, dass ich für diese 6 Zeilen jetzt 2 Tage getüftelt und nen Forum befragt hab .

Heissen Dank an euch, denn auch wenn die letztliche Lösung nicht mehr SO viel mit den Vorschlägen zu tun hat, bin ich so doch erst in die richtige Such-Richtung geraten!