efficient polygon drawing
Moderators: simonsunnyboy, Mug UK, Zorro 2, Moderator Team
efficient polygon drawing
Hi there,
I have never written a polygon fill routine in 68000. I used the Amiga Blitter to draw lines, but not fill mode.
I have written an polygon drawing utility in C# to help evaluate ways to do this, but the results aren't very encouraging.
A simple triangle in a 320x200 display might have 433 points which have to be filled per scanline.
The aim of this program isn't to make shapes on the PC but to provide data to do it on Atari demos.
Given a polygon of npoints I need to:
1. Use Bresenham's algorithm to get all the points on the lines,
2. Sort by Y and then by X to give up and down and left to right points for each scanline,
3. Fill between the lines.
Now I understand I can optimise the fill routine using limited planes, and having a precalculated table of edge masks and fill 16 pixels at a time using move.w but the sorting routine looks complicated. It also looks as if it could take up a lot of memory.
How on earth did demo programmers on the ST manage to create demos like Tridi and Oxygene's text zoomer in Ooh Crikey What A Scorcher at such a decent frame rate?
I have never written a polygon fill routine in 68000. I used the Amiga Blitter to draw lines, but not fill mode.
I have written an polygon drawing utility in C# to help evaluate ways to do this, but the results aren't very encouraging.
A simple triangle in a 320x200 display might have 433 points which have to be filled per scanline.
The aim of this program isn't to make shapes on the PC but to provide data to do it on Atari demos.
Given a polygon of npoints I need to:
1. Use Bresenham's algorithm to get all the points on the lines,
2. Sort by Y and then by X to give up and down and left to right points for each scanline,
3. Fill between the lines.
Now I understand I can optimise the fill routine using limited planes, and having a precalculated table of edge masks and fill 16 pixels at a time using move.w but the sorting routine looks complicated. It also looks as if it could take up a lot of memory.
How on earth did demo programmers on the ST manage to create demos like Tridi and Oxygene's text zoomer in Ooh Crikey What A Scorcher at such a decent frame rate?
You do not have the required permissions to view the files attached to this post.
Still got, still working: Atari 4Mb STe, 520STFM (x2), 2.5Mb STF, Atari 2600JR, Flashback 8 Gold.
Hardware: Cumana CSA 354, Ultimate Ripper, Blitz Turbo, Synchro Express II (US and UK Versions).
Hardware: Cumana CSA 354, Ultimate Ripper, Blitz Turbo, Synchro Express II (US and UK Versions).
Re: efficient polygon drawing
1. To simplify things, draw triangles instead of polygons, it's a lot simpler. Each triangle is divided up into 2 triangles (one upper and one lower).
2. Don't use Bresenham to scan the edges, use DDA with fixed point arithmetic.
3. Sorting of y coordinates is done only once per triangle.
4. Identification of the left and right edges is only done once per triangle.
5. Lookup tables with precalculated lines for the edges require quite a lot of memory and will lead to imperfections (Omega did this for the Grotesque demo, look carefully and you'll be able to spot the imperfect edges and sometimes odd looking objects). It's a tradeoff I guess.
6. There's quite a few ways of speeding things up. Draw triangles/polygons that are side by side on different planes to avoid having to perform 'or' operations on begin/end words. Use the blitter if available. Fill triangles/polygons vertically rather than horizontally, and so on. A lot of time were put into developing fast routines. It wasn't done over night.
2. Don't use Bresenham to scan the edges, use DDA with fixed point arithmetic.
3. Sorting of y coordinates is done only once per triangle.
4. Identification of the left and right edges is only done once per triangle.
5. Lookup tables with precalculated lines for the edges require quite a lot of memory and will lead to imperfections (Omega did this for the Grotesque demo, look carefully and you'll be able to spot the imperfect edges and sometimes odd looking objects). It's a tradeoff I guess.
6. There's quite a few ways of speeding things up. Draw triangles/polygons that are side by side on different planes to avoid having to perform 'or' operations on begin/end words. Use the blitter if available. Fill triangles/polygons vertically rather than horizontally, and so on. A lot of time were put into developing fast routines. It wasn't done over night.
Daniel, New Beat  http://newbeat.atari.org.
Like demos? Have a look at our new Falcon030 demo It's that time of the year again, or click here to feel the JOY.
Like demos? Have a look at our new Falcon030 demo It's that time of the year again, or click here to feel the JOY.
Re: efficient polygon drawing
If you can use the blitter, there is a way to just draw the outline of the polygon, then make a xor pass vertically from one screen plane on itself one line lower => it will fill the polygon.
I do this here :
https://youtu.be/iNbVcFThTxY?t=18
Sources are here :
https://github.com/gibs75/demOS/blob/ma ... POLYZOOM.S
https://github.com/gibs75/demOS/blob/ma ... POLYZOOM.C
https://github.com/gibs75/demOS/blob/ma ... POLYZOOM.H
I know Nucleus (HMD) has used this technic in the Phototro.
I do this here :
https://youtu.be/iNbVcFThTxY?t=18
Sources are here :
https://github.com/gibs75/demOS/blob/ma ... POLYZOOM.S
https://github.com/gibs75/demOS/blob/ma ... POLYZOOM.C
https://github.com/gibs75/demOS/blob/ma ... POLYZOOM.H
I know Nucleus (HMD) has used this technic in the Phototro.
Re: efficient polygon drawing
Vectors (by Wachu) in both demos are filled with the BLiTTER:
https://www.youtube.com/watch?v=j8VfQirw7FM
https://www.youtube.com/watch?v=66xBWXtsN5Q
The BLiTTER fills a line by line, all 4 bitplanes in one go. Endmask1/3 used to mask the beginning and the ending of the line. Halftone registers are used for choosing valid color (any of sixteen colors).
https://www.youtube.com/watch?v=j8VfQirw7FM
https://www.youtube.com/watch?v=66xBWXtsN5Q
The BLiTTER fills a line by line, all 4 bitplanes in one go. Endmask1/3 used to mask the beginning and the ending of the line. Halftone registers are used for choosing valid color (any of sixteen colors).
Lynx I / Mega ST 1 / 7800 / Portfolio / Lynx II / Jaguar / TT030 / Mega STe / 800 XL / 1040 STe / Falcon030 / 65 XE / 520 STm / SM124 / SC1435
DDD HDD / AT Speed C16 / TF536 / SDrive / PAK68/3 / Lynx Multi Card / LDW Super 2000 / XCA12 / SkunkBoard / CosmosEx / SatanDisk / UltraSatan / USB Floppy Drive Emulator / Eiffel / SIO2PC / Crazy Dots / PAM Net
Hatari / Steem SSE / Aranym / Saint
http://260ste.atari.org
DDD HDD / AT Speed C16 / TF536 / SDrive / PAK68/3 / Lynx Multi Card / LDW Super 2000 / XCA12 / SkunkBoard / CosmosEx / SatanDisk / UltraSatan / USB Floppy Drive Emulator / Eiffel / SIO2PC / Crazy Dots / PAM Net
Hatari / Steem SSE / Aranym / Saint
http://260ste.atari.org

 Fuji Shaped Bastard
 Posts: 3115
 Joined: Sun Aug 03, 2014 5:54 pm
Re: efficient polygon drawing
The real fun starts with polygons like this:
You do not have the required permissions to view the files attached to this post.
Re: efficient polygon drawing
That's when you draw it using triangles instead!ThorstenOtto wrote:The real fun starts with polygons like this:
Screenshot_20181012_023354.png
Daniel, New Beat  http://newbeat.atari.org.
Like demos? Have a look at our new Falcon030 demo It's that time of the year again, or click here to feel the JOY.
Like demos? Have a look at our new Falcon030 demo It's that time of the year again, or click here to feel the JOY.
Re: efficient polygon drawing
Thanks for the helpful advice. I've never seen that Cybernetics demo before. Definitely a lot of food for thought in those demos.
Still got, still working: Atari 4Mb STe, 520STFM (x2), 2.5Mb STF, Atari 2600JR, Flashback 8 Gold.
Hardware: Cumana CSA 354, Ultimate Ripper, Blitz Turbo, Synchro Express II (US and UK Versions).
Hardware: Cumana CSA 354, Ultimate Ripper, Blitz Turbo, Synchro Express II (US and UK Versions).
Re: efficient polygon drawing
I think most of the things that are important are already mentioned by Daniel.
In terms of speed, most cpu time is usually spend on the filling. This can be done horizontally (per scanline) or vertically (per yblock).
Pulse contains both a xorfiler (for the cube) and a hline filler (for the tunnel) that you can have a look at for the implementations.
https://github.com/ggnkua/Atari_ST_Sour ... ulsemain.s :8900 for xorfiller and dda linedraw
https://github.com/ggnkua/Atari_ST_Sour ... ulsemain.s :14008 for a generalized polygon routine that translates a polygon onto an edgelist (xstart and xend per scanline), for it then to fill.
Other than writing `very optimized' fill routines, you can also try and limit the amount of area that needs filling each frame; for example by only filling the difference between the frames (not sure how this is called); but Rapido did this in the Synergy 3d code (publication of source pending).
In terms of speed, most cpu time is usually spend on the filling. This can be done horizontally (per scanline) or vertically (per yblock).
Pulse contains both a xorfiler (for the cube) and a hline filler (for the tunnel) that you can have a look at for the implementations.
https://github.com/ggnkua/Atari_ST_Sour ... ulsemain.s :8900 for xorfiller and dda linedraw
https://github.com/ggnkua/Atari_ST_Sour ... ulsemain.s :14008 for a generalized polygon routine that translates a polygon onto an edgelist (xstart and xend per scanline), for it then to fill.
Other than writing `very optimized' fill routines, you can also try and limit the amount of area that needs filling each frame; for example by only filling the difference between the frames (not sure how this is called); but Rapido did this in the Synergy 3d code (publication of source pending).
 BoNuS
 Atari Super Hero
 Posts: 785
 Joined: Mon Jan 19, 2009 12:45 pm
 Location: The Netherlands
 Contact:
Re: efficient polygon drawing
I thought you got the sources from the Synergy demo, there is a lot of polygon drawing (maybe even the best) in there ?
http://bonus.home.xs4all.nl/
( I have just to much Atari stuff)
( I have just to much Atari stuff)
Re: efficient polygon drawing
Thanks mlynn.
Feel free to ask if you need more info.
Feel free to ask if you need more info.
Re: efficient polygon drawing
How is the XOR filler done? Sounds interessting to try it out with the blitter? But I can't see how it can automatically draw a line? It seems like all that will happen is that black pixels turn white (0 to 1) and the opposite. Nothing else.
ST / STFM / STE / Mega STE / Falcon / TT030 / Portfolio / 2600 / 7800 / Jaguar / 600xl / 130xe
Re: efficient polygon drawing
You first have to draw the outline of the polygon using a line drawing routine, and then perform the XOR pass.
Last edited by dhedberg on Wed Nov 07, 2018 10:33 pm, edited 1 time in total.
Daniel, New Beat  http://newbeat.atari.org.
Like demos? Have a look at our new Falcon030 demo It's that time of the year again, or click here to feel the JOY.
Like demos? Have a look at our new Falcon030 demo It's that time of the year again, or click here to feel the JOY.
Re: efficient polygon drawing
you copy a full bitplane on itself in xor mode with blitter with destadr = sourceadr + line size (160 bytes for instance). what it does is to make the horizontal borders of the outline working as a toggle fill / do not fill
Re: efficient polygon drawing
Take a look at this siggraph paper cowritten by Rob Pike no less. XOR filling is described at page 18 onwards, but I recommend reading the full paper as there are many more interesting tricks you can do with bitblt!Zamuel_a wrote:How is the XOR filler done? Sounds interessting to try it out with the blitter? But I can't see how it can automatically draw a line? It seems like all that will happen is that black pixels turn white (0 to 1) and the opposite. Nothing else.
That's still doable with a single pass XOR fill btw.ThorstenOtto wrote:The real fun starts with polygons like this:
is 73 Falcon patched atari games enough ? ^^
Re: efficient polygon drawing
But that would just invert the drawn outlines?. Not fill it. If I have a black screen (0) and for a horizontal line have two white pixels on it (1) (start and end pixels for that line) and XOR that with a line filled with white (1) I would get 0 XOR 1 = 1 for the beginning on the line and to my pixel. The pixel would be black 1 XOR 1 and the fill between would be 0 XOR 1 = white. End piel black and the remaining screen white. So it's a inverse, not a fill.you copy a full bitplane on itself in xor mode with blitter with destadr = sourceadr + line size (160 bytes for instance). what it does is to make the horizontal borders of the outline working as a toggle fill / do not fill
ST / STFM / STE / Mega STE / Falcon / TT030 / Portfolio / 2600 / 7800 / Jaguar / 600xl / 130xe
Re: efficient polygon drawing
Here i only draw the outline of the letter and do a xor pass to fillb the rotating logo. https://youtu.be/iNbVcFThTxY?t=18
You just have to be careful when drawing lines when dy is greater than dx. In this case you need a line draw than put only one pixel for each x. This is not a regular line draw in these cases.
It works because the xored state propagates from one line to the other. You will have 0 xor 1 gives 1. Next line you will have 1 xor 0 gives 1 and this will go on till you meet another outline doing 1 xor 1 gives 0.
It propagates because your dest address = source address + one line pitch (probably 160 bytes)
You just have to be careful when drawing lines when dy is greater than dx. In this case you need a line draw than put only one pixel for each x. This is not a regular line draw in these cases.
It works because the xored state propagates from one line to the other. You will have 0 xor 1 gives 1. Next line you will have 1 xor 0 gives 1 and this will go on till you meet another outline doing 1 xor 1 gives 0.
It propagates because your dest address = source address + one line pitch (probably 160 bytes)
Re: efficient polygon drawing
Okay, so you make an XOR with the previous (or next?) drawn line on the screen. I can see that it might work for some occasions, but not all of them. If the drawn outline is filled in the pixel above and the current pixel is also filled, when the new pixel will be zero so it can't work. I guess I miss something, but I can't find any information on this when I try to google it. It seems like a smart trick, if I can figure it out.
For example:
0000001100000
0000010010000
0000100001000
0000010010000
0000001100000
If I XOR the current line with the previous once I would get:
0000001100000
0000011110000
0000111111000
00000*11*0000 < Here we get 1 XOR 1 = 0 so the outline is removed.
000000**00000 <
If I would OR instead of XOR it looks like it might work.
For example:
0000001100000
0000010010000
0000100001000
0000010010000
0000001100000
If I XOR the current line with the previous once I would get:
0000001100000
0000011110000
0000111111000
00000*11*0000 < Here we get 1 XOR 1 = 0 so the outline is removed.
000000**00000 <
If I would OR instead of XOR it looks like it might work.
ST / STFM / STE / Mega STE / Falcon / TT030 / Portfolio / 2600 / 7800 / Jaguar / 600xl / 130xe
Re: efficient polygon drawing
Another trick to have this working is to draw the lines using "xor" instead of "or" to avoid having 1 pixel edges
In your case it means you would have an outline looking like this :
001100
010010
000000
010010
001100
In your case it means you would have an outline looking like this :
001100
010010
000000
010010
001100
Re: efficient polygon drawing
I made a quick XOR draw test on my PC and it almost works. I draw a triangle with lines and XOR each line with the previous one after that. That actually filled the triangle, but at the edges it draws a vertical line to the bottom of the screen. Since the edges of a triangle is just one pixel. I tried to XOR instead of OR the pixels so that any new pixels that get drawn on top of a current ones turn into zero and it helped a little. Still it's not 100% "safe", but I guess I need to find a good line draw routine that works.
ST / STFM / STE / Mega STE / Falcon / TT030 / Portfolio / 2600 / 7800 / Jaguar / 600xl / 130xe
Re: efficient polygon drawing
I made a quick XOR draw test on my PC and it almost works. I draw a polygon with lines and XOR each line with the previous one after that. That actually filled the triangle, but at the edges it draws a vertical line to the bottom of the screen. Since the edges of a triangle is just one pixel. I tried to XOR instead of OR the pixels so that any new pixels that get drawn on top of a current ones turn into zero and it helped a little. Still it's not 100% "safe".
For example if the polygon bottom pixel is removed in the line routine, that leaves a hole and the filler fills to the bottom of the screen. So how to solve that without a lot of special checks after the object is drawn to fill in gaps and remove unnecessary pixels. For this to be efficient I guess it has to be as automatic as possible.
I did this simple program in C:
(my plot routine plots to a RGB screen with the same value for all components so 255 = white in my test)
For example if the polygon bottom pixel is removed in the line routine, that leaves a hole and the filler fills to the bottom of the screen. So how to solve that without a lot of special checks after the object is drawn to fill in gaps and remove unnecessary pixels. For this to be efficient I guess it has to be as automatic as possible.
I did this simple program in C:
(my plot routine plots to a RGB screen with the same value for all components so 255 = white in my test)
Code: Select all
void line(int x1, int y1, int x2, int y2)
{
float dydx;
float y;
int x;
dydx = (float)(y2  y1) / (float)(x2  x1);
y = y1;
for (x = x1; x <= x2; x++)
{
Plot(x, (int)y, 255 ^ GetPixel(x, (int)y));
y += dydx;
}
}
void XORfill()
{
int x, y;
BYTE color1, color2, final_color;
line(10, 10, 250, 100);
line(150, 150, 250, 100);
line(80, 250, 150, 150);
line(10, 10, 80, 250);
for (y = 0; y < 300; y++)
{
for (x = 0; x < 320; x++)
{
color1 = testGetPixel(x, y);
color2 = testGetPixel(x, y1);
final_color = color1^color2;
Plot(x, y, final_color);
}
}
}
ST / STFM / STE / Mega STE / Falcon / TT030 / Portfolio / 2600 / 7800 / Jaguar / 600xl / 130xe
Re: efficient polygon drawing
I have not made special checks / cases except :
 for the clipping routine : when the polygon exits the screen at top, I draw an horizontal line y=0 for the corresponding abscisses
 as said before, for lines where dy > dx, I have a different line routine that draw only one pixel for each x
But except that, my line routine is based on a regular Lucas algorithm
https://github.com/gibs75/demOS/blob/ma ... POLYZOOM.S
And I think I have done nothing special on coordinates precompute
https://github.com/gibs75/demOS/blob/ma ... POLYZOOM.C
I have also used a xor pass for image compression here (just compress the outline of the logo in RLE then refill at runtime after outline decompress)
https://youtu.be/Gbq4wI9HsEw
 for the clipping routine : when the polygon exits the screen at top, I draw an horizontal line y=0 for the corresponding abscisses
 as said before, for lines where dy > dx, I have a different line routine that draw only one pixel for each x
But except that, my line routine is based on a regular Lucas algorithm
https://github.com/gibs75/demOS/blob/ma ... POLYZOOM.S
And I think I have done nothing special on coordinates precompute
https://github.com/gibs75/demOS/blob/ma ... POLYZOOM.C
I have also used a xor pass for image compression here (just compress the outline of the logo in RLE then refill at runtime after outline decompress)
https://youtu.be/Gbq4wI9HsEw
Re: efficient polygon drawing
Does your testgetpixel gives 0 when y == 1 ?
Re: efficient polygon drawing
I think that you must be sure that if you draw a line in xor mode from (0,0 to 100,100) and another line from (100, 100 to 120, 150), the pixel at (100, 100) it's drawn only one time.
Re: efficient polygon drawing
I draw the lines with xor instead of or so end pixels that overlap will be black. That doesnt solve all problems and I guess polygons will have holes in the corners since the pixels arent drawn.
Since I draw the lines one pixel in x each time I dont have to take special care if dy>dx. But end pixels that consists of two vertical pixels without any black pixels between results in a vertical line that extends to the bottom of the screen.
Since I draw the lines one pixel in x each time I dont have to take special care if dy>dx. But end pixels that consists of two vertical pixels without any black pixels between results in a vertical line that extends to the bottom of the screen.
ST / STFM / STE / Mega STE / Falcon / TT030 / Portfolio / 2600 / 7800 / Jaguar / 600xl / 130xe
Re: efficient polygon drawing
in my routine I draw in order A > B > C > D > ... > A
have you tried drawing from x1 to < x2 ? instead of <= x2 ?
I think I do something like that because of this part : if dx = 0 => do nothing and if dy = 0 => hline
have you tried drawing from x1 to < x2 ? instead of <= x2 ?
I think I do something like that because of this part : if dx = 0 => do nothing and if dy = 0 => hline
Code: Select all
trace:
lea pitch.w,a2 *
sub.w d2,d0 * d0: width
beq.s return * if dx = 0 => do nothing
neg.w d0 *
sub.w d3,d1 * d1: height
beq h_line * if dy = 0 => hline
blt.s trace_ok *
lea pitch.w,a2 * if dy negative => invert address increment
neg.w d1 * abs (dy)
trace_ok:
neg.w d1 *
lea pitchmul(pc),a1 * compute start address : a0 += y2 * pitch
add.w d3,d3 *
move.w (a1,d3.w),d3 *
; add.w d3,d3 * (pitch / 2) * 2
add.w d3,a0
cmp.w d0,d1 * Compare dx & dy
; blt.s horizontal * => dx > dy => horizontal routine
bgt vertical * => dy > dx => vertical routine
beq d45 * => equal => 45° routine