Log inRegister an accountBrowse CSDbHelp & documentationFacts & StatisticsThe forumsAvailable RSS-feeds on CSDbSupport CSDb Commodore 64 Scene Database
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..
2008-04-17 21:01
Skate

Registered: Jul 2003
Posts: 494
read c=hacking magazine issues #8 and #9 first. that should help a lot.
2008-04-17 21:23
doynax
Account closed

Registered: Oct 2004
Posts: 212
Quote: read c=hacking magazine issues #8 and #9 first. that should help a lot.

Thank you.. Those articles are surprisingly complete.
2008-04-17 21:28
Oswald

Registered: Apr 2002
Posts: 5094
hmm this sbx trick is nifty, I dont even understand it :) apart from the sine theorems I'm afraid there are not much tricks left, except the x*y=((x+y)^2/2)-((x+y)^2/2) which you probably aready know. and stuff like getting all cube coordinates with additions/substraction of the matrix elements, using all the symmetry you can get, etc.

there's grahams's method to rotate 192 dots in one-der: you build a rotation matrix, then precalculate (adc speedcode) the multiplies of the x,y,z elements of your unit vector. then you can calculate the 3d positions of a lot of dots based on those tables with additions/substractions. to speed up address calculations you can lay out 3 32 char wide char matrices so the start of each char row will be aligned to a page. then to speed up dot clearing you can store the calculated addy into an sta xxxx speedcode after having the dot plotted. 32 char wide char matrixes are ideal for plotters.

another trick is to use a character screen. linedrawing will be very costly as you have to plot chars aswell etc, but you gain a lot when it comes to eorfill/clr. Desert Dream uses this method to plot the lines in the linetunel&lineball part, and the rotating "1024" text & circle saw & at the pyramids. (melon and spaceship are sprites)

speaking of dithering natural wonders bugs me a lot, looking at the code it appears me it shouldnt be able to do what it does but it still works :)
2008-04-17 21:48
Martin Piper

Registered: Nov 2007
Posts: 722
SNES Star Fox (Star Wing in Europe) used the character screen for its 3D rendering.
2008-04-17 21:54
doynax
Account closed

Registered: Oct 2004
Posts: 212
Quote:
hmm this sbx trick is nifty, I dont even understand it :)
All it really does is use subtraction and SBX's masking effect to test and clear the bits in order (i.e. msb to lsb).

Quote:
there's grahams's method to rotate 192 dots in one-der: you build a rotation matrix, then precalculate (adc speedcode) the multiplies of the x,y,z elements of your unit vector. then you can calculate the 3d positions of a lot of dots based on those tables with additions/substractions.
I've been trying to do something similar, that is transform vertices manually from prescaled matrices, but keeping track of things is tricky. I mean a cube is fine but try hand-rolling a dodecahedron..

Quote:
another trick is to use a character screen. linedrawing will be very costly as you have to plot chars aswell etc, but you gain a lot when it comes to eorfill/clr. Desert Dream uses this method to plot the lines in the linetunel&lineball part, and the rotating "1024" text & circle saw & at the pyramids. (melon and spaceship are sprites)
You know, this is actually what I've been doing =)
Not out of choice really, as it was a damned mess to implement, but I've been working on the NES which lacks a bitmap mode or fast VRAM access (here's a preview which only works in Nestopia).

Quote:
speaking of dithering natural wonders bugs me a lot, looking at the code it appears me it shouldnt be able to do what it does but it still works :)
I would have assumed it was only a matter of EOR filling alternate scanlines separately. Are you saying there are more efficient alternatives, or is there just more to it that I've missed?

By the way is there any viable way of rendering concave models with EOR filling? That is methods to efficiently figure out which polygons might need to be clipped against each other and clever ways of doing the actual clipping.
2008-04-17 22:21
Oswald

Registered: Apr 2002
Posts: 5094
here's an idea I havent used so far: if you have a kind of small amount of vertices like in case of a dodecahedron, one could use precalculated tables to scale the unit vector to match the needed coordinates, then its all adcs and table lookups again, except for the perspective.

dithering: well maybe its just me being dumb.. :/ but I can not visualise how graham can do it with just one eorbuffer, and plotting each times 2 pixels under eachother in the liner. for the dither not to be messed up the line's pixel pattern must be aligned vertically, but the lineroutine seem to be not care about that (ie seemingly no anding of lowmost bit of y coord). also plotting 2 pixels each time would mean a loss of resulotion which is not visible on the result :)

the only viable way to do concave models with eor filling is presented in altered states imho :)

btw your NES routine is _very_ impressive :)
2008-04-17 23:04
doynax
Account closed

Registered: Oct 2004
Posts: 212
Quote:
here's an idea I havent used so far: if you have a kind of small amount of vertices like in case of a dodecahedron, one could use precalculated tables to scale the unit vector to match the needed coordinates, then its all adcs and table lookups again, except for the perspective.
That's *exactly* what I've been doing, except even the perspective is based on logarithm tables. Granted, the precision is a bit crappy but I can live with it.

Quote:
dithering: well maybe its just me being dumb.. :/ but I can not visualise how graham can do it with just one eorbuffer, and plotting each times 2 pixels under eachother in the liner. for the dither not to be messed up the line's pixel pattern must be aligned vertically, but the lineroutine seem to be not care about that (ie seemingly no anding of lowmost bit of y coord). also plotting 2 pixels each time would mean a loss of resulotion which is not visible on the result :)
Okay.. Well, you have fun disassembling that one and I'll let you get to me when you've figured it out ;)

Quote:
the only viable way to do concave models with eor filling is presented in altered states imho :)
Huh. The only thing I noticed was a three second sequence with a cube and a skewed lid which overlapped the base. But from the looks of it they simply assign two bit patterns to the same color so the overlap doesn't matter.
I still think it should be possible to handle real concave objects without precalculating everything. Just imagine the sheer awesomeness of a 3D text scroller.

Quote:
btw your NES routine is _very_ impressive :)
The limited RAM space and crappy graphics chip may be real problems but you can still do a lot more with that 1.7 MHz processor and large ROMs than people seem to realize. I mean good luck fitting 32k of unrolled line drawing code or a two-dimensional atan2 table into a C64 demo.
2008-04-17 23:08
Cruzer

Registered: Dec 2001
Posts: 1048
My favorite trick is to precalc the data, since doing realtime math on 1MHz/8bits seems a bit too ambitious for me. The usual argument against precalculation is of course that it takes up too much memory, but what I have learned is that it can be packed enough to leave room for everything you need, including unrolled code.

E.g. face hidden status, or any other status that typically stays the same for a number of frames, like which direction a texture mapped face is drawn, can be packed down to an initial state and a count for each time it changes, as well as some bits for the new value. Or if it's binary, like face hidden status, the latter can be omitted, since there is always only one other available option to switch to. So an object with 20 faces that each change hidden state on average 10 times in the duration of the effect, the total memory consumption would be like 220 bytes.

Coords can be packed pretty good too with delta-packing. I'm working on some vectorballs where each coord only takes about 4-5 bits for both X and Y values. So for the 49 bobs that I have currently, it takes about 27 bytes/frame, which means I can have 30 seconds of unique movement running in 25 fps with about 20K of tables.

Other favorites are some routines I developed for filled vector some years ago, like this one for line drawing, using precalculated y-coords for each pixel, which is of course faster than any iterative algorithm (Bresenham go home:)...

ldy yCoords,x
lda #pixel
eor (fillerPnt),y
sta (fillerPnt),y

Which happens to work very well with this filler (notice immeditate mode - two cycles faster than normally)

eor #byte
sta gfx

The drawback is that it only works if the lines are max 51 pixels high, but I have a new version on the way that tackles this by dividing the line into smaller segmnents, that can be drawn in "parallel" which in return makes the whole thing even faster, since the coord lookup, and in some cases the pixel value can be reused for several pixels.

Another idea which I haven't used yet is to make the filler skip the unnecessary parts. Most of the time a typical eor filler is just wasting time on eor'ing with 0 and storing the same byte that was there before, so if you could make it skip at least a good bit of these wastelands of nothingness, there would be a lot of cycles to gain, especially for big flatshaded objects. I have some ideas on how to do this without adding any overhead to the linedrawer/filler, and without using too much memory or rastertime for administration, but I'm afraid I can't go into details.
2008-04-17 23:31
Oswald

Registered: Apr 2002
Posts: 5094
imho you cant do better than altered states' trick or precalculating the lines. doing inconvex objects with eorfiller would need a very complex routine. its not only clipping the lines, but theres even need to mess with the colors :(
2008-04-18 06:52
doynax
Account closed

Registered: Oct 2004
Posts: 212
Quoting Cruzer
Coords can be packed pretty good too with delta-packing. I'm working on some vectorballs where each coord only takes about 4-5 bits for both X and Y values. So for the 49 bobs that I have currently, it takes about 27 bytes/frame, which means I can have 30 seconds of unique movement running in 25 fps with about 20K of tables.
And I'd wager that floppy streaming comes in handy here too.

Quote:
Other favorites are some routines I developed for filled vector some years ago, like this one for line drawing, using precalculated y-coords for each pixel, which is of course faster than any iterative algorithm (Bresenham go home:)...
Hey, that's pretty clever :)
Y-major lines work out particularly nicely as they'll skip right over the invisible parts and you'll automatically hit the right X coordinate.
Honestly, I wouldn't have thought there'd be enough memory for this kind of scheme. But as you say a bit of subdivision (or just plain short lines) it ought to work out. Too bad it won't work in char mode though.

Quote:
Another idea which I haven't used yet is to make the filler skip the unnecessary parts. Most of the time a typical eor filler is just wasting time on eor'ing with 0 and storing the same byte that was there before, so if you could make it skip at least a good bit of these wastelands of nothingness, there would be a lot of cycles to gain, especially for big flatshaded objects. I have some ideas on how to do this without adding any overhead to the linedrawer/filler, and without using too much memory or rastertime for administration, but I'm afraid I can't go into details.
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.
 
... 21 posts hidden. Click here to view all posts....
 
Previous - 1 | 2 | 3 | 4 - Next
RefreshSubscribe 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
Rub_0201
stephan-a
fuzzybad
Rebok/BOOM!/Tropyx
Guests online: 119
Top Demos
1 Next Level  (9.7)
2 13:37  (9.7)
3 Mojo  (9.7)
4 Coma Light 13  (9.6)
5 Edge of Disgrace  (9.6)
6 What Is The Matrix 2  (9.6)
7 The Demo Coder  (9.6)
8 Uncensored  (9.6)
9 Comaland 100%  (9.6)
10 Wonderland XIV  (9.6)
Top onefile Demos
1 No Listen  (9.6)
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 Musicians
1 Rob Hubbard  (9.7)
2 Mutetus  (9.7)
3 Jeroen Tel  (9.7)
4 Linus  (9.6)
5 Stinsen  (9.6)

Home - Disclaimer
Copyright © No Name 2001-2024
Page generated in: 0.074 sec.