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 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.
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.
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.
y coordinate of the new point
P4 is the same as the
y coordinate of the middle-in-
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:
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.
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.
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.
Scripting Web Services Prototypes
A Conversation with Ray Ozzie
Mobile Application Development: Web vs. Native
Andre Charland, Brian LeRoux
©2013 ACM 0001-0782/13/03
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 firstname.lastname@example.org or fax (212) 869-0481.
The Digital Library is published by the Association for Computing Machinery. Copyright © 2013 ACM, Inc.
No entries found