[CSDb] - User Forums - 3D projection on the C=64 (or...how do I divide?)

You are not logged in - nap

CSDb User Forums

Forums > C64 Coding > 3D projection on the C=64 (or...how do I divide?)

2004-02-13 08:51

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....

2004-08-19 21:17

St0fF

Registered: Oct 2002
Posts: 40

actually we found out some really important things here in ilmenau/germany:
the basic v2-routines are the fastest approaches for accurate calculations ... just gotta optimize those routines (or make them fixpoint)
the approach heavily beats the so highly cheered up intel math library on PCs ... just watch some stockholme syndrome releases ;) I translated the basic code to math for abductee, then he implemented it in SSE2 - fucking fast, fastest routines in the world!

2006-05-25 21:26

ready.

Registered: Feb 2003
Posts: 441

Don't know if anybody has come up with it, but here is my idea. I needed to do object-size-reduction in 2D-graphics, let's say a circle and let's say I want to reduce its radius to make it look fall into the screen farther and farther, smaller and smaller: I have to divide the radius by an increasing number, of course. We all know it's easy to divide by 2, 4, 8, 16, and so on, just using ROR or better LSR for shorter execution time. So it's easy to load a number into the accumulator and get 1/2, 1/4, 1/8... so I get the 50%, 25%, 12.5%....if I add these values toghether I can get 12.5%, 25%, 12.5+25=37.5%, 50%, 50+12.5=62.5%, 50+25=75%, .... of the original value.

I thought 12.5%, 25%, 50% could be enough for me, but more accurancy can be obtained doing more LSRs to get 1/16=6.25%, 1/32 and so on, and then add them toghether to get the percentage you want. Example:

lda SOMETHING
ldy #$00
sty v1
sty v2
lsr
h1: tay ;y is the 50% value of SOMETHING
lsr
h2: sta v2 ;v2 is the 25% value of SOMETHING
lsr
h3: sta v1 ;v1 is the 12.5% value of SOMETHING
lda (v1) ,y
sta v1
ldy v2
lda (v1),y ; I get the y+v2+v1=(50+25+12.5)% of SOMETHING

You have the result into the accumulator. A table should be created with numbers from 0 to $ff or even less if you need. v1 points to it.

Then you need a part which puts into the h1, h2, h3 locations the NOP code to exclude the percentage you don't want to add.

2006-05-26 00:05

_V_
Account closed

Registered: Jan 2002
Posts: 124

Funny thing, division... staying out of log-space, you get Cruzer's multiplication of x*(1/y). Now, 1/y is also called the "inverse" of y, so basically, x/y = x*(1/y) is the same as saying "find the inverse of y, then scale the result by a factor of x".

An interesting fact about the inverse function [ let's call this function f: f(t) = 1/t ] is that its graph is symmetrical with respect to the primary diagonal [with point (1,1) on the diagonal]. This means that if (for some value of t) we find a point u so that

f(t) = u
then also f(u) = t

For example, f(2) = 1/2 = 0.5
but also f(0.5) = 1/0.5 = 2

[ also f(f(t)) = t as (obviously) 1/(1/t) = t ]

Anyway, this symmetry could be useful to reduce the size of the "1/y table" as described by Cruzer (or boost its accuracy by being able to add more intermediate points to the table). For example, if a 1/y table is stored as follows:

location 1/y
1 1
2 0.5
3 0.333...
4 0.25
5 0.2
etcetera,

then it's easy to find the inverse of 3: just look for the value 3 at the "location" column, see which "1/y" value is linked to it, and you get 0.333....

To the find the inverse of 0.333..., the process is reversed: look for the value 0.333... at the "1/y" column, see which "location" value is linked to it, and voila, you get 3.

In pseudo-code, you'd get something like this:

Given y, search inverse of y:

(1) Is y >= 1?
YES: goto (2)
NO : goto (3)
(2) search for y in "location" column, inverse of y is linked value in "1/y" column
(3) search for y in "1/y" column, inverse of y is linked value in "location" column

This might help Nightlord with the accuracy problem he encountered while trying Cruzer's solution. Personally, I prefer logarithms (of some base number, n) as demonstrated by Perff, as they're so elegant:

logn(x/y) = logn(x) - logn(y)

[ by the way, in Europe log(x) usually refers to base 10 (Brigg logarithm) while ln(x) refers to base e (Napier logarithm). Which got me confused about Perff's formula, but then I remembered that the US writes ln(x) as log(x) (they never heard about Brigg) =P. In what follows, I'll be using the European notation. ]

One disadvantage of logn-functions is that they don't have any easy symmetries as the one for 1/t. For large t values, ln(t) diverges very slowly to infinity, whereas it diverges to minus infinity extremely rapidly as t gets close to 0. Also logn(1) is always 0. So, you'll have to use a rather large log-table with high accuracy as t gets smaller than 1 and reduced accuracy as t gets larger and larger (the difference between ln(11000) and ln(10000) is slightly less than 0.1, for example).

There is an interesting connection between ln(t) and 1/t, by the way, which involves derivatives:

D[ln(t)] = 1/t (t>0)

The derivative of ln(t) is exactly 1/t (with t>0). So by calculating 1/t, you know exactly how fast ln(t) changes near t. Of course, derivatives aren't exactly A-material for the good old c64, so I'll leave it at this :).

2006-05-26 10:36

Graham
Account closed

Registered: Dec 2002
Posts: 990

Hmm nobody posted the normal binary division by now, so I'll do it:

ASL $FD
ROL

LDX #$08
.loop1
CMP $FC
BCC *+4
SBC $FC
ROL $FD
ROL
DEX
BNE .loop1

LDX #$08
.loop2
CMP $FC
BCC *+4
SBC $FC
ROL $FE
ASL
DEX
BNE .loop2

Divides the value in $FD by the value in $FC, 8 bit integer result in $FD, the first 8 fraction bits are in $FE.

Ofcourse both loops should be unrolled :) I didn't want to write down the unrolled code here.

2006-05-31 21:00

tecM0

Registered: Jan 2002
Posts: 40

Quote: One of the methods I have used the most when dividing (and multiplying) in assembler is using logarithm.
I use the fact that:
x/y = e^(log x - log y)

You have one table containing values of log(x), and another table of e^x

When you want to divide the content of the X-reg with the Y-reg you do:

sec lda logtable,x sbc logtable,y tax lda exptable,x

That's it! :)
(You must of course take care of overflows etc.)

One downside using this is that the result is not 100% accurate, but it's fast and you can also use it for multiplying. (do an add instead of sbc)

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.

2006-05-31 21:15

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.

2006-05-31 21:23

tecM0

Registered: Jan 2002
Posts: 40

log (basic v2) stay under 6 for $ff isnt this right?
the problem is the EXP :(

T.

2006-05-31 21:56

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

2006-07-14 18:10

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.

2006-07-14 20:27

John West
Account closed

Registered: Aug 2004
Posts: 4

Quoting AmiDog

Has 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.

Previous - 1 | 2 | 3 | 4 - Next

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

zscs
Alakran_64
BYB/Hokuto Force
Mike
DnP
Mibri/ATL^MSL^PRX
Twilight/Excess/Arcade
Martin Piper
Raf/Vulture Design
slimeysmine
BlackJack/Civitas
Guests online: 178

Top Demos

1 Next Level  (9.7)
2 13:37  (9.7)
3 Mojo  (9.7)
4 Coma Light 13  (9.6)
5 The Demo Coder  (9.6)
6 Edge of Disgrace  (9.6)
7 What Is The Matrix 2  (9.6)
8 Uncensored  (9.6)
9 Comaland 100%  (9.6)
10 Wonderland XIV  (9.6)

Top onefile Demos

1 No Listen  (9.7)
2 Layers  (9.6)
3 Cubic Dream  (9.6)
4 Party Elk 2  (9.6)
5 Copper Booze  (9.6)
6 X-Mas Demo 2024  (9.5)
7 Dawnfall V1.1  (9.5)
8 Rainbow Connection  (9.5)
9 Onscreen 5k  (9.5)
10 Morph  (9.5)

Top Groups

1 Performers  (9.3)
2 Booze Design  (9.3)
3 Oxyron  (9.3)
4 Censor Design  (9.3)
5 Triad  (9.3)

Top Webmasters

1 Slaygon  (9.6)
2 Perff  (9.6)
3 Sabbi  (9.5)
4 Morpheus  (9.4)
5 CreaMD  (9.1)

Page generated in: 0.047 sec.