|Previous||Table of Contents||Next|
In the previous chapter, we explored the surprisingly intricate process of filling convex polygons. Now were going to fill them an order of magnitude or so faster.
Two thoughts may occur to some of you at this point: Oh, no, hes not going to get into assembly language and device-dependent code, is he? and, Why bother with polygon fillingor, indeed, any drawing primitivesanyway? Isnt that what GUIs and third-party libraries are for?
To which I answer, Well, yes, I am, and, If you have to ask, youve 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, doesnt 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. Ill reserve judgement on whether that is a good thing or not, but Ill 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 anotherand to programs running on other platforms, such as the Macas 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 programmingall programming, for that matterwill 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, its 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 whats 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 its not obvious from the X Window System documentation); if you understood the previous chapters discussion, youre 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 theyre very visible parts of the software you develop. That said, lets learn more about filling convex polygons.
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 well work up polygon-filling code thats fast enough to be truly usable.
Our original polygon filling code involved three major tasks, each performed by a separate function:
The amount of time that the previous chapters 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.
Lets start with drawing, which is easily sped up. The previous chapters code used a double-nested loop that called a draw-pixel function to plot each pixel in the polygon individually. Thats a ridiculous approach in a graphics mode that offers linearly mapped memory, as does VGA mode 13H, the mode in which were 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, thats uniquely suited to filling linear memory buffers. Theres no way to use REP STOS directly in C code, but its 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 cant 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 memorya 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, its sometimes much simpler just to use a little assembly code and be done with it.
|Previous||Table of Contents||Next|