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

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.
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
Pages303-308
Number of pages6
ISBN (Print)1595936661, 9781595936660
DOIs
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

Conference

ConferenceSPM 2007: ACM Symposium on Solid and Physical Modeling
Country/TerritoryChina
CityBeijing
Period4/06/076/06/07

Keywords

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

Fingerprint

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

Cite this