Article

Free access

I-COLLIDE: an interactive and exact collision detection system for large-scale environments

Authors:

Jonathan D. Cohen,

Dinesh Manocha,

Madhav PonamgiAuthors Info & Claims

I3D '95: Proceedings of the 1995 symposium on Interactive 3D graphics

Pages 189 - ff.

https://doi.org/10.1145/199404.199437

Published: 15 April 1995 Publication History

Abstract

we present an exact and interactive collision detection system, I-COLLIDE, for large-scale environments. Such environments are characterized by the number of objects undergoing rigid motion and the complexity of the models. The algorithm does not assume the objects' motions can be expressed as a closed form function of time. The collision detection system is general and can be easily interfaced with a variety of applications. The algorithm uses a two-level approach based on pruning multiple-object pairs using bounding boxes and performing exact collision detection between selected pairs of polyhedral models. We demonstrate the performance of the system in walkthrough and simulation environments consisting of a large number of moving objects. In particular, the system takes less than 1/20 of a second to determine all the collisions and contacts in an environment consisting of more than 1000 moving polytopes, each consisting of more than 50 faces on an HP-9000/750.

References

[1]

A.Garica-Alonso, N.Serrano, and J.Flaquer. Solving the collision detection problem. IEEE Computer Graphics and Applications, 13(3):36-43, 1994.

Digital Library

[2]

D. Barait. Curved surfaces and coherence for nonpenetrating rigid body simulation. A CM Computer Graphics, 24(4):19-28, 1990.

Digital Library

[3]

D. Bara.ff. Dynamic simulation o} non-penetrating rigid body simulation. PhD thesis, Cornell Universilzy, 1992.

[4]

S. Cameron. Collision detection by four-dimensional intersection testing. Proceedings of International Conference on Robotics and Automation, pages pp. 291-302, 1990.

[5]

S. Cameron. Approximation hierarchies and sbounds. In Proceedings. Symposium on Solid Model. ing Foundations and CAD/CAM Applications, pages 129-137, Austin, TX, 1991.

Digital Library

[6]

J. Cohen, M. Lin, D. Manocha, and K. Ponamgi. Interactive and exact collision detection for largescaled environments. Technical Report TR94-005, Department of Computer Science, University of North Carolina, 1994.

Digital Library

[7]

P. Dworkin and D. Zeltzer. A new model for efficient dynamics simulation. Proceedings Eurographics workshop on animation and simulation, pages 175- 184, 1993.

[8]

H. Edelsbrunner. A new approach to rectangle intersections, Part I. Internat. J. Comput. Math., 13:209- '2 lC, 1983.

[9]

J. Snyder et. al. Interval methods for multi-point collisions between time dependent curved surfaces. In Proceedings of A CM Siggraph, pages 321-334, 1993.

Digital Library

[10]

E. G. Gilbert, D. W. Johnson, and S. S. Keertffi. A fast procedure for computing the distance between objects in three-dimensional space. IEEE J. Robotics and Automation, vol RA-4:pp. 193-203, 1988.

[11]

J. K. Hahn. Realistic animation of rigid bodies. Computer Graphics, 22(4):pp. 299-308, 1988.

Digital Library

[12]

J.E. Hopcroft, J.T. Schwartz, and M. Sharir. Efficient detection of intersections among spheres. The International Journal of Robotics Research, 2(4):77- 80, 19~3.

[13]

H.Six and D.Wood. Cotmting and reporting imersections of D-ranges. IEEE Transactions on Computers, pages 46-55, 1982.

[14]

P. M. Hubbard. Interactive collision detection. In Proceedings of IEEE Symposium on Research Frontiers in Virtual Reality, October 1993.

[15]

J.C. Latombe. Robot Motion Planning. Kluwer Academic Publishers, 1991.

Digital Library

[16]

M. Lin and J. Canny. Efficient collision detection for animation. In Proceedings of the Third Eurograohics Workshop on Animation and Simulation, Cambridge, England, 1991.

[17]

M.C. {,in. Efficient Collision Detection for Animation and Robotics. PhD thesis, Department of Electrical F, ngineering and Computer Science, Univers:ity of Cafifornia, Berkeley, December 1993.

[18]

M. Moore and J. Wilhelms. Collision detection and response for computer animation. Computer Graphics, 22(4):289-298, 1988.

Digital Library

[19]

M.Shamos and D.Hoey. Geometric intersection problems. Proe. 17th An. IEEE Syrup. Found. on Cornput. Science, pages 208-215, 1976.

Digital Library

[20]

A. Pentland. Computational complexity versus simulated environment. Computer Graphics, 22(2):185- 192, 1990.

Digital Library

[21]

M. Ponamgi, D. Manocha, and M. Lin. Incremental algorithms for collision detection between solld models. Technical Report TR94-061, Department of Computer Science, University of North Carolina, Chapel Hill, 1994.

Digital Library

[22]

F.P. Preparata and M. I. Shamos. Computational Geometry. Springer-Verlag, New York, 1985.

Digital Library

[23]

W.Thibault and B.Naylor. Set operations on polyhedra u,~ing binary space partitioning trees. A CM Computer Graphics, 4, 1987.

Digital Library

[24]

D. Zeltzer. Autonomy, interaction and presence. Presence, 1(1):127, 1992.

Digital Library

Cited By

Burdea GCoiffet P(2024)Modeling Virtual EnvironmentsVirtual Reality Technology10.1002/9781119512608.ch6(309-403)Online publication date: 30-Aug-2024
https://doi.org/10.1002/9781119512608.ch6
Sun ZQiu YYang BJia ZZhang GZong Z(2023)A Data-Driven Model for Ice-Breaking Resistance of Structure Based on Non-Smooth Discrete Element Method and Artificial Neural Network MethodJournal of Marine Science and Engineering10.3390/jmse1103046911:3(469)Online publication date: 22-Feb-2023
https://doi.org/10.3390/jmse11030469
Gottschalk SLin MManocha D(2023)OBBTree: A Hierarchical Structure for Rapid Interference DetectionSeminal Graphics Papers: Pushing the Boundaries, Volume 210.1145/3596711.3596791(757-766)Online publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1145/3596711.3596791
Show More Cited By

Index Terms

I-COLLIDE: an interactive and exact collision detection system for large-scale environments

Recommendations

GI-COLLIDE: collision detection with geometry images
SCCG '05: Proceedings of the 21st Spring Conference on Computer Graphics

A new collision detection algorithm GI-COLLIDE is presented. The algorithm works with geometry images and codes bounding spheres as a perfectly balanced mip-map-like hierarchical data structure. The largest geometry image in the hierarchy stores the ...
True motion-compensated de-interlacing algorithm

This paper presents a true motion-compensated de-interlacing (TMCD) algorithm based on a fast true motion estimation scheme. The fast true motion estimation scheme, designated as a variable block size true motion estimation for a translated motion model ...
Video de-interlacing by adaptive 4-field global/local motion compensated approach

A de-interlacing algorithm using adaptive 4-field global/local motion compensated approach is presented. It consists of block-based directional edge interpolation, same-parity 4-field motion detection, global/local motion estimation and compensation. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

I3D '95: Proceedings of the 1995 symposium on Interactive 3D graphics

April 1995

218 pages

ISBN:0897917367

DOI:10.1145/199404

Chairman:
Michael Zyda
Naval Postgraduate School, Monterey, CA

Copyright © 1995 ACM.

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

SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 15 April 1995

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SI3D95

Sponsor:

SIGGRAPH

SI3D95: 1995 Symposium on Interactive 3D Graphics

April 9 - 12, 1995

California, Monterey, USA

Acceptance Rates

Overall Acceptance Rate 148 of 485 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

362
Total Citations
View Citations
3,621
Total Downloads

Downloads (Last 12 months)478
Downloads (Last 6 weeks)36

Reflects downloads up to 14 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Burdea GCoiffet P(2024)Modeling Virtual EnvironmentsVirtual Reality Technology10.1002/9781119512608.ch6(309-403)Online publication date: 30-Aug-2024
https://doi.org/10.1002/9781119512608.ch6
Sun ZQiu YYang BJia ZZhang GZong Z(2023)A Data-Driven Model for Ice-Breaking Resistance of Structure Based on Non-Smooth Discrete Element Method and Artificial Neural Network MethodJournal of Marine Science and Engineering10.3390/jmse1103046911:3(469)Online publication date: 22-Feb-2023
https://doi.org/10.3390/jmse11030469
Gottschalk SLin MManocha D(2023)OBBTree: A Hierarchical Structure for Rapid Interference DetectionSeminal Graphics Papers: Pushing the Boundaries, Volume 210.1145/3596711.3596791(757-766)Online publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1145/3596711.3596791
Cao JWang M(2023)A Fast and Generalized Broad-Phase Collision Detection Method Based on KD-Tree Spatial Subdivision and Sweep-and-PruneIEEE Access10.1109/ACCESS.2023.327420211(44696-44710)Online publication date: 2023
https://doi.org/10.1109/ACCESS.2023.3274202
Lashgari MRabbani HPlonka GSelesnick I(2022)Reconstruction of Connected Digital Lines Based on Constrained RegularizationIEEE Transactions on Image Processing10.1109/TIP.2022.319799131(5613-5628)Online publication date: 2022
https://doi.org/10.1109/TIP.2022.3197991
Kim YKim JPark D(2022)GraphDistNet: A Graph-Based Collision-Distance Estimator for Gradient-Based Trajectory OptimizationIEEE Robotics and Automation Letters10.1109/LRA.2022.31969567:4(11118-11125)Online publication date: Oct-2022
https://doi.org/10.1109/LRA.2022.3196956
Alobaid FAlmohammed NMassoudi Farid MMay JRößger PRichter AEpple B(2022)Progress in CFD Simulations of Fluidized Beds for Chemical and Energy Process EngineeringProgress in Energy and Combustion Science10.1016/j.pecs.2021.10093091(100930)Online publication date: Jul-2022
https://doi.org/10.1016/j.pecs.2021.100930
Wang XWang SWang MLi XSun DSu C(2022)Research on particle collision forward search algorithm and CFD–DEM variable time step coupling calculation methodActa Mechanica10.1007/s00707-022-03358-5233:11(4919-4937)Online publication date: 4-Oct-2022
https://doi.org/10.1007/s00707-022-03358-5
Zhou QXu WLiu G(2021)A contact detection algorithm for triangle boundary in GPU-based DEM and its application in a large-scale landslideComputers and Geotechnics10.1016/j.compgeo.2021.104371138(104371)Online publication date: Oct-2021
https://doi.org/10.1016/j.compgeo.2021.104371
Costa NPechlivanoglou TPapagelis M(2021) OL-HeatMapBig Data Research10.1016/j.bdr.2021.10023525:COnline publication date: 15-Jul-2021
https://dl.acm.org/doi/10.1016/j.bdr.2021.100235
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Figures

Tables

Media

View Table of Conten