You are here

Constructing Mathlets Quickly using LiveGraphics3D - Advanced Two-Dimensional Mathlets

Jonathan Rogness and Martin Kraus

Earlier in the article we described how to simulate two-dimensional graphics with LiveGraphics3D. Now that we've discussed occlusions and intersections, we can discuss some of the more advanced issues with two-dimensional scenes. To illustrate the problems, we will construct the convex hull of five points on the xy-plane. Our basic approach to this problem will be very simple: we just show all triangles defined by all possible triples of points. Since the user should be able to drag all points, their coordinates have to be defined by independent variables. Here is a first try:

Resulting Applet:

Notice that we've used appropriate settings for   and   to make the picture look two-dimensional, but unfortunately this is still not an attractive mathlet. You can drag the red points in the xy-plane and get a rough idea of what their convex hull is, but the overlapping triangles are ugly and obscure the fifth point. There are a few things to be done.

For two-dimensional graphics, the standard "diffuse" lighting of polygons is usually not required. We can disable diffuse lighting by specifying the option  , and specify colors using  .

In the example, all primitives (polygons and points) are in the same plane; therefore, the depth sorting is numerically unstable and occlusions of points and triangles are unpredictable. We solve this problem with two "tricks": First, the z-coordinate of all points are slightly increased such that they are all in front of the triangles and never occluded by them. With the help of multiple z values, you are free to specify an arbitrary occlusion order for two-dimensional primitives. This method should only be used with a large   vector, in order to avoid perspective effects for z values different from 0.

We'll also disable edges of polygons by specifying an empty directive  . This does not avoid the unstable sorting of the overlapping polygons; however, we do not need to care about it any longer since all triangles have exactly the same color.

These changes have been incorporated into the following code.

Resulting Applet:

We can show the actual convex polyline of the convex hull by adding thick lines between all pairs of points in an additional "depth layer" with z coordinates smaller than 0. All lines within the convex hull will be occluded by the triangles, while at least half of the thick lines at the edges of the convex hull are visible. The additional primitives are defined in this list:

    (* This list is inserted in the previous code
    after (or before) the list of polygons *)
    Thickness[0.02], (* Thick lines *)
    RGBColor[0, 0, 0], (* Black lines *)
    Line[{{x0, y0, -0.1}, {x1, y1, -0.1}}],
    Line[{{x0, y0, -0.1}, {x2, y2, -0.1}}],
    Line[{{x0, y0, -0.1}, {x3, y3, -0.1}}],
    Line[{{x0, y0, -0.1}, {x4, y4, -0.1}}],
    Line[{{x1, y1, -0.1}, {x2, y2, -0.1}}],
    Line[{{x1, y1, -0.1}, {x3, y3, -0.1}}],
    Line[{{x1, y1, -0.1}, {x4, y4, -0.1}}],
    Line[{{x2, y2, -0.1}, {x3, y3, -0.1}}],
    Line[{{x2, y2, -0.1}, {x4, y4, -0.1}}],
    Line[{{x3, y3, -0.1}, {x4, y4, -0.1}}]

A nice effect can be accomplished by additionally coloring the triangles white with the help of the directive  , i.e., making them indistinguishable from the background.

Resulting Applet:

This completes the example. It should be noted that we haven't actually constructed a convex hull but rather used a trick to display it. A more "constructive" way of approaching this problem would be to check for each line between two points whether all other points are on the same side of it. Here is an example for the line between  and  :

        If[Sign[x1 y0 - x2 y0 - x0 y1 + x2 y1 + x0 y2 - x1 y2] ==
        Sign[x1 y0 - x3 y0 - x0 y1 + x3 y1 + x0 y3 - x1 y3] &&
        Sign[x1 y0 - x3 y0 - x0 y1 + x3 y1 + x0 y3 - x1 y3] ==
        Sign[x1 y0 - x4 y0 - x0 y1 + x4 y1 + x0 y4 - x1 y4],
        Line[{{x0, y0, 0}, {x1, y1, 0}}],
    (* Analogously for all other pairs of points. *)

In general this approach is preferable, among other reasons because it can be adapted for convex hulls in three dimensions. However, it results in rather large expressions, which we wanted to avoid in this introduction.

Jonathan Rogness and Martin Kraus, "Constructing Mathlets Quickly using LiveGraphics3D - Advanced Two-Dimensional Mathlets," Convergence (May 2006)