Doing 3D games on the Oric ?

Want to talks about games you like, would like to see developed on the Oric, it's here.
User avatar
Twilighte
Game master
Posts: 819
Joined: Sat Jan 07, 2006 12:07 am
Location: Luton, UK
Contact:

Post by Twilighte »

Dbug wrote:Something to consider as well is that we are losing about 20% of the whole cpu time due to the crapy IRQ system, which is easy to rewrite for a game purpose.
Absolutely, and all current demos for Wurlde do not use interrupts at all!!
If i could figure out some way of processing sound effects and timed events outside interrupts, i'd not use them. May work on strobing the hardware timers for this.

Back to 3D graphics.. wouldn't this be cool?

Image
Ok, only a mockup but an accurate one at that, using RGB.
One interesting aspect of the game driller (First Freescape game) is that the actual 3D playing area is 256x103. And the above screen is reduced from this to 234x103 yet such a lores still retains most of its character and is easily identifiable for what scene it presents. I think you'll agree the addition of colours makes 3D games much more striking.

I have no real understanding of the feasability of filled 3D polygon graphics on the Oric. Dbug did some work on this culminating in his 3D cube demo.
User avatar
Chema
Game master
Posts: 3013
Joined: Tue Jan 17, 2006 10:55 am
Location: Gijón, SPAIN
Contact:

Post by Chema »

Dbug, it can be twice as fast... mine is not optimized and I saw yours uses self-modifying code to avoid inside-loop checks.

However if figures are correct yours should display over 60 diagonals per second, and that not taking into account overhead due to the C loop and IRQs!

Mine was over 32..., even if it should be quite linear with number of pixels drawn...

And we have not taken special cases such as vertical or horizontal-only lines, or drawing several pixels in a scan and *then* plotting it onscreen...

Anyway it should suffice for wired 3D with hidden faces removal, which is what we need for an Elite Clone.

Anyway clipping is another problem. A projected vertex might end up outside the screen area, but still you need to draw the visible part of the lines ending in that vertex. Either some trick is used, or using also 16-bit (or at least 9-bit) coordinates for all the drawing routines might be a nightmare. Ideas?

I don't like the idea of reducing the screen area (or making pixels bigger) so we have a coordinate system of 64x64 for instance, so we have some room for holding points out of screen in 8-bit values... but surely there is a trick.

The speccy did it and, in some games, with very good frame rates, so why not in an Oric? :)

I played with 3D in the past, but my rotation routines (they rotated the point of view with a polygon on screen) had lots of errors due to the 8-bit math... Even if projection mostly worked.

What I did was using 2 buffers which hold projections of all the vertex. One holded the new values and the other the old values. At each frame lines connecting vertex are drawn for both buffers, thus ereasing the old line and drawing the new one.

The 16-bit multiplication routine I had in hand might not be fast enough. Figures (not calculated by me) are:

Max time taken ($ffff * $ffff) is 661 cycles. Average time is around max time for 8-bit numbers.

Max time taken for 8-bit numbers ($ff * $ff) is 349 cycles. Average time is 143 cycles.

I am not sure if this would suffice, but I'm afraid it won't, as any 3D operation needs several multiplications and always using 16-bit math is much more expensive than using 8-bit.

Chema
User avatar
Chema
Game master
Posts: 3013
Joined: Tue Jan 17, 2006 10:55 am
Location: Gijón, SPAIN
Contact:

Post by Chema »

Ah... one more thing.

In your line routine you are using Dbug's Method of Flood Filling Memory :)

You use at least:
- two 201 tables for pixel address
- three 256 tables for mul6, div6 and mod6
- An additional table of 240 bytes for I don't know what...

which is 1410 bytes of tables! add that to your 711 bytes routine and other minor tables...

I am using just two tables, one of 200 bytes and another of 240, which are used for pixel address (pointer, mod6, and bit inside scan).

But, of course, this means lots of more cycles per loop, even if it is just the jsr/rts and other minor operations...

I wonder if there is any way of mixing these two, to keep the speed while saving memory. Or do you think we can make this expense? Remember we will need at least a sin table and others for fast multiplication (a table of squares, typically, but depend on the algorithm). I fear we end up with using 5K just for drawing lines and make multiplications!

Well, in the end, we can allways put that in overlay and load from disk :)

Some (large) notes about making 3D... This is long but I would like to get some feedback on it... even if it might be confusing at some points.

Everything is based on Vertexes. We need 3 lists of vertex coordinates (16-bit each <x,y,x>) of MAX_VERTEX length... More than 64 vertexes could be too many to deal with.

A polygon is defined by a list of vertex (indexes to the above list), such as
<v1,v2,v3,v4,$ff> ($ff indicating the end of list)

which means "draw a line from v1 to v2, then from v2 to v3, then from v3 to v4 and close it with a line from v4 to v1".

Objects are defined by a list of polygons, e.g.
<number of polygons> <v1,v2,v3,v4,$ff><v5,v6,v7,$ff>...

Converting everything to triangles makes life much easier, but it was not used in Elite (I think) and might increase the number of lines to draw and vertex to move!

3D movement is just applying transformations to sets of vertex. When a ship moves or rotates, only its vertexes are transformed. When the player does this (roll its ship or turn), ALL the vertexes are transformed. Transformations are matrix operations, normally being some multiplications for the value of the sin or cos of the angle and/or some additions/substractions.

Then, at each frame project them over the list of vertex projections. Two buffers (old and new), each one with two (x,y) 16-bit entries per vertex.

Then "simply" draw each object, i.e. get a polygon, calculate if it is hidden or not (more multiplications here) and, if not, draw it line by line.

Another thing that should be done is keeping track of those lines that have already been drawn (as pairs of vertex, which are indexes of 8-bit). Before drawing a line, look if it has been already drawn to skip the process...

Need a good way of storing this information to speed up the search process... I imagine Dbug setting up a matrix of MAX_VERTEX*MAX_VERTEX to implement this :)

This only deals with objects in the scene, and I am avoiding talking about clipping!

In fact we need to keep track of objects out of sight (as they appear on the radar) and "drop" them into the scene when they get in the field of view (and pop them out when they exit the field of view).

I think this is easier, as we just need to know there is an object at 3D coordinates <x,y,z> and deal with its movement and actions (firing, escaping...), BUT also need to apply transformations, as the reference system is usually set up with the player ship as origin.

Maybe this can be skipped, and use a "world" scene with "absolute" 3D coordinates, and change them when the object enters the field of view, but I don't know if there will be problems here...

This is indeed a great challenge! but it was also making an isometric game... even some thought it was impossible :)

If only we could add one of the creators of Elite to this discussion to enlighten us...
User avatar
Dbug
Site Admin
Posts: 4437
Joined: Fri Jan 06, 2006 10:00 pm
Location: Oslo, Norway
Contact:

Post by Dbug »

Chema wrote:Ah... one more thing.

In your line routine you are using Dbug's Method of Flood Filling Memory :)

You use at least:
- two 201 tables for pixel address
- three 256 tables for mul6, div6 and mod6
- An additional table of 240 bytes for I don't know what...

which is 1410 bytes of tables! add that to your 711 bytes routine and other minor tables...
Tss, tss.
Check the code if you plan on commenting on it.
I just used my default initialization routine, half of these tables are not used at all.

Adress tables can be 200 bytes instead of 201 bytes, Mod6, Mul6 and Bit6 are not used at all

The 240 bytes 'Bit6Reverse' table contains the bit position for each possible pixel horizontally. By using that I avoid a modulo 6 operation.

Give a pixel position stored in register X and tmp0 containing the current scanline:

Code: Select all

	ldy _TableDiv6,x
	lda (tmp0),y
	eor _TableBit6Reverse,x
	sta (tmp0),y
The first line get the offset of the byte in the scanline (ie: X divided by 6), the second line get the value in the screen, the third one masks in the current pixel, the last one write it back to screen.

Please not it may be possible to not actually read/mask but just write directly the value to screen. This will result in some corruption if close lines reunites at the same position, but not even sure it will be annoying if the objects are large.
Chema wrote:Or do you think we can make this expense? Remember we will need at least a sin table and others for fast multiplication (a table of squares, typically, but depend on the algorithm). I fear we end up with using 5K just for drawing lines and make multiplications!
What I believe is not in wasting memory, or not wasting memory, but in using all the available memory depending of what needs to be done.
User avatar
Chema
Game master
Posts: 3013
Joined: Tue Jan 17, 2006 10:55 am
Location: Gijón, SPAIN
Contact:

Post by Chema »

Dbug wrote:Tss, tss.
Check the code if you plan on commenting on it.
I just used my default initialization routine, half of these tables are not used at all.
Impressive :) I skimmed through the sources, but was a bit confused. Well you know I allways admired your work... this example perfectly illustrates why :)

[BTW I was joking not critisizing at all! when I saw the benchmark my mouth was open wide]

It is a very quick line routine, we can use it!
What I believe is not in wasting memory, or not wasting memory, but in using all the available memory depending of what needs to be done.
Completely agree. I still have problems when designing with thinking in using tables for everything!

Need to keep this post small. I am currently ill in bed, but will come back next week... (I hope).

Just let me say I have a first proof of concept of the above ideas working... I mean Objects represented by lists of polygons, which are lists of vertex, which are projected... It is quite general.

I have rotations in the screen plane in the three axes and, even if there are many bugs and things to solve (such as hidden face removal, which is currently not working correctly :? ) it is a good start.

I am using 16-bit arithmetic and the commented multiplication routine, which is not very fast. The worst problem now is having a line routine which could do clipping... which might mean dealing with 16-bit coordinates (lines from -10,-10 to 210,10 are partially visible).

There are also aberrations, so also some problems somewhere... in projection, in number precision... no idea.

Cheers.
User avatar
Dbug
Site Admin
Posts: 4437
Joined: Fri Jan 06, 2006 10:00 pm
Location: Oslo, Norway
Contact:

Post by Dbug »

Probably possible to take as an input signed 16 bits coordinates, perform the clipping, and then take the result of the clipping as unsigned 8 bits coordinates.

For the clipping, the usual fast method is to use the cohen & sutherland method. Basically it consists in splitting the coordinates in 9 areas, based on if they are one the left, right, top or bottom of the clipped area, using some binary masking and simple tests.

More indication here: http://gamedev.cs.colorado.edu/tutorial ... erland.pdf

The cool thing is that the trivial cases of completely out and inside are fast to check.

Problem is the interpolation for "cutting" the part which is out of the screen, probably costly to do.

For the rotations, I was using something using only sums of trigonometric constants, and the objects defined only using polar coordinates, but that's kind of tricky to use to do anything decent.

Basically think instead of having an object vertex defined as x,y,z, you have them defined as alpha,beta,distance from the center. Makes it easy to rotate an object like a cube, since the corners are equidistant from the center, but it's hard to move objecst in 3d space using this kind of method because you don't have a global 3d space anymore.

And for me the biggest problem is always the project because of the divisions.
User avatar
Chema
Game master
Posts: 3013
Joined: Tue Jan 17, 2006 10:55 am
Location: Gijón, SPAIN
Contact:

Post by Chema »

Greetings.

Just a note. I have found a couple of very interesting articles about this subject in C=Hacking. They include not only a way to set up a 3D world, but also fast routines for multiplying, projecting and rotating objects.

Some considerations the author makes coincide with what I have already observed in my first tests, so I think we are on the right path, and he provides solutions for most problems!

They deserve an in-depth reading... I will put hands on this as soon as I have some time.

Cheers.

EDIT Just gave it a look. It is very interesting. It has a method for FAST multiplications, while retaining the needed accuracy and bit-length and other matters, such as how to get rid of the divisions when projecting.

However it needs a variation in the approach to objects I am doing. It keeps objects vertices as local coordinates refering to the object center point, so need to keep a rotation matrix for each object where all the movements are... accumulated. Then, if the object is visible, it projects all its vertices after applying this matrix.

I was applying rotations and translations to all vertices each time, which also were refered to the player's ship, so no need to keep track of these and calculations were easier... even if had to be done to ALL vertices.

His approach is better, more general and has many other advantages, so I will switch to it. Problem is I will need time to adapt all the code.

Besides, I need to figure out all the routines from the explanations (I have source code, but it is not complete, need to create tables, change fixed memory locations and translate from another assembler with macros.

This might take time. :(
User avatar
Dbug
Site Admin
Posts: 4437
Joined: Fri Jan 06, 2006 10:00 pm
Location: Oslo, Norway
Contact:

Post by Dbug »

I worked a bit more on the line drawing routine today, and now instead of 856, the bench routine is down to 842. Guess it's possible to improve even more by puting the code in zero page, but then it's starting to be very complicated to use.

If you find a fast way to do a division, without loosing too much accuracy, we can probably do a line routine which is way faster than the current one.

Brensenham incremental algorithm is great because it is all integer, and does not require any division, but if you can afford to do fixed point arithmetic, on a limited screen resolution, then a standard fixed point line drawing is probably more efficient.

Need to test that :)
User avatar
Chema
Game master
Posts: 3013
Joined: Tue Jan 17, 2006 10:55 am
Location: Gijón, SPAIN
Contact:

Doing 3D games on the Oric ?

Post by Chema »

Greetings...

As some of you know I've been working on a 3D engine for the Oric lately. But it is not necessary to reinvent the wheel... so I have converted Stephen Judd's lib3d and obj3d libraries for the C64 to the Oric.

The process was quite easy, once you understood how things are done. This engine is rather powerful and fast, can handle up to 128 objects at the same time (even if many more might exist in the game and the can share shapes) and it is very easy to use (from assembly).

And with the addition of Dbug's marvelous polygon routine (man, you are a genious), I can finally post a small demo.

This demo contains three programs that basically do the same thing: rotate an object along its 3 axes and from time to time move and rotate the point of view (your ship!).

Beware though that clipping is not performed, so if the object gets offscreen somehow, strange things may happen...

The first demo (tetdemo.tap) rotates and moves a simple tetrahedron, so you can see how fast the engine is... Here is an screenshot

Image

You will say, "well it goes quite well, but it is an easy shape... Would you be able to do a game with this?". So I also include the second demo (cobrademo.tap), which does the same thing with a ship similar to the most famous of the game Elite

Image

Okay, okay... some fill patterns are not correctly chosen for each of the 15 faces, but hey... this is a demo...

And, finally, one of the nicest things about the engine. It can handle objects which are not convex... meaning that a face is not either hidden or visible, but can be partially hidden by another polygon. To illustrate this, here is the third demo (shipdemo.tap), with a star-like ship thingy, made up of 20 faces...

Image

Of course you have to run the programs to see how they work. So download the three of them from here:

http://www.defence-force.org/ftp/forum/ ... Ddemo1.zip

Ok I admit that complex objects take longer to draw and even flicker sometimes, but I feel the performance is quite adequate indeed!

As I said it is not an ad-hoc code, but a generic engine, so now who can say it is not possible to do an Elite-like game on our dear Oric?

(maybe the same who said it was not possible to code a Knight Lore-like game on the Oric :) )

Enjoy and, please, post your comments!
Last edited by Chema on Tue Dec 31, 2019 9:53 am, edited 1 time in total.
User avatar
Dbug
Site Admin
Posts: 4437
Joined: Fri Jan 06, 2006 10:00 pm
Location: Oslo, Norway
Contact:

Post by Dbug »

Cool :D
Are you using the latest version I published on the forum ?

And it should be even faster when stopping to refresh the whole screen (thanks to the cockping/gui display :D)
User avatar
Chema
Game master
Posts: 3013
Joined: Tue Jan 17, 2006 10:55 am
Location: Gijón, SPAIN
Contact:

Post by Chema »

Dbug wrote:Cool :D
Are you using the latest version I published on the forum ?

And it should be even faster when stopping to refresh the whole screen (thanks to the cockping/gui display :D)
Yes and YES.

I am using the latest version from the forum. Just nearly off the shelf, with some small adjustments... Only things I don't know how to do are clipping and hidden-face removal (I am using cross-products in these demos).

And we can update just 2/3 of the screen (and even avoid a small frame to draw a rectangle around this area). So it should go even faster...

Cheers.
User avatar
Chema
Game master
Posts: 3013
Joined: Tue Jan 17, 2006 10:55 am
Location: Gijón, SPAIN
Contact:

Post by Chema »

Greetings again...

Some time with loads of work, so little time for Oric.

Anyway I am still playing with this baby. I indeed think we could develop a good 3D space game with the library and Dbug's excellent filler.

As probably we would like to plot planets and suns, I have been playing a bit with a circle drawing routine that could use the filler. For now I have adapted a C algorithm I found on the net to draw filled circles.

The code is:

Code: Select all

void circlePoints(int cx, int cy, int x, int y)
    {
        if (x == 0) {
            MinX[cy+y]=cx;
            MaxX[cy+y]=cx+1;
            MinX[cy-y]=cx;
            MaxX[cy-y]=cx+1;
            MaxX[cy]=cx+y;
            MinX[cy]=cx-y;
   
        } else 
        if (x == y) {
            MaxX[cy+y]=cx+x;    
             MinX[cy+y]=cx-x;
             MaxX[cy-y]=cx+x;
             MinX[cy-y]=cx-x;        
        
        } else 
        if (x < y) {
            MaxX[cy+y]=cx+x;
            MinX[cy+y]=cx-x;
            MaxX[cy-y]=cx+x;
            MinX[cy-y]=cx-x;
            MaxX[cy+x]=cx+y;
            MinX[cy+x]=cx-y;
            MaxX[cy-x]=cx+y;
            MinX[cy-x]=cx-y;
        }
    }

void circleMidpoint(int xCenter, int yCenter, int radius)
    {
        int x; 
        int y; 
        int p; 

        x=0;
        y=radius;
        p= (5 - radius*4)/4;
        
        PolyY0=yCenter-radius;
        PolyY1=yCenter+radius+1;

        circlePoints(xCenter, yCenter, x, y);

        while (x < y) {
            x++;
            if (p < 0)
            { 
                p += 2*x+1;
            }
            else 
            {
                y--;
                p += 2*(x-y)+1;
            }
            circlePoints(xCenter, yCenter, x, y);
        }
    }
It seems quite fast, even if it should be converted to asm, and optimized, of course.

We will have trouble with starfields, as stars will "jump" or appear/disappear while the filler draws odd/even lines at each frame. I have checked it and it does not work quite well. For planets it is more reasonable, even if looks a bit strange.

Worst problem is (as usual) how to include clipping, as it will slow things down and will make us work with 16-bit coordinates.

Also something is wrong when mixing this and the library, as the result is buggy (for loops stop working and other strange behaviours). I think it is because the library is not intended to work with C and makes use of the zero page without taking care...

Cheers.
User avatar
Dbug
Site Admin
Posts: 4437
Joined: Fri Jan 06, 2006 10:00 pm
Location: Oslo, Norway
Contact:

Post by Dbug »

Why not reuse the disc drawing routine you got for the intro of space 1999 ?
You have a fully working disc drawing routine, all you need is to remove the "pattern" masking in the scanline drawing code :)
User avatar
Chema
Game master
Posts: 3013
Joined: Tue Jan 17, 2006 10:55 am
Location: Gijón, SPAIN
Contact:

Post by Chema »

Dbug wrote:Why not reuse the disc drawing routine you got for the intro of space 1999 ?
You have a fully working disc drawing routine, all you need is to remove the "pattern" masking in the scanline drawing code :)
Ah yes, well I did not understand a line of code of that routine... but indeed it is in my mind. However the need of turning to 16-bit coordinates and clipping is a must for discs and polys... :roll:
User avatar
Chema
Game master
Posts: 3013
Joined: Tue Jan 17, 2006 10:55 am
Location: Gijón, SPAIN
Contact:

Post by Chema »

Greetings again.

Having the clipped line routine at hand I could setup a bunch of objects in the 3D world and create a demo where you can move (in all the 3D directions and rotations) the point of view, while the objects rotate along their 3 axes.

It works quite well, despite using the double buffer. Frame rate is low but not unusable IMHO.

I have also worked a bit on the radar display. It was trickier than I expected, but now I have a radar which can be plotted over the viewscreen and easy to change its inclination, position and size. It does not display the circles yet and also should go on the bottom position of the screen, where the Elite radar is placed.

However, even if it is easy to place it at the correct position, I need some time. I should either use another double buffer to update it, or some kind of eor drawing (with all the inconvenience). Need to think about it. But keeping it where it is now is not possible once we switch to filled polys.

In the meantime here is an screenshot with five objects: one is visible and the other four are at the furthest corner positions possible while still in range of the radar, to have an approximated idea of its maximum size.

Image

The radar center is not shown, and it seems quite easy to add things such as objects that do not display on the radar (ECM-equipped ships, for instance).

Cheers.
Post Reply