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.

Tom Leathrum, "Writing Mathlets III: A Call to Math Professionals - Why More Precise Methods are Too Difficult," Convergence (September 2005)

JOMA

Journal of Online Mathematics and its Applications