# draw 2d line with clipping

This topic is 2013 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

i would need a function for drawing (rasterizing) a 2d line on the screen

it should work for iint 32 range values for start_x, start_y and end_x, end_y

(I mean it should ewen get a values like  DrawLine( -1000000, 1000000, 300, 200, 0xffffff) ;) but should be clipped to the screen rectangle (of the width and height like 800x600)

A bit trouble was when I clipped the line to the screen rectangle and draw it with the bressenham, It showed to be a bit incorrect becouse of fact that

incoming screen edge bressenham starting points were realy like  (102.3 , 0) - (95.7, 0) and casting it to (102, 0)  - (96, 0) for bressenham usage wassomewhat inexact

besides that i do not know how the clipping routine should look like to be efficient

In general this leads to some thing at all -

when it seem that i couls consider DrawLine routine to be

taking only integer values (this is probably how bressenham

works, it treats 0,0 as top left pixel, It shows that this "integer"

approach is to narrow - and for example when doing clipping

it is a need to some routine that is able to be working on

fractional starting points coordinates (though besides i would like to work on integer) how to do that is bressenham capable to work on fractional starting and ending points points

DrawBressenhamLine(12.5, 7.3, 128.9, 411.8)  ?

Edited by fir

##### Share on other sites

Looking at the algorithm, to me it seems you could modify it in such a way.

It seems as if you should only need to round the values in a few places which expect them to be integers, however you also need to initialize the "error" variable to a nonzero value (looking at the wikipedia article) to account for the fact that there is already error (since the error essentially represents the fractional part of the coordinate of the current point being drawn)

Modifying the wiki article (x0,x1,y0,y1 would be floats or doubles here):

function line(x0, x1, y0, y1)
int deltax := x1 - x0 //make these 2 lines floats
int deltay := y1 - y0
real error := 0 //initialize this to deltaerr*fractionalPartOf(x0) <-!!!
real deltaerr := abs (deltay / deltax)
int y := y0 //make this floor(y0) (floor because of how the initial error is set)
for x from x0 to x1 //round these to integers somehow
plot(x,y)
error := error + deltaerr
if error ? 0.5 then
y := y + 1
error := error - 1.0


I commented what should be changed. It might work, might not.

Edited by Waterlimon

##### Share on other sites

Looking at the algorithm, to me it seems you could modify it in such a way.

It seems as if you should only need to round the values in a few places which expect them to be integers, however you also need to initialize the "error" variable to a nonzero value (looking at the wikipedia article) to account for the fact that there is already error (since the error essentially represents the fractional part of the coordinate of the current point being drawn)

maybe, but how? (this is also the trouble with midpoint circle drawing routine when i want to draw large circles (like 5 000 pixel radius) co i need to clip and modify somewhat midpoint for arcs

(I was discussing different approach to bressenham in the post near here (by fixedpoints dx , dy)  but im not sure if this would be not slower and also this is probably burden by some inexact errors when drawing)

anyway yet worse for me is to find good line to screen rectangle clipping routine

Edited by fir

##### Share on other sites

Modifying the wiki article (x0,x1,y0,y1 would be floats or doubles here):

function line(x0, x1, y0, y1)
int deltax := x1 - x0 //make these 2 lines floats
int deltay := y1 - y0
real error := 0 //initialize this to deltaerr*fractionalPartOf(x0) <-!!!
real deltaerr := abs (deltay / deltax)
int y := y0 //make this floor(y0) (floor because of how the initial error is set)
for x from x0 to x1 //round these to integers somehow
plot(x,y)
error := error + deltaerr
if error ? 0.5 then
y := y + 1
error := error - 1.0


I commented what should be changed. It might work, might not.

Hmm I would need to rethink it when using fixedpoints maybe

If you can hint it would be welcome so i could try the results

other thing is that if i doing fixedpoint coordinates maybe i should do wu-lines instead of bressenham becouse when i would like for example draw 0,0 to 100,100 where 0,0 is point between the four pixels so how to interpret it -- but then with wu-lines I got another trouble - counting  gamma for background pixel gamma for input pixel then gamma the result - it makes me lose heart for it

##### Share on other sites

The idea is essentially that you take the original plotting loop (PASSING INTEGER COORDS + range of x where to draw).

Then you split it into two parts:

2. Advance and draw every pixel

where the first part is applied over the non-drawn outside screen range and the second for the area inside screen. The rest is just ignored.

Now, you should be able to express (1) in a non-loop form, simplifying it down to very simple arithmetic. Try to do something like that with whatever algorithm you use.

eg:

//ORIGINAL
function line(x0, x1, y0, y1, xmin, xmax)
int deltax := x1 - x0
int deltay := y1 - y0
real error := 0
real deltaerr := abs (deltay / deltax)
int y := y0
for x from max(x0,xmin) to min(x1,xmax)
plot(x,y)
error := error + deltaerr
if error ? 0.5 then
y := y + 1
error := error - 1.0

//SPLIT LOOP
function line(x0, x1, y0, y1, xmin, xmax)
int deltax := x1 - x0
int deltay := y1 - y0
real error := 0
real deltaerr := abs (deltay / deltax)
int y := y0
for x from x0 to xmin //no draw
error := error + deltaerr
if error ? 0.5 then
y := y + 1
error := error - 1.0
for x from max(x0,xmin) to min(x1,xmax) //draw
plot(x,y)
error := error + deltaerr
if error ? 0.5 then
y := y + 1
error := error - 1.0

//SIMPLIFY FIRST LOOP
function line(x0, x1, y0, y1, xmin, xmax)
int deltax := x1 - x0
int deltay := y1 - y0
real error := 0
real deltaerr := abs (deltay / deltax)
int y := y0

error := error + deltaerr*(xmin-x)
y := y + (how many times u can negate 1 out of error so that error>=0.5)
error := error - (how many times u can negate 1 out of error so that error>=0.5)

for x from max(x0,xmin) to min(x1,xmax) //draw
plot(x,y)
error := error + deltaerr
if error ? 0.5 then
y := y + 1
error := error - 1.0


Something like that.

You basically need to:

1) Pretend that the algorithm draws the actual long line

2) Optimize the parts that dont actually draw, which means a loop becomes some simple math operations on variables

##### Share on other sites

There is no need to execute the loop to obtain the correct values of x, y and error. The error is simply the vertical distance from the line to the current pixel. If (x_0, y_0) the better approximation of the first pixel to draw on the screen and y = m*x + q is the line equation, then error = m*x_0 + q - y_0. You should then be able to draw the following pixels without problems.

##### Share on other sites

It sounds like you want a line drawing algorithm that has subpixel accuracy, like Xiaolin Wu's <a data-ipb="nomediaparse" data-cke-saved-href="http://en.wikipedia.org/wiki/Xiaolin_Wu" href="http://en.wikipedia.org/wiki/Xiaolin_Wu" s_line_algorithm"="">line algorithm

EDIT:  Grr, the auto linker/highlighter is having a devil of a time with the apostrophe in the link

http://en.wikipedia.org/wiki/Xiaolin_Wu%27s_line_algorithm

Edited by Glass_Knife

##### Share on other sites

I tried to fix the link, but I just made it worse.  Gaaahhhh.  HTML!!!  I changed the ' to a %27.  Looks ugly but gets you there...

Edited by Glass_Knife

##### Share on other sites

alright tnx for the answers , will answer a bit later ned a bit of time

##### Share on other sites

There is no need to execute the loop to obtain the correct values of x, y and error. The error is simply the vertical distance from the line to the current pixel. If (x_0, y_0) the better approximation of the first pixel to draw on the screen and y = m*x + q is the line equation, then error = m*x_0 + q - y_0. You should then be able to draw the following pixels without problems.

I got such three 'problem cases ' :

when doing integer line drawing everythink is about to be known how to do it - also if  you doing float line drawing (if

i call this name wu-line when you use float coordinates and

divide color on near pixel parts) it is also about to be known

how to do it

- but if you want to do some integer line drawing (i mean without color dividing only 0/1) on a float starting and ending coordinates then some problems appear

I ) what coordinates to chose, do set a 0,0 as a centre of topt left pixel or 0,0 should be only a corner of the pixel where its centre is in 0.5,0.5 - this is in some way incoherent with full discrete version in one case or incohherent in full wu-line version in second case

II) how to draw such pixels as 0,0 when 0,0 is chosen as a corner point between 4 pixels :/

so in summary i mean that clear integer drawline, in some cases as clipping is distorted into problematic half-integer half-float DrawLine routine

III)

when chosing wu-line wu-line probably resolves the problems of this half-integer-half-float case but there is a gamma problem

when drawing wu-line on color bitmap i cannot just average its

pixel color with its background pixel color - or can I ?

when drawing real color on screan i need to gamma it

(boost to lighter value like 128 to 194 or something) also when reading color i need probably ungamma it (visible 194->128 real)

then average and gamma it again ?

- this is probably better but will be 5x 10x 15x ? times slower

so i would like probably to provide both versions of the routines

PS.

Also i am not sure what i should do with fron wu tline  and background colors, should i average them?

when drawing white line on black blackground it is easy but

what if i need to wrote a white line on a gray background?

If fitted in one pixel it would be white on gray but if divided on

two pixels it would be gray on gray so the white line just will be vanishing there

Edited by fir

• ### Game Developer Survey

We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a \$15 incentive for your time and insights. Click here to start!

• 16
• 11
• 23
• 42
• 75