[CSDb] - User Forums - Your favorite 3d tricks

You are not logged in - nap

CSDb User Forums

Forums > C64 Coding > Your favorite 3d tricks

2008-04-17 20:36

doynax
Account closed

Registered: Oct 2004
Posts: 212

Your favorite 3d tricks

In the interest of educating newbies like me who don't yet know all the tricks, and detracting attention from that ridiculous multithreading "debate" I thought we could share some tips on how to write a speedy vector part.
Because the depressing fact is that aside from this very forum there seems to be about zero information on how to do 3D on 8-bit systems, unless it's all been hiding in some old diskmag somewhere (and as far as I'm concerned information that isn't indexed by Google might as well not exist).

Now, to start things off..

You can get rid of all those nasty multiplications when building a rotation matrix from Euler angles by exploiting the trigonometric product rules ( 2*cos x*cos y = cos(x - y) + cos(x + y) and friends ). I realize that this is probably common knowledge but its far from obvious and without it those multiplications are real cycle eaters. Oh, and thanks for the tip WVL :)

Another method is an alternative to Bresenham, or fixed point slopes, for deciding whether to continue on the major axis or move diagonally when drawing lines. The idea here is simply that those decisions can easily be precalculated and stuffed into bit arrays. The tricky part here is that you can use SBX to test these bits while letting the same mask for figuring out what pixels to plot in a horizontal run in turn mask our decision bits in X.

In other words:

	lda #%11111111
	sbx #%10000000
	bcs .x1

	eor #%01111111
	eor pixels,y
	sta pixels,y
	iny

	lda #%01111111
.x1	sbx #%01000000
	bcs .x2

	eor #%00111111
	eor pixels,y
	sta pixels,y
	iny

	lda #%00111111
.x2	sbx #%00100000
	bcs .x3
	.
	.
	.

So please post any interesting suggestions you've got. Any efficient and/or elegant methods for doing clipping, transformations, line drawing, lighting, dithering and all the other black arts..

... 21 posts hidden. Click here to view all posts....

2008-04-20 10:22

Skate

Registered: Jul 2003
Posts: 494

About lighting and dithering, I'd like to remind you two demos and a their open-source engine.

Water/Aesrude
Water 90%

Mist/Civitas
Mist

Dalaman 3D Engine
Dalaman 3D Engine

All coded by Nightlord for your pleasure.

2008-04-21 14:18

Cruzer

Registered: Dec 2001
Posts: 1048

Quote:

Then allow me to speculate ;)
How about keeping a separate bit array with one element per screen tile. Then when drawing a line you'd plot a separate low-resolution outline to the bit array, i.e. a conservative estimate of which cells in the real bitmap the line might cover. The standard line algorithm should work if modified to draw both tiles when moving diagonally. At least that's a scheme I tinkered with, without getting it to work I might add..
But I guess setting up and clipping all those extra lines would be a tad too costly to be practical.

You were right about dividing it into some cells, but as usual my philosophy is "why do it in realtime if it can be precalculated without taking up too much memory?"

One idea I have is to analyze in advance which cells needed to be filled when, and save this as a packed list that could be depacked in realtime w/o adding too much overhead. Kinda an extension on how I optimized the funfiller in YKTR2, except that only worked for start/end for each column, and not for "holes" inside.

The number of cells could be a round number like 256, which means each cell will be 1/256th the size of the filled area. So if it's using one charset, each cell will be a char big, but they could be any other size depending on the effect's size, and no one says 256 is the optimal number either. For each of them we need to predetermine whether it can be skipped for each frame, which could be done with some conditions like that all pixels must the same as the previous frame, and that the inital value before any eor'ing has been done is the same as the value after the last eor. If this is the case there is no need to fill this cell at all, and both eor'ing and sta'ing can be skipped.

To make the filler skip a cell, the first command must be changed from eor #$00 (assuming that's how the filler works, but it would work for absolute mode as well with a few modifications) to some branch, e.g. bcc, which skips to the next cell. This can be done by eor'ing the opcode with #EOR_IMM^BCC and the argument byte with the branch length. To switch it back to fill-mode, it just needs to be eor'ed with the same values again. This code modding could for instance be done with 256 specialized routines, which I think would be pretty quick.

Storing which cells to change can be done with one byte/frame for each cell that must swap status. Since there is always only one option on what the state should be (the opposite of the current one) we just need the cell number, thus one byte.

The size of the look-up tables depends on how many cells would change state/frame. E.g. if we have a cube, and it rotates from one face facing the eye to another, probably most of the cells would have to change state about two times => 512 bytes used. And if this happens 10 times during the effect, we would need 5K. So probably not a big deal as long as the effect is pretty simple and shortlived. But I could be wrong, need to make some proof-of-concept test to be sure.

The advantage of this method is that it adds very little administration overhead. No need for additional lowres lines or anything like that, and the filler itself doesn't get any slower at all. It doesn't even know anything about that it's optimized, it just gets modded from the outside, which I think should be possible to do pretty fast.

Guess the only problem I can see (apart from the agony of implementing it) would be if it turns out to require more memory than expected. But I have some schemes for this as well. E.g. to add some rigidity, so only cells which have a certain number of fill-free frames in a row gets switched to skip-mode, otherwise they just stay in fill mode. Another idea could be to add some additional "layers" of bigger cells to make it possible to switch big areas faster and with lesser memory consumption. And maybe it's more efficient to do the start/end of each column more like I did for the YKTR2 effect, which as far as I remember didn't consume very much.

2008-04-22 07:18

HCL

Registered: Feb 2003
Posts: 728

@Oswald, it's interesting to see that you hardly believe the dither-shit in NaturalWonders is possible. Especially after seing your large dithered vectors in Real.. It's obvious how you made that one, and NW is just one step ahead. I don't know if Graham was inspired of your vector, but i was when i made my dithered vector, and my line-routine looks much more like yours.. drawing in two buffers.

Well, i think you have figured out how Graham does his dithered line-drawing by now, and you see it really is using two buffers, only they are aligned 1 byte from each other.. the line routine ajusts (with the eor(zp),y) to only draw one bit-pattern into one buffer and another bit pattern into the other. The eor-filling is then made with two buffers. The gain: only draw one line (two lines at the same time), the loss: always draw both lines, even if one is invisible.

2008-04-22 18:35

Krill

Registered: Apr 2002
Posts: 2980

Quote:

but as usual my philosophy is "why do it in realtime if it can be precalculated without taking up too much memory?"

Sigh. Looks like i'll always stay the king of the c64-4k hill. :\

2008-04-22 19:11

Oswald

Registered: Apr 2002
Posts: 5094

HCL,ah I understand now. (forgot meanwhile the eor (),y stuff, now rechecked). Im suprised now I didnt get it for the first time... :) btw glad that real inspired you :) that vector in vector stuff was inspired in turn by some classic amiga demo. cant recall its name atmo tho.

2008-04-24 15:45

doynax
Account closed

Registered: Oct 2004
Posts: 212

I just did some back-of-the-envelope calculations and it seems like I could optimize the transformation code by a factor of two, save lots of memory on code and tables as well as increase the precision by dropping the perspective divisions.

The depressing part is that the only object which actually seems to benefit from it is the cube (and even there I got a lot of complaints about the exaggerated perspective), more complex models just look plain weird if you let the Z depths have more than about a 25% effect. Sure, if you had a real scene to place the camera within, with Z-clipping and everything, then it'd be invaluable but for a single object spinning around in the middle of the screen there isn't much you can do with it..

Does anyone actually ever bother with proper perspective projection?

2008-04-24 16:09

Oswald

Registered: Apr 2002
Posts: 5094

perspective projection is just a table and a multiplication.

x=(x/z)*n
x=x*1/z)*n

n is constant. you'll have a table of (1/z)*n. look up the value for Z, use a 8x8=16 bit mul, throw away the low8 bits. done.

afaik everyone does it like that. or similarly.

2008-04-24 16:30

doynax
Account closed

Registered: Oct 2004
Posts: 212

And that's just what I've been doing it myself but with a 16x8-bit multiplication instead. Well, in the old demo I used logarithmic division but the precision was horrible.

But without perspective there's no need to work out the Z value of the vertices, or the Z vector of the matrices or store all those multiplication tables. Plus you don't need to work out the low-bytes of X and Y coordinates when building the vertices, only propagate carry from the additions/subtractions (this saves a surprising amount of cycles). Or at least that's what I think should happen *if* I dropped Z support, but I might have missed something.

It seems like the only reason I'm doing the perspective right now is because it wouldn't be "real" 3d without it..

2008-04-24 18:04

Oswald

Registered: Apr 2002
Posts: 5094

you can only get away with dots/bobs without perspective imho. I dont understand why it is such a big problem to you tho. and 3d rotations: by using symmetries and thinking of the 3d matrix as vectors you can boil down vertex calcs into a series of additions of 3d vectors, after you have built your matrix with a series of additions.

I think you are aiming simply too high, your methods of doing 3d actually represent the state of the art way of doing it on the c64, you cant do it much faster. 98% of c64 demos doing 3d do it slower than how you already do it.

2008-04-24 18:46

doynax
Account closed

Registered: Oct 2004
Posts: 212

Quoting Oswald

you can only get away with dots/bobs without perspective imho.

I've been trying out a few things in my C prototype and the whole thing is kind of weird.
For low-polygon objects (say a cube or a tetrahedron) you truly *need* a small bit of perspective or the the illusion of 3d falls apart, it doesn't have to be much mind you but it has to be there (about 10% of scaling difference between nearest and farthest points is sufficient). On the other hand if you try let the Z value have more than a 30% effect on more complex objects (an icosahedron or a dodecahedron in my case) then it just looks *wrong*. And here I see no problems whatsoever when dropping Z altogether.

Yet I don't particularly feel like maintaining separate code paths for them. Perhaps the simple objects would look better with a bit of lighting?

Quoting Oswald

I think you are aiming simply too high, your methods of doing 3d actually represent the state of the art way of doing it on the c64, you cant do it much faster. 98% of c64 demos doing 3d do it slower than how you already do it.

Trying to optimize this bloody program has become a matter of diminishing returns, and the transformation code just happens to be the easiest thing to attack right now.
I've just run out of practical ideas on how to squeeze cycles out of the line drawing or filling code and I'm not quite ready to give up yet, which is why I created this thread in the first place I suppose.

Previous - 1 | 2 | 3 | 4 - Next

Refresh

Subscribe to this thread: