Dr. Dobb's is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.


Channels ▼
RSS

C/C++

Spinning Purple Larks, Swirling Leaves, Rotating Ellipses


Jan00: C Programming

Al is a DDJ contributing editor. He can be contacted at [email protected].


W e're coming to you again this month from the coal and farm region of central eastern Pennsylvania. We loaded up the Titanic (a.k.a. the RV) and headed north for Judy's 100th high-school reunion. That's right, the 100th. Before you start thinking I have a thing for older women, this is how it happened: Judy's high school, Mahanoy Area Township High School (the "Purple Larks"), marked the 100th anniversary of its first graduating class with a reunion at the Lakeside Ballroom for any Purple Larks who attended the school at any time in the last 100 years and who are, of course, still alive. A thousand-plus Purple Larks attended the reunion representing the classes of '24 through '64 (when they moved the high-school students elsewhere and converted the building to a middle school).

The celebration lasted all day. The Purple Larks visited and renewed old friendships, toured the schoolhouse, bought T-shirts and coffee mugs, dined family style, guzzled libations from a cash bar, and spun around the dance floor to the music of a 15-piece band that recreated the music from the several eras that the many classes represented. There was supposed to be a barbershop quartet, too, but the harmonizing foursome insisted that there would be quiet during their performance. Yeah, right. How are you going to keep a thousand celebrating Purple Larks quiet long enough to get through even one chorus of "Down By The Old Mill Stream"?

Knowing that many of her class members were going to be there, Judy spent a lot of extra time choosing just the right outfit and doing her makeup. Like most reunion alumni, Judy was concerned about how she had stood up against the ravages of time as compared to her classmates. I'd say something sexist like, "It's a girl thing," but there were plenty of bad rugs and hair-dye jobs among the gentlemen Purple Larks, too. Always the gallant husband, and not knowing anyone well enough to busy myself with conversation, I made a lone visual inventory of the chicks at this bash and reported back to Judy that, according to my survey, which was not yet completed, she was, bar none, the prettiest and youngest looking lady there. "How far did you get," she asked? "Up to the class of '43," I answered. "Go finish," she snapped, "and don't come back unless you have good news to report."

Autumn Leaves

Autumn is at its most brilliant in the Ringtown valley. I worried that the drought of '99 would lessen the beauty that we've come to expect of this time of year, but Mother Nature would not allow her summer thirst to compromise her autumn palette. Every narrow mountain road in this region at this time becomes framed in vivid reds, yellows, oranges, golds, purples, blues, and greens, each color in an infinite number of hues, with the sun adding highlights in some places and casting shadows in others. A walk along one of these lanes on a windy day yields an occasional shower of falling leaves that suggest the sense of being caught in a blizzard of color. This magic light and color show lasts but a week or two, and every day is a new experience with new hues and colors as autumn bravely and beautifully fights its annual losing battle with the barren and colorless winter yet to come.

I'll share with you a secret that pilots of small airplanes in the Eastern U.S. know. Take a low-altitude flight through the Appalachian chain -- the Poconos, the Blue Ridge, the Great Smoky Mountains -- when the mountain range is in the full colors of autumn. On any given day, when viewed from the surly bonds of terra firma, the fall colors of the mountain trees all seem to have the same variations. Incredibly beautiful, but mostly all the same. Slip those bonds, take wing, and view the foliage from a few hundred feet up whereupon the autumn colors combine to sharply define the contours of the land itself. This effect occurs because the shape and position of each mountain and its proximity to other mountains determines how much sunlight hits the trees on each side for how long and at what time of day. The trees on each mountainside change color at different times and rates, and the effect is a patchwork of blended colors -- nature's own topographic map extending as far as you can see.

More Graphics Templates

This month continues the development of the graphics template library that I started two months ago. First, some background: The original purpose of the library was to demonstrate the abstraction mechanisms of C++ with a class library that supports drawing basic 2D graphical elements. Using graphics to teach C++ is a natural fit because the problem fits the solution and vice versa. Carrying the concept further leads to a library that teaches how to implement a portable, reusable graphics library by using the abstraction mechanisms of C++.

You can download the graphics template library of this project from DDJ (see "Resource Center," page 5). Each month's version of the library is different from previous ones, reflecting its progress. The library does not maintain upward or downward compatibility between versions of itself and applications that use it because the library is still under development. Instead, I share with you its preliminary and interim versions as the project proceeds, always keeping in mind that the library is foremost a teaching tool and only coincidentally a developer's tool. The public interfaces will and do change as my mind changes about how they should work and as the requirements of the problem evolve. This approach reflects my design philosophy and what I consider to be among the most important guidelines that designers and developers can learn, which is: Every solution to a problem changes the problem.

I'm using the Quincy 99 IDE and the Mingw32 port of the GCC 2.95.1 compiler suite to develop the library and its test applications. You can download these tools by going to http://www.midifitz.com/alstevens/ quincy99/ and reading the directions there. The library is platform independent, however. The library uses templates to parameterize the graphical platform, leaving the graphical rendering as generic as possible and maintaining the appearance of portability. I say "appearance" because I have not tested the library on any operating platform other than Win32, which the Mingw32 compilers support, and I have not compiled the library with any other compiler.

The Ellipse

This month's library adds an ellipse shape to the library implemented as a template class in ellipse.h. An ellipse is a stretched circle. You can think of it as a circle with a horizontal radius and a vertical radius, although it's a little more complex than that. The algorithm for computing the points of the arcs that form an ellipse comes from Michael Abrash's book The Zen of Graphics Programming, which you can find on "Dr. Dobb's Essential Books on Graphics Programming CD-ROM" if you don't already have the book. Michael wrote his ellipse-drawing algorithm in C, and the code is well organized and readily supports a port to a C++ template class, which is what I did. His explanation of the algorithm is classic Abrash -- concise and accurate -- and I won't try to improve on it here. The algorithm does not provide for ellipse shapes that you can rotate, and Abrash deftly defers that discussion. I'll talk more about rotating shapes later in this column and how I've addressed the rotating ellipse problem so far.

An application instantiates an ellipse by providing its center coordinates and the two radius values. The Ellipse template is derived from the Circle template adding the second radius value and an overridden draw function.

The specialize.h file specializes the draw functions for all the shapes when the parameterized graphical platform is a class derived from the TYFCApp class, which I built and use to implement graphical applications under Win32. Whereas the Ellipse template class constructor uses center coordinates and radius values as initializing arguments, the Win32 API Ellipse function uses a pair of x- y- coordinates that define a rectangle within which the ellipse fits. The specialized Ellipse<TYFCApp>::draw() function converts the templates values to the arguments that Win32 needs.

Filling Objects

Filling shapes involves drawing them with a color filling in the insides of the shape from border to border. Not all shapes can be filled. Lines and polylines cannot because they do not form a shape with edges that represent a continuous outside border. Each shape that can be filled has a drawfilled member function.

Filling rectangles that have not been rotated is easy. The Rectangle::drawfilled function simply draws lines the width of the rectangle from the top edge through the bottom edge.

Filling a circle is a bit less simple, though not overly complicated. The Circle::draw function draws the circle if it is not to be filled and computes and stores the circle's points if it is to be filled. Then, if the circle is to be filled, the Circle::draw function calls the Circle::drawfilled function to do the drawing. The drawfilled function sorts the vector of points by the y-coordinate first and then by the x-coordinate so that the points are in order top to bottom and across within that. Then the function uses the sorted vector to draw horizontal lines between each outer vertical edge.

Rotated rectangles and polygons are more complicated, and I went again to Abrash for the solution. A polygon can have many sides going all over the place, and a simple top to bottom scan does not work. You have to organize the polygon by edges and work with them. Once again, Michael does a good job of explaining the algorithm and I urge you to read his book for the details. My port of his algorithm looks a bit simpler because I use standard containers and do not have to do my own sorting. As with a circle, the draw function computes and stores the polygon's points if the polygon is to be filled. The "drawfilled" algorithm builds a vector of the polygon's vertical edges and sorts the vector by y- and x-coordinates. It then iterates the table, drawing lines and changing the organization of the table as it goes along. Michael explains this procedure in detail and I am not sure I can even do an adequate job in the space I have, so please read his explanation if you want to understand it.

When you compare my port of the code with Michael's original, you find that I was able to eliminate one repetitive sort from the procedure. Perhaps this is a function of using standard containers rather than the custom ones that Michael contrives for this purpose, but eliminating an expensive sort from an algorithm provided by "Mr. Optimizer" himself gives one a certain smug sense of accomplishment. I can't really take credit for the discovery, though. Sometimes code hides or reveals facets of itself. By using the C++ language and std::vector for the edge tables, I was able to look at the sort and see that the vector was still in the sequence of the sort from a previous operation. That detail is obscured in Michael's code simply by the fact that it is written in C and uses custom, obfuscated containers to store edges.

Of course, it might turn out that there is some specific kind of weird-shaped polygon that needs the additional sort, one that I have not tested, and so I shall have to swallow my pride, stop gloating, and put the sort back in. I'm sure someone will let me know.

Rotating Objects

This month adds the ability to rotate graphical objects. Each object stores position coordinates, point coordinates, and other values necessary to draw itself. A circle, for example, stores only its position and radius. A line stores its position and end points. A polyline and the things derived from it store position and vertices where the lines connect. In all cases, the point data are relative to the position data.

Rotating an object, in this month's edition, involves storing in the object the desired degrees of rotation. Then, when the draw and drawfilled functions compute points to draw, the program rotates those points the stored number of degrees around an assumed center of 0/0. The drawpoint operation always draws points relative to the object's screen position coordinates, and the points are always stored relative to zero, so this procedure works.

Rotating graphical objects independently, however, does not support the grouping of objects in a hierarchy, which must rotate an object not only independently relative to its own position but also relative to the position of the group in which the object is a member. Given that groups should be able to include other groups, this layered rotation has to be nested multiple levels of a variable number. This requirement has performance implications because its simplest implementation would rotate an object once for itself and once for all the groups up the hierarchy. Solving this problem usually involves implementing affine matrix manipulations, and I'll delay that solution until a later edition.

Rotating Ellipses

Recall that I said that Abrash does not address the rotation of an ellipse. Every ellipse in his approach has two radiuses with either the same x- or the same y-coordinate. Ellipses, therefore, cannot be rotated. To address that problem, I used the rotating algorithm to rotate around the center all the points that the ellipse drawing algorithm computes. This approach almost works. Because the rotating algorithm uses floating-point numbers and std::sin and std::cos functions to compute integer coordinates, sometimes there are rounding errors that cause some points to be computed redundantly and others to be left blank. The visual result is a suggestion of an ellipse with some jagged edges. This image is almost acceptable until you rotate a filled ellipse. The Ellipse class uses the drawfilled function of its base Circle class, described earlier, and an ellipse that has holes in its edges winds up with blank lines when it is filled. I'll try to address that problem in a later edition, but I'm not too worried about it just now. The Win32 Ellipse function does not support rotated ellipses either, with the result that if you include specialize.h, you cannot rotate ellipses.

Moving Objects

Moving (translating) objects is simple because of how they are stored. The program changes their screen position and the draw and drawfilled functions do the rest. Once again, the library needs to consider the implications of moving object groups, and I'll handle that in a later edition.

Hysteria, Paranoia, and Snake Oil

The autumn leaves might be full splendor as I write, but this issue is, according to the date on the cover, the first one of the new millennium (unless you insist that the millennium really begins next year, in which case I refer you to last month's rant on that subject). I'm writing this column in October, 1999, editorial lead times being what they are, and many of you will read these words around the beginning of December, 1999, publishing lead times being what they are. So between us, despite the issue date, we still don't know the full consequences of the Y2K hysteria because it hasn't happened yet. But the clock is ticking. For the past several weeks the tube has been showing one-hour infomercials in a last-ditch effort to feed the national paranoia and worry people into buying products to combat the predicted holocaust of two-digit year failures. They employ vaguely recognizable actors who read from doomsday scripts. The actors are supposed to add credibility to whatever panacea the peddlers are peddling. If there was anything to it, they wouldn't be using such over-the-hill old-timers as Dick Van Patten, Richard Roundtree, and Hugh O'Brian just because they need the work and will work cheap. They'd use contemporary actors with real social consciousness and credibility like Pamela Anderson Lee.

The hype is working, though. Many people refuse to acquire or use software that is not certified bona fide Y2K compliant. Huh? I wrote a small application for jazz piano players and sell it from a web site. It uses MIDI technology to provide real-time bass and drums accompaniment to whatever song you play. Recently I've been getting e-mail from prospective buyers who ask if the program is Y2K compliant. Meaning what? Is there some place I can get my program certified by some industry-acknowledged authority who grants or denies stamps of approval? Are there laws to back up this certification and penalties for claiming compliance when no such compliance has been certified and no such claims authorized? What exactly is a "Y2K compliant" application?

If you wonder why I am skeptical about the sincerity of the Y2K quick-buck, quick-fix hucksters, consider this. Most of the so-called repairs involve finding places in software and databases where the year is represented by two digits and where consequent date miscalculations affect the purposes and functions of the applications. Well then, tell me this: If everyone is all of a sudden so all-fired conscientious about Y2K and its attendant problems, how come all the repairs involve substituting four-digit years for two-digit years? Hello, out there. What happens in Y10K? Are we doomed to repeat the same mistake every 10,000 years? Haven't we learned our lesson?

I don't blame the buyers. They've been intimidated into thinking that something awful is going to happen if they use non-compliant software during the millennium turnover. Except that no one tells them what constitutes compliance or how they can determine that compliance has been achieved, much less certified. So they ask the seller. What is a seller going to say, that the program will not run after December 31? Sorry, but you'll have to use another program after that.

Be assured, my program will run after December 31, 1999. It doesn't care on which day or in which millennium you are playing "Stars Fell On Alabama." (No, I am not predicting that stars will fall on Alabama on January 1, 2000. It's just the name of a song.)

DDJ


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.