Collision Detection ( Sphere - Box )

[BonJovi]

Έχω υλοποιήσει μία συνάρτηση, η οποία υπολογίζει αν μία σφαίρα τέμνει ένα... κουτί (κυβοειδές). Χρησιμοποιώ τη μέθοδο του κοντινότερου σημείου. Πιο συγκεκριμένα, καθώς κινείται η σφαίρα, υπολογίζω κάθε φορά ποιο είναι το κοντινότερο σημείο του κουτιού σε αυτή και υπολογίζω την απόσταση του από το κέντρο της σφαίρας.

 

Το πρόβλημα είναι το εξής: με ποιο τρόπο μπορώ να υπολογίσω ποια από όλες τις έδρες του κουτιού τέμνει για πρώτη φορά η σφαίρα ώστε να καθορίσω και την κίνησή / κατεύθυνσή της στη συνέχεια?

[godlike]

Αυτό που χρειάζεσαι (αν κατάλαβα σωστά) είναι κάποια data για να ξεχωρίσεις τα 2 primitives όταν υπάρχει collision. Συνήθως αυτά τα data είναι: ένα vector που δείχνει την κατεύθυνση στην οποία πρέπει να κινηθεί το ένα από τα 2 (normal), έναν float που δείχνει πόση απόσταση πρέπει να κινηθεί πάνω στο vector (depth) και το σημείο της σύγκρουσης (impact_point).

 

Όλα αυτά αν υποθέσουμε ότι κατάλαβα τι ζητάς και εάν υποθέσουμε ότι το box είναι ένας axis-align bounding box (aabb). Ο κώδικας είναι ο παρακάτω:

 

>
bool SeperationTest( const aabb_t& box, const bsphere_t& sphere, vec3_t& normal, vec3_t& impact_point, float& depth )
{
const vec3_t& c = sphere.center;
const float r = sphere.radius;
const vec3_t& min = box.min;
const vec3_t& max = box.max;
vec3_t cp; // closest point of box that its closer to the sphere's center

for( int i=0; i<3; i++ )
{
	if( c[i] >= max[i] ) // if the center is greater than the max then the closest point is the max
		cp[i] = max[i];
	else if( c[i] <= min[i]  ) // relative to the above
		cp[i] = min[i];
	else           // the c lies between min and max
		cp[i] = c[i];
}

vec3_t sub = c - cp; // if the c lies totaly inside the box then the sub is the zero,
                     // this means that the length is also zero and thus its always smaller than rsq

float sublsq = sub.LengthSquared();
if( sublsq > r*r ) return false; // if no collision leave before its too late

if( IsZero(sublsq) ) // this means that the closest point is coincide with the center so the center is totaly inside tha box. We have to revise the calcs
{
	int n_axis = 0; // the axis that the normal will be
	float min_d = FLT_MAX; // in the end of "for" the min_d holds the min projection dist of c to every cube's facet
	float coord = 0.0;
	for( int i=0; i<3; i++ )
	{
		// dist between c and max/min in the i axis
		float dist_c_max = max[i]-c[i];
		float dist_c_min = c[i]-min[i];

		if( dist_c_max < min_d && dist_c_max < dist_c_min )
		{
			min_d = dist_c_max;
			n_axis = i;
			coord = max[i];
		}
		else if( dist_c_min < min_d )
		{
			min_d = dist_c_min;
			n_axis = i;
			coord = min[i];
		}
	}

	float dif = coord - c[n_axis];

	normal.SetZero();
	normal[n_axis] = dif / min_d; // aka ... = (dif<0.0f) ? -1.0f : 1.0f;

	depth = r + min_d;

	impact_point = c-(normal*r);
}
// the c is outside the box
else
{
	normal = c - cp;

	depth = r - normal.Length();

	normal.Normalize();

	impact_point = c-(normal*r);
}

return true;
}

[afnman]

Θεωρητικα και στα γρήγορα:

Οταν η αποσταση του κεντρο της σφαιρας απο το κοντινοτερο σημειο του κουτιου ειναι 0, τότε υπολογιζεις για κάθε πλευρά του κουτιού τα normals (κανονικά διανύσματα). Εαν το εσωτερικό γινόμενο του normal της πλευράς με το μοναδιαιο δυανυσμα (διευθυνση) της σφαίρας ειναι μικροτερο του 0 τότε ειναι αυτή ειναι η πλευρά που εχει συγκρουστεί.

Σκεψου επισης οτι υπάρχει και η πιθανοτητα να πετύχει γωνια η σφαίρα.

[BonJovi]

godlike, πολύ πιθανό να είναι αυτό που θέλω. Απλά δεν έχω καταλάβει απόλυτα το θεωρητικό υπόβαθρο πάνω στο οποίο βασίζεται ο κώδικας. Υπάρχει σε κάποιο site να του ρίξω μια ματιά?

 

Πάντως ξεκινάει με τον υπολογισμό του σημείου του box που βρίσκεται πιο κοντά στη σφαίρα, ακριβώς όπως το έχω υλοποιήσει. Δεν έχω καταλάβει, όμως, στη συνέχεια τη λογική. Στην περίπτωση που το κέντρο της σφαίρας, είναι μέσα στο box, το n_axis καθορίζει τον άξονα και το κανονικό διάνυσμα βάσει του οποίου θα ανακλαστεί η σφαίρα? Αν π.χ. το n_axis είναι ο άξονας x, σημαίνει ότι η σφαίρα χτυπάει κάποια έδρα στα πλάγια, οπότε αλλάζει η κατεύθυνση της μόνο στον άξονα x? Στην περίπτωση που το κέντρο της σφαίρας είναι εκτός του box, πώς καθορίζεται αυτό?

 

Επίσης, πολύ σημαντικό είναι το γεγονός ότι ο παραπάνω κώδικας επιστρέφει το σημείο σύγκρουσης (impact point). Με βολεύει πάρα πολύ γιατί θέλω πρώτα να υπολογίζω αν η σφαίρα θα χτυπήσει το box στην επόμενη κίνησή της, ώστε να την τοποθετώ στο σημείο που εφάπτεται με το box και να μη το διαπερνάει.

 

 

 

afnman, πολύ καλή δείχνει η προσέγγιση σου και εύκολη στην υλοποίηση. Υπάρχει περίπτωση να είναι το εσωτερικό γινόμενο μικρότερο του 0 σε παραπάνω από μία πλευρές του box? (Μήπως πρέπει να είναι μικρότερη της ακτίνας της σφαίρας αφού η σύγκριση γίνεται με το κέντρο της?) Αν ναι, ποια επιλέγω? Τότε υπεισέρχεται η περίπτωση της γωνίας που αναφέρεις? (Φαντάζομαι ότι εννοείς τις ακμές του κύβου, οι γωνίες δε με ενδιαφέρουν σε αυτό που υλοποιώ αλλά δεν είναι κακό να υπάρχει έλεγχος για να το έχω γενικευμένο για άλλες εφαρμογές).

[afnman]

 

afnman, πολύ καλή δείχνει η προσέγγιση σου και εύκολη στην υλοποίηση. Υπάρχει περίπτωση να είναι το εσωτερικό γινόμενο μικρότερο του 0 σε παραπάνω από μία πλευρές του box? (Μήπως πρέπει να είναι μικρότερη της ακτίνας της σφαίρας αφού η σύγκριση γίνεται με το κέντρο της?) Αν ναι, ποια επιλέγω? Τότε υπεισέρχεται η περίπτωση της γωνίας που αναφέρεις? (Φαντάζομαι ότι εννοείς τις ακμές του κύβου, οι γωνίες δε με ενδιαφέρουν σε αυτό που υλοποιώ αλλά δεν είναι κακό να υπάρχει έλεγχος για να το έχω γενικευμένο για άλλες εφαρμογές).

 

 

Ναι, υπαρχει περιπτωση το εσωτερικο γινόμενο να ειναι αρνητικο περισσοτερο απο 1 φόρα και αυτο σημαινει οτι η μπάλα χτυπησε γωνίες ή ακμές.

Στην περιπτωση των ακμών, 2 θα ειναι οι πλευρές που θα επιστρεψουν αρνητικο αποτελεσμα, μπορεις να διαλεξεις μια στην τύχη. Εαν θες να βρεις ποιες ακμές ή γωνιες χτύπησε η σφαίρα, εκει θελει σκέψη ;p

[godlike]

godlike, πολύ πιθανό να είναι αυτό που θέλω. Απλά δεν έχω καταλάβει απόλυτα το θεωρητικό υπόβαθρο πάνω στο οποίο βασίζεται ο κώδικας. Υπάρχει σε κάποιο site να του ρίξω μια ματιά?

 

Πάντως ξεκινάει με τον υπολογισμό του σημείου του box που βρίσκεται πιο κοντά στη σφαίρα, ακριβώς όπως το έχω υλοποιήσει. Δεν έχω καταλάβει, όμως, στη συνέχεια τη λογική. Στην περίπτωση που το κέντρο της σφαίρας, είναι μέσα στο box, το n_axis καθορίζει τον άξονα και το κανονικό διάνυσμα βάσει του οποίου θα ανακλαστεί η σφαίρα? Αν π.χ. το n_axis είναι ο άξονας x, σημαίνει ότι η σφαίρα χτυπάει κάποια έδρα στα πλάγια, οπότε αλλάζει η κατεύθυνση της μόνο στον άξονα x? Στην περίπτωση που το κέντρο της σφαίρας είναι εκτός του box, πώς καθορίζεται αυτό?

 

Επίσης, πολύ σημαντικό είναι το γεγονός ότι ο παραπάνω κώδικας επιστρέφει το σημείο σύγκρουσης (impact point). Με βολεύει πάρα πολύ γιατί θέλω πρώτα να υπολογίζω αν η σφαίρα θα χτυπήσει το box στην επόμενη κίνησή της, ώστε να την τοποθετώ στο σημείο που εφάπτεται με το box και να μη το διαπερνάει.

 

Είτε το κέντρο της σφαίρας είναι μέσα στο aabb είτε είναι εκτός, ο normal μπορεί να είναι οτιδήποτε! Φαντάσου να πετάς με δύναμη μια μπάλα σε μια κόχη ενός κουτιού, η σφαίρα δεν θα φύγει κάθετα σε κάποια πλευρά του κουτιού αλλά κάπως περίεργα. Αυτό προσπαθεί να προσομοιώσει ο παραπάνω αλγόριθμος. Το μαθηματικό υπόβαθρο είναι μακροσκελές για να το αναλύσω, προσπάθησε να προσαρμόσεις τον αλγόριθμο στα δικά σου δεδομένα να δεις αν δουλεύει. Και ότι θέλεις το ξανασυζητάμε.

[BonJovi]

Ευχαριστώ για τις απαντήσεις, παιδιά. Το έχω αφήσει προσωρινά αυτό που φτιάχνω για να τελειώσω διάφορες εργασίες που πρέπει να παραδώσω αρχές Σεπτέμβρη. Θα προσπαθήσω να υλοποιήσω αυτά που προτείνατε και θα επανέλθω με τα αποτελέσματα και τυχόν απορίες. Στην ουσία αυτό που φτιάχνω είναι ένα παιχνίδι με πέναλτι και θέλω να βάλω δύο περιπτώσεις: να χτυπάει η μπάλα δοκάρι και να απομακρύνεται ή να καταλήγει στα δίχτυα, γι' αυτό με ενδιαφέρει και ποια έδρα χτυπάει για πρώτη φορά τελικά. Το είχα υλοποιήσει ως ένα βαθμό με τον υπολογισμό τομής ακτίνας (πάνω στην οποία κινείται η σφαίρα) και του επίπεδου πάνω στο οποίο βρίσκεται η μπροστινή πλευρά του δοκαριού αρχικά. Απλά μου φαινόταν ότι έχει πολλή φασαρία με αυτό τον τρόπο και πολλούς υπολογισμούς, αφού θα έπρεπε να ορίσω και τα επίπεδα των εσωτερικών εδρών των δοκαριών, ενώ πρέπει να ψάχνω αν η σφαίρα βρίσκεται στα όρια του επιπέδου που πρέπει για να χτυπήσει το δοκάρι. Ευχαριστώ και πάλι και θα επανέλθω σύντομα.

[BonJovi]

godlike, χρησιμοποίησα ένα κομμάτι της δικής σου μεθόδου. Έχω κάνει κάτι πατεντούλες βέβαια για να το προσαρμόσω και δεν το έχω φτιάξει ακόμα να παίζει ιδανικά αλλά, όπως έγραψα και στο προηγούμενο post, είμαι λίγο πιεσμένος από θέμα χρόνου αυτό τον καιρό. Το αποτέλεσμα φαίνεται στο link http://www.miniplay.gr/ep.swf. (Πρέπει να κάνεις κλικ μέσα στο παράθυρο κι ας είναι εξαφανισμένος ο κέρσορας και στη συνέχεια για τυχόν επόμενη εκτέλεση, refresh τη σελίδα ). Κάποια στιγμή θα το φτιάξω καλύτερα γιατί έχει μικροπροβληματάκια.