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

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.

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.
• 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.
• 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.
• 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.
• 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.
• 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.
• 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.
• 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.
• 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.
• 16: H. Jang and J. Han. Fast collision detection using the a-buffer. Vis. Comput., 24(7):659--667, 2008.
• 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.
• 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.
• 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.
• 22: P. Lienhardt. Topological models for boundary representation: a comparison with n-dimensional generalized maps. Comput. Aided Des., 23(1):59--82, 1991.
• 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.
• 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.
• 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.
• 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.
• 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.