Τι κάνω λάθος?

[Alchemist`]

Φτιάχνω ένα script για να εντοπίζει collisions, το πρόβλημα είναι πως ενώ τα πράγματα φαίνονται απλά, δεν δουλεύει...

 

Ορίστε ένα σχήμα του προβλήματος:

 

 

έχουμε το μπλέ τετράγωνο, το οποίο έχει διαστάσεις 16χ16, και κέντρο το pl_x,pl_y, (8,8 relative). Θέλω να εντοπίζω εάν υπάρχει collisions στο κόκκινο περίγραμμα του τετραγώνου, δλδ σε απόσταση 9 από το κέντρο. Η συνάρτηση Place_free(x,y) δείχνει αν υπάρχει κάποιο αντικείμενο στο σημείο x,y. Από το 0,0 του σχήματος, το χ αυξάνεται προς τα δεξιά, ενώ το y προς τα κάτω, κανένα δεν παίρνει αρνητική τιμή. Η μαύρες και άσπρες περιοχές δεν μας ενδιαφέρουν.

 

Ορίστε το script Που χρησιμοποιώ για τον έλεγχο όλων των σημείων του περιγράμματος:

 

Σημείωση, το user είναι το id του αντικειμένου που χρησιμοποιεί το script, απλά αγνοήστε το.

>
user = argument0
pl_x = argument1
pl_y = argument2

check_x = 0
check_y = 0

//left & right collisions
{for (check_y = pl_y-9;check_y = pl_y+9;check_y = check_y+1) 
if (not(place_free((pl_x+9),check_y))) then {
 user.right_collision = 1
} else {user.right_collision = 0}
if (not(place_free((pl_x-9),check_y))) then {
 user.left_collision = 1
} else {user.left_collision = 0}
}
//up & down collisions
{for (check_x = pl_x-9;check_x = pl_x+9;check_x = check_x+1) 
if (not(place_free(check_x,(pl_y-9)))) then {
 user.up_collision = 1
} else {user.up_collision = 0}
if (not(place_free(check_x,(pl_y+9)))) then {
 user.down_collision = 1
} else {user.down_collision = 0}
}

 

Το πρόβλημα είναι ότι, φαινομενικά, δουλεύουν σωστά μόνο το down και το left collision, και δεν μπορώ να καταλάβω το γιατί... Ίσως η όλη προσέγγιση είναι λάθος... Μπορεί να μου πει κανείς τι δεν κάνω σωστά? Thanks...

 

EDIT: ο έλεγχος αριστερά εντοπίζει collision και όταν είναι από πάνω... :S

[V.I.Smirnov]

Στα γρήγορα μιλώντας, αυτός ο τρόπος δεν είναι καλός.

 

Το μπλε ορθογώνιο είναι ευθυγραμισμένο με τους άξονες (είναι ένα axis aligned bounding box - AABB).

Aν το αντικείμενό σου βρίσκεται στο σημείο p, ο σωστός τρόπος είναι να βρεις το σημείο q επί του περιγράμματος του AABB που είναι κοντύτερα στο p.

Συγκρίνεις την απόσταση των p,q και στα πλαίσια κάποιας ακρίβειας αποφασίζεις αν υπάρχει τομή ή όχι.

Ή βρίσκεις την απόσταση d του p από το ΑΑΒΒ (και μετά κάνεις σύγκριση όπως και παραπάνω).

Να ο ψευδοκώδικας για τις δύο περιπτώσεις (ισχύει για 3d collision detection μεταξύ σημείου και ΑΑΒΒ).

 

>void ClosestPtPointAABB(Point p, AABB b, Point &q)
{
/* 
  For each coordinate axis, if the point coordinate value is
  outside box, clamp it to the box, else keep it as is
*/

for (int i = 0; i < 3; i++) 
{
  float v = p[i];
  if (v < b.min[i]) v = b.min[i]; // v = max(v, b.min[i])
  if (v > b.max[i]) v = b.max[i]; // v = min(v, b.max[i])
  q[i] = v;
}

}

 

 

>
// Computes the square distance between a point p and an AABB b
float SqDistPointAABB(Point p, AABB 
{
float sqDist = 0.0f;

for (int i = 0; i < 3; i++) {
// For each axis count any excess distance outside box extents
float v = p[i];
if (v < b.min[i]) sqDist += (b.min[i] - v) * (b.min[i] - v);
if (v > b.max[i]) sqDist += (v - b.max[i]) * (v - b.max[i]);
}
return sqDist;
}

 

-

[Alchemist`]

Στα γρήγορα μιλώντας, αυτός ο τρόπος δεν είναι καλός.

 

Το μπλε ορθογώνιο είναι ευθυγραμισμένο με τους άξονες (είναι ένα axis aligned bounding box - AABB).

Aν το αντικείμενό σου βρίσκεται στο σημείο p, ο σωστός τρόπος είναι να βρεις το σημείο q επί του περιγράμματος του AABB που είναι κοντύτερα στο p.

Συγκρίνεις την απόσταση των p,q και στα πλαίσια κάποιας ακρίβειας αποφασίζεις αν υπάρχει τομή ή όχι.

Ή βρίσκεις την απόσταση d του p από το ΑΑΒΒ (και μετά κάνεις σύγκριση όπως και παραπάνω).

 

Συμφωνώ μέχρι εδώ, αλλά τι γίνεται αν έχουμε περισσότερα από 1 collisions ταυτόχρονα, και πολλά είδη αντικειμένων που βρίσκονται σε διάφορα σημεία? Θα κάνουμε τον ίδιο έλεγχο για όλα? Θα είναι αποδοτικό αυτό αν έχουμε π.χ. 200 αντικείμενα?

 

Με τον παραπάνω τρόπο προσπάθησα να ανεξαρτητοποιήσω το collision detection από α) ποιό είναι το άλλο αντικείμενο και β) Τι σχήμα έχει το άλλο αντικείμενο. Απλώς τσεκάρω τί γίνεται Pixel προς Pixel γύρω του.

[Directx]

Αν το περιβάλλον εργασίας σου, παρέχει (όπως η VCL της Delphi/C++ Builder) κάποια ρουτίνα IntersectRect μπορεί να σε βοηθήσει να ανιχνεύσεις με σιγουριά πότε το τετράγωνο εισέρχεται ή εφάπτεται πάνω σε κάποιο άλλο τετράγωνο.

 

Για παράδειγμα, η IntersectRect σε βοηθά πολύ εύκολα να κάνεις κάτι σαν το παρακάτω:

 

http://www.youtube.com/watch?v=qxnj2NqqrjQ

 

Καλή συνέχεια!!

[V.I.Smirnov]

@Alchemist

 

Έδωσα ψευδοκώδικα που αφορά μόνον σημεία vs AABB διότι μίλησες για σημεία και στον κώδικά σου έλεγχες σημεία.

Aν με το "πολλά είδη αντικειμένων" εννοείς άλλα γεωμετρικά σχήματα, τότε πρέπει να χρησιμοποιήσεις αντίστοιχα tests.

Π.χ. σφαίρα vs ΑΑΒΒ. Ή να θεωρήσεις ότι ένα αντικείμενο περικλείεται προσσεγγιστικά από ένα ΑΑΒΒ ή ΟΒΒ (- oriented bounding box)

ή σφαίρα και να κάνεις test με αυτά. Έτσι θα έχεις ΑΑΒΒ vs ενός μόνον σχήματος (λιγότερο ακριβές αλλά θα δουλέψει).

Τα tests για τέτοια σχήματα είναι ουσιωδώς εφαρμογή της μεθόδου διαχωριζόμενων αξόνων (separating axis method).

Η μέθοδος αυτή είναι γενική στην ιδέα της αλλά κι' αυτή όμως υλοποιείται εν πολλοίς λαμβάνοντας υπόψη το σχήμα των πολυγώνων.

 

H απόλυτη λύση είναι ο αλγόριθμος Gilbert-Johnson-Keerhthi που είναι από τους πιο γρήγορους και ισχύει για όλα τα

κυρτά πολύγωνα (2d ή 3d) ενοποιημένα και ανεξαρτήτως του πλήθους των πλευρών τους. Παρόλο που δεν έχει πολύπλοκη υλοποίηση,

είναι δυσνόητος διότι βασίζεται στην διαφορά πολυγώνων κατά Minkowski και σε έννοιες από την κυρτότητα τις οποίες δεν γνωρίζει

ο πολύς κόσμος.

 

Ο ψευδοκώδικας που παρέθεσα έχει τις λιγότερες δυνατές πράξεις (ομοίως και για άλλα σχήματα).

Για μεγάλο πλήθος αντικειμένων η τεχνική που εμμέσως βοηθά αρκετά, είναι το πρόγραμμα να κάνει σωστή χρήση της cache μνήμης (data cache optimizations).

Αυτό είναι γενικά πολύ σημαντικό σε κώδικα όπου σαρώνεται μεγάλο μέρος της μνήμης.

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

 

-