Efficient view point selection for silhouettes of convex polyhedra

Silhouettes of polyhedra are 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)) time 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. (C) 2011 Elsevier B.V. All rights reserved.