Even though standard line drawing looks good for horizontal, vertical, and 45 degree lines, it's sometimes useful to be able to draw at other angles without having the problem of "jaggies" on the lines. The solution to this problem has been known for at least 500 years—it's called anti-aliasing.

A common misconception is that anti-aliasing is expensive and will slow your critical application down to a crawl. So here's a little routine which shows you how to avoid the speed problem. It's actually only slightly slower than regular line drawing and still lets you have that nice anti-aliased look!

The idea is to use a modification of the Bresenham algorithm, in which the error term is used to compute the relative brightness of two pixels. The parameters that compute the error term are pre-scaled, so they give an index directly into a color table.

The current code is designed for an 8-bit bitmap, but it's a trivial exercise (which I leave to you) to convert it to 32-bit graphics. Note that in this simple implementation, there is not clipping code—so be careful.

Another simplification in the code is that the routine will not blend the color of the line with the existing background. In many cases, this approximation is OK, but you may need to read the old pixel and blend it with the new color before writing it back. If you do that, performance will suffer.

The last parameter of the function (mp) is a pointer to a table of 32 char containing the palette to be used. An example of a palette could be a simple gray ramp:

void    main()
{
    uchar       palette[32];
    BScreen     s;
    rgb_color   c;
    long        entry;

    for (i = 0;i < 32; i++) {
        c.red = i * 8;
        c.green = i * 8;
        c.blue = i * 8;
        entry = s.IndexForColor(c);
        palette[i] = entry;
    }
}

And now the code...

void    anti_fline(BBitmap *b, long x1,long y1,long x2,
                   long y2, uchar *mp)
{
    long    dx,dy;
    long    sy;
    long    rowbyte;
    long    error;
    long    cpt;
    uchar   *base;
    float   k;

    base = (char *)b->Bits();
    //get bitmap base
    rowbyte = b->BytesPerRow();
    //number of byte per row

    dx = x2-x1;
    // delta x
    dy = y2-y1;
    // delta y

    base = base + y1*rowbyte+x1;
    //compute start point address

    if (dx==0 && dy==0) {
    //single pixel case optimisation
        *base = *mp;
        return;
    }



    if (dy<0) {
    //if the line goes up
        sy = -1;
        //step up
        dy = -dy;
        //get dy positive again
        rowbyte = -rowbyte;
        //invert rowbyte to go up
    }
    else
        sy = 1;

    if (dx > 0) {
    //if going right
        if (dx > dy) {
        //select case, is it more horizontal than vertical?
            cpt = x2 - x1;
            //how many pixels do we draw
            k = (31*65536)/(dx);
            //init the error
            dy = (int)(dy*k);
            //scale the dithered variables
            dx = (int)(dx*k);
            error = dx >> 1;
            //init the error at half the delta x

            while(cpt>=0) {
                *base = mp[31 - (error>>16)];
                //write a pixel
                cpt--;
                *(base+rowbyte) = mp[(error>>16)];
                //and its complement one line up or down
                base++;
                //go right one pixel
                error += dy;
                //update the error dither
                if (error >= dx) {
                    base += rowbyte;
                    //go up or down one line if the error is greater than dx
                    error -= dx;
                }
            }
        }
        else {
        //second case, more horizontal than vertical
            cpt = dy;
            //how many pixels to draw
            k = (31*65536)/(dy);

            dy = (int)(dy*k);
            dx = (int)(dx*k);
            //scale and init the dithered variables
            error = dy>>1;

            while(cpt >= 0) {
                *base =  mp[31 - (error>>16)];
                //write a pixel
                cpt--;
                *(base+1) =  mp[(error>>16)];
                //and its complement one to the right
                base += rowbyte;
                //go one line down (or up).
                error += dx;
                //update the error
                if (error >= dy) {
                    base++;
                    //go one right if necessary
                    error -= dy;
                }
            }
        }
    }
    else {
    //basically the same code by going left
        dx = -dx;
        //instead of right
        if (dx > dy) {
            error = dx >> 1;
            //the code could be compacted by using
            cpt = dx;
            //a positive or negative value for the
            k = (31*65536)/(dx);
            //horizontal direction, but there is a
            dy = (int)(dy*k);
            //small performance advantage into writing
            dx = (int)(dx*k);
            //the explicit code.

            while(cpt>=0) {
                *base = mp[31 - (error>>16)];
                cpt--;
                *(base+rowbyte) = mp[(error>>16)];
                base--;
                error += dy;
                if (error >= dx) {
                    base += rowbyte;
                    error -= dx;
                }
            }
        }
        else {
            error = dy>>1;
            cpt = dy;
            k = (31*65536)/(dy);
            dy = (int)(dy*k);
            dx = (int)(dx*k);

            while(cpt >= 0) {
                *base =  mp[31 - (error>>16)];
                cpt--;
                *(base-1) =  mp[(error>>16)];
                base += rowbyte;
                error += dx;
                if (error >= dy) {
                    base--;
                    error -= dy;
                }
            }
        }
    }
}

Working with media and processing it in real time is inherently complicated. That's why the new BeOS Media Kit is complex, and requires greater attention to detail than other BeOS programming. In preparation for next month's Be Developer's Conference (BeDC), we've created a series of convenience and utility classes to make programming Media Kit nodes easier.

In this article I'll give you a sneak preview of one of these utility classes, and show you the direction we're heading in for some of our convenience nodes. Note that while the functionality of these classes will remain fairly consistent, their interface is still a work in progress, and may change in the final release.

A fundamental concept of the Media Kit is that the media being played or manipulated has the notion of time associated with it. The job of a node is to handle this media data at the right time, to make sure the end user sees the correct information. All basic Media Kit control messages also have associated times; a node is responsible for properly managing all of these timed events.

Enter the new BTimedEventQueue utility class. The idea is that data representing a specific event is pushed to the queue along with a time when that event needs to occur (as seen by the user). The queue is sorted by the event time, so a node can pop the appropriate event off the queue and handle it at the right time and in the proper order.

Now, a quick look at the main functions of the class.

status_t PushEvent( bigtime_t time, int32 what,
     void *pointer, uint32 pointer_cleanup, int64 data);

Here, an event is represented by a performance time, a what value, some pointer data, a flag denoting how the pointer should be cleaned up, and an int64 worth of additional storage.

Events are usually pushed on to the queue in a node hook function, for example:

MyBufferConsumer::BufferReceived(BBuffer *buffer)
{
  if (!fRunning)
     buffer->Recycle();
     return;

  // add the event to the queue
  status_t error = B_OK;
  error = fEvents->PushEvent(
     buffer->Header()->start_time,
     BTimedEventQueue::B_HANDLE_BUFFER,
     buffer,
     BTimedEventQueue::B_RECYCLE,
     0);

  if (error != B_OK)
     buffer->Recycle();
}

Here the pointer keeps track of the buffer to work with, the cleanup specifies that the buffer should be recycled during cleanup (if not sent correctly), and the data field is not used.

The PopEvent() function, which takes pointers to the data members of the event, retrieves events from the queue:

status_t PopEvent(bigtime_t *time, int32 *what,
     void **pointer, uint32 *pointer_cleanup, int64 *data);

When an event is popped off the queue it is usually handed to a HandleEvent() function. In HandleEvent() the node should look at the 'what' member and decide what action to take. Whoever handles the event is responsible for cleaning up anything stored in the pointer field, based on the pointer_cleanup information.

If you need to clear a large number of items out of the queue without handling them, FlushEvents() lets you specify which events to clear.

status_t FlushEvents(bigtime_t time,
     time_direction direction, bool inclusive = true,
     int32 event = B_ANY_EVENT);

When flushing events you can specify a time from which to base your decision, a direction in time, whether to include the specified time in the flush, and the event type to clear out. The function is very flexible, allowing you to remove all items with a given event type what like this:

fEvents->FlushEvents(B_INFINITE_TIMEOUT,
     BTimedEventQueue::B_BEFORE,
     true, BTimedEventQueue::B_HANDLE_BUFFER);

Or, you can clear out all types within a given range in time:

fEvents->FlushEvents(someTime, BTimedEventQueue::B_AFTER);

In either case, when events are flushed from the queue, the CleanUpEvent() function of the queue is called. It looks at the event and cleans up the pointer data appropriately. If you add your own cleanup type, you'll need to subclass the event queue to provide the appropriate cleanup functionality.

There are also two functions for investigating the contents of the queue:

bool HasEvents();
bigtime_t NextEvent(int32 *what);

HasEvents() returns a boolean and is fairly self-explanatory. NextEvent() gives information about the next event that needs to occur. It returns the time the event needs to occur, and if passed an int32 pointer, it will fill in the 'what' value of the next event. If there are no events in the queue, NextEvent() returns B_INFINITE_TIMEOUT for the time and B_NO_EVENT for the event type.

The real advantage of this class is that it simplifies the main loop of a node. A main loop with an event queue now looks something like this in psuedo-code:

MyMediaNode::MainLoop()
{
  while (!timeToQuit) {
     while (noEventsInQueue || notTimeForNextEvent) {
       timedOut = WaitForMessages(untilNextEventInRealTime);
       if (timedOut) break;
     }
     PopEventFromQueue();
     HandleEvent();
  }
}

If the queue does not have any events, or if it's not time for the next event, the node loops over the WaitForMessages() call until it is time for the next event.

status_t
MyMediaNode::WaitForMessages(bigtime_t waitUntil)
{
  status_t err = read_port_etc(port, code, message,
     message_size, B_ABSOLUTE_TIMEOUT, waitUntil);
   if (err = B_TIMED_OUT)
     return err;
   /* handle the incoming message */
   HandleMessage(code, message, message_size);
   return B_OK;
}

WaitForMessages() services the control loop and handles all messages that come in. After a message arrives, something is usually added to the queue, and the next event time is evaluated.

When it's finally time to handle an event, the first event is popped off the queue and HandleEvent() is called.

This is a much easier to understand main loop, and as such should be easier to get right.

I've packaged up the BTimedEventQueue class and a sample node that uses it. The ChromeVideo node is derived from a first pass at a filter node that uses a main loop similar to the one above. It's a simple video filter that takes 32-bit color video and outputs somewhat freaky 8-bit gray video (using an algorithm that takes the red value of a pixel and bitshifts it down by 3, then puts the resulting value in the outgoing buffer). The ChromeVideo and the underlying BBufferFilter are works in progress and don't yet do everything they should. The purpose of distributing them now is to let you see the event queue in action.

You can find ChromeVideo at:

ftp://ftp.be.com/pub/samples/media_kit/ChromeVideo.zip

Don't miss the ReadMe, so you understand the contents of the package.

To see the class in action you need a supported video card and the corresponding capture and display nodes. You can find an alpha version of the Bt848 nodes and supporting application for R4 at Steve Sakoman's site:

http://www.sakoman.com/

These nodes are part of the upcoming 4.1 upgrade.

This has been a first look at how we're trying to simplify the writing of Media Nodes. If you want to know more, register for the upcoming BeDC -- Programming with the Media Kit:

http://www.be.com/developers/developer_conference/BeDC_info.html

See you there!

Keeping our past newsletters on line has many advantages. One of these is that they give readers a sense of the history of our little company. Sometimes, sharp-eyed readers kindly give us an opportunity to shed the light of logic, or apology, on apparent contradictions. For instance, I wrote a column titled "The War of Two Browsers" on August 28th, 1996. In it, I wrote "In the meantime, we happen to agree with Microsoft: the browser ought to be integrated in the system and presented to application programmers as an API, a class library. After all, several years ago, we didn't call our 'user shell' a Finder or a File Manager, we called it a browser."

How does this square with our subsequent criticism of Microsoft's integration of the Explorer Web browser in Windows in subsequent columns: On February 3rd, 1999, and on February 10th, 1999? Are we contradicting ourselves? Did I even remember our August 1996 position when I wrote my February 1999 columns? No and Yes.

Let's start with two premises. First, the "border" issue, and second, what you can no longer do once you've become a monopoly. The "border" issue invoked here refers to the difficulty of setting up a clean, well-lighted fence between what we imprecisely call the operating system and the applications. Today, it appears extremely difficult, some say impossible, to write a usable English sentence as a test of which is which. If the code meets condition A, it belongs to the OS. We have trouble describing what "condition A" would be. I don't know if the trouble lies more with the speed of technological evolution making definitions obsolete, or with the very protean nature of software. I guess that it's more the latter than the former.

In any event, how does one write laws or regulations governing borders that are imprecise at any given moment—and that move very fast once you unfreeze the clock. This would seem to support Microsoft's right to put whatever they please in Windows—a spreadsheet, a word processor (there's a decent one already, WinPad), or a Web browser whose capabilities would help many other system modules or applications—if we stick to a common-sense but imprecise definition for these two.

Turning to the second issue: Things that change once you become a monopoly. In a market where no player dominates, common-sense and, it seems, the law both say that exclusionary incentives can be offered. What I have in mind is offering a retailer an incentive to distribute your brand of yogurt and only your brand of yogurt. For instance, a supplementary discount above the normal wholesale price. Retailers who offer several brands of yogurt pay wholesale, but the retailer who offers brand X exclusively gets a supplementary rebate.

In a truly competitive market, this is legit. Other retailers exist who might bet customers will prefer a choice of yogurt. Smaller margins on brand X might be compensated by more volume, or more store traffic and the opportunity to sell fidgets, bidgets and ridgets, not just an assortment of yogurt. Once you become a monopolist, things change. Retailers effectively offer only one brand, brand X. In addition to the wholesale price, the retailer gets a substantial supplementary discount based on not offering and/or advertising any emerging new brand. If he does, he loses a sizeable amount of money. Sales from the emerging brand Y cannot make up for the loss, and his competitors who didn't budge pay a lower price for the monopoly product. The market is locked.

This is but one example of what happens when you become a monopoly: Behavior that's acceptable when the market is truly competitive must be rejected once a monopoly situation sets in. With this in mind, let's consider the manner and the motives for Microsoft's integration of the Explorer browser into Windows. They could have done it "fair and square," one module (or a small number of modules) somewhere in the system, a sort of Web driver (I realize the metaphor is crude, but the point is valid nonetheless). Today, you can update or replace a driver and, if the driver works as intended or better, the user benefits, applications get better performance, the system is improved.

Even if a browser is more complicated that a dial-up module, it features a finite list of pipes for information to come in and go out of. One way of integrating the browser makes it easy to disconnect and reconnect the pipes, another way makes it deliberately difficult. Did Microsoft make the disconnection and reconnection deliberately difficult and, if they did, why? As a monopolist, are they free to make it arbitrarily difficult to remove Explorer? Did they have an anti-competitive motive for doing so? Did they leverage their monopoly? Did they fear that another Web browser might prevent them from gaining control of the HTML dialect mostly spoken on the Web?

In our case, we found we could offer a browser and make it easily removable. In other words our browser is integrated in the sense that it's "in the box" when you install the BeOS, it's in the system. But if, in the future, you want to install a competitive browser, it's a simple drag and drop move. Integration doesn't have to be anti-competitive.