“Adaptive image-based intersection volume” by Wang, Faure and Pai

A method for image-based contact detection and modeling, with guaranteed precision on the intersection volume, is presented. Unlike previous image-based methods, our method optimizes a nonuniform ray sampling resolution and allows precise control of the volume error. By cumulatively projecting all mesh edges into a generalized 2D texture, we construct a novel data structure, the Error Bound Polynomial Image (EBPI), which allows efficient computation of the maximum volume error as a function of ray density. Based on a precision criterion, EBPI pixels are subdivided or clustered. The rays are then cast in the projection direction according to the non-uniform resolution. The EBPI data, combined with ray-surface intersection points and normals, is also used to detect transient edges at surface intersections. This allows us to model intersection volumes at arbitrary resolution, while avoiding the geometric computation of mesh intersections. Moreover, the ray casting acceleration data structures can be reused for the generation of high quality images.

1. 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. Google ScholarDigital Library
2. Baciu, G., and Wong, W. S.-K. 2004. Image-based collision detection for deformable cloth models. IEEE Transactions on Visualization and Computer Graphics 10, 649–663. Google ScholarDigital Library
3. Barbić, J., and James, D. 2007. Time-critical distributed contact for 6-dof haptic rendering of adaptively sampled reduced deformable models. In Proc. ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 171–180. Google ScholarDigital Library
4. Barbić, J., and James, D. L. 2010. Subspace self-collision culling. ACM Trans. Graph. 29 (July), 81:1–81:9. Google ScholarDigital Library
5. Dingliana, J., and O’Sullivan, C. 2000. Graceful degradation of collision handling in physically based animation. Computer Graphics Forum 19, 239–247.Google ScholarCross Ref
6. Dold, C. 2005. Extended gaussian images for the registration of terrestrial scan data. In ISPRS WG III/3, III/4, V/3 Workshop “Laser scanning 2005”.Google Scholar
7. Faure, F., Barbier, S., Allard, J., and Falipou, F. 2008. Image-based collision detection and response between arbitrary volume objects. In Proc. ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 155–162. Google ScholarDigital Library
8. Galoppo, N., Otaduy, M. A., Mecklenburg, P., Gross, M., and Lin, M. C. 2006. Fast simulation of deformable models in contact using dynamic deformation textures. In Proc. ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 73–82. Google ScholarDigital Library
9. Govindaraju, N. K., Knott, D., Jain, N., Kabul, I., Tamstorf, R., Gayle, R., Lin, M. C., and Manocha, D. 2005. Interactive collision detection between deformable models using chromatic decomposition. ACM Trans. Graph. 24 (July), 991–999. Google ScholarDigital Library
10. Hable, J., and Rossignac, J. 2005. Blister: Gpu-based rendering of boolean combinations of free-form triangulated shapes. ACM Trans. Graph. 24 (July), 1024–1031. Google ScholarDigital Library
11. Harmon, D., Panozzo, D., Sorkine, O., and Zorin, D. 2011. Interference-aware geometric modeling. ACM Trans. Graph. 30 (Dec.), 137:1–137:10. Google ScholarDigital Library
12. Heidelberger, B., Teschner, M., Keiser, R., Muller, M., and Gross, M. 2004. Consistent penetration depth estimation for deformable collision response. In Proc. VMV, 339–346.Google Scholar
13. Heidelberger, B., Teschner, M., and Gross, M. 2004. Detection of collisions and self-collisions using image-space techniques. In Proc. WSCG, 145–152.Google Scholar
14. Hermann, E., Faure, F., and Raffin, B. 2008. Ray-traced collision detection for deformable bodies. In 3rd International Conference on Computer Graphics Theory and Applications, 293–299.Google Scholar
15. Horn, B. K. P. 1984. Extended gaussian images. Proc. of the IEEE 72, 1671–1686.Google ScholarCross Ref
16. Je, C., Tang, M., Lee, Y., Lee, M., and Kim, Y. J. 2012. Polydepth: Real-time penetration depth computation using iterative contact-space projection. ACM Trans. Graph. 31, 5:1–5:14. Google ScholarDigital Library
17. Menon, J., Marisa, R. J., and Zagajac, J. 1994. More powerful solid modeling through ray representations. IEEE Comput. Graph. Appl. 14 (May), 22–35. Google ScholarDigital Library
18. NVIDIA. 2007. NVIDIA CUDA Compute Unified Device Architecture Programming Guide. NVIDIA Corporation.Google Scholar
19. Parker, S. G., Bigler, J., Dietrich, A., Friedrich, H., Hoberock, J., Luebke, D., McAllister, D., McGuire, M., Morley, K., Robison, A., and Stich, M. 2010. Optix: a general purpose ray tracing engine. ACM Trans. Graph. 29 (July), 66:1–66:13. Google ScholarDigital Library
20. Press, W. H., Teukolsky, S. A., Vetterling, W. T., and Flannery, B. P. 2007. Numerical Recipes 3rd Edition: The Art of Scientific Computing, 3 ed. Cambridge University Press. Google ScholarDigital Library
21. Ruina, A., Bertram, J. E., and Srinivasan, M. 2005. A collisional model of the energetic cost of support work qualitatively explains leg sequencing in walking and galloping, pseudo-elastic leg behavior in running and the walk-to-run transition. Journal of Theoretical Biology 237 (Nov), 170–192.Google ScholarCross Ref
22. Schvartzman, S. C., Pérez,. G., and Otaduy, M. A. 2010. Star-contours for efficient hierarchical self-collision detection. ACM Trans. Graph. 29 (July), 80:1–80:8. Google ScholarDigital Library
23. Sud, A., Govindaraju, N., Gayle, R., Kabul, I., and Manocha, D. 2006. Fast proximity computation among deformable models using discrete voronoi diagrams. ACM Trans. Graph. 25 (July), 1144–1153. Google ScholarDigital Library
24. Tang, M., Manocha, D., and Tong, R. 2009. Multi-core collision detection between deformable models. In 2009 SIAM/ACM Joint Conference on Geometric and Physical Modeling, 355–360. Google ScholarDigital Library
25. Tang, M., Manocha, D., Lin, J., and Tong, R. 2011. Collision-streams: fast gpu-based collision detection for deformable models. In Symposium on Interactive 3D Graphics and Games, 63–70. Google ScholarDigital Library
26. Teschner, M., Kimmerle, S., Heidelberge, B., Zachmann, G., Raghupathi, L., Fuhrmann, A., Cani, M.-P., Faure, F., Magnenat-Thalmann, N., Strasser, W., and Volino, P. 2004. Collision detection for deformable objects. In Eurographics State-of-the-Art Report, 119–139.Google Scholar