Abstract - collision detektion är av största vikt för många tillämpningar inom datorgrafik och visualisering. Vanligtvis är ingång till en kollisionsdetektionsalgoritm ett stort antal geometriska objekt som består av en miljö, tillsammans med en uppsättning föremål som rör sig i miljön. Förutom att bestämma exakt de kontakter som uppstår mellan par av objekt, måste man också göra det i realtid. Tillämpningar som haptisk kraft-feedback kan kräva över 1000 kollision frågor per sekund. I den här artikeln utvecklar och analyserar vi en metod, baserad på gränsande volymhierarkier, för effektiv kollisionsdetektering för föremål som rör sig inom mycket komplexa miljöer. Vårt val av avgränsande volym är att använda en "diskrete orientation polytope" (" -dop"), en konvex polytope vars facetter bestäms av halvrymder vars yttre normal kommer från en liten fast uppsättning av orienteringar. Vi jämför en mängd olika metoder för att bygga hierarkier ("BVtrees") av avgränsande - dop. Vidare föreslår vi algoritmer för att upprätthålla ett effektivt BV-träd för rörliga objekt, när de roterar, och för att utföra snabb kollisionsdetektering med hjälp av BV-träd av rörliga objekt och av miljön. Våra algoritmer har implementerats och testats. Vi tillhandahåller experimentella bevis som visar att vårt tillvägagångssätt ger betydligt snabbare kollisionsdetektering än tidigare metoder.
Scener kan representeras i hierarkiska träd av avgränsande volymer REF.
Efficient Collision Detection Using Bounding Volume Hierarchies of k-DOPs
{'venue': 'IEEE TRANSACTIONS ON VISUALIZATION AND COMPUTER GRAPHICS', 'journal': None, 'mag_field_of_study': ['Computer Science']}