ACM

Communications of the ACM

Home/Magazine Archive/March 2013 (Vol. 56, No. 3)/The Story of the Teapot in DHTML/Full Text

Practice

The Story of the Teapot in DHTML

By Brian Beckman, Erik Meijer
Communications of the ACM, March 2013, Vol. 56 No. 3, Pages 50-55
10.1145/2428556.2428571
Comments

View as: Print Mobile App ACM Digital Library Full Text (PDF) In the Digital Edition Share:

Before there was Scalable Vector Graphics (SVG), Web Graphics Library (WebGL), Canvas, or much of anything for graphics in the browser, it was possible to do quite a lot more than was initially obvious. To demonstrate, we created a JavaScript program that renders polygonal 3D graphics using nothing more than HTML and CSS. Our proof-of-concept is fast enough to support physics-based small-game content, but we started with the iconic 3D "Utah teapot" (Figure 1) as it tells the whole story in one picture. (For background, see http://bit.ly/KQK9a.) It is feasible to render this classic object using just regular <div> elements, CSS styles, and a bit of JavaScript code (Figure 2). This tiny graphics pipeline serves as a timeless demonstration of doing a lot with very little.

The inspiration for this project came from Web developer Jeff Lau, who on his blog UselessPickles implemented a textbook graphics pipeline in handwritten JavaScript (http://www.uselesspickles.com/triangles/) Lau's demo embodies a glorious hack for efficiently rendering triangles in HTML, shown in Figure 3.

The glorious hack is explained later, but, to spoil the punch line, once you have arbitrary triangles, you can easily render arbitrary polygons, and thus arbitrary polygon-based models. The only remaining issues for game-competent 3D graphics are texture mapping, bump mapping, reflection mapping, and performance. These various kinds of mappings all require pixel-based primitives: the ability to render individual pixels efficiently. Though it is possible to render individual pixels using just the <div> element with a CSS style to shrink the element to pixel size, this obviously does not provide sufficient performance for classic scan conversion of 3D models. The work to render individual pixels is quadratic in the linear size of a 2D figure, meaning that doubling the size of a figure requires roughly four times the work.

The <div> elements, however, also begrudgingly provide a way to draw vertical and horizontal lines, if, for no other reason, than for borders around text. Several other bloggers (including David Betz and the late Walter Zorn) noted that by decomposing a figure into parallel "raster lines" instead of pixels, work is linear in the linear size of the figure, meaning that doubling the size only doubles the work. They created JavaScript 2D graphics libraries with reasonable performance by combining pixel drawing where necessary and line drawing where possible in <div>s.

The following is an HTML page that illustrates the linear method by drawing a right triangle of eight vertical raster lines of linearly increasing height:

The CSS style sheet and the inline position and height declarations create eight instances of <div> with linearly increasing left coordinate and linearly increasing height. This HTML page renders as shown in Figure 4.

The linear pattern of coordinate and height values in HTML should be obvious. It should also be obvious how to write a program to generate a similar HTML page that renders not only right triangles with a scheme like this: just arrange the coordinate and dimension values to be linearly increasing or decreasing in appropriate ways. The following program dynamically generates <div> elements exactly as the static markup:

Standard rasterizer algorithms such as Bresenham's permit drawing all kinds of figures. Any programmer who has taken Computer Graphics 101 has seen enough now to create an entire workable 2D graphics library in HTML.

Logarithmic Performance

It is possible to achieve quadratic performance from pixels and linear performance from rasters. Can we do better than linear? Lau found logarithmic performance, meaning that doubling the linear size of a figure requires only a constant amount of more work, usually just one or two more calls to primitives. Logarithmic is much more efficient than linear. The difference is the same as that between binary search and linear search. Lau noticed that <div> + CSS has a subtly hidden primitive right triangle, if you know where to look. Then he presented a beautiful way to decompose an arbitrary triangle into a logarithmic number of right triangles: his glorious hack.

Notice in Figure 5 that HTML allows rendering the four borders of a <div> completely independently by setting the border-XXX colors. Setting the width of the <div> to zero removes the text, leaving just four triangles, as in Figure 6.

Is it possible to get rid of two of the triangles? This is straightforward: make the width of the right (yellow) border zero as in the "animation" in Figure 7, and similarly shrink the bottom (blue) border to make it disappear as well, as in Figure 8; this leaves just a green and a red right triangle.

Now, setting one of the remaining border colors to "transparent" renders a single right triangle at the native efficiency of the underlying browser's rendering engine, presumably very high (Figure 9).

Setting the left and bottom borders' width to zero and making the other appropriate borders transparentstraightforward extensions of Lau's methodproduces HTML primitives for all four kinds of right triangles, as in Figure 10.

Assume at this point a JavaScript function drawRightTriangle(P1, P2, P3) that can render any of these right triangles given the (coordinates of the) three vertices. The details are tedious and unenlightening, but suffice it to say that each of the four branches in the implementation must set the proper attributes of an underlying <div> tag, either directly or through CSS style classes.

Now we have really fast right triangles, but where are the arbitrary triangles with logarithmic performance, where doubling the triangle size means just one or two extra calls to the right-triangle primitive? Lau's original code is iterative in style, but the underlying recursive description is elegant, as follows:

Consider an arbitrary triangle; by definition of a triangle, the three vertices are not all on the same line. There are just two cases to consider: either there is one horizontal leg, or there is not (Figure 11). If there is one horizontal leg, then skip to the next paragraph. If there is not one horizontal leg, then cut the triangle with one horizontal line into two triangles, each with one horizontal leg. Cutting the triangle means computing the coordinates of a new point, P4, as in Figure 12.

The y coordinate of the new point P4 is the same as the y coordinate of the middle-in-y point, P2that is, P4.y == P2.yand the x coordinate of the new point is proportionately as far from the x coordinate of the bottom point as the y coordinate of the new point is from the y coordinate of the bottom point:

The pseudocode, assuming that P1, P2, and P3 are in downward, increasing-y order, is:

There is one final function to write: drawTriangleWithOneHorizontalLeg. Recall that the two kinds of triangles-with-one-horizontal-leg are hanging-down and standing-up. They are completely symmetric, so let us work out the final steps only for the standing-up triangle. There are three possible cases:

The tip is between the two base verticesan acute triangle.
The tip is exactly over one of the two base verticesa right triangle.
The tip is either to the right or the left of the base segmentan obtuse triangle.

If acute, cut the triangle vertically into two right triangles and call it a day! If right, well, it is a right triangle and done! If obtuse, then cut the triangle vertically into one right triangle (done) and one obtuse triangle (recurse on drawTriangle). Beautiful! (See Figure 13.)

To avoid infinite recursion in the third case, you must also stop if a triangle is too smallsay, smaller than one pixel. From this description, all the corner cases are covered and any programmer should be able to write a correct implementation that performs well. When all the recursion has bottomed out, the decomposition of a triangle looks like Figure 14, which is what Lau drew in the first place.

His algorithm decomposes an arbitrary triangle into one or two triangles with horizontal legs; let's call those aligned triangles. It decomposes any acute aligned subtriangle into two aligned right triangles, and it decomposes any aligned obtuse subtriangle into a recursive number of aligned right triangles. Mathematically, this recursive number is infinite. Computationally, because you can render only a finite approximation of the mathematical structure on a screen with a finite pixel size, the number is logarithmic in the size of the figure.

Note the following small improvement: an acute aligned triangle can be rendered directly by setting the border opposite the aligned leg of the <div> to zero width and the borders on either side of the target triangle to transparent color, as in Figure 15.

Also note that it seems impossible to decompose an obtuse aligned triangle into a finite number of acute aligned triangles. Marc Levy provides the following argument sketch: if there were a finite number, then you could find the smallest one by sorting them by size. Consider the smallest one and draw a horizontal cut from its vertex farthest from the base of the original triangle. The residue is a triangle similar to the original triangle, thus leaving a smaller version of the original problem, in which there are even smaller acute aligned triangles. We assumed, however, that we had the smallest one, so that premise must be wrong: there does not exist a smallest one; therefore, there is not a finite number of them.

From a Teapot to Triangles and Back

Now that you know how to draw any triangle anywhere on the screen, how can you get the teapot? First, get some data from the public domain in a well-documented format called OFF (http://segeval.cs.princeton.edu/public/off_format.html) as seen in Table 1.

Use a free graphics tool to decimate the data (trim it down to manageable size) to get the data in Table 2. Then convert the data into JavaScript via editor macros or a simple script. The final ingredients to the graphics pipeline are backface culling, Z-ordering, orientation by quaternions, and a kinematics library for spinning the object. Add a little spring-and-dashpot physics, and you can make your teapot bounce, morph, shatter, and unshatter. Code for all of these examples is available at https://github.com/gousiosg/teapots.

With the right leverage applied at exactly the right fulcrum point, it is relatively easy to do amazing things, such as rendering the classic teapot in HTML and CSS. Or, to paraphrase the Hacker's dictionary, we can extract great pleasure out of stretching the capabilities of programmable systems beyond the original intent of their designers.

Authors

Brian Beckman ([email protected]) is working with Bing on Maps and signals and has held many positions at Microsoft since 1992, from Crypto (SET) to Biztalk to research in functional programming. He wrote the first version of the Time Warp Operating System on the Caltech Hypercube 19841989. He holds a Ph.D. in Astrophysics from Princeton University (1982) and has filed over 80 patents with 30 issued.

Erik Meijer ([email protected]) has been working on "democratizing the cloud" for the past 15 years. He is perhaps best known for his work on the Haskell, C#, and Visual Basic languages, targeting JavaScript as assembly language, and his contributions to LINQ and Rx (Reactive Framework). He is a part-time professor of cloud programming at TUDelft and runs the cloud programmability team at Microsoft.

Figures

Figure 1. The "Utah Teapot" (from "Fast Ray Tracing by Ray Classification," by James Arvo and David Kirk, 1987).

Figure 2. The teapot rendered in HTML, OSS, and JavaScript.

Figure 3. Lau's DHTML demo.

Figure 4. Render of linear method.

Figure 5. HTML border colors.

Figure 6. Triangles in HTML.

Figure 7. Shrinking the first triangle.

Figure 8. Shrinking the second triangle.

Figure 9. Making the third triangle transparent.

Figure 10. HTML primitives for all four kinds of right triangles.

Figure 11. Two types of triangle.

Figure 12. Forcing a horizontal side of the triangle.

Figure 13. Forcing a vertical side of the triangle.

Figure 14. The decomposition of a triangle.

Figure 15. A small improvement.

Tables

Table 1. Original teapot data; 3,751 triangles too much for good dynamic performance.

Table 2. Teapot data after uniform decimation; 263 triangles with great performance.

Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and full citation on the first page. Copyright for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or fee. Request permission to publish from [email protected] or fax (212) 869-0481.

No entries found