@inproceedings{ae85bf2f87254011b1017275c411b646,

title = "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.",

keywords = "Bounding volume hierarchy, Ellipsoid-tree, Shape approximation, Solid models, Volume approximation",

author = "Shengjun Liu and Wang, {Charlie C.L.} and Hui, {Kin Chuen} and Xiaogang Jin and Hanli Zhao",

year = "2007",

month = jul,

doi = "10.1145/1236246.1236289",

language = "English",

isbn = "1595936661",

series = "Proceedings - SPM 2007: ACM Symposium on Solid and Physical Modeling",

publisher = "Association for Computing Machinery",

pages = "303--308",

editor = "Spencer, {Stephen N.}",

booktitle = "SPM '07",

address = "United States",

note = "SPM 2007: ACM Symposium on Solid and Physical Modeling ; Conference date: 04-06-2007 Through 06-06-2007",

}