Power diagram depth sorting.
Paolo Cignoni, Leila De Floriani · 1998
In this paper we propose a new approach to the depth sorting problem. Given a simplicial complex \\Gamma in IE d , our approach is based on the preliminary construction of a convex complex \\Gamma in IE d+1 , whose projection on IE d corresponds to \\Gamma, and on the representation of \\Gamma as a power diagram. This approach exhibits a O(m log m) runtime complexity to sort a simplicial complex with m cells and requires only linear storage. 1 Introduction The problem of sorting a set of objects in space according to their distance from a given viewpoint has been extensively studied in the literature mainly for its important applications in computer graphics. We were interested in this problem because its relevance in volume visualization; another area where the two-dimensional version of this problem arises is visibility computation on terrains [8]. Many techniques exist [3] for the direct visualization of an unstructured volumetric dataset orgainized as a tetrahaedral comple...