Bounding Box Collision/intersection aber wie?

[estartu]

Hallo.
Ich programmiere hier in Java und mit jogl.
In meinem Programm gibt es zwei Kugel.

Ich möchte testen ob sich die zwei Kugeln berühren.
Ich bin nun auf Bounding Box Collision und intersection gestossen.

Kann mir jemand erklären wie ich von meinen beiden Kugeln zu zwei bounding boxen komme und wie ich dann diese auf intersections-überprüfen kann?

Ich bräuchte mal ein codebeispiel wie ich von der Kugel zu dem Bounding Box Objekt komme und wie ich dann diese intersection-Prüfung ausführe.



estartu

 

[ice-breaker]

Code kann ich dir nicht bieten aber eine Lösungsidee :wink:

wenn du einen Kugel zeichnest, hast du einen Durchmesser, nun bilde anhand dieses Radius eine Box (Bounding Box) um deinen Kugel, den gleichen Schritt vollführst du mit der 2 Kugel.
Sollten sich nun beide Boxen berühren oder überschneiden, dann berechnest du den Abstand der beiden Mittelpunkte der Kugel. sollte der Abstand größer sein als Radius1+Radius2 dann berühren sich beide Kugeln nicht
Die Bounding Box hat den Zweck die Kollisionsberechnung möglich effizient zu gestalten, denn man muss ja nicht dauerhaft den Abstand beider Mittelpunkte der Kugel berechnen, man kann sich ja darauf beschränken, dass eine Kollision erst statt finden kann, wenn sich die beiden Boxen berühren.

 

[schalentier]

Aehm... die Berechnung ob sich 2 Kugeln schneiden ist doch viel einfacher, als der Test, ob sich 2 Boxen schneiden...

Also fuer Kugeln braucht man echt keine Bounding Boxes... die braucht man fuer komplexere Objekte und dann entscheidet man sich wahlweise fuer Kugeln oder Boxen als Bounding-Koerper (je nach dem was besser zum eigentlichen Objekt passt)

 

[Evolver]

boolean checkCollision(Rect pBoxA, Rect pBoxB)
{
    if(pBoxA.mMinX>pBoxB.mMaxX) return false;
    if(pBoxA.mMaxX<pBoxB.mMinX) return false;
    if(pBoxA.mMinY>pBoxB.mMaxY) return false;
    if(pBoxA.mMaxY<pBoxB.mMinY) return false;
    return true;
}

Die Kollisionserkennung mit BoundingBox besteht nur aus 4 Vergleichen. Für die Berechnung des Abstands zweier Punkte (das baucht man ja bei Kugeln) muss man zweimal quadireren und dann die Wurzel ziehen. Das ist viel rechenaufwändiger. Gerade wenn man viele Kugeln hat, lohnen sich BoundingBoxes auf jeden Fall.

 

[estartu]

Hallo Ihr zwei.
Danke für eure Antworten.
Das sind meine ersten Experimente mit Kollisionen.
Ich will natürlich später auf komplexere Gebilde als nur Kugeln hinaus weshalb ich das mit den Bounding Boxen machen will. Ich könnte jatzt auch mit Würfeln experimentieren.

wenn du eine Kugel zeichnest, hast du einen Durchmesser, nun bilde anhand dieses Radius eine Box (Bounding Box) um deine Kugel

Genau darum geht es mir ja.
Ich weiss halt einfach nicht wie ich diese Bounding Box erzeugen soll.
Gibt es einen Befehl createBoundingBox(...
oder so ?

estartu

 

[EgonOlsen]

Genau darum geht es mir ja.
Ich weiss halt einfach nicht wie ich diese Bounding Box erzeugen soll.
Gibt es einen Befehl createBoundingBox(...
oder so ?

Den gibt es erst, wenn du die entsprechende Methode geschrieben hast. Die Bounding Box ist ja nichts, was mit Jogl gerendert werden würde. Sie ist nur ein gedachter Kasten um dein Objekt herum, mit dem du rechnen kannst. Die Bounding Box für eine Kugel im Objektraum zu erstellen ist trivial und wurde oben schon beschrieben: Du hast den Mittelpunkt und den Radius. Damit ergeben sich die Eckpunkte einer minimalen, an den Koordinatenachsen ausgerichteten Bounding Box (denn generell ist jeder Kasten, der ein Objekt komplett einschließt eine BB, auch wenn er 100* größer als nötig wäre). Die speicherst du in irgendeiner Struktur und fertig ist die BB. Für komplexere Körper, die sich auch im Raum drehen (ok, kann die Kugel auch, aber da ist es egal), musst du diese BB dann natürlich ebenfalls transformieren, sonst wird das nichts mit der Kollisionserkennung. Aber für Kugeln ist das wie gesagt egal.

 

[Evil-Devil]

Eine Bounding Box ist nichts weiter als ein QUader. Du benötigst lediglich ein Objekt/Array oder Vector in dem die Box gespeichert ist und die musst du dann dem jeweiligen Objekt noch zuweisen.

Dann nimmst du den Startpunkt der Box (X,Y) und die Länge/Breite und kannst damit die Collision mit einer anderen Box berechnen. Idealweise geschiet dies über eine seperate Funktion oder die Boundingbox bringt die Funktion selbst mit.

 

[schalentier]

Jupp ich hab irgendwie falsch gedacht. Dennoch, fuer KugelBounding"Boxen" braucht man nur 3 Subtraktionen, 3 Additionen und 3 Multiplikationen, sowie einen Vergleich (Quadrieren und Wurzelziehen kannste dir schenken ;-)).

@EgonOlsen: Dreht man BoundingBoxen wirklich mit dem Koerper mit? Weil dann wird die Berechnung auf Ueberlappung in der Tat schwierig... (Kollisition 2er Boxen, die beliebig im Raum liegen...).

 

[schalentier]

Das hat mir nun keine Ruhe gelassen:

import java.util.List;
import java.util.ArrayList;

/**
 * Created by IntelliJ IDEA.
 * User: schalentier
 * Date: 21.06.2007
 * Time: 13:33:00
 * To change this template use File | Settings | File Templates.
 */
public class BoundingTest {
    private static final int NO_BOUNDINGS = 10000;

    public class BoundingBox{
        double x1, y1, z1;
        double x2, y2, z2;

        public BoundingBox(double x1, double y1, double z1, double x2, double y2, double z2) {
            this.x1 = x1;
            this.y1 = y1;
            this.z1 = z1;
            this.x2 = x2;
            this.y2 = y2;
            this.z2 = z2;
        }

        public boolean intersect( BoundingBox b ) {
            if( b.x1>x2 ) return false;
            if( b.y1>y2 ) return false;
            if( b.z1>z2 ) return false;
            if( b.x2<x1 ) return false;
            if( b.y2<y1 ) return false;
            if( b.z2<z1 ) return false;
            return true;
        }
    }

    public class BoundingSphere {
        double x,y,z;
        double r, rSquared;

        public BoundingSphere(double x, double y, double z, double r) {
            this.x = x;
            this.y = y;
            this.z = z;
            this.r = r;
            rSquared = r*r;
        }

        public boolean intersect( BoundingSphere s ) {
            double distSquared = (s.x-x)*(s.x-x) + (s.y-y)*(s.y-y) + (s.z-z)*(s.z-z);
            if( distSquared< rSquared + s.rSquared ) return true;
            return false;
        }
    }

    public long benchmarkBoxes() {
        List<BoundingBox> boxes = new ArrayList<BoundingBox>();
        for( int i=0;i< NO_BOUNDINGS; i++) {
            boxes.add( new BoundingBox(Math.random(),Math.random(),Math.random(),Math.random(),Math.random(),Math.random()));
        }
        int numberOfIntersects = 0;
        long time = System.nanoTime();
        for( int i=0;i<NO_BOUNDINGS;i++ ) {
            for( int j=0;j<NO_BOUNDINGS;j++ ) {
                if( j==i ) continue;

                if( boxes.get(i).intersect( boxes.get(j) ) ) numberOfIntersects++;
            }
        }
        time = System.nanoTime() - time;
        System.out.println("Intersecting Boxes "+numberOfIntersects);
        System.out.println("Time "+time);
        return time;

    }

    public long benchmarkSpheres() {
        List<BoundingSphere> spheres = new ArrayList<BoundingSphere>();
        for( int i=0;i< NO_BOUNDINGS; i++) {
            spheres.add( new BoundingSphere(Math.random(),Math.random(),Math.random(),Math.random()));
        }
        int numberOfIntersects = 0;
        long time = System.nanoTime();
        for( int i=0;i<NO_BOUNDINGS;i++ ) {
            for( int j=0;j<NO_BOUNDINGS;j++ ) {
                if( j==i ) continue;

                if( spheres.get(i).intersect( spheres.get(j) ) ) numberOfIntersects++;
            }
        }
        time = System.nanoTime()-time;
        System.out.println("Intersecting Spheres "+numberOfIntersects);
        System.out.println("Time "+time);
        return time;
    }

    public static void main(String[] args) {
        double temp = 1;
        // initialize vm
        for( int i=0;i<10000000; i++) { temp*=temp; }
        System.out.println("Starting benchmark...");
        BoundingTest test = new BoundingTest();
        long timeBoxes = test.benchmarkBoxes();
        long timeSpheres = test.benchmarkSpheres();

        System.out.println("Boxes/Spheres "+(double) timeBoxes/(double) timeSpheres);

    }
}


-->

Starting benchmark...
Intersecting Boxes 1669276
Time 5829930147
Intersecting Spheres 60922124
Time 6948703558
Boxes/Spheres 0.8389953749412776

Jo, BoundingBoxes sind bisschen schneller als Kugeln... aber nicht wirklich der Rede wert ;-)

 

[EgonOlsen]

@EgonOlsen: Dreht man BoundingBoxen wirklich mit dem Koerper mit? Weil dann wird die Berechnung auf Ueberlappung in der Tat schwierig... (Kollisition 2er Boxen, die beliebig im Raum liegen...).

Kann man machen...es kommt auf den Anwendungsfall an. Ich würde es auch vermeiden, wenn es nicht nötig ist, aber wenn man eine Kollision im Raum nur anhand der BBs bestimmen will, kann es nötig werden. In jPCT mache ich das zumeist nicht, weil die Kollisionen sowieso im Objectspace berechnet werden und ich nie zwei BBs kollidieren lasse. Wenn man Kollisionen im Objectspace berechnet, müsste man auch nur eine Box transformieren, nämlich in den Objectspace der anderen. Das mag die Berechnung etwas vereinfachen.

 

[estartu]

Aha.
Ich glaube langsam blicke ich durch.
Ich dachte eine Bounding Box wäre eine Klasse der ich die Grösse oder die Koordinaten eines Objektes, egal ob Kugel oder Quader übergeben kann und das dieses neue Objekt dann die Funktion intersect mitbringt.
Danke an euch alle.

estartu