Top

Published in:

2011 | OriginalPaper | Chapter

10. Inner Sphere Trees and Their Application to Collision Detection

Authors : Rene Weller, Gabriel Zachmann

Published in: Virtual Realities

Publisher: Springer Vienna

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We present a novel geometric data structure for approximate collision detection at haptic rates between rigid objects. Our data structure, which we call inner sphere trees, supports different kinds of queries, namely, proximity queries and the penetration volume, which is related to the water displacement of the overlapping region and, thus, corresponds to a physically motivated force. Moreover, we present a time-critical version of the penetration volume computation that is able to achieve very tight upper and lower bounds within a fixed budget of query time. The main idea is to bound the object from the inside with a bounding volume hierarchy, which can be constructed based on dense sphere packings. In order to build our new hierarchy, we propose to use an AI clustering algorithm, which we extend and adapt here. The results show performance at haptic rates both for proximity and penetration volume queries for models consisting of hundreds of thousands of polygons.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

previous chapter SEE MORE: Improving the Usage of Large Display Environments

next chapter The Value of Constraints for 3D User Interfaces

Please visit cg.in.tu-clausthal.de/research/ist/video to watch some videos of our benchmarks.

Agarwal, P., Guibas, L., Nguyen, A., Russel, D., Zhang, L.: Collision detection for deforming necklaces. Computational Geometry: Theory and Applications 28(2–3), 137–163 (2004)MathSciNetMATHCrossRef

Barbič, J., James, D.L.: Six-dof haptic rendering of contact between geometrically complex reduced deformable models. IEEE Transactions on Haptics 1(1), 39–52 (2008)CrossRef

vanden Bergen, G.: A fast and robust GJK implementation for collision detection of convex objects. Journal of Graphics Tools 4(2), 7–25 (1999)MathSciNetCrossRef

Birgin, E.G., Sobral, F.N.C.: Minimizing the object dimensions in circle and sphere packing problems. Computers & OR 35(7), 2357–2375 (2008). URL http://dx.doi.org/10.1016/j.cor.2006.11.002

Bradshaw, G., O’Sullivan, C.: Adaptive medial-axis approximation for sphere-tree construction. In: ACM Transactions on Graphics, vol. 23(1), pp. 1–26. ACM press (2004). URL http://visinfo.zib.de/EVlib/Show?EVL-2004-1

Cameron, S.: Enhancing GJK: Computing minimum and penetration distances between convex polyhedra. In: Proceedings of International Conference on Robotics and Automation, pp.3112–3117 (1997)

Cottrell, M., Hammer, B., Hasenfuss, A., Villmann, T.: Batch and median neural gas. Neural Networks 19, 762–771 (2006)MATHCrossRef

Faure, F., Barbier, S., Allard, J., Falipou, F.: Image-based collision detection and response between arbitrary volumetric objects. In: ACM Siggraph/Eurographics Symposium on Computer Animation, SCA 2008, July 2008. Dublin, Irlande (2008)

Fisher, S.M., Lin, M.C.: Fast penetration depth estimation for elastic bodies using deformed distance fields (2001)

10.

Gärtner, B.: Fast and robust smallest enclosing balls. In: J.Nesetril (ed.) ESA, Lecture Notes in Computer Science, vol. 1643, pp. 325–338. Springer, Berlin (1999) URL http://link.springer.de/link/service/series/0558/bibs/1643/16%430325.htm

11.

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

12.

Gottschalk, S., Lin, M.C., Manocha, D.: OBBTree: A hierarchical structure for rapid interference detection. Computer Graphics 30(Annual Conference Series), 171–180 (1996)

13.

Hammer, B., Hasenfuss, A., Villmann, T.: Magnification control for batch neural gas. In: ESANN, pp. 7–12 (2006). URL http://www.dice.ucl.ac.be/Proceedings/esann/esannpdf/es2006-8%3.pdf

14.

Hasegawa, S., Sato, M.: Real-time rigid body simulation for haptic interactions based on contact volume of polygonal objects. Computer Graphics Forum 23(3), 529–538 (2004)CrossRef

15.

Hoff, K.E., Zaferakis, A., Lin, M., Manocha, D.: Fast 3d geometric proximity queries between rigid & deformable models using graphics hardware acceleration. Tech. Rep. TR02-004, Department of Computer Science, University of North Carolina – Chapel Hill (2002). URL ftp://ftp.cs.unc.edu/pub/publications/techreports/02-004.pdf. Friday, 8 March 2002 20:06:33 GMT

16.

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

17.

Hudson, T.C., Lin, M.C., Cohen, J., Gottschalk, S., Manocha, D.: V-COLLIDE: Accelerated collision detection for VRML. In: R.Carey, P.Strauss (eds.) VRML 97: Second Symposium on the Virtual Reality Modeling Language. ACM, New York (1997)

18.

Johnson, D.E., Cohen, E.: A framework for efficient minimum distance computations. In: Proceedings of the IEEE International Conference on Robotics and Automation (ICRA-98), pp. 3678–3684. IEEE Computer Society, Piscataway (1998)

19.

Johnson, D.E., Willemsen, P.: Six degree-of-freedom haptic rendering of complex polygonal model. In: HAPTICS, pp. 229–235. IEEE Computer Society (2003). URL http://csdl.computer.org/comp/proceedings/haptics/2003/1890/0%0/18900229abs.htm

20.

Kim, Y.J., Lin, M.C., Manocha, D.: Incremental penetration depth estimation between convex polytopes using dual-space expansion. IEEE Transactions on Visualization and Computer Graphics 10(2), 152–163 (2004). URL http://visinfo.zib.de/EVlib/Show?EVL-2004-24

21.

Kim, Y., Otaduy, M., Lin, M., Manocha, D.: Fast penetration depth computation for physically-based animation. In: S.N. Spencer (ed.) Proceedings of the 2002 ACM SIGGRAPH Symposium on Computer Animation (SCA-02), pp. 23–32. ACM, New York (2002)CrossRef

22.

Kim, Y., Otaduy, M., Lin, M., Manocha, D.: Fast penetration depth estimation using rasterization hardware and hierarchical refinement (short). In: COMPGEOM: Annual ACM Symposium on Computational Geometry (2003)

23.

Klosowski, J.T., Held, M., Mitchell, J.S.B., Sowizral, H., Zikan, K.: Efficient collision detection using bounding volume hierarchies of k-dops. IEEE Transactions on Visualization and Computer Graphics 4(1), 21–36 (1998). DOIhttp://dx.doi.org/10.1109/2945.675649

24.

Larsen, E., Gottschalk, S., Lin, M., Manocha, D.: Fast proximity queries with swept sphere volumes. In: Technical Report TR99-018 (1999)

25.

Martinetz, T.M., Berkovich, S.G., Schulten, K.J.: ‘Neural-gas’ network for vector quantization and its application to time-series prediction. IEEE Transactions on Neural Networks 4(4), 558–569 (1993)CrossRef

26.

McNeely, W.A., Puterbaugh, K.D., Troy, J.J.: Six degrees-of-freedom haptic rendering using voxel sampling. In: A.Rockwood (ed.) Siggraph 1999, Annual Conference Series, pp. 401–408. ACM Siggraph, Addison Wesley Longman, Los Angeles (1999). URL http://visinfo.zib.de/EVlib/Show?EVL-1999-269

27.

Mendoza, C., O’Sullivan, C.: Interruptible collision detection for deformable objects. Computers & Graphics 30(3), 432–438 (2006). URL http://dx.doi.org/10.1016/j.cag.2006.02.018

28.

Morris, D.: Algorithms and data structures for haptic rendering: Curve constraints, distance maps, and data logging. In: Technical Report 2006-06 (2006)

29.

O’Brien, J.F., Hodgins, J.K.: Graphical modeling and animation of brittle fracture. In: SIGGRAPH ’99: Proceedings of the 26th annual conference on Computer graphics and interactive techniques, pp. 137–146. ACM/Addison-Wesley, New York, NY, USA (1999). DOIhttp://doi.acm.org/10.1145/311535.311550

30.

Ong, C., Gilbert, E.: Growth distances: New measures for object separation and penetration. T-RA 12, 888–903 (1996)

31.

Ortega, M., Redon, S., Coquillart, S.: A six degree-of-freedom god-object method for haptic display of rigid bodies with surface properties. IEEE Transactions on Visualization and Computer Graphics 13(3), 458–469 (2007). URL http://dx.doi.org/10.1109/TVCG.2007.1028

32.

Quinlan, S.: Efficient distance computation between non-convex objects. In: Proceedings of International Conference on Robotics and Automation, pp. 3324–3329 (1994)

33.

Redon, S., Lin, M.C.: A fast method for local penetration depth computation. Journal of Graphics Tools 11(2), 37–50 (2006). URL http://jgt.akpeters.com/papers/RedonLin06/

34.

Renz, M., Preusche, C., Pötke, M., peter Kriegel, H., Hirzinger, G.: Stable haptic interaction with virtual environments using an adapted voxmap-pointshell algorithm. In: Proc. Eurohaptics, pp. 149–154 (2001)

35.

Schuermann, A.: On packing spheres into containers (about Kepler’s finite sphere packing problem). In: Documenta Mathematica, vol.11, pp. 393–406 (2006). URL http://arxiv.org/abs/math/0506200

36.

Trenkel, S., Weller, R., Zachmann, G.: A benchmarking suite for static collision detection algorithms. In: V.Skala (ed.) Inter’l Conf. in Central Europe on Computer Graphics, Visualization and Computer Vision (WSCG). Union Agency, Plzen, Czech Republic (2007). URL http://cg.in.tu-clausthal.de/research/colldet_benchmark

37.

Zhang, L., Kim, Y.J., Varadhan, G., Manocha, D.: Generalized penetration depth computation. Computer-Aided Design 39(8), 625–638 (2007). URL http://dx.doi.org/10.1016/j.cad.2007.05.012

Title: Inner Sphere Trees and Their Application to Collision Detection
Authors: Rene Weller
Gabriel Zachmann
Publisher: Springer Vienna
Book: Virtual Realities
Print ISBN: 978-3-211-99177-0

Electronic ISBN: 978-3-211-99178-7

Copyright Year: 2011
DOI: https://doi.org/10.1007/978-3-211-99178-7_10