skip to main content
10.1145/1315184.1315240acmconferencesArticle/Chapter ViewAbstractPublication PagesvrstConference Proceedingsconference-collections
Article

Stride scheduling for time-critical collision detection

Published: 05 November 2007 Publication History

Abstract

We present an event-based scheduling method for time-critical collision detection that meets time constraints by balancing and prioritizing computation spent on intersection tests without starvation. Our approach tests each potentially colliding pair of objects at a different frequency, with unbounded temporal resolution. We preserve believability by adaptively prioritizing intersection tests to reduce errors in collision detection, using information about the objects and scene. By combining kinetic sweep and prune with stride scheduling we interleave rendering, broad phase collision pruning, narrow phase intersection testing, and collision response. This approach accrues no per-frame overhead and allows interruption at any point in collision detection, including the broad phase.

References

[1]
Coming, D. S., and Staadt, O. G. 2006. Kinetic sweep and prune for multi-body coninuous motion. Computers & Graphics 30, 3 (June), 439--449.
[2]
Dingliana, J., and O'Sullivan, C. 2000. Graceful degradation of collision handling in physically based animation. Computer Graphics Forum 19, 3, 239--248.
[3]
Fares, C., and Hamam, Y. 2005. Collision detection for rigid bodies: A state of the art review. In GraphiCon 2005.
[4]
Hubbard, P. M. 1995. Collision detection for interactive graphics applications. IEEE Trans. Visualization and Computer Graphics 1, 3, 218--230.
[5]
Hubbard, P. M. 1996. Approximating polyhedra with spheres for time-critical collision detection. ACM Transactions on Graphics 15, 3, 179--210.
[6]
O'Sullivan, C., and Dingliana, J. 1999. Real-time collision detection and response using sphere trees. In Proc. of the 15th Spring Conference on Computer Graphics '99, 83--92.
[7]
O'Sullivan, C., and Dingliana, J. 2001. Collisions and perception. ACM Trans. Graph. 20, 3, 151--168.
[8]
van den Bergen, G. 1999. A fast and robust GJK implementation for collision detection of convex objects. Journal of Graphics Tools 4, 2, 7--25.
[9]
Waldspurger, C. A., and Weihl, W. E. 1995. Stride scheduling: Deterministic proportional-share resource management. Tech. Rep. MIT/LCS/TM-528.

Cited By

View all
  • (2013)A Brief Overview of Collision DetectionNew Geometric Data Structures for Collision Detection and Haptics10.1007/978-3-319-01020-5_2(9-46)Online publication date: 2013
  • (2009)Collision detection algorithm based on slice projection2009 International Conference on Mechatronics and Automation10.1109/ICMA.2009.5246407(671-675)Online publication date: Aug-2009
  • (2009)Time‐critical collision handling for deformable modelingComputer Animation and Virtual Worlds10.1002/cav.29820:2-3(355-364)Online publication date: 5-May-2009

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
VRST '07: Proceedings of the 2007 ACM symposium on Virtual reality software and technology
November 2007
259 pages
ISBN:9781595938633
DOI:10.1145/1315184
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 November 2007

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. Collision Detection
  2. dynamic scenes
  3. many-body collision detection
  4. time-critical computing

Qualifiers

  • Article

Conference

VRST07

Acceptance Rates

Overall Acceptance Rate 66 of 254 submissions, 26%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 15 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2013)A Brief Overview of Collision DetectionNew Geometric Data Structures for Collision Detection and Haptics10.1007/978-3-319-01020-5_2(9-46)Online publication date: 2013
  • (2009)Collision detection algorithm based on slice projection2009 International Conference on Mechatronics and Automation10.1109/ICMA.2009.5246407(671-675)Online publication date: Aug-2009
  • (2009)Time‐critical collision handling for deformable modelingComputer Animation and Virtual Worlds10.1002/cav.29820:2-3(355-364)Online publication date: 5-May-2009

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media