Writing Mathlets III: A Call to Math Professionals

Author(s): 
Tom Leathrum

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.

Published September, 2005
© 2005 by Tom Leathrum

Writing Mathlets III: A Call to Math Professionals - Introduction

Author(s): 
Tom Leathrum

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.

Published September, 2005
© 2005 by Tom Leathrum

Writing Mathlets III: A Call to Math Professionals - The Puzzle

Author(s): 
Tom Leathrum

The applet shown here displays two surfaces in an opaque, faceted form. The surfaces are a hyperbolic paraboloid ( blue), given by the equation = (xy2 )/8, and a circular paraboloid ( red), given by the equation = (xy2)/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.

Writing Mathlets III: A Call to Math Professionals - The Method

Author(s): 
Tom Leathrum
To draw a surface given by f(x,y ) in three dimensions, the applet uses a procedure with these steps:
  • Divide the xy-plane into small triangular regions -- essentially a tiling of the plane with triangles. The triangles should be nonoverlapping, except for shared edges. In the applet, each unit grid square in the xy-plane is divided into four triangles, using the edges of the grid square and the line segments joining each corner of the square to the point at the center of the square.
  • For each vertex (x,y) of a triangle, compute f(x,y). Then the point (x,y,z) in space will be a vertex of the facet directly above the triangle in the xy-plane. In this way, the surface is represented in approximation by a collection of contiguous planar polygonal facets. The vertices of each facet lie on the surface, so smaller facets give better approximations.
  • For each facet, find a center point (a,b,c) -- there are several ways this could be done, and the choice used here will be discussed below.
  • Compute the length of the (linear algebra) projection of the vector from the origin to (a,b,c) onto the view vector. (The view vector is the unit vector perpendicular to the computer's screen -- see the second article in this series for a thorough discussion of view vectors.) Since the view vector is a unit vector, this is just the dot product of the vector (a,b,c) with the view vector.
  • Sort the facets by the value of the length of the projection computed in the preceding step. This should have the effect (and this is where the problems appear) of listing the facets in order from front to back.
  • Draw the facets on the computer screen (projected to two dimensions, as described in the preceding article), opaquely and in order from back to front, so the facets at the front overdraw the facets at the back.
Since the computation of a center point and its projection onto the view vector must be repeated for every facet, it now becomes important to count the facets. With bounds of -10 to 10 on x and y values, and using the procedure of dividing the xy -plane into four triangles for each unit grid square, each surface has 1600 facets. For two surfaces, that comes to a total of 3200 facets. Note that the last three steps above must be repeated every time the graph is rotated even just a little bit, because the view vector changes, so mouse motions would require these steps to be executed many times and rapidly. The two problematic steps are computing a center point for each facet and sorting the facets by the length of the projection. The real question is whether this center-point projection gives an accurate representation of front-to-back ordering for the facets.

Writing Mathlets III: A Call to Math Professionals - Basic Sorting

Author(s): 
Tom Leathrum
My focus in this article is the geometry involved in deciding how to sort facets, but the sorting process itself presents some interesting problems as well. General sorting procedures have been studied extensively in computer science -- see especially Donald Knuth's The Art of Computer Programming, Vol. 2: Sorting and Searching --  and this is not an appropriate place for an extensive comparison of sorting techniques. But there is an interesting and important decision to be made here, so it is worth looking briefly at some of the possible sorting procedures.

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.

Writing Mathlets III: A Call to Math Professionals - Center Points of Facets

Author(s): 
Tom Leathrum
The center point computed for each facet is the centroid of the triangle: For each vertex, draw the line to the midpoint of the opposite side -- these lines are called medians of the triangle. Then the three lines cross at a single point, the centroid of the triangle. The applet here demonstrates this. You can drag the red vertex points of the triangle within the graphing region, and the applet updates the median lines (shown in blue, with the midpoints of sides in yellow ) and centroid ( green) as you drag.

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.

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

Author(s): 
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.

Writing Mathlets III: A Call to Math Professionals - Why More Precise Methods are Too Difficult

Author(s): 
Tom Leathrum

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.

Writing Mathlets III: A Call to Math Professionals - Coming in Future Articles (Maybe)

Author(s): 
Tom Leathrum
I have several ideas in mind for future articles in this series. Here are a few ideas, in no particular order, and with no guarantee that any of these ideas will actually result in a complete article.
  • I have written two applets to present visual aspects of common techniques of integration, Substitution and Integration by Parts. Both use similar techniques for generating the graphs, involving combining functions with derivatives to build parameterizations. This isn't surprising, since both techniques can be viewed as changes of variables. What surprised me in writing the applets was that Integration by Parts didn't require all of the information usually used in a typical integration in order to generate the graph, but the construction is still remarkably similar to that in the Substitution applet.
  • An applet for computing derivatives (symbolically, not numerically) led me to consider some questions about techniques for parsing expressions and about permutations and transformations of the resulting parse trees. This is an interesting problem in the intersection of combinatorics and linguistics.
  • Some discussions with a colleague who writes applets for probability and statistics (see Kyle Seigrist's article, "The Probability/Statistics Object Library," JOMA vol. 4, 2004) have led me to consider the numerical techniques used in common mathematical method libraries to generate "pseudorandom" number sequences. I hope to present some visual applets to show that system developers who design the library calls must be careful about how the pseudorandom number sequence generating technique is constructed, and that applet developers may need to be wary of some pitfalls associated with pseudorandom number sequences.