Αυτό είναι το μέρος ΙΙ της σειράς τριών μερών μας στη φυσική των βιντεοπαιχνιδιών. Για το υπόλοιπο αυτής της σειράς, δείτε:

Μέρος I: Εισαγωγή στη δυναμική του άκαμπτου σώματος
Μέρος III: Περιορισμένη άκαμπτη προσομοίωση σώματος

---

Στο Μέρος Ι αυτής της σειράς, διερευνήσαμε άκαμπτα σώματα και τις κινήσεις τους. Σε αυτήν τη συζήτηση, ωστόσο, τα αντικείμενα δεν αλληλεπιδρούν μεταξύ τους. Χωρίς κάποια πρόσθετη εργασία, τα προσομοιωμένα άκαμπτα σώματα μπορούν να περάσουν το ένα από το άλλο, ή «interpenetrate», το οποίο είναι ανεπιθύμητο στις περισσότερες περιπτώσεις.

Για να προσομοιώσουμε πιο ρεαλιστικά τη συμπεριφορά των στερεών αντικειμένων, πρέπει να ελέγξουμε αν συγκρούονται μεταξύ τους κάθε φορά που κινούνται, και αν το κάνουν, πρέπει να κάνουμε κάτι γι 'αυτό, όπως η εφαρμογή δυνάμεων που αλλάζουν τις ταχύτητές τους, έτσι ότι θα κινηθούν προς την αντίθετη κατεύθυνση. Εδώ είναι ιδιαίτερα σημαντική η κατανόηση της φυσικής σύγκρουσης προγραμματιστές παιχνιδιών .

Στο Μέρος II, θα καλύψουμε το βήμα ανίχνευσης σύγκρουσης, το οποίο συνίσταται στην εύρεση ζευγών σωμάτων που συγκρούονται μεταξύ ενός πιθανώς μεγάλου αριθμού σωμάτων που είναι διάσπαρτα σε έναν 2D ή 3D κόσμο. Στην επόμενη και τελική δόση, θα μιλήσουμε περισσότερο για την «επίλυση» αυτών των συγκρούσεων για την εξάλειψη των αλληλοδιεισδύσεων.

Για μια ανασκόπηση των εννοιών γραμμικής άλγεβρας που αναφέρονται σε αυτό το άρθρο, μπορείτε να ανατρέξετε στο γραμμικό μάθημα συντριβής άλγεβρας στο Μέρος Ι .

Φυσική σύγκρουσης σε βιντεοπαιχνίδια

Στο πλαίσιο των άκαμπτων προσομοιώσεων σώματος, μια σύγκρουση συμβαίνει όταν τα σχήματα δύο άκαμπτων σωμάτων τέμνονται ή όταν η απόσταση μεταξύ αυτών των σχημάτων πέφτει κάτω από μια μικρή ανοχή.

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

Η ευρεία φάση είναι υπεύθυνη για την εύρεση ζευγών άκαμπτων σωμάτων που είναι ενδεχομένως συγκρούονται και αποκλείουν ζευγάρια που σίγουρα δεν συγκρούονται, μεταξύ όλων των σωμάτων που βρίσκονται στην προσομοίωση. Αυτό το βήμα πρέπει να μπορεί να κλιμακωθεί πολύ καλά με τον αριθμό των άκαμπτων αμαξωμάτων για να βεβαιωθούμε ότι παραμένουμε καλά κάτω από το Ή ( ν 2)χρονική πολυπλοκότητα. Για να επιτευχθεί αυτό, αυτή η φάση χρησιμοποιεί γενικά διαχωρισμός χώρου σε συνδυασμό με όγκοι οριοθέτησης που δημιουργούν ένα ανώτερο όριο σύγκρουσης.

Η στενή φάση λειτουργεί στα ζεύγη άκαμπτων σωμάτων που βρίσκονται από την ευρεία φάση που μπορεί να συγκρούονται. Είναι ένα βήμα βελτίωσης όπου καθορίζουμε εάν οι συγκρούσεις πραγματικά συμβαίνουν και για κάθε σύγκρουση που βρίσκεται, υπολογίζουμε τα σημεία επαφής που θα χρησιμοποιηθούν για την επίλυση των συγκρούσεων αργότερα.

Στις επόμενες ενότητες θα μιλήσουμε για ορισμένους αλγόριθμους που μπορούν να χρησιμοποιηθούν σε ευρεία και στενή φάση.

Ευρεία φάση

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

Ορισμένοι δημοφιλείς τύποι όγκων οριοθέτησης είναι προσανατολισμένα κουτιά οριοθέτησης (OBB), κύκλοι σε 2D και σφαίρες σε 3D. Ας δούμε έναν από τους πιο απλούς τόμους οριοθέτησης: πλαίσια οριοθέτησης με άξονα (AABB) .

Οι AABBs παίρνουν πολλή αγάπη από τους προγραμματιστές φυσικής επειδή είναι απλοί και προσφέρουν καλές ανταλλαγές. Ένα δισδιάστατο AABB μπορεί να αντιπροσωπεύεται από μια δομή όπως αυτή στη γλώσσα C:

typedef struct { float x; float y; } Vector2; typedef struct { Vector2 min; Vector2 max; } AABB;

Το min Το πεδίο αντιπροσωπεύει τη θέση της κάτω αριστεράς γωνίας του πλαισίου και το max Το πεδίο αντιπροσωπεύει την επάνω δεξιά γωνία.

Για να ελέγξουμε αν δύο AABB τέμνονται, πρέπει να μάθουμε μόνο αν οι προβολές τους τέμνονται σε όλους τους άξονες συντεταγμένων:

BOOL TestAABBOverlap(AABB* a, AABB* b) d2y > 0.0f) return FALSE; return TRUE;

Αυτός ο κωδικός έχει την ίδια λογική του b2TestOverlap λειτουργία από το Πλαίσιο 2D κινητήρας (έκδοση 2.3.0). Υπολογίζει τη διαφορά μεταξύ του min και max και των δύο AABB, και στους δύο άξονες, και στις δύο σειρές. Εάν κάποια από αυτές τις τιμές είναι μεγαλύτερη από το μηδέν, τα AABB δεν τέμνονται.

Παρόλο που μια δοκιμή αλληλεπικάλυψης AABB είναι φθηνή, δεν θα βοηθήσει πολύ αν εξακολουθούμε να κάνουμε δοκιμές ανά ζεύγος για κάθε πιθανό ζεύγος, καθώς εξακολουθούμε να έχουμε το ανεπιθύμητο Ή ( ν 2)χρονική πολυπλοκότητα. Για να ελαχιστοποιήσουμε τον αριθμό των δοκιμών αλληλεπικάλυψης AABB μπορούμε να χρησιμοποιήσουμε κάποιο είδος διαχωρισμός χώρου , το οποίο λειτουργεί με τις ίδιες αρχές όπως δείκτες βάσης δεδομένων που επιταχύνουν τα ερωτήματα. (Γεωγραφικές βάσεις δεδομένων, όπως PostGIS , στην πραγματικότητα χρησιμοποιούν παρόμοιες δομές δεδομένων και αλγόριθμους για τους χωρικούς τους ευρετήρια.) Σε αυτήν την περίπτωση, ωστόσο, τα AABBs θα κινούνται συνεχώς, οπότε γενικά, πρέπει να δημιουργήσουμε ξανά δείκτες μετά από κάθε βήμα της προσομοίωσης.

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

Ο αλγόριθμος ταξινόμησης και σάρωσης

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

Η προβολή ενός AABB σε έναν άξονα συντεταγμένων είναι ουσιαστικά ένα διάστημα[ σι , είναι ](δηλαδή αρχή και τέλος). Στην προσομοίωσή μας, θα έχουμε πολλά άκαμπτα σώματα και, επομένως, πολλά AABB, και αυτό σημαίνει πολλά διαστήματα. Θέλουμε να μάθουμε ποια διαστήματα τέμνονται.

Στον αλγόριθμο ταξινόμησης και σάρωσης, εισάγουμε όλα σι και είναι τιμές σε μία λίστα και ταξινομήστε την αύξουσα από τις κλιμακωτές τιμές τους. Μετά εμείς σκούπισμα ή διασχίστε τη λίστα. Όποτε σι Η τιμή αντιμετωπίζεται, το αντίστοιχο διάστημα αποθηκεύεται σε ξεχωριστή λίστα ενεργά διαστήματα , και όποτε είναι συναντάται η τιμή, το αντίστοιχο διάστημα αφαιρείται από τη λίστα των ενεργών διαστημάτων. Ανά πάσα στιγμή, όλα τα ενεργά διαστήματα τέμνονται. (Ολοκλήρωση αγοράς Διδακτορική διατριβή του David Baraff , Π. 52 για λεπτομέρειες. Προτείνω τη χρήση αυτό το διαδικτυακό εργαλείο για να δείτε το αρχείο postscript.) Η λίστα των διαστημάτων μπορεί να επαναχρησιμοποιηθεί σε κάθε βήμα της προσομοίωσης, όπου μπορούμε να ταξινομήσουμε αποτελεσματικά αυτήν τη λίστα χρησιμοποιώντας είδος εισαγωγής , το οποίο είναι καλό στην ταξινόμηση λιστών σχεδόν ταξινομημένων.

Σε δύο και τρεις διαστάσεις, η εκτέλεση της ταξινόμησης και σάρωσης, όπως περιγράφεται παραπάνω, σε έναν άξονα συντεταγμένων θα μειώσει τον αριθμό των άμεσων δοκιμών διασταύρωσης AABB που πρέπει να εκτελεστούν, αλλά η απόδοση μπορεί να είναι καλύτερη σε έναν άξονα συντεταγμένων από τον άλλο. Επομένως, εφαρμόζονται πιο εξελιγμένες παραλλαγές του αλγορίθμου τύπου και σάρωσης. Στο βιβλίο του Ανίχνευση σύγκρουσης σε πραγματικό χρόνο (σελίδα 336), το Christer Ericson παρουσιάζει μια αποτελεσματική παραλλαγή όπου αποθηκεύει όλα τα AABBs σε έναν μόνο πίνακα, και για κάθε εκτέλεση της ταξινόμησης και σάρωσης, επιλέγεται ένας άξονας συντεταγμένων και ο πίνακας ταξινομείται με την min τιμή των AABBs στον επιλεγμένο άξονα, χρησιμοποιώντας γρήγορη ταξινόμηση . Στη συνέχεια, ο πίνακας διασχίζεται και πραγματοποιούνται δοκιμές αλληλεπικάλυψης AABB. Για να προσδιορίσετε τον επόμενο άξονα που πρέπει να χρησιμοποιηθεί για ταξινόμηση, το διαφορά υπολογίζεται το κέντρο του AABBs και ο άξονας με μεγαλύτερη διακύμανση επιλέγεται για το επόμενο βήμα.

Δέντρα δυναμικής οριοθέτησης

Μια άλλη χρήσιμη χωρική μέθοδος διαμέρισης είναι η δέντρο δυναμικού ορίου όγκου , επίσης γνωστός ως Dbvt . Αυτός είναι ένας τύπος ιεραρχία οριακού όγκου .

Το Dbvt είναι ένα δυαδικό δέντρο στο οποίο κάθε κόμβος έχει ένα AABB που οριοθετεί όλα τα AABBs των παιδιών του. Τα ΑΑΒΒ των ίδιων των άκαμπτων σωμάτων βρίσκονται στους κόμβους των φύλλων. Συνήθως, ένα Dbvt «ερωτάται» δίνοντας το AABB για το οποίο θα θέλαμε να εντοπίσουμε διασταυρώσεις. Αυτή η λειτουργία είναι αποτελεσματική επειδή τα παιδιά των κόμβων που δεν τέμνουν το ερώτημα AABB δεν χρειάζεται να ελεγχθούν για επικάλυψη. Ως εκ τούτου, ένα ερώτημα σύγκρουσης AABB ξεκινά από τη ρίζα και συνεχίζεται αναδρομικά μέσω του δέντρου μόνο για κόμβους AABB που τέμνονται με το ερώτημα AABB. Το δέντρο μπορεί να ισορροπηθεί περιστροφές δέντρων , όπως σε ένα Δέντρο AVL .

Το Box2D έχει μια εξελιγμένη εφαρμογή του Dbvt στο b2DynamicTree τάξη . ο b2BroadPhase τάξη είναι υπεύθυνη για την εκτέλεση της ευρείας φάσης και χρησιμοποιεί μια παρουσία b2DynamicTree για να εκτελέσετε ερωτήματα AABB.

Στενή φάση

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

Κυρτά και κοίλα σχήματα

Ως γενικός κανόνας της φυσικής του βιντεοπαιχνιδιού, δεν είναι ασήμαντο να καθοριστεί εάν δύο αυθαίρετα σχήματα τέμνονται ή να υπολογίζεται η απόσταση μεταξύ τους. Ωστόσο, μια ιδιότητα που έχει κρίσιμη σημασία για τον καθορισμό του πόσο δύσκολη είναι, είναι η κυρτότητα του σχήματος. Τα σχήματα μπορούν να είναι είτε κυρτός ή κοίλος και τα κοίλα σχήματα είναι πιο δύσκολο να δουλέψουμε, επομένως χρειαζόμαστε μερικές στρατηγικές για να τα αντιμετωπίσουμε.

Σε κυρτό σχήμα, ένα γραμμικό τμήμα μεταξύ οποιωνδήποτε δύο σημείων εντός του σχήματος πέφτει πάντα εντελώς μέσα στο σχήμα. Ωστόσο, για ένα κοίλο (ή «μη κυρτό») σχήμα, το ίδιο δεν ισχύει για όλα τα πιθανά τμήματα γραμμής που συνδέουν σημεία στο σχήμα. Εάν μπορείτε να βρείτε τουλάχιστον ένα τμήμα γραμμής που πέφτει έξω από το σχήμα, τότε το σχήμα είναι κοίλο.

τι είναι οι διαρροές μνήμης στη java

Υπολογιστικά, είναι επιθυμητό όλα τα σχήματα να είναι κυρτά σε μια προσομοίωση, καθώς έχουμε πολλούς ισχυρούς αλγόριθμους δοκιμής απόστασης και τομής που λειτουργούν με κυρτά σχήματα. Ωστόσο, δεν θα είναι όλα τα αντικείμενα κυρτά και συνήθως δουλεύουμε γύρω τους με δύο τρόπους: κυρτό κύτος και κυρτή αποσύνθεση.

ο κυρτό κύτος ενός σχήματος είναι το μικρότερο κυρτό σχήμα που το περιέχει πλήρως. Για ένα κοίλο πολύγωνο σε δύο διαστάσεις, θα ήταν σαν να σφίγγετε ένα καρφί σε κάθε κορυφή και να τυλίγετε μια λαστιχένια ταινία γύρω από όλα τα νύχια. Για τον υπολογισμό της κυρτής γάστρας για ένα πολύγωνο ή πολύεδρο, ή γενικότερα, για ένα σύνολο σημείων, ένας καλός αλγόριθμος που χρησιμοποιείται είναι ο γρήγορο κύτος αλγόριθμος, ο οποίος έχει μέση χρονική πολυπλοκότητα Ή ( ν κούτσουρο ν ).

Προφανώς, εάν χρησιμοποιήσουμε ένα κυρτό κύτος για να αντιπροσωπεύσουμε ένα κοίλο αντικείμενο, θα χάσει τις κοίλες του ιδιότητες. Ανεπιθύμητη συμπεριφορά, όπως συγκρούσεις «φάντασμα» μπορεί να γίνει εμφανής, καθώς το αντικείμενο θα έχει ακόμα μια κοίλη γραφική παράσταση. Για παράδειγμα, ένα αυτοκίνητο έχει συνήθως κοίλο σχήμα και αν χρησιμοποιούμε ένα κυρτό κύτος για να το αντιπροσωπεύσουμε φυσικά και στη συνέχεια να τοποθετήσουμε ένα κουτί πάνω του, το κουτί μπορεί να φαίνεται να αιωρείται στον παραπάνω χώρο.

Σε γενικές γραμμές, τα κυρτά κύτη είναι συχνά αρκετά καλά για να αντιπροσωπεύουν κοίλα αντικείμενα, είτε επειδή οι μη ρεαλιστικές συγκρούσεις δεν είναι πολύ αισθητές, είτε οι κοίλες ιδιότητές τους δεν είναι απαραίτητες για ό, τι προσομοιώνεται. Ωστόσο, σε ορισμένες περιπτώσεις, ίσως θέλουμε το κοίλο αντικείμενο να συμπεριφέρεται σαν κοίλο σχήμα φυσικά. Για παράδειγμα, εάν χρησιμοποιήσουμε ένα κυρτό κύτος για να αντιπροσωπεύσουμε ένα μπολ φυσικά, δεν θα μπορέσουμε να βάλουμε τίποτα μέσα σε αυτό. Τα αντικείμενα απλώς θα επιπλέουν πάνω του. Σε αυτήν την περίπτωση, μπορούμε να χρησιμοποιήσουμε ένα κυρτή αποσύνθεση του κοίλου σχήματος.

Οι κυρτοί αλγόριθμοι αποσύνθεσης λαμβάνουν ένα κοίλο σχήμα και επιστρέφουν ένα σύνολο κυρτών σχημάτων των οποίων η ένωση είναι ίδια με το αρχικό κοίλο σχήμα. Ορισμένα κοίλα σχήματα μπορούν να αναπαρασταθούν μόνο από μεγάλο αριθμό κυρτών σχημάτων και αυτά μπορεί να γίνουν απαγορευτικά δαπανηρά για υπολογισμό και χρήση. Ωστόσο, μια προσέγγιση είναι συχνά αρκετά καλή, και έτσι, αλγόριθμοι όπως V-HACD παράγουν ένα μικρό σύνολο κυρτών πολυεδρών από ένα κοίλο πολυέδρον.

Ωστόσο, σε πολλές περιπτώσεις φυσικής συγκρούσεων, η κυρτή αποσύνθεση μπορεί να γίνει με το χέρι, από έναν καλλιτέχνη. Αυτό εξαλείφει την ανάγκη φορολόγησης της απόδοσης με αλγόριθμους αποσύνθεσης. Δεδομένου ότι η απόδοση είναι μια από τις πιο σημαντικές πτυχές των προσομοιώσεων σε πραγματικό χρόνο, είναι γενικά καλή ιδέα να δημιουργείτε πολύ απλές φυσικές αναπαραστάσεις για πολύπλοκα γραφικά αντικείμενα. Η παρακάτω εικόνα δείχνει μια πιθανή κυρτή αποσύνθεση ενός 2D αυτοκινήτου χρησιμοποιώντας εννέα κυρτά σχήματα.

Δοκιμή για διασταυρώσεις - Το θεώρημα του διαχωριστικού άξονα

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

Συνήθως είναι πιο οπτικά διαισθητικό να βρείτε μια γραμμή σε 2D ή ένα επίπεδο σε 3D που διαχωρίζει τα δύο σχήματα, ωστόσο, η οποία είναι ουσιαστικά η ίδια αρχή. Ένα διάνυσμα ορθογώνιο στη γραμμή στο 2D, ή το κανονικό διάνυσμα του επιπέδου σε 3D, μπορεί να χρησιμοποιηθεί ως «διαχωριστικός άξονας».

Οι κινητήρες της φυσικής του παιχνιδιού έχουν μια σειρά διαφορετικών κατηγοριών σχημάτων, όπως κύκλους (σφαίρες σε 3D), άκρα (τμήμα μιας γραμμής) και κυρτά πολύγωνα (πολυέδρα σε 3D). Για κάθε ζεύγος τύπου σχήματος, έχουν έναν ειδικό αλγόριθμο ανίχνευσης σύγκρουσης. Ο απλούστερος από αυτούς είναι πιθανώς ο αλγόριθμος κύκλου-κύκλου:

typedef struct { float centerX; float centerY; float radius; } Circle; bool CollideCircles(Circle *cA, Circle *cB) { float x = cA->centerX - cB->centerX; float y = cA->centerY - cB->centerY; float centerDistanceSq = x * x + y * y; // squared distance float radius = cA->radius + cB->radius; float radiusSq = radius * radius; return centerDistanceSq <= radiusSq; }

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

Για οποιοδήποτε ζεύγος σχημάτων, υπάρχει ένας άπειρος αριθμός αξόνων που μπορούμε να δοκιμάσουμε για διαχωρισμό. Έτσι, ο καθορισμός του άξονα που θα δοκιμάσετε πρώτα είναι ζωτικής σημασίας για μια αποτελεσματική εφαρμογή SAT. Ευτυχώς, όταν δοκιμάζουμε αν συγκρούεται ένα ζευγάρι κυρτών πολυγώνων, μπορούμε να χρησιμοποιήσουμε τους ακροδέκτες ακμής ως πιθανούς διαχωριστικούς άξονες. Το κανονικό διάνυσμα ν ενός άκρου είναι κάθετα προς το άκρο του φορέα, και δείχνει σημεία έξω από το πολύγωνο. Για κάθε άκρη κάθε πολυγώνου, πρέπει απλώς να μάθουμε αν είναι όλες οι κορυφές του άλλου πολυγώνου μπροστά της άκρης.

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

Για τα πολυέδρα, μπορούμε να χρησιμοποιήσουμε τα φυσιολογικά πρόσωπα και επίσης το εγκάρσιο προϊόν όλων των συνδυασμών άκρων από κάθε σχήμα. Αυτό ακούγεται σαν πολλά πράγματα για δοκιμή. Ωστόσο, για να επιταχύνουμε τα πράγματα, μπορούμε να αποθηκεύσουμε προσωρινά τον τελευταίο άξονα διαχωρισμού που χρησιμοποιήσαμε και να προσπαθήσουμε να τον χρησιμοποιήσουμε ξανά στα επόμενα βήματα της προσομοίωσης. Εάν ο προσωρινός άξονας διαχωρισμού δεν αποθηκεύει τα σχήματα πια, μπορούμε να αναζητήσουμε έναν νέο άξονα ξεκινώντας από πρόσωπα ή άκρα που γειτνιάζουν με την προηγούμενη όψη ή άκρη. Αυτό λειτουργεί επειδή τα σώματα συχνά δεν κινούνται ή περιστρέφονται πολύ μεταξύ των βημάτων.

aws πιστοποιημένο σχέδιο αρχιτέκτονα λύσεων

Το Box2D χρησιμοποιεί SAT για να ελέγξει εάν δύο κυρτά πολύγωνα τέμνονται στον αλγόριθμο ανίχνευσης σύγκρουσης πολυγώνων-πολυγώνων b2CollidePolygon.cpp .

Απόσταση υπολογιστών - Ο αλγόριθμος Gilbert-Johnson-Keerthi

Σε πολλές περιπτώσεις σύγκρουσης φυσικής, θέλουμε να θεωρήσουμε ότι τα αντικείμενα συγκρούονται όχι μόνο αν τέμνονται στην πραγματικότητα, αλλά και αν βρίσκονται πολύ κοντά το ένα στο άλλο, κάτι που απαιτεί από εμάς να γνωρίζουμε την απόσταση μεταξύ τους. ο Gilbert-Johnson-Keerthi Ο αλγόριθμος (GJK) υπολογίζει την απόσταση μεταξύ δύο κυρτών σχημάτων και επίσης τα πλησιέστερα σημεία τους. Είναι ένας κομψός αλγόριθμος που λειτουργεί με μια σιωπηρή αναπαράσταση κυρτών σχημάτων μέσω λειτουργιών υποστήριξης, αθροισμάτων Minkowski και απλών, όπως εξηγείται παρακάτω.

Λειτουργίες υποστήριξης

ΠΡΟΣ ΤΟ λειτουργία υποστήριξης μικρό ΠΡΟΣ ΤΟ( ρε )επιστρέφει ένα σημείο στο όριο του σχήματοςΠΡΟΣ ΤΟπου έχει την υψηλότερη προβολή στο διάνυσμα ρε . Μαθηματικά, έχει το υψηλότερο σημείο με ρε . Αυτό ονομάζεται a σημείο στήριξης , και αυτή η λειτουργία είναι επίσης γνωστή ως υποστήριξη χαρτογράφησης . Γεωμετρικά, αυτό το σημείο είναι το πιο μακρινό σημείο στο σχήμα προς την κατεύθυνση ρε .

Η εύρεση ενός σημείου στήριξης σε ένα πολύγωνο είναι σχετικά εύκολη. Για ένα σημείο στήριξης για το διάνυσμα ρε , πρέπει απλώς να περάσετε από τις κορυφές του και να βρείτε αυτό που έχει το υψηλότερο σημείο με ρε , σαν αυτό:

Vector2 GetSupport(Vector2 *vertices, int count, Vector2 d) { float highest = -FLT_MAX; Vector2 support = (Vector2){0, 0}; for (int i = 0; i highest) { highest = dot; support = v; } } return support; }

Ωστόσο, η πραγματική ισχύς μιας λειτουργίας υποστήριξης είναι ότι καθιστά εύκολη την εργασία με σχήματα όπως κώνοι, κύλινδροι και ελλείψεις, μεταξύ άλλων. Είναι μάλλον δύσκολο να υπολογιστεί η απόσταση μεταξύ τέτοιων σχημάτων απευθείας και χωρίς έναν αλγόριθμο όπως το GJK θα πρέπει συνήθως να τα διακρίνετε σε ένα πολύγωνο ή πολυέδρο για να κάνετε τα πράγματα πιο απλά. Ωστόσο, αυτό θα μπορούσε να οδηγήσει σε περαιτέρω προβλήματα, επειδή η επιφάνεια ενός πολυέδρου δεν είναι τόσο λεία όσο η επιφάνεια, ας πούμε, μιας σφαίρας, εκτός εάν το πολύεδρο είναι πολύ λεπτομερές, το οποίο μπορεί να οδηγήσει σε κακή απόδοση κατά την ανίχνευση σύγκρουσης. Μπορεί επίσης να εμφανιστούν και άλλες ανεπιθύμητες ενέργειες. Για παράδειγμα, μια 'πολυεδρική' σφαίρα μπορεί να μην κυλάει ομαλά.

Για να λάβουμε ένα σημείο στήριξης για μια σφαίρα που να επικεντρώνεται στην προέλευση, πρέπει απλώς να ομαλοποιήσουμε ρε (δηλαδή, υπολογισμός ρε / || ρε ||, που είναι ένα διάνυσμα με μήκος 1 (μήκος μονάδας) που δείχνει ακόμη προς την ίδια κατεύθυνση ρε και μετά το πολλαπλασιάζουμε με την ακτίνα της σφαίρας.

Ελεγχος Το χαρτί του Gino van den Bergen για να βρείτε περισσότερα παραδείγματα λειτουργιών υποστήριξης για κυλίνδρους και κώνους, μεταξύ άλλων σχημάτων.

Τα αντικείμενά μας, φυσικά, θα μετατοπιστούν και θα περιστραφούν από την προέλευση στον χώρο προσομοίωσης, οπότε πρέπει να είμαστε σε θέση να υπολογίσουμε σημεία στήριξης για ένα μεταμορφωμένο σχήμα. Χρησιμοποιούμε ένα μετασχηματισμός συγγενών Τ ( Χ ) = Ρ Χ + ντο να μετατοπίσουμε και να περιστρέψουμε τα αντικείμενά μας, όπου ντο είναι ο φορέας μετατόπισης και Ρ είναι το μήτρα περιστροφής . Αυτός ο μετασχηματισμός περιστρέφει πρώτα το αντικείμενο σχετικά με την προέλευση και μετά το μεταφράζει. Η λειτουργία στήριξης για ένα μεταμορφωμένο σχήμαΠΡΟΣ ΤΟείναι:

Minkowski Sums

ο Άθροισμα Minkowski δύο σχημάτωνΠΡΟΣ ΤΟκαισιορίζεται ως:

Αυτό σημαίνει ότι υπολογίζουμε το άθροισμα για όλους τους πόντους που περιέχονται στοΠΡΟΣ ΤΟκαισι. Το αποτέλεσμα είναι σαν φουσκώνοντας ΠΡΟΣ ΤΟμεσι.

Ομοίως, ορίζουμε το Διαφορά Minkowski όπως και:

το οποίο μπορούμε επίσης να γράψουμε ως άθροισμα MinkowskiΠΡΟΣ ΤΟμε-ΣΙ:

Για κυρτόΠΡΟΣ ΤΟκαισι,Α⊕Βείναι επίσης κυρτό.

Μία χρήσιμη ιδιότητα της διαφοράς Minkowski είναι ότι εάν περιέχει την προέλευση του χώρου, τα σχήματα τέμνονται, όπως φαίνεται στην προηγούμενη εικόνα. Γιατί αυτό? Διότι εάν δύο σχήματα τέμνονται, έχουν τουλάχιστον ένα κοινό σημείο, το οποίο βρίσκεται στην ίδια θέση στο διάστημα και η διαφορά τους είναι το μηδέν διάνυσμα, που είναι στην πραγματικότητα η προέλευση.

Ένα άλλο ωραίο χαρακτηριστικό της διαφοράς Minkowski είναι ότι εάν δεν περιέχει την προέλευση, η ελάχιστη απόσταση μεταξύ της προέλευσης και της διαφοράς Minkowski είναι η απόσταση μεταξύ των σχημάτων.

Η απόσταση μεταξύ δύο σχημάτων ορίζεται ως:

Με άλλα λόγια, η απόσταση μεταξύΠΡΟΣ ΤΟκαισιείναι το μήκος του συντομότερου διανύσματος απόΠΡΟΣ ΤΟπρος τοσι. Αυτός ο φορέας περιέχεται στοΑ⊖Βκαι είναι αυτό με το μικρότερο μήκος, το οποίο κατά συνέπεια είναι εκείνο που είναι πλησιέστερο στην προέλευση.

Σε γενικές γραμμές, δεν είναι απλό να δημιουργηθεί ρητά το άθροισμα δύο μορφών Minkowski. Ευτυχώς, μπορούμε να χρησιμοποιήσουμε και τη χαρτογράφηση υποστήριξης εδώ, καθώς:

ποιο από αυτά δεν είναι ένας τρόπος για να βοηθήσετε τον εαυτό σας να κατανοήσει το μεγαλύτερο εύρος της ροής εργασίας;

Simplex

Ο αλγόριθμος GJK αναζητά επαναληπτικά το σημείο της διαφοράς Minkowski που βρίσκεται πλησιέστερα στην προέλευση. Το κάνει με την κατασκευή μιας σειράς απλοί που είναι πιο κοντά στην προέλευση σε κάθε επανάληψη. Ένα απλό - ή πιο συγκεκριμένα, α k-απλό για έναν ακέραιοπρος το- είναι το κυρτό κύτος τουk + 1 άκρως ανεξάρτητη σημεία σε ένα k-διαστατικό χώρο. Δηλαδή, εάν για δύο σημεία, δεν πρέπει να συμπίπτουν, για τρία σημεία επιπλέον δεν πρέπει να βρίσκονται στην ίδια γραμμή, και εάν έχουμε τέσσερα σημεία, δεν πρέπει επίσης να βρίσκονται στο ίδιο επίπεδο. Ως εκ τούτου, το 0-simplex είναι ένα σημείο, το 1-simplex είναι ένα τμήμα γραμμής, το 2-simplex είναι ένα τρίγωνο και το 3-simplex είναι ένα τετράεδρο. Εάν αφαιρέσουμε ένα σημείο από ένα απλό, μειώνουμε τη διαστατικότητά του κατά ένα, και αν προσθέσουμε ένα σημείο σε ένα απλό, αυξάνουμε τη διαστατικότητά του κατά ένα.

GJK σε δράση

Ας τα συνδυάσουμε όλα αυτά για να δούμε πώς λειτουργεί το GJK. Για να προσδιορίσετε την απόσταση μεταξύ δύο σχημάτωνΠΡΟΣ ΤΟκαισιξεκινάμε παίρνοντας τη διαφορά του MinkowskiΑ⊖Β. Ψάχνουμε για το πλησιέστερο σημείο στην προέλευση στο σχήμα που προκύπτει, καθώς η απόσταση από αυτό το σημείο είναι η απόσταση μεταξύ των αρχικών δύο σχημάτων. Επιλέγουμε κάποιο σημείο β σεΑ⊖Β, που θα είναι η προσέγγιση απόστασης. Ορίζουμε επίσης ένα κενό σύνολο σημείωνΣΕ, το οποίο θα περιέχει τα σημεία στο τρέχον simplex δοκιμής.

Στη συνέχεια μπαίνουμε σε ένα βρόχο. Ξεκινάμε παίρνοντας το σημείο υποστήριξης σε = δΑ⊖Β(- β ), το σημείοΑ⊖Βτου οποίου προβάλλεται β είναι πιο κοντά στην προέλευση.

Αν|| σε ||δεν είναι πολύ διαφορετικό από αυτό|| β ||και η γωνία μεταξύ τους δεν άλλαξε πολύ (σύμφωνα με ορισμένες προκαθορισμένες ανοχές), αυτό σημαίνει ότι ο αλγόριθμος έχει συγκλίνει και μπορούμε να επιστρέψουμε|| β ||ως την απόσταση.

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

Η επόμενη εικόνα δείχνει ένα παράδειγμα τεσσάρων επαναλήψεων του αλγορίθμου GJK. Το μπλε αντικείμενο αντιπροσωπεύει τη διαφορά MinkowskiΑ⊖Βκαι το πράσινο διάνυσμα είναι β . Μπορείτε να δείτε εδώ πώς β ακονίζει στο πλησιέστερο σημείο στην προέλευση.

Για μια λεπτομερή και σε βάθος εξήγηση του αλγορίθμου GJK, ρίξτε μια ματιά στο άρθρο Μια γρήγορη και ισχυρή εφαρμογή GJK για ανίχνευση σύγκρουσης κυρτών αντικειμένων , από τον Gino van den Bergen. Το blog για το dyn4j η μηχανή φυσικής έχει επίσης ένα υπέροχη ανάρτηση στο GJK .

Το Box2D έχει εφαρμογή του αλγορίθμου GJK το b2Distance.cpp , στο b2Distance λειτουργία. Χρησιμοποιεί μόνο GJK κατά τη διάρκεια υπολογισμού κρούσης στον αλγόριθμό του για συνεχή ανίχνευση σύγκρουσης (ένα θέμα που θα συζητήσουμε περαιτέρω παρακάτω).

Ο κινητήρας φυσικής Chimpunk χρησιμοποιεί GJK για όλη την ανίχνευση σύγκρουσης και η εφαρμογή του είναι σε cpCollision.c , στο GJK λειτουργία. Εάν ο αλγόριθμος GJK αναφέρει διασταύρωση, πρέπει να γνωρίζει ποια είναι τα σημεία επαφής, μαζί με το βάθος διείσδυσης. Για να γίνει αυτό, χρησιμοποιεί τον Αλγόριθμο Επεκτεινόμενου Πολύτοπου, τον οποίο θα διερευνήσουμε στη συνέχεια.

Προσδιορισμός βάθους διείσδυσης - Ο αλγόριθμος διευρυνόμενου πολυτόπου

Όπως αναφέρθηκε παραπάνω, εάν τα σχήματαΠΡΟΣ ΤΟκαισιτέμνονται, το GJK θα δημιουργήσει ένα απλόΣΕπου περιέχει την προέλευση, μέσα στη διαφορά MinkowskiΑ⊖Β. Σε αυτό το στάδιο, γνωρίζουμε μόνο ότι τα σχήματα τέμνονται, αλλά στο σχεδιασμό πολλών συστημάτων ανίχνευσης σύγκρουσης, είναι επιθυμητό να μπορούμε να υπολογίσουμε πόση διασταύρωση έχουμε και ποια σημεία μπορούμε να χρησιμοποιήσουμε ως σημεία επαφής, έτσι ώστε χειριζόμαστε τη σύγκρουση με ρεαλιστικό τρόπο. ο Διευρυνόμενος αλγόριθμος πολυτόπων (EPA) μας επιτρέπει να λάβουμε αυτές τις πληροφορίες, ξεκινώντας από το σημείο όπου το GJK σταμάτησε: με ένα απλό που περιέχει την προέλευση.

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

Όταν δύο σχήματα τέμνονται, η διαφορά τους Minkowski περιέχει την προέλευση και το σημείο στο όριο της διαφοράς Minkowski που είναι πιο κοντά στην προέλευση είναι το MTV. Ο αλγόριθμος EPA βρίσκει αυτό το σημείο επεκτείνοντας το simplex που μας έδωσε η GJK σε ένα πολύγωνο. διαδοχικά διαιρώντας τα άκρα του με νέες κορυφές.

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

Χρησιμοποιώντας το GJK σε συνδυασμό με το EPA, λαμβάνουμε μια λεπτομερή περιγραφή της σύγκρουσης, ανεξάρτητα από το εάν τα αντικείμενα τέμνονται ήδη ή είναι αρκετά κοντά ώστε να θεωρούνται σύγκρουση.

Ο αλγόριθμος EPA περιγράφεται στο άρθρο Ερωτήματα εγγύτητας και υπολογισμός βάθους διείσδυσης σε αντικείμενα τρισδιάστατων παιχνιδιών , γραμμένο επίσης από τον Gino van den Bergen. Το blog dyn4j έχει επίσης ένα δημοσίευση σχετικά με το EPA .

Ανίχνευση συνεχούς σύγκρουσης

Οι τεχνικές φυσικής του βιντεοπαιχνιδιού που παρουσιάζονται μέχρι στιγμής εκτελούν ανίχνευση σύγκρουσης για ένα στατικό στιγμιότυπο της προσομοίωσης. Αυτό ονομάζεται διακριτή ανίχνευση σύγκρουσης και αγνοεί τι συμβαίνει μεταξύ των προηγούμενων και των τρεχόντων βημάτων. Για αυτόν τον λόγο, ορισμένες συγκρούσεις ενδέχεται να μην εντοπιστούν, ειδικά για αντικείμενα που κινούνται γρήγορα. Αυτό το ζήτημα είναι γνωστό ως σήραγγες .

Οι τεχνικές συνεχούς ανίχνευσης σύγκρουσης προσπαθούν να βρουν πότε δύο σώματα συγκρούστηκαν μεταξύ του προηγούμενου και του τρέχοντος βήματος της προσομοίωσης. Υπολογίζουν το χρόνος κρούσης , έτσι μπορούμε στη συνέχεια να επιστρέψουμε στο χρόνο και να επεξεργαστούμε τη σύγκρουση σε αυτό το σημείο.

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

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

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

Λαμβάνοντας υπόψη τη γραμμική κίνηση μεταξύ των βημάτων, μπορούμε να γράψουμε την ακόλουθη συνάρτηση για τη θέση του ντο έναςαπό τ Εγώ -έναςπρος το τ Εγώ

Είναι μια γραμμική παρεμβολή από Χ ένας( τ Εγώ -ένας)προς το Χ ένας( τ Εγώ ). Το ίδιο μπορεί να γίνει και για Χ 2. Για αυτό το διάστημα μπορούμε να γράψουμε μια άλλη συνάρτηση απόστασης:

Ορίστε αυτήν την έκφραση μηδέν και παίρνετε ένα τετραγωνική εξίσωση επί τ . Οι ρίζες μπορούν να βρεθούν απευθείας χρησιμοποιώντας το τετραγωνικός τύπος . Εάν οι κύκλοι δεν τέμνονται, ο τετραγωνικός τύπος δεν θα έχει λύση. Εάν το κάνουν, μπορεί να οδηγήσει σε μία ή δύο ρίζες. Εάν έχει μόνο μία ρίζα, αυτή η τιμή είναι ο χρόνος αντίκτυπου. Εάν έχει δύο ρίζες, η μικρότερη είναι η ώρα της κρούσης και η άλλη είναι η στιγμή που οι κύκλοι χωρίζονται. Σημειώστε ότι ο χρόνος κρούσης εδώ είναι ένας αριθμός από 0 έως 1. Δεν είναι χρόνος σε δευτερόλεπτα. είναι απλώς ένας αριθμός που μπορούμε να χρησιμοποιήσουμε για την παρεμβολή της κατάστασης των σωμάτων στην ακριβή τοποθεσία όπου συνέβη η σύγκρουση.

Συνεχής ανίχνευση σύγκρουσης για μη κύκλους

Η σύνταξη μιας συνάρτησης απόστασης για άλλα είδη σχημάτων είναι δύσκολη, κυρίως επειδή η απόσταση τους εξαρτάται από τους προσανατολισμούς τους. Για το λόγο αυτό, γενικά χρησιμοποιούμε επαναληπτικούς αλγόριθμους που μετακινούν τα αντικείμενα πιο κοντά σε κάθε επανάληψη έως ότου είναι αρκετά κοντά να θεωρηθεί σύγκρουση.

ο συντηρητική πρόοδος Ο αλγόριθμος μετακινεί τα σώματα προς τα εμπρός (και τα περιστρέφει) επαναλαμβανόμενα. Σε κάθε επανάληψη υπολογίζει ένα ανώτερο όριο για μετατόπιση. Ο αρχικός αλγόριθμος παρουσιάζεται στο Διδακτορική διατριβή του Brian Mirtich (τμήμα 2.3.2), που εξετάζει τη βαλλιστική κίνηση των σωμάτων. Αυτό το χαρτί του Erwin Coumans (ο συγγραφέας του Bullet Physics Engine) παρουσιάζει μια απλούστερη έκδοση που χρησιμοποιεί σταθερές γραμμικές και γωνιακές ταχύτητες.

Ο αλγόριθμος υπολογίζει τα πλησιέστερα σημεία μεταξύ των σχημάτωνΠΡΟΣ ΤΟκαισι, σχεδιάζει ένα διάνυσμα από το ένα σημείο στο άλλο και προβάλλει την ταχύτητα σε αυτό το διάνυσμα για να υπολογίσει ένα ανώτερο όριο κίνησης. Εγγυάται ότι κανένα σημείο στο σώμα δεν θα προχωρήσει πέρα ​​από αυτήν την προβολή. Στη συνέχεια, προωθεί τα σώματα προς τα εμπρός με αυτό το ποσό και επαναλαμβάνεται έως ότου η απόσταση πέσει κάτω από μια μικρή τιμή ανοχής.

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

Επίλυση συγκρούσεων

Μόλις εντοπιστεί σύγκρουση, είναι απαραίτητο να αλλάξετε τις κινήσεις των αντικρουόμενων αντικειμένων με ρεαλιστικό τρόπο, όπως να τα αναγκάσετε να αναπηδήσουν μεταξύ τους. Στην επόμενη και τελευταία δόση σε αυτές τις θεωρίες, θα συζητήσουμε μερικές δημοφιλείς μεθόδους για την επίλυση συγκρούσεων σε βιντεοπαιχνίδια.

βιβλιογραφικές αναφορές

Εάν ενδιαφέρεστε να αποκτήσετε μια βαθύτερη κατανόηση σχετικά με τη φυσική σύγκρουσης όπως οι αλγόριθμοι και οι τεχνικές ανίχνευσης σύγκρουσης, το βιβλίο Ανίχνευση σύγκρουσης σε πραγματικό χρόνο , από τον Christer Ericson, είναι απαραίτητο.

Δεδομένου ότι η ανίχνευση σύγκρουσης βασίζεται σε μεγάλο βαθμό στη γεωμετρία, το άρθρο του ApeeScape Υπολογιστική γεωμετρία στο Python: Από τη θεωρία στην εφαρμογή είναι μια εξαιρετική εισαγωγή στο θέμα.

Σχετίζεται με: Ένα εισαγωγικό σεμινάριο προγραμματισμού ρομπότ