efficient polygon drawing

[mlynn1974]

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?

[dhedberg]

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.

[metalages]

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.

[Cyprian]

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

[ThorstenOtto]

The real fun starts with polygons like this:

Screenshot_20181012_023354.png

[dhedberg]

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

That's when you draw it using triangles instead!

[mlynn1974]

Thanks for the helpful advice. I've never seen that Cybernetics demo before. Definitely a lot of food for thought in those demos.

[wietze]

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

[BoNuS]

I thought you got the sources from the Synergy demo, there is a lot of polygon drawing (maybe even the best) in there ?

[metalages]

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

[Zamuel_a]

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.

[dhedberg]

You first have to draw the outline of the polygon using a line drawing routine, and then perform the XOR pass.

[metalages]

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

[ggn]

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!

The real fun starts with polygons like this:

Screenshot_20181012_023354.png

That's still doable with a single pass XOR fill btw.

[Zamuel_a]

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.

[metalages]

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]

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.

[metalages]

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]

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.

[Zamuel_a]

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);
      }

   }
}






[metalages]

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

[metalages]

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

[swapd0]

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]

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.

[metalages]

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