Bryan Mumford <PICLIST@mitvma.mit.edu> wrote:

> I don't see the point in calculating and storing Bresenham's (2 *
> deltay) and (deltax - deltay)

Bryan:

The constants end up that way as a consequence of the requirement for
integer rounding to work properly.

If you start with a line-drawing algorithm that uses the slope-
intercept formula y = mx + b, the first optimization you'd make would
be to use integers instead of floats.  Once you do, you'll want to
round to nearest integers consistently, and the easiest way to do
that is to make the formula y = mx + b + 0.5.

If you proceed to optimize that algorithm, you'll get to a point
where your code looks like (I'm using dx and dy for deltax and
deltay):

    d = dy/dx + 0.5
    ....
    x += 1
    d += dy/dx
    if (d > 1) {
        y += 1
        d -= 1
    }

The fractions are awkward, so we remove them by multiplying by 2 *
dx:

    d = 2 * dy + dx
    ....
    x += 1
    d += 2 * dy
    if (d > (2 * dx)) {
        y += 1
        d -= 2 * dx
    }

Since we'd much rather compare the fraction to 0 than to 2 * dx, we
subtract 2 * dx from the initialization value and the comparison
value:

    d = 2 * dy - dx
    ....
    x += 1
    d += 2 * dy
    if (d > 0) {
        y += 1
        d -= 2 * dx
    }

So that's where the 2dy, -2dx, and 2dy-dx terms come from.

You can draw lines the way you described, by initializing to 0 and
then simply adding dy and subtracting dx, but they won't be plotted
on the same points as if you used the canonical y = mx + b formula or
Bresenham's algorithm (which was derived from that formula).

It may also be important to you that a line drawn from (a,b) to (c,d)
is plotted on the same points as a line drawn from (c,d) back to
(a,b).  If that IS important, you should check your algorithm to see
whether it satisfies that requirement.

-Andy

=== Andrew Warren -- aiw@cypress.com
=== Principal Design Engineer
=== Cypress Semiconductor Corporation
===
=== Opinions expressed above do not
=== necessarily represent those of
=== Cypress Semiconductor Corporation

--
http://www.piclist.com hint: PICList Posts must start with ONE topic:
[PIC]:,[SX]:,[AVR]: ->uP ONLY! [EE]:,[OT]: ->Other [BUY]:,[AD]: ->Ads