Visible-object determination for interactive visualization

Abstract

A system and method for performing visible object determination based upon a dual search of a cone hierarchy and a bounding (e.g. hull) hierarchy. Visualization software running on a host processor represents space with a hierarchy of cones constructed by recursive refinement, and generates a hierarchy of bounding hulls from a given collection of objects by recursively grouping clusters of objects. Hull nodes in the hull hierarchy reflect cluster membership. Each hull node stores parameters which characterize a bounding hull for the corresponding cluster or object. The visualization software searches the cone and hull hierarchies starting with the root cone and the root hull. Each leaf-cone is assigned a visibility distance value which represents the distance to its closest known object. The visibility distance value of a non-leaf cone is set equal to the maximum of the visibility distance values for its subcone children. Before exploring a given cone-hull pair, a cone-restricted minimum distance between the cone and the hull is measured and compared to the visibility distance value of the cone. Only when the former is smaller than the latter will the cone be searched against the hull. Assuming the search condition is satisfied, subhulls of the given hull are again conditionally explored against the given cone (or its subcones) in ascending order of their cone-hull distances from the cone (or its subcones). When the recursive search of the two trees is completed, visible objects will have been assigned to each leaf-cone.