gbadev.org forum archive

Here's a nagging question...

Alot of interger based line routines I've seen have
a common problem when dealing with lines at near vertical
or near horizontal. Example...

instead of:

Code:

XXXXXXXX
XXXXXXXX

you get this:

Code:

X
XXXXXXXXXXXXXXX

Can anybody offer a way of getting rid of this?

It seems to be releated to the direction of the line and integer math.

The lower right quardrant types seem fine. But I didn't
want to implement a bunch of end swapping to deal with it.

Any suggestions?

Chris

I am hard-pressed to think of an algorithm that would generate a line like your second example, especially seeing as it seems to be generating more of an arc than a line. Can you post the algorithm you're using?

Dan.

FPChris wrote:

Here's a nagging question...

Code:

X
XXXXXXXXXXXXXXX

Can anybody offer a way of getting rid of this?

If you are doing this the way I think you are, then I think you'll have to add some constant before you divide. I think the constant is derived y0 and y1 when horizontal, and from x0 and x1 when vertical. (It's more of a proportion, perhaps?)

-Brendan

Here's part of it. I am writing and 'x' edge tabler for polygon routines
so for the 'x row' fill in the loop I'm just plotting the leading pixel
to test the results for now.

I have seen this happen in several bresenham implementations.

Code:

s32 dx = (x2-x1);
s32 dy = (y2-y1);

s32 m = (dx << 16) / dy;
s32 x = x1 << 16;

s32 yoff = 1;
if(y1 > y2){ yoff = -1; m=-m; }
s32 loop = abs(dy);

for(int i=0;i<loop;i++,y1+=yoff){ //loop y1 to y2

DrawPixel(x>>16,y1,clr,buf);
x+=m;

}//i

DrawPixel(x2,y2,clr,buf); //last pixel

I just found an article at:

http://www.cit.gu.edu.au/~anthony/info/graphics/bresenham.procs

I'll give it a read and see if it explains this sort of error.
At quick glance it appears too.

Chris

Hmm, I gave that article a quick look and it seemed to be using some sort of error terms, which are a little confusing sometimes. A much easier way using regular fixed point is explaned at Hugo Elias's web site.
The theory is that you interpolate along your line until your Y position is at an even integer, and then start drawing. The way to do that is by getting the Y distance between the actual start of the line and the center of the next pixel, which is done like this:

yError = INT_TO_FIXED( FIXED_TO_INT(y) + 1 ) - y;

That page has an image that shows graphically what yError is, which helps a lot to understand it.

Then you do like
x += deltaX * yError;
y += INT_TO_FIXED(1);

And then draw the line as normal. It seems like I remember that method moving everything down one pixel, which it does seem like it would do. I'd have to do some experimenting, but I think you could do it like

yError = INT_TO_FIXED(FIXED_TO_INT(y)) - y;

And skip adding the 1 to y and it would be in the right place. I think you could end up with a negtive yError that way though, because if y was say .8, chopping off the fractional portion would get 0, and then subtracting the .8 from 0 would give -.8 for yError, which is right, because rounding down to the top edge of pixel 0, you would need to 'back up' along the 'real space' line and then start drawing forward.

Well, I hope that makes sense to you, or at least the web site does. It all depends on how you define your pixel space. The way he does it, the center of the top row is defined to be 0, which makes anything between the very top edge and the center of the top row's pixels negative, which I think is why mine was getting off by one, because it was clipping anything in that range. The second method I was talking about (not adding 1) defines the borders between the pixels to be the integer coordinates, so the very top edge of the screen is 0, and the edge between the first and second rows of pixels is 1. I think it works either way, just gotta keep your head straight on what you're doing.
_________________
___________
The best optimization is to do nothing at all.
Therefore a fully optimized program doesn't exist.
-Deku

Thanks, I'll give it a read.

From what I've read elsewhere drawing the line in two
different directions can make a difference as well. So in order
not to have gaps between my poly edges I probably have to
use a swap ends so than A->B draws the same line as B->A etc.

This may be effecting the fixed point I was using and causing
and improper line to be draw depending on which end I was
working from -> to.

Chris

FPChris wrote:

Thanks, I'll give it a read.

From what I've read elsewhere drawing the line in two
different directions can make a difference as well. So in order
not to have gaps between my poly edges I probably have to
use a swap ends so than A->B draws the same line as B->A etc.

This may be effecting the fixed point I was using and causing
and improper line to be draw depending on which end I was
working from -> to.

Chris

My suggesttions :-

Use fixed point slopes.
Avoid Bresenham altogether.

Make sure you sample your edge from consistent pixel positions for every pixel. So make sure you take your x from the same y position for each vertical pixel. (I use y=0.5 in each pixel)
That way you should avoid the issues you're getting in your polygon drawer. This is a common problem.

So if your line starting y is at pixel position 0.9 then you need to fixup your y to 0.5 and then fixup your x also.
So x+=(0.9-0.5)*dx
This means when you add your horizontal gradient for every vertical you sample consistently at 0.5 in your pixel.
Confused ? Well I've not found a good way of explaining this, someone else might be able to help you more on this.

gbadev.org forum archive

C/C++ > Drawing lines and fixed point

#22461 - FPChris - Tue Jun 22, 2004 2:45 am

#22462 - poslundc - Tue Jun 22, 2004 3:23 am

#22463 - sgeos - Tue Jun 22, 2004 4:12 am

#22464 - FPChris - Tue Jun 22, 2004 4:56 am

#22465 - FPChris - Tue Jun 22, 2004 5:12 am

#22509 - DekuTree64 - Wed Jun 23, 2004 6:09 am

#22519 - FPChris - Wed Jun 23, 2004 12:34 pm

#30732 - AnthC - Sat Dec 04, 2004 1:25 am