Computing nice projections of convex polyhedra

Abstract

Projections are important properties of polyhedra and other 3D objects due to its potential application in the field of computer graphics, object reconstruction, machine vision, computational geometry and knot theory. Niceness of projection refers to some structural and geometric properties of the projection. Considerable amount of research work has been done on different criteria of niceness. Some common criteria of niceness includes maximizing (minimizing) the area of projection, maximizing (minimizing) the volume of projection in arbitrary lower dimensions, minimizing the number of crossing in the projection of 3D lines and generating silhouettes which meet some predefined criteria. In this thesis, we have developed algorithms such that the minimum visibility ratio of faces and edges of convex polyhedra is maximized. For a particular view v of a polyhedron P, our algorithm runs in O((ICI +Ivlllog(ICI +Ivll) time, where Ivl is the number of faces visible in v and ICI is the size of the view cone of that view and both Ivl and ICI can be much less than n, where n is the number of vertices of P. For all views of P, our algorithm takes 0(n2Iogn) time. Moreover, we have extended our algorithms to solve this problem for segments in 3D which takes O(nlogn) time.