Computing nice projections of 2D and 3D scene

Abstract

Computing nice projections of objects in 2D and 3D is a well studied problem in computational geometry. By nice projections we mean optimal projections having some special geometric property. Aside from theoretical interest, its application reaches in the domain of computer graphics, computer vision, object recognition, 3D graph drawing, visualization, robotics, knot theory etc. Considerable amount of research work has been done based on different criteria of niceness. For 3D objects some common criteria of niceness include maximizing (minimizing) the area of projection, minimizing the number of crossing in the projection of 3D lines, minimum overlapping among line segments and vertices, monotonicity of polygonal chains and generating silhouettes which meet some predefined criteria. However, computing orthogonal projections of a set of line segments in 2D and 3D with the following optimality criteria have not been considered so far: (i) sum of the projected length of the line segments in 2D is the minimum and maximum, (ii) sum of the projected area of the triangles in 3D is the minimum and maximum, (iii) sum of the projected length of the line segments in 3D is maximum and minimum. (iv) maximizing (minimizing) the minimum (maximum) ratio between actual length and projected length of line segments in 2D. This thesis addresses these four problems and gives separate algorithms for each.. The underlying concept for Problem(i) and (ii) are similar. Here the idea of McKenna-Seidls algorithm is used by extending the concept of view from convex polyhedra to 2D and 3D scene. We have developed an O(n log n) algorithm for finding an optimal direction in Problem(i) and an O(n2) algorithm for that in Problem(ii). For problem (iii) we give several approximation algorithms. Experimental result shows that our algorithm is within constant factor of the optimum solution. In addition to our main objective on this problem, the above algorithm can be used in a novel application, which is to find the maximum (minimum) perimeter of a convex polyhedron in an orthogonal projection and for which no solution is known. The running time of this algorithm is O(n2). For Problem (iv), we developed an O(nlogn) algorithm to find an optimal solution.