EasyCE ->faster line drawing routine

by **MirekCz** » Dec 2, 2001 @ 6:50pm

Ello, I have modified for my own use the EasyCE line drawing routine so it works now with 24:8 fixed math and it has got several modifications to increase performace. As-is it works in 320x240 mode so you will have to make slight changes to make it work with 240x320/whatever you use mode. Hope it will help someone:) PS.If you find some bugs/a way to increase this routine speed feel free to post it. If you find use in this routine feel free to post here, too. I might throw here more routines... #define Abs(A) (((A)>(0))?(A):(-(A))) void DrawLine(int x1,int y1,int x2,int y2,unsigned short color,unsigned short *pWhere) { if (y1>y2) { //switch y1 and y2 int h=y1; y1=y2; y2=h; h=x1; x1=x2; x2=h; } int len=Abs(x2-x1); if (Abs(y2-y1)>len) len=Abs(y2-y1); len=len>>8; if (len!=0) { int dx=(x2-x1)/len; int dy=(y2-y1)/len; if (y1<0) { if (dy>0) { i=-(y1/dy)+1; x1+=dx*i; y1+=dy*i; len-=i; } else len=0; } if (len>0) if (x1<0) { if (dx>0) { i=-(x1/dx)+1; x1+=dx*i; y1+=dy*i; len-=i; } else len=0; } if (len>0) if (y2>(240<<8)) { if (dy>0) { i=((y2-(240<<8))/dy)+1; x2-=dx*i; y2-=dy*i; len-=i; } else len=0; } if (len>0) if (x2>(320<<8)) { if (dx>0) { i=((x2-(320<<8))/dx)+1; x2-=dx*i; y2-=dy*i; len-=i; } else len=0; } for (i=0;i<len;i++) { pWhere[((y1>>8)<<8)+((y1>>8)<<6)+(x1>>8)]=color; x1+=dx; y1+=dy; } } } input - x,y values 24:8 fixed math, 16bit color and a pointer to backbuffer/whatever (currently 320x240, with few simple modifications it will work with 240x320 etc.

by **MirekCz** » Dec 2, 2001 @ 6:51pm

this stupid cigarette-smile is "8 )" , sorry about that... someone should turn it off (and yes, checking "no smilies" doesn't help

by **Digby** » Dec 3, 2001 @ 2:44am

Does this routine of yours draw the last pixel? If I want to draw a 2 pixel line from (0,0) to (0,1), the only pixel that is drawn is at (0,0)? It might be worth it to check for special cases like horizontal and vertical lines early. Your inner loop can be optimized a bit, however there is a faster line drawing algorithm in use these days. Abrash covers this in his book. You basically step along the minor axis instead of the major and then fill a span of pixels at each step. The length of the span will be the same value each time, or one of two alternating values each time. The span lengths are precalculated based on the slope of the line and the direction you're stepping in your inner loop. If you're interested in this algorithm and can't find the Abrash text, let me know and I'll send something your way. I feel your pain with trying to post code on this site. I wish that they would try to be a bit more accommodating to developers here. I don't think other sites like FlipCode.com have these sort of problems.

by **Phantom** » Dec 3, 2001 @ 4:06am

I know of a faster way, it's called Bresenham... Should be quite a lot faster than fixed point line drawing code. There's something even better: Run-length slice line drawing. Anyway, your fixed point code should already be a lot faster than my code.

If you don't mind, I'll add it to EasyCE for the next release. Thanks!

by **MirekCz** » Dec 3, 2001 @ 4:25am

Phantom:np, that's why I have placed it in here anyway:) ohh and doesn't run-length slice line drawing refer to the same thing digby mentioned about Abrash...?:) I will try to optimize it even further later, I will post new code here if I succeed.... trying to write a gourand interpolation poly routine atm:)

by **Digby** » Dec 3, 2001 @ 4:54am

Mirek, Run-length slice line drawing is what I was referring to in my earlier post. Here's a link to containing Abrash's chapter explaining how it is implemented: . I've written software rasterizers a few years ago. Gouraud shading is pretty simple, but if you get into a jam, ping either me or Jacco. I know he's done it too. I actually met Henri Gouraud at the 1990 SIGGRAPH in Dallas. Nice guy for a frenchman.

by **MirekCz** » Dec 3, 2001 @ 6:19am

Thanks a lot Digby!:) I will read and hopefully implement it later tommorow or so... trying to get a simple 3d engine to work today:) Gourand is working fine already:))) It works with half the speed of a poly filler... you can see 16bpp mode drawback with larger triangles thru... (hopefully adding texture mapping will make it much less visible, on the other hand IPAQ 12bit display will make it even worse...) ohh well.. I guess I will leave texture mapping for tommorow... it was always hard for me to get it right:) not mentioning perspective correct tmapping.. ohh well:) I will try to get going with a simple 3d engine now... god I will be happy once it starts to work:) btw.How do you implement gourand lighting? (I assume this is the easiest/fastest way to achieve fine results) Currently I'm doing it with 2 normalizations (for spotlights, 1 for omni light) without calculating "shinines" effect.. all those sqrt functions are killing even my duron... anyone knows how to do it faster?(getting rid of at least one sqrt would help heaps)

by **MirekCz** » Dec 3, 2001 @ 6:28am

Digby:hmm, you was right, It was drawing 1 pixel less then it should, corrected it now, here's new source if anyone cares... void DrawLine(int x1,int y1,int x2,int y2,unsigned short color,unsigned short *pWhere) { if (y1>y2) { //switch y1 and y2 int h=y1; y1=y2; y2=h; h=x1; x1=x2; x2=h; } int len=Abs(x2-x1); int dx; int dy; if (Abs(y2-y1)>len) len=Abs(y2-y1); len=len>>8; if (len!=0) { dx=(x2-x1)/len; dy=(y2-y1)/len; } if (y1<0) { if (dy>0) { i=-(y1/dy)+1; x1+=dx*i; y1+=dy*i; len-=i; } else len=0; } if (len>0) if (x1<0) { if (dx>0) { i=-(x1/dx)+1; x1+=dx*i; y1+=dy*i; len-=i; } else len=0; } if (len>0) if (y2>(240<<8)) { if (dy>0) { i=((y2-(240<<8))/dy)+1; x2-=dx*i; y2-=dy*i; len-=i; } else len=0; } if (len>0) if (x2>(320<<8)) { if (dx>0) { i=((x2-(320<<8))/dx)+1; x2-=dx*i; y2-=dy*i; len-=i; } else len=0; } for (i=0;i<len+1;i++) { pWhere[((y1>>8)<<8)+((y1>>8)<<6)+(x1>>8)]=color; x1+=dx; y1+=dy; } } sorry for the &(@(@&*% faces, just replace them with "8 )"

by **Digby** » Dec 3, 2001 @ 2:15pm

Gouraud lighting is probably the cheapest. First, never compute any type of lighting for static geometry that is being lit by a light that never moves. Precompute the lighting values so you don't need to do it each frame. Store a normalized (unit length = 1) normal at each vertex with your geometry. When you go to light the vertex, transform the light into object space, then use a dot product to calculate the cosine of the angle between vertex normal and the light vector. Something a lot of folks forget but any interpolant needs perspective correction - not just textures. This means an additional divide per pixel for the color value. Look at using dithering to improve the look of gouraud shading. I posted something on this a few months ago with example bitmaps of showing how nice a simple dither can look.

EasyCE ->faster line drawing routine

EasyCE ->faster line drawing routine

Re: EasyCE ->faster line drawing routine

Re: EasyCE ->faster line drawing routine

Re: EasyCE ->faster line drawing routine

Re: EasyCE ->faster line drawing routine

Re: EasyCE ->faster line drawing routine

Re: EasyCE ->faster line drawing routine

Re: EasyCE ->faster line drawing routine

Re: EasyCE ->faster line drawing routine

Sort

Forum Description

Moderators:

Forum permissions