efficient polygon drawing

All 680x0 related coding posts in this section please.

Moderators: simonsunnyboy, Mug UK, Zorro 2, Moderator Team

mlynn1974
Captain Atari
Captain Atari
Posts: 210
Joined: Mon Mar 03, 2008 10:33 pm
Contact:

efficient polygon drawing

Postby mlynn1974 » Wed Oct 10, 2018 11:21 pm

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 n-points 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, 2.5Mb STF.
Hardware: Cumana CSA 354, Ultimate Ripper, Blitz Turbo, Synchro Express II (US and UK Versions).

User avatar
dhedberg
Atari Super Hero
Atari Super Hero
Posts: 832
Joined: Mon Aug 30, 2010 8:36 am
Contact:

Re: efficient polygon drawing

Postby dhedberg » Wed Oct 10, 2018 11:39 pm

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. Look-up tables with pre-calculated 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 trade-off 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 MORE.

User avatar
metalages
Obsessive compulsive Atari behavior
Obsessive compulsive Atari behavior
Posts: 130
Joined: Thu Jun 06, 2013 5:14 pm
Location: France
Contact:

Re: efficient polygon drawing

Postby metalages » Thu Oct 11, 2018 7:55 pm

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.

User avatar
Cyprian
Atari God
Atari God
Posts: 1518
Joined: Fri Oct 04, 2002 11:23 am
Location: Warsaw, Poland

Re: efficient polygon drawing

Postby Cyprian » Thu Oct 11, 2018 9:39 pm

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).
Jaugar / TT030 / Mega STe / 800 XL / 1040 STe / Falcon030 / 65 XE / 520 STm / SM124 / SC1435
SDrive / PAK68/3 / CosmosEx / SatanDisk / UltraSatan / USB Floppy Drive Emulator / Eiffel / SIO2PC / Crazy Dots / PAM Net
Hatari / Steem SSE / Aranym / Saint
http://260ste.appspot.com/

ThorstenOtto
Captain Atari
Captain Atari
Posts: 448
Joined: Sun Aug 03, 2014 5:54 pm

Re: efficient polygon drawing

Postby ThorstenOtto » Fri Oct 12, 2018 12:36 am

The real fun starts with polygons like this:
Screenshot_20181012_023354.png
You do not have the required permissions to view the files attached to this post.

User avatar
dhedberg
Atari Super Hero
Atari Super Hero
Posts: 832
Joined: Mon Aug 30, 2010 8:36 am
Contact:

Re: efficient polygon drawing

Postby dhedberg » Fri Oct 12, 2018 9:03 am

ThorstenOtto wrote:The real fun starts with polygons like this:
Screenshot_20181012_023354.png

That's when you draw it using triangles instead! ;-)
Daniel, New Beat - http://newbeat.atari.org. Like demos? Have a look at our new Falcon030 demo MORE.

mlynn1974
Captain Atari
Captain Atari
Posts: 210
Joined: Mon Mar 03, 2008 10:33 pm
Contact:

Re: efficient polygon drawing

Postby mlynn1974 » Fri Oct 12, 2018 11:32 pm

Thanks for the helpful advice. I've never seen that Cybernetics demo before. Definitely a lot of food for thought in those demos.
:coffe:
Still got, still working: Atari 4Mb STe, 520STFM, 2.5Mb STF.
Hardware: Cumana CSA 354, Ultimate Ripper, Blitz Turbo, Synchro Express II (US and UK Versions).

wietze
Captain Atari
Captain Atari
Posts: 221
Joined: Fri Mar 01, 2013 10:52 pm

Re: efficient polygon drawing

Postby wietze » Sat Oct 13, 2018 8:58 am

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 y-block).

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).

User avatar
BoNuS
Atari Super Hero
Atari Super Hero
Posts: 749
Joined: Mon Jan 19, 2009 12:45 pm
Location: The Netherlands
Contact:

Re: efficient polygon drawing

Postby BoNuS » Sat Oct 13, 2018 9:10 am

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/
2 x Falcon 030 - a mint Atari TT - Mega STE - 2x STE - 1x Mega 2 - 2x STFM - 1 x STF - 3x SC1224 - 2x SM124 - 1x SM125 2x Portofolio+interface
- 3x 1435 monitor - 1 x Ult.Ripper cardridge - Mega 1,2,and 4 ( just to much Atari stuff)

User avatar
metalages
Obsessive compulsive Atari behavior
Obsessive compulsive Atari behavior
Posts: 130
Joined: Thu Jun 06, 2013 5:14 pm
Location: France
Contact:

Re: efficient polygon drawing

Postby metalages » Mon Oct 22, 2018 9:52 pm

Thanks mlynn.
Feel free to ask if you need more info.

Zamuel_a
Atari God
Atari God
Posts: 1234
Joined: Wed Dec 19, 2007 8:36 pm
Location: Sweden

Re: efficient polygon drawing

Postby Zamuel_a » Wed Nov 07, 2018 4:16 pm

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

User avatar
dhedberg
Atari Super Hero
Atari Super Hero
Posts: 832
Joined: Mon Aug 30, 2010 8:36 am
Contact:

Re: efficient polygon drawing

Postby dhedberg » Wed Nov 07, 2018 4:22 pm

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 MORE.

User avatar
metalages
Obsessive compulsive Atari behavior
Obsessive compulsive Atari behavior
Posts: 130
Joined: Thu Jun 06, 2013 5:14 pm
Location: France
Contact:

Re: efficient polygon drawing

Postby metalages » Wed Nov 07, 2018 10:31 pm

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

User avatar
ggn
Atari God
Atari God
Posts: 1207
Joined: Sat Dec 28, 2002 4:49 pm

Re: efficient polygon drawing

Postby ggn » Thu Nov 08, 2018 6:37 am

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.


Take a look at this siggraph paper co-written 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!

ThorstenOtto wrote:The real fun starts with polygons like this:
Screenshot_20181012_023354.png


That's still doable with a single pass XOR fill btw.
is 73 Falcon patched atari games enough ? ^^

Zamuel_a
Atari God
Atari God
Posts: 1234
Joined: Wed Dec 19, 2007 8:36 pm
Location: Sweden

Re: efficient polygon drawing

Postby Zamuel_a » Thu Nov 08, 2018 7:47 am

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


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.
ST / STFM / STE / Mega STE / Falcon / TT030 / Portfolio / 2600 / 7800 / Jaguar / 600xl / 130xe

User avatar
metalages
Obsessive compulsive Atari behavior
Obsessive compulsive Atari behavior
Posts: 130
Joined: Thu Jun 06, 2013 5:14 pm
Location: France
Contact:

Re: efficient polygon drawing

Postby metalages » Thu Nov 08, 2018 11:14 pm

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)

Zamuel_a
Atari God
Atari God
Posts: 1234
Joined: Wed Dec 19, 2007 8:36 pm
Location: Sweden

Re: efficient polygon drawing

Postby Zamuel_a » Fri Nov 09, 2018 12:52 pm

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.
ST / STFM / STE / Mega STE / Falcon / TT030 / Portfolio / 2600 / 7800 / Jaguar / 600xl / 130xe

User avatar
metalages
Obsessive compulsive Atari behavior
Obsessive compulsive Atari behavior
Posts: 130
Joined: Thu Jun 06, 2013 5:14 pm
Location: France
Contact:

Re: efficient polygon drawing

Postby metalages » Fri Nov 09, 2018 8:34 pm

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

Zamuel_a
Atari God
Atari God
Posts: 1234
Joined: Wed Dec 19, 2007 8:36 pm
Location: Sweden

Re: efficient polygon drawing

Postby Zamuel_a » Tue Nov 13, 2018 11:15 pm

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

Zamuel_a
Atari God
Atari God
Posts: 1234
Joined: Wed Dec 19, 2007 8:36 pm
Location: Sweden

Re: efficient polygon drawing

Postby Zamuel_a » Tue Nov 13, 2018 11:43 pm

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)

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, y-1);

         final_color = color1^color2;

         Plot(x, y, final_color);
      }

   }
}




ST / STFM / STE / Mega STE / Falcon / TT030 / Portfolio / 2600 / 7800 / Jaguar / 600xl / 130xe

User avatar
metalages
Obsessive compulsive Atari behavior
Obsessive compulsive Atari behavior
Posts: 130
Joined: Thu Jun 06, 2013 5:14 pm
Location: France
Contact:

Re: efficient polygon drawing

Postby metalages » Thu Nov 15, 2018 11:04 pm

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

User avatar
metalages
Obsessive compulsive Atari behavior
Obsessive compulsive Atari behavior
Posts: 130
Joined: Thu Jun 06, 2013 5:14 pm
Location: France
Contact:

Re: efficient polygon drawing

Postby metalages » Fri Nov 16, 2018 7:16 am

Does your testgetpixel gives 0 when y == -1 ?

swapd0
Atari freak
Atari freak
Posts: 60
Joined: Thu Dec 13, 2007 8:56 pm

Re: efficient polygon drawing

Postby swapd0 » Fri Nov 16, 2018 11:11 am

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.

Zamuel_a
Atari God
Atari God
Posts: 1234
Joined: Wed Dec 19, 2007 8:36 pm
Location: Sweden

Re: efficient polygon drawing

Postby Zamuel_a » Fri Nov 16, 2018 1:41 pm

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.
ST / STFM / STE / Mega STE / Falcon / TT030 / Portfolio / 2600 / 7800 / Jaguar / 600xl / 130xe

User avatar
metalages
Obsessive compulsive Atari behavior
Obsessive compulsive Atari behavior
Posts: 130
Joined: Thu Jun 06, 2013 5:14 pm
Location: France
Contact:

Re: efficient polygon drawing

Postby metalages » Fri Nov 16, 2018 7:33 pm

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

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


Social Media

     

Return to “680x0”

Who is online

Users browsing this forum: No registered users and 1 guest