Author Topic: Starion: 3D space battle with impossibly smooth animation. How ?  (Read 5970 times)

0 Members and 1 Guest are viewing this topic.

Offline cpcitor

  • The user previously known as FindYWay
  • CPC6128
  • ****
  • Posts: 299
  • Country: fr
  • My heart still runs on traditional CPC.
    • My code for the CPC.
  • Liked: 148
  • Likes Given: 371
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 :

Quote
So, 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.

Quote
As 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 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.

Offline Gryzor

  • Administrator
  • 6128 Plus
  • *****
  • Posts: 16.082
  • Country: gr
  • CPC-Wiki maintainer
    • CPCWiki
  • Liked: 3493
  • Likes Given: 6293
Wow that's f*cking smooth! Had forgotten about it...

Offline MaV

  • Supporter
  • 6128 Plus
  • *
  • Posts: 1.103
  • Country: at
  • Ius summum saepe summa est malitia.
  • Liked: 400
  • Likes Given: 828
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."

Offline cpcitor

  • The user previously known as FindYWay
  • CPC6128
  • ****
  • Posts: 299
  • Country: fr
  • My heart still runs on traditional CPC.
    • My code for the CPC.
  • Liked: 148
  • Likes Given: 371
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.

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.

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.

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,
« Last Edit: 23:32, 24 October 13 by cpcitor »
Had a CPC since 1985, currently software dev professional, including embedded systems.

I made 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.

Offline TFM

  • Visit the mysteries of the CPC at www.futureos.de
  • Supporter
  • 6128 Plus
  • *
  • Posts: 9.899
  • Country: aq
  • Space Chicken for FutureOS is free!
    • index.php?action=treasury
    • FutureOS - The revolution on CPC!
  • Liked: 1982
  • Likes Given: 4650
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

Offline arnoldemu

  • Supporter
  • 6128 Plus
  • *
  • Posts: 5.336
  • Country: gb
    • Unofficial Amstrad WWW Resource
  • Liked: 2275
  • Likes Given: 3478
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

Offline MaV

  • Supporter
  • 6128 Plus
  • *
  • Posts: 1.103
  • Country: at
  • Ius summum saepe summa est malitia.
  • Liked: 400
  • Likes Given: 828
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é! ;)

Quote
Besides 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.

Quote
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.
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


Quote
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).
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).

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

Quote
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.)
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."

Offline TFM

  • Visit the mysteries of the CPC at www.futureos.de
  • Supporter
  • 6128 Plus
  • *
  • Posts: 9.899
  • Country: aq
  • Space Chicken for FutureOS is free!
    • index.php?action=treasury
    • FutureOS - The revolution on CPC!
  • Liked: 1982
  • Likes Given: 4650
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

Offline arnoldemu

  • Supporter
  • 6128 Plus
  • *
  • Posts: 5.336
  • Country: gb
    • Unofficial Amstrad WWW Resource
  • Liked: 2275
  • Likes Given: 3478

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

Offline TFM

  • Visit the mysteries of the CPC at www.futureos.de
  • Supporter
  • 6128 Plus
  • *
  • Posts: 9.899
  • Country: aq
  • Space Chicken for FutureOS is free!
    • index.php?action=treasury
    • FutureOS - The revolution on CPC!
  • Liked: 1982
  • Likes Given: 4650
Really looking forward to your game!!!
TFM of FutureSoft
Also visit the CPC and Plus users favorite OS: FutureOS - The Revolution on CPC6128 and 6128Plus

Offline MaV

  • Supporter
  • 6128 Plus
  • *
  • Posts: 1.103
  • Country: at
  • Ius summum saepe summa est malitia.
  • Liked: 400
  • Likes Given: 828
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'm intrigued. Can you explain this more specifically? Specifically, what's the trade-off in your solution?
« Last Edit: 17:47, 31 October 13 by MaV »
Black Mesa Transit Announcement System:
"Work safe, work smart. Your future depends on it."

Offline TFM

  • Visit the mysteries of the CPC at www.futureos.de
  • Supporter
  • 6128 Plus
  • *
  • Posts: 9.899
  • Country: aq
  • Space Chicken for FutureOS is free!
    • index.php?action=treasury
    • FutureOS - The revolution on CPC!
  • Liked: 1982
  • Likes Given: 4650
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

Offline MaV

  • Supporter
  • 6128 Plus
  • *
  • Posts: 1.103
  • Country: at
  • Ius summum saepe summa est malitia.
  • Liked: 400
  • Likes Given: 828
Of 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."

Offline TFM

  • Visit the mysteries of the CPC at www.futureos.de
  • Supporter
  • 6128 Plus
  • *
  • Posts: 9.899
  • Country: aq
  • Space Chicken for FutureOS is free!
    • index.php?action=treasury
    • FutureOS - The revolution on CPC!
  • Liked: 1982
  • Likes Given: 4650
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

Offline arnoldemu

  • Supporter
  • 6128 Plus
  • *
  • Posts: 5.336
  • Country: gb
    • Unofficial Amstrad WWW Resource
  • Liked: 2275
  • Likes Given: 3478
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

Offline cpcitor

  • The user previously known as FindYWay
  • CPC6128
  • ****
  • Posts: 299
  • Country: fr
  • My heart still runs on traditional CPC.
    • My code for the CPC.
  • Liked: 148
  • Likes Given: 371
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 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.

Offline TFM

  • Visit the mysteries of the CPC at www.futureos.de
  • Supporter
  • 6128 Plus
  • *
  • Posts: 9.899
  • Country: aq
  • Space Chicken for FutureOS is free!
    • index.php?action=treasury
    • FutureOS - The revolution on CPC!
  • Liked: 1982
  • Likes Given: 4650
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

Offline sigh

  • 6128 Plus
  • ******
  • Posts: 1.283
  • Liked: 576
  • Likes Given: 59
That game looks so incredibly impressive. The code must of been optimized to the max!

Offline arnoldemu

  • Supporter
  • 6128 Plus
  • *
  • Posts: 5.336
  • Country: gb
    • Unofficial Amstrad WWW Resource
  • Liked: 2275
  • Likes Given: 3478
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

Offline arnoldemu

  • Supporter
  • 6128 Plus
  • *
  • Posts: 5.336
  • Country: gb
    • Unofficial Amstrad WWW Resource
  • Liked: 2275
  • Likes Given: 3478
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

Offline ralferoo

  • Supporter
  • 6128 Plus
  • *
  • Posts: 970
  • Country: gb
  • Liked: 583
  • Likes Given: 222
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
« Last Edit: 22:15, 18 December 13 by ralferoo »

Offline arnoldemu

  • Supporter
  • 6128 Plus
  • *
  • Posts: 5.336
  • Country: gb
    • Unofficial Amstrad WWW Resource
  • Liked: 2275
  • Likes Given: 3478
when is your next demo?
My games. My Games
My website with coding examples: Unofficial Amstrad WWW Resource

Offline ralferoo

  • Supporter
  • 6128 Plus
  • *
  • Posts: 970
  • Country: gb
  • Liked: 583
  • Likes Given: 222
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. :(


Offline Gryzor

  • Administrator
  • 6128 Plus
  • *****
  • Posts: 16.082
  • Country: gr
  • CPC-Wiki maintainer
    • CPCWiki
  • Liked: 3493
  • Likes Given: 6293
What I wouldn't give for a CPC core for MiST... ;)

Offline sigh

  • 6128 Plus
  • ******
  • Posts: 1.283
  • Liked: 576
  • Likes Given: 59
I still cant stop looking at this.

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