Jump to content
  • Advertisement
Sign in to follow this  
TheVoid

line drawing (special case)

This topic is 5390 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

Hi, Im trying to implement triangle rasterization algorithm: edge walking. The problem is that I must "draw" the special line segment. This is a line segment drew by the Bresenham's or DDA line drawing algorithm (red means the start of the line, and green the end): And here is a line segment that I need: I need algorithm that woun't draw more than one pixel in single row. This problem occurs only when deltaX is greater than deltaY. If deltaX is less or equal than deltaY everything is ok. In all cases y2 wil be always greater or equal y1. Where can I find more about edge walking algorithm? Im' not sure I'm implementing it in right way! Thanks in advance. edited: I forgot to add that algorithm must work for 16-bit signed integers. [Edited by - TheVoid on October 12, 2004 4:54:43 PM]

Share this post


Link to post
Share on other sites
Advertisement
it's very simple.
Something like
r=(deltaX<<16)/deltaY;
int x=x1+32768;// optionally - makes it look nicer for small deltaX/deltaY
for(int y=y1;y<=y2;y++){
use (x>>16),y as you want;
x+=r;
}

It's also more efficient than typical Bresenham (note lack of unpredicable branch)

edit: and some explanations:
x is storen in 16.16 fixed point format, and 32768 = 0.5 in that format.So x is at center of cell, so with small deltaX / deltaY, you have a step in center, not in bottom, and it looks better.

[Edited by - Dmytry on October 12, 2004 10:53:23 AM]

Share this post


Link to post
Share on other sites
Quote:
Hi.
Do you know how edge walking algorithm works?
Do you have any resources about it?


You mean triangle rendering / rasterizing / drawing?
Probably it's not called edge walking. When i read "edge walking" i for first time think it's something about graph theory/AI .

No resources, but i have implemented it already, for any n-gons(not only triangles). It's pretty simple.

For triangles it's even simpler.
1: it's better not to do <<16 in triangle drawer but pass already shifted x coords to it, or floats. So it will look better when triangle is slowly moving.

Assuming x coords is all shifted left by 16 (and optionally incremented by 32768), y coords isn't.
Algorithm:

sort vertices [x1,y1] [x2,y2] [x3,y3] by y
so y1<=y2 , y2<=y3
You need to handle equality cases specially - bypass non-working divisions, (let anything/0=0 ) and everything will be ok.
then do
int x_left=x1;
int x_right=x1;
int d_x_left1=(x2-x1)/(y2-y1);
int d_x_right1=(x3-x1)/(y3-y1);
int d_x_left2=(x3-x2)/(y3-y2);
int d_x_right2=d_x_right1;
if(d_x_right1<d_x_left1){swap _right_ with _left_ ;}
for(int y=y1;y<y2;y++){
draw a line from x_left>>16 to x_right>>16 , at y
x_left+=d_x_left1;
x_right+=d_x_right1;
}
for(;y<=y3;y++){
draw a line from x_left>>16 to x_right>>16 , at y
x_left+=d_x_left2;
x_right+=d_x_right2;
}

System need to have at least 32-bit int for this to work.
i'm replying there so when someone else asks the same, i'll link this thread....
edit: typos.

Share this post


Link to post
Share on other sites
but the bresenham's algorithm doesn't require floating point computations, and it can be done on 16 bit integers.

Share this post


Link to post
Share on other sites
but it doesn't require floating point. It uses fixed point (same as integer). Except that, it's better to pass vertices as floating point, if you ever want to use it in custom 3D engine or any game....

if your system's native type is 16 bit, and branching is not an issue, yes, bresentham may be better. but do you really code for 16 bit platform?

Share this post


Link to post
Share on other sites
'Bresenham' usually comes with an outdated presentation that barely hides an ultra obvious algo. So much that some may fail to see that it's simply incrementing two coordinates linearilly :

When a line is rather horizontal
for(x=xmin; x<=xmax; x++){ y+=dy; plot((int)x, (int)y); }
(dx implicitely 1, dy a slope)

In floating point, that's all. For fixed point it's simply a matter of >>16 to discretize (<=> (int) cast).

When a line is more vertical :
for(y=ymin; y<=ymax; y++){ x+=dx; plot((int)x, (int)y); }

Usually, only this second case of Bresenham is used for polygonal rasterization. That's Because horizontal spans are rendered, since the video mem is usually a collection of horizontal arrays of pixels. (BTW Doom1, rastered vertically because of ModeX).

The only subtle issue in triangle rasterization, is to be very accurate about discretization.Select only the pixels with a center strictly INSIDE the triangle. Dmytry pointed out the +0.5 trick to have a cheap nearest() function.

But there is also a problem in dealing with ymin. Discretizing the 6 initial coords (3 verts) is one dirty way. You can still start by doing so. Else you must advance from the non discretized ymin to the next line after ymin.

Share this post


Link to post
Share on other sites
@Dmytry
You forgot a detail (important)
(I consider it's a typo since you have the same exact rating as me now ;) )

Quote:
Original post by Dmytry
int d_x_left1 =((x2-x1)<<16)/(y2-y1);
int d_x_right1=((x3-x1)<<16)/(y3-y1);
int d_x_left2 =((x3-x2)<<16)/(y3-y2);

Share this post


Link to post
Share on other sites
i said
Quote:

Assuming x coords is all shifted left by 16 (and optionally incremented by 32768), y coords isn't.

[grin]
I considered to left left shifting outside the algorithm. Because, with floating point coords at input it's needed to do x*65536.0 instead of shifting, etc.

As about Bresenham, no, Bresenham is somewhat different(at least i think so):

Assuming x2>x1 , y2>y1 , 'assuming 'em all to not be shifted.

Simplest, ugly-looking, unoptimized code for "4-connected Bresenham" :
dx=(x2-x1);
dy=(y2-y1);
tmp=0;
x=x1;y=y1;
while( (x<=x2) && (y<=y2) ){
if(tmp>0){
tmp-=dx;
y+=1;
}else{
tmp+=dy;
x+=1;
}
plot(x,y);
}
Think why it work: When (x-x1)*dy-(y-y1)*dx >0, we're in left-down halfspace and need to increment x to get to right-up hanfspace. Otherwise, we need to increment y to get into left down halfspace. Ops, i automatically assumed that y+ arrow points down, like on computer screen in raw pixel access mode [grin].

It's possible to write similar thing for what OP wants, at each step it's needed to increment y by 1, increment x by (dx/dy) at once , increment tmp accordinly to make it be equal to (x-x1)*dy-(y-y1)*dx, and depending to sign of tmp add or not add 1 to x and dy to tmp. But it still have branching, that is, it will probably be slow on modern PCs. It's possible to remove branching by using trick
(a>>32)&b =0 if a>=0 , =b otherwise.

I can write such version but it will take some time and it's easy to make typos, and it's slower and harder to understand than fixed point version. Also it's very hard to explain w/o drawings...

Also, some different but similar algorithms for drawing circles, ellipses, and maybe some other curves is also named after Bresenham..... i probably have implemented 'em all , maybe except unaligned ellipse... will check my old code (in Pascal). I wrote a 2d drawing lib that even had a very-very fast floodfill (out of sport interest).

Share this post


Link to post
Share on other sites
It's true it's not immediatly equivalent algorithmically. It depends on what we call algorithm and implementation. Also I have maybe read other 'versions' abusively called Bresenham, which produce the same output but are closer to the fixed point version, with in fact integer and fractional parts split into two separate integers. Playing with some carries (well bits changing).

Still I am quasi sure it gives the same output (apart numerical precision considerations). Scale dx and dy in your code by 1/dy and see how it looks like. Same behaviour, and with equivalences, simplifications, ... a pen and a paper, see how the code could be simplified ;)

The pros of Besenham are outdated, it was meant to avoid a division, which costed so much 10 years ago and before. So instead of computing dx/dy or dy/dx (whichever is absolutely less than one), the fractional part was dealt with branching. Today having to branch inside the inner loop would cost much more than having one comparison and one division once outside the loop. That's why its deprecated for line drawing or even ellipses or most curves I think. Plus Bresenham would not work well with sub-pixel accurate vertex coords (floating point). It was more for line(int, int, int, int); functions.

Share this post


Link to post
Share on other sites
Quote:
Original post by Charles B
It's true it's not immediatly equivalent algorithmically. It depends on what we call algorithm and implementation. Also I have maybe read other 'versions' abusively called Bresenham, which produce the same output but are closer to the fixed point version, with in fact integer and fractional parts split into two separate integers. Playing with some carries (well bits changing).

Still I am quasi sure it gives the same output (apart numerical precision considerations). Scale dx and dy in your code by 1/dy and see how it looks like. Same behaviour, and with equivalences, simplifications, ... a pen and a paper, see how the code could be simplified ;)

The pros of Besenham are outdated, it was meant to avoid a division, which costed so much 10 years ago and before. So instead of computing dx/dy or dy/dx (whichever is absolutely less than one), the fractional part was dealt with branching. Today having to branch inside the inner loop would cost much more than having one comparison and one division once outside the loop. That's why its deprecated for line drawing or even ellipses or most curves I think. Plus Bresenham would not work well with sub-pixel accurate vertex coords (floating point). It was more for line(int, int, int, int); functions.


Yes,after multiplying by 1/dy we get the same thing.
But i disagree about branching. It can be eliminated. But of course for lines it will be still slower than fixed point version,

First, there's cmov that can be used in things like
tmp>0?dy : dx
and second, we can compute
mask=(tmp>>31); // on PC's , if you shift negative integer right by 32, it's all filled with 1's , and positive is zero
So
a=b+c&mask;
can be used instead of branch.
So for circles i'm sure Bresenham is the fastest method.

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!