| |
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...
|
|
| |
JackAsser
Registered: Jun 2002
Posts: 2014 |
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)).
|
| |
Oswald
Registered: Apr 2002
Posts: 5094 |
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 |
| |
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! |
| |
JackAsser
Registered: Jun 2002
Posts: 2014 |
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 |
| |
Oswald
Registered: Apr 2002
Posts: 5094 |
and 32 on the amiga, to pick some nits :) |
| |
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. |
| |
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. |
| |
JackAsser
Registered: Jun 2002
Posts: 2014 |
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/ |
| |
Oswald
Registered: Apr 2002
Posts: 5094 |
I havent said blitter or horizontal... I was just rather trying to make a slight hint that no blitter is no bonus :) |
