Ellipsoid-tree construction for solid objects

Shengjun Liu, Charlie C.L. Wang, Kin Chuen Hui, Xiaogang Jin, Hanli Zhao

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review


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.
Original languageEnglish
Title of host publicationSPM '07
Subtitle of host publicationproceedings of the 2007 ACM symposium on Solid and physical modeling
EditorsStephen N. Spencer
Place of PublicationNew York, NY
PublisherAssociation for Computing Machinery
Number of pages6
ISBN (Print)1595936661, 9781595936660
Publication statusPublished - Jul 2007
EventSPM 2007: ACM Symposium on Solid and Physical Modeling - Beijing, China
Duration: 4 Jun 20076 Jun 2007

Publication series

NameProceedings - SPM 2007: ACM Symposium on Solid and Physical Modeling


ConferenceSPM 2007: ACM Symposium on Solid and Physical Modeling


  • Bounding volume hierarchy
  • Ellipsoid-tree
  • Shape approximation
  • Solid models
  • Volume approximation


Dive into the research topics of 'Ellipsoid-tree construction for solid objects'. Together they form a unique fingerprint.

Cite this