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

Welcome to our latest new user eightbitswide ! (Registered 2024-12-24)

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-05-13 11:44

Nightlord
Account closed

Registered: Jan 2003
Posts: 131

cruzer:

at the moment i am using division for 2d line slope calculation. it is precalculated in my engine which makes it bound between 0 to $40 and i store slopes as $xx.xx so i spend $40 x $40 x 2 = $2000 bytes which hurts my mind. since i don't use eors to fill and i fill line by line (this lets me to make surfaces with dithered patterns unlike eor)i need to take one step in y everyline and left/right slope steps in left and right boundaries of line. for this reason i could not find a way to use stephen judd's add-dx-until-bigger-than-dy approach. (it isnot applicable for me when dx > dy)

can any body give some fresh ideas.

2004-05-13 14:20

Oswald

Registered: Apr 2002
Posts: 5094

nightlord: my guess is, that using logs and exps is accurate enough for your routine, either u use this one, or the bloody slow, but hell accurate bit shifter killer one. (you can find this on steve judd's page)

and speaking of patterns, you can have 13 different ones if you use eorfilling a bit more trickyer: have 2 eor buffers, one with the odd, one with the even lines of your screen. then you draw each line into both of them, but with a different colour pattern for the pixelmasks. then you just eor to the screen in 2 go the odd and even lines, and voila you have patterns :)

2004-05-13 18:56

Cruzer

Registered: Dec 2001
Posts: 1048

When dx>dy I guess you need to do an integer division for the Bresenham algorithm, although I have never tried to implement it on the c64. Maybe you can make some LUT-stuff for this, that doesn't fill too much.

2004-05-13 20:40

White Flame

Registered: Sep 2002
Posts: 136

You technically don't need to do a divide.

All's that Bresenham does is keep track of the slope's fraction in a numerator/denominator pair instead of in fixed point. When the numerator gets bigger than the denominator, you bump by 1 pixel and subtract the denominator from the numerator. If you change that comparison to a "while(num>=denom) { ++x; num-=denom; }" loop (with --x for the other direction obviously), the same general code will work no matter the slope. Whether that's faster or slower than doing a divide before-hand (to figure out the integer portion of the delta so you don't need to loop the num>demon compare) depends on the slope of the line. Where the delta is large, a divide is faster. However, if the delta is large, the line won't be very long, so it sort of evens out. The code is a lot shorter and easier to manage if you do a compare loop.

2004-05-17 11:41

Nightlord
Account closed

Registered: Jan 2003
Posts: 131

oswald: you are the master of odd/even lines

thx everyone

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.

Previous - 1 | 2 | 3 | 4 - Next

Refresh

Subscribe to this thread: