| | Scout
Registered: Dec 2002
Posts: 1570 |
3D projection on the C=64 (or...how do I divide?)
Hi!
After 12 years I picked up coding again on the C=64.
What I want to make is a simple 3D starfield.
I know something about 3D programming, so that's no issue.
The only thing I stumbled on is how to implement 3D projection (X1=X/Z) and especially the dividing part of it.
How can I implement this on the C=64?
Any hints, tips?
Thanx!
R.
(Asm on the PC is so much easier ;-) |
|
... 25 posts hidden. Click here to view all posts....
|
| | WVL
Registered: Mar 2002
Posts: 902 |
Quote: logtable-values stay small if i made it right...hmmm
but how you calculate the expttable?
i wanna divide 255 by 255 but precalc
in basic fails due ?exp(x) goes BIIIG fast.
T.
short answer :
don't use log10 or ln, but choose a smart base for your logarithm instead. Hint : make sure the maximum value of your log-table is $ff (I always use 2 bytes, so my max value is $ffff). This way you get the most accuracy from your table. |
| | tecM0
Registered: Jan 2002
Posts: 40 |
log (basic v2) stay under 6 for $ff isnt this right?
the problem is the EXP :(
T. |
| | WVL
Registered: Mar 2002
Posts: 902 |
Quote: log (basic v2) stay under 6 for $ff isnt this right?
the problem is the EXP :(
T.
But you want log($FF) to be $FF for biggest accuracy. Values ranging from 0->6 give no room to undo the logarithm.
To find out what your base should be, you can use the following equation :
loga(x)/loga(b)=logb(x)
as an example, we want logb(255)=255, what should b be?
logb(255)=255=log10(255)/log10(b) =>
log10(b)=log10(255)/255=0,009437 =>
b=1,02 (roughly)
So log1,02(255)=255.
in other words, for c64 stuff, forget about using 10 or e as base, 10^(log10(255)/255) is the real base of choice :D
|
| | AmiDog
Registered: Mar 2003
Posts: 97 |
Has anyone tried the "multiply with scaled reciprocal" approach for division?
Using an 8-bit table, some bitshifting and a 8x8 multiply (using the table of squares method) one should get a 100% accurate quotient. |
| | John West
Account closed
Registered: Aug 2004
Posts: 4 |
Quoting AmiDogHas anyone tried the "multiply with scaled reciprocal" approach for division?
It's not quite 100% accurate, but it's never more than one out. It gets more results exactly right if the reciprocal table is rounded, so you're calculating floor((x*floor(0.5+256/y))/256). The rounding can be built into the table, so it's no more work. |
| | Graham
Account closed
Registered: Dec 2002
Posts: 990 |
1 off is ok, remember that you have an error in that range anyway due to rounding.
Oh and btw, I use X*(1/Y) too when I need a fast div. |
| | John West
Account closed
Registered: Aug 2004
Posts: 4 |
... and if you don't mind it being up to two out, you don't need to calculate the low byte of the multiply. That saves a few cycles. |
| | AmiDog
Registered: Mar 2003
Posts: 97 |
Well, you do need an 9-bit reciprocal to get a 100% accurate result, but as the msb of the reciprocal is always one, you don't need to store it anywhere, and a multiply by 256 is just an add. Some C-code:
/* 9-bit reciprocal table, but msb is always one and not stored */
unsigned char r0[128];
void build_table(void)
{
unsigned long i, d, r;
for (i=0; i<128; i++) {
d = i | 0x80; /* 1 < d < 2 */
r = 0x80000000 / (d << 8); /* 1 / d -> 1/2 < r < 1 */
r += 0x80; /* round the reciprocal */
r <<= 1; /* remove constant 1-bit */
r0[i] = (unsigned char)(r >> 8);
}
}
unsigned char div8(unsigned char a, unsigned char b)
{
int log = 7;
/* division by one need to be handled separately */
if (b == 1) {
return a;
}
/* normalize b so that 1 <= b < 2 */
while (!(b & 0x80)) {
b <<= 1;
log--;
}
/* if b is a power of two */
if (b == 0x80) {
return a >> log;
}
/* msb is always one, so don't use it for indexing (save some memory) */
unsigned char r = r0[b & 0x7f];
/* now multiply */
unsigned short ar = (unsigned short)a * (unsigned short)r;
ar >>= 8;
ar += (unsigned short)a; /* ar is now an 9-bit value */
ar >>= (log + 1);
return (unsigned char)ar;
}
This has been tested and is 100% accurate. I don't know how fast/slow it will be when translated to 6502 code. Maybe adding a table or two for the normalizing step could help. |
| | AmiDog
Registered: Mar 2003
Posts: 97 |
Just noticed that a divide by zero will cause an endless loop, so better replace:
if (b == 1) {
return a;
}
with
if (b <= 1) {
return a;
}
to avoid the endless loop. The result of a divide by zero is usually considered undefined anyway, so it doesn't really matter what we return... |
| | AmiDog
Registered: Mar 2003
Posts: 97 |
I just couldn't control myself, here's some 6502 code:
_divu_8
lda div_b
cmp #2
bcs + ; >= 2
lda div_a
rts
+ ldx #8
- dex
asl
bcc -
bne +
lda div_a
- lsr
dex
bne -
rts
+ tay
lda r0_table,y
ldy div_a
sta zp8_1
sta zp8_2
eor #$ff
sta zp8_3
sta zp8_4
sec
lda (zp8_1),y
sbc (zp8_3),y
lda (zp8_2),y
sbc (zp8_4),y
clc
adc div_a
ror
- lsr
dex
bne -
rts
div_a
.byte $0
div_b
.byte $0
r0_table
.byte $01,$00,$fd,$00,$f9,$00,$f5,$00,$f1,$00,$ed,$00,$ea,$00,$e6,$00
.byte $e2,$00,$df,$00,$db,$00,$d8,$00,$d5,$00,$d1,$00,$ce,$00,$cb,$00
.byte $c8,$00,$c4,$00,$c1,$00,$be,$00,$bb,$00,$b8,$00,$b5,$00,$b3,$00
.byte $b0,$00,$ad,$00,$aa,$00,$a7,$00,$a5,$00,$a2,$00,$9f,$00,$9d,$00
.byte $9a,$00,$98,$00,$95,$00,$93,$00,$90,$00,$8e,$00,$8b,$00,$89,$00
.byte $87,$00,$84,$00,$82,$00,$80,$00,$7e,$00,$7b,$00,$79,$00,$77,$00
.byte $75,$00,$73,$00,$71,$00,$6f,$00,$6d,$00,$6b,$00,$69,$00,$67,$00
.byte $65,$00,$63,$00,$61,$00,$5f,$00,$5d,$00,$5b,$00,$59,$00,$58,$00
.byte $56,$00,$54,$00,$52,$00,$51,$00,$4f,$00,$4d,$00,$4b,$00,$4a,$00
.byte $48,$00,$47,$00,$45,$00,$43,$00,$42,$00,$40,$00,$3f,$00,$3d,$00
.byte $3c,$00,$3a,$00,$39,$00,$37,$00,$36,$00,$34,$00,$33,$00,$31,$00
.byte $30,$00,$2f,$00,$2d,$00,$2c,$00,$2a,$00,$29,$00,$28,$00,$26,$00
.byte $25,$00,$24,$00,$22,$00,$21,$00,$20,$00,$1f,$00,$1d,$00,$1c,$00
.byte $1b,$00,$1a,$00,$19,$00,$17,$00,$16,$00,$15,$00,$14,$00,$13,$00
.byte $12,$00,$10,$00,$0f,$00,$0e,$00,$0d,$00,$0c,$00,$0b,$00,$0a,$00
.byte $09,$00,$08,$00,$07,$00,$06,$00,$05,$00,$04,$00,$03,$00,$02,$00
This will divide two 8-bit numbers in some 90-150 cycles. The code can easily be extended to handle larger dividends. |
| Previous - 1 | 2 | 3 | 4 - Next | |
