Advertisement Jump to content
Sign in to follow this  
fir

draw 2d line with clipping

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement

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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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:

1. Advance but no draw

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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites

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

Share this post


Link to post
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

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!