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: 203
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: 801
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: 122
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: 1504
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: 399
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: 801
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: 203
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: 220
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: 735
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)


Social Media

     

Return to “680x0”

Who is online

Users browsing this forum: No registered users and 2 guests