Interference-aware geometric modeling

Abstract

While often a requirement for geometric models, there has been little research in resolving the interaction of deforming surfaces during real-time modeling sessions. To address this important topic, we introduce an interference algorithm specifically designed for the domain of geometric modeling. This algorithm is general, easily working within existing modeling paradigms to maintain their important properties. Our algorithm is fast, and is able to maintain interactive rates on complex deforming meshes of over 75K faces, while robustly removing intersections. Lastly, our method is controllable, allowing fine-tuning to meet the specific needs of the user. This includes support for minimum separation between surfaces and control over the relative rigidity of interacting objects.

References

1. Aldrich, G., Pinskiy, D., and Hamann, B. 2011. Collision-driven volumetric deformation on the GPU. Eurographics 2011.
2. Allard, J., Faure, F., Courtecuisse, H., Falipou, F., Duriez, C., and Kry, P. G. 2010. Volume contact constraints at arbitrary resolution. ACM Trans. Graph. 29 (July), 82:1--82:10.
3. Angelidis, A., Cani, M., Wyvill, G., and King, S. 2006. Swirling-sweepers: Constant-volume modeling. Graphical Models 68, 4, 324--332.
4. Au, O. K.-C., Tai, C.-L., Chu, H.-K., Cohen-Or, D., and Lee, T.-Y. 2008. Skeleton extraction by mesh contraction. ACM Trans. Graph. 27 (August), 44:1--44:10.
5. Baraff, D. 1989. Analytical methods for dynamic simulation of non-penetrating rigid bodies. In Proc. SIGGRAPH, 223--232.
6. Baraff, D. 1994. Fast contact force computation for nonpenetrating rigid bodies. In Proc. SIGGRAPH, 23--34.
7. Barbič, J., and James, D. 2008. Six-dof haptic rendering of contact between geometrically complex reduced deformable models. IEEE Transactions on Haptics, 39--52.
8. Botsch, M., and Sorkine, O. 2007. On linear variational surface deformation methods. IEEE Transactions on Visualization and Computer Graphics, 213--230.
9. Botsch, M., Pauly, M., Gross, M., and Kobbelt, L. 2006. Primo: coupled prisms for intuitive surface modeling. In Proceedings of the fourth Eurographics symposium on Geometry processing, Eurographics Association, 11--20.
10. Boyd, S., and Vandenberghe, L. 2004. Convex Optimization. Cambridge University Press, New York, NY, USA.
11. Bridson, R., Fedkiw, R., and Anderson, J. 2002. Robust treatment of collisions, contact and friction for cloth animation. ACM Trans. Graph. 21, 3, 594--603.
12. Catmull, E., and Clark, J. 1978. Recursively generated B-spline surfaces on arbitrary topological meshes. Computer-Aided Design 10, 6, 350--355.
13. Cottle, R., Pang, J., and Stone, R. 1993. The Linear Complementarity Problem. Academic Press, New York, NY.
14. Ericson, C. 2004. Real-Time Collision Detection (The Morgan Kaufmann Series in Interactive 3D Technology). Morgan Kaufmann, December.
15. Faure, F., Barbier, S., Allard, J., and Falipou, F. 2008. Image-based collision detection and response between arbitrary volumetric objects. In ACM Siggraph/Eurographics Symposium on Computer Animation, SCA 2008, July, 2008.
16. Gain, J., and Dodgson, N. 2001. Preventing self-intersection under free-form deformation. IEEE Transactions on Visualization and Computer Graphics, 289--298.
17. Harmon, D., Vouga, E., Tamstorf, R., and Grinspun, E. 2008. Robust treatment of simultaneous collisions. ACM Trans. Graph. 27, 3, 23:1--23:4.
18. Harmon, D., Vouga, E., Smith, B., Tamstorf, R., and Grinspun, E. 2009. Asynchronous contact mechanics. ACM Trans. Graph. 28, 87:1--87:12.
19. Heidelberger, B., Teschner, M., and Gross, M. 2004. Detection of collisions and self-collisions using image-space techniques. Journal of WSCG 12, 3, 145--152.
20. Kaufman, D. M., Edmunds, T., and Pai, D. K. 2005. Fast frictional dynamics for rigid bodies. ACM Trans. Graph. 24, 946--956.
21. Lötstedt, P. 1984. Numerical simulation of time-dependent contact and friction problems in rigid body mechanics. SIAM Journal on Scientific and Statistical Computing 5, 370--384.
22. McNeely, W. A., Puterbaugh, K. D., and Troy, J. J. 1999. Six degree-of-freedom haptic rendering using voxel sampling. SIGGRAPH '99, 401--408.
23. Mirtich, B., and Canny, J. 1995. Impulse-based dynamic simulation. In WAFR: Proceedings of the workshop on Algorithmic foundations of robotics, A. K. Peters, Ltd., Natick, MA, USA, 407--418.
24. Moore, M., and Wilhelms, J. 1988. Collision detection and response for computer animation. ACM, New York, NY, USA, SIGGRAPH '88, 289--298.
25. Provot, X. 1997. Collision and self-collision handling in cloth model dedicated to design garments. In Proc. Computer Animation and Simulation, Springer Verlag, 177--189.
26. Sederberg, T. W., and Parry, S. R. 1986. Free-form deformation of solid geometric models. ACM, New York, NY, USA, SIGGRAPH '86, 151--160.
27. Selle, A., Lentine, M., and Fedkiw, R. 2008. Amass spring model for hair simulation. ACM Trans. Graph. 27, 3, 64--64.
28. Snyder, J. M. 1995. An interactive tool for placing curved surfaces without interpenetration. ACM, New York, NY, USA, SIGGRAPH'95, 209--218.
29. Sorkine, O., and Alexa, M. 2007. As-rigid-as-possible surface modeling. In Proc. Symposium on Geometry Processing, 109--116.
30. Sorkine, O., Cohen-Or, D., Lipman, Y, Alexa, M., Rössl, C., and Seidel, H. 2004. Laplacian surface editing. In Proc. Symposium on Geometry processing, 175--184.
31. Stewart, D., and Trinkle, J. 1996. An implicit time-stepping scheme for rigid body dynamics with inelastic collisions and coulomb friction. Intl. Journal for Numerical Methods in Engineering 39, 2673--2691.
32. Terzopoulos, D., Platt, J., Barr, A., and Fleischer, K. 1987. Elastically deformable models. ACM, New York, NY, USA, SIGGRAPH '87, 205--214.
33. Teschner, M., Heidelberger, B., Müller, M., Pomeranets, D., and Gross, M. 2003. Optimized spatial hashing for collision detection of deformable objects. In Proc. VMV, 47--54.
34. Teschner, M., Kimmerle, S., Zachmann, G., Heidelberger, B., Raghupathi, L., Fuhrmann, A., Cani, M.-P., Faure, F., Magnenat-Thalmann, N., and Strasser, W. 2004. State-of-the-art report: Collision detection for deformable objects. In Proc. Eurographics, 119--139.
35. UNC, 2010. Self-ccd: Continuous collision detection for deforming objects.
36. Von Funck, W., Theisel, H., and Seidel, H. 2006. Vector field based shape deformations. ACM Trans. Graph. 25, 3, 1118--1125.
37. Wriggers, P., and Laursen, T. A. 2007. Computational contact mechanics, vol. 498 of CISM courses and lectures. Springer.

Index Terms

• Computing methodologies

  • Computer graphics

    • Shape modeling

• Theory of computation

  • Randomness, geometry and discrete structures

    • Computational geometry