Line drawing, single plane bitmap

All 680x0 related coding posts in this section please.

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

siriushardware
Captain Atari
Captain Atari
Posts: 347
Joined: Thu Aug 21, 2014 7:55 pm
Location: UK

Line drawing, single plane bitmap

Postby siriushardware » Fri Mar 18, 2016 1:17 am

This query is not actually assembler specific, but there is no 'General coding' subforum. The point is that I need to know how to do this using only the ability to turn on individual pixels one after the other to form a line. Assume there are no OS or Mid / High level language line drawing functions available.

I have a project in mind which is not actually for Atari but for an even older system using a single monochrome bitplane with one bit = 1 pixel on or off. The Atari in hi-rez mode would be an ideal system to test out methods.

I'm OK with how to turn a particular pixel at a particular co-ordinate in a single bitmapped plane on or off, so you can assume I have a pre-existing subroutine which I can call for that purpose. Let's call the subroutine PLOT (X,Y)

Suppose I have a 2D grid of 32 * 32 pixels.

The requirement is for a routine which is to draw a line between X1, Y1 and X2, Y2 when those two co-ordinates can be anywhere in the 32 * 32 grid, any distance apart within the boundaries of the grid, and X2 may have a greater OR lower value than X1, and Y2 may have a greater OR lower value than Y1.

The main problem I have with visualising this is how to translate the slope on a line into the necessary 'three pixels along, one step up, three pixels along, one step up, three pixels along, one step up' action. If I go into mspaint, select the thinnest possible line (one pixel wide) to draw with and zoom in to see what's happening, it pulls some fairly complex patterns in order to get the line to fit between two chosen end points.

Sometimes it's just three along, one down, three along, one down - other times two down, one across, six down, one across, two down, one across, six down, one across with perhaps a shorter group of four at each end in order to make the line between the two points as smooth and direct as possible.

Can anyone suggest a way to calculate the ideal pixel step size / length with which to draw a line between (X1,Y1), (X2, Y2)? Oh, one further problem. Integer maths only. Still possible?

User avatar
troed
Atari God
Atari God
Posts: 1182
Joined: Mon Apr 30, 2012 6:20 pm
Location: Sweden

Re: Line drawing, single plane bitmap

Postby troed » Fri Mar 18, 2016 1:34 am

Use half of the register to store the fraction, half for the integer. When you add, the result of the fractions will "roll over" into the integer part. Draw using only the integer value.

User avatar
mfro
Atari Super Hero
Atari Super Hero
Posts: 663
Joined: Thu Aug 02, 2012 10:33 am
Location: SW Germany

Re: Line drawing, single plane bitmap

Postby mfro » Fri Mar 18, 2016 4:45 am


User avatar
Mikefulton
Captain Atari
Captain Atari
Posts: 169
Joined: Sun Nov 29, 2015 10:27 am

Re: Line drawing, single plane bitmap

Postby Mikefulton » Fri Mar 18, 2016 6:03 am

You're overthinking it. As mfro suggests, look up the Bresenham's algorithm.

mfro wrote:https://en.wikipedia.org/wiki/Bresenham's_line_algorithm


It's a fairly easy algorithm to implement, and after you have it working, then maybe you can make another pass to optimize it.

Zarchos
Captain Atari
Captain Atari
Posts: 183
Joined: Wed May 09, 2012 7:38 pm
Location: FRANCE

Re: Line drawing, single plane bitmap

Postby Zarchos » Fri Mar 18, 2016 6:28 am

Yes use Bresenham's algo and refine it for peculiar slopes if you want to gain speed.
Line clipping is there, I don't know what the others used but I used the Cohen-Sutherland's algo
https://en.wikipedia.org/wiki/Line_clipping
Atari 1040 STE+SATAN, 520ST, 800xl, xegs, Amiga 500, 2000 with 68020, Archimedes, RISC PCs + Iyonix, Omega, BBC B, Atom, Electron, ZX 81, Spectrum 48/128/+2/+3, Speccy2010, Russian clones, Sam Coupe, V6Z80P, QL with accelerators, Enterprise 128, Einstein inc 256, Oric Atmos, MSX 1, 2, Thomson MO5, Amstrads inc CPC+, C 16, 64, 128, VG5000, Apple IIGS and more ! Yes I want to create a museum when I retire.

siriushardware
Captain Atari
Captain Atari
Posts: 347
Joined: Thu Aug 21, 2014 7:55 pm
Location: UK

Re: Line drawing, single plane bitmap

Postby siriushardware » Fri Mar 18, 2016 8:25 am

Thanks gents, I'd never heard of Bresenham's algorithm before - looks to be exactly what I was after.

User avatar
Mikefulton
Captain Atari
Captain Atari
Posts: 169
Joined: Sun Nov 29, 2015 10:27 am

Re: Line drawing, single plane bitmap

Postby Mikefulton » Sat Mar 19, 2016 3:00 am

siriushardware wrote:Thanks gents, I'd never heard of Bresenham's algorithm before - looks to be exactly what I was after.


Anybody doing graphics programming on a retro platform like the ST where they'll be doing raw pixel pushing should become familiar with some of the classic texts on computer graphics algorithms.

http://www.amazon.com/Computer-Graphics ... r+graphics

http://www.amazon.com/Computer-Graphics ... r+graphics

Zarchos
Captain Atari
Captain Atari
Posts: 183
Joined: Wed May 09, 2012 7:38 pm
Location: FRANCE

Re: Line drawing, single plane bitmap

Postby Zarchos » Sat Mar 19, 2016 9:02 am

Mikefulton wrote:
siriushardware wrote:Thanks gents, I'd never heard of Bresenham's algorithm before - looks to be exactly what I was after.


Anybody doing graphics programming on a retro platform like the ST where they'll be doing raw pixel pushing should become familiar with some of the classic texts on computer graphics algorithms.

http://www.amazon.com/Computer-Graphics ... r+graphics

http://www.amazon.com/Computer-Graphics ... r+graphics



Seconded. Add to this list the 'Graphics gems' books.
http://www.realtimerendering.com/resour ... phicsGems/
Atari 1040 STE+SATAN, 520ST, 800xl, xegs, Amiga 500, 2000 with 68020, Archimedes, RISC PCs + Iyonix, Omega, BBC B, Atom, Electron, ZX 81, Spectrum 48/128/+2/+3, Speccy2010, Russian clones, Sam Coupe, V6Z80P, QL with accelerators, Enterprise 128, Einstein inc 256, Oric Atmos, MSX 1, 2, Thomson MO5, Amstrads inc CPC+, C 16, 64, 128, VG5000, Apple IIGS and more ! Yes I want to create a museum when I retire.

mlynn1974
Obsessive compulsive Atari behavior
Obsessive compulsive Atari behavior
Posts: 119
Joined: Mon Mar 03, 2008 10:33 pm
Contact:

Re: Line drawing, single plane bitmap

Postby mlynn1974 » Sun Oct 23, 2016 11:19 pm

I have attached a nice line routine with quite good documentation by Tony of DigiTech.
There is also a version with a nice wrapper for STOS if anyone is interested.

In 1991 I spoke with Tony about this problem because I needed a fast line routine for STOS.
He wrote one in one night! A few weeks later he improved it.
The version I used is LINES2.S but I kept the first version as well.
For interest you can diff DIAGLINE.S and LINE2.S with Beyond Compare to see how he optimised it.
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
mfro
Atari Super Hero
Atari Super Hero
Posts: 663
Joined: Thu Aug 02, 2012 10:33 am
Location: SW Germany

Re: Line drawing, single plane bitmap

Postby mfro » Mon Oct 24, 2016 5:57 am

mlynn1974 wrote:I have attached a nice line routine with quite good documentation by Tony of DigiTech.


I've only had a (very) brief look into that. To me, it doesn't appear to be particularily efficient as it appears to use divisions to calculate the line slope.

Even a very naive Bresenham's implementation doesn't need divisions (only a multiplication * 2 which can easily be achieved by a left shift), so I would consider that faster (and simpler).

mlynn1974
Obsessive compulsive Atari behavior
Obsessive compulsive Atari behavior
Posts: 119
Joined: Mon Mar 03, 2008 10:33 pm
Contact:

Re: Line drawing, single plane bitmap

Postby mlynn1974 » Mon Oct 24, 2016 11:15 pm

According to Tony:
The routine isn't that fast, but it is about 45-50% faster than Powerman's line rout and the Dynamic Duo's rout (although I think that the Dynamic Duo's rout was an old version).

I would also add that it is at least 6 times faster than STOS's built in line draw command.
My pattern test shows small gaps in certain places so it should be fixed\improved but remember this code is 25 years old!

I once converted Bresenham's Line Drawing Algorithm from C to VB6 based on code in this book:
https://www.amazon.co.uk/Programmers-Gu ... 0201624907

I can't remember if I still have the VB code but it would probably take me ages to convert it to 68000 these days.
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
metalages
Atari freak
Atari freak
Posts: 50
Joined: Thu Jun 06, 2013 5:14 pm
Location: France
Contact:

Re: Line drawing, single plane bitmap

Postby metalages » Tue Oct 25, 2016 9:18 am

I have a 68k Luca line drawing routine here (with clipping)
https://github.com/gibs75/demOS/blob/ma ... POLYZOOM.S

When dy > dx this implementation is a bit particular because it draws only one pixel for each column (=> it is designed to perform a xor pass to fill the shape in a post pass) but it should be not too hard to change it into a regular line drawing routine.

Kalms
Retro freak
Retro freak
Posts: 13
Joined: Sat Oct 28, 2006 10:18 am
Location: Linkoping, Sweden
Contact:

Re: Line drawing, single plane bitmap

Postby Kalms » Mon Oct 31, 2016 10:22 pm

I wrote a line routine some time ago. Available here: https://github.com/Kalmalyzer/segmented-line

It is intended for drawing regular lines; not for scanconverting polygons. It uses DDA at its core; pregenerates code segments for rendering 16-pixel runs at different angles, and will first do DDA on the 16-pixel-level, and then do regular per-pixel DDA for the last modulo-16 pixels. It is quick for long lines. There are probably quicker methods if your lines typically are less than 16 pixels long.


Social Media

     

Return to “680x0”

Who is online

Users browsing this forum: No registered users and 2 guests