Schnitt: Gerade/Rechteck

[Medium]

Aloah! Wieder mal eine Schnitt-Frage...

Ich hab eine beliebige Gerade (bzw. Strecke, ich kann beides liefern) und ein achsenparalleles Rechteck. Ich möchte nun wissen, ob meine Gerade/Strecke dieses Rechteck schneidet/passiert, ohne dafür aufwendige Operationen machen zu müssen. Trigonometrie und Steigungsbestimmung scheiden z.B. aus. Am Rande: Ich brauch den genauen Schnittpunkt nicht.

Ich hab irgendwo mal aufgeschnappt, dass das nur über Vergleich von min/max Koordinaten geht (ein paar Differenzbildungen wären sicher kein Beinbruch falls nötig), aber ich komme einfach nicht dahinter.
Was ich bereits erkannt habe ist, dass eine Gerade die nicht schneidet, erst die minX und maxX (bzw. minY und maxY) Koordinate des Rechteckes passiert, und danach erst die anderen beiden. Eine Gerade die schneidet, passiert erst eine X, dann eine Y, dann die andere X dann die andere Y Koordinate - also abwechselnd.
Im Falle einer Strecke (die ja Anfang und Ende hat) können Schnitte fehlen, so dass sie z.B. nur die min/max X oder Y durchstößt, und sonst nichts.

Ob das überhaupt eine brauchbare Erkenntnis ist weiss ich leider nicht :stupid:. Überlappung von 2 Rechtecken wäre einfach, da wüsste ich wie - aber bei der Geraden brauch ich mal nen Anstupser.

Danke schon Mal vorab, und nettes WE!

[Reinhard Kern]

Zitat:

Zitat von Medium

...Ich hab eine beliebige Gerade (bzw. Strecke, ich kann beides liefern) und ein achsenparalleles Rechteck. Ich möchte nun wissen, ob meine Gerade/Strecke dieses Rechteck schneidet/passiert, ohne dafür aufwendige Operationen machen zu müssen. ...

Was immer du für aufwendig hältst (ich wills garnicht wissen), ich würde es so angehen: für Xmin und Xmax des Rechtecks die Y-Koordinate der Geraden berechnen (Geradengleichung) und mit Ymin und Ymax des Rechtecks vergleichen (= 4 x SUB). Die Gerade schneidet das Rechteck dann nicht, wenn die Y-Werte des Rechtecks alle (echt) kleiner sind als der Y-Wert der Geraden an diesem X-Wert. dann läuft die Gerade oben vorbei. Oder sie sind alle grösser, dann läuft die Gerade unter dem Rechteck vorbei.

Ist alles aus dem Kopf und ohne Zeichnung, wenn ich mich vertan habe bitte Korrektur. Wenn nicht dürfte es nicht einfacher gehen.

Gruss Reinhard

[Medium]

Aufwendig ist alles was CPU-Zeit kostet. Ich muss das ein paar 100.000 Mal mit so 100 Rechtecken durchexerzieren, und will dafür nicht mehr als ein paar Sekunden, gerne weniger brauchen. Addieren, Subtrahieren und Vergleichen ist okay, Multiplizieren wohl auch, ab Dividieren werd ich schon hellhörig :)

Nach deinem Beitrag etwas Gesuche bin ich nun auf folgende Methode gestoßen:
Ausgangslage ist ein Strahl, gegeben durch A+t*B (A und B = 2D-Vektoren) und ein beliebiges achsenparalleles Rechteck. Jetzt berechne ich den Schnitt des Strahls mit den 4 "Strahlen" die die Rechteck-Kanten beschreiben, aber nur so weit bis ich die 4 t's hab, welche mir quasi sagen bei welcher Entfernung mein 1. Strahl diese Achsenparallelen schneidet. 2 davon für die X-Schnitte, 2 für die Y-Schnitte. Wenn jetzt einer oder beide von einem Paar zwischen den Werten des anderen Paares liegen, müsste ich schneiden.

Jetzt muss ich nur noch testen ob das performancemäßig meinen Anforderungen standhalten kann - und ob's überhaupt wirklich so geht :)

Danke dir schon mal! Und falls da noch möglicherweise schnellere Einfälle in manchen Köpfen schwirren: Ich bin da sehr offen für ;)

[Nikolas]

Ein sehr schneller Einfall: http://www.cgal.org/
Das ist eine freie Computer-Geometrie-Bibliothek, die unter anderem so etwas sehr gut abdeckt. Es werden ziemlich viele Beispiele mitgeliefert, also sollte es recht gut machbar sein.

CGAL::do_intersect (iso_rect!)

[Medium]

Eine externe Lib kommt leider überhaupt nicht in Frage :(

[alzaimar]

Wenn Du das umgebende (achsenparallele) Rechteck einer Stecke betrachtest, dann könnten Dir deine Erkenntnisse bezüglich der Erkennung der Überlappung von Rechtecken weiterhelfen. Eventuell gepaart mit einer Fallunterscheidung, denn das umschließende Rechteck (P1-P2-P3-P4) einer Geraden (P1-P3) überlappt ein anderes Rechteck am Punkt P2, aber damit schneidet die Gerade P1-P3 nicht notwendigerweise(!) das Rechteck. Hier müsstest Du also analytisch prüfen, sonst ist der Fall klar.

[Medium]

Genau den Ansatz hatte ich schon, allerdings ist das Verfahren viel zu grob. Es geht darum: Ich habe ein Bild in kleinere Bilder zerlegt. Dann nehm ich einen Punkt im Bild, und von diesem aus einen Vektor. Nun will ich eine Liste aller Rechtecke haben, die dieser daraus erzeugte Strah schneidet.
Ich kann nun aus dem Strahl durchaus eine Strecke machen in dem ich einfach den 2. Punkt so wähle dass er ausserhalb des Bildes liegt um den selben Effekt zu haben, jedoch führt das dazu, dass ich viel zu viele Rechtecke als Schnittkandidaten habe - im Worst-Case alle.

Das hier hängt mit meinem kürzlich hier erstellten Thema zusammen, wie man eine Gerade mit einer Fkt. 3. Grades schneidet, und das braucht eben so arg lange, dass ich diese Methode hier brauche um vorab sehr "billig" möglichst viel auszuschließen. Im Grunde macht man das bei fast allen 3D Anwendungen genau so, nur eben mit dem "View-Frustum" und einem Octree der Szene. Bei mir isses halt nur 2D, der Frustum ist eine Linie, und der Octree ist ein regelmäßiges Gitter von Rechtecken.

[Nikolas]

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

Kleiner Vorschlag:

Nimm deine Strecke als Geradengleichung und evaluiere sie an den waagrechten Kanten. Für Einheitskästchen also
y=mx+c ->
y = 1 => x=3.4, abgerundet bist du also im Kästchen (3,1)
y = 2 => x=4.9, -> (4,1)
y = 3 => x=6.4 -> (5,1),(6,1) <- kleiner Spezialfall für recht flache Geraden.

Damit solltest auf jeden Fall recht schnell sein, da du fuer jede Ebene nur eine Addition und ein Abrunden ausfuehren musst. (und dazu noch nie Abfrage bei sehr flachen geraden, wobei du schon durch m>0.5? entscheiden kannst, ob der Fall auftreten kann.

Alternativ koenntest du dir auch den Bresenham-Algorithmus anschauen, der wird eigentlich eingesetzt, um Geraden oder Kreise zu zeichnen und entscheidet, welche Pixel geschwärzt werden, was recht genau deine Frage beantworten koennte.

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

[Medium]

Zitat:

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 :stupid: (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 :mrgreen:.

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! :dp:

[Nikolas]

Die Darstellung der Geraden ist beliebig austauschbar :mrgreen:

Ich geh mal davon aus, dass dein Strahl im Kästchen mit Index (linke untere Ecke) s=(x,y) beginnt und Richtung d=(u,v) läuft, wobei d normalisiert ist. Deine Kästchen haben Länge (W,H). Mit L = H/v hast du den Vector d'=L*d, der von der der linken unteren ecke von (x,y) zu waagrechten mit y=x+W läuft.
Jetzt hast du die x-Werte x_i=x+i*u' (x*i*L*u) und kannst schauen, in welchem Kästchen das liegt.

Damit kommst du pro Ebene mit einer Addition (x_(i+1)=u'+x_i), einem Abrunden (und vielleicht noch der Abfrage wegen uebersprungener Kästchen hin.

Deine Ansätze nutzen überhaupt nicht aus, das die Rechtecke sehr nett angeordnet sind und du somit z.B. weisst, dass wenn deine Strecke durch (x,y) und (x+3,y) geht, wohl auch (x+1,y) geschnitten werden muss.


// Könntest du vielleicht dein Problem noch ein Mal erklären? Ich habe das Gefühl, dass es da vielleicht auch einen komplett anderen Ansatz für die Berechnung gibt, der noch mal schneller sein könnte.

[Medium]

Den Satz vorm Edit bin ich grad dabei kaputt zu machen, indem ich nicht mehr regelmäßig unterteile, sondern in einen Quadtree :mrgreen:

Was ich genau machen möchte ist folgendes:

Ich habe einen Satz Splines (so ca. 100-300 Stück, jeder so bestehend aus ~10 Segmenten im Schnitt). Diese Splines sind Kanten (eigentlich Kanten von Kanten...) eines Ausgangsbildes, beinhalten also auch Farbinformationen.
Aus diesen Splines will ich nun wieder ein Bitmap erzeugen, dass dem Original möglichst nahe kommt. In diesem Ansatz möchte ich also rund um jeden Pixel schauen, welches Spline ich von dort aus als erstes "sehe", und dessen Farbe an der Schnittstelle addiere ich im Verhältnis zur Entfernung auf meinen Pixel.

Zuvor habe ich das durch wiederholtes Anwenden einer modifizierten diskreten Wärmediffusionsfunktion in einem DirectX9 Pixelshader gemacht, wofür die Splines zunächst auf ein sonst leeres Bild gezeichnet wurden und dann schrittweise verbreitert und vermischt.

Als nächstes hab ich einen ähnlichen Ansatz wie jetzt, mit obigem vermischt. Ich zeichne also die Splines in mein Bitmap, und gehe dann von jedem Pixel aus in alle Richtungen Pixel für Pixel durch, bis ich auf eines treffe dass zu einem Spline gehört. Dann hab ich auch eine Farbe und eine Entfernung. Das hab ich ebenfalls in einem Shader gemacht.

Dann kam ich drauf, dass dieses pixelweise Voranschreiten ja eigentlich Käse ist, da man ja Schnitte mit Funktionen 3. Grades (was ein Spline-Segment letztlich ist) durchaus auch explizit berechnen kann, was irgendwie eleganter ist :). Und genau das tu ich grad, allerdings nicht in einem Shader, da ich bisher keine Lust hatte mir auszudenken wie ich meine Spline-Daten in Form einer Textur in diesen hineinfüttern will. Das wäre dann evtl. der nächste Schritt, wenn die CPU-Version so weit wie auch nur möglich optimiert ist.

Das ganze Projekt reift schon so ein paar Monate, also so ganz unversucht hab ich andere Ansätze nicht gelassen. Für geniale Einfälle bin ich aber immer mehr als offen!

[Nikolas]

Klingt nach einem spannenden Projekt. Ich hab gerade meinen Master an der ETH begonnen und spezialisiere mich im Bereich Robotik und Bildverarbeitung, wenn du nichts dagegen hast, würde ich mir die Arbeit gerne mal anschauen, mit splines habe ich noch nie gearbeitet, da kann ich sicher was lernen. (Gerne auch eine Vorab-Version)

[Medium]

Nikolas, du gewinnst jetzt erstmal einen Blumentopf :)

Ich hab nun eine Lösung die einfach nur abgeht wie Schmidt's Katze (und noch mehr), und sie basiert tatsächlich quasi auf Bresenham! Was mich an dem Algo anfangs immer ein wenig gestört hat ist, dass ich damit für jedes Pixel für jeden Winkel Divisionen (zumindest aber Int-Divs und Modulos) rein bekomme, zusätzlich zu einer Reihe von Fallunterscheidungen. Ein fittes Kerlchen auf GameDev hatte dann die Wahnsinnsidee (die im Nachhinein fast schon zu simpel ist):
Statt den DDA (das ist quasi die Oberklasse von Algos zu denen auch Bresenham gehört) immer und immer wieder neu zu berechnen, macht man dies nur ein einziges Mal für nur einen einzigen Block, und baut sich daraus eine Lookup-Table die die Block-Offsets zu jedem Startpixel im Block, zu jedem Winkel in einer Liste bereit hält - da ja diese schließlich für alle Blöcke identisch aussieht, abgesehen von der Länge. Die maximale Länge in Blocks ist dann einfach sqrt((bildbreite/blocksize)²+(bildhöhe/blocksize)²)*2 (mal zwei wegen 4er Nachbarschaft, d.h. ein diagonaler Sprung ist zwei gerade Sprünge), was dann die Obergrenze in der LUT ist die man je brauchen würde.

Praktisch hab ich nun also eine List<Point>[,,] in der ich einfach nachschauen kann wo ich für den aktuellen Pixel beim aktuellen Winkel den nächsten Block finde (wobei Point halt für X bzw. Y nur -1, 0 und 1 beinhaltet). Die LUT zu bauen dauert selbst bei großer Blockzahl um 50-100ms, also praktisch garnix, so dass ich das einfach mal als strukturelles Optimum ansehe. Der Quadtree musste also letztlich doch dran glauben :)

Ich bin nun aber auch echt reif für reichlich :cheers: