Ellipsoid-tree construction for solid objects

ABSTRACT

As ellipsoids have been employed in the collision handling of many applications in physical simulation and robotics systems, we present a novel algorithm for generating a bounding volume hierarchy (BVH) from a given model with ellipsoids as primitives. Our algorithm approximates the given model by a hierarchical set of optimized bounding ellipsoids. The ellipsoid-tree is constructed by a top-down splitting. Starting from the root of hierarchy, the volume occupied by a given model is divided into k sub-volumes where each is approximated by a volume bounding ellipsoid. Recursively, each sub-volume is then subdivided into ellipsoids for the next level in the hierarchy. The k ellipsoids at each hierarchy level for a sub-volume bounding is generated by a bottom-up algorithm - simply, the sub-volume is initially approximated by m spheres (m » k), which will be iteratively merged into k volume bounding ellipsoids and globally optimized to minimize the approximation error. Benefited from the anisotropic shape of primitives, the ellipsoid-tree constructed in our approach gives tighter volume bound and higher shape fidelity than another widely used BVH, sphere-tree.

REFERENCES

• 1: Gareth Bradshaw , Carol O'Sullivan, Sphere-tree construction using dynamic medial axis approximation, Proceedings of the 2002 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 21-22, 2002, San Antonio, Texas [doi>10.1145/545261.545267]
• 2: Gareth Bradshaw , Carol O'Sullivan, Adaptive medial-axis approximation for sphere-tree construction, ACM Transactions on Graphics (TOG), v.23 n.1, p.1-26, January 2004 [doi>10.1145/966131.966132]
• 3: Choi, Y.-K., Wang, W., Liu, Y., and Kim, M.-S. 2006. Continuous collision detection for elliptic disks. IEEE Transactions on Robotics 22, 2, 213--224.
• 4: David Cohen-Steiner , Pierre Alliez , Mathieu Desbrun, Variational shape approximation, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 5: 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]
• 6: Philip Martyn Hubbard, Collision detection for interactive graphics applications, Brown University, Providence, RI, 1996
• 7: 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]
• 8: 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
• 9: Larsen, E., Gottschalk, S., Lin, M. C., and Manocha, D. 2000. Fast distance queries with rectangular swept sphere volumes. In Proceedings of IEEE International Conference on Robotics and Automation, IEEE Press, 3719--3726.
• 10: Eric Lengyel, Mathematics for 3D game programming and computer graphics, Charles River Media, Inc., Rockland, MA, 2001
• 11: Lloyd, S. 1982. Least squares quantization in PCM. IEEE Transactions on Information Theory 28, 2, 129--137.
• 12: Palmer, I., and Grimsdale, R. 1995. Collision detection for animation using sphere-trees. Computer Graphics Forum 14, 2, 105--116.
• 13: Quinlan, S. 1994. Efficient distance computation between non-convex object. In Proceedings of IEEE International Conference on Robotics and Automation, IEEE Press, 3324--3329.
• 14: 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
• 15: W. Wang , Y.-K. Choi , B. Chan , M-S. Kim , J. Wang, Efficient collision detection for moving ellipsoids using separating planes, Computing, v.72 n.1-2, p.235-246, April 2004 [doi>10.1007/s00607-003-0060-0]
• 16: Weltz, E. 1991. Smallest enclosing disks (balls and ellipsoids). In New Results and New Trends in Computer Science, Springer-Verlag, H. Maurer, Ed., vol. 555 of Lecture Notes in Compututer Science, 359--370.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Physically based modeling

Keywords:
bounding volume hierarchy, ellipsoid-tree, shape approximation, solid models, volume approximation