Previous Table of Contents Next


Chapter 39
Fast Convex Polygons

Filling Polygons in a Hurry

In the previous chapter, we explored the surprisingly intricate process of filling convex polygons. Now we’re going to fill them an order of magnitude or so faster.

Two thoughts may occur to some of you at this point: “Oh, no, he’s not going to get into assembly language and device-dependent code, is he?” and, “Why bother with polygon filling—or, indeed, any drawing primitives—anyway? Isn’t that what GUIs and third-party libraries are for?”

To which I answer, “Well, yes, I am,” and, “If you have to ask, you’ve missed the magic of microcomputer programming.” Actually, both questions ask the same thing, and that is: “Why should I, as a programmer, have any idea how my program actually works?”

Put that way, it sounds a little different, doesn’t it?

GUIs, reusable code, portable code written entirely in high-level languages, and object-oriented programming are all the rage now, and promise to remain so for the foreseeable future. The thrust of this technology is to enhance the software development process by offloading as much responsibility as possible to other programmers, and by writing all remaining code in modular, generic form. This modular code then becomes a black box to be reused endlessly without another thought about what actually lies inside. GUIs also reduce development time by making many interface choices for you. That, in turn, makes it possible to create quickly and reliably programs that will be easy for new users to pick up, so software becomes easier to both produce and learn. This is, without question, a Good Thing.

The “black box” approach does not, however, necessarily cause the software itself to become faster, smaller, or more innovative; quite the opposite, I suspect. I’ll reserve judgement on whether that is a good thing or not, but I’ll make a prediction: In the short run, the aforementioned techniques will lead to noticeably larger, slower programs, as programmers understand less and less of what the key parts of their programs do and rely increasingly on general-purpose code written by other people. (In the long run, programs will be bigger and slower yet, but computers will be so fast and will have so much memory that no one will care.) Over time, PC programs will also come to be more similar to one another—and to programs running on other platforms, such as the Mac—as regards both user interface and performance.

Again, I am not saying that this is bad. It does, however, have major implications for the future nature of PC graphics programming, in ways that will directly affect the means by which many of you earn your livings. Not so very long from now, graphics programming—all programming, for that matter—will become mostly a matter of assembling in various ways components written by other people, and will cease to be the all-inclusively creative, mindbendingly complex pursuit it is today. (Using legally certified black boxes is, by the way, one direction in which the patent lawyers are leading us; legal considerations may be the final nail in the coffin of homegrown code.) For now, though, it’s still within your power, as a PC programmer, to understand and even control every single thing that happens on a computer if you so desire, to realize any vision you may have. Take advantage of this unique window of opportunity to create some magic!

Neither does it hurt to understand what’s involved in drawing, say, a filled polygon, even if you are using a GUI. You will better understand the performance implications of the available GUI functions, and you will be able to fill in any gaps in the functions provided. You may even find that you can outperform the GUI on occasion by doing your own drawing into a system memory bitmap, then copying the result to the screen; for instance, you can do this under Windows by using the WinG library available from Microsoft. You will also be able to understand why various quirks exist, and will be able to put them to good use. For example, the X Window System follows the polygon drawing rules described in the previous chapter (although it’s not obvious from the X Window System documentation); if you understood the previous chapter’s discussion, you’re in good shape to use polygons under X.

In short, even though doing so runs counter to current trends, it helps to understand how things work, especially when they’re very visible parts of the software you develop. That said, let’s learn more about filling convex polygons.

Fast Convex Polygon Filling

In addressing the topic of filling convex polygons in the previous chapter, the implementation we came up with met all of our functional requirements. In particular, it met stringent rules that guaranteed that polygons would never overlap or have gaps at shared edges, an important consideration when building polygon-based images. Unfortunately, the implementation was also slow as molasses. In this chapter we’ll work up polygon-filling code that’s fast enough to be truly usable.

Our original polygon filling code involved three major tasks, each performed by a separate function:

  Tracing each polygon edge to generate a coordinate list (performed by the function ScanEdge);
  Drawing the scanned-out horizontal lines that constitute the filled polygon (DrawHorizontalLineList ); and
  Characterizing the polygon and coordinating the tracing and drawing (FillConvexPolygon ).

The amount of time that the previous chapter’s sample program spent in each of these areas is shown in Table 39.1. As you can see, half the time was spent drawing and the other half was spent tracing the polygon edges (the time spent in FillConvexPolygon was relatively minuscule), so we have our choice of where to begin optimizing.

Fast Drawing

Let’s start with drawing, which is easily sped up. The previous chapter’s code used a double-nested loop that called a draw-pixel function to plot each pixel in the polygon individually. That’s a ridiculous approach in a graphics mode that offers linearly mapped memory, as does VGA mode 13H, the mode in which we’re working. At the very least, we could point a far pointer to the left edge of each polygon scan line, then draw each pixel in that scan line in quick succession, using something along the lines of *ScrPtr++ = FillColor; inside a loop.

However, it seems silly to use a loop when the x86 has an instruction, REP STOS, that’s uniquely suited to filling linear memory buffers. There’s no way to use REP STOS directly in C code, but it’s a good bet that the memset library function uses REP STOS, so you could greatly enhance performance by using memset to draw each scan line of the polygon in a single shot. That, however, is easier said than done. The memset function linked in from the library is tied to the memory model in use; in small (which includes Tiny, Small, or Medium) data models memset accepts only near pointers, so it can’t be used to access screen memory. Consequently, a large (which includes Compact, Large, or Huge) data model must be used to allow memset to draw to display memory—a clear case of the tail wagging the dog. This is an excellent example of why, although it is possible to use C to do virtually anything, it’s sometimes much simpler just to use a little assembly code and be done with it.


Previous Table of Contents Next

Graphics Programming Black Book © 2001 Michael Abrash