Any good examples of 3D vector programming?

[Art]

I would like to try to program a very simple flight simulator. Nothing special, only a horizont and some lines. Are there any good examples of 3D vector graphics programming and a simple flight model for the Spectrum assembler? I don't think I can create a real simulator, but I would like just to try to program something and to see how it works.

[+3code]

Not sure if this can help you:
viewtopic.php?t=532

[Art]

I am not sure either, but thank you. I'll look at it.

[Tommo]

I can offer you my effort for the Sam Coupé as something of an example that's broadly similar to how you'd go about things on a Spectrum, but I'm not sure about good. The biggest misstep is in the approach taken to line clipping, I think — I'm doing full plane arithmetic when I should have just used a binary search for the intersection point — but all the other areas could also definitely do with work.

I keep meaning to write a newer version, but I keep meaning to do a lot of things.

That all said, being the original author I can definitely answer any questions you might have on general approach, what I specifically did and didn't, and more on what I wish I'd done differently, if that'd be helpful.

[Art]

Thank you, I'll look at it. It looks a bit complicated, but it's probably just because I've never made vector graphics. I should probably take just some bits from it and make a little test.

[Tommo]

Thank you, I'll look at it. It looks a bit complicated, but it's probably just because I've never made vector graphics. I should probably take just some bits from it and make a little test.

Yeah, sorry — it started off relatively simple and then in my naivety I think I made some bad choices in pursuing optimisation. That plus the focus on a particular use case of Elite-style face removal for mostly-hidden lines.

If it were for something like Battlezone or any of those other Atari games it'd be about a trillion times simpler.

I don't know your level of prior experience so I don't know exactly what would be appropriate, but I could at least pencil out what I'd imagine how something more like the flight simulator you describe might look in general code terms? If you're new to 3d then it's probably just the stuff of maintaining an orientation that'll be most unintuitive.

[Art]

The hidden line removal looks very nice, but I think I should use just the most simple line graphics without any tricks. Like in mentioned Battlezone. As for my experience with assembler programming, it's quite low, I've done some simple raster graphics and moving etc., but not any line graphics or 3D. As for advanced mathematical computing and lines, only in Basic and C. So I don't expect very much from my tests, at least not very soon.

[Tommo]

Cool. Then starting tips, in a disorganised fashion:

To transform points you'll end up applying a matrix to a point.

If you were restricting yourself to Battlezone — everything on a plane, rotating around a single axis — then you might store each object's 3d state as a position and an angle. You can't do the same thing for full 3d movement by just using two or three angles though, because of a phenomenon called gimbal lock, which more or less means because you'd have to apply the rotations sequentially and there's always going to be an ordering that makes a later axis the same as an earlier one.

On an 8-bit computer the easiest fix is just to keep orientation and position directly as a matrix. You'll then have a few functions to operate on a matrix: rotate it one unit around its own x axis, around its own y axis, around its own z axis, and move it some amount around all of those axes. The former three will just be hard-coded sets of multiplications, plus some sort of precision-error-catching fix-up, the latter will just add multiples of the current axes to the current position.

You might specifically want to look up 'orthonormal' matrices, i.e. those in which the three axes are mutually orthogonal, and are of unit length (that's the 'normal' bit).

For the horizon you can completely ignore viewer position — model the horizon as being at infinite. So you'll just inspect the rotational part of your matrix.

The complete pipeline for a vertex is just: apply matrix to it, project it onto screen by dividing its x and y by z. With some appropriate scaling as per the size of the viewport.

That obviously works correctly only while z > 0 — while the point is in front of the viewer. And you'll more likely test for something like z > 1. You're picking how far back you're pretending the viewer is from the 2d screen. So there's an easy fix for points: don't project unless z > 1.

Lines are supposed to join two points, so you're in trouble if one is at z > 1 and one isn't. There's two solutions here:

• keep objects small and draw them only if the centre of the object is far enough away that no lines will cross z = 1. The object will wholly disappear if you get too close, but usually that means you'd be inside of the object, which gameplay probably doesn't allow anyway; or
• for each line calculate where it crosses z=1 and just draw the portion between there and the vertex for which z > 1. This is what you'd do if you were e.g. drawing large walls within a maze.

There's a correlated question of clipping at screen edges. You can either maintain 16-bit screen coordinates and clip in 2d, or clip before projection by finding a point of intersection analogously to the z=1 example, then project and draw. If you do that then your line drawer never need check whether a pixel is on-screen, which is nice.

For screen edges you'll be looking for boundaries where x = -z, x = z, y = -z, y = z. This is where I did some linear algebra in my version, but now think I should just have used a binary search.

There's a 512-byte lookup-table way to multiple two 8-bit numbers just by adding and subtracting plus a couple of table lookups and a further add. That's so fast that you might want to think about storing all your vectors as unsigned so that you can use the same table for top and bottom parts of e.g. 8x16 multiplies without sign bits getting troublesome. Keep the signs in a separate flags byte and manipulate them separately — e.g. for a signed multiple do the unsigned bit via the table, then just XOR the signs.

Divides are then the only complex maths operation you'll probably have to do live. I actually used a lookup table to turn them into multiplies on the Sam, but that was 64kb in size. The Sam has quite a lot more in memory than it has in processing speed though; I don't think that trade-off works on a Spectrum, even if it is one with more than 64kb of RAM.

Plus point: if you can get a fast 8x8 divide with remainder going then you can look into the run-slicing version of line drawing. Which can be done with perfect pixel precision in a Bresenham-esque fashion, maintaining an error term. You have to pay for the divide but then you'll be working out how many pixels to draw in a row or column before moving to the next, rather than stepping through them one at a time. On a Spectrum that could be a big win when drawing long broadly-horizontal lines as it'll save constantly loading a video byte, setting a single pixel, storing it, reloading it, setting another pixel, storing it, etc.

Even if you do classic Bresenham, it's probably a good idea to implement the horizontal-esque case by accumulating lengths of run and then plotting them rather than going pixel-by-pixel.

Also re: objects rather than points, and precision, it's not uncommon to transform just the centre of the object, check whether the object is anywhere close to on-screen, then look at the depth of the object and only if it is below a certain threshold to continue with the actual points. Games like elite plot a single bit point for objects that are on-screen but too far away to be worth doing in more detail.

Doing that allows you to use much bigger numbers for object centre than for points on an object. E.g. you might have all objects be positioned on a grid that is 16 or 24 bits in each axis, but the points on the object are stored only at 8-bit precision relative to their centre. You save not only storage but transformation time — having transformed the object centre you can just apply the rotational parts of the view matrix to the points (i.e. 8x8 multiplies) and add them to wherever the centre was.

A net route in might be:

• establish multiplications;
• implement matrix to point multiplication;
• try some perspective-free point plotting to test those;
• establish division;
• try perspective projection of your points;
• add line rasterisation and experiment while carefully keeping all your points on-screen;
• implement clipping;
• do whatever you intended to do about object centre versus object-local precision for transformations, and realise that you're largely done.

... and those are just the badly-worded thoughts that spring straight to mind, in an incoherent order. I dare imagine I've left a million things out.

[Art]

Thank you! It looks good. I like the idea about object centres. So, probably multiplication, matrix and point plotting will be a good start for maybe next several months. I should also look at how lookup tables for computing work.

[Tommo]

Ugh, with hindsight I neglected to go into sufficient detail on that multiplication-by-table thing. It's this:

Code: Select all

(x+y)^2 = x^2 + y^2 + 2xy
(x-y)^2 = x^2 + y^2 - 2xy

=> (x+y)^2 - (x-y)^2 = 4xy

Therefore to get x*y you just need a lookup table of f(x) = (x^2)/4; look up f(x+y) and f(x-y) and then get the difference of the results.

Bonus observation: any error you accumulate in that /4 will cancel itself out when you do the final subtraction. So you don't need to store (x^2), do the arithmetic and then shift to divide by four. You can just do it in the table.

[Art]

OK, thank you. It will be interesting.

[chip-fork]

This is for the BBC not Spectrum, but this site about Elite has lots of well written explanations of all the routines.
For example there's one on back face culling. And one on drawing the ships to screen.

https://www.bbcelite.com/deep_dives/

[Art]

Thanks, yes, there are some interesting explanations.

I've already found some routines for point and line drawing, so I am trying to move simple 2D objects.

[Art]

To understand how 3D transformations work, I've made a little test in Basic. Of course it's very slow, so I accelerated the recording, but it works:
http://phoenix.inf.upol.cz/~rachunl/test/cube.mp4

For the time being, I decided to use only Battlezone-style transformations, so finally I found it very simple. There are only two simple calculations, for the x and z coordinates, one lookup table for the 3D to screen projection, and two tables of sin and cos. I can move the point of view forward and backward and rotate left and right. Now I have to convert everything to the assembler code.

[chip-fork]

That's cool! you made impressively rapid progress with this project.

[Art]

Yes, I didn't expect it so soon. I always thought that simulator-style 3D vector graphics were very complicated, but finally it's quite easy. The main challenge for me is its assembler programming, which needs very different thinking in contrast to Basic, and I probably need to learn assembler again, because I was using it many years ago for very simple programs.

By the way those web pages of BBC Elite programming contain very interesting method of 3D computing without sin and cos functions, which is very simple and fast, but it didn't work for me yet. So maybe later.

[Alone Coder]

You can use the 3D engine from Info Guide #13: https://www.pouet.net/prod.php?which=88844
It's open-source and customizable.
Supports both 48K and ATM-Turbo 2.

[Art]

Yes, thank you, the 3D engine from Info Guide 13 is really great and I can look at the code for some ideas, if I will understand it. I would like to understand everything I do about Spectrum flight simulators and I'm not very experienced in this area, so I need to start with something very simple to be comfortable in assembly programming.

[Art]

I can offer you my effort for the Sam Coupé as something of an example that's broadly similar to how you'd go about things on a Spectrum, but I'm not sure about good. The biggest misstep is in the approach taken to line clipping, I think — I'm doing full plane arithmetic when I should have just used a binary search for the intersection point — but all the other areas could also definitely do with work.

In the file matrix.z80s, do you use the same approach which is used in the Spectrum version of Elite?

Lines are supposed to join two points, so you're in trouble if one is at z > 1 and one isn't. There's two solutions here:

• keep objects small and draw them only if the centre of the object is far enough away that no lines will cross z = 1. The object will wholly disappear if you get too close, but usually that means you'd be inside of the object, which gameplay probably doesn't allow anyway; or
• for each line calculate where it crosses z=1 and just draw the portion between there and the vertex for which z > 1. This is what you'd do if you were e.g. drawing large walls within a maze.

There's a correlated question of clipping at screen edges. You can either maintain 16-bit screen coordinates and clip in 2d, or clip before projection by finding a point of intersection analogously to the z=1 example, then project and draw. If you do that then your line drawer never need check whether a pixel is on-screen, which is nice.

For screen edges you'll be looking for boundaries where x = -z, x = z, y = -z, y = z. This is where I did some linear algebra in my version, but now think I should just have used a binary search.

I am still struggling with line clipping on the screen borders and on z=1, so for the time being I just draw the whole object or nothing. So you compute a point of intersection and use it as 3D coordinates of a new end point of the line. I'll try to figure it out. But why x = -z, x = z, y = -z, y = z?

By the way, your video example looks very nice.

[Tommo]

I can offer you my effort for the Sam Coupé as something of an example that's broadly similar to how you'd go about things on a Spectrum, but I'm not sure about good. The biggest misstep is in the approach taken to line clipping, I think — I'm doing full plane arithmetic when I should have just used a binary search for the intersection point — but all the other areas could also definitely do with work.

In the file matrix.z80s, do you use the same approach which is used in the Spectrum version of Elite?

I would be very surprised if not; you've got a 3x3 matrix to describe rotation plus a three-component vector to describe translation. Which is the same thing as having a 4x4 matrix in which the bottom row is implicitly (0, 0, 0, 1), which you apply to coordinates that implicitly have a fourth component of 1.

In terms of dealing with the difference between a camera matrix and and object matrix, you want one to be the inverse of the other. That follows directly from the definition of the problem: you want the object with the object matrix to appear at the origin and unrotated from that camera. So you want the camera matrix to be the inverse.

For an orthonormal matrix, you can get the inverse of the 3x3 bit by just taking the transpose, because of the way that dot products work — you'll get 0 in the product of the matrix and its transpose wherever a column and a row represent vectors that are at right angles, and the 'ortho' bit of orthonormal, i.e. everything at right angles, thereby ensures you'll get 0s everywhere you should in an identity matrix.

The 1s you need will appear every time you're doing the dot product of a vector with itself. That's where the 'normal' bit comes into play — the dot product of a vector with itself is the square of its length. And the vectors are normalised, i.e. of length 1. So the output is 1s.

Then the adjustment you have to make to translation falls out just from writing the result of multiplying out on paper.

Lines are supposed to join two points, so you're in trouble if one is at z > 1 and one isn't. There's two solutions here:

• keep objects small and draw them only if the centre of the object is far enough away that no lines will cross z = 1. The object will wholly disappear if you get too close, but usually that means you'd be inside of the object, which gameplay probably doesn't allow anyway; or
• for each line calculate where it crosses z=1 and just draw the portion between there and the vertex for which z > 1. This is what you'd do if you were e.g. drawing large walls within a maze.

There's a correlated question of clipping at screen edges. You can either maintain 16-bit screen coordinates and clip in 2d, or clip before projection by finding a point of intersection analogously to the z=1 example, then project and draw. If you do that then your line drawer never need check whether a pixel is on-screen, which is nice.

For screen edges you'll be looking for boundaries where x = -z, x = z, y = -z, y = z. This is where I did some linear algebra in my version, but now think I should just have used a binary search.

I am still struggling with line clipping on the screen borders and on z=1, so for the time being I just draw the whole object or nothing. So you compute a point of intersection and use it as 3D coordinates of a new end point of the line. I'll try to figure it out. But why x = -z, x = z, y = -z, y = z?

By the way, your video example looks very nice.

Yes, I compute the point of intersection in 3d space, then project that and draw the line using it. Though, again, I stupidly use linear algebra when I should have just used a binary search, given the lack of hardware divide and multiply.

Anyway, the usual projection formula for a 3d world is:

screen_x = half_width + half_width * x / z
screen_y = half_height + half_height * y / z

i.e. divide by z, then scale up to the number of pixels you want to paint, then put the centre in the centre. You've normally scaled y or x in advance to apply a proper aspect ratio before projection.

So anything where x = z will be at half_width + half_width * 1, i.e. exactly on the right edge of the display. Ditto -x = z will be exactly on the left, and ±y = z will be at the top and bottom.

[Art]

Thank you for the explanation. I think I understand, but I don't know yet how to compute fast the point of intersection with x=z etc., so I tried the 2D line clipping and I'll see later.

But I noticed another problem. As you can see in the following example, I can walk only towards the house, I can't walk in any other direction. When I rotate the scene, it still walks towards the house. And I can see the house only from one side, I can't walk around it or see it from any other angle.

http://phoenix.inf.upol.cz/~rachunl/test/cube2.mp4

I tried to simplify the computation, but probably I simplified it too much, or I made some other mistakes. I only need to walk forward and backward and to rotate left and right, so I used this for every vertex of the house:

x'=x*cos(a)-(z+tz)*sin(a)
y'=y
z'=x*sin(a)+(z+tz)*cos(a)

x,y,z - original 3D coordinates
x',y',z' - transformed 3D coordinates
a - angle of rotation around the y axis
tz - length of translation along the z axis

[Art]

Oh, of course, in this example, I can move only in the z direction. So when I rotate left or right, I can't go forward, because it's not the z direction. For testing, I added also moving in the x and y direction, so I can go around the house, but only in this awkward way:
http://phoenix.inf.upol.cz/~rachunl/test/cube3.mp4

x'=(x+ox+tx)*cos(a)-(z+oz+tz)*sin(a)
y'=(y+oy+ty)*1.33
z'=(x+ox+tx)*sin(a)+(z+oz+tz)*cos(a)

x,y,z - original 3D coordinates
x',y',z' - transformed 3D coordinates
a - angle of rotation around the y axis
ox,oy,oz - 3D coordinates of the centre of the house
tx,ty,tz - length of translation along the x,y,z axis
1.33 - aspect ration correction for the 4:3 screen

So when I rotate left of right, I guess that I need to compute the new forward direction vector tx,ty,tz and add its components to x',y',z'. I hope it won't be too slow. I also tried to play with a 4x4 matrix with combined rotation and translation.

[Art]

So it works. Still in Basic, but I tried to use mostly integer variables without division (or a division by 64 etc.) to prepare it for the assembler, and I prepared several little assembler routines. I still need to figure out how to store and use multiple objects, and still don't know if it's better to move and rotate all vertices of the scene together, or to move and rotate only objects centres and then the objects vertices (if the objects aren't moving, for example buildings).

But before that, I'd like to do a good line clipping at the screen border. I tried a 2D clipping algorithm. I found the Liang-Barsky one and I modified it for the Spectrum. It works very well in Basic, but of course it's slow. In preparation for the assembler I tried to reduce the need of big numbers, floating point and division. But it still needs big numbers, and now its precision is worse even with two-byte integers. You can see that some lines are missing when the house is very near:

http://phoenix.inf.upol.cz/~rachunl/test/cube4.mp4

Maybe I just programmed it badly, I don't know. In any case, when I see many Spectrum games with vector graphics, it's clear that it can be much better.

I'd like to try the 3D line clipping before the 2D projection, but I still don't know how to do it. Maybe it's a better way and maybe it's the only solution for the z=1 clipping. Is there some good explanation anywhere?

Does anybody know which line clipping algorithm for 3D vector graphics is usually used on the Spectrum? Is there any example of it?

[catmeows]

and still don't know if it's better to move and rotate all vertices of the scene together, or to move and rotate only objects centres and then the objects vertices (if the objects aren't moving, for example buildings).

For a bigger scene it is probably better to move and rotate just centres and the clip whole object using bounding sphere or cube. You can use some quick tests like z<constant and depending on your view frustrum maybe some other quick test like z<abs(x)*constant or z<abs(y)*constant to quickly reject objects that are behind you or too much to the left or to the right or too much up or down. If your constant=2^N you can do all computation with bit shifts and simple integer comparison.

But before that, I'd like to do a good line clipping at the screen border. I tried a 2D clipping algorithm. I found the Liang-Barsky one and I modified it for the Spectrum. It works very well in Basic, but of course it's slow. In preparation for the assembler I tried to reduce the need of big numbers, floating point and division. But it still needs big numbers, and now its precision is worse even with two-byte integers. You can see that some lines are missing when the house is very near.

I'm guessing here but it seems to me as a bug rather than issue with precission, clipping on other sides doesn't seem to have issues.

[catmeows]

One thing: I believe something like Cohen-Sutherland clipping could quicky reject or accept some of lines using just comparisons and you could use Liang-Barski for undecided cases only ?