The Virtues of inexpensive approximation

 Journal:   Dr. Dobb's Journal  April 1991 v16 n4 p133(9)
 Title:     The virtues of inexpensive approximation: the Edsun Continuous
            Edge Graphics DAC. (Hardware Review) (Graphics Programming; Edsun
            Laboratories Inc.'s Continuous Edge Graphics Digital-to-Analog
            Converter) (evaluation)
 Author:    Abrash, Michael.

 Summary:   Edsun Laboratories Inc's Continuous Edge Graphics
            Digital-to-Analog Converter (DAC) features support for 8
            bits-per-pixel (bpp) per color gun, compatibility with standard
            VGA DACs, capability to specify a pixel's color and capability for
            information to be embedded in the bitmap.  The Continuous Edge
            Graphics DAC is complex to program and does not give users
            complete control over color, but its attributes are very
            substantial to any graphics programmer.  The combination of the
            DAC with the VGA standard is likely to create its own high-end
            standard for computer graphics.  The only problem with
            implementing the high-end graphics will be software support.
 Company:   Edsun Laboratories Inc. (Products).
 Product:   Edsun Laboratories Continuous Edge Graphics (Digital-to-analog
 Topic:     Tutorial
            Digital to Analog Converters
            VGA Standard
            Computer Graphics.
 Feature:   illustration
 Caption:   VGA data stream. (chart)
            Pixel values. (table)

 Full Text:

 The Virtues of Inexpensive Approximation: The Edsun Continuous Edge Graphics

 A while back, Hal Hardenbergh (of DTACK Grounded, neural net, and Offramp
 fame) was good enough to help me figure out how to draw roundish objects
 rapidly.  Circles were no problem for Hal; neither were ellipses with
 horizontal or vertical major axes.  The sticking point was tilted ellipses.

 The problem wasn't that Hal didn't know how to draw tilted ellipses; the
 problem was drawing them fast.  No matter how he approached the problem, he
 always ended up stuck with one small term that was very expensive (that is,
 slow) to calculate.  And there matters stood for a while.

 One day, Hal called and said, "I can draw tilted ovals very fast.  These are
 not ellipses.  However, they look so much like ellipses that it's hard to
 tell them apart."  Hal had replaced the expensive term with an easily
 calculated but slightly less accurate term.  The resulting ovals were no
 longer mathematically ellipses--but they were sure as heck close.

 Sometimes you really do need genuine ellipses--but not very often.  Computer
 graphics is the art of approximating the ideal in such a way that the eye and
 brain together fill in the gaps, and in that context, a tilted ellipse-like
 oval will almost always serve as well as a true ellipse -- better, if the
 oval can be drawn faster than the ellipse.

 In other words, an inexpensive approximation often beats an expensive ideal.

 Which brings us to the Continuous Edge Graphics Digital-to-Analog Converter
 (CEG/DAC), from Edsun Laboratories.

 The Edsun Continuous Edge DAC

 The CEG/DAC, which may well impact the state of IBM PC graphics every bit as
 much as Super VGA did, is a triumph of inexpensive approximation over
 expensive perfection.  For about $15 added cost (in quantity; projected to
 drop to around $5 within a year), otherwise off-the-shelf VGAs can approach
 and sometimes even surpass 24-bit-per-pixel (bpp) display quality, with
 stunning results.  It is literally impossible to watch Edsun's demo and not
 lust for a CEG/DAC.  The CEG/DAC is being touted as an antialiasing device,
 about which I have my doubts.  (It vastly expands the number of colors
 available in a single VGA frame, but in a sharply limited fashion.  More
 about this later.)  It might be more accurate to call it a dejagging palette
 expansion device, but whatever it is, it works.

 The CEG/DAC is less than ideal in several respects.  It's complex to program,
 it doesn't give you complete color control, and software that takes advantage
 of CEG/DAC features is often slower than normal VGA software at the same
 resolution.  Nonetheless, for good and sufficient reasons which I will
 explain shortly, I think that a year from now the high-end VGA standard will
 be CEG/DAC-plus-Super VGA, much as Super VGA is the standard today.  Once the
 price of the CEG/DAC drops a little, a Super VGA manufacturer would be nuts
 to build an adapter without CEG/DAC, a user would be foolish to buy a Super
 VGA sans CEG/DAC, and a graphics programmer would be right out of his gourd
 not to at least investigate the technology.  Photorealistic CEG/DAC images
 look amazingly better than standard 256 color images; lines look like they
 stepped off the Planet of the Vector Displays (okay, there's a little
 striping, but we're picking very small nits here); polygons blend together
 seamlessly; detail is much easier to pick out; and text looks terrific on the

 To put it simply, CEG/DAC graphics Just Plain Look Great.  And they're cheap.
 Ignore that at your own risk.

 How It Works

 The CEG/DAC combines the following four attributes, none of which seems
 particularly profound:

 * Compatibility with standard VGA DACs

 * Support for 8 bpp per color gun

 * Capability for information to be embedded in the bitmap to reprogram the
 palette on-the-fly

 * Capability for a pixel's color to be specified as a weighting of adjacent
 colors on the same scan line

 Together, these seemingly innocuous features may set the next PC graphics

 VGA DAC Compatibility

 Like any VGA DAC, the CEG/DAC sits at the end of the VGA adapter's pixel
 pipeline, accepting 8-bit pixel attribute values from the VGA chip,
 converting them into red, green, and blue pixel colors, and sending the
 appropriate RGB voltage levels to the monitor.  Until a specific sequence of
 OUTs kicks it into CEG mode, the CEG/DAC performs this pixel conversion just
 like the VGA-standard Inmos DAC; each pixel attribute is used as a look-up
 index in an internal 256-entry palette table, and the looked-up RGB value is
 sent to the monitor.  The CEG/DAC is Inmos-compatible right down to the pins,
 so manufacturers can put CEG/DACs on VGAs without altering board layouts,
 BIOSs, or manufacturing processes.  This, in combination with the relatively
 low price, instantly converts the CEG/DAC from a high-end item with a niche
 market to a mass-market part.  Why?  Because the CEG/DAC is an inexpensive,
 no-fuss way for VGA manufacturers to distinguish and add value to their
 products, a valuable attribute indeed in a market where every VGA is
 beginning to look like every other, and prices are falling through the floor.

 I predict that there will be CEG/DACs on several hundred thousand VGAs within
 a year even if no one ever uses it in CEG mode.  In years past, "1024 X 768"
 sold a lot of Super VGAs, even though the 30Hz interlacing used to reach that
 resolution was capable of frying optic nerves in a matter of minutes.
 Likewise, it's of immense value to manufacturers to be able to use the
 CEG/DAC to claim "740,000 colors" and "2048 X 2048 effective resolution"
 (that is, that CEG/DAC displays at 1024 X 768 are equivalent to normal
 displays at 2048 X 2048, an interesting concept to which we'll return another
 time).  Let's not carry the analogy too far, because the CEG/DAC is far more
 useful than was the 30Hz 1024 X 768 mode; the point is that the actual
 utility of the CEG/DAC is almost superfluous to its widespread use, which
 seems virtually assured.  That, in turn, means that the CEG/DAC should
 quickly reach the critical mass at which it becomes worthwhile for
 mass-market software to support it routinely -- and that's the definition of
 a PC standard in my book.

 The Standard of Comparison:

 24 Bits per Pixel

 In order to understand the importance and limitations of the remaining
 CEG/DAC features, we must first look at the traditional high-end standard for
 color graphics: 24-bpp color selection, yielding 16,777,216 independently
 selectable colors per pixel, enough to convince the eye that it's looking at
 a continuous color spectrum, or at least that portion of the spectrum that a
 CRT can display.  The obvious benefit of 24 bpp is that the colors of the
 primitives that make up graphics displays -- points, lines, polygons, and so
 on -- can be independently selected from a virtually unlimited palette,
 giving the programmer a free hand in color selection.  It's worth noting,
 however, that you'll never need all 16,000,000-plus colors simultaneously;
 there are, after all, fewer than a million pixels even at 1024 X 768
 resolution.  Then, too, primitives are rarely drawn in a random mix of
 colors; typically, each primitive is drawn in a single color or a mix of a
 few colors.  It's likely that at most only a few hundred completely unrelated
 "main" colors will be required for a typical display, although thousands of
 variations on and combinations of those colors may also be required.

 The less obvious benefit of 24 bpp is that it allows for excellent
 antialiasing.  Raster graphics attempts to render an image of essentially
 infinite resolution on a medium of decidedly finite resolution--the computer
 screen.  The generally inadequate pixel-by-pixel rate at which the image is
 sampled onto the screen can result in considerable error (aliasing) in
 rendering the image.  The most notable symptom of aliasing is jagged
 primitive edges.

 Antialiasing is the process of reducing the error of the displayed image
 relative to the original (ideal) image, in any of a number of ways, a topic
 to which we'll return in the future.  For now, what's important to understand
 about antialiasing is that it creates attractive, smooth displays that are
 good representations of ideal images, and that it is generally performed by
 selecting the color of a given pixel as a function of the colors surrounding
 that pixel in the ideal image.  As a very simple example, pixels that fall
 right on the boundary between a white polygon and a black polygon could be
 weighted 50 percent white and 50 percent black, as shown in Figure 1.  While
 the resulting image has the same resolution as if antialiasing had not been
 performed, the eye perceives the gray pixels as blending into the adjacent
 polygons when displayed on the screen, and the edges appear to be smooth.

 There are three points to be made here.  First, 24 bpp is perfect for
 antialiasing because by making all colors available, it allows just the right
 color weighting to be selected for each pixel.  Second, antialiasing does not
 involve selection of random pixel colors, but rather of pixel colors closely
 related to the colors of adjoining pixels.  Antialiasing does not require new
 main colors, but rather variations on the main colors used to draw the
 primitives; there is considerable color coherence between neighboring pixels.
 Third, antialiasing need not be perfect to be useful.  Merely eliminating
 jagged edges is a major step in the direction of visually appealing displays,
 regardless of the mathematical correctness of the procedure by which this is

 24 bpp, though theoretically ideal, suffers from one major shortcoming: It's
 expensive.  It requires both a great deal of memory (2.5 Mbyte for 1024 x 768
 24-bpp), and hardware designed to handle the vast amounts of video data that
 must be pumped out to the screen.  (It's worth noting, though, that
 relatively inexpensive 15 bit-per-pixel VGAs, built around the Tseng Labs
 ET4000 chip, should be available soon.)  Performance also suffers from the
 need to manipulate larger bitmaps, and often from the increased demands that
 scanning all that video data places on memory bandwidth, as well.
 High-resolution adapters tend to be plagued by similar problems.  The CEG/DAC
 doesn't provide either 24 bpp or higher resolution, but neither does it
 require any extra memory or additional hardware, and it places no additional
 demands on memory bandwidth.

 8 bpp per Color Gun

 The standard VGA DAC supports only 6 bpp per color gun, but in CEG mode the
 CEG/DAC provides a full 8 bpp per gun.  This extra color information is,
 however, made available in the normal way, via the 256-entry palette look-up
 table (albeit with 24-bit RGB entries), so this feature alone doesn't
 increase the number of colors available at one time.

 Reprogramming the Palette On-The-Fly

 The CEG/DAC allows information embedded in the bitmap to reprogram the
 palette on-the-fly, a feature Edsun calls EDP, for Edsun Dynamic Palette.
 EDP expands the available color set by allowing the palette to be treated as
 a dynamic resource during the course of a frame; you can, if you want, have a
 completely different palette available for the hundredth scan line than you
 had for the first.  However, EDP is not so useful as it may initially appear
 to be, because in order to reprogram the palette, at least six pixels in a
 row must display the same color, as follows:

 The CEG/DAC normally accepts pixel values from the VGA and looks up the
 corresponding RGB values, just as a standard VGA DAC does.  However, in CEG
 modes, certain pixel values are treated as commands rather than as pixel
 attributes; Table 1 shows the list of commands in Advanced-8 mode (more on
 this shortly).  A portion of the palette is given over to these commands, so
 fewer pixel colors than normal can be selected directly through the palette;
 only 223 main pixel colors are available in Advanced-8 mode, and fewer still
 in other modes.  Nonetheless, the total number of colors available in a
 single frame is vastly increased by the use of command values to derive new
 colors from the main colors and to change the palette on-the-fly.  (The
 command-driven nature of the CEG/DAC is the reason a VGA adapter doesn't have
 to be changed if a CEG/DAC is installed.  The bitmap is laid out in exactly
 the same way as usual; only the interpretation of some of the values in the
 bitmap changes, and the CEG/DAC does that interpretation.  The VGA sends
 pixel values from the bitmap to the DAC just as it always does, without the
 faintest notion of the new meanings of some of the values in CEG mode.)

 When a pixel set to the EDP command value is received by the DAC, the next
 four pixel values are taken to specify the new red, green, and blue values
 for the palette location to load, and the index of that location.  While this
 is going on, the DAC has no new pixel information to display; the data stream
 from the VGA that should have provided the pixel values is instead providing
 the palette load values, as shown in Figure 2.  The CEG/DAC compensates by
 displaying the last known pixel color for the duration of the palette load,
 so each EDP load results in six identical pixels in a row.

 EDP loads can be handled without impacting the displayed image by sacrificing
 a portion of one or both sides of the bitmap to make a solid border; the EDP
 commands can be placed in this part of the bitmap without affecting the
 image, which is displayed in the remaining portion of the bitmap.
 Sacrificing five percent of the bitmap for a left edge border and five
 percent for a right border in 1024 x 768 mode allows 20 palette entries to be
 reprogrammed on every line.  It would certainly be better if EDP commands
 could be executed during normal border time, but the VGA chip doesn't send
 information from the bitmap to the DAC at that time.  A special VGA chip
 could easily be built that would allow more efficient palette loading -- but
 this way the CEG/DAC requires no modification to existing VGAs, and that
 characteristic is key to the success of the CEG/DAC.

 Another way to handle EDP loads is to perform them in bitmap locations where
 there just happen to be at least six pixels in a row of the same color.  This
 is obviously a complex proposition, especially if the screen is constantly
 changing.  Using the CEG/DAC effectively is without a doubt a nontrivial
 programming exercise; the CEG/DAC makes high-quality graphics possible, but
 the bulk of the work in actually realizing such graphics falls on the

 The quick-minded among you will no doubt note that EDP doesn't actually make
 any more colors simultaneously available; they're available in the same
 frame, but you're still limited to 223 main colors at any one time.  True
 enough, but rarely will you need more than 200 main colors on a single scan

 Pixel Weighting

 The basic premise of pixel weighting is simple: Any pixel that's set to a
 pixel-weighting command value is drawn as the specified mix of the colors
 (not the attributes, but the final, looked-up, 24-bit colors) of the nearest
 pixels to the left and right.  (See Table 1.)  If either neighboring pixel is
 also a command rather than a color, the color of the nearest pixel that is a
 color is used.  (Pixel weighting actually follows a more complicated set of
 rules, particularly for line drawing and multipixel weighting sequences, as
 described in Edsun's CEG Level 3 Specification, but conceptually the above
 description will do.)  This allows 32 weightings of colors, ranging in steps
 of 1/31 from 100 percent one color to 100 percent the other; oddly, this does
 not allow weightings of exactly 50-50.  These weightings tend to be well
 suited to smoothing edges and boundaries, as illustrated by Figure 3.
 Similarly, pixel weighting tends to provide useful colors when color
 gradients are drawn.

 Pixel weighting is truly the key to the CEG/DAC.  The advertised 740,000
 colors result from pixel weighting: 742,813 is the exact number, derived as
 each of the 223 main colors mixed in any of 30 ways with the 222 other main
 colors, divided by two because half the combinations are duplicates, plus the
 223 unweighted main colors themselves.  (The number of available colors is
 slightly higher if EDP is disabled, because an additional pixel value is then
 freed up for use as an attribute.  If EDP is enabled, additional colors can
 be made available by loading the palette on-the-fly.)  Pixel weighting
 doesn't actually allow you to select any arbitrary one out of 742,813 colors
 for any given pixel; in fact, you still have a choice of only one of at most
 256 colors for any one pixel.  However, if you can get by with 223 or fewer
 main colors (bearing in mind that EDP can change the main colors), the
 weightings available at any given pixel are useful for smoothing edges or
 shading, so you get a good portion (although by no means all) of the utility
 that 740,000 simultaneous colors would offer.

 Pixel weighting is scarcely a perfect solution.  Many antialiasing algorithms
 consider not only horizontally but also vertically adjacent pixels; pixel
 weighting takes no account of those pixels at all.  In general, points at
 which three or more colors need to be taken into account aren't amenable to
 pixel weighting.  What's more, because pixel weighting is left-to-right
 sequence dependent, it doesn't allow for proper weighting of the leftmost
 pixel on a scan line, and it can't always handle weighting sequences that are
 disrupted by intersecting primitives.  (Edsun has, however, put in special
 cases that allow, for example, a near-vertical single-width line to cross a
 weighting sequence without disrupting the sequence.  See the CEG Level 3
 Specification for details on the special case mix rules, which are fairly

 What pixel weighting amounts to is horizontal color mixing; as such, it
 provides many but not all of the colors needed for ideal antialiasing.  (EDP
 can patch "holes" in the available color set, but only to a limited extent,
 because of the requirement for six consecutive pixels of the same color and
 because it must also be used to change main colors as necessary.)
 Nonetheless, CEG/DAC graphics look good even when mathematically correct
 antialiasing isn't possible; Lord knows, they do expand the color palette and
 get rid of the jaggies.

 Like a stereo with the bass cranked up or an overbright TV, a CEG/DAC image
 can look terrific even if it isn't an ideal representation of the original
 image.  I wouldn't call the CEG/DAC an "antialiasing" device in the classic
 sense, but what it does is useful in its own right; in fact, I expect new
 drawing and rendering approaches to spring up around it.  To quote Foley and
 van Dam, from the Second Edition of Computer Graphics (page 646): "A simple
 or fast algorithm may be used if it produces attractive effects, even if no
 justification can be found in the laws of physics."

 Pixel Weighting Details

 There are actually three distinct CEG modes.  The one described above is
 Advanced-8 mode, available in all 8-bpp modes.  There's also Advanced-4 mode,
 used in 4-bpp display modes, which is similar but offers only seven or eight
 main colors (depending on whether EDP is enabled) and eight weightings.  (See
 Table 2.)  The final mode, Basic-8, also available in 8-bpp modes, is quite
 different.  (See Table 3.)  Instead of requiring that a pixel contain either
 a color attribute or a command, each Basic-8 pixel contains both a 4-bit
 color attribute and a one-of-eight pixel weighting; EDP is not available in
 Basic-8.  The color attribute is mixed with an earlier pixel, possibly but
 not necessarily the preceding pixel.  Because it is simpler and more flexible
 than Advanced-8, Basic-8 is useful for applications that need no more than 16
 main colors.

 Pros and Cons

 It's unquestionably more difficult to program a CEG/DAC bitmap than a normal
 VGA or 24-bpp adapter.  For general drawing with a full set of primitives,
 you must consider the surrounding state of the bitmap as you draw, because
 you may partially overwrite pixel weighting sequences already in the bitmap,
 producing unintended effects.  Such is the cost of sequence-dependent bitmap

 CEG/DAC code also often runs slower than standard VGA code at the same
 resolution, because there's more calculation to be performed for each pixel.
 However, CEG/DAC code is generally faster than equivalent code would be
 running on an adapter with 24 bpp or two to four times the resolution,
 because those approaches require that more bytes of display memory be
 manipulated per pixel or that many more pixels be drawn.  Also, it's not
 necessary that you use pixel weightings and EDP everywhere on the screen; you
 may choose to use only the 223 main colors for most of the screen, and
 reserve CEG drawing for a logo, or for a few special icons.

 On balance, the CEG/DAC involves considerable added software complexity,
 provides slower performance at a given resolution, and doesn't fit standard
 antialiasing, drawing, and rendering models particularly well.  On the other
 hand, it makes wonderful graphics possible, and is faster and much, much
 cheaper than higher-resolution or higher-color displays.  Basically, the
 burden with the CEG/DAC falls entirely on the programmer, who has to deal
 with the complex bitmap and must come up with drawing models suited to this
 odd chip.  As far as the user is concerned, it looks good and costs little--a
 winner across the board.

 And remember, users pay the freight.

 Gamma Correction

 Edsun has built into the CEG/DAC "gamma correction"--the process of
 generating a desired percentage of full brightness when mixing colors--making
 for accurate mixing, and saving programmers a major headache in calculating
 color mixes.  Interestingly, gamma correction plus pixel weighting makes the
 CEG/DAC able to produce useful color components other than the 256 normally
 selectable for each color gun via the palette look-up table.  If a 50-50
 pixel weighting (actually, 16/31 to 15/31, which is as close as the CEG/ DAC
 can come to 50-50 because of the 1/31 pixel weighting step) is specified
 between a pixel with a red color component of 254 and another of 255, a red
 gamma-corrected component with a brightness halfway between the two will be
 sent to the monitor.  In this respect, the CEG/DAC exceeds the
 color-generation capabilities of even 24-bpp adapters.

 How to Develop for the CEG/DAC

 To develop for the CEG/DAC, you'll need a VGA with a CEG/DAC, along with
 Edsun's basic documentation: Edsun Continuous Edge Graphics/ D-to-A
 Converters Data Sheet and Edsun Continuous Edge Graphics Level 3
 Specification.  You'll also want to get Edsun's CEG Software Development Kit
 (SDK), a $250 library of CEG-aware graphics functions--lines, ellipses, CEG
 control, and the like--and sample code.  Applications developed with the SDK
 are royalty-free.  SDK source code is available at no cost if you sign a
 nondisclosure and license agreement that allows you to distribute object code

 The SDK is adequate to get started with CEG programming, but it isn't a
 complete graphics library; for instance, there's no support for clipping.
 Neither is the SDK particularly well optimized for performance; for example,
 a little probing with a debugger revealed that polygons are filled one dot at
 a time via calls to a draw-pixel subroutine.  I found the SDK to be
 functional, but something of a chore to use, partly because the manual was of
 marginal assistance in dealing with the many unfamiliar CEG-specific
 functions; more explanatory and overview material would help greatly.  The
 SDK is a good way to get started with CEG/DAC programming, and will no doubt
 improve with time (like the rest of us, it will take some time for Edsun's
 programmers to master CEG), but right now, don't expect too much from it.
 Personally, I'd get the SDK source code and treat that as no more than a
 starting point.  Clever programmers willing to take the time to understand
 the hardware and program the CEG bitmap directly will surely be able to work
 wonderful tricks with both display quality and performance.

 The SDK comes with some utilities, including several to convert from Targa to
 CEG format and back; image manipulation tools are on the way for the next SDK
 revision.  However, there are currently no tools to let you edit icons or
 prototype screens.  That, I suspect, will change in a hurry; if you're
 looking for an interesting and potentially lucrative project, you could do
 worse than to build a first-rate CEG/DAC image editor.

 Microsoft Windows CEG drivers will be available soon, so for Windows
 applications, the benefits of the CEG/DAC will be automatic with driver


 The CEG/DAC is an odd and complex technology, and it will be some time before
 its full potential is known.  Areas for further research include maximizing
 performance, exploring the possibilities of the CEG/DAC's extremely fine
 color control, and allocating EDP loads in a changing bitmap, which seems to
 me a first-rate optimization problem.

 Given that CEG/DAC programming makes for more attractive lines, edges, text,
 and images at little cost, I think that CEG/DAC-plus-Super VGA is likely to
 set the high-end mass-market standard, at least until XGA arrives in force,
 and possibly longer.  CEG could well be applied to an XGA DAC clone, or, for
 that matter, to 15-bpp VGAs or non-PC systems.  CEG/DAC-plus-Super VGA may
 dominate the market between vanilla VGA and Targa-level adapters until
 low-cost 24-bit-per-pixel graphics become available, a matter of a few years
 at least.

 Is the ascendancy of the CEG/DAC a sure thing?  Hardly.  I do think that
 Super VGA manufacturers will put it into play; they can't afford not to.  The
 problem is software: The chip is unfamiliar, limited in many respects, and
 just plain hard to program.  Still, for all its imperfections, the CEG/DAC
 makes possible some very desirable graphics that were formerly flat-out
 impossible for mass-market software--and that sort of potential doesn't stay
 untapped in the PC arena for very long.

 [BACK] Back

Discuss this article in the forums

Date this article was posted to 7/16/1999
(Note that this date does not necessarily correspond to the date the article was written)

See Also:
Michael Abrash's Articles

© 1999-2011 All rights reserved. Terms of Use Privacy Policy
Comments? Questions? Feedback? Click here!