COMP 236: Spring 2001

I like to see a tool for visualizing a very specific optimization problem.

The tool does not necessarily perform the optimization (although it might!), but I could use it to gain insights into the problem's geometry which would in turn lead me to an algorithmic solution. Ultimately, the tool could be used to help prototype and debug a new algorithm.

Since '96 I have been thinking about a method for finding the minimal enclosing oriented bounding box for a polytope. "Minimal" can refer to volume, surface area, diagonal, or (I think) any other monotonic function of the three box dimensions. O'Rourke presented an O(n^3) solution for volume minimization in which each O(1) step required application of a Newton-Raphson root finder applied to a high order polynomial (at least order 6) whose coefficients were extremely complex trig functions. His solution is very hard to follow, in spite of his excellent presentation. He told me once that it has never been fully implemented. I am not aware of any other solution, though I haven't looked into the literature since '98 or so. O'Rourke doubts that a solution asymptotically faster than O(n^3) can be found. I think he's probably right.

I'm having trouble getting a handle on the problem, and I need a visualization tool to help me see how the optimization "landscape" is shaped.

Each orientation of the box can be represented by a quaternion. I need the tool to generate and display subsets of quaternions satisfying given relations (relations involving the given polytope and the box, for example). For instance, what is the set of orientations which bring the +Y face of the box into contact with polytope vertex #34? What about the orientations which bring face +Z of the box flush with polytope face #3? What about the orientations which make the +Y AXIS of the box perpendicular to polytope edge #16? I want to be able to type these expressions in, and have the quat sets generated and displayed. I'd like to generate new sets from old sets, using union, difference, and intersection. This will require some kind of notation which I can type and the tool can parse.

It is fairly easy to show that the orientation of the minimal box must satisfy several of the kinds of conditions described above. I have a conjecture that given the right sort of coordinate system, the orientation sets satisfying these various conditions are really fairly simple expressions, and I think an implementable O(n^3) solution could be posed in much simpler terms, using vector spaces, sets, convex hulls, voronoi regions, and quaternions.

For visualization aspects, I envision having two, three, or four windows on screen at a time. One would contain the polytope, and possibly an enclosing box. The others would contain various views of quat sets in orientation space. All these views should be highly interactive.

• I'd like to be able to rotate or pan or zoom any of them (and recenter, easily).
• I'd like to be able to tie the viewpoints of several windows together, so that as I change the view in one box, the views in the others match it (although they contain different geometric data).
• I'd like to be able to click on any element within any of these views and get information about it. For example, clicking on a vertex, edge, or face of the polytope, and get information about its identity or geometry (such as index number, or length, or area).
• Also, clicking on a point representing a quaternion, and get its coordinates in various forms, and the volume of the box at that orientation.
• I'd like to be able to select two quats and have it display the third quat that gets you from the first to the second, as well as print out the angle of that rotation.
• I'd like to be able to click on two adjacent faces of the polytope, and have it tell me the angle at which they meet.
• I'd like to have the tool color code each quat in a set according to the volume of the box at that orientation, and highlight the minimal one.

There are many ways to view orientation space, and I'd like to jump from one to another using the tool. I can think of three, off the top of my head.

1. A 3D plot of the euler angles, and there are 12 sequences of euler angle axes I could choose from. I don't imagine finding this view useful, however.
2. The vector part of a unit quaternion embedded in 3 space. In fact, I would like to be able to choose any three of the four components of a unit quaternion to use as the X,Y, and Z coordinates in a 3D interactive plot.
3. An axis/angle plot: every orientation can be thought of as a simple rotation about some axis, so plot a point at a distance proportional to angle in direction of the rotation axis. Views (2) and (3) are very closely related.

Furthermore, since many of these views will be quite dense with data, I want to be able to place cutting planes through them, and view only the contents of the cut plane. Many of the quat sets will be solid regions or 2D curved surfaces, and looking at slices with arbitrarily placed cut planes will be helpful. I would recommend using OpenGL user clip planes for this, rather than computing the plane slices analytically.

As I said, I've been thinking about this optimization problem for a few years, now. I know that I can't tackle it analytically. But in the past I have had great success with exploratory visualization to gain insights into various problems. A lot of things become simple when you find the right perspective.

If the tool helps us solve the optimization problem, I can imagine someone (whoever wants to take on this monster) getting at least two papers out of it -- one on the solution to the problem, which promises to be more elegant and more general than O'Rourke's, and another on how this tool helped us to arrive at the solution. They would also get some enthusiastic tutoring on quat math and computational geometry, if they want it.

This is a lot of stuff. I would settle for any subset of what I have described above. I think that only a very versatile (and very fast) programmer could do all of it -- graphical display, interaction, computational geometry, scientific computing, parsing a specialized language. Doing it in OpenGL on a PC would be most useful to me. Using GLUT/GLUI would be perfect