Fej og beskær

Sweep And Prune ( rus. find and trim ) er navnet på en algoritme i fysiksimuleringer, der bruges i kollisionsdetektionsproblemer for at reducere antallet af par af faste kroppe ( eng.  solid ), der skal kontrolleres for en kollision, dvs. er, for et kryds. Sweep And Prune er således en optimeringsalgoritme . Sweep And Prune-algoritmen sorterer begyndelsen (øvre grænse) og ender (nedre grænse) af Bounding -volumenet for hver krop langs mange vilkårlige akser. Når to kroppe bevæger sig, kan deres begyndelse og slutning overlappe hinanden. Hvis afgrænsningsvolumen for to kroppe overlapper langs alle akser, så er disse kroppe markeret til kontrol af kryds ved hjælp af mere nøjagtige og tidskrævende algoritmer.  

Sweep And Prune-algoritmen udnytter tidsmæssig sammenhæng , da der er stor sandsynlighed for, at kroppe ikke vil bevæge sig en væsentlig afstand i løbet af et simulationstrin. På grund af dette kan den sorterede liste over start- og slutafgrænsningsvolumener ved hvert simuleringstrin opdateres med relativt få beregningsoperationer.

Afhængigt af den anvendte type afgrænsningsvolumen er det nødvendigt at opdatere dimensionerne af afgrænsningsvolumenet, hver gang kroppen omorienteres. For at omgå dette kan tidsmæssig kohærens bruges til at beregne ændringer i geometrien af ​​beregningsvolumenet, som kræver færre operationer. En anden tilgang er at bruge afgrænsende kugler som afgrænsende volumener . 

Sweep And Prune-algoritmen er også kendt som sortering og sweep, [1] som blev givet til den af ​​David Baraff Ph .  D i hans 1992-artikel [2] . Efterfølgende værker som "I-COLLIDE" af Cowan og andre refererer til algoritmen som "Sweep And Prune". [3]

Noter

  1. ↑ Ericson, Christer (2005), Kollisionsdetektion i realtid , Morgan Kaufmann-serien i interaktiv 3D-teknologi, Amsterdam: Elsevier, s. 329–338, ISBN 978-1558607323 , < http://realtimecollisiondetection.net/books/rtcd/ > Arkiveret 27. juni 2009 på Wayback Machine 
  2. ↑ Baraff, D. (1992), Dynamic Simulation of Non-Peterating Rigid Bodies, (Ph. D-afhandling) , Computer Science Department, Cornell University, s. 52–56 , < http://www.cs.cmu.edu/~baraff/papers/index.html > Arkiveret 5. juni 2010 på Wayback Machine 
  3. ↑ Cohen, Jonathan D.; Lin, Ming C.; Manocha & Ponamgi, Madhav K. (9.-12. april 1995), I-COLLIDE: an Interactive and Exact Collision Detection System for Large Scale Environments) , Proceedings of the 1995 Symposium on Interactive 3D Graphics (Monterey, CA), s. 189–196 , < http://www.cs.jhu.edu/~cohen/Publications/icollide.pdf > Arkiveret 21. august 2008 på Wayback Machine 

Eksterne links