Efficient View Point Selection for Silhouettes of Convex Polyhedra

摘要

The silhouette of polyhedra is an important primitive in application areas such as machine vision and computer graphics. In this paper, we study how to select view points of convex polyhedra such that the silhouette satisfies certain properties. Specifically, we give algorithms to find all projections of a convex polyhedron such that a given set of edges, faces and/or vertices appear on the silhouette. We present an algorithm to solve this problem in O(k~2) tune for k edges. For orthogonal projections, we give an improved algorithm that is fully adaptive in the number l of connected components formed by the edges, and has a time complexity of O(k log k + kl). We then generalize this algorithm to edges and/or faces appearing on the silhouette.