Writing Mathlets III: A Call to Math Professionals - The Problems with Sorting

Tom Leathrum
Adding 40,000 steps for sorting the facets to 16,000 operations for computing center-point projections still does not exceed 100,000 total steps at each change of the view vector during a graph rotation. For the typical case of only slightly perturbed lists of facets, it will in fact be less than 50,000 steps at each change. Keeping the rotations visually smooth could require hundreds of such changes in the view vector during the mouse motion, but usually the applet keeps up with the calculations pretty well. However, the sorting procedure has some problems.

First Problem: The applet here displays, in outline, two transparent triangles in three dimensions, planar but not coplanar, one red and one blue. For each triangle, a green line segment connects the center point (centroid) of the triangle to a black arrow. (You will need to rotate the graph, by clicking and dragging with the mouse, to see the black arrow.) The buttons set the view perspective to standard views: "Front" shows the graph with the view vector parallel to the black arrow. (This is also the initial view when the applet is loaded -- with the black arrow end-on in this view, the line segment forming the shaft of the arrow can't be seen without rotating the graph a bit.) "Side" shows the graph with the view vector rotated 90 degrees from the "Front" view, as if you had clicked and dragged the mouse to the right on the graph. "Top" shows a top view, as if (from the "Front" view) you had clicked and dragged the mouse downward on the graph.

To see the sorting problem shown by this applet, first click the "Front" button. Now click and drag the mouse on the graph, moving the mouse alternately left and right, until you can determine which triangle is closest to you, the viewer, from the "Front" view. Clicking the "Top" button may help you see that the blue triangle is in front. Note also that the arrowhead on the black arrow points directly out from the computer screen in the front view, downward in the top view. Now click the "Side" button, so the arrowhead points to the right. Note which of the green line segments is closest to the arrowhead: the one connecting to the red triangle's center point. This indicates that, from the "Front" view, the center point projection would determine that the red triangle should be drawn in front of the blue triangle. In other words, sorting by center point (centroid) projection gets the sorted order of triangular facets wrong in cases like this.

The Second Problem: The applet here also displays the outlines of two transparent non-coplanar triangles in three dimensions, one red and one blue. In this applet, however, the two triangles intersect -- the line of intersection for the two triangles is shown as a green line segment. Again, the graph can be rotated by clicking and dragging your mouse on the graph. Doing so does not help determine which triangle is in front of the other, though -- indeed, from any view, part of the red triangle will be in front of the blue triangle, and part will be behind. The center point projection technique will draw one triangle opaquely over the other, ignoring the intersection.

The first problem may perhaps be fixed by using a different method of comparing facets for sorting, either some method other than center point projection or some center point other than the centroid. Although I cannot prove it, I suspect that any reasonable center point will be susceptible to the same sort of problem shown in the first applet on this page. The second problem is more fundamental, though: There is no way to determine which of the two triangles is in front of the other, because neither is. No other method of comparing facets for sorting can fix this problem.