3D for a Calculator

[Sc4freak]

Hi, I've been trying to write a very simple 3D wireframe engine for my calculator (don't laugh - it's a moderately powerful TI-89 Titanium). It sounds ridiculous, I know, but all I want is a simple program which can draw a wireframe cube in 3D, output it to screen and be able to rotate and be affected by perspective. And it has to be done in Ti-Basic.

Thing is, I wouldn't have a clue when it comes to doing depth, perspective, rotation, scale and projection onto a 2D screen from virtual 3D space. I have 8 points, each with XYZ values, placed and connected with lines to form a simple 3D looking wireframe cube.

Now, the hardest thing for me to do here has been to implement perspective and rotation. I don't have the slightest clue on how to apply such things to the points (vertices, whatever) of a 3D object in 3D space.

Is there some kind of algorithm, or formula (in plain English/Maths so I can translate it to TI-Basic fairly easily) that I need to do this?

EDIT: Also, speed is of little concern. If it takes several seconds to render a frame, then so be it. Just as long as it isn't extreme (i.e. taking >1 min to render a frame)

 

[JHoxley]

You need to get really friendly with some matrix mathematics

From what I remember, my TI-83+ had decent matrix operations, which should at least make such an implementation possible without too much maths.

Direct3D is a long way from a TI-Basic calculator but it's transformation pipeline is still fundamentally the same as many others.

You have a world matrix that transforms the cube from model space (I'd define a cube as +/- 0.5 of the origin, making it a unit cube) to world space. This is where you'd apply your rotations, scaling and translation (look up "SRT" matrices if you want).

The results of this then get fed into the view matrix transform - this remaps everything to camera space.

Next up is the projection matrix - which is where it gets fun This is where your perspective comes in (although, it could be orthogonal if you want) along with a field of view. The outputs of this should be in -1:+1 projection space coordinates.

The final step is the viewport matrix which remaps the -1:+1 space to your 0..1024 type screen coordinates.

Now the true beauty of all this lies in matrix multiplication. You can construct a single matrix as World*View*Projection*Viewport and then apply that matrix to the incoming vertices. No matter how complex each of those steps are you still end up with a constant number of operations per-vertex.

Now, I've intentionally left it as fairly brief as it is a huge subject and there are a number of ways to achieve the same results.

Digging up a "classical" graphics textbook and maybe a linear algebra text should sort you out. Also, you might want to try finding a copy of Andre LaMothe's "Tricks of the windows game programming gurus" - istr it covered a lot of the "old skool" rasterization techniques.

hth
Jack

 

[Mate Kovacs]

Why TI-Basic, and not assembly?
Some TI-8x demos to convince you.

 

[Sc4freak]

Because ASM is impossibly hard to code for

JHoxley: Thanks! I really found that useful, pointed be in the right direction. I found a Wikipedia article about it here: http://en.wikipedia.org/wiki/3D_projection

Unfortunately, I'm having trouble making sense of it all. First, I converted the XYZ location of a point on the screen (which, by the way, has 0,0 at the top left hand corner and 158,78 at the very bottom right hand corner) to the co-ordinate system you mentioned.

Working off the Wikipedia article, I've plugged in all the values in the World Transform matrices, which apparently control rotation, and scale. But, that's as far as I've gotten. I don't even know what the Camera Transform matrices do, and I'm having trouble understanding how to implement Perspective Transform.

Wikipedia says:
A perspective distortion can be generated using the following 4×4 matrix:

where μ is the angle between a line pointing out of the camera in z direction and the plane through the camera and the right-hand edge of the screen, and ν is the angle between the same line and the plane through the camera and the top edge of the screen.

What does it mean by "Z direction"? If it's referring to my Z axis, I've currently got that pointing in the same direction that you're looking at on the screen (so up and down the screen is X and Y, while "through" the screen is Z). But if that's true, then that means that μ = 90, and 1/tan(90) = 0 (since anything below infinity divided by infinity = 0)?

I've tried rendering the cube with only the World Transform, and it becomes all distorted and comes out as a rectangle which, when rotated, seems to have its pivot anywhere but in the "cube" itself.

I'm pretty sure that I copied in the World Transform matrices correctly (Wikipedia wasn't too clear about the rest), and I think I get the co-ordinate conversion correct. Any help for a clueless soul?

 

[K.I.L.E.R]

Because ASM is impossibly hard to code for

It may take more time to develop something for it but ASM (at least x86 ASM) is the easiest programming language out there.
It's so simple.

Your calculator wouldn't be able to handle 3D at a good framerate.

http://en.wikipedia.org/wiki/Motorola_68000

Good luck rendering a real time 3D demo at more than 1fps.

 

[Frank]

I did things like that on a Sinclair ZX Spectrum. Without any real matrix calculations. You don't really need those for something simple like that.

Pythagoras is all you need, as long as you keep it simple. Forget about perspective, for a start. And just calculate the xyz values independently. And if you want it filled with hidden surface removal, draw the individual shapes, back to front, and use floodfill.

 

[Mate Kovacs]

ASM (at least x86 ASM) is the easiest programming language out there.

Yep, it's not hard to learn, but it's not very productive (in most cases) either. Sometimes we just like it rough.
And x86 asm especially is a b!tch , has a lot of irregularities (compared to the m68k, for example, not to mention the RISC stuff).

I did things like that on a Sinclair ZX Spectrum. Without any real matrix calculations. You don't really need those for something simple like that.

Respect, man! I've never had the opportunity to get my hands on one (I'm too young), but I've read an ISA reference.

@Sc4freak:
Let's forget about perspective for a second, and get rotation work first! If we have 3 non-coplanar vectors in 3-space, X, Y and Z, then we can write any vector V as their linear combination, that is V = x*X + y*Y + z*Z. (NOTE: Capital letters denote vectors, small letters denote scalars.) In this context, X, Y and Z are called basis vectors. The (x,y,z) vector is called "model-space" position in 3DGFX terminology. Now, if we have a bunch of points, described in a model-space, we can "virtually" rotate all of them about the model-space's origin by rotating its basis vectors, and calculating the "world-space" positions using that linear combination. (If you want the world-space position of the model-space origin to differ from the world-space origin, then you have to add the world-space position of the model-space origin to every transformed position, that is V = x*X + y*Y + z*Z + O.) Since we don't want to move the camera, just rotate the object (your cube) itself, we can skip world-space->camera-space transform. We do a very simple camera-space->screen-space (3D->2D) transform by simply dropping the z coordinates (orthographic projection). (You usually have to apply scaling factors here, in order to size your scene properly, too.) We still have one problem, since this way the origin (0,0,0) will be mapped to (0,0), so when we rotate e.g. a cube about the origin, it'll rotate about the top-left corner of the screen. So if we want the origin to be mapped to the center of the screen, we have to add the screen-space position of the center of the screen to each transformed position.

If you apply a perspective projection instead of the orthographic one, you get the "real deal". (To get a perspective projection formula, you only need paper, pencil and some knowledge about similar triangles.)

You may have already realized that the V = x*X + y*Y + z*Z linear combination can actually be written as a vector-matrix multiplication: V = (x,y,z)*[X,Y,Z]. Rotation, scaling and shear can be expressed by 3x3 transformation matrices. (In case of a rotation matrix, X, Y and Z have a length of 1, and are pairwise perpendicular, so there's no scaling or shear.)

The good thing about (homogeneous) 4x4 transformation matrices is that you can pack almost all the above-mentioned additional transforms into them.

 

[K.I.L.E.R]

You know how long it is to do those operations on a decent sized square on my TI-83 Plus?
It takes long enough to just draw a straight line on a graph.
I just hope the OP's TI-89's 12MHz chip is much faster than the Z80.

I did things like that on a Sinclair ZX Spectrum. Without any real matrix calculations. You don't really need those for something simple like that.

Pythagoras is all you need, as long as you keep it simple. Forget about perspective, for a start. And just calculate the xyz values independently. And if you want it filled with hidden surface removal, draw the individual shapes, back to front, and use floodfill.

 

[Nite_Hawk]

You know how long it is to do those operations on a decent sized square on my TI-83 Plus?
It takes long enough to just draw a straight line on a graph.
I just hope the OP's TI-89's 12MHz chip is much faster than the Z80.

Have you ever tried playing Daedalus on your ti-83? It's pretty impressive (even if it only looks like wolf-3d).

Nite_Hawk

 

[Frank]

You know how long it is to do those operations on a decent sized square on my TI-83 Plus?
It takes long enough to just draw a straight line on a graph.
I just hope the OP's TI-89's 12MHz chip is much faster than the Z80.

The Spectrum was only 4Mz. And the Basic was more than fast enough for such things. And things like cos, sin and tan can such a calculator do really fast.

Really, just calculate the points with plain geometric operations, that's MUCH faster and simpler than matrices.

 

[Tahir2]

The Motorola 68000 is a very powerful chip and ran the ATARI ST and Amiga just fine. Check out some of the 3D possible on the ST system:

http://www.atari.org/links/ST/

 

[K.I.L.E.R]

I thought matrix operations on a Z80 or on a Motorolla would be done very fast.
They are supported natively, even in the ASM routines.

Do they have "0 checks" to avoid multiplications by 0?

 

[Mate Kovacs]

I thought matrix operations on a Z80 or on a Motorolla would be done very fast.
They are supported natively, even in the ASM routines.

Do they have "0 checks" to avoid multiplications by 0?

There are no instructions dedicated to matrix operations in either of those ISAs, IIRC.
I don't really understand what your second question is. Both of them have compare and conditional jump instructions, but why would you want to avoid multiplication by 0? Did you mean division?

EDIT: Or did you mean that the TI-8x runtime environments implement matrix operations by built-in routines?

 

[K.I.L.E.R]

They do have built in routines.
I didn't mean they have dedicated units to matrix operations.
I also don't mean divisions by zero.

It's probably a stupid question because the TI-8x calcs aren't dedicated graphics processors.

Normally under OGL, the modelview matrix (from my own analysis) usually has a fair amount fo zeros(making it a sparse matrix), it actually benefits from sticking it into a tree and then multiplying and adding element by element without any zero multipliciations.

This isn't to say it's true under all cases or even all that many cases for that matter.
Just my own analysis.

Anyway I thought it might be a good idea to include some of these optimisations into the TI-8x calculators if they aren't there if you plan on doing any 3d calculations with matrices.

Then again the optimisation may end up costing more than the multiplication, moreso on a system like a TI-8x.
I guess it's just better to do what Diplo said.
Just use equations.

There are no instructions dedicated to matrix operations in either of those ISAs, IIRC.
I don't really understand what your second question is. Both of them have compare and conditional jump instructions, but why would you want to avoid multiplication by 0? Did you mean division?

EDIT: Or did you mean that the TI-8x runtime environments implement matrix operations by built-in routines?

 

[Mate Kovacs]

Then again the optimisation may end up costing more than the multiplication, moreso on a system like a TI-8x.
I guess it's just better to do what Diplo said.
Just use equations.

I partly agree with DiGuru on using simple formulas, since you don't really need a 4x4 transformation matrix here. But if you need gimbal-lock free rotation, the best way is to compute a 3x3 transformation matrix for each frame. So transforming a point is 9 multiplications, 6 additions, plus the same perspective projection you'd use anyway. If you exploit the properties of the cube, you don't even need multiplications.
NOTE: By 'multiplication', 'addition', etc I mean the abstract operations on the scalar-type used, not necessarily asm instructions.

IMO the bottleneck would be the line-drawing / face-filling routine, so it doesn't really matter whether you use naive matrix operations or not.

 

[Sc4freak]

Nah, since it's only a wireframe the calculator only has to switch a few pixels (12 lines on a 160x100 resolution 1-bit colour screen). It actually takes 2-3 seconds to do the trig calculations and perspective calculations for all 8 vertices, especially since I'm using a couple of expensive built-in square-root functions.

Oh, and sorry I deserted this thread for so long, the calculator was put on hold for a while since I had other things to do . Not to say that I've got the darn thing working, I still can't get the rotation to work properly (perspective I've got covered already with a moderately accurate simulation). I've tried using polar co-ordinates to rotate the vertices around a common point, but that was only moderately sucessful. Because of the formula, I couldn't do X, Y and Z rotations all at once; and would only work for 1 axis of rotation if I disabled the other 2. I've also tried various matrices and formulae I've found on the internet, but they all involved fairly heavy use of trigonometry and turned out to be quite slow, and I couldn't get a lot of them to work. I'm now looking towards books for some research before going back in and attempting this again.

So, besides Tricks of the windows game programming gurus, what other good books are out there which can give a beginner some more information about general 3D game programming? And if possible, not just 3D, topics such as physics and the maths behind it would also be interesting, I think. It'd be nice if the books either were general or focused on the C programming language since for the most part it's easily translatable for the calculator (My C++ skills aren't too hot).

Thanks for all your help, everyone.

 

[Mate Kovacs]

It actually takes 2-3 seconds to do the trig calculations and perspective calculations for all 8 vertices, especially since I'm using a couple of expensive built-in square-root functions.

One of the oldest demoscene tricks is to use precalculated tables to compute sin/cos.
E.g. for pi/65536 radians of accuracy, you could use (say) two 256-entry tables (one with pi/256 and another with pi/65536 radians of accuracy) plus some additional calculations (involving the so-called trigonometric addition formulas).

EDIT:
I just realized how bad of an example that was, since if you want to represent angles with 16 bit numbers, you have 2*pi/65536, that is, pi/32768 radians of accuracy. Not to mention you only need to cover pi/2 radians with lookup, if you can afford some bit-tweaking.
What do you use those square roots for, BTW? Somehow it just doesn't sound right.
I don't know if the lookup trick would really help, I guess the real performance-killer is TI-BASIC itself.

 

[Sc4freak]

Oh, the square roots were used for perspective calculations, which I have since removed and replaced with a different way of doing it.

As for the books, I can't find any for any decent price. At the local Borders book shop, "Tricks of the 3D game programming gurus" (for example) costs $100. A bit much...