# The Bresenham Line-Drawing Algorithm

## The Bresenham Line-Drawing Algorithm

Thuật toán này khá mới, cải tiến hơn so với thuật toán Bresenham đang dạy trong các trường đại học.

//Chi tiết bài viết

Consider drawing a line on a raster grid where we restrict the

allowable slopes of the line to the range .

If we further restrict the line-drawing routine so that it always

increments

plotted a point at

range of options as to where it may put the

line:

So, working in the

drawing becomes a matter of deciding between two possibilities at each

step.

We can draw a diagram of the situation which the plotting program finds

itself in having plotted

In plotting

be making a compromise between what it would like to draw and what the

resolution of the screen actually allows it to draw. Usually the

plotted point

point on the line will not be addressable on the pixel grid. So we

associate an error, , with

each

the real value of

This

error will range from -0.5 to just under +0.5.

In moving from

true (mathematical) y-ordinate by an amount equal to the slope of the

line,

difference between this new value and

Otherwise we will plot

so doing we minimise the total error between the mathematical line

segment and what actually gets drawn on the display.

The error resulting from this new point can now be written back into

,

this will allow us to repeat the whole process for

the next point along the line, at

The new value of error can adopt one of two possible values, depending

on what new point is plotted. If

value of error is given by:

Otherwise it is:

This gives an algorithm for a DDA which avoids rounding operations,

instead using the error variable to

control plotting:

This still employs floating point values. Consider, however, what

happens if we multiply across both sides of the plotting test by

and then by 2:

All quantities in this inequality are now integral.

Substitute

for .

The test

becomes:

This gives an

plot.

The update rules for the error on each step may also be cast into

form. Consider the floating-point versions of the

update rules:

Multiplying through by

yields:

which is in

form.

Using this new ``error'' value, ,

with the new test and

update equations gives Bresenham's integer-only line drawing algorithm:

Here is a C++ implementation of the Bresenham algorithm for line

segments in the first octant.

void linev6(Screen &s,

unsigned x1, unsigned y1,

unsigned x2, unsigned y2,

unsigned char colour )

{

int dx = x2 - x1,

dy = y2 - y1,

y = y1,

eps = 0;

for ( int x = x1; x <= x2; x++ ) {

s.Plot(x,y,colour);

eps += dy;

if ( (eps << 1) >= dx ) {

y++; eps -= dx;

}

}

}

This is an all-integer function, employs left shift for multiplication

and eliminates redundant operations by tricky use of the

eps variable.

This implementation of Bresenham's algorithm is incomplete, it does not

check the validity of its arguments. A real implementation should do

this.

In fact, a real implementation of Bresenham's algorithm should do more

than simply reject lines with slopes lying outside the first octant,

it should handle lines of arbitrary slope.

If we try out the C++ implementation of the Bresenham algorithm, we

find it has some peculiar properties.

As expected, it fails to plot lines with negative slopes (try it and

see what happens). It also fails to plot lines of positive slope

greater than 1 (this is an interesting case, try it also and see if you

can explain what is happening).

More unusually, we find that the order in which the endpoints are

supplied

to this routine is significant, it will only work as long as x1

is smaller than x2.

In fact, if we have two line segments with the same endpoints, and the

same slope, this routine may draw one of them successfully but fails to

draw the other one.

Of course, this is not surprising really, when we consider that the

function works by

emphasise, however, that the routine is plotting

direction is significant. Considering all the vectors from

regions, (the ``octants'') and the basic Bresenham algorithm works in

only one of them.

A full implementation of the Bresenham algorithm must, of course, be

able

to handle all combinations of slope and endpoint order.

Some of the regions in the plane, those for which

smaller than

the

line segment.

It is also clear that we will need a piece of code to handle large

slopes by stepping over

However, careful consideration of the diagram will reveal that there is

one case which cannot be reduced to a version of the algorithm we have

already looked at. If we want to draw a line having a small

basic Bresenham algorithm to do this. (The same point applies to lines

of

slopes may be adapted to this case by stepping over

of

Consider a line with negative slope between 0 and 1 (i.e., small

negative slope. Given that a line-drawing algorithm has plotted a point

at

between

As usual there will be an error, ,

associated with

attempt to minimise error, so plot

Otherwise plot

the above is

inequality:

It is worth comparing this with the decision inequality for the case of

positive slope.

The error update rules are also subtly different for this case of

negative slope.

If plotting

by:

Otherwise, plotting

A pseudocode algorithm for this routine may be written as:

This is cast in terms of floating-point values.. It is, however, a

trivial matter to convert the algorithm into an integer-only form.

Colin Flanagan / flanaganc@ul.ie

//Chi tiết bài viết

**The basic Bresenham algorithm**Consider drawing a line on a raster grid where we restrict the

allowable slopes of the line to the range .

If we further restrict the line-drawing routine so that it always

increments

*x*as it plots, it becomes clear that, havingplotted a point at

*(x,y)*, the routine has a severely limitedrange of options as to where it may put the

*next*point on theline:

- It may plot the point
*(x+1,y)*, or: - It may plot the point
*(x+1,y+1)*.

So, working in the

*first positive octant*of the plane, linedrawing becomes a matter of deciding between two possibilities at each

step.

We can draw a diagram of the situation which the plotting program finds

itself in having plotted

*(x,y)*.In plotting

*(x,y)*the line drawing routine will, in general,be making a compromise between what it would like to draw and what the

resolution of the screen actually allows it to draw. Usually the

plotted point

*(x,y)*will be in error, the actual, mathematicalpoint on the line will not be addressable on the pixel grid. So we

associate an error, , with

each

*y*ordinate,the real value of

*y*should be .This

error will range from -0.5 to just under +0.5.

In moving from

*x*to*x+1*we increase the value of thetrue (mathematical) y-ordinate by an amount equal to the slope of the

line,

*m*. We will choose to plot*(x+1,y)*if thedifference between this new value and

*y*is less than 0.5.Otherwise we will plot

*(x+1,y+1)*. It should be clear that byso doing we minimise the total error between the mathematical line

segment and what actually gets drawn on the display.

The error resulting from this new point can now be written back into

,

this will allow us to repeat the whole process for

the next point along the line, at

*x+2*.The new value of error can adopt one of two possible values, depending

on what new point is plotted. If

*(x+1,y)*is chosen, the newvalue of error is given by:

Otherwise it is:

This gives an algorithm for a DDA which avoids rounding operations,

instead using the error variable to

control plotting:

This still employs floating point values. Consider, however, what

happens if we multiply across both sides of the plotting test by

and then by 2:

All quantities in this inequality are now integral.

Substitute

for .

The test

becomes:

This gives an

*integer-only*test for deciding which point toplot.

The update rules for the error on each step may also be cast into

form. Consider the floating-point versions of the

update rules:

Multiplying through by

yields:

which is in

form.

Using this new ``error'' value, ,

with the new test and

update equations gives Bresenham's integer-only line drawing algorithm:

- Integer only - hence efficient (fast).
- Multiplication by 2 can be implemented by left-shift.
- This version limited to slopes in the first octant, .

Here is a C++ implementation of the Bresenham algorithm for line

segments in the first octant.

void linev6(Screen &s,

unsigned x1, unsigned y1,

unsigned x2, unsigned y2,

unsigned char colour )

{

int dx = x2 - x1,

dy = y2 - y1,

y = y1,

eps = 0;

for ( int x = x1; x <= x2; x++ ) {

s.Plot(x,y,colour);

eps += dy;

if ( (eps << 1) >= dx ) {

y++; eps -= dx;

}

}

}

This is an all-integer function, employs left shift for multiplication

and eliminates redundant operations by tricky use of the

eps variable.

This implementation of Bresenham's algorithm is incomplete, it does not

check the validity of its arguments. A real implementation should do

this.

In fact, a real implementation of Bresenham's algorithm should do more

than simply reject lines with slopes lying outside the first octant,

it should handle lines of arbitrary slope.

**Handling multiple slopes**If we try out the C++ implementation of the Bresenham algorithm, we

find it has some peculiar properties.

As expected, it fails to plot lines with negative slopes (try it and

see what happens). It also fails to plot lines of positive slope

greater than 1 (this is an interesting case, try it also and see if you

can explain what is happening).

More unusually, we find that the order in which the endpoints are

supplied

to this routine is significant, it will only work as long as x1

is smaller than x2.

In fact, if we have two line segments with the same endpoints, and the

same slope, this routine may draw one of them successfully but fails to

draw the other one.

Of course, this is not surprising really, when we consider that the

function works by

**incrementing***x*. It doesemphasise, however, that the routine is plotting

*vectors*,direction is significant. Considering all the vectors from

*(x1,y1)*to*(x2,y2)*we find that there are eightregions, (the ``octants'') and the basic Bresenham algorithm works in

only one of them.

A full implementation of the Bresenham algorithm must, of course, be

able

to handle all combinations of slope and endpoint order.

Some of the regions in the plane, those for which

*x2*issmaller than

*x1*can be handled by exchanging the endpoints ofthe

line segment.

It is also clear that we will need a piece of code to handle large

slopes by stepping over

*y*instead of*x*values.However, careful consideration of the diagram will reveal that there is

one case which cannot be reduced to a version of the algorithm we have

already looked at. If we want to draw a line having a small

*negative*slope, we will have to consider a modification of thebasic Bresenham algorithm to do this. (The same point applies to lines

of

*large*negative slope as well, but the code for small negativeslopes may be adapted to this case by stepping over

*y*insteadof

*x*).**Bresenham for negative slopes**Consider a line with negative slope between 0 and 1 (i.e., small

negative slope. Given that a line-drawing algorithm has plotted a point

at

*(x,y)*, its choice about where to plot the next point isbetween

*(x+1,y-1)*and*(x+1,y)*.As usual there will be an error, ,

associated with

*y*. Choice of the next point to plot will be based on anattempt to minimise error, so plot

*(x+1,y)*if:Otherwise plot

*(x+1,y-1)*. Notice that the error generated bythe above is

*negative*. A little manipulation gives a decisioninequality:

It is worth comparing this with the decision inequality for the case of

positive slope.

The error update rules are also subtly different for this case of

negative slope.

If plotting

*(x+1,y)*the*new*value of error is givenby:

Otherwise, plotting

*(x+1,y-1)*gives new error:A pseudocode algorithm for this routine may be written as:

This is cast in terms of floating-point values.. It is, however, a

trivial matter to convert the algorithm into an integer-only form.

Colin Flanagan / flanaganc@ul.ie

**anbinhtrong**- Admin
- Tổng số bài gửi : 216

Join date : 05/11/2009

Age : 28

Đến từ : BT

Trang

**1**trong tổng số**1**trang**Permissions in this forum:**

**không có quyền**trả lời bài viết