Tom Leathrum is Associate Professor of Mathematics at Jacksonville State University.In this third article in the series, I continue with the intent of encouraging working college math instructors to write their own applets, and to share their results with other developers, by providing mathematical incentives for learning how to write applets. This article continues the theme from the second article, looking at some of the interesting mathematics underlying three-dimensional graphics. The preceding article (see link at left) was about the linear and affine transformations that form the techniques for projecting a three-dimensional image onto the two-dimensional computer screen. Here I build on the terminology from that article (in particular, "view vectors") to consider finer geometrical problems involved in presenting surface graphs.
Tom Leathrum is Associate Professor of Mathematics at Jacksonville State University.In this third article in the series, I continue with the intent of encouraging working college math instructors to write their own applets, and to share their results with other developers, by providing mathematical incentives for learning how to write applets. This article continues the theme from the second article, looking at some of the interesting mathematics underlying three-dimensional graphics. The preceding article (see link at left) was about the linear and affine transformations that form the techniques for projecting a three-dimensional image onto the two-dimensional computer screen. Here I build on the terminology from that article (in particular, "view vectors") to consider finer geometrical problems involved in presenting surface graphs.
The applet shown here displays two surfaces in an opaque, faceted form. The surfaces are a hyperbolic paraboloid ( blue), given by the equation z = (x2 - y2 )/8, and a circular paraboloid ( red), given by the equation z = (x2 + y2)/4 - 5. All three coordinate axes are drawn with bounds -10 to 10.
The graph can be rotated in the applet by clicking and dragging the mouse on the graph. As you rotate the graph, look closely at the intersection of the two surfaces. Most of the problems with this mode of presenting the surfaces appear at or near this intersection. First, the intersection is not very precise -- the edges of the facets give the intersection a polygonal appearance, whereas the actual intersection is a smooth (i.e. differentiable) closed curve in space. Indeed, constructing a parameterization for that curve is a reasonable vector calculus problem. The second apparent problem is that partial facets seem to appear in places where they shouldn't -- corners of facets from one surface seem to poke through the other surface.
The method used to present these surfaces in the applet is a compromise, but a somewhat necessary compromise. If you rotate the graph quickly, you may notice that the rotations seem to stall briefly, and the surfaces may even sometimes appear to "crack." This happens because the browser's applet runtime environment cannot keep up with the rapid updates needed for fast rotations. More precise methods for presenting surfaces are available, but they would have even more trouble keeping up with fast rotations, because the greater precision would make heavier demands on the runtime environment.
So this article's puzzle is about that compromise: how this faceted presentation is accomplished, what problems arise with it, and why it really isn't a good idea to fix the problems. Describing the faceted presentation method and its problems will involve interesting aspects of three-dimensional geometry. The comparison between this method and more precise methods will include just a taste of computational complexity.
The applet on this page shows a direct side-by-side comparison, a sort of "race," with three different sorting algorithms, Merge Sort, Insertion Sort, and Hoare's QuickSort. The list elements are represented as vertical lines of different lengths, from length 1 to length 100. When the applet initially loads, all of the lists are in sorted order, so you see what appear to be solid black triangles. When you click the "Randomize" button, the lists are scrambled pretty thoroughly, and all three methods are given the same scrambled list. When you click the "Start" button, all three methods begin sorting the list. Note here that QuickSort and Merge Sort perform just about equally well, with perhaps just a bit better performance from QuickSort. If you get tired of waiting for Insertion Sort to finish, click the "Stop" button.
The "Clear" button resets the applet to its initial state, with all three lists sorted. Now click the "Perturb" button in the applet. This does not thoroughly scramble the lists, but instead leaves nearly half of the list untouched, and the elements that are moved are generally not moved far in the list. Again, all three methods are given the same unsorted list. Click the "Start" button again. Note now that both QuickSort and Insertion Sort perform well.
The applet counts the numbers of basic operations each method performs when sorting the list: comparisons between two elements and swapping two elements. Actually, Merge Sort doesn't use swap operations as the other two do. It takes two adjacent, previously sorted segments of list and copies them into an external block of memory, merging the two sorted segments into a single sorted segment in the process. Then it copies the newly sorted segment back into the block occupied by the two original segments. So instead of counting the swapping operations, this method counts the operations of putting single elements back into the list, which gives a count consistent with the swap operations in the other methods.
Merge Sort is the algorithm provided in the Java libraries as part of the Java Collections Framework. The decision to provide this as the default sorting procedure is a sound one, since the method is generally efficient and its performance is consistent. However, during mouse rotations of a graph, as in the applet on page 2, the list of facets is generally not randomized, but rather only slightly perturbed, and, as seen on this page, the performance of Merge Sort can easily be beaten by other methods.
The Insertion Sort algorithm is a simple, some would say naïve, method: With a previously sorted initial segment, take the next element in the list, and swap it down into the sorted segment until it is in its appropriate place, then repeat until the entire list is sorted. It has generally poor performance, but it can have some surprisingly good results for lists that are only slightly perturbed, as seen in the applet on this page. In fact, it can sometimes beat Merge Sort.
The QuickSort algorithm is more difficult to explain and understand, and its performance envelope has some potentially bad worst-case scenarios, but its typical performance is at least as good as, and often better than, Merge Sort. Indeed, the problems with QuickSort have more to do with how divisions are chosen for its divide-and-conquer strategy -- if the elements chosen for divisions of the unsorted list wind up consistently too far to one side of the sorted list, the performance suffers -- and even randomly chosen divisions keep good performance. Moreover, as is important for the graph rotations, QuickSort performs well on lists that are only slightly perturbed.
So the graphing applet on page 2 uses the QuickSort algorithm. For the list of 3200 facets, the sorting procedure typically takes no more than about 40,000 steps, significantly less for lists that are only slightly perturbed.
This choice of center point for the triangular facets has several advantages, not least of which is that it is easy to compute. Even in three dimensions, computing the centroid of a triangle (given the coordinates of the vertices) amounts to just computing the coordinatewise average. In the graphing applet on page 2, this coordinatewise average is recomputed and stored each time a new vertex is added to the facet, but then it does not have to be recomputed during mouse rotations, which saves quite a few operations. Recall that the length of the projection onto the unit view vector is just a dot product, requiring three multiplications and two additions, for a total of 5 operations. (These five operations would be the same for any other choice of computed center point.) At 5 operations per facet for 3200 facets, that comes to a total of 16,000 operations.
There are other possible choices for computed center points, such as the orthocenter of the triangle: For each vertex, draw the line perpendicular to the opposite side (the altitudes of the triangle). These three lines cross at a single point called the orthocenter. However, the orthocenter may not even be in the interior of the triangle, for example, if the triangle has an obtuse angle. This could have the effect of putting a facet artificially out of place in the sorted list. Besides, the orthocenter is fiendishly difficult to compute in three dimensions, compared to the centroid.
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.
There are ways to improve the appearance of the graphed surfaces in three dimensions. I will consider two such techniques here and compare them with the basic center-point projection technique described on pages 3-6.
The first approach directly addresses the second problem posed on page 6: When two facets intersect, subdivide the facets along the line of intersection. The resulting polygons may no longer be triangles, but they must still be planar, and they can be further subdivided to get back to triangular facets.
In the graphing applet on page 2, the triangular facets lie over corresponding triangles in the xy-plane, so for each such triangle in the xy-plane, only two facets, one on each surface, need to be checked for intersection. In the more general case of graphing surfaces described parametrically, though, every facet must be checked against every other facet, even facets on the same surface. Just finding the line of intersection is somewhat computationally intensive -- it amounts to finding the solution line for a system of two linear equations in three unknowns. (Think of the linear equations as describing the planes in which the triangular facets lie.) Even in the simplest case, this would involve some 15 or 20 basic arithmetic operations. Multiply this by either 1600 pairs of facets lying over triangles in the xy -plane, or by over a million pairs of facets in the general parametric case. The advantage of this technique is that the subdivisions would need to be computed only once, before the first time the graph is drawn -- subsequent graph displays can be drawn by sorting the new smaller facets. However, this does not address the first problem (Which facet is in front?) at all, and it would cause what many users would perceive as an unreasonable delay in displaying the initial graph.
The most general approach would involve finding the frontmost surface that must be displayed on each screen pixel. In Tom Farmer's article, "Geometric Photo Manipulation " (JOMA vol. 2, 2002), this technique is called the "z -buffer" strategy. For the record, the projection technique I described in my second article in this series is what Farmer calls an orthographic projection -- he gives usable formulas for both orthographic projection and one-point perspective projection.
For each screen pixel in the graph area, imagine a line perpendicular to the screen. That line intersects the surfaces in some relatively small number of points (except in cases extreme enough to be considered degenerate), and moreover these points of intersection can be strictly sorted front to back. A total sort is unnecessary, though -- a linear pass through the points to find the frontmost one will suffice. Then color the screen pixel with the color of that surface at that point.
The problem here is finding the points of intersection. This will depend largely on the complexity of the surface being drawn. Therefore, subdividing the surface into planar polygonal facets may still be a good idea, since a point of intersection between a line and a plane can be computed relatively easily. Even so, you would need to check every facet for whether it intersects the line. This must be repeated for every pixel -- in the my graphing applet, the graph area is 300 by 300 pixels, or 90,000 pixels. Multiply this by 3200 facets and the number of operations needed to find the intersection of a line and a plane, if you do subdivide the surface, or by the number of operations needed to find the intersection of a line with an arbitrary surface, if you don't subdivide. This must also be repeated every time the graph is rotated, even a little bit. If the center-point projection technique has performance problems during the mouse rotations, this technique would be utterly unbearable.
The only way ultimately to solve this problem and get good, accurate graphs of surfaces would be to speed up the runtime environment using native binary code to do the computationally intensive tasks. This is the approach used by the Java3D extensions to the basic Java runtime environment. However, the Java3D extensions are not widely used among typical Web users, and they involve some potentially difficult installation procedures (depending on the platform).
This drawback is at least partially addressed in the JOGL package, which provides Java bindings to the methods in the OpenGL open-source graphics library. OpenGL is widely implemented and even standard on many platforms, so the typical user would not need to install anything new. The problems shift to the developer, who must deal with some nonstandard tools in order to build the JOGL calls into new software. However, there are still some compatibility issues -- some hardware video cards do not have the ability to implement hardware-accelerated forms of some of the more advanced OpenGL calls, and software versions would run into the performance problems just described. Moreover, both the JOGL/OpenGL combination and the Java3D extensions are designed for the more graphics-intensive object rendering of three-dimensional animations, including textures and lighting, far beyond what is needed for a typical surface graph in a mathematics applet.
So in designing applets to graph surfaces in three dimensions, I have decided to compromise: I settle for a less-than-accurate graph in return for reasonable performance in the rotation operations. If you are already familiar with Java, you may be interested in seeing some annotated source code from the faceted surface applet on page 2.