More Web Proxy on the site http://driver.im/

research-article

Particle-based forecast mechanism for continuous collision detection in deformable environments

Authors:

Jean-Francois DufourdAuthors Info & Claims

SPM '09: 2009 SIAM/ACM Joint Conference on Geometric and Physical Modeling

Pages 147 - 158

https://doi.org/10.1145/1629255.1629274

Published: 05 October 2009 Publication History

Abstract

Collision detection in geometrically complex scenes is crucial in physical simulations and real time applications. Works based on spatial hierarchical structures have been proposed for years. If correct performances are obtained for static scenes, these approaches show some limitations when the complexity of the scene increases and particularly in case of deformable meshes. The main drawback is the time needed to update the spatial structures - often trees - when global deformations or topological changes occur in the scene. We propose a method to detect collisions in complex and deformable environments with constant time amortized complexity for small displacements.

Our method is based on a convex decomposition of the environment coupled with a forecast mechanism exploiting temporal coherence. We use the topological adjacencies and incidence relationships to reduce the number of geometrical tests. Deformations of the scenes are handled with no cost as far as no topological changes occur. Topological transformations, like cuts and sewings, are handled locally, exploiting the spatial coherence and do not imply global updates. We illustrate our method in two experimental frameworks: a particles flow simulation and a meshless animation system both lying in a deformable mesh. We compare our work with classical optimization based on bounding volumes hierarchies to validate its efficiency on large scenes.

Supplementary Material

JPG File (s147-jund.jpg)

Download
9.63 KB

AVI File (s147-jund.avi)

Download
19.49 MB

References

[1]

D. Bielser, P. Glardon, M. Teschner, and M. Gross. A state machine for real-time cutting of tetrahedral meshes. 11th Pacific Conference on Computer Graphics and Applications, pages 377--386, 2003.

Digital Library

[2]

E. Brisson. Representing geometry structures in d dimensions: Topology and order. Discrete&Computational Geometry, pages 387--426, 1993.

[3]

D. Cazier and J. Dufourd. A formal specification of geometric refinements. Visual Computer, 15:279--301, 1999.

[4]

J. D. Cohen, M. C. Lin, D. Manocha, and M. Ponamgi. I-collide: an interactive and exact collision detection system for large-scale environments. In Proc. of the symposium on Interactive 3D graphics, pages 189--ff., 1995.

Digital Library

[5]

S. Cotin, P. Neumann, X. Wu, S. Fonteneau, P. Bensoussan, J. Dequidt, D. Marchal, L. Grisoni, and S. Karpf. Collaborative development of an open framework for medical simulation. In MICCAI Open-Source Workshop, 2005.

[6]

S. Curtis, R. Tamstorf, and D. Manocha. Fast collision detection for deformable models using representative-triangles. In Proc. of the symposium on Interactive 3D graphics and games, pages 61--69. ACM, 2008.

Digital Library

[7]

H. Edelsbrunner and L. Guibas. Topologically sweeping an arrangement. In Proc. of the 18th ACM Symposium on the Theory of Computing (Berkeley), pages 389--403, 1986.

Digital Library

[8]

M. Gangnet, J.-C. Hervé, T. Pudet, and J.-M. V. Thong. Incremental computation of planar maps. In Proc. of ACM-SIGGRAPH Conf. on Computer Graphics, volume 23, pages 345--354, 1989.

Digital Library

[9]

B. Geiger. Real-time collision detection and response for complex environments. In Proc. of the International Conference on Computer Graphics, pages 105--113. IEEE Computer Society, 2000.

Digital Library

[10]

E. Gilbert, D. Johnson, and S. Keerthi. A fast procedure for computing the distance between complex objects in three-dimensional space. IEEE Journal of Robotics and Automation, 4(2):193--203, 1988.

[11]

S. Gottschalk, M. C. Lin, and D. Manocha. Obbtree: a hierarchical structure for rapid interference detection. In Proc. of the 23rd annual conference on Computer graphics and interactive techniques, pages 171--180, 1996.

Digital Library

[12]

N. K. Govindaraju, D. Knott, N. Jain, I. Kabul, R. Tamstorf, R. Gayle, M. C. Lin, and D. Manocha. Interactive collision detection between deformable models using chromatic decomposition. ACM Trans. Graph., 24(3):991--999, 2005.

Digital Library

[13]

S. Guy and G. Debunne. Monte-carlo collision detection. Technical Report RR-5136, INRIA, 2004.

[14]

M. Held, J. T. Klosowski, and J. S. B. Mitchell. Evaluation of collision detection methods for virtual reality fly-throughs. In In Canadian Conference on Computational Geometry, pages 205--210, 1995.

[15]

P. M. Hubbard. Collision detection for interactive graphics applications. IEEE Trans. on Visualization and Computer Graphics, 1(3):218--230, 1995.

Digital Library

[16]

H. Jang and J. Han. Fast collision detection using the a-buffer. Vis. Comput., 24(7):659--667, 2008.

Digital Library

[17]

P. Jiménez, F. Thomas, and C. Torras. 3D Collision Detection: A Survey. Computers and Graphics, 25(2):269--285, 2001.

[18]

L. Joussemet, A. Crosnier, and C. Andriot. Espions: A novel algorithm based on evolution strategy for fast collision detection. In EuroHaptics, pages 159--167, 2006.

[19]

J. T. Klosowski, M. Held, J. S. Mitchell, H. Sowizral, and K. Zikan. Efficient collision detection using bounding volume hierarchies of k-DOPs. IEEE Transactions on Visualization and Computer Graphics, 4(1):21--36, 1998.

Digital Library

[20]

P. Kraemer, D. Cazier, and D. Bechmann. Extension of half-edges for the representation of multiresolution subdivision surfaces. The Visual Computer, 25(2):149--163, 2009.

Digital Library

[21]

J. Lenoir, S. Cotin, C. Duriez, and P. F. Neumann. Interactive physically-based simulation of catheter and guidewire. Computers&Graphics, 30(3):416--422, 2006.

Digital Library

[22]

P. Lienhardt. Topological models for boundary representation: a comparison with n-dimensional generalized maps. Comput. Aided Des., 23(1):59--82, 1991.

Digital Library

[23]

M. Lin and J. Canny. A fast algorithm for incremental distance calculation. Proc. of the IEEE International Conference on Robotics and Automation Proceedings, 2:1008--1014, 1991.

[24]

M. C. Lin and D. Manocha. Handbook of Discrete and Computational Geometry, chapter 35 - Collision and proximity queries. CRC Press, 2004.

[25]

A. Lindblad and G. Turkiyyah. A physically-based framework for real-time haptic cutting and interaction with 3d continuum models. In Proc. of the ACM symposium on Solid and physical modeling, pages 421--429, 2007.

Digital Library

[26]

M. Müller, B. Heidelberger, M. Teschner, and M. Gross. Meshless deformations based on shape matching. ACM Trans. Graph., 24(3):471--478, 2005.

Digital Library

[27]

M. A. Otaduy and M. C. Lin. Clods: dual hierarchies for multiresolution collision detection. In Proc. of the Eurographics/ACM SIGGRAPH symposium on Geometry processing, pages 94--101, 2003.

Digital Library

[28]

M. Teschner, B. Heidelberger, M. Müller, D. Pomeranerts, and M. Gross. Optimized spatial hashing for collision detection of deformable objects. In Vision, Modeling, Visualization, pages 47--54, 2003.

[29]

M. Teschner, S. Kimmerle, G. Zachmann, B. Heidelberger, L. Raghupathi, A. Fuhrmann, M.-P. Cani, F. Faure, N. Magnetat-Thalmann, and W. Strasser. Collision detection for deformable objects. In Eurographics State-of-the-Art Report, pages 119--139, 2004.

[30]

G. van den Bergen. Efficient collision detection of complex deformable models using aabb trees. J. Graph. Tools, 2(4):1--13, 1997.

Digital Library

[31]

I. Wald, W. R. Mark, J. Günther, S. Boulos, T. Ize, W. Hunt, S. G. Parker, and P. Shirley. State of the art in ray tracing animated scenes. In Eurographics State-of-the-Art Report, pages 89--116, 2007.

Cited By

Jund TKraemer PCazier D(2018)A unified structure for crowd simulationComputer Animation and Virtual Worlds10.1002/cav.144923:3-4(311-320)Online publication date: 21-Dec-2018
https://dl.acm.org/doi/10.1002/cav.1449
Čejka JSpagnuolo MĎurikovič R(2016)Evaluation of continuous collision detection accelerated with tetrahedral structuresProceedings of the 32nd Spring Conference on Computer Graphics10.1145/2948628.2948639(17-23)Online publication date: 27-Apr-2016
https://dl.acm.org/doi/10.1145/2948628.2948639
Rumman NSchaerf MBechmann D(2015)Collision detection for articulated deformable charactersProceedings of the 8th ACM SIGGRAPH Conference on Motion in Games10.1145/2822013.2822034(215-220)Online publication date: 16-Nov-2015
https://dl.acm.org/doi/10.1145/2822013.2822034
Show More Cited By

Recommendations

Continuous Self-Collision Detection for Deformable Surfaces Interacting with Solid Models

In this paper, we propose a new continuous self-collision detection CSCD method for a deformable surface that interacts with a simple solid model. The method is developed based on the radial-view-based culling method. Our method is suitable for the ...
Efficient collision detection for example-based deformable bodies
MIG '17: Proceedings of the 10th International Conference on Motion in Games

We introduce a new collision proxy for example-based deformable bodies. Specifically, we approximate the deforming geometry as a union of spheres. During pre-computation we perform a sphere packing on the input, undeformed geometry. Then, for each ...
Image-Based Collision Detection for Deformable Cloth Models

Modeling the natural interaction of cloth and garments with objects in a 3D environment is currently one of the most computationally demanding tasks. These highly deformable materials are subject to a very large number of contact points in the proximity ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

SPM '09: 2009 SIAM/ACM Joint Conference on Geometric and Physical Modeling

October 2009

380 pages

ISBN:9781605587110

DOI:10.1145/1629255

Conference Chair:
Wim Bronsvoort
Delft University of Technology, The Netherlands
,
General Chairs:
Daniel Gonsor
The Boeing Company
,
William Regli
Drexel University
,
Thomas Grandine
The Boeing Company
,
Jan Vandenbrande
The Boeing Company
,
Program Chairs:
Jens Gravesen
Technical University of Denmark, Denmark
,
John Keyser
Texas A&M University

Copyright © 2009 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

SIAM Activity Group on Geometric Design

In-Cooperation

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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 October 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Conference

SIAM '09

Sponsor:

SIAM '09: 2009 SIAM/ACM Joint Conference on Geometric and Physical Modeling

October 5 - 8, 2009

California, San Francisco

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
290
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)1

Reflects downloads up to 20 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Jund TKraemer PCazier D(2018)A unified structure for crowd simulationComputer Animation and Virtual Worlds10.1002/cav.144923:3-4(311-320)Online publication date: 21-Dec-2018
https://dl.acm.org/doi/10.1002/cav.1449
Čejka JSpagnuolo MĎurikovič R(2016)Evaluation of continuous collision detection accelerated with tetrahedral structuresProceedings of the 32nd Spring Conference on Computer Graphics10.1145/2948628.2948639(17-23)Online publication date: 27-Apr-2016
https://dl.acm.org/doi/10.1145/2948628.2948639
Rumman NSchaerf MBechmann D(2015)Collision detection for articulated deformable charactersProceedings of the 8th ACM SIGGRAPH Conference on Motion in Games10.1145/2822013.2822034(215-220)Online publication date: 16-Nov-2015
https://dl.acm.org/doi/10.1145/2822013.2822034
Pitiot TCazier DJund THabibi AKraemer P(2014)Deformable polygonal agents in crowd simulationComputer Animation and Virtual Worlds10.1002/cav.158125:3-4(343-352)Online publication date: 1-May-2014
https://dl.acm.org/doi/10.1002/cav.1581

View Options

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents