avatar_cpcitor

Starion: 3D space battle with impossibly smooth animation. How ?

Started by cpcitor, 23:43, 20 October 13

Previous topic - Next topic

0 Members and 1 Guest are viewing this topic.

cpcitor

Hello,

Starion always standed out (at least in my experience) from other 3D programs. (At that time I knew Elite, 3D StartStrike, Starglider and a few others.)

Its appears to immerse the player in a consistently displayed 3D world with an animation that is impossibly smooth.
Granted, the world is simpler than in games mentioned above and actually fairly small, but the animation !

Starion is mentioned a few times on CPCWiki forums. From a programmer's perspective :

The reason of this thread is about the rest of the programming. Clearing the screen quickly is not enough.  :D.

Last link above says :

QuoteSo, how's it done? Well, briefly, they're constructed using SINE tables to calculate the perspective and to give the illusion of depth. Perhaps the space-ships look a little squashed from some angles and the point of infinity is pitched a little close owing to the compact size of the programmer's universe, but these are minor criticisms.

Sine/cosine tables were somehow to be expected anyway.

QuoteAs for the 3D shapes, they're all constructed in high memory and transferred onto the screen using another version of the Stack method. In fact, he uses nearly all the alternate registers except for the two HL pairs.

This is not very clear. And although this article says the MSX version does not flicker, the CPC version does flicker a bit but it is completely acceptable IMHO.

Anyone already investigated further how David Webb wrote that ?

PS: In case you wish to play it again, you can find the list of unscrambled words and matching dates in The Tipshop and the final password http://cpcrulez.fr/forum/viewtopic.php?&f=10&t=3300 .
Had a CPC since 1985, currently software dev professional, including embedded systems.

I made in 2013 the first CPC cross-dev environment that auto-installs C compiler and tools: cpc-dev-tool-chain: a portable toolchain for C/ASM development targetting CPC, later forked into CPCTelera.

Gryzor

Wow that's f*cking smooth! Had forgotten about it...

MaV

I'm not partial to Starion. The animation is smooth but the wire-frames look too distorted. I suspect the point of infinity for the perspective is too close to the viewer, since the far side of the wire frames look much too small in comparison to the parts that are closer to the viewer. The best example is the ship itself when it is rotating in the main menu (I think).
I assume that was also done to avoid hidden line removal (HLR) which is a bit costly, and to up the number of vertices. Proof of that is the complex wireframe of the ship.

3D Starstrike has done a better job but still has the problem that without HLR, it is up to the viewer to discern which points are far away to establish a sense of perspective. Point of proof, look away then back at the screen and see how quickly you figure out the object's position in 3D space.

The one game that did this right is Starglider (and thus arguably all games with proper surface rendering like Starstrike II and the games by Incentive software).


The article mentions some techniques (stack method, sin/cos tables) which may have been new and not well-known in '85/'86, but I guess they can be called trivial today. I don't know anything about "high memory" on the ZX Spectrum but it is safe to assume that this is nothing new.

Black Mesa Transit Announcement System:
"Work safe, work smart. Your future depends on it."

cpcitor

Quote from: MaV on 12:30, 24 October 13
I'm not partial to Starion. The animation is smooth but the wire-frames look too distorted. I suspect the point of infinity for the perspective is too close to the viewer, since the far side of the wire frames look much too small in comparison to the parts that are closer to the viewer. The best example is the ship itself when it is rotating in the main menu (I think).
I assume that was also done to avoid hidden line removal (HLR) which is a bit costly, and to up the number of vertices. Proof of that is the complex wireframe of the ship.

I have different explanations for the defects in Starion, nothing to do with hidden line removal.

Focal length

When doing 3D computation rigorously you have to know the distance between the screen and the viewer's eyes.
In photography it's called the focal length, see http://en.wikipedia.org/wiki/Focal_length#In_photography .

In practice it is unknown and variable as you move your head. Instead, a constant number is used.

Small focal length

What you describe is the result of choosing a too small constant.
The picture below illustrates. The satellites have very different apparent sizes due to the choice of a small focal length.
Besides this, the shapes are mathematically correct, in the sense that the program uses correct 3D projection equations, not crude approximations.

[attachimg=1]

Why small focal length

There is a common reason for choosing a small constant: it creates a more dramatic, deeper sense of perspective.
When really too small, it feels like you write.

Other defects: irregular shapes and motion, too long lines missing.

When playing to make the attached screenshots, I noticed something in Starion.

When really close to the rotating planet, the rotating motion of satellites becomes somewhat irregular.
When really close to a letter, its shape is sometimes slightly distorted.

My guess is that choosing a small number allows to conceal the limited precision of 3D computation, or of some table (e.g. division or sine) used.

The small focal length, by increasing impression of depth, also allows not to feel how the world is small. The enemy spaceship is never very far actually.

Also, when really close to some object, e.g. time warp, lines extending outside the screen disappear. Example below: first image is correct, second misses rightmost edge of pentagonal shape.

[attachimg=2][attachimg=3]

The planets are actually very small objects, so coming close to them magnifies the rounding errors.

My conclusion is that very probably, Starion is optimized to death with a great mastery of computation, precision and error propagation, and with good compromises between game parameters (focal length, world size, etc) to make limited-precision and high-speed computation viable.

Quote from: MaV on 12:30, 24 October 13
3D Starstrike has done a better job but still has the problem that without HLR, it is up to the viewer to discern which points are far away to establish a sense of perspective. Point of proof, look away then back at the screen and see how quickly you figure out the object's position in 3D space.

Yes, I noticed that.

Quote from: MaV on 12:30, 24 October 13
The one game that did this right is Starglider (and thus arguably all games with proper surface rendering like Starstrike II and the games by Incentive software).

Yes, from memories Starglider had good geometry.

Elite had hidden line removal (within an object only, no handling of superposition of objects) which make a good rendering, too. The framerate was good for an 8-bit and the feeling of an actual immense universe made Elite a great game (though very hard to start with, so easy to wreck your ship on space station entry).

All those don't have the incredible framerate of Starion, hence my conclusion above.

Quote from: MaV on 12:30, 24 October 13
The article mentions some techniques (stack method, sin/cos tables) which may have been new and not well-known in '85/'86, but I guess they can be called trivial today. I don't know anything about "high memory" on the ZX Spectrum but it is safe to assume that this is nothing new.

Yes, that's why I created this thread in the first place: to see if someone had already done some analysis (which I'm not planning to do.)

Regards,
Had a CPC since 1985, currently software dev professional, including embedded systems.

I made in 2013 the first CPC cross-dev environment that auto-installs C compiler and tools: cpc-dev-tool-chain: a portable toolchain for C/ASM development targetting CPC, later forked into CPCTelera.

TFM

Well... imho ... Starglider is superior and would be even better on 128 KB.
TFM of FutureSoft
Also visit the CPC and Plus users favorite OS: FutureOS - The Revolution on CPC6128 and 6128Plus

arnoldemu

I am finding that with my 3d, the range of the fixed point values was a problem, and also underflow/overflow is always a big problem too. This is always the case with fixed point maths.

I have to use integers for my world to give enough range - I use blender to place the rings and a python script to generate the data for the game.

I need to use fixed point for rotations to make them smoother, but if I use too many bits I get overflow.

For my 3d I don't clear the screen. I draw black lines over the lines I drawed before - same method as Elite does on the BBC. If you always draw using the same function, draw from the same coordinates then your line draw code will draw over the top always.

I have a table of fixed point values for the perspective calculation (focal length). The focal length is fixed, but it is the same for most 3d games including the new ones.

The problem normally comes when they use too wide a angle of view. The image becomes distorted like looking through an old glass fish bowl.

You have to use close to 60 degrees total. 45 is a bit easier because the perspective then comes closer to a simple shift instead of a divison (or more, a multiplication of a fixed point fraction).

I have a couple of problems with my 3d that I need to resolve before I can release the game.

One is the speed of drawing the lines. I need to make this much faster - i am working on something.
Another is I need to make the anaglyph mode better - there is not enough depth at this time.

But I will fix these for sure.

For 3d you also have to do line clipping too.

So there is a lot to do and process to make a 3d line or 3d filled game.

My games. My Games
My website with coding examples: Unofficial Amstrad WWW Resource

MaV

Quote from: cpcitor on 23:29, 24 October 13
Focal length

When doing 3D computation rigorously you have to know the distance between the screen and the viewer's eyes.
In photography it's called the focal length, see http://en.wikipedia.org/wiki/Focal_length#In_photography .

In practice it is unknown and variable as you move your head. Instead, a constant number is used.

Small focal length

What you describe is the result of choosing a too small constant.
The picture below illustrates. The satellites have very different apparent sizes due to the choice of a small focal length.
Touché! ;)

QuoteBesides this, the shapes are mathematically correct, in the sense that the program uses correct 3D projection equations, not crude approximations.
I do not doubt that. If they were approximations, you'd experience a lot of errors, and the game would be unplayable.

QuoteAlso, when really close to some object, e.g. time warp, lines extending outside the screen disappear. Example below: first image is correct, second misses rightmost edge of pentagonal shape.
Taking your images as examples, it could be that the clipping algorithm disregards all lines when both vertices of a line are out of the field of sight, as is the case in the right image. As soon as at least one vertex is within the viewport the line(s) is/are drawn. I need to play the game again with more examples of this to see if my assumption is correct (currently at work, do not know when I'll have time).


Quote
My conclusion is that very probably, Starion is optimized to death with a great mastery of computation, precision and error propagation, and with good compromises between game parameters (focal length, world size, etc) to make limited-precision and high-speed computation viable.
I second the first part.  But in my POV the compromises are not good, since it leads to a distorted look. Starglider has done a better job. And that's the point where HLR jumps in. It's much better IMO to trade off a bit of speed and show an object without having lines visible that should not be so (which is unrelated to focal length).
I think that is our misunderstanding here, and it is entirely a matter of taste.
Starion is still a masterpiece, no doubt.

Here's an interview with David Webb:
ZX Spectrum Games: Spectrum Games - Programmer Interview - David M Webb

In question 9 he expounds on the stack technique used in Starion. The answer to question 10 explains his affinity for 3d graphics (math exam).

The two books mentioned in the interview are available in pdf on:
http://www.worldofspectrum.org/infoseekpub.cgi?regexp=^David+M.+Webb$&loadpics=1


QuoteYes, from memories Starglider had good geometry.

Elite had hidden line removal (within an object only, no handling of superposition of objects) which make a good rendering, too. The framerate was good for an 8-bit and the feeling of an actual immense universe made Elite a great game (though very hard to start with, so easy to wreck your ship on space station entry).
Starglider also does HLR on one object only. You can clearly see that on the tanks for example, where the vehicle and the gun are separate objects. Viewed from a lower position you can see that the lines of the gun are not removed when the vehicle should hide part of it. Also the moving parts of the walkers and the flying vehicles are separate objects, neither of those objects's lines are removed when the two objects overlay each other (though each object by itself has HLR).

QuoteAll those don't have the incredible framerate of Starion, hence my conclusion above.
No doubt, Starion has the highest framerate of them all!

QuoteYes, that's why I created this thread in the first place: to see if someone had already done some analysis (which I'm not planning to do.)
I may look deeper into the code in the future. There's a bit of a problem though: The topic is demanding and reverse engineering 3D graphics in assembly very arduous.

Black Mesa Transit Announcement System:
"Work safe, work smart. Your future depends on it."

TFM

Quote from: arnoldemu on 11:36, 25 October 13
For my 3d I don't clear the screen. I draw black lines over the lines I drawed before.


Use a routine which puts whole &00 bytes in the V-RAM instead of drawing a line, you will get a BIG speed up that way. You can basicly use the draw routine's algorithm, but won't need to mask pixel.



TFM of FutureSoft
Also visit the CPC and Plus users favorite OS: FutureOS - The Revolution on CPC6128 and 6128Plus

arnoldemu

Quote from: TFM on 19:22, 25 October 13

Use a routine which puts whole &00 bytes in the V-RAM instead of drawing a line, you will get a BIG speed up that way. You can basicly use the draw routine's algorithm, but won't need to mask pixel.
nice idea, I'll give it a go.
My games. My Games
My website with coding examples: Unofficial Amstrad WWW Resource

TFM

TFM of FutureSoft
Also visit the CPC and Plus users favorite OS: FutureOS - The Revolution on CPC6128 and 6128Plus

MaV

Quote from: arnoldemu on 11:36, 25 October 13For my 3d I don't clear the screen. I draw black lines over the lines I drawed before - same method as Elite does on the BBC. If you always draw using the same function, draw from the same coordinates then your line draw code will draw over the top always.
I'm intrigued. Can you explain this more specifically? Specifically, what's the trade-off in your solution?
Black Mesa Transit Announcement System:
"Work safe, work smart. Your future depends on it."

TFM

Clearing a whole screen costs you about 1.63 Frames in the quickest way. While erasing few objects [nb]a technique I use for Cyber Chicken[/nb] or few lines[nb]Arnoldemu uses for his game[/nb] can be done in a part of a FRAME. When done smart: 3D can work at 50 fps. [nb]Of course there is a point when the number of objects reach a threshold and you break down to 25 fps.[/nb]
TFM of FutureSoft
Also visit the CPC and Plus users favorite OS: FutureOS - The Revolution on CPC6128 and 6128Plus

MaV

Quote from: TFM on 18:08, 31 October 13Of course there is a point when the number of objects reach a threshold and you break down to 25 fps.
And that's the point I'm most interested in. I've been pondering the same solution - only clear what you need to clear - and I'm searching for one with the smallest trade-off. :)
Black Mesa Transit Announcement System:
"Work safe, work smart. Your future depends on it."

TFM

That depends what you like to do. Solid objects? Lines? Wireframe?


As rule of the tumb you can say, UNdraw what you did draw before, an don't bother to erase a bit "more" if it allows you to get faster (by pushing bytes instead of points f.e.).

TFM of FutureSoft
Also visit the CPC and Plus users favorite OS: FutureOS - The Revolution on CPC6128 and 6128Plus

arnoldemu

Quote from: MaV on 18:31, 31 October 13
And that's the point I'm most interested in. I've been pondering the same solution - only clear what you need to clear - and I'm searching for one with the smallest trade-off. :)
I've not really compared different methods yet so I can't say.

So, when i draw, I remember the coordinates of each line. I then process that before drawing new lines.
I keep 2 lists because I am double buffering.

25fps would be great ;) Perhaps when I've got my better line drawing working.



My games. My Games
My website with coding examples: Unofficial Amstrad WWW Resource

cpcitor

Interesting.

So you're still doing bresenham twice.
How about doing it only once and remember the list of bytes affected by the lines ?
To erase just write 0 to the list of affected bytes.
Are there proven circumstances where not doing Bresenham + pixel to bytes conversion is faster ?
Had a CPC since 1985, currently software dev professional, including embedded systems.

I made in 2013 the first CPC cross-dev environment that auto-installs C compiler and tools: cpc-dev-tool-chain: a portable toolchain for C/ASM development targetting CPC, later forked into CPCTelera.

TFM

Quote from: cpcitor on 20:43, 31 October 13
How about doing it only once and remember the list of bytes affected by the lines ?
To erase just write 0 to the list of affected bytes.


That's what I suggested before. But managing lists can be tedious and time consuming. In reality (at least here in TFM's lab) it works best when using custom "line eraser routines". That system works even better for sprites and shapes.

TFM of FutureSoft
Also visit the CPC and Plus users favorite OS: FutureOS - The Revolution on CPC6128 and 6128Plus

sigh

That game looks so incredibly impressive. The code must of been optimized to the max!

arnoldemu

Quote from: cpcitor on 20:43, 31 October 13
Interesting.

So you're still doing bresenham twice.
How about doing it only once and remember the list of bytes affected by the lines ?
To erase just write 0 to the list of affected bytes.
Are there proven circumstances where not doing Bresenham + pixel to bytes conversion is faster ?
yes I do bresenham twice. Once to draw, and once to erase.

Yes I could store off the list of bytes, but because I am double buffering I would need two lists and that is going to be quite a problem with ram. It would slow down the draw but speed up the erase.

I could store the rectangle that bounds the line and clear that. That would also work, but lots of wasted bytes to erase.

Another possibility is to split the screen into 8x8 tiles, and based on the equation mark off the blocks that are dirty and just erase those, it would take less ram I think than storing the bytes I modified.

hmmm.. I will try by storing the bytes and see how much ram/time tradeoff I get.
My games. My Games
My website with coding examples: Unofficial Amstrad WWW Resource

arnoldemu

Quote from: cpcitor on 20:43, 31 October 13
Interesting.

So you're still doing bresenham twice.
How about doing it only once and remember the list of bytes affected by the lines ?
To erase just write 0 to the list of affected bytes.
Are there proven circumstances where not doing Bresenham + pixel to bytes conversion is faster ?
another possibility is to do a modified bresenham which is a bytewise low resolution version.
My games. My Games
My website with coding examples: Unofficial Amstrad WWW Resource

ralferoo

Sugarlumps does bresenham in two halves and has a tripled buffered display list and double buffered screen.

At any given time, it's displaying frame Dn and drawing into Dn+1 from the display list Ln+1. As the inner loop of bresenham can be written to take a fixed number of cycles, this can be done during the visible portion of the screen where I need to be cycle counting anyway in order to change the CRTC registers regularly.

In the top and bottom border when timing isn't important, it's calculating the display list for Ln+2 which is when it precalculates the deltas and total iterations of the loop per line. It stores these parameters in the Ln+2 list and makes a copy in the Ln+3 list so that those pixels are erased on the frame after they're drawn.

Ironically, sugarlumps was designed to be a 3D engine and even though I wrote my filled polygon code, I actually barely used that in the demo and mostly did 2D effects instead...  :-[

Source: ralferoo/sugarlumps · GitHub

EDIT: actually, I just released I posted some information about this already and I don't actually double buffer the screen, I carefully time drawing it over 2 frames such that it never tears: Sugarlumps demo

arnoldemu

My games. My Games
My website with coding examples: Unofficial Amstrad WWW Resource

ralferoo

I don't know, I have nothing in the works at the moment - I'm spending some time doing bits and bobs to my FPGA emulator when I can get some free time... and that's sadly quite limited at the moment. :(


Gryzor


sigh

I still cant stop looking at this.

I'm thinking - Wing Commander.......

Powered by SMFPacks Menu Editor Mod