skip to main content
10.1145/1174429.1174450acmconferencesArticle/Chapter ViewAbstractPublication PagesgraphiteConference Proceedingsconference-collections
Article

Oriented convex polyhedra for collision detection in 3D computer animation

Published: 29 November 2006 Publication History

Abstract

This paper presents a method for fast-approximate collision detection between 3D models S undergoing rigid body motion. To enclose a 3D model in as tight as possible, we propose an approach known as oriented convex polyhedra R(S). By surrounding the 3D models tightly, the veracity of detected collision can be improved. It is known that the large number of empty corners which belongs to any 3D bounding volumes B(S) can affect the truthfulness of collision detection. Therefore, we describe a way to compute R(S) using intersection of a set of halfspaces. The directions of these halfspaces are generated from calculating covariance matrix. To acquire the tightest R(S) as possible, we have improved the quality of abutting corners by implementing similar approach as Tribox Bounds method. In our case, improvements of abutting corners are important since the generated intersection points will be used for intersection testing. To detect collision between R(S), we utilize local space of R(S) and perform a straightforward approach by simply checking its interval pairs. Our proposed approach was implemented and we perform a number of comparisons in terms of time and recorded collision with other B(S). From the conducted tests, R(S) performs well and might be a possible choice for detecting collisions of the 3D models undergoing rigid body motion.

References

[1]
Assarsson, U. and Möller, T. 2000. Optimized View Frustum Culling Algorithms for Bounding Boxes. Journal of Graphics Tools Volume 5, Issue 1 Pages: 9--22.
[2]
Bade, A. and Away, Yuwaldi. 2004.Bounding Volumes Approaches in Collision Detection: Requirements and advantages. 2nd National Conference on Computer Graphics and Multimedia 2004 (CoGRAMM04), Kuala Lumpur, Malaysia.
[3]
Bergen, G. V. D. 2003. Collision detection in interactive 3D environments, Morgan Kaufmann Publishers. USA.
[4]
Bergen, G. V. D. 1998. Efficient Collision Detection Of Complex Deformable Using AABB Trees. Journal of Graphics Tools 2,4. pages 1--13.
[5]
Chin-Shyurng, F. and Jui-Lung, W. 1999. Efficient Time-Interrupted and Time-Continuous Collision Detection Among Polyhedral Objects in Arbitrary Motion. Journal Of Information Science and Engineering 15, 769--799 (1999).
[6]
Crosnier, A., Rossignac, J. 1999. Tribox bounds for three-dimensional objects. Computers & Graphics 23 (3): 429--437.
[7]
Ericson. C. 2004. Real Time Collision Detection, Morgan Kaufmann Publishers. USA.
[8]
Eberly. D. 2002. Dynamic Collision Detection Using Oriented Bounding Boxes. Geometric Tools Inc. Chapel Hill, North Carolina. http://www.geometrictools.com.
[9]
Funfzig, C. and. Fellner, D. 2003. Easy realignment of k-Dop Bounding Volumes. Proceeding of Graphics Interface 2003, pages 257--264.
[10]
Gottschalk, S., Lin, M. C. and Manocha, D. 1996. OBB-Tree: A Hierarchical Structure for Rapid Interference Detection. In Computer Graphics Proceedings, Annual Conference Series, ACM SIGGRAPH. New Orleans, Louisiana. pages 171--180.
[11]
Gottschalk, S. 2000. Collision Queries Using Oriented Bounding Box, Ph.D Thesis, Department of Computer Science, University of North Carolina, Chapel Hill.
[12]
Hubbard, P. M. 1995. Collision Detection For Interactive Graphics Application. IEEE Transactions on Visualization and Computer Graphics. 1(3):218--230.
[13]
Halperin, D. and Sharir, M. 1993. New bounds for lower envelopes in three dimensions with application to visibility in terrains. Proceedings of 9th ACM Symposium on Computational Geometry. Pages 11--18.
[14]
Kay, T. L. and Kajiya, J. T. 1986. Ray Tracing Complex Scenes. Computer Graphics (SIGGRAPH '86 Proceedings. Volume 20, pages 269--278.
[15]
Klosowski, J. T. 1998. Efficient Collision Detection For Interactive 3D Graphics and Virtual Environment. Ph.D Thesis, State University of New York, Stony Brook.
[16]
Klosowski, J. T., Held, M., Mitchell, J. S. B., Sowizral, H. and Zikan, K. 1998. Efficient Collision Detection Using Bounding Volume Hierarchies Of k-Dops. IEEE Transaction on Visualization and Computer Graphics. Volume. 4, no.1.
[17]
Konecny, Petr. 1998. Bounding Volumes in Computer Graphics. MSc Thesis, Faculty of Informatics, Masaryk Universitiy, Brno, Czech Republic.
[18]
Lahanas. M, K. Thorsten, Milickovic. N, Karouzakis. K, Baltas. D. and Zamboglou. N. 2000. Optimized Bounding Boxes for Three-Dimensional Treatment Planning in Brachytherapy. Medical Physics, vol. 27, no. 10, pp. 2333--2342.
[19]
Larsson, T., Akenine-Möller, T. 2003. Strategies for Bounding Volume Hierarchy Updates for Ray Tracing of Deformable Models. MRTC Report, ISSN 1404--3041 ISRN MDH-MRTC-92/2003-1-SE.
[20]
Moller, T. and Haines, E. 1999. Real-Time Rendering. A K Peters Ltd.
[21]
Moore, M. P. and Wilhemls, J. 1988. Collision Detection and Response For Computer Animation. SIGGRAPH '88 Proceeding. pages.22(4):289--298.
[22]
Müller, G., Schäfer. S. and Fellner, D. 1999. A Rapid Clustering Algorithm for Efficient Rendering. Eurographics Association, ISSN 1017--4656.
[23]
Zachmann, G. 1998. Rapid collision detection by dynamically aligned DOP-Trees. Proceeding of IEEE Virtual Reality Annual International Symposium (VRAIS 1998), Atlanta, Georgia, pages 90--97.

Cited By

View all
  • (2015)Virtual reality for improving safety and collaborative control of industrial robotsProceedings of the 2015 Virtual Reality International Conference10.1145/2806173.2806197(1-6)Online publication date: 8-Apr-2015
  • (2012)Development of real-time virtual environment with hierarchical constructionProceedings of the 6th International Conference on Ubiquitous Information Management and Communication10.1145/2184751.2184870(1-6)Online publication date: 20-Feb-2012
  • (2011)Balanced Hierarchical Method of Collision Detection in Virtual EnvironmentSoftware Engineering and Computer Systems10.1007/978-3-642-22203-0_43(493-501)Online publication date: 2011

Index Terms

  1. Oriented convex polyhedra for collision detection in 3D computer animation

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    GRAPHITE '06: Proceedings of the 4th international conference on Computer graphics and interactive techniques in Australasia and Southeast Asia
    November 2006
    489 pages
    ISBN:1595935649
    DOI:10.1145/1174429
    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: 29 November 2006

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. bounding volumes
    2. collision detection
    3. virtual environments

    Qualifiers

    • Article

    Conference

    GRAPHITE06
    Sponsor:

    Acceptance Rates

    GRAPHITE '06 Paper Acceptance Rate 47 of 83 submissions, 57%;
    Overall Acceptance Rate 124 of 241 submissions, 51%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)1
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 27 Jan 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2015)Virtual reality for improving safety and collaborative control of industrial robotsProceedings of the 2015 Virtual Reality International Conference10.1145/2806173.2806197(1-6)Online publication date: 8-Apr-2015
    • (2012)Development of real-time virtual environment with hierarchical constructionProceedings of the 6th International Conference on Ubiquitous Information Management and Communication10.1145/2184751.2184870(1-6)Online publication date: 20-Feb-2012
    • (2011)Balanced Hierarchical Method of Collision Detection in Virtual EnvironmentSoftware Engineering and Computer Systems10.1007/978-3-642-22203-0_43(493-501)Online publication date: 2011

    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