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.
-----------------------------------------------------------------------------
Descriptors..
Company: Edsun Laboratories Inc. (Products).
Product: Edsun Laboratories Continuous Edge Graphics (Digital-to-analog
converter).
Topic: Tutorial
Digital to Analog Converters
Evaluation
VGA Standard
Computer Graphics.
Feature: illustration
chart
table.
Caption: VGA data stream. (chart)
Pixel values. (table)
-----------------------------------------------------------------------------
Full Text:
The Virtues of Inexpensive Approximation: The Edsun Continuous Edge Graphics
DAC
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
CEG/DAC.
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
standard.
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
done.
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
software.
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
line.
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
complex.)
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
encoding.
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
royalty-free.
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
installation.
Implications
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
See Also: © 1999-2011 Gamedev.net. All rights reserved. Terms of Use Privacy Policy
|