Optimal rotation of 3D model for 2D projection

Question

I'm looking for a way to determine the optimal X/Y/Z rotation of a set of vertices for rendering (using the X/Y coordinates, ignoring Z) on a 2D canvas.

I've had a couple of ideas, one being pure brute-force involving performing a 3-dimensional loop ranging from 0..359 (either in steps of 1 or more, depending on results/speed requirements) on the set of vertices, measuring the difference between the min/max on both X/Y axis, storing the highest results/rotation pairs and using the most effective pair.

The second idea would be to determine the two points with the greatest distance between them in Euclidean distance, calculate the angle required to rotate the 'path' between these two points to lay along the X axis (again, we're ignoring the Z axis, so the depth within the result would not matter) and then repeating several times. The problem I can see with this is first by repeating it we may be overriding our previous rotation with a new rotation, and that the original/subsequent rotation may not neccesarily result in the greatest 2D area used. The second issue being if we use a single iteration, then the same problem occurs - the two points furthest apart may not have other poitns aligned along the same 'path', and as such we will probably not get an optimal rotation for a 2D project.

Using the second idea, perhaps using the first say 3 iterations, storing the required rotation angle, and averaging across the 3 would return a more accurate result, as it is taking into account not just a single rotation but the top 3 'pairs'.

Please, rip these ideas apart, give insight of your own. I'm intreaged to see what solutions you all may have, or algorithms unknown to me you may quote.

Answer 1

I would compute the principal axes of inertia, and take the axis vector v with highest corresponding moment. I would then rotate the vertices to align v with the z-axis. Let me know if you want more details about how to go about this.

Intuitively, this finds the axis about which it's hardest to rotate the points, ie, around which the vertices are the most "spread out".

Without a concrete definition of what you consider optimal, it's impossible to say how well this method performs. However, it has a few desirable properties:

• If the vertices are coplanar, this method is optimal in that it will always align that plane with the x-y plane.

• If the vertices are arranged into a rectangular box, the box's shortest dimension gets aligned to the z-axis.

EDIT: Here's more detailed information about how to implement this approach.

First, assign a mass to each vertex. I'll discuss options for how to do this below. Next, compute the center of mass of your set of vertices. Then translate all of your vertices by -1 times the center of mass, so that the new center of mass is now (0,0,0).

Compute the moment of inertia tensor. This is a 3x3 matrix whose entries are given by formulas you can find on Wikipedia. The formulas depend only on the vertex positions and the masses you assigned them.

Now you need to diagonalize the inertia tensor. Since it is symmetric positive-definite, it is possible to do this by finding its eigenvectors and eigenvalues. Unfortunately, numerical algorithms for finding these tend to be complicated; the most direct approach requires finding the roots of a cubic polynomial. However finding the eigenvalues and eigenvectors of a matrix is an extremely common problem and any linear algebra package worth its salt will come with code that can do this for you (for example, the open-source linear algebra package Eigen has SelfAdjointEigenSolver.) You might also be able to find lighter-weight code specialized to the 3x3 case on the Internet.

You now have three eigenvectors and their corresponding eigenvalues. These eigenvalues will be positive. Take the eigenvector corresponding to the largest eigenvalue; this vector points in the direction of your new z-axis.

Now, about the choice of mass. The simplest thing to do is to give all vertices a mass of 1. If all you have is a cloud of points, this is probably a good solution.

You could also set each star's mass to be its real-world mass, if you have access to that data. If you do this, the z-axis you compute will also be the axis about which the star system is (most likely) rotating.

Answer 2

This answer is intended to be valid only for convex polyhedra.

In http://203.208.166.84/masudhasan/cgta_silhouette.pdf you can find "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."

The paper is an in-depth analysis of the properties and algorithms of polyhedra projections. But it is not easy to follow, I should admit.

With that algorithm at hand, your problem is combinatorics: select all sets of possible vertexes, check whether or not exist a projection for each set, and if it does exists, calculate the area of the convex hull of the silhouette.

You did not provide the approx number of vertex. But as always, a combinatorial solution is not recommended for unbounded (aka big) quantities.