[CSDb] - User Forums - EOR filler/linedrawer

Welcome to our latest new user NthSt4r ! (Registered 2025-05-17)

You are not logged in - nap

CSDb User Forums

Forums > C64 Coding > EOR filler/linedrawer

2008-02-12 10:22

Shadow
Account closed

Registered: Apr 2002
Posts: 355

EOR filler/linedrawer

Yeah, I know I am late to the party, but I recently discovered the beauty of the EOR filler!
I had heard the term before but never reflected much on it. Then a while ago I just sat down with a piece of paper and started working on it.
It's just great! Things like how way multicolor mode just falls into place - you can even have transparency etc. Whoever came up with this first was damn smart!
Btw. is the EOR filler a C64 invention, or has it been in use in computer graphics even earlier? I googled for different combinations 'XOR fill, XOR filler, EOR etc.' but nothing much comes up.

Anyway - now to my question: the EOR line drawer. My pseudocode looks something like this:

if(x1==x2) return;
if(x1>x2)
{
	swap([x1,y1] with [x2,y2])
}
xp=x1;
yp=y1;
ya=(y2-y1)/(x2-x1);        
while(xp<x2)
{
	pixel[xp,yp] = pixel[xp,yp] xor COL;
	yp+=ya;
	xp+=1;
}

Then in my implementation I had to divide it further into two cases depending on whether I have increasing or decreasing Y.
Anyway, are there any common optimizations that can be done to this (on an algorithmic level, I know you can unroll the thing etc, I remember reading Horizon doing this in their filledvector for example, but at the moment I'm trying to get the logic itself as clean as possible).
For example the div to calculate the YA is quite expensive, but I can't see anyway to avoid that...

2008-02-12 10:33

JackAsser

Registered: Jun 2002
Posts: 2038

EOR-fillers on C64 simply mimics the behavior of the blitter on the Amiga.

About the div... consider doing x/y = x*1/y = x*invtab[y] etc... Implementing multiplications can be done much much faster than a div. Also if you're careful you may use logaritms, remember that a/b == e^(log(a)-log(b)).

2008-02-12 12:09

Oswald

Registered: Apr 2002
Posts: 5118

you either use bresenham, or slope driven lines, in an unrolled loop fashion. this means you have a piece of code for EACH pixel column on your screen for each 4 cases. then you calculate the entry point according to startx and jump into the unrolled loop, also stick in an rts to endx.

bresenham:

small slope case:

lda actbytecolumn,y
ora #%11000000
sta actbytecolumn,y
txa
adc width
bcc nooverflow
sbc height
iny
nooverflow
tax

big slope case:

lda actbytecolumn,y
ora #%11000000
sta actbytecolumn,y
txa
back
iny
adc width
bcc back
sbc height
tax

width=abs(x1-x2)
height=abs(y1-y2)

I might have mixed up the order of width and height in the example codes. I always use trial and error to find the correct use of them :)

"slope" line:

lda actbytecolumn,y
ora #%11000000
sta actbytecolumn,y
txa
adc lowadd
tax
tya
adc hiadd
tay

lowadd/hiadd are the result of a div, but you can do a div based on LOG and EXP functions, it will be inaccurate but will draw nice lines. when you have your tables right it will look like this:

ldx number1
ldy number2

lda logtable,x
sec
sbc logtable,y
tax
lda exptable_lo,x
sta lowadd
lda exptable_hi,x
sta hiadd

2008-02-12 21:06

Shadow
Account closed

Registered: Apr 2002
Posts: 355

JackAsser: My memory of Amiga coding is very hazy to say the least, but weren't the bitplanes arranged in with bytes increasing in x-direction? To make EOR-fill work then, the blitter would had to do bit-by-bit exclusive or on the bytes?
Well, totally unrelated discussion I guess.

Oswald:
Thanks, some good examples there! My code is pretty much the 'slope' approach, but not unrolled. Seeing your code I realize now that I probably have to go with unrolling, since I probably burn twice as many cycles since I have to fetch the bit-value from a table etc. At first I thought it would eat quite a bit of mem when you want to run double buffered, but I a quick calculation ends up with be something like 17*4*16 bytes per linedrawer, that's not bad at all!

2008-02-12 22:08

JackAsser

Registered: Jun 2002
Posts: 2038

Quote: JackAsser: My memory of Amiga coding is very hazy to say the least, but weren't the bitplanes arranged in with bytes increasing in x-direction? To make EOR-fill work then, the blitter would had to do bit-by-bit exclusive or on the bytes?
Well, totally unrelated discussion I guess.

Oswald:
Thanks, some good examples there! My code is pretty much the 'slope' approach, but not unrolled. Seeing your code I realize now that I probably have to go with unrolling, since I probably burn twice as many cycles since I have to fetch the bit-value from a table etc. At first I thought it would eat quite a bit of mem when you want to run double buffered, but I a quick calculation ends up with be something like 17*4*16 bytes per linedrawer, that's not bad at all!

Well, EOR-filling is just the method of toggeling the filling state depending on the graphics underneith. The fact that you can fill 4 or 8 columns simultaneous on the c64 is just an extra bonus. ;D

2008-02-13 07:03

Oswald

Registered: Apr 2002
Posts: 5118

and 32 on the amiga, to pick some nits :)

2008-02-13 09:23

HCL

Registered: Feb 2003
Posts: 728

About teh double buffering.. Often you don't need to double buffer your line-buffer, since that one is not going to be visible. You just draw your lines, eor-fill into some visible buffer (now *that* one has to be double buffered!), erase your line-buffer (e.g. by drawing the lines again), and start again.

The headache is that a fast (=unrolled) eor-filler needs quite some space, especially if (since) it has to be double buffered. The line-routines almost disappear in comparation. Either you can live with spending a big part of the mem with eor-filler, or you find something better out.

2008-02-13 12:46

Graham
Account closed

Registered: Dec 2002
Posts: 990

Quote: and 32 on the amiga, to pick some nits :)

2-times no :)

The Amiga Blitter is processing 16 bit words, and polygon filling on Amiga works horizontal not vertical so on Amiga only one row at a time is processed not 16 columns.

2008-02-13 12:55

JackAsser

Registered: Jun 2002
Posts: 2038

Quote: 2-times no :)

The Amiga Blitter is processing 16 bit words, and polygon filling on Amiga works horizontal not vertical so on Amiga only one row at a time is processed not 16 columns.

Exactly what I meant. ;D And the bonus on c64 is 4 columns simultaneous. \o/

2008-02-13 14:58

Oswald

Registered: Apr 2002
Posts: 5118

I havent said blitter or horizontal... I was just rather trying to make a slight hint that no blitter is no bonus :)

Refresh

Subscribe to this thread:

You need to be logged in to post in the forum.

Search the forum:
Search for in
All times are CET.

Search CSDb

Advanced

Users Online

TFWP
Carcass
Guests online: 102

Top Demos

1 Next Level  (9.7)
2 13:37  (9.7)
3 Mojo  (9.6)
4 Coma Light 13  (9.6)
5 Codeboys & Endians  (9.6)
6 Edge of Disgrace  (9.6)
7 Signal Carnival  (9.6)
8 Comaland 100%  (9.6)
9 What Is The Matrix 2  (9.6)
10 Uncensored  (9.6)

Top onefile Demos

1 Scan and Spin  (10)
2 At the Cinema  (9.8)
3 Nine  (9.8)
4 Layers  (9.6)
5 Cubic Dream  (9.6)
6 Party Elk 2  (9.6)
7 Datastiltje 2014 Win..  (9.5)
8 Copper Booze  (9.5)
9 Onscreen 5k  (9.5)
10 Libertongo  (9.5)

Top Groups

1 Artline Designs  (9.4)
2 Booze Design  (9.3)
3 Oxyron  (9.3)
4 Performers  (9.3)
5 Censor Design  (9.3)

Top NTSC-Fixers

1 Pudwerx  (10)
2 Stormbringer  (9.7)
3 Fungus  (9.7)
4 Booze  (9.5)
5 Grim Reaper  (9.3)

Page generated in: 1.955 sec.