Sphere-tree construction using dynamic medial axis approximation

ABSTRACT

Collision handling is very computationally expensive, especially in large scale interactive animations. Hierarchical object representations play an important role in performing efficient collision handling. Many different geometric primitives have been used to construct these representations, which allow areas of interaction to be localised quickly. For time-critical algorithms, such as interruptible collision detection, there are distinct advantages to using hierarchies of spheres, known as sphere-trees. This paper presents a novel algorithm for the construction of sphere-trees. The algorithm presented approximates objects, both convex and non-convex, with a higher degree of fit than existing algorithms. In the lower levels of the representations, there is almost an order of magnitude decrease in the number of spheres required to represent the objects to a given accuracy.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	BLUM, H., AND NAGEL, R. 1978. Shape description using weighted symmetric axis features. Pattern Recognition 10, 167-180.
	2	BOWYER, A. 1981. Computing Dirichlet tessellations. The Computer Journal 24, 2, 162-166.
	3	BRADSHAW, G. 2001. Bounding Volume Hierarchies for Level-of-Detail Collision Handling. PhD thesis, Trinity College Dublin, IRELAND.
	4	CAMERON, S. 1997. Enhancing GJK: Computing minimum penetration distances between convex polyhedra. In Proceedings of the Int. Conf. On Robotics and Automation, 3112-3117.
	5	Jonathan D. Cohen , Ming C. Lin , Dinesh Manocha , Madhav Ponamgi, I-COLLIDE: an interactive and exact collision detection system for large-scale environments, Proceedings of the 1995 symposium on Interactive 3D graphics, p.189-ff., April 09-12, 1995, Monterey, California, United States [doi>10.1145/199404.199437]
	6	DINGLIANA, J., AND O'SULLIVAN, C. 2000. Graceful degradation of collision handling in physically based animation. Computer Graphics Forum, (Proceedings, Eurographics 2000) 19, 3, 239-247.
	7	GILBERT, E., JOHNSON, D., AND KEERTHI, S. 1988. A fast procedure for computing the distance between complex objects in three-dimensional space. IEEE Transactions on Robotics and Automation 4, 2, 193-203.
	8	S. Gottschalk , M. C. Lin , D. Manocha, OBBTree: a hierarchical structure for rapid interference detection, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.171-180, August 1996 [doi>10.1145/237170.237244]
	9	Taosong He, Fast collision detection using QuOSPO trees, Proceedings of the 1999 symposium on Interactive 3D graphics, p.55-62, April 26-29, 1999, Atlanta, Georgia, United States [doi>10.1145/300523.300529]
	10	Philip M. Hubbard, Collision Detection for Interactive Graphics Applications, IEEE Transactions on Visualization and Computer Graphics, v.1 n.3, p.218-230, September 1995 [doi>10.1109/2945.466717]
	11	Philip Martyn Hubbard, Collision detection for interactive graphics applications, Brown University, Providence, RI, 1996
	12	HUBBARD, P. 1995. Real-time collision detection and time-critical computing. In Workshop On Simulation and Interation in Virtual Environments.
	13	Philip M. Hubbard, Approximating polyhedra with spheres for time-critical collision detection, ACM Transactions on Graphics (TOG), v.15 n.3, p.179-210, July 1996 [doi>10.1145/231731.231732]
	14	INAGAKI, H., SUGIHARA, K., AND N. SUGIE. 1992. Numerically robust incremental algorithm for constructing 3D Voronoi diagrams. In Proceedings of the 4th Canadian Conference on Computational Geometry, 334-339.
	15	James T. Klosowski , Martin Held , Joseph S. B. Mitchell , Henry Sowizral , Karel Zikan, Efficient Collision Detection Using Bounding Volume Hierarchies of k-DOPs, IEEE Transactions on Visualization and Computer Graphics, v.4 n.1, p.21-36, January 1998 [doi>10.1109/2945.675649]
	16	KRISHNAN, S., GOPI, M., LIN, M., MANOCHA, D., AND PATTEKAR, A. 1998. Rapid and accurate contact determination between spline models using ShellTrees. In Proceedings of Eurographics '98, vol. 17(3), 315-326.
	17	Shankar Krishnan , Amol Pattekar , Ming C. Lin , Dinesh Manocha, Spherical shell: a higher order bounding volume for fast proximity queries, Proceedings of the third workshop on the algorithmic foundations of robotics on Robotics : the algorithmic perspective: the algorithmic perspective, p.177-190, August 1998, Houston, Texas, United States
	18	LARSEN, E., GOTTSCHALK, S., LIN, M., AND MANOCHA, D. 1999. Fast proximity queries with swept sphere volumes. Tech. Rep. TR99-018, Dept. of Computer Science, University of North Carolina.
	19	LIN, M., AND CANNY, J. 1991. Efficient algorithms for incremental distance computation. In Proc. IEEE Conference on Robotics and Automation, 1008-1014.
	20	Ming Chieh Lin , John F. Canny, Efficient collision detection for animation and robotics, 1993
	21	Brian Mirtich, V-Clip: fast and robust polyhedral collision detection, ACM Transactions on Graphics (TOG), v.17 n.3, p.177-208, July 1998 [doi>10.1145/285857.285860]
	22	O'SULLIVAN, C., AND DINGLIANA, J. 1999. Realtime collision detection and response using sphere-trees. In Proceedings of the Spring Conference on Computer Graphics, 83-92.
	23	PALMER, I., AND GRIMSDALE, R. 1995. Collision detection for animation using sphere-trees. Computer Graphics Forum 14, 2, 105-116.
	24	Madhav K. Ponamgi , Dinesh Manocha , Ming C. Lin, Incremental Algorithms for Collision Detection Between Polygonal Models, IEEE Transactions on Visualization and Computer Graphics, v.3 n.1, p.51-64, January 1997 [doi>10.1109/2945.582346]
	25	QUINLAN, S. 1994. Efficient distance computation between nonconvex objects. In Proceedings International Conference on Robotics and Automation, 3324-3329.
	26	Rich Rabbitz, Fast collision detection of moving convex polyhedra, Graphics gems IV, Academic Press Professional, Inc., San Diego, CA, 1994
	27	Szymon Rusinkiewicz , Marc Levoy, QSplat: a multiresolution point rendering system for large meshes, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.343-352, July 2000 [doi>10.1145/344779.344940]
	28	Szymon Rusinkiewicz , Marc Levoy, Streaming QSplat: a viewer for networked visualization of large, dense models, Proceedings of the 2001 symposium on Interactive 3D graphics, p.63-68, March 2001 [doi>10.1145/364338.364350]
	29	Gino van den Bergen, Efficient collision detection of complex deformable models using AABB trees, Journal of Graphics Tools, v.2 n.4, p.1-13, April 1997
	30	WELTZ, E. 1991. Smallest enclosing disks (balls and ellipsoids). In New Results and New Trends in Computer Science, H. Maurer, Ed. 359-370.
	31	WHITE, D. (www). Smallest Enclosing Ball of Points/Balls. http://vision.ucsd.edu/dwhite/ball.html.
	32	WILSON, A., LARSEN, E., D. MANOCHA, AND LIN, M. 1998. IMMPACT: A system for interactive proximity queries on massive models. Tech. Rep. TR98-031, Dept. of Computer Science, University of North Carolina.